The following example is a LISP program that defines three functions union, intersection, and member, and then applies these functions to some test cases. The functions union and intersection are to be applied to "sets," each set being represented by a list of atomic symbols. The functions are defined as follows. Note that they are all recursive, and both union and intersection make use of member.
member[a;x] = [null[x]
F;eq|a;car(x]]
T;
T
member [a;cdr[x]]]
union[x;y] = [null[x]
y;member[car[x];y]
union
[cdr[x];y];T
cons[car[x];union[cdr[x];y]]]
intersection[x;y] = [null[x]
NIL; member[car[x];y]
cons[car[x];intersection[cdr[x];y]];
T
intersection[cdr[x];y]]
To define these functions, we use the pseudo-function define. The program looks like this:
DEFINE ((
(MEMBER (LAMBDA (A X) (COND ((NULL X) F)
( (EQ A (CAR X) ) T) (T (MEMBER A (CDR X))) )))
(UNION (LAMBDA (X Y) (COND ((NULL X) Y) ((MEMBER
(CAR X) Y) (UNION (CDR X) Y)) (T (CONS (CAR X)
(UNION (CDR X) Y))) )))
(INTERSECTION (LAMBDA (X Y) (COND ((NULL X) NIL)
( (MEMBER (CAR X) Y) (CONS (CAR X) (INTERSECTION
(CDR X) Y))) (T (INTERSECTION (CDR X) Y)) )))
))
INTERSECTION ((A1 A2 A3) (Al A3 A5))
UNION ((X Y Z) (U V W X))
This program contains three distinct functions for the LISP interpreter. The first function is the pseudo-function define. A pseudo-function is a function that is executed for its effect on the system in core memory, as well as for its value. define causes these functions to be defined and available within the system. Its value is a list of the functions defined, in this case (MEMBER UNION INTERSECTION).
The value of the second function is (Al A3). The value of the third function is (Y Z U V W X). An inspection of the way in which the recursion is carried out will show why the "elements" of the "set" appear in just this order.
Following are some elementary rules for writing LISP 1.5 programs.
1. A program for execution in LISP consists of a sequence of doublets. The first list or atomic symbol of each doublet is interpreted as a function. The second is a list of arguments for the function. They are evaluated by evalquote, and the value is printed.
2. There is no particular card format for writing LISP. Columns 1-72 of any number of cards may be used. Card boundaries are ignored. The format of this program, including indentation, was chosen merely for ease of reading.
3. A comma is the equivalent of a blank. Any number of blanks and/or commas occur at any point in a program except in the middle of an atomic symbol.
4. Do not use the forms (QUOTE T), (QUOTE F), and (QUOTE NIL). Use T, F, and NIL instead.
5. Atomic symbols should begin with alphabetical characters to distinguish them from numbers.
6. Dot notation may be used in LISP 1.5. Any number of blanks before or after the dot will be ignored.
7. Dotted pairs may occur as elements of a list, and lists may occur as elements of dotted pairs. For example,
((A . B) X (C . (E FG)))
is a valid S-expression. It could also be written
((A . B) . (X . ((C . (E . (F . (G . NIL)))) . NIL))) or
((A . B) X (C E F G))
8. A form of the type (A B C . D) is an abbreviation for (A . (B . (C . D))). Any other mixing of commas (spaces) and dots on the same level is an error, e.g (A . B C).
9. A selection of basic functions is provided with the LISP system Other functions may be introduced by the programmer. The order in which functions are introduced is not significant. Any function may make use of any other function.