tl; dr
- 「アンダースタンディング コンピュテーション」楽しかった！
- Haskellでやった例を上げたので良かったら参考にどうぞ
本の紹介
本書は計算理論をRubyでわかりやすく紹介する書籍です。コンピュータサイエンスの主要なテーマである「計算とは何か」という問いに対して、難しい数学の知識を利用をせず、Rubyを使って実際にプログラムを作りながら解説します。さらに、なぜこれらのアイデアが大切なのか、そしてそのアイデアは我々の日常的なプログラミングにどう関係していくのかを解き明かしていきます。日本語版ではまつもとゆきひろさんによる「日本語版まえがき」を収録。プログラミングの根底にある理論を学ぶことで、より広く深くプログラミングを考えたいプログラマ必携の一冊です。
以下ざっくり各章の内容紹介
| 章タイトル | 内容 |
|---|---|
| 1章 Rubyひとめぐり | Rubyの文法やREPLの使い方の説明 |
| 第Ⅰ部 2章 プログラムの意味 | 操作的意味論や表示的意味論について、簡単な言語を実装しながら学ぶ |
| 3章 最も単純なコンピュータ | 決定性有限オートマトン、非決定性有限オートマトンと正規表現について実装しながら学ぶ |
| 4章 能力を高める | プッシュダウンオートマトン(スタックの操作ができるようになったオートマトン)を作り、前章で作ったオートマトンと比較する |
| 5章 究極の機械 | チューリングマシンについて実装しながら学ぶ |
| 第Ⅱ部 6章 無からのプログラミング | Rubyでラムダ計算を真似てFizzBuzzを書く |
| 7章 至るところにある万能性 | ラムダ計算を含む、チューリングマシン以外のチューリング完全なシステムの紹介と実装をしていく。SKIコンビネータやライフゲームなど |
| 8章 不可能なプログラム | チューリングマシンにできないこととその理由について。Quineも出てくる |
| 9章 おもちゃの国のプログラミング | 抽象解釈と静的意味論について。2章で作った言語に簡単な型システムを実装する |
この本は、簡単に言うと「プログラマのためのコンピュータサイエンス入門本」です。
上で紹介した通り、ごく簡単な言語の実装からオートマトン、チューリングマシン、ラムダ計算、型システムなど、プログラマなら「いつかは理解したい、作ってみたい」と思うような概念を実際に作りながら学ぶことができます。
300ページちょっとの本にこれだけの内容が詰め込まれていて、圧巻です。
この本は数学に親しんでない人向けに書かれていて数式や証明は出てこないので、個人的にはとても有り難かったです。おかげで挫折することなくいい感じにCSに入門できた気がします。
この本のおかげでSICPやTAPLに挑む勇気も湧いてきました。
Ruby以外の勉強したい言語でやると練習にもなって1粒で2度おいしい！
Haskell でやってみた
Ruby でやっても良かったのですが、 Haskell の方が個人的には書いてて気持ちいいのでチャレンジしてみました。
Haskell は Ruby とは互いに距離のある言語なので、写経は割と苦労します。
コード例を共有しておくので、僕と同じく Haskell でチャレンジする人がいれば参考になると幸いです。
src/ 以下が実装コードで、 test/ 以下には書籍内の動作確認に相当するコードがあります(HSpec)。
極力書籍中のコードとHaskellのコードが一致するように努めたのであまりHaskellらしくないかもしれません。
ただそれとは関係なく僕のHaskell力が低くて苦しんでる箇所もあるので、イケてないところを指摘してもらえると飛び上がって喜びます。
すごく楽しい本だったので、興味のある人は是非やってみてください！