代码之家 › 专栏 › 技术社区 › sepp2k

Oz中的尾部递归优化

oz recursion functional-programming

7

sepp2k · 技术社区 · 16 年前

chapter about function in the Oz tutorial ,它说:

类似于惰性函数语言尾部递归优化在某些严格函数中未找到语言,包括标准ML, 方案,以及并发函数 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中何时是递归的呢?

2 回复 | 直到 11 年前

1

5

Community Mohan Dere 6 年前

这叫做 Tail Recursion Modulo Cons . 基本上, 预编直接进入名单之后递归调用与附加直接进入名单递归调用(从而将列表构建为纯函数“循环”的“副作用”)。这是尾部递归的一个推广,它不仅适用于 cons 只列出具有常量操作的任何数据构造函数。

Technical Report TR19: Unwinding Structured Recursions into Iterations 它的正式名称是David H。D沃伦于1980年在编写第一个Prolog编译器的背景下。

第一将返回值设置为承诺,然后实现它。

彼得·范·罗伊,这本书的合著者 Concepts, Techniques, and Models of Computer Programming by Peter Van Roy and Seif Haridi Tail-recursive map and declarative agents :

fun {Map F Xs}
   if Xs==nil then nil
   else {F Xs.1}|{Map F Xs.2} end
end
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 最初是未绑定的。这不仅仅是一个聪明的把戏;它之所以意义深远,是因为它允许声明式并发和声明式多代理系统。

2

3

Pascal Cuoq 16 年前

我必须假设他们在Oz中讨论这个转换。Lispers过去用手进行优化——所有的值都是可变的,在这种情况下,函数名为 setcdr

回到你的问题上来,其他现代语言不会自动这样做,可能是因为在构建过程中可以观察到不完整的值,而这一定是Oz找到的解决方案。与其他语言相比,《绿野仙踪》还有哪些不同之处可以解释它?