7.6

Diseño e Implementación de Compiladores

CC5116 - Primavera 2020

Éric Tanter

Auxiliares: Daniela Campos & Kenji Maillard

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

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.

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.11.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). 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
Then simply go to VS Code, lookup for the extension named VSCode OCaml Platform, and you should be good to go.

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

 

notes

09/09

 

Names, scope and stacks

 

notes

21/09

 

Binary operations and conditionals

 

notes

23-28/09

 

Multiple data types and tagging values

 

notes

30/09-05/10

 

Errors and calling functions

 

notes

07/10

 

Function declarations

 

notes

14/10

 

Heap allocation: tuples

 

notes

26/10

 

Mutable variables and structures

 

notes

09/11...16/11

 

First-class functions

 

notes

30/11...09/12

 

Memory management

 

notes

14/12

 

Overflow and tail calls

 

notes

16/12

 

Proving a compiler correct

 

CPDT and CompCert

21/12

 

Intermediate representations, analyses and optimizations

 

Michel Steuwer’s SPLV talks 1 and 3

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

 

enunciado

week 4

 

Let bindings and multiple data types

 

enunciado

week 6

 

First-order functions and basic C interoperability

 

enunciado

week 8

 

Heap allocation: tuples

 

enunciado

week 10

 

First-class functions

 

enunciado

week 12

 

Garbage collection

 

enunciado

Testing

Testing your code is critically important. And testing a compiler is particularly challenging!

Please read these notes (NEU).