Designing and Using Combinators: The Essence of Functional
Programming
A graduate course by John Hughes
Combinator libraries, nowadays often called Domain Specific Embedded
Languages, offer an easy way to provide a customised programming language
for a particular application domain. Such a language can greatly simplify
applications. The idea of a DSEL is not specific to Haskell, but Haskell is an
excellent "host language" to embed a customised language in, and indeed, this
approach to programming has a long history in the functional language
community.
DSELs can be a valuable tool for researchers, because they support
"exploratory language design". A researcher can identify appropriate
abstractions in the problem domain, and rapidly build a DESL that embodies
them to experiment with.
This course will explain the combinator library idea, give many examples
and applications, and discuss design principles to help you invent your
own. We will also discuss research projects in several areas, where a DSEL is
a key enabling technology.
Requirements
This course is worth 1 study credit for PhD students. To be awarded the
credit, you should complete the exercises (except perhaps for Part 2 of A Stream Processor Monad Transformer). You may solve
the exercises in pairs.
Course Materials
| A lightning tour of Haskell |
Lecture (html,
ps,
ppt)
Accompanying
exercises
Resource: haskell.org |
| Domain specific embedded languages |
Lecture (html, ps, ppt)
Reading: Modular
Domain Specific Languages and Tools |
| Monads and monad transformers |
Lecture (html, ps, ppt)
Reading: Monad
Transformers and Modular Interpreters
Exercises: Exceptions and Extending the Parsing Library
Resource: Phil
Wadler's classic papers on monads
Source code: module MonadTransformers
|
| QuickCheck and Wash/CGI |
Lecture (html, ps, ppt)
Reading:
QuickCheck: A
Lightweight Tool for Random Testing of Haskell Programs
Resource: QuickCheck home
page
Reading: WASH/CGI: Server-side Web Scripting with Sessions, Compositional
Forms, and Graphics
Resource: WASH home page
|
| Deriving combinator implementations |
Lecture (html, ps, ppt)
Reading:Deriving
Backtracking Monad Transformers
Resource: The
Design of a Prettyprinting Library
Source code: module Pretty
Exercise: A Stream Processor Monad Transformer
|
| Functional reactive programming |
Lecture (ps, ppt)
Reading: Functional Reactive
Animation
Resource: the Fran home page
Resource: the FRP home page
|
Things we didn't cover
- Static information in DSELs, Swierstra parsers.
- Arrows.
- Embedding techniques: phantom types. Compile-time
computation using fundeps.
- Compiling combinators (PAN).
- Example:
financial combinators.
- Scripting combinators.
- Code generation combinators.
- Continuations: process and simulation libraries.
- GUI combinators.
Links