Diseño e Implementación de Compiladores
CC5116 - Primavera 2020

Información general
El propósito de este curso es elucidar la implementación de compiladores modernos y eficientes para lenguajes de programación de alto nivel. El curso se centra en las conexiones entre los distintos mecanismos de los lenguajes de programación y su impacto en el diseño de un compilador, incluyendo problemas algorítmicos y pragmáticos.
A lo largo del curso, el estudiante desarrolla compiladores para lenguajes cada vez más sofisticados, desde el parseo hasta la generación de código assembler x86-64. Los mecanismos estudiados incluyen tipos de datos primitivos, estructuras de datos, procedimientos, recursión, interacción con C, verificación e inferencia de tipos, funciones de primera clase, objetos, y gestión de la memoria. Además, se abordan temas de eficiencia de ejecución y optimizaciones.
A través del continuo trabajo de implementación, el cual se sugiere se haga en pares, el estudiante también aprenderá lecciones importantes sobre ingeniería de software y testing, además de descubrir un nuevo lenguaje de programación (OCaml).
Horarios
Las clases de cátedra serán en horario 1.4-3.4. Las auxiliares serán en horario 5.2, y serán exclusivamente sesiones de apoyo a los desarrollos propios de los participantes.
Requisitos
Este curso tiene como requisitos a los cursos de Lenguajes de Programación (CC4101) y Arquitectura de Computadores (CC4301).
Evaluación
Cada estudio de un nuevo mecanismo culmina con la entrega de una versión actualizada del compilador en desarrollo. Esas entregas representan un control continuo (NC), donde cada entrega cuenta por igual (ver detalles en siguiente sección). Este trabajo se realiza por grupos de dos estudiantes, o individualmente, según preferencia. Se realizarán además 5 quizzes (individuales) sobre conceptos expuestos en clases (NQ), donde cada quiz cuenta por igual.
La nota final (NF) del curso se calcula de la siguiente manera: NF = 0.8 * NC + 0.2 * NQ.
⚠ Evaluación por Especificaciones
Para las entregas de su compilador, adoptaremos una forma de evaluación conocida como specs grading (o mastery grading), la cual difiere bastante de lo usual. La idea es simple: se define un mínimo no negociable de logros que tiene que demostrar, y puede volver a intentar hasta conseguirlo.
⚠ Código de Conducta
Al mantenerse en este curso los/as estudiantes se comprometen a seguir el código de conducta.
Materials
Software
To develop your compilers, you will need to use the following:
OCaml, version 4.11, a programming language well-suited for implementing compilers (see below for the specific installation instructions).
opam, version 2.0 (or newer), a package manager for ocaml libraries and tools.
nasm, an open-source assembler
Clang, a compiler for C programs. (You may use gcc if you prefer, but you’ll be on your own to ensure that everything works correctly.)
In order to setup your ocaml environment, you should first install opam, following the instructions for your distribution. Then create a switch with the right ocaml version and install the tools and libraries used in the course with the following invocations from the command line.
$ opam init
$ opam update
$ opam switch create compilation 4.11.0
;; adapt according to your shell -- this is shown for bash
$ eval `opam env`
$ opam install dune utop merlin containers alcotest
dune, version 2.6 (or newer), a build manager for ocaml.
utop, a rich REPL (Run-Eval-Print-Loop) for ocaml with autocompletion and syntax coloring.
merlin, provides contextual information on ocaml code to various IDEs.
containers, an extension to the standard library.
alcotest, a simple and colourful unit test framework.
There is no specific IDE for OCaml. A time-tested solution is to use Emacs (with tuareg and merlin). Recently, a first (alpha) version of the OCaml Platform for VS Code was released – it seems to work pretty well, so I plan to use it. There’s also some community-backed support for IntelliJ, although I haven’t tried it.
For VS Code, you first need to install OCaml LSP:
$ opam pin add ocaml-lsp-server https://github.com/ocaml/ocaml-lsp.git
$ opam install ocaml-lsp-server
Books
There is no textbook (see lectures below), but the following may be useful complements (available at the library):
Andrew Appel, Modern Compiler Implementation in ML, Cambridge University Press, 1998.
Keith D. Cooper and Linda Torczon, Engineering a Compiler, 2nd Ed., Morgan Kaufmann, 2004.
Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, Pearson Education Inc, 2006.
Online resources
OCaml Resources
UTop: A nice frontend to the OCaml interactive toplevel
X86 Resources
X64 Resources
A tutorial on NASM (specifically x64- and macOS-related issues)
Others
An interactive tutorial on using Git
Lectures
The lecture notes (and this web page design and original content) are from Ben Lerner’s course at Northeastern University (NEU). I am slightly adapting them as we go along to take into account specific design and pedagogical choices; see links below.
Also, remember to checkout the (private) course Dropbox for recordings and hand-written lecture notes. See U-cursos for links.
Date |
| Topics |
| Additonal material |
02/09 |
| Introduction & tiny compiler |
| NEU notes 1 and 2 |
07/09 |
| Unary operations |
| |
09/09 |
| Names, scope and stacks |
| |
21/09 |
| Binary operations and conditionals |
| |
23-28/09 |
| Multiple data types and tagging values |
| |
30/09-05/10 |
| Errors and calling functions |
| |
07/10 |
| Function declarations |
| |
14/10 |
| Heap allocation: tuples |
| |
26/10 |
| Mutable variables and structures |
| |
09/11...16/11 |
| First-class functions |
| |
30/11...09/12 |
| Memory management |
| |
14/12 |
| Overflow and tail calls |
| |
16/12 |
| Proving a compiler correct |
| |
21/12 |
| Intermediate representations, analyses and optimizations |
|
Homework schedule
The course will have one deliverable every 2 weeks. This is a continuous development project using a GitHub repository, and a deliverable is only a specific tag/release of the GitHub project. More information here.
You can start making progress on a given delivery at any time, as soon as the description is available and we’ve seen enough material in the lectures.
The schedule is approximately as follows:
Due Date |
| Title |
| Description |
week 2 |
| OCaml warmup |
| |
week 4 |
| Let bindings and multiple data types |
| |
week 6 |
| First-order functions and basic C interoperability |
| |
week 8 |
| Heap allocation: tuples |
| |
week 10 |
| First-class functions |
| |
week 12 |
| Garbage collection |
|
Testing
Testing your code is critically important. And testing a compiler is particularly challenging!
Please read these notes (NEU).