2012/07/05

gitと継続の類似性、というのをふと考えた。

gitは変更の依存関係を記録している。マージを考えなければ、これはブランチを葉とする木構造になる。一方、継続がある処理系ではスタックが木構造になる。ただしgitではスタックのポップに相当する操作 (git checkout HEAD^) はあまり一般的ではないが。

call/ccで継続を捕まえるのは、gitの開発ツリーで現在のHEADコミットIDを覚えておく(タグでもつけて)ことに相当する。git checkout HEAD^ で開発を巻き戻しても、コミットIDさえ覚えていればいつでもその状態に戻ってこれる。

いくつかスタックを積む=コミットする

     CALL/CC
---A----B----C----D----E
                       ^SP

もいちどcall/ccでコミットEを記憶

     CALL/CC        CALL/CC
---A----B----C----D----E
                       ^SP

call/cc を使ったコルーチンは、二つのブランチを行ったり来たりする感じ。

上の状態から別の変更をいくつかコミットした。

     CALL/CC        CALL/CC
---A----B----C----D----E
         \
          \
           F----G----H
                     ^SP

ここでcall/ccでもってIを記録しておいて…

     CALL/CC        CALL/CC
---A----B----C----D----E
         \
          \       CALL/CC
           F----G----H
                     ^SP

Eを記憶していた継続を起動 = git checkoutでブランチを乗り換え

     CALL/CC        CALL/CC
---A----B----C----D----E
         \             ^SP
          \       CALL/CC
           F----G----H

部分継続はgit rebaseに少し似ているかもしれない。 git resetと区別するために、部分継続のshift/resetを大文字でSHIFT/RESETと書くことにする。

スタックが深くなってゆく途中でRESET、SHIFTを発行したとする。

      RESET          SHIFT
---A----B----C----D----E
                       ^SP

ここからもひとつpopしたとする。 (git checkout HEAD^)

      RESET          SHIFT
---A----B----C----D----E
   ^SP

新たな変更を加えてcommitしてく。

      RESET          SHIFT
---A----B----C----D----E
    \
     \
      F----G
           ^SP

途中でRESETしたとする。

      RESET          SHIFT
---A----B----C----D----E
    \
     \   RESET
      F----G----H----I
                     ^SP

この時点でさっきのSHIFTで捕まえた部分継続を起動することは、 git rebase --onto G B E に相当する。

      RESET          SHIFT
---A----B----C----D----E
    \
     \   RESET
      F----G----C'---D'---E'
                          ^SP

とここまで考えたんだけど、マージとか考え出すとアナロジーが破綻するのでやっぱり無理がある気がして放り投げ。オチは無い。

Island Life