30歳からのプログラミング

30歳無職から独学でプログラミングを開始した人間の記録。

『コンピュータシステムの理論と実装』を読んだ

「コンピュータが動いている仕組みを知りたい? だったら実際に作ってみるのが一番!」というわけで実際にコンピュータを作っていく、他に類を見ない一冊。
単純な電子回路から始まってアプリケーションソフトウェアの開発まで行うので、各論よりもまずは全体像を掴みたい、各モジュールがどのように連携してひとつのシステムとして動いているのかを知りたい、という人に特にお勧めできる。
どのモジュールにおいても詳細には立ち入らないので、低レイヤの入門としてもよいかもしれない。

www.oreilly.co.jp

Twitter でお勧めされてよさそうだったので、読み始めた。
存在は知っていたが敷居が高そうで敬遠していたのだが、そうでもないとのことだったので。

twitter.com

twitter.com

結果として、読んでよかった。自分が知りたかったことを知れた。

コンピュータがどのように動いているのか、プログラムはどのように実行されるのか、ということについて何となくだがイメージできるようになった。
これまでは、コンピュータシステムがひとつの巨大なブラックボックスになっていて、その中で何が行われているのか、全く分かっていなかった。断片的な知識はあるのだが、それがつながっていない。「01だけで全ての情報を表現する」みたいな話は知っていたが、それがどうして「コンピュータ」になるのか分からなかった。01を扱う単純な回路がコンピュータになってしまうことには違和感を感じるというか、唐突なジャンプがあるように思えた。「単純な回路」と「コンピュータ」が同一線上にはなくて、魔法のように感じてしまっていた。
本書を読んで、魔法などなく、ちゃんと地続きの話なんだと感じることができた。

プリミティブな機械をほとんど魔法のように仕立て上げる仕組み

という表現が本書に出てくるが(250ページ)、まさに人間の努力によって魔法のようになっているだけで、元を辿れば単純な機械なのだ。

ブラックボックスは解体され、もう少し細かい粒度で「コンピュータシステム」を捉えられるようになった。
ブラックボックスを開けて、その中がどのような部品で構成されているのか、何となくはイメージできるようになった。
まだ曖昧な理解の部分は多いし、各部品の中身についても理解が浅いのだが、部品同士の関係性、それぞれの部品の役割、全体の処理の流れといったものを多少なりとも理解できるようになったのは大きい。
そういう状態になりたくて本書を読もうと思ったわけだから、よかった。

とにかく全体像を知りたかった。その分野の全体を貫くような原理や概念、分野全体がどういう構成や構造になっているのかを示す見取り図、そういったものがあると学習効率が大幅に向上するから。
個々の部品の詳細ではなく、それらの部品の組み合わせによって作られる全体を、まずは理解する。そうすることで、それぞれの部品が何のために存在するのか、どういう役割を期待されているのか、他の部品とどのように連携しているのか、といったことが分かってくる。そうすると、部品自体を勉強するときの効率がよくなる。資料に書かれている文章の文脈や行間を読み取れる可能性が高まり、理解が捗る。
新しい部品が出てきたときのキャッチアップも、やりやすくなる。それが何のための部品なのか、全体の構造のうちのどの部分にあたるものなのか、といったことが分かるから。そうすると議論の要点を把握しやすいし、その部品が(既存の部品と比較して)どんな特徴を持っているのか、何を解決しようとしているのか、理解しやすくなる。

全体像の把握は、課題解決のスピード向上にもつながると思う。
何か解決したいことがあった際に、大体どんなことをすればいいのか、大まかなあたりを付けることができる。しかも高い精度で。解決のための具体的な知識を持っていなかったとしても、どういう風にアプローチすればいいのか、どの角度から攻めればいいのか、推察できる。だから、何を調べればいいのかが分かる。
逆に全体像を理解していない場合、取っ掛かりを掴めなかったり、見当違いのことをしたりして、遠回りすることになる。
この記事に出てくる「jQuery から DB を操作する方法とかを調べることになります」という例が分かりやすくて好きなのだが、なぜそういうことになってしまうのかというと、記事にあるように、クライアントサーバモデルというウェブサービスの全体像に関する知識が不足しているから。
ある程度経験のあるウェブプログラマからすれば笑い話かもしれない。しかし自分は、これと同じような過ちを多発してしまっているのではないかという疑念を抱いている。コンピュータシステムを理解していないことで。だから、細部の詳細はともかく、基本的な仕組みや考え方は理解したいという気持ちがあった。
それが分かれば、演繹的に考えることができるようになる。さっきの例で言えば、クライアントサーバモデルという考え方を理解していれば、そして jQuery はクライアントで UI を作るためのライブラリであるということを理解していれば、jQuery で DB を操作することはできない、ということが論理的に導き出せる。逆に仕組みや原理を理解せずに機械的に「jQuery では DB を動かすことはできない」ということだけを覚えてしまうと、「じゃあ React は? Vue では動かせるの?」ということをいちいち調べることになってしまう。

この「全体と部品」という構造は再帰的なものであり、部品だと思っていたものも、それ自体がひとつの全体であり、その中にはそれを構成する様々な部品がある。そして全体として捉えていたものも、レイヤーや粒度を変えれば別の「全体」を構成する部品であったりする。

本書は、それ以上は複数の部品に分解できないような、プリミティブな要素からスタートする。
具体的には、単純な電子回路からスタートする。それを構成する部品やさらにその部品としてトランジスタや半導体、シリコン、といったものがあるが、それらの話題は物理学の領域になってくるので本書では扱わない。電子回路を最小要素として、そこから話を進めていく。

まずは回路同士を組み合わせて複雑な回路を作り、さらにそれを組み合わせて、単純な計算や保存を行えるいくつかの装置を作る。そして装置を組み合わせて、コンピュータアーキテクチャを完成させる。ソフトウェアも同様に拡張を繰り返していき、単純なシステムを部品として、より大きくより複雑な全体を作っていく。
そして最終的には、「高水準言語で書かれたアプリケーションを動かせるコンピュータシステム」という全体像に到達する。

そして本書は、各章が、部品(モジュール)単位で分かれている。
ある章で部品を完成させたら、その次の章でその部品を土台にしてより複雑な部品を作る、という形で進んでいく。
そのため章毎の独立性が高く、興味のある章から読むということが可能になる。
そして目次を見ると分かるが、どの章も同じ構成になっていて話の流れに一貫性があり、読みやすい。

実際に手を動かすというが本書の特徴で、そのためのツールやテストスクリプトもネット上で無料で取得できる。
特に素晴らしいのはテストスクリプトで、このおかげで自分が何を作るべきかが明確になるし、正しく作れているのかを客観的に判定できる。
ただ、全てを実装しようとするとかなり時間が掛かるはずなので、無理してやる必要はないと思う。ただ本書を読むだけでも、かなり勉強になる。自分も一部しかやっていない。

注意点としては、本書の内容はかなり端折られたものであるということ。
全体像を示すのが目的なのだから当然だとは思うし、細部に立ち入りすぎても仕方ないから、不満というわけではない。
だが特に OS は、現実のそれとはかなり異なるので注意が必要。
本書で OS として作られるものは、「OS が果たしている役割を実装したライブラリ」である。アプリケーションを書く際にハードウェアを意識しないで済むよう、ハードウェアが絡むような処理を予め実装してライブラリとして切り出しておいた、という話である。
そのため、マルチタスクは対応しておらず、コンパイルしたアプリケーションをハードウェアで直接実行する形になっている。

もうひとつの注意点は、難解とまでは言わないが、決して初心者向けではないこと。
多少なりとも低レイヤの用語に触れたことがないと、なかなか厳しいと思う。
図や表が豊富であり、最初に受ける印象よりは簡単ではあるが、初心者向けというわけではない。
自分の場合、より丁寧に記述してある『痛快! コンピュータ学』と『基礎からわかるTCP/IP ネットワークコンピューティング入門 第3版』の第 3 章を副読本として使った。本書と補い合うような内容であり、理解が深まった。

books.shueisha.co.jp

www.ohmsha.co.jp

以下は、本書の内容を、副読本の内容も交えながら整理したもの。

ハードウェアとバイナリコード

値の計算

コンピュータは01の組み合わせによって情報を表現し、処理を行う。

ブール代数という理論が、これを支えている。
ブール代数では、ブール値と呼ばれる 2 種類の値を対象に演算を行う。ブール値は01でもいいし、truefalseでもいいし、onoffでもいい。本書では01を用いている。
そして、ブール値に対して演算を行うための関数をブール関数と呼ぶ。
ブール関数はブール値を受け取りブール値を返すが、有名なのはANDORNOTだろう。例えばANDはブール値を 2 つ受け取り、両方とも1なら1を出力し、それ以外のケースでは0を出力する。
ブール関数はいくつかの種類があるが、ANDORNOTの 3 つの組み合わせによって、他の全てのブール関数を表現できることが分かっている。

ブール関数を実装した物理的なデバイスのことを、ゲートと呼ぶ。
ブール関数を実現していればその仕組みは何でも構わないのだが、現代では、トランジスタを使って実装されることが多い。
トランジスタで作られたゲートを回路と呼ぶ。

本書では、NAND回路だけを使える状態で開発がスタートする。
NANDとはNOT ANDのことであり、ANDとは逆の結果を返す。そして、NANDさえあればANDORNOTの 3 つを作れる。
そのため、NANDの組み合わせだけで、全てのブール関数の回路を実装できることになる。

さらに、複数の回路を組み合わせることで、多ビットや多入出力を扱える回路を作れる。
多ビットとは複数の桁を持ったブール値であり、例えば 4 ビットなら0010のような 4 桁の値を扱える。これはつまり、2 進数を表現できるということである。

ここまでに作ってきた回路を組み合わせ、そして符号付き整数の表現方法として「2 の補数」という方式を使うことで、正と負のどちらの加算も行えるようになる。

値の保存

これでブール演算と算術演算の両方を行えるようになり、値の計算ができるようになった。
だが値の計算をできるだけでは、コンピュータは作れない。値の保存も、できるようになる必要がある。

値の保存は、フリップフロップという回路とクロックという仕組みによって、実現できる。
フリップフロップもNAND回路から作り上げることができるのだが、本書では詳しく触れられていない。
フリップフロップの基本的な仕組みの説明は以下のページが分かりやすかった。

tsumori-tech.com

sagara-works.jp

フリップフロップによって、「前回の値」という概念を回路に持ち込むことができるようになった。

コンピュータにおいて「時間」という概念を表現するために使われるのが、クロック。
コンピュータのなかでは、常に信号が流れている。この信号がクロックであり、クロックの値は周期的に01を行き来している。この値が変化すると、時間の単位がひとつ進んだことになる。
この仕組みによって時間を表現することができる。

さらに、クロックの値が切り替わった瞬間を基準とすることで、全ての回路を同期させることができる。
ある回路が出力した結果が別の回路に届き、受け取った回路が処理を終えるまでには、ある程度の時間がかかる。そうすると回路と回路の整合性が問題になる。ある回路は最新の値を受け取っているが別の回路はまだ受け取っていない、ということになる。
クロックの値の変化を時間の単位とすることで、クロックの値が切り替わるまでに全ての回路に最新の値が行き渡り処理が終わっていれば、同期が取れていることになる。

本書では、クロックを実現している仕組みについては、特に触れられていない。NAND回路のように、所与のものとして与えられている。

これで、0もしくは1を、格納したり取り出したりすることができる回路を作れた。これをレジスタと呼ぶ。
そしてレジスタを並べることで、多ビットに対応したレジスタを作るができる。
さらにレジスタを積み重ねることで、複数の値を保存できるようになる。これがメモリである。
各レジスタにユニークな番号を振っていくことで、レジスタを一意に特定できるようになる。この番号をアドレスと呼ぶ。

ここまででコンピュータを作るための部品が揃ったので、あとはこれを組み合わせていく。

バイナリコードでコンピュータに指示を出す

ハードウェアをどのようなアーキテクチャにするのかについて、細かい決まりはない。
だがプログラム内蔵方式については、現代のコンピュータのほとんどが採用している。
これは、コンピュータに何をさせるかという情報をメモリに書き込み、コンピュータはメモリからそれを読み取って処理を行っていくという方式。
これによって、同じハードウェアでも異なる処理をさせることができる。
この特徴が、コンピュータをコンピュータ足らしめている。コンピュータが、単なる計算機ではなく、汎用性や柔軟性を持つ機械になった。

コンピュータは01しか扱えない。どんなに複雑な構造になっても、単純な回路の組み合わせに過ぎない。
そのため、ブール値を入力として受け取り、所定の処理を行ってブール値を出力する、という仕組みは変わらない。
コンピュータは、ブール値しか扱えない。

そのため、コンピュータに対する指示も、01の組み合わせで表現するしかない。
これを、バイナリコードと呼ぶ。
特定のアドレスXにバイナリコードを格納しておくと、コンピュータはそれを読み取り、その指示に従って処理を行う。
処理が終わるとコンピュータはアドレスX + 1に格納されているバイナリコードを読み取って、処理を行う。それが繰り返されていく。
一行のバイナリコードがひとつのアドレスに対応しているため、上記の処理の流れは、バイナリコードを一行ずつ読んでいるということになる。

コンピュータに対する指示といっても、抽象的な指示はできない。
ここまで見てきたようにコンピュータはかなり単純な仕組みなので、指示の内容も単純なものになる。
指定されたアドレスに保存されている値を読み取ったり、その値に対して算術演算やブール演算を行ってその結果を別のアドレスに格納したり、といった形になる。

バイナリコードの法則や規則などの仕様は、設計者が自由に決めていい。
但し、ハードウェアのアーキテクチャには、依存することになる。
本書のハードウェアアーキテクチャはHackと名付けられているが、Hackを動かすためのバイナリコードは、Hackの設計を前提としたものになる。
例えば、Hackのメモリで使われているレジスタは、16 ビットである。そのため、ひとつひとつのバイナリコードの長さは、必然的に 16 ビットになる。16 ビットに収めないといけない。収められないような命令は、2 つの命令に分割することになる。
そしてHackは、メモリのアドレスを 15 ビットで表現する。そのため、「ABというふたつのアドレスを指定し、Aに格納されている値に1を加算して、その結果をBに格納する」という命令は、絶対にひとつの、つまり 16 ビットのバイナリコードでは表現できない。ひとつのアドレスを指定するだけで 15 ビットを使ってしまうのだから。
このように、バイナリコードを自由に定義できるとはいえ、ハードウェアの制約は受けることになる。先程例示したような命令をひとつのバイナリコードで表現したいのなら、それが可能になるようなハードウェアにしておく必要がある。

Hackには周辺機器としてスクリーンとキーボードが与えられるが、これらの機器とのやり取りはメモリをインターフェイスにして行われる。
スクリーンの場合、ピクセル毎に、対応するメモリアドレスを割り当てる。例えば左上隅のピクセルのアドレスが801であるなら、8010を格納すると白を、1を格納すると黒を、そのピクセルは表示する。これを全てのピクセルに対して行うことで、図形や文字を描画できる。
キーボードの場合も同様に、対応するメモリアドレスを予め決めておき、どのキーを押したかを表す情報をそのアドレスに書き込めばよい。そうすればコンピュータは、どのキーを押下されたのかを判断できる。

ハードウェアの説明は以上である。
ここまで見てきたように、コンピュータは01を対象にした計算しかできない。
プログラム内蔵方式によって処理の内容を変えられるとはいえ、そもそも実行可能な処理に限りがある。
にも関わらず、コンピュータが多種多様な用途で使えるのは何故なのか。

クロード・シャノンという人物の理論によるところが大きい。シャノンは、あらゆる情報は符号化によって01で表現できることを明らかにした。
先程の周辺機器とのやり取りもまさに、符号化によって行われている。キーボードの場合であれば、A1B2shift90といった具合に、各キーに対してユニークな番号を割り振っていく。そしてその番号を 2 進数に変換すれば、全てのキーを01だけで表現できる。
そして、あらゆる情報を01で表現できるということは、あらゆる情報をひとつの仕組み、ひとつの道具で扱えるということを意味する。画像だろうが音声だろうが文字列だろうが、同列に扱える。
そしてコンピュータはまさに01の扱いに長けており、01で表現された情報を扱うのに適していた。
つまり、コンピュータが質的な進化をして複雑な現実も扱えるようになったというより、複雑な現実を01で表現できるというシャノンの発見や理論によって、現実をコンピュータで扱えるようになったと言える。

ソフトウェア

Hackアーキテクチャでは、コンピュータへの命令を格納するメモリとデータを格納するメモリは分かれており、命令を格納するメモリは読み込み専用になっている。
そのため、命令を随時書き換えることはできず、予め命令が書き込まれたメモリを使う。違う命令を実行させたいときは、メモリを差し替えることになる。

このような仕組みであるため、ソフトウェアの開発はHack上では行われず、他のコンピュータで作成したバイナリコードをメモリに書き込み、それをHackに読み込ませる形になる。
このとき、開発者がバイナリコードそのものを書いても問題はないのだが、バイナリコードは01の羅列であり、これを人間が書くのは現実的ではない。
そのため、もっと抽象度の高い形でコンピュータへの命令を表現し、それをバイナリコードに変換することが一般的になっている。

本書ではハードウェアの構築は 5 章で終わり、それ以降は、バイナリコードの抽象化を推し進めていくことになる。
抽象化はレイヤー構造になっており、複数の段階を経て、バイナリコードに変換される。
最も抽象度が高いのがJavaCのような高水準言語であり(本書ではJackという高水準言語を定義して用いる)、本書では「高水準言語 -> VM(バーチャルマシン)言語 -> アセンブリ -> バイナリコード」という順番で変換が行われる。
これはあくまでも一例であり、例えば、VM を使わない高水準言語もある。また、記述された命令全体を一括で変換する言語もあれば、一行ずつ逐次変換しながら実行していく言語もある。
何にせよ重要なのは、人間によって扱いやすい言語で記述し、それを最終的にバイナリコードへと変換することである。この仕組みによって、コンピュータへの命令を比較的簡単に記述できるようになっている。

もうひとつ、ソフトウェア開発の生産性向上において重要なのが、ハードウェアの抽象化である。
今のままでは、全てのソフトウェア開発者が、ハードウェアの仕様を理解する必要がある。
スクリーンに何かを描画しようと思ったら、スクリーンの仕様について理解し、対応するメモリアドレスはどこなのかを把握し、そのアドレスに対して適切な書き込みを行わないといけない。
これを全ての開発者が行わなければならないのは非効率だし、ハードルが高い。
ハードウェアの操作を行う処理を予め記述しておき、アプリケーションはただそれを呼び出せばよいという状態にしておけば、アプリケーションの開発は飛躍的に楽になる。
ハードウェアの操作について予め記述しておき、アプリケーションがそれを意識しないで済むようにすることが、OS の役割のひとつである。
本書で OS として作るものは擬似的なそれであり、実態はただのライブラリである。そのライブラリを利用したアプリケーションを変換すると、単一のバイナリコードになる。
実際の OS はアプリケーションとは別の独立したソフトウェアである。アプリケーションがハードウェアの機能を利用する際は OS にその仕事を依頼し(システムコール)、OS がアプリケーションの代わりにハードウェアの操作を行う。

恒等関数と extends キーワードを使った TypeScript のテクニック

この記事の内容は TypeScript のv4.1.3で、compilerOptions.noUncheckedIndexedAccessを有効にした状態で動作確認している。

参考: zenn.dev

恒等関数(Identity Function)とは、渡されたものを返す関数。

function identity<T>(arg: T) {
  return arg;
}

const x = identity(1); // const x: 1
const y = identity(() => 1); // const y: () => 1

引数をそのまま返しているため当然だが、値は変わらない。

このままだと何の意味もないが、extendsキーワードを使って型に制約を与えることができる。
例えば以下のidentityには、ReturnNumberかそのサブタイプしか渡せない。

type ReturnNumber = () => number;
const identity = <T extends ReturnNumber>(arg: T) => arg;

identity(() => 1); // Ok
identity(() => 'a'); // Error
identity((x: number) => x); // Error

これだけでは変数名: ReturnNumberのようにアノテートするのと、変わらないように見える。
だが以下のケースでは、xyで型が異なっている。

type ReturnNumber = () => number;
const identity = <T extends ReturnNumber>(arg: T) => arg;

const x = identity((): 1 => 1);
const y: ReturnNumber = (): 1 => 1;

type Foo = typeof x; // () => 1
type Bar = typeof y; // () => number

yにはReturnNumberとアノテートしているので、yの型はReturnNumber(つまり() => number)になる。
だがxに対してはアノテートしていないので、identityに渡した(): 1 => 1がそのまま返ってきて代入されるので、() => 1になる。

このように恒等関数とextendsキーワードを活用することで、値に制限を加えつつ、本来の型を保つことができる。
このテクニックを使うことで、従来は難しかった表現が可能になる。

例えば以下のxObjという制約を満たしている。
それでいてidentityに渡されたオブジェクトリテラルの型がそのまま保持されるので、keyof typeof xで具体的な情報を取れるし、プロパティへのアクセスも適切に機能する。

type Value = number;
type Obj = Record<string, Value>;
const identity = <T extends Obj>(arg: T) => arg;

const x = identity({
  one: 1,
  two: 2,
  three: 3,
});

type Foo = keyof typeof x; // "one" | "two" | "three"

x.one; // number
x.foo; // Error

そしてObjの制約に違反するようなフィールドを追加すると、TypeScript がエラーを出す。

const x = identity({
  one: 1,
  two: 2,
  three: 3,
  four: '4', // Error
});

同様のことを恒等関数を使わずに実現しようとすると、かなり難しくなる。

まず、xに対して何もアノテートをつけないと、当然のように何の制約も与えられない。

const x = {
  one: 1,
  two: 2,
  three: 3,
  four: '4', // Error にならない
};

なので、Objでアノテートしてみる。
そうすると、four: '4'のようなフィールドを加えようとした時に、TypeScript がエラーを出してくれるようになる。

しかし今度は、Fooから詳細な情報が失われ、stringになってしまった。
また、全てのプロパティへのアクセスがnumber | undefinedになってしまった。
これは先程のidentityを使ったケースに比べて、明らかに使い勝手が悪くなっている。

type Value = number;
type Obj = Record<string, Value>;

const x: Obj = {
  one: 1,
  two: 2,
  three: 3,
};

type Foo = keyof typeof x; // string

x.one; // number | undefined
x.foo; // number | undefined

以下のようにKeyを用意することで、同等の使い勝手を取り戻せる。

type Key = "one" | "two" | "three";
type Value = number;
type Obj = Record<Key, Value>;

const x: Obj = {
  one: 1,
  two: 2,
  three: 3,
};

type Foo = keyof typeof x; // "one" | "two" | "three"

x.one; // number
x.foo; // Error

だがこの場合、フィールドを追加する度にKeyxの両方に記述しないといけない。

@@ -1,4 +1,4 @@
-type Key = "one" | "two" | "three";
+type Key = "one" | "two" | "three" | "four";
 type Value = number;
 type Obj = Record<Key, Value>;

@@ -6,4 +6,5 @@
   one: 1,
   two: 2,
   three: 3,
+  four: 4,
 };

どちらか一方にだけ記述するとエラーになるため記述し忘れることはないだろうが、手間であることには変わりない。
同じ情報を二箇所で管理することになってしまっているわけで、identityを使ったケースのほうが正規化されており望ましいように思える。

参考資料