Oz中的尾递归优化

Question

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

类似于懒惰的函数语言，Oz允许某些形式的尾递归优化，这些优化在某些严格的函数语言中是找不到的，包括标准ML、Scheme和并发函数语言Erlang。但是，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中函数尾递归到底是什么时候？

Answer 1

这叫做。基本上，在递归调用之后直接对列表进行前缀与直接在递归调用之前附加到列表(从而将列表构建为纯函数“循环”的“副作用”)是一样的。这是尾递归的推广，它不仅适用于cons列表，而且适用于任何具有常量操作的数据构造函数。

1974年，丹尼尔·P·弗里德曼(DanielP.Friedman)和戴维·S·怀斯(DavidS.Wise)在http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR19中首次将它描述为一种LISP编译技术，1980年大卫·H·D·沃伦(DavidH.D.Warren)在编写第一个Prolog编译器时正式命名并引入了LISP编译技术。

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

Peter van Roy，这本书的合著者，同时也是Oz的设计者之一，同时也是它的实现者之一，他解释了TRMC到底是如何在Lambda的评论线程中工作的：http://lambda-the-ultimate.org/node/2273#comment-40235。

当直接转换为Oz语法时，上述糟糕的Scheme代码示例将转化为好的尾递归Oz代码。这意味着： fun {映射F}如果Xs==nil那么没有其他的{FXs.1}{映射FXs.2}结束结束 这是因为Oz有单赋值变量。为了理解执行过程，我们将这个示例翻译成Oz内核语言(为了清晰起见，我只提供了部分翻译)： proc {映射F Xs Ys}如果Xs==nil，则在Ys=Y|Yr {FXs.1}{映射F Xs.2 Yr}结束端Ys=nil局部Yr 也就是说，Map是尾递归的，因为Yr最初是未绑定的.这不仅仅是一个聪明的诡计；它是深刻的，因为它允许声明性并发和声明性多代理系统。

Answer 2

我不太熟悉懒惰的函数语言，但是如果您在问题中考虑函数映射，如果允许堆中暂时不完整的值(每次调用一个更完整的值)，就很容易转换为尾递归实现。

我不得不假设他们在谈论奥兹的这种转变。Lispers过去通过手工进行这种优化--所有的值都是可变的，在这种情况下，将使用一个名为setcdr的函数--但是您必须知道您在做什么。计算机并不总是有千兆字节的内存。用手做这件事是有道理的，但现在可以说不再是这样了。

回到您的问题，其他现代语言可能不会自动完成，可能是因为在构建不完整值时可以观察到它，这一定是Oz找到了解决方案。与解释它的其他语言相比，奥兹语还有哪些不同之处？