COMP 212: Functional Programming

Objectives

The purpose of this course is to introduce the theory and practice of functional programming (FP). The characteristic feature of FP is the emphasis on computing by calculation. The traditional distinction between program and data characteristic of imperative programming (IP) is replaced by an emphasis on classifying expressions by types that specify their behavior. Types include familiar (fixed and arbitrary precision) numeric types, tuples and records (structs), classified values (objects), inductive types such as trees, functions with specified inputs and outputs, and commands such as input and output. Execution of imperative programs is generalized to evaluation of well-typed expressions by a smooth extension of mathematical experience to programming practice.

The advantages of FP are significant:

Verification: There is a close correspondence between the reasoning that justifies the correctness of a program and the program itself. Principles of proof by induction go hand-in-hand with the programming technique of recursion.
Parallelism: Evaluation of compound expressions is naturally parallel in that the values of subexpressions may be determined simultaneously without fear of interference or conflict among them. This gives rise to the central concepts of the work (sequential) and span (idealized parallel) complexity of a program, and allows programs to exploit available parallelism without fear of disrupting their correctness.
Abstraction: FP stresses data-centric computation, with operations that act on compound data structures as whole, rather than via item-by-item processing. More generally, FP emphasizes the isolation of abstract types that clearly separate implementation from interface. Types are used to express and enforce abstraction boundaries, greatly enhancing maintainability of programs, and facilitating team development.

By the end of the course, we expect you to:

write functional programs
analyze their sequential and parallel complexity
reason mathematically about their behavior
structure them using abstract types

Prerequisites: COMP 211. MA 228 (or some other math class if you're not ready for that yet) works well as a corequisite.

Activities

There will be two lectures per week, Tu-Th 10:20-11:40 in HA 84. This time will be used for chalk-board lectures, for interactively coding as a whole class, and possibly for small-group or individual work. Lectures will be your primary source of information for the course, and attendance is strongly encouraged.

There will be weekly lab sessions held on Wednesdays, 5:40pm and 7:10pm, in Exley 72. The intention of labs is for you to practice the skills introduced in lecture, under the supervision of the TAs, to prepare you for the week’s homework. The lab assignment will be handed out on Tuesday or Wednesday; you are expected to familiarize yourself with the assignment and with related lecture material before lab. Because different students work at different rates, we do not expect everyone to finish all of the problems in the lab handout. We do expect you to put in a good-faith effort to work on the provided problems and learn something. Labs will be graded on a scale of 0/1: you will receive a 0 if you do not attend lab at all, you leave early, or you do not engage with the material. You will receive a 1 if you put in a good-faith effort and the TAs determine that you have made satisfactory progress.

There will be weekly written and programming assignments. Homeworks are designed to help you internalize the course material; they consist of written problems and short to medium-sized programming tasks. No credit will be given for homework handins that do not compile. If you cannot make it to class for some reason, you may drop the HW off at Dan's office, Exley 633. No late homeworks will be accepted, except by permission of instructor.

There will be an in-class midterm and final exam. As the only completely non-collaborative type of assignment in the course, exams account for a significant portion of your grade. However, lest that sound too scary, the exams will not ask you to learn new skills or be very creative, just to demonstrate that you have acquired the skills we ask you to practice in homeworks and labs.

Assessment

Your grade will be based on homework assignments (45%), a midterm exam (20%), a final exam (30%), and lab/class participation (5%). (Percentages are subject to change.) Generally, 90%-100% should be interpreted as A work, 80-90% as B, 70-80% as C, 60-70% as D, and below that as failing. However, the instructor may adjust the final letter grade boundaries (in either direction) at the end of the semester, to account for differences between the intended and actual difficulty of the assignments. Assignments will be graded for correctness, clarity, and efficiency.