[Caml-list] Amb

[Jonathan Bryant]

All,

I'm having to learn Scheme for a class, and I ran across a simple but
really useful predicate: amb. More info on this can be found here:
http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-
H-16.html#node_chap_14

Since OCaml doesn't seem to have this, I implemented it:

exception Amb
let rec amb l = match l with
| [] -> raise Amb
| h::t -> try h () with Amb -> amb t

let amb l = try Some (amb l) with Amb -> None

(* val amb : (unit -> 'a) list -> 'a option *)

I know things are not added to the standard library lightly, but it
seems that this one function doesn't really need it's own library and
could be easily added somewhere. It just seems that this would be a
small but convenient addition.

--Jonathan Bryant

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

[Brian Hurt]

Jonathan Bryant wrote:

> All,
>
> I'm having to learn Scheme for a class, and I ran across a simple but
> really useful predicate: amb. More info on this can be found here:
> http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-
> H-16.html#node_chap_14
>
> Since OCaml doesn't seem to have this, I implemented it:
>
> exception Amb
> let rec amb l = match l with
> | [] -> raise Amb
> | h::t -> try h () with Amb -> amb t
>
> let amb l = try Some (amb l) with Amb -> None
>

You might try:
let rec amb = function
| [] -> None
| h :: t ->
let r =
try
Some(h ())
with
| _ -> None
in
match r with
| None -> amb t
| Some(_) as e -> e
;;

As a slightly better implementation.

Brian

[Andrej Bauer]

To make this thread worthy of a non-beginner ocaml list, let me point
out that amb is supposed to work as an _angelic_ nondeterministic choice
operator. This means it must choose a value that, if at all possible,
leads to successful completion of the computation. In particular, the
piece of code (assuming exception Amb denotes failure)

if (abm [(fun _ -> false); (fun _ -> true)]) then
7
else
(raise Amb)

should return 7, i.e., the amb inside the conditional should "know" (be
told by an angel) that the right choice is the second element of the
list because it leads to 7, whereas chosing the first one leads to failure.

I am afraid the implementation given by Jonathan does not satisfy this
condition. And I don't see how to make it work. The scheme
implementation involves callcc magic. If anyone knows a reasonable
implementation of amb, I'd be interested to know.

Andrej

[Tom]

What would amb do with this kind of program:

let f_out = open_out "file1.tmp";;
output_string f_out "good\n";;
close_out;;

if (abm [(fun _ -> false); (fun _ -> true)]) then

let f_in = open_in "file1.tmp" in
if input_line f_in = "good" then exit 0 (* SUCCESS *)
else raise Amb
else
let f_out2 = open_out_get [Open_trunc] 0o777 "file1.tmp" in
output_string f_out2 "bad\n"

?

- Tom

[Jon Harrop]

On Friday 09 February 2007 21:55, Brian Hurt wrote:
> let rec amb = function
>
> | [] -> None
> | h :: t ->
>
> let r =
> try
> Some(h ())
> with
>
> | _ -> None
>
> in
> match r with
>
> | None -> amb t
> | Some(_) as e -> e
>
> As a slightly better implementation.

I think you're trying to box the returned value in order to evade non-tail
recursion but the OPs function was actually already tail recursive because
the recursive call to "amb" occurs outside the try..with.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

[Jon Harrop]

Spawn parallel universes?

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

_______________________________________________

[Brian Hurt]

On Sat, 10 Feb 2007, Jon Harrop wrote:

> On Friday 09 February 2007 21:55, Brian Hurt wrote:
>> let rec amb = function
>>
>> | [] -> None
>> | h :: t ->
>>
>> let r =
>> try
>> Some(h ())
>> with
>>
>> | _ -> None
>>
>> in
>> match r with
>>
>> | None -> amb t
>> | Some(_) as e -> e
>>
>> As a slightly better implementation.
>
> I think you're trying to box the returned value in order to evade non-tail
> recursion but the OPs function was actually already tail recursive because
> the recursive call to "amb" occurs outside the try..with.

He was doing the boxing on the return as well. And note, in the above
code I only box once.

Brian

[ol...@pobox.com]

Andrej Bauer wrote:
> let me point out that amb is supposed to work as an _angelic_
> nondeterministic choice operator. This means it must choose a value
> that, if at all possible, leads to successful completion of the

> computation.... The scheme implementation involves callcc magic.

> If anyone knows a reasonable implementation of amb, I'd be
> interested to know.

Here it is. Ocaml has something better than call/cc: delimited
continuations. So, amb is trivially implementable, in two lines of
code. We also need a `toplevel function', to tell us if the overall
computation succeeded. One may think of it as St.Peter at the
gate. For now, we take a computation that raises no exception as
successful. In general, even non-termination within a branch can be
dealt with intelligently (cf. `cooperative' threading which must yield
from time to time).

Regarding effects incurred while evaluating branches: one deal with
them as one deal with effects when implementing any transactional
mechanism: you prohibit them, you log the updates, you log the state
before the beginning so to undo, you use zipper for functional
`mutations' (which can be done with delimited continuations, too), you
operate in a sandbox, etc. The ZFS talk gives an example:
http://pobox.com/~oleg/ftp/Computation/Continuations.html#zipper-fs

Here are the tests. The second one requires a three-step clairvoyance:

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

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