CSE3322, (S)ML IX : Introduction

Another F.P. technique:

• Continuations
  • are "just" functions (SML VI), but they
  • allow different "control mechanisms" to be implemented/simulated,
    
  • such as non-determinism.

Continuations

A continuation is a function that 'continues' a computation.

  (f o g) x = f(g x)

  fun g' c x = c(g x)

then g' f y = (f o g) y,   c is the continuation of g'

-- not v. exciting here, but g' has the option of not calling c at all, or calling it twice, etc..

. . . continuations . . .

A functional programming language does not support "state", but you can implement/simulate state . . .

  datatype State  = whatever
  and      Answer = whatever'

  and      Cont = State -> Answer

  and      Step = Cont -> State -> Answer
             (* = Cont ->      Cont     *)

. . . continuations

. . . and if

  f, g : Step
  s : State
  fin = fn s => <extract answer from s>
  fin : State -> Answer = Cont

  g (f fin) s : Answer

-- i.e. do g and then do f and then finish. (NB. Reads from left to right.)

Non-determinism by continuations

'success' is continue searching, 'fail' is return empty handed ([]), and 'fin' is return a solution (list).

  fun success cont   = cont
  and fail    cont L = []
  and fin     L      = [L]

'literal n' is just add 'n' to the partial solution

  fun literal n cont L = cont (n::L)

'either' takes two alternative search generators 'gen1' and 'gen2' and passes its continuation 'cont' to both of them, concatenating (@) all results that either(!) returns.

  fun either gen1 gen2 cont L =
    (gen1 cont L) @ (gen2 cont L)

. . . non-determinism

'pipe' passes all results, if any, from 'gen1' to 'gen2'

  fun pipe gen1 gen2 cont =
    gen1 (gen2 cont)

To 'run' a search generator starting with the empty solution ([]), do it and then 'fin'.

  fun run gen = gen fin []

'choose n' is either n, or n-1, ..., or 1

  fun choose  n =
    if n=0 then fail  (* no choices left *)
    else either (literal n) (choose(n-1))

. . . non-determinism

'doo n' does a step n times

  doo n gen = if n=0 then success
              else pipe (doo(n-1)gen) gen

'filter' passes on any results that satisfy a predicate 'p'.

  fun filter p cont L =
    if p L then cont L else []






. . . e.g. n-queens problem


 queens n =
  doo n (pipe (choose n) (filter valid))


If n=5 . . . 
[[2,4,1,3,5],
[3,1,4,2,5],
[1,3,5,2,4],
[2,5,3,1,4],
[1,4,2,5,3],
[5,2,4,1,3],
[4,1,3,5,2],
[5,3,1,4,2],
[3,5,2,4,1],
[4,2,5,3,1]]
: int list list






complete; also see
[Comp.J.]:


(* Using continuations as generators:
   L. Allison. Continuations Implement Generators and Streams.
   Computer J., BCS, Vol.33, No.5, pp.460-465, 1990.

Cont = partial solution -> solution list
Generator = Cont -> Cont

fin :Cont
success, fail :Generator
literal : 't -> Generator
choose  :Int -> Generator
either, pipe :Generator -> Generator -> Generator
doo :Int -> Generator -> Generator
run :Generator -> solution list
*)
(* ------------------------------------------general operators-- *)
fun fin     L = [L]

and success cont   = cont
and fail    cont L = []

and literal n cont L = cont (n::L)      (* add n to partial soln *)

and either  gen1 gen2 cont L = (gen1 cont L) @ (gen2 cont L)

and pipe    gen1 gen2 cont   = gen1 (gen2 cont)

and filter  p cont L = if p L then cont L else []

and run gen = gen fin []

and choose  n = if n=0 then fail  (* no choices left *)
                else either (literal n) (choose(n-1))

and doo n gen = if n=0 then success else pipe (doo(n-1)gen) gen

(* ---------------------------------------------------n queens-- *)
and valid []     = true |
    valid (h::t) = let
      fun v col []     = true
        | v col (a::b) =
            if h=a orelse h=a+col orelse h=a-col then false
            else v (col+1) b
      in v 1 t
      end

and queens n = doo n ( pipe (choose n) (filter valid) );

(* e.g. *)  run (queens 5)

(* N-queens using Continuations for Generators. *)
(* Translated to SML, LA, CSSE, Monash, .au, 21/6/2005 *)








Summary

Continuations are "just" functions.
They can be used to program (implement, simulate)
state-transformers, and non-standard control mechanisms, e.g.

non-determinism
  (Prolog's
control mechanism),
coroutines,
exceptions,
arbitrary jumps and other 'sequencers'.





Origins
A. W. Mazurkiewicz, Proving algorithms by tail functions,
Information and Control, 18, pp. 220-226, 1971.

Also see:

R. W. Floyd,
Nondeterministic algorithms,
J.ACM, 14(4), pp. 636-644, 1967.



 


7/2005 ©
L. Allison,
School of Computer Science and Software Engineering,
Monash University, Australia 3800.

Created with "vi (Linux & Solaris)",    charset=iso-8859-1