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.