Continuations

LA home
Computing
FP
 SML
  SML97
   Conts.

Also see:
Sem.
 n-Queens

Continuations can be used to implement non-standard control mechanisms such as non-determinism (backtracking):


(* 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 *)

[[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
  Q  
    Q
 Q   
   Q 
Q    
13524
e.g.

Note that either passes on its continuation twice, once to each its two alternatives, gen1 and gen2.

queens n can be read as, "do the following n times (doo n), choose an int between 1 and n inclusive (choose n) and (pipe) check that it does not invalidate the problem's constraints (filter valid) given the previous choices."

Notes

Continuations Implement Generators and Streams. The Computer J., 33(5), pp.460-465, 1990,
and more [conventional].
www:

SML:
:: cons
[x1,...] list
[ ] list
@ append
fn =>  &lambda .
: has type
Compared

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Saturday, 25-May-2019 12:14:50 EDT.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.