## 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 1 3 5 2 4
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:
 The C++ Cookbook mastering the language

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.