Re: [Caml-list] Generators/iterators and lazy evaluation?

[Alain Frisch <Alain.Frisch@inria.fr>]

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