Oz 中的尾递归优化

发布于 2024-08-06 02:20:13 字数 790 浏览 9 评论 0原文

类似于惰性函数式语言奥兹国允许某些形式的尾递归优化是在某些严格的功能中没有发现语言包括标准机器学习，方案和并发函数语言 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 的递归调用。

所以我的问题是：如果“Oz 中的标准函数定义不是懒惰的”，那么 Oz 会做什么，而像 Scheme 或 Erlang 这样的语言不能（或不会？）能够为此函数执行尾递归优化？在 Oz 中，函数到底什么时候是尾递归的？

原文

In the chapter about function in the Oz tutorial, it says that:

similar to lazy functional languages
Oz allows certain forms of
tail-recursion optimizations that are
not found in certain strict functional
languages including Standard ML,
Scheme, and the concurrent functional
language Erlang. However, standard
function definitions in Oz are not
lazy.

It then goes on to show the following function which is tail-recursive in Oz:

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

What this does is, it maps the empty list to the empty list and non-empty list, to the result of applying the function F to its head and then prepending that to the result of calling Map on the tail. In other languages this would not be tail recursive, because the last operation is the prepend, not the recursive call to Map.

So my question is: If "standard function definitions in Oz are not lazy", what does Oz do that languages like Scheme or Erlang can't (or won't?) to be able to perform tail-recursion optimization for this function? And exactly when is a function tail-recursive in Oz?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

罗罗贝儿 2024-08-13 02:20:13

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

1974 年，Daniel P. Friedman 和 David S. Wise 在 技术报告 TR19：将结构化递归展开为迭代，由 David HD Warren 于 1980 年在该上下文中正式命名和引入编写第一个 Prolog 编译器。

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

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

当直接翻译成 Oz 语法时，上面的坏方案代码示例会变成好的尾递归 Oz 代码。这给出：
有趣的{Map F Xs}
   如果 Xs==nil 则 nil
   else {F Xs.1}|{映射 F Xs.2} end
结尾
这是因为 Oz 有单赋值变量。为了理解执行过程，我们将这个示例翻译成 Oz 内核语言（为了清楚起见，我只给出了部分翻译）：
proc {Map F Xs Ys}
   如果 Xs==nil 则 Ys=nil
   其他地方 Y 年 在
      Ys=Y|Yr
      {F Xs.1 Y}
      {地图 F Xs.2 年}
   结束结束
结尾
也就是说，Map 是尾递归的，因为 Yr 最初是未绑定的。这不仅仅是一个聪明的把戏；它意义深远，因为它允许声明式并发和声明式多代理系统。

This is called Tail Recursion Modulo Cons. Basically, prepending to the list directly after the recursive call is the same as appending to the list directly before the recursive call (and thus building the list as a "side-effect" of the purely functional "loop"). This is a generalization of tail recursion that works not just with cons lists but any data constructor with constant operations.

It was first described (but not named) as a LISP compilation technique in 1974 by Daniel P. Friedman and David S. Wise in Technical Report TR19: Unwinding Structured Recursions into Iterations and it was formally named and introduced by David H. D. Warren in 1980 in the context of writing the first-ever Prolog compiler.

The interesting thing about Oz, though, is that TRMC is neither a language feature nor an explicit compiler optimization, it's just a side-effect of the language's execution semantics. Specifically, the fact that Oz is a declarative concurrent constraint language, which means that every variable is a dataflow variable (or "everything is a promise", including every storage location). Since everything is a promise, we can model returning from a function as first setting up the return value as a promise, and then later on fulfilling it.

Peter van Roy, co-author of the book Concepts, Techniques, and Models of Computer Programming by Peter Van Roy and Seif Haridi, also one of the designers of Oz, and one of its implementators, explains how exactly TRMC works in a comment thread on Lambda the Ultimate: Tail-recursive map and declarative agents:

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.

回复收藏 0 原文