CMSC 22300: Functional Programming

Course Description

This course presents the functional programming paradigm, based on the idea of functions as "first-class" values that can be computed and operated on like other data. Functional languages provide great power of expression while maintaining simplicity, making it easier to write correct and maintainable software. Functional programming has gradually found new applications in areas like finance, telecommunications, and graphics. The essential feature of treating functions as values has also been added to a broad range of conventional languages, such as Python, C#, C++, Objective C, Visual Basic and Google's Go language.

The course will use the languages Haskell and ML as representatives of the two main schools of functional programming, the pure and the impure (i.e. eliminating or permitting side-effects). After learning the basic elements of these languages, we will explore functional programming techniques that can be exploited in many areas of application.

We will briefly compare the functional paradigm with the related paradigm of object oriented programming. In the later part of the course we will cover more advanced topics including concurrent functional programming, reactive functional programming, and programming with dependent types.

Students should have experience programming in one or more programming languages, and familiarity with basic concepts of naive set theory and logic would be helpful. Inductive definitions and inductive proofs will play a central role.

Course Text

The primary text for the course consists of the provided Lecture Notes. These notes will be revised and extended as the course proceeds.

Adequate documentation and tutorials for programming in SML and Haskell are available online, but the following books are useful for background material or further study:

1. ML for the Working Programmer (2nd Edition) by Laurence C. Paulson, Cambridge University Press (paperback).
2. Real World Haskell by John Goerzen and Don Stewart. This book is available on-line in an almost final draft, as a Kindle edition, and as a paperback from O'Reilly.

There are a number of other books on Standard ML and Haskell. The following two are particularly useful:

• The Standard ML Basis Library by Emden R. Gansner and John H. Reppy. This documents the built-in libraries for Standard ML. Most of the content of this book is also available online at http://www.standardml.org/Basis.
• Haskell 98 Language and Libraries: The Revised Report. This is also available online at http://www.haskell.org/onlinereport.

Programming Exercises

This course involves learning functional programming through writing programs in both Standard ML and Haskell.

There are several good sources of documentation and tutorials for SML/NJ available online, and some of these are given in the course SML/NJ page. You can install a copy on your own machine (Mac OS X, Linux, or Windows) by following the instructions at http://smlnj.cs.uchicago.edu/dist/working/110.74/index.html. Standard ML is installed on most department servers and workstations, and is located at /opt/smlnj/smlnj-110.74/bin/sml. If you are using a department machine, you might want to add the directory /opt/smlnj/smlnj-110.74/bin to your PATH.

You can find information about Haskell at the Haskell home page http://www.haskell.org/. We will be using the GHC Haskell compiler in this course, and you should install the "Haskell Platform" found at http://hackage.haskell.org/platform. The GHC compiler is also installed on most department machines, in /usr/bin (e.g. /usr/bin/ghci for the interactive compiler).

Programming assignments should be submitted by email to the course TA. They should be sent as attachments, either plain text for single source files, or zip archives or tarballs for multi-file programs.

This course is not centered on programming projects, but the operational semantics techniques used to formalize programming language concepts are easily translated to programs that implement the concepts. We will use the language Standard ML for such programming experiments. There are several good sources of documentation and tutorials for SML/NJ available online, and some of these are given in the course SML/NJ page.

Course Grading Policies

• Grading will be based on the following:
• Homework exercises: 50%
• Midterm exam: 20%
• Final exam: 30%
• Assigments: Homework assignments will normally be given on Tuesdays and will be due at the beginning of the same day the following week, unless otherwise specified. The policy on late homework is that each student can have a one-time 24 hour extension of the due date, to be used at their discretion. Extensions for cause (illness, religious holiday, family emergency) will be granted on a case-by-case basis, in response to a request in advance of the due date.
• Late Homework Policy: The policy will be that each student can have a one-time 24 hour extension of the due date, to be used at their discression. Extensions for cause (illness, religious holiday, family emergency) will be granted on a case-by-case basis, in response to a request in advance of the due date.
• Final Examination: The final examination will be a two hour in-class exam given during Finals week.