 |
School of Computer Science
Computer Science COMP 199 (Winter term)
Excursions in Computing Science
Notes on LISP.
Prepared for COMP 302 (SOCS, McGill)
Copyright (c) T. H. Merrett, 1989
LISP illustrates at least three major concepts in programming languages, which
is remarkable for such an early language. First, its exhaustive exploitation
of the computable expression, even to the point of function-valued
expressions: this results from basing LISP in the mathematics of recursive
function theory, which requires these ideas. Second, the notion of a single,
high-level data structure which can represent both data and programs. This
data structure is recursively defined, and, consequently, the programs that
use the data structure are usually recursive. Third, programs and data have
the same form, so that programs themselves can be manipulated, altered and
constructed.
- We will start our discussion with recursive data structures. The fundamental
data structure of LISP is the ordered binary tree, defined
An O2TREE is an ATOM or ( O2TREE . O2TREE )
The word, "ordered", means that we can distinguish the left subtree from the
right subtree. These are just ordered binary trees themselves, hence the
recursion. Since no data structure on a computer can go on forever, the ATOM
is provided for the leaves of the tree. The above representation is called
"dot notation", and the O2TREE before the dot is the left subtree, while the
O2TREE after the dot is the right subtree. Here are some examples, with the
capital letters representing ATOMS.
NIL the empty tree
(A . B) complete tree of height 1
((A . B) . (C . D)) complete tree of height 2
(A . (B . NIL)) incomplete tree of height 2
- Two basic operations are: car, which returns the first component of its
argument; and cdr, which returns the second component. From these can be built
composite functions, e.g., caar[]=car[car[]], cddr[]=cdr[cdr[]],
cadr[]=car[cdr[]], cdadr[]=cdr[car[cdr[]]], etc. (You might wonder where these
strange names came from. They abbreviate phrases which refer to the IBM 7094,
on which LISP was first implemented: "Contents of Address Register" and
Contents of Decrement Register". They have been retained probably because they
give such convenient names for their compositions.)
car[(A . B)] = A
car[((A . B) . C)] = (A . B)
cdr[(A . B)] = B
cdr[((A . B) . C)] = C
cadr[(A . (B . C))] = car[cdr[(A . (B . C))]] = B
A third basic operation is cons, which combines its two arguments into a
single tree. This operation is defined as the inverse of car and cdr together:
car[cons[t1;t2]] = t1
cdr[cons[t1;t2]] = t2
Here are some examples.
cons[A;B] = (A . B)
cons[(A . B);C] = ((A . B) . C)
The three other basic functions are null, equal and atom. These are Boolean
functions, and return the values NIL, for false, and T for true.