Programming languages allow us to express our intentions to computers and to each other. This course teaches you how to analyze programming languages, focusing on semantics, the meaning of programs in languages. To understand the semantics of a programming language, we take an engineering approach, building interpreters and compilers for the language. We use this approach to understand a variety of constructs in functional and object-oriented languages and to understand how these constructs interact with each other in real-world languages.
|Lectures||Mon, Wed 8:45–10:15 in Room SI-006|
L&C on Moodle
|Grading||30% Participation, 20% Quizzes, 50% Final exam|
|Mon 18 Feb||Welcome||slides|
|Wed 20 Feb||Haskell crash course||[GIH] chapters 1–3||Install ghc|
|Mon 25 Feb||Algebraic datatypes and pattern matching (Haskell)||Haskell 1|
|Wed 27 Feb||Datatypes and type classes (Haskell)|
|Mon 4 Mar||Red-black trees (Haskell)||rbtree.hs|
|Wed 6 Mar||Lists (Haskell), quiz||Haskell 2|
|Mon 11 Mar||Abstract syntax trees (Haskell and Java)||ast.hs|
|Wed 13 Mar||Interpreters (numbers) (Haskell and Java)||ML Numbers|
|Mon 18 Mar||Strong vs. weak typing (booleans) (Haskell)||ast-bool-weak-typing.hs, ast-bool-strong-typing.hs|
|Wed 20 Mar||Error handling with
|Mon 25 Mar||Variables and environments and stores|
|Wed 27 Mar||Reader and State monads||reader.md||Interpreter|
|Mon 1 Apr||Type checking||typer2.hs|
|Wed 3 Apr||Functions||lambda0.hs (dynamic scoping), lambda1.hs (static scoping), lambda9.hs (substitution semantics)||ML Scoping|
|Mon 8 Apr||Compilation and syntax-directed translation, quiz|
|Wed 10 Apr||More compilation|
|Mon 15 Apr||Regular expressions|
|Wed 17 Apr||Scanning implementation, regex derivatives||notes, paper|
|Mon 22 Apr||Holiday: no class|
|Wed 24 Apr||Holiday: no class|
|Mon 29 Apr||LL parsing||notes|
|Wed 1 May||Holiday: no class|
|Wed 6 May||LR parsing||notes||hgrep|
|Wed 8 May||LALR parser generators|
|Mon 13 May||Memory management (GC)|
|Wed 15 May||More GC|
|Mon 20 May||Introduction to Rust, quiz||Parser exercises|
|Wed 22 May||Ownership and lifetimes||Rust book, main.rs|
|Mon 27 May||Rust traits|
|Wed 29 May||More Rust traits||Rust exercises 1|
There will be approximately one assignment per week. There are three types of assignments.
In a mystery language assignment, you will be given two or more interpreters for a programming language. All three interpreters support the same syntax, which is identical to Python syntax. The interpreters all implement the same semantics except for one language feature. Your task in this assigment is to explore the different implementations and precisely describe how they differ.
In a programming assignment, you will implement (in Haskell) an interpreter for a simple programming language, or implement a compiler phase, or implement a tool used in compiler development.
In a written assignment, you will do exercises related to semantics, typing, parsing, and other programming language issues.
There will be approximately one 15-minute quiz every two weeks.
The final exam is a 3-hour written exam. The best preparation for the exam is to do the assignments and to read the the assigned readings.
Programming assignments may be done in pairs. The contributions of each student must be explicitly Each student is responsible for understanding the assignments.
Mystery language and written assignments must be done on your own.
Cheating and plagiarism are unacceptable. You are free to discuss assignments and solutions with others. However, you must write your own assignments, and must not represent any portion of others’ work as your own. Any cases of plagiarism or cheating will result in penalties for all involved, up to and including receiving a 0 for the course.