Amb

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

Re: [Caml-list] Amb

[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

Re: [Caml-list] Amb

[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

Re: [Caml-list] Amb

[Tom]

[-- Attachment #1: Type: text/plain, Size: 410 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 643 bytes --]

Re: [Caml-list] Amb

[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

Re: [Caml-list] Amb

[Jon Harrop]

On Friday 09 February 2007 22:42, Tom wrote:
> 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"

Spawn parallel universes?

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

Re: [Caml-list] Amb

[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