On Sat, 2006-09-09 at 00:15 +1000, skaller wrote:
> 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 .. :)
To give an idea of how Felix works.. in Stephen M Watt's
superb paper (meaning: any idiot like me can read that paper)
there are instructions for optimising iterators.
If we already had a data flow analyser it would probably
be easy to implement, but we don't yet.
Anyhow, the first instruction is to 'inline' the iterators.
Obvious. But they're marked 'noinline' right now quite
deliberately.
Well, since an iterator is just a function, can't I just
inline it the same way?
The answer is no. At present, a function is inlined by:
copy the body into the caller
replace parameter with argument either eagerly or lazily
replace return x with assignment to a variable and
a jump to the end of the function
replace the function call with the variable
This is all 'obvious'. Note that inlining the body *includes*
copying all the variables too, and also includes copying
nested functions: I call this cloning, but it is actually
cloning plus specialisation (you have to substitute parameter
with argument in the child functions too).
To do this with an iterator implies nesting the SWITCH.
This is NOT true for procedures. When a procedure is inlined,
the labels get cloned into the parent and all the gotos
adjusted. But the parent 'pc' variable can be used for
all these labels.
This is NOT true for iterators. Remember the call to an iterator
is normally made through a variable .. which means there
is a *second* copy of the 'pc' variable. In fact that is why
the tree visitor example works .. the call chain is actually
preserved in user space, even though yielding loses the
machine stack.
In other words .. the iterator has to have a private
copy of the pc variable cloned into the caller,
and a nested switch on that copy must be used inside
the iterator.
So what you say? Well, at present the pc variable
and switch are C macros physically inserted by the
code generator at the top of the function and in
the constructor and class declarations: there is
no provision for a nested switch. I could certainly
put one in during code generation, but how would
I know where?
The point is Felix intermediate language does not
have a term for a computed jump!
What I need to do is 'lift' the pc variable
out of C++ space and make it a Felix variable,
and then be able to jump on it.
Ergo: Felix is telling me the next thing to implement
is a computed goto, because I cannot inline iterators
without one. In turn, this needs a new data type
for a variable which can hold a label value.
Of course .. a label is just a continuation,
and a computed jump is just a way to resume
a continuation.. so there's an issue here how
to handle this, since the target might be non-local.
Felix can *already* do long jumps, and they can
already be 'computed' by wrapping them in a closure,
then choosing between closures.
The strange thing is that the Watt optimisation probably
just drops out of the equivalence of functional programming
and procedural programming, evident when the FP form
is CPS transformed, and the PP form is SSA transformed
(and you end up with the same graph! -- this particular
result kills the idea that FP is any better than procedural
programming: recursion under CPS is just a goto, general
recursion is just a computed goto:)
Anyhow you can look forward to:
proc f() {
var pc : label = a;
start:>
goto pc;
c:>
print "c";
a:>
print "a";
pc = c;
goto start;
}
because it seems at the moment that to inline an iterator
I have to 'lift' the compute goto and label assignments
into 'user space'.. making this safe is another issue ...
--
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
