Advanced Compiler Construction

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 T 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.

Epilogue removal

The epilogue code of functions that always end with a tail call should be removed. These functions can be identified using the predicate E presented in the course.

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/Code.scala
  compiler/minischeme/EtaExpander.scala
  compiler/minischeme/FileReader.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/SeqReader.scala
  compiler/minischeme/Symbol.scala
  compiler/minischeme/Token.scala
  compiler/minischeme/Tree.scala
  compiler/minischeme/TreePrinter.scala

Notice in particular that you should disable closure conversion for this submission! This is to make sure that bugs in your closure converter do not influence this submission.

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, and possibly 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.

Remember that according to our submission regulations, we do not accept solutions that fail to compile.

The archive containing your solution should be submitted on Moodle before 23:55, April 23, 2009.

Ecole polytechnique fédérale de Lausanne

Programming Methods Laboratory