# Some Applications of Continuations

Preprint to: The Computer Journal, vol.31, no.1, pp.9-16, doi:10.1093/comjnl/31.1.9, 1988

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

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

**o**g = 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 p_{1}p_{2}cont = p_{1}(p_{2}cont) seq :Parser->Parser->Parser either p_{1}p_{2}cont input = append (p_{1}cont input) (p_{2}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 'p_{1}' and then 'p_{2}' and finally do 'cont',
call p_{1} with a continuation which is (p_{2} 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 begin len:=len+1; read(l[len]) end; readln; writeln; sentence( fin, 1 ); writeln('finished; next one please') 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

λ tree_{1}, tree_{2}. listmerge (flatten tree_{1}) (flatten tree_{2})

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 tree_{1}tree_{2}= 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 tree_{1}cont_{1}tree_{2}cont_{2}= if not null (left tree_{1}) then m (left tree_{1}) (travright tree_{1}cont_{1}) tree_{2}cont_{2}else if not null (left tree_{2}) then m tree_{2}cont_{2}tree_{1}cont_{1}else if elt tree_{1}<= elt tree_{2}then travright tree_{1}cont_{1}(elt tree_{2}) (travright tree_{2}cont_{2}) else travright tree_{2}cont_{2}(elt tree_{1}) (travright tree_{1}cont_{1}), fin switch cont = cont maxint halt, halt switch cont = nil in if null tree_{1}then traverse tree_{2}halt maxint halt else if null tree_{2}then traverse tree_{1}halt maxint halt else m tree_{1}fin tree_{2}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 tree_{1} (and later tree_{2}) while
building a continuation to traverse tree_{1}.
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 [1990].