2003-05-03 [長年日記]
λ. 色々せっぱ詰まってたり。ゴールデンウィークなのに……
λ. 床屋
へ行く。
λ. いろいろ
プリンセスチュチュ見忘れた。魔探偵ロキは見たのですが。
λ. call/ccによるshift/resetの表現
メモ。ぐるぐる。
def _abort(&thunk)
v = thunk.call
Thread.current[:__meta_continuation__].call(v)
end
def reset(&thunk)
th = Thread.current
mc = th[:__meta_continuation__]
callcc{|k|
th[:__meta_continuation__] = lambda{|v|
th[:__meta_continuation__] = mc
k.call(v)
}
_abort(&thunk)
}
end
def shift(&f)
callcc{|k|
_abort{
f.call(lambda{|v| reset{ k.call(v) } })
}
}
end
p 1 + reset{ 3 } #=> 4
p 1 + reset{ 2 * shift{|k| 4 } } #=> 5
p 1 + reset{ 2 * shift{|k| k[4] } } #=> 9
p 1 + reset{ 2 * shift{|k| k[k[4]] } } #=> 17
shift/reset その2に続く。
難しい。catch-throwでは書けないのですよね、、、それより何これ？(^^;
shift/resetは「部分継続」を扱うオペレータです。callccが「リターンした後の計算全体」をブロック引数に束縛するのに対して、shiftは「最近のresetに戻るまでの計算」をブロック引数に束縛します(で、shiftのブロックからリターンしたらresetまでジャンプしてリターンする)。ポイントは、通常の継続とは違って部分的な計算を表しているので、関数的に使えるところ。<br><br># 実装はまだ他人に説明できるほど理解できてなかったり……(^^;;<br><br>ついでにJARHを作ってみる。<br>reset{ print shift{|k| k.call("Just another "); k } }.call("Ruby hacker,")<br>#=> Just another Ruby hacker,
なるほど！面白いですね。<br>例が難しい、、、こういうことですよね。<br><br>k = nil<br>p reset{ 2 * shift{|k| 3}} #=> 3<br>p k[1] #=> 2<br>p k[2] #=> 4<br>p k[3] #=> 6
そうです。<br><br>ちなみに、call/ccがスタックの全体をコピーする必要があったのに対して、shift/resetではスタックの上部だけコピーすれば十分なので、call/ccよりも効率的な実装が可能なようです。<br>Final Shift for Call/cc: Direct Implementation of Shift and Reset<br>http://citeseer.ist.psu.edu/gasbichler02final.html<br><br>あと、『Java と相互呼び出し可能なScheme 処理系「ぶぶ」における継続機能と例外処理機能の実装』<br>http://www.ipsj.or.jp/members/Trans/Jpn/03/2001/4211/article004.html<br>のテクニックってJRubyでも使えないかなぁ……
この実装は等価でしょうか：<br><br>def reset<br> callcc{|k|<br> (Thread.current[:stack] ||= []).push k<br> v = yield<br> Thread.current[:stack].pop.call v<br> }<br>end<br> <br>def shift<br> callcc{|k|<br> v = yield lambda{|u|<br> callcc{|c|<br> Thread.current[:stack].push c<br> k.call u<br> }<br> }<br> Thread.current[:stack].pop.call v<br> }<br>end
だと思います。<br><br>最初の実装から、<br>(1) meta continuation の保存と復元にスタック(Array)を使う<br>(2) _abortと、shift内のresetをインライン展開<br>(3) スタックに積むのを、「popしてから継続を呼び出す」Procから、継続そのものに置き換えて、呼び出す側であらかじめpopするようにする<br>という変換をすると、この実装(とほぼ同じもの)が得られます。