LoginSignup
0

More than 3 years have passed since last update.

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

Last updated at Posted at 2019-03-09

はじめに

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

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

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

これまでの取り組み

足し算の実現

対象ソース

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にソースを上げておきます。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0