トップ «前の日記(2003-05-01) 最新 次の日記(2003-05-07)» 月表示 編集

日々の流転


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に続く。

本日のツッコミ(全6件) [ツッコミを入れる]
ψ はら (2003-05-07 12:13)

難しい。catch-throwでは書けないのですよね、、、それより何これ?(^^;

ψ さかい (2003-05-07 22:25)

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,

ψ はら (2003-05-08 22:18)

なるほど!面白いですね。<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

ψ さかい (2003-05-10 00:50)

そうです。<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でも使えないかなぁ……

ψ はら (2003-05-10 01:53)

この実装は等価でしょうか:<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

ψ さかい (2003-05-10 23:06)

だと思います。<br><br>最初の実装から、<br>(1) meta continuation の保存と復元にスタック(Array)を使う<br>(2) _abortと、shift内のresetをインライン展開<br>(3) スタックに積むのを、「popしてから継続を呼び出す」Procから、継続そのものに置き換えて、呼び出す側であらかじめpopするようにする<br>という変換をすると、この実装(とほぼ同じもの)が得られます。