应用序和正常序

首先是区别，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总是需要展开。