[CPS変換]継続ってパイプライン的な何かだなと思ったらなんかわかってきた4

まとめ： callCCも、もっと簡単に書ける! うれしい!...けど?

前の記事で、もっと簡単にパイプラインの中で分岐できるってのが分かったんだけど、振り返ってみたら、これってcallCCももっと簡単にできるってことだよなあ、って気付いたんでやってみます。
前の前の記事の焼き直しです。

const ret = x =>
  k => k(x)

const evalCont = x => x

const callCC = f =>
  m => f( jumpTo(m) )( m )

const jumpTo = m =>
  x => k => k !== m ? jumpTo(m)(x) : m(x) 

独自の pipe 関数も、 bind も定義しません。 よく考えてみれば、そもそも 継続自体がパイプラインであり、bind なんじゃないの?って気づいちゃったんで。

jumpTo のところが変っています。これで callCCの中では kを無視して、外に出たら普通に戻るようになります。

どうなるか使ってみます。

const g = x =>
  callCC(exit => (x === 0 ? exit(x): ret(x))
         (x => ret(x + 1))
         (x => ret(x + 1))
        )
  (x => ret(x + 1))
  (evalCont)

g(0)  // 1
g(1)  // 4

ちゃんと動いた!

フィボナッチ数列もやってみます。

const fibCPS = n =>
  callCC(exit => (n < 2 ? exit(1) : fibCPS(n - 2))
                  (a => fibCPS(n - 1)
                        (b => ret(a + b))
                  )
        )

fibCPS(5)(evalCont) // 8

ちゃんと動いてる! やったね。

と思ったんだけど...

落しあながあります。callCCの中と外で同じ関数を使いまわすとちゃんと動きません。

const incCPS = x =>ret(x +1)
const g = x =>
  callCC(exit => (x === 0 ? exit(0): ret(x))
         (incCPS)
         (incCPS)
        )
  (incCPS)
  (evalCont)

g(0)  // 1 になってほしいのに 3 になっちゃう...
g(1)  // 4

jumpToで関数が同じかどうかで判断してるから、そりゃそうなるわ。いい考えだと思ったんだけどなあ...

何とかしてみる

泥縄式ですが対策はないことはないです。何か他とかぶらないもので callCC の出口を教えてやればよい。
Symbol を使ってみます。

const Extract = Symbol("extract")

const ret = x => 
  k => k === Extract ? m => m(x) : k(x)

const evalCont = 
      x => x

const callCC = c => 
  c(Extract)

const exit = x => 
  k => k === Extract ?  m => m(x) : exit(x) 

何かかえってすっきりしたかも?

まず、callCC の 終わりを教える Extract を定義しました。
callCC は 継続のいれもの内の値 を (本来継続ではない)Extract に渡そうとします。
ret と exit は、Extract を受けとったら、Extract は捨てて、その次の継続に値を渡そうとします。
jumpTo は、もう callCC の継続を束縛しなくてもよくなったので、 直接 exit として定義します。

今度はうまく行くかな?

const incCPS = x =>ret(x + 1)

const g = x =>
  callCC((x === 0 ? exit(0) : ret(x))
         (incCPS)
         (incCPS)
        )
  (incCPS)
  (evalCont)

g(0)  // 1 
g(1)  // 4

うん、ちゃんと動いてる。やったね!

もうちょっと何とかしてみる

この見た目なら人類が普通にcallCCを使う日も近いんじゃないでしょうか?
基本これで、ちょい改良します。
このシステムで始終使うret の中で比較をしてるので速度がだいぶ落ちるってのがあります。
ret は元に戻して他の部分を工夫します。

const SkipOut = x => ret(x)  

const ret = x => 
  k => k(x)

const evalCont = 
      x => x

const callCC = c => 
  c(SkipOut)

const exit = x => 
  k => k === SkipOut ? ret(x) : exit(x) 

Symbolだったところを関数にして、独自性だけが欲しかったところを機能も使うようにしました。

ret(x) は SkipOut の関数の機能を使って、ret(x) を返します。
exit(x) は SkipOut かどうかを判断して ret(x) か exit(x) を返します。

これもちゃんと動くようです。

const incCPS = x =>ret(x + 1)

const g = x =>
  callCC((x === 0 ? exit(0) : ret(x))
         (incCPS)
         (incCPS)
        )
  (incCPS)
  (evalCont)

g(0)  // 1 
g(1)  // 4

これがいいかな?