Alternative to MIT course

At UC Berkeley there is an alternative to the MIT course "Structure and Interpretation of Computer Programs". The webcast page can be found here. The video is only streaming (Real Media), but the audio can be downloaded as a (MP3) podcast through iTunes.

There is a UCB Scheme, called STk, which has versions for Windows, Linux and Mac OS X.

In Mac OS X (which I happen to use), you'll need to run from a X11 terminal window, which needs to be pre-installed. For versions of Mac OS X before 10.4 (Tiger), you need to download XDarwin, if you haven't done so already. For OS X 10.4 and higher, there is a X system—X11 and Xorg—on the install disk, which should be used instead of the download from XDarwin.org. If you have X11 available in your /Applications/ folder, you already have X installed.

NB: While the podcast is convenient, it is not very useful to understand the lessons. You really need to watch the video stream, and perhaps use the podcast as a preview, to get a quick overview of the lecture before paying attention to details.

SICP - 1.1 The Elements of Programming

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
(+ 5 3 4)
(- 9 1)
(/ 6 2)
(+ (* 2 4) (- 4 6))
(define a 3)
(define b (+ a 1))
(+ a b (* a b))
(= a b)
(if (and (> b a) (< b (* a b)))
    b
    a)
(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
(+ 2 (if (> b a) b a))
(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))

Solution

10
12
8
3
19
4
16
6
16

Exercise 1.2.

Translate the following expression into prefix form

5 + ⅓ + (2 - (3 - (6 + ⅓)))
————————————————————————————
      3(6 - 2)(3 - 7)

Solution

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

Exercise 1.3.

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

Solution

(define (sum-squares-largest-two a b c)
  (if (> a b)
      (if (> b c)
          (+ (sq a) (sq b))
          (+ (sq a) (sq c)))
      (if (> a c)
          (+ (sq a) (sq b))
          (+ (sq b) (sq c)))))
(define (sq x)
  (* x x))

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)
  ((if (> b 0) + -) a b))

Solution

If b is larger than zero, the + operation is used to combine a and b, otherwise the - operation is used. The latter operation negates the negative (or zero) value of b, and, in effect, adds the absolute value of b to a.

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

Then he evaluates the expression

(test 0 (p))

What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)

Solution

In the case of normal-order evaluation, (test 0 (p)) is evaluated as follows:

(test 0 (p))

(if (= 0 0)
    0
    (p)

(if (= 0 0)
    0
    (p)

(if #t
    0
    (p)

0

In the applicative order, (test 0 (p)) is evaluated as follows:

(test 0 (p))

(test 0 (p))

(test 0 ((p)))

(test 0 (((p))))

...

The interpreter keeps adding parentheses around (p) until infinity, and there will never be a result printed, because it will take forever to evaluate the expression (test 0 (p)).

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

Eva demonstrates the program for Alyssa:

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0

Delighted, Alyssa uses new-if to rewrite 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 attempts to use this to compute square roots? Explain.

Solution

The program goes into an endless loop, because it keeps evaluating (sqrt-iter (improve guess x) x) with new values for guess, adding a new-if in each iteration after the existing new-if.

The reason that this happens is because if is a keyword and

(if predicate consequent alternative)

is a special case, instead of a regular combination or a procedure (like new-if). This means the order in which terms are evaluated in the if special form is different than in the new-if procedure.

The special form if evaluates the predicate first and if it returns a non-false value (everything else than #f), it evaluates the consequence, never evaluating the alternative. This means that if there is a base case, the recursion will end at some point. In the original definition there is such a base case, namely when the absolute value of the difference between the square of the guess and the number value the sqrt-iter definition consumes is less than a certain constant value.

When the new-if procedure is used, the three argument expressions of the procedure call are evaluated before new-if is applied to the evaluated expressions. In order to evaluate the third argument expression, which is a recurvive call to sqrt-iter, the new-if of that recursive call has to be evaluated first. Of course, this recursive call also has a third argument expression, with the same consequence of calling new-if for that successive recursive call, and so on. The result is that new-if calls are being added to the evaluation process and there is never going to be a base case that ends this. The program gets into an endless loop until the user halt it.

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, arithmetic operations are almost always performed with limited 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 better for small and large numbers?

Solution

For x < 1e-6, the square root of x is always smaller than 0.001, so the absolute value of the difference between the square of guess and x will always be smaller than 0.001, and the result of good-enough? will always be a true value.

In real computers, if x is sufficiently large, the number of decimal places will be too small to hold enough precision to let guess² close in on x.

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

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

(define (good-enough? old-guess guess)
  (<
   (if (< old-guess guess)
       (/ guess old-guess)
       (/ old-guess guess))
   1.001))

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

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

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 better approximation is given by the value

x/y² + 2y
—————————
    3

Use this formula to implement a cube-root procedure analogous to the square-root procedure. (In section 1.3.4 we will see how to implement Newton's method in general as an abstraction of these square-root and cube-root procedures.)

Solution

(define (cube-root x)
  (cube-root-iter 2.0 1.0 x))

(define (cube-root-iter old-guess guess x)
  (if (good-enough? old-guess guess)
      guess
      (cube-root-iter guess (improve guess x)
                 x)))

(define (good-enough? old-guess guess)
  (<
   (if (< old-guess guess)
       (/ guess old-guess)
       (/ old-guess guess))
   1.001))

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

Towers of Hanoi - 3

Let's look at the steps for (move 3 1 2 3):

step disk from  to  spare
  1    1    1    2    3
  2    2    1    3    2
  3    1    2    3    1
  4    3    1    2    3
  5    1    3    1    2
  6    2    3    2    1
  7    1    1    2    3

Now reorder the lines on the disk row, in reverse order:

step disk from  to  spare
  4    3    1    2    3
  2    2    1    3    2
  6    2    3    2    1
  1    1    1    2    3
  3    1    2    3    1
  5    1    3    1    2
  7    1    1    2    3

This means disk 3 is moved once, disk 2 is moved twice, and disk 1 is moved four times. What causes this?

See what happens for each disk:

1. move pile on top of disk 3 on to spare
2. move disk to destination
3. move pile back on top of disk (at destination)

So, for each move of a disk, the pile on top of it is moved twice as often:

• disk 3 is moved once
• pile on top of disk 3 (disks 1 and 2) are moved twice

• disk 2 is moved twice
• for each move of disk 2, disk 1 on top of disk 2 is moved twice

• disk 1 is moved four times

More general for a pile of n disks, for p between 1 and n:

1. move pile on top of disk p (consisting of disks 1 tru p-1) to spare
2. move disk p to destination
3. move pile at spare to destination

• disk 1 tru p-1 is moved twice as often as disk p

Therefore, the total number of moves is:

Sum(p=1 tru n) { 2^n-p }

or

2ⁿ - 1

Another observation is that:

• disk 1 is always moved in odd steps (1, 3, 5, etc.)
• disk 2 is always moved in steps 2, 6, 10, etc.
• disk 3 is always moved in steps 4, 12, 20, etc.
• disk p is always moved in step

  2^p-1 mod 2^p

Look at the following moves, depending on the number of disks, n:

n = 1
disk 1: from → to

n = 2
disk 2: from → to
disk 1: from → spare → to

n = 3
disk 3: from → to
disk 2: from → spare → to
disk 1: from → to → spare → from → to

n = k
disk k-0: from → to
disk k-1: from → spare → to
disk k-2: from → to → spare → from → to
disk k-3: from → spare → to → from → spare → to → from → spare → to
...

To find the disk of a n disk Towers of Hanoi puzzle, depending on the current value of step, use this program:

;; find-disk-for-step: number number -> number
;; find the disk that is moved in a step
;; in a n high Tower of Hanoi
;; if step is out of range, then return a -1
(define (find-disk-for-step step n)
  (if (> step (- (expt 2 n) 1))
      -1
      (find-disk-for-step-loop step n 1)))
;; find-disk-loop number number number -> number
;; check which disk is moved in a certain step
;; of the Towers of Hanoi puzzle
;; seed this recursion with disk = 1
(define (find-disk-for-step-loop step n disk)
  (if (= (modulo step (expt 2 disk)) (expt 2 (- disk 1)))
      disk
      (find-disk-for-step-loop step n (+ disk 1))))

The program consists of two definitions.

There is a the definition called find-disk-for-step, which consumes step (which stands for the step, or move number, in the puzzle) and n (which stands for the total number of disks in the puzzle), and produces either the disk that is moved in that step, or a value of -1 if the value of step is out of range (too high).

Then there is the definition that is called from the first definition, as a helper definition. This second definition is called find-disk-for-step-loop, which consumes step and n, and a disk parameter, which should be seeded with the value 1. The definition tests if a disk is moved for the given values of step and n. It checks if the following condition is true:

step mod 2^disk == 2^disk-1

if it is true, disk has been found and is returned as a result, otherwise a higher value of disk is tested, by recursing the find-disk-for-step-loop with disk + 1 as an argument for the disk parameter, and the same values as before for the other parameters.

Now we now which disk is moved in a particular step, we can use what we have observed before to formulate a definition that finds the move of a disk in a certain step, expressed in the values of from, to and spare, as used as arguments in (move n from to spare). Of course, we already know what disk moves.

What we observed was, that the bottom disk in the starting position, moves as follows:

disk n: from → to

The disk on top of the bottom disk, moves as follows:

disk n-1: from → spare → to

The disk on top of that disk, moves as follows:

disk n-2: from → to → spare → from → to

In general:

disk n - (even number):
from → to → spare → from → to → spare → ...

disk n - (odd number):
from → spare → to → from → spare → to → ...

Restated as follows:

if (modulo n 2) is equal to (modulo disk 2) then:
from → to → spare → from → to → spare → ...
else:
from → spare → to → from → spare → to → ...

If we want to find how many times a disk has moved in the puzzle, based on the value of step, we can use this formula:

        step - 2^disk-1
moved = —————————————
            2^disk

If moved is equal to zero, this particular disk hasn't moved. If it's equal to one, it has moved once, etc. We can use this to determine a move, once we have established which disk moves, which is based on the value of step. Now about the details:

if (modulo n 2) is equal to (modulo disk 2) then:

in case

(= (modulo moved 3) 0)
  (print-move disk from to)

(= (modulo moved 3) 1)
  (print-move disk to spare)

(= (modulo moved 3) 2)
  (print-move disk spare from)

else:

in case

(= (modulo moved 3) 0)
  (print-move disk from spare)

(= (modulo moved 3) 1)
  (print-move disk spare to)

(= (modulo moved 3) 2)
  (print-move disk to from)

So, now we can run the value of step from 1 to 2ⁿ-1, inclusive, determine which disk is moved, what the move is, and print that to the screen.

This all is enough to write the definitions:

;; move : number number number number -> string
;; calculate moves for Towers of Hanoi
;; side effect: display move disk: from -> to
;; example:
;; (move 3 1 2 3)
;; 1: 1 -> 2
;; 2: 1 -> 3
;; 1: 2 -> 3
;; 3: 1 -> 2
;; 1: 3 -> 1
;; 2: 3 -> 2
;; 1: 1 -> 2
;; "done"
(define (move n from to spare)
  (move-loop n from to spare 1))

;; calculate each move through iteration
;; using step as a counter
;; seed step with 1
(define (move-loop n from to spare step)
  (define disk (find-disk step n 1))
  (if (< step (expt 2 n))
      (begin
        (print-step-move step n disk from to spare)
        (move-loop n from to spare (+ step 1)))
      "done"))

;; print a move of a disk
(define (print-step-move step n disk from to spare)
  (define moved (/ (- step (expt 2 (- disk 1))) (expt 2 disk)))
  (cond
    [(= (modulo n 2) (modulo disk 2))
      (cond
        [(= (modulo moved 3) 0)
         (print-move disk from to)]
        [(= (modulo moved 3) 1)
         (print-move disk to spare)]
        [else
         (print-move disk spare from)])]
    [else
      (cond
        [(= (modulo moved 3) 0)
         (print-move disk from spare)]
        [(= (modulo moved 3) 1)
         (print-move disk spare to)]
        [else
         (print-move disk to from)])]))

;; print a move
(define (print-move n from to)
  (begin
    (display n)
    (display ": ")
    (display from)
    (display " -> ")
    (display to)
    (newline)))

;; find which disk is moved in the current step
(define (find-disk step n disk)
   (if (= (modulo step (expt 2 disk)) (expt 2 (- disk 1)))
      disk
      (find-disk step n (+ disk 1))))

The iterative process is not necessarily faster than the recursive process, because, in contrast to the recursive process in the Fibonacci numbers, there are no steps that could be calculated from earlier steps, or something.

Remember, that in the Fibonacci number problem,

Fib(n) = Fib(n-1) - Fib(n-2)

uses Fib(n-2) when trying to calculate Fib(n-1) (which is equal to Fib(n-2) + Fib(n-3)). This lead to inefficiency when using the formulas straight in a code definition.

In the Towers of Hanoi, on the other hand, there is no such inefficiency. A recursive or iterative process is just another way to express a solution to the problem.

Towers of Hanoi - 2

In the video tutorial 1b of the MIT Lisp video tutorials, the solution of the Towers of Hanoi puzzle is expressed as this Lisp definition:

(define (move n from to spare)
  (cond
    ((= n 0) "done" )
    (else)
      (move (-1+ n) from spare to)
      (print-move n from to)
      (move (-1+ n) spare to from))))

I have translated that into DrScheme, using Textual (MzScheme, includes R5RS), which can be found at the end of this posting (see Program).

Now look at the program trace of (move 3 1 2 3), using substitution (as explained in the video tutorial):

(move 3 1 2 3)              ;;  n  T  F  S
  (move (-1+ 3) 1 3 2)      ;;  3  1  2  3
    (move (-1+ 2) 1 2 3)    ;;  2  1  3  2
      (move (-1+ 1) 1 3 2)  ;;  1  1  2  3
        "done"              ;;  0  1  3  2
      (print-move 1 1 2)    ;;  1  1  2  3
      (move (-1+ 1) 3 2 1)  ;;  1  1  2  3
        "done"              ;;  0  3  2  1
    (print-move 2 1 3)      ;;  2  1  3  2
    (move (-1+ 2) 2 3 1)    ;;  2  1  3  2
      (move (-1+ 1) 2 1 3)  ;;  1  2  3  1
        "done"              ;;  0  2  1  3
      (print-move 1 2 3)    ;;  1  2  3  1
      (move (-1+ 1) 1 3 2)  ;;  1  2  3  1
  (print-move 3 1 2)        ;;  3  1  2  3
  (move (-1+ 3) 3 2 1)      ;;  3  1  2  3
    (move (-1+ 2) 3 1 2)    ;;  2  3  2  1
      (move (-1+ 1) 3 2 1)  ;;  1  3  1  2
        "done"              ;;  0  3  2  1
      (print-move 1 3 1)    ;;  1  3  1  2
      (move (-1+ 1) 2 1 3)  ;;  1  3  1  2
        "done"              ;;  0  2  1  3
    (print-move 2 3 2)      ;;  2  3  2  1
    (move (-1+ 2) 1 2 3)    ;;  2  3  2  1
     (move (-1+ 1) 1 3 2)   ;;  1  1  2  3
        "done"              ;;  0  1  3  2
     (print-move 1 1 2)     ;;  1  1  2  3
     (move (-1+ 1) 3 2 1)   ;;  1  1  2  3
        "done"              ;;  0  3  2  1

I have used indentation to show how deep the trace is in the iteration (in essence, how low the value of n is), and color coding to indicate which of the three steps is being executed inside the combination of the alternative expression (see MIT/GNU Scheme - Conditionals) as used in the definition above. Furthermore, I have added in the comments fields the substituted values for n, from, to, and spare (n F T S).

As you can see, this is a recursive process, and certainly not an iteration. Now, can we rewrite this program, so it does an iterative process to solve the puzzle, instead of the current recursive process?

Program

;; Towers of Hanoi, solution 1

;; move : number number number number -> string
;; calculate moves for Towers of Hanoi
;; side effect: display move disk: from -> to
;; example:
;; (move 3 1 2 3)
;; 1: 1 -> 2
;; 2: 1 -> 3
;; 1: 2 -> 3
;; 3: 1 -> 2
;; 1: 3 -> 1
;; 2: 3 -> 2
;; 1: 1 -> 2
;; "done"
(define (move n from to spare)
  (cond
    [(= n 0) "done" ]
    [else (begin
            (move (-1+ n) from spare to)
            (print-move n from to)
            (move (-1+ n) spare to from))]))
(define (print-move n from to)
  (begin
    (display n)
    (display ": ")
    (display from)
    (display " -> ")
    (display to)
    (newline)))
(define (-1+ x)
  (- x 1))

Towers of Hanoi

The Towers of Hanoi puzzle is not that easy to solve. If you want to play a digital version of that puzzle, go to Towers of Hanoi DHTML game.

Now let's see how to solve a four disk puzzle.



This is the start position.



And this is the end position.

A step in between the start and end position could be something like this:



Directly followed by this:



This is the only move the largest red disk will make.

How about the next disk, the yellow one?

Well, it has three positions, the start position, on tower 2 (while the red disk is still on tower 1), and on top of the red disk on tower 3):



The red disk hasn't moved yet, and the yellow disk have moved to tower 2.



The red disk has moved, and the yellow disk has moved on top of the red disk on tower 3.

Now, let's recap what we've done so far:

• We have moved the disks on top of the red disk, to make the red disk free, and move it to it's final tower.
• In order to make the red disk free to move from tower 1 to tower 3, we have to move the other disks to tower 2, with the yellow disk at the bottom of the pile of disks. In order to be able to move the yellow disk to tower 2, we need to move the disks on top of it to tower 3. Then we move the yellow disk to tower 2, and the other disks on top of the yellow disk on tower 2.
• Once the red disk is on tower 3, we need to move the yellow disk on tower 2 to tower 3. In order to do that, we need to move the disks on top of the yellow disk to tower 1. After that, we can move the yellow disk on top of the red disk on tower 3.

I see a pattern there, in order to move a disk at the bottom of a pile of disks, we need to move the disks on top of it to the spare tower. If you want to move a disk from tower O to tower D, the remaining tower S is the spare tower (where O, D, and S can either be one of 1, 2, 3). That smells like a recursive process.

So this is the process:

• move disks on top of red disk to tower 2:
  • move disks on top of yellow disk to tower 3:
    • move cyan disk on top of green disk to tower 2
    • move green disk to tower 3
    • move cyan disk to tower 3, on top of green disk
  • move yellow disk to tower 2
  • move disks on tower 3 to tower 2, on top of yellow disk:
    • move cyan disk on top of green disk to tower 1, on top of red disk
    • move green disk to tower 2, on top of yellow disk
    • move cyan disk to tower 2, on top of green disk
• move red disk to tower 3
• move disks on tower 2 to tower 3, on top of red disk:
  • move disks on top of yellow disk to tower 1:
    • move cyan disk on top of green disk to tower 3
    • move green disk to tower 1
    • move cyan disk to tower 1, on top of green disk
  • move yellow disk top tower 3, on top of red disk
  • move disks on tower 1 to tower 3, on top of yellow disk:
    • move cyan disk on top of green disk to tower 2
    • move green disk to tower 3, on top of yellow disk
    • move cyan disk to tower 3, on top of green disk

Here is an animation of this procedure:



If we study this more closely, we can see that in order to move a pile of disks from the origin to the destination, you need to:

1. park the disks on top of the bottom disk to the spare
2. move the freed bottom disk to it's destination
3. move the parked pile back on the bottom disk

That should be enough to understand the puzzle, but not quite enough to develop our program to solve the puzzle.

Fibonacci numbers

Fibonacci numbers can be defined as follows:



We can simply write a Scheme program that does just that:

;; Fib : number -> number
;; calculate Fibonacci number
;; examples:
;; (Fib 0) -> 0
;; (Fib 1) -> 1
;; (Fib 5) -> 5
;; (Fib 10) -> 55
(define (Fib n)
  (cond
    [(< n 2) n]
    [else
     (+
      (Fib (- n 1))
      (Fib (- n 2)))]))

Testing:

> (Fib 0)
0
> (Fib 1)
1
> (Fib 5)
5
> (Fib 10)
55

Here is the trace of (Fib 4), leaving out the uninteresting bits:

(Fib 4)
(+ (Fib 3) (Fib (- 4 2)))
(+ (+ (Fib 2) (Fib (- 3 2))) (Fib (- 4 2)))
(+ (+ (+ (Fib 1) (Fib (- 2 2))) (Fib (- 3 2))) (Fib (- 4 2)))
(+ (+ (+ 1 (Fib 0)) (Fib (- 3 2))) (Fib (- 4 2)))
(+ (+ 1 (Fib 1)) (Fib (- 4 2)))
(+ 2 (Fib 2))
(+ 2 (+ (Fib 1) (Fib (- 2 2)))
(+ 2 (+ 1 (Fib 0)))
3

Compare this with (Fib 3):

(Fib 3)
(+ (Fib 2) (Fib (- 3 2)))
(+ (+ (Fib 1) (Fib (- 2 2))) (Fib (- 3 2)))
(+ (+ 1 (Fib 0)) (Fib (- 3 2)))
(+ 1 (Fib 1))
2

According to the lecture video (see below), in this process, space of Fib(n) is proportional to n, and time is proportional to Fib(n).

Notice that some terms are calculated several times, which indicates code inefficiency. This is clearly not an iterative process, but rather some kind of recursive process.

Can the program be rewritten so, that it does an iterative process, instead of the current recursive process?

Well, how about starting the calculation from 2 and going upwards to n? If n is 0 or 1, the answers are 0 and 1, respectively. Then we use the following definition of Fibs, in which we pass intermediate Fibonacci values as parameters of Fibs, in a recursive fashion:

(define (Fibs a b c n)
  (cond
    [(> c n) b]
    [else (Fibs b (+ a b) (+ c 1) n)]))

In this definition, b is the previous Fibonacci number, a is the Fibonacci number before that, c indicates the order of the current intermediate Fibonacci number, and n indicates the desired order for the Fibonacci number. We seed Fibs with a = 0, b = 1, c = 2, n = n.

Let's try (Fibs 0 1 2 5) in a trace:

(Fibs 0 1 2 5)
(Fibs 1 1 3 5)
(Fibs 1 2 4 5)
(Fibs 2 3 5 5)
(Fibs 3 5 6 5)
5

We can see that the time of Fibs is proportional to n, and the space is proportional to 1. This, therefore, is an iteration process.

Here is the complete program for calculating a Fibonacci number:

;; Fib : number -> number
;; calculate a Fibonacci number
;; e.g. (Fib 4) -> 3
;; e.g. (Fib 10) -> 55
(define (Fib n)
  (cond
    [(< n 2) n]
    [else (Fibs 0 1 2 n)]))
(define (Fibs a b c n)
  (cond
    [(> c n) b]
    [else (Fibs b (+ a b) (+ c 1) n)]))

And (Fib 10) produces 55:

> (Fib 10)
55

If you try out both programs with a really large number (say 100000), you will notice a distinct difference in speed. The second is much faster than the first.

Credits

I have to confess that I didn't come up with the solutions myself.

The first solution was taken from a Lisp tutorial video (lesson 1b of the MIT Lisp video tutorials), and converted into Scheme.

The second solution was taken from Lecture notes about Fibonacci numbers by David Eppstein, professor of Computer Science. The code was written in Python, so I needed to convert from an imperative language notation into the declarative language notation of Scheme, which I had never done before. So there was indeed a, though modest, learning experience in all of this. On that same notes page are some alternative methods you could try.

When in need for a solution, Google is your friend.

Linear iteration and linear recursion

Although all loops in Scheme are done using recursion, the resulting code execution, can be quite different. Observe this peano arithmetic (only increment and decrement by one) addition, taken from the lesson 1b (Procedures and Processes; Substitution Model) of the MIT Lisp video tutorial page and modified for DrScheme (also see this tutorial on Google Video):

;; plus1 : number number -> number
;; add two numbers
;; by only using increments and decrements
;; example : (plus1 3 5) should produce 8
(define (plus1 x y)
  (if (= x 0)
      y
      (plus1 (dec x) (inc y))))
(define (inc x)
  (+ x 1))
(define (dec x)
  (- x 1))

(plus1 3 5)

If we trace this (plus1 3 5), leaving out the uninteresting parts, we get this:

(plus1 3 5) |
(plus1 2 6) |
(plus1 1 7) | time = O(x)
(plus1 0 8) |
8           |
------------
space = O(1)

linear iteration : time = O(x), space = O(1)

The time it takes to run the code is proportional to the value of x, in other words, ordinal to x (O(x)). The amount of memory storage it takes to execute this code, the space, is constant, or ordinal to 1 (O(1)). This is the hallmark of a linear iteration.

If we modify the code of plus1, so it delays the addition of y until the end of the execution, we get something like this:

;; plus2 : number number -> number
;; add two numbers
;; by only using increments and decrements
;; example : (plus2 3 5) should produce 8
(define (plus2 x y)
  (if (= x 0)
      y
      (inc (plus2 (dec x) y))))
(define (inc x)
  (+ x 1))
(define (dec x)
  (- x 1))

(plus2 3 5)

If we trace (plus2 3 5) as before, we get this:

(plus2 3 5)                   |
(inc (plus2 2 5))             |
(inc (inc (plus2 1 5)))       |
(inc (inc (inc (plus2 0 5)))) | time = O(x)
(inc (inc (inc 5)))           |
(inc (inc 6))                 |
(inc 7)                       |
8                             |
------------------------------
space = O(x)

linear recursion : time = O(x), space = O(x)

Again, the number of steps is proportional to the value of x (that there are twice as many steps doesn't matter at this point). However, the amount of space isn't constant, but proportional to value of x. This is the hallmark of a linear recursion.

Although both methods plus1 and plus2 use the same recursive looping technique, the resulting code execution (process) is quite different.

There are two other interesting problems discussed in this video tutorial lesson, Fibonacci numbers and the Towers of Hanoi. These can be expressed both as a recursive and an iterative process. I will discuss both problems in separate posts, once I've digested the concepts of this video tutorial.

Structure and Interpretation of Computer Programs

Through the Code Newbie forum (I'm forum member Rasheed), I got a reference to Structure and Interpretation of Computer Programs by MIT Press. They use Scheme, just like that other great on-line book, How to Design Programs (also see Why this blog?, and the tag How to Design Programs on this blog).

There is also a series of hour long lectures on Google video. I have here a list of videos I have found (lectures 9a, 9b, and 10a were missing when I did a search on Google Video):

• Lecture 1a: Overview and Introduction to Lisp
• Lecture 1b: Procedures and Processes; Substitution Model
• Lecture 2a: Higher-order Procedures
• Lecture 2b: Compound Data
• Lecture 3a: Henderson Escher Example
• Lecture 3b: Symbolic Differentiation; Quotation
• Lecture 4a: Pattern Matching and Rule-based Substitution
• Lecture 4b: Generic Operators
• Lecture 5a: Assignment, State, and Side-effects
• Lecture 5b: Computational Objects
• Lecture 6a: Streams, Part 1
• Lecture 6b: Streams, Part 2
• Lecture-7a: Metacircular Evaluator, Part 1
• Lecture 7b: Metacircular Evaluator, Part 2
• Lecture 8a: Logic Programming, Part 1
• Lecture 8b: Logic Programming, Part 2
• Lecture 10b: Storage Allocation and Garbage Collection

I also found the original videos, which you can download from this page. That is perhaps the best way to retrieve the videos. You can either download or torrent a DIVX .avi or a MPEG video file from each of the 20 lectures (ten times a and b lessons). This was a good reason for me to start using the Azureus bit-torrent client, because I want these lessons burnt on DVD.