Fri, 29 Sep 89 00:33:58 +0100

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) |

From: | Lennart Augustsson <augustss@cs.chalmers.se> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.