[心得] Generator 與 Continuation

看板Ruby作者godfat (godfat 真常)時間18年前 (2007/02/27 00:59)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串1/2 (看更多)

Ruby standard library 裡有個 Generator, 放在 generator.rb 裡。大抵上是拿來把 internal iterator 轉換成 external iterator 用的。兩種 iterator 有什麼差別？如果你熟悉 C++ 或 Java 的話，他們所使用的就是 external iterator. 顧名思義，這是一種外部的 iterator, 即 iterator 本身跟 container/collection 是分開的。 C++: typedef std::vector<int> vint; vint v; for(vint::iterator i=v.begin(), iend=v.end(); i!=iend; ++i) std::cout << *i << "\n"; Java: Vector<Integer> v = new Vector<Integer>(); for(Iterator i=v.iterator(); i.hasNext();) out.println(i.next()); 如果是 internal iterator 的話，就像是 foreach/for in 那樣 C++: BOOST_FOREACH(int i, v){ // 由於這是 macro 做的，不確定能不能省略 std::cout << i << "\n"; } Java: for(int i: v) out.println(i); 也就是說，你只能依序得到元素，但你不能操控會給你的元素是什麼。 external iterator 有比較強大的彈性，internal iterator 使用起來方便。 Ruby 的 each 很明顯是 internal iterator, 你把要施行的動作傳給 container/collection, 然後由他來替你施行動作。可以看成是這樣： def each func = nil, &block # 以下決定使用 block 或傳入的 Proc like 物件，寫入 func 中 if block_given? func = block else raise TypeError, "#{func} don't respond to :call" unless func.respond_to? :call func = func end # 以下依次呼叫外部 Proc like 物件，傳入被 travel 者 0...self.size.times{|i| func.call self[i] } end 由於 travel 的動作被隱藏起來了，所以使用時方便，不用再去說明 travel 法。缺點也正是因為 travel 被隱藏起來了，所以如果不是要用預設的 travel 法，則動他不得。要用非預設的方式，只能使用 external iterator. Ruby 目前沒什麼好的 external iterator, 所以只好使用 Generator 去模擬。（當然，Array 很好做 external iterator, 但其他的就比較困難。）用法大概是像這樣： v = [0, 1, 2, 3, 4] g = Generator.new v while g.next? puts g.next end Generator 的做法很單純，他還是使用 each 去呼叫，不過卻去「卡住」 travel 的過程。這就是靠 Continuation 去做了。關於 Continuation, 本板前面有其相關心得，不多重複了。寫成概念有點像這樣： def next @target.each{|i| 卡住 return i } end 每次呼叫 Generator 的 next 時，就放掉「卡住」，於是傳回當時的 i, 然後在傳回下一個 i 之前，再卡住執行流程。next 可以用這種概念實作出來。不過 prev 就沒辦法了。Generator 有提供 rewind, 使 travel 整個重來，但是沒有 prev 這種能夠往前走一格的方式…。要有的話，勢必不能使用 each. 幸運的是……由於 standard library 的 generator.rb 我看不懂，看了好一陣子，只得到了點概念，但還是搞不懂他為什麼要把實作變得這麼複雜 :( 沒記錯的話，總共有三個 Continuation 物件，又有一個額外的 queue array... 我完全搞不懂他這個 queue 存在的意義。所以我自己嘗試寫了一下，以確保我沒有誤解什麼東西。我只用了兩個 Continuation, 沒有 queue. 當然，整個概念還是從他的程式碼來的，我只是把我看不懂的部份拿掉，然後用自己的意思解讀一次。用該檔案裡面的 unit test 測試了一下，每一個測試都通過了，很搞不懂原本的實作為什麼要弄得這麼複雜…。更何況由於我撰寫的裡面少了一個 Continuation 和一個 array, 執行效率應該還比較高。不知道是不是我疏忽了什麼，不然這樣的狀況似乎有點詭異。 * 原本我是想詳細解說我的實作的，不過 Continuation 我覺得有點複雜，從寫完到現在也經過一段時間了，詳細的做法我已經不記得了…。 Orz 更何況此篇已經有點太長了，也差不多是「欲知詳情，請待下回分曉」的時候 XD 所以以下就僅附上程式碼，以 Ruby license 釋出。 p.s. 我覺得 Continuation 太過於複雜（另類 goto），似乎應該少用為妙 class Generator include Enumerable def initialize enum = nil, &block if enum @block = lambda{|g| enum.each{|i| g.yield i}} else @block = block end @index = 0 @value = nil if @con_next = callcc{|c|c} @block.call self @con_next.call end end def next raise EOFError, "no more elements available" if end? @index += 1 result = @value @con_yield.call if @con_next = callcc{|c|c} result end def yield value @value = value @con_next.call if @con_yield = callcc{|c|c} end def next? return true if @con_yield return false end def end? !next? end def index @index end alias_method :pos, :index def current raise EOFError, "no more elements available" unless @value @value end def rewind initialize &@block self end def each rewind yield(self.next) while self.next? self end end -- 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.135.28.18