Assignment Compilation Of Nested Functions

Pt04
%TOC%

---+ Introduction

In this assignment, you will extend your compiler to support the
nested functions of Tiger. Nested functions in Tiger have lexical
scope, which means that they can access local variables and function
arguments of the surrounding function declarations. In terms of a
stack machine this means that these nested function need to have
access to the stack frame of the surrounding functions.

Hence, at runtime, the nested function needs to know the context in
which the function *statically* (i.e. in the source) occurs. This
context can be hard to locate, as is illustrated by the following
example.

<verbatim>
let function f() =
      let var x := 2
          function g() : int = x * 5
          function h() =
            let function i() = printint(g())
             in i()
            end
       in h()
      end
 in f()
end
</verbatim>

The function =g= uses the local variable =x=, which is defined in the
function =f=. So, if =g= is invoked, then it requires, in whatever
way, some information about the invocation of =f= in which the
invocation of =g= occurs. The function =g= is invoked from the
function =i=, so =i= needs to provide this information to =g= in this
call.

There are three alternatives to organize this context information:

<ul>
  <li>

<em>Lambda lifting</em> transforms a program to make all these
non-local variables explicit arguments of the functions. After lambda
lifting, nested functions are no longer necessary.

For example, the previous example could be transformed to

<verbatim>
let function f() =
      let var x := 2
       in h(x)
      end

    function g(x : int) : int = x * 5

    function h(x : int) = i(x)

    function i(x : int) = printint(g(x))

 in f()
end
</verbatim>

Assignments to non-local variables in nested functions are a problem,
since this will require a reference to the variable instead of a copy
of the value (as in the example above). A minor problems is that Tiger
does not support pointers or by-reference variables, but this can be
simulated by using records or arrays.

  </li>

  <li>

<em>Displays</em> can be used to maintain references to the stack
frames organized according to there static occurence in the source
file, as opposed to the order in which they are invoked dynamically.

  </li>

  <li>

<em>Static links</em> can be used to give all function invocations a
pointer to the stack frame of the surrounding function (i.e. the
function in which the function statically occurs).

  </li>
</ul>

We will use static links to implement support for nested functions,
but feel free to implement the alternatives as well ;) .

---++ Static Links

Static links are used to find the location of non-local
variables. Non-local variables reside in the stack frame of different
function invocation, so it takes more effort to use these.

Let's take a look at an example:
<verbatim>
let var x
    var y
    var z
 in x := 2
  ; y := 4
  ; z := 0
  ; let function mul(a : int, b : int) =
          z := a * b
     in mul(x, y)
    end
end
</verbatim>

The assignment to =z= involves such a non-local variable: the location
of =z= is in the stack frame of =main=. Therefore, the =mul= function
needs a reference to this stack frame. This is called a static link.

The static link does not necessarily link to the stack frame of the
caller: the static link for a function =g= should link to the stack
frame of the function in which =g= is lexically enclosed.

In the next example, the function =g= is invoked from function =i=,
but function =i= should not pass its own frame pointer as static link
to =g=, since =g= needs to lookup variables in the stack frame of
=f=. So, function =i= should pass the frame pointer of =f= to =g=.

<verbatim>
let function f() = ...
      let function g() = ...
          function h() = ...
            let function i() = g()
</verbatim>

---+ Assignment

As will be clear by now, you must extend your implementation to use
static links to deal with non local variables.

For this, you have to extend your implementation at two places: a
function call should pass the right static link to the callee and a
the use of a non local variable must use the static links to get to
right stack frame.

*Tip*: both cases must produce some Tiger expression for getting the
static link at runtime. In the case of a variable, this is to access a
location in a non-local stack frame (where the static link points
to). In the case of function call, this is to pass a link to a stack
frame to the function. Fortunately, the code that produces a static
link can be reused for both situations.

*Tip*: a static link points to a stack frame and you can decide for
yourself it it should point to the end or the beginning of the stack
frame (=fp= versus =sp). Pointing to the end is easier if all
locations of variables are expressed by a distance to the end of the
stack frame. On the other hand, following a series of static links is
easier if they point to the _beginning_ of the stack frame. Since, if
they point to the end of a stack frame, then you need to know the size
of the stack frame to determine the location of the next static link
on the stack.

In your traversal, you need to maintain some more information in
dynamic rules: the =CurrentScope= (which behaves like some sort of
global variable) and the =ParentScope=, which returns encloding
function for a given function name. For example, if the traversal is
currently in function =h=, then the current scope is =h=. Also, we
will know the parent scopes of =f= (=main=), =g= (=f=), and =h= (=f=).

<verbatim>
let function f() = ...
      let function g() = ...
          function h() = ...
            let function i() = g()
</verbatim>

It is not allowed to implement the support for static links at the
location where the variable is used. This must be implemented in the
dynamic rule that is defined at the place where a variable is declared
(say =VarFromStack=). In other words, =VarFromStack= must rewrite a
=Var(_)= to a complete =stack= expression. Usually, we say that such a
dynamic rule plays an *active role*, as opposed to dynamic rules that
are used to pass _information_ to the right places (e.g. =ParentScope=
and =CurrentScope=). The =VarFromStack= dynamic rule can at
application time use the =CurrentScope= to determine what code has to
be produced.

=VarFromStack= can work in two different ways (choose for yourself).

---++ Option 1

The most attractive way is to use another active dynamic rule for
generating static links (=StaticLink=). At every function declaration
you can declare a new =StaticLink= rule for retrieving the static link
of this function.

This dynamic rule should be parameterized with the expression to reach
the stack frame of the function itself. In our =fghi= example, if we
need the static link to the stack frame of =f= (which is passed to
function =g= and =h=), then we first need a static link to the stack
frame of =h=. Based on this expression, we can retrieve the static
link to the stack frame of =f=.

---++ Option 2

An alternative implementation is to generate a list of functions of
which you have to follow the static links and generate the full static
link expression from this list. This is a bit different from the
previous option, where the static link is constructed incrementally by
applying dynamic rules.

For example, in our =fghi= example the call of =g= in =f= will need to
follow the static links of =i=, =h=, and =f=. So, we first determine
this list of functions and then generate a static link expression from
that list.

This list of functions can be generated by using the current scope and
the parent scope of the callee. For example, at the call to =g= we are
in scope =i= and we know that the parent scope of =g= is function
=f=. So now, we can produce this list of functions by repeatedly
applying the =ParentScope= dynamic rule to the =CurrentScope=, =i=,
until we are function =f=. Make sure that this strategy does the right
job by testing some examples!

Now, from this list of functions an expression can be generated that
follows the static links of all these functions.

---+ Examples

In these examples, we have used a static link that points to the end of the stack frame. Because of this, the stack frame size is substracted from the static link to obtain the next static link. If you are using the beginging of the stack frame (the frame pointer), then the static link of that stack frame will always be at position =-1=.

---++ Example

<verbatim>
let var x := 2
    function g() : int = x * 5
 in printint(g())
end
</verbatim>

<verbatim>
    function main() =
      (sp := sp + 4;
       stack[(sp - 4)] := 2;
       let function g() : int =
             (sp := sp + 0;
              rt := stack[(stack[(sp - 1)] - 4)] * 5;
              rt;
              sp := sp - 0)
        in stack[(sp - 1)] := sp;
           g();
           stack[(sp - 3)] := rt;
           stack[(sp - 1)] := 0;
           stack[(sp - 2)] := stack[(sp - 3)];
           printint()
       end;
       sp := sp - 4)
</verbatim>

---++ Example

<verbatim>
let var x var y var z
 in x := 3
  ; y := 4
  ; let function mul() : int =
          let var a var b var c var d
           in x * y
          end
     in printint(mul())
    end
end
</verbatim>

<verbatim>
    function main() =
      (sp := sp + 6;
       stack[(sp - 6)] := 3;
       stack[(sp - 5)] := 4;
       let function mul() : int =
             (sp := sp + 4;
              rt := stack[(stack[(sp - 5)] - 6)] * stack[(stack[(sp - 5)] - 5)];
              rt;
              sp := sp - 4)
        in stack[(sp - 1)] := sp;
           mul();
           stack[(sp - 3)] := rt;
           stack[(sp - 1)] := 0;
           stack[(sp - 2)] := stack[(sp - 3)];
           printint()
       end;
       sp := sp - 6)
</verbatim>

---++ Example

<verbatim>
let var x
    var y
    var z
 in x := 2
  ; y := 4
  ; z := 0
  ; let function mul(a : int, b : int) =
          z := a * b
     in mul(x, y)
    end
  ; printint(z)
end
</verbatim>

<verbatim>
    function main() =
      (sp := sp + 6;
       stack[(sp - 6)] := 2;
       stack[(sp - 5)] := 4;
       stack[(sp - 4)] := 0;
       let function mul() =
             (sp := sp + 0;
              stack[(stack[(sp - 1)] - 4)] := stack[(sp - 2)] * stack[(sp - 3)];
              sp := sp - 0)
        in stack[(sp - 1)] := sp;
           stack[(sp - 2)] := stack[(sp - 6)];
           stack[(sp - 3)] := stack[(sp - 5)];
           mul()
       end;
       stack[(sp - 1)] := 0;
       stack[(sp - 2)] := stack[(sp - 4)];
       printint();
       sp := sp - 6)
</verbatim>


---++ Example

<verbatim>
let function f() = 
      let var x := 2
          function g() = x := x * 5
          function h() =
            let function i() = g()
             in i()
            end
       in h()
        ; printint(x)
      end
 in f()
end
</verbatim>

<verbatim>
    function main() =
      (sp := sp + 1;
       let function f() =
             (sp := sp + 3;
              stack[(sp - 3)] := 2;
              let function g() =
                    (sp := sp + 0;
                     stack[(stack[(sp - 1)] - 3)] := stack[(stack[(sp - 1)] - 3)] * 5;
                     sp := sp - 0)

                  function h() =
                    (sp := sp + 1;
                     let function i() =
                           (sp := sp + 1;
                            stack[(sp - 1)] := stack[(stack[(sp - 2)] - 2)];
                            g();
                            sp := sp - 1)
                      in stack[(sp - 1)] := sp;
                         i()
                     end;
                     sp := sp - 1)

               in (stack[(sp - 1)] := sp;
                   h());
                  (stack[(sp - 1)] := 0;
                   stack[(sp - 2)] := stack[(sp - 3)];
                   printint())
              end;
              sp := sp - 3)

        in stack[(sp - 1)] := sp;
           f()
       end;
       sp := sp - 1)
</verbatim>