Which control structure?

Which control structure?

[Andrej Bauer]

I would like to have a control structure which allows me to "copy 
continuations". The idea is to obtain a continuation and then try what 
would happen if we passed it various values.

An example: suppose we have a p : (unit -> bool) -> bool. I want to compute

  (p (fun () -> false), p (fun -> true))

in a particularly strange way (I have my reasons), something like this:

  callcc (fun k ->
     p (fun () -> (callcc l -> k (l false, l true))); raise Badness)

This of course does not make any sense, but I am trying to convey an idea:

- we register the continuation k
- we start evaluating p on our specially crafted argument
- if p never evaluates the specially crafted argument we raise
   an exception
- if p evaluates the special argument, we record "the continuation"
   l and then we want to _evaluate it twice_: once by passing it
   false and once by passing it true. We want to collect the results
   and pass them to the outer continuation k.

I am asking, is there out there (in whatever language) something that 
would let me do this?

Andrej

Re: [Caml-list] Which control structure?

[Andrej Bauer]

If anybody cares, I can do what I want in SML/NJ using a particularly 
ugly combination of callcc and store, see below. Is there a sane way to 
achieve the same thing? I suspect I want delimited continuations, but I 
am not sure.

-----
open SMLofNJ.Cont ;

(* A perverse way of computing (p false, p true) by invoking p only once. *)

fun two p =
     let val c = ref NONE (* here we store the continuation *)
	val a = ref NONE (* here we store p false *)
	val b = ref NONE (* here we store p true *)
     in
	(* store p true into a, and save the continuation *)
	a := SOME (p (callcc (fn k => (c := SOME k; true)))) ;

	(* see if we're hapenning the first or the second time *)
	if !b = NONE then (
	     (* first time around *)
		 b := !a ; (* store p false into b *)
	         (* reinvoke to compute p true *)
                 let val SOME k = !c in throw k false end)
	else
	    (* second time around *)
	    let val SOME x = !a
		val SOME y = !b
	    in
		(x, y)
	end
     end
-----

Andrej

Re: [Caml-list] Which control structure?

[oleg]

Andrei Bauer wrote:

> (* A perverse way of computing (p false, p true) by invoking p only once. *)

I'm afraid the given code may invoke p twice:

        a := SOME (p (callcc (fn k => (c := SOME k; true)))) ;

Here, the continuation is captured while evaluating the argument of p
-- before p is even invoked. So, the captured continuation contains
the invocation of p. Invoking that continuation twice will enter p
twice.

> I can do what I want in SML/NJ using a particularly ugly combination
> of callcc and store,

In almost all useful circumstances call/cc appears in combination with
store -- which is a dead give-away that we are dealing with delimited
continuations. The following code does compute (p false, p true) by
really entering p only once (but exiting it twice). The argument to p
must be a thunk, so we are able to enter p, or to get p to swallow the
hook.

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 (fun () -> c))))))
;;

(* val shift : 'a Delimcc.prompt -> (('b -> 'a) -> 'a) -> 'b = <fun> *)

let abort p v = take_subcont p (fun sk () -> v);;
(* val abort : 'a Delimcc.prompt -> 'a -> 'b = <fun> *)

let two p =
  let prompt = new_prompt () in
  let result = new_prompt () in
  push_prompt result (fun () ->
   push_prompt prompt (fun () ->
     p (fun () -> shift prompt (fun sk -> 
       abort result (sk false, sk true))));
    failwith "can't happen")
;;

(* val two : ((unit -> bool) -> 'a) -> 'a * 'a = <fun> *)

let p arg = print_endline "P is invoked. Haven't evaled the arg yet";
            not (arg ());;
(* val p : (unit -> bool) -> bool = <fun> *)

let test = two p;;

(*
 P is invoked. Haven't evaled the arg yet
 val test : bool * bool = (true, false)
*)

The output proves that p has been entered only once. One might find
the technique of returning the result by aborting a bit unusual -- on
the other hand, when trying to deceive the devil all means are good...

Incidentally, the amb in OCaml does precisely the same tricks:
	http://okmij.org/ftp/ML/ML.html#amb

(and more, e.g., probabilistic execution)

Re: [Caml-list] Which control structure?

[Andrej Bauer]

oleg@pobox.com wrote:
> In almost all useful circumstances call/cc appears in combination with
> store -- which is a dead give-away that we are dealing with delimited
> continuations.

I suspected that much, and hoped for a reply from you :-)

> The following code does compute (p false, p true) by
> really entering p only once (but exiting it twice).

Excellent, thank you.

> The argument to p must be a thunk, so we are able to enter p, or to get p to swallow the
> hook.

This is not a problem because in my actual non-simplified problem p is a 
functional of type (int -> bool) -> bool. Now let me see if I can apply 
delimited continuations in the non-simplified version. Thank you again!

Andrej