(* Ambient in ML *)
(*
http://groups.google.com/group/fa.caml/browse_thread/thread/d919ffcfd7af90e3/f9f4d239cca2f32b
*)

(* Open the DelimCC library
  http://pobox.com/~oleg/ftp/Computation/Continuations.html#caml-shift
*)
open Delimcc;;
let shift p f = take_subcont p (fun sk () ->
  push_prompt p (fun () -> (f (fun c -> 
    push_prompt p (fun () -> push_subcont sk c)))))
;;

(* How evaluation has finished *)
type res = 
    Done                             (* Finished with the result *)
  | Exc     of exn                   (* Got an exception -- no good *)
  | Choices of (unit -> res) list    (* Alternative universes *)

exception Amb		             (* Raise when all choices are bad *)
;;

let topprompt = new_prompt ();;

(* If it looks like an OS scheduler, it's because it is *)
let toplevel thunk =
  let rec loop queue = function 
  | Done (* evaluation of a branch finished successfully *)
     -> ()
  | Exc _ -> try_another queue
  | Choices more  -> (* OK, add them to the end: breadth-first *)
      try_another (queue @ more)
  and try_another = function
  |  [] -> raise Amb (* No more choices *)
  |  h::t -> loop t (try h () with e -> Exc e)
  in
  loop [] (push_prompt topprompt 
	     (fun () -> try let _ = thunk () in Done with e -> Exc e))
;;

(* Split the universe. Something like `fork (2)' *)
let amb choices = shift topprompt (fun sk -> 
  Choices (List.map (fun choice -> (fun () -> sk choice)) choices));;


(*  Andrej Bauer's test *)
let test1 () =
  let v = 
    if (amb [(fun _ -> false); (fun _ -> true)]) then
      7
    else failwith "Sinner!"
  in Printf.printf "got the result %d\n" v
;;

let test1r = toplevel test1;;
(*
  got the result 7
*)

(* Test that invokes the Pythagorean spirit *)
let numbers = 
  List.map (fun n -> (fun () -> n))
    [1;2;3;4;5];;
let pyth () = 
  let (v1,v2,v3) =
    let i = amb numbers in
    let j = amb numbers in
    let k = amb numbers in
    if i*i + j*j = k*k then (i,j,k) else failwith "too bad"
  in Printf.printf "got the result (%d,%d,%d)\n" v1 v2 v3
;;

let pythr = toplevel pyth;;
(*
 got the result (3,4,5)
*)