Structure and Interpretation of Compupter Programs 1
Chapter 1 of Structure and Interpretation of Compupter Programs.
 1.1 The elements of programming
 1.2 Procedures and the process they generate
 1.3 Formulating abstractions with higherorder procedure
1.1 The elements of programming
1.1.1 Expressions
It may be somewhat confusing at first because it departs significantly from the customary mathematical convention. Prefix notation has several advantages, however.

It can accommodate procedures that may take arbitrary number of arguments, as in the following examples:
(+ 35 21 12) (* 23 43 12)
No ambiguity can arise.

It extends in a straightforward way to allow combinations to be nested.
1.1.2 Naming and environment
A critical aspect of a programming language is the means it provides for …
Here are further examples of the use of define
:
(define pi 3.14159)
(define radius 10)
(* pi (* radius radius))
Nameobject can be created incrementally in successive interactions. This feature encourages the incremental development and testing of programs.
1.1.3 Evaluating combinations
1.1.4 Compound procedures
1.1.5 The substitution model for procedure application
 normalorder evaluation: fully expand and then reduce
 applicativeorder evaluation: evaluate the arguments and then apply
1.1.6 Coditional Expressions and predicates
Exercise 1.5
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
(test 0 (p))
If the interpreter uses applicativeorder, the last call will lead to an infinite recusion because the second parameter will always be evaluated. If the interpreter uses normalorder the last call will just return 0.
1.1.7 Example: square roots by Newton’s method
Newton’s method describes the way to find the root of a function \(f(x)\), i.e., such a \(x\) such that \(f(x) = 0\).
We can derive the Newton’s method as the following:
\[\begin{align} f(x) &\approx f(x_0) + f'(x_0)(x  x_0) = 0\quad \text{(Taylor expansion)} \\ &\Rightarrow x = x_0  \frac{f(x_0)}{f'(x_0)} \end{align}\]If we want to find the square root of \(z\), i.e., \(x^2 = z\) we would have \(f(x) = x^2 z\), assuming we have an initial guess \(x_0\) then according to the above drivation we can get the next better value as
\[x = x_0  \frac{x_0^2  z}{2x_0} = \frac{x_0 + \frac{z}{x_0}}{2}.\]If the change \(\frac{x_0^2  z}{2x_0} = \frac{x_0  z/x_0}{2}\) is very small we can terminate the iteration process.
(define (average x y)
(/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess)))
(define (goodenough? guess x)
(< (abs ( guess (/ x guess))) 0.00001))
(define (sqrtiter guess x)
(if (goodenough? guess x)
guess
(sqrtiter (improve guess x)
x)))
(define (mysqrt x)
(sqrtiter 1.0 x))
Excercise 1.6
(define (newif predicate thenclause elseclause)
(cond (predicate thenclause)
(else elseclause)))
At this time newif
is a function so every time we call it we need to evaluate all its three parameters, which may lead to an infinite recusion because the third parameters will always be evaluted.
Excercise 1.7
Terminating the iteration process when the change \(\frac{x_0^2  z}{2x_0} = \frac{x_0  z/x_0}{2}\) is small enough.
(define (goodenough? guess x)
(< (abs ( guess (/ x guess))) 0.00001))
1.1.8 Procedure as BlackBox abstractions
(define (mysqrt x)
(define (improve guess)
(average guess (/ x guess)))
(define (goodenough? guess)
(< (abs ( guess (/ x guess))) 0.00001))
(define (sqrtiter guess)
(if (goodenough? guess)
guess
(sqrtiter (improve guess)
x)))
(sqrtiter 1.0))
1.2 Procedures and the process they generate
1.2.1 Linear recursion and iteration
(define (factorial n)
(if (= n 0)
1
(* n (factorial ( n 1)))))
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))
 Recursive process. The substitution model reveals a shape of expansion followed by contraction. The expansion occurs as the process builds up a chain of deferred operations. The contraction occurs as the operations are actually performed.
 Iteration process. Iteration process in Lisp is characterized by recursive procedure. In general, an iterative process is one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process evolves.
Exercise 1.9
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
The first process is a recursive process as it involves the deferred operation inc
, while the second process is an iterative process since at any give time its state can be summarized by the variables a, b
.
Exercise 1.10
Ackermann’s function.
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A ( x 1)
(A x ( y 1))))))
(A 0 n); 2n
(A 1 n); 2^n
(A 2 n); 2^2^2...^2
1.2.2 Tree Recursive
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib ( n 1))
(fib ( n 2))))))
Let the number of leaves of Fib(n) be LFib(n) then we can conclude that LFib(n) = LFib(n1) + LFib(n2) as well as LFib(1) = LFib(0) = 1, which implies LFib(n) = Fib(n+1).
Fib(n) is the closest integer to \(\phi^n / \sqrt{5}\) where \(\phi = (1 + \sqrt{5})/2\).
\[\phi^2 = \phi + 1\]The space required grows linearly with the input, because we need keep track only of which nodes are above us in the tree at any point in the computation, i.e., the space required is proportional to the maximum depth of the tree.
Iterative process, let \(a, b = 1, 1\) then repeatedly apply the simultaneous transformations
\[\begin{align} & a \leftarrow a+ b \\ & b \leftarrow a \end{align}\](define (fib n)
(define (fibiter a b count)
(if (= count 0)
b
(fibiter (+ b a) a ( count 1))))
(fibiter 1 0 n))
Counting Change
The number of ways to change amount \(a\) using \(n\) kinds of coins equals
 the number of ways to change amount \(a\) using all but the first kind of coins, plus
 the number of ways to change amount \(ad\) using all \(n\) kinds of coins, where \(d\) is the denomination of the first kind of coin.
Recursively reducing the problem into smaller ones:
 If \(a\) is exactly 0, we should count that as 1 way to make change.
 If \(a\) is less than 0, we should count that as 0 way to make change.
 If \(n\) is 0, we should count that as 0 way to make change.
(define (firstdenomination kindsofcoins)
(cond ((= kindsofcoins 1) 1)
((= kindsofcoins 2) 5)
((= kindsofcoins 3) 10)
((= kindsofcoins 4) 25)
((= kindsofcoins 5) 50)))
(define (cc amount kindsofcoins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kindsofcoins 0)) 0)
(else (+ (cc amount
( kindsofcoins 1))
(cc ( amount
(firstdenomination kindsofcoins))
kindsofcoins)))))
(define (countchange amount)
(cc amount 5))
Exercise 1.11
\[f(n) = \begin{cases} n, \quad n < 3\\ f(n1) + 2f(n2) + 3f(n3), \quad n \geq 3 \end{cases}\];; recursive process
(define (f n)
(cond ((< n 3) n)
(else (+ (f ( n 1))
(* 2 (f ( n 2)))
(* 3 (f ( n 3)))))))
;; iterative process
(define (fiter n)
(define (iter a b c counter)
(cond ((= counter 0) a)
(else (iter (+ a (* 2 b) (* 3 c))
a
b
( counter 1)))))
(cond ((< n 3) n)
((iter 2 1 0 ( n 2)))))
Exercise 1.12
(trinum n m)
computes the m
th element in n
row.
(define (trinum n m)
(cond ((or (= n 1) (= m 1) (= m n)) 1)
(else (+ (trinum ( n 1) ( m 1))
(trinum ( n 1) m)))))
Exercise 1.13
1.2.3 Orders of Growth
Exercise 1.1.5
(define (cube x) (* x x x))
(define (p x) ( (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
a. Three times.
b. Both the space and time complexity are \(O(\log(a))\).
1.2.4 Exponentiation
\[\begin{align} b^n = (b^{n/2})^2 \quad &\text{if $n$ is even} \\ b^n = b\cdot b^{n1} \quad &\text{if $n$ is odd} \end{align}\](define (expt b n)
(if (= n 0)
1
(* b (expt b ( n 1)))))
(define (exptiter b n)
(define (iter counter product)
(if (= counter 0)
product
(iter ( counter 1) (* product b))))
(iter n 1))
(define (square x)
(* x x))
(define (fastexpt b n)
(cond ((= n 0) 1)
((even? n) (square (fastexpt b (/ n 2))))
(else (* b (fastexpt b ( n 1))))))
Exercise 1.16
(define (fastexptiter b n)
(define (iter a base counter)
(cond ((= counter 0) a)
((even? counter) (iter a
(* base base)
(/ counter 2)))
(else (iter (* a base)
base
( counter 1)))))
(iter 1 b n))
a
absorbs base
into it only when counter
is odd otherwise raising base
.
Exercise 1.19
\(T_{pq}\) transforms the pair \((a, b)\) according to \(a \leftarrow bq + aq + ap\) and \(b \leftarrow bp + aq\).
Applying \(T_{pq}\) and get
\[\begin{align} a_1 &\leftarrow b_0 q + a_0 q + a_0 p \\ b_1 &\leftarrow b_0 p + a_0 q \end{align}\]Applying \(T_{pq}\) again and get
\[\begin{align} a_2 &\leftarrow b_0 (q^2 + 2pq) + a_0 (q^2 + 2pq) + a_0 (p^2 + q^2) \\ b_2 &\leftarrow b_0 (p^2 + q^2) + a_0 (q^2 + 2pq) \end{align}\]which equals to applying the transformation \(T_{p'q'}\) of the same form with \(p' = p^2 + q^2\) and \(q' = q^2 + 2pq\).
(define (fastfib n)
(fastfibiter 1 0 0 1 n))
(define (fastfibiter a b p q count)
(cond ((= count 0) b)
((even? count)
(fastfibiter a
b
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))
(/ count 2)))
(else (fastfibiter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
( count 1)))))
1.2.5 Greatest Common Divisors
The idea of the algorithm is based on the observation, if \(r\) is the remainder when \(a\) is divided by \(b\), then the common divisors of \(a\) and \(b\) are precisely the same as the common divisors of \(b\) and \(r\).
\[a = k \cdot b + r \Rightarrow \text{GCD}(a, b) = \text{GCD}(b, r)\](define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
If the Euclid’s Algorithm requires \(k\) steps to compute the GCD of some pair, then the smaller number in the pair must be greater than or equal to the \(k\)th Fibonacci number.
Exercise 1.20
When using the normalorder evaluation rule, in the \(i\)th time calling gcd
the depth of remainder
will be \(i\) which looks like (remainder 6 (remainder 40 (remainder 206 40)))
. If the entire process requires \(k\) steps, then the total number of remainder
operations is \(\sum_{i=1}^k i = \Theta(k^2)\).
When using the applicativeorder evaluation rule, the remainder
operations required is just \(\Theta(k)\).
1.2.6 Example: Testing for Primality
Searching for divisors
(define (smallestdivisor n)
(finddivisor n 2))
(define (finddivisor n testdivisor)
(cond [(> (square testdivisor) n) n]
[(divides? testdivisor n) testdivisor]
[else (finddivisor n (+ testdivisor 1))]))
(define (divides? a b)
(= (remainder b a) 0))
(define (prime? n)
(= n (smallestdivisor n)))
The Fermat test
If \(n\) is a prime number and \(a\) is any positive number less than \(n\), then \(a^n \equiv a\ (\text{mod}\ n)\).
(define (expmod base exp m)
(cond [(= exp 0) 1]
[(even? exp)
(remainder (square (expmod base (/ exp 2) m))
m)]
[else
(remainder (* base (expmod base ( exp 1) m))
m)]))
(define (expmoditer base exp m)
(define (iter a b counter)
(cond [(= counter 0) a]
[(even? counter)
(iter a (square b) (/ counter 2))]
[else
(iter (remainder (* a b) m) b ( counter 1))]))
(iter 1 base exp))
(define (fermattest n)
(define (tryit a)
(= (expmod a n n) a))
(tryit (+ 1 (random ( n 1)))))
(define (fastprime? n times)
(cond [(= times 0) #t]
[(fermattest n) (fastprime? n ( times 1))]
[else #f]))
Exercise 1.25
Integer overflows.
Exercise 1.26
At each step when exp
is even, the procedure grows out two branches from the current node. And the tree corresponding to the first call will have depth \(\log(n)\), thus the number of leaves in the tree is around \(2^{\log(n)} = n\).
1.3 Formulating abstractions with higherorder procedure
1.3.1 Procedures as Arguments
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
(define (sumcubes a b)
(sum cube a inc b))
(define (sumintegers a b)
(sum (lambda (x) x) a inc b))
(define (pisum a b)
(define (piterm x)
(/ 1.0 (* x (+ x 2))))
(define (pinext x)
(+ x 4))
(sum piterm a pinext b))
Exercise 1.29
Simpson’s Rule
\(\int_a^b f = \frac{h}{3}[y_0 + 4y_1 + 2y_2 + 4y_3 + 2y_4 + \ldots + 2y_{n1} + 4y_{n1} + y_n]\) where \(h = (ba)/n\), for some even integer \(n\), and \(y_k = f(a+kh)\).
(define (simpsonintegral f a b n)
(define (simpsonsum acc f v k h)
(cond [(= k (+ n 1)) acc]
[(or (= k 0) (= k n))
(simpsonsum (+ acc (f v))
f
(+ v h)
(+ k 1)
h)]
[(even? k)
(simpsonsum (+ acc (* 2 (f v)))
f
(+ v h)
(+ k 1)
h)]
[else
(simpsonsum (+ acc (* 4 (f v)))
f
(+ v h)
(+ k 1)
h)]))
(define h (/ ( b a) n))
(* (simpsonsum 0 f a 0 h)
(/ h 3)))
Exercise 1.30
(define (sumiter term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result))))
(iter a 0))
1.3.2 Constructing procedure using lambda
(lambda (x) (+ x 4))
Using let
to create local variables
The general form of a let
expression (in Racket) is
(let ([<var1> <exp1>]
[<var2> <exp2>]
[<var3> <exp3>]
...
[<varn> <expn>])
<body>)
which is interpreted as an alternate syntax for
((lambda (<var1> ... <varn>)
<body>)
<exp1>
...
<expn>)
The variables’ values are computed outside the let
. For example, if the value of x
is 2, the expression
(let ([x 3]
[y (+ x 2)])
(* x y))
will have value 12.
However, if we want to use the local variables defined in previously, we can use let*
in Racket such as
(let* ([x 3]
[y (+ x 2)])
(* x y))
the value is 15.
Exercise 1.34
(f f) =>
(f 2) =>
(2 2) => "application: not a procedure;"
Procedures as General Methods
Finding roots of equations by the halfinterval method
(define (search f negpoint pospoint)
(define (closeenough? x y)
(< (abs ( x y)) 0.001))
(let ([midpoint (average negpoint pospoint)])
(if (closeenough? negpoint pospoint)
midpoint
(let ([testvalue (f midpoint)])
(cond [(positive? testvalue)
(search f negpoint midpoint )]
[(negative? testvalue)
(search f midpoint pospoint)]
[else midpoint])))))
(define (halfintervalmethod f a b)
(let ([avalue (f a)]
[bvalue (f b)])
(cond [(and (negative? avalue) (positive? bvalue))
(search f a b)]
[(and (negative? bvalue) (positive? avalue))
(search f b a)]
[else
(error "Values are not of opposite sign" a b)])))
The root between 2 and 4 of \(\sin x = 0\):
(halfintervalmethod sin 2.0 4.0)
\(x^3  2x  3 = 0\) between 1 and 2:
(halfintervalmethod (lambda (x) ( (cube x) (* 2 x) 3)) 1.0 2.0)
Finding fixed points of functions
A number \(x\) is called a fixed point of a function \(f\) if \(x\) satisfies the equation \(f(x) = x\).
(define (fixedpoint f firstguess)
(define (closeenough? v1 v2)
(< (abs ( v1 v2)) tolerance))
(define (try guess)
(let ([next (f guess)])
(if (closeenough? guess next)
next
(try next))))
(try firstguess))
Defining sqrt
using fixed points method:
(define (sqrt x)
(fixedpoint (lambda (y) (average y (/ x y)))
1.0))
in which we used \(y \mapsto \frac{1}{2}(y + x/y)\).
Exercise 1.35
\(\phi\) is the root of equation \(x^2  x  1 = 0\) which implies the transformation \(x \mapsto x + 1/x\)
(define (goldratio)
(fixedpoint (lambda (x) (+ 1 (/ 1 x)))
1.0))
Exercise 1.36
(define (logxx)
(fixedpoint (lambda (x) (/ (log 1000) (log x)))
2.0))
(define (logxxaverage)
(fixedpoint (lambda (x) (average (/ (log 1000) (log x)) x))
2.0))
Exercise 1.37
(define (contfrac n d k)
(define (frac i)
(if (= i k)
(/ (n i) (d i))
(/ (n i)
(+ (d i) (frac (+ i 1))))))
(frac 1))
(define (contfraciter n d k)
(define (fraciter i result)
(if (= i 0)
result
(fraciter ( i 1)
(/ (n i)
(+ (d i) result)))))
(fraciter k 0))
\(k\) should be 5 to get an approximation that is accurate to 4 decimal places.
(contfrac (lambda (i) 1.)
(lambda (i) 1.)
100)
(contfraciter (lambda (i) 1.)
(lambda (i) 1.)
1000)
Exercise 1.38
(define (approximatee k)
(define (d i)
(if (= (remainder (+ i 1) 3) 0)
(* 2
(/ (+ i 1) 3))
1.))
(+ 2
(contfraciter (lambda (i) 1.)
d
k)))
Exercise 1.39
(define (tancf x k)
(define (n i)
(if (= i 1)
x
( (* x x))))
(contfraciter n
(lambda (i) ( (* 2 i) 1.))
k))
1.3.4 Procedures as returned values
\(f(x)\) is a differentiable function, then a solution of the equation \(f(x) = 0\) is a fixed point of the function
\[x \mapsto x  \frac{f(x)}{f(x)'}\](define (deriv f)
(lambda (x)
(/ ( (f (+ x dx)) (f x))
dx)))
(define dx 0.00001)
(define (newtontransform f)
(lambda (x)
( x (/ (f x) ((deriv f) x)))))
(define (newtonsmethod f guess)
(fixedpoint (newtontransform f) guess))
(newtonsmethod (lambda (x) ( (square x) 2)) 1.0)
Exercise 1.40
(define (cubic a b c)
(lambda (x)
(+ (* x x x) (* a x x) (* b x) c)))
Exercise 1.41
(define (double f)
(lambda (x) (f (f x))))
(((double (double double)) inc) 5); > 21
Exercise 1.42
(define (compose f g)
(lambda (x) (f (g x))))
((compose square inc) 6); > 49
Exercise 1.43
(define (repeated f n)
(define (fi i)
(if (= i 1)
f
(compose f (fi ( i 1)))))
(fi n))
(define (repeatediter f n)
(define (iter i r)
(if (= i 1)
r
(iter ( i 1) (compose f r))))
(iter n f))
((repeatediter square 2) 5); > 625