应用序和正常序
首先是区别,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
总是需要展开。