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.

## Leave a comment

Comments feed for this article