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.