Figure 1: Photo by Amelie & Niklas Ohlrogge on Unsplash
In the article How To Learn All Programming Languages, I explained learning programming language concepts is an effective way to master all programming languages.
Recursion, continuation, and continuation-passing style are essential ideas for functional programming languages. Have an understanding of them will help much in knowing how programming languages work; even we don’t use them in daily programming tasks.
In this post, let’s learn these concepts of programming languages with some short Python programs.
Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.
Most modern programming language support recursion by allowing a function to call itself from within its own code. Recursion is the default programming paradigm in many functional programming languages, such as Haskell, OCaml.
Many daily programming tasks or algorithms could be implemented in recursion more easily. Suppose you want to list all the files and sub-directories of a directory recursively, recursion will be a natural choice for implementation.
Let’s have a look at this simple recursive Python program:
def fib_rec(n): if n < 2: return 1 else: return fib_rec(n - 1) + fib_rec(n - 2) print(fib_rec(5))
It is a naive implementation for computing Fibonacci numbers. A key point of recursion is there must be an exit point, the third line of
return 1 is the exit point for this program.
But what is the drawback of recursion?
Let’s add more debug information for this program, print the call depth in the beginning of function:
import traceback def fib_rec(n): print(len(traceback.extract_stack()) * '*' + ": " + str(n)) if n < 2: return 1 else: return fib_rec(n - 1) + fib_rec(n - 2) print(fib_rec(5))
The output will be:
* implies the call depths of the current function call. As we can see from the output, 2 points need to notice:
- There are duplicated computations during the whole progress. fib_rec(3), fib_rec(2), fib_rec(1) are called multiple times.
- The call stacks will grow quickly as the input number increase. Stack overflow exception will be thrown out if we want to compute fib_rec(1000).
How could we fix these general issues of recursion?
Tail recursion is a special form of recursion, in which the final action of a procedure calls itself again. In above program, the last action is
return 1 or
return fib_rec(n-1) + fib_rec(n-2), this is not a tail recursion.
Let’s try to convert above program to tail recursion:
def fib_tail(n, acc1=1, acc2=1): print(len(traceback.extract_stack()) * '*' + ": " + str(n)) if n < 2: return acc1 else: return fib_tail(n - 1, acc1 + acc2, acc1) print(fib_tail(5))
The output is like this:
From the result, we could find out we removed some duplicated computations, we solved the issue #1 of the above program.
Tail Call Optimization (TCO)
There is a technical called tail call optimization which could solve the issue #2, and it’s implemented in many programming language’s compilers. But not implemented in Python. Guido explains why he doesn’t want
tail call optimization in this post.
Anyway, let’s have an understanding of how
tail call optimization works. We know that any call of sub-function will create a new stack frame during the execution. If we treat function call as a black box, we could reuse the same stack frame when the tail function call happens.
To do this, a compiler with
TCO will try to eliminate the last tail call with a jump operation and fix the stack overflow issue. Suppose if Python had a
goto operation, we could replace the last call of
goto and update the related parameters.
# NOTE!!! This is pseudo-code def fib_tail(n, acc1=1, acc2=1): START: if n < 2: return acc1 else: #return fib_tail(n - 1, acc1 + acc2, acc1) n = n - 1 tmp = acc1 acc1 = acc1 + acc2 acc2 = tmp goto START
From the result, the compiler actually could convert a recursive function into an iterative version. All iterative functions can be converted to recursion because iteration is just a special case of recursion (tail recursion).
This is the reason why many FP don’t perform poorly even we write code in recursive style. Compilers do their job!
And even more, functional programming languages adopt the continuation-passing style (CPS), in which control is passed explicitly in the form of a continuation.
A continuation is an abstract representation of the control state of a program.
Let’s say continuation is a data structure that represents the computational process at a given point in the process’s execution, we could save an execution state and continue the computational process latter.
lambda function in Python could be used for this since we could pass a lambda function as parameters and call them later.
Let’s define the simplest continuation, this continuation will return the original value with any parameter:
end_cont = lambda value: value
Then we try to convert the above fib_tail function into a CPS. We add an extra parameter called
def fib_cps(n, cont): print(len(traceback.extract_stack()) * '*' + ": " + str(n)) if n < 2: return cont(1) else: return lambda: fib_cps( n - 1, lambda value: lambda: fib_cps( n - 2, lambda value2: lambda: cont(value + value2))) print(fib_cps(5, end_cont))
The output is:
<function <lambda> at 0x101d52758>
Emm, we only got a lambda function as a result. Remember we could continue to execute a continuation, so we continue to run this lambda function, the returned value is still a continuation …
v = fib_cps(5, end_cont) print(v) print(v) v = v() print(v) v = v() print(v) v = v() print(v) .... **: 5 <function <lambda> at 0x10d493758> ***: 4 <function <lambda> at 0x10d493848> ***: 3 <function <lambda> at 0x10d4938c0> ***: 2 <function <lambda> at 0x10d493938> ***: 1
Let’s wrap a function to call
v repeatedly until we got a real value:
def trampoline(f, *args): v = f(*args) while callable(v): v = v() return v
Then run it with:
print(trampoline(fib_cps, 5, end_cont))
Woo! The stack depth always keeps the same during the execution procedure. Some compilers of functional programming languages will do CPS-transform automatically.
We just had a little but real experience of tail recursion, tail call optimization, and continuation. Continuations are useful for implementing other control mechanisms in programming languages such as exceptions, generators, and coroutines. A good understanding of these concepts helps us to understand programming languages deeper.
I hope you enjoy it.