Node.js でつくる WASM トランスパイラー - 02：四則演算を実装する

はじめに

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

※この記事のアップデート版はこちら ... Node.js でつくる Node.js-WASM コンパイラー - 02：四則演算を実装する

• 前回の記事 ... 01：初めてのWASMで定数戻り値を返す

前回からだいぶ間が空いてしまいましたが、今回は四則演算と余り（+, -, *, /, %)を実装してみましょう。

これまでの取り組み

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

足し算の実現

対象ソース

Node.jsの対象となるコードはこちらです。単純な整数の足し算です。

add.js

1 + 2;

これをミニインタープリター、ミニコンパイラーで使ったモジュール（module_parser_13.js）でパース/単純化したASTを作ります。結果はこちらのようになります。

[ '+', [ 'lit', 1 ], [ 'lit', 2 ] ]

足し算を表現するWASMは次のようになります。32ビット整数の足し算は i32.add を使います。

(module
  (export "exported_main" (func $main))
  (func $main (result i32)
    (i32.add
      (i32.const 1)
      (i32.const 2)
    )
  )
)

WASTの生成

前回の整数リテラルに加えて、足し算（'+')も2項演算子として生成できるように拡張します。

• generateLiteral() ... 整数リテラル生成
• generateAddOperator() ... 足し算生成
  • 内部で、演算子の左の項、右の項を生成するために、generate()を再帰的に呼び出す
• TABs() ... WASTのインデントを整形するためのユーティリティ関数

generate()を拡張

// ---- genereate WAST block ---
function generate(tree, indent) {
  if (tree === null) {
    return '';
  }

  if (tree[0] === 'lit') {
    return generateLiteral(tree, indent);
  }

  // --- add operator ---
  if (tree[0] === '+') {
    return generateAddOperator(tree, indent);
  }

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

// -- 整数リテラル --
function generateLiteral(tree, indent) {
  const v = tree[1];

  const block = TABs(indent) + '(i32.const ' + v + ')';
  return block;
}

// --- 足し算 ---
function generateAddOperator(tree, indent) {
  // 左側の項を生成する
  const leftBlock = generate(tree[1], indent + 1);

  // 右側の項を生成する
  const rightBlock = generate(tree[2], indent + 1);

  // 足し算を生成する
  let block = TABs(indent) + '(i32.add' + LF();
  block = block + leftBlock + LF();
  block = block + rightBlock + LF();
  block = block + TABs(indent) + ')';
  return block;
}

// --- インデント整形用 ---
function TABs(n) {
  let tabs = '';
  let i = 0;
  while (i < n) {
    tabs = tabs + TAB();
    i = i + 1;
  }

  return tabs;
}

これで、足し算も生成できるようになりました。

足し算の実行

足し算までサポートしたトランスパイラーのコードを mininode_wasm_02_add.js とします。これでWASMを生成して実行してみましょう。

• WAST→WASM変換 ... wasm-as を利用
• WASMの実行 ... 前回用意した run_wasm_simple.js を利用

$ node mininode_wasm_02_add.js add.js
$ cat generated.wast
(module
  (export "exported_main" (func $main))
  (func $main (result i32)
    (i32.add
      (i32.const 1)
      (i32.const 2)
    )
  )
)
$ wasm-as generated.wast
$ node run_wasm_simple.js generated.wasm
Loading wasm file: generated.wasm
ret code=3

終了コードが「3」となり、1+2が計算できました。

複数の足し算

今回の足し算の生成では、再帰的な処理を行っています。これにより、複数の足し算があっても生成できるようになっています。

対象となるソースと、それを表す単純化ASTはこちらです。

add_many.js

1 + 2 + (3 + (4 + 5) );

単純化AST

[ '+',
  [ '+', [ 'lit', 1 ], [ 'lit', 2 ] ],
  [ '+', [ 'lit', 3 ], [ '+', [ 'lit', 4 ], [ 'lit', 5 ] ] ]
]

WAST/WASM生成、実行結果がこちら。

複数足し算の実行結果

$ node mininode_wasm_02_add.js sample/add_many.js 
$ cat generated.wast
(module
  (export "exported_main" (func $main))
  (func $main (result i32)
    (i32.add
      (i32.add
        (i32.const 1)
        (i32.const 2)
      )
      (i32.add
        (i32.const 3)
        (i32.add
          (i32.const 4)
          (i32.const 5)
        )
      )
    )
  )
)
$ wasm-as generated.wast
$ node run_wasm_simple.js generated.wasm
Loading wasm file: generated.wasm
ret code=15

入れ子の足し算が生成され、実行結果も正しく「15」が得られました。

残りの四則演算のサポート

WASMの演算命令

符号付32ビット整数の演算には、次の命令を使います。

• i32.add ... 足し算(+)
• i32.sub ... 引き算(-)
• i32.mul ... 掛け算(*)
• i32.div_s ... 割り算(/)
• i32.rem_s ... 余り(%)

これをサポートするように、generate()関数を拡張します。

二項演算子の生成

先ほどは足し算専用でしたが、四則演算の二項演算子に対応するようにかくちょうします。

generate()の拡張

// ---- genereate WAST block ---
function generate(tree, indent) {
  if (tree === null) {
    return '';
  }

  if (tree[0] === 'lit') {
    return generateLiteral(tree, indent);
  }

  // --- binary operator ---
  if (tree[0] === '+') {
    return generateBinaryOperator(tree, indent, 'add');
  }
  if (tree[0] === '-') {
    return generateBinaryOperator(tree, indent, 'sub');
  }
  if (tree[0] === '*') {
    return generateBinaryOperator(tree, indent, 'mul');
  }
  if (tree[0] === '/') {
    return generateBinaryOperator(tree, indent, 'div_s');
  }
  if (tree[0] === '%') {
    return generateBinaryOperator(tree, indent, 'rem_s');
  }

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

// --- 二項演算子 ---
function generateBinaryOperator(tree, indent, operator) {
  const leftBlock = generate(tree[1], indent+1);
  const rightBlock = generate(tree[2], indent+1);

  let block = TABs(indent) + '(i32.' + operator + LF();
  block = block + leftBlock + LF();
  block = block + rightBlock + LF();
  block = block + TABs(indent) + ')';
  return block;
}

演算子の左の項、右の項を再帰的に生成するのは、足し算の時と同様です。

四則演算の実行

対象ソース

四則演算と余りを用いた、次のソースを用意しました。

sample/binoperator.js

// expect 2
(1 + 3*5 - 4/2) % 3;

WASM生成と実行

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

• トランスパイラーで、sample/binoperator.js → generated.wast
• wasm-as で、generated.wast → generated.wasm
• run_wasm_simple.js で実行

$ node mininode_wasm_02.js sample/binoperator.js
$ cat generated.wast
(module
  (export "exported_main" (func $main))
  (func $main (result i32)
    (i32.rem_s
      (i32.sub
        (i32.add
          (i32.const 1)
          (i32.mul
            (i32.const 3)
            (i32.const 5)
          )
        )
        (i32.div_s
          (i32.const 4)
          (i32.const 2)
        )
      )
      (i32.const 3)
    )
  )
)
$
$ $wasm-as generated.wast
$ node run_wasm_simple.js generated.wasm
Loading wasm file: generated.wasm
ret code=2

実行結果の終了コードは「2」です。(1 + 3*5 - 4/2) % 3 = (1 + 15 - 2) % 3 = 14 % 3 = 2 なので、想定通りになりました。

テストの改良

前回は、単一のソースを対象としたテストとして、test_exitcode.sh というシェルスクリプトを用意しました。
今回はこれを複数回実行して、トータルの成功/失敗件数を出すシェルスクリプトを用意します。

メインの処理はこちらです。

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

  # usage:
  #  sh test_exitcode.sh compilername interpname filename 
  #
  sh test_exitcode.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

# --- report --
Report

# --- exit ----
exit $err_count

実行すると、次のように結果を出します。

$ sh test_exitcode_multi.sh
... 途中経過は省略 ... 
===== test finish ======
 total=6
 OK=6
 NG=0
======================

これで今後の回帰テストも楽になりました。

次回は

次回は、複数行のとローカル変数を実装する予定です。

これまでのソース

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

• GitHubのレポジトリ ... https://github.com/mganeko/node_wasm
• mininode_wasm_02.js ... 今回のWASMトランスパイラー
• mininode_14.js ... 比較用のNode.jsミニインタープリター
• module_parser_13.js ... ミニインタープリター、ミニコンパイラー、WASMトランスパイラーで共通に使うパーサー
• module_xxxx ... ミニインタープリターやWASMトランスパイラーで使うモジュール類
• sample/add.js ... 足し算の変換対象ソース
• sample/add_many.js ... 複数の足し算の変換対象ソース
• sample/binoperator.js ... 四則演算の変換対象ソース
• test/test_exitcode_multi.sh ... 複数のテストをまとめて行うシェルスクリプト