7.6

Diseño e Implementación de Compiladores

CC5116 - Primavera 2021

Éric Tanter

Auxiliares: Diego Ortego y Tomás Vallejos

Neo

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

La organización del curso está centrada en el desarrollo de su proyecto, con distintas modalidades para apoyar su aprendizaje y ayudar el trabajo de implementación de manera constante a lo largo del semestre.

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.

Vea los detalles aquí

⚠ 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:

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.12.0
;; adapt according to your shell -- this is shown for bash
$ eval `opam env`
$ opam install dune utop merlin containers alcotest
A brief description of the installed tools and libraries:

There is no specific IDE for OCaml. A time-tested solution is to use Emacs (with tuareg and merlin). I’m using the OCaml Platform for VS Code, which works pretty well and is under active development. 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 install ocaml-lsp-server
Then simply go to VS Code, lookup for the extension named VSCode OCaml Platform, and you should be good to go.

Hint for VS Code: run this in the VS Code integrated terminal for automatic rebuild when a file changes:

$ dune build --watch --terminal-persistence=clear-on-rebuild

We recommend using Linux or macOS, if possible. If you use Windows, then install the Windows Subsystem for Linux. Past experience from students with WSL indicates that:

Books

There is no textbook (see lectures below), but the following may be useful complements (available at the library):

Online resources

OCaml Resources

X86 Resources

X64 Resources

Others


Lectures

The lecture notes (and this web page design and original content) are from Ben Lerner’s course at Northeastern University (NEU). I have slightly adapted them to take into account specific design and pedagogical choices; see links below.

Date

 

Topics

 

Additonal material

26/08

 

1. Introduction & tiny compiler

 

video 1.1, video 1.2, NEU notes 1 and 2

02/09

 

2. Unary operations

 

video 2 and notes

 

3. Names, scope and stacks

 

video 3 and notes

09/09

 

4. Binary operations and conditionals

 

video 4 and notes

 

5. Multiple data types and tagging values

 

video 5.1, video 5.2 and notes

23/09

 

6. Errors and calling functions

 

video 6.1, video 6.2 and notes

30/09

 

7. Function declarations

 

video 7 and notes

07/10

 

8. Heap allocation: tuples

 

video 8 and notes

14/10

 

9. Mutable variables and structures

 

video 9 and notes

21/10

 

10. First-class functions

 

video 10.1, video 10.2, video 10.3 and notes

11/11

 

11. Memory management

 

video (TBD) and notes

18/11

 

12. Overflow and tail calls

 

video (TBD) and notes

25/11

 

13. Proving a compiler correct

 

video (TBD), CPDT and CompCert

02/12

 

14. Intermediate representations, analyses and optimizations

 

video (TBD), Michel Steuwer’s SPLV talks 1 and 3


Homework schedule

The course has 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 you’ve studied the corresponding lecture material.

The schedule is approximately as follows:

Due Date

 

Title (topics)

 

Description

week 3: 03/09

 

OCaml warmup

 

enunciado and video

week 5: 26/09

 

Let bindings and multiple data types (2-5)

 

enunciado and video

week 7: 10/10

 

First-order functions and basic C interoperability (6-7)

 

enunciado (TBD)

week 9: 24/10

 

Heap allocation: tuples (8-9)

 

enunciado (TBD)

week 11: 21/11

 

First-class functions (10)

 

enunciado (TBD)

week 13: 05/12

 

Garbage collection (11)

 

enunciado (TBD)


Testing

Testing your code is critically important. And testing a compiler is particularly challenging! Please read these notes (NEU).

In your development, you will have to use a (homemade) library for black-box testing of your compiler, called BBCTester.

Note: it is your responsability to design adequate test suites for your compiler!