7

在Oz 教程中关于函数的章节中，它说：

类似于惰性函数式语言 Oz 允许某些形式的尾递归优化，这些优化在某些严格的函数式语言中找不到，包括标准 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 中的尾递归函数究竟是什么时候？

4

2 回答 2

5

这称为尾递归模Cons。基本上，在递归调用之后直接添加到列表与在递归调用之前直接添加到列表相同（因此将列表构建为纯功能“循环”的“副作用”）。这是尾递归的概括，它不仅适用于列表，还适用于任何具有常量操作的数据构造函数。cons

1974 年，Daniel P. Friedman 和 David S. Wise 在Technical Report TR19: Unwinding Structured Recursions into Iterations中首次将其描述（但未命名）为 LISP 编译技术，并于 1980 年由 David HD Warren 正式命名并引入编写第一个 Prolog 编译器的上下文。

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

Peter van Roy 是由 Peter Van Roy 和 Seif Haridi合着的《计算机编程的概念、技术和模型》一书的合著者，他也是 Oz 的设计者之一，也是它的实现者之一，他在评论线程中解释了 TRMC 的工作原理关于 Lambda the Ultimate：尾递归映射和声明性代理：

当直接翻译成 Oz 语法时，上面的不良 Scheme 代码示例会变成良好的尾递归 Oz 代码。这给出了：

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

这是因为 Oz 具有单赋值变量。为了理解执行，我们将这个例子翻译成 Oz 内核语言（为了清楚起见，我只给出了部分翻译）：

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

也就是说，Map是尾递归的，因为Yr最初是未绑定的。这不仅仅是一个聪明的把戏；它是深刻的，因为它允许声明式并发和声明式多代理系统。

于 2014-08-05T11:34:53.273 回答
3

我对惰性函数语言不太熟悉，但是如果您考虑问题中的函数 Map ，如果允许堆中暂时不完整的值（一次调用静音为更完整的值），则很容易转换为尾递归实现一次）。

我不得不假设他们正在谈论 Oz 中的这种转变。Lispers 过去常常手动进行这种优化——所有值都是可变的，在这种情况下，setcdr将使用一个名为的函数——但你必须知道你在做什么。计算机并不总是有千兆字节的内存。手动执行此操作是合理的，可以说不再是。

回到您的问题，其他现代语言可能不会自动执行此操作，可能是因为在构建时可以观察到不完整的值，而这一定是 Oz 找到的解决方案。与其他可以解释它的语言相比，Oz 中还有哪些其他差异？

于 2009-10-03T11:46:41.477 回答