1270: Functional

2013-09-27T11:39:47Z

24.187.72.209: /* Explanation */ Reward is a pun of reword.

{{comic
| number = 1270
| date = September 26, 2013
| title = Functional
| image = functional.png
| titletext = Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.
}}

==Explanation==
{{incomplete|if that's the recursion pun I think it is, Randall needs a caning.}}

'''TL;DR:''' After [[White Hat]] questions his faith in {{w|functional programming}}, [[Cueball]] says that "tail recursion is its own reward." This is a pun of the phrase "Tail recursion is its own reword". To reword a statement is to express it using different words. Tail recursion refers to when a function finishes by going back and calling itself with different arguments, forming a loop. The structure of this technique allows a compiler to compiled into a more efficient form ("reworded"). If you aren't groaning by now, read on.

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.

For example, the {{w|factorial}} function has a recursive definition:

factorial(n) = 1 if n = 0
factorial(n) = n * factorial(n - 1) if n > 0

which can be coded as:

factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)

{{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.

The efficiency and elegance are the literal rewards of tail recursion.

The {{w|greatest common divisor}} function can be coded as:

gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)

Here, the recursive call to gcd is tail recursive since its the last step of the function.

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.

factorial2(n, acc):
if n == 0:
return acc
else:
return factorial2(n - 1, n * acc)

factorial(n):
return factorial2(n, 1)

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.

Cueball is making the pun that "(functional programming) is an end unto itself", which would be both figuratively and literally correct.

The title text describes that to {{w|Abstract mathematics|abstract mathematicians}} functional programming is both powerful and flexible, as well as intuitive and clear since it comes very close to the way mathematicians usually describe functions. On the other hand to non-mathematicians, functional programming can be exactly the opposite (thus being non-intuitive and unclear as abstract mathematics appears to them).

The title text is also a reference to a common saying about C (An {{w|Imperative programming|imperative programming}} language): "C combines the flexibility and power of assembly language with the user-friendliness of assembly language".

==Transcript==
:[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?
:Cueball: Tail recursion is its own reward.

{{comic discussion}}
[[Category:Comics featuring White Hat]]
[[Category:Comics featuring Cueball]]
[[Category:Programming]]
[[Category:Recursion]]

Talk:1270: Functional

2013-09-27T11:31:08Z

24.187.72.209: Reward is a pun of Reword

I'm getting the adblock message at the top.. on mobile. On an unrelated note, I laughed and I don't even get it. Edit: I'm also seeing an ad while seeing the message.[[Special:Contributions/50.159.5.112|50.159.5.112]] 06:03, 27 September 2013 (UTC)
:This shouldn't be in comic discussion. I have written an updated version of our ad plugin that should only display a message to people using adblock, but we're using a sitenotice for now to test the waters. We'll take it down in about a day, promise!
:Also, would you be complicit if I were to move this to the relevant forum? '''[[User:Davidy22|{{Color|#707|David}}y²²]]'''[[User talk:Davidy22|<tt>[talk]</tt>]] 06:13, 27 September 2013 (UTC)
I removed that misguided explanation about lists that was not tail recursive. I'm also wondering if we should also mention that tail call optimization is also applicable to mutually recursive functions. In fact proper functional languages will always apply it whether the functions are recursive or not. Maybe emphasize the fact that "The efficiency and elegance are the literal rewards of tail recursion."?

I feel like the examples should be in Haskall, because that is the major functional language... [[Special:Contributions/67.160.98.42|67.160.98.42]] 09:48, 27 September 2013 (UTC) GBGamer117
:I think Hask'''e'''ll is more common, but I agree. And to emphasize the clarity, usually if/else blocks are avoided using pattern matching. I.e. tail-recursive factorial can be written as follows:
fac2::Integer->Integer-> Integer -- optional function header
fac2 acc 0 = acc
fac2 acc n = fac2 (acc*n) (n-1)

fac::Integer-> Integer
fac = fac2 1
:--[[User:Chtz|Chtz]] ([[User talk:Chtz|talk]]) 10:34, 27 September 2013 (UTC)
::Addendum: I did not dare to edit that yet, as I am unsure if this actually helps anyone not familiar with functional programming (and I don't think this page should include a Haskell crash course just to explain this comic). --[[User:Chtz|Chtz]] ([[User talk:Chtz|talk]]) 10:43, 27 September 2013 (UTC)

I thought about the text a little and don't the the interpretation "tail recursion is an end unto itself" is correct. I think what's going on is a pun of the word "reward". "Tail recursion is it's own reword" makes more sense since you are calling the same function but are "rewording" the arguements. To reword means to re-express something with different words. --[[Special:Contributions/24.187.72.209|24.187.72.209]] 11:31, 27 September 2013 (UTC)

explain xkcd - User contributions [en]

1270: Functional

Talk:1270: Functional