世界線航跡蔵

Mad web programmerのYuguiが技術ネタや日々のあれこれをお送りします。

2015年02月21日

アンダースタンディング・コンピュテーション

アンダースタンディング・コンピュテーション』を監訳者の笹田さんから頂戴したので、読んだ感想をまとめてみる。

この本はRubyを用いて計算理論を紹介しようというものだ。具体的には次のようなトピックを扱っている。

  • 形式的意味論
    • 操作的意味論
    • 表示的意味論
  • オートマトンとチョムスキー階層
  • ラムダ計算
  • 停止性問題と計算不能性
  • 静的意味論と型システム

サンプルが丁寧に書かれていて簡単に動作させられること。これが本書の強みだと言える。 正直なところ今までオートマトンはともかく形式的意味論は他の本を何度を読んでもいまいちピンと来なかったのだが、本書のサンプルプログラムを動かして初めて理解が進んだ気がする。

そもそも本文にも書かれているように、ミニ言語の形式的意味論をより強く(曖昧な)言語であるRubyで書いたところで理論的には意味は無い。 意味の定義がRubyの形式的意味論に依存するようになるだけで、問題をより難しくしているに過ぎないことになる*1。 それでも、読みやすく処理系の入手が容易な言語でサンプルを動かすのは学習上の利点は大きいと感じた。

いままで理解がいまいちだった理由にも思い当たった。 意味論にせよオートマトン、ラムダ計算いずれにしても、きちんと理解しようと思ったら結局は実際にステップを追って意味の評価を進めてみるしかないのだろう。 顧みれば、実務でオートマトンを書くのはたまにあることだし、そもそも私は正規表現エンジンを書きたくてプログラミングを覚えたようなものなのでその辺の経験はいくらかあった。 これに対してスモールステップ意味論を意識しながら構文解析することは少ないし、Yaccのような具体的なパーザージェネレータと教科書に出てくる数学的な表記の乖離はオートマトンのそれよりも大きい。 これが理解が進まない原因だったに違いない。

その点、本書はある程度数学的厳密さを放棄してでも読者が手を動かすことを促している。 定義を一つ一つ追って評価してみる手順を紙と鉛筆でやるのはなかなか億劫だが、幸いなことに我々の前には高性能な計算機械があるのでこれを補助に使えばそんなに大変でもない。 そこでRubyを用いた実装なのだ。いろんな入力に反応して実際に意味論が評価され抽象機械が動作するのは見ていて楽しい。

Rubyという言語の選択も悪くない。余分な構文要素や非本質的な処理なしに簡潔にプログラムの意図を書き下せるというRubyの利点が良く活かされている。 ラムダ計算そのものを出自とするいくつかの関数型言語とどちらが良いかは議論の余地があるが、Rubyの良い点を見いだすとすれば「ラムダ計算と異質な表記」であることが挙げられる。 つまり、記述されているものと記述しているものの区別が容易である。

理解をさらに進めるとすればこの後改めて、数学的により厳密な教科書を当たるべきなのだろう。ただ、初心者がまずは手軽に試して概要をつかむための本として良い本だと思った。 本書を読むならば是非サンプルプログラムはすべて実際に動かしてみるべきである。私もまだ動かしていない残りの部分をぼちぼち試してみようと思う。


*1一応Rubyの操作的意味論はISO/IEC 30170に定義されてはいるが、本書のサンプル言語の意味論より明らかに大きく複雑だ


トラックバック

http://yugui.jp/articles/884/ping

現在のところトラックバックはありません

コメント

blog comments powered by Disqus

ご案内

前の記事
次の記事

タグ一覧

過去ログ

  1. 2016年07月
  2. 2016年01月
  3. 2015年09月
  4. 2015年08月
  5. 過去ログ一覧

フィード

フィードとは

その他

Powered by "rhianolethe" the blog system