CS 135: Designing Functional Programs

Here is a possible week-by-week description of the course. It is to be used more as an aid to understanding the content than an actual schedule; any given week may contain too much or not enough material, and certainly not every example listed can be covered.

The text defines a series of five teaching language subsets supported by the instructional development environment; I have indicated where the changes occur. I have also marked with the yen sign (¥) teaching language constructs which are not in standard Scheme; for the most part, these are either trivial substitutions or simple to define in the standard language. Although Scheme makes heavy use of expressions, some things that look like expressions are special forms to be interpreted differently.

Week 1: (Language level 1) Numbers and arithmetic. Scheme supports arbitrary-precision integers, rationals (displayed as fractions), and inexact reals, marked as such. Prefix notation for common arithmetic functions, e.g. (+ 3 2). Definition of functions using the special form define. Examples: area of ring, Fahrenheit-Celsius conversion. Well-formed and ill-formed expressions; error messages. A design recipe for a function, with a contract, purpose, examples, definition, and tests. Designing functions; auxiliary functions. Using define to bind a name to a value, e.g. (define pi 3.14). Boolean functions. Functions that test conditions, e.g. (< x y). Conditional expressions using the special form cond. Symbols defined using quote or ', e.g. 'red, 'blue. The difference between symbols and strings.

Week 2: Compound data using the example of a 2-D coordinate or posn (¥). Drawing simple pictures. User-defined structures using the special form define-struct (¥). Example: (define-struct entry (name office-number phone)), which creates the constructor function make-entry and the selector functions entry-name,entry-office-number, and entry-phone. Imposing some meaning on structures by using data definitions, e.g. a description of entry that says name is a string, office-number and phone are numbers. Designing functions that operate on compound data (e.g. drawing slightly less simple pictures). Types of data: numbers, booleans, symbols, structures. Type predicates. Using type predicates to define functions that operate on mixed data (unions); the design recipe for such functions.

Week 3: The syntax and semantics of the beginning language. A simple BNF grammar. The substitution rule for function application. The semantics of special forms. Introduction to lists using the cons function for construction. Interpretations of lists using nested boxes, using cons-expressions, and using define-struct. The functions first and rest (¥) for operating on lists. The recursive definition of a list. Functions which process lists. Designing functions for self-referential data definitions (design recipe).

Week 4: Functions which produce lists. Lists which contain structures. A recursive definition of a natural number; processing natural numbers using this definition. Examples involving auxiliary recursive functions. (Language level 2.) The list abbreviation for constructing a list, e.g. (list 1 2 4 5 7). Quoting a list, e.g. '(1 2 4 5 7).

Week 5: More self-referential data definitions, e.g. ancestor family tree, binary search trees. Lists within lists. Expressions as trees. Mutually referential data definitions, e.g. descendant family tree.

Week 6: Designing functions for mutually referential data definitions (design recipe). Development through iterative refinement, e.g. developing a data representation for a directory-structured file system by refinement. Processing two lists simultaneously, e.g. concatenating lists, employee payroll from a list of employee pay rates and another of hours worked. Adapting the design recipe.

Week 7: (Language level 3) Organizing definitions using local (¥). Encapsulating auxiliary functions and definitions using the special form local. Lexical scope and block structure. Finding similarities in functions: functional abstraction. The development of the filter function, which when applied to a list and supplied a relational predicate, extracts a list of those items for which the predicate holds. Similarities in data definitions: data abstraction.

Week 8: The syntax and semantics of functions as values. Contracts for generic functions. Abstracting from examples. When to form an abstraction: to avoid copy-and-modify. Functions that produce functions (using define inside local, and then the equivalent definition using the special form lambda, which is language level 4). Mathematical examples (sequences and series, numerical integration, numerical differentiation).

Week 9: Generative recursion (recursion that does not follow naturally from a data definition), e.g. quicksort. A general recipe for generative recursion. The problem of termination. Examples: fractals, binary search for roots, Newton's method, Gaussian elimination.

Week 10: Backtracking. The cost of computing. Vectors as compared to lists; the cost of backtracking using each. Problems caused by not accumulating information. Accumulator-style functions.

Week 11: (Language level 5) The usefulness of mutation: address books, traffic lights. Assignment to variables using set!, e.g. (define x 3) followed by (set! x (+ x 2)). The use of begin to sequence expressions. Memory and state variables, and design recipes for functions that change memory.

Week 12: State changes from user interactions (e.g. hangman) and from recursion. The vocabulary, grammar, and semantics of Scheme with mutation. Mutation of structures, and design recipes for functions which do this. Mutation of vectors.

Week 13: (one lecture) History of CS, with emphasis on the concepts covered in this course.