We’re going to introduce a simple model for how the interpreter evaluates expression that you type in, and then go on to look at an important feature of Lisp (well, an important feature of any programming language…): conditionals.

1.1.5 The substitution model for procedure application

A model for how the interpreter applies primitive procedures to arguments is as follows:

To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

Let’s illustrate this by evaluating

(sum-of-squares 3 4)

which expands to

(+ (square 3) (square 4))

Now, (square 3) evaluates to 9 and (square 4) evaluates to 16, so we have

(+ 9 16)

and finally we get the result

25

This is called the substitution model for procedure application. This is not how the interpreter really works, but it is a simple model that captures the spirit.

Applicative order and normal order

We said that the interpreter first evaluates the operator and operands, and then applies the procedure to the resulting arguments. This is not the only way to evaluate compound procedures. An alternative model does not evaluate any expressions until their results are needed. Instead, it substitutes expressions for parameters until it obtains an expression involving only primitives, and then performs the whole evaluation.

For example, (sum-of-squares 3 4) would be evaluated first to

(+ (square 3) (square 4))

and then to

(+ (* 3 3) (* 4 4))

and now that we only have primitives, we can begin evaluating the whole expression:

(+ 9 16)

and finally

25

This is called normal-order evaluation, as opposed to applicative-order evaluation which is what the compiler actually uses. Normal-order evaluation is less efficient (since you can end up evaluating the same expression multiple times) and becomes problematic when we leave the realm of procedures that can be modeled by substitution.

1.1.6 Conditional expressions and predicates

There is a special construct in Lisp for doing case analysis, called cond which stands for “conditional”. It is used as follows:

> (define (abs x)
    (cond ((> x 0) x)
          ((= x 0) 0)
          ((< x 0) (- x))))

The general form of a conditional expression is

(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>))

i.e. it consists of the symbol cond followed by pairs of expressions in parentheses:

(<p> <e>)

called clauses. The first expression in each pair must be a predicate, i.e. an expression that evaluates to true or false.

Conditional expressions are evaluated as follows. The predicate <p1> is evaluated first. If its value is false then <p2> is evaluated, and so on. This continues until a predicate is found whose value is true, in which case the interpreter returns the value of the appropriate consequent <e> as the value of the cond expression. If none of the predicates evaluate to true, then the value of the cond is undefined.

There is a special symbol else which can be used in place of the final predicate. This causes the cond to return the value of the final expression <e>. We could also write the absolute value procedure as:

> (define (abs x)
    (cond ((< x 0) (- x))
          (else x)))

There is also the special form if, a restricted form of conditional that can be used when there are exactly two mutually exclusive cases. This gives another way to write the absolute value procedure:

> (define (abs x)
    (if (< x 0)
        (- x)
        x))

The general form of an if expression is

(if <predicate> <consequent> <alternative>)

To evaluate the expression, the interpreter first evaluates the <predicate> part. If it is true, then it returns the value of <consequent> as the value of the if, otherwise it returns the value of <alternative>. It is important to realise that only one of the <consequent> and the <alternative> are ever evaluated.

In addition to primitive predicates like and = there are also logical composition operators, enabling us to construct compound predicates. The three most common are

(and <e1> ... <en>)

which returns false if any of the <e> evaluate to false, and otherwise returns true,

(or <e1> ... <en>)

which returns true if any of the <e> evaluate to true, and otherwise returns false, and

(not <e>)

which returns true if <e> evaluates to false, and false if evaluates to true.

As an example of use, we could define a predicate to test whether one number is greater than or equal to another by

> (define (>= x y)
    (not (< x y)))

and we can use it:

> (>= 10 2)
#t
> (>= 2 10)
#f

Next I’ll look at some of the exercises.

Advertisements