Diseño e Implementación de Compiladores

CC5116 - Primavera 2023

Éric Tanter

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.

• Clases síncronicas: los Jueves 16h15. Esta clase es en modalidad “aula invertida”, es decir que tiene que haber leído los apuntes y/o visto los videos correspondientes antes de cada clase (ver Lectures). Tiene que postear sus preguntas en el foro u-cursos, hasta la noche anterior al día de clase. La clase se hace si y solamente si hay preguntas en el foro.

• Sesiones de seguimiento de proyectos (obligatorio): [horarios por determinar] Cada dos semanas, via Discord, en horario según asignación hecha por los auxiliares.

• Horarios de consulta asincrónica (opcional): [horarios por determinar] via Discord (mismo servidor). Los auxiliares se conectarán y responderán cuando tengan tiempo, así que considérelo como un email++.

Requisitos

Este curso tiene como requisitos el curso de Lenguajes de Programación (CC4101), y el curso de Programación de Software de Sistemas (CC3301) o de 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, aunque se recomienda fuertamente trabajar en pares). 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.12 (or newer), 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.12.0
;; adapt according to your shell -- this is shown for bash
$ eval `opam env`
$ opam install dune utop merlin containers alcotest

• dune, version 2.9 (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). 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

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:

• when installing opam with add-apt-repository, it’s also necessary to apt install gcc, binutils-dev, make and pkg-config, and

• call opam init with the switch --disable-sandboxing, as explained here.

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, in particular this one is great to get started!

• For emacs support: tuareg and merlin

• UTop: A nice frontend to the OCaml interactive toplevel

X86 Resources

• x86 interpreter

• UVa x86 Assembly Guide

• Mac OS Stack Alignment

• C Calling Convention

• Wikibooks X86 Assembly

• X86 Instructions

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 have slightly adapted them to take into account specific design and pedagogical choices; see links below.

The schedule is as follows (approx/subject to changes):

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 as follows (approx/subject to changes):

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!