1270: Functional

2013-09-28T11:26:21Z

SleekWeasel: /* Explanation */

{{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|1270: Functional}}

[[White Hat]] questions [[Cueball]]'s faith in {{w|functional programming}}. [[Cueball]] responds saying, "Tail recursion is its own reward."

In computer science, recursion is where a function invokes itself with arguments representing a smaller computation than the current invocation received. Eventually, the computation is small enough to require no further recursive invocations. In general, a recursive function can invoke itself several times for each level (see {{w|Quicksort}}), but in the simplest case a function makes only one call for each level of the computation, which is computationally equivalent to a standard {{w|iterative}} loop in a program.

For example, the {{w|factorial}} function can be coded as:

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

{{w|Tail recursion}} is a special case of recursion whose very '''last''' operation is to invoke the function itself or return a definite value. In this situation, the compiler can substitute a normal recursive call with a simple jump to the start of the function, with the new arguments. This turns a tail-recursive call into an iterative loop, which has better time and memory efficiency, whilst retaining the presentational simplicity of a recursive call: when the tail-recursive function finally returns from its non-recursive step, it will immediately return to the original calling code, instead of inefficiently and pointlessly remembering where it came from on each level down and relinquishing that knowledge on each level up as each level returns to the return statement of its predecessor level.

Not all programming languages implement this optimisation for tail recursion - the compiler/interpreter writers may not have considered it worth expending the overhead of recognising the situation or saving the time and space involved in storing the status of each level of the recursion on the stack.

The first example of "factorial" shown above is not tail recursive because the multiplication operation cannot be evaluated until after the recursive invocation returns. This example ''is'' tail recursive inside the helper function:

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

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

which is transformed behind the scenes to

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

The technique here is to use a helper function with an additional argument called an accumulator which will accumulate results from previous calls to the function, often used to implement tail recursive or iterative versions of recursive functions. This is not applicable for all recursive functions, though.

Cueball is making a play on words where "Tail recursion is its own reward" is used both in the "it's worth doing on elegance and intellectually satisfying grounds alone" sense and 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 <em>all levels</em> of a tail-recursive function".

The title text says 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. The humorous contrast is that 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 the {{w|Imperative programming|imperative programming}} language, 'C': "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]]

1270: Functional

2013-09-28T11:19:46Z

SleekWeasel: /* Explanation */

{{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|1270: Functional}}

[[White Hat]] questions [[Cueball]]'s faith in {{w|functional programming}}. [[Cueball]] responds saying, "Tail recursion is its own reward."

In computer science, recursion is where a function invokes itself with arguments representing a smaller computation than the current invocation received. Eventually, the computation is small enough to require no further recursive invocations. In general, a recursive function can invoke itself several times for each level (see {{w|Quicksort}}), but in the simplest case a function makes only one call for each level of the computation, which is computationally equivalent to a standard {{w|iterative}} loop in a program.

For example, the {{w|factorial}} function can be coded as:

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

{{w|Tail recursion}} is a special case of recursion whose very '''last''' operation is to invoke the function itself or return a definite value. In this situation, the compiler can substitute a normal recursive call with a simple jump to the start of the function, with the new arguments. This turns a tail-recursive call into an iterative loop, which has better time and memory efficiency, whilst retaining the presentational simplicity of a recursive call: when the tail-recursive function finally returns from its non-recursive step, it will immediately return to the original calling code, instead of inefficiently and pointlessly remembering where it came from on each level down and relinquishing that knowledge on each level up as each level returns to the return statement of its predecessor level.

Not all programming languages implement this optimisation for tail recursion - the compiler/interpreter writers may not have considered it worth expending the overhead of recognising the situation or saving the time and space involved in storing the status of each level of the recursion on the stack.

The first example of "factorial" shown above is not tail recursive because the multiplication operation cannot be evaluated until after the recursive invocation returns. This example 'is' tail recursive inside the helper function:

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

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

which is transformed behind the scenes to

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

The technique here is to use a helper function with an additional argument called an accumulator which will accumulate results from previous calls to the function, often used to implement tail recursive or iterative versions of recursive functions. This is not applicable for all recursive functions, though.

Cueball is making a play on words where "Tail recursion is its own reward" is used both in the "it's worth doing on elegance and intellectually satisfying grounds alone" sense and 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 <em>all levels</em> of a tail-recursive function".

The title text says 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. The humorous contrast is that 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 the {{w|Imperative programming|imperative programming}} language, 'C': "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]]