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

[skaller <skaller@users.sourceforge.net>]

On Thu, 2007-04-05 at 07:16 +1000, Erik de Castro Lopo wrote:

> One ocaml solution to this is an class/object:
> 
>     class pow2gen =
>         object
>             val mutable current = 0
>     
>             method next () =
>                 current <-
>                     if current == 0 then 1
>                     else current * 2 ;
>                 current
>         end

Yep, and one solution would be for an Ocaml programmer to modify
Felix so it can generate Ocaml instead of C++.

Felix mechanically translates threaded code into event driven
code, that is, it control inverts procedures so that I/O and
calls become returns which remember their return point.

The general structure of a translated procedure ( in Ocaml notation ):

	mutable pc : int
	mutable parent: ptype
	method resume() = match pc with
	| 1 -> ...
	| 2 -> ...
	..
	| 6 -> ... pc <- 7; new thing (self)         (* call thing *)
	| 7 -> ... let tmp = parent in parent <- NULL; tmp (* return *)
	| 8 -> ... pc <- 9; self                  (* yield *)



which is used by 

	while(tr != NULL) tr <- tr#resume()


I call this procedural continuation passing, Reynolds calls it
the method of resumptions. You will note the object here
is a stack frame on the heap, and they're linked together
into a spaghetti stack by parent pointers.

To make this work for functions you add a pointer saying
where to put the result, and translate the function
to a procedure accepting the additional pointer.

This requires unravelling applications to SSA (single 
assignment) form so an application:

	x := f a

is modelled by

	f (x,a)
	

There are more details, the above is only a sketch: you can
have a look at the precise model used by Felix (which is written
in Ocaml), noting Felix generators are simply functions translated
to procedures and stored in variables so when they're resume()d
they just keep going (whereas ordinary procedures invoked via
variables are clones of a prototype to ensure they start in
a fresh state).

The thing to note is that this is a two step model:

A. Translate Python to control inverted Ocaml code
B. Compile and execute the generate Ocaml code

and hence produces high performance native code. The problem
is that Python is dynamically typed .. so most of the performance
will be lost doing type dispatches.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net