ライブラリなしで自作言語：可変性をsetterの有無で表す言語 "Settlang"
わたすけです。普段は自作OS等の低レイヤからWebフロントエンドまで広く浅くやっています。いつもは自分で作ったサイトこと watasuke.net で記事を書いているのですが、Zennで「今年の最も大きなチャレンジ」に関する記事の投稿イベントがあると聞いたので、こっちに記事を書いてみようと思います。
僕にとって、今年における唯一 [1] のチャレンジは 「U-22 プログラミング・コンテスト (以下U22プロコン) 」への参加です。僕はRustでプログラミング言語を作って応募しました。U22プロコンに応募するのは3回目ですが、今回はじめて一次審査を通過することが出来ました。最終審査まで残ることは叶いませんでしたが……。
ということで、今回はその応募作品である 「可変性をsetterの有無で表す言語 "Settlang"」 について紹介させていただきます。
言語概要
Settlang (せとらんぐ) です。各変数に関数を結びつけると、その変数はmutable、つまり内容を変更できる変数となります。変数名.set(引数) でその関数が呼び出され、関数の戻り値が変数の新しい中身となります。
簡易的なサンプルを置いておきます：
#*
Settlang minimal example
(READMEから引っ張ってきてコメントを和訳したもの)
*#
fn accumulator(self: i64, e: i64) -> i64 {
# 足した値を返すだけ
ret self + e
}
fn randomize() -> i64 {
ret random(0, 100)
}
# `main` と命名された関数がエントリーポイント
fn main() -> i64 {
# これらは 'setter' 関数を持つので、可変
let sum: i64 | accumulator = 0
let rnd: i64 | randomize = 0
for i in 0..10 {
rnd.set() # rnd の setter を呼ぶ
print("{}", rnd) # 値を出力
if i != 9 {
print(", ")
}
sum.set(sum, rnd) # sum の setter を呼ぶ
}
println("")
ret sum
}
Rustで実装されています。コンパイル結果はWebAssemblyとして出力されます。
リポジトリはこちらです：
Webブラウザ上で動作するPlaygroundも用意しています：
先ほど挙げたexampleを含む、いくつかのexampleを閲覧・実行できます。こちらはバンドラとしてViteを使っています [2] が、React等は使わないことにしました。そこまで凝ったことをするつもりはなかったので……。
制作のモチベーション
それはReactを書いていたときに浮かんできました。長年クラスで運用しているテスト対策問題の共有サービス をリファクタリングしていて、ロジックを useReducer に置き換えていた時のことです。書いていたコードを一部抜き出してみると、こんな感じです：
type Action =
{ type: 'title/set', data: string }
| { type: 'tags/set', data: TagData[] }
| { type: 'exam/move', from: number, to: number };
function reducer(current, action) {
// 本当は引数のcurrentを直接編集するのはよろしくないです
switch (action.type) {
case 'title/set':
current.title = action.data;
break;
/* 'tags/set' と 'exam/move' の実装は省略 */
}
return current;
}
// こんな感じで使います：
const [state, dispatch] = React.useReducer(reducer, {title: '', exam: [], tags: []});
// -> state.title = '', state.tags = []
dispatch({ type: 'title/set', data: 'Hello' });
// -> state.title = 'Hello'
dispatch({ type: 'tags/set', data: [{id: 0, name: 'TagName'}] });
// -> state.tags = [{id: 0, name: 'TagName'}]
これを書いていて、ふと思いました。これは変数 state に対する setterをいくつか用意し、引数でそれを切り替えているようなものなのではないでしょうか？
この解釈自体が妥当かどうかは知りませんが、この気付きをもとに作ったのが Settlang です。性質からして当然ではありますが、静的型付け言語と呼べるものだと思います。構文は主にRustに寄せましたが、全体的にタイプ数を減らしたいというモチベーションでキーワードを決めました。これにより、return ではなく ret になっている、1行コメントが // ではなく # である、などの差異があります。
ライブラリ不使用
ライブラリに頼らずに自力で実装したほうが、Wasmをはじめとする諸々への理解が深まりそうだと思っていました。また、U-22プロコンでのアピールポイントが欲しかったという理由もあります。
というわけで、「exampleをコンパイルして実行結果を確かめる」というテストを実行する箇所を除き、外部crateを一切用いていません。テストは流石に権威（？）あるWasmランタイムを使うべきだと思ったので、Wasmerを使っています。
自分で実装した部分で、特筆すべきだと思う点について書いていきます。
Wasm・JS間のやりとり
Rustでブラウザで動かすWasmをビルドするとき、最も簡単な方法としてはwasm-packを使うというものが挙げられるでしょう。Rustが吐き出したWasmを読み込む処理や、JSからその関数を呼び出すためのwrapperを生成してくれます。
今回はライブラリを使わずに実装ということで、wasm-packも使用しません。Wasmの読み込みから実行まで、すべて自力で実装しました。
ところで、JSでWasmを読み込んだとき、Wasmからexportされている関数を呼び出すのは基本的にそれほど難しくありません。ただし、引数として文字列を渡そうとすると、少しややこしいことになってきます。
Rustで wasm32-unknown-unknown をターゲットとすると、ビルドして出力されたWasmファイルからmemoryがexportされていることを確認できます。
$ wasm2wat target/wasm32-unknown-unknown/release/playground_compiler.wasm | grep '(export "memory"'
(export "memory" (memory 0))
このメモリを介して、データをやり取りします。例えば、関数呼び出し時の引数として文字列を渡す際は、メモリに文字列を書き込んで、そのアドレスを渡すという方式をとっています。
以下、playground_front/main.js を一部改変しながら載せて解説していきます。詳しい処理を知りたい方はリンクからリポジトリに飛んでください。
コンパイラ（Wasmバイナリ）の読み込み
まずWasmを読み込んでインスタンスを作ります。
const res = await fetch('/settlang/compiler.wasm');
const compiler = WebAssembly.instantiateStreaming(res);
メモリに書き込む
HTMLの <textarea> から入力を受け取り、TextEncoderでバイト列にします。Wasmのインスタンスからexportされたメモリを取得して、入力から変換されたバイト列を書き込みます。以下の例では input_ptr のところ、つまり0x10番地にバイト列を書き込んでいます。この数字は適当です。
const encoder = new TextEncoder();
const input_area = document.getElementById('input_area');
const input = encoder.encode(input_area.value);
const input_ptr = 16;
const buffer = new Uint8Array(compiler.instance.exports.memory.buffer);
buffer.set(input, input_ptr);
input と input_ptr は次でも使います。
コンパイラから読み込む
playground用のコンパイラは pub fn build(input_str: *mut u8, input_len: usize) -> *const u8 という関数だけを実装しています。pub を付けて公開している関数は、Wasmバイナリからもexportされるようになります。
実装はざっくりこんな感じです。詳しくは playground_compiler/lib.rs を読んでみてください。
pub fn build(input_ptr: *mut u8, input_len: usize) -> *const u8 {
// 実行結果を格納するVec。最初、先頭32bitは0
let mut output: Vec<u8> = 0u32.to_be_bytes().to_vec();
// 引数からStringを作り、そこからbackend用の構造体を作る
let (input, _, _) = String::with_capacity(input_len).into_raw_parts();
let input = unsafe {
// 引数として渡された、文字列のバイト列が書き込まれたアドレスからコピー
core::ptr::copy(input_ptr, input, input_len);
// Stringとして再構築
String::from_raw_parts(input, input_len, input_len)
};
let mut code = backend::source_code::SourceCode::new(&input);
// ビルド（コンパイル結果をWasm Builderに渡す）
let mut contents = 'build: {
let program = match backend::compile(&mut code) {
Ok(program) => program,
Err(e) => break 'build e.as_bytes().to_vec(),
};
match backend::builder::wasm::build(program) {
Ok(wasm) => {
// 成功したら、outputの先頭32bitを1(u32)にする
output = 1u32.to_be_bytes().to_vec();
wasm
}
Err(error) => format!("[error] failed to build WASM file : {}", error)
.as_bytes()
.to_vec(),
}
};
// 出力結果とそのサイズを格納して、バッファへのポインタを返却
output.extend(contents.len().to_be_bytes());
output.append(&mut contents);
output.into_raw_parts().0
}
build 関数は、入力された文字列（のバイト列）をメモリの input_str 番地から読み取ってStringを組み立てます。これを（backend モジュールで実装されている関数に渡して）コンパイルし、その結果をVecに格納して、そのVecのバッファを指すポインタを戻り値として返却します。
バッファの先頭32bitはu32（ビッグエンディアン）で表される [3] 終了コードです。その次の32bitはコンパイラの出力長です。コンパイルが成功した場合、終了コードは1になり、コンパイラの出力はビルド結果（Wasmバイナリ）になります。失敗した場合、終了コードは0 [4] で、コンパイラの出力はエラーを示す文字列です。
さて。JS側で、先ほど使った input_ptr および input を使って、以下のようにbuild 関数を呼び出します：
const retval_build = compiler.instance.exports.build(input_ptr, input.length);
戻り値が結果を格納しているバッファへのポインタとなっています。JavaScriptのDataViewを用いて、以下のようにデータを取得できます：
const viewer = new DataView(compiler.instance.exports.memory.buffer);
// 終了コード
const is_succeed = viewer.getUint32(retval_build + 0) === 1; // 0:3
// コンパイラの出力長
const output_len = viewer.getUint32(retval_build + 4); // 4:7
// コンパイラの出力（バイト列）
const output = (() => {
const buffer = [];
for (let i = 0; i < output_len; ++i) {
const c = viewer.getUint8(retval_build + 8 + i);
buffer.push(c);
}
return new Uint8Array(buffer);
})();
viewer からの結果取得にはfor文を使っています。もうちょっと上手に書けないんですかね。あんまり調べてませんが。
ビルド成果の実行
ビルドが成功していれば、output はWasmバイナリになっているはずです。インスタンス化して実行できます。
const generated = await WebAssembly.instantiate(output, {std: /* stdlib */ });
generaged.instance.exports.main();
第2引数の std には、JavaScriptで実装した標準ライブラリを渡しています。例えば、Rustっぽい print / println や、ユーザーからの入力を受け取る read などです。
パーサー
ライブラリを使わないので当然パーサーも自作しました。nom を参考にしつつ、パーサーコンビネータ……と言って良いのかわかりませんが、そんな感じの実装になりました。個人的にはかなり気に入っています。あまり汎用的ではないのですが、ちょっと手入れしていつか他のプロジェクトに導入したいです。
setter呼び出し部分、つまり 変数名.set(引数) のパースは個人的に気に入っているので、パーサーの呼び出し例として貼っておきます：
変数名 → 0個以上の空白 (に相当するもの) → '.' → 0個以上の空白 → "set" → 0個以上の空白 → '(' ... という感じです。
Wasmバイナリの出力
仕様を読んで、その通り実装するだけです。
……まあ正直に言うと、これだけだと個人的に分かりづらいなあと思ってしまう部分もいくつかあったので、Wasmをテキスト形式で書いて wat2wasm コマンドでバイナリを覗いて仕様を確認する、といったこともやっていました。
LEB128
Wasmは即値をLEB128というフォーマットで表現します。整数を可変長のバイト列で表現するためのもので、あるバイトの最上位bitが0であれば終端bit、みたいなフォーマットです。DWARFで用いられていたものらしく、DWARFの仕様書 (P283あたり) にpseudo codeがあるので、それに沿って実装すればOKです。こんな感じになりました：
反省
U-22プロコンにも落ちたし、そもそも心残りもいくつかあるので、振り返っておきます。
何が出来るのか分からない
アイデアを思いついて、実装を見据えながら構文などを考えているとき、常に頭にあったのは「これ何が嬉しいんだ？」という思いです。変数にsetterがあったところで何が嬉しいんでしょうか。そもそもimmutable最高！みたいな主張が主流 [5] である現代において、mutationの方式をウリにするのって何だか時代に逆行しているような気がしないでもないですし。
まあ実装してみなければPoCも作れないよな、という思いで実装し、結局この問いに対する答えを得られないままU-22プロコンに応募し、「何が出来るのかわからない」という雰囲気のフィードバックとともに落選通知を受け取りました。まあ……しょうがないかなと思っています。
いちおう思いついた使い道も書いておきます。まず、引数の型として、以下のような範囲指定を受け付けるようにして、バリデーションを簡素化する、というものです。
# 引数 m に対して、0 < m <= 12 の制約を課す
fn set_month(m: i8.ge(0).leq(12)) -> i8 { ret m }
let month: i8 | set_month = 4;
month.set(12) // ok
#* NG
month.set(-1)
month.set(0)
month.set(99)
*#
篩型というらしいです。これはコンパイル時の検査なら可能かもしれませんが、ユーザーからの入力を受け取るとなると、いい感じのエラーハンドリング機構も一緒に導入しなければならないでしょう。結局エラーハンドリングをどうするか決められず、そしてそもそも実装時間が足りなかったため、これは実装していません。
それから、関数型言語で見られる引数のパターンマッチングをsetterにも適用したら、例えばステートマシンとかを書きやすくなったりとかして、嬉しい可能性があるかもな、と思いました。加えて、変数が変更されるときは必ず関数呼び出しを経由することになるので、デバッガ等で値をトレースするのが簡単にならないかなとかも考えました。これらについては、実装時間の不足はもちろん、そもそもアイデアをまだ深く考えていないので、実装はしていません。
アイデアが思い浮かばないのは、コンピュータサイエンスへの理解不足や、扱えるプログラミング言語のレパートリーが少なすぎることも一因だと思っています。実際、前述した引数のパターンマッチングは、関数型言語について調べていた時に思いついたものです。もっと色々なプログラミング言語に触れたりしてみたいな、と思っています。
実装期間が短い
U-22プロコンの締切は08/30で、僕が提出を行ったのは締切当日の23:30頃です。それに対して、initial commitをしたのは08/02です。開発期間を1ヶ月しか設けられなかったのは、ある程度は仕方がない部分もある [6] のですが、それにしても短すぎたと思っています。
とりあえず応募するためには動くものが必要だと思っており、実装面で妥協した点が大量にあります。型はi32とi64（と読み取り専用の文字列型）しかないし、if文かどこか忘れましたが 特定箇所で変数を宣言できなかったりするし……。
また、変数のsetterは複数指定できるようにして、引数の型や個数で呼び出すsetterを変えられるようにしたかったのですが、これも時間の都合で省く羽目になりました。複数setterを実装して、かつ値を型のように扱えるようにすれば、それこそ React.useReducer のようなことが出来ていたかもな、と思っています。
コンパイラのことを理解しないまま実装した
これも実装期間の短さと少し関係があるのですが、LL(1)とかそのあたりを全く理解しないまま実装したのが少し心残りです。途中で理解しようとして頑張った形跡はあるのですが……
……これらを理解するよりも、U-22プロコンでアピールできる機能をちゃんと実装するほうが重要だと思い、理解を諦めました。時間が許せばもう少しきちんと理解して実装したかったという思いはあります。tokenizer.rs が明らかにtokenize以上のことをしてるし……。
おわりに
可変性をsetterの有無で表す言語、Settlang の紹介でした。心残りも多いですが、それっぽいプログラミング言語を作るのは初めてで、思ってたよりもちゃんとした形になったのは嬉しかったです。また機会があれば、文法や型システムについて学んだうえで、別のプログラミング言語を作ってみたいとも思っています。
普段は watasuke.net で記事を書いています。最近だと Keyball44 を組んだ話とか、高専祭のホームページを作った話とかを書いています。よければご覧ください。
Discussion