プログラム– category –
シェル、インタプリタ、バージョン管理。小さく作り直して仕組みを知る。
-
プログラム
インタプリタを自作する演習 — 字句解析と構文解析から実行まで
1+2*3が9になる素朴な計算から始めて、字句解析・構文解析・評価の3部品で小さな言語を作ります。優先順位が関数の呼び出しの深さで表せること、スコープが親子の線であることを手で確かめます。 -
プログラム
bashは魔法ではない — シェルを自作して確かめる
毎日打っている bash が、コマンドを打った瞬間に何をしているのか。読む・分ける・実行して待つ、の3つだけです。fork と exec と wait を C言語で60行書いて、cd が外部コマンドではありえない理由まで、実際に動かして確かめます。 -
プログラム
索引が「速い」の正体 — データベースを自作する
MySQLに INSERT した瞬間、ディスクでは何が起きているのか。索引を張ると速くなるのはなぜか。答えを読むかわりに、Node.jsで30行の「追記するだけのデータベース」を書いて確かめます。書き込みは速いのに読み出しが全行走査で遅いところを20万件で実測し、メモリ上に「キー→ファイル内の位置」の索引を足して桁を変える。さらに書いた直後にプロセスを殺してデータを消し、fsync がなぜ要るのか、トランザクションログが何のためにあるのかを体で理解します。削除しても消えない追記ログ、墓標とコンパクション、B+木との違い、そして範囲検索ができないという限界まで。 -
プログラム
gitは差分を保存していない — コミットを自作する
毎日打っている git commit が、ディスクの上で何を作っているのか。先に本物の .git の中を開いて、blob・tree・commit の3種類しか無いことを確かめます。そのうえで同じものを Node.js で114行書き、自作した mygit が作ったオブジェクトを本物の git cat-file と git log に読ませます。ブランチが41バイトのテキストであること、Gitが差分ではなく毎回まるごと保存していることまで、実物で確認します。 -
プログラム
HTTPはただのテキストだった — サーバー自作
http.createServer の1行が、代わりに何をやっているのか。net モジュール(TCP)だけでサーバーを書き、生のバイト列を自分で読み、リクエスト行とヘッダを自分で分解します。改行が \r\n であること、データは1回で全部来ないこと、Content-Length を間違えるとブラウザが待ち続けること。全部わざと起こして目で確かめます。 -
プログラム
正規表現が固まる理由 — エンジンを100行で自作する
正規表現は呪文ではありません。連結・選択・繰り返しの3つだけなら、パーサとオートマトンで100行そこそこで作れます。先に /(a+)+$/ が30文字の入力で14秒固まるところを実測して見せ、そのあと自作して「なぜ固まるのか」を内側から説明します。同じ入力を自作エンジンに食わせると0ミリ秒で返る理由と、それでも実務でバックトラック方式が使われる理由まで。 -
プログラム
1万件で100倍になる — 計算量とO記法を測る
O記法は見たことがあるけれど説明はできない、という状態を終わらせます。数学は使いません。配列から1件探す処理を1000件から100万件まで測って、時間が件数に比例することを表で見る。Mapに変えると件数を増やしても変わらないことを見る。二重ループの重複検出が1000件から1万件で100倍になるところを実測し、Setで書き換えて桁を戻す。二分探索が100万件を20回で終えることをカウンタで数え、並べ替えのコストと、nが小さいときは二重ループのほうが速いという実測まで。証明はしません。全部、自分のVMで数字を出します。 -
プログラム
配列は先頭への挿入が遅い — データ構造を自作する
配列と Map があれば大抵のプログラムは書けます。それなのに教科書には連結リスト・ハッシュ表・木が必ず出てくる。理由は「それぞれ何が速くて何が遅いかが違う」からです。まず配列の先頭挿入が遅いことを10万件で実測し、連結リストを書いて逆転させ、次にハッシュ表を40行で書いて Map の中身を開け、バケツを4つに減らして衝突が O(n) に近づくところを測ります。最後に二分探索木を書き、昇順に入れると一直線に潰れて再帰が Maximum call stack size exceeded で落ちるところまで実際に起こします。OS自作のフリーリストも、自作データベースの索引も、この3つのどれかでできていました。
1