为什么正态顺序和应用顺序评估没有给出相同的值？

Question

我正在阅读这本书计算机程序的结构和解释，第 2 版，第 21 页“应用顺序与正常顺序”小节中写道 -

可以证明，对于可以使用替换进行建模并产生合法值的过程应用程序，正常顺序和应用顺序评估会产生相同的值。 （参见练习 1.5，了解“非法”值的实例，其中正态顺序和应用顺序评估不会给出相同的结果。）

现在在上面提到的练习中，代码如下：

(define (p) (p))

(define (test x y)
  (if (= x 0) 0 y))

(test 0 (p))

如果我使用替代模型，

1. 检索

   test

   程序的主体：

(if (= x 0) 0 y)

2. 将形参

   x

   替换为参数 0，将

   y

   替换为参数

   (p)

   ：

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

(if #t 0 (p))

0

我认为

0

是方案中的合法值。

现在根据文本，正常顺序和应用顺序评估应该给出相同的结果。

正常订单评价：

1. 扩展（首先用操作数表达式替换参数）：

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

(if #t 0 (p))

2. 减少：

0

适用订单评估：

test

将根据定义的程序进行评估。

0

将评估为数字 O。

(p)

将评估为

(p)

，这将评估为

(p)

在评估参数

(p)

时，解释器将继续永远评估它（以无限递归的方式）。所以，我们不会得到表达式的值。

您可以看到，正常顺序给出了值，而应用顺序则没有。那么，如果替代模型给出了合法的值，那么为什么它们不一样呢？

Answer 1

给出定义

(define (p) (p))

替代模型是否为

(p)

提供了合法值？它有任何价值吗？

否：没有：计算无法终止。因此，在这种情况下，应用顺序和正常顺序并不等同。特别是，正常顺序将为表达式

(test 0 (p))

提供一个值，而应用顺序则不会。

事实上，鉴于上面

p

的定义，那么

(p)

根本没有值，因为它永远不会终止：这不依赖于使用替换模型，它只取决于

p

的定义这一事实是循环的：定义没有基本情况。

但是给定

(define (test x y)
  (if (= x 0) 0 y))

然后，在正常顺序评估下，

(test 0 (p))

将永远不会尝试评估

(p)

，因此将终止。另一方面，应用顺序评估，will尝试评估

test

的所有参数，因此将尝试评估

(p)

，但无法终止。