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.

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

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.
– Wikipedia

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 at the beginning of the 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:

The * 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

Tail recursion is a special form of recursion, in which the final action of a procedure calls itself again. In the 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 fib_tail with 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!

Continuation-passing style

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.

Sounds obscure?

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.

Seems like 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 cont:

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.

Summary up

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.