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=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 431D3BC0A for ; Wed, 4 Apr 2007 22:46:45 +0200 (CEST) Received: from smtp3-g19.free.fr (smtp3-g19.free.fr [212.27.42.29]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l34KkiX3024973 for ; Wed, 4 Apr 2007 22:46:44 +0200 Received: from [192.168.0.1] (rke75-3-82-229-183-156.fbx.proxad.net [82.229.183.156]) by smtp3-g19.free.fr (Postfix) with ESMTP id 72F015E071; Wed, 4 Apr 2007 22:46:44 +0200 (CEST) Message-ID: <46140EB5.50700@inria.fr> Date: Wed, 04 Apr 2007 22:46:45 +0200 From: Alain Frisch User-Agent: Icedove 1.5.0.8 (X11/20061116) MIME-Version: 1.0 To: Raj B Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Generators/iterators and lazy evaluation? References: In-Reply-To: X-Enigmail-Version: 0.94.0.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 46140EB4.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; frisch:01 frisch:01 ocaml:01 ocaml:01 iterator:01 runtime:01 threads:01 computations:01 stack:01 source-level:01 bytecode:01 brics:01 bytecode:01 afaik:01 threads:01 Raj B wrote: > The 'yield' statement is the point where the function returns the next > value and suspends itself until the next time it is 'forced'. At that > time it resumes execution where it left off. > > OCaml makes this particularly hard to implement this due to lack of > 'control flow' features, including even a call/cc. The only way I can > see right now is breaking this code down into little functions, saving > the current execution environment during the suspend and keeping track > of the right function to call the next time. > > I've been thinking about whether I can express this in some elegant way > in some lazy construct in OCaml, since this is basically a form of > 'lazy' evaluation. I think you cannot implement this notion of iterator without some kind of control flow operator (at runtime) or some code rearrangement (at compile time). The point is that you must mainting several active "threads" of computations, including their own stack. A natural solution, as you suggest, is to write your interpreter in continuation-passing style. This should not be too hard, and will actually make your source-level interpreter look more like a bytecode interpreter (especially if you additionnaly defunctionalize the interpreter, see: http://www.brics.dk/RS/03/Abs/BRICS-RS-03-Abs/BRICS-RS-03-Abs.html#BRICS-RS-03-14 ). Btw, a related solution is to push the idea and write a real bytecode interpreter. Another approach would be to use an implementation of control operators for OCaml. AFAIK, they exist only in bytecode ( http://caml.inria.fr/pub/ml-archives/caml-list/2006/02/8fc9c1a56c497b9743515a5e3432d704.en.html ). Yet another solution would be to rely on OCaml threads (but that will probably be inefficient and not very pretty). -- Alain