CONTINUATIONS (CONTINUATION- PASSING STYLE, CPS)

Functional parameterization of functions
"Continuation-passing style is a notation notation that makes explicit every aspect of the control and data control and data flow" (Andrew W. Appel).

---

The CPS Technique
Definición

CPS is a functional programming technique consisting of the following:

• In a function f(x), of parameter(s) x, an extra parameter < i>c, which represents a more general function, i.e., f(x, c).
  
  
• The new function, with arguments a and c, does not return the result r = f(a ), but the result of applying the function c to r, i.e., c(r) = c(f(a)). In general, f(x, c) = c(f(x)).

The function c with argument r represents what "remains to be done" (after obtaining the first result r) to complete the final result of the function f. That is why c is called "continuation function" or, simply, "continuation". And the function that includes as parameter a continuation function is called "function with continuation" or "CPS function".


Difference between the functions f(a, c) and c(f(a))

In both cases the result is the same, but there are important differences:

1. In the first function, c is a parameter and in the second one it is not.
   
   
2. In the first function, after executing and obtaining the result r, c (with argument r) is called. Subsequently, the control is returned. In the second function, after obtaining r, there is return (of the result and of the control) to the function c.
   
   
3. In the first case, there may be higher-order continuations, i.e., the continuation could in turn invoke another function with continuation, which in turn could call another function with continuation, etc., so the function is functionally open. In the second case, the function is functionally closed.

Implementation in MENTAL
Specification

The CPS function in MENTAL can be represented in the classical form (with parameters in parentheses) f(x c) being:

x: parameter(s) of the function f.
c: function continuation.

Definition:

⟨( f(x c) = c(f(x)) )⟩

Example

1. Normal style.
   
   Function definition:
   ⟨( square(x) = x*x )⟩
   
   Function usage:
   square(4) // ev. 4*4 ev. 16
   
   
2. CPS.
   
   Function definition (an additional parameter is added):
   ⟨( square(x c) = c(x*x) )⟩
   
   Definition of a function continued:
   ⟨( sum5(x) = x+5 )⟩
   
   Function usage:
   square(4 add5) // ev. add5(4*4) ev. add5(16) ev. 16+5 ev. 21
   
   Definition of another function continued:
   ⟨( prod5(x) = 5*x )⟩
   
   Using the function with the new function continued:
   square(4 prod5) // ev. prod5(4*4) ev. prod5(16) ev. 5*16 ev. 80

Continuation function with parameters

The function c represents a function with any number of parameters. For example, generalizing the above example by one parameter,

⟨( sum(n)(x) = x+n )⟩

square(4 add(23)) // ev. add(23)(4*4) ev. 16+23 ev. 39

An example of a continuation function with two parameters is the following:

⟨( linear(a b)(x) = (a*x + b) )⟩

square(4 linear(2 5)) // ev. linear(2 5)(4*4) ev. 2*16 + 5 ev. 37

Note that it is necessary to separate the parameters of the continuation function from the parameter corresponding to the result of the CPS function.


Null continuation

In the CPS function

⟨( square(x c) = c(x*x) )⟩

if we use as continuation the null expression (θ), we have, for example:

square(4 θ) // ev. square(4)

Therefore, when the continuation is null, we are in the normal style.


Bound and free variables in CPS

A CPS function −like any generic parameterized expression− has variables of two types:

• bound. These are the parameters used by CPS functions and by continuations.
• Free. They are the variables of the abstract space.

Example:

(u=7 v=2 w=5)
⟨( fun(x c) = c(x + w) )⟩ // bound: x, c free: w
⟨( cont(x) = (u*x + v) )⟩ // bound: x free: u, v

fun(4 cont) // ev. cont(4+5) ev. cont(9) ev. (7*9 + 2) ev. 65

Continuation in recursive functions

Applying a continuation to a recursive function produces a new (extended) function that applies to the original recursive function.

Example with factorial:

1. Normal style:
   
   ⟨( fac(n) = (1 ← n=1 →' n*fac(n−1))) )⟩

fac(4) // ev. 4*3*2*1 ev. 24
   
   
2. CPS:
   
   ⟨( facx(n c) = (c(fac(n))) )⟩
   
   If we use the following function
   
   ⟨( linear(a b)(x) = (a*x + b) )⟩
   
   we have:
   
   facx(4 linear(2 5)) // ev. linear(2 5)(24) ev. 224+5 ev. 53

Example with Fibonacci sequence: 1, 1, 2, 2, 3, 5, 8, 13, ...

1. Normal style:
   
   ⟨( fibo(n) = (1 ← n>2 →' (fibo(n−1) + fibo(n−& 2)))) )⟩

fibo(1) // ev. 1
fibo(2) // ev. 1
fibo(3) // ev. 2
fibo(4) // ev. 3
fibo(5) // ev. 5
...
   
   
2. CPS:
   
   ⟨( fibox(n c) = c(fibo(n)) )⟩
   
   If we use the following function
   
   ⟨( double(x) = 2*x )⟩
   
   we have:
   
   fibox(1 double) // ev. double(1) ev. 2
fibox(2 double) // ev. double(1) ev. 2
fibox(3 double) // ev. double(2) ev. 4
fibox(4 double) // ev. double(3) ev. 6
fibox(5 double) // ev. double(5) ev. 10
...
   
   What you get are the double values of the Fibonacci sequence.

Higher order continuations

A continuation function can, in turn, have another continuation function. The general form for two continuation functions is

⟨( f(x c1 c2) = c2(c1(f(x))) )⟩

For example:

⟨( square(x c1 c2) = c1(x*x c2)) )⟩ // eq.
⟨( square(x c1 c2) = c2(c1(x*x))) )⟩

Definition of a function continuation c1:

⟨( sum5(x) = x+5 )⟩

Definition of a function continuation c2:

⟨( prod3(x) = 3*x) )⟩

Using the function:

square(4 add5 prod3)) // ev. prod3(add5(4*4)) // ev. prod3(16+5) ev. prod3(21) ev. 63

The higher-order continuation functions could, in turn, have parameters.


Beyond CPS. The parameterization of expressions

The CPS technique is the functional parameterization of functions, but it is a particular case of the general case of adding parameters to expressions, which can be done in MENTAL.

• All kinds of expressions (functions, rules, objects, data, etc.) can be parameterized.
  
  
• Parameters can be inserted at strategic points to facilitate their later use in a more generic way.
  
  
• The same parameter can be instantiated as a function or as data.
  
  
• You can add as many parameters as you want to the expressions.

Examples of function on intermediate results (not on the final result):

1. Factorial:
   
   ⟨( fac(n c) = (c(1) ← n=1 →' c(n)*fac(n−1 c)))) )⟩
   
   
   fac(1 c) // ev. c(1)
fac(2 c) // ev. c(2)*c(1)
fac(3 c) // ev. c(3)*c(2)*c(1)
...
   
   If c=θ, we have the normal factorial function.
   
   If we use the function ⟨( double(x) = x*2 )⟩, we have:
   
   
   fac(1 double) // ev. double(1) ev. 2

fac(2 double) // ev. double(2)*double(1) ev. 4*2 ev. 8

fac(3 double) // ev. double(3) * double(2) * double(1) ev. 6*4*2 ev. 48 ...
   
   
2. Fibonacci Sequence: 1, 1, 2, 2, 3, 5, 8, 13, ...
   
   ⟨( fibo(n c) = (c(1) ← n>2 →' c(fibo(n−1 c) + fibo(n−2 cb>)))) )⟩
   
   
   fibo(1 c) // ev. c(1)
fibo(2 c) // ev. c(1)

fibo(3 c) // ev. c(fibo(2 c) + fibo(1 c)) ev. c(2*c(1))

fibo(4 c) // ev. c(fibo(3 c) + fibo(2 c)) ev. c(c(2*c(1)) + c(1))
...
   
   If c=θ, we have the normal Fibonacci function.
   
   If we use the same function above (double) as c, we have:
   
   
   fibo(1 double) // ev. double(1) ev. 2

fibo(2 double) // ev. double(1) ev. 2

fibo(3 double) // ev. double(2 + 2) ev. 8

fibo(4 double) // ev. double(2 + 8) ev. 20
...

Examples of data parameterization:

1. ⟨(unodos(c) = c(12))⟩
   
   Parameterization using a function:
   
   
   ⟨(double(x) = 2*x)⟩

unodos(double) // ev. 2*12 ev. 24
   
   Parameterization using data:
   
   
   unodos(123) // ev. 123(12)
   
   
2. ⟨( record(c) = (c(6) c(12) c(9) c(17) c(8))) )⟩
   
   Parameterization using a function:
   
   
   ⟨( selec(n)(x) = (x<n → x) )⟩ // select x if less than n

register(select(10)) // ev. (6 9 8)
   
   Parameterization using data:
   
   
   register(abc)) // ev.(abc(6) abc(12) abc(9) abc(17) abc(8))
   
   
3. ⟨( log(c) = (6 12 9 17 8)c )⟩
   
   Parameterization using a function:
   
   
   ⟨( selec(s)(x) = ( x⇓s ) )⟩ // s is the selection criterion

register(select(>9)) // ev. (6 12 9 17 8)⇓(>9) ev. (12 17)
   
   Parameterization using data:
   
   
   record(u v w) // ev. (6 12 9 17 8)(u v w)

Conclusions

In traditional programming languages, f is fixed (it cannot be variable). In MENTAL, it can be variable, so the concept of continuation is irrelevant, since it makes no difference whether the continuation is included as a parameter or as a function. For example,

⟨( square(x) = x*x )⟩
⟨( double(x) = x*2 )⟩
⟨( f(x c) = c(f(x) )⟩

Variable function name:

(f = square)
f(5 c) // ev. square(5 c)) ev. c(square(5)) ev. c(25)

Function name continuation variable:

(c = square)
f(5 c) // ev. f(5 square) ev. square(f(5)) ev. f(5)*f(5)

Variable function name and variable continuation function name:

(f = square)
(c = double)
f(5 c) // ev. square(5 double) ev. double(square(5)) ev. double(25) ev. 50

---

Addenda
Main features of the CPS technique

• The CPS technique can be considered as a high-level parameterized branching (goto), since a call to a continuation function is actually a jump to another part of the program.
  
  
• By introducing an additional parameter in the function definition, functions are generalized. Another way of looking at it is to say that the original language is extended and made more flexible.
  
  Paradoxically, at the same time, we can find ourselves with an environment of a lower level of abstraction, of greater detail, because the computational sequences are made explicit. This is why this technique is used internally in compilers and interpreters of programming languages, especially functional ones, to successively approximate a high-level language to another low-level language (such as machine code) by means of sequences of expressions.
  
  In fact, a certain analogy can be established between a program made with continuations and a von Neumann-type machine, where the CPS execution sequences would correspond to the instructions and the variables to the registers of the machine.
  
  
• If a program is performed entirely with continuations, then returns (control and value returns) are completely eliminated. Consequently, there is no need to internally use a stack for storing these values, making such an implementation simpler.
  
  The execution would consist of a sequence of the form.
  
  
  (f1(a1 c1) f2(a2 c2) f3(a3 c3) ...)
  
  being:
  
  
  fi: function with continuation
  ai: argument(s)
  ci: continuation
  
  The environment is dragged from one element to the next and calls and data are made explicit.
  
  CPS has the effect of linearizing the execution of a program, as opposed to the classical programming system, which we can qualify as "reactive", since each call corresponds to a return with a response.
  
  Any traditional function can be rewritten in CPS, so it is possible to discard the stack completely and use only continuations.
  
  
• The CPS technique has an advantage over normal functions when the result of the function involves a large amount of data, since there is no need to group them together to return as a result, nor is there a need to collect them in the calling function.
  
  
• What is obtained with the CPS technique is not a higher order function (function of function), since this concept corresponds to that of a function in which the parameters are functions and the result is another function.

Applications of the CPS technique

The CPS technique was born in the late 1960s. Since then, in addition to its aforementioned application in the development of compilers and interpreters, it has also been applied in a variety of areas:

• Program transformation.
• Generators.
• Exceptions.
• Remote procedure calls.
• Persistent computing.
• Concurrent programming.
• Event-driven programming.
• Etc.

Bibliography

• Applel, Andrew W. Compiling with Continuations. Cambridge University Press, 1992.
  
  
• Friedman, D.P.; Wand, M.; Heynes, C.T. Essentials of Programming Languages. The MIT Press, 1992. [Cubre el tema CPS en profundidad con el lenguaje functional Scheme.]
  
  
• Jones, Neil. D.; Gomard, Carsten K.; Sestoff, Meter. Partial Evaluation and Automatic Program Generation. Prentice Hall International Series in Computer Science, 1993. [Se estudia CPS como técnica en la generación de programas.]
  
  
• Kalsey, Richard A. A correspondence between continuation passing style and static single assignement form. ACM SIGPLAN Notices, 30(3): 13-22, March 1995.
  
  
• Sabry, Amr; Felleisen, Mathias. Reasoning about programs in continuation-passing style. Lisp and Symbolic Computation, 6(3-4):289-360, 1993.
  
  
• Stansifer, Ryan. The Study of Programming Languages. Prentice-Hall, New Jersey, 1995. [Trata el tema CPS en el contexto del cálculo lambda.]