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

# はじめに

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

※この記事のアップデート版はこちら ... [Node.js でつくる Node.js-WASM コンパイラー - 02：四則演算を実装する](https://qiita.com/massie_g/items/e01c6b4a0834ca89fdea)


- 前回の記事 ... [01：初めてのWASMで定数戻り値を返す](https://qiita.com/massie_g/items/916845afba513c8b712c)

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

## これまでの取り組み

- [Node.jsでつくるNode.js（ミニインタープリター） - もくじ](https://qiita.com/massie_g/items/3ee11c105b4458686bc1)
- [Node.jsでつくるNode.jsミニコンパイラ - もくじ](https://qiita.com/massie_g/items/3ba1ba5d55499ee84b0b)

# 足し算の実現

## 対象ソース

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

```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のインデントを整形するためのユーティリティ関数

```js: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はこちらです。

```js: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()関数を拡張します。

## 二項演算子の生成

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

```js: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;
}
```

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

## 四則演算の実行

### 対象ソース

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

```js: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 なので、想定通りになりました。

# テストの改良

[前回は](https://qiita.com/massie_g/items/916845afba513c8b712c)、単一のソースを対象としたテストとして、[test_exitcode.sh](https://github.com/mganeko/node_wasm/blob/master/test/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
======================
```

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

# 次回は

次回は、[複数行のとローカル変数を実装](https://qiita.com/massie_g/items/4aea9e95579a30b16bc2)する予定です。


# これまでのソース

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

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