dOvs/Compilation 2024

Course information

This course covers the design and implementation of compiler and runtime systems for programming languages. The contents of the course include concrete and abstract syntax, parsing, scopes and environments, type checking, runtime support, translation, code generation, static analysis, register allocation.

Description of qualifications The course provides the participants with insights into the theory of compilation of programming languages and practical experience with the application of compiler technology. At the end of the course, the participants will be able to: i) identify and formulate compilation phases; ii) describe and apply principles and theory of compilation of programming languages; iii) implement a compiler for a modern high-level programming language and analyze its properties; iv) evaluate and reflect how compiler technology influences the design of programming languages.

Time and place

  • Mon, 10:00 – 12:00, 1514-213 Aud. I
  • Wed, 12:00 - 14:00, 1514-213 Aud. I

Lectures

The lectures will cover the general topics as well as specific issues in relation to the project, and solutions to weekly exercises. The language of instruction is English.

Project groups

The participants must work in groups of size three. Each group will collaborate on a solution to the programming project and will share 40% of their final grades.

Additional help may be obtained through the web board or by e-mail.

Literature and materials

The following material is used in the course.

Textbook

The course textbook that is available from the university book store (Gad Stakbogladen Naturfag):

Andrew W. Appel
Modern Compiler Implementation in ML

Cambridge University Press
ISBN: 0-521-60764-7

OCaml book

Our main OCaml reference is the following online OCaml book OCaml Programming: Correct + Efficient + Beautiful

For selected topics and tools, we will refer to the respective manual pages and official documentation.

AU Compilation handbook

All assignment material and supplimentary reading is available in the AU Compilation handbook.

Course plan

The schedule is tentative all term. Stay tuned for updates. Reading instructions for each lecture are marked with the book icon . Note that the material in the lectures do not always correspond one-to-one to the material in the reading. We recommend the reading to happen in sync with the schedule, that is to happen before or shortly after each lecture. Reading marked as bonus is not required. Do it only if you have the time.

Week 35

Monday, August 26th

The what and why of compilers. What will you learn.
Modern Compiler implementation in ML, Chapter 1
AU Compilation handbook, Development container
OCaml book, Chapters 1 - 3
Bonus: The History of FORTRAN I, II, and III
Extra-bonus: Oral History of John Backus
Extra-extra-bonus: Interpreters and Compilers (Bits and Bytes, 1983)

Thursday, August 29th

x86-64 recap.
OCaml book, Chapter 4
AU Compilation handbook, Arithmetic Expressions in OCaml and x86 Assembly
AU Compilation handbook, x86-64
Bonus: Caml trading – experiences with functional programming on Wall Street

Week 36

Monday, September 2nd

Expression programs. Basic semantic analysis. Representing x86 programs.
AU Compilation handbook, Expression Programs and x86 Assembly
OCaml book, Chapter 5
OCaml book, Chapter 7.1
Modern Compiler implementation in ML, Chapters 5.1 – 5.2
Hand-in due Wed, Sep 04, 23:59 – OCaml and x86

Thursday, September 5th

Optimizations for expression programs.
OCaml book, Chapter 7.2

Week 37

Monday, September 9th

In-class study cafe.
AU Compilation handbook, Basic optimizations

Thursday, September 12th

LLVM introduction.
AU Compilation handbook, LLVM-- (up to but not including GEP)
AU Compilation handbook, LLVM-- programming
Hand-in due Fri, Sep 13, 23:59 – Expression Programs and x86

Week 38

Monday, September 16th

In-class study cafe.

Thursday, September 19th

Semantic analysis for Phase 1 of Dolphin.
AU Compilation handbook, Dolphin – Phase 1 (up to and including Semantic analysis)

Week 39

Monday, September 23rd

LLVM code generation for Phase 1 of Dolphin.
AU Compilation handbook, Dolphin – Phase 1 (Code generation)
Hand-in due Wed, Sep 25, 23:59 – LLVM-- programming

Thursday, September 26th

Instructor office hours (no lecture).

Week 40

Monday, September 30th

Liveness analysis.
Modern Compiler implementation in ML, Chapter 10, except 10.2

Thursday, October 3rd

In-class study cafe.

Week 41

Monday, October 7th

Register allocation.
Modern Compiler implementation in ML, Chapter 11
Hand-in due Wed, Oct 09, 23:59 – Dolphin phase 1

Thursday, October 10th

Instructor office hours (no lecture).
No classes week 42

Week 43

Monday, October 21st

Lexical Analysis.
Modern Compiler implementation in ML, Chapter 2
OCamllex manual from the official OCaml documentation – Overview of OCamllex (17.1) and Syntax of lexer definitions (17.2)
Bonus: Where GREP came from
Extra-bonus: Regular-expression derivatives reexamined
Hand-in due Wed, Oct 23, 23:59 – Dolphin phase 2

Thursday, October 24th

Parsing.
Modern Compiler implementation in ML, Chapter 3 (except Error recovery)

Week 44

Monday, October 28th

Parsing tools.
Menhir documentation
AU Compilation handbook, Dolphin – Phase 3
Modern Compiler implementation in ML, Chapter 4
Bonus: Reachability and Error Diagnosis in LR(1) Parsers

Thursday, October 31st

In-class study cafe.

Week 45

Monday, November 4th

Functions and comma expressions: semantic analysis and code generation.
AU Compilation handbook, Dolphin – Phase 4
Hand-in due Wed, Nov 06, 23:59 – Dolphin phase 3

Thursday, November 7th

Aggregates: front-end and semantic analysis.
AU Compilation handbook, Dolphin – Phase 5 (up to and including Semantic analysis)

Week 46

Monday, November 11th

Aggregates: code generation.
AU Compilation handbook, LLVM-- (GEP)
AU Compilation handbook, Dolphin – Phase 5 (Code generation)
LLVM official manual – The Often Misunderstood GEP Instruction
Hand-in due Wed, Nov 13, 23:59 – Dolphin phase 4

Thursday, November 14th

Strings. Advanced topics.

Week 47

Monday, November 18th

In-class study cafe.

Thursday, November 21st

Garbage collection.
Modern Compiler implementation in ML, Chapter 13 (up to and including 13.4)

Week 48

Monday, November 25th

Hand-in due Wed, Nov 27, 23:59 – Dolphin phase 5

Thursday, November 28th

Loop optimizations.
Modern Compiler implementation in ML, Chapter 18

Week 49

Monday, December 2nd

In class study cafe.
Hand-in due Wed, Dec 04, 23:59 – Final code

Thursday, December 5th

Wrap up.

Exam

Assessment

7-point grading scale

Grading

External co-examination

Prerequisites

Submission and approval of the final compiler project.

Exam aid

None

Comments

The final grade is a function of three components
  1. Project hand-ins (individual + group) that will contribute to 40% of the grade.
  2. Individual exam performance that will contribute to the rest of the grade.