应用序和正常序

首先是区别,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_itermy_if会一直递归下去,而加入不使用my_if而直接使用if就不会出现无限递归。上面的Scheme代码也是如此,结论就是打算使用cond来替代if是不行的,无论是应用序还是正则序都不行,因为系统自带的if是特殊处理的,而自定义的my_if总是需要展开。