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. Lectures will be in Exley 150, Tuesday and Thursday 2:50-4:10pm. If you miss class or want to review, the (asynchronous) videos from a previous year's course will be linked from the lectures page. There are also readings (lecture notes from a previous instance of this course). We may cover a bit of new material this semester that is not in these pre-recorded videos or notes, especially towards the end of the semester.

There will be weekly lab sessions held on Wednesday at 1:20pm-2:40pm in Exley 638 and 2:50pm-4:10pm in Exley 103 (ST Lab). Labs are intended to be the bridge between lectures and homeworks: you practice the skills introduced in lecture, with help, to prepare you for the week’s homework. There will occaisonally be a bit of new material beyond the lecture content introduced in lab, and you are responsible for this material. Solutions will be posted with the labs. Lab attendance is optional but strongly recommended, but ultimately you should use the labs in the way that is best for you (doing them during lab time; trying them on your own and reading the solutions; or reading through the problems and solutions before starting the week's homework). Some lab solutions will be discussed in the next day's lecture, so you should plan to do them before then to avoid spoilers.

There will be weekly written and programming assignments. Homeworks are designed to help you internalize the course material and are where most of the learning in the class happens; they consist of written problems and short to medium-sized programming tasks. Homeworks will be submitted by uploading them to a Google Drive folder. No late homeworks will be accepted except by permission of instructor (but please ask if you need extra time!).

For assistance with the homeworks, there will be regular help sessions.

In place of exams, there will be non-collaborative challenge problems on many homeworks. These problems will test your proficiency with the material without help from the course staff.

Assessment

Your grade will be based on the homework assignments. Around 80% of the homework points will be from regular problems, and 20% will be from non-collaborative challenge problems. Each homework will be worth somewhere between 50 and 100 points depending on its length, with your overall grade depending on the total number of points received. 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. You are allowed to take the course CR/U, in which case a D- or better is required for a transcript grade of CR. However, to use it the class to declare the COMP major, it must be taken for a grade, and you must get a C- or better.