应用序和正常序

应用序和正常序

首先是区别，Ben Bitdiddle发明了一种检测方法，如下

(define (p) (p))

(define (test x y)

(if (= x 0) 0 y))

再来看，牛顿法求平方根

(define (abs x)

(if (> x 0) x (- x)))

(define (good-enough? guess x)

(if (< (abs (- (* guess guess) x)) 0.001) #t #f))

;; can't replace if to my-if

(define (my-if pred then otherwise)

(cond ((pred) (then))

(else (otherwise))))

(define (average x y)

(/ (+ x y) 2))

(define (guess-again guess x)

(average guess (/ x guess)))

(define (sqrt-iter guess x)

(if (good-enough? guess x)

guess

(sqrt-iter (guess-again guess x) x)))

(define (sqrt x)

(sqrt-iter 1.0 x))

对于第一段代码，如果运行

(test 0 (p))

会发现程序会一直运行下去，直到内存耗尽。这是因为Scheme是一种应用序语言，应用序（applicative order)的是，对一个表达式，在进行求值前会对其进行展开，对于第一段代码：

(test 0 (p))

(if (= 0 0) 0 (p))

(if (= 0 0) 0 (p))

(if (= 0 0) 0 (p))

...

简单来说，就是在求解if的值之前会将所有的表达式进行展开，然而表达式(p)的值也是一个表达式(p)，因此就这样不停的进行展开，最后内存耗尽。

与之想反的另一种方式叫做正则序(nomal order)，对于上面代码，会将0带入计算，发现0已经匹配便不再对剩余的部分进行展开。换句话说，只有在用到的时候才会计算，也叫做lazy evaluation。

对于第二段代码，如果运行

(sqrt 4)

同样会发现程序一直运行下去，直到内存耗尽。为了解释，看看下面这段C的翻译

使用C语言强制将if实现为过程

double my_if(bool pred, double then, double otherwise)

{

if(pred)

{

return then;

}

return otherwise;

}

...

double sqrt_iter(double guess, double x)

{

return my_if(good_enough(guess, x), guess, sqrt_iter(guess_again(guess, x), x));

}

发现在sqrt_iter中my_if会一直递归下去，而加入不使用my_if而直接使用if就不会出现无限递归。上面的Scheme代码也是如此，结论就是打算使用cond来替代if是不行的，无论是应用序还是正则序都不行，因为系统自带的if是特殊处理的，而自定义的my_if总是需要展开。