自作言語作ってるます part2 - 借り初めのひみつきち

というわけで、前回の日記で言っていた本当に作りたかったものがある程度形になったので公開します。

ToyScript

独自のスクリプト言語作りました。

名前は「ToyScript」要するにゴミです。

github.com

フロントエンドもバックエンドもすべて WebAssembly 前提で設計しているので簡単にブラウザ上で Playground を動かすことができます。

→Playground はコチラ

基本的な文法として TypeScript のサブセットを採用しています。

既存の文法を踏襲した方が学習難易度やエディターの支援で有利
C言語系の文法よりパースが楽でAST化しやすそう
略語が同じ TS になる

等の理由により採用しました。

語彙を借用しているだけであくまで別の言語なので、型チェックが TypeScript より厳しかったり動的な型がないなどの意図的な非互換部分もあり、将来的な完全互換性も目指していません。

また、スクリプトと名前がついていますが、一旦中間言語にコンパイルしたあと WebAssembly で出力して自作のランタイムで実行される完全に静的な言語です。

このような言語を作った主な理由として、 WebAssembly 上で動作する軽量な言語が欲しかったなどの理由があります。 *1

実はフロントエンドは１年前から作っていてすでにある程度動いてましたが、バックエンドが色々必要になってめんどくさくなって中断していました。。。

詳細

処理フェーズとしては大きく分けると、トークン化、AST (抽象構文木) 構築、型システム（名前解決、型チェック、型推論など）、IR (中間言語) 生成、簡易最適化、 WASM 出力という構成になっていて、デバッグ用に AST や IR を中間出力できるようになっています。

通常トークン化はソースコードの断片を文字の種類などでグループに分けて属性を付与していきますが、その過程でソースコードの断片文字列のコピーが大量に発生します。ひとつひとつのトークンはほとんどが数バイトの小さい文字列ですが、量が多いので大量のメモリ確保と解放の処理が発生します。 Rust ならではの工夫として、トークン化処理の文字列のコピーを極力減らしています。

JavaScript 系言語は自由形式でありながら行の最後に「；」が必須ではないという特徴を持つため「式」を AST にする処理が複雑で、式の終端を検知する処理の調整はかなり大変でした。

中間言語は最終的に WebAssembly で出力する前提で WebAssembly っぽい雰囲気がありつつ、簡単な最適化するために SSA (Static Single Assignment) っぽい独特な雰囲気になっています。WebAssembly にはローカル変数という概念があって中間言語もローカル変数の存在を維持しているので厳密には SSA ではなく、ローカル変数に絡んだ処理は現状最適化できません。

主な最適化は以下のようになっています。

drop 命令に繋がっている削除可能な命令を削除します。(call 命令があった場合は drop ごと残す、local.tee の場合は local.set に置き換えるなど)
- 変数への代入・関数呼び出し、条件式として評価されない式は最終的に drop 命令で破棄されるため、これによってほとんどの無駄な計算は削除されます。
定数と定数同士の演算命令は基本的に定数命令に置き換えます。
一部の定数と変数の演算命令でよりコストの低い命令列に置き換え可能な場合、置き換えます。(0 との演算や2の累乗の乗除算など)
eqz 命令と比較命令がセットで存在する場合、 eqz を削除して条件を反転します。（eq ↔️ ne など）
eqz 命令と定数命令がセットで存在する場合、 0 の場合は定数 1、それ以外の場合は定数 0 に置き換えます。
br_if 命令の分岐条件が定数の場合、 0 の場合は分岐削除、それ以外の場合は br に置き換えます。
br, return, unreachable 命令以降の命令は次の end まで実行されないため、該当する命令があった場合削除します。
いずれかの分岐ターゲットにならないブロック命令 (block, loop, end) を削除します。
以上の最適化で nop に置き換わった命令を削除して切り詰めてレジスタ名を振りなおします。