COMP 150FP Schedule

Wed, Jan 14

Opening exercise: embedded languages

Additional papers handed out in class:

• Chris Okasaki, Techniques for Embedding Postfix Languages in Haskell (2002)
• Chris Okasaki, Red-Black Trees in a Functional Setting (1999)

Mon, Jan 19

No class (Martin Luther King Day)

Wed, Jan 21

Programming exercises: higher-order functions for embedded PostScript; Bubblesearch packing of albums into DVDs

Additional papers handed out in class:

• Lesh and Mitzenmacher, BubbleSearch: A Simple Heuristic for Improving Priority-based Greedy Algorithms (2006)

Mon, Jan 26

Solutions to DVD-packing problem

Additional papers handed out in class:

• Stephen K. Park and Keith W. Miller, Random number generators: good ones are hard to find (1988)

Wed, Jan 28

Why functional programming matters
Read:

• John Hughes, Why Functional Programming Matters (1989)

Mon, Feb 2

Read:

• Philip Wadler, How to Replace Failure by a List of Successes: A method for exception handling, backtracking, and pattern matching in lazy functional languages (1985)

Wed, Feb 4

Calculuating programs using algebraic laws
Read:

• Richard S. Bird, Functional Pearl: A program to solve Sudoku (2006)
• Richard S. Bird and Shin-Cheng Mu, Inverting the Burrows-Wheeler transform (2004)

Mon, Feb 9

Program calculation for the compiler
Read:

• A Gill, J Launchbury, and SL Peyton Jones, A short cut to deforestation
• Duncan Coutts, Roman Leshchinskiy, and Don Stewart, Stream Fusion: From Lists to Streams to Nothing At All (2007)

Wed, Feb 11

I/O in a pure functional language
Read:

• Simon Peyton Jones and Philip Wadler, Imperative functional programming. (1993)

Additional papers handed out in class:

• Jon L. Bentley and Robert Sedgewick, Fast Algorithms for Sorting and Searching Strings (1997)

Mon, Feb 16

No class (Presidents' Day)

Wed, Feb 18

Monads!
Read:

• Simon Peyton Jones, Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell (2001)

Thu, Feb 19

Continue work from previous class

Mon, Feb 23

Review of algebraic data types; design of a Unix shell

Additional papers handed out in class:

• M. Douglas McIlroy, Enumerating the Strings of Regular Languages (2004)

Wed, Feb 25

Overloading
Read:

• Philip Wadler and Stephen Blott, How to make ad-hoc Polymorphism less ad hoc (1989)

Mon, Mar 2

No class (A big snowstorm)

Wed, Mar 4

Overloading
Read:

• Mark P. Jones, A system of constructor classes: overloading and implicit higher-order polymorphism (1993)
• Koen Claessen and John Hughes, QuickCheck: a Lightweight Tool for Random Testing of Haskell Programs (2000)

Useful background reading before class:

• Simon Peyton Jones, Mark Jones, and Erik Meijer, Type Classes: An Exploration of the Design Space (1997)

Additional papers handed out in class:

• Mark P. Jones, First-class Polymorphism with Type Inference (1997)
• Peter Thiemann, An embedded domain-specific language for type-safe server-side web scripting (2005)
• Peter Thiemann, Modeling HTML in Haskell (2000)

Mon, Mar 9

Ternary search trees; the NFA challenge; applying QuickCheck; plans for 2nd half

Wed, Mar 11

Analysis of what we have (and have not) learned; plans for the second half of the term

Mon, Mar 16

No class (Spring Break)

Wed, Mar 18

No class (Spring Break)

Mon, Mar 23

Higher-order functions and parsing combinators
Read:

• Graham Hutton and Erik Meijer, Functional Pearl: Monadic parsing in Haskell (1998)

Useful background reading before class:

• Graham Hutton, Higher-order Functions for Parsing (1992)
• Jeroen Fokker, Functional Parsers (1995)

Additional papers handed out in class:

• David A. Turner, The Semantic Elegance of Applicative Languages (1981)
• John Hughes, The Design of a Pretty-printing Library (1995)
• Philip Wadler, A prettier printer (1999)
• Olivier Danvy, Functional Unparsing (1998)

Wed, Mar 25

Operational semantics: the fire hose
Read:

• Gilles Kahn, Natural Semantics (1987)

Useful background reading before class:

• Peter J. Landin, The Mechanical Evaluation of Expressions (1964)
• Gordon D. Plotkin, A structural approach to operational semantics (1981)
• Matthias Felleisen and Robert Hieb, The Revised Report on the Syntactic Theories of Sequential Control and State (1992)
• John Launchbury, A natural semantics for lazy evaluation (1993)

Mon, Mar 30

Proof system and metatheory for inequality of Peano numerals

Wed, Apr 1

Small-step operational semantics with explicit contexts (expressions only)

Mon, Apr 6

Two forms of operational semantics compared

Wed, Apr 8

Using contexts to implement control operators

Mon, Apr 13

Review of small-step operational semantics with mutable state and a control operator

Wed, Apr 15

Continuations and definitional interpreters

Additional papers handed out in class:

• John C. Reynolds, Definitional Interpreters Revisited (1998)
• John C. Reynolds, Definitional Interpreters for Higher-Order Programming Languages (1998)
• Sheng Liang, Paul Hudak, and Mark Jones, Monad Transformers and Modular Interpreters (1995)

Mon, Apr 20

No class (Patriots' Day)

Wed, Apr 22

Type inference
Read:

• Luis Damas and Robin Milner, Principal Type-Schemes for Functional Programs (1982)
• Dominique Clément, Thierry Despeyroux, Gilles Kahn, and Joëlle Despeyroux, A simple applicative language: mini-ML (1986)

Mon, Apr 27

Type inference with higher-rank polymorphism
Read:

• Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, and Mark Shields, Practical type inference for arbitrary-rank types (2007)