Languages, Compilers and Interpreters (Cod. 653AA)

Master Course in Computer Science at UniPi

IMT
unipi

Announcements

The laboratory part of the course starts on Thursday 26th of September! The first lecture will be an introduction to OCaml: please bring your laptop and install an OCaml compiler.

The Google meet link for the lessons is meet.google.com/img-nvjw-xgb - due to connection problems, the online meeting is not guaranteed, but lessons will be recorded

Lesson Recover: We will recover the missed lessons on

  • 13/12 from 9:00 to 11:00 (room X3)
  • 19/12 from 12:00 to 14:00 (room X2) <-- Notice, the location has been changed!
there will be no additional contents in these lesons, only support for the project (thus lessons will not be recorded)

Course Outline

This it the laboratory module of the course with the same name given by prof. Roberta Gori. The objective is to put in practice what you will learn in the theoretical part of the course by implementing different (simple) programming languages. The programming language adopted for the exercises and the project is OCaml. At the end of the course, the students who completed all the mandatory assignments will have developed a simple interpreter and a compiler.

Syllabus

  • OCaml basics
  • Implementing the semantics of (simple) programming languages
  • Lexing and Parsing with ocamllex and menhir
  • Defining and enforcing a type system for a functional language
  • Compiling a simple imperative language
  • Implementing a simple data-flow analysis tool

Resources (tools and bibliography)

  • The OCaml language
  • The OCaml API
  • OPAM (the OCaml packet manager)
  • utop is an improved toplevel (i.e., Read-Eval-Print Loop) for OCaml (not mandatory, but sometimes it is useful to try some code interactively. Install it via opam).
  • Dune (a build system for OCaml) : if you take some time to learn how to use it, it will simplify your life, but you can live without it, and it is not mandatory for the course
  • The book Real World OCaml by Yaron Minsky and Anil Madhavapeddy is our main reference for the basics of OCaml
  • OCamllex : the lexer generator that we will use for lexing in our project (ignore ocamlyacc, we will use menhir)
  • Menhir : the LR(1) parser generator that we will use for parsing in our project
  • The section Parsing with OCamllex and Menhir from the aforementioned book Real World OCaml gives you an overview of our lexing and parsing pipeline with some concrete examples
  • The book Compilers: Principles, Techniques, and Tools (2nd Edition) by Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman is a well-known guide to compilers. I recommend using it in case of problems with the parsing phase
  • The book Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson and Chris Hankin is where to look for the static analysis section of our project

Lessons

Project Assignment

At the end of the course, the students are required to submit some code and a report. The project will be composed of different fragments, one for each topic of the course (please be aware that some of the fragments depend on others). Ideally, each lesson targets a specific objective, like parsing a given language or implementing a static analysis tool, and it gives some high-level indications on how to implement it in OCaml. The assignment for the student is to follow the indications and produce the OCaml code. Some minor details are left unspecified on purpose, requiring the students to solve them on their own ;). My main suggestion for the code is to keep it as simple and declarative as possible, postponing optimization to the end. The report must explain the choices of the student in solving the problems encountered while implementing the code (more details in the description of the tasks), and it must contain a guide on how to compile and execute the code.