This is an archive of the Spring 2012 version of 15-150, taught by Dan Licata. This spring semester was the most polished version of the three times I taught the course, Spring 2011, Fall 2011, and Spring 2012. I designed 15-150 with Robert Harper, along with the Spring 2011 TAs, Ian Voysey, Michael Arntzenius, Arbob Ahmad, and Zach Sparks.
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:
Moreover, FP generalizes IP by treating commands as forms of data that may be executed for their effects on the environment in which they occur. Upon completion of this course, students will have acquired a mastery of basic functional programming technique, including the design of programs using types, the development of programs using mathematical verification techniques, and the exploitation of parallelism in applications.
Prerequisites: 21-127: Concepts of Mathematics, or permission of instructor. Students will require some basic mathematical background, such as the ability to do a proof by mathematical induction, in order to reason about program correctness.
Successful completion of this course is necessary and sufficient for entry into 15-210 Data Structures and Algorithms, which will build on the functional model of computation to develop a modern account of parallel algorithms for a wide variety of abstract types.