差分をめぐる旅 (1)

Posted on October 3, 2017

はじめに

「差分をめぐる旅」と銘打ったものの、この旅はまだ終わっていない。終わっ ていないどころかちょうど身支度ができたあたりである。稚拙ではあるものの 研究成果と呼んで恥ずかしくないものは出来つつあるのだが、その成果が日の 目を見るのはまだまだ先だと考えていた。しかしながら、技術的な議論の場に のっぴきならない状況が生じつつあることや、あれこれ理由をつけて知識の公 開を先延ばしにしてもさほど良い効果は期待できないだろうといった理由から、 こうして差分に関する研究を逐次、散文・随筆形式で記録していこうと思い至っ た次第である。

なお、この研究は @pokarim との共同研究 である。共同研究とは言いつつ、貢献の大半は、いや重要なところはほぼすべ て @pokarim によって提供されたといって過言ではない。どのように研究が進 展していったか、書ける部分については必要に応じて書いていきたいと思う。

現時点で得られている成果から考えるならば、まず差分の形式的定義から始め て、それからそれがどういった性質を持つのか、あるいはプログラミングにお いてどのように役立つのか、といったことを説明すべきなのかもしれないが、 応用はおろか基礎についても十分に探索されていない現時点で、そういった順 序の説明はむしろ要らぬ誤解を与える恐れがある。また、無味乾燥な形式的定 義からは、その動機や必然性、歴史的経緯といったものが理解されにくいこと も考えられる。したがって、ここではむしろ、ある程度時系列を考慮に入れる つもりだが、基本的には私の思うままに書いていこうと思う。そのほうが結果 的に差分についての正確な理解に繋がるだろう。

ところで、研究者でもない人間が自身の活動を「研究」と称することに違和感 を覚える方もいるかもしれない。自分としてはこの研究がアカデミックにおけ る「研究」に該当するか否かは全く興味がなく、ましてや自分を研究者だとも 思っていない。ただ、適切な言葉が見つからなかっただけだ。研究という言葉 が気になるなら「探求」とか「探索」とか「夏休みの自由研究」とでも読み替 えていただきたい。

宣言的言語の罠

私が差分に至るきっかけとなったのは高精度コード補完機能の研究開発であっ た。この研究開発は宣言的言語に取り憑かれるあまり、道半ばで諦めるという か要するに失敗したわけだが、差分に至る上で良い影響を与えたのは間違いな い。幸運なことに、失敗するにしても正しく失敗できたのだ。具体的な失敗の 経緯はそのうち書くつもりだが、ここではなぜ宣言的言語が罠たりえるのか説 明したいと思う。

当時の私は差分を明示的に扱うという発想を持っておらず、むしろ技術的な趣 向としては宣言的な記述を好み、宣言的な記述が主で(主に計算効率のための) 差分は従だと考えていた。その上、差分は開発者から隠蔽されているほうが良 いと考えていた。そうしたほうがブラックボックス内で最適化する余地がある だろうと考えたからだ。要は、問題を宣言的に記述するところまではこちらで やるから、あとは機械が良きに計らえ、ということだ。魅力的なアイデアに感 じられるかもしれないが(実際私は魅力的に感じた)、これは大変よくある間 違いなのだ。

アカデミックの世界ではそういった研究がごろごろ転がっている。典型的なも のは、通常の書き方でプログラムを書けば自動的にインクリメンタル版を導出 しますよ、というものだ。言うまでもないことだがそういった研究はことごと く失敗している。性能がでないのが最大の理由なのだが、実務的にもそこはボ トルネックにならないからである。そもそも大抵の場合、バッチ版1を書くかインクリメンタル版を書くか暗黙的に決まってい ることが多い。

たとえばわれわれは、データベースにブログ記事を保存する処理をデータベー スに対するインクリメンタルな処理だとは考えていない。バッチの観点から見 れば、データベースのスナップショットは、個々のイベントを畳み込んだ結果 に他ならないのだが、ブログシステムを作っているときに普通はそう考えない。 要するに、われわれはバッチ版とインクリメンタル版のどちらを主とするか処 理に応じて暗黙のうちに切り替えているのだ。問題はどちらの場合にもほとん ど共通の道具立てで対応している現状である。インクリメンタルな処理を記述 するには、それに適した道具立てが存在するはずだ。意外なことにこの観点に 基づいた探索はほとんどされていなかった。

そういうわけで、宣言的言語の理想を追い求めるまえに、インクリメンタルな 処理を記述するためのごく低レベルな道具をまずは揃えようではないか、とい う発想に至るわけである。そしてそれが今回のテーマである差分なのだ。とこ ろで、この発想に至るまでに数多くの宣言的言語の罠を回避せねばならなかっ たことは付言する価値があるだろう。どのような困難があったかは折に触れて 書いていきたいと思う。


  1. ここでは 「インクリメンタル」の対義語として「バッチ」を使っているが適切な用語が あるかもしれない