Assignment 6

In this assignment, you will add support for nested procedures, closures, and tail call elimination to the intermediate language.

First, carefully read all of compilerA6 in Transformations.scala. Then implement these language features in compilerA6.

Nested procedures

Add support for nested procedures by doing the following.

1. Implement the depth field of Procedure in ProgramRepresentation.scala.
2. Add a static link to the parameters of every procedure (in its paramChunk) by completing the implementation of paramChunks.
3. Complete the implementation of computeStaticLink.
4. Complete the implementation of eliminateCalls. Do not concern yourself with closures or tail calls for now. You can mostly copy your code from eliminateCalls from Assignment 5, but you will be modifying it substantially here in Assignment 6. Modify the code to support nested procedures by computing an argument for the static link.
5. Copy your implementation of frame from Assignment 5.
6. In phaseTwo, copy your addEntryExit from Assignment 5. The identical code should work for now, but you will modify it when you add support for closures.
7. In phaseTwo, complete the implementation of eliminateVarAccesses to support accesses to variables and parameters defined in outer procedures.

Closures

Before implementing closures in Transformations.scala, implement the allocate method of the SimpleHeapAllocator in MemoryManagement.scala.

Then add support for closures in Transformations.scala by doing the following.

1. Implement frameOnHeap to determine which procedures require that their frame be allocated on the heap. The frame of a procedure must be allocated on the heap if:

1. the procedure might be used as a closure, or
2. the procedure is the outer procedure of a procedure whose frame is allocated on the heap.

2. Make adjustments to eliminateCalls and addEntryExit to reflect the fact that the frames (and parameter chunks) of some procedures need to be allocated on the heap instead of the stack.
3. Add code to eliminateCalls to eliminate ClosureCalls in addition to direct Calls.
4. Complete the implementation of eliminateClosures.

Tail calls (optional, bonus)

Add support for tail calls by doing the following (in any order).

1. Complete the implementation of detectTailCalls.
2. Implement copyChunk in MemoryManagement.scala.
3. Make adjustments to eliminateCalls to generate tail calls for Calls and CallClosures whose isTail is true.