Programming Language Technology

DAT151 (Chalmers) / DIT231 (GU)

Winter Term 2024 (LP2)

Sources on GitHub

Canvas / GitLab / Schedule / Slack (join!) / Chalmers studieportal / GU ad (sv) / GU kursplan / GU course description / Course page 2022

Schedule

Lectures are Tuesdays and Thursdays, starting at 13:15, both on campus and in Zoom.
Tuesday lectures are in HC2,
Thursday lectures in SB-H6 with exceptions Thu 7nd Nov in HC3 and Thu 12th Dec in HC1 and Thu 28rd Nov and 19th Dec in SB-H5.

Material: plt = course book, dragon = Dragon book. Slides follow closely the plt book.

Date Time Title Lecture material Reading material
Tue 05/11 13-15 PL Design, Compilation Phases slides, plt 1, dragon 1, git
Thu 07/11 13-15 HC3 Grammars / BNFC / Hands-on with Lab 1 live coding start, result slides, plt 2, dragon 2.8.2,4.1-4.3
Tue 12/11 13-15 Formal languages and parsing shift-reduce parsing, LR-table, lr-demo slides, plt 3, dragon 3,4
Thu 14/11 13-15 Theory of lexing slides, plt 3, dragon 3,4
Mon 18/11 23 Lab 1 deadline
Tue 19/11 13-15 Type checking script, prime.c, prime-stms.c, division.c, division-annotated.c slides, plt 4, dragon 5,6
Thu 21/11 13-15 Interpreting script slides, plt 5
Tue 26/11 13-14 Hands-on with Lab 2 (Haskell) live code script: monadic interpreter
Tue 26/11 14-15 Hands-on with Lab 2 (Java) script, Annotated.java
Thu 28/11 13-15 SB-H5 Code generation script, prime.c, prime.j slides, plt 6, dragon 6,7
Tue 03/12 13-14 Hands-on with Lab 3 (Haskell) live code snippet
Tue 03/12 14-15 Hands-on with Lab 3 (Java) live code snippet
Wed 04/12 23 Lab 2 deadline
Thu 05/12 13-15 Functional programming languages script slides, plt 7, dragon 6.5,7.3
Tue 10/12 13-15 Type inference and polymorphism script, visualization tool plt 7.7-9
Thu 12/12 HC1 13-14 Hands-on with Lab 4 (Haskell) live code
Thu 12/12 14-15 Hands-on with Lab 4 (Java) live code
Tue 17/12 13-15 Dependent types (Agda) live coding start, result
Wed 18/12 23 Lab 3 deadline
Thu 19/12 SB-H5 13-15 Preparing for the exam last year's exam, live solution
2025
Mon 13/01 23 Lab 4 deadline
Thu 16/01 8.30-12.30 Exam
Fri 24/01 23 Final lab deadline all lab returns
Tue 15/04 8.30-12.30 First reexam
Thu 28/08 14-18 Second reexam

The official course schema is in Time Edit.

Description

The aim of the course is to give understanding of how programming languages are designed, documented, and implemented.
The course covers the basic techniques and tools needed to write interpreters, and gives a summary introduction to compilation as well.
Those who have passed the course should be able to

  1. define the lexical structure of programming languages by using regular expressions, explain the functioning of finite automata, and implement lexical analysers by using standard tools;

  2. define the syntax of programming languages by using context-free grammars, explain the principles of LL and LR parsing, and implement parsers by using standard tools;

  3. define and implement abstract syntax;

  4. master the technique of syntax-directed translation and its efficient implementation in their chosen programming language;

  5. formulate typing rules and implement type checkers;

  6. formulate operational semantic rules and implement interpreters;

  7. write simple code generators;

  8. be familiar with the basic implementation issues of both imperative and functional languages;

  9. master the principles of polymorphic type checking by unification;

  10. implement an interpreter for a functional language.

Teachers

Andreas Abel, responsible course teacher and examiner.

Assistants:

Questions regarding this class (organization, content, labs) should be asked publicly on the Slack forum in the most cases.
You are also welcome to answer questions by others.
Do not give away any lab solutions when you ask or answer questions!

Lab supervision

Lab supervision is offered in room ED3354 and online on Tue, Thu and Fri.
Starting 13 Nov we offer Zoom-only supervision on Wednesdays 15:15-17:00.
The lab rooms and supervision are available from Tue 05 Nov till Fri 20 Dec 2024.
Attendance is voluntary.

Day Time Location Supervisors
Tue 15:15-17:00 Zoom, ED3354 Andreas, David, Jonas
Wed 15:15-17:00 Zoom only David, Eric
Thu 15:15-17:00 Zoom, ED3354 Andras, Jonas, Ruohan
Fri 13:15-15:00 Zoom, ED3354 Andras, Ruohan, Eric

Extra Zoom-only supervision session will be provided:

We use Slack to organize the lab supervision. Please join our Slack workspace and the channel #queue.

The TAs will be present in lab rooms during lab supervision slots, available for help both in-person and virtually.
To ask for help, just send a ticket request through the #queue Slack channel.

Labs

You have to pass the labs to pass the course.
However, the course grade is determined solely by the exam.

The labs are quite substantial, so please set aside at least 30 full working hours (4 full working days) before the deadline.
It is recommended to start at least 10 days before the deadline.

Labs are to be solved in groups of two. (Individual solutions are accepted per exception, please contact the course responsible.) You are expected to find a lab partner with whom you will do the labs.
If you have difficulties finding a partner, please use Slack channel #lab-partner.
Groups are formed on Canvas and then recreated automatically on Chalmers GitLab.
After the first lab has been submitted, the groups are fixed. (Should you nevertheless need to urgently change to group, please contact the course responsible.)

The labs will be published in your Gitlab group and a solution repository will be created for you there.
Submission of your solution is by creating a submission tag in the repository.
Please read the detailed lab instructions at:
https://chalmers.instructure.com/courses/31854/pages/lab-infrastructure-on-chalmers-gitlab

Keep your lab solutions confidential!
If you post problems and discussions around the labs on Canvas etc., make sure you do not give away the solution.

We guarantee two gradings per lab: one for the version submitted before the ordinary deadline for that lab, the other for a resubmission before the final deadline.
If your first submission does not build or does not pass the testsuite, you will just get fails testsuite as grading.

As part of the grading, you may be asked to explain your solution in person to a course teacher.
Be prepared to get a call for such an explanation meeting.
In particular, make sure you understand all parts of the solution (good documentation helps!).

Exam

The written exam determines the course grade, the usual grading scales apply:
Chalmers: 5, 4, 3, U;
Gothenburg University: VG, G, U.

Exam dates: 16 Jan 2025 am J, 15 Apr 2025 am J, 28 Aug 2025 pm J.

The exam tests the understanding of the course contents from a more high-level view, e.g., the underlying theoretical concepts.
The exam has the same structure as these old exams (download as archive).

Further, here are some old exercises and solutions to prepare for the exam.

Literature

  1. The main book will be one that developed from earlier editions of this course:

    Aarne Ranta,
    Implementing Programming Languages. An Introduction to Compilers and Interpreters,
    College Publications, London, 2012.
    Web page (with extra material and links to selling sites)

    Please also check the errata page (welcome to submit errata not covered there yet).

  2. If you are really interested in the topic, for instance, if you want to continue with the Compiler Construction course, you should also consider the Dragon book,

    Aho, Lam, Sethi & Ullman,
    Compilers Principles, Techniques & Tools, Second edition,
    Pearson/Addison Wesley 2007.

Both books are available at web bookshops. The main book will also be sold at Cremona.

A good (yet slightly dated) introduction to monads in Haskell, useful for implementing interpreters, type checkers, and compilers, is this article:

Philip Wadler,
Monads for functional programming.
In Advanced Functional Programming,
First International Spring School on Advanced Functional Programming Techniques,
Båstad, Sweden, May 24-30, 1995.

It also contains an introduction to parser combinators.

Software

To solve the labs, you need a developer environment with the following tools.

General tools

You need to invoke tools from a command shell.
For one, the make build tool and the git version control tool are required.

Setting PATH and other environment variables

Tools can be invoked from the shell only if they are in the PATH of your command shell.
You can add directories to the search path by setting the PATH variable in the initialization script of your shell. Such scripts are located in your $HOME directory. The name of the initialization script usually contains the name of the shell.

Appending the line export PATH=/absolute/path/to/dir:${PATH} to the initialization script will add directory /absolute/path/to/dir to the front of the :-separated list of search paths.

Note that updates to the initialization script only take effect when the shell is restarted.

Haskell tools

Recent versions of the following Haskell tools need to be installed and in your PATH.

We suggest the following installation.

  1. First install GHCup.

  2. You can use ghcup tui to review your installed versions of Haskell tools and to install/uninstall them. After installing a tool, you have to "set" it to make it visible in your shell. Install and set the latest Stack version, and also GHC 9.4.8.

  3. Use Stack to install the remaining tools.

    stack install alex happy BNFC

    This might alert you in the end that you do not have the installation directory in your system PATH; in this case, go and add it there.

  4. Verify that these tools are working by querying their version:

    stack --version
    ghc   --version
    bnfc  --version
    alex  --version
    happy --version

Java

You need the java virtual machine in your PATH.

java -version

We will use version 21 of Java.

You might chose to solve the labs in Java.
In this case, you need the Java Development Kit (JDK). You can get all neccessary Java dependencies by installing openjdk-21 (e.g. with a package manager on Linux/macOS or by downloading here on Windows).
We publish Java stubs for the labs that use Gradle build tool, preconfigured to install the Java parser generator CUP and the lexer generator JFLex. If you use the stubs, there is not need to install Gradle, CUP and JFlex yourself.

Student representatives

Student representatives for DAT151 Programming language technology.

Program @student.chalmers.se Name
MPALG fadiab Fadi Abunaj
MPCSN antonand Anton Andersson
UTBYTE davfern David Fernández-Sanguino
MPALG tobhag Tobias Hägglund
MPCAS erhaka Erik Håkansson

https://teach-plt.github.io/www/, (C) Andreas Abel 2024