Diseño e Implementación de Compiladores

7.8

Diseño e Implementación de Compiladores

CC5116 - Primavera 2020

Auxiliares: Daniela Campos & Kenji Maillard

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:

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

A brief description of the installed tools and libraries:

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

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

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

OCaml home page and User manual
OCaml tutorials
For emacs support: tuareg and merlin
UTop: A nice frontend to the OCaml interactive toplevel

X86 Resources

X64 Resources

A tutorial on NASM (specifically x64- and macOS-related issues)
An X64 cheat sheet and another one

Others

An interactive tutorial on using Git
A number converter (Hexa-Binary among many 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-11/11	First-class functions	notes
	Memory management
	Overflow and tail calls
	Type checking and inference
	Further topics: objects, 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	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
week 12	Garbage collection
week 14	Open project: analysis and optimization, new features, etc.

Testing

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

Please read these notes (NEU).