SICP 全笔记

a. The sum procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures.51 Write an analogous procedure called product that returns the product of the values of a function at points over a given range. Show how to define factorial in terms of product. Also use product to compute approximations to using the formula52

$$\frac{\pi}{4}=\frac{2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 \dots}{ 3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \dots} $$ b. If your product procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.

product 过程

product 过程与 sum 过程是非常类似的。

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

;; product tests begin
(load "../testframe.scm")
(assert= (product (lambda (x) x)
                  1
                  (lambda (x) (+ 1 x))
                  10)
         (* 2 3 4 5 6 7 8 9 10))

并且可以猜想这样的类似过程应该再抽象一次，于是有了 练习 1.32.

Wallis Product

题目中的

$$\frac{\pi}{4}=\frac{2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdot 8 \dots}{ 3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \dots} $$ 写为

$$\frac{\pi}{2}=\frac{2}{1} \cdot \frac{2}{3} \cdot \frac{4}{3} \cdot \frac{4}{5} \cdot \frac{6}{5} \dots $$ 于是，我们定义一个过程 f，它以代表第 n 项的 n 为参数，并返回第 n 项的数值。在 product 中的 next 过程即对当前处理的项目 k 不断加 1。

(define (factorial n)
  (define (identity x) x)
  (define (inc x) (+ 1 x))
  (product identity 1 inc n))

;; 1. tests begin

(assert= (factorial 1) 1)
(assert= (factorial 4) 24)

;;; 2. get pi from the wallis-product
(define (wallis-product n)
  (define (f item)
    (cond ((even? item) (/ item (+ item 1)))
          (else (/ (+ item 1) item))))
  (define (inc x)
    (+ x 1))
  (* 2.0 (product f 1 inc n)))

;;; spot the result
(wallis-product 10) ;Value: 3.002175954556907
(wallis-product 100) ;Value: 3.1260789002154112
(wallis-product 1000) ;Value: 3.1400238186005973
(wallis-product 10000) ;Value: 3.1414355935899083

迭代式的 product

依然可以参照 sum 的迭代式写出 product 的迭代过程：

(define (product/iter item a next b)
  (define (iter c result)
    (if (> c b)
        result
        (iter (next c)
              (* result (item c)))))
  (iter a 1))


(assert= (factorial/testing 4) 24)