| Latest revision |
Your text |
| Line 1: |
Line 1: |
| | {{comic | | {{comic |
| | | number = 1270 | | | number = 1270 |
| − | | date = September 27, 2013 | + | | date = September 26, 2013 |
| | | title = Functional | | | title = Functional |
| | | image = functional.png | | | image = functional.png |
| Line 8: |
Line 8: |
| | | | |
| | ==Explanation== | | ==Explanation== |
| − | [[White Hat]] questions [[Cueball]]'s faith in {{w|functional programming}}. [[Cueball]] responds saying, "Tail recursion is its own reward."
| + | {{incomplete|if that's the recursion pun I think it is, Randall needs a caning.}} |
| | | | |
| − | {{w|Functional programming}} is a paradigm of computer programming with roots in {{w|Lambda Calculus}}. Core tenets of functional languages often include: function application and composition, declarative syntax, immutable data structures, and mathematically pure functions. Functional programming often uses {{w|Recursion (computer science)|recursive functions}} to serve the same purpose that loops serve in other programming languages. A recursive function calls itself again, typically with slightly different arguments. E.g., the following {{w|Factorial|factorial function}} is recursive because it calls itself again for any argument value n greater than 0. | + | '''TL;DR:''' After [[White Hat]] questions his faith in {{w|functional programming}}, [[Cueball]] says that "tail recursion is its own reward." This implies the equivalent sentence "tail recursion is an end unto itself," and that's where the pun lies. Tail recursion refers to when a function finishes by going back and calling itself, forming a loop. If you aren't groaning by now, read on. |
| | | | |
| − | factorial(n):
| + | Recursion refers to functions that invoke themselves at some point to perform a smaller part of their computation - except where the task at hand is simple enough not to require it. |
| − | if n == 0:
| |
| − | return 1
| |
| − | return n * factorial(n-1)
| |
| | | | |
| − | {{w|Tail call|Tail recursion}} is a particular sort of recursion that often compiles into more efficient code (see the longer explanation below), but the differences between tail recursion and other sorts of recursion aren't important to the humor of this comic. | + | For example, the {{w|factorial}} function has a recursive definition: |
| | | | |
| − | The comic is a pun on two readings of "Tail recursion is its own reward". The expression "X is its own reward" often is used to suggest that X is {{w|intrinsic value (ethics)|intrinsically valuable}} in its own right. Some (but not all) programmers and mathematicians find recursive functions elegant and intrinsically pleasing, so would take tail recursion to be its own reward in this sense. Since recursive functions call themselves again, and make use of the resulting values, there is also a sense in which recursive functions also serve as their own "reward" - i.e., the recursive function itself returns the values that the function requires to perform its tasks. So even if you don't find tail recursion intrinsically pleasing, there is still this technical sense in which it is its own reward anyway.
| + | factorial(n) = 1 if n = 0 |
| | + | factorial(n) = n * factorial(n - 1) if n > 0 |
| | | | |
| − | The title text is humorous in part because it violates two expectations. First, expressions of the form "X combines some trait of Y with some trait of Z" usually talk about combining traits of two different things (i.e., Y is not equal to Z) whereas this text surprises the reader by having "abstract mathematics" occupy the role of both Y and Z. And second, such expressions usually list two positive traits. The first listed trait (the "flexibility and power of abstract mathematics") is pretty clearly positive. However the second trait (the "intuitive clarity of abstract mathematics") is less clearly positive. Many people actually find abstract mathematics to be quite lacking in intuitive clarity, and for much the same reasons many people often find functional programming also to be lacking in intuitive clarity. So the title text invites the reader to puzzle over whether it really is a positive thing for functional programming to be able to claim to match the "intuitive clarity of abstract mathematics", or whether [[Randall]] might instead have just smacked functional programming with a funny {{w|backhanded compliment}}. Another explanation is that the fact that that part of the title text is confusing is a metaphor for the fact that abstract mathematics and functional programming can be confusing, and the first part of the title text is flexible because it can be applied to a wide variety of situations with different things filling in the blanks for X, Y, and Z, and it's apparently powerful because it's used in marketing a lot,{{Citation needed}} so advertisers must feel that it will have a powerful effect.
| + | which can be coded as: |
| | | | |
| − | ===Further explanation=== | + | factorial(n): |
| − | Functional programming is a famous paradigm (or style) in modern programming that favors functions that can be evaluated like mathematical functions, i.e., functions are "evaluated" (executed) to return a value (their output) which exclusively depends upon the values of their arguments (their inputs). {{w|imperative programming|Imperative programs}}, by contrast, often make use of one or more variables that are external to the function that is currently executing. This means that an "imperative function" may return a different result for the same input due to changes in a non-local variable, whereas a "pure function" will ''always'' return the same result for a given input; however, in practice some functional programming languages also support non-local variables.
| + | if n == 0: |
| | + | return 1 |
| | + | else: |
| | + | return n * factorial(n - 1) |
| | | | |
| − | Additionally, for similar reasons, functional programming systems often strive to eliminate or at least rigorously encapsulate (contain) so-called "side effects"; i.e., "functional-style" functions should have absolutely no effect on anything ''other than'' their return value. This is to say, in well-designed "functional-style" computer code, all functions, or as many as is practicable, should be stringently self-contained, their behaviour should depend entirely and exclusively upon their written definition and the values of their arguments, and they should be totally unable to affect anything else in the program except via their explicit return value.
| + | {{w|Tail recursion}} refers to a recursive function whose final operation is to invoke the function itself - crucially with no subsequent computation involved. This means that instead of pushing each level of recursion onto the stack, the compiler can simply arrange for the recursive call to jump to the start of the function with the new parameters - effectively turning a recursive call into an iterative loop, whilst retaining the simplicity of a recursive call. |
| | | | |
| − | This is directly contrary to the imperative programming paradigm, where functions are often designed and invoked especially for some ulterior effect that will eventuate when they are executed; some "imperative-style" functions even have ''no return value'', and exist purely because running them is known to cause some other desired result. In functional programming, these are not considered functions at all, but rather "procedures", and the difference between functions and procedures is quite strong; some languages which are purely functional do not admit procedures as valid parts of the language at all.
| + | The efficiency and elegance are the literal rewards of tail recursion. |
| | | | |
| − | Unlike {{w|Procedural programming|procedures}}, functions always return a value. For example, {{w|Sine|sine(x)}} returns 1 when x is 90°. Furthermore, the function may call itself (usually with slightly different parameters), thus effectively starting a loop. This is called {{w|Recursion (computer science)|recursion}}.
| + | The {{w|greatest common divisor}} function can be coded as: |
| | | | |
| − | In order to {{w|Iteration|iterate}}, imperative programs usually use {{w|Loop (programming)|loops}}. Functional programs usually use recursion instead.
| + | gcd(a, b): |
| − | | + | if b == 0: |
| − | For example, the {{w|factorial}} function (e.g. "factorial(5) = 5 x 4 x 3 x 2 x 1") can be coded imperatively as:
| + | return a |
| | + | else: |
| | + | return gcd(b, a % b) |
| | | | |
| − | factorial(n):
| + | Here, the recursive call to gcd is tail recursive since its the last step of the function. |
| − | prod = 1
| |
| − | while n > 0:
| |
| − | prod = prod * n
| |
| − | n = n - 1
| |
| − | end
| |
| − | return prod
| |
| | | | |
| − | An imperative, recursive (but not tail-recursive) implementation can look like this:
| + | The first example is not tail recursive because the multiplication cannot be evaluated until after its right operand has been calculated. This next example performs its multiplication before the final step - the recursion - and is, thereby, tail recursive. |
| | | | |
| − | factorial(n): | + | factorial2(n, acc): |
| − | if n > 0: | + | if x == 0: |
| − | return n * factorial(n-1) | + | return acc |
| | else: | | else: |
| − | return 1 | + | return factorial2(n - 1, n * acc) |
| − | | |
| − | In this situation, the recursion stops when the argument (n) is not greater than zero. Without the conditional definition, it would be an infinite loop. {{w|Tail recursion}} is a special case of recursion whose very '''last''' operation is to invoke the function itself or return a definite value. The previous example is not tail-recursive, since after the call to "factorial(n-1)", the returned value has to be multiplied by n.
| |
| − | | |
| − | This (functional) example is tail recursive inside the helper function:
| |
| − | | |
| − | factorial(n) = factorial_helper(n, 1)
| |
| | | | |
| − | factorial_helper(n, prod) = | + | factorial(n): |
| − | if n > 0 then | + | return factorial2(n, 1) |
| − | factorial_helper(n - 1, prod * n)
| |
| − | else
| |
| − | prod
| |
| − | | |
| − | e.g.
| |
| − | factorial(5) = factorial_helper(5, 1)
| |
| − | factorial_helper(5,1) = factorial_helper(5-1, 1*5)
| |
| − | factorial_helper(4,5) = factorial_helper(4-1, 5*4)
| |
| − | factorial_helper(3,20) = factorial_helper(3-1, 20*3)
| |
| − | factorial_helper(2,60) = factorial_helper(2-1, 60*2)
| |
| − | factorial_helper(1,120) = factorial_helper(1-1, 120*1)
| |
| − | factorial_helper(0,120) = 120
| |
| − | | |
| − | In functional programming, tail recursion is detected by the compiler or interpreter and can be executed as efficiently as loops in imperative programming languages. This makes tail recursion an essential programming technique in functional programming.
| |
| | | | |
| − | Cueball is making a play on words where "Tail recursion is its own reward" is used both in the sense that it is worth doing on the grounds of being elegant and intellectually satisfying alone, without the programmer having to "actually get" anything from it, as well as in the sense that the 'tail call' of a function is its final step, and is the final step (and hence the result/reward) for ''all levels'' of a tail-recursive function.
| + | The technique used here is to use a helper function with an additional argument called an accumulator which will accumulate results from previous calls to the function. It is often used to implement tail recursive or iterative versions of recursive functions. This is not applicable for all recursive functions, though. |
| | | | |
| − | The title text suggests that to {{w|Abstract mathematics|the mathematically minded}} functional programming may be both powerful and flexible as well as intuitive and clear since it very closely approximates the way mathematicians ordinarily think about general recursive functions. The implicit humorous contrast is that, to many (possibly most) others, including many software engineers, functional programming can seem abstruse or highly unobvious for the exact same reason, ''because'' it closely approximates abstract mathematical logic rather than the mechanistic, stepwise logic valued in the imperative programming style. It is also a reference to a common saying among functional programmers about the imperative programming language, 'C': "C combines the flexibility and power of {{w|assembly language}} with the user-friendliness of assembly language", which is a humorous take on the original saying "C combines the flexibility and power of {{w|assembly language}} with the user-friendliness of a high-level language".
| + | Cueball is making the pun that "(functional programming) is an end unto itself", which would be both figuratively and literally correct. |
| | | | |
| | ==Transcript== | | ==Transcript== |
| − | :[White Hat stands behind Cueball, who is sitting at a computer.] | + | :[White Hat stands behind Cueball, who is sitting at a computer] |
| | :White Hat: Why do you like functional programming so much? What does it actually ''get'' you? | | :White Hat: Why do you like functional programming so much? What does it actually ''get'' you? |
| | :Cueball: Tail recursion is its own reward. | | :Cueball: Tail recursion is its own reward. |
| Line 89: |
Line 66: |
| | [[Category:Programming]] | | [[Category:Programming]] |
| | [[Category:Recursion]] | | [[Category:Recursion]] |
| − | [[Category:Puns]]
| |
