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))
endprocedure
enddefine;

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

;;; MISHAP - enp: EXECUTING NON-PROCEDURE
;;; 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])
enddefine;

** -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))
endprocedure(%f,g%)
enddefine;

vars logsin = fred(log,sin);

frozval(1,logsin)=>
** <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))
endprocedure
enddefine;

(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);
frozval(1,logsin)=>
** <ident <undef g>>
:

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

Quote:
> 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.

Robin.

Sun, 17 Dec 1995 18:04:30 GMT

 Page 1 of 1 [ 2 post ]

Relevant Pages