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)