A typed intermediate language and algorithms for compiling scala by successive rewritings

Scala is a 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 cannot 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 that cannot be correctly rewritten. A typed intermediate language that generalizes some aspects of Scala and thus enables the rewriting of all programs is described. The two rewriting phases are then formally described using this intermediate language.