Functional Programming (CSE 502)
Fall Quarter 2000
Tuesdays and Thursdays, 11.30 - 12.50, in JM561.
Instructor:
John Launchbury
Course Structure
I teach in an informal style and encourage class participation as much as possible,
but it is vital that the lecture material be reinforced by hands-on experience. Each week I will assign some reading
from the course text together with programming exercises. Because the homework is designed to help you master the
subject, it is worth heeding the following warning: if you do not do substantially
all of the homework, then do not expect to pass. 50% of the marks for the course will come from weekly coursework, and another
30% from a final project. In addition, the course includes a midterm which is designed
to confirm understanding of the basics.
- Week 1. Functional Programming Basics. Values, types,
abstraction. Function definitions. Evaluation. Examples with simple
geometric graphics. (fp01.ps, fp02.ps)
- Week 2. Small functional programs. Displaying shapes. Polymorphism,
higher-order functions, trees. (fp03.ps, fp04.ps)
- Week 3. Expressions over richer types. New list processing
functions. Composite geometrical shapes. Operations over functions and
trees. (fp05.ps, fp06.ps)
- Week 4-5. Algorithmic and reasoning methods. Techniques in recursion
and induction. Combinators. Parsing. (fp07.ps, fp08.ps,
parsing.hs) Type classes. (fp10.ps)
- Week 6. Midterm.
- Week 7. Actions. Midterm review. Monads. Begin
projects. (fp12.ps, project.ps)
- Week 8. Real world FP. Debugging and testing functional programs.
(Hood and
Quickcheck
libraries). State, monad control structures (fp15.ps)
- Week 9. GUI programing in FP. (fp16.ps)
- Week 10. Graphs. Handling sharing. Comparing functional with
imperative methods. Animations
(Tk Gofer).
(fp18.ps, fp19.ps).
- Week 11. Projects Due.
Course Text
Paul Hudak The Haskell School of Expression: Learning Functional Programming through
Multimedia,
Cambridge University Press, ISBN: 0521644089
This book teaches functional programming as a way of thinking and problem solving, using Haskell, the most popular
purely functional language. Rather than using the conventional mathematical examples commonly found in other
programming language textbooks, the author draws examples from multimedia applications, including graphics,
animation, and computer music, thus rewarding the reader with working programs for inherently more interesting
applications. Aimed at both beginning and advanced programmers, this tutorial begins with a gentle introduction to
functional programming and moves rapidly on to more advanced topics. An underlying theme is the design and
implementation of domain specific languages, using three examples: FAL (a Functional Animation
Language), IRL (an Imperative Robot Language), and MDL (a Music Description Language). Details
about programming in Haskell are presented in boxes throughout the text so they can be easily referred
to and found quickly.
Supporting Software
Each student will need access to a Haskell implementation which are available free from the
Haskell web site. I strongly recommend the Hugs
interpreter, together with the associated graphics
libraries (note: for Windows systems dowload both the graphics library
source code and the Win32 binaries). These should work both on Windows and Linux systems.
A Few Cool Haskell Links
- Our Haskell ray tracer
programming competition entry, written in 72 hours.
- Conal Elliott's wacky image
transformations.
- The Lava hardware
specification system