2015 年に読んだ面白論文

ということで、いつものです。企画だけしておいて長いこと放置してました、すいませんでした忙しかったんです。なんならまだ忙しいです。しかしいい加減書かないと駄目だということで、とりあえず一つ紹介してみる。目標は一日一本、で三日で三本…

Genericity extensibility and type-safety in the Visitor pattern

Visitor おじさん（と勝手に呼んでる）こと Bruno Oliveira 先生の博論です。Sony Reader に突っ込んだ日付が三年前だったので、どうやら三年かけて読み終えたらしい。三年。これ 2015 年に読んだといえるのだろうか…

この論文の面白さは、兎に角論文中のこの一文が全てといってもいい気がします。

How can a thesis be written around a single design pattern? — one may wonder.

Visitor pattern というと GoF のアレです。デザインパターン一つで博論が書けるのか。書けてしまうみたいです。self-contained にするための Scala の説明とか除いて、大体 100 ページくらい書けてしまう程には、実は Visitor pattern というのは奥が深いらしい。無駄に寄り道したり XML を舐めてみたりでページ数水増しされてるなんてことはないゾ！

Visitor pattern と一言にいっても、色んな形があります。Visitor pattern の分類は "A Type-theoretic Reconstruction of the Visitor Pattern" で先行研究として行われています。Qiita にも書きました。

ようは Visitor は internal, external そして imperative, functional に分けられるということです。とりあえず以下では Visitor = Functional Visitor ということで話を進めます。

いきなり結論からいきますが、Internal Visitor は Church encoding に対応しています。じゃあ External Visitor は…？ラムダ計算におけるデータ型の encoding というと、Church encoding や Scott encoding が有名ですが、Parigot encoding というのもあります。これは元々は、古典論理に対応する物として lambda-mu calculus というものがあり、そこで使われたデータ型の encoding 方法です。実用方面からでてきた Visitor pattern ですが、整理してみると実は色々なものと対応していることが分かってくる。

そこまでいったら後はどんどんやっていくぞ、ということで、Internal と External を "Strategy" として抽象化し、Internal や External の他にも Para(Paramorphism) Strategy を追加してみたり、データ型のエンコードできるんだから、と DGP(Datatypes Generic Programming) における Indexed-type にならって Indexed-Visitor とかやってみたり…超 Generic な定義になった Visitor 一つで、どんどんやっていく。Expression Problem もやっていく。後に LtU でも取り上げられた Object Algebras に比べるとかなり重いですが、この論文での formalization があったから Object Algebras に繋がったのだなあと考えると Visitor 偉いなあという感じです。

というわけで Visitor が好きになれること間違いなしの面白論文紹介でした。

後二本くらい頑張って紹介する。TBD