Programming Language Technology

DAT151 (Chalmers) / DIT231 (GU)
Winter Term 2021 (LP2)

http://www.cse.chalmers.se/edu/course/DAT151/

Fire / Canvas / Schedule / Chalmers studieportal / GU ad (sv) / GU kursplan / GU course description / Course page 2020

News and changes

2022-01-19
Remember the final lab deadline on Friday 28th of January 2022. The last supervision sessions (Zoom only) are offered Tuesday 25th and Wednesday 26th 15.15-17.00.

2022-01-19
The exam got 90 submissions, with many excellent ones! Exam text and solution.

Exam review will be held Monday 24 January 2022 13:30-15:00 in EDIT 6128. If you are not able to show up in person, please email the course responsible with subject "PLT 2022 exam review". If this is during the exam review time, please also supply a zoom link, so that a remote review can be facilitated on the spot.
2021-11-17
Tuesday lectures on 2 dates, 2021-11-23 (next week) and 2021-12-14 (final Tuesday lecture) will take place in SB-H1 (210 seats!).

2021-11-15
Tuesday lecture (2021-11-16) in HB3.

2021-11-04
Stub for today's live coding online.

2021-11-03
Until further notice, lectures will be streamed on Zoom (link see Canvas). On-campus attendance is recommended though, for a better lecture experience and better interaction.
2021-11-01
Lab supervision is available both via Zoom and in ED3354. Queueing is via Waglys in both cases. Details see below.

The lecture hall HC2 of tomorrow's lecture (Tue 2 Nov 13-15) has only 104 seats. Thus, I will offer streaming of this lecture via Zoom (hybrid format). You are welcome to join via Zoom in case you cannot or do not want to attend in person (e.g. if you shy crowds these days, or have symptoms etc). Zoom link will be published via Canvas.

2021-10-27
First published version of this page.

Schedule

Tuesday lectures are in HC2, with exceptions, Thursday lectures in HA1, starting at 13:15.

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

Date Time Title Material
Tue 02/11 13-15 PL Design, Compilation Phases slides, plt 1, dragon 1, code
Thu 04/11 13-15 Grammars / BNFC / Hands-on with Lab 1 slides, plt 2, dragon 2.8.2,4.1-4.3, live coding start
Tue 09/11 13-15 Formal languages and parsing slides, plt 3, dragon 3,4, LL parser code LR-table.txt
Thu 11/11 13-15 Theory of lexing slides, plt 3, dragon 3,4
Mon 15/11 23 Lab 1 deadline
Tue 16/11 13-15 HB3 Type checking slides, plt 4, dragon 5,6, script prime.c
Thu 18/11 13-15 Interpreting slides, plt 5, script
Tue 23/11 13-14 SB-H1 Hands-on with Lab 2 (Haskell) lab2 PM script Monads
Tue 23/11 14-15 SB-H1 Hands-on with Lab 2 (Java)
Thu 25/11 13-15 Code generation slides, plt 6, dragon 6,7, script
Mon 29/11 23 Lab 2 deadline
Tue 30/11 13-14 Hands-on with Lab 3 (Haskell) lab3 PM
Tue 30/11 14-15 Hands-on with Lab 3 (Java)
Thu 02/12 13-15 Functional programming languages slides, plt 7, dragon 6.5,7.3, script
Tue 07/12 13-15 Type inference and polymorphism plt 7.7-9, script
Thu 9/12 13-14 Hands-on with Lab 4 (Haskell)
Thu 9/12 14-15 Hands-on with Lab 4 (Java)
Tue 14/12 13-15 SB-H1 Dependent types (Agda) Live coding start
Wed 15/12 23 Lab 3 deadline
Thu 16/12 13-15 Preparing for the exam Training exam Solution Answer Q1 Q1.c Answer Q3-6
2022
Mon 10/01 23 Lab 4 deadline
Thu 13/01 8.30-12.30 Exam Exam
Mon 24/01 13.30-15.00 Exam review (EDIT 6128) Solution
Fri 28/01 23 Final lab deadline all lab returns
Tue 12/04 8.30-12.30 First reexam
Thu 25/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 Canvas forum in the most cases. You are also welcome to answer questions by others. (Don't give away any lab solutions when you ask or answer questions!)

Laboration times and supervision

Lab supervision workflow: Start a Zoom meeting and invite your group partner to join. To ask for help, sign up on the Waglys digital waiting list with your 10-digit Zoom ID (as "6435657890" from "https://chalmers.zoom.us/j/6435657890"), so that the TAs know where to find you. Please make sure your meeting does not require password to get in. A TA will join your Zoom meeting as soon as it's your turn.

Lab supervision is also available in room ED3354 on Tue, Thu and Fri.

Day Time Location Supervisors
Tue 15:15-17:00 Zoom, ED3354 Mohammad, Andreas
Thu 15:15-17:00 Zoom, ED3354 Mohammad, Anna
Fri 13:15-15:00 Zoom, ED3354 Oskar, Anna

The lab rooms and supervision are available from Tue 02 Nov till Fri 17 Dec 2021, except for Fri 05 Nov which is a half-day. Extra supervision sessions (Zoom) are planned for January 2022, 15:15-17:00, at the following days: Tue 18th, Wed 19th, Jan 25th, Jan 26th.

Attendance in these classes is optional. Normally, each student should attend at most one supervised laboration time each week. Since attendance is not compulsory, there may be room for more times. But, if there is lack of room, those who attend their first supervision of the week have priority to get a place and supervisor help.

Laborations

There will be four laborations, written in pairs. (Individual solutions are accepted per exception, please contact the course responsible.) 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.

It is recommended to use a version control system like git for code development. In case you use cloud-based code hosting like, e.g., GitLab, GitHub, or Bitbucket, make sure your repository is private to not give away your lab solution. (Along the same lines, never post your solution on public fora and mailing lists!)

Reporting is done via Fire. Before submitting your solution, run your program through the provided test suite. Also, make sure that your submission contains all necessary files and the build succeeds. For instance, if you are submitting an archive, unpack the archive in a fresh directory and check the build there.

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.

Note: You have to submit something by the first deadline, otherwise Fire will not allow a (re)submission for the final deadline. (In the worst case, if you absolutely did not manage to work on the lab before the first deadline, submit an empty solution.)

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: 13 Jan 2022 am J, 12 Apr 2022 am J, 25 Aug 2022 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

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)

Errata

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

If you are solving the labs on your own Windows machine, you might have to obtain some command-line developer tools stemming from the Unix world, like make, tar, etc. (These are by default available on Linux and can be installed from Xcode on macOS.) Windows from version 10 offers installation of a Linux distro via the Windows Subsystem for Linux (WSL). Other options are MSYS2 and Cygwin.

BNFC

We use the BNF Converter (Homepage | Hackage | Stackage | GitHub).

Download and installation instructions at https://bnfc.digitalgrammars.com/.

When using the Java backend, you will need either ANTLR or the CUP libraries and either JFLex or the JLex libraries. CUP has seen incompatible changes in its interface; thus, the version you need may depend on your BNFC version.

Java/CUP Instructions for BNFC ≥ 2.8.2 (uses CUP v0.11b)

Download the JAVA archives for CUP v11b, CUP v11b runtime, and JLex. Make sure they are placed in your classpath, for example (Linux / macOS) by storing these jars in $HOME/java-lib/ and adding the following line (or a suitable variant) to .bashrc (could also be .bash_profile or similar):

    export CLASSPATH=.:${HOME}/java-lib/java-cup-11b.jar:${HOME}/java-lib/java-cup-11b-runtime.jar:${HOME}/java-lib/JLex-1.2.6.jar:${CLASSPATH}

Java/CUP Instructions for BNFC ≤ 2.8.1 (uses CUP v0.10k)

You can download pre-compiled versions here. Make sure they are placed in your classpath, for example (Linux / macOS) by extracting to ~/javatools/ adding the following to .bashrc:

    export CLASSPATH=.:~/javatools/:~/javatools/Cup/:${CLASSPATH}

On Debian-style Linux (like Ubuntu), the following now also works to install these libaries:

    sudo apt install jlex cup

Then the class path needs to be set as follows (bash):

    export CLASSPATH=.:/usr/share/java/JLex.jar:/usr/share/java/cup.jar

Student representatives

Student representatives for DAT151 Programming language technology.

Program @student.chalmers.se Name
MPALG burmanj Joakim Burman
MPCSN yitao Yitao Dong
MPALG syedrahamatulla gmail com Rahamatullah Syed
MPALG erikbri Erik Brink
risnew William Risne