IndexAnnouncements
Instructor Contact Info
Course Description
Course Textbooks
Programming Exercises
Course Policies
Course Mailing List
Homework Assignments
Lecture Notes
Handouts
Sample Code
Programming in SML
SML/NJ FAQ
Announcements/Updates
The first class will be on Monday, March 29, 2010 at 1:30pm in Ry 277.A Midterm Exam will take place in class on Monday, May 3.
The Final Exam will take place 10:30am-12:30pm on Friday, June 11 in Ryerson 277.
Instructor Contact Info
Name Role Office Office hours Phone David MacQueen Professor Ryerson 250 By appointment 2-4980 dbm@cs.uchicago.edu George Kuan TA Ryerson 257B 5:00-6:00pm Tuesday 2-9110 gkuan@cs.uchicago.edu 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#, and the new Go language from Google.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 compare the functional paradigm with the related paradigm of object oriented programming. Finally we will include an brief overview of concurrent functional programming in ML and Haskell.
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 Textbook
The textbooks for the course are:There are a number of other books on Standard ML and Haskell. The following two are particularly useful:
- ML for the Working Programmer (2nd Edition) by Laurence C. Paulson, Cambridge University Press (paperback).
- 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.
- 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.72/index.html. Standard ML is installed on most department servers and workstations, and is located at /opt/smlnj/smlnj-110.71/bin/sml. If you are using a department machine, you might want to add the directory /opt/smlnj/smlnj-110.71/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.
Course Policies
- Grading will be based on the following weightings:
- Homework exercises: 60%
- Midterm exam: 20%
- Final exam: 20%
- Assigments: Homework assignments will normally be given on Wednesdays and will be due by the beginning of class the following Wednesday. Up to two assignments can be late by one class session during the quarter. Programming assignments should be submitted by email to kuan at cs.uchicago.edu, in the form of plain text attachments.
- Collaboration: As in most courses, we encourage students to discuss course content among themselves. Discussions of assignment problems is also permitted to an extent, but submitted assignments should be your own work, and collaborative discussions should be acknowledged.
- Final Examination: The final examination will be a two hour in-class exam given during Finals week (Friday, 6/11/2010, 10:30-12:30, Ryerson 277). It counts the same as the midterm, so it can be thought of as a second midterm.
Course Mailing List
A mailing list has been created for the course. The address is cmsc22300@mailman.cs.uchicago.edu. The web page for the mailing list is at a https://mailman.cs.uchicago.edu/mailman/listinfo/cmsc22300.Homework Assignments
Here are links to the homework assignments.
- Homework 1 (due April 7).
- Homework 1 Solution.
- Homework 2 (due April 14). Homework 2 Solution.
- Homework 3 (due April 21). Homework 3 Solution.
- Homework 4 (due Friday!, April 30). Homework 4 Solution.
- Homework 5 (due Friday, May 14). Homework 5 Solution.
unifyfn.sml (unify functor, 2(a))
term1.sml (terms for 2(b))
term2.sml (terms for 2(c))- Homework 6 (due Friday, May 21 (problems 1-3)). Homework 6 Solution.
Code: (2) output.sml, (3) input.hs, (4) stream2.sml, inputfn.sml- Homework 7 (calculator project) (due Friday, June 4*)
Reader.hs (revised input.hs)
IO-parsing.hs (processing IO input)
listinstream.sml (instream as char list)
readerfn.sml (reader functor)
reader.sml (reader functor applied to ListInstream)
hw7.tgz - a complete SML solution (excepting type checking)Midterm Solutions
Midterm 1 Solutions
Midterm 2 (final) SolutionsLecture Notes
- script1.txt
- script2.txt
- script3.txt (datatypes and records)
- Slides on typing.
- script4.txt (polymorphic type checking)
- script5.txt
- lecture7.txt
- lecture8.txt
- lecture9.txt
- script11.txt (4/23, lazy evaluation and streams)
- script12.txt (4/26, Haskell guards, ML exceptions, references)
- script13.pdf (4/28, ML references)
unify1.sml (unification with substitution)
unify2.sml (unification with reference variables)- script14.txt (4/30, arrays, vectors, strings)
- script15.txt (5/5, SML modules)
- script16.txt (5/10, SML functors, value restriction)
- script17.txt (5/12, More on Haskell type classes, comparison with ML modules)
- script18.txt (5/14, More on Haskell type classes, Modeling functional input.)
input.sml: ML implementation of functional input.
inputfn.sml: functor implementation of functional input.- script19.txt (5/19, Haskell IO monad)
- script20.txt (5/21, Continuations, coroutines)
prodcon-cor.sml (producer/consumer coroutines)
threads.sml (cooperatively scheduled threads)- script21.txt (5/26, Concurrent ML)
Concurrent ML Home Page
prodcon-cml.sml (CML producer/consumer example)
prodcon-cml.cm (CM descriptor file for prodcon-cml.sml)
README with instructions for compiling and running prodcon-cml.sml.- script22.txt (6/2, Concurrent Haskell)
con1.hs (simple Concurrent Haskell example)
prodcon-mvar.hs (producer/consumer in Concurrent Haskell using MVar)
prodcon-chan.hs (producer/consumer in Concurrent Haskell using Chan)
Handouts
Papers and Presentations
- Why Functional Programming Matters by John Hughes.
- Essentials of Standard ML Modules by Mads Tofte.
- Four Lectures on Standard ML by Mads Tofte.
- Reppy talk on Concurrent Language Design
- Concurrent Haskell by Simon Peyton Jones, Andrew Gordon, and Sigbjorn Finne (rather dated)
Additional Useful Links