Re: Graph reduction, recursion, and the Y combinator

worley@compass.com (Dale R. Worley) says
> ... In theoretically pure lambda calculus,
> recursion is expressed using the Y combinator, or some such, which can
> be represented in terms of the simpler combinators. Has anyone
> actually done this in graph reduction execution?
Yes, I'm sure many have tried this. I know I have.


> Has anyone analyzed the optimization which removes the Y and replaces
> it with the circular edge?
I haven't seen anything formal on this, but not using the "knot-tying"
version of Y gives you horrible space leaks. Any recursion will unfold
the definition of a function as deep as the recursion has ever been in that
function. Most of the time it is not possible to garbage collect the
unfolded part of the graph unless you use a very clever collector.
As far as I know there is *no* reason to use the unfolding version except
if you want to avoid cycles in the graph.


> Is this a special case of a more general optimization?
Yes and no. Y handles everything you write in a correct way (I've no
formal proof of this, but I believe it to be true), but for each recursive
definition you can tailor a special combinator that does it in a more
efficient may.


Check in "The Implementation of Functional Programming Languages"
by Simon Peyton Jones (Prentice Hall, ISBN 0-13-453333-X or
0-13-453325-9) for suitable ways to do all this.
This book is a *must* for anyone interested in implementation of
lazy functional languages.


-- Lennart Augustsson

Return to the comp.compilers page.
Search the comp.compilers archives again.