Here's something else Felix does.
the idea is for any expression:
f (g (h (k x, r x))))
you can safely factor it:
val t1 = r x;
val t2 = k x;
val y3 = h (t2, t1);
val y4 = g y3;
val y5 = f y4;
and there will be no performance impact. In fact what Felix does is this:
When it sees a nasty looking expression it "unravels" it like the above
into straight line assignments by adding new variables.
Some stuff is done on the unravelled code because it makes certain patterns
easier to recognise. one of these is inlining!
Then Felix looks at sequences of straight line code and "reravels" it
into a huge nasty expression, eliminating all the variables (provided
they're only used once). This gets rid of "user factored" temporaries
by the same algorithm as the compiler generated ones.
Note .. this is done after inlining so a lot more stuff got inserted
before the reravelling.. :)
Some optimisations work better on the nasty expressions, and getting
rid of variables is usually good. A side effect is that some "initialisers"
might get inserted twice. In this case the variables is "used more than once"
but it is only used more than once in the same expression (not further down
in the code).
If an assignment like:
tmp = generator argument;
is seen it is NOT "reravelled". This ensures generators get evaluated
"at most once" and also "in order of writing", so the side-effects are
deterministic.
Now you understand this process you can begin to see what how vals
work: in this process vals are lazily inlined, i.e. they're replaced by
their initialisers and the actual variable eliminated (except for generators!)
This is generally safe, because even if a val depends on a var variable,
the var cannot change whilst evaluating functional code (functions aren't
allowed to have side effects), and the one place that it can change,
when a generator is executed, is guaranteed to be lifted out and evaluated
in a deterministic order (another "unwritten" specification :)
I hope this all sounds sane. Its why vals are evaluated either eagerly
or lazily: to guarantee the programmer can safely factor expressions
without fear of a performance penalty.
The problem with indeterminate semantics when using closures
now follows. Eager evaluation may make this deterministic,
but it breaks the guarantee the unravel/reravel algorithm is designed
to preserve, and it removes all the optimisation opportunities that
algorithm exposes.
Note also that this routine could also support common subexpression
factoring: although at present I don't think it does, it does recognise
when a *user* val is used twice. There's a rule I think it goes:
If it is used 1 or 2 times substitute (lazy eval), if 3 or more,
keep the variable (eager). This prevent bloat and possible
expensive re-evaluation of the same expression.
[I forget the actual rule]
Again you see, why vals have to be either eager or lazy.
The optimiser depends on it for a LOT of optimisations.
We need to change the rules so that this process can continue,
but be a bit safer.
you could say: if a val depends on a variable it is treated like
a generator and always eagerly evaluated.
Actually something like that actually is implemented I think.
The problem is it doesn't take closure formation into account.
That's very hard. You need to understand that the state of the art
in closure elimination is Haskell, but it still produces dog slow code
in many cases .. that's how hard the problem is.
Felix doesn't use closures as much, and you cannot expect the
Felix compiler to handle them as well as Haskell (at least not
until we have a team of top flight theoreticians working full
time on it!)
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
