LISP

Copyright 1995, 1999 by Donald R. Tveter
http://www.dontveter.com drt@christianliving.net, don@dontveter.com
Commercial Use Prohibited

Chapter 13
LISP

13.1  Basic LISP Concepts and Functions

LISP is short for ``LISt Processing language" and it is one of the earliest programming languages developed. It was originally designed merely as a useful notation by McCarthy but one of his students realized it could be useful as a programming language and went on to produce the first LISP interpreter. There are a great many versions of LISP available and all these LISPs have a great deal in common, yet there are many annoying variations. The examples we will look at here will be from versions 1.4 and 1.6 of XLISP. There is a whole series of XLISP systems produced by David Betz that he has put in the public domain. The more recent versions of XLISP are fairly close to a recent standard, called Common LISP. Like PROLOG, LISP is normally run in an interactive mode. The user types in expressions to be evaluated and the interpreter prints out the results. LISP does not have the pattern matching capability of PROLOG built into it so in section 13.5 we will show a simple pattern matching function that matches patterns and instantiates variables somewhat like PROLOG.

13.1.1  Symbolic Expressions

The LISP language consists of Symbolic-expressions , or S-expressions for short. The basic building block is an atom . Atoms consist of a string of letters and digits and most special characters except for the following ones:
( ) ` , . " ;
Some possible atoms are:
plus
+
x1
1x
*
nil

pretty-print
St_Louis
?var1
97
Some LISPs allow character strings in addition to atoms. Character strings are enclosed in double quotation marks, as in:
"hello world"
More complex S-expressions are built up by dotting together two atoms or two S-expressions to give a dotted pair. For instance, if we dot together the atoms, a and b, this becomes the dotted pair:
(a . b)
This S-expression is stored internally as a binary tree with a on the left and b on the right. This tree structure is shown on the left in figure 13.1. Still more complex S-expressions can be formed by dotting together more S-expressions. For instance, we could dot together (a . b) with (c . d) giving ((a . b) . (c . d)). This tree is shown on the right in figure 13.1. For obvious reasons, this type of notation is referred to as ``dotted pair" notation.

These general sorts of S-expressions are not used very often, instead, there is a special sort of S-expression called a list that is used almost all the time. A list containing the atoms, a and b is written as:
(a b)
Internally, this too, is a binary tree and its tree diagram is shown on the left in figure 13.2. Notice that on the bottom right of this tree there is a special atom, called nil , or the empty list (that can also be written as ``()"). Obviously the list, (a b) can also be written out in dotted pair notation as:
(a . (b . nil))
LISP will print out trees in list notation whenever possible. At the right in figure 13.2 is the expression, ((a b) (c d)), a list containing lists.

This short description of S-expressions actually describes the whole syntax of the language. Everything in LISP consists of S-expressions, both the data and the program. For example, here is a simple function designed to find n!:

   (defun fact (n)
          (cond ((equal n 0) 1)
                (t (* n (fact (- n 1))))))
The need to use lots of parentheses in forming functions should be readily apparent. LISP was not designed to fit existing human pattern recognition templates so it usually takes a while for people to build up an inventory of pattern recognition templates that makes it possible to easily write and understand LISP functions. One consequence of this poor design is that users often manage to forget one or more parentheses when writing down or typing in a LISP function1. Some LISP systems contain special editors that aid in forming correct expressions. Some editors have a LISP mode that can be helpful in matching parentheses up correctly. It is virtually impossible to work with LISP unless the system has some ``pretty-printing" capability that will neatly indent expressions to make them readable.

13.1.2  Built-In Functions

We will now start looking at some of the simplest built-in functions. Some of the easiest functions to describe are the ones that do arithmetic. For instance, to add together two numbers such as 1 and 2, type in:

   > (+ 1 2)
   3
In this sequence, > represents a prompt from the LISP interpreter. The interpreter immediately prints the answer 3 just below. The LISP interpreter regards the first item in a list as a function to evaluate and the remaining items are arguments that are usually evaluated2 before they are passed on to the function. When the arguments are numbers, the numbers naturally evaluate to themselves. The + function will actually allow an unlimited number of numbers to be added together in one step:
   > (+ 1 2 3 4 5)
   15
Also an unlimited number of numbers can be multiplied together using the * function:
   > (* 3 4 2)
   24
For - and /, only two operands are allowed:
   > (/ 27 9)
   3

   > (- 88 100)
   -12
The following call asks for the absolute value of -88:
   > (abs -88)
   88
There are usually many other functions available in most versions of LISP to calculate special functions such as sin, cos, tan, log and so on.

LISP can also handle more complex expressions as well:

   > (+ (* 2 3) (* 2 4))
   14

13.1.3  Variables

Of course, LISP has variables that can be assigned values and LISP has several functions to do this. The most commonly used one is setq. Setq evaluates its second argument but not its first so that it behaves just like an assignment statement in a normal language, like Pascal. Below are some examples of ``assignment statements" in LISP:

   > (setq a 1)
   1
   > (setq b 2)
   2
   > (setq c (+ a b))
   3
Notice that as a side-effect, LISP also prints out the value that was stored away. The last assignment statement gave c the value, 3. We can also check this out by typing in, simply, c and LISP will go look up the value:
   > c
   3
Variables in LISP are created whenever they are needed and they become global variables, so the three assignments above created the global variables a, b and c as well as gave them values. Variables can also be declared inside functions and these variables vanish when the function call ends. Depending on the exact variety of LISP, it may or may not be possible to reference them from other functions. Any variable can take on any sort of value, an atom (numeric or symbolic), a dotted pair or a list and the LISP interpreter automatically keeps track of the type of each variable's value.

In the above examples all the variables were being assigned numeric values but they can also be assigned the values of S-expressions. For instance, we may want to give the atom d, the value of another atom, x:

   > (setq d x)
LISP looks up the value of x and places it in the location, d. This corresponds nicely to the Pascal statement:
   d := x
Now, in Pascal, if you wrote:
   d := 'x',
Pascal would not attempt to look up the value of x. Pascal sees this as meaning the character x itself. The same situation in LISP is the following:
   > (setq d 'x)
   x
In this case, the quote mark in front of the x tells LISP not to try to look up the value of x, but merely to take the symbol, x and put it into the location, d. So, if we ask LISP what d is, we get:
   > d
   x

The other assignment function LISP has is called set and it evaluates both its first and second arguments, so assuming d now has the value x, the following statement will set x to 99:

   > (set d 99)
   99
Thus, if we now look at the value of x, we find that it is 99:
   > x
   99
Set therefore allows an extra level of generality that is not found in most conventional languages: the location where a value goes can itself be a variable.

If we want to let d have the symbolic value consisting of the list, (john loves mary), we can use set or setq as follows:

   > (setq d '(john loves mary))
   (john loves mary)
   > (set 'd '(john loves mary))
   (john loves mary)
Here, the quote mark in front of the list, (john loves mary) prevents LISP from trying to evaluate the list. Without this quote mark, LISP would think of john as a function to evaluate and loves and mary as arguments that needed to be evaluated and then passed on to the function, john.

This notation using a single quote mark in front of something is actually a shorthand notation for the function, quote. Quote is a function that takes in its argument and sends back as its answer, the same value that went into it. The above examples using quote could have been written out in this long-hand fashion as follows:

   (setq d (quote x))
   (set (quote d) (quote x))
   (setq d (quote (john loves mary)))
   (set (quote d) (quote (john loves mary)))

Another useful function, eval, can be used to evaluate its argument further. For instance we will give the atom, x, the value y and give y the value z:

   > (setq x 'y)
   y
   > (setq y 'z)
   z
If we ask for the value of x, we get:
   > x
   y
If we ask for (eval x) we get:
   > (eval x)
   z

13.1.4  Manipulating S-expressions

We now want to look at another set of basic LISP function, the ones that make it possible to put together and tear apart S-expressions. We start first with cons, short for listcons tructor. In this example we can cons together two atoms a and b:

   > (cons a b)
   (a . b)
Obviously, cons forms a dotted pair with its arguments. The first argument of the cons ends up as the item on the left and the second arguments ends up as the item on the right. If we cons a and nil together we get:
   > (cons a nil)
   (a)
Likewise, if we have a list, (b c) and we want to produce a list with the atom a on the front of (b c) we type in:
   > (cons 'a '(b c))
   (a b c)
Here are a couple of more examples of cons and its effects:
   > (cons '(a b c) '(x y z))
   ((a b c) x y z)
   > (setq list1 '(x y z))
   (x y z)
   > (cons 'a list1)
   (a x y z)
It is important to notice that in the last example, list1 was not changed when the atom, a, was consed with list1. List1 is still just the list, (x y z). Quite often people see an expression like:
   (cons 'a list1)
and expect that list1 is changed but to actually change the value of list1 would require the statement:
   > (setq list1 (cons 'a list1))

A second important means of constructing S-expressions is to use append to run two lists together as in the following examples:

   > (append '(a b c) '(x y z))
   (a b c x y z)
   > (append '(a b c) '(x y z) '(1 2 3))
   (a b c x y z 1 2 3)
Some LISPs allow append to have an arbitrary number of arguments while other LISPs limit the number of arguments to only two.

Another useful function is list that takes its arguments and puts them in a list. Here are two examples:

   > (list 'x)
   (x)
   > (list 'x (cons 'a (list 'b)))
   (x (a b))

The functions that tear lists apart have very unfortunate names, they are: car, that returns the first item in the list and cdr (pronounced could-er) that returns all but the first item in the list. These names come from the names of registers on one of the first computers to run LISP and LISPites have never felt a real need to replace them with sensible names like first and rest although some newer LISPs also have the functions first and rest in addition to car and cdr. Some examples of using car are the following:

   > (car '(a b c))
   a
   > (car '((a b) (c d) (e f)))
   (a b)
   > (car '((a b) c d))
   (a b)
   > (car '((a b c d (e f))))
   (a b c d (e f))

Needless to say, trying to take the car of an atom is likely to provoke an error or produce some strange result. Exactly what will happen varies from LISP to LISP. Some examples of the use of cdr are these:

   > (cdr '(a b c))
   (b c)
   > (cdr '((a b) (c d) (e f)))
   ((c d) (e f))
   > (cdr '((a b) c d)))
   (c d)
   > (cdr '((a b c d (e f))))
   nil
Of course, the cdr of an atom is likely to produce an error or a strange result as well.

Some LISPs have a last function last that will give the last item of a list in a list or the last atom in a dotted pair:

   > (last '(a b c))
   (c)
   > (last '(a . (b . c)))
   c

To get to an item deeper within a tree, calls to car and cdr can naturally be nested, as in these calls:

   > (car (cdr '(a b c)))
   b
   > (car (cdr '(a (b c) d)))
   (b c)
   > (car (cdr '((a b) c d)))
   c
   > (car (car '((a b) c d)))
   a
   > (cdr (cdr '((a b) c d)))
   (d)
Reaching items within a list in the above fashion is awkward so LISPs have functions that combine the actions of cars and cdrs in just one function. For instance, the sequence, (car (cdr x)) can be replaced by (cadr x) and (cdr (car x)) can be replaced by (cdar x). The names are derived by taking the long version of the sequence of operations and extracting, from left to right, the middle letter and then putting a ``c" in front and an ``r" on the end. Here are some examples of these compound functions:
   > (cadr '(a b c))
   b
   > (cadr '(a (b c) d))
   (b c)
   > (cdar '(((a b)(c d)) x y z))
   ((c d))
   > (caar '((a b) c d))
   a
   > (cddr '((a b) c d))
   (d)
Some LISPs carry this out to 3 or 4 cars and cdrs but even this organization can be awkward. Newer LISPs often have the nth function that returns the nth item in a list, counting the first item as item 0, as for example:

   > (nth 3 '(a b c d e f))
   d
   > (nth 0 '(a b c))
   a
   > (nth 3 '(a b c))
   nil
Asking for an item beyond the end of the list returns nil.

13.1.5  Defining Functions

The last basic function we will look at in this section is the LISP function to define functions. In most LISPs this function is called defun. Defun expects the first argument to be the name of the function and the second argument to be the list of parameters, which must be the empty list (nil) for functions with no arguments. The parameters are all value parameters. All the remaining S-expressions in the defun function call are statements that LISP evaluates when the function is called. The value calculated for the last statement in the function is the value that the function returns. Values cannot be returned through the arguments of the function but global variables can be set within a function. Here is the definition of a simple function, plus-ends, that adds together the first and last numbers in a list:

   (defun plus-ends (x)
      (+ (car x) (car (last x))))
The function is called like any other LISP function as in:
   > (plus-ends '(1 2 3 4 5 6 7))
   8

There are many other points regarding functions and defining and using variables in functions that are quite important to know, but these fine points of functions and variables will be considered in a later section. We simply defined defun here so that some simple functions could be defined in the next few sections.

LISP13.2 Control Functions

13.2  Control Functions

In this section we will look at a few of the most useful and widely used functions for controlling execution but first we need to look at functions that test for various conditions. In doing tests, LISP functions will return the built-in constant, nil (or the empty list, ``()") for false and the built-in constant, t or some non-nil value for true.

13.2.1  Predicates

Predicates are functions that return true or false (t or nil). Many, but not all LISP functions that are predicates have names ending in ``p". The first predicate we look at is called numberp which tests to see if its argument is a number. Here are some examples of the use of numberp:

   > (numberp 9)
   t
   > (numberp 'x)
   nil
   > (numberp '(1 2 3))
   nil
The predicate, atom, tests for atoms:
   > (atom 1)
   t
   > (atom 'x)
   t
   > (atom '(+ x y))
   nil
The predicate, listp (not to be confused with list), tests for non-atoms:
   > (listp 1)
   nil
   > (listp 'x)
   nil
   > (listp '(+ x y))
   t
   > (listp (cons 'a 'b))
   t
The function, boundp, checks to see if its argument has a value. Suppose, x does, but y does not. Here are some examples of boundp:
   > (setq x 1)
   1
   > (boundp 'x)
   t
   > (boundp 'y)
   nil

The function, =, tests for the equality of numbers but note that it does NOT test symbolic expressions correctly:

   > (= 1 2)
   nil
   > (= 2 (+ 1 1))
   t
   > (= '(b c) '(b c))
   nil
The function, /=, tests for inequality of numbers but not lists and non-numeric atoms:
   > (/= 1 2)
   t
   > (/= '(b c) '(b c))
   t
In addition, the functions, > , > = , < and < = can be used to test relationships between numbers:
   > (> 8 9)
   nil
   > (< 8 9)
   t
   > (>= 9 8)
   t
   > (<= 1 2)
   t
The function, equal, will correctly test for equality of numbers, lists and symbolic atoms:
   > (equal 1 1)
   t
   > (equal 1 2)
   nil
   > (equal '(b c) '(b c))
   t
   > (equal 'a (car '(a b c)))
   t
The function, null, is the same as the function, not. They both invert true/false values:
   > (null (= 1 2))
   t
   > (not (= 1 2))
   t
   > (null (equal 'a (car '(a b c))))
   nil

13.2.2  and and or

LISP has functions to or and and together results. To show some examples we will first assign x, y and z some values:

   > (setq x 1)
   1
   > (setq y 2)
   2
   > (setq z 3)
   3
   > (or (= x 1) (> z 0))
   t
   > (and(= x 1) (> z 0))
   t
   (and (= x 1) (= y 2) (< z 0))
   nil
   > (or (= x 2) (= y 14) (> z 0))
   t
The and and or functions will take an arbitrary number of arguments. The or function checks the conditions in order until it finds one condition that is true. If it finds one, it will not go on to check any other conditions there may be and it returns as its value this non-nil value that it found. If none of its arguments are non-nil, or returns nil. The and function checks its arguments until the function succeeds by finding that all its arguments are non-nil, in which case it returns the value of its last argument, or if it finds an argument that is nil, it returns nil without checking any more arguments. In the above examples, we have been checking numerical relations, but remember that LISP's definitions for true and false, are non-nil and nil, so the following tests are valid as well:
   > (and 'hello 'world)
   world
   > (and '(hello world))
   (hello world)
   > (and nil '(hello world))
   nil
   > (or 'hello 'world)
   hello
   > (or nil '(+ x y) nil)
   (+ x y)

13.2.3  cond

The original and most common conditional function in LISP is the cond function. Its basic form is the following:

   (cond ( <test 1>      <answer 1> )
         ( <test 2>      <answer 2> )
            .
            .
            .
         ( <test n>      <answer n> ))
Each argument of cond consists of a list where the first item in the list is a test expression to evaluate and the second item is an answer expression. Cond starts looking at its arguments one by one to try to find a test that comes up non-nil and if it finds one it evaluates the corresponding answer and returns that value for the cond. In case it doesn't find a non-nil test expression, the cond returns nil. For an example of cond we will first set a variable, x, to be the list, (a b c). Then we type in a cond statement that looks for the atom b in all three positions in the list. If it finds b in the first position, it will return 1, otherwise if it finds b in the second position, it will return 2, otherwise if it finds c in the third position it returns 3 otherwise it returns nil. Here is the sequence given to LISP together with its responses:
   > (setq x '(a b c))
   (a b c)
   > (cond ((equal 'b (car x)) 1)
   >       ((equal 'b (cadr x)) 2)
   >       ((equal 'b (caddr x)) 3)
   >       (t nil))
   2
One extra item of note is the use of the built-in constant, t, that is always true, in the final test. The use of t as a test condition amounts to creating an ``otherwise" or ``default" clause, since t is always true.

Older LISPs only allow one S-expression for the answer portion but many newer LISPs allow more than one S-expression to be evaluated. In this case, the final S-expression becomes the value of the cond. Here is an example of this newer type of cond:

   (cond ((equal x y) (print x) (+ x y))
         (t (print x) (print y) (- x y)))
In this cond, if x equals y then x is printed and the sum, (+ x y) is returned, otherwise x and y are printed and the difference, (- x y) is calculated and becomes the value of the cond.

All LISPs will allow the test condition, if true, to be the value of the cond if there is no answer portion, as in:

   > (cond ((cons 'a 'b)))
   (a . b)

13.2.4  Some Simple Examples That Use Cond

For another example of the use of cond, here is the well known factorial function:

   (defun fact (n)                     ; function definition
      (cond ((equal n 0) 1)            ; if n = 0 return 1
            (t (* n (fact (- n 1)))))) ; otherwise recurse
Little needs to be said about this solution. If n is equal to 0 then the answer is 1 and 1 becomes the value of the cond. Since the cond is the last expression in the function definition, the function call returns this value. If n is not equal to 0, the cond will make a recursive call to fact. Comments in LISP begin with a ``;" and continue to the end of the line. One problem with this notation for comments is that the comments get thrown away when a file of functions gets read in, so if you list a function on the screen, to find out how it works you won't get the comments. It is not hard to define a comment function using defun (or maybe better yet a macro, using defmacro) that does nothing but give a comment, then the comments won't be lost when the function is read in.

In section 4.2 we gave definitions for a function member, that checks to see if a symbol is in a list. Most LISPs have the member function built-in, but here is a home-made definition of member, which we will call, mem, instead:

   (defun mem (x l)
      (cond ((null l) nil)
            ((equal x (car l)) t)
            (t (mem x (cdr l)))))
Again the first argument, x, is the item to look for and l is the list to look in. Here are some calls to mem:
   > (mem 'b '(a b c))
   t
   > (mem 'd '(a b c))
   nil
This LISP version of member is different from the PROLOG version in that it must start off with an explicit test as to whether or not the list to search is empty. If it is not empty, you can go on to do the other tests. If it is empty, you must explicitly return nil. So there are a couple of steps here that have to be explicitly written out, unlike PROLOG where the steps come automatically. The second test covers the case where the first value in l is equal to x. If this case is true, return t. The otherwise clause covers the case where x is not the first number in the list. In this last case, the answer to send back is then the answer as to whether or not x is in the cdr of l.

Here is the LISP version of the PROLOG predicate, pos, also defined in section 4.2 that returns a list of positive numbers in a list, l:

   (defun pos (l)
      (cond ((null l) nil)
            ((> (car l) 0) (cons (car l) (pos (cdr l))))
            (t (pos (cdr l)))))
A possible call would be:
   > (pos '(-1 44 97 -300 10))
   (44 97 10)
This LISP version is even closer to the PROLOG version. The first test returns nil if the list is empty. The second test checks to see if the first number, (car l) is greater than zero. If it is, then the result to send back is the number consed onto whatever positive numbers there are in the rest of the list. These other numbers are found by calling pos with the cdr of l. The otherwise clause covers the case where the first number is not positive. It says that the list of positive numbers in the list is the list of positive numbers in the rest of the list.

13.2.5  Iteration

We are now going to go and look at functions that can be used to do iteration and the problem of making a list of all the positive numbers in a given list will be used to illustrate the methods. The first function to allow looping in LISP was the prog (short for program) function and it allows for labels and gotos within the function. Of course, it dates back to the time before people realized that goto statements were the work of the Devil. The following is an outline of a prog function:

   (prog (<a list of variables>)
         <function call or label>
         <function call or label>
            .
            .
            .
         <function call or label>)
The first argument is a list of variables that the prog will use. If there are no variables needed, this first argument should be nil. Any variables that are listed are initialized to nil but newer LISPs allow variables to be initialized to specific values. These variables are destroyed when the prog finishes. Here is an example of a version of pos, called iter-pos-prog, that uses a prog with a label and goto statement:
   (defun iter-pos-prog (l)
      (prog (first positives)
            loop
            (cond ((null l) (return positives)))
            (setq first (car l))
            (cond ((> first 0)
                   (setq positives (cons first positives))))
            (setq l (cdr l))
            (go loop)))
A call to this function and its result is:
   > (iter-pos-prog '(-1 44 97 -300 10))
   (10 97 44)
As to how the prog works, when the prog is entered, the variables, first and positives are created and set to nil. LISP passes right by the identifier, loop, that is being used as a label. This is just an arbitrary name, but it is a commonly used one for labels within a prog. Following the label, the cond checks to see if the list of numbers to check, l, is empty. If it is, then the corresponding return function evaluates its argument and lets that be the value of the prog. If the list isn't empty, then we let the variable, first, be the first item in the list. The following call to cond checks to see if first is greater than 0. If it is, positives is changed to a new value with the value of first consed onto the current list of positives. Then this first item is removed from the list, l, making the list shorter. The go function sends the interpreter to the statement after the label, loop.

13.2.6  mapcar

The above way of looping is really quite awkward and prog should be avoided except when it is absolutely necessary. LISP provides a neater way of performing the same operation on a list of numbers, using the mapcar function. Mapcar's first argument is the function to compute and its second argument is the list of items to work on. Mapcar takes the first item from the list, computes the function value and places this new value at the start of an answer list. Then mapcar moves on to compute the function value of the second item in the list. This result is added to the end of the answer list, and so on. Here is a LISP function that uses mapcar to do the pos problem:

   (defun iter-pos-mapcar (l)
      (mapcar 'positive l))
Of course, we still need to define the function, positive:
   (defun positive (x)
      (cond ((> x 0) x)
            (t nil)))
Here is a sample call of iter-pos-mapcar:
   > (iter-pos-mapcar '(-1 44 97 -300 10))
   (nil 44 97 nil 10)
Unfortunately, the list contains the atom nil for negative numbers, so this is not yet quite right, however it is quite easy to write another function that will strain out the nils. Some LISPs have a function, mapc that works just like mapcar, except it will strain out nil values from the answer list.

13.2.7  dolist

Another iterating function found in more modern LISPs is, dolist. The syntax of dolist is as follows:

   (dolist (<variable> <list> <result>)
           (executable statement)
           (executable statement)
              .
              .
              .
           (executable statement))
When dolist begins, the variable is set to the first value in list. The statements are then executed and LISP sets the variable to the second item in the list, and the statements are executed again. This cycle continues until there are no more items in list. < result > is then the value returned by the call to dolist. Here is an example of dolist to do the pos problem again and also a call of the function:
   (defun iter-pos-dolist (l)
      (setq positives nil)
      (dolist (x l positives)
              (cond ((> x 0)
                     (setq positives (cons x positives))))))
   > (iter-pos-dolist '(-1 44 97 -300 10))
   (10 97 44)
Notice that in this case, when the setq statement sets positives to nil, it will create a new global variable, positives.

Newer LISPs have many other control functions as well, including an if-then-else function and many other looping functions.

LISP13.3 Input, Output, Strings and Properties

13.3  Input, Output, Strings and Properties

This section covers input and output functions, string manipulation functions and property list functions.

13.3.1  Output

A couple of print statements appeared in the last section. The print function simply prints out its one argument and then writes an end of line marker. To print out an item without writing an end-of-line marker, the function, prin1 is used. The function, terpri will write an end-of-line marker. Here is a function called, dummy that simply writes out its three parameters on one line:

   (defun dummy (x y z)
      (prin1 x)
      (prin1 y)
      (prin1 z)
      (terpri))
The following is a call to dummy, and its result:
   > (dummy 1 2 'hello)
   12hello
   nil
The value returned by terpri is nil and so the value of dummy is nil. In addition to print and prin1, princ will print a single character or a character string. In this case printc prints a single blank:
   (princ " ")
Princ is like prin1 in that it does not write an end-of-line marker. LISPs that have string handling capabilities probably allow print and prin1 to print out strings as well so in many LISPs there is no need for princ.

13.3.2  backquote

Constructing and printing an output expression can often be awkward. For instance, you may want to print out a message together with the value of a variable all in one list, such as:

   (x is 1)
One way to do this is to write:
   (print (append '(x is) (list x)))
There is a convenient function, called backquote, that can make the process a little easier. The short-hand for calling the function, backquote is to use the backquote character, ```", in the same way you would use ``'" as a short-hand for quote. Backquote functions like quote, but with two exceptions. The first exception is that an item in the list immediately preceded by a comma is evaluated:
   (print `(x is ,x))
This call to print then produces the string, (x is 1). The comma is also treated internally as a function called, comma. A second convenience that can be used within backquote is a comma followed by an at sign, ``,@". The item after this pair should be a list that gets spliced into the backquoted one. For example let m be the list defined like so:
   > (setq m '(a list into a list))
   (a list into a list)
Typing in ,@m, in the middle of a backquoted expression fits m into the list, as in:
   > (print `(the comma-at function splices ,@m))
   (the comma-at function splices a list into a list)
   (the comma-at function splices a list into a list)
This backquote feature is common in newer LISPs but not in older ones. The backquote function does not need to be used just within the print function, it can be used anywhere, but it is most often found within print.

13.3.3  Writing to Other Files

For all the printing functions there is an optional extra parameter, a pointer to the file to print on. Naturally the default is the terminal output file. To create a file pointer to some other file, say, outfile, the function openo is called as shown in this example where two lines are printed to outfile:

   > (setq out-file-ptr (openo "outfile"))
   #<File: #a2d68>
   > (print 'hello out-file-ptr)
   hello
   > (print 'world out-file-ptr)
   world
To close the file, the function close is called with the file pointer:
   > (close out-file-ptr)
   nil
The file outfile, now contains the two lines:
   hello
   world

13.3.4  Reading S-expressions

The read function reads an S-expression from the input file and produces a prompt. In the following case, the user types in the list, (hello world) at the second prompt and then the read function call returns the value (hello world), which prints out as the value of the call:

   > (read)
   > (hello world)
   (hello world)
Another function, read-char, will read a single character. If an argument to read or read-char is present, it is assumed to be a file pointer. Files are opened for input using the function, openi and the filename is enclosed in double quotation marks:
   > (setq in-file (openi "outfile"))
   #<File: #a2d68>
   > (read in-file)
   hello
   > (read in-file)
   world
   > (read in-file)
   nil
When end-of-file is reached, nil is returned. Again, the function, close, is necessary to close a file.

13.3.5  explode and implode

Some other useful functions are explode, that takes an atom and converts it to a list of characters, or really the numeric ASCII codes for the characters:

   > (explode 'hello)
   (104 101 108 108 111)
Implode takes in a list of the ASCII codes for characters and fuses them into a single symbol:
   > (implode '(104 101 108 108 111))
   hello

13.3.6  string manipulation functions

Many LISPs have character manipulation functions. For example, here is a demonstration of how the string concatenation function, strcat, can be used:

   > (setq x "hello")
   "hello"
   > (setq y " world")
   " world"
   > (strcat x y)
   "hello world"

The function, chr converts the ASCII code for a single character to that character:

   > (chr 104)
   "h"
Strlen will find the length of a string:
   > (strlen "hello")
   5
The function, itoa, for integer to ASCII, takes in an integer and produces a character string:
   > (itoa 104)
   "104"
The function, atoi, for ASCII to integer, takes a string and converts it to an integer:
   > (atoi "137")
   137

13.3.7  Property Lists

Another important feature of LISP is that in addition to an atom having a value, an atom can also have a number of other properties. Early versions of LISP had the put (or putprop) function to assign properties and the get function to look up properties. Newer versions of LISP use the setf function to assign properties and won't necessarily have the put function. It is easy to define put using setf, however. First, here is a summary of put and its arguments:

   (put property atom-name value)
And here are some calls to put to give some atoms some properties:
   > (put 'size 'man 'large)
   large
   > (put 'size 'boy 'medium)
   medium
   > (put 'texture 'man 'soft)
   soft
   > (put 'texture 'rock 'hard)
   hard
The function get will return the property value of an atom. These are some examples of get:
   > (get 'rock 'texture)
   hard
   > (get 'boy 'size)
   medium
Properties can be removed by using the remprop function:
   > (remprop 'boy 'size)
   nil
   > (get 'boy 'size)
   nil
The use of setf for storing properties is rather strange. As an example of its use, here is a call to setf inside a home-made version of put:
   (defun put (property atom-name value)
      (setf (get atom-name property) value))
Setf has many other uses as well, but we will not discuss them.

LISP13.4 Advanced Functions and Macros

13.4  Advanced Functions and Macros

In this section, we will look at more features of standard functions as well as macros, another type of function. First we will consider the problem of declaring variables within a function and the problem of what variables can be accessed at a given time. This is quite a problem because there are two ways of treating variables. In older LISPs, such as XLISP 1.4, a strategy of dynamic scoping was used while most newer LISPs, such as XLISP 1.6, follow the COMMON LISP approach of using static (or lexical) scoping.

13.4.1  let and let*

The first point we look at will be the let and let* functions that create variables. Let and let* are only found in the newer LISPs. Let and let* can be used anywhere within a LISP function but they are most commonly seen at the beginning of a function. Effectively they are used to declare extra variables to be used within the function and they vanish when the function ends. The structure of let and let* are:

   (let* ((<variable 1> <initial value>)
          (<variable 2> <initial value>)
             .
             .
             .
          (<variable n> <initial value>))
         (<executable statement>)
         (<executable statement>)
             .
             .
             .
         (<executable statement>))
The difference between let and let* is best described by using two small functions that are identical, except that one uses let and the other uses let*. Here is the first function, dummy-with-let:
   (defun dummy-with-let (a)
      (let ((x a)
            (y x))
           (print '(inside dummy-with-let))
           (print `(x is ,x))
           (print `(y is ,y))))
This function doesn't do anything special, it merely prints out a little message and the value of x and the value of y. When the let is entered, the variable x is assigned the value a but because the let function doesn't look at any of the assignments it has made so far, y will be assigned whatever value it had before the local x was assigned the value a. For instance, we can set up a global variable, x and set it to 99:
   > (setq x 99)
   99
A call to dummy-with-let will then make y be the value, 99. Here is a call to dummy-with-let and the results it produces:
   > (dummy-with-let 1)
   (inside dummy-with-let)
   (x is 1)
   (y is 99)
   (y is 99)
On the other hand, let* does know about the assignments it has made, so the following function, dummy-with-let* gives y the same value as x:
   (defun dummy-with-let* (a)
      (let* ((x a)
             (y x))
            (print '(inside dummy-with-let*))
            (print '(x is ,x))
            (print '(y is ,y))))
   > x
   99
   > (dummy-with-let* 1)
   (inside dummy-with-let*)
   (x is 1)
   (y is 1)
   (y is 1)

13.4.2  Lexical and Dynamic Scoping

A big difference between the various versions of LISP has to do with what variables are accessible from what functions. Newer LISPs only allow a user to access global variables and the variables within the scope of the block in which the variable is declared. This corresponds to the way Pascal works. This scheme is known as lexical scoping and the newer LISPs, such as XLISP 1.6 work this way. Older LISPs, such as XLISP 1.4 use dynamic scoping to look up variables. In this older method, every variable is kept on a run-time stack, together with its name, then, when a variable is needed, LISP starts at the top of the stack and finds the first variable with that name and returns its value. LISP programmers that are not used to this unusual scheme will therefore occasionally run up against really strange errors.

To illustrate the differences between the two methods, here are two simple functions, scope1 and scope2 that don't do anything special:

   (defun scope1 (a b)
      (let ((x a)
            (y b))
           (print '(inside scope1))
           (print (append '(x is) (list x)))
           (print (append '(y is) (list y)))
           (scope2 (+ a b))))
   (defun scope2 (c)
      (print '(inside scope2))
      (print (append '(x is) (list x)))
      (print (append '(y is) (list y))))
Scope1 prints out the values of x and y and then calls scope2. Here is what happens with dynamic scoping:
   > (scope1 1 2)
   (inside scope1)
   (x is 1)
   (y is 2)
   (inside scope2)
   (x is 1)
   (y is 2)
   (y is 2)
On the other hand, here is what happens with lexical scoping:
   > (scope1 1 2)
   (inside scope1)
   (x is 1)
   (y is 2)
   (inside scope2)
   error: unbound variable - x

13.4.3  Macros

The kind of functions we have been creating with defun all evaluate their arguments before they execute. Older LISPs refer to the type of function that evaluates its arguments as an expr and a function that does not evaluate its arguments is called a fexpr . Newer LISPs don't have fexpr's but they have the defmacro function that creates a function that acts like a fexpr in that it does not evaluate its arguments, but then in addition, whatever a macro finds as its answer is evaluated again in a variable environment that is independent of the macro.

The first feature of the macro definition we will show is how the macro computes its value. First, here is a function, called add-function, that takes in two parameters and forms a list with the atom, +, at the start followed by its two parameters:

   > (defun add-function (x y) (list '+ x y))
   add-function
   > (add-function 3 4)
   (+ 3 4)
Of course, the result is as expected. Now we will define a macro called add-macro that is otherwise identical to add-function:
   (defmacro add-macro (x y) (list '+ x y))
Now if we call add-macro with the parameters 3 and 4, it will form the list, (+ 3 4) and then LISP will go on to evaluate it:
   > (add-macro 3 4)
   7

The next couple of features to illustrate will be how arguments to macros are not evaluated and how the macro result is evaluated in an environment outside of the macro. To do the illustration, we will use a macro, add-macro2, that is much the same as add-macro:

   (defmacro add-macro2 (p1 p2)
      (let* ((x 1)
             (y 2))
            (print p1)
            (print p2)
            (list '+ p1 p2)))
The only differences are that we will have an x and y inside the let* and the two parameters, p1 and p2 will be printed out when the macro executes. We will set up global variables x and y to be 7 and 8 respectively:
   > (setq x 7)
   7
   > (setq y 8)
   8
We now call add-macro2 with x and y as parameters:
   > (add-macro2 x y)
   x
   y
   15
The first thing to notice about the output is that p1 and p2 have the values x and y and not 7 and 8. Of course, this is because macros don't evaluate their arguments. As the function executes, the x within the let* is set to 1 and the y within the let* is set to 2. Then, the expression, (+ x y) is constructed and becomes the value of the let*. The variables x and y within the let* vanish and the parameters, p1 and p2 also vanish. Now, the expression, (+ x y) is evaluated, giving a value of 15. It is easy to look at the last statement in a macro and think that it will know about variables in the macro. We made this special demonstration to emphasize the fact that the final expression created by the macro is not evaluated within the macro.

The final feature of functions and macros has to do with the fact that they can have optional parameters or even an arbitrary number of parameters. A nice instance of when optional parameters come in handy is, if you wrote your own LISP pretty-printing function, called, say pp. On most occasions, you probably want the function pretty-printed on the screen, so a call like, (pp fact) is convenient. On the other hand, there may be occasions when pretty-printing a function to a different file is necessary. On those occasions, you want to specify the file pointer as a second argument so a definition for pp would start out as:

   (defmacro pp (item &optional where)
      (let* ((fptr (cond (null where) *standard-output*)
                         (t (openo ...
The &optional keyword flags where as an optional parameter. If there is no second parameter in a call, where will be nil. In the let*, fptr, the file pointer is either set to the file pointer, *standard-output* if where is nil or otherwise, to some other file pointer created by openo.

Another way to get an arbitrary number of parameters is to use the keyword, &rest, followed by the name of the variable that gets the parameters as in:

   (defmacro comment (&rest c) t)
Whatever the macro is called with, it is all put in the list, c, and it is up to the programmer to break off items from the list, as necessary. This comment macro doesn't do any calculation and it just sends back the value, t. With this macro, arbitrary long comments can be inserted in LISP code, as in:
   (comment With the comment macro, comments won't be lost when
            they are read in)
Note, though that there will be a penalty in the execution time of a function containing this type of comment.

LISP13.5 A Few Examples

13.5  A Few Examples

In this section we will finish discussing LISP by looking at a few examples of common problems done in LISP: substitution of expressions in a tree, quicksort and a matching problem that is similar to PROLOG matching.

13.5.1  Substitution

The first function to look at is the substitution into a tree function. Most LISPs already have a built-in substitution function called, subst but we will write our own, called sub. Sub will search through its first argument, a tree, for instances of its second argument, old. If it finds an instance of old, it replaces it with a new expression, given in the third argument of sub. For example:

   > (sub '(a b (c d a) b) 'b 'x)
   (a x (c d a) x)
   > (sub '((a b) (c d)) '(a b) '(a b c d))
   ((a b c d) (c d))
The function to do this is straightforward:
   (defun sub (tree old new)
      (cond ((null tree) nil)
            ((equal tree old) new)
            ((atom tree) tree)
            (t (cons (sub (car tree) old new)
                     (sub (cdr tree) old new)))))
For the first test, if the tree is nil then return nil. The second test looks at the whole tree to see if it is equal to the expression to replace. If it is, then it is replaced by the new expression. The third test is to see if the tree is just a single atom (that won't be equal to the old expression) and if it is an atom, return that atom. The otherwise clause simply forms an answer where the answer is the new tree formed by substituting into the car of the tree and then consing this with the new tree formed by substituting into the cdr of the tree.

13.5.2  Quicksort

The next example to look at will be quicksort. Recall that the algorithm works as follows. First select a number, called the key, possibly the first number in the list and use it to split the list into two separate lists, one called left that will have all the values less than or equal to key and one called right that will have all the numbers greater than key. For instance, given the list:

   (19 5 23 17 89 0 10),
it would be split into the two lists:
Left:
(0 17 5)
Right:
(101 89 23)
Second, sort these two lists, again using quicksort. This will set off a series of recursive calls. When this series finishes, the left list and the right list will be in order:
Left:
(0 5 17)
Right:
(23 89 101)
We can now attach the key to the front of the right list and append both of these together to give:
   (0 5 17 19 23 89 101)

Here is the LISP definition of quicksort:

   (defun qs (l)
      (let* ((twolists nil)
             (left nil)
             (right nil)
             (sortedleft nil)
             (sortedright nil))
            (cond ((null l) nil)
                  (t (setq twolists (partition (car l) (cdr l)))
                     (setq left (car twolists))
                     (setq right (cdr twolists))
                     (setq sortedleft (qs left))
                     (setq sortedright (qs right))
                     (append sortedleft
                             (cons (car l) sortedright))))))
The trivial condition in the process is to note that the sorted version of an empty list is the empty list. The second condition does the real work. The first problem is to split the list, l, into two portions, left and right. The number that splits the list will be the first item in l, or (car l). Obviously the list l could be split by first calling one function to return all the numbers less than or equal to (car l) and then calling a second function to return all the numbers greater than (car l) but this version does not work that way. Instead just one function call is made to a function called, partition. Partition will have to return two lists. To do this, partition will take the two lists and cons them together to form just one value to return. This list will be saved in the variable, twolists. So if the initial list to sort was (19 5 23 17 89 0 101) then calling partition will produce:
   > (partition 19 '(5 23 17 89 0 101))
   ((0 17 5) 101 89 23)
In the next steps, left will get the first part of this list and right will get the rest. The function qs will then get the list, left, and produce the list, sortedleft. A second call to qs with right will produce the list, sortedright. In the last step the pieces are put together.

There is still the matter of looking at how to partition the numbers into two lists in just one call. The definition of partition and a function it uses called partition2 are as follows:

   (defun partition (key l) (partition2 key l nil nil))
   (defun partition2 (key l left right)
      (cond ((null l) (cons left right))
            (t (cond ((> (car l) key)
                      (partition2 key (cdr l) left
                                  (cons (car l) right)))
                     (t (partition2 key (cdr l)
                                    (cons (car l) left)
                                    right))))))
The function partition itself, does little, it merely sets up a call to another function, partition2, where the real work is done. The first parameter of partition2 is the key used to divide the list, l, the second parameter. The third and fourth parameters function as accumulating parameters . In each recursive call of partition2, the first number in l is taken off and added to either the front of the third parameter, left, or the front of the fourth parameter, right. At the beginning of the process, the variables will be:
   key = 19
   l = (5 23 17 89 0 101)
   left = ()
   right = ()
The function will find that the first number of l should be added to the left hand list. In the next call of partition, the variables will be:
   key = 19
   l = (23 17 89 0 101)
   left = (5)
   right = ()
In each recursive call the first number in l will be added to one list or the other. Finally, l will be empty and the result sent back will be left consed onto right.

13.5.3  PROLOG-Like Pattern Matching

The final example we will look at in this section is a LISP matching function that does a simple version of PROLOG-like pattern matching. We will assume that there is one list that contains a pattern, possibly including variables, while a second list is a fact that never has any variables in it. With this restriction, the simple matcher will not be able to handle rules. We will call the pattern matching function, match. Here are a few sample calls to match, and the values that are returned:

   > (match '(likes john X) '(likes john mary))
   ((X mary))
   > (match '(likes X Y) '(likes bob cardinals))
   ((Y cardinals) (X bob))
   > (match '(likes bob cardinals) '(likes bob cardinals))
   t
   > (match '(likes bob cubs) '(likes bob cardinals))
   nil
As can be seen, the pattern is the first argument and the data is the second argument. Variables, as in PROLOG will start with a capital letter. When the two lists match, a list is returned that contains variables and their values. If there are no variables and the lists match, t is returned. If the patterns don't match, nil is returned.

In programming this function, two problems will immediately come to mind. The first problem is that we need a way to identify a variable and the following function will do this:

   (defun variable (x)
      (let* ((firstch (car (explode x))))
            (cond ((and (>= firstch 65)
                        (<= firstch 91))
                   t)
                  (t nil))))
This function works by taking its variable, x, exploding it into a list of ASCII characters and examining the first one. If it falls in the range, 65 to 91, it is a capital letter so return t, otherwise return nil.

The second problem that comes to mind is that we will need to keep a list of variables and their values. A list that keeps variables and their values is known as an association list . The values returned in the above examples show the association lists that the matching function created. Many LISPs have built-in functions for this problem, but creating a list and a function to search it is quite easy so we will do without using the built-in functions. The structure of the association list will look like:

   ((<variable 1> <value 1>)
    (<variable 2> <value 2>)
       .
       .
       .
    (<variable n> <value n>))
The function that searches the association list for a variable and returns its value, will be called, val. Here is its definition:
   (defun val (x a)
      (cond ((null a) nil)
            ((equal (caar a) x) (car (cdar a)))
            (t (val x (cdr a)))))
The item to search for is x and the association list is a. This function follows the typical recursive pattern. The first item on the list is checked to see if it is the variable-value pair we are looking for and if it is, the value is returned. If the first item on the association list is not what we're looking for, val searches the rest of the list by passing the cdr of a on to another call of val. When the list, a, is nil in a call to val, then nil is returned and the recursion stops.

With the functions variable and val at hand, we can go on to the major part of the problem, the function match. The problem will really be divided into two functions, match and match2. Here is the definition of match:

   (defun match (p d)
      (cond ((equal (length p) (length d))
             (match2 p d nil))
            (t nil)))
First, the function, match will make a simple test to see if the pattern list, p, and the data list, d, are the same length. If they are the problem is passed on to match2. Match2 has a third argument that is the association list. Naturally it must start out empty and this call to match2 supplies this empty list.

Match2 is rather more complicated. Its arguments are the pattern, the data and the association list. Here is the definition of match2:

   (defun match2 (p d a)
      (cond ((null p)
             (cond ((null a) t)
                   (t a)))
            ((equal (car p) (car d)) (match2 (cdr p) (cdr d) a))
            ((and (variable (car p)) (null (val (car p) a)))
             (match2 (cdr p)
                     (cdr d)
                     (cons (list (car p) (car d)) a)))
            ((and (variable (car p))
                  (equal (val (car p) a) (car d)))
             (match2 (cdr p) (cdr d) a))
            (t nil)))
Match2 follows the standard pattern for recursive functions. It deals with the first items in the lists p and d. If the tests on these succeed, match2 is called with the cdrs of p and d. If p (and therefore, also, d) become null, then every item in the two original lists must have matched. We will now look at this general scheme in more detail.

The first condition to check is whether or not p has anything left in it. We could just as well have checked d and if we hadn't put the length check into the function match, we would have to check to see if both p and d were null to detect a successful match. If match2 finds p is nil, we have to check if there are instantiated variables in the association list. If there are, this association list is sent back otherwise then t is sent back.

The second test in the cond is fairly simple:

   ((equal (car p) (car d)) (match2 (cdr p) (cdr d) a))
This test checks the first atom in p against the first atom in d. If they match, then the problem becomes whether or not the rest of the lists, p and d match. This problem is passed on to another call of match2 using the same association list. For example, suppose the function call started out with:
   p = (likes john X)
   d = (likes john mary)
Then the two likes match and the problem becomes, in the next recursive call of match:
   p = (john X)
   d = (john mary).
The third test is more complicated:
   ((and (variable (car p)) (null (val (car p) a)))
   (match2 (cdr p)
           (cdr d)
           (cons (list (car p) (car d)) a)))
If the atom at the start of the pattern, p, is a variable and val reports that this variable isn't in the association list yet, then obviously the variable can match whatever item is on the front of the data list. The variable and its value will get added to the association list. For example, if we were working on the problem:
   (match '(likes X Y) '(likes bob cardinals))
and we had progressed in the problem to the point where:
   p = (Y)
   d = (cardinals)
then the association list coming into this call of match2 would be:
   a = ((X bob)).
The atom, cardinals will match with Y. The list, (Y cardinals) will be formed and consed onto a so the next call of match2 will get:
   a = ((Y cardinals) (X bob))
Again, the question as to whether or not p and d match becomes the question as to whether or not the cdrs of p and d match and this problem is passed on to match2.

The last major test covers the case where the variable already has a value:

   ((and (variable (car p)) (equal (val (car p) a) (car d)))
    (match2 (cdr p) (cdr d) a))
In this case, val returns the value of the variable and if this value is the same as (car d), then the match succeeds. The rest of the problem is passed on to match2, but there is no need to put another entry on the association list. This test comes into use for instance, in the call:
   (match '(likes X X) '(likes john mary))
Suppose the matching has progressed to the point where:
   p = (X)
   d = (mary)
   a = (X john)
This fourth test will take the X from p and check to see if it is a variable. It is, so LISP moves on to val to look up its value. Val returns, john. John does not match mary so the match fails. If, on the other hand, d was (john), then the X in p will match john and the matching process will continue.

If any of the four tests fail, then the whole match fails and the function returns nil. An otherwise clause at the end of the cond makes this explicit.

Some extensions to this problem to make a LISP program somewhat like a PROLOG interpreter are suggested in the exercises. A word of advice to the reader: if you plan on doing some of the exercises in this book using LISP, it is not necessary to write a PROLOG-like interpreter in LISP first. It is far easier to just produce a LISP program specific to the task at hand.

LISP12.6 Exercises

13.6  Exercises


13.1.
Draw tree structures for the following LISP expressions:

   (a b (c d))
   ((a b (c d)))
   ((a (b c) d))
   ((a b (c d) (e f)) (g)))


13.2.
If it exists, give the car, cdr, caar, cddr, cadr and cdar for each of the expressions in the above exercise.


13.3.
The function, iter-pos-prog, returned a list of positive numbers that was the reverse of their order in the input list. Write an iterative version using a prog that will not reverse their order in the input list. Some LISPs will have a built-in function, reverse to reverse a list but if your LISP has this function, don't use the built-in one.


13.4.
Program the recursive fibonacci function.


13.5.
Write a function, strain, that will remove nil items from a list such as: (nil 44 97 nil 10) to give, (44 97 10). Do this function twice, once recursively and once using iteration.


13.6.
Write a LISP function, nodupl, that will remove duplicate entries from a list. For example:

   > (nodupl '(h e l l o w o r l d))
should give:
   (h e l o w r d)


13.7.
Write a macro function sqq, for ``set quoted quoted" that will take in a variable length list of variables and values and set the variables to those values. For instance, given:

   (sqq a 100 b 200 c 300 d z)
sqq should set a to 100, b to 200, c to 300 and d to (quote z). Second write another macro, squ for ``set quoted unquoted" that will do the same except this time the call:
   (squ a 100 c 300 d z)
will set a to 100, c to 300 and d to the current value of z. Third write another macro, suu for ``set unquoted unquoted" that will do the same except this time the call:
   (suu a 100 d z)
will have to look up the value of a and set it to 100 and look up the value of d and set it to z.


13.8.
People often look at a LISP expression like:

   (cons 'a l)
and expect l to change, but of course, it does not. LISP produces a copy of l, puts the atom on the front of the copy and returns this answer without changing l so the above expression is really comparable to writing 1 + x in standard languages. Write a macro called gluon, that will change the value of its second argument so, for instance, if l is (b c), then (gluon 'a l) will give l the new value, (a b c).


13.9.
There are a few more examples of common problems that are done as PROLOG problems in section 12.3. Even if you have only read section 4.2, on PROLOG As a Notation, you should be able to understand the examples in section 12.3. Do the tree search problem and the selection sort problem over in LISP. For the selection sort problem, make sure your version will handle lists with duplicate entries.


13.10.
Binary search trees have the useful property that at a parent node, every number to the left of the node is less than the value at the parent node and every number to the right of the node is greater than or equal to the parent node.

a)Write a LISP function that will search a binary search tree for a given number. Naturally you will take advantage of the order within the tree to do the search quickly.

b)Write a LISP function to insert numbers into a binary search tree.

c)Write a LISP function to delete a number from a binary search tree.


13.11.
Program mergesort in LISP using only recursion.


13.12.
The match function in section 13.5 is simpler than the PROLOG type of matching. Add these two features to the matching problem:

a)When PROLOG is given a question it goes and searches through a whole database of facts whereas the match function in the last section only attempts to match one question against one piece of data. Write some extra LISP functions that will search a whole database of facts, then when the program finds an answer, it should print out the values of the instantiated variables, like PROLOG, and then wait for a response from the user. If the user types a ``;", the search for matches should continue, otherwise, let the matching process end.

b)The function, match, is not capable of handling rules. Modify it and/or create more functions so that it has this capability. A simple version of this could deal with just a short rule, like:

        likes(X,lemonade) :- likes(X,yankees).
or you may want to program a slightly more complex version that handles more than one clause to the right of the ``:-" operator. Choose whatever input notation for the rules that you feel like. In a simple version, a rule could be input as:
        (:- (likes (X lemonade)) (likes (X yankees)))
or if you are more ambitious have your program input actual PROLOG text.


13.13.
Write a LISP function or functions to take the derivatives of common functions written out in LISP's prefix type notation. Below is a small function you might want to use as a starting point. It will take the derivative of a variable with respect to itself, the derivative of a constant and the derivative of the sum of two functions:

   (defun deriv (f var)
      (cond ((and (atom f)
                  (equal f var) 1))
            ((atom f) 0)
            ((equal (car f) '+)
             (list '+
                   (deriv (cadr f) var)
                   (deriv (car (cddr f)) var)))))
The first argument is the function to take the derivative of and the second argument specifies what the variable is. These are some sample calls of deriv:
   > (deriv 'c 'x)
   0
   > (deriv 'x 'x)
   1
   > (deriv '(+ 1 x) 'x)
   (+ 0 1)
   > (deriv '(+ x x) 'x)
   (+ 1 1)
Have your program do derivatives for the following functions, where c is a constant and u and v are functions or variables:
1)
(- u),
2)
(- u v),
3)
(* c u),
4)
(* u v),
5)
(/ u v),
6)
(exp u), e to the power u,
7)
(power u c), u to the power, c, and
8)
(ln u), the natural log of u.

Footnotes:

1For this reason, some people believe that the actual origin of the name, LISP comes from ``Lots of Irritating Single Parentheses".

2Some function evaluate all their arguments while another type of function called a macro never evaluates its arguments and then there are functions like setq, described below that evaluates only one of its arguments. LISP programmers simply have to know how each function treats its arguments.


File translated from TEX by TTH, version 2.60.
On 7 Feb 2000, 15:20.