Webエンジニアのブログ

「コンピュータシステムの理論と実装」を要約する


コンピューターサイエンスの学習のため、「コンピュータシステムの理論と実装 ―モダンなコンピュータの作り方」という書籍を読んでいます。本記事では自分の備忘録+アウトプットとして、本の内容を要約してみます。

1章 ブール論理

論理ゲート

全てのデジタル機器は、情報の保存と処理を行うために設計された回路から出来ている。 そのような回路は、論理ゲート、または論理回路という構成要素から出来ている。

物理的には論理ゲートを作るための材料や製造方法は多く存在するが、全てのゲートは論理的には同じ振る舞いをする。

Nand関数

Nand関数は、理論的に興味深い性質を持っている。 それは、And,Or,NotはそれぞれNand(またはNor)だけから作ることができるという点である。 つまり、Nandを実現した物理デバイスが自由に使えるのであれば、どのようなブール関数でもNandをつなぎ合わせて作れるということである。

回路

現代のデジタルコンピュータのほとんどの全てが、2値データの表現と伝達を行うために電気を用いている。 しかし2値のスイッチングや伝送を行う技術が電気の他にあれば、それを採用することもできる。 実際に、過去50年間の間に多くの研究がなされており、磁石、光、バイオ、水圧、空気圧などの多くのメカニズムが使われているものもあった。

複合ゲート

論理ゲートの入力と出力は全て0と1からなる要素であるため、それらを互いに組み合わせて複合ゲートを構成することができる。 例えばAnd(a, b, c)というブール関数の実装については、And(And(a, b), c)という風に構成することができる。

私たちが触れているコンピュータは、全てこのようにシンプルな論理ゲートから構成されている。 あまりに単純なものから、人間が手に負えないほど複雑なものが作られる、ということである。

2章 ブール算術

2進数

私たちが普段使っている10進法は10を底として数を表すが、2進法は2を底とする。 例えば10011という2進数を10進数で表すとき、以下のように計算する。 1・2^4 + 0・2^3 + 0・2^2 + 1・2^1 + 1・2^0=19

2進数加算

2進数の加算をするためには、それぞれの桁を右から左へと足し合わせればよい。 その際に両方の数字が1の場合、ビットが繰り上がり、その桁上りビット(キャリービットともいう)を左の桁に加算する。 2進数の一番右の桁を最下位ビット、一番左の桁を最上位ビットというが、最上位ビットでキャリービットの値が1の場合、オーバーフローであることを報告する。 オーバーフローが報告されなければその加算は無事に終了したことになる。

符号付き2進数

n桁の2進数は2^n通りの異なるビット配列を生成することができる。 そして符号付き数字を表現するためには、この2^n通りの領域を均等にふたつに分けることが自然な方法である。

2の補数

今日ほとんどすべてのコンピューターで用いられる符号を表す方式は、2の補数と呼ばれる方式である。 n桁の2進数においてマイナスを表すには2^n - xという定義を用いる。

例えば5ビットの2進数において、-2、つまりマイナス(00010)twoを2の補数で表すとすると、 2^5 - (00010)two = (32)ten - 2ten = (30)ten = (11110)twoとなる。

この計算の結果が正しいことを証明するためには、(00010)two + (11110)two = (00000)twoであることから確認することができる。 正確には(100000)twoであるが、5ビットの2進システムで処理を行っているため、最も左に位置する6番目のビットは無視される。

2の補数表現には次のような性質がある。

  • 正の数の最上位ビットは0である
  • 負の数の最上位ビットは1である

3章 順序回路

1章と2章で構築した論理演算や算術演算の回路は、すべて組み合わせ回路と呼ばれる。 組み合わせ回路は、入力値の組み合わせだけによって関数の値が決定する。 このような回路は、状態を保つことはできない。

コンピュータは値を計算するだけでなく、その値を保存し呼び出すことができなければならない。 そのため、時間が経過してもデータを記憶することのできる記憶素子を備える必要がある。 この記憶素子を順序回路から構築することができる。

クロック

ほとんどの全てのコンピュータでは、継続的に変化する信号をマスタクロックが送信することによって時間の経過を表現する。 実際にハードウェアにおける実装はオシレーターに基づくのが一般的である。 このオシレーターは、0/1, low/high, tick/tockのようなラベル付けがされる2つのフェースを絶え間なく行き来する。 tickの始まりからtockの終わりまでに経過した時間を周期(cycle)と呼ぶ。 1周期がタイムユニット(単位時間)としてモデル化される。

フリップフロップ

コンピューターで使われている順序回路の中で、最も基本となる回路はフリップフロップである。 このフリップフロップにはいくつか種類があるが、本書ではD型フリップフロップ(以下DFF)と呼ばれるタイプを用いる。

DFFのインターフェイスは1ビットの入力と1ビットの出力である。 さらにDFFにはクロック入力があり、このクロック入力にはマスタクロックからの信号が絶えず送られる。 これらのデータ入力とクロック入力が合わさることで、DFFは時間に基づく振る舞いが可能になる。 DFFは、ひとつ前のタイムユニットの入力値を出力する。 out(t) = in(t- 1) tは現在のタイムユニット

レジスタ

レジスタとはデータを格納したり呼び出したりすることができる記憶装置である。 レジスタは、伝統的なストレージの振る舞いであるout(t) = out(t - 1)を実現する。

多ビットのレジスタは、複数の1ビットレジスタから構築することができる。 保持すべきビットの数は幅(width)と表現し、この値は16,32,64などの数字が用いられる。 そのような多ビットのレジスタの持つ値は、一般的にワード(word)と呼ばれる。

メモリ

レジスタをたくさん積み重ねることで、RAM(Random Access Memory)ユニットを構築することができる。 ランダムアクセスメモリという名前の由来は、ランダムに選ばれたワードに対して、そのワードが位置する場所に制限を受けることなく、書き込み/読み込みができる、ということから来ている。 最初にRAMの各ワードに対して、他とは重複しないユニークな番号をアドレスとして割り当てる。

RAMを設計する場合、基本的なパラメータとして幅(width)とサイズ(size)を指定する必要がある。 幅は各ワードの幅であり、サイズはRAMに存在するワードの数である。 現代の一般的なコンピューターでは、32もしくは64ビット幅で、百万を超えるサイズのRAMが用いられる。

カウンタ

カウンタは順序回路であり、タイムユニットが進むごとにout(t) = out(t - 1) + cとなるように、ある整数の値が加算されている。 ここでcは通常1が用いられる。 一般的なCPUにはプログラムカウンタが含まれ、このプログラムカウンタの出力は次に実行されるプログラム演算のアドレスとして解釈される。 また一般的なカウンタは、カウンタの値をゼロにする、新しいカウンタ値を読み込む、加算の代わりに減算を行うなどの機能を持つ。

4章 機械語

コンピュータ全体において最も重要なインターフェイスは機械語である。 機械語においてハードウェアとソフトウェアが交わり、機械語においてプログラマーの抽象的思考がシリコン上で実行される物理的操作に変換される。

プロセッサ

プロセッサは中央演算装置やCPUと呼ばれ、仕様で決められた基本的な命令セットを実現することができる。 これらの命令セットには、算術演算と論理演算、メモリアクセス演算などが含まれる。

これらの演算のオペランドは、レジスタやメモリから取り出されるバイナリデータであり、また同様に演算の結果もレジスタもしくはメモリに格納することができる。 オペランドとは被演算子、つまり演算の対象となる値のことである。例えば1 + 2という式において、1と2はオペランドであり、+は演算子である。

レジスタ

メモリへのアクセスは比較的時間のかかる操作である。 そのため、ほとんどのプロセッサはレジスタをいくつか備えており、各レジスタはひとつの値だけを保持できるようになっている。 レジスタはプロセッサから極めて近い場所にあるので、高速にアクセスすることができる。

言語

機械語のプログラムは一連の符号化された命令である。 例えば16ビットコンピュータで用いられる一般的な命令は1010001100011001のような形式になる。

この命令の意味を理解するためには、ハードウェアプラットフォームの命令セットを知らなければならない。 つまり、ハードウェアの仕様によって命令の解釈は様々である。

ハーモニック

バイナリコード(2値コード)はいくぶん暗号めいているため、機械語は通常、バイナリコードとハーモニックの両方を用いて記される。 ハーモニックとは、記号や英単語で表せられる命令文のことである。 ハードウェア設計者は、例えば1010という命令コードをADDというハーモニックで表すように決めることができる。

アセンブリ

ハーモニックを用いることで、記号を用いてプログラムを書くことができる。 その場合、テキスト処理を用いてハーモニックとオペランドへ分解し、領域ごとに対応するバイナリ表現へと変換すればよい。 その結果を組み合わせれば、バイナリの命令コードが完成する。

この記号による表記はアセンブリ言語、またはアセンブリと呼ばれる。 またアセンブリから機械語であるバイナリへと変換するプログラムはアセンブラと呼ばれる。

5章 コンピュータアーキテクチャ

プログラム内蔵方式

我々の周りにある機会と比べて、デジタルコンピュータは驚くべきほどの多様性を持つ。 この驚くべき柔軟性は、ぽうログラム内蔵方式と呼ばれる素晴らしいアイデアによってもたらされている。

コンピュータはハードウェアのプラットフォーム上で一連の命令を実行することができる。 これらの命令を組み合わせて、優れたプログラムを自由に作ることができる。

ノイマン型アーキテクチャ

今日のプラットフォームはほとんどノイマン型アーキテクチャによって構築されている。 ノイマン型アーキテクチャは、中央演算装置(CPU)を中心としてメモリデバイスを操作し、入力デバイスからデータを受け取り、出力デバイスへデータを送信する。

メモリ

ノイマン型コンピュータのメモリには2種類の情報が格納される。 ひとつはデータ項目であり、もうひとつはプログラミング命令である。

高水準言語で書かれたプログラムでは、変数、配列、オブジェクトといったデータ形式を操作することができる。 それらのデータは機械語に変換されるとバイナリデータになり、コンピュータのデータメモリに格納される。

また高水準言語で書かれたコマンドが機械語に変換されると、それらはバイナリのワードになり、機械語の命令を表すようになる。 これらの命令はコンピュータの命令メモリに格納される。

CPU

CPUはコンピュータアーキテクチャにおいて中心的な存在である。 その役割は、現在読み込まれているプログラムの命令を実行することである。 これらの命令がCPUに指示することは、計算の実行やメモリから値を読み書きすることなどがある。

レジスタ

CPUに「メモリアドレスがjにあるデータを取得せよ」とCPUが命令すると、次の手続きが発生する。 またレジスタはCPU内に物理的に存在しているため、アクセスに時間を要しない。

  1. CPUからRAMのアドレス入力へjという値が送られる
  2. RAMは対象のメモリレジスタ(アドレスはj)を選ぶ
  3. RAM[j]のデータをCPUへ送る

CPUが異なればレジスタの数やレジスタの種類は異なる。

データレジスタ

このレジスタは簡易的なメモリのような役割で使われる。 例えば、(a - b)・cという値を計算する場合、はじめの(a - b)の計算結果を一時的に覚えておく必要があるため、これを格納する。

アドレスレジスタ

データを読み書きするために、CPUは常にメモリにアクセスする必要がある。 メモリアクセスの伴う命令はすべて、メモリのどのワードにアクセスするかというアドレスを指定しなければならない。

そのアドレスは現在の命令に含まれるかもしれない。または一つ前の命令の実行結果に依存して決定されるかもしれない。 後者の場合、アドレスの値は専用のレジスタ、つまりアドレスレジスタに格納される。

プログラムカウンタ

プログラムを実行する時、命令メモリから次にフェッチすべき命令のアドレスをCPUは追う必要がある。 そのアドレスはプログラムカウンタと呼ばれる特別なレジスタに保持される。 現在の命令を実行する過程で、CPUはプログラムカウンタを更新する。

入出力

コンピュータの外にある環境とインタラクティブにやりとりするために、I/Oデバイス(入出力装置)を用いる。 これにはスクリーンやキーボード、プリンタなどが含まれる。

全てのデバイスがコンピュータにとってまったく同じに見えるような、メモリマップドI/Oという仕掛けがある。 このアイデアは、デバイスのための領域をメモリに割り当てることである。 そうすることで、I/OデバイスをCPUにとって通常のメモリ領域のように見せかけることができる。

例えばマウスを動かしたりキーボードを押したりすると、それに対応するメモリマップに値が書き込まれる。 これと同様に、出力装置を操作したい場合は、対応するメモリマップに値を書き込めばよい。

メモリマップドI/Oによって、CPUやプラットフォームの設計と、デバイスの設計を完全に独立して行うことができる。

6章 アセンブラ

本章では、アセンブリ言語で書かれたプログラムをバイナリで書かれたプログラムへ変換するアセンブラを実装する。

シンボル

メモリアドレスを参照するには、実際のメモリアドレスの数字を用いる。 アセンブリでシンボルを仕様するケースは一般的に2つある。

  • 変数
  • ラベル(LOOPで用いられる)

例えばweightという変数を用いたアセンブリ言語がある場合、そのweightが参照するアドレスを明確にバイナリで書かなければならない。 そこで、ユーザーの定義した変数名やラベルを実際のメモリアドレスへ対応付ける処理を、シンボルテーブルによって解決する。

シンボルテーブル解決

シンボルテーブルを作成するには、ソースコード中でxxxという新しいシンボルに遭遇するたびに、(xxx, n)という行を追加していく。nは対象とするシンボルのメモリアドレスである。 シンボルテーブルの構築が完了すれば、シンボルテーブルを用いてシンボルの含まないコードへと変換する。

シンボルを含むプログラムのためのアセンブラ

アセンブリプログラムは、シンボルを定義する前であってもシンボルによるラベルを用いることができる(gotoコマンドの移動先のように)。

この問題を解決するために、「2パスのアセンブラ」というコードの最初から最後まで読む作業を2回繰り返すアセンブラを用いる。 最初のパスにおいて、アセンブラはシンボルテーブルだけを作成する。そして2回目のパスでは、各シンボルを対応するアドレスに置き換え、最終的なバイナリコードを生成する。

7章 バーチャルマシン#1: スタック操作

本章はコンパイラの構築へ向けた初めの一歩である。このコンパイラは一般的な高水準言語をコンパイルする。

高水準言語は初めに中間コードへ変換され、その中間コードは機械語へと変換される。 この2段階による変換処理のモデルは古くからあるアイデアに基づき、JavaやC#に取り入れられ、再び脚光を浴びた。

中間コードは実際のプラットフォーム上で実行される代わりに、バーチャルマシン(VM)上で実行されるように設計されている。 VM変換器は、VMコードをHackのアセンブリコードへと変換する。

バーチャルマシンの理論的枠組み

高水準言語を特定のコンピュータ上で実行するためには、プログラムをそのコンピュータの機械語に変換しなければならない。 コンパイラを実装するには、どのような高水準言語と機械語を対象とするのであれ、そのふたつの組み合わせに依存したプログラムを書かなければならない。

このような依存性を分離するためには、コンパイルという作業全体を2つのステージに分けることで解決できる。 最初のステージでは高水準言語を中間コードに変換し、2番目のステージは中間コードを機械語へと変換する。 このステージの分離はとても魅力的である。なぜなら、最初のステージは高水準言語の仕様だけに依存し、2番目のステージは機械語の仕様だけに依存するからである。

バーチャルマシン用の言語を明示的に用いることは実用面で利点がある。 ひとつ目の利点は、別のプラットフォームを対象としたコンパイラが必要な場合、バーチャルマシンの実装を置き換えるだけですむことである。 ふたつ目の利点は、複数の言語コンパイラによって、同じVMのバックエンドを利用することができるという点である。 またVMの実装を改善してパフォーマンスを向上させることができれば、それより上のレイヤにあるコンパイラは、すべてその恩恵を受けることができる。

スタックマシン

VM言語を構成する要素は、算術操作、メモリ操作、プログラムフロー、サブルーチン呼び出しなどがある。 VM言語を実装するにあたって、スタック(Stack)と呼ばれるデータ構造にデータを格納する方法が最もキレイな実装法である。

スタックマシンという計算モデルに置いて、算術命令はスタックの一番上からオペランドを取り出し、その結果をスタックの一番上に置く。 どのような算術命令や論理命令であっても、この単純なスタックによるモデルを用いて実装することができる。

基本となるスタック命令

スタックはいくつかの操作命令をサポートする。その中でもっとも重要な命令はpushとpopである。 push命令はスタックの一番上にデータを追加し、pop命令はスタックの一番上のデータを取り出す。スタックは「後入れ先出し」である。

スタックへのアクセスは、これまで見てきたメモリアクセスとはいくつかの点において異なる。 ひとつ目の相違点は、スタックでアクセス可能な場所は一番上の場所に限られるという点である。 ふたつ目は、スタックのデータを読み出すための命令は損失を伴うという点である。つまり、一番上のデータを取り出す唯一の方法は、スタックからそのデータを取り除かなければならない。 3つ目の相違点は、スタックへのデータ書き込みは、スタックの一番上にデータを追加することによって行われ、その下のデータには影響を与えないという点である。

スタックは配列とスタックポインタを用いて実装することができる。スタックポインタは配列の最後の要素の次の場所を指す。

スタック算術

スタックベースによる算術計算は簡単に行うことができる。 オペランドはスタックからポップされ、所望の命令がそのオペランドに対して実行される。そして結果がスタックへ戻される。 例えばd=(2-x)*(y+5)がどのように行われるか次に示す。

push 2
push x
sub
push y
push 5
add
mult
pop d

このように、どのような複雑な算術式であっても、スタック上での単純な一連の命令へと系統的に変換することができる。

8章 バーチャルマシン#2: プログラム制御

本章では、ネスト化されたサブルーチン呼び出しや引数の受け渡し、再帰処理やメモリ割り当てなどの複雑な仕事を、スタック処理によってこなせることを示す。

プログラムフロー

コンピュータプログラムは「goto xxx」コマンドによって任意の場所にある命令を実行することができる。 条件付き分岐を行う場合は「if-goto xxx」コマンドを用いて、与えられたブール条件がtrueの場合のみ移動する命令をマシンに行わせる。 スタックマシンのパラダイムにおけるもっとも自然なアプローチは、スタックの最上位にある値を条件とすることである。

サブルーチン呼び出し

プログラムの実行時にサブルーチン(ユーザーによって実装された命令、つまり関数など)が呼び出されると、低レイヤにおいては次の処理が裏で行われる。

  1. サブルーチンの呼び出し側から呼び出された側のサブルーチンへ引数を渡す。
  2. 呼び出された側のサブルーチンを実行する前に、サブルーチンの呼び出し側の状態を保存する。
  3. 呼び出された側のサブルーチンにおいて、ローカル変数のためのメモリ空間を確保する。
  4. 呼び出された側のサブルーチンへ実行を移す。
  5. 呼び出された側から呼び出し側へ値を返す。
  6. 利胆時に、呼び出された側のサブルーチンによって使われたメモリ空間を再利用できるようにする。
  7. 呼び出し側の状態を復帰させる。
  8. サブルーチンの次の場所に実行を移す。

このような一連の処理をハウスキーピング処理と呼び、これはコンパイラによって解決する。

power(累乗)のようなサブルーチンは、一時記憶に置かれるローカル変数を用いるのが普通である。このローカル変数は、サブルーチンを開始してからリターンするまでの間、メモリ中に保持されたままでなければならない。 このことは、サブルーチンがネスト化されることを考えると複雑な問題になるが、後入れ先出しの処理モデルを用いれば簡単に実装することができる。

returnコマンドでサブルーチンの処理から戻る命令は少しトリッキーである。というのは、returnコマンドの後に戻り先のアドレスは指定されていないからである。 returnコマンドに遭遇したときの正しい動作は、呼び出したコマンドの次のコマンドの場所(リターンアドレス)へ移動することである。

まずは呼び出し側がリターンアドレスをプッシュし、そのサブルーチンのコードを実行する。そしてその後でreturnコマンドに出くわしたときに、スタックからリターンアドレスをポップし、その場所へgotoコマンドを実行する。

9章 高水準言語

ここまで本書で学んだハードウェアとソフトウェアは、全て低水準(低レイヤ)であった。低水準とは人が直接読み書きすることを想定していないということである。

本章ではJackという独自の高水準言語についての説明を行う。 Jackはあまりおもしろみのない単純な言語であるが、簡単に習得することができ、そしてコンパイル作業をシンプルにすることができるからである。

(この章は言語の説明が主であるため省略)

10章 コンパイラ#1: 構文解析

本章ではJack言語のコンパイラを作る。コンパイルのプロセスは概念的にふたつの作業に基づいている。 ひとつ目の作業は、ソースプログラムの構文を理解し、そこからプログラムの意味を明らかにすることである。 これは一般的に構文解析と呼ばれ、本章のテーマである。

構文解析はさらにふたつに分けられる。それはトークナイザ(tokenizer)とパーサ(parser)である。 トークナイザは、ソースコードに対して意味を持つコードの最小単位である「トークン字句」に変換する。 パーサは一連のトークンを言語の構文ルールに適合させ、その構文構造を明らかにする。

字句解析

構文解析における最初の一歩は、文字のグループをトークンとしてまとめることである。 この作業は通常、字句解析やスキャニング、トークン化などと呼ばれる。 C言語を例にすると以下のように解析する。

while (count <= 100) {
    count++:
    // ...
}
while
(
count
<=
100
)
{
count
++
;
}

文法

一旦プログラムをトークンへと字句解析すれば、トークンを形式的な構造へとパースするという難しい作業が待っている。

ほとんどの全てのプログラム言語は、文脈自由文法として知られる定式化によって定義することができる。 文脈自由文法は、ある言語の構文要素がより単純な要素からどのように構成されるか、ということを指定したルールの集合である。 例えばJavaの文法では、100, count, <=という3つの最小単位であるトークンから、count <= 100という式を構成することができる。

文法はふたつの視点から見ることができる。 宣言を行う視点から見ると、文法はトークン(終端要素、ターミナルとも呼ばれる)をより高水準な構文要素(非終端要素とも呼ばれる)へ組み合わせる方法を指定する。 分析を行う視点から見ると、文法はその逆のことを行う、つまり与えられた入力(トークンの集合)を、非終端要素へ、そしてより低水準な非終端要素へ、そしてもうそれ以上分解できない終端要素へとパースを行う。

構文解析

文法が入力テキストを正しいものとして受理するか確認する作業は構文解析(パース、parsing)と呼ばれる。 文法のルールは階層的な構造であるため、パーサによって生成される出力は木の形をしたデータ構造(構文木や導出木と呼ばれる)になる。

再帰下降構文解析

構文木を構築するためのアルゴリズムにはさまざまなものがある。 トップダウン的なアプローチによる再帰下降構文解析と呼ばれる方法は、言語の文法によって規定されるネスト化された構文を使って、トークンの列に対して再帰的に構文解析を行う。

LL(1)文法

再帰下降アルゴリズムはシンプルであるが、非終端記号をパースする際に複数の可能性が存在することがある。 非終端要素の種類を決めるにあたり、いくつかの選択肢があった場合、最初のトークンだけからトークンの種類を決定することができる性質をLL(1)と呼ぶ。 最初のトークンだけから要素の種類を決定できない場合、先読みして解析する必要がある。

11章#2: コード生成

JavaやC#と同様に、Jackコンパイラはバックエンドとフロントエンドのふたつの要素から構成される。 バックエンドの正体はバーチャルマシンであり、7章と8章で開発した。 フロントエンドのモジュールは、構文解析器とコード生成器から構成されており、高水準言語とVM言語の間のギャップを埋め合わせるように設計されている。 本章ではコード生成器の開発を行う。

データ変換

プログラムは様々な型(type)を扱う。これには整数やブーリアン、配列やオブジェクトなどの型がある。 また変数にはライフサイクルとスコープ(ローカル変数かグローバル変数かなど)といったものがある。 これらの管理はシンボルテーブルによって行う。

シンボルテーブル

ほとんどのコンパイラは変数の型などをシンボルテーブルによって管理する。 コンパイラは識別子に出くわすたびにテーブルに識別子を追加し、他の場所で識別子に出くわすたびにシンボルテーブルから探し出す。

変数操作

ソースプログラムで宣言される様々な型の変数を、対象とするプラットフォーム上でどのように対応づけるかという問題がある。 変数の型が異なればメモリサイズも異なり、変数の属性が異なればそのライフサイクルも異なる。 例えばスタティック変数はひとつだけ存在し、プログラムの実行中はずっと存在するようにしなければならない。

しかしこのような困難な作業は、すでに7章と8章で構築したバーチャルマシンで扱っているため、このバックエンドで操作する必要はない。

配列操作

ほとんどの場合において配列は連続したメモリ領域に格納される。配列名は通常、ポインタとして扱われる。 ポインタである配列名は、その配列が格納されたRAMのベースアドレスを指す。

オブジェクト操作

クラスのオブジェクトはデータ(プロパティ)やメソッドなどがカプセル化されている。これらのプロパティとメソッドは別物として扱われる。 データに関しては配列と似ており、連続したメモリ領域に格納される。 メソッドはインスタンスのプロパティなどと違ってひとつだけしか存在しない。すべてのオブジェクトは同じメソッドを参照して実行している。

コマンド変換

ここでは高水準のコマンドがどのように変換されるのかという説明を行う。

式の評価

x + g (2 , y, -z) * 5のような高水準言語の式を評価するためにどのようなコードを生成するかは、池沼とするコード(変換先のコード)に依存している。 スタックベースのプラットフォームの場合は、構文木を後置表記法(逆ポーランド表記法としても知られる)で出力するだけでよい。

例えばf (x, y)のようなコードは以下のように変換される。

push x
push y
call f

フロー制御

高水準言語にはifやwhileといったフロー制御を行う仕組みが備わっている。しかし低水準言語には条件付きgotoや無条件gotoのふたつだけ備えられているのが普通である。 そのためそのふたつのプリミティブな命令だけを使って操作を表現しなければならない。 以下に変換例を示す。

if (cond)
    s1
else
    s2
...
    ~(cond)を計算するVMコード
    if-goto L1
    s1を計算するVMコード
    goto L2
label L1
    s2を計算するVMコード
label L2

もしネストされたフロー制御がある場合は、こういった変換を再帰的に行う必要がある。

12章 オペレーティングシステム

これまでの章でHackと呼ばれるコンピュータのハードウェアに関するアーキテクチャや、その上で動作するソフトウェアについて説明してきた。 コンピュータの主要なインターフェイスについて残すところはあとひとつ、オペレーティングシステム(OS)である。

OSはハードウェアとソフトウェアのギャップを埋めるために設計されており、ユーザーにとってコンピュータを扱いやすいように設計されている。

例えば「Hello World」のようなテキストをコンピュータのスクリーンに表示させるためにはピクセルを特定の場所に描画しなければならない。これを行うにはハードウェアの仕様を調べ、RAMの守りマップに対して適切な場所にビットを書き込むコードを書く必要がある。 そういったことを担うのがOSである。

数学操作

コンピュータシステムは加算や乗算などの数学操作をサポートしなければならない。 通常、加算はハードウェアつまりALUのレベルで行われる。 乗算と除算についてはハードウェア化ソフトウェアのどちらかで行われる。これはコストとパフォーマンスに依存して決まる。

効率優先

数学アルゴリズムはnビットのバイナリ数に対して処理を行う。 一般的なアーキテクチャにおいて、nは16,32,64のいずれかに該当する。

原則としてnのサイズに処理時間が比例するアルゴリズムが求められる。 もしnの指数関数であるfor i = 1...y { result = result + x}のようなアルゴリズムを用いて繰り返し加算しようと思えば、大きな値であれば膨大な処理時間を要する。 そのため、乗数の値(0から2^nの範囲)ではなくnに比例した処理時間となるアルゴリズムが必要である。

数字の文字列表示

コンピュータにおいて数を表現するため内部的にバイナリコードが用いられる。 しかし人にとっては数は10進数表記の方が扱いやすい。そのため人が数字を読むまたは入力する場合は変換する必要がある。

ASCIIコードでは0は48、1は49、2は50、30は51のようになっている。つまりxという数のASCIIコードを求めるにはxに48を加算するだけでよい。

メモリ管理

動的メモリ割り当て

メモリ管理はコンパイラ、OS、バーチャルマシン実装によって見えない場所で行われる。ここではOSの役割について説明する。

Javaプログラムでは配列やオブジェクトを新たに生成すると、そのメモリブロックが割り当てられる。そして必要なくなればRAM領域は再利用される。このように自動的にオブジェクトの破棄を行う機能をガーベッジコレクションと呼ぶ。動的に割り当てられるRAMセグメントはヒープ(Heap)と呼ばれる。ヒープの管理を行う責任があるのがOSである。

断片化

動的メモリ割り当てをしばらく実行させると、断片化(フラグメンテーション)が問題になる。断片化とは、利用可能なメモリ領域が細切れになることである。

そのためデフラグというフラグメンテーションを解消する操作を行い、物理的に連続したメモリ領域へと断片化された領域を結合させる。このデフラグはオブジェクトが破棄されるタイミングで行うことができる。

可変長な配列と文字列

ここではs1="New York"のような高水準な命令について考える。このような可変長な文字列はどのように実装することができるだろうか。モダンな言語においては文字列を表現するためにStringクラスを使うことが一般的である。

文字列オブジェクトは配列を用いて実現することができる。通常、文字列が生成されると、ある最大の長さを収納可能な配列が割り当てられる。その最大長のメモリサイズは文字列オブジェクトのライフサイクルを通して保たれていなければならない。

入出力管理

コンピュータにはキーボードやスクリーン、マウスなどの様々な入出力装置とつながれている。このような入出力装置はそれぞれに特有の構造をしているため、それぞれの装置にアクセスするための便利な関数群、つまりデバイスドライバを作る必要がある。

13章 さらに先へ

これまで実装してきたソフトウェアは修正・拡張して別の設計を取り入れることができる。 たとえばアセンブリ言語やJack言語を好きなように拡張できるし、コンパイラを好きなように書き直すこともできる。

さあ、あなたならどうする?


{ "name": "hareku", "job": "Software Engineer" }