Scheme and Functional Programming

December 5, 2000

In functional programming, you get work done by evaluating expressions that return results. Functional programming is notable for what is missing. There is no assignment: each evaluation returns a new object, you never change the value of an existing object. There is (usually) no sequential top-to-bottom or right-to-left evaluation order: the order in which subexpressions are evaluated does not matter. Despite these apparent limitations, functional programming is surprisingly powerful. The limitations make make certain programming techniques possible, prevent whole classes of errors, and can make programs easy to analyze.

Notable characteristics of functional programming in Scheme are:

• Simple syntax based on lists and prefix operators
• Programs are composed from self-contained procedures. The behavior of a purely functional procedure depends only on it arguments. There is no dependence on some surrounding environment of global variables or any history of past actions. This means that each such procedure can be completely understood and thoroughly tested independently of all the others.
• Interactive interpreter including a trace facility makes it easy to experiment and create programs piece-by-piece.
• Higher-order functions that generalize patterns with procedure arguments are used, instead of code that does one specific task.
• Lambda expressions can define new functions where needed and match already defined functions to a particular context.
• Recursive problem solving: break the problem into a base case that can be solved easily, and a sub-problem that has the same structure as the original, but is smaller. Recursion also achieves something like scratch memory: the stack of pending recursive calls can store intermediate results temporarily. Recursion can also be used for repetition.
• A single construct -- the list -- represents many data structures including sequences, tables and dictionaries, trees, networks etc.
• List manipulation based on a constructor function cons and two selectors car (first element) and cdr (rest of the list).
• Built-in input/output procedures can read and write entire lists (that is, complete data structures) not just characters, strings and lines.
• Lists can also represent programs.
• The language interpreter is an ordinary procedure that can be called from a user's program. The interpreter is a meta-circular definition of the language.

Most other programming languages provide some of these features, but in Scheme (and other Lisp dialects) they are particularly convenient and work together most powerfully.

It is also possible to program write non-functional (not dysfunctional!) programs in Scheme. Scheme provides input-output (side effects), assignment (set! etc.), sequence (begin etc.), and even an iteration construct (do).