作者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)