Preprint to: L. Allison, 'Some Applications of Continuations', The Computer Journal, Volume 31, Issue 1, pp.9-16, doi:10.1093/comjnl/31.1.9, 1988.

# Some Applications of Continuations

#### L. Allison, Department of Computer Science,Monash University, Clayton, Victoria 3168, Australia

 home  Bib  Algorithms  Bioinfo  FP  Logic  MML  Prog.Lang and the  mmlist

FP (external)
FP (local)

Semantics

Abstract: Continuations are used in [denotational semantics] to describe control commands such as jumps. Here it is shown that they can be used as a programming technique to simulate backtracking and co-routines.

Keywords: continuation, backtracking, coroutine, non-determinism, functional programming.

# Introduction.

Continuations are used in denotational semantics [Stra74] [Miln76] to describe the semantics of control mechanisms and of control commands such as jumps. Continuations are an example of a sophisticated use of high order functions. Strachey and Wadsworth [Stra74] give their origins in the tail functions of Mazurkiewicz [Mazu71] and of Morris. Here, continuations are used as a programming technique to simulate non-determinism and coroutines either in a functional language or when using a functional style in an imperative language. It is hoped that this will further the use of this powerful tool from the functional programming armoury.

Functional composition, o, is the usual way of combining two functions:

```  f:B->C,  g:A->B
fog x = f(g x)
```

Two composed functions pass an intermediate value between themselves. Continuations give another way to combine functions. There is a function g' related to g:

```  g':(B->C)->A->C
g' f x = f(g x)
```
Note that fog = g' f. f is a continuation to g'. In this case, g' passes a value (g x) and control to f. There is no o operator involved. g' has the extra freedom to manipulate the flow of control and it will be exploited in the following sections.

## Non-determinism.

Non-determinism appears where there may be zero, one or many solutions to a problem and where a search is necessary to discover which will succeed. This section illustrates the implementation of non-determinism by continuation functions via an example from parsing. Non-determinism is a central feature of logic programming languages such as Prolog [Cloc81]. The technique of implementing non-determinism in a functional language is present in the various denotational semantics of Prolog [Jone84] [Nich85] and in implementations of Prolog in functional programming [Carl84] but it deserves wider exposure. The use of continuations is implicit in the organization of the trail stack in a conventional implementation of Prolog.

The following grammar is non-deterministic:

```  <S> ::= <aORaa> <aORaa>
<aORaa> ::= a | aa
```
The string "aaa" has two parses - a(aa) or (aa)a. Such a grammar cannot usually be parsed by recursive descent because of the non-determinism. However, recursive descent plus continuations can do the job.

The following example indicates how this grammar can be parsed. It is written in a simple functional language. The answers returned by the parser are just indications of success but the parse trees could easily be returned. First some general operators are defined:

```  Types or domains:
Ans = {Success}*
input :Text = char*
cont :Pcont = Text->Ans
Parser = Pcont->Text->Ans = Pcont->Pcont

fin input = if null input then [Success] else nil
fin :Pcont

letter ch cont input
= if null input then nil
else if ch = hd input then cont tl input
else nil
letter :char->Parser

seq p1 p2 cont = p1 (p2 cont)
seq :Parser->Parser->Parser

either p1 p2 cont input
= append (p1 cont input) (p2 cont input)
either :Parser->Parser->Parser
```

Using these operators, the particular grammar can be programmed:

```  a = letter 'a'
aORaa = either a (seq a a)
S = seq aORaa aORaa
a, aORaa, S :Parser
```

The expression 'S fin string', will indicate how many parses the string has.

Each parser has a parser continuation, a Pcont, which follows it. The function 'seq' forms the sequential composition of two parsers, as indicated by concatenation in BNF. The definition of seq exactly follows that of sequential composition (;) in the standard semantics of programming languages. To parse 'p1' and then 'p2' and finally do 'cont', call p1 with a continuation which is (p2 cont). The function 'either' performs alternation, '|'. It simulates non-determinism by trying both alternatives with the following continuation and appending results.

If only one solution is required, fin should be modified to raise an exception which should be caught by S.

### Pascal.

The central idea in the parser of the previous section is that of parser continuations, Pcont. These can be programmed in Pascal. The only slight difficulty is the lack of curried functions (or procedures). This means 'seq' and 'either' cannot be used in partially parameterized form which renders them rather pointless; suitable in-line code is more appropriate.

```
program Continuations(input, output);
var l:array[1..80]of char;  {the input string}
len:integer;              {its length}

procedure fin(m:integer);
begin if m=len+1 then writeln('Success') end;

procedure aORaa(procedure cont(p:integer); n:integer);
begin if l[n]='a' then
begin cont(n+1);                   {a }
if l[n+1]='a' then cont(n+2) {aa}
end
end;

procedure sentence(procedure cont(p:integer); n:integer);
procedure aORaaCont( n:integer );
begin aORaa(cont, n) end;
begin aORaa( aORaaCont, n )
end;

begin writeln('type a string for parsing');
while not eof do
begin len:=0;
while not eoln do
sentence( fin, 1 );
end
end.
```

In this version the input is held in a global buffer 'l'. Because Pascal is imperative it is possible, although not essential, for the final continuation 'fin' to act as a side effect.

If it is only necessary to accept the first parse out of many, procedure fin should be modified to do a non-local goto out of the parser.

### Parsers.

In parsing terms, the original grammar requires a slow-back top-down parser. The string "aaa" can be parsed as a(aa) or (aa)a. The first aORaa can succeed by parsing "a" but its activation cannot be discarded because it may be required to succeed again as "aa". When one of the parsers is run, the first aORaa in a sentence calls the second one which is incorporated in the first's continuation. The first one is still active and can succeed again in another way.

## Coroutines.

A set of coroutines is a collection of routines which pass control amongst themselves. A coroutine is resumed from the point at which it was last suspended; apart from its initial start it resumes just after the point that it last resumed some other coroutine. Simula and Modula provide coroutines. In this section the example of merging two search trees will be used to illustrate how continuations can simulate coroutines.

A search tree is a binary tree in which the elements in the left subtree are less than the element in the root which is less than the elements in the right subtree. This property also applies to all subtrees. The problem is to merge the elements of two search trees so as to print one ascending list of their elements. The natural solution to this problem uses two coroutines. Each coroutine traverses one tree in infix order. Coroutine A resumes coroutine B when the element that A is examining exceeds the element that B is examining.

There are many other solutions such as

```λ tree1, tree2. listmerge (flatten tree1) (flatten tree2)
```
but these all produce temporary structures or visit some nodes more than once. The tree merge algorithm given here simulates the coroutine solution.

### Tree flattening.

The tree merge algorithm is based on the following unusual way of flattening a single tree.

```  Type:
cont :Cont = Void -> List of element

flatten t =
let fin () = nil,
fl t cont =
if null t then cont()
else let contright()=(elt t).(fl(right t)cont)
in  fl (left t) contright
in  fl t fin

flatten :Tree of element -> List of element
fin, contright :Cont
fl :Tree of element -> Cont -> List of element
```

The continuation parameter 'cont' of 'fl' is an accumulating parameter. It is a function which will flatten the rest of the tree once fl has flattened the left subtree. Note that '.' is the infix list constructor. Flatten can easily be programmed in Pascal.

### Tree merging.

The tree flattening function of the previous section can be used as the basis of a tree merging function. To merge two trees first find their smallest (left most) values, then traverse one tree until an element larger than a 'switch' value is met. Then an 'alternative' function must be invoked. The alternative will traverse the other tree until a switch back to the first tree is necessary. The alternative is the coroutine or cofunction of the current traversal function.

```
Type:
Cont = element -> Cont -> List of element

merge tree1 tree2 =
let rec
traverse tree cont switch alternative =
if null tree then
cont switch alternative
else
traverse (left tree) (travright tree cont) switch alternative,

travright tree cont switch alternative =
if null tree then
cont switch alternative
else if elt tree <= switch then
(elt tree).(traverse (right tree) cont switch alternative)
else
alternative (elt tree) (travright tree cont ),       --- [*]

m tree1 cont1 tree2 cont2 =
if not null (left tree1) then
m (left tree1) (travright tree1 cont1) tree2 cont2
else if not null (left tree2) then
m tree2 cont2 tree1 cont1
else if elt tree1 <= elt tree2 then
travright tree1 cont1 (elt tree2) (travright tree2 cont2)
else
travright tree2 cont2 (elt tree1) (travright tree1 cont1),

fin  switch cont =  cont maxint halt,

halt switch cont = nil
in
if null tree1 then
traverse tree2 halt maxint halt
else if null tree2 then
traverse tree1 halt maxint halt
else m tree1 fin tree2 fin

fin, halt :Cont
traverse, travright :Tree of element -> Cont -> Cont
m :Tree of element -> Cont -> Tree of element -> Cont -> List of element
merge : Tree of element -> Tree of element -> List of element
```

A continuation simulates a coroutine. Its element parameter is a parameter of the resumption. The Cont parameter is the other coroutine, itself to be resumed at a later date. When the alternative is resumed [*] it is given a switch parameter and the "current" coroutine. Note that travright is not a continuation but

``` travright t c :Cont,  if  t:Tree of element,  c:Cont
```

If one of the trees is empty, traverse the other tree. Otherwise 'm' finds the least element of tree1 (and later tree2) while building a continuation to traverse tree1. When the continuation for each tree is built, the appropriate one is started and the two of them swap control as necessary.

### Pascal and Algol.

The treemerge function cannot be programmed in Pascal because this language does not allow recursive function types such as 'Cont'. However it can be programmed in Algol-68 which does allow such types.

McVitie and Wilson give an Algol-60 program for the stable marriage problem [McVi71, algorithm 2 and sec3.2]. It uses recursive procedure calls in a way that mimics continuations. Coincidentally, it appeared at about the same time as Mazurkiewicz's paper [Mazu71]. The stable marriage problem has a natural solution by coroutines [Alli83].

## Conclusion.

The use of continuations allow a function to govern the flow of control into and out of what would normally be considered a subsequent computation. This allows unusual control regimes such as non-determinism and coroutines to be simulated in functional programming. In particular, non-deterministic grammars can be parsed by simple recursive descent plus continuations and functions can be made to cooperate as coroutines.

### References.

[Alli83] L. Allison. Stable marriages by coroutines. Information Processing Letters 16 pp61-65 Feb 1983.
[Carl84] M.Carlsson. On implementing Prolog in functional programming. 1984 International Symposium on Logic Programming pp154-159.
[Cloc81] W.F.Clocksin, C.S.Mellish. Programming in Prolog. Springer Verlag 1981.
[Jone84] N.D.Jones, A.Mycroft. Denotational semantics of Prolog. 1984 International Symposium on Logic Programming pp281-288
[Mazu71] A.W.Mazurkiewicz. Proving algorithms by tail functions. Information and Control 18 p220-226 1971.
[McVi71] D.G.McVitie, L.B.Wilson. The stable marriage problem. CACM 14(7) pp486-490 July 1971, and algorithm 411 CACM 14(7) pp491-492 July 1971.
[Miln76] R.Milne, C.Strachey. A Theory of Programming Language Semantics. Chapman Hall 1976 (2 vols).
[Nich85] T.Nicholson, N.Foo. A denotational semantics for Prolog. Basser Dept. Computer Science, University of Sydney 1985.
[Stra74] C.Strachey, C.P.Wadsworth. Continuations, a mathematical semantics for handling full jumps. PRG-11 Oxford University 1974

See [treemerge.a68], [Pascal] and also .

 Coding Ockham's Razor, L. Allison, Springer A Practical Introduction to Denotational Semantics, L. Allison, CUP

 Linux  Ubuntu free op. sys. OpenOffice free office suite The GIMP ~ free photoshop Firefox web browser

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University, was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.) Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Friday, 01-Jul-2022 17:03:50 AEST.