PT Course Center for ST
Assignment Compilation Of Nested Functions
Pt04
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.
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
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:
-
Lambda lifting 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
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() endAssignments 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. - Displays 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.
- Static links 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).
.
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:
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
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.
let function f() = ...
let function g() = ...
function h() = ...
let function i() = g()
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).
let function f() = ...
let function g() = ...
function h() = ...
let function i() = g()
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 ourfghi 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
let var x := 2
function g() : int = x * 5
in printint(g())
end
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)
Example
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
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)
Example
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
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)
Example
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
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)