IFT 3065/6232 -- Compilation


Professeur: Stefan Monnier


Description

La connaissance intime des langages de programmation est cruciale pour pouvoir écrire des programmes fiables, portables, et efficaces. La compréhension des techniques d'implantation des langages de programmation, autant d'interprétation, que de compilation, et donc non seulement indispensable à la réalisation de nouveaux compilateurs et la conception de nouveaux langages, mais est beaucoup plus généralement nécessaire pour écrire du code de qualité. C'est dans cette optique que ce cours traitera des sujets qui touchent à la définition, l'interprétation, et la compilation des langages de programmation. Les sujets suivants sont au menu, quoiqu'il n'y aura pas le temps de tous les couvrir:

Horaire et dates

Jour Heure Lieu Type
Mardi 13h30-15h30 AA-1411 Cours
Vendredi 9h30-10h30 AA-1411 Cours
Vendredi 10h30-12h30 AA-1411 Exercices
23 avr 9h30-12h30 AA-1411 Final

Il n'y aura pas de cours les 19 et 22 janvier.

Voir aussi la page du programme des cours pour ift-3065 et ift-6232

Évaluation

L'évaluation du cours sera basée principalement sur un travail pratique divisé en 2 étapes: la première consistera en l'implantation d'un interpréteur d'un langage de programmation, et la seconde le transformera en un compilateur. Chaque partie compte pour 25% de la note finale. De plus, 10% de la note sera basée sur une présentation en classe du compilateur.

Le projet est à faire seul ou par groupe de deux. Comme mentionné, il consiste en l'implantation d'un compilateur. Le langage à compiler, ainsi que les fonctionnalités du compilateurs seront à votre choix. Vous devrez présenter un plan de travail au début du trimestre, puis un rapport accompagné du code correspondant pour chacune des deux phases. La travail attendu d'un étudiant inscrit à IFT-6232 est bien sûr plus conséquent, donc il devra inclure un langage plus complexe et/ou des fonctionnalités supplémentaires.

Pour IFT-3065, la note finale sera aussi composée à 40% de l'examen final.

Pour IFT-6232, la note finale sera aussi composée à 20% de l'examen final, et à 20% de 2 présentation d'articles en classe.

Tout au long du cours des exercices non-évalués seront demandés (lecture d'articles, lecture de code source de compilateurs existants et exercices de programmation). Il est important de faire les exercices car les évaluations viendront tester l'acquisition des concepts visés par les exercices.

Manuels

Il n'y a pas de manuel officiel pour ce cours. Si vous voulez un livre pour accompagner ce cours, je recommande un mélange de Advanced Compiler Design & Implementation de Muchnick, Building an Optimizing Compiler de Morgan, Modern Compiler Implementation in ML de Appel, ainsi que Types and Programming Languages de Benjamin C. Pierce.

notes de cours

Exemple d'interpréteur


Travail Pratique

Le travail pratique est à faire seul ou en groupe de deux. Il consiste en deux parties: la première consiste en l'implantation d'un interpréteur, et la deuxième y ajoutera un back-end pour en faire un compilateur.

Le langage à compiler est à votre choix. Compiler un langage de programmation réel est une grosse tâche, donc vous allez généralement vouloir vous limiter à un sous-ensemble ou une variante simplifiée; de plus votre compilateur souffrira probablement de diverses limitations.

Le langage dans lequel est écrit le compilateur peut être choisi entre Haskell, SML, et OCaml. D'autres choix peuvent se justifier, mais il vous faudra me convaincre. Votre code doit fonctionner et sera testé sur un système GNU/Linux. Le rapport doit être livré dans le format PDF et le code ne doit pas dépasser 80 colonnes.

La première phase devra normalement contenir les éléments suivants: analyse lexicale, analyse syntaxique, évaluateur, runtime, et ensemble de tests, dont au moins un suffisamment complexe, tel qu'une routine de tri de tableau ou de liste.

La deuxième phase devra générer du code pour l'architecture de votre choix, e.g. AMD64, IA32, ARM, MIPS, ou encore C ou LLVM.

Chaque phase du TP compte pour 25% de la note finale et sera accompagnée d'un rapport (max 6 pages pour le premier, 10 pages pour le dernier). De plus, une présentation en classe de votre travail, à la fin du cours, comptera pour 10% de la note finale.

La phase 1 du TP est à rendre au plus tard le 27 février. La phase 2 du TP sera à rendre au plus tard le 26 avril. Vous devez avant ça présenter un brouillon de votre plan de travail pour la première phase du TP d'ici au 15 janvier. Ce plan (maximum 1 page) devra inclure une description brève du langage que vous voulez implanter, des phases et fonctionnalités supportées, ainsi qu'un calendrier.

Les étudiants inscrit au cours IFT-6232 devront bien sûr viser un langage plus complexe/complet et une implantation plus sophistiquée.

Ressources:

Le travail est à rendre avec la command remise:

    % ssh remise.iro.umontreal.ca
    % remise ift3065 tp1 rapport.pdf <files> ...
  
Utiliser ift3065 ou ift6232 selon le cours auquel vous êtes inscrit (et utiliser tp2 pour la deuxième partie du travail pratique).

Articles

Chaque étudiant de ift-6232 doit présenter 2 articles de la liste ci-dessous (d'autres articles peuvent être proposés, bien sûr). Les présentations dureront un maximum de 30min chacune. Une présentation d'article devrait:

Pour cela, il sera généralement nécessaire d'introduire divers concepts et techniques sans lesquels l'article serait incompréhensible. Aussi il sera souvent utile de remettre l'article dans son contexte: expliquer quels étaient les problèmes importants de l'époque et quels problèmes actuels ne les affectaient pas encore. Une discussion de l'impact/influence de l'article est aussi une bonne idée.

La contrainte principale est le temps: 30min c'est très court pour présenter tout ça. Donc il vous faudra bien planifier votre présentation, en pensant à quels sont les éléments que l'audience doit vraiment comprendre. En général vous devrez pour cela éliminer toutes sortes de "détails" intéressants. Ne vous étonnez pas si vous finissez par passer 20minutes d'introduction et seulement 10min sur l'article en soi (mais assurez-vous que vous aurez le temps d'arriver à ces 10minutes). Aussi pour pouvoir aller plus vite, il vous faudra utiliser des slides, ce qui vous aidera aussi à mieux structurer la présentation.

Note: les présentations se feront avec mon laptop pour réduire les temps de transfert d'une machine à une autre. Donc vous devrez m'envoyer par email vos slides au format PDF au plus tard 2h avant le début du cours.

Horaire

Jour Orateur Article
23 mar Erick Abstract Interpretation: A unified lattice model for static analysis of program by construction or approximation of fix points
Hajar Analysis of pointers and structures
Julien Control Flow Analysis in Scheme
26 mar Benoît Unboxed objects and polymorphic typing
Keita Iterated register coalescing
Christian Shrinking lambda expressions in linear time
Michæl
Francisco Compiling Polymorphism Using Intensional Type Analysis
30 mar Maxime Optimizing MATLAB through Just-In-Time Specialization
Hajar Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
Julien Global Optimization by Suppression of Partial Redundancies
6 avr Erick Region-Based Memory Management
Keita Selective and Lightweight Closure Conversion
Benoît Efficient and safe-for-space closure conversion
9 avr Maxime Dynamic Optimistic Interprocedural Analysis: a Framework and an Application
Christian ORBIT: an optimizing compiler for scheme
Michæl
Francisco From System F to Typed Assembly Language

Optimisations "classiques"

Optimization of range checking, Victoria Markstein, John Cocke, and Peter Markstein, 1982.
Engineering a simple, efficient code-generator generator, C. W. Fraser and D. R. Hanson and T. A. Proebsting, 1992.
Shrinking lambda expressions in linear time, Andrew Appel and Trevor Jim, JFP 1997.
Compiler-directed thermal management for VLIW functional units, M. Mutyam and F. Li and V. Narayanan and M. Kandemir, and M. J. Irwin, LCTES'2006.
Iterated register coalescing, Lal George and Andrew W. Appel, 1996.
Global optimization by suppression of partial redundancies, E. Morel and C. Renvoise, 1979.

Analyses

Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Patrick Cousot and Radhia Cousot, 1997.
Analysis of pointers and structures, D. R. Chase and M. Wegman and F. K. Zadeck, 1990.
Control Flow Analysis in Scheme, Olin Shivers, 1988.

Représentation des types à l'exécution

Representing Type Information in Dynamically Typed Languages, David Gudeman, 1993
How to make ad-hoc polymorphism less ad hoc, P. Wadler and S. Blott, 1988
Unboxed objects and polymorphic typing, Xavier Leroy, 1992
Compiling Polymorphism Using Intensional Type Analysis, Bob Harper and Greg Morrisett, 1995
Flexible Representation Analysis, Zhong Shao, 1997
Message Dispatch on Modern Computer Architectures, Karel Driesen and Urs Hölzle and Jan Vitek, 1994

Filtrage

Compiling pattern matching, Lennart Augustsson, 1985.
Optimizing pattern matching

CPS

Debunking the "expensive procedure call" myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO, 1977
ORBIT: an optimizing compiler for scheme, 1986

SSA

Global value numbers and redundant computations, B. K. Rosen and M. N. Wegman and F. K. Zadeck, 1988.
Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, R. Cytron and J. Ferrante and B. K. Rosen and M. N. Wegman, 1991
A Correspondence between Continuation Passing Style and Static Single Assignment Form, 1995
SSA is Functional Programming, 1998
Simple Generation of Static Single-Assignment Form, 1998?

Conversion de fermetures

Selective and Lightweight Closure Conversion, 1996
Efficient and safe-for-space closure conversion, 2000

Inférence de types

Type Inference with Polymorphic Recursion, 1991
Type Inference with Constrained Types, 1999
MLF: Raising ML to the Power of System F, 2003
Discriminative sum types locate the source of type errors, 2003

Gestion mémoire

Improving locality of reference in a garbage-collecting memory management system, Robert Courts, 1988.
Implementation of the typed call-by-value λ-calculus using a stack of regions, Mads Tofte et Jean-Pierre Talpin, 1994
Region-Based Memory Management, Mads Tofte et Jean-Pierre Talpin, 1997

Compilation certifiée

From System F to Typed Assembly Language, Greg Morrisett, David Walker, Karl Crary, and Neal Glew, 1999

Stefan Monnier
Best viewed with ANY browser