作者godfat (godfat 真常)
看板Ruby
标题Re: [Ruby] recursive lambda
时间Tue Apr 24 21:13:28 2007
edited: rambda 少讲一个缺点
ok, 就 Ruby 实作 recursive lambda 大概有以下结论…
1. 原文提到的 call stack this 实作
优点：
1. 可以把 "this" pass around, 这正是初衷之一
缺点：
1. 因为是额外去模拟出 call stack, 所以 func call 有额外 cost
2. 针对使用 yield 的 func 无法使用！（昨天才发现的）
因为 yield 似乎不会产生 func call, 所以无法从 call stack
找出正确的 func :(
如：(0...10).map(&lambda{|n| n<=1 ? 1 : this[n-2]+this[n-1]}))
由於 map 的实作是用 yield, 所以这边的 this 会呼叫到错误的对象
切记切记… :(
2. Y/Z combinator, 基本上我觉得意思差不多
优点：
1. 行为绝对正确…
缺点：
1. 由於多了许多间接呼叫，使得递回本身出现许多额外 cost
2. client 的 func 必须改写成：lambda{|this|lambda{...}} 的形式
3. rambda... 这昨天才测试完毕的
名字当然是随便取的，没有特别意义（就 LR 互换而已）
做法其实很单纯，就是把原本 lambda{} 的 func cache 起来，
回传一个特制的 lambda, 有记住 this 是什麽的版本 :o
rambda{|n| n==1 ? 1 : n*this[n-1]}
程式码：
class Rambda
def initialize &block
@this = eval block.to_ruby
define_instance_method :call, &@this
alias_instance_method :[], :call
end
attr_reader :this
alias_method :to_proc, :this
end
def rambda &block
Rambda.new &block
end
优点：
1. 用起比 fixed point combinator 方便，也没 call stack 危险
缺点：
1. 这东西用到了 Ruby2Ruby, 跑起来一定很慢…很蠢…
2. 慢就算了，要用 Ruby2Ruby 还得灌一堆其他的
3. 由於重新 eval 过，所以 scope 改变，不能 refer local variable...
v = "can't refer this"
rambda{v}.call # raise NameError...
大概就是这样了 :)
--
In Lisp, you don't just write your program down toward the language,
you also build the language up toward your program.
《Programming Bottom-Up》－ Paul Graham 1993
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.134.30.220
※ 编辑: godfat 来自: 220.134.30.220 (04/24 21:16)