The following is an iterative implementation that uses a “bottom-up” approach to compute an element of the sequence:

def fib(n): if n == 0: return 0 prev, crnt = 0, 1 for i in range(1, n): prev, crnt = crnt, prev + crnt return crnt 

Unlike a naive recursive implementation that takes time exponential in \(n\) and linear space, this iterative version takes linear time and constant space. We can translate the iterative implementation to a recursive one by introducing additional function parameters to replace each of the local variables, resulting in the following:

def fib(n, prev=0, crnt=1, i=1): if n == 0: return 0 if i == n: return crnt return fib(n, crnt, prev + crnt, i + 1) 

We use default arguments to provide the variables their initial values. The termination conditions are the same as the iterative version: when n == 0 for the base case, and when i == n for the recursive case. And the variable updates are the same, just that the new values are passed to a recursive call rather than modifying the existing variables. The resulting function is tail-recursive, and with tail-call optimization, it is exactly equivalent to the iterative version.

A recursive implementation can also be translated to an iterative one, though the equivalent iterative version may require an explicit data structure to replace the implicit storage provided by the call stack. As an example, the following is a recursive function that computes the sum of the elements contained in a binary tree:

def deep_sum(tree): if not tree: return 0 return (tree.datum + deep_sum(tree.left) + deep_sum(tree.right)) 

This is a tree-recursive function, and it makes use of a call stack that is linear with respect to the height of the tree. An equivalent iterative implementation needs to provide this storage manually:

def deep_sum(tree): sum = 0 stack = [tree] while stack: if tree := stack.pop(): sum += tree.datum stack.append(tree.left) stack.append(tree.right) return sum 

The initial value for sum is the same as the return value for the base case in the recursive version. In both implementations, if the current tree is non-empty, its datum is added to the sum, and the computation is repeated on each child.

Since either iteration or recursion can express the same algorithm, if both are available in a programming system, it is up to the programmer which one to use. A programmer may decide that one tool is a more natural fit for a particular algorithm, or they may consider which one their system can optimize better. Ideally, the programmer is adept at both tools and makes the decision based on which is more appropriate for the use case rather than which one they are more comfortable utilizing.

Higher-Order Functions

Recall that a first-class entity is one that supports the operations that can be done on other entities in a language, including being passed as a parameter, returned from a function, and created dynamically. In a language in which functions are first class, it is possible to write higher-order functions that take in another function as a parameter or return a function. Other languages may also support higher-order functions, even if functions are not first-class entities that can be created at runtime.

Function Objects

In some languages, it is possible to define objects that aren’t functions themselves but provide the same interface as a function. These are known as function objects or functors. In general, languages enable functors to be written by allowing the function-call operator to be overloaded. Consider the following example in C++:

class Counter  public: Counter : count(0) <> int operator()()  return count++; > private: int count; >; 

The Counter class implements a functor that returns how many times it has been called. Multiple Counter objects can exist simultaneously, each with their own count:

Counter counter1, counter2; cout  counter1()  endl; // prints 0 cout  counter1()  endl; // prints 1 cout  counter1()  endl; // prints 2 cout  counter2()  endl; // prints 0 cout  counter2()  endl; // prints 1 cout  counter1()  endl; // prints 3 

Functors allow multiple instances of a function-like object to exist, each with their own state that persists over the lifetime of the functor. This is in contrast to functions, where automatic objects do not persist past a single invocation, and static objects persist over the entire program execution.

Python also allows functors to be written by defining the special __call__ method:

class Counter: def __init__(self): self.count = 0 def __call__(self): self.count += 1 return self.count - 1 

In general, additional parameters can be specified when overloading the function-call operator, emulating functions that can take in those arguments.

Some languages do not allow the function-call operator itself to be overloaded but specify conventions that allow functor-like objects to be defined and used. For example, the following is an implementation of Counter in Java using the Supplier interface, which specifies a zero-argument method that produces a T :

class Counter implements SupplierInteger>  public Integer get()  return count++; > private int count = 0; > 

This functor-like object is then invoked by explicitly calling the get() method:

SupplierInteger> counter1 = new Counter(); SupplierInteger> counter2 = new Counter(); System.out.println(counter1.get()); // prints 0 System.out.println(counter1.get()); // prints 1 System.out.println(counter1.get()); // prints 2 System.out.println(counter2.get()); // prints 0 System.out.println(counter2.get()); // prints 1 System.out.println(counter1.get()); // prints 3 

As another example, the Predicate interface in Java is implemented by functor-like objects that take in an argument and return a boolean value:

interface PredicateT>  boolean test(T t); . > class GreaterThan implements PredicateInteger>  public GreaterThan(int threshold)  this.threshold = threshold; > public boolean test(Integer i)  return i > threshold; > private int threshold; > 

Code that uses these functor-like objects calls the test() method rather than calling the object directly:

GreaterThan gt3 = new GreaterThan(3); System.out.println(gt3.test(2)); // prints out false System.out.println(gt3.test(20)); // prints out true 

Separate interfaces are provided for common patterns in the java.util.function library package.

Functions as Parameters

A higher-order function may take another function as a parameter. We first examine languages that only have top-level functions and allow a pointer or reference to a function to be passed as an argument. We then examine how passing a function as an argument can affect the environment in which the function’s code is executed.

Function Pointers

In some languages, functions can be passed as parameters or return values but cannot be created within the context of another function. In these languages, all functions are defined at the top level, and only a pointer or reference to a function may be used as a value. Consider the following example in C, a language that provides function pointers:

void apply(int *array, size_t size, int (*func)(int))  for (; size > 0; --size, ++array)  *array = func(*array); > > int add_one(int x)  return x + 1; > int main()  int A[5] =  1, 2, 3, 4, 5 >; apply(A, 5, add_one); printf("%d, %d, %d, %d, %d\n", A[0], A[1], A[2], A[3], A[4]); return 0; > 

The apply() function takes in an array, its size, and a pointer to a function that takes in an int and returns an int . It applies the function to each element in the array, replacing the original value with the result. The add_one() function is passed as an argument to apply() (C automatically converts a function to a function pointer), and the result is that each element in A has been incremented.

Binding Policy

In the code above, there are three environments associated with the add_one() function: its definition environment, the environment where it was referenced (in main() ), and the environment where it was called (in apply() ). Depending on the semantics of the language, any of these three environments may be components of the environment in which the body of add_one() is executed.

Recall that in static scope, the code in a function has access to the names in its definition environment, whereas in dynamic scope, it has access to the names in the environment of its use. Considering dynamic scope, is the non-local environment of a function the one where the function was referenced or the one where it was called? The following is an example where this distinction is relevant:

int foo(int (*bar)())  int x = 3; return bar(); > int baz()  return x; > int main()  int x = 4; print(foo(baz)); > 

In dynamic scope, a function has access to the environment of its use. In the example above, however, the result is different depending on if the use environment of baz() is where the function was referenced or where it was called. In the former case, the non-local environment of baz() is the environment of main() , and the x in the body of baz() would refer to the one defined in main() . This is known as deep binding. In the latter case, the non-local environment of baz() is the environment of foo() , and x in baz() would refer to the one defined in foo() . This is called shallow binding. Both approaches are valid, and the binding policy of a language determines which one is used.

Binding policy can also make a difference when static scope is used in the case of functions defined locally inside of a recursive function. However, deep binding is universally used in languages with static scope, so that the environment established at the time of a function’s definition is the one the function has access to.

Nested Functions

A key feature of functional programming is the ability to define a function from within another function, allowing the dynamic creation of a function. In languages with static scoping, such a nested function has access to its definition environment, and the combination of a function and its definition environment is called a closure. Variables used in the nested function but defined in the enclosing environment are said to be captured by the closure. If a nested function is returned or otherwise leaks from the enclosing function, the environment of the enclosing function generally must persist after the function returns, since bindings within it may be accessed by the nested function.

As an example, consider the following higher-order function in Python that returns a nested function:

def make_greater_than(threshold): def greater_than(x): return x > threshold return greater_than 

The make_greater_than() function takes in a threshold value and constructs a nested function that determines if its input is greater than the threshold value. The threshold variable is located in the activation record of make_greater_than() but is captured by greater_than() . Since the latter is returned, the activation record must persist so that invocations of greater_than() can access the binding for threshold .

Observe that each time make_greater_than() is called, a different instance of greater_than() is created with its own enclosing environment. Thus, different invocations of make_greater_than() result in different functions:

>>> gt3 = make_greater_than(3) >>> gt30 = make_greater_than(30) >>> gt3(2) False >>> gt3(20) True >>> gt30(20) False >>> gt30(200) True 

Figure 24 from Python Tutor shows the state when gt3(2) is called.

The parent frame of the invocation is that in which threshold is bound to 3, so x > threshold evaluates to false.

Languages that are not purely functional may allow modification of a captured variable. For example, the following defines a data abstraction for a bank account using nested functions:

def make_account(balance): def deposit(amount): nonlocal balance balance += amount return balance def withdraw(amount): nonlocal balance if 0  amount  balance: balance -= amount return amount else: return 0 return deposit, withdraw 

The nonlocal statements are required in Python, since it assumes that assignments are to local variables by default. We can then use the created functions as follows:

>>> deposit, withdraw = make_account(100) >>> withdraw(10) 10 >>> deposit(0) 90 >>> withdraw(20) 20 >>> deposit(0) 70 >>> deposit(10) 80 >>> withdraw(100) 0 >>> deposit(0) 80 

Decorators

A common pattern in Python is to transform a function (or class) by applying a higher-order function to it. Such a higher-order function is called a decorator, and Python has specific syntax for decorating functions:

This is largely equivalent to:

def name>(parameters>): body> name> = decorator>(name>) 

The decorated function’s definition is executed normally, and then the decorator is called on the function. The result of this invocation is then bound to the name of the function.

As an example, suppose we wanted to trace when a function is called by printing out the name of the function as well as its arguments. We could define a higher-order function that takes in a function and returns a new nested function that first prints out the name of the original function and its arguments and then calls it:

def trace(fn): def tracer(*args): args_string = ', '.join(repr(arg) for arg in args) print(f'fn.__name__>(args_string>)') return fn(*args) return tracer 

Here, we make use of variadic arguments to pass any number of arguments to the original function. (For simplicity, we ignore keyword arguments.) We can then use decorator syntax to apply this to a function:

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

Now whenever a call to factorial() is made, we get a printout of the arguments:

>>> factorial(5) factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0) 120 

Notice that the recursive calls also call the transformed function. This is because the name factorial is now bound to the nested tracer function in the enclosing environment of factorial() , so looking up the name results in the tracer function rather than the original one. A side effect of this is that we have mutual recursion where a set of functions indirectly make recursive calls through each other. In this case, the tracer calls the original factorial() , which calls the tracer, as shown in the diagram in Figure 25 for factorial(2) from Python Tutor.

Lambda Functions

Nested function definitions allow the construction of functions at runtime, fulfilling one of the requirements for functions to be a first-class entity. So far, however, we’ve only seen nested function definitions that are named, introducing a binding into the definition environment. This is in contrast to other first-class entities, such as data values, that can be created without being bound to a name. Just like it can be useful to construct a value without a name, such as when passing it as an argument or returning it, it can be useful to construct unnamed functions. These are called anonymous or lambda functions.

Lambda functions are ubiquitous in functional languages, but many common imperative languages also provide some form of lambda functions. The syntax and capabilities differ between different languages, and we will examine a few representative examples.

Scheme

Lambdas are a common construct in the Lisp family of languages, those languages being primarily functional, and Scheme is no exception. The lambda special form constructs an anonymous function:

(lambda ( ) ) 

A function definition using the define form can then be considered a shorthand for a variable definition and a lambda :

(define (  ) ) --> (define (lambda ( ) )) 

As an example, consider the following function that creates and returns an anonymous function that adds a given number to its argument:

(define (make-adder n) (lambda (x) (+ x n) ) ) 

This is simpler and more appropriate than an equivalent definition that only uses define :

(define (make-adder n) (define (adder x) (+ x n) ) adder ) 

We can then call the result of make-adder on individual arguments:

> (define add3 (make-adder 3)) > (add3 4) 7 > (add3 5) 8 > ((make-adder 4) 5) 9 

Nested functions in Scheme use static scope, so the anonymous function has access to the variable n in its definition environment. It then adds its own argument x to n , returning the sum.

Scheme is not purely functional, allowing mutation of variables and compound data. Nested functions, whether anonymous or not, can modify variables in their non-local environment. The following function creates a counter function that returns how many times it has been called:

(define (make-counter) (let ((count 0)) (lambda () (set! count (+ count 1)) (- count 1) ) ) ) 

The set! form mutates a variable to the given value. We can then use the make-counter function as follows:

> (define counter (make-counter)) > (counter) 0 > (counter) 1 > (counter) 2 

Python

Python supports anonymous functions with the lambda expression. This takes the following form:

lambda parameters>: body expression> 

The syntax of lambda expressions in Python produce a constraint on anonymous functions that is not present in named nested functions: the body must be a single expression, and the value of that expression is automatically the return value of the function. In practice, this limitation is usually not a problem, since lambdas are often used in functional contexts where statements and side effects may not be appropriate.

The following is a definition of the greater_than() higher-order function that uses a lambda:

def make_greater_than(threshold): return lambda value: value > threshold 

As can be seen in this example, simple nested functions that are used in only a single place can be written more succinctly with a lambda expression than with a definition statement.

While lambda functions in Python have access to their definition environment, they are syntactically prevented from directly modifying bindings in the non-local environment.

Java

Java does not allow nested function definitions, but it does have syntax for what it calls “lambda expressions.” In actuality, this construct constructs an anonymous class with a method corresponding to the given parameters and body, and the compiler infers the base type of this class from the context of its use.

The following example uses a lambda expression to construct a functor-like object:

public static IntPredicate makeGreaterThan(int threshold)  return value -> value > threshold; > 

We can then use the result as follows:

IntPredicate gt3 = makeGreaterThan(3); System.out.println(gt3.test(2)); // prints out false System.out.println(gt3.test(20)); // prints out true 

Java allows a lambda to take in any number of arguments, and providing types for the parameters is optional. The body can be a single expression or a block containing arbitrary statements.

On the other hand, Java places a significant restriction on lambda expressions. A lambda can only access variables in its definition environment that are never reassigned, and it cannot modify them itself. This is because lambdas are not implemented as closures, but rather as functor-like objects that store “captured” variables as members. The following is effectively equivalent to the code above, but using named classes and methods:

public static IntPredicate makeGreaterThan(int threshold)  return Anonymous(threshold); > class Anonymous implements IntPredicate  Anonymous(int threshold)  this.threshold = threshold; > public boolean test(int value)  return value > threshold; > private final int threshold; > 

C++

Like Java, C++ has lambda expressions, but they provide more functionality than those in Java. A programmer can specify which variables in the definition environment are captured, and whether they are captured by value or by reference. The former creates a copy of a variable, while the latter allows a captured variable to be modified by the lambda.

The simplest lambda expressions are those that do not capture anything from the enclosing environment. Such a lambda can be written as a top-level function instead [ 3 ] , and C++ even allows a captureless lambda to be converted to a function pointer. For example, the following code passes a lambda function to a higher-order function that takes in a function pointer:

A captureless lambda is actually implemented as a functor, avoiding an indirection when the lambda is invoked without first converting it to a function pointer.

int max_element(int *array, size_t size, bool (*less)(int, int))  assert(size > 0); int max_so_far = array[0]; for (size_t i = 1; i  size; i++)  if (less(max_so_far, array[i]))  max_so_far = array[i]; > > return max_so_far; > int main()  int array[5] =  3, 1, 4, 2, 5 >; cout  <max_element(array, 5, [](int a, int b)  return a > b; >)  <endl; > 

The code constructs a lambda function that returns true if the first element is bigger than the second, and passing that to max_element() finds the minimum rather than the maximum element.

Lambdas that capture variables, whether by value or by reference, have state that is associated with a specific evaluation of a lambda expression, and this state can differ between different calls to the enclosing function. As a result, such a lambda is not representable as a top-level function. Instead, C++ implicitly defines a functor type for a capturing lambda. Evaluating a capturing lambda expression constructs an instance of this functor type, with the captured values and references stored as non-static members. Since the functor type is implicitly defined, type deduction with the auto keyword is usually used where the type of the functor is required.

The following is an example that uses a lambda to define a greater-than functor:

auto make_greater_than(int threshold)  return [=](int value)  return value > threshold; >; > int main()  auto gt3 = make_greater_than(3); cout  <gt3(2)  <endl; // prints 0 cout  <gt3(20)  <endl; // prints 1 cout  <make_greater_than(30)(20)  <endl; // prints 0 > 

The = in the capture list for the lambda specifies that all variables from the enclosing environment that are used by the lambda should be captured by value. The code above is equivalent to the following that explicitly uses a functor:

class GreaterThan  public: GreaterThan(int threshold_in) : threshold(threshold_in) <> bool operator()(int value) const  return value > threshold; > private: const int threshold; >; auto make_greater_than(int threshold)  return GreaterThan(threshold); > 

As indicated in the code above, a variable captured by value is implicitly qualified as const .

An enclosing variable may also be captured by reference. However, a variable that is captured by reference does not have its lifetime extended. The reasoning for this is twofold. The first, practical reason is that C++ implementations generally use stack-based management of automatic variables, and when a function returns, its activation record on the stack is reclaimed. Requiring that a variable live past its function invocation prevents activation records from being managed using a stack. The second, more fundamental reason is that the RAII (i.e. scope-based resource management) paradigm in C++ requires that when an automatic variable goes out of scope, the destructor for its corresponding object is run and the object reclaimed. Relaxing this requirement would result in undesirable effects similar to those of finalizers in garbage-collected languages.

The end result is that a lambda functor that captures by reference should not be used past the existence of its enclosing function invocation. The following counter definition is therefore erroneous:

auto make_counter()  int count = 0; return [&]()  return count++; >; > 

The lifetime of the count variable ends when make_counter() returns, so that calling the lambda functor afterwards erroneously uses a dead object.

An alternative is to capture count by value, which stores a copy as a member of the lambda, and then mark the lambda as mutable . This removes the implicit const qualification from variables captured by value, allowing them to be modified:

auto make_counter()  int count = 0; return [=]() mutable  return count++; >; > 

This definition is equivalent to the Counter functor we defined in Function Objects.

Common Patterns

We now take a look at some common computational patterns in functional programming. We will look at how to abstract these patterns as higher-order functions, as well as how to use them with lambda functions.

Sequence Patterns

A number of functional patterns operate over sequences. These patterns take in a sequence and a function and apply the function to elements of the sequence, producing a new sequence or value as a result. Since these are functional patterns, the original sequence is left unchanged.

Map

The map pattern takes a sequence and a function and produces a new sequence that results from applying the function to each element of the original sequence. For example, the following adds 1 to each element of a Scheme list:

> (map (lambda (x) (+ x 1)) '(1 2 3)) (2 3 4) 

We can define this higher-order function as follows, using the name map1 to avoid conflict with the built-in Scheme map :

(define (map1 func lst) (if (null? lst) lst (cons (func (car lst)) (map1 func (cdr lst))) ) ) 

Applying map1 to an empty list results in an empty list. Otherwise, map1 applies the given function to the first item in the list and recursively calls map1 on the rest of the list.

The built-in Scheme map also works with a non-unary function, as long as the number of lists provided matches the number of arguments the function expects. For instance, we can apply cons to corresponding elements from two lists as follows:

> (map cons '(1 2 3) '(4 5 6)) ((1 . 4) (2 . 5) (3 . 6)) 

The argument lists must have the same length. We can define our own version of this as a variadic procedure:

(define (map-n func list1 . lists) (if (null? list1) '() (let ((firsts (map1 car (cons list1 lists))) (rests (map1 cdr (cons list1 lists)))) (cons (apply func firsts) (apply map-n func rests) ) ) ) ) 

We use map1 to obtain the first element from each list, as well as the rest of each list. We then use apply to apply func to the first elements, as well as to recursively map func across the rest of the lists.

Python has a similar built-in map() that takes in a function and at least one sequence, producing a new sequence that results from applying the function to corresponding elements from the input sequences. Unlike Scheme’s version, Python allows the sequences to differ in length, with the result sequence having the same length as the shortest input sequence.

>>> list(map(lambda x, y: x + y, [1, 2, 3], (4, 5))) [5, 7] 

Reduce

In the reduce pattern, a two-argument function is applied to the first two items in a sequence, then it is applied to the result and the next item, then to the result of that and the next item, and so on. A reduction may be left or right associative, but the former is more common. Figure 26 illustrates the difference between left- and right-associative reductions.

Often, if only a single item is in the sequence, that item is returned without applying the function. Some definitions allow an initial value to be specified as well for the case in which the sequence is empty.

The following examples compute the sum and maximum element of a Scheme list:

> (reduce-right (lambda (x y) (+ x y)) '(1 2 3 4)) 10 > (reduce-right (lambda (x y) (if (> x y) x y)) '(1 2 3 4)) 4 

We can define a right-associative reduction as follows, which assumes that the given list has at least one element:

(define (reduce-right func lst) (if (null? (cdr lst)) (car lst) (func (car lst) (reduce-right func (cdr lst))) ) ) 

Python includes a left-associative reduce() function in the functools module.

Filter

The filter pattern uses a predicate function to filter items out of a list. A predicate is a function that takes in a value and returns true or false. In filter, elements that test true are retained while those that test false are discarded.

The following example filters out the odd elements from a list:

> (filter (lambda (x) (= (remainder x 2) 0)) '(1 2 3 4)) (2 4) 

The following is a definition of filter :

(define (filter pred lst) (if (null? lst) lst (if (pred (car lst)) (cons (car lst) (filter pred (cdr lst))) (filter pred (cdr lst)) ) ) ) 

Python provides a built-in filter() function as well.

Any

The any pattern is a higher-order version of or (disjunction). It takes a predicate and applies the predicate to each successive item in a list, returning the first true result from the predicate. If no item tests true, then false is returned. Some languages use the name find for this pattern rather than any.

The following examples search a list for an even value:

> (any (lambda (x) (= (remainder x 2) 0)) '(1 2 3 4)) #t > (any (lambda (x) (= (remainder x 2) 0)) '(1 3)) #f 

A short-circuiting any function can be defined as follows:

(define (any pred lst) (if (null? lst) #f (let ((result (pred (car lst)))) (or result (any pred (cdr lst)) ) ) ) ) 

The every pattern can be similarly defined as the higher-order analogue of conjunction.

Composition

Programs often compose functions, applying a function to the result of applying another function to a value. Wrapping these two function applications together in a single function enables both operations to be done with a single call. For example, the following multiplies each item in a list by three and then adds one:

> (map (compose (lambda (x) (+ x 1)) (lambda (x) (* 3 x))) '(3 5 7) ) (10 16 22) 

We can define compose as follows:

(define (compose f g) (lambda (x) (f (g x)) ) ) 

Partial Application and Currying

Partial application allows us to specify some arguments to a function at a different time than the remaining arguments. Supplying \(k\) arguments to a function that takes in \(n\) arguments results in a function that takes in \(n-k\) arguments.

As an example, suppose we want to define a function that computes powers of two. In Python, we can supply 2 as the first argument to the built-in pow() function to produce such a function. We need a partial-application higher-order function such as the following:

def partial(func, *args): def newfunc(*nargs): return func(*args, *nargs) return newfunc 

We can then construct a powers-of-two function as follows:

>>> power_of_two = partial(pow, 2) >>> power_of_two(3) 8 >>> power_of_two(7) 128 

Python actually provides a more general implementation of partial() that works for keyword arguments as well in the functools module. C++ provides partial application using the bind() template in the header.

A related but distinct concept is currying, which transforms a function that takes in \(n\) arguments to a sequence of \(n\) functions that each take in a single argument. For example, the pow() function would be transformed as follows:

>>> curried_pow(2)(3) 8 

The curried version of the function takes in a single argument, returning another function. The latter takes in another argument and produces the final value. Since the original pow() takes in two arguments, the curried function chain has length two.

We can define currying for two-parameter functions as follows in Python:

def curry2(func): def curriedA(a): def curriedB(b): return func(a, b) return curriedB return curriedA 

Then we can call curry2(pow) to produce a curried version of pow() .

We can also define an “uncurry” operation that takes in a function that must be applied to a sequence of \(n\) arguments and produce a single function with \(n\) parameters. The following does so for a sequence of two arguments:

def uncurry2(func): def uncurried(a, b): return func(a)(b) return uncurried 

>>> uncurried_pow = uncurry2(curried_pow) >>> uncurried_pow(2, 3) 8 

Some functional languages, such as Haskell, only permit functions with a single parameter. Functions that are written to take in more than one parameter are automatically curried.

Continuations

An running program encompasses two types of state: the data that the program is using and the control state of the program, such as the stack of active functions and the code locations in each of those functions. This control state can be represented in the form of a continuation.

A continuation can be invoked in order to return control to a previous state. Since a continuation only represents control state, invoking a continuation does not return data to their previous state. Instead, data retain the values they had at the time the continuation was invoked. The following is an analogy of invoking a continuation by Luke Palmer:

Say you’re in the kitchen in front of the refrigerator, thinking about a sandwitch [sic]. You take a continuation right there and stick it in your pocket. Then you get some turkey and bread out of the refrigerator and make yourself a sandwitch, which is now sitting on the counter. You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwitch. But fortunately, there’s a sandwitch on the counter, and all the materials used to make it are gone. So you eat it. :-)

In most non-functional languages, a continuation only exists in implicit form, and there is a restricted set of operations that can be done to invoke a continuation. In many functional languages, however, continuations are first-class entities that can be passed as parameters and returned from functions. We first examine restricted forms of continuations before considering the more general, first-class version.

Restricted Continuations

Simple forms of control flow, such as conditionals and loops, do not involve continuations, since they do not return to a previous state of control. Subroutines and exceptions, on the other hand, do revert control to a previous state and thus make implicit use of continuations.

Subroutines

Subroutines involve transfer of control between a caller and callee. When a subroutine is called, the control state of the caller must be saved, so that when the subroutine completes, control can be transferred back to the caller. Implementations make use of activation records and call stacks that record the sequence of active calls as well as information about how to return execution to a previous call. These data structures represent the control state of a program and thus constitute a continuation.

Languages restrict how the implicit continuation representing a caller’s state can be invoked. In some languages, including many functional languages such as Scheme, the caller’s continuation is only invoked when the subroutine completes normally. Other languages have a mechanism to terminate a subroutine early, sometimes called abrupt termination, and invoke the continuation of the caller. In imperative languages, this usually takes the form of a return statement. For example, the following Python function uses a return to immediately invoke the caller’s continuation:

def foo(x): return x # invoke caller's continuation # more code, but not executed if x  0: bar(x) baz(x) . 

As with any continuation, invoking a caller’s continuation does not restore the previous state of data. For example, consider the following Python code:

def outer(): x = 0 def inner(): nonlocal x x += 1 inner() print(x) 

When the call to inner() completes, the continuation of outer() is resumed, but the value of x is not restored to its state before the call to inner() . Instead, it retains its modified value, and the code prints 1 .

A more general concept provided by some languages is a coroutine, which involves two routines passing control to each other by invoking each other’s continuation. Coroutines differ from mutual recursion in that each routine’s control state is resumed when it is invoked rather than creating a fresh function invocation with its own state.

The following is pseudocode for coroutines that pass control to each other, with one producing items and the other consuming them:

var q := new queue coroutine produce loop while q is not full create some new items add the items to q yield to consume coroutine consume loop while q is not empty remove some items from q use the items yield to produce 

Both coroutines yield control to the other. Unlike with subroutines, when a coroutine is passed control, execution resumes from where it previously paused and in the context of the same environment.

Python provides an implementation of coroutines over a tasking layer, with several abstractions for passing data between running coroutines and waiting for completion of an action. The following implements the producer/consumer model using an asyncio.Queue for passing values between the producer and consumer:

import asyncio q = asyncio.Queue(2) # queue capacity of 2 async def produce(): for i in range(5): print('[producer] putting', i) await q.put(i) print('[producer] done putting', i) async def consume(): for i in range(5): print('[consumer] got:', await q.get()) loop = asyncio.get_event_loop() loop.run_until_complete(asyncio.gather(produce(), consume())) 

The latter two statements start the producer and consumer coroutines running and wait for their completion. The producer passes control to the coroutine returned by q.put(i) , which places an item into the queue. Execution will not return to the producer until this completes, so the producer will be forced to wait if the queue is full. The consumer extracts items from the queue using the q.get() coroutine, waiting if no items are available. The following is the output when the code is run:

[producer] putting 0 [producer] done putting 0 [producer] putting 1 [producer] done putting 1 [producer] putting 2 [consumer] got: 0 [consumer] got: 1 [producer] done putting 2 [producer] putting 3 [producer] done putting 3 [producer] putting 4 [consumer] got: 2 [consumer] got: 3 [producer] done putting 4 [consumer] got: 4 

This demonstrates how execution passes back and forth between the consumer and producer coroutines.

Exceptions

Exceptions also cause control to be passed from one execution state to an earlier one, but unlike returning from a subroutine, the receiver of control need not be the direct caller of a function. Upon entering a try block, the control state is saved and the associated exception handlers are added to a stack of active handlers. When an exception is raised, the handler stack is searched for a handler that can accommodate the exception type, the continuation of the associated function is invoked, and the handler code is executed.

As a concrete example, consider the following Python code:

def foo(x): try: bar(x) except: print('Exception') def bar(x): baz(x) def baz(x): raise Exception foo(3) 

When the try statement in the invocation of foo(3) is reached. the associated exception handler is added to the handler stack. Execution proceeds to the call to bar(3) and then to baz(3) , which raises an exception. This passes control to the first exception handler that can handle an exception of type Exception , which was located in the call to foo(3) . Thus, the latter’s continuation is invoked and the exception handler is run.

The specific mechanisms used to provide exceptions vary between languages and implementations. Some languages don’t incorporate exceptions directly but provide a control mechanism that enables an exception mechanism to be built on top of it. For example, the C standard library header setjmp.h defines a setjmp() function that saves the execution state of a function, and a corresponding longjmp() function that restores the state at the time of the call to setjmp() . Exceptions can also be implemented with first-class continuations, as we will see below.

Generators

A generator is a generalization of a subroutine, allowing its execution to be paused and later resumed. A subroutine is always executed from its entry point, and every entry into a subroutine creates a new activation record. On the other hand, a generator can suspend its execution, and the programmer can resume execution of the generator at the point where its execution state was suspended and using the same activation record. Thus, the paused state of a generator is a form of continuation.

Generators are usually used to write iterators that compute their values lazily. When a generator computes an item, it yields the item to its caller by invoking the continuation of the caller, much like a subroutine. Upon resumption of the generator, the next value is computed and yielded to its caller, which need not be the same function as the previous caller.

The following is a generator in Python that produces an infinite sequence of natural numbers:

def naturals(): num = 0 while True: yield num num += 1 

Generators in Python implement the same interface as an iterator, so the next item can be obtained by calling the next() function on a generator:

>>> numbers = naturals() >>> next(numbers) 0 >>> next(numbers) 1 >>> next(numbers) 2 

We can use a generator to represent a range, computing each value as the generator is resumed:

def range2(start, stop, step = 1): while start  stop: yield start start += step 

The sequence of values produced by this generator is finite, and after the last value is produced and the body of range2() exits, a StopIteration exception is automatically raised:

>>> values = range2(0, 10, 3) >>> next(values) 0 >>> next(values) 3 >>> next(values) 6 >>> next(values) 9 >>> next(values) Traceback (most recent call last): File "", line 1, in StopIteration 

A StopIteration is used by the Python for loop to determine the end of an iterator:

>>> for i in range2(0, 10, 3): . print(i) . 0 3 6 9 

As another example, we can define a unary version of the built-in map using a generator:

>>> def map_unary(func, iterable): . for item in iterable: . yield func(item) . >>> map_unary(lambda x: x + 1, [1, 4, -3, 7]) >>> list(map_unary(lambda x: x + 1, [1, 4, -3, 7])) [2, 5, -2, 8] 

The built-in map is actually variadic, applying an \(n\) -ary function to items taken from \(n\) iterables:

>>> for item in map(lambda x, y: x - y, [1, 2, 3], (-4, -5, -6, -7)): . print(item) . 5 7 9 

As can be seen from this example, map stops when the shortest input iterable is exhausted. We can attempt to write a variadic generator similar to map :

>>> def map_variadic(func, *iterables): . iterators = [iter(it) for it in iterables] . items = [0] * len(iterables) . while True: . for i in range(len(iterators)): . items[i] = next(iterators[i]) . yield func(*items) . 

We start by obtaining an iterator from each iterable, and then constructing a list that will hold an element from each iterator, initialized with dummy zero values. We follow this with an infinite loop that obtains the next item from each iterator, storing it in the list, invoking func on these items, and yielding the result. When the shortest iterator is exhausted, invoking next() on it will raise a StopIteration , and our intent was for this to end the map_variadic() generator as well. Unfortunately, Python does not allow a StopIteration to be propagated out of a generator:

>>> list(map_variadic(lambda x, y: x - y, [1, 2, 3], (-4, -5, -6, -7))) Traceback (most recent call last): File "", line 6, in map_variadic StopIteration The above exception was the direct cause of the following exception: Traceback (most recent call last): File "", line 1, in RuntimeError: generator raised StopIteration 

Instead, a generator is required to terminate normally or with a return when it is complete. Thus, we need to catch the StopIteration and then exit:

>>> def map_variadic(func, *iterables): . iterators = [iter(it) for it in iterables] . items = [0] * len(iterables) . try: . while True: . for i in range(len(iterators)): . items[i] = next(iterators[i]) . yield func(*items) . except StopIteration: . pass . 

Here, we’ve used a dummy pass statement in the except clause, since execution will proceed to the end of the generator body and exit. It would be equally valid to use a return statement instead. The generator now works as intended:

>>> list(map_variadic(lambda x, y: x - y, [1, 2, 3], (-4, -5, -6, -7))) [5, 7, 9] 

The yield from statement can be used to delegate to another generator (or iterator). The following is a definition of a positives() generator that delegates to an instance of naturals() :

>>> def positives(): . numbers = naturals() . next(numbers) # discard 0 . yield from numbers # yield the remaining items in numbers . >>> numbers = positives() >>> next(numbers) 1 >>> next(numbers) 2 >>> next(numbers) 3 

We construct a naturals() generator, discard the initial 0, and then use yield from to produce the remaining items from the naturals() generator.

Python also has generator expressions, similar to list comprehensions, that succinctly produce a generator. The following produces a generator of negative integers from naturals() :

>>> negatives = (-i for i in naturals() if i != 0) >>> next(negatives) -1 >>> next(negatives) -2 >>> next(negatives) -3 

As with list comprehensions, the filtering conditional is optional in a generator expression.

Generators are also called semicoroutines, since they involve a standard routine that passes control to a resumable routine. Unlike a coroutine, however, a generator can only return control to its caller, while a full coroutine can pass control to any other coroutine.

First-Class Continuations

In some languages, continuations are first-class entities, allowing the current control state to be saved in an explicit data structure, passed as a parameter, and invoked from arbitrary locations. First-class continuations can be used to emulate any of the restricted forms of continuations above. Depending on the language, it may only be permitted to invoke a continuation once, or a continuation may be resumed any number of times.

In Scheme, the call-with-current-continuation procedure, often abbreviated as call/cc , creates a continuation object representing the current control state. The call/cc procedure must be passed an argument:

(call-with-current-continuation ) 

Here, must be a Scheme procedure that takes an argument, and call/cc invokes this procedure with the newly created continuation object as the argument. The called procedure may use the continuation like any other data item, including discarding it, saving it in a data structure, and returning it, as well as invoking it. For example, in the following code, the procedure discards the continuation and returns a value normally:

> (+ 1 (call/cc (lambda (cc) 3 ) ) ) 4 

The continuation object constructed by the invocation of call/cc above represents the following execution state:

Here, replaces the call to call/cc , and it will be replaced by the value with which the continuation is invoked.

If the procedure invoked by call/cc returns a value normally, the invocation of call/cc evaluates to that same value, the same behavior as a standard function call. In the example above, the procedure returns the value 3, which replaces the call to call/cc , resulting in a final value of 4.

On the other hand, if the continuation created by call/cc is invoked, then control resumes at the location of the call/cc . A continuation must be passed a value when it is invoked, and the call/cc evaluates to that value:

> (+ 1 (call/cc (lambda (cc) (cc 5) 3 ) ) ) 6 

In the code above, the continuation represents the same execution state of (+ 1 ) . The function argument of call/cc invokes the continuation with value 5, causing execution to immediately resume at the point where call/cc is called, with the value 5 replacing the call to call/cc , as if it were a standard function call that produced the given value. This results in the execution (+ 1 5) , resulting in a final value of 6.

More interesting behavior can occur when a continuation is saved in a variable or data structure. Consider the following:

> (define var (call/cc (lambda (cc) cc ) ) ) 

The procedure called by call/cc returns the continuation, so the call/cc invocation evaluates to the continuation, which is then bound to var . The continuation itself represents the execution:

(define var ) 

We can bind another variable to the same object:

> (define cont var) 

Now we can use this new variable to invoke the continuation:

> (cont 3) ; executes (define var 3) > var 3 > (cont 4) ; executes (define var 4) > var 4 

Invoking the continuation with a value causes evaluation to resume at the call/cc , with the given value replacing the call/cc . Thus, invoking cont with the value 3 results in the following:

(define var (call/cc (lambda (cc) cc ) ) ) --> (define var ) --> (define var 3) 

Thus, var is bound to 3. If we invoke cont with 4, we get:

(define var (call/cc (lambda (cc) cc ) ) ) --> (define var ) --> (define var 4) 

The result is that var is now bound to 4.

As a more complex example, consider the following definition of a factorial procedure:

(define cont '()) (define (factorial n) (if (= n 0) (call/cc (lambda (cc) (set! cont cc) 1 ) ) (* n (factorial (- n 1))) ) ) 

The base case is a call to call/cc . Then when (factorial 3) is called, the execution state when the base case is reached is:

(* 3 (* 2 (* 1 ))) 

As before, represents the call to call/cc . The argument to call/cc sets the global variable cont to refer to the newly created continuation and then evaluates normally to 1. The value 1 thus replaces the call/cc , resulting in a final value of 6:

> (factorial 3) 6 

If we then invoke the continuation with the value 3, the 3 replaces the call/cc in the execution state represented by the continuation:

> (cont 3) ; executes (* 3 (* 2 (* 1 3))) 18 

If we call (factorial 5) , cont is modified to refer to a continuation representing the execution:

(* 5 (* 4 (* 3 (* 2 (* 1 ))))) 

Invoking the continuation on 4 then results in 480:

> (factorial 5) 120 > (cont 4) ; executes (* 5 (* 4 (* 3 (* 2 (* 1 4))))) 480 

Signaling Errors

We can use first-class continuations to implement a basic mechanism for aborting a computation and signaling an error. We begin with a simple procedure to print an error message:

(define (report-error message) (begin (display "Error: ") (display message) (newline) ) ) 

This procedure expects to be called with a message string, and it prints out Error: followed by the message to standard out. However, invoking the procedure does not abort the computation in the caller. Thus, if we encounter an error in a larger computation, invoking report-error causes a message to print but continues where the computation left off. The following is an example:

(define (inverse x) (if (= x 0) (report-error "0 has no inverse") (/ 1 x) ) ) 

The inverse procedure reports an error if the argument x is zero. However, it still returns the (undefined) result of calling report-error to the caller of inverse . This can result in an error at the interpreter level:

> (+ (inverse 0) 1) Error: 0 has no inverse +: contract violation expected: number? given: # argument position: 1st other arguments. 1 context. [context elided]

In this Scheme implementation, the newline procedure returns a special #void value, which gets returned by report-error and then by inverse . The caller of inverse then attempts to add 1 to this result, resulting in an interpreter error.

In order to abort the computation entirely once an error has been signaled, we can make use of a continuation. We arrange for the continuation to save the control state at the top level of a program. but with a following invocation to report-error if an error message is provided:

(define error-continuation (let ((message (call/cc (lambda (c) c) ) ) ) (if (string? message) (report-error message) ) message ) ) 

Here, the call to call/cc saves the control state with the program about to bind the name message within a let to the result of invoking the continuation. In the initial computation, the continuation object is passed to the lambda , which immediately returns it. The call to call/cc evaluates to this value, so message is bound to the continuation object itself, and the body of the let is evaluated. This checks if message is a string, calling report-error if this is the case. The let as a whole evaluates to the value of message , which is then bound to error-continuation in the global frame.

If we invoke error-continuation again, execution will resume at the point of binding message , and it will eventually result in error-continuation being rebound to something other than the continuation object. To avoid losing the continuation, we can bind another name to it:

(define error error-continuation) 

Now even if error-continuation is rebound, the name error still refers to the continuation object.

If we invoke error with a string, the continuation is invoked with that value, and the value is plugged into where the continuation was created. Thus, message is bound to the string, and the body of the let is evaluated. Since message is a string, report-error is called, printing an error message. The let evaluates to the message string, which is then bound to the name error-continuation in the global frame. At this point, execution has reached the top level, so computation is completed without causing an error in the interpreter.

If we repeat our previous example, but invoking error rather than report-error , we get the following:

(define (inverse x) (if (= x 0) (error "0 has no inverse") (/ 1 x) ) ) > (+ (inverse 0) 1) Error: 0 has no inverse 

We no longer have an error reported by the interpreter itself.

Call and Return

First-class continuations can be used to emulate the more restricted control constructs provided by imperative languages. For instance, Scheme does not provide a specific mechanism that allows a procedure to terminate abruptly, returning a value to the caller. However, we can emulate call and return, including abrupt returns, with continuations. We do so by explicitly representing the call stack in a data structure that provides push and pop operations:

(define call-stack '()) (define (push-call call) (set! call-stack (cons call call-stack)) ) (define (pop-call) (let ((caller (car call-stack))) (set! call-stack (cdr call-stack)) caller ) ) 

We will use this call stack to store a procedure’s continuation when it calls another procedure. A return just pops a continuation off the stack and invokes it with the given return value:

(define (return value) ((pop-call) value) ) 

We then provide a mechanism for saving a caller’s continuation, by pushing it onto the call stack, and invoking the callee. For simplicity, we restrict ourselves to single-argument functions here, but this can be generalized using Scheme’s variadic arguments.

(define (call func x) (call-with-current-continuation (lambda (cc) (push-call cc) (func x) ) ) ) 

We can then write procedures that use the call stack to terminate abruptly:

(define (foo x) (if ( x 10) (return x) ; return x if ) (let ((y (- x 10))) (return (+ x (/ x y))) ; otherwise return x + x / (x - 10) ) (some more stuff here) ; control never reaches here ) (define (bar x) (return (- (call foo x))) ; call foo and return the negation (dead code) ; control never reaches here ) 

We can then call foo and bar :

> (+ 1 (call foo 3)) 4 > (+ 1 (call foo 20)) 23 > (+ 2 (call bar 3)) -1 > (+ 2 (call bar 20)) -20 

Exceptions

We can simulate exception handling with a handler stack, using the same approach as call and return above. The following is a complete implementation:

(define handler-stack '()) (define (push-handler handler) (set! handler-stack (cons handler handler-stack)) ) (define (pop-handler) (let ((handler (car handler-stack))) (set! handler-stack (cdr handler-stack)) handler ) ) (define exception-state #f) (define (set-exception) (set! exception-state #t) ) (define (clear-exception x) (set! exception-state #f) x ) (define (throw exception) (set-exception) ((pop-handler) exception) ) (define (try func x handler_func) (let ((result (call-with-current-continuation (lambda (cc) (push-handler cc) (func x) ) ) ) ) (if exception-state (clear-exception (handler_func result)) result ) ) ) 

We can then define functions that use exceptions:

(define (foo x) (if (= x 0) (throw "invalid argument: 0\n") (/ 10 x) ) ) (define (bar x) (+ (foo x) 1) ) (define (baz x) (try bar x (lambda (exception) (display exception) '() ) ) ) 

Now we can invoke baz with a valid and an erroneous argument:

> (baz 2) 5 > (baz 0) illegal argument: 0 () 

© Copyright 2016, Amir Kamil, licensed under the Creative Commons Attribution-ShareAlike 4.0 International license.