Chapter 2

BASIC LISP PROGRAMMING

Lisp stands for List Processing and is invented by John McCarthy from MIT in mid-1950s. Common Lisp dialects are, INTERLISP, FRANZLISP, MACLISP, PC SCHEME, and COMMON LISP etc.

2.1 GENERAL FEATURES

(a) In its "pure" form

1. LISP computes all values by function application. The concepts of "variable", "declaration" and "assignment" do not exist.
2. The only control mechanisms, other than (simple) function application, are recursion and the use of conditionals. The concepts of "loop", "goto" and "label" do not exist.
3. The only non-trivial data structure which is also known as s-expression or symbolic expression is the list. (There are no records or arrays).

(c) The LISP translator is resident at run-time and in LISP we can write "programs which write programs".

(d) Storage can be generated dynamically. Garbage collection is handled automatically by the system. Garbage collection is a way in which memory cells are reclaimed for the free storage list. A garbage collector is invoked when the free storage lis t is near exhaustion.

(d) LISP treats data types dynamically. At one instance X may be an integer. At another instant X may be a list.

(e)E="2.1">LISP is an interactive language. Translation and execution can easily be interleaved. LISP programs are easy to debug. When a run-time error occurs, the system preserves the context of the error and we can easily interrogate this con text.

2.2 ATOMS

An atom is an indivisible data value such as:

Also, NIL (or 'NIL) is a special atom which is used to denote the null list.

2.3 FUNCTIONAL NOTATION

Any non-trivial expression in LISP is composed of terms of the form

One must get used to this notation. In LISP, an expression such as

is written as

In Common LISP 'PLUS' is represented by the symbol (+)

2.3.1 List Diagrams

It sometimes helps to be able to draw list diagrams. Here are some examples:

2.3.2 Evaluation Inhibiting Signal

How far should the evaluation process go into an expression? LISP needs help in making this decision. For instance, let us consider the following expression:

Quote mark prevents LISP from thinking about A in (A B C) as a function to be applied to B and C.

Let us take another example.

So, the result is CDR.

Leaving out the quote mark will result in an attempt to use A as a procedure. Unless you define a procedure you will get error (undefined procedure).

2.4 SOME PRIMITIVE LIST OPERATORS

(CAR   x)                Selects the "head" of a list cell   



(CDR   x)                Selects the "tail"  of a list cell 


(CONS  x  y)             Constructs the list cell

(LIST  x1  x2.. xN)      Constructs the list

Examples


EXPRESSION                                                           VALUE 

(CONS 'A  (LIST 'B 'C))                                           '(A  B  C) 



(CAR  '(A  B  C))                                                 'A  


(CDR '(A B C))                                                    '(B C) 



(CONS (CDR '(A B C)) (CAR '((D  E)  F)))                          '((B  C)  D E)

2.4.1 Shorthand Notation for Combinations of CAR and CDR

LISP allows the following short hand notation:

  (CADR X)    means (CAR (CDR X)) 


  (CDDR X)    means (CDR (CDR X)) 


  (CADDAR X)  means (CAR (CDR (CDR (CAR X))))

2.5 BOOLEAN VALUES

LISP has an unusual convention for Boolean values:

           NIL   denotes  "false" 


anything else    denotes  "true"

(ATOM x) is true if x is an atom, false if x is not.

Note: NIL is classified as an atom, but is used to represent the null list.

2.6 EQUALITY TESTS IN LISP

There are two tests for equality in LISP:

EQ essentially compares addresses. (EQ 'ZAP 'ZAP) is true, since atoms are stored once only. But (EQ '(A B) '(A B)) lists with different addresses.

EQUAL performs a full recursive inspection of objects to test for equality of value. Thus (EQUAL '(A B) '(A B)) is true.

NOTE: EQUAL in safer to use than EQ.

2.7 FUNCTIONS

2.7.1 Function Definitons

Here's a function to square a number:

     (DEF SQUARE
          (LAMBDA (X)
              (TIMES  X   X)))

Having defined this function we can immediately test it

     (SQUARE 2)  ?- - -  input

           4     ?- - -  system response

At the outermost level,  LISP will read in an expression, translate it, 

evaluate it and print the result.

2.7.2 Lambda Expressions

A Lambda expression defines an anonymous function.The general form of 

a lambda expression is
                               may be (),  if no parameters
                   (LAMBDA (X1 ... XN)   exp)

which means "that function of X1 ... XN whose value is given by  the expression exp".

This function has no name.  We can use DEF to give the function a  name.

( DEF nm lam)  will associate the name "nm" with the lambda  expression "lam".
Example

   (DEF FUN
     (LAMBDA  (X  Y)                     Computes
       (DIFF (TIMES  X  X)            X2 - Y2
           (TIMES    Y  Y))))

2.8 CONDITIONAL EXPRESSIONS (COND'S)

The general form of a COND is

    (COND (c1  e1)

          (c2  e2)     "clauses"

          (cN  eN))

The meaning of the COND is given by the following flow-chart:

Note that the  entire COND is an expression which always delivers  a value (possibly NIL).

Example: Function to find the larger of two numbers.

      (DEF MAX2
         (LAMBDA  (X  Y)
                  (COND  ((GREATERP  X  Y)  X)
                         (  T  (Y)))

The flow-chart for MAX2 is

2.9 Recursive Functions

The usual approach to writing a recursive function in LISP is

1. Break the problem up into cases. Use a COND to distinguish the cases.
2. Specify the simple cases first.
3. Solve the more complex cases by recursion.

Cases:

1. If N = 1, FACT = 1
2. Otherwise FACT (N) = N * FACT (N-1)

   (DEF FACT
               (LAMBDA  (N) 
                     (COND  ((EQUAL (N  1)  1) 
                            (T  (TIMES  N  (FACT  (SUB1  N)))) 
                                        )))

Cases:

1. If L = NIL, LENGTH = O
2. Otherwise, LENGTH = 1 + LENGTH (tail of list)

 
     (DEF LENGTH 
            (LAMBDA  (L) 
                  (COND  ((NULL L)  O) 
                         (T  (ADD1  LENGTH (CDR  L))   )))

(LENGTH '(A  B  C))                     1st call 

  = 1 + (LENGTH  '(B  C))               2nd   " 

  = 1 + 1 + (LENGTH '(C))               3rd   " 

  = 1 + 1 + 1 + (LENGTH  NIL)           4th   " 

  = 1 + 1 + 1 + 0                       return to 4th call 

  = 1 + 1 + 1                           return to 3rd call 

  = 1 + 2                               return to 2nd call 

  = 3                                   return to 1st call

Cases:

1. Max of list of length 1 = head of list
2. Otherwise

MAX = max of (head of list, MAX of tail of list)

 
            (DEF MAX 
                 (LAMBDA  (L) 
                        (COND  ((NULL  (CDR  L))  (CAR  L)) 
                               (T  (COND  ((GREATERP  (CAR  L) (MAX (CDR L))) 
                                                      (CAR  L)) 
                                          (T  (MAX  (CDR  L))))) 
                                                                            )))

Example: Define a function to produce a list of replicated values.

E.g. (REP 4 'A) = '(A A A A)

(DEF  REP 
      (LAMBDA  (N  X) 
          (COND  ((ZEROP  N)  NIL) 
                 (T  (CONS  X  (REP  (SUB1  N)  X))) 
                                         )))

E.g. (LAST '(A B C)) = 'C

(DEF  LAST 
   (LAMBDA  (L) 
       (COND  ((NULL  (CDR  L)) (CAR  L)) 
              (T  (LAST  (CDR  L)))  )))

Cases:

1. (REVERSE NIL) = NIL
2. 

(DEF REVERSE 
    (LAMBDA  (L) 
      (COND  ((NULL L)  NIL) 
             (T  (APPEND  (REVERSE  (CDR  L)) 
                           (LIST  ((CAR  L))))  ))))

2.10 Dealing with Nested Lists ("Trees")

When writing recursive functions for lists such as:

it is usually necessary to

1. Use a recursive call to process (CDR X)
2. Use another recursive call to process (CAR X)

Example: Count the number of times that a given value V occurs in some list L.
E.g. (COUNT 6 '(2 (6 (6 3) 4) (2 6))) = 3

Cases:

1. If L is an atom (which could result from some previous recursive call), compare L to V and return 0 or 1.
2.  
3. Otherwise

(COUNT L) = (COUNT (CAR L)) + (COUNT (CDR L))

              (DEF  COUNT 
   (LAMBDA  (V  L) 
      (COND  ((ATOM  L) 
               (COND  ((EQ  L  V)  1)  (T  0))) 
              (T  (PLUS  (COUNT  V  (CAR  L)) 
                         (COUNT  V (CDR  L))))   )))

E.g. (FLATTEN '((A (B C)) (D) E)) = '(A B C D E)

   (DEF  FLATTEN 
      (LAMBDA (L) 
         (COND  ((NULL L)  NIL) 
                (T  (COND  ((ATOM  (CAR L)) 
                            (CONS  (CAR L) 
                                   (FLATTEN (CDR L)))) 
                           (T  (APPEND 
                                  (FLATTEN  (CAR L)) 
                                  (FLATTEN  (CDR  L)))) 
                                      ))     )))

2.11 The PROG Feature

Generally, one tends to follow a recursive style of programming in LISP. However, now and then, perhaps for efficiency reasons, it becomes necessary to use a more conventional, iterative approach. The PROG allows this. The general form of a PROG is as follows:

D may be () 
             (PROG  (locals) 

             S1 

             S2 

             SN)

(exp)         (computethe expression exp and throw the result away(usually exp involves some useful side - effect) 

(RETURN exp)  Return exp as the value of the entire PROG - expression                        
   X          (X  is atomic)  X  is used as a label (GO  X)      
              Goto statement.

          (SETQ  V  E)

           V  :  = E

(DEF  LENGTH 
     (LAMBDA (L) 
         (PROG (N) 
            (SETQ N  O) 
               LOOP 
                 (COND ((NULL L)  (RETURN N))) 
                     (SETQ N (ADD1 N)) 
                        (SETQ L (CDR L)) 
                            (GO LOOP) 
                               )))

2.12 The (Run-Time) Symbol Table

LISP maintains a "symbol table" containing entries of the form

For example, if X = '(A B) and Z = 4, the symbol table might appear as below:

This symbol is present at run-time and so we can change the meaning of a variable (and hence its type) at run-time. Thus, LISP is a "dynamic type" language. Many languages build the symbol table at compile-time, and the type of any variable is fixed throughout run-time.

2.13 The Run-Time Stack

All LISP functions

1. Take their input parameters from the run-time stack.
2. Place their result on the run-time stack.

Consider the expression 

   (PLUS  (TIMES  2 4)  (TIMES  3  3)) 

The sequence of execution will be as follows:

ACTION                          STACK 

PUSH  2                           2 

PUSH  4                           4     top                      
                                  2 

CALL TIMES                              (TIMES removes 2 params) 

LEAVE TIMES (RETURN)              8 

PUSH  3                           3                                   
                                  8 

PUSH  3                           3                                   
                                  3                                   
                                  8 

CALL TIMES                        8 

LEAVE TIMES                       9 
                                  8

CALL PLUS                         0 
LEAVE PLUS                       17

2.14 Treatment of Locals (Function Entry-Exit)

Function parameters »locals are treated the following way:

1. They are given initial values, in the symbol table, upon function entry. Where necessary, previous meanings of identifiers in the symbol table are pushed down.
2. The symbol table is restored upon function exit.

(DEF FUN 
        (LAMBDA  (X) 
          (PROG  (Z) 
              (SETQ  Z  1) 
            ))) 
     (SETQ  X  '(A  B)) 
     (SETQ Z  0)       (FUN  4)

1. Just before the call (FUN 4) the symbol table will be


2. Just after entry to FUN, the symbol table will be


3. Just after (SETQ Z 1) in FUN, the Z - entry will be


4. Upon leaving FUN, the symbol table will be restored to the status shown in 1

2.15 EVAL

(EVAL exp) causes exp to be translated and then evaluated.

Example:

             (SETQ  X  1) 
             (SETQ  Y  2) 
             (EVAL '(PLUS X Y))
                       3

The function COMPOSE computes f(g(x)) given f, g and x:

                 (DEF SQUARE 
                    (LAMBDA  (X)  (TIMES  X  X))) 
                 (DEF COMPOSE 
                     (LAMBDA  (F  G  X) 
                        (EVAL  (LIST  F  (LIST  G  X)))))  

                 (COMPOSE  'SQUARE  'ADD1  2) 
                             9 

                 (COMPOSE   'ADD1  'SQUARE  2) 
                             5

2.16 MAPCAR

MAPCAR applies a function systematically to all elements in a list.

E.g. (MAPCAR 'ADD1 '(2 3 4))

has the value '(3 4 5),

Also: (MAPCAR '(LAMBDA (X) (TIMES X X)) '(2 3 4))

has the value '(4 9 16)

2.17 APPLY

The expression (APPLY fn lst) causes the function fn to be applied to the list of arguments lst.

Examples:

(APPLY  'APPLY  'ADD1    '(2))     produces 3 

     (APPLY  '(LAMBDA  (X)  (TIMES  X  X))  '(2))   produces 4 

            (APPLY  'GREATERP  '(2  3))     produces NIL.