2012/07/05

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

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

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

• 現在のブランチでcall/ccを発行=現在のコミットBを記録

       CALL/CC
  ---A----B
          ^SP
  

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

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

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

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

• 最初のcall/ccで捕まえた継続を起動する(大域脱出) は git reset --hard B に相当

       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
  

• SHIFT部分の実行を終えると、スタックは自動的にresetまで巻き戻される。git reset --hard B したと思えばいい。

        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
  

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

Tags: 継続, git, Programming