评估流程是否正常（Scheme）？

Question

正在研究SICP，ex1.20给出如下代码：

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

题目问的是当我们运行(gcd 206 40)分别按应用顺序和正常顺序调用remainder的次数。我可以弄清楚余数在应用顺序中被调用了 4 次，但我不明白为什么在正常顺序时它会变成 18 次。在我看来，首先调用(gcd 40 (remainder 206 40))，接下来我们需要计算(remainder 206 40)，也就是6，如果我们想知道我们去到哪个分支，然后(remainder 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

edit：实际上，我所说的正常顺序是call-by-name。懒是按需调用确实都是正常顺序

您的直觉对于应用顺序是正确的，在函数调用之前评估参数（即找出它们的值）。但在正常顺序中，它们仅在 inside 函数调用中被评估，当需要它们的值时 - 然后，这个值被遗忘。顺便说一句，记住找到的值的正常顺序称为 lazy 评估。

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

> (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))))
....

你可以看出区别。

评估流程是否正常（Scheme）？

The evaluation process in normal order(Scheme)?

scheme

sicp