Re: What is "lambda lifting"? (Juergen Exner)
Mon, 13 Nov 1995 10:10:51 GMT

          From comp.compilers

Related articles
What is "lambda lifting"? (1995-11-09)
Re: What is "lambda lifting"? (1995-11-12)
Re: What is "lambda lifting"? (1995-11-13)
Re: What is "lambda lifting"? (1995-12-01)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Juergen Exner)
Keywords: optimize, functional
Organization: TU Berlin Fachbereich Informatik
References: 95-11-074
Date: Mon, 13 Nov 1995 10:10:51 GMT (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: 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.