View on GitHub

Languages and Compilers

Spring 2018

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)
Igor Moreno (2nd floor open space)
Ilya Yanok (SI-206)
Programming languages 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. ( — The first edition is also (mostly) acceptable, and cheaper, but chapter references will be to the second edition.
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 20% Participation, 20% Quizzes, 60% Final exam


Date Topic Preparation Notes
Mon 19 Feb Welcome   slides
Wed 21 Feb Haskell crash course Install ghc, [GIH] chapters 1–3, Haskell 0  
Mon 26 Feb Algebraic datatypes and pattern matching Haskell 1  
Wed 28 Feb Datatypes and type classes    
Mon 5 Mar Abstract syntax trees Haskell 2
Wed 7 Mar Numbers, quiz ML Numbers  
Mon 12 Mar Interpreters   ast.hs
Wed 14 Mar More interpreters, intro to monads   ast-monad.hs
Mon 19 Mar Holiday: no class    
Wed 21 Mar More interpreters, booleans, strong vs. weak typing ML Conditionals ast-bool.hs
Mon 26 Mar Variables and environments   ast-vars.hs
Wed 28 Mar Mutable state, quiz Haskell 3 ast-mutable.hs
Mon 2 Apr Holiday: no class    
Wed 4 Apr Holiday: no class    
Mon 9 Apr Monoid and Foldable   fold.hs, wc.hs
Wed 11 Apr Parser Combinators 1 Haskell 4 parser0.hs
Mon 16 Apr Parser Combinators 2   parser1.hs
Wed 18 Apr Parsing and scanning    
Mon 23 Apr Scanning   notes
Wed 25 Apr LL parsing Haskell 5 notes
Mon 30 Apr LR parsing   notes
Wed 2 May LALR parser generators    
Mon 7 May Functions    
Wed 9 May More functions, quiz    
Mon 14 May Objects   notes, notes
Wed 16 May Objects LR(0) state machine  
Mon 21 May Holiday: no class    
Wed 23 May Generics   slides
Mon 28 May Garbage collection   notes
Wed 30 May Curry-Howard LR parser generator notes



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

You are encouraged to work on the programming assignments with your classmates. The contributions of each student must be explicitly described. All students are 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. Assignments found to have been plagiarized will be given a grade of 0.