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.

Pascal是为了建造金字塔——壮丽辉煌、令人震撼,是由各就其位的沉重巨石筑起的静态结构。而Lisp是为了构造有机体——同样的壮丽辉煌令人震撼,由各就其位但却永不静止的无数简单的有机片段构成的动态结构。

1.1.7 Example: Square Roots by Newton’s Method

这是一个使用牛顿法求平方根的Lisp程序:

(define (sqrt-iter guess x)  
	(if (good-enough? guess x)
	     	guess
      	(sqrt-iter (improve guess x)
                 	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

主要讲了递归和迭代,例子有计算斐波那契数列,阶乘和换零钱方式的统计。Lisp的特性在处理这种问题时基本上就是把递归过程直接翻译成Lisp语句。

看了一周java代码后看Lisp和Python就是种享受!

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