scheme - 评估过程是否按正常顺序(方案)进行？

Question

我正在研究SICP，ex1.20给出了以下代码:

    (define (gcd a b)
      (if (= b 0)
        a
        (gcd b (remainder a b))))

该问题询问当我们分别以应用顺序和正常顺序运行 (gcd 206 40) 时调用余数的次数。我可以算出余数按应用顺序被调用了 4 次，但我不明白为什么在正常顺序下它会变成 18 次。在我看来，首先调用 (gcd 40 (remainder 206 40))，接下来我们需要计算 (remainder 206 40)，如果我们想要的话，它是 6知道我们去哪个分支，然后(余数40 6)，依此类推，结果也是4次。但答案给出了以下过程:

     (gcd 206 40) 

     (if (= 40 0) ...) 

     (gcd 40 (remainder 206 40)) 

     (if (= (remainder 206 40) 0) ...) 

     (if (= 6 0) ...) 

     (gcd (remainder 206 40) (remainder 40 (remainder 206 40))) 

     (if (= (remainder 40 (remainder 206 40)) 0) ...) 

     (if (= 4 0) ...) 

     (gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 

     (if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0) ...) 

     (if (= 2 0) ...) 

     (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))) 

     (if (= (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0) ...) 

     (if (= 0 0) ...) 
     (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 

所以总共是18次。 我认为这两个答案之间的主要区别在于，我认为一旦计算出余数，就不需要再计算了，但答案似乎每次都会计算它。这是编译器的问题吗？这不是效率太低了吗？

Answer 1

编辑:实际上，我所描述的正常顺序是按名称调用。懒惰是按需调用，两者确实都是正常顺序。

---

对于应用顺序，您的直觉是正确的，即在函数调用之前对参数进行求值(即找出它们的值)。但按照正常顺序，它们仅在需要它们的值时在函数调用内部求值 - 然后，该值就被忘记了。顺便说一下，记住找到的值的正常顺序被称为“惰性评估”。

因此，评估应用顺序的归约序列为

> (gcd 206 40)
= (if (= 40 0) 206 (gcd 40 (remainder 206 40)))
= (gcd 40 (remainder 206 40))
> (remainder 206 40) => 6
= (gcd 40 6)
= (if (= 6 0) 40 (gcd 6 (remainder 40 6)))
= (gcd 6 (remainder 40 6))
> (remainder 40 6) => 4
= (gcd 6 4)
....

但对于正常订单来说，它会是

> (gcd 206 40)
= (if (= 40 0) 206 (gcd 40 (remainder 206 40)))
= (gcd 40 (remainder 206 40))
= (if (= (remainder 206 40) 0) 40 
                   (gcd (remainder 206 40) (remainder 40 (remainder 206 40))))
....

你可以看到差异。