書籍紹介『アンダースタンディング コンピュテーション――単純な機械から不可能なプログラムまで』

書籍紹介『アンダースタンディング コンピュテーション――単純な機械から不可能なプログラムまで』

書いた人:ささだ

書籍情報

1697_under_computation_cvr_stroke.jpg
書籍名
アンダースタンディング コンピュテーション――単純な機械から不可能なプログラムまで
著者、監訳者、訳者
Tom Stuart 著、笹田 耕一 監訳、笹井 崇司 訳
発売日
2014年09月18日
ISBN
ISBN978-4-87311-697-6
原書
Understanding Computation

公式ページより。

本書は計算理論をRubyでわかりやすく紹介する書籍です。コンピュータサイエンスの主要なテーマである「計算とは何か」という問いに対して、難しい数学の知識を利用をせず、Rubyを使って実際にプログラムを作りながら解説します。さらに、なぜこれらのアイデアが大切なのか、そしてそのアイデアは我々の日常的なプログラミングにどう関係していくのかを解き明かしていきます。日本語版ではまつもとゆきひろさんによる「日本語版まえがき」を収録。プログラミングの根底にある理論を学ぶことで、より広く深くプログラミングを考えたいプログラマ必携の一冊です。

書籍の紹介

なんの因果か、監訳者をさせてもらったので、宣伝するために記事を書きます。

本書「アンダースタンディング コンピュテーション」は、あおり文どおり、コンピュータサイエンスで出てくる、チューリングマシンとか、なんとか意味論とか、そういう難しそうな話を、Ruby で動くコードを使って紹介しているので、数学とかわからなくても安心! な俺得な本です。

まずは意味論について紹介して、その後オートマトン、チューリングマシンと進み、万能計算機についての紹介をします。そして、ラムダ計算やらなにやら、万能計算機と同等の計算能力をもつ計算モデルを紹介し、それらがチューリングマシンと同様に万能であることを説明します。何言ってるかよくわからないかもしれませんが、本書を読むと、何が万能やねん、とか、これらが同じように万能であるか、とか、そういう説明する方法なんかがわかると思うので、興味があったら是非読んで下さい。

最近私が Ruby のベンチマークで追加した https://github.com/ruby/ruby/blob/trunk/benchmark/bm_app_lc_fizzbuzz.rb のコードが、いわゆる FizzBuzz のコードになっているのですが、ラムダ計算で実装されたものになります。なんじゃこりゃ、と思うかもしれませんが、これがどう、何故動くのか、本書ではキッチリ説明してあります(というか、このコード自体が本書からの引用です。著者の許可を得ています)。

で、万能計算機の限界(計算不能性)を紹介して、最後に型推論の簡単なところを紹介して終わります。ある大学の先生に紹介したんですが、「このページ数にこんなに詰め込んであって凄い!」という書評を頂きました。というわけで、興味がある方は買って下さい。


さて、るびまなので、あんまり内容と関係ないんですが、どんな Ruby コードが書いてあるか紹介してみると、Ruby で Ruby らしくない、副作用のないコードを使っています。これはかなり衝撃的でした。

たとえば、スタックの実装ですが、こんな感じです。

 class Stack < Struct.new(:contents)
   def push(character)
     Stack.new([character] + contents)
   end

   def pop
     Stack.new(contents.drop(1))
   end

   def top
     contents.first
   end

   def inspect
     "#<Stack (#{top})#{contents.drop(1).join}>"
   end
 end
 # usage on IRB
 >> stack = Stack.new(['a', 'b', 'c', 'd', 'e'])
 => #<Stack (a)bcde>
 >> stack.top
 => "a"
 >> stack.pop.pop.top
 => "c"
 >> stack.push('x').push('y').top
 => "y"
 >> stack.push('x').push('y').pop.top
 => "x"

スタックへの push は、まぁ Ruby だと、インスタンス変数で持った配列へのアクセスとして実装されるんじゃないかと思います。が、この実装では、新しいスタックを作って返しています。

本書から当該箇所への言及を引用します。

これは純粋関数的(purely functional)なスタックです。#push メソッドと#pop メソッドは非破壊的です。これらは既存のスタックを変更する代わりに、新しい Stack インスタンスを返しています。この実装は毎回新しいオブジェクトを生成するため、破壊的な #push と #pop 操作を持つ伝統的なスタック(そうしたければ、Array をそのまま使えます)よりも効率は悪くなりますが、取り扱いが簡単になります。なぜなら、2箇所以上で使われる Stack を変更したときの影響について、気にしなくてもよいためです。

関数型言語などで使われるアプローチですね。ちなみに、それらの言語では、このようにまるっとしたコピーを作らないで、できるだけ中身を共有するような効率の良い実装が使われることが多いと思います。

というかそもそも、私は Struct をこんなふうに使うなんて知らなかったですよ!

ちなみに、本書で開発するチューリングマシンを使うと、次のように遊ぶことができます(これも、本書からの引用)。

 >> rulebook = DTMRulebook.new([
      # 状態1: aを探して右にスキャンする
      TMRule.new(1, 'X', 1, 'X', :right), # Xをスキップする
      TMRule.new(1, 'a', 2, 'X', :right), # aを消して、状態2に進む
      TMRule.new(1, '_', 6, '_', :left),  # 空白を見つけて、状態6(受理状態)に進む

      # 状態2: bを探して右にスキャンする
      TMRule.new(2, 'a', 2, 'a', :right), # aをスキップする
      TMRule.new(2, 'X', 2, 'X', :right), # Xをスキップする
      TMRule.new(2, 'b', 3, 'X', :right), # bを消して、状態3に進む

      # 状態3: cを探して右にスキャンする
      TMRule.new(3, 'b', 3, 'b', :right), # bをスキップする
      TMRule.new(3, 'X', 3, 'X', :right), # Xをスキップする
      TMRule.new(3, 'c', 4, 'X', :right), # cを消して、状態4に進む

      # 状態4: 文字列の末尾を探して右にスキャンする
      TMRule.new(4, 'c', 4, 'c', :right), # cをスキップする
      TMRule.new(4, '_', 5, '_', :left),  # 空白を見つけて、状態5に進む

      # 状態5: 文字列の先頭を探して左にスキャンする
      TMRule.new(5, 'a', 5, 'a', :left), # aをスキップする
      TMRule.new(5, 'b', 5, 'b', :left), # bをスキップする
      TMRule.new(5, 'c', 5, 'c', :left), # cをスキップする
      TMRule.new(5, 'X', 5, 'X', :left), # Xをスキップする
      TMRule.new(5, '_', 1, '_', :right) # 空白を見つけて、状態1に進む
    ])
 => #<struct DTMRulebook rules=[...]>
 >> tape = Tape.new([], 'a', ['a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'], '_')
 => #<Tape (a)aabbbccc>
 >> dtm = DTM.new(TMConfiguration.new(1, tape), [6], rulebook)
 => #<struct DTM ...>
 >> 10.times { dtm.step }; dtm.current_configuration
 => #<struct TMConfiguration state=5, tape=#<Tape XaaXbbXc(c)_>>
 >> 25.times { dtm.step }; dtm.current_configuration
 => #<struct TMConfiguration state=5, tape=#<Tape _XXa(X)XbXXc_>>
 >> dtm.run; dtm.current_configuration
 => #<struct TMConfiguration state=6, tape=#<Tape _XXXXXXXX(X)_>>

楽しそうですネ!

本書に出てくるコードは、http://computationbook.com/code からすべてダウンロードできます。

監訳者あとがき

監訳者後書きとして書いたものを、転載しても良い、とのことだったので転載します。


これなら私でも読める、と思いました。

私(監訳者)はプログラミング言語処理系を開発する仕事をしています。ですが、プログラミング言語に関わる理論が苦手で、なるべく近寄らないようにしていました。この分野の教科書では、数学というツールを使い、無駄なく、緻密な議論が華麗に展開されていくことが多いですが、その基礎を知らないと、とっつきにくく感じられることもあると思います(私にはそうでした)。また、オートマトンやラムダ計算など、個々のトピックは知っていても、なぜそれらを学ぶ必要があるのか、いまいちピンとこない人もいるのではないでしょうか(私がそうでした)。このように、プログラミングは得意としていても、プログラミング理論というと二の足を踏んでしまう人は、一定数存在するのではないかと思います。

今回、本書(原著タイトル:Understanding Computation)の監訳の話を頂いたとき、このように理論分野が苦手でしたが、これなら私でも読める、と思わせる説得力がありました。難しいテーマを扱っているにも関わらず、読みやすい文章に、具体的なRubyプログラム。とくに、6章にある、FizzBuzz問題をラムダ計算で解く、数ページにもわたる最終的なProcオブジェクトだけでのRubyプログラムは圧巻です。

本書はコンピュータサイエンスの主要なテーマである「計算とはどういうものか」という問いに対して、プログラムの意味から始めて、単純な機械から万能機械、計算可能性から決定不能問題といった重要なトピックをわかりやすく紹介しながら、答えを探っていきます。さらに、紹介した理論を一歩ずつRubyプログラムで実現していくため、プログラムの挙動を通じて理解を深めていくことができます。プログラムは手元の計算機環境で実行することができるので、読者は納得するまでいじって試すことができます。

まえがきの冒頭に、「本書は、プログラミング言語と計算理論に興味のあるプログラマ、特に数学やコンピュータサイエンスのバックグラウンドのない人のために書かれています」とあります。いまさら大学の講義を受けるのも難しいけれど、プログラミング言語理論にはちょっと興味があった、という人にとって、本書はうってつけです。もちろん、この道を学ぼうとする初学者にとっても、よい導きの書となるでしょう。本書に出会うことができる学生さんが、本当に羨ましいです。

なお、本書は計算理論やプログラミング言語理論の教科書ではありません。厳密さよりもわかりやすさを優先しているため、形式的な議論などは行なわれていません。この分野をより専門的に勉強したい方は、別の教科書などを参照してください。

日本語訳のサポートページは http://www.oreilly.co.jp/books/9784873116976/ にあります。より発展的な内容を勉強するための、本書の次に読むべき本なども紹介しています。また、登場するRubyプログラムは、すべて http://computationbook.com/code にて原著者によって公開されています。自習などで役に立てて下さい。

このように、高度な内容を含み、訳出が難しい部分のある原書でしたが、笹井崇司さんによりわかりやすく翻訳して頂きました。また、Rubyの父であるまつもとゆきひろさん(matz)に前書きを寄稿して頂きました。

本書の監訳では、稲葉一浩さん(@kinaba)、福森匠大さん(http://sorah.jp/)、遠藤侑介さん(@mametter)、酒井政裕さん(@masahiro_sakai)、住井英二郎さん(東北大学)、坂口和彦さん(筑波大学)、山下伸夫さん(聖徳大学)、上野雄大さん(東北大学)という錚々たる識者の方々に内容をレビューしてもらい、助言を頂きました。この場を借りて、御礼申し上げます。とくに、遠藤さんには全編に渡って丁寧にレビューして頂き、専門家としての多くのご指摘を頂きました。また、鳥井雪さん(妻)には一緒に勉強しながら全編をチェックして頂きました。苦手な分野での初めての監訳で、品質をここまで高めることができたのは、協力して下さった皆様のおかげです。

本書が、あなたの楽しいコンピューティングライフの一助になれば幸いです。

目次

 日本語版まえがき
 はじめに

 1章 Rubyひとめぐり
     1.1 対話型 Rubyシェル
     1.2 値
         1.2.1 基本データ
         1.2.2 データ構造
         1.2.3 Proc
     1.3 制御フロー
     1.4 オブジェクトとメソッド
     1.5 クラスとモジュール
     1.6 その他の機能
         1.6.1 ローカル変数と代入
         1.6.2 文字列の式展開
         1.6.3 オブジェクトのインスペクト
         1.6.4 文字列のプリント
         1.6.5 可変長引数のメソッド
         1.6.6 ブロック
         1.6.7 Enumerable
         1.6.8 Struct
         1.6.9 モンキーパッチング
         1.6.10 定数の定義
         1.6.11 定数の削除

 第I部 プログラムと機械
 2章 プログラムの意味
     2.1 「意味」の意味
     2.2 構文
     2.3 操作的意味論
         2.3.1 スモールステップ意味論
         2.3.2 ビッグステップ意味論
     2.4 表示的意味論
         2.4.1 式
         2.4.2 文
         2.4.3 応用
     2.5 実際の形式意味論
         2.5.1 形式
         2.5.2 意味の理解
         2.5.3 その他のスタイル
     2.6 パーサの実装

 3章 最も単純なコンピュータ
     3.1 決定性有限オートマトン
         3.1.1 状態、規則、入力
         3.1.2 出力
         3.1.3 決定性
         3.1.4 シミュレーション
     3.2 非決定性有限オートマトン
         3.2.1 非決定性
         3.2.2 自由移動
     3.3 正規表現
         3.3.1 構文
         3.3.2 意味論
         3.3.3 パース
     3.4 等価性

 4章 能力を高める
     4.1 決定性プッシュダウン・オートマトン
         4.1.1 ストレージ
         4.1.2 規則
         4.1.3 決定性
         4.1.4 シミュレーション
     4.2 非決定性プッシュダウン・オートマトン
         4.2.1 シミュレーション
         4.2.2 非等価性
     4.3 プッシュダウン・オートマトンによるパース
         4.3.1 字句解析
         4.3.2 構文解析
         4.3.3 実用性
     4.4 どれだけ能力があるか

 5章 究極の機械
     5.1 決定性チューリングマシン
         5.1.1 ストレージ
         5.1.2 規則
         5.1.3 決定性
         5.1.4 シミュレーション
     5.2 非決定性チューリングマシン
     5.3 最大の能力
         5.3.1 内部ストレージ
         5.3.2 サブルーチン
         5.3.3 複数のテープ
         5.3.4 多次元のテープ
     5.4 汎用機械
         5.4.1 エンコード
         5.4.2 シミュレーション

 第II部 計算と計算可能性
 6章 無からのプログラミング
     6.1 ラムダ計算をまねる
         6.1.1 Procの利用
         6.1.2 問題
         6.1.3 数
         6.1.4 ブール値
         6.1.5 述語
         6.1.6 ペア
         6.1.7 数値演算
         6.1.8 リスト
         6.1.9 文字列
         6.1.10 解答
         6.1.11 高度なプログラミングテクニック
     6.2 ラムダ計算の実装
         6.2.1 構文
         6.2.2 意味論
         6.2.3 パース

 7章 至るところにある万能性
     7.1 ラムダ計算
     7.2 部分再帰関数
     7.3 SKIコンビネータ計算
     7.4 Iota
     7.5 タグシステム
     7.6 循環タグシステム
     7.7 コンウェイのライフゲーム
     7.8 ルール 110
     7.9 ウルフラムの 2,3チューリングマシン

 8章 不可能なプログラム
     8.1 厳然たる事実
         8.1.1 万能システムはアルゴリズムを実行できる
         8.1.2 プログラムはチューリングマシンの代わりになる
         8.1.3 コードはデータである
         8.1.4 万能システムは永久にループできる
         8.1.5 プログラムは自己参照できる
     8.2 決定可能性
     8.3 停止性問題
         8.3.1 停止性チェッカーの構築
         8.3.2 決してうまくいかない
     8.4 その他の決定不能な問題
     8.5 残念なこと
     8.6 なぜ起こるのか
     8.7 計算不能性に対処する

 9章 おもちゃの国のプログラミング
     9.1 抽象解釈
         9.1.1 ルート計画
         9.1.2 抽象化:符号の掛け算
         9.1.3 安全と近似:符号の足し算
     9.2 静的意味論
         9.2.1 実装
         9.2.2 利点と制限
     9.3 応用

 あとがき
 監訳者あとがき
 索引

おわりに

目次を読んで、「興味がある人」という人には良い本だと思うので、良かったら買ってね!

(売り上げは、私の懐にはほとんど影響しないのだけど...)