A Little History

Lisp is very old language, second only to Fortran in the family tree of high level languages. In the late 1950s John McCarthy described a language, named "Lisp 1," that had all the important parts of the current language, in particular the lists, and atoms. He was trying to develop a language that would adequately express the lambda-calculus of Alonzo Church that arose in the 1930s.

McCarthy wrote a paper describing a Lisp function that would interpret any Lisp function, including itself. This function, eval, is like a universal Turing machine. The Lisp language he described was a universal language that could implement all other languages. In fact, this latter is truer than you might at first think - many modern top end compilers are written in languages which, if not actually Lisp, at least are morally Lisp. The first Fortran compiler for UNIX, f77, was written in Lisp. Those of you who use GNUemacs may be interested to know that it is written mainly in Lisp.

Lisp never looked back. From Lisp 1 there spawned dozens of Lisps, each exploring its own niche of computer science, each choosing a set of ideas to develop, each picking a new set of names for the basic functions. Lisp is not a language, it is a family of languages: a family tree can be constructed showing the major paths of development. Unfortunately, this profusion of dialects, like the Tower of Babel, has lead to a state where any particular Lisp program may or may not run on a particular implementation of Lisp. Or if your program does run, it may do something entirely contrary to your expectation.

This may seem a disaster to a Fortran programmer, who wants her program to run on any compiler on any machine. But the diversity has led to important developments and cross-fertilization of ideas, as perhaps, objects from one branch are merged with logic programming from another to confront pure functional forms from a third.

There are a few things common to all Lisps: lists and atoms, the function cons to construct lists, and the functions car and cdr to take them apart.

McCarthy implemented his Lisp on an IBM 704 whose instruction format had four sections named cpr (contents of the prefix register), ctr (contents of the tag register), car (contents of the address register), cdr (contents of the decrement register). The way he arranged things was when he referred to a list, the car would be in the address register, the cdr in the decrement register...and the names just stuck.

The Ball of Mud

A poetic reason for the divergence of Lisp was given by Moses: A language such as APL is like a diamond. It is perfectly symmetric, and shines brightly. However, if you wish to add a new feature to the language, the symmetry is smashed, and the diamond cracks and shatters.

Lisp, on the other hand, is a ball of mud. Essentially shapeless, you can easily add new extensions and ideas, and all you get is a larger ball of mud ready and able to accept more and more. Lisp is infinitely extensible: you can add new functions that have exactly the same importance to the system as the built-in commands, or even redefine the built-in commands. You can, if you feel that way inclined, redefine the whole syntax. Imagine the possibilities if C allowed you to redefine the while loop, or Fortran let you introduce exactly that form of DO loop that you required for your application.

Over the years many important new ideas have first been tried out using Lisp. Optimizing compilers were first written in Lisp. The idea of tail recursion removal was implemented in Lisp compilers as early as 1962. Only since the late '80 have other languages caught on: C compilers are beginning to spot the advantages of tail recursion. Object oriented systems and object oriented graphics were first developed using Lisp. Similarly were pure functional ideas, and logic programming and rewrite systems. Other languages have subsequently been conceived (Prolog, ML, C++) that are based on these ideas, but they were all prototyped in Lisp.

Lisp typically runs as an interpreter, using a read-eval-print loop. This loop sits and waits for input, reads it, evaluates the expression it has read, and then prints the result. (As an aside, the read-eval-print loop is often written in Lisp, and could be redefined into something more exotic, such as a control program for some piece of machinery.) This interactive use is one of the reasons Lisp is so important as a prototyping tool: a function can be tried, and altered, and then re-tried as often as you wish, and function call always refers to the latest definition of a function. Thus if you define foo, and then bar which calls foo, you can define bar in the knowledge that foo will use your new definition. (This is somewhat like the language Forth (which was developed using the idea from Lisp, of course).)

Julian Padget, jap@maths.bath.ac.uk, this version October 19, 1994