Re: What is "lambda lifting"?

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

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