Simon Willison’s Weblog

Functional programming

27th September 2002

Functional Programming

These notes cover the first two lectures of Dr Bradford’s Function Programming course.

This course is about the gapp between computer science theory and practise. It consists of a written exam (75%) mainly on Lambda calculus and coursework (35%) written in Lisp.

The three themes of the course are:

• Practise—programming in Lisp
• Theory—a formal theory of computation
• Link—how theory and practise influence each other

There are several styles of programming:

Unstructured

deals with manipulating bytes (e.g Assembler)

Procedural

based around control structures and functions (C-Like, e.g Pascal and Algol)

Object-Oriented

helps represent ideas, for when programs get too big for procedural languages to stay effective (Java, C++, etc)

Declarative

Prolog

Functional

Lisp-like languages, the topic of this course

In functional programming, one of the key concepts is that variables are kept as local as possible. This means that functional code should be easy to quickly understand as sections of the code are self contained.

Links

• Course notes
• Notes on EU Lisp
• Teach Yourself Lisp

Books

• Barendregt “The Lambda Calculus”—a comprehensive guide to Lambda calculus, very hard going
• Hindley and Selddin “Introduction to Combinators and Lambda Calculus”—more readable than the above
• Abelson and Sussman “The Structure and Interpretation of Computer Programs”—good as a general computer science text book, concentrates on Scheme as the example programming language.

Lisp

Lisp means “List Processor”. It was invented in 1956 by John McCarthy with the aim of providing a computerised implementation of Lambda calculus, a formal theory of computation devised in the 1920s. Lambda calculus and Lisp are very heavily related. Lisp was invented as a language for manipulating symbols rather than numbers. A symbol has no meaningful value (unlike numbers which have an inherent meaning).

Lisp is designed to deal with dynamic data structures. Unlike languages such as C and Java, a list in Lisp can have items appended to it and deleted from it throughout the life of the program without any need for memory allocation code. Lisp implements garbage collection and memory management. It is a dynamically efficient language, specially designed to handle dynamic data structures.

Lisp is naturally recursive—many problems in Lisp are solved using recursion, which is also an important aspect of lambda calculus (where many things are defined in terms of themselves).

Lisp has a very simple syntax, and is a very simple language. This was important back in the 50s when super computers were less powerful than a modern singing Christmas card.

In Lisp, the data and the programs look exactly the same. This is another similarity with lambda calculus where no distrinction is made between the two. This also means that a Lisp interpreter can be written in Lisp.

The History of Lisp

Lisp has a long and complicated history, dating back to the first released version (1.0) in 1959. There are hundreds of versions of Lisp now with many small but significant incompatabilities between versions. Some versions were designed for speed while others were designed for semantic purity. Several attempts have been made to standardise Lisp, including Standard Lisp and Common Lisp.

Common Lisp

Took the best bits of many Lisp versions, resulting in a truly huge and complicated language with a lot of confusing features.

Standard Lisp

Took the features that were common to most Lisp implementations, resulting in a much simpler language.

Another important Lisp variant is Scheme, which threw away everything non-essential in the many Lisp variants and resulted in a cut-down language with a very mathematical approach. Scheme is a very pure and interesting language (at least for Computer Scientists) but some people object to Scheme being labelled a Lisp and see it as a new language inspired by Lisp.

EuLisp is a version of Lisp sponsored by the European Commission in the 90s, partly for political reasons (the American’s had Common Lisp) and partly because Common Lisp was a huge sprawling specification while Scheme was so heavily regulated that adding new functions was an almost impossible process. EuLisp was developed (at least in part) by professors now at the University of Bath. It was originally intended to take the position in the market now held by Java but suffered political set backs and never reached its full potential. There is currently a project to create an ISO standardised Lisp version (strongly backed by the Japanese) which has yet to have any impact on the computer science industry.

Conclusion: Lisp is not a single language—it is a whole family of languages.

Lisp Syntax

The basic data structure in Lisp is the list, which is a sequence of objects. Objects can be atoms or other lists. An atom is an object in Lisp that is not a list and is generally indivisible.

(the cat sat (on the) mat)

The above is an example of list syntax in Lisp. The list consists of 5 elements, 4 of which are symbols and one of which is another list itself containing 2 symbols. Symbols are separated by spaces, and lists are deliminated by normal parentheses.

Numbers are not symbols. The following list consists of 3 integers.

(1 3 4)

Lists can be arbitrarily nested. The empty list, () is usually made available by the interpreter in a variable called nil.

Lisp can be compiled and executed in the same way as C, but it can also be used as an interactive interpreter which runs in a read->eval->print loop:

> (+ 2 3)
6
>

To get Lisp to execute a statement, the statement must be entered as a list. The first element in the list is a function (or more commonly a variable containing a function, as in the above example where the + symbol contains the function for addition) while the other elements represent the arguments to that function. The addition function demonstrated above accepts two or more arguments in EuLisp, but in other Lisp variants may only accept exactly two arguments (or even be called something different such as plus).

Generally, a function call looks like this: (function arg arg ....)

There are a very few cases when you will not write Lisp code in the above form—an atom can be written on its own, as can a number (which will stand for its own value). The only time an atom does not stand for itself is when it is a variable.

If a variable has no value and you ask for one you will get an error. In Lisp, even errors are objects (data structures) that can be manipulated.

Essentially, the only difference between data and a Lisp program is what you do with it.

There are several special Lisp forms. The most important is quote, which allows a Lisp programmer to specify that a list is meant to be used as data rather than executed as code. The quote function returns its arguments unchanged and unevaluated:

> (quote (+ 1 2))
(+ 1 2)
>

A shorthand way of writing the above statement is to use a single apostrophe: '(+ 1 2) which is the exact equivalent of the above statement.