自作言語「Chestnut」の仕組みとミスったところ

19069 ワード
N高等学校 自作言語 C++ C++ テキストリンク

この記事は N高等学校 Advent Calendar 2019 の19日目です。

N高等学校４期生のがーねっとです。
今回の記事では、私が自作しているプログラミング言語の仕組みについて紹介したいと思います。

前日の記事は @Plum_Very さんの 【Unity臭】Unity特有の安っぽさを消臭してマシな画面を作る です。

注意点

Qiita初投稿です。自作言語つよつよマンでもないです。
僅かな知識と独断のみで制作を進めているので、間違いなどがあるかもしれません。
その際はコメントにてご指摘いただけると助かります。

いきなりズバッと言語仕様を変えることがあるかも...

言語概要

現時点での名前は「Chestnut」です。
構文的にはJavaとPythonをあわせた感じだと思います。

主にこれらを目指して制作しています。
・ どこでも動く
・ 書きやすい
・ 読みやすい
・ わかりやすい

今回は仮想マシンを使った実装について紹介したいと思います。
いつか他言語へのトランスコンパイラも作って紹介したい...！

実行してみよう

まずは $ ches cmp -i <filepath> でコンパイルします。
プログラムの拡張子は .ches です。

コンソール
$ ches cmp -i Hello.ches
Hello.ches
main(str[] args)
  println("Hello, world!")

コンパイルすると、中間言語に変換されたコードが別ファイルに書き込まれます。
この場合だと Hello.chesc に自動で中間コードが書き込まれます。

chescファイルは ches run -i <filepath> で実行(インタプリト)します。

コンソール
$ ches run -i Hello.chesc
Hello, world!

...これらができるようになる予定です。。

プログラムを動かす流れ

プログラムを動かすまでの大まかな流れを紹介します。

全体を簡単に説明すると、コンパイラが中間コードを生成してそれをインタプリタが実行します。

コンパイル

Chestnutプログラムを中間コードに変換します。

段階 説明
コマンド実行 $ ches cmp -i <filepath>
↓
字句解析 トークンに分割
↓
構文解析 抽象構文木(AST)に変換
↓
命令変換 ASTを中間コードの命令に変換
↓
バイナリ変換 命令をバイナリに変換

インタプリト

中間コードを解析して命令を実行します。

段階 説明
コマンド実行 $ ches run -i <filepath>
↓
命令変換 バイナリを中間言語の命令に変換
↓
命令実行 中間言語の命令を実行

仮想マシン

独自の仮想マシンでChestnutを動かすことにしました。
VM知識はほとんどないので、ILやJVMを参考に「こんな感じかな？」と設計しています。

以下では、自作VMの仕組みや中間コードの構文を紹介していきます。
ここでは便宜上、中間コードをテキスト形式で記述します。

マジックナンバー

chescファイルのマジックナンバーは「compiled_ches」です。
マジックナンバーはファイルの先頭に必ず記されます。

グループ定義

VMにおいては、関数はグループ(命令の集まり)として管理されます。
グループは、それぞれ「グループ番号(10バイト乱数)」と「グループ名(関数名と同様)」をもちます。
グループを定義する構文は group <グループ番号> <グループ名> です。

以下の中間コードの2~3行目については、後ほど説明します。

DefGroup.ches
main(str[] args)
DefGroup
0| compiled_ches
1| group e3a610acd5c1655ad7ba DefGroup.main
2| lspush null
3| exit

リスト／スタック

データを保持するには、LLとLSを使います。
LLに値をプッシュする構文は llpush <値> です。
LSに値をプッシュする構文は lspush <値> です。

LS.ches
main(str[] args)
  int hoge = 123
  str huga = "456"
LS

0| compiled_ches
1| group e3a610acd5c1655ad7ba LS.main
2| lspush 123
3| lspush "456"
4| lspush null
5| exit

グループ呼び出し

グループを呼び出す流れを説明します。

  1. 呼び出し先に渡す引数をlspushします。

  2. グループを呼び出します。
    構文は call <グループ番号> です。

  3. 戻り値をlspushします。
    　※ 戻り値の型がvoidの場合はnullをプッシュします。

  4. 処理が完了したらグループを終了します。
    構文は exit です。

わかりにくいと思うので、リストに表すとこんな流れです。

場所 処理
呼び出し元 引数をプッシュ
↓
グループを呼び出す
↓
呼び出し先 グループの処理
↓
戻り値をプッシュ
↓
グループを終了
呼び出し元 ↓
処理を続ける

mainグループの最後にある「lspush null / exit」は、引数なし(null)をプッシュしてグループを終了するという命令なのです。

CallGroup.ches
main(str[] args)
  getName()

getName()
  return "John"
CallGroup
0| compiled_ches
1| group e3a610acd5c1655ad7ba CallGroup.main
2| call b8fb5a506d94846cff48
3| lspush null
4| exit
5| group b8fb5a506d94846cff48 CallGroup.getName
6| lspush "John"
7| exit

四則演算

四則演算の命令は以下のとおりです。

  • nadd ... 加算
  • nsub ... 減算
  • smul ... 乗算
  • sdiv ... 除算

これらの命令は、LSの末尾２つの要素を演算して、その結果をLSにプッシュします。

OpeExp.ches
main(str[] args)
  int hoge = 10 + 2 * 3.4

0| compiled_ches
1| group e3a610acd5c1655ad7ba OpeExp.main
2| lspush 2
3| lspush 3.4
4| nmul
5| lspush 10
6| nadd
7| lspush null
8| exit

「2をプッシュ → 3.4をプッシュ → nmulで乗算」のような感じです。
数式を逆ポーランド記法で解釈しているため、演算の順番が入れ替わっています。

リストとスタック

データの保持にはリストとスタックを使います。

  • スレッドリスト (TL) は、各スレッドの情報を保持します。

  • グループリスト (GL) は、各グループ呼び出しごとの情報を保持します。

  • ローカルリスト (LL) は、引数などの情報を保持します。

  • ローカルスタック (LS) は、演算結果などの一時的な情報を保持します。

これらを図に表すとこのような感じになります。

ちょっとややこしい。

命令一覧

参考程度にどうぞ。

命令 引数 内容
call <グループ番号> グループを実行する
group <グループ番号> <グループ名> グループを定義する
llpush <値> LLに値をプッシュする
lspush <値> LSに値をプッシュする
nadd LSの末尾２つの数字を加算する
nub LSの末尾２つの数字を減算する
nmul LSの末尾２つの数字を乗算する
ndiv LSの末尾２つの数字を除算する
exit グループを終了する

自作VMの紹介はそろそろ終わります。

ミスったところ

小さいミスならたくさんあるのですが、中でもまたひっかかりそうなミスを選んでみました。

ファイル読み込み

std::ifstreamを使って読み込んだ文字をstd::vectorに追加していくプログラムを書きました。

// かなり省略

std::ifstream ifs(path);

std::vector<unsigned char> source;
unsigned char uc;

while(!ifs.eof()) {
    ifs.read((char*)&uc, sizeof(unsigned char));
    source.push_back(uc);
}

ifs.close();

しかし、sourceの要素数がおかしいことに気づく...
sourceの末尾に「0x00」が余計についてるっぽい。

std::ifstream ifs(path);

std::vector<unsigned char> source;
unsigned char uc;

do {
    ifs.read((char*)&uc, sizeof(unsigned char));
    source.push_back(uc);
} while(!ifs.eof());

ifs.close();

原因は普通のwhile文でEOFを判断していたこと。
こういうときはdo-whileを使うらしいです。

無駄な最適化

「4000行のChestnutコードをコンパイルする」というテストをしていました。
予想通り、コンパイルするにはかなり時間がかかります。(7000msほど)

そこで、-Ofastオプションで最適化をすると1500msに短縮されました。
なんかすごいね。(小並感)

それ以来ずっと最適化してきたのですが、「数行のコードをコンパイルする」という最適化が不要なテストでもしていたので、コンパイル1回につき5秒という無駄な最適化の時間を過ごすことになりました。
最適化は適度に使いましょう。

最適化に5秒もかかるのってプログラムの書き方が悪いのかなあ...

filesystemが使えない

「ディレクトリ内のchesファイルをすべてコンパイルする」という機能をつけるため、ディレクトリ内のファイル一覧を取得する方法を調べていました。

ネットでfilesystemライブラリを知ったので早速使おうとしたところ...

example.cpp
#include <filesystem>
Console
fatal error: 'filesystem' file not found

Oof...

原因はGCCのバージョンが古すぎただけでした。(GCC4.2.1だった)
Homebrewで最新版(執筆時9.2.0)をinstallしてコンパイルしたら使えました。

(この程度で数日ずっと悩んでたとか言えない...)

std::mapを 「{{}}」 で初期化

普通の凡ミスです。
要素数０のすっからかんのmapを渡そうと、「{{}}」を引数においたところ...

example.cpp
int main(int argc, char *argv[]) {
    hoge({{}});
}

void hoge(std::map<std::string, std::string> map) {
    std::cout << map.size() << std::endl;    // 出力: 1
}

要素数が１になっていました。
上の例だと、hoge({}); が正しいです。

結論?

自作言語制作は楽しい！

あとがき

記事書きを放置してたら投稿日の朝３時まで記事を書く羽目になりました。
何事にも計画性は大事...

言語について書ききれなかったこともあるので、機会があればまた記事を書くかもしれません。
そのときは自作言語のトランスコンパイラの記事として書くかも...？

特に話すこともないのでそろそろ終わりです。
見ていただきありがとうございました。

GitHub

リポジトリはこちら
Garnet3106/chestnut

リリース → masterブランチ
デベロップ → developブランチ