Course Description

The EducationPage is the `official' web-page for this course and has schedule information. This page provides a longer description.

Prerequisites

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)

Tools

Heap Profiling

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.

Tracing

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.

Haddock documentation generation

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 tool.

Quickcheck

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? library. QuickCheck? provides combinators to define properties, observe the distribution of test data, and define test data generators.

Combinator Libraries

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).

Pretty Printing

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.

Web Authoring System Haskell (WASH)

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.

Financial Contracts

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.

Monadic programming

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!).

Arrows

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.

Multiparameter Type Classes

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.

Special Topics

Monadic IO

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++.

wxHaskell

wxHaskell 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

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.

Literature

Pointers to additional literature in CourseLiterature

Form

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)

Assesment

The final mark for this course wil consist of:

• 20% marks for exercises made
• 40% presentation
• 40% final examination

Final Results

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.

• BoekhoudingAFP2.xls: