# Re: Graph reduction, recursion, and the Y combinator

## Lennart Augustsson <augustss@cs.chalmers.se>Fri, 29 Sep 89 00:33:58 +0100

From comp.compilers

Related articles
Graph reduction, recursion, and the Y combinator worley@compass.com (1989-09-23)
Re: Graph reduction, recursion, and the Y combinator augustss@cs.chalmers.se (Lennart Augustsson) (1989-09-29)
| List of all articles for this month |

 From: Lennart Augustsson Date: Fri, 29 Sep 89 00:33:58 +0100 Newsgroups: comp.compilers In-Reply-To: <1989Sep26.041357.26728@esegue.segue.boston.ma.us> Organization: Chalmers University of Technology

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

Post a followup to this message