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

8. lambda mysticism part II

9. #'(lambda ... (lambda

10. (lambda ()) vs #'(lambda ())

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

12. New Face Lift to Site

 

 
Powered by phpBB® Forum Software