コンピューター理論、チョットデキルようになりたい

コンピュータサイエンスの学び直しです

学び直し35日目：7章　バーチャルマシン#1：背景

記録

コンパイラ構築に向けた始めの一歩として、バーチャルマシンを学ぶ。高水準プログラムを機械語へ一気に変換するのではなく、その間に中間コードを設けるらしい。高水準プログラムから中間コードへ、中間コードから機械語へと変換していく。

バーチャルマシン（Virtural Machine, VM）

概要

中間コードは実際のプラットフォーム上で実行されない。代わりに、バーチャルマシン上で実行されるように設計されている。バーチャルマシンは実際には存在しない抽象化された（中間コードを入れたらそれに応じて何かしら返してくれる）コンピュータとのこと。

中間にワンクッション挟むことで、高水準言語と機械語の組み合わせによる依存性を分離できる。これにより高水準言語をいろんなところに使いまわせるようになる。つまり、「移植性」がよくなる。

「高水準言語→バーチャルマシン」と「バーチャルマシン→機械語」のふたつのステージを独立して考えることができる。

VM 言語

バーチャルマシンは「言語」を持っている。これが VM 言語。「算術」「メモリアクセス」「プログラムフロー」「サブルーチン呼び出し」のためのコマンドが含まれる。VM 言語を機械語に変換する、VM変換器というものを作ることになる。

VM 実装を備えるコンピュータやデジタル機器であれば、他の機器向けに作ったソフトウェア資産を流用できるとのこと。ひとつの共通ルールに従っていると、いろんなところで使いまわしが効くってことかな。

スタックマシン

スタックいうデータ構造を用いた算術モデルをスタックマシンという。スタックの説明は端折ります。かの有名な Last In First Out のデータ構造のことです。

VM言語で「算術」「メモリアクセス」「プログラムフロー」「サブルーチン呼び出し」を行うために用いられている。競プロでやってたことって、このあたりでとても活きてきそう。

今日の筋トレ

リングフィットアドベンチャー

学び直し34日目：6章　アセンブラ：プロジェクトまとめ（6章終了）

記録

main プログラムを書いたのだけど、モジュール読み込みでこけてしまいうまく動かない…Python の調査になるのでいったん飛ばしちゃおう。path がなんかアカンのかな。

github.com

6章まとめ

今日の筋トレ

リングフィットアドベンチャー

学び直し33日目：6章　アセンブラ：プロジェクト-Symbol Tableモジュール

記録

引き続き Hack コンピュータのアセンブラを Python で実装中。今日は Symbol と実アドレスを紐づけるための Symbol Table モジュールを実装（写経）。

github.com

Symbol Table モジュール

Symbol を key, Address を value とするように、辞書型を操作できればOK。やらないかんことは明確。
初期化時に定義済みシンボルを格納した辞書を作り、ラベルや変数シンボルを追加するときは 16 番目のアドレスから使っていくようにしたらよい。ただし、定義済みシンボルを上書きしないように気を付ける必要がありそう。

次やること

main プログラムを書いてデバッグする。

今日の筋トレ

今日は休筋日

学び直し32日目：6章　アセンブラ：プロジェクト-Codeモジュール

記録

引き続き Hack コンピュータのアセンブラを Python で実装中。今日はアセンブリ言語のニーモニックをバイナリコードへ変換するモジュールを書いた。相変わらず以下を参考にさせていただいている。

github.com

Code モジュール

C 命令の仕様に基づいて、dest, comp, jump のニーモニック を key、バイナリコードを value とする辞書を用意して、適宜呼び出せばよい。C 命令さえ理解できていればやることは明確。

次やること

Symbol Table モジュールを書く。

今日の筋トレ

リングフィットアドベンチャーをがんばる予定。

学び直し31日目：6章　アセンブラ：プロジェクト-Parserモジュール

記録

Hack コンピュータのアセンブラを Python で実装中。アセンブラって結局のところ、アセンブリ言語をある規則のもと 0/1 に書き換えるテキスト変換プログラムなのでは。。

自力でがんばろうと思ったけど、Python の勉強になってしまいそうなので、とりあえず以下のコードを写経させていただきつつ進めている。書かれている内容自体は何となく理解できたと思う（正規表現の詳細はよくわかんね）。
github.com

Parser モジュール

構文解析のためのモジュール。解析できる状態まで、コードを分解するのが役目っぽい。

必要な機能（メソッド）は下記。Python の正規表現をうまく利用すると、スムーズに実装できるみたい（慣れが必要…）。

  • .asm を読み込む
  • 読み込んだファイルの各行を取得する
  • 取得した各行が A, C, シンボルラベル のどのコマンドか識別する
  • A 命令かシンボルラベルの場合、そのシンボルを抽出する。
  • C 命令の場合、dest, comp, jump をそれぞれ抽出する。 これらが Code モジュールに渡されるのだと思う。

次やること

Code モジュールの実装。こいつでニーモニック（つまりアセンブリ言語）をバイナリに変換する。

今日の筋トレ

今日は休筋日

学び直し30日目：6章　アセンブラ：実装、展望

記録

アセンブラをどうやって実装するか見た。4つのモジュールから構成されるようにすればよさげ。また、アセンブラはどの言語を用いても作れるみたいなので、割となじみのある Python で書こうと思う。
困ったらこの方のコードを参考にさせてもらおう。
github.com

仕様

アセンブラを構成するモジュール

以下3つのモジュールを駆使して、メインプログラムを書くことになりそう。

  1. Parser モジュール
    • 構文解析する。「A 命令か、C 命令か、疑似コマンドかの判別」、「シンボルはどれか」、「dest, comp, jump はどれか」。
    • 構文解析って何ぞやって感じだったけど、ググったら正に"構文解析"としか呼びようがないんですね。
  2. Code モジュール
  3. SymbolTable モジュール
    • Symbol と実際のアドレスを紐づけるモジュール。Python なら辞書型使えばよさそう。
シンボルを含むアセンブラ

アセンブリプログラムはシンボル定義前でもそのシンボルを使える。そのため、アセンブラはアセンブリプログラムを最初から最後まで読む作業を2回続けて繰り返しているらしい。

  • 一回目：シンボルテーブル作成。バイナリコードは生成しない。
  • 二回目：シンボルテーブルを利用して、最終的なバイナリコードを生成する。

展望

アセンブラ単体で使用されることはほぼないらしい。人ではなくコンパイラによってアセンブリプログラムが書かれる（生成される）ことが多いのだそう。コンパイラも直接機械語を生成した方が都合がいいので、多くの高水準言語のコンパイラは、高水準プログラム言語のコード中にアセンブリ言語によるコードを埋め込むことを許可しているとのこと（C言語とか）。

今日の筋トレ

今日は休筋日

学び直し29日目：6章　アセンブラ：Hackアセンブラからバイナリへの変換仕様

記録

アセンブリコマンドとバイナリコードの対応表を基本的には良いすればよいわけだが、その対応表を作るにあたり規約を定められている。

ファイルの種類

  • バイナリコードのファイル拡張子が .hack、アセンブリ言語のファイル拡張子が .asm。
    • バイナリコードの n 行目は、命令メモリの n 番目のアドレスに格納される。
    • アセンブリ言語の各行は、命令かシンボル宣言のどちらか。
      • 命令は A 命令 or C 命令の二種類。さんざんやってきたので割愛。
      • ラベルシンボルは疑似コマンドと呼ばれる。次のコマンドが格納されるアドレスと結び付けられる。疑似コマンドは、機械語のコードに生成されない（次の場所に飛ばすだけっぽい）。
    • アセンブラのニーモニックはすべて大文字。ラベルや変数は大文字と小文字を区別して使用可能。慣例としてはラベルは大文字で変数は小文字。

シンボル

定義済みのシンボル、ラベルシンボル、変数シンボルの3種類ある。

  • 定義済みシンボル：レジスタや SCREEN, KBD などすでに用途が決まってそうなもの。
  • ラベルシンボル：(Xxx) で使われているもの。(LOOP) とか。これを使って、疑似コマンドの次のコマンド位置を参照する。
  • 変数シンボル：定義済みでもラベルでもなくいもの。最初に変数に遭遇した順に、メモリが順に割り当てられる。開始アドレスは 0x0010。

今日の筋トレ

リングフィットアドベンチャーがんばった。もう一周やるか…