Languages and Compilers

Spring 2019

Course info

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
Course staff
Prof. Nate Nystrom (SI-203)
Filippo Schiavio (2nd floor open space)
General references
[PLP] Programming Language Pragmatics
Michael L. Scott, 2009
[Dragon] Compilers: Principles, Techniques, and Tools, 2nd edition
Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey Ullman, 2006.
Haskell references
Real World Haskell
Bryan O'Sullivan, Don Stewart, and John Goerzen, 2008
[Bird] Thinking Functionally with Haskell
Richard Bird, 2015
(Earlier edition: Introduction to Functional Programming by Richard Bird and Philip Wadler, 1988)
[LYHGG] Learn You a Haskell for Great Good!
Miran Lipovača, 2011
[GIH] A Gentle Introduction to Haskell
Paul Hudak, John Peterson, Jospeh Fasel, 2000
Neil Mitchell, 2012
What I wish I knew when learning Haskell
Stephen Diehl, 2018
The Haskell 98 Report (Revised)
Simon Peyton Jones et al., 2002
Moodle website L&C on Moodle
Grading 30% Participation, 20% Quizzes, 50% Final exam


Date Topic Readings Due
Mon 18 Feb Welcome slides  
  Functional programming    
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 Maybe and Either ast-bool-either.hs  
Mon 25 Mar Variables and environments and stores    
Wed 27 Mar Reader and State monads 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    
  Systems programming    
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,  
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.

Quizzes and exams

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.

Group Work

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.