SICP 读书笔记

1.1.1 程序设计的基本元素

; 表达式
;; 前缀表示法
(+ 12 23)
(+ 1 2 3 4)
(/ 10 5 2) ;; /= 1
;; 表达式当然可以嵌套
  (+ (* 3
        (+ (* 2 4)
           (+ 3 5)))
     (+ (- 10 7)
        6))

1.1.2 命名和环境

; 声明一个变量
(define x 123)
(define y (* x x))

1.1.4 复合过程

; 定义一个函数
(define (square x) (* x x))
; 在 racket 中,上式是下式的简写
; 相当于把一个 lambda 表达式赋值给一个变量
(define square (lambda (x) (* x x)))

1.1.5 过程应用的代换模型

  • 应用序求值 -> 先求值参数而后应用
  • 正则序求值 -> 完全展开而后归约 (thunk?)

考虑使用一个测试来判断是否为正则序还是应用序

(define (p x) (p x)) ; 在 racket 中,需要函数名字后面跟一个名字……,所以只能这么写
(define (test x y)
    (if (= x 0)
         0
         y))

考虑 (test 0 (p 1))
;; 如果是应用序,先考虑求解 test 函数的参数,即 0 和 (p 1),然而后者是个死循环,会卡死
;; 如果是正则序,会先展开
(if (= 0 0)
    0
    (p 1))
然后进入求值,看到 (= 0 0) 就直接返回了

1.1.6 条件表达式和谓词

;; 通过 cond 运算子,后会跟若干个 ((谓词), (结果)),谓词会解释为 true 和 false,会一个一个计算,知道为 true,就返回后面的结果。
;; 在 racket 里面 [] 和 () 这两种形式是可以互换的
(define (new-abs x)
  (cond [(> x 0) x]
        [(< x 0) (- x)]
        [(= x 0) 0]))
;; 当然也可以简写
(define (new-abs x)
  (cond [(< x 0) (- x)]
        [else x]))
;; 还可以用 if 做小分支
(define (new-abs x)
  (if (< x 0)
      (- x)
      x))
;; 还有 and or not 三个运算子,前两者具有短路效应

练习 1.3,求三个值中的最大的两个值的和

(define (max-of-two-sum a b c)
  (if (and (< a b) (< a c))
       (+ b c)
       (max-of-two-sum b c a)))
;; 如果 a 是最小的,那么当然返回的是 b + c
;; 否则的话,那么 a 肯定就不是最小的了,要么 b 最小,要么 c 最小
;; 那么就比较 b 和 c 的大小就好了,所以返回 (max-of-two-sum b c a)
;; 不能返回 (max-of-two-sum c b a) 的原因是因为,这个在递归的时候,无法遍历所有情况(下一次又到了 a b c)

1.1.7 采用牛顿法求平方根

原理见:http://blog.punkid.org/2008/02/28/compute-the-square-root-via-newtons-iteration

The contrast between function and procedure is a reflection of the general distinction between describing properties of things and describing how to do things, or as it is sometimes referred to, the distinction between declarative knowledge and imperative language

先考虑使用描述性的语言描述整个过程,然后实际上就很好解决这个问题了

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

;; improve
(define (improve y x)
  (average y
           (/ x y)))

;; average
(define (average a b)
  (/ (+ a b) 2))

;; good-enough?
(define (good-enough? y x)
  (< (abs (- y x)) 0.001))

练习 1.6

由于 Racket 的求值顺序是应用序的,所以参数在传进去的时候会先求值,后规约。此时满足不满足 new-if的条件都会运算另外一个分支,造成无限循环。

练习 1.7

;; good-enough?
(define (good-enough? y new-y)
  (< (abs (/ (- y new-y)
             y)) 0.01))

(define (sqrt-iter y x)
  (let ([new-y (improve y x)])
    (if (good-enough? y new-y)
      new-y
      (sqrt-iter new-y x))))

;; 这里使用 let,声明了一个临时变量,语法是
(let ([variable expr])
  ...)

1.1.8 过程作为黑箱抽象

块结构,可以在函数内部继续定义一些内部定义。可以帮助隐藏一些不需要使用者关注的过程。

Table of Contents