書評：アンダースタンディングコンピュテーション
監訳者のささださんから「アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで」を頂いたので紹介。
「プログラムの『意味』とは何か？」という抽象的な問いに真っ向から挑む本。プログラムの「意味」には、「それによって計算機がどう操作されるか」で表現する方法と、「それを別の（もっとシンプルな）言語に変換するとしたらどうなるか」で表現する手法とがある。本書ではこの２つの手法があることを解説し、それぞれの手法について深堀りしていく。
「計算機がどう操作されるか」路線では、もちろん次に「『計算機』って何だ？」という問いに挑む必要性が出てくる。まずは能力の劣った計算機である「決定性有限オートマトン」から初めて、それが正規表現というある種のプログラミング言語とどういう対応の仕方をしているのかを解説するのにまる1章割いている。このストーリー仕立ては面白い。
その後、有限オートマトンの能力の限界について解説し、更に能力を高めた機械として「プッシュダウン・オートマトン」について解説する。これにまたまる1章を割いた上で、次の章でついに本丸であるところの「チューリングマシン」が登場する。熱い！
6章から第二部が始まる。この章では「最小限のプログラミング言語」を作るために、Rubyからいろいろな機能を取り除いて、最終的に「変数の参照」「一引数関数の作成」「一引数関数の呼び出し」の3つだけしかない、「型なしラムダ計算」にたどり着く。この章のゴールは文字列も代入も数値も制御構文もない小さい言語でFizzBuzzを実装するところにある。そんなことができるってことに驚く人もいるかもしれないね。
次の章では型なしラムダ計算で万能チューリングマシンをシミュレートできることを解説してから、同様にチューリング完全であるような色々なもの（SKIコンビネータ計算、Iota、タグシステム、コンウェイのライフゲーム、…）を紹介している。その次ではプログラムすることが不可能な問題について。最後の章ではプログラムを正確に実行することなく、単純化して実行することで有益な情報を引き出すことについて解説している。
いやー、すごい本だ。300ページちょいでこの範囲を俯瞰できるとは。
この本は「数学やコンピュータサイエンスのバックグラウンドがない人」向けに書かれているとのこと。「計算理論に興味のある人に」とも書いてあるけど、たぶん世の中の大部分の人はこれが「計算理論」と呼ばれていることを知らないんじゃなかろうか。
UnlambdaだとかLazyKだとか*1、関数だけで色々できちゃうだとか*2、Yコンビネータがどうとか*3、チューリング完全がどうとか*4そういう話をブログなどで断片的に聞いて気になっている人もいるかと思う。そういう話題が一体どういう位置づけなのか、俯瞰した地図を与えてくれるのが本書だ。
