Lecture 12

Subroutines (II)

"first-class" operations, identifiers, ...

"first-class" functions should have the following properties:
  o can give a name to
  o pass as argument
  o return as result

How to implement such functions in a lexical scoping language?
(it is trivial to implement in dynamic scoping, why?)

Solution: Pass a code pointer to the function together with access link to where
the function is defined.

For lexical scope, the environment where a function is defined needs 
to be carried over with the function definition when the function is 
passed as argument.

E.g., 

  f
     y (var)
     g
        x (var)
        x + y

if g is passed, g's access link needs to come along. Otherwise you don't
know where to find value for variable y, which is not local to g.

For a real example, pass comparison function to a sorting function.



     Quiz: why in C we don't need to package up the environment?
     A: because in C there is no nested functions.


To return a function as result.

  f
  {
     y
     g
     {
        x + y;
     }
     return &g;
  }

where to find y? y is in f's frame, which may no longer exist, 
say poped out of the stack.

Therefore, stack is not sufficient to support returning a function 
as result or putting a fucntion inside data structure, when 

     1) the values of local names must be retained when an activation ends,
     2) a called activation outlives the caller.

It is the combination of nested functions (where inner functions may use variables 
defined in the outer functions) and functions returned as results (or stored into
variables) that causes local variables to need life time longer that their
enclosing function invocations.

Heap does not check its lifetime when allocate memory for a thing.
So, we can put the frame into a Heap and let garbage collector 
to take care of.  But this is not a good solution. Because control link 
may point to other frame and control link of this other frame point 
to another frame ...
all these frames can not be collected though they are not really needed.

One solution: split frame into what f cares about and what g cares about, 
namely f's local variables (not all local variables of f are used in g, these
that are used by inner-nested functions are called escape).

                  ^
                  |
   |-----------|  |                             ^
   | |control  |--|                             |
   |f|---------|            |---------------|   |
   | | vars    |--------->  |f| access link |---|
   |-----------|            |---------------|
   |return addr|            |  y = 3        |
   |-----------|            |---------------|
   |   misc    |
   |___________|

    this part can           this part goes (or escapes) to Heap
    stay on stack           (to serve as closure)


What is in misc?

e.g.,

fib(n) = fib(n-1) + fib(n-2)
         --------
         this is saved into the frame as misc. 

Things (usually without a name) created by compiler for internal 
convenience can be put on stack.

ML implements differently.
e.g.,

   fun add x = 
        let fun a y = x + y
        in a end

equavilent to a curried version

   fun add x y = x + y

where in the first implementation, a is returned as function.  
< code pointer, 5>

Passing the value of x along with function a. Later, for assignment, this copy
is not accessible for update. But it is ok in ML because ML does'nt support
assignment.