Mon, 13 Nov 1995 10:10:51 GMT

Related articles |
---|

What is "lambda lifting"? md94-tar@nada.kth.se (1995-11-09) |

Re: What is "lambda lifting"? hbaker@netcom.com (1995-11-12) |

Re: What is "lambda lifting"? jue@cs.tu-berlin.de (1995-11-13) |

Re: What is "lambda lifting"? johnsson@cs.chalmers.se (1995-12-01) |

Newsgroups: | comp.compilers |

From: | jue@cs.tu-berlin.de (Juergen Exner) |

Keywords: | optimize, functional |

Organization: | TU Berlin Fachbereich Informatik |

References: | 95-11-074 |

Date: | Mon, 13 Nov 1995 10:10:51 GMT |

md94-tar@nada.kth.se (Tomas Arvidsson) writes:

In Marc Feeleys and James S. Millers report on their "Parallel Virtual

Machine for Efficient Scheme Compilation" (PVM) they use the term

"lambda lifting" several times (in conjunction with front end

optimizations) and I just can't find out what it means.

[...]

The notion "lambda lifting" is one well-know technique to compile

functional languages.

According to [PeJo] p. 220ff the transformation of arbitrary

lambda-expressions into super-combinators is called lambda lifting.

*>From [PeJo], p. 223:*

->A supercombinator S of arity n>=0 is a lambda expression of the form

-> \\x1.\\x2. ... \\xn.E [\\ should denote the lambda]

->where E is not a lambda abstraction[...]such that

-> (i) S has no free variables

-> (ii) any lambda abstraction in E is a supercombinator

-> (iii) [...]

For short, supercombinators don't contain free variables at any

recursion level.

*>From [PeJo], p. 228:*

->Following Johnsson[1985], we call the transformation from lambda

->expressions to supercombinators `lambda lifting` since all the lambda

->abstractions are lifted to the top level.

PeJo: Simon L. Peyton Jones: The Implementation of Functional

Languages; Prentice Hall 87

Johnsson[1985]: Lambda-Lifting: transforming programs to recursive

equations. In: Conference on Functional Programming, Languages and

Computer Architecture, LNCS 201

Greetings jue

--

--

Juergen Exner: jue@cs.tu-berlin.de FAX: 030/314-73623

snail-mail: TU Berlin; Sekr. FR 5-13; Franklinstr. 28-29; 10587 Berlin

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.