Lambda Lifting 
Author Message
 Lambda Lifting

Jonathan Cunningham has asked me to explain "lambda lifting". Well...
in POP-11 terms, consider:

define fred(f,g);
  procedure(x); f(g(x))

fred is a procedure that returns a procedure - the function product of f and
g. Or at least that is what is intended. However, observe that f and g occur
FREE in the inner procedure. As POP-11 this will not work. E.g.

vars logsin = fred(log,sin);
logsin(2.3) =>

;;; INVOLVING:  <undef g>
;;; FILE     :  /users/staff/other/pop/.article   LINE NUMBER:  23
;;; DOING    :  compile runproc compile

Now c. 1968 Rod Burstall and I were having a conversation in which he grumbled
about this. I said - "but you can fix it up with POPVAL". In POP-11 notation:

define fred(f,g);
  popval([procedure(x); ^f(^g(x)) endprocedure])

** -3.21559

But this did not make Rod any happier - procedures should behave properly,
and not their texts. He muttered things about closures. I was reluctant to
redo an important chunk of the language, so thought "if the offending f and
g were ARGUMENTS of the inner procedure, they could be happily bound by
a neat little hack.

define fred(f,g);
  procedure(x,f,g); f(g(x))

vars logsin = fred(log,sin);

** <procedure log>

This is all written up in "Programming in POP-2". Somewhat later, theory
caught up with practice, and it was shown, by Turner I think, that this was a
general mechanism for handling free variables in the lambda calculus (he also
did a lot of other clever things which we had not discussed). POP-11, I think,
does it automatically:

define fred(f,g); lvars f g;
  procedure(x); f(g(x))

(this is not quite eqivalent, since POP-11 allows for you to assign to the
free variables, so that an identifier has to be partially applied).

vars logsin = fred(f,g);
** <ident <undef g>>

Sat, 16 Dec 1995 18:13:21 GMT  
 Lambda Lifting

> There is an important subclass of procedure, that we might as
> well call "stand-alone", that have a simple property.  Stand-alone
> procedures are defined using a restricted set of variables.  They
> are allowed to refer to EITHER
>  (1) global variables  [strictly speaking this should be
>        other procedures which are stand-alone.]
>        OR
>  (2) variables declared inside the procedure.

These are of course the variables that C handles.

Strictly speaking, in the lambda calculus, global variables are free,
so that a super-combinator can only have constructors and primitives. Any
user-defined functions have to be passed in as arguments.


Sun, 17 Dec 1995 18:04:30 GMT  
 [ 2 post ] 

 Relevant Pages 

1. Can global refs be freed from lambda-lifting ? ( was Is Lambda-lifting necessary ? )

2. lambda lifting vs env trimming

3. "Down with Lambda Lifting"?

4. Lambda-lifting

5. Is Lambda Lifting always necessary ?

6. down with lambda lifting

7. Lambda Lifting (part 2)

8. #'(lambda ... (lambda

9. (lambda ()) vs #'(lambda ())

10. no re-binding of nested-scope locals, no re-binding in lambda, no,,, {was Re: lambda)

11. New Face Lift to Site

12. lamda lifting


Powered by phpBB® Forum Software