LEARNING LISP

Contents | Control Structures | Properties and Lambda Expressions

Eval and Apply

In this brief chapter, we will show you the entire Lisp interpreter. Well, not really, but we will show you some functions which form the "heart" of the Lisp system.

When you type an expression into the Lisp system, it is passed to a function called EVAL. EVAL [EVALuate] processes your expression and returns the result. What is this thing called EVAL?

:(SETQ A '(CAR B))

  (CAR B )

:(SETQ B '(AA BB CC DD))

  (AA BB CC DD )

:(EVAL A)

  AA

:(CAR '(AA BB CC DD))

  AA

:(EVAL 'A)

  (CAR B )
Let's see what happened. First we defined two variables, A and B. Note that the value of A is a legal Lisp expression. When Lisp EVALuates A, it is as if we had typed in the expression ourselves. Lisp returns the value of the expression as the result. When Lisp EVALuates "A", it returns the value of the value of 'A, which is the same thing as the value of A.

The importance of this ability may not be immediately apparent. However, notice that this enables us to manipulate programs as data and then evaluate them. Most other programming languages do not provide this facility. Here is a small example.

:(SETQ FUN 'MULT)

  MULT

:(SETQ X 3)

  3

:(SETQ Y 2)

  2

:(SETQ VARS '(X Y))

  (X Y )

:(EVAL (CONS FUN VARS))

  6
In Lisp, there is another function which will evaluate a function and its data: APPLY. The generic form of the APPLY function is "(APPLY function-name list-of-arguments)". To repeat the last line in the above example use the APPLY function.
:(APPLY FUN X Y)

  6
Let's apply what we know about EVAL to the problem of evaluating polynomials. The polynomials are going to be represented by their associated Lisp expressions. Thus,
3x2+15
will be represented as
(ADD (MULT 3 (MULT x x)) 15)
Suppose we have this representation as the value of some variable.
:(SETQ P '(ADD (MULT 3 (MULT X X)) 15))))

  (ADD (MULT 3 (MULT X X ) ) 15 )

:(EVAL P)

  42
Now we have the capability to form polynomials and then evaluate them. EVAL gives us a very handy way of making FEXPRs much more powerful. Suppose that we wanted to write an addition function that used many arguments, no just two. We want to be able to write "(add* 1 2 3 . . .)" and get back their sums. Here's a possible FEXPR to do that.
:(DEFINE (ADD* (FLAMBDA (L)

:  (ADD-SUB L))))

   ADD*

:(DEFINE (ADD-SUB (LAMBDA (L)

:  (COND

:    ((NULL L) 0)

:    (T (ADD (CAR L) (ADD-SUB (CDR L))))))))

   ADD-SUB
Convince yourself that this works for "(add* 1 2 3 4 5)". Now try using SETQ to set up some values and use them in ADD*.
:(SETQ SOME 5)

  5

:(SETQ MORE 6)

  6

:(SETQ VALUES 7)

  7

:(ADD* VALUES MORE SOME)

    ** ERROR: BAD NUMERIC ARG **
      ADD :: ((CAR L ) (ADD-SUB (CDR L ) )
      )

+()

  NIL
What happened? Well, when recursion stopped down in ADD-SUB, it returned a 0 which the next level tried to add to the then-car of the list, SOME. Well, SOME is not a number! ADD can't deal with it like that! SOME is not an atom--it has a value, but its name isn't that value [it isn't like numeric atoms in that respect]. How do we get its value from its name? Right, EVAL! Here's a new definition of ADD-SUB that works:
:(DEFINE (ADD-SUB (LAMBDA (L)

:  (COND ((NULL L) 0)

:  (T (ADD (EVAL (CAR L))

:     (ADD-SUB (CDR L))))))))

  ADD-SUB
Convince yourself! Trace EVAL and ADD-SUB and see why.

Exercises to Evaluate in Your Head

  1. There is a way to write ADD* by changing ADD* itself instead of ADD-SUB. It also relies on EVAL but it does the evaluation before ADD-SUB ever gets called. Can you think of a way of doing this? If so, fix ADD*. If not, look up MAPCAR and recurse through this problem!
  2. Write a function called DEFUN that permits us to get rid of some of the irritating parentheses. We want to be able to do this:
    :(defun function-name (args list) body . . .)
    :(defun function-name fexpr (arg) body . . .)
    
    Have it fill the material that DEFINE wants to see and then call DEFINE. Notice that unless we say "fexpr", it makes an EXPR. This will need a special test.
  3. Write a function called NEWSETQ that counts the number of times it is used. It should look exactly like SETQ as far as its arguments are concerned. You should also keep the count in some global variable called NEWSETQ-USE-COUNT.

Answers

  1. (DEFINE (ADD* (FLAMBDA (L)
       (ADD-SUB (MAPCAR 'EVAL L))
    )))
    
  2. (DEFINE (DEFUN (FLAMBDA (L)
       (COND
         ((EQUAL (CADR L) 'FEXPR)
            (EVAL (CONS 'DEFINE
               (LIST (CONS (CAR L)
                 (LIST (CONS 'FLAMBDA (CDDR L)))
                     )
            ))
          ))
       (T (EVAL (CONS 'DEFINE
         (LIST (CONS (CAR L)
            (LIST CONS 'LAMBDA (CDR L))
              )
         ))
       ))
       )
    )))
    
  3. (DEFINE (NEWSETQ (FLAMBDA (L)
       (SETQ (NEWSETQ-USE-COUNT (ADD NEW-SETQ-USE-COUNT 1))
       (EVAL (CONS 'SETQ L))
    )))
    
Contents | Control Structures | Properties and Lambda Expressions