Concepts, Techniques, and Models of Computer Programming

I found another good resource for learning how to write computer programs, called "Concepts, Techniques, and Models of Computer Programming", by Peter Van Roy and Seif Haridi. It uses declarative programming and distributive computing as a programming paradigm, and its programming language of choice is Mozart-Oz.

One could see this as a successor of "Structure and Interpretation of Computer Programs" by Harold Abelson and Gerald Jay Sussman, which used functional programming as a programming paradigm, and Scheme as the programming language of choice.

Both have their values as instructional books, because they learn you to see computer programming in new ways you never imagined existed before.

I will be concentrating on the SICP book for now, but it is good to know that there are more excellent books to learn how to write programs using your human intelligence and imagination, instead of copying and pasting what others have done before you. Nothing wrong with the latter, but I don't aspire to become a script kiddie, or even a code monkey. I want to design programs.

Aquamacs Emacs

I was trying to get to grips with GNU Emacs, when I came across a Mac OS X specific equivalent, called Aquamacs. Well, it isn't really an equivalent, but, if I understood correctly, it is a graphical user interface (GUI) shell around GNU Emacs. It is meant to keep you in the spirit of GUI, not having to switch gears to a command-line-interpreter-state of mind.

• Aquamacs website

Thinking in C

On Mindview.net there is an excellent C foundation course in Shockwave Flash format that you can download from here as a ZIP archive for off-the-Net viewing. It isn't a full introductory course, but rather concentrating on the parts of C you'll need to better understand Java or C++.

Mindview also has courses in C++ and Java, called Thinking in Java and Thinking in C++, so this Thinking in C course could be seen as an introductory course for these other, more advanced courses. If I understood correctly, the old versions of these two courses can be downloaded for free, but if you want the most recent versions, you have to buy the printed copies, which seems reasonable to me.

I have done the first introductory chapter and it seems to be excellent for those who have little programming experience. However, I don't recommend it for the absolute newbies in programming, because it might be a little too steep in the learning curve for those. You need to be aware of some basic concepts of program development, and how your system works on the command line.

For those absolute newbies to programming, I recommend a site like the platform-independent Programming 101.

For how the command line works, I advice to visit:

• Command-line reference (Windows)
• Learning the Mac OS X Terminal (Mac OS X)
• An introduction to the Linux command line (Linux)

I realize that these might not be the best links for newbies (especially the Windows link). If anyone has suggestions, feel free to put it in a comment.

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

What is a Good First Programming Language?

While Googling, I came across the web article What is a Good First Programming Language, by Diwaker Gupta. In short, it depends on the audience. For first-graders, qBasic is probably a good choice, while for college freshmen, C is probably the best choice for a first programming language.

My first language was Apple II Basic, followed by 6502 micro-assembler, in college, late 1970s (actually, I learned Fortran first, on a mainframe PDP computer, with punch cards input and teletype printout; the programs were written ('developed') by hand with pen and paper, and transfered along with the data onto punch cards, which where read by a punch card reader; next, you needed to wait a few hours for your program to be executed and the results printed on a line printer, collected by an assistant, who put it in your print bin). Later on, I bought a Commodore 64, learned Basic, micro-assembler, hexcoding, macro-assembler, and Pascal. I did some C, C++, Java, JavaScript, Python and Lua, and now I'm learning Scheme. So I can claim that Scheme is certainly not my first language (and probably not my last as well).

How to Design Programs - 3.3 Finger Exercises on Composing Functions

Exercise 3.3.1.

The United States uses the English system of (length) measurements. The rest of the world uses the metric system. So, people who travel abroad and companies that trade with foreign partners often need to convert English measurements to metric ones and vice versa.

Here is a table that shows the six major units of length measurements of the English system:

English		metric
1 inch	=	2.54	cm
1 foot	=	12	in.
1 yard	=	3	ft.
1 rod	=	5(1/2)	yd.
1 furlong	=	40	rd.
1 mile	=	8	fl.

Develop the functions inches->cm, feet->inches, yards->feet, rods->yards, furlongs->rods, and miles->furlongs.

Then develop the functions feet->cm, yards->cm, rods->inches, and miles->feet.

Hint: Reuse functions as much as possible. Use variable definitions to specify constants.

Solution

;; inches->cm : number -> number
;; convert inches into cm
(define (inches->cm inches)
  (* inches INCH->CM))

;; feet->inches : number -> number
;; convert feet into inches
(define (feet->inches feet)
  (* feet FOOT->INCH))

;; yards->feet : number -> number
;; convert yards into feet
(define (yards->feet yards)
  (* yards YARD->FOOT))

;; rods->yards : number -> number
;; convert rods into yards
(define (rods->yards rods)
  (* rods ROD->YARD))

;; furlongs->rods : number -> number
;; convert furlongs into rods
(define (furlongs->rods furlongs)
  (* furlongs FURLONG->ROD))

;; miles->furlongs : number -> number
;; convert miles into furlongs
(define (miles->furlongs miles)
  (* miles MILE->FURLONG))

(define MILE->FURLONG 8)
(define FURLONG->ROD 40)
(define ROD->YARD 5.5)
(define YARD->FOOT 3)
(define FOOT->INCH 12)
(define INCH->CM 2.54)

;; feet->cm : number -> number
;; convert feet into cm
(define (feet->cm feet)
  (inches->cm
   (feet->inches feet)))

;; yards->cm : number -> number
;; convert yards into cm
(define (yards->cm yards)
  (feet->cm
   (yards->feet yards)))

;; rods->inches : number -> number
;; convert rods into inches
(define (rods->inches rods)
  (feet->inches
   (yards->feet
    (rods->yards rods))))

;; miles->feet : number -> number
;; convert miles into feet
(define (miles->feet miles)
  (yards->feet
   (rods->yards
    (furlongs->rods
     (miles->furlongs miles)))))

Exercise 3.3.2.

Develop the program volume-cylinder. It consumes the radius of a cylinder's base disk and its height; it computes the volume of the cylinder.

Solution

;; volume-cylinder : number number -> number
;; calculate volume of cylinder
;; example: (volume-cylinder 4 4) -> 201.06176
(define (volume-cylinder radius height)
  (*
   (area-circle radius)
   height))

;; area-circle : number -> number
;; calculate area of circle
;; example: (area-circle 4) -> 50.26544
(define (area-circle radius)
  (* PI (sqr radius)))

(define PI 3.14159)

Exercise 3.3.3.

Develop area-cylinder. The program consumes the radius of the cylinder's base disk and its height. Its result is the surface area of the cylinder.

Solution

;; area-cylinder : number number -> number
;; calculate surface area of cylinder
;; example: (area-cylinder 4 4) -> 201.06176
(define (area-cylinder radius height)
  (+
   (* 2
      (area-circle radius))
   (* height
      (circumference-circle radius))))

;; circumference-circle : number -> number
;; calculate circumference of circle
;; example: (circumference-circle 4) -> 25.13272
(define (circumference-circle radius)
  (* 2
     (* PI radius)))

;; area-circle : number -> number
;; calculate area of circle
;; example: (area-circle 4) -> 50.26544
(define (area-circle radius)
  (* PI (sqr radius)))

(define PI 3.14159)

Exercise 3.3.4.

Develop the function area-pipe. It computes the surface area of a pipe, which is an open cylinder. The program consumes three values: the pipe's inner radius, its length, and the thickness of its wall.

Develop two versions: a program that consists of a single definition and a program that consists of several function definitions. Which one evokes more confidence?

Solution

;; area-pipe number number number -> number
;; calculate surface area of open pipe
;; example: (area-pipe-multi 3 5 0.1) -> 195.4697298
(define (area-pipe-multi inner-radius length thickness-wall)
  (+
   (area-pipe-wall inner-radius length)
   (area-pipe-wall
    (+ inner-radius thickness-wall)
    length)
   (*
    2
    (-
     (area-circle (+ inner-radius thickness-wall))
     (area-circle inner-radius)))))

;; area-pipe-wall : number number -> number
;; calculate area of pipe wall
;; examples:
;; (area-pipe-wall 3 5) -> 94.2477
;; (area-pipe-wall 3.1 5) -> 97.38929
(define (area-pipe-wall radius length)
  (* (circumference-circle radius)
     length))

;; area-circle : number -> number
;; calculate area of circle
;; examples:
;; (area-circle 3) -> 28.27431
;; (area-circle 3.1) -> 30.1906799
(define (area-circle radius)
  (* PI (sqr radius)))

;; circumference-circle : number -> number
;; calculate circumference of circle
;; examples:
;; (circumference 3) -> 18.84954
;; (circumference 3.1) -> 19.477858
(define (circumference-circle radius)
  (* 2 PI radius))

(define PI 3.14159)

;; area-pipe : number number number -> number
;; calculate surface area of open pipe
(define (area-pipe radius length thickness-wall)
  (+
   (* 2 3.14159 radius length)
   (* 2 3.14159
      (+ radius thickness-wall)
      length)
   (* 2
      (-
       (* 3.14159 (sqr
                   (+ radius thickness-wall)))
       (* 3.14159 (sqr radius))))))

Obviously, the solution with the multiple definitions evokes more confidence, because you can develop a higher order function before getting into the details of the lower order functions.

Exercise 3.3.5.

Develop the program height, which computes the height that a rocket reaches in a given amount of time. If the rocket accelerates at a constant rate g, it reaches a speed of g * t in t time units and a height of 1/2 * v * t where v is the speed at t.

Solution

;; height : number -> number
;; calculate height of rocket at certain time
;; example: (height 3) -> 45
(define (height time)
  (* 0.5 (speed time) time))

;; speed : number -> number
;; calculate speed of rocket at certain time
;; example: (speed 3) -> 30
(define (speed time)
  (* G time))

(define G 10)

Exercise 3.3.6.

Recall the program Fahrenheit->Celsius from exercise 2.2.1. The program consumes a temperature measured in Fahrenheit and produces the Celsius equivalent.

Develop the program Celsius->Fahrenheit, which consumes a temperature measured in Celsius and produces the Fahrenheit equivalent.

Now consider the function

;; I : number -> number
;; to convert a Fahrenheit temperature to Celsius and back
(define (I f)
  (Celsius->Fahrenheit (Fahrenheit->Celsius f)))

Evaluate (I 32) by hand and using DrScheme's stepper. What does this suggest about the composition of the two functions?

Solution

;; Fahrenheit->Celsius number -> number
;; examples:
;; (Fahrenheit->Celsius 32) -> 0
;; (Fahrenheit->Celsius 212) -> 100
(define (Fahrenheit->Celsius F)
  (* (- F 32) (/ 5 9)))

;; Celsius->Fahrenheit number -> number
;; examples:
;; (Celsius->Fahrenheit 0) -> 32
;; (Celsius->Fahrenheit 100) -> 212
(define (Celsius->Fahrenheit C)
  (+ (* C (/ 9 5)) 32))

;; I : number -> number
;; to convert a Fahrenheit temperature to Celsius and back
(define (I f)
  (Celsius->Fahrenheit (Fahrenheit->Celsius f)))

(I 32) is Celsius->Fahrenheit applied to (Fahrenheit-Celsius 32)

(Fahrenheit-Celsius 32)
evaluates to
(/ (* (- 32 32) 5) 9)
(/ (* 0 5) 9)
(/ 0 9)
0

(Celsius-Fahrenheit 0)
evaluates to
(+ (/ (* 0 9) 5) 32)
(+ (/ 0 5) 32)
(+ 0 32)
32

DrScheme's Stepper:

(I 32)

(Celsius->Fahrenheit
  (Fahrenheit->Celsius 32))

(Celsius->Fahrenheit
  (Fahrenheit->Celsius 32))

(Celsius->Fahrenheit
  (* (- 32 32) (/ 5 9)))

(Celsius->Fahrenheit
  (* (- 32 32) (/ 5 9)))

(Celsius->Fahrenheit
  (* 0 (/ 5 9)))

(Celsius->Fahrenheit
  (* (/ 5 9)))

(Celsius->Fahrenheit (* 0 5/9))

(Celsius->Fahrenheit (* 0 5/9))

(Celsius->Fahrenheit 0)

(Celsius->Fahrenheit 0)

(+ (* 0 (/ 9 5)) 32)

(+ (* 0 (/ 9 5)) 32)

(+ (* 0 9/5) 32)

(+ (* 0 9/5) 32)

(+ 0 32)

(+ 0 32)

32

The constants 32 and 5/9 could be incorporated in both as variables.