Note of “Structure And Interpretation Of Computer Programs” (1)

Pascal is for building pyramids – imposing, breathtaking, static structures built by armies pushing heavy blocks into place. Lisp is for building organisms – imposing, breathtaking, dynamic structures built by squads fitting fluctuating myriads of simpler organisms into place.


1.1.7 Example: Square Roots by Newton’s Method


(define (sqrt-iter guess x)  
	(if (good-enough? guess x)
      	(sqrt-iter (improve guess x)
(define (improve guess x)  
	(average guess (/ x guess)))  
(define (average x y)  
	(/ (+ x y) 2))
(define (good-enough? guess x)
	(< (abs (- (* guess guess) x)) 0.001))
(define (sqrt1 x)
	(sqrt-iter 1.0 x))

The sqrt program also illustrates that the simple procedural language we have introduced so far is sufficient for writing any purely numerical program that one could write in, say, C or Pascal. This might seem surprising, since we have not included in our language any iterative (looping) constructs that direct the computer to do something over and over again. Sqrt-iter, on the other hand, demonstrates how iteration can be accomplished using no special construct other than the ordinary ability to call a procedure.

1.2 Procedures and the Processes They Generate



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

30 When we discuss the implementation of procedures on register machines in chapter 5, we will see that any iterative process can be realized ``in hardware’’ as a machine that has a fixed set of registers and no auxiliary memory. In contrast, realizing a recursive process requires a machine that uses an auxiliary data structure known as a stack.

31 Tail recursion has long been known as a compiler optimization trick. A coherent semantic basis for tail recursion was provided by Carl Hewitt (1977), who explained it in terms of the ``message- passing’’ model of computation that we shall discuss in chapter 3. Inspired by this, Gerald Jay Sussman and Guy Lewis Steele Jr. (see Steele 1975) constructed a tail-recursive interpreter for Scheme. Steele later showed how tail recursion is a consequence of the natural way to compile procedure calls (Steele 1977). The IEEE standard for Scheme requires that Scheme implementations be tail-recursive.”

comments powered by Disqus