Chapter 1.1 (Scheme Basics)

June 10, 2025

1.1.3 Evaluating Combinations

The procedure the interpreter follows to evaluate combinations is as follows:

Evaluate the sub-expressions of the combination
Apply the procedure that is the value of the left-most subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

These rules are recursive in nature, since sub-expressions can themselves exists out of expressions. For example, evaluating the following:

(* (+ 2 (* 4 6)) (+ 3 5 7))

Requires the evaluation rule to be applied to 4 different combinations

(* 4 6)
(+ 3 5 7)
(+ 2 24) #24 being the result of (* 4 6)
(* 26 15) #both being the result of previous evaluations

1.1.4 Compound Procedures

tldr; Compound procedures are procedures built from other procedures. They are used in exactly the same way as primitive procedures, and their signatures are indistinguisable from each other.

1.1.5 The substitution model for procedure application

Lets illustrate the substitution model by evaluating the combination (f 5) where f is

(define (f a)
	(sum-of-squares (+ a 1) (* a 2)))

(sum-of-square (+ 5 1) (* 5 2))

(+ (square (+ 5 1)) (square (* 5 2)))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
followed by the reductions
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

This “fully expand and then reduce” evaluation model is called the normal-order evaluation. It basically keeps substituting operand expressions for expressions until the expression only contains primitive operators. It would then start evaluating. This is different from the evaluation the interpreter actually uses, which is called the applicative-order evaluation which is done as follows:

(sum-of-square (+ 5 1) (* 5 2))

(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

Do keep in mind that interpreters do not evaluate expressions by substituting text like we do here. These models are basically here to make it simpler to reason about evaluation.

1.1.6 Conditional Expressions and Predicates

One of the special forms in Lisp (Expressions that do not follow the normal evaluation rules specified earlier) is the case analysis. Its basically a switch statement and has the following syntax taking abs as an example:

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

or the more general form:

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

The combination of the predicate p and the consequent expressions e is called a clause. The predicates are evaluated one after the other, and as soon as a predicate returns true, its corresponding expression evaluated and returned. If no predicates evaluate to true, it returns undefined. A “better” way to write this case analysis would be:

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

This is a special case, and makes sure the procedure never returns undefined.

If a case analysis is restricted to precisely 2 cases, we can use the if expression

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

In addition to the logical < = > operators, there are also logical composition operators. The three most frequently used ones are:

(and <e1> <e2> ... <en>). The expressions are evaluated one by one, left-to-right order. if any <e> evaluates to false, the value of the and is false and the rest of the expressions are NOT evaluated
(or <e1> <e2> ... <en>). The expressions are evaluated one by one, left-to-right order. if any <e> evaluates to true, that value is returned, and the rest of the expressions are NOT evaluated. If all <e> evaluate to false, the value of the or expression is false as well.
(not <e>) inverts the result of evaluating <e>.

1 and 2 are special forms, NOT procedures, because the sub-expressions are not necessarily all evaluated. not is an ordinary procedure, as <e> is always full evaluated.

Exercise 1.1 What is the result of the following expressions?

10 -> 10
-
(+ 5 3 4) -> 12
-
(- 9 1) -> 8
-
(/ 6 2) -> 3
-
(+ (* 2 4) (- 4 6)) -> 6
-
(define a 3) -> nothing
-
(define b (+ a 1)) -> nothing
-
(+ a b (* a b)) ->
(+ 3 (+ 3 1)(* 3 (+ 3 1))) ->
(+ 3 4 (* 3 4)) ->
(+ 3 4 12) -> 19
-
(= a b) -> #f
-
(if (and (> b a) (< b (* a b))) b a) ->
(if (and #t #t) b a) -> 4 #b
-
(cond ((= a 4) 6)
	((= b 4) (+ 6 7 a))
	(else 25)) ->
(+ 6 7 3) -> 16
-
(+ 2 (if (> b a) b a)) ->
(+ 2 4) -> 6
-
(* (cond ((> a b) a)
		((< a b) b)
		(else -1))
	(+ a 1)) ->
(* 4 (+ 3 1)) -> 16

Exercise 1.2 Translate the following expression into prefix notation: $\frac{5 + 4 + \left( 2 - \left( 3 - \left( 6 + \frac{4}{5} \right) \right) \right) }{ 3(6 - 2)(2-7)}$

(/
	(+ 5 (+ 4 (- 2 (- 3 (+ 6 (/ 4 5))))))
	(* 3 (- 6 2)(- 2 7)))

Exercise 1.3 Define a procedure that takes 3 numbers as arguments and returns the sum of squares of the two larger numbers.

(define (f a b c)
	(define (square x) (* x x))
	(define (sum-of-squares x y) (+ (square x)(square y)))

	(cond (( and (< x y) (< x z)) (sum-of-squares y z))
		((and (< y x) (< y z)) (sum-of-squares x z))
		(else (sum-of-squares x y)))))

Exercise 1.4 Use observation to describe the behaviour of the following procedure:

(define (a-plus-abs-b a b)
	((if (> b 0) + -) a b))

In lisp, an operator is just an expressions, so it can be the result of a procedure. In this case we check if b is larger than 0. If so, we just add 2 positive integers together using the + procedure. If b is smaller than 0, we need the - procedure to cancel out the - from b.

Exercise 1.5 Given the following two procedures

(define (p) (p))
and
(define (test x y)
	(if (= x 0) 0 y))

And evaluation as follows: (test 0 (p))

How do both applicative-order evaluation and normal-order evaluation look in this case?

Applicative Order Evaluation
(test 0 (p))
Evaluating each element of the combination:
(if (= 0 0) 0 (p)) -> LOOP as it keeps evaluating (p)

Normal Order Evaluation
(test 0 (p))
Fully expand and then reduce only when needed
(if (= 0 0) 0 (p))
since (= 0 0) -> #t (p) is never evaluated

1.1.7 Example: Square Roots by Newton’s Method

Exercise 1.6 Given a new version of if

(define (new-if predicate then-clause else-clause)
	(cond (predicate then-clause)
		(else else-clause)))

If we use that to implement a new version of sqrt-iter

(define (sqrt-iter guess x)
	(new-if (good-enuf? guess x)
	guess
	(sqrt-iter (improve guess x) x)))

Why would that not work?

Because new-if is not a special form, but just a regular function, normal evaluation rules are applied by the interpreter. Remember, they are as follows:

Evaluate the sub-expressions of the combination

Apply the procedure that is the value of the left-most subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

This means each sub-expression of new-if will be evaluated before the procedure is applied. And because the else-clause is (srt-iter (improve guess x) x) we end up in an infinite evaluation loop.

Exercise 1.7 The following good-enuf? method is not very effective for finding the square roots of very small numbers as well as very large numbers:

(define (good-enuf? guess x)
	(< (abs (- (square guess) x)) 0.001))

Explain why. For very small numbers, since we are comparing within a maring of error of 0.001, any number below that we need to find the square of is just immensely inaccurate. It just exits out of good-enuf too early. One way you could improve that is by making the delta smaller, say 0.0000000001 or something arbitrary, but then you will run into issues when computing (sq 0.0000000000000001). How realistic that is?

Exercise 1.8 The method for Cube Roots is based on the fact that if y is an approximation of the cube root of x, then a better approximation is given by: $\frac{x/y^2 + 2y}{3}$ Implement a cube-root procedure analogous to the square root procedure.

(define (cube x) (* x x x))
(define (good-enuf? guess x)
	(< (abs (- (cube guess) x)) 0.0000001))
(define (improve guess x)
	(/ (+ (* 2 guess) (/ x (square guess))) 3))
(define (cube-iter guess x)
	(if (good-enuf? guess x)
	guess
	(cube-iter (improve guess x) x)))

1.1.8 Procedures as black box abstractions

sqrt-iter and cube-iter are the first examples of processes defined by a set of procedures. They are also both recursive, that is, the procedure is defined in terms of itself. Another important observation is that the problem of computing a square root breaks up naturally into a number of subproblems: How to tell whether a guess is good enough, how to improve a guess, and so on. The entire sqrt procedure closely mimics the decomposition of the problem into subproblems.

The importance of this decomposition is not the dividing into parts, that can happen with any arbitrary ruleset. Rather, it is crucial that each procedure accomplishes an identifiable task that can be used as a module. This module can then be used as an abstraction of a procedure, a so-called procedural abstraction. At the level of sqrt-iter we can just assume modules like average or square do what they are supposed to do.

Internal definitions and block structure So far, the existing program existed of a couple of sub-procedures which were all defined outside the body of the square or cube method. While this can be helpfull, we can also internalize all these methods so we don’t expose them.

(define (sqrt x)
	(define (good-enuf? guess x)
		(< (abs (- (square guess) x)) 0.0001))
	(define (improve guess x) (average guess (/ x guess)))
	define (sqrt-iter guess x)
		(if (good-enuf? guess x)
		guess
		(sqrt-iter (improve guess x) x)))
	(sqrt-iter 1.0 x))

This kind of nesting of definitions is called block structure. And while this makes sure there are less naming clashes (since all the “helper” procedures do not leak out) it has another benefit. Since the variable x is bound to the definition of sqrt, there is no need to redefine it in all the signatures of all the helper functions, thus the following procedure is equivalent

(define (sqrt x)
	(define (good-enuf? guess)
		(< (abs (- (square guess) x)) 0.001))
	(define (improve guess) (average guess (/ x guess)))
	(define (sqrt-iter guess)
		(if (good-enuf? guess)
		guess
		(sqrt-iter (improve guess))))
	(sqrt-iter 1.0))

X is a free variable inside the procedure of sqrt. This disciple is called lexical scoping.