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)

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 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 'p₁' and then 'p₂' and finally do 'cont', call p₁ with a continuation which is (p₂ 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

λ tree1, tree2. listmerge (flatten tree1) (flatten tree2)

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 tree₁ (and later tree₂) while building a continuation to traverse tree₁. 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].