自作言語でWASMを出力

WATはS式で書かれたただのテキストファイルです。

(module
  (func (export "main") (result i64)
    (i64.const 1)
    (i64.const 2)
    (i64.const 3)
    i64.mul
    i64.add
  )
)

これは「1 + 2 * 3」を計算するモジュールです。中身はスタックマシンの命令列そのもので、(i64.const n)で値をスタックに積み、i64.addのような命令がスタックから値をpopして計算しpushする、という仕組みになっています。バイナリの.wasmにするにはwat2wasmというツール（WABTというツールキットに含まれる）に投げるだけです。

つまり「自作言語 → WAT文字列を組み立てる → wat2wasmに渡す」という流れさえ作れば、バイナリフォーマットの詳細を一切知らなくてもWasmを吐くコンパイラが作れます。今回はRustで四則演算だけの超ミニ言語 minimini_lang を作って、これを試してみました。

ミニ言語の文法

パーサーはlalrpopというRust用のパーサジェネレータを使って書きました。

use std::str::FromStr;
use crate::ast::{Expr, BinOp};

grammar;

match {
    r"\s*" => {},
    r"//[^\n\r]*" => {}, // line comments
    _
}

pub Expr: Expr = {
    <l:Expr> "+" <r:Term> => Expr::binop(l, BinOp::Add, r),
    <l:Expr> "-" <r:Term> => Expr::binop(l, BinOp::Sub, r),
    Term,
};

Term: Expr = {
    <l:Term> "*" <r:Factor> => Expr::binop(l, BinOp::Mul, r),
    <l:Term> "/" <r:Factor> => Expr::binop(l, BinOp::Div, r),
    Factor,
};

Factor: Expr = {
    Num => Expr::Int(<>),
    "(" <Expr> ")",
};

Num: i64 = {
    r"[0-9]+" => i64::from_str(<>).unwrap(),
};

+ -より* /の方が結合が強く、どちらも左結合、という一般的な四則演算の文法です。

AST

パース結果はこのシンプルなASTになります。

#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    Int(i64),
    BinOp { lhs: Box<Expr>, op: BinOp, rhs: Box<Expr> },
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinOp {
    Add,
    Sub,
    Mul,
    Div,
}

impl Expr {
    pub fn binop(lhs: Expr, op: BinOp, rhs: Expr) -> Expr {
        Expr::BinOp {
            lhs: Box::new(lhs),
            op,
            rhs: Box::new(rhs),
        }
    }

    pub fn get_children(&self) -> Vec<&Expr> {
        match self {
            Expr::Int(_) => vec![],
            Expr::BinOp { lhs, rhs, .. } => vec![lhs.as_ref(), rhs.as_ref()],
        }
    }
}

ASTをWATに変換する

コンパイラの本体はここです。ASTを再帰的に辿って、後置記法（スタックマシンなので当然そうなる）の命令列を組み立てているだけです。

pub fn compile_to_wat(ast: &crate::ast::Expr) -> String {
    let instrs = ast_to_wat_string(ast);
    format!(
        "(module\n  (func (export \"main\") (result i64)\n    {}\n  )\n)\n",
        instrs.join("\n    ")
    )
}

fn ast_to_wat_string(ast: &crate::ast::Expr) -> Vec<String> {
    match ast {
        crate::ast::Expr::Int(n) => vec![format!("(i64.const {})", n)],
        crate::ast::Expr::BinOp { lhs, op, rhs } => {
            let lhs_str = ast_to_wat_string(lhs);
            let rhs_str = ast_to_wat_string(rhs);
            let op_str = match op {
                crate::ast::BinOp::Add => "i64.add",
                crate::ast::BinOp::Sub => "i64.sub",
                crate::ast::BinOp::Mul => "i64.mul",
                crate::ast::BinOp::Div => "i64.div_s",
            };
            let mut result = Vec::new();
            result.extend(lhs_str);
            result.extend(rhs_str);
            result.push(op_str.to_string());
            result
        }
    }
}

#[cfg(test)]
mod tests{
    use super::*;

    #[test]
    fn test_ast_to_wat_string() {
        let ast = crate::ast::Expr::binop(
            crate::ast::Expr::Int(1),
            crate::ast::BinOp::Add,
            crate::ast::Expr::binop(
                crate::ast::Expr::Int(2),
                crate::ast::BinOp::Mul,
                crate::ast::Expr::Int(3),
            ),
        );
        let wat_strings = ast_to_wat_string(&ast);
        let expected = vec![
            "(i64.const 1)".to_string(),
            "(i64.const 2)".to_string(),
            "(i64.const 3)".to_string(),
            "i64.mul".to_string(),
            "i64.add".to_string(),
        ];
        assert_eq!(wat_strings, expected);
    }
}```

`ast_to_wat_string`が命令列を作り、`compile_to_wat`がそれを`(module (func (export "main") (result i64) ...))`というテンプレートに埋め込んでいます。文字列を`format!`で組み立てているだけなので、コンパイラのバックエンドとしてはかなり牧歌的です。

## CLI

あとはファイルを受け取ってWATを吐き出すだけのCLIです。入力は`.mmm`拡張子のファイルにして、出力は同じ名前の`.wat`ファイルに書き出すようにしました。

```rust
use std::env;
use std::fs;
use std::path::PathBuf;
use std::process::exit;

fn main() {
    let args: Vec<String> = env::args().collect();
    let Some(path) = args.get(1) else {
        eprintln!("usage: {} <file.mmm>", args[0]);
        exit(1);
    };

    let src = match fs::read_to_string(path) {
        Ok(src) => src,
        Err(e) => {
            eprintln!("failed to read {path}: {e}");
            exit(1);
        }
    };

    let ast = match minimini_lang::parse_expr(&src) {
        Ok(ast) => ast,
        Err(e) => {
            eprintln!("parse error: {e}");
            exit(1);
        }
    };

    let wat = minimini_lang::compiler::compile_to_wat(&ast);

    let out_path = PathBuf::from(path).with_extension("wat");
    if let Err(e) = fs::write(&out_path, wat) {
        eprintln!("failed to write {}: {e}", out_path.display());
        exit(1);
    }
    println!("wrote {}", out_path.display());

}

実際に動かしてみる

1 + 2 * 3 と書いたファイルをコンパイルすると：

$ cargo run -- simple.mmm
wrote simple.wat

先頭に貼ったWATがそのまま出力されます。これをwat2wasmでバイナリ化して、Node.jsのWebAssemblyAPIから呼び出すと、ちゃんと計算結果が返ってきます。

$ wat2wasm simple.wat -o simple.wasm
$ node -e "
    const bytes = require('fs').readFileSync('simple.wasm');
    WebAssembly.instantiate(bytes).then(({instance}) => {
      console.log(instance.exports.main());
    });
  "
7n

1 + 2 * 3 = 7。優先順位も含めてちゃんと計算できています。

まとめ

• WATはただのテキストなので、自作言語のコンパイラは「ASTを辿って文字列を組み立てる」だけで作れる
• バイナリの.wasm化はwat2wasm（WABT）に任せられる
• 実行はブラウザでもNode.jsのWebAssembly APIでも可能
• テキストなのでテストも普通のシェルスクリプトで組める

「Wasmを吐くコンパイラを作る」というと身構えてしまいますが、WATを経由すれば、パーサーさえ書ければ半日もあれば動くものができてしまいます。次は変数や関数呼び出しなど、もう少し言語らしい機能を足していきたいところです。