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

この記事は N高等学校 (1) Advent Calendar 2020 の11日目です。

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

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

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

注意書き

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

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

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

作る目的

私が現在自作している「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. バイトコードを読み込む

// 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バイトの命令コードを取得して処理します。


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命令を書いておきます。

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コードをコンパイルすると

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
Twitter ... @Garnet3106

去年のアドカレ記事 ... 自作言語「Chestnut」の仕組みとミスったところ
※ ↑今は仕組みがいろいろ変わってます