Oz中的尾递归优化

Question

在关于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尾部的结果.在其他语言中,这不是尾递归,因为最后一个操作是prepend,而不是递归调用Map.

所以我的问题是:如果"Oz中的标准函数定义不是懒惰的",那么Oz做什么,像Scheme或Erlang这样的语言不能(或不会？)能够对此函数执行尾递归优化？究竟什么时候函数尾部递归在Oz？

Answer 1

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

1974年，Daniel P. Friedman和David S. Wise在《技术报告TR19：将结构化递归展开为迭代》中首次描述（但未命名）为LISP编译技术，并由David HD Warren在1980年正式命名和引入。编写第一个Prolog编译器的上下文。

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

彼得·范·罗伊（Peter van Roy）和彼得·范·罗伊（Peter Van Roy）和塞夫·哈迪（Seif Haridi）共同撰写了《计算机编程的概念，技术和模型》一书。在Lambda 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最初未绑定，所以是尾递归的。这不仅是一个聪明的把戏。它之所以具有深远意义，是因为它允许声明式并发和声明式多主体系统。