Oz中的尾递归优化

Question

在《Oz教程中关于函数的章节》中，它提到：

类似于惰性函数式语言，Oz允许某些形式的尾递归优化，这在某些严格的函数式语言（包括Standard ML、Scheme和并发函数式语言Erlang）中是找不到的。然而，在Oz中，标准函数定义并不是惰性的。

接下来，它展示了以下在Oz中是尾递归的函数。

fun {Map Xs F}
   case Xs
   of nil then nil
   [] X|Xr then {F X}|{Map Xr F}
   end 
end 

这个函数的作用是将空列表映射到空列表，将非空列表映射到将函数 F 应用于其头部并将结果前置到对尾部调用 Map 的结果。在其他语言中，这不是尾递归，因为最后的操作是前置而不是对 Map 的递归调用。

所以我的问题是：如果“Oz 中的标准函数定义不是惰性的”，那么 Oz 在这个函数上做了什么，使得像 Scheme 或 Erlang 这样的语言无法（或不会）执行尾递归优化？在 Oz 中，一个函数何时是尾递归的？

- sepp2k

---

更多信息请访问https://stackoverflow.com/tags/tailrecursion-modulo-cons/info。 - Will Ness

更多信息请参见https://stackoverflow.com/tags/tailrecursion-modulo-cons/info。 - undefined

Answer 1

这被称为尾递归模数Cons。基本上，在递归调用之后直接将元素添加到列表的开头，与在递归调用之前直接将元素添加到列表的末尾（因此通过纯函数“循环”的“副作用”构建列表）是相同的。这是尾递归的一般化，不仅适用于cons列表，还适用于具有常量操作的任何数据构造器。

它最初被描述为LISP编译技术，由Daniel P. Friedman和David S. Wise在1974年的技术报告TR19：将结构递归展开为迭代中，但没有命名。它在1980年由David H. D. Warren正式命名并引入，用于编写第一个Prolog编译器。

关于 Oz 的有趣之处在于 TRMC 既不是一种语言特性，也不是显式的编译器优化，而是语言执行语义的副作用。具体来说，Oz 是一种声明式并发约束语言，这意味着每个变量都是数据流变量（或“一切都是承诺”，包括每个存储位置）。由于一切都是承诺，我们可以将从函数返回建模为首先设置返回值为承诺，然后稍后履行它。

Peter van Roy 是《计算机编程的概念、技术和模型》一书的合著者之一，也是 Oz 的设计者和实现者之一，在 Lambda the Ultimate 的评论线程中解释了 TRMC 的工作原理。

The above example of bad Scheme code turns into good tail-recursive Oz code when translated directly into Oz syntax. This gives:

fun {Map F Xs}
   if Xs==nil then nil
   else {F Xs.1}|{Map F Xs.2} end
end

This is because Oz has single-assignment variables. To understand the execution, we translate this example into the Oz kernel language (I give just a partial translation for clarity):

proc {Map F Xs Ys}
   if Xs==nil then Ys=nil
   else local Y Yr in
      Ys=Y|Yr
      {F Xs.1 Y}
      {Map F Xs.2 Yr}
   end end
end

That is, Map is tail-recursive because Yr is initially unbound. This is not just a clever trick; it is profound because it allows declarative concurrency and declarative multi-agent systems.

- Jörg W Mittag

---

由于一切都是承诺，我们可以将函数返回建模为首先将返回值设置为承诺，然后在稍后履行它。这样做会使其完全惰性，不是吗？相反，引用的 Oz 代码似乎显示（符合我在基于 Prolog 的经验中所预期的）返回值的_结构_立即被完全设置，并填充有尚未设置的变量（类似于 Prolog 的未实例化逻辑变量）。如果我理解正确，在 Oz 中任何尝试从尚未设置的变量读取的操作都会阻塞 1/ - Will Ness

2/ 直到其他线程设置了该变量的值；我猜这就是使这些变量成为“数据流变量”的原因。所以，Ys=Y|Yr使用两个空洞设置了“cons”结构；{F Xs.1 Y}过程调用设置了Y的值，然后进行了{Map F Xs.2 Yr}过程调用（显然，在尾部位置），并且不需要阻塞/恢复操作，因为同一线程继续进行尾调用并设置所有结果列表的单元格。所以，这种魔法似乎存在于这些Oz“过程”中，类似于Prolog谓词（再次猜测）。 /2 - Will Ness

Answer 2

我对惰性函数式语言不是很熟悉，但如果您考虑到您问题中的Map函数，那么将其转换为尾递归实现就很容易，只要暂时允许堆中的不完整值（一次调用一个更完整的值）。

我必须假设他们在Oz中谈论这种转换。Lispers曾经手动执行此优化-所有值都是可变的，在这种情况下，将使用一个名为setcdr的函数-但您必须知道自己在做什么。计算机并非总是拥有千兆字节的内存。当时手动执行此操作是有道理的，但现在可能不再合适。

回到您的问题，其他现代语言可能不会自动执行此操作，原因可能是在构建过程中可能观察到不完整的值，而这可能就是Oz找到解决方案的原因。与其他语言相比，Oz还有哪些不同之处可以解释这一点呢？

- Pascal Cuoq

---

我其实对Oz并不是很了解。据我所知，它与Lisp并没有太大的区别。最近几天我只是随便玩了一下，意外地发现它能优化递归，这让我感到有些惊讶。 - sepp2k

我只从读Peter Van Roy的《计算机程序设计的概念、技术和模型》中了解Oz，但事实上它确实具有不完整的值——在并发编程中广泛使用，因为读取不完整的值会导致当前线程阻塞。所以Pascal猜测它的工作原理可能是这样的。 - Nathan Shively-Sanders

由于Oz也是一种逻辑语言，因此它可能有逻辑变量的概念，在这种情况下，它将与其他逻辑语言（如Prolog）一样进行尾递归。 - rvirding

请点击此处查看其具体工作原理：http://lambda-the-ultimate.org/node/2273#comment-40235 - wmeyer