Faculté informatique et communications IC, Section d'informatique, Institut d'informatique fondamentale IIF (Laboratoire de méthodes de programmation 1 LAMP1)

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

Altherr, Philippe ; Odersky, Martin (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2006 ; no 3509.

Ajouter à la liste personnelle
    Summary
    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.
    Résumé
    Scala est un langage de programmation à usage général développé à l'EPFL. Il combine des concepts provenant des langages orientés-objets à d'autres provenant des langages fonctionnels. Scala est fortement typé est possède un système de types relativement complexe qui incorpore de nombreux concepts avancés. Le compilateur Scala est constitué d'une succession de phases qui réécrivent le code source en des versions de plus en plus simples jusqu'au stade où le code peut être trivialement traduit en code objet. Il est attendu que chaque phase produise du code Scala correctement typé. Cette thèse commence par décrire en détails les constructions les plus importantes de Scala ainsi que son système de types. Elle s'intéresse ensuite à deux phases de réécriture du compilateur dont l'implantation s'est révélée beaucoup plus difficile que prévue. En effet, durant le développement du compilateur, il a été découvert que certains programmes ne peuvent pas être simplifiés en les réécrivant si on se restreint à du code Scala correctement typé. Les deux phases posant problème sont décrites en détails ainsi que les programmes qui ne peuvent pas être correctement réécrits. Un langage intermédiaire typé qui généralise certains aspects de Scala et permet ainsi de réécrire tous les programmes est décrit. Les deux phases de réécriture sont ensuite décrites formellement à l'aide de ce langage intermédiaire.