Lambda Lifting (part 2)
Author Message
Lambda Lifting (part 2)

Here's another perspective on ``lambda-lifting'' that might be
useful.

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.
In particular, they NEVER refer to variables that are declared
at an outer, non-global level.

For example, the procedure "SA" is stand-alone but "NSA" is not.

define some_outer_proc( fred ); lvars fred;

define SA( x, y ); lvars x, y;
f( x, y, x )
enddefine;

define NSA();
fred
enddefine;

enddefine;

So, why are stand-alone procedures important?  There are several
answers.  The most relevant answer in POP-11 is that they can be
compiled independently of their lexical context.  Another view on
this is that, if we think of lambda-calculus rather than POP-11,
we discover that stand-alone functions (called super-combinators,
for historical reasons) obey some especially simple transformation
and rewrite rules.

In POP-11, we care about stand-alone procedures because we can
transform every procedure definition into a stand-alone definition
and therefore compile any procedure.  This transformation is
lambda-lifting.  [Again, strictly speaking, it is the procedural
language equivalent of lambda-lifting.  However, there seems no
virtue in drawing this distinction.]

Lambda-lifting is the repeated elimination of ``awkward'' variables.
These are the non-global, non-local variables, of course.

For example, when we see

define compose( f, g ); lvars f, g;
procedure(); f(); g() endprocedure
enddefine;

we note that the inner procedure refers to f & g -- both "awkward".
To eliminate "f", we will have to transform the inner procedure into
a closure of a new procedure.

define compose( f, g ); lvars f, g;
define lconstant g0001( ref_f ); lvars ref_f;
cont( ref_f )(); g();
enddefine;
g0001(% consref( f ) %)
enddefine;

Note that "f" becomes "ref_f", in order to cope with any possible updates.
And, of course, we need to eliminate "g" from "g0001".

define compose( f, g, ); lvars f, g;
define lconstant g0002( ref_f, ref_g ); lvars ref_f, ref_g;
cont( ref_f )(); cont( ref_g )();
enddefine;
lvars g0001 = g002(% consref( g ) %);
g0001(% consref( f ) %)
enddefine;

And this can be simplified to

define compose( f, g ); lvars f, g;
define lconstant g0002( ref_f, ref_g ); lvars ref_f, ref_g;
cont( ref_f )(); cont( ref_g )();
enddefine;
g0002(% consref( f ), consref( g ) %)
enddefine;

And this is the process used by the POP-11 compiler to implement
full-lexical binding -- although ident-records are used rather than
refs.

Hope this was of interest.

Steve

Sun, 17 Dec 1995 09:04:11 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages

Powered by phpBB® Forum Software