From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.4 required=5.0 tests=AWL,NO_REAL_NAME,SPF_FAIL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id C949ABC69 for ; Wed, 3 Oct 2007 10:02:55 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAFbpAkfAXQImh2dsb2JhbACOOAIBCAon X-IronPort-AV: E=Sophos;i="4.21,223,1188770400"; d="scan'208";a="17225959" Received: from discorde.inria.fr ([192.93.2.38]) by mail4-smtp-sop.national.inria.fr with ESMTP; 03 Oct 2007 10:02:54 +0200 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l9382sRK028202 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Wed, 3 Oct 2007 10:02:55 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAJPpAkfAEKcgh2dsb2JhbACOOAIBCAon X-IronPort-AV: E=Sophos;i="4.21,223,1188770400"; d="scan'208";a="2312657" Received: from selenite.metnet.navy.mil ([192.16.167.32]) by mail2-smtp-roc.national.inria.fr with ESMTP; 03 Oct 2007 10:02:54 +0200 Received: (qmail 27682 invoked by uid 107); 3 Oct 2007 08:02:44 -0000 Received: from unknown (HELO Adric.metnet.fnmoc.navy.mil) (10.100.105.152) by selenite.metnet.navy.mil with SMTP; 3 Oct 2007 08:02:44 -0000 Received: by Adric.metnet.fnmoc.navy.mil (Postfix, from userid 760) id 5B954A9A1; Wed, 3 Oct 2007 01:00:53 -0700 (PDT) To: Andrej.Bauer@fmf.uni-lj.si Cc: caml-list@inria.fr Subject: Re: [Caml-list] Which control structure? Reply-To: oleg@pobox.com Errors-To: oleg@okmij.org From: oleg@pobox.com Message-Id: <20071003080053.5B954A9A1@Adric.metnet.fnmoc.navy.mil> Date: Wed, 3 Oct 2007 01:00:53 -0700 (PDT) X-Miltered: at discorde with ID 47034CAE.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; oleg:01 invocation:01 delimited:01 val:01 val:01 failwith:01 bool:01 endline:01 bool:01 ocaml:01 swallow:98 devil:98 amb:98 amb:98 invoke:01 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 = *) let abort p v = take_subcont p (fun sk () -> v);; (* val abort : 'a Delimcc.prompt -> 'a -> 'b = *) 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 = *) let p arg = print_endline "P is invoked. Haven't evaled the arg yet"; not (arg ());; (* val p : (unit -> bool) -> bool = *) 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)