is the `official' web-page for this course and has schedule information. This page provides a longer description.
Students are assumed to have a basic knowledge of functional programming (preferably Haskell or ML), as e.g. taught in the courses on Functional Programming
and Grammars and Parsing
in the bachelors program.
Contents (may/will be adapted/extended)
Innocently looking programs may generate huge demand of heap space. Small changes in the program may prevent this. Insight in how lazy evaluation really works may help to prevent large resource consumption. Heap profiling may give insight in when values are produced, and when they are used for the last time.
Functional programs are not always easy to debug, but fortunately there are tools that will (at a huge cost in execution efficiency) generate a full trace af all the executions steps that are taken. Stepping through these traces with special tools may give insights in where errors have been made.
Functional programs maybe small when compared to equivalent java or C++ programs. This makes them however not always easier to understand. Haddock provides a means to include documentation of a program in the program text. From these annotation documentation can be generated by the Haddock
From the Quickcheck page: QuickCheck
is a tool for testing Haskell programs automatically. The programmer provides a specification of the program, in the form of properties which functions should satisfy, and QuickCheck
then tests that the properties hold in a large number of randomly generated cases. Specifications are expressed in Haskell, using combinators defined in the QuickCheck
provides combinators to define properties, observe the distribution of test data, and define test data generators.
Functional programming languages are particularly well suited for the description of domain specific languages, by embedding them in such a language by the definition of a set of combinators. Examples of this are parser combinators, pretty printing combinators, and combinators for grphical animations and simulation of event based and continuous systems.
Parsing libraries and grammar analysis
Parser combinators form the outstanding example of a combinator language, in which one can almost directly transcribe a context free grammar into a functional program. Over the years such libraries have been refined, and provided with many useful extra features. We will study the internals Utrecht Parser Combinator Library
, that allows the construction of very efficient error correcting parsers. We will study two papers. The first paper
describes how we can write parser combinators that can analyse and optimese themselves, whereas the second paper
shows how we can produce results in an online way (i.e. during parsing).
Just as parser combinators, pretty printing combinators have been studied extensively, and many libraries have been constructed over the years. We will study the internals of one of those libraries.
Data Base access (Haskell DB)
Another example of a combinator library is the embedding of access to data bases form functional languages. In Utrecht Daan Leijen has developed HaskellDB?
, a description of which forms part of his thesis (congratulations Daan!)
Functional Reactive Programming (Yampa)
Yampa is the culmination of our efforts to provide domain-specific embedded languages for the programming of hybrid systems using the concepts of Functional Reactive Programming (FRP). Yampa is structured using arrows, which greatly reduce the chance of introducing space- and time-leaks into reactive, time-varying systems.
WASH is a family of embedded domain specific languages (EDSL) for programming Web applications. Each language is embedded in Haskell, which means that it is implemented as a combinator library.
From the Financial Contracts
page: Financial and insurance contracts do not sound like promising territory for functional programming and formal semantics, but in fact we have discovered that insights from programming languages bear directly on the complex subject of describing and valuing a large class of contracts.
We introduce a combinator library that allows us to describe such contracts precisely, and a compositional denotational semantics that says what such contracts are worth. We sketch an implementation of our combinator library in Haskell. Interestingly, lazy evaluation plays a crucial role.
Programming Patterns & Paradigms
Just as in OO-programming functional programmers follow specific patterns. Thanks to the expressiveness of the language such patterns can often be described directly by means of a set of class definitions. The use of such patterns is then achieved by instantiating such calsses by providing class instances.
Monads have proven to be an effective program structuring mechanism, and once well understood, have a tendency to show up everywhere. Unfortunately they are hard to combine into larger structures. Recently Jeff Newburn has produced a tutorial
in which he describes monads from the ground up (Thanks Jeff!).
From the Haskell site: Arrows are a new abstract view of computation, defined by John Hughes [Hug00]. They serve much the same purpose as monads -- providing a common structure for libraries -- but are more general. In particular they allow notions of computation that may be partially static (independent of the input) or may take multiple inputs. If your application works fine with monads, you might as well stick with them. But if you're using a structure that's very like a monad, but isn't one, maybe it's an arrow.
Aspect oriented programming
Programs are composed of a large number a smaller algoritnms and desgn patterns, that have a weak but very specific interaction. As with normal OO patterns it is not always easy to combine these independently into a Haskell program. We will show how for a specific class of aspects this may be achived by the use of fisrt-class attribute grammar combinators.
When Haskell was originally designed it contained a rather straightforward mechanism for handling overloading. With the extension to multi-parameter type classes, that is now supported by most modern Haskell compilers, we have reached a situation where we are dealing with "a programming language inside another programming language". For most people who are confronted with these new possibilities the large number of new ways to do things takes a while to get used to. Functional dependencies
adds an important new way of dealing with the complexities generated by the expresssive power of multi parameter type classes.
Interfacing to the outside world
Haskell is just one of the world's most popular programming languages, but there are many more. The Foreign Function Interface
describes how to make Haskell programs interact with programs written in other languages such as C++.
is a library for writing functional programs that perform graphical IO. It provides an interface to the wxWindows set of programs. It comes with some examples, and is waiting for you to be used in nice further demo's ...
Template Haskell brings the power of meta-programming to the Haskell world. It enables you to partially execute your program, while returning a piece of an Haskell abstract syntax tree that is subsequently embedded and type checked in the context of the orginal program. Many fascinating online program generation techniques suddenly become possible. Beware: this is still an area of active research, but guaranteed to never go away again. Its use is described in the paper Template Meta Programming
by Simon Peyton Jones
Pointers to additional literature in CourseLiterature
Besides the normal lectures, participants will all be assigned a subject from the above mentioned list of topics, about which they will have to prepare:
- a presentation
- a set of exercises to be handed in by their fellow students
- a critical review of the work handed in by their fellow students
- a final written examination regarding the obligoratory reading material (that you may take with you)
The final mark for this course wil consist of:
- 20% marks for exercises made
- 40% presentation
- 40% final examination
There were 10 exercises to be made, so I awarded 0.2 point for every "+" and 0,5 point for every "0", and 0,2 point for "n.v.t.". In the final computation I added 0.5 to the overall result in order to make two 5.5 marks pass. The grades are in the attached spreadsheet. Please check whether your marks have been entered correctly, and none are missing.