『 アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで 』を監訳者の笹田さんから頂戴したので、読んだ感想をまとめてみる。
この本はRubyを用いて計算理論を紹介しようというものだ。具体的には次のようなトピックを扱っている。
サンプルが丁寧に書かれていて簡単に動作させられること。これが本書の強みだと言える。 正直なところ今までオートマトンはともかく形式的意味論は他の本を何度を読んでもいまいちピンと来なかったのだが、本書のサンプルプログラムを動かして初めて理解が進んだ気がする。
そもそも本文にも書かれているように、ミニ言語の形式的意味論をより強く(曖昧な)言語であるRubyで書いたところで理論的には意味は無い。 意味の定義がRubyの形式的意味論に依存するようになるだけで、問題をより難しくしているに過ぎないことになる *1 。 それでも、読みやすく処理系の入手が容易な言語でサンプルを動かすのは学習上の利点は大きいと感じた。
いままで理解がいまいちだった理由にも思い当たった。 意味論にせよオートマトン、ラムダ計算いずれにしても、きちんと理解しようと思ったら結局は実際にステップを追って意味の評価を進めてみるしかないのだろう。 顧みれば、実務でオートマトンを書くのはたまにあることだし、そもそも私は正規表現エンジンを書きたくてプログラミングを覚えたようなものなのでその辺の経験はいくらかあった。 これに対してスモールステップ意味論を意識しながら構文解析することは少ないし、Yaccのような具体的なパーザージェネレータと教科書に出てくる数学的な表記の乖離はオートマトンのそれよりも大きい。 これが理解が進まない原因だったに違いない。
その点、本書はある程度数学的厳密さを放棄してでも読者が手を動かすことを促している。 定義を一つ一つ追って評価してみる手順を紙と鉛筆でやるのはなかなか億劫だが、幸いなことに我々の前には高性能な計算機械があるのでこれを補助に使えばそんなに大変でもない。 そこでRubyを用いた実装なのだ。いろんな入力に反応して実際に意味論が評価され抽象機械が動作するのは見ていて楽しい。
Rubyという言語の選択も悪くない。余分な構文要素や非本質的な処理なしに簡潔にプログラムの意図を書き下せるというRubyの利点が良く活かされている。 ラムダ計算そのものを出自とするいくつかの関数型言語とどちらが良いかは議論の余地があるが、Rubyの良い点を見いだすとすれば「ラムダ計算と異質な表記」であることが挙げられる。 つまり、記述されているものと記述しているものの区別が容易である。
理解をさらに進めるとすればこの後改めて、数学的により厳密な教科書を当たるべきなのだろう。ただ、初心者がまずは手軽に試して概要をつかむための本として良い本だと思った。 本書を読むならば是非サンプルプログラムはすべて実際に動かしてみるべきである。私もまだ動かしていない残りの部分をぼちぼち試してみようと思う。
