Oz中的尾递归优化

在关于Oz教程中的函数的章节中，它说：类似于懒惰的函数式语言 Oz允许某些形式的尾递归优化没有发现某些严格的功能语言包括标准ML，方案，并发功能语言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中函数尾递归？

已邀请:

2 个回复

棠媳鳖

这称为Tail RecursionModuloCons。基本上，在递归调用之后直接在列表前面添加与在递归调用之前直接附加到列表相同（并因此将列表构建为纯功能“循环”的“副作用”）。这是尾递归的推广，它不仅适用于cons列表，而且适用于具有常量运算的任何数据构造函数。它首先被描述（但没有命名）作为LISP编译技术于1974年由Daniel P. Friedman和David S. Wise在技术报告TR19中展开：将结构化递归展开到迭代中它由David HD Warren在1980年正式命名和介绍。编写有史以来第一个Prolog编译器的环境。然而，关于Oz的有趣之处在于，TRMC既不是语言特性也不是显式编译器优化，它只是语言执行语义的副作用。具体来说，Oz是一种声明式并发约束语言，这意味着每个变量都是一个数据流变量（或“一切都是一个承诺”，包括每个存储位置）。由于一切都是一个承诺，我们可以模拟从函数返回，首先将返回值设置为promise，然后再实现它。 Peter van Roy是Peter Van Roy和Seif Haridi所着的计算机编程概念，技术和模型的合着者，他也是Oz的设计者之一，也是其实现者之一，他解释了TRMC在评论主题中是如何工作的在Lambda上终极：尾递归映射和声明代理：上面的错误Scheme代码示例在直接转换为Oz语法时变成了良好的尾递归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最初是未绑定的。这不仅仅是一个聪明的伎俩;它是深刻的，因为它允许声明性并发和声明性多代理系统。

车料

我对懒惰的函数式语言并不太熟悉，但如果你在你的问题中考虑函数Map，如果允许在堆中暂时不完整的值，则很容易转换为尾递归实现（在一次调用时将其静音为更完整的值）在一个时间）。我不得不假设他们正在谈论奥兹的这种转变。 Lispers曾经手工完成这项优化 - 所有值都是可变的，在这种情况下会使用一个名为setcdr的函数 - 但你必须知道你在做什么。计算机并不总是有几千兆字节的内存。手工做到这一点是合理的，可以说不再是这样。回到你的问题，其他现代语言不会自动执行，可能是因为在构建时可以观察到不完整的值，这必须是Oz找到解决方案的原因。与其他解释它的语言相比，Oz还有哪些其他差异？

要回复问题请先登录或注册

Oz中的尾递归优化

2 个回复

发起人

oz

问题状态

Oz中的尾递归优化

与内容相关的链接

2 个回复

发起人

oz

问题状态