独断と偏見で考えた自作スタックマシンの紹介

この記事は [N高等学校 (1) Advent Calendar 2020](https://qiita.com/advent-calendar/2020/n-highschool) の11日目です。

[前回の記事] [C++で競技プログラミングをWindows10でやりたい](https://qiita.com/YuuAyakawa/items/fcfea382d69f765d1fcb) ([@YuuAyakawa](https://qiita.com/YuuAyakawa))
[次回の記事] [ニコニコをダークモード化する拡張機能を作ったが、クソコードになったので改良修正した話。](https://qiita.com/nekozuki_dev/items/c2e3793db48f43a40096) ([@nekozuki_dev](https://qiita.com/nekozuki_dev))

どうも、N高4期生のがーねっとです。

今回は自作のバイトコードと、それを動かすスタックマシンの仕組みについて紹介します。
中検が終わって最近プログラミング言語の制作を再開したのでこのテーマにしました。
( 内容が[去年のアドカレ](https://qiita.com/advent-calendar/2019/n-highschool)と少し被ってる... )

## 注意書き

1μmの知識と独断&偏見で作っているのでおかしいところがあるかもしれません。
今後もしかすると仕様を変えるかもしれません。

~~細かいことは気にしない！~~

コメントでご感想 / ご指摘などいただけるとうれしいですが、お手柔らかにお願いします (涙目

## 作る目的

私が現在自作している「[Chestnut](https://github.com/Garnet3106/chestnut/)」というプログラミング言語を動かすためです。
もちろんコンパイラも同時に制作中です。

この仮想マシンはJavaでいうとJVMの部分になります。
コンパイルによって生成したバイトコードを仮想マシンで実行します。

## 開発環境

- C++17
- GCC 4.2.1
- VSCode

## コマンド

未リリースなので紹介する意味は特にありません()

```
ソースコードをコンパイル (コンパイラのコマンド)
$ chesc -i hello.ches -o hello.chesc
```

```
バイトコードを実行
$ ches -i hello.chesc
```

## 命令一覧

一部の命令を紹介します。

命令コードは1バイトなので理論上は256個まで作れることになります。
( さすがにそんなには作りませんが() )

|命令名|処理内容|その他|
|:-:|:-:|:-:|
|add|値の加算||
|sub|値の減算||
|mul|値の乗算||
|div|値の除算||
|and|論理積の演算||
|or|論理和の演算||
|equal|一致の判断||
|greater|大小の比較||
|rev|ビット反転||
|join|値の結合||
|jump|処理部分の移動||
|jumpif|処理部分の移動|演算スタックのトップ値が1の場合のみジャンプ|
|push|作業スタックにプッシュ||
|pop|作業スタックをポップ||
|load|演算スタックにプッシュ||
|ret|ブロックを抜ける||
|syscall|システム命令を実行||

## スタックの種類

演算では2種類のスタックを使用します。

|名前|英語名 (略称)|役割|プッシュ / ポップ命令|
|:-:|:-:|:-:|:-:|
|作業スタック|Working Stack (WS)|演算スタックに使うデータを保持|push / pop|
|演算スタック|Operation Stack (OS?)|命令に渡すデータを保持|load / -|

スタックの種類によって値操作の呼び方が変わります。
( ロード = 演算スタックへのプッシュ )

### コード例

```
push    32      16      ; 16をプッシュ
push    32      8       ; 8をプッシュ
load    2               ; 2つの値をロード

mul             ; ロードされた値を乗算 (16 * 8)

load    1       ; 演算結果をロード (関数の戻り値)

pop     ; 演算結果をポップ
pop     ; 8をポップ
pop     ; 16をポップ

ret     ; ブロックから抜ける
```

mul命令では、ロードされた値を演算し、その結果を作業スタックにプッシュしています。
( 演算スタックは演算後にクリアされるため、命令によってそれをクリアする必要はない )

## バイトコードの区切り

バイトコードはいくつかのパートで区切られています。

### ヘッダ部分

ヘッダ部分にはマジックナンバーやバージョン情報などのデータが記述されます。
この部分はファイルの先頭に位置していて、サイズは固定です。
( 今のところは128バイト; ヘッダ情報が大きくなれば増やす予定 )

先頭にはバージョンごとに決められたマジックナンバーが記述されます。
最初のリリースのマジックナンバーは `4F 52 49 4E 43 48 41 4E` にする予定です。
( この方法はあまりよくない気がするけど、まあ気にしない気にしない... )

### 命令部分

ヘッダ部分に続いて命令部分が位置します。
命令部分には文字通り、プログラムの命令が記述されます。
すべての命令の末尾には `0x01` が置かれます。

もちろんこの部分のサイズは固定ではありません。

[参考] [## オペコードとオペランド](##オペコードとオペコード)

### 識別子部分

ここにはクラス、関数、定数などの情報が記述されます。
識別子部分の開始位置はヘッダ情報から参照できます。

↓は記述される情報の例です。

|項目|記述される情報|
|:-:|:-:|
|名前空間|識別子, 名前, その他|
|クラス|識別子, 名前, その他|
|関数|識別子, 名前, 開始インデックス|
|定数|識別子, 名前, 値|

## オペコードとオペランド

オペコードは1バイトです。
オペランドの長さは命令や値によって変わります。

### バイトコード例

「32ビットの値 58971 をプッシュする」という命令を例にとると...

```
; アセンブリ的な表記
push 32 58971

; Hex表記
12 06 E6 5B
```

`0x12` ... push命令のコード
`0x06` ... 値のデータサイズ ( 0x06 = 32ビット = int型 )
`0xE6 0x5B` * ... 実際にプッシュする値 ( * 58971 )

## 処理手順

### 1. バイトコードを読み込む

```cpp
// this->bytesの初期化などは省略...
// typedef unsigned char Byte;

std::ifstream ifs(filePath);
Byte byte;

do {
    ifs.read((char*)&byte, sizeof(char));
    this->bytes[BYTE_LEN++] = byte;
} while(!ifs.eof());

if(BYTE_LEN > 0)
    this->bytes[--BYTE_LEN] = 0;

ifs.close();
```

↑はソースコードからいろいろ抜き取ったものです。
ついイン/デクリメントを多用してしまう...

### 2. 命令を実行する

読み込んだバイトコードから1バイトの命令コードを取得して処理します。

```cpp

void ches::Interpreter::runNextInst() {
    try {
        if(this->index < HEADER_LEN || this->index >= this->idAreaIndex) {
            /* エラー処理 */
            this->finalize();
        }

        Byte opcode = BYTE;
        Byte opcodeIndex = this->index;

        // opcode分をindexに追加する
        this->index++;

        switch(opcode) {
            case IT_InstDiv: {
                /* エラー処理 */
                this->finalize();
            } break;

            case IT_Add: {
                /* add命令の処理 */
            } break;

            case IT_Equal: {
                /* equal命令の処理 */
            } break;

            case IT_Jump: {
                /* jump命令の処理 */
            } break;

            /* 以降の命令は省略 */

            default: {
                // 無効な命令なのでエラー
                /* エラー処理 */
                this->finalize();
            } break;
        }
    } catch(〜) {
        /* エラー処理 */
        this->finalize();
    }
}
```

↓命令の処理の例として、push命令を書いておきます。

```cpp
case IT_Push: {
    #define BYTE                        (this->bytes[this->index])
    #define BYTES_AT(indexPair)         (this->getBytes(indexPair))
    #define STACK_PUSH(size, value)     this->stack.push(size, value);

    Byte size = BYTE;
    this->index++;

    std::pair<int, int> index = GET_DIV_INDEX(this->index));
    STACK_PUSH(size, BYTES_AT(index);
} break;
```

`GET_DIV_INDEX(index)` は渡されたインデックスから `0x01` までの長さと開始位置を返します。
引数の `index` は参照渡しで、終了位置まで自動でインデックスが進んでくれます。

( マクロを使いすぎたりしてるので後で書き直します )

## コード例

このChestnutコードをコンパイルすると

```cpp
main(str[] args)
    str name = "Garnet"
    println("Hello, " ~ name ~ "!")
end
```

↓こうなります (命令部分のみ)

```
push    32      "Garnet"
push    32      "Hello, "

load    2
join

push    32      "!"

load    2
join

load    1
jump    

ret
```

.....時間があれば解読してみてください()

## 最後に / 今後すること

記事を読んでくださってありがとうございます。

現在はC++でスタックマシンを実装中です。
コンパイラも含めてある程度のものが動くようになればリリースする予定です。
( この記事を書いた人は計画性を備えてないのでいつになるかは未定 )

リリースするまでにはChestnutの公式Twitterも作れたらいいなと。

下にChestnut関連のリンクを貼ったのでもしご興味があればどうぞ。
よろしければコメントなどいただけるとうれしいです。

それでは。

## リンク

GitHub ... [Garnet3106/chestnut](https://github.com/Garnet3106/chestnut/)
Twitter ... [@Garnet3106](https://twitter.com/Garnet3106)

去年のアドカレ記事 ... [自作言語「Chestnut」の仕組みとミスったところ](https://qiita.com/Garnet3106/items/ceed33d99c255cc70588)
※ ↑今は仕組みがいろいろ変わってます