Lehrstuhl für Datenbanksysteme (Database Systems Chair)

As the size and complexity of software systems is growing we are facing increasing challenges related to development time/costs and program correctness. Established programming languages are evolving (e.g., by accommodating new features) and completely new languages are being created to address the aforementioned challenges. This in turn requires developers to constantly update there skills with new programming techniques.

In this course we will be studying advanced features of functional programming languages, results of the latest programming languages research that are already making impact on software industry. The features in main-stream programming languages that originated or are inspired by functional programming languages include: generics in Java; type inference in C#; list comprehensions in Python; monad comprehensions in C# and Visual Basic; blocks in C, C++ and Objective-C; closures in Java; anonymous functions C# and concepts in C++. As for the programming techniques that draw there inspiration from functional programming, Google's MapReduce framework deserves a particular mention.

We have chosen to use Haskell, a standard, purely functional programming language, throughout the course as it incorporates all the topics that we cover in a single coherent language. Having said that, no prior knowledge of Haskell is required. The course aims to improve the student's programming skills in general as the acquired know-how is transferrable in a wide variety of programming languages, be it functional or otherwise.

Index

• Introduction
• General course information
• Enrolment requirements
• Examination form
• Course goals
• Literature
• Topics
• Lectures
• Time and location
• Project
• Project Solutions
• Writing Assignment
• Student Papers
• Paper Review
• Assignments
• Software
• Useful links
• Lecturers

General course information

• ECTS: 6 (for diploma students: 2V+2Ü SWS, Praktische Informatik)
• The course can be taken as either a Bachelor or Master course
• Course language: English
• Lectures: 1x 2 hours per week
• Guided lab-session: 1x 2 hours per week
• QA session: 1x 2 hours per week (optional)

Enrolment requirements

Fluency in at least one programming language (e.g., Informatik I & II are sufficient).

Examination form

Weekly exercises: 40%
Project: 40%
Research/Writing/Review: 20%

Course goals

After this course a student can effectively use novel programming techniques that are currently entering main-stream programming languages and were inspired or influenced by state-of-the-art functional programming languages.
In particular the student will learn:

• purely functional programming;
• methods for combining purely functional programming with imperative programming with effects;
• lazy and strict evaluation strategies;
• advanced type systems with type inference;
• abstractions for structuring large programs and libraries;
• functional programming techniques to tackle challenging, and in the same time practical, problems (e.g., program correctness and performance,      automated testing, concurrency and parallelism);
• wide variety of functional programming tools and libraries;
• how to research and explain (through writing) novel programming techniques to fellow programmers.

Literature

None of the books has to be bought, we will only use material that is available online.

• Real world Haskell
• Learn you a Haskell

Topics

Topics (roughly corresponds to lecture titles):

• Introduction to functional programming
• Defining functions
• Types and classes
• List comprehensions
• Recursive functions
• Higher-order functions
• Interactive programs
• Declaring types and classes
• Lazy evaluation
• Reasoning about programs
• Type systems with type inference
• Property based automated testing
• Functors and applicative functors
• Monoids and monads
• Monad transformers
• Modules and abstract data types
• Documenting and packaging modules into libraries and applications
• Profiling and performance tuning
• Deverloping purely functional data structures
• Embedded domain-specific languages
• Metaprogramming
• Parallelism and concurrency
• Datatype-generic programming
• Functional programming techniques in mainstream, object-oriented, imperative, multi-paradigm and domain-specific languages

Lectures

The lecture table below provides a (tentative) overview of the lecture topics. Slides of the lectures will be made available after the lectures.

Time and location

Note: New time and location! Please see below.

Project

As an AFP course project you need to implement the Lambda the Gathering game (from the ICFP 2011 programming contest) player in Haskell. The game description is available here.The deadline for the course project submission is 2012-JAN-30 23:59:59. Before that, we will organise practice tournaments on QA and practicum sessions.

The AFP course project specific rules are the following:

• You must work in a team with four, five or six members.
• A team name may only contain upper and lower case latin letters.
• The project must be implemented in Haskell.
• The executable that plays the game should be built using the Cabal build system.
• Both the cabal file and the executable that it produces should be named as LTG-YourTeamName, where YourTeamName is your team name.

Holding Lambda the Gathering Matches

The console-based binaries for holding LTG matches (useful for training purposes) can be downloaded from the game description page (linked above).

• Source code
• Statically linked Linux binary (x86-64)
• Statically linked Mac OS X binary (tested on Snow Leopard and Lion)
• Statically linked Windows binary (tested on Windows XP)

This is a graphical visualiser of LTG match logs. The visualiser was originally developed for the ICFP 2011 programming contest by the "Funktion im Kopf der Mensch" team from Austria. I have modified the original source code to fix a number of bugs, to address a plenty of compiler warnings, to allow selection of the visualiser's font and to enable statically linked builds on Mac OS X, Linux and Windows.

A Lambda the Gathering match can be visualised as follows:

> ltg match bot1 bot2 2>&1 | ltg-vis

Here, ltg is the binary provided by the contest organisers. The match log, which is written to stderr is redirected to the graphical visualiser.

If the provided binaries do not work for you then download the source code and build it. Adjust the default build rule in the Makefile if required. If you build the visualiser on an architecture not listed here and you wish to make your binary available for other students please email to George.

Project Solutions

8 Teams participated in the programming project. The assignment was to create a bot that plays the game of lambda the gathering. On the 02-02-2012 we held a tournament where all bots competed against eachother. The bot of team qwert won the tournament.

Below you find all the bots that where created for this assignment:

• All Your Lambda Are Belong to Us
• der Programm
• Grusig
• Knights of the Lambda Calculus
• Never Gonna Inc You Up
• Qwert
• Team Euclid And Monad
• Team Awesome

Writing Assignment

As we told in the third lecture instead of presenting you guys get to write a paper/tutorial. Which style you can pick best depends on the topic (some topics are suited for both styles). In the paper style writings we expect both how things work internally but also why/how you would use it (a bit more briefly). In the tutorial style papers we expect a nice structured story explaining how the tool/concept/library/etc. can be used along with demo code and in somewhat less depth (but still reasonably deep) on how it works. The paper has to be handed in through CIS by Sunday the 15th of January. On the 16th of January you will then receive the paper you have to review along with further instructions. The deadline for the review will be on the 23th of January before the lecture (14:00).

There is no minimal length but you will probably not do very well content wise with just one page. Recommended length is 4+ pages, with an absolute maximum of 8 pages. You can use Latex to write your paper/tutorial but other tools are also allowed (but make sure it all looks good with consistently referenced figures, sources and so on.), we recommend you hand in a pdf file regardless of what tool you use (other file format we might not be able to open, or it may look ugly on our machines). Use the A4 page size with 2cm margins, an 11pt font, and single line spacing. You can work in teams of two.

Your paper/tutorial has to be written in English. Unlike with the weekly exercise the quality of writing will influence your grade. This will make roughly a half point to one point difference. If you do a good/OK job content wise it will not lead to a failing grade. The other way round, perfect English but bad content might very well lead to a failing grade.

We compiled a list of possible topics, which we divided into several categories. This list is not fixed, you are allowed to suggest other topics (we will then consider whether it is an appropriate topic). We do not provide pointers to reading material/papers. When you really cannot find anything, or doubt the quality of material you found, you can contact us.

Pick three topics from the list below and e-mail them to us (along with the names of both authors). E-mail us before the 2nd of November 9am. Lists that are send in later will be considered after dividing the topics of those that were in time (and might lead to having to pick new topics).

The list of topics:

Tools:

Darcs
Hoogle
lhs2tex
Snap
Yesod
Happstack
Haddock
Agda

Libraries:
XML libraries (HaXML, HXT)
Alternative to lazy IO (Iteratee, Enumerator)
Scrap Your Boilerplate (Generic programming)
Uniplate (Generic programming)
Yampa (Functional Reactive Programming)
Reactive (Functional Reactive Programming)
Bytestring
Text
Vector
HUnit
Smallcheck and LazySmallcheck

Haskell Extensions and Related Concepts:
Monad Comprehensions
Arrows and the arrow notation
Functional dependencies
Type families (type functions)
Safe Haskell
FFI (Foreign Function Interface)
Quasi-Quoting

Parallelism and  Concurrency:
par and pseq combinators
parallel strategies
monad-par
concurrency in Haskell
Software Transactional Memory (STM)
Data Parallel Haskell (DPH)
Cloud Haskell
Repa
Accelerate

Parsing:
Parsec
uu-parsinglib

Databases:
HDBC
HaskellDB
Database Supported Haskell (DSH)

Student Papers

As a part of this course all participants had to write a paper on a functional programming related topic, either individually or in pairs. The assignment description can be found here.

Below we list the papers written by the participating students who agreed to publish their work on the course page. We publish these papers so that the other students can have a look at other interesting functional programming related topics. The papers can be downloaded from here.

• Warp and HTTP-server - Fabian Aicheler and Thomas Kuebler
• Tutorial on Type Families in Haskell - Constantin Bär and Steffen Hildebrandt
• The Quick, The Small and The Lazy - Mathias Bartl
• tutorial for gtk2hs - Volker Börner and Marc Hartmayer
• Tutorial for HUnit - Christian Duta and Sebastian Brandt
• HaskellDB -- A Tutorial - Tobias Brösamle and Kaan Sahin
• Parallel Strategies - Sebastian Buck and Helmut Dobretzberger
• Concurrency in Haskell - Nadja Klein and Magnus Deininger
• Software Transactional Memory - Michael Schober and Benjamin Dietrich (source code available)
• Foreign Function Interface - Florian Franzen and Konstantin Schmid
• XML in Haskell - Demen Güler and Johannes Keller
• Haskell: A Vector Tutorial - Julian Gutekunst and Philipp Kirstahler
• Functional Dependencies in Haskell - Niklas Heinsohn and Michael Römer
• Database Supported Haskell (DSH) A tutorial - David Wojnar and André Hennig
• Haddock - Niklas Kasenburg and Andreas Friedrich
• Tutorial on Data Parallel Haskell - Michael Kaulig and Sebastian Veith
• Monad Comprehensions - Gregor J. Kovács and Volodymyr Piven
• Arrows - Achim Krause
• Parsec - Christian Lippmann
• Alternatives to Lazy IO in Haskell - Thorsten Ludwig and Richard Hanten
• Biohaskell - Immanuel Luhn and Alf Scotland
• Scrap your Boilerplate: A Practical Design Pattern for Generic Programming Tutorial - Julianus Pfeuffer and Alexander Peltzer
• DARCS -- Distributed Version Management - Paul Seitz and Björn Petri

Paper Review

You have to review the paper of another team as part of the research/writing exercise. If you co-operated with somebody for the paper you *have* to work together on the review as well.

This review should be one page (a bit more is ok, a full page more is not). As for font size etc. the rules are the same as with the paper (use the A4 page size with 2cm margins, an 11pt font, and single line spacing).

Start your paper with a brief introduction about the problem the authors are discussing or what they try to achieve and whether they did so convincingly. Then in half a page summarise the paper.

In the remainder of the review discuss (as a list of points) flaws in the paper, writing/language problems and questions that the paper doesn't answer. Also list the papers good/strong points.

Conclude with a general assessment of the paper (very good/good/OK/bad/very bad) and argue how you came to this conclusion.

Critiques should be fair and you are to consider the scope and reasonable boundaries of the work. Avoid being rude/unreasonable (this doesn't rule out honesty). Your review will be handed to the writer of the paper (after being graded by us, and we feel your comments are not harmful). The reviews will not be anonymised.

Assignments

A set of assignments will be handed out (roughly) every week before you will start working on the project. These assignments have to be handed in through cis before the start of the lecture of the next week.

Software

During this course we will use the programming language Haskell. The most widly used compiler for this language is the Glasgow Haskell Compiler (or GHC for short). We recommend that you install the latest version of the Haskell platform which contains the GHC compiler together with a set of commonly used packages and tools.The Haskell platform can be downloaded from here.

Useful links

Haskell
GHC
Hoogle / Hayoo
HackageDB
Haskell Communities and Activities report
The Monad.Reader

Lecturers

George Giorgidze and Jeroen Weijers