Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@massie_g(がねこ まさし)

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

Last updated at Posted at 2019-11-16

はじめに

Node.jsで小さなプログラミング言語を作ってみるシリーズを、「ミニインタープリター」「ミニコンパイラー」とやってきました。そして三部作(?)の最後として、 ミニNode.jsからWASMを生成する小さなコンパイラーに取り組んでいます。今回は四則演算と余り（+, -, *, /, %)を実装してみましょう。

※以前の記事「Node.js でつくる WASM トランスパイラー - 02：四則演算を実装する」のアップデート版になります

これまでの取り組み

足し算の実現

対象ソース

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

add.js
1 + 2;

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

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

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

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

WATの生成

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

  • generateLiteral() ... 整数リテラル生成
  • generateAddOperator() ... 足し算生成
    • 内部で、演算子の左の項、右の項を生成するために、generate()を再帰的に呼び出す
  • TABs() ... WATのインデントを整形するためのユーティリティ関数
generate()を拡張
// ---- genereate WAT 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);
  const rightBlock = generate(tree[2], indent);

  let block = '';
  block = block + leftBlock + LF();
  block = block + rightBlock + LF();
  block = block + TABs(indent) + 'i32.add' + LF();;
  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を生成して実行してみましょう。

  • WAT→WASM変換 ... wat2wasm を利用
  • WASMの実行 ... 前回用意した run_wasm_simple.js を利用
$ node mininode_wasm_02_add.js add.js
$ cat generated.wat
(module
  (export "exported_main" (func $main))
  (func $main (result i32)
    i32.const 1
    i32.const 2
    i32.add

    return
  )
)
$ wat2wasm generated.wat
$ 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 ] ] ]
]

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

複数足し算の実行結果
$ node mininode_wasm_02_add.js sample/add_many.js 
$ cat generated.wat
(module
  (export "exported_main" (func $main))
  (func $main (result i32)
    i32.const 1
    i32.const 2
    i32.add

    i32.const 3
    i32.const 4
    i32.const 5
    i32.add

    i32.add

    i32.add

    return
  )
)
$ wat2wasm generated.wat
$ 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 WAT 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);
  const rightBlock = generate(tree[2], indent);
  const op = 'i32.' + operator;

  let block = '';
  block = block + leftBlock + LF();
  block = block + rightBlock + LF();
  block = block + TABs(indent) + op + LF();
  return block;
}

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

四則演算の実行

対象ソース

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

sample/binoperator.js
// expect 2
(1 + 3*5 - 4/2) % 3;

WASM生成と実行

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

  • コンパイラーで、sample/binoperator.js → generated.wat
  • wat2wasm で、generated.wat → generated.wasm
  • run_wasm_simple.js で実行
$ node mininode_wasm_02.js sample/binoperator.js
$ cat generated.wat
(module
  (export "exported_main" (func $main))
  (func $main (result i32)
    i32.const 1
    i32.const 3
    i32.const 5
    i32.mul

    i32.add

    i32.const 4
    i32.const 2
    i32.div_s

    i32.sub

    i32.const 3
    i32.rem_s

    return
  )
)
$
$ wat2wasm generated.wat
$ 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インタープリター
  • $case_count ... 実行したテストの数
  • $ok_count ... 成功したテストの数
  • $err_count ... 失敗したテストのkazu

複数回実行し、結果をレポートします。

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

0
0
0

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
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?