Notes on: Structure and Interpretation of Computer Programs (Abelson & Sussman, 2002) - WIP

The book can be found here.

Building Abstractions with Procedures

The Elements of Programming

A programming language is our mental framework for organising ideas about process. It provides three mechanisms for combining simple ideas such that they together form more complex ideas:

  • primitive expressions, which represent the simplest entities the language is concerned with,
  • means of combination, by which compound elements are built from simpler ones, and
  • means of abstraction, by which compound elements can be named and manipulated as units.

Expressions

Expressions such as these, formed by delimiting a list of expressions within parentheses in order to denote procedure application, are called combinations. the leftmost element in the list is called the operator , and the other elements are called operands . The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands.

Placing the operator to the left of the operands is called prefix-notation.

Let's take a look at the nesting of expressions:

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

If we align the operands vertically as above we pretty-print our code.

Naming and the Environment

Every programming language uses names which identify a variable whose value is the object. In the Scheme dialect of list we use define. In Lisp every expression has a value.

Lisp programmers know the value of everything but the cost of nothing (Alan Perlis)

Here is an example of how to use define:

(define pi 3.14159)
(define radius 10)
(* pi (* radius radius))

(define circumference (* 2 pi radius))
circumference

In order to keep track of the name-object pairs, the interpreter maintains a memory called the (global) environment.

Evaluating Combinations

Let us consider the following recursive evaluation rule:

To evaluate a combination, do the following:

  1. Evaluate the subexpressions of the combination.
  2. Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

Hence, the following code

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

can be represented in the following tree strucure:

This “percolating upwards” is called tree accumulation. This evaluation rule does not apply to so-called special forms, such as define, which each have their own evaluation rule.

Compound Procedures

Any programming language must have:

  • Numbers and arithmetic operations are primitive data and procedures. Nesting
  • of combinations provides a means of combining opera- tions. Definitions that
  • associate names with values provide a limited means of abstraction.

Next, we need procedure definitions which open a whole new realm of possibility.

Let's define a compound procedure called square:

(define (square x) (* x x))

Now we can easily define another procedure that makes use of square:

(define (square x) (* x x))
(define (sum-of-squares x y)
  (+ (square x) (square y)))
(sum-of-squares 3 4)

which evaluates to 25. We can take this even further:

(define (square x) (* x x))
(define (sum-of-squares x y)
  (+ (square x) (square y)))
(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))
(f 5)

which gives us 136.

The Substitution Model for Procedure Application

Let us consider the combination from above to illustrate the subsitution model:

(f 5)
;; retrieve the body of f and replace parameters with the arguments
(sum-of-squares (+ 5 1) (* 5 2))
;; apply sum-of-square to 6 and 10
(+ (square 6) (square 10))
;; reduce the expression by using the definition of square
(+ (* 6 6) (* 10 10))
(+ 36 100)

NB: This is not how the interpreter really works, as we'll see later. The subsitution model serves the purpose of providing an entry point to thinking about procedure application.

Applicative vs. Normal Order

The “first evaluate arguments and then apply procedures” way of doing things that we used above (applicative-order evaluation) is not the only way.

The other evaluation model is the “fully expand and then reduce” model, which is called normal-order evaluation and illustrated below:

(f 5)
(sum-of-squares (+ 5 1) (* 5 2))
(+    (square (+ 5 1))      (square (* 5 2))  )
(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))
(+         (* 6 6)             (* 10 10))
(+           36                   100)
                    136

Conditional Expression and Predicates

Often, we want to do different things depending on the result of a test (case analysis). In Lisp we use cond to do that. The first expression in each pair is called the predicate (either true or false) and the second one is the consequent expression (value returned if predicate is true).

(define (abs x)
;;      (<p>   <e>)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

;; use else when to specify what to return if all clauses have been bypassed
(define (abs x)
  (cond ((< x 0) (- x))
        (else x)))

;; use if if you have exactly two cases in the case analysis
(define (abs x)
  (if (< x 0)
      (- x)
      x))

Of course, we should be able to construct compound predicates also with logical composition operations and not purely numerical ones:

;; specify a number range: 5 < y < 10
(and (> x 5) (< x 10))

;; greater than or equal
(define (>= x y)
  (or (> x y) (= x y)))

;; alternatively:
(define (>= x y)
  (not (< x y)))
Exercise 1.1

Below is a sequence of expressions. What is the result printed by the interpreter in response to each expression? Assume that the sequence is to be evaluated in the order in which it is presented.

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

Translate the following expression into prefix form:

\[ \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)))
;; -37/150
Exercise 1.3

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

(define (sq x)
  (* x x))

(define (ssq x y)
  (+ (sq x) (sq y)))

(define (max3 x y z)
  (cond ((> x y) (cond ((> x z) x)
                       (z)))
        ((> y z) y)
         (z)))

(define (max2 x y)
  (if (> x y) x y))

(define (larger-ssq x y z)
  (cond ((= (max3 x y z) x) (ssq x (max2 y z)))
        ((= (max3 x y z) y) (ssq y (max2 x z)))
        ((= (max3 x y z) z) (ssq z (max2 x y)))))
Exercise 1.4

Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:

(define (a-plus-abs-b a b)
  ;; the if-expression evaluates to a "+" or "-" depending on the clause (> b 0)
  ((if (> b 0) + -) a b))
Exercise 1.5

Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:

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

(test 0 (p))

Using normal-order evaluation, the last expression evaluates to 0 as the infinite-loop-producing procedure p is not evaluated. This is not true for applicative-order evaluation, where the arguments are evaluated first. Here, the process ends in an infinite loop.

Example: Square Roots by Newton's Method

There is a difference between a mathematical function of a square root (which can be used to recognise a square root or derive some interesting insights about it) and a procedure to generate a squre root.

For generating sqaure roots, we can use Newton's method of approximation:

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

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

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

(define (sqrt x)
  (sqrt-iter 1.0 x))

The sqrt-iter procedure also underlines that iteration can be achieved using no special construct but the ability to call a procedure

Exercise 1.6

Alyssa P. Hacker doesn't see why if needs to be provided as a special form. “Why can't I just define it as an ordinary procedure in terms of cond ?” she asks. Alyssa's friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))
;; demo
(new-if (= 2 3) 0 5)
;; 5
(new-if (= 1 1) 0 5)
;; 0

Now, Alyssa wants to use new-if for the square-root program:

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

What happens when Alyssa aempts to use this to compute square roots? Explain.

The interpreter returns the following error message:

;Aborting!: maximum recursion depth exceeded

This is due to the fact that the new-if procedure does not share the property of the if special form to only evaluate the consequence when the predicate evaluates to #t. Hence, infinite recursion whenever we call new-if and there one of the consequents is a function call.

Exercise 1.7

The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arith- metic operations are almost always performed with lim- ited precision. this makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses this kind of end test. Does this work beer for small and large numbers?

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

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

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? cur next x)
  (< (/ (abs (- cur next)) x) 0.0000001))

(define (sqrt x)
  (sqrt-iter 1.0 x))
Exercise 1.8

Newton's method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a beer approximation is given by the value

\[ \frac{x / y^{2}+2 y}{3} \]

Use this formula to implement a cube-root procedure analogous to the square-root procedure

(define (cbrt-iter guess x)
  (if (good-enough? guess (improve guess x) x)
      guess
      (cbrt-iter (improve guess x)
                 x)))

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

(define (square x) (* x x))

(define (improve guess x)
  (/ (+ (/ x (square guess)) (* 2 guess)) 3))

(define (good-enough? cur next x)
  (< (/ (abs (- cur next)) x) 0.0000001))

(define (cbrt x)
  (cbrt-iter 1.0 x))

Procedures as Black-Box Abstractions

The procedure definition binds its formal parameters such that they become bound variables. If variables are not bound, they are free. The set of expressions for which there is a binding defines its name is called scope of that name.

Often it can be useful to “hide” or localise the subprocedures of a given procedure by utilising what is called a block structure. In the case of our sqrt function, we could write:

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

As can be inspected above, x is a free variable in the internal procedure definitions. This discipline is called lexical scoping, which the authors define as follows:

Lexical scoping dictates that free variables in a procedure are taken to refer to bindings made by enclosing procedure definitions; that is, they are looked up in the environment in which the procedure was defined.

Procedures and the Processes They Generate

Our situation is now analogous to someone who knows the rules of how pieces move in chess but knows nothing of openings, tactics or strategy. We don't know any patterns yet.

A procedure is a pattern for the local evolution of a computational process. It specifies how each stage of the process is built upon the previous stage

Linear Recursion and Iteration

Consider the factorial function:

\[ n !=n \cdot(n-1) \cdot(n-2) \cdots 3 \cdot 2 \cdot 1 \]

Another way to write this is:

\[ n !=n \cdot[(n-1) \cdot(n-2) \cdots 3 \cdot 2 \cdot 1]=n \cdot(n-1) ! \]

From the latter, we can define the following procedure to generate the factorial of \(n\):

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

The authors visulise the resulting recursion of \(6!\) as follows:

We can also iterate by defining a counter that increases by one each step and is multiplied with the product of the last iteration. So, \(n!\) is the value of the product when the counter exceeds \(n\).

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

This can be visualised as follows:

Here some important distinctions are to be made. The authors clarify that a recursive process is different from a recursive procedure:

When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written.

Scheme is tail-recursive, i.e. it executes an iterative process in constant space, even if it is described by a recursive procedure. This means, that in Scheme we don't need any special iteration constructs such as for, while, until etc. They are only useful as sytactic sugar.

Exercise 1.9

Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

;; (inc (+ 3 5))
;; (inc (inc (+ 5 2)))
;; (inc (inc (inc (+ 1 5))))
;; (inc (inc (inc (inc (+ 0 5)))))
;; (inc (inc (inc (inc (5)))))
;; (inc (inc (inc 6)))
;; (inc (inc 7))
;; (inc 8)
;; 9
;; --> recursive

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

;; (+ 3 6)
;; (+ 2 7)
;; (+ 1 8)
;; (+ 0 9)
;; 9
;; --> iterative process:
Exercise 1.10

The following procedure computes a mathematical function called Ackermann's function. What are the values of the expression below the procedure definition. Also, give concise mathematical definitions for the functions computed by the procedures f , g , and h for positive integer values of \(n\). For example, (k n) computes \(5n^2\).

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

(A 1 10)
;; 1024

(A 2 3)
;; 65536

(A 3 3)
;; 65536

(define (f n) (A 0 n))
;; 2n
(define (g n) (A 1 n))
;; 2^n
(define (h n) (A 2 n))
;; 2^2^2^2 : n times
;; Knuth's up-arrow notation
(define (k n) (* 5 n n))
;; 5n^2

Tree Recursion

To understand tree recursion, consider the Fibonacci sequence:

\[0,1,1,2,3,5,8,13,21, …\]

In general, the Fibonacci numbers can be defined by the rule:

\[ \mathrm{Fib}(n)= \left\{\begin{array}{ll}0 & \text { if } n=0 \ 1 & \text { if } n=1 \ \mathrm{Fib}(n-1)+\mathrm{Fib}(n-2) & \text { otherwise } \end{array}\right. \]

Let's translate that into Lisp:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

This process looks like a tree:

This is pretty bad as the number of times that the procedure will compute is precisely Fib\((n + 1)\), e.g. in the case above exactly eight times. Thus, the process uses a number of steps that grows exponentially with the input. The space, however, only grows linearly with the input as we only need to keep track of the nodes above the current one at any point during computation.

Let's define an iterative procedure to do the same thing:

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

The authors summarise:

The difference in number of steps required by the two methods — one linear in n, one growing as fast as Fib(n) itself — is enormous, even for small inputs.

However, tree-recursive processes aren't useless. Often, they are easier to design and understand. Apparently, the Scheme interpreter itself evaluates expression using a tree-recursive process.

Example: Counting Change
(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

;; takes kinds of coins available
;; returns denomination of first kind
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

(count-change 10)
Exercise 1.11

A function f is defined by the rule that

\[ f(n)=\left\{\begin{array}{ll}n \quad \text { if } n<3 \ f(n-1)+2 f(n-2)+3 f(n-3) & \text { if } \quad n \geq 3\end{array}\right. \]

Write a procedure that computes \(f\) by means of a recursive process. Write a procedure that computes \(f\) by means of an iterative process.

;; recursive
(define (f-recur n)
  (cond ((< n 3) n)
        (else (+ (f-recur (- n 1))
                 (* 2 (f-recur (- n 2)))
                 (* 3 (f-recur (- n 3)))))))

(f-recur 10)
;; 1892

;; iterative version 1
(define (f-iter-1 n)
  (define (f-iter a b c count)
    (cond ((< count 0) count)
          ((= count 0) a)
          ((= count 1) b)
          ((= count 2) c)
          (else (f-iter b c (+ c (* 2 b) (* 3 a)) (- count 1)))))
  (f-iter 0 1 2 n))

(f-iter-1 4)
;; f-iter (1 2 (+ 2 (* 2 1) (* 3 0)) (- 3 1))
;; f-iter (1 2 (+ 2 2 0)) 2)
;; f-iter (1 2 4 2)
;; --> 4

;; iterative version 2
(define (f-iter-2 n)
  (define (f-iter a b c count)
    (cond ((< n 3) n)
          ((<= count 0) a)
          (else (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))
  (f-iter 2 1 0 (- n 2)))

(f-iter-2 10)
;; 1892
Exercise 1.12

The following pattern of numbers is called Pascal’s triangle:

The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

(define (pascal r c)
  (if (or (= c 1) (= c r))
       1
       (+ (pascal (- r 1) (- c 1))
          (pascal (- r 1) c))))

(pascal 5 3)
;; 6

;;   c
;; r 1
;;   1 1
;;   1 2 1
;;   1 3 3 1
;;   1 4 6 4 1
;;   ...
Exercise 1.13
  1. Proposition

    For all \(n \in \mathbb{N}\) let \(P(n)\) be the proposition:

    \(Fib(n)=\frac{\varphi^{n}-{\psi}^{n}}{\sqrt{5}}\)

  2. Basis for induction

    \(P(0)\) is true, as this shows:

    \[ \dfrac {\varphi^0 - \psi^0} {\sqrt 5} = \dfrac {1 - 1} {\sqrt 5} = 0 = Fib(0) \]

  3. Induction hypothesis

    \(\forall 0 \le j \le k + 1: Fib(j) = \dfrac {\varphi^j - \psi^j} {\sqrt 5}\)

    Thus, we need to show:

    \(Fib(k + 2) = \dfrac {\varphi^{k + 2} - \psi^{k + 2} } {\sqrt 5}\)

  4. Induction step

    We have the following two identities:

    \[ \varphi^2 = (\frac {1 + \sqrt 5} 2)^2 = \frac 1 4 ({6 + 2 \sqrt 5}) = \frac {3 + \sqrt 5} 2 = 1 + \varphi \]

\[ \psi^2 = (\frac {1 + \sqrt 5} 2)^2 = \frac 1 4 ({6 + 2 \sqrt 5}) = \frac {3 + \sqrt 5} 2 = 1 + \psi \]

Hence:

\[ \varphi^{k+2}-\psi^{k+2} = (1+\varphi) \varphi^{k}-(1+\psi) \psi^{k} \]

\(= (\varphi^{k}-\psi^{k})+(\varphi^{k+1}-\psi^{k+1})\)

\[ = \sqrt{5}(Fib(k)+Fib(k+1)) = \sqrt{5} Fib(k+2) \]

The result follows by the principle of mathematical induction.

Therefore:

\(\forall n \in \mathbb{N}: Fib(n) = \frac {\varphi^n - \psi^n} {\sqrt 5}\)

Orders of Growth

Let \(R(n)\) be the amount of resources the process requires for a problem of size \(n\).

The authors make some further important definitions

We say that \(R(n)\) has order of growth \(\theta(f(n))\), written $R(n) = θ(f(n)) (pronounced “theta of \(f(n)\)”), if there are positive constants \(k_1\) and \(k_2\) independent of \(n\) such that \(k_1f(n) \leq R(n) \leq k_2 f(n)\) for any sufficiently large value of \(n\). (In other words, for large \(n\), the value \(R(n)\) is sandwiched between \(k_1 f (n)\) and \(k_2 f (n)\).)

Exercise 1.14

Draw the tree illustrating the process generated by the aforementioned count-change procedure of in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?

(count-change 11)
|
(cc 11 5)__
|          \
(cc 11 4)   (cc -39 5)
|       \___
|           \
(cc 11 3)   (cc -14 4)
|       \_______________________________________________________
|                                                               \
(cc 11 2)                                                      (cc 1 3)
|       \_________________________                              |     \__
|                                 \                             |        \
(cc 11 1)                        (cc 6 2)                      (cc 1 2) (cc -9 3)
|       \___                      |     \__                     |     \__
|           \                     |        \                    |        \
(cc 11 0)   (cc 10 1)            (cc 6 1) (cc 1 2)             (cc 1 1) (cc -4 2)
         __/ |                 __/ |       |     \__            |     \__
        /    |                /    |       |        \           |        \
(cc 10 0)   (cc 9 1)  (cc 6 0)   (cc 5 1) (cc 1 1) (cc -4 2)   (cc 1 0) (cc 0 1)
         __/ |                 __/ |       |     \__
        /    |                /    |       |        \
(cc 9 0)    (cc 8 1)  (cc 5 0)   (cc 4 1) (cc 1 0) (cc 0 1)
         __/ |                 __/ |
        /    |                /    |
(cc 8 0)    (cc 7 1)  (cc 4 0)   (cc 3 1)
         __/ |                 __/ |
        /    |                /    |
(cc 7 0)    (cc 6 1)  (cc 3 0)   (cc 2 1)
         __/ |                 __/ |
        /    |                /    |
(cc 6 0)    (cc 5 1)  (cc 2 0)   (cc 1 1)
         __/ |                 __/ |
        /    |                /    |
(cc 5 0)    (cc 4 1)  (cc 1 0)   (cc 0 1)
         __/ |
        /    |
(cc 4 0)    (cc 3 1)
         __/ |
        /    |
(cc 3 0)    (cc 2 1)
         __/ |
        /    |
(cc 2 0)    (cc 1 1)
         __/ |
        /    |
(cc 1 0)    (cc 0 1)

The space requirement of cc is proportional to the maximum height of the recursion tree, because at any given point in the recursive process, the interpreter must only keep track of the nodes that lead to the current root. Since the maximum height of the tree is dominated by the branch that contains the most successive calls, i.e. the leftmost one in the graph, it is growing linearly with \(n\) (amount). In other words, \(\theta(n)\).

The time requirement can be deduced as follows:

  1. (cc amount 1) = \(\theta(n)\)
  2. (cc amount 2) = (cc amount 1) + (cc (- amount 5) 2))
  3. Here, we have \(\theta(n^2)\) when kinds-of-coins is 2.
  4. Hence, we get \(\theta(n^k)\) (\(k\) being kinds-of-coins) for cc(amount kinds-of-coins) since every 2nd branch is \(\theta(k)\), and the first branch is called \(\theta(n)\) times.
Exercise 1.15

The sine of an angle (specified in radians) can be computed by making use of the approximation \(x \approx x\) if \(x\) is sufficiently small, and the trigonometric identity

\(\sin x=3 \sin \dfrac{x}{3}-4 \sin ^{3} \dfrac{x}{3}\)

to reduce the size of the argument of \(sin\). (For purposes of this exercise an angle is considered “sufficiently small” if its magnitude is not greater than 0.1 radians.) These ideas are incorporated in the following procedures:

(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)))))

(sine 12.15)

;;(p (sine 4.05))
;;(p (p (sine 1.35)))
;;(p (p (p (sine 0.45))))
;;(p (p (p (p (sine 0.15)))))
;;(p (p (p (p (p (sine 0.05))))))
  1. How many times is the procedure p applied when (sine 12.15) is evaluated?

    As can be seen above the procedure is applied five times.

  2. What is the order of growth in space and number of steps (as a function of \(a\) or angle) used by the process generated by the sine procedure when (sine a) is evaluated?

    So, the basic intuition is that sine is applied as many times as angle can be divided by three until the absolute result is smaller than 0.1. To describe this mathematically, we need the notion of a ceiling (as we want to output an integer). So, we can write

    \[\dfrac{12.15}{3^{n}}< 0.1 \\\
    = 3 \times 12.15^{-n} < 0.1 \]

    \[ \log(3) \times -n \times log(12.15) < log(0.1) \]

    Thus, we can write the number of required computations as

    \(\Bigg\lceil\dfrac{\log\dfrac{12.15}{0.1}}{\log{3}}\Bigg\rceil = 5\)

    or more generally

    \(\Bigg\lceil\dfrac{\log\dfrac{a}{0.1}}{\log{3}}\Bigg\rceil\)

    Hence, the order of growth in space is \(\theta(log(x))\).

Exponentiation

This is a recursive definition of the exponent \(n\) for a given integer \(b\):

\begin{array} {l}b^{n}=b \cdot b^{n-1} \ b^{0}=1 \end{array}

In Scheme this linearly recursive process looks as such:

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

This requires \(\theta(n)\) steps and \(\theta(n)\) space. The corresponding iterative definition of the process would be:

(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product))))

This requires \(\theta(n)\) steps and \(\theta(1)\) space. We can be faster, however if we make use of the following:

\begin{array} {l}b^{2}=b \cdot b \ b^{4}=b^{2} \cdot b^{2} \ b^{8}=b^{4} \cdot b^{4} \end{array}

We can thus amend our process such that it runs even faster:

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

(define (even? n)
  (= (remainder n 2) 0))

How fast exactly? Well, computing \(b^{2n}\) using fast-expt requires only one more computation than computing \(b^{n}\).

Exercise 1.16

Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that \((b^{n/2})^{2} = (b^{2})^{n/2}\) , keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product \(ab^n\) is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

(define (iter-fast-expt b n)
   (define (iter b n a)
     (cond ((= 0 n) a)
           ((even? n) (iter (square b) (/ n 2) a))
           (else (iter b (- n 1) (* b a)))))
   (iter b n 1))

(iter-fast-expt 5 6)
;; 15625
Exercise 1.17

The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

(define (double k)
  (+ k k))

(define (halve k)
  (/ k 2))

(define (multiply a b)
  (cond ((or (= a 0) (= b 0)) 0)
        ((even? a) (multiply (halve a) (double b)))
        (else (+ b (multiply (- a 1) b)))))

(multiply 300 5001)
;; 1500300
Exercise 1.18

Using the result of the previous two exercises, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.

(define (double k)
  (+ k k))

(define (halve k)
  (/ k 2))

(define (fast-multiply a b)
  (define (iter a b s)
    (cond ((= a 0) s)
          ((even? a) (iter (halve a) (double b) s))
          (else (iter (- a 1) b (+ b s)))))
  (iter a b 0))

(fast-multiply 601 3)
;; 1803
Exercise 1.19

There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables \(a\) and \(b\) in the fib-iter process of earlier: \(a \rightarrow a + b\) and \(b \rightarrow a\). Call this transformation \(T\), and observe that applying \(T\) over and over again \(n\) times, starting with 1 and 0, produces the pair \(Fib(n + 1)\) and \(Fib(n)\). In other words, the Fibonacci numbers are produced by applying \(T^{n}\) , the \(n^{th}\) power of the transformation \(T\), starting with the pair (1, 0). Now consider \(T\) to be the special case of \(p = 0\) and \(q = 1\) in a family of transformations \(T_{pq}\), where \(T_{pq}\) transforms the pair (a, b) according to \(a \rightarrow bq + aq + ap\) and \(b \rightarrow bp + aq\). Show that if we apply such a transformation \(T_{pq}\) twice, the effect is the same as using a single transformation \(T_{p'q’}\) of the same form, and compute \(p’\) and \(q’\) in terms of \(p\) and \(q\). This gives us an explicit way to square these transformations, and thus we can compute \(T^{n}\) using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* q q) (* p p))
                   (+ (* 2 (* q p)) (* q q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

(fib 10)

The intuition here is the following. Observe that we can write the linea \(T_{pq}\) as a matrix:

\[ \begin{pmatrix} p+q & q \ q & p \end{pmatrix} \begin{pmatrix} a \ b \end{pmatrix} = \begin{pmatrix} bp + aq + ap \ bp + aq \end{pmatrix} \]

Now, we are told, we can just apply the matrix on the left twice (square) such that we get a single transformation \(T_{p'q’}\):

\[ \begin{pmatrix} p+q & q \\\
q & p \end{pmatrix} \begin{pmatrix} p+q & q \\\
q & p \end{pmatrix} = \begin{pmatrix} … & … \\\
p’ & q’ \end{pmatrix} = \begin{pmatrix} … & … \\\
q^{2} + 2pq & q^{2} + p^{2} \end{pmatrix} \]

Greatest Common Divisors

The greatest common divisor (GCD) of two integers \(a\) and \(b\) is defined to be the largest integer that divides both \(a\) and \(b\) with no remainder. For example, the GCD of 16 and 28 is 4.

Euclid's Algorithm is really smart. Let r be the remainder of the division of a by b. Then GCD(a, b) = GCD(b, r). In Scheme this looks as follows:

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

This code represents an iterative process whose number of steps grows as the logarithm of the numbers involved.

Exercise 1.20

The process that a procedure generates is of course dependent on the rules used by the interpreter. As an example, consider the iterative gcd procedure given above. Suppose we were to interpret this procedure using normal-order evaluation, as discussed before (The normal-order-evaluation rule for if is described in Exercise 1.5.) Using the substitution method (for normal order), illustrate the process generated in evaluating (gcd 206 40) and indicate the remainder operations that are actually performed. How many remainder operations are actually performed in the normal-order evaluation of (gcd 206 40)? In the applicative-order evaluation?

;; normal-order
;; NB: fully expand, then reduce
(gcd 40 (remainder 206 40))

(if (= (remainder 206 40) 0)
    40
    (gcd (remainder 206 40) (remainder 40 (remainder 206 40))))

;; 1 in if-condition

(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))

(if (= (remainder 40 (remainder 206 40)) 0)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))

;; 2 in if-condition

(gcd (remainder 40 (remainder 206 40))
     (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))

(if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0)
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))))

;; 4 in if-condition

(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
     (remainder (remainder 40 (remainder 206 40))
                (remainder (remainder 206 40)
                           (remainder 40 (remainder 206 40)))))

(if (= (remainder (remainder 40 (remainder 206 40))
                (remainder (remainder 206 40)
                           (remainder 40 (remainder 206 40)))) 0)
    ;; the condition is finally met so we now evaluate the line below
    (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
    (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40))
                    (remainder (remainder 206 40)
                               (remainder 40 (remainder 206 40))))))

;; 7 in if-condition

(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

;; 4 in final reduction
;; 18 in total with normal-order evaluation

;; applicative-order evaluation
;; NB: first evaluate, then apply procedures
(gcd 206 40)
(gcd 40 (remainder (206 40)))

(gcd 40 6)
(gcd 40 (remainder (40 6)))

(gcd 6 4)
(gcd 40 (remainder (6 4)))

(gcd 4 2)
(gcd 40 (remainder (4 2)))

(gcd 2 0)
;; 4 in total with
;; applicative-order evaluation

Testing for Primality

This first procedure leverages the fact that \(n\) is prime if and only if \(n\) is its smalles divisor:

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

(define (prime? n)
  (= n (smallest-divisor n)))

(prime? 12307926403)
;; #t

The steps required by this procedure has order of growth \(\theta(\sqrt{n})\)

Another procedure leverages Fermat's little theorem which is worth of being stated:

If \(n\) is \(a\) prime number and \(a\) is any positive integer less than \(n\), then \(a\) raised to the \(n^{th}\) power is congruent to \(a\) modulo \(n\).

NB Two numbers are congruent modulo \(n\) if they both have the same remainder when divided by \(n\). The remainder of a number \(a\) when divided by \(n\) is also referred to as the remainder of \(a\) modulo \(n\), or simply as \(a\) modulo \(n\).)

This is the code in Lisp:

;; compute the exponential of number modulo another number
(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))))

;; perform the Fermat test by
;; 1. choosing a random number a between 1 and n-1 and
;; 2. checking whether the remainder modulo n of a^n is equal to a
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

;; here we can specify how many times we want to run the test, i.e.
;; how sure we want to be
(define (prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (prime? n (- times 1)))
        (else false)))

(prime? 12307926403 10)
Exercise 1.21

Use the smallest-divisor procedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999.

(define (smallest-divisor n)
  (define (find-divisor n test-divisor)
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor n (+ test-divisor 1)))))
  (define (divides? a b)
    (= (remainder b a) 0))
  (find-divisor n 2))

(smallest-divisor 199)
;;199
(smallest-divisor 1999)
;;1999
(smallest-divisor 19999)
;;7

WIP

Bibliography

</home/lino/org/exocortex/biblio/library.bib>

Avatar
Linus Sehn
Graduate Student in International Relations

I am interested in all the ways computer technology reconfigures the political landscape

Next
Previous

Related