A computational process is much like a sorcerer's idea of a spirit. It cannot be seen or touched... The programs we use to conjure processes are like a sorcerer's spells. (pg 1)

This section familiarizes the reader with the basics of programming, specifically in Scheme. I'm going to exclude a few of the simpler ideas and try to focus on the core concepts introduced. I've purposely left out the first three exercises because of their introductory nature.

A language should be used as a framework within which we organize our ideas about processes. The most basic mechanisms are:

• Primitive Expressions - simplest elements of a language
• Means of Combination - compound elements built from simpler ones
• Means of Abstraction - naming compound elements

Substitution Model

A model to help illustrate procedure application. The general idea for any compound expression is take the body and substitute each operand with the formal parameter.

There are two evaluation methods of the substitution model, applicative-order and normal-order.

• Applicative-order - Evaluate the operator and operands then apply the resulting procedure to the resulting arguments
• Normal-order - Substitute operands until only primitive values, then evaluate

Exercise 1.4

Explain how applicative-order evaluation is used to produce the expected value.

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

The if condition determines when the process should subtract b from a, or add b to a. First both of the operands are evaluated, then the operator (which is the whole if statement). This returns the correct process needed to add the absolute value of b to a. Then this new procedure is evaluated and returned as the result of the procedure a-plus-abs-b.

Exercise 1.5

Show the bahavior of the interpreter in both forms of the substitution mode using this example.

(define (p) (p))

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

And the solution..

; Applicative-order evaluation
(test 0 (p))
(if (= 0 0) 0 (p))
; 0

; Normal-order evaluation
(test 0 (p))
(test 0 (p))
(test 0 (p))
(test 0 (p))
(test 0 (p))
; ..etc

; Normal-order evaluation is unable to determine a primitive operator with
; the definition of p

The applicative-order example will expand the operands and operator, then it will apply the resultant procedure to the resultant arguments. The normal-order example attempts to expand each operator into a primitive expression. So, everytime it tries to expand (p) it still gets (p) and has to try again forever and ever. It never gets to the step of evaluating the operator.

Exercise 1.6

Explain what happens when the special-form if is replaced with a procedure new-if.

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

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

Because in applicative-order evaluation, the operands are expanded first, the new-if procedure calls sqrt-iter infinitely. In the special-form if the predicate is evaluated first, and then either the appropriate consequent or alternative -- not both.

Exercise 1.7

The good-enough? procedure fails for small numbers of square roots because the precision value we use 0.001 will pass before we get close enough to an appropriate value. For larger numbers the program enters an infinite loop because it cannot compare the minor differences of such large numbers when they are represented with floating point values.

By comparing the difference between each guess and the previous guess we can get a better result for smaller and larger values.

;; Compare the difference between the current guess and the previous
;; guess. If the difference is small enough return true
(define (good-enough? guess prevGuess)
  (< (abs (- guess prevGuess)) 0.001))

;; We have to adjust the sqrt-iter procedure to remember the previous
;; guess, and pass it to good-enough?
(define (sqrt-iter guess prevGuess x)
  (if (good-enough? guess prevGuess)
      guess
      (sqrt-iter (improve guess x)
                 guess
                 x)))

;; Now update the sqrt procedure passing 0 as the initial prevGuess
(define (sqrt x)
  (sqrt-iter 1.0 0 x))

Exercise 1.8

Using the sqrt procedure as an example, a cube root procedure can be defined as:

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

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

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

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

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

Black-Box Abstraction

... It is crucial that each procedure accomplishes an identifiable task that can be used as a module in defining other procedures. (p 26)

This idea is also a foundational concept in Unix Philosophy

This section introduces block structure and lexical scope. Since these concepts are in almost every programming language , I'll just mention them and move on.

Conclusion

This ends the first section. Most of this is introductory syntax and semantics. The most important part introduced is the evaluation process. If you are reading the textbook, it is absolutely critical to work on the solutions. Knowledge is not fully absorbed unless it is applied.