chili 默默学编程

SICP(3):计算过程


本文目录

1、代换模型

2、迭代和递归


代换模型

程序计算的过程,用的是代换模型(substitution model)

substitution model:

To evaluate an application:

- evaluate the operator to get procedure;

- evaluate the operands to get arguments;

- apply the procedure to the arguments:

- copy the body of the procedure,substituting the arguments supplied for the formal paremeters of the procedure

- evaluate the resulting new body


举了 2 个例子:

1、计算组合表达式的情况

(define (sos x y)
  (+ (sq x) (sq y)))

(define (sq x)
  (* x x))
(sos 3 4)
- (+ (sq 3) (sq 4))
- (+ (sq 3) (* 4 4))
- (+ (sq 3) 16)
- (+ (* 3 3) 16)
- (+ 9 16)
- 25

2、计算条件表达式的情况

To evaluate an IF expression:

- evaluate the predicate expression

- if it yields TRUE

evaluate the consequent expression

- otherwise

evaluate the alternative expression

(IF <predicate>
    <consequent>
    <alternative>)

迭代(iteration)和递归(recursion)

1、Peano arithmetic(两种全加法)

// iteration
(define (+ x y)
  (if (= x 0)
    y
    (+ (-1+ x) (1+ y))))

// linear recursion
(define (+ x y)
  (if (= x 0)
    y
    (1+ (-1+ x) y)))

2、画圆

(define (CIRCLE x y)
  (PLOT x y)
  (CIRCLE (- x (* y DT))
          (+ y (* x DT))))

3、Fibonacci numbers

// 指数递归
(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

// 迭代
(define (fib n)
  (define (fib2 a b c) 
    (if (= c 2) 
        (+ a b) 
        (fib2 b (+ a b) (- c 1))))
  (if (< n 2)
      n
      (fib2 0 1 n)))


reply ( 0 )