functional-programming - Oz 中的尾递归优化

Question

在 chapter about function in the Oz tutorial ，它说:

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.

然后继续显示以下函数，它是 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 中的标准函数定义不是懒惰的”，那么像 Scheme 或 Erlang 这样的语言不能(或不会？)为这个函数执行尾递归优化，Oz 做了什么？确切地说，Oz 中的函数何时是尾递归的？

Answer 1

这叫做Tail Recursion Modulo Cons .基本上，在递归调用之后直接添加到列表与在递归调用之前直接添加到列表相同(因此将列表构建为纯函数“循环”的“副作用”)。这是尾递归的推广，不仅适用于 cons列出但任何具有常量操作的数据构造函数。
1974 年，Daniel P. Friedman 和 David S. Wise 在 Technical Report TR19: Unwinding Structured Recursions into Iterations 中首次将其描述为(但未命名)为 LISP 编译技术。它由 David H. D. Warren 在 1980 年在编写有史以来第一个 Prolog 编译器的背景下正式命名和引入。
然而，关于 Oz 的有趣之处在于，TRMC 既不是语言功能也不是显式编译器优化，它只是语言执行语义的副作用。具体来说，Oz 是一种声明性并发约束语言，这意味着每个变量都是数据流变量(或“一切都是 promise ”，包括每个存储位置)。由于一切都是 promise ，我们可以将函数的返回建模为首先将返回值设置为 promise ，然后再实现它。
Peter van Roy，该书的合著者 Concepts, Techniques, and Models of Computer Programming by Peter Van Roy and Seif Haridi ，也是 Oz 的设计者之一及其实现者之一，在 Lambda the Ultimate 的评论线程中解释了 TRMC 的工作原理: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.