Graph reduction, recursion, and the Y combinator

worley@compass.com (Dale R. Worley)
23 Sep 89 03:08:26 GMT

          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: worley@compass.com (Dale R. Worley)
Date: 23 Sep 89 03:08:26 GMT

In most discussions of graph reduction execution of the combinator
representation of the lambda calculus, recursive functions are
represented by introducing a circularity in the tree that represents
the function defintion. 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? Has anyone analyzed
the optimization which removes the Y and replaces it with the circular
edge? Is this a special case of a more general optimization?


Dale
worley@compass.com




Post a followup to this message

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