1.1 The Elements of Programming
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.
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
which we organize our ideas about processes.
The most basic
- Primitive Expressions - simplest elements of a language
- Means of Combination - compound elements built from simpler ones
- Means of Abstraction - naming compound elements
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 [</class>]ex1.04
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
Exercise 1.5 [</class>]ex1.05
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
(p) and has to try again forever and ever. It never gets to the
step of evaluating the operator.
Exercise 1.6 [</class>]ex1.06
Explain what happens when the special-form
if is replaced with a
(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
new-if procedure calls
sqrt-iter infinitely. In the
if the predicate is evaluated first, and then either the
appropriate consequent or alternative – not both.
Exercise 1.7 [</class>]ex1.07
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 [</class>]ex1.08
sqrt procedure as an example, a cube root procedure can be
(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))
… 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 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.