On Fri, 2006-09-08 at 00:21 -0700, Erick Tryzelaar wrote:
> skaller wrote:
> > Felix now supports first class iterators, as a special
> > case of generators. Here is an example:
>
> Thats so awesome. Much better than my streams :) A couple comments on
> the syntax.
Just to try to explain this again another way.
The implementation of generators involved a couple of changes:
1) The 'gen' keyword instead of 'fun'
The effect is: it makes an ordinary function in the symbol
table with a tag 'generator' in the property list.
2) The inliner 'lifts' generator applications out of
expressions: given
... f ( g x, .. ) ...
when it sees 'g x' it checks if 'g' was declared(1) as
a generator, and if so it lifts it out with
var tmp = g x;
... f tmp ...
3) If a Felix function is marked as a generator, it's
clone() method says
return this; // cheat on cloning
instead of
return new(gc, shape_g) g(*this); // make real clone
The effect is a call through a variable:
tmp->clone()->apply(x)
reduces semantically (but not syntactically) to:
tmp->apply(x)
so side effects of the apply method are done on the
object tmp. With a real clone() in place the side-effects
only apply to the clone and are lost when the function
returns (unless it returns a pointer to variable inside
itself of course). The garbage collector throws the
frame out.
4) Yield is implemented by:
(a) add a magic 'pc' variable to the class, init to 0
(b) add a SWITCH(pc) at the start of the apply method,
(drop thru if pc = 0)
(c) make yield v generate:
pc = next;
return v;
next:
The actual SWITCH macro etc are identical to that
used for procedures. The Duff implementation is
exactly the same.
That's it, more or less. The effect is when calling
the generator, any arguments are rebound to the function
parameters, then we jump to the place we last left off.
The implementation of yield has almost nothing at all
to do with generators: the only connection is that
the clone() method is kludged, so a call through a
variable doesn't keep making fresh copies of a
virgin closure, which would of course prevent things
working since all the state, including the pc variable,
would be lost .. this actually happened in my first
test of the tree visitor because { .. yield ... }
wasn't recognized as a generator and so it got cloned.
You probably saw the patch fixing that go into SVN :)
So .. generators are a 'by product' of a couple of minor
implementation modifications. I didn't sit around and
design a new theory .. I modified the existing implementation
in a couple of 'clever' ways and the result just drops
out of the implementation.
Well constructed implementations tend to do this:
some listeners may scream here .. but it is often
a good idea to ignore all the theory and just implement
simple cute things: they will usually turn out to
be theoretically better than a theorist would dream
up, because (a) they're small, and (b) they fit
in an existing architecture and (c) they typecheck.
Getting 'fibres' to work was quite hard. But having
got the scheduler and control inversion working,
the implementation of channels just 'dropped out'.
I had some complicated code with lists of blocked
thread etc and suddenly the simplest channel implementation
just threw the lot away. The scheduler didn't need
any modifications, and RF's fabuous 'svc_general'
just handled them seamlessly.
The result: Felix fibres can't deadlock. Finite streams
are perfectly represented: if a thread tries to read
past the end of a stream it just disappears, so the
very question cannot arise.
This is miles better than any other language: in effect
it is an option Monad a'la Haskell, but with no possibility
the divergence will be evaluated: laziness par excellance!
What's more, unlike some of the 'theoretically correct'
stuff going into Haskell, like the transactional memory,
the implementation is lightning fast. It's only a couple
of machine instructions to context switch on a channel.
This gives me considerable confidence the model is
actually theoretically superior, as well.
This also explains the rather strange and unexpected
fact that Felix fthread/fibres are *detached* threads:
there is no join primitive. To do a fork/join requires
extra work, as we noted with our 'parallel' constructions.
Anyhow, the point of this 'rant' is basically to say:
I didn't *design* 'generators'. Felix designed them.
I just followed his instructions, and implemented them:
he spoke in a dream one night, around the 5th cup
of coffee .. :)
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
