Node.js でつくる Node.js-WASM コンパイラー - 03：ローカル変数を実装する

はじめに

Node.jsで小さなプログラミング言語を作ってみるシリーズを、「ミニインタープリター」「ミニコンパイラー」とやってきました。そして三部作(?)の最後として、 ミニNode.jsからWASMを生成する小さなコンパイラーに取り組んでいます。

※以前の記事「Node.js でつくる WASM トランスパイラー - 03：ローカル変数を実装する」のアップデート版になります。

• Node.jsでつくるNode.js-WASMコンパイラ - もくじ
• 前回の記事 ... 02：四則演算を実装する

これまでの取り組み

• Node.jsでつくるNode.js（ミニインタープリター） - もくじ
• Node.jsでつくるNode.jsミニコンパイラ - もくじ

今回実現したいこと

今回はローカル変数のサポートが目標ですが、合わせて他の機能も実装します。

• ローカル変数（宣言、参照、代入）
• 複数行のサポート ... 変数を使って複数の計算を行うため
• 簡易デバッグ出力 ... 途中の計算結果を確認するため

簡易デバッグ出力

WASMから直接コンソール出力することはできないため、呼び出し元のJavaScript(Node.js)から、コンソール出力用の関数を渡すようにします。

呼びだし元

WASMから使うための関数を用意し、WebAssembly.instantiate()の際に渡します。

呼び出し例(run_wasm_putn.js)

const imports = {
  // WASM側には、imported_putn()という関数が見えている
  imported_putn: function(arg) { 
    console.log(arg);
  }
};

let source = fs.readFileSync(filename);
let typedArray = new Uint8Array(source);

WebAssembly.instantiate(typedArray, 
  { imports: imports }
).then(result => {
  // WASM側では、exported_main() という関数をエキスポートしている
  const ret = result.instance.exports.exported_main();
  process.exit(ret);
}).catch(e => {
  console.log(e);
});

WAT/WASM内

• 関数をimportして、それを内部の名前に割り付ける
• 関数呼び出しは call を使う

WASM側での読み込み、関数呼び出し(use_putn.wat)

(module
  ;; --- imported_putn() という外部の関数を、$putn() として内部で呼べるようにする
  (func $putn (import "imports" "imported_putn") (param i32))

  ;; --- $main()関数を、外部にexported_main() という名前で公開する
  (export "exported_main" (func $main))

  ;; --- 実際の処理 ---
  (func $main (result i32)
    ;; --- 外部の関数を呼びだす ---
    i32.const 123
    call $putn

    i32.const 0
    return
  )
)

putn()の実行結果

wat2wasmで.watを.wasmに変換し、Node.jsを使って実行します。

$ wat2wasm use_putn.wat 
$ node run_wasm_putn.js use_putn.wasm
123

期待通り、123が標準出力に表示されまました。

コンパイラーの拡張

対象のミニNode.jsコードを用意します。

putn.js

putn(123);

これをパース、単純化すると次の単純化ASTが得られます。

[ 'func_call', 'putn', [ 'lit', 123 ] ]

func_call が関数呼び出しに相当します。今回は簡易版の実装として、putn()だけ呼び出せるような処理を、コンパイラーのgenerate()関数に追加します。（※lctxについては、あとで説明します）

function generate(tree, indent, lctx) {
  // ... 省略 ...

  if (tree[0] === 'func_call') {  // tree = ['func_call', 'name', arg1, ... ]
    const funcName = tree[1];
    if (funcName === 'putn') {
      return generateCallPutn(tree, indent, lctx);
    }

    println('-- ERROR: unknown func in generate() ---');
    printObj(tree);
    abort();
  }

  // ... 省略 ...
}

// --- debug func putn() ---
function generateCallPutn(tree, indent, lctx) {
  // tree = ['func_call', 'name', arg1, arg2, ... ]

  const valueBlock = generate(tree[2], indent, lctx);
  if (!valueBlock) {
    println('---ERROR: empty args for putn() --');
    abort();
  }

  let block = valueBlock + LF();
  block = block + TABs(indent) + 'call $putn' + LF();

  return block;
}

関数呼び出しの処理の生成は、新しく用意したgenerateCallPutn()関数で行っています。引数は1個だけを想定していますが、それが式だった場合も想定して再帰的にgenerate()を呼び出しています。

複数行のサポート

せっかくのローカル変数を活かすには、複数行の処理が書きたいところです。例えば次のようなミニNode.jsのコードを用意します。（最後の0（ゼロ）は終了コードになります）

multi_lines.js

putn(1);
putn(123);
0;

これをパース、単純化すると次の単純化ASTが得られます。stmts(statements)が複数行のかたまりに相当します。

[ 'stmts',
  [ 'func_call', 'putn', [ 'lit', 1 ] ],
  [ 'func_call', 'putn', [ 'lit', 123 ] ],
  [ 'lit', 0 ] ]

これに対応するよう、コンパイラーのgenerate()関数を拡張しておきましょう。

function generate(tree, indent, lctx) {
  // ... 省略 ...

  // --- multi lines ---
  if (tree[0] === 'stmts') {
    let i = 1;
    let block = '';
    while (tree[i]) {
      block = block + generate(tree[i], indent, lctx) + LF() + LF();
      i = i + 1;
    }
    return block;
  }

  // ... 省略 ...
}

ローカル変数のサポート

ローカル変数を扱うために、3つの処理を考えます。

• 変数の宣言（と初期値の代入）: var_decl
• 変数の再代入: var_assign
• 変数の参照: var_ref

変数の宣言

ローカル変数の宣言は、初期値がない場合と、初期値がある場合があります。

ミニNode.jsでの表記

let a;
let b = 1;

これをパース、単純化した内部の単純化ASTは次のようになっています。

単純化AST

[ 'var_decl', 'a', null ],
[ 'var_decl', 'b', [ 'lit', 1 ] ],

WATでの表記

WebAssemblyのテキスト表現WATでは、ローカル変数に相当する「local $変数名」があるので、それを使います。初期値がある場合は、宣言後に「set_local」を用いて値をセットします。

WATでの表記

;; let a;
(local $a i32)

;; let b = 1;
(local $b i32)
i32.const 1
set_local $b

コンパイラーの拡張

まず、宣言されたローカル変数をコンパイラー内で覚えておくために、ローカルコンテキスト(lctx)というハッシュ（連想配列）を用意します。これが先ほどからgenerate()の引数に追加されていたのです。今回は型もi32の一種類だけなので、シンプルな持ち方にしています。

ローカル変数の保持

lctx['変数名'] = '$変数名' 

これを使って、generate()関数を拡張します。

function generate(tree, indent, lctx) {
  // ... 省略 ...

  // --- local variable --
  if (tree[0] === 'var_decl') {
    const block = declareVariable(tree, indent, lctx);
    return block;
  }

  // ... 省略 ...
}

// --- declare variable ---
function declareVariable(tree, indent, lctx) {
  // -- check NOT exist --
  const name = tree[1];
  if (name in lctx) {
    println('---ERROR: varbable ALREADY exist (compiler) --');
    abort();
  }

  // -- add local variable --
  const varName = '$' + name;
  lctx[name] = varName;

  // --- assign initial value --
  let init = generate(tree[2], indent, lctx);

  let block = '';
  if (init) {
    block = block + init + LF();
    block = block + TABs(indent) + 'set_local ' + varName + LF();
  }

  return block;
}

実際の変数宣言は、declareVariable()関数で生成しています。初期値が式で渡せるように、その評価のためにgenerate()を再帰的に呼び出します。

変数の代入

変数に値を代入する場合、単純化ASTでは var_assign で表現しています。

[ 'var_assign', 'a', 代入する値 ],

代入する値の部分はリテラルだったり、式だったりします。

WATでは、すでに変数の宣言で登場している「set_local」を使います。generate()関数を拡張し、assignVariable()関数を追加しました。

function generate(tree, indent, lctx) {
  // ... 省略 ...

  // --- local variable --
  if (tree[0] === 'var_assign') {
    const block = assignVariable(tree, indent, lctx);
    return block;
  }

  // ... 省略 ...
}

function assignVariable(tree, indent, lctx) {
  // -- check EXIST --
  const name = tree[1];
  if (name in lctx) {
    let block = '';
    const varName = lctx[name];

    const valueBlock = generate(tree[2], indent, lctx);
    if (!valueBlock) {
      println('---ERROR: var assign value NOT exist --');
      abort();
    }

    block = block + valueBlock + LF();
    block = block + TABs(indent) + 'set_local ' + varName + LF();

    return block;
  }

  println('---ERROR: varibable NOT declarated (assign)--:' + name);
  abort();
}

assignVariable()ではローカルコンテキスト lctx から変数表記を取り出して利用します。代入する内容は例によってgenerate()を呼び出して生成しています。

変数の参照

変数aの値を参照する場合、単純化ASTでは var_ref で表現しています。

[ 'var_ref', 'a' ],

WATでは、次のように「get_local」を使います。

 (get_local $a)

変数の参照のために generate()関数を拡張し、referVariable()関数を追加しました。

function generate(tree, indent, lctx) {
  // ... 省略 ...

  // --- local variable --
  if (tree[0] === 'var_ref') {
    const block = referVariable(tree, indent, lctx);
    return block;
  }

  // ... 省略 ...
}

// --- variable refer ---
function referVariable(tree, indent, lctx) {
  // -- check EXIST --
  const name = tree[1];
  if (name in lctx) {
    let block = '';
    const varName = lctx[name];

    block = TABs(indent) + 'get_local ' + varName;

    return block;
  }

  println('---ERROR: varibable NOT declarated (ref)--:' + name);
  abort();
}

referVariable()ではローカルコンテキスト lctx から変数表記を取り出して利用します。get_local を使うと、変数の値が読み出されてスタックに積まれます。そのまま式で利用したり、関数の引数として利用することができます。

全体の結合

• ローカル変数のためのローカルコンテキストの準備
• 簡易デバッグ出力のための関数 putn() のインポート
• 出力するWATのインデント調整

を行うため、処理を追加し、今回のコンパイラーの完成となります。

function initialLocalContext() {
  const ctx = {
  };
  return ctx;
}
let l_ctx = initialLocalContext(); // top level local context

// --- load and parse source ---
const tree = loadAndParseSrc();

// --- compile to WAT --
const wat = compile(tree, l_ctx);

// ---- compile simplified tree into WAT ---
function compile(tree, lctx) {
  const mainBlock = generate(tree, 2, lctx);
  const varBlock = generateVariableBlock(tree, 2, lctx);

  let block = '(module' + LF();
  block = block + TAB() + '(func $putn (import "imports" "imported_putn") (param i32))' + LF();
  block = block + TAB() + '(export "exported_main" (func $main))' + LF();
  block = block + TAB() + '(func $main (result i32)' + LF();
  block = block + varBlock + LF();
  block = block + mainBlock + LF();
  block = block + TAB() + TAB() + 'return' + LF();
  block = block + TAB() + ')' + LF();
  block = block + ')';

  return block;
}

全体のソースコードは、 mininode_wasm_03.js として GitHub に上げておきます。

変数を使った処理の実行

対象ソース

複数の処理を行う、次のコードを対象にします。

var.js

// --- putn() test ---
putn(1); // 1

// --- declare variable ---
let a = 1 + 2 + 3;
putn(a); // 6

// --- assigne variable, refer variable ---
let b;
b = a + 1;
b = b + 2;
putn(b); // 9
putn(a + b * 2); // 24

b; // expect 9

WASM生成と実行

コンパイラーのソースコードを、mininode_wasm_03.js とします。

• コンパイラーで、sample/var.js → generated.wat
• wat2wasm で、generated.wat → generated.wasm
• run_wasm_putn.js で実行

$ node mininode_wasm_03.js sample/var.js
$ cat generated.wat
(module
  (func $putn (import "imports" "imported_putn") (param i32))
  (export "exported_main" (func $main))
  (func $main (result i32)
    (local $a i32)
    (local $b i32)

    i32.const 1
    call $putn

    i32.const 1
    i32.const 2
    i32.add

    i32.const 3
    i32.add

    set_local $a

    get_local $a
    call $putn

    get_local $a
    i32.const 1
    i32.add

    set_local $b

    get_local $b
    i32.const 2
    i32.add

    set_local $b

    get_local $b
    call $putn

    get_local $a
    get_local $b
    i32.const 2
    i32.mul

    i32.add

    call $putn

    get_local $b

    return
  )
)
$ wat2wasm generated.wat
$ node run_wasm_putn.js generated.wasm
Loading wasm file: generated.wasm
1
6
9
24
ret code=9

想定通りの数値が表示され、戻り値も9になりました。

標準出力のテスト

前回までは戻り値を比較するテストを行っていました。今回は標準出力を比較するテストを用意します。比較の対象は、次の3つです。

• Node.jsで直接実行したときの標準出力
• ミニNode.jsコンパイラーで生成したWASMを、Node.jsで実行したときの標準出力
• ミニNode.jsインタープリターからコンパイラーを実行して生成されたWASMを、Node.jsで実行したときの標準出力

この3つが一致していたら、テストは成功とします。

Node.jsで直接実行

前処理

実行対象となるソースは次の内容です。

var.js

// --- putn() test ---
putn(1); // 1

// --- declare variable ---
let a = 1 + 2 + 3;
putn(a); // 6

// --- assigne variable, refer variable ---
let b;
b = a + 1;
b = b + 2;
putn(b); // 9
putn(a + b * 2); // 24

b; // expect 9

ここで呼び出している putn() は、今回用意した簡易デバッグ出力関数です。Node.jsで実行するには、この関数を用意する必要があります。
そこで、次のコードを用意しておいて、連結してから実行することにしました。

builtin_helper.js

function putn(n) {
    console.log(n);
}

※ GitHubにあるコードは、以後のステップで使う処理も含んでいるので、違う内容になっています。

これを連結してから実行するように、シェルスクリプトで関数を用意しました。

PreprocessBuiltinForDirect() {
  echo "-- preprocess for builtin func:  src=$jsfile tmp=$direct_file --"
  cat $helper_file > $direct_file # putn(), puts()
  cat $jsfile >>  $direct_file
}

• $jsfile ... テストに使うjsのファイル名
• $direct_file ... Node.jsでの直接実行用に一時的に変換したファイル名
• $helper_file ... 組み込み関数を定義した、ヘルパーファイル名

直接実行

前処理が終わったら、Node.jsで実行します。実行時の標準出力の内容をファイルにリダイレクトして記録しておきます。

NodeDirect() {
  echo "-- node $src --"
  node $direct_file > $direct_stdout
  direct_exit=$?
  echo "direct exit code=$direct_exit"
}

ここで、変数は次を保持しています。

• $direct_file ... Node.jsでの直接実行用に一時的に変換したファイル名
• $direct_stdout ... Node.jsで直接実行した際の標準出力を記録しておくファイル名

WASMの生成と実行

js → WATヘの変換

WATの生成は 01：01：WASMで定数戻り値を返す の処理と同じです。

# -- translate to wat ---
TranslateToWat() {
  echo "--- translate src=$jsfile wat=$wat_file translater=$translater ---"
  node $translater $jsfile
  if [ "$?" -eq "0" ]
  then
    echo "translate SUCCERSS"
    mv generated.wat $wat_file
  else
    echo "ERROR! ... translate FAILED !"
    exit 1
  fi
}

ここで、変数の内容は次の通りです。

• $translater ... テスト対象になっている、（ミニNode.jsで書かれた）トランスパイラーのファイル名
• $jsfile ... テストに使うjsのファイル名
• $wat_file ... 生成するWATファイル名

WAT → WASM への変換

WAT → WASMへの変換は wat2wasm を使います。こちらも 01 同じ処理です。

WatToWasm() {
  echo "--- wat $wat_file to wasm $wasm_file --"
  $wat_to_wasm $wat_file -o $wasm_file
  if [ "$?" -eq "0" ]
  then
    echo "wat2wasm SUCCERSS"
  else
    echo "ERROR! ... wat2wasm FAILED !"
    exit 1
  fi
}

変数の内容は次の通りです。

• $wat_to_wasm ... wat2wasm のパス。パスを通しておくか、事前に環境変数WAT2WASM_FOR_TESTにフルパスを設定しておく
• $wat_file ... 変換するWATファイル名
• $wasm_file ... 変換後のWASMファイル名

WASMの実行

WASMの実行時には、標準出力をファイルにリダイレクトして記録しておきます。

ExecWasm() {
  echo "--- exec $wasm_file from node"
  node $wasm_exec $wasm_file > $wasm_stdout
  wasm_exit=$?
  echo "wasm exit code=$wasm_exit"
}

変数の内容は次の通りです。

• $wasm_exec ... wasmの実行に使うNode.jsのコード。今回は run_wasm_builtin.js を利用
• $wasm_file ... 実行するWASMファイル名
• $wasm_stdout ... 標準出力を記録するファイル名

実行に利用している run_wasm_builtin.js は、この記事の最初に用意した run_wasm_putn.js と同様の処理ですが、 putn() 以外にも今後のステップで利用する他のビルトイン関数も含めて用意しています。 run_wasm_builtin.js については、別の記事で説明する予定です。

ミニインタープリターを使ったWASM生成

引き続き今回のコンパイラーは、以前つくったミニNode.jsインタープリターで動くことを縛りにしています。
詳細は省略しますが、もう一つWASMファイルを生成、実行しています。実行時の標準出力は、こちらもファイルに記録しておきます。

標準出力のチェック

標準出力の比較では改行文字の違いは無視して diff を取っています。

DiffStdout() {
  diff --strip-trailing-cr $direct_stdout $wasm_stdout > $diff_direct_wasm
  diff --strip-trailing-cr $direct_stdout $interp_wasm_stdout > $diff_direct_interp_wasm
}

ここで変数は次の通りです。

• $direct_stdout ... Node.jsで直接実行した場合の標準出力の内容
• $wasm_stdout ... コンパイラーで生成した WASM を実行した場合の標準出力の内容
• $interp_wasm_stdout ... ミニンタープリターから実行したコンパイラーで生成した WASM を実行した場合の標準出力の内容
• $diff_direct_wasm ... 直接実行と、WASMの標準出力の差分ファイル
• $diff_direct_interp_wasm ... ミニンタープリターを使った場合の標準出力の差分ファイル

その差分の中身が空であればテストは成功、中身が何かあったらテストは失敗とみなします。

CheckStdout() {
  if [ -s $diff_direct_wasm ]
  then
    echo "ERROR! ... node <-> wasm stdout are different"
    cat $diff_direct_wasm
    exit 1
  else
    echo "OK ... node <-> wasm stdout are same"
  fi

  if [ -s $diff_direct_interp_wasm ]
  then
    echo "ERROR! ... node <-> inerp-wasm stdout are different"
    cat $diff_bin
    exit 1
  else
    echo "OK ... node <-> inerp-wasm stdout are same"
  fi
}

ここまでのテスト実行するシェルスクリプトを、test_stdout.sh とします。

複数テストの実行

前回の 02：四則演算を実装する で用意した複数のテストを拡張して、今回の標準出力の比較を使ったテストを組み込みます。

TestSingleStdout() {
  # --- exec 1 test case --
  testfile=$1

  # usage:
  #  sh test_stdout.sh compilername interpname filename 
  #
  sh test_stdout.sh $compiler $interpreter $testfile
  last_case_exit=$?

  # --- check test result--
  case_count=$(($case_count+1))
  if [ "$last_case_exit" -eq 0 ]
  then
    # -- test OK --
    ok_count=$(($ok_count+1))
    echo "$testfile ... OK" >> $summary_file 
  else
    # -- test NG --
    err_count=$(($err_count+1))
    echo "$testfile ... NG" >> $summary_file 
  fi
}

• 引数 ... 実行対象のソース
• $compiler ... コンパイラー（テストの対象）
• $interpreter ... 比較に使うミニNode.jsインタープリター

これを使って、これまでのテストをまとめて実行することができます。

# ---- exec test case -----
# step_01
TestSingleExitCode one.js
TestSingleExitCode two.js
TestSingleExitCode eight.js

# step_02
TestSingleExitCode add.js
TestSingleExitCode add_many.js
TestSingleExitCode binoperator.js

# step_03
TestSingleStdout putn.js
TestSingleStdout multi_lines.js
TestSingleStdout var.js

次回は

次回は、比較演算子を実装する予定です。

ここまでのソース

GitHubにソースを上げておきます。

• GitHubのレポジトリ ... https://github.com/mganeko/mini_node_wasm
• mininode_wasm_03.js ... 今回のWASMコンパイラー
• mininode_15.js ... 比較用のNode.jsミニインタープリター
• module_parser_15.js ... ミニインタープリター、ミニコンパイラー、WASMコンパイラーで共通に使うパーサー
• module_xxxx ... ミニインタープリターやWASMコンパイラーで使うモジュール類
• sample/putn.js ... 簡易デバッグ出力 putn() を利用するサンプル
• sample/multi_lines.js ... 複数行の処理を確認するサンプル
• sample/var.js ... ローカル変数を利用するサンプル
• test/builtin_helper.js ... Node.jsでの直接実行時に、組み込み関数を補うためのソース
• test/test_stdout.sh ... 標準出力の差分をチェックするテスト
• test/test_multi.sh ... 複数のテストをまとめて行うシェルスクリプト（終了コード or 標準出力)