Browse thread
Generators/iterators and lazy evaluation?
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2007-04-04 (20:46) |
From: | Alain Frisch <Alain.Frisch@i...> |
Subject: | Re: [Caml-list] Generators/iterators and lazy evaluation? |
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