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.
Fluency in at least one programming language (e.g., Informatik I & II are sufficient).
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:
None of the books has to be bought, we will only use material that is available online.
Topics (roughly corresponds to lecture titles):
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:
The console-based binaries for holding LTG matches (useful for training purposes) can be downloaded from the game description page (linked above).
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.
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:
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).
Haskell Extensions and Related Concepts:
Parallelism and Concurrency:
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 above.
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.
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.
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.
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.
Introduction, Defining Functions
Reading: LyaH Chapter 1, Chapter 2 (upto "An intro to lists" and/or RWH Chapter 1
Types and Classes, Defining Functions, List Comprehensions, Recursion
Reading: LyaH Chapter 1-5 and/or RWH Chapter 1/2
Higher-Order Functions, Declaring Types, Declaring Classes
Reading: LyaH Chapter 6 & 8 and/or RWH Chapter 3 & 6
Lazy Evaluation, IO, Modules, Cabal
Reading: LyaH Chapter 7 & 9 and the paper Why Functional Programming Matters by John Hughes published in the Computer Journal in 1989
Reading: Principal type-schemes for functional programs by Luis Damas & Robin Milner
Functors & Applicative Functors
Reading: LyaH Chapter 8 (section Functor Typeclass) & Chapter 11 andThe Typeclassopedia by Brent Yorgey (Chapter in "The Monad Reader" issue 13) pages: 18-28
Abstract Data Types and Automated Property-based Testing
Reading: Real World Haskell - Chapter 11. Testing and quality assurance (also covers Haskell Program Coverage) and Koen Claessen and John Hughes. QuickCheck: a lightweight tool for random testing of Haskell programs.
Monoids and Monads
Lecturer: George - Contains Project Slides
Reading: Real World Haskell (Chapter 18) andThe Typeclassopedia by Brent Yorgey (Chapter in "The Monad Reader" issue 13)
Datatype-generic Programming in Haskell
Guest lecturer: Andreas Löh
Final Lecture (summary of the course topics, relevance to other languages and programming techniques, and where do we go from here)