# 15-150: Functional Programming, Fall 2016

## Overview

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:

• Verification: There is a close correspondence between the mathematical reasoning that justifies the correctness of a program and the program itself. Principles of proof by mathematical induction go hand-in-hand with the programming technique of recursion.
• Parallelism: Since expressions have no side-effects, it is natural to use parallel evaluation: the values of independent subexpressions may be determined simultaneously, without fear of interference or conflict, and the final result is not affected by evaluation order. 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.

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 or 21-128) and (15-112 or 15-122). 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.

## Note to Students

Take care of yourself. Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.

All of us benefit from support during times of struggle. You are not alone. There are many helpful resources available on campus and an important part of the college experience is learning how to ask for help. Asking for support sooner rather than later is often helpful.

If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit their website at http://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.

If you or someone you know is feeling suicidal or in danger of self-harm, call someone immediately, day or night:

CaPS: 412-268-2922
Re:solve Crisis Network: 888-796-8226
If the situation is life threatening, call the police:
On campus: CMU Police: 412-268-2323
Off campus: 911

## Past Instances

• Summer 1 2016, taught by Brandon Bohrer
• Spring 2016, taught by Michael Erdmann
• Fall 2015, taught by Steve Brookes
• Spring 2015, taught by Michael Erdmann
• Fall 2014, taught by Steve Brookes
• Summer 2014, taught by Carlo Angiuli
• Spring 2014, taught by Michael Erdmann
• Fall 2013, taught by Steve Brookes
• Summer 2013, taught by Iliano Cervesato
• Spring 2013, taught by Michael Erdmann
• Fall 2012, taught by Steve Brookes and Jeannette Wing
• Summer 2012, taught by Ian Voysey
• Fall 2011 and Spring 2012, taught by Dan Licata
• Spring 2011, created and taught by Robert Harper and Dan Licata