これは何？
継続を勉強しようと思って、お茶の水大学の浅井先生の書かれたpdfの「shift/reset プログラミング入門」を読んでいました。pdfはこちら: http://pllab.is.ocha.ac.jp/~asai/cw2011tutorial/main-j.pdf 魅力的な例が多くて楽しかったのですが、計算を追うのが大変だったところ、shiftを戻すのが複雑な例になると大変になることがあり、手計算したいところがあったので計算したのですが、そのようなメモを残しておこうと思います。
これから読む方へ / 私がどう読んだか
あとで気づいたのですが、このpdfはACM SIGPLAN Continuation Workshop 2011という学術ワークショップで行なわれたチュートリアルのpdfのようで、こちらがメインページのようです: pllab.is.ocha.ac.jp ここに、お手持ちのプログラミング言語で試す方法が示されているので、御自分でお好みの言語で試してみると良いと思います。
私はこれに気づかず、shift/resetがある言語を探してDr.Racketを使うことにしましたが、OCamlのほうが慣れていたのでそちらにすればよかったとあとで思いました。
あと、Dr.Racketでやるときにはこちらに正確な意味論が書いてあるので、それが助けになるかもしれません:
私がDr.Racketでやった実装
2章7節のsame-fringe
ツリーを平らにしたときの等価性を継続をつかって確かめるものです。 gist.github.com
2章8節
文字列連結する対象を外部から差し込むものです。 gist.github.com
2章10節の状態モナド
状態モナドぽいものを継続で実現し、値の状態を操作して取得するものです(OchaCamlとLISPの文法の違いもありこれの理解が大変だった…) gist.github.com
計算ノート
resetとshiftの間を、穴つきの下線で強調しています。継続のなかに差し込む「k」のところで、それを戻すところがわかりやすくなっている…と思います。
2章10節の状態モナド
2章11節のA正規形変換
「a-term(ほにゃらか)」のところを、「ほにゃらか」の波下線として表記しています。これは手計算してよかった。
感謝
途中、状態モナドのところがどうしてもわからなくなり、Dr.Racketのコミュニティのdiscordにお邪魔して質問しました。そこで、usaoさん( usaoc (Wing Hei Chan) · GitHub
)という方に教えていただき、私の書いたコードをこのようにDr.Racket風に書き直してまで丁寧に教えてくだだいました。ありがとうございました。
