lisp.org

Table of Contents

1 sicp   export

1.1 ch1

In the definition of good-enough? above, guess and x are bound variables but <, -, abs, and square are free. The meaning of good-enough? should be independent of the names we choose for guess and x so long as they are distinct and different from <, -, abs, and square. (If we renamed guess to abs we would have introduced a bug by capturing the variable abs. It would have changed from free to bound.) The meaning of good-enough? is not independent of the names of its free variables, however. It surely depends upon the fact (external to this definition) that the symbol abs names a procedure for computing the absolute value of a number. Good-enough? will compute a different function if we substitute cos for abs in its definition.

1.1.1 1.1.5 过程的代换模型

1.1.2 1.2 过程与它们所产生的计算

    ;;;阶乘factorial
    ;;迭代
    (define (factorial n)
        (fact-iter 1 1 n))

    (define (fact-iter product counter max-count)
        (if (> counter max-count)
            product 
            (fact-iter (* counter product)
                       (+ counter 1)
                       max-count)))

    ;;递归
    (define (factorial n)
        (if (= n 1)
            1
            (* n (factorial (- n 1)))))

    ;;;菲波纳切数
    ;;树形递归
    (defun fib(n)
      (cond ((= n 1) 1)
            ((= n 0) 0)
            (t (+ (fib (1- n)) (- n 2)))))
    ;;线性迭代
    ;;法1
    (defun fib(n)
      (labels ((fib-iter (pa pb counter max-counter)
                 (cond ((> counter max-counter )
                        pb)
                       (t (fib-iter pb (+ pa pb) (1+ counter) max-counter)))))
        (fib-iter 0 1 1  n)))
    ;;法2
    (defun fib (n)
      (labels ((fib-iter (b a count)
                 (if (= count 0) 
                     b
                     (fib-iter (+ b a) b (1- count)))))
        (fib-iter 1 0 n)))

    ;;树形递归
    (defun foo (n)
      (cond ((= n 0) 0)
            ((= n 1) 1)
            ((= n 2) 2)
            (t (+ (foo (1- n)) (* 2 (foo (- n 2))) (* 3 (foo (- n 3)))))))
    ;;线性迭代
    (defun foo (n)
      (labels ((iter (c b a i)
                 (if (= i 2) c
                     (iter (+ c (* 2 b) (* 3 a)) c b (1- i)))))
        (iter 2 1 0 n)))


    ;;;SECTION 1.2.3
    ;;EXERCISE 1.15  正统sin(x)的数值计算
    (define (cube x) (* x x x))

    (define (p x) (- (* 3 x) (* 4 (cube x))))

    (define (sine angle)
        (if (not (> (abs angle) 0.1))
            angle
            (p (sine (/ angle 3.0)))))



    ;;;SECTION 1.2.4

    ;; Linear recursion
    (define (expt b n)
        (if (= n 0)
            1
            (* b (expt b (- n 1)))))


    ;; Linear iteration
    (define (expt b n)
        (expt-iter b n 1))

    (define (expt-iter b counter product)
        (if (= counter 0)
            product
            (expt-iter b
                       (- counter 1)
                       (* b product)))) 

    ;; Logarithmic recursion
    (define (fast-expt b n)
        (cond ((= n 0) 1)
              ((even? n) (square (fast-expt b (/ n 2))))
              (else (* b (fast-expt b (- n 1))))))

    (define (even? n)
        (= (remainder n 2) 0))

    ;;最佳答案
    (define (iter-fast-expt b n) 
        (define (iter N B A) 
            (cond ((= 0 N) A) 
                  ((even? N) (iter (/ N 2) (square B) A)) 
                  (else (iter (- N 1) B (* B A))))) 
      (iter n b 1)) 

    ;;ex1.17
    (defun mul (a b)
      (labels ((mul-iter (a b c)
                 (cond ((zerop b)   c)
                       ((evenp b)  (mul-iter (dou a) (hal b) c))
                       (t   (mul-iter a  (1- b)  (+ c a)))))
               (dou (n)
                 (* n 2))
               (hal (n)
                 (/ n 2)))
        (mul-iter a b 0)))

        ;;;1.2
  (defun smallest-divisor  (n)
             (labels ((find-divisor (n test-divisor)
                        (cond ((> (square test-divisor) n) n)
                              ((zerop (mod n test-divisor)) test-divisor)
                              (t (find-divisor n (1+ test-divisor)))))
                      (square (i)
                        (* i i)))
               (find-divisor n 2)))

  (defun prime? (n)
    (if (= 1 n) nil
        (= (smallest-divisor n) n)))

;;判断素数的九行scheme代码
  (define (smallest-div n) 
      (define (divides? a b) 
          (= 0 (remainder b a))) 
    (define (find-div n test) 
        (cond ((> (sq test) n) n) ((divides? test n) test) 
              (else (find-div n (+ test 1))))) 
    (find-div n 2)) 

  (define (prime? n) 
      (if (= n 1) false (= n (smallest-div n)))) 

  ;;;ex 1.22
  (let ((n (truncate 1e17)))
               (loop for i upto 100 do
                 (if (prime? (+ n i))
                    (print (+ n i) )))) ;;=> search a prime number

  (timed-prime-test 99999998430674959 ) ;;=>  elapsed time is 8 second 

  (defun timed-prime-test( n)
               (print n)
             (start-prime-test n (get-universal-time)))

  (defun start-prime-test (n start-time)
             (if (prime? n)
                 (report-prime (- (get-universal-time) start-time))))

  (defun report-prime ( elapsed-time)
               (print " *** ")
             (print  elapsed-time))

  ;;;1.2.6 fermat-prime?
  (defun expmod (base exp  m)
             (labels ((square (i)
                        (* i i)))
               (cond ((zerop exp) 1)
                     ((evenp exp) 
                      (mod (square (expmod base (/ exp 2) m))
                           m))
                     (t  (mod (* base (expmod base (1- exp) m))
                              m)))))

  (defun fermat-test (n)
             (labels ((try-it (a)
                        (= (expmod a n n) a)))
               (try-it (1+ (random (1- n))))))

  (defun fast-prime? (n times)
             (cond ((zerop times ) 
                    t)
                   ((fermat-test n)   
                    (fast-prime? n (1- times)))
                   (t nil)))

  (loop repeat 100
              count (fast-prime? 6 1))   =>58
  ;;数字6被单次的费马测试判断为素数的概率为60%左右。但可以知道数字6被10次的费马测试判断为素数的概率接近于0。同时,对于越大的非素数,一般来说其通过单次费马测试越难,因为相对于大数n,其基本无法找到一个数a<n,使(mod a^n n)= a ,而这为素数的必备。
  ;;大于100的整数被单次费马测试误判为素数的概率接近于0。

1.1.3 1.3 用高阶函数做抽象

;;一个连续求和过程
  (define (sum term a next b) 
      (if (> a b) 
          0
          (+ a (sum term (next a) next b))))

  (define (itersum term a next b) 
      (define (iter a result) 
          (if (> a b) 
              result 
              (iter (next a) (+ result (term a))))) 
    (iter a 0)) 
;;用sum过程定义积分integral
;;根据积分的定义可知,只需要对sum过程定义一个较小的步长dx,然后对sum过程得到的值乘以dx即可
(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2)) add-dx b)
     dx))

;: (integral cube 0 1 0.01)



  ;;1.31 定义连乘过程的递归计算过程或迭代计算过程
  (define (product term a next b)
      (if (> a b)
          1
          (* (term a) (product term (next a) next b))))

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



  ;;1.32 用更一般的计算过程accumulate 来定义连续加法和连续乘法
  (define (accumulate combiner null-value term a next b)
      (if (> a b )
          null-value
          (combiner (term a) (accumulate combiner null-value term (next a) next b))))

  (define (sum-acc term a next b)
      (define (combiner x y)
          (+ x y))
    (accumulate combiner 0 term a next b))

  (define (product-acc term a next b)
      (define (combiner x y)
          (* x y))
    (accumulate combiner 1 term a next b))

  ;;迭代过程
  (define (accumulate combiner null-value term a next b) 
      (define (iter a res) 
          (if (> a b) res 
              (iter (next a) (combiner res (term a))))) 
    (iter a null-value)) 

  ;;1.33 含有谓词筛选的连续计算过程filter-accumulate
  (define (filtered-accumulate combiner null-value term a next b filter) 
    (if (> a b) null-value 
        (if (filter a) 
            (combiner (term a) (filtered-accumulate combiner null-value term (next a) next b filter)) 
            (filtered-accumulate combiner null-value term (next a) next b filter))))

  ;; ;;两个数的最大公约数的欧几里得算法
  ;;  (define (gcd m n) 
  ;;    (cond ((< m n) (gcd n m)) 
  ;;          ((= n 0) m) 
  ;;          (else (gcd n (remainder m n))))) 

  ;;  (define (relative-prime? m n) 
  ;;  (= (gcd m n) 1)) 

  ;;filter-accumulate 用于计算所有与n互素(且小于n)的数的乘积。
   (define (product-of-relative-primes n) 
     (define (filter x) 
       (relative-prime? x n)) 
   (filtered-accumulate * 1 identity 1 inc n filter)) 

;;练习1.43
;;(repeated f n) 得到单参数过程f重复执行N次的单参数过程。
(define (repeated f n)
          (cond ((= n 1) (lambda (x) (f x)))
                (else (lambda (x) (f ((repeated f (- n 1)) x))))))
;;((repeated inc  3) 1) => 4
1.1.3.1 1.3.2 用lambda表达式构造过程

lambda用与define同样的方式创建过程,二者创建的过程完全一样,但lambda式不为有关过程提供名字,即不能使该过程与环境中的任何名字相关联。
事实上,以下两式等价。
(define (plus4 x) (+ x 4))
(define plus4 (lambda (x) (+ x 4)))
由此,也易于理解,在scheme内部一个名字以何种方式指向一个函数。即,当用define 式定义了一个函数后(假设名为plus4),那么plus4名字将唯一地指向该函数对象,
并且其有两种使用情况,位于列表的首个位置或其他位置时,名字foo的意义也是相同的,即都指代一个过程(lambda (x) (+ 4))。
所以,lambda式的出现也就不足为怪了。
以下两式等价
(plus4 1) => 5
((lambda (x) (+ x 4)) 1) => 5

;;;SECTION 1.3.3

;; Half-interval method

(define (search f neg-point pos-point)
  (let ((midpoint (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond ((positive? test-value)
                 (search f neg-point midpoint))
                ((negative? test-value)
                 (search f midpoint pos-point))
                (else midpoint))))))

(define (close-enough? x y)
  (< (abs (- x y)) 0.001))

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) (positive? b-value))
           (search f a b))
          ((and (negative? b-value) (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of opposite sign" a b)))))


;: (half-interval-method sin 2.0 4.0)

;: (half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
;:                       1.0
;:                       2.0)


;; Fixed points

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

1.1.4 迭代与递归

P22页讲述二者区别????插入图片

cat/spider image

Figure 1: 递归与迭代的区别

1.2 ch2

1.2.1 ????疑问

ex2.38

;; 得到集合s的所有排序
(define (permutations s)
  (if (null? s)                         ; empty set?
      (list nil)                        ; sequence containing empty set
      (flatmap (lambda (x)
                 (map (lambda (p) (cons x p))
                      (permutations (remove x s))))
               s)))
;; (permutations '(1 2)) => ((1 2) (2 1))

(define (remove item sequence)
  (filter (lambda (x) (not (= x item)))
          sequence))

;;Nested mappings P84
;;嵌套映射可以用来枚举区间,有点像嵌套的 do 或者 loop ,不同的是append操作最终将枚举的结果全部放入一个单层表中
;: (accumulate append
;:             nil
;:             (map (lambda (i)
;:                    (map (lambda (j) (list i j))
;:                         (enumerate-interval 1 (- i 1))))
;:                  (enumerate-interval 1 n)))

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))
;;(flatmap (lambda (i)
;:                    (map (lambda (j) (list i j))
;:                         (enumerate-interval 1 (- i 1))))
;:                  (enumerate-interval 1 3))   => ((2 1) (3 1) (3 2))
;;同样的枚举效果在SBCL中的代码为:
(let (var)
   (loop for i upto 3  do
      (loop for j from 0 upto (1- i) do
         (push (list i j) var)))
  (reverse var))
;;=> ((2 1) (3 1) (3 2))

1.2.2 2.4 抽象数据的多重表示

cat/spider image

Figure 2: 通用函数定义

1.2.3 2.3 符号数据!!!!

(car ''a) => quote
;; (car ''something) is treated by the interpreter as:
;; (car (quote (quote something)))
;; The first occurrence of 'quote' quotes the next entity
;; (quote something),which is actually a list with two elements, so
;; caring this list yields 'quote.

1.2.3.1 2.3.4 Huffman编码树!!!!
1.2.3.2 尝试同时使用不同的数据结构

表 - 有序表 - 二叉平衡树
增长速度:n2 - n - log(n)

1.2.4 2.2 层次性数据和闭包性质

  (define (map proc items)
    (if (null? items)
        nil
        (cons (proc (car items))
              (map proc (cdr items)))))

  (define (count-leaves x)
    (cond ((null? x) 0)
          ((not (pair? x)) 1)
          (else (+ (count-leaves (car x))
                   (count-leaves (cdr x))))))

  (define (deep-reverse items) 
              (define (iter items result) 
                (cond  ((null? items)    result) 
                       ((pair? (car items))   
                        (iter (cdr items) (cons (deep-reverse (car items)) result)))
                       (else
                          (iter (cdr items) (cons (car items) result)))))
              (iter items ()))

  ;;ex2.28

;; 注意遍历多层树的关键在于深层表的脱括号,本定义第三行为关键,即一旦发现items的car 为一个表,则将items变化:将原car 的子表脱括号后置于items表的前面。
 (define (fringe items) 
   (cond ((atom? items) items)
         ((pair? (car items)) (fringe (cons (caar items) (cons (cdar items) (cdr items))))) 
         ((null? (car items)) (fringe (cdr items))) 
         (else (cons (car items) (fringe (cdr items)))))) 
;;!!!!以上定义不够简明,根据SICP,fringe应该为这样一个树形的枚举enumerate-tree(借助于append)。
(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))

 ;; Also works with empty sub-lists: 
 (fringe '(1 2 3 (4 5) 6 () (((7 (8 9) (()) 10) 11) 12))) 
 ;;Value: (1 2 3 4 5 6 7 8 9 10 11 12) 

;;ex2.29
;;我的计算二叉活动体的总重量过程
;;原来想不定义局部过程rec-weight-branch而只使用total-weight 一个过程在多层次数据中递归使用
;;但事实是,mobile二叉活动体的枝和主体层数据结构有明显的不同,不是简单的脱括号操作可以实现的,
;;所以必须单独定义一个局部子过程rec-weight-branch用于计算枝的重量
;;由此可见,对总体过程total-weight来说,第一时间明确和提出主过程(+ left-branch-weight right-branch-weight )是重要的
(define (total-weight mobile)
            (define (rec-weight-branch  bran)
              (cond ((atom?  (cadr bran)) (cadr bran))
                    (else  (total-weight (cadr bran)))))
           (+ (rec-weight-branch (left-branch mobile))
              (rec-weight-branch (right-branch mobile))))

;;我的计算二叉活动体平衡的过程
;;注意思考的逻辑流程,如果逻辑流程是对的,那么代码也变得水到渠成。比如定义check-balance mo : 定义基本过程check-base mo=> T 表示mo最外层满足平衡; 且 如果 左枝结构为一个表(活动体)left,则继续 check-balance left (注意此处不能用check-base,因为其没有向深层递归的能力) ; 右枝同左枝。
(define (weight x)
          (if (pair? x)    (total-weight x) x))

(define (check-balance mo)
          (define (check-base mo1)
            (if (pair? mo1)
               (= (* (branch-length (left-branch mo1)) (weight (branch-structure (left-branch mo1))))
                  (* (branch-length (right-branch mo1)) (weight (branch-structure (right-branch mo1)))))
               #t))
       (and (check-base mo)
            (let ((left (branch-structure (left-branch mo)))
                  (right (branch-structure (right-branch mo))))
               (and  (if (pair?  left)
                        (check-balance left)    #t)
                     (if (pair?  right)
                        (check-balance right)    #t)))))

1.2.4.1 序列操作有助于模块化
;; Sequence operations

;: (map square (list 1 2 3 4 5))

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

;: (filter odd? (list 1 2 3 4 5))

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

;: (accumulate + 0 (list 1 2 3 4 5))
;: (accumulate * 1 (list 1 2 3 4 5))
;: (accumulate cons nil (list 1 2 3 4 5))

;; EXERCISE 2.36
;; 对多个子表组成的表seqs,沿多个子表的元素逐个执行累积
(define (accumulate-n op init seqs)
           (if (null? (car seqs))
                nil
               (cons (accumulate op init (map car seqs))
                     (accumulate-n op init (map cdr seqs)))))
;;(accumulate-n + 0 '((1 2) (3 4))) => (4 6)

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))

;: (enumerate-interval 2 7)

(define (enumerate-tree tree)
  (cond ((null? tree) ())
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))

;: (enumerate-tree '( 1 ( 2 3))) => (1 2 3)

(define (sum-odd-squares tree)
  (accumulate +
              0
              (map square
                   (filter odd?
                           (enumerate-tree tree)))))

;;利用horner规则求多项式
(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) 
                    (+ (* higher-terms x) this-coeff))
              0
              coefficient-sequence))
;;(horner-eval 3 '(1 2 3)) => 34              

1.2.4.2 利用序列映射定义矩阵运算
(define (dot-product w v )
        (accumulate + 0 (map * w v)))
;;(dot-product '(1 2 3) '(4 5 6)) => 32

(define (matrix-*-vector m v)
         (map (lambda (w) (dot-product w v)) m))
;;(matrix-*-vector '((1 2)(3 4))  '(2 3)) => (8 18)

(define (transpose mat)
        (accumulate-n cons nil mat))
;;(transpose '((1 2)(3 4))) => ((1 3) (2 4))

(define (matrix-*-matrix m n)
           (let ((cols (transpose n)))
             (map (lambda (w) (matrix-*-vector cols w)) m)))
1.2.4.3 对表和树的映射

由以下的多个示例可知,树的映射和表的映射有明显差异,即树的映射在CAR和CDR两个方向(树状)都产生递归,而对表的映射则只通过CAR项进行遍历。

(define (copy-list lst)
           (cond ((null? lst) ())
              (else (cons (car lst) (copy-list (cdr lst))))))

(define (copy-tree tree)
      (define (atom? x) (not (pair? x)))
          (cond ((atom?  tree ) tree)
                (else (cons (copy-tree (car tree)) (copy-tree (cdr tree)) ))))

;;!!!!实现copy-tree的另一种方法是将树看成子树的序列,并对它使用map。对于基础情况,也就是当被处理的子树是树叶时,就直接返回它; 如果某棵子树不为树叶,则对其使用copy-tree 进入下一次深入处理(map 操作相当于进行了一次脱括号,而带有map的函数copy-tree被递归调用,可以不断地脱括号)。
;;这种map加递归的组合,可以实现对树的操作,但似乎只适合于对tree中任意位置数据无差别单次操作的情况,即无法针对树中的结构化数据进行操作
(define (copy-tree tree)
        (map (lambda (sub-tree)
                (if (atom? sub-tree) sub-tree 
                    (copy-tree sub-tree)))
              tree))

;;进一步抽象,对于树的映射 fun,总可以使用(tree-map fun tree)实现
(define (tree-map fun tree)
         (map (lambda (sub-tree)
                  (if (atom? sub-tree) (fun sub-tree)
                      (tree-map fun sub-tree)))
               tree))
;;(tree-map square '(1 2 3 (4 5))) =>  (1 4 9 (16 25))


;;????EX2.32


;; Mapping over lists P70
(define (scale-list items factor)
  (if (null? items)
      nil
      (cons (* (car items) factor)
            (scale-list (cdr items) factor))))

;; Mapping over trees
(define (scale-tree tree factor)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (* tree factor))
        (else (cons (scale-tree (car tree) factor)
                    (scale-tree (cdr tree) factor)))))

1.2.4.4 2.2.4 ????一个图形语言

画家

1.2.5 2.1 数据意味着什么

一般而言,我们总可以将数据定义为一组适当的构造函数和选择函数,以及它们必须满足的一组条件。
数据的过程性表示很重要,有关的程序设计风格称为消息传递。比如,可以用如下过程性表示方式定义序对cons。

(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

 (define (cons a b) 
   (lambda (m) (m a b))) 

;; ex 2.6 丘奇计数——正整数的一种过程性表示
;; 即将正数n表示为对任意过程f执行n次的过程。
;; 任意丘奇数的表示可由丘奇数zero和add-1操作直接得到。
;; 由此处丘奇数系统的建立,easily found that it's important and needed for scheme language
;; to have a unique name space (for variable and produce along).同时,scheme语言中一个代表了过程的名字,将直接出现在表的第一位,以使过程被执行。
;; 进一步地,可以认为,在scheme 中,所有的计算,事实上是在进行各种过程的计算,而scheme的极简语法将使这种过程计算的字面表达变得可能。


(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

 (define zero 
     (lambda (f) (lambda (x) x))) 
 (define one 
     (lambda (f) (lambda (x) (f x)))) 
 (define two 
     (lambda (f) (lambda (x) (f (f x))))) 



1.3 ch3

1.3.1 EXERCISE

;; EXERCISE 3.1 
;; 定义一个累加器,一个累加器是一个过程,反复用数值参数调用它,会使它的各个参数累加到一个和数中。
;: (define A (make-accumulator 5))
;: (A 10)
;: (A 10)
(define (make-accumulator balance)
            (lambda (x)
               (begin (set! balance (+ balance x))
                  balance)))

;; EXERCISE 3.2
;;make-monitor 用于返回一个过程,其可给出指定函数被调用的次数。
;: (define s (make-monitored sqrt))
;: (s 100)
;: (s 'how-many-calls?)
(define (make-monitored fun)
   (define (make-accumulator balance)
            (lambda (x)
               (set! balance (+ balance x))))
   (define a2 (make-accumulator 0))
   (lambda (n)
        (cond ((eq? n 'how-many-calls?) (a2 0))
              (else (begin (a2 1)(fun n) )))))

;; EXERCISE 3.3
;;创建一个带密码的账户,其返回一个过程,该过程可根据符号参数执行现金存取操作。
 (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) 
     (cond ((not (eq? p password)) (lambda (x) "Incorrect password")) 
           ((eq? m 'withdraw) withdraw) 
           ((eq? m 'deposit) deposit) 
           (else (error "Unknown request -- MAKE-ACCOUNT" m)))) 
   dispatch) 

;; EXERCISE 3.5
;;蒙特卡洛方法计算面积
(define (circle-test)
        (let ((x (random-in-range 2.0 8.0))
              (y (random-in-range 4.0 10.0)))
          (< (+ (square (- x 5))
                (square (- y 7)))
             9)))

(define (monte-carlo trials experiment)
         (define (iter trials-remaining trials-passed)
              (cond ((= trials-remaining 0) 
                     (/ trials-passed  trials))
                    ((experiment)
                     (iter  (- trials-remaining 1) (+ 1 trials-passed)))
                    (else 
                       (iter  (- trials-remaining 1)  trials-passed))))
          (iter trials 0))

(define (estimate-pi trials)
         (* (monte-carlo trials circle-test) (/ 36 9.0)))

;; EXERCISE 3.5

(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 pwd m) 
      (if (eq? m 'auth) 
          (lambda () (eq? pwd password)) 
          (if (eq? pwd password) 
              (cond ((eq? m 'withdraw) withdraw) 
                    ((eq? m 'deposit) deposit) 
                    (else (error "Unknown request -- MAKE-ACCOUNT" m))) 
              (error "Incorrect password")))) 
  dispatch) 

(define (make-joint account orig-pwd joint-pwd) 
  (define (withd raw amount) ((account orig-pwd 'withdraw) amount)) 
  (define (deposit amount) ((account orig-pwd 'deposit) amount)) 
  (define (dispatch pwd m) 
      (if (eq? m 'auth) 
          (lambda () (eq? pwd joint-pwd)) 
          (if (eq? pwd joint-pwd) 
              (cond ((eq? m 'withdraw) withdraw) 
                    ((eq? m 'deposit) deposit) 
                    (else (error "Unknown request -- MAKE-ACCOUNT" m))) 
              (error "Incorrect password")))) 

  (if ((account orig-pwd 'auth)) 
      dispatch 
      (error "Incorrect original password of target account"))) 

cat/spider image

Figure 3: 蒙特卡洛方法计算面积积分

1.3.2 3.1.1 局部状态变量(银行账户)

cat/spider image

Figure 4: 3.1.1局部变量(银行账户)

(define (make-accumulator balance)
            (lambda (x)
               (set! balance (+ balance x))))

(define (make-monitored fun)
         (define a1 (make-
           (lambda (n)
             (cond (
(define (make-monitored fun)
         (define a1 (make-accumulator 0))
           (lambda (n)
             (cond ((eq? n how-many-calls?) (

1.3.3 3.1.3 引进赋值的代价

只要我们不使用赋值,以同样的参数对同一过程求值两次一定产生出同样的结果。因此可以认为过程是在计算数学函数。不用任何赋值的程序设计称为函数式程序设计。
如果一个语言支持在表达式里“同一的东西可以相互替换”的观念,这样替换不会改变有关表达式的值,这个语言就称为是具有引用透明性。在我们的计算机语言里包含了SET!之后,也就打破了引用透明性,就使确定能否通过等价的表达式代换去简化表达式变成了一个异常错综复杂的问题了。

Author: lispsu

Validate