这次回顾第三章第一部分习题。

学习资料:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm

https://github.com/DeathKing/Learning-SICP

https://mitpress.mit.edu/sites/default/files/sicp/index.html

https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454

参考资料:

https://sicp.readthedocs.io/en/latest

http://community.schemewiki.org/?SICP-Solutions

http://community.schemewiki.org/?sicp

3.1(p154)

(define (make-accumulator sum)
    (lambda (value)
        (begin (set! sum (+ sum value))
               sum)))

(define A (make-accumulator 5))
(display (A 10))
(newline)
(display (A 10))
(newline)
(exit)

结果如下:

15
25

3.2(p154)

(define (make-monitored function)
    (define cnt 0)
    (define f function)
    (define (how-many-calls?)
        cnt)
    (define (reset-count)
        (set! cnt 0))
    ; 求值
    (define (eval x)
        (begin (set! cnt (+ cnt 1))
               (f x)))
    (define (dispatch m)
        (cond ((eq? m 'how-many-calls?) (how-many-calls?))
              ((eq? m 'reset-count) (reset-count))
              (else (eval m))))
    dispatch)
    
(define s (make-monitored sqrt))
(display (s 100))
(newline)
(display "调用次数:")
(display (s 'how-many-calls?))
(newline)
(display (s 25))
(newline)
(display "调用次数:")
(display (s 'how-many-calls?))
(newline)
(display "reset")
(newline)
(s 'reset-count)
(display "调用次数:")
(display (s 'how-many-calls?))
(newline)
(exit)

结果如下:

10
调用次数:1
5
调用次数:2
reset
调用次数:0

备注:这里只考虑输入为合理的情形。

3.3(p154)

(define (make-account balance password)
    (define (withdraw amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                   balance)
            "Insufficient funds"))

    (define (deposit amount)
        (set! balance (+ balance amount))
        balance)

    (define (dispatch p m)
        (if (eq? p password)
            (cond ((eq? m 'withdraw) withdraw)
                  ((eq? m 'deposit) deposit)
                  (else (error "Unknown request -- MAKE-ACCOUNT"
                        m)))
            (lambda (x) "Incorrect password")))
    dispatch)

(define acc (make-account 100 'secret-password))
(display ((acc 'secret-password 'withdraw) 40))
(newline)
(display ((acc 'some-other-password 'deposit) 50))
(newline)
(exit)

结果如下:

60
Incorrect password

3.4(p154)

参考资料:

https://stackoverflow.com/questions/10036760/scheme-quicksort-exception-attempt-to-apply-non-procedure-1-2-3-4-5-7

(define (make-account balance password)
    (define cnt 0)
    (define (withdraw amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                   balance)
            "Insufficient funds"))
    (define (deposit amount)
        (set! balance (+ balance amount))
        balance)
    (define (call-the-cops amount)
        (error "Incorrect password for too many times!" amount))

    (define (dispatch p m)
        (if (eq? p password)
            ;通过则直接重置
            (begin  (set! cnt 0)
                    (cond ((eq? m 'withdraw) withdraw)
                          ((eq? m 'deposit) deposit)
                          (else (error "Unknown request -- MAKE-ACCOUNT" m))))
            (begin  (set! cnt (+ cnt 1))
                    (if (= cnt 7)
                        call-the-cops
                        (lambda (x) "Incorrect password")))))
    dispatch)

(define (test-k-times k)
    (if (= k 0)
        (display "finish")
        (begin ((acc 'some-other-password 'deposit) 1)
               (test-k-times (- k 1)))))

; test
(define acc (make-account 100 'secret-password))
(display ((acc 'secret-password 'withdraw) 1))
(newline)
(test-k-times 6)
(newline)
; 重置cnt
(display ((acc 'secret-password 'withdraw) 1))
(newline)
(test-k-times 6)
(newline)
(test-k-times 1)
(newline)
(exit)

结果如下:

99
finish
98
finish
Exception in error: invalid message argument 1 (who = "Incorrect password for too many times!", irritants = ())

3.5(p157)

将问题推广为椭圆的情形:

(load "helper.scm")

(define (experiment x1 x2 y1 y2)
    (define a (/ (abs (- x1 x2)) 2))
    (define b (/ (abs (- y1 y2)) 2))
    (define x0 (/ (+ x1 x2) 2))
    (define y0 (/ (+ y1 y2) 2))
    (define x (random-in-range x1 x2))
    (define y (random-in-range y1 y2))
    (< (+ (/ (square (- x x0)) (square a))
          (/ (square (- y y0)) (square b)))
       1))

(define (estimate-integral experiment x1 x2 y1 y2 trials)
    ; pi * a * b / (4 * a * b) = p
    ; pi = 4 * p
    (define (get-pi p)
        (* 4 p))
    (define (iter trials-remaining trials-passed)
        (cond ((= trials-remaining 0)
               (/ trials-passed trials))
              ((experiment x1 x2 y1 y2)
               (iter (- trials-remaining 1) (+ trials-passed 1)))
              (else
               (iter (- trials-remaining 1) trials-passed))))
    (get-pi (iter trials 0.0)))

(display (estimate-integral experiment 0.0 10.0 10.0 30.0 1000))
(newline)
(display (estimate-integral experiment 0.0 1.0 3.0 10.0 10000))
(exit)

结果如下:

3.148
3.1468

3.6(p157)

(load "ch3support.scm")

(define random-init 7)
(define (rand x)
    (define (generate)
        (begin (set! x (rand-update x))
                x))
    (define (reset new-value)
        (begin (set! x new-value)
                new-value))
    (define (dispatch m)
        ; 这里如果使用generate, 则返回的是过程
        (cond ((eq? m 'generate) (generate))
              ((eq? m 'reset) reset)
              (else (error "Unknown request" m))))
    dispatch)

(define rand-num (rand random-init))
(display (rand-num 'generate))
(newline)
(display ((rand-num 'reset) 10))
(newline)
(exit)

结果如下:

88
10

3.7(p161)

(define (make-account balance password)
    ; 密码存储在passwords中, len为密码个数
    (define passwords (list password))
    (define len 1)

    (define (withdraw amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                   balance)
            "Insufficient funds"))
    (define (deposit amount)
        (set! balance (+ balance amount))
        balance)

    ; 判断密码
    (define (judge-password passwords p)
        (define (judge-password-iter passwords p l)
            (if (= l len)
                #f
                (or (eq? (car passwords) p)
                    (judge-password-iter (cdr passwords) p (+ l 1)))))
        (judge-password-iter passwords p 0))

    ; 更新密码
    (define (add-password p)
        (set! passwords (append passwords (list p)))
        (set! len (+ len 1)))

    (define (dispatch p m)
        (if (judge-password passwords p)
            (cond ((eq? m 'withdraw) withdraw)
                  ((eq? m 'deposit) deposit)
                  ((eq? m 'add-password) add-password)
                  (else (error "Unknown request -- MAKE-ACCOUNT"
                        m)))
            ; f))
            (lambda (x) "Incorrect password")))
    dispatch)

(define (make-joint account p1 p2)
    (begin ((account p1 'add-password) p2)
            account))

(define peter-acc (make-account 100 'secret-password))
(display ((peter-acc 'secret-password 'withdraw) 40))
(newline)
(display ((peter-acc 'some-other-password 'deposit) 50))
(newline)
; 关联账户
(define paul-acc
   (make-joint peter-acc 'secret-password 'some-other-password))
; 对比结果
(display "paul's account: ")
(display ((paul-acc 'some-other-password 'deposit) 50))
(newline)
(display "peter's account: ")
(display ((peter-acc 'secret-password 'deposit) 0))
(newline)
(exit)

结果如下:

60
Incorrect password
paul's account: 110
peter's account: 110

3.8(p162)

(define (get-f v)
    (define (f x)
        (begin (set! v (* v x))
                v))
    f)

(define f1 (get-f 1))
(define f2 (get-f 1))

; 对比
(display (+ (f1 0) (f1 1)))
(newline)
(display (+ (f2 1) (f2 0)))
(exit)

结果如下:

0
1

后续三题见参考资料,大佬整理的很详细。

3.9(p167)

参考资料:

https://sicp.readthedocs.io/en/latest/chp3/9.html

递归版本:

全局环境:

  • factorial

新环境:

  • E1: n = 6, 指向全局环境。
  • E2: n = 5, 指向全局环境。
  • E3: n = 4, 指向全局环境。
  • E4: n = 3, 指向全局环境。
  • E5: n = 2, 指向全局环境。
  • E6: n = 1, 指向全局环境。

迭代版本:

全局环境:

  • factorial, fact-iter

新环境:

  • E1: n = 6, 指向全局环境。
  • E2: product = 1, counter = 1, max-count = 6, 指向全局环境。
  • E3: product = 1, counter = 2, max-count = 6, 指向全局环境。
  • E4: product = 2, counter = 3, max-count = 6, 指向全局环境。
  • E5: product = 6, counter = 4, max-count = 6, 指向全局环境。
  • E6: product = 24, counter = 5, max-count = 6, 指向全局环境。
  • E7: product = 120, counter = 6, max-count = 6, 指向全局环境。
  • E7: product = 720, counter = 7, max-count = 6, 指向全局环境。

3.10(p170)

参考资料,这题貌似有点问题,函数应该是我下面的写法更合适:

https://sicp.readthedocs.io/en/latest/chp3/10.html

(define (make-withdraw1 initial-amount)
  (let ((balance initial-amount))
    (lambda (amount)
      (if (>= balance amount)
          (begin (set! balance (- balance amount))
                 balance)
          "Insufficient funds"))))

(define (make-withdraw2 initial-amount)
    ((lambda (balance)
        (lambda (amount)
            (if (>= balance amount)
                (begin (set! balance (- balance amount))
                        balance)
                "Insufficient funds")))
     initial-amount))

; test
(define W1 (make-withdraw1 100))
(display (W1 50))
(newline)
(define W2 (make-withdraw2 100))
(display (W2 50))
(newline)
(exit)

结果如下:

50
50

3.11(p173)

参考资料:

https://sicp.readthedocs.io/en/latest/chp3/11.html