Computer LaboratoryComputer Science Syllabus - Introduction to Functional Programming

Introduction to Functional Programming
Next: Numerical Analysis II Up: Lent Term 2006: Part Previous: Digital Communication I   Contents

Introduction to Functional Programming

Lecturer: Dr Marcelo Fiore

No. of lectures: 12

Aims

The general aim of the course is to introduce the functional style of programming using the programming language ML. Specifically, the course will introduce, illustrate, and examine the principles of functional programming using key features of ML: structured datatypes, higher-order functions, and type inference. Throughout the course applications will be demonstrated via case studies.

Lectures

• Overview and motivation. Imperative commands versus functional expressions. Evaluation strategies: call-by-value, call-by-name, call-by-need. Lazy evaluation.

• Introduction to Standard ML. Basic types: integers, reals, strings, Booleans. Structured types: tuples, lists, functions.

• Lists and recursion. Functions on lists: length, reverse, append. Recursion versus iteration. Utilities.

• Basic sorting. Equality types. Sorting lists using quicksort and merge sort.

• Datatypes. Enumerated types. Pattern matching. Raising and handling exceptions. Binary trees: computing size and depth, traversing, balancing. Multi-branching trees, S-expressions.

• Further datatypes. Binary search trees. Functional arrays. Propositional logic: negation normal form, conjunctive normal form.

• Higher-order functions. Higher-order functions. Lambda notation. Curried functions. Functionals: list summation, map, matrix multiplication, list folding.

• Higher-order functions continued. Unbounded sequences. Consuming and joining sequences. Functionals on sequences. Numerical computations. Searching infinite trees.

• Program specification and verification. Testing versus program verification. Formal versus rigorous proof. Proofs of ML programs. Mathematical and course-of-values induction.

• Induction. Structural induction on lists. Proofs of appending and reversing. Structural induction on trees. Specification of sorting.

• Types. ML type inference. Polymorphism: types and type schemes. Axioms and inference rules.

• Case study: a functional parser. Parsing functionals: alternation, sequencing, transformation, repetition. Example: propositional logic.

Objectives

At the end of the course students should

• be familiar with key concepts of programming in a functional style

• be able to develop software in ML in a competent manner

• understand how to use type-checking for clearer and verifiable programs

* Paulson, L.C. (1996). ML for the working programmer. Cambridge University Press (2nd ed.).
Okasaki, C. (1998). Purely functional data structures. Cambridge University Press.

Other useful references:

Backus, J. (1978). Can programming be liberated from the von Neumann style? A functional style and its algebra of programs. Communications of the ACM, vol. 21, pp. 613-641.
Landin, P.J. (1966). The next 700 programming languages. Communications of the ACM, vol. 9, pp. 157-166.

Next: Numerical Analysis II Up: Lent Term 2006: Part Previous: Digital Communication I   Contents
Christine Northeast
Sun Sep 11 15:46:50 BST 2005

 © 2005 University of Cambridge Computer Laboratory Please send any comments to pagemaster@cl.cam.ac.uk Page last updated on 11-Sep-2005 at 15:57 by Christine Northeast