LA home

Also see:

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

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

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."


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

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

↑ © L. Allison,   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Tuesday, 07-Jul-2020 09:42:22 EDT.

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