| title | subtitle | date |
|---|---|---|
Programming Language Technology |
DAT151 (Chalmers) / DIT231 (GU) |
Winter Term 2024 (LP2) |
Canvas / GitLab / Schedule / Slack (join!) / Chalmers studieportal / GU ad (sv) / GU kursplan / GU course description / Course page 2022
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.
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
-
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;
-
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;
-
define and implement abstract syntax;
-
master the technique of syntax-directed translation and its efficient implementation in their chosen programming language;
-
formulate typing rules and implement type checkers;
-
formulate operational semantic rules and implement interpreters;
-
write simple code generators;
-
be familiar with the basic implementation issues of both imperative and functional languages;
-
master the principles of polymorphic type checking by unification;
-
implement an interpreter for a functional language.
Andreas Abel, responsible course teacher and examiner.
Assistants:
- András Kovács
- David Wärn (homepage)
- Eric Olsson
- Felix Cherubini
- Jonas Höfer
- Ruohan Li
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 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:
- Wed 8 Jan 2025 15:15-17:00 (Jonas, David)
- Thu 9 Jan 2025 15:15-17:00 (Jonas, David, Ruohan)
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.
-
For in-person attendance, write your name and how to find you (room if not ED3354, number of the PC in front of you (or any other hint how to recognize you)).
-
For online help, start a Zoom meeting and invite your group partner to join. Please then sign up by providing a clickable URL to your Zoom meeting (e.g.,
https://chalmers.zoom.us/j/6435657890/pwd=OXlBcGxMZjkzNGsyplpYZENYWlVodi09), so that the TA knows where to find you. -
Monitor the queue, the TA will join you/your Zoom meeting as soon as it’s your turn.
You have to pass the labs to pass the course. However, the course grade is determined solely by the exam.
- Lab 1 - parser (deadline 18/11)
- Lab 2 - type checker and interpreter (deadline 04/12)
- Lab 3 - code generator (deadline 18/12)
- Lab 4 - functional language interpreter (deadline 12/01/2025)
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!).
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.
-
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).
-
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.
To solve the labs, you need a developer environment with the following tools.
You need to invoke tools from a command shell. For one, the make build tool and the git version control tool are required.
- On Linux, these are available by default.
- On macOS, you can install them from Xcode (
xcode-select –-install). - On Windows, you should install Git for Windows. This installs Git Bash, a command line shell that mimics Linux and has
makeandgit. You should generally just work from inside Git Bash in the rest of the course.
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.
- E.g. for the Bash:
.bashrcor.bash_profile - E.g. for the Zsh:
.zshrc
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.
- On Windows, this list is
;-separated because:is reserved for drive names. Windows also allows to set environment variables globally for a user through the Control Panel.
Note that updates to the initialization script only take effect when the shell is restarted.
Recent versions of the following Haskell tools need to be installed and in your PATH.
- Haskell Stack, e.g. version 3.1.1
- The Haskell compiler GHC version 9.4.8
- BNFC, the BNF Converter, e.g. version 2.9.5
- Haskell lexer generator Alex
- Haskell parser generator Happy
We suggest the following installation.
-
First install GHCup.
- When asked, answer Yes to adding the ghcup installation directory to PATH.
- Also answer Yes to installing
stack. - On Windows: copy the install script from the GHCup webpage into PowerShell. The installation might take a long time (10+ minutes), apparently because of the Windows Defender antivirus checking the installation very slowly. After this is finished, work in Git Bash for all of the following steps.
-
You can use
ghcup tuito 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. -
Use Stack to install the remaining tools.
stack install alex happy BNFCThis 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. -
Verify that these tools are working by querying their version:
stack --version ghc --version bnfc --version alex --version happy --version
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 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