# プログラミングする際に今日も役立ってる文献

プログラミングを独学する上で役立つ（役立った）書籍を紹介する流れが
最近ちらほら見受けられて読んでいて非常に楽しいので、
見てるばっかりでなく自分も出力していきたい、と思って書いている次第です。

あんまり肩肘はらずに、
「読んで得したなあと未だに思っている計算機科学***文献***」
ぐらいでテーマを捉えて書いてみたいと思います。

# 1. Monadic Parsing in Haskell (Hutton & Meijer '98)
いきなりですが論文です
+ https://www.cambridge.org/core/journals/journal-of-functional-programming/article/abs/monadic-parsing-in-haskell/E557DFCCE00E0D4B6ED02F3FB0466093
+ 著者版: http://www.cs.nott.ac.uk/~pszgmh/pearl.pdf

今日では「構文解析器（パーザ）」を組み立てる方法としてスタンダードなものとなったパーザコンビネータライブラリの実装方法について述べたものです。

巨大なものを構築する際に、基本的な・原始的な・不可分な道具を組み合わせて・合成して、小さいとこから大きなものを作るという、ソフトウェアやプログラムを書く際にも有効な典型的手法が、分かりやすい具体例に対するアプローチとして現れている点が興味深いです。
***手法的な話は、覚えられる程度のサイズの一つの完結する例を知ってると便利ですよね、という感じです。***

それ単体で意味のあるものを組み合わせて、一回り大きくてそれ自体で意味のあるものを作って、それを組み合わせて……という方法は明瞭でわかりよく、例えばテストなんかもしやすいわけです。
とはいえ欠点もあって、エラーハンドリングとか実行速度とかちゃんとしたとこまで考えていくと色々問題が出てきて、それについては様々な後続研究が発生して今日まで続いている……みたいなところも含めて気に入っています。

上の論文より細かく書かれている
* Monadic Parser Combinators (Hutton & Meijer '96)
* pdf: https://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf

の方がオススメです。こちらはページ数に余裕があるのでより気合の入った説明がなされていて、今日ではこれもよく知られた「Parserモナド = ListモナドにStateモナド変換子を適用したもの」という説明がされています。コンビネータライブラリの考え方そのものが、より小さい部品の合成で解釈されるという主張です。

# 2. Finger trees: a simple general-purpose data structure (Hinze & Paterson '05)
また論文です。

+ https://www.cambridge.org/core/journals/journal-of-functional-programming/article/abs/finger-trees-a-simple-generalpurpose-data-structure/BF419BCA07292DCAAF2A946E6BDF573B
+ こっから読めます: http://www.staff.city.ac.uk/~ross/papers/FingerTree.html

その昔、ICFP contest 2007というプログラミングコンテスト https://save-endo.cs.uu.nl/ があったのですが、その中で巨大文字列を操作するパートがあり、何も考えんと言語の標準ライブラリに入ってる文字列クラスを使うと実行速度が終わってしまうという回がありました。

多くの言語では遅すぎて終わったのですが、生き残ることが出来た言語とデータ型の組み合わせとして
* C++ の rope
* https://www.boost.org/sgi/stl/Rope.html
* `Ropes: an alternative to strings` https://www.cs.rit.edu/usr/local/pub/jeh/courses/QUARTERS/FP/Labs/CedarRope/rope-paper.pdf
* Haskell の `Data.Sequence`
* https://hackage.haskell.org/package/containers-0.6.4.1/docs/Data-Sequence.html

がありました。この辺のデータ構造の実装（を理解するのに使えるの）がFinger Treeの論文です。

このコンテストのsummary reportがあるのですが
http://www.cs.uu.nl/research/techreps/UU-CS-2007-029.html

この中に
> when they realised that their implementation of the DNA machine was too slow, their first instinct was often to switch to a “faster” language such as C.
> But the problem wasn’t the language but algorithmic complexity:
a straight-forward Haskell implementation using the right data structure (e.g. Data.Sequence [3]) would be fast enough and outperform by several orders of magnitude an optimised C implementation using a dumb data structure.
> So programmers should worry less about languages and more about good old complexity.

という箇所があります。
Haskellは流石にオーバーヘッドが色々あるので、全く同じ処理をCで書き直せば基本的にCに軍配があがるわけですが、この時には、データ構造のefficiencyがそのあたりの不利を余裕で覆したのです。

***アルゴリズムの本などで、データ構造には（操作の種類によって）得手不得手があるというのは我々は勿論知っているのですが、「こんなに」違ってくるのかということを身を以て体感できた瞬間だったので、今でもありがたがっています。***

読者それぞれにそういう体験があって、あなたには別の具体例があると思います。自分にとってのそれはICFP contest 2007とfinger treeという感じでした。

Finger treeのアイディアと実装自体は難しくない（計算量の解析などを行うと話は別なのですが）ので、読んだことがなければ是非読んでみてください。
また、この論文をベースにして新しく書かれたものも最近出版されました。こちらも是非。
https://dl.acm.org/doi/10.1145/3406088.3409026

# 3. SICP -- Structure and Interpretation of Computer Programs --
+ https://www.shoeisha.co.jp/book/detail/9784798135984

言わずと知れた「計算機プログラムの構造と解釈」です。
やや変わったアプローチで書かれたインタプリタやコンパイラの作り方が学べる本、と書くと間違いではないと思うんですが、正解でもないと思うんですよねえ。（現実に通用する）コンパイラ作るという目的で選ぶとなると、AppelのTiger book https://www.cs.princeton.edu/~appel/modern/ml/ とかになると思います。
ただそういう標準的なテキストには書かれないがちな Meta-circular evaluator という考え方を軸にした展開などは癖になるので読んでいて楽しいです。

で、今日でも役に立つかどうかというと、この本は（ちょっと見慣れないような）練習問題がたくさんあって、例えば1章と2章の練習問題を全部解くだけでも、あっなんか似たような思考を昔したことがあるなとなって、遡るとSICPだったということが割とあります。

あと個人的にこの本が嬉しいのは次のような場合で。
普通の飲み会とか学会の懇親会とかで、「へ〜その話面白いですね」みたいなこというと「いや、SICPの○章のExerciseにあったやん」となることが***これまでに何度も***あって、全員読んでいるので話が盛り上がる。これです。
ワンピースや刃牙、ハンターハンター、マスターキートンの話が通じない人にも、SICPの話は通じます。ほんとに。指輪物語、ナルニア国物語、ゲド戦記を知らなくてもSICPなら知ってる。

この本には個人的な思い入れがあって、丁度高校2年ぐらいの「もう高校行ってても意味ないんちゃう？」みたいな時期に巡り合った本で、大学に行くとこういうのが体系的に学べるのかな感じでちょっと冷静に考え直せたという小話があります。フィボナッチ数列の一般項を求めたのも、この本が最初だった気がします。

以前と違って、今はこの本を読むためのサポートも色々あったり(http://planet.racket-lang.org/package-source/soegaard/sicp.plt/2/1/planet-docs/sicp-manual/index.html)、途中で行き詰まっても他の読者の実装もgithubかなんかで見つかると思うので、読み進めやすくなってるかなあと思います。

# 4. はじめて読む486 (蒲地 '94)
+ https://www.amazon.co.jp/dp/4756102131
+ https://www.kadokawa.co.jp/product/318569000010/

Mona OSの本(??)で知ったものです:
https://www.amazon.co.jp/dp/4839917639

かつてOSを自作する際に今ほどよいリファレンスもなかった時代から
（そして恐らくそれ以前からも）語り継がれている本だと思うのですが、
IntelのCPU（IA32）の特にOSをサポートする機能が体系的に学べます。
ところどころコードも出てくるので、実際にコンパイルして実行しなくても、そのタイミングごとに地に足ついた理解が出来ているか確認できるのも良さ。

CPUを作るとかゴリゴリにCPUフレンドリーなプログラム最適化をしたいのでCPUを知りたいという人よりは、
どちらかというと、「OSを作ったりLinuxカーネルのソースコードを読むという立場からCPUを使うという視点」でCPUの内部に触れる折に役立つと思います。
その視点から必要になる部分のCPUの内部情報が、過不足ない良い抽象度とふんだんな図で身につくと思います。

2021年でも役に立つのかというと、
例えばページングのCPU側でのサポートの基本的な仕組みはこの頃からあるので、一度読んで基本的な仕組みを知っておくと、Linuxのカーネルのメモリ管理周りのコードを読まなくちゃならんとか、Intelのマニュアル読んで最新の事情に追いつかないといけない、という時にメチャ便利です。差分だけ読めば済むので。
業務で普通に役立っています。

一方でセグメントとか32bitでは使ったけど64bitだと使わないところも当然しっかり書いてくれているので、限界までコンパクトにまとまっていて欲しい人にはほんの少しだけ分量が辛いかも知れないです。とはいえこれは逆に言えばややレガシーなところがしっかり書かれているということ他ならず、他にもDOSでのハックも様々に書かれているなどあって、読み物としても面白いです。

# 5. Exceptional C++ & More Exceptional C++ (Sutter '99 & '01)
* https://www.oreilly.com/library/view/exceptional-c-47/0201615622/
* https://www.oreilly.com/library/view/more-exceptional-c/020170434X/

`C++`でこのタスクをどう解決する? というパズルを考えていくスタイルの本なのですが、そのやり方でこの場合もカバーできるか?? というのが徹底的に畳み掛けてこられて、うーんもう自分でプログラム書きたくないなという気分にすらなれる良書。コードは`C++`で書かれているのですが、どんな言語を使っているプログラマでも思わず唸る内容が含まれていると思うのでオススメです。
大規模な開発だと、（extensibilityとかreusabilityとか、genericityについての）コードのロバストさを念頭に置いてコードを書かないといかんのですが、そういう姿勢がこの本読むと身につくと思います。

個人的には `Object Lifetimes`, `Memory Management`, `Optimization and Performance`（効率的な文字列クラスを実装する章で自然とCoWまで話が及びます)の章が、仕事でRustのプログラムを書いている時にもメチャクチャ役に立っています。

これに似た感じの本、他にないかなー

# 6. Games and Full Abstraction for a Functional Metalanguage with Recursive Types (McCusker '98)
+ https://www.springer.com/jp/book/9781447111658

いわゆるgame semanticsの本（というより博論が書籍になったもの)なのですが、full abstraction theoremまで一冊で証明まで読もうとすると、このMcCuskerの博論が良いかなあという気がします。今だともっと良い本があるかもしれません。修士の頃に頑張って読みました。

Game semanticsってなんやねん かつ 表示的意味論は知っている人は、次のAbramskyとMcCuskerの解説PDFを ***絶対に*** 読んでください
* https://www.irif.fr/~mellies/mpri/mpri-ens/articles/abramsky-mccusker-game-semantics.pdf
* 表示的意味論別に知らなくとも、2.3節まで読んでみると、ああこういう考え方するのかというのは掴めます（なんなら別に知らなくても読めます）

表示的意味論含めて０から知りたいという人は、勝股先生の次のPDFを読んでみてください
* http://www.kurims.kyoto-u.ac.jp/~kenkyubu/kokai-koza/katsumata.pdf

Game semanticsは、プログラムに対する意味を与える一つの方法で、表示的意味論側に立つものではあるんですが、（Full abstraction theoremが成立するぐらいには）表示的意味論で操作的意味論やっている気すらしてくるぐらいに細かいレベルで色々操作できるものです。
とはいえ操作的意味論とは違って、プログラム言語のsyntacticalな要素に立脚しないので表示的意味論ではあって……

でgame semantics知ってると何の役に立つのかというと
* プログラム知らない人にプログラムを教える時に役に立つ
* 関数やクラスの設計をする時にinteractionベースで考えると視点が増えて打開策が産まれる

とかいうのがあります。

# 7. An Introduction to Kolmogorov Complexity and Its Applications (Li & Vitányi)
+ https://www.springer.com/jp/book/9783030112974
+ 幾つか版が出ているようなんですが上のが一番新しい、かつ、自分で読んだ初版から内容変わってなさそうなのでこれで

シャノン情報量よりKolmogorov Complexityベースの議論の方が好きなのでという感じで特にそれ以上でも以下でもないんですが、至るところで使います。
圧縮不能性からわりかしなんでも展開できたりするのは便利です。

(シャノン情報量とKolmogorov Complexityの２つの関係性についてはこっち見てみてください: https://homepages.cwi.nl/~paulv/papers/info.pdf)

圧縮不能性というのは、そのまんまですけど「どうやっても圧縮できん(=復元可能な形では長さを縮められない)文字列がある」みたいなことで、ちゃんと書こうとするといい感じに形式化しないといけないんですが、形式化に関しては最近丁度良い論文が出たので、興味がある方は参考にしてみてください
+ https://www.dropbox.com/s/q1whqz0v2c0falm/CPP2021-Kolmogorov-complexity.pdf

圧縮不能性使うと何が言えるのというのは、
具体例をしこたま使って体に叩き込むと便利なんですが、例えば形式言語理論でも色々あります。
有限オートマトンの面白い性質が楽に導けることもあります:
+ https://core.ac.uk/download/pdf/301633041.pdf
+ 4ページの2つ目のCorollary（two-way有限オートマトンで受理できる言語は有限オートマトンで受理できる)
+ DPDA以降はミスってるかもしれないので読まない方が良いかも

# 8.Gems of Theoretical Computer Science (Schöning & Pruim '98)
+ https://www.springer.com/jp/book/9783642643521

この本は計算論に関するよもやま話集という感じなんで、これもプログラミングする時というよりも、飲み会で役に立ちます。

各章で一つずつ重要な定理をコンパクトに証明していくのですが、
標準的な教科書では *まだ* 扱われていないものも多くて、面白いです。

例えば

+ `The Priority Method`の章は、停止性問題より（ざっくらばんに言うと）簡単だが決定不能な問題があるということを系として導ける、Friedberg-Muchnikのpriority methodを扱っていますし、
+ `The Second LBA Problem`の章は、Linear bounded automataというオートマトンのクラスがcomplementを取る操作について閉じているかという1998年になってやっと肯定的に解かれた問題などを扱っています。
+ `Hilbert’s Tenth Problem`の章も、10ページそこらで完全な証明が与えられるわけないんですが、要所を書いてくれているので、やる気がでて全証明読んでみるかという気になったりします（自分は全証明は追ったことないです）

同系統の本だと、理論計算機科学の大家であるKozenの次の本もあります。
これもオススメです
https://www.springer.com/gp/book/9781846282973

# おわりに
今日の自分のプログラミングのスタイルや
ものを考える時に影響を与えている文献でぱっと思いつくもの、
あの本で読んだこと今使ってるな（雑談含め)と思う頻度が多いもの、
で挙げてみると8つ出てきました。

他にも本当は色々あります。例えば
+ Birdとde MoorのAlgebra of Programming https://wiki.c2.com/?AlgebraOfProgramming

など。とはいえ幾ら良いと言えども、現在入手困難なものは避けました。

また、あくまでも、単に今まで読んだことがあるものという括りなので、
例えばSICPを挙げたことによって、
類似する他書を排他したいというような思惑はないです。
むしろ「自分は似たジャンルの文献でこういうのを知っていて、
様々な理由でこちらの方が良い」ということがあったら、それは知りたいです。
一冊読んじゃうと中々他のものを読まなくなるのと、
それもあって最近出版された本を読まないがちなんですよね……

本のタイトルだけ箇条書きにするぐらいでも良かった気がするのですが、
せっかくなので、
内容というよりも個人的な思い入れみたいなことを付記したところ、
やや中途半端になったかなという感じもあります。

Game semanticsっぽい考え方を普段のプログラミングで使ったり、
圧縮不能性の議論をちょっとした性質を証明したりするのに使うのは、
チャンスがあればそれはそれで一つの文章に出来たら良いな、と思いました。
今後コンパクトな良い例に遭遇して覚えていたら、
メモを作ってみたいと思います。

これを読んでくださった方にも、
是非とも私的に役に立っている文献リストを作ってもらい、
それを共有してもらえると嬉しいです。
私的なチョイスになるほど広く知られていない
面白いものが出てくると思っています。
（あとそういうものが書けたら、
[Twitterのアカウント](https://twitter.com/ranha)で教えてもらえると一層幸いです。）