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 implementCall and 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 when the target procedure is nested (has an outer procedure). When the target procedure is a top-level procedure (not nested, with no outer procedure), the computation of the static link can be just the empty block.
  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.


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.
  1. 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.
  2. Add code to eliminateCalls to eliminate ClosureCalls in addition to direct Calls.
  3. 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.