A Typed Intermediate Language and Algorithms for Compiling Scala by Successive Rewritings

Abstract

Scala is a new general-purpose programming language developed at EPFL. It combines concepts coming from object-oriented languages with other ones coming from functional languages. Scala is strongly typed and comes with a relatively complex type system which incorporates several advanced concepts.

The Scala compiler consists of successive phases which rewrite the source code into ever simpler versions until the code is simple enough such that in can be trivially translated into object code. It is expected that each phase generates well-typed Scala code.

This thesis starts by describing in details the main language constructions of Scala along with its type system. It then focuses on two rewriting phases whose implementation was much more difficult than expected. Indeed, during the development of the compiler, it was discovered that some programs can not be simplified by rewriting them if the produced code has to be well-typed Scala code.

The two problematic phases are described in details as well as the programs which can not be correctly rewritten. A typed intermediate language which generalizes certain aspects of Scala and thus makes it possible to rewrite all programs is described. The two rewriting phases are then formally described using this intermediate language.

Full Text