Advanced Compiler Construction - Project 5: Tail call elimination

Introduction

The goal of this third graded assignment is to modify your minischeme compiler so that it optimises tail calls, using the technique presented in the course.

Identifying tail calls

To optimise tail calls, they must first be identified. This is precisely the goal of the τ function presented in the course.

Translating this function to Scala code is however not as easy as it seems, because it identifies calls with a unique number attached to them. To simulate this, a natural idea is to store the trees corresponding to tail calls in a set. Unfortunately, trees being Scala case classes, they are compared by content, not by identity! This is a problem here, as it can lead to non-tail calls being incorrectly identified as tail calls, as in the following function:

  (define print-int-twice
    (lambda (i)
      (print-int i)
      (print-int i)))

If sets of trees are used to identify tail calls, the first call to print-int will incorrectly be considered as a tail call! That's because print-int-twice contains another call to the same function that, from the point of view of Scala's notion of equality for case classes, is equal to the first.

To solve this problem, trees should be wrapped into an object that gurantees that they are compared by identity, before being stored into a set. The wrapper class can be defined as follows:

  class Eq[T <: AnyRef](private val obj: T) {
    override def equals(that: Any): Boolean =
      that.isInstanceOf[Eq[T]] && (this.obj eq that.asInstanceOf[Eq[T]].obj)
  }

Optimising tail calls

Once tail calls have been identified, optimising them is very easy, at least in the context of this project. The course provides all the necessary information.

Solution submission

Your solution must be submitted as a ZIP archive containing exactly the following files - not one more, not one less:

  README  (short description of your solution)
  compiler/minischeme/ClosureConverter.scala
  compiler/minischeme/Code.scala
  compiler/minischeme/EtaExpander.scala
  compiler/minischeme/Generator.scala  (modified to eliminate tail calls)
  compiler/minischeme/Instruction.scala
  compiler/minischeme/Interpreter.scala
  compiler/minischeme/Label.scala
  compiler/minischeme/Main.scala
  compiler/minischeme/NameAnalyzer.scala
  compiler/minischeme/Opcode.scala
  compiler/minischeme/Parser.scala
  compiler/minischeme/Primitives.scala
  compiler/minischeme/Register.scala
  compiler/minischeme/Report.scala
  compiler/minischeme/Representable.scala
  compiler/minischeme/Scanner.scala
  compiler/minischeme/Symbol.scala
  compiler/minischeme/Token.scala
  compiler/minischeme/Tree.scala
  compiler/minischeme/TreeGenerator.scala
  compiler/minischeme/TreePrinter.scala

The README file should contain a short description of your solution and its peculiarities, as well as the name of all its authors. With the exception of Generator.scala, ClosureConverter.scala and Main.scala, the files you submit should be identical to the ones you received. If they are not, explain why in the README file.

To help you check the contents of the archive, we provide you with a Scala script called SubCheck5.scala. When run with your archive as argument, this script should not report any problem.

The archive containing your solution should be attached to an e-mail sent to michel.schinz+acc5@gmail.com, before 23:59, April 24, 2008.

Ecole polytechnique fédérale de Lausanne

Laboratoire des méthodes de programmation