Lisp 中`do` 和`do*` 的区别？

Question

我正在研究这两个函数，它们的区别仅在于循环运行时 ret 和 curr 的赋值方式。在第一个函数中，ret 和 curr 是并行的 bound；在第二个函数中，它们按顺序绑定。

并行绑定

(defun maxpower (base maximum)
    "returns base ^ k such that it is <= maximum"
    (do ((ret 1 curr)               ; parallel
         (curr base (* base curr))) ; binding
        ((> curr maximum) ret)))

顺序绑定

(defun maxpower* (base maximum)
    "returns base ^ k such that it is <= maximum"
    (do* ((ret 1 curr)                ; sequential
          (curr base (* base curr)))  ; binding
         ((> curr maximum) ret)))

问题：第一个函数是否以某种方式错误 ^(*) 因为 curr 在同时（并行）？

IOW：如果我更改绑定的顺序，并行版本应该没有区别吗？
Lisp 如何决定 bindings 的并行化？

在我的测试中，两个函数 return 具有相同的值。

^{(*)：我是C出身；我会说第一个函数调用未定义的行为。}

Answer 1

在 maxpower 的情况下，“curr 同时更新和求值 ” 是不正确的。 do 中的步骤形式都在任何分配发生之前进行评估。对于 do，Hyperspec 表示“the assignment of values to vars is done in parallel, as if by psetq," and for psetq it says that "first all of the forms are evaluated, and only then are the variables set to the resulting values."

在发布的代码中，两个定义应该产生相同的结果，因为在完成任何分配之前评估步骤形式。但是，如果绑定的顺序颠倒，事情就会不同：

(defun maxpower (base maximum)
  (do ((curr base (* base curr))
       (ret 1 curr))
      ((> curr maximum) ret)))

(defun maxpower* (base maximum)
  (do* ((curr base (* base curr))
        (ret 1 curr))
       ((> curr maximum) ret)))

现在对于第一个函数，(* base curr) 和 curr 同时求值，curr 和 ret 的值并行更新。但是，对于第二个函数，计算 (* base curr) 并将结果分配给 curr，然后计算 then curr 并将其分配给 [=21] =].

对于这些新定义，您可以看到结果不同，在原始定义中，两个函数对于 (maxpower 2 5) 和 (maxpower* 2 5) 都会返回 4:

CL-USER> (maxpower 2 5)
4
CL-USER> (maxpower* 2 5)
8

Answer 2

最好先看看 let 和 let*。如果您理解这一点，那么 do 与 do* 的区别就在于此，除了对步骤形式的额外考虑。

Common Lisp 是一种经过严格评估的语言。在 let 和 let* 中，变量 init-forms 都是从左到右求值的。区别在于范围和绑定。在 let 下，所有 init 形式都在 none 变量可见的范围内求值，而在 let* 下，形式在所有先前变量都可见的环境中进行评估。其次，由于在let*下，前面的变量是可见的，所以它们的值也是成立的。

使用 let 我们可以创建一个范围，其中两个变量的值出现交换：

(let ((x y)
      (y x))
   ...)

初始化表达式 y 和 x 首先按顺序计算，然后新值 x 和 y 绑定到结果值，这使这成为可能。

另一方面：

(let* ((a 1)
       (b (+ a 2)))

这里，1被求值，a被绑定。然后，此 a 对计算其值的 (+ a 2) 表达式可见，并绑定到 b.

现在，进入 do/do*。这些宏在第一次迭代之前执行与 let/let* 完全相同的变量绑定。在绑定变量时，do 和 do* 之间的区别与 let 和 let* 之间的区别完全相同。

do/do* 宏也有阶梯形式，它们将下一个值赋给相应的迭代变量。这些步骤形式都在所有变量的范围内，不管宏运算符是do还是do*。无论您使用 do 还是 do*，您都可以在任何步骤形式中引用任何变量。不同之处在于分配发生的时间。在do下，所有的step形式从上到下依次求值，然后为它们对应的变量赋新值，用于下一次迭代。在 do* 下，行为是“assign as you go”。在评估每个步骤形式时，会分配相应的变量。因此，在 do 下，当步进形式引用任何变量时，它引用的是先前迭代中的值。在 do* 下，如果 step-form 引用词法上较早的变量，它会获取新值。如果它指的是一个词法后面的变量，它仍然看到先前迭代的旧值。

我们要强调的是，let和do虽然有一些“平行”的行为，但从某种意义上说，并没有平行评价。所有可见效果都是从左到右执行的。似乎并行发生的是变量开始存在，或者在新的迭代中被赋予新的值。但这只是在程序无法观察中间进度的意义上是并行的。例如，将函数参数传递给函数同样是“并行的”；程序未观察到函数调用部分正在进行且仅传递了一半参数的状态。

Lisp 中`do` 和`do*` 的区别？

Difference between `do` and `do*` in Lisp?

lisp

common-lisp

undefined-behavior