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 computation as evaluation. 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 applicative 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. Well-typed expressions are evaluated to produce values, in a manner that is guaranteed to be type-safe. Because functional programs do not cause side-effects we can take advantage of simple mathematical principles in reasoning about applicative behavior and analyzing the runtime properties of programs.
The advantages of FP are significant:
Moreover, FP generalizes IP by treating commands as forms of data that may be executed for their effects.
Upon completion of this course, students will have acquired a mastery of basic functional programming techniques, including the design of programs using types, the development of programs using mathematical techniques for verification and analysis, the use of abstract types and modules to structure code, and the exploitation of parallelism in applications.
Prerequisites: 15-151 or 21-127. 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. In addition, it will be very useful for a student to have developed abstraction skills and to have familarity with the core mathematical structures of Computer Science, such as sets, relations, graphs, and trees.
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.