Node.js でつくる WASMコンパイラー - 06：文字列出力を実装しFizzBuzzを実現する

はじめに

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

• Node.jsでつくるNode.js-WASMコンパイラ - もくじ
• 前回の記事 ... 05：条件分岐とループを実装する

これまでの取り組み

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

今回の実現したいこと

前回作った if による条件分岐と while ループを使って FizzBuzz を実現するのが今回の目的です。が、そのためには準備しなくてなならないものがあります。それは「Fizz」「Buzz」といった決まった文字列を画面出力する手段です。

• 固定の文字列（文字列定数）を扱う
• 文字列定数を標準出力に表示する、 puts() 組み込み関数

puts() の実体は、putn() の時と同様に、WASMの呼び出し元(Node.js)で用意して渡してあげます。WASMの中では、それを import して利用します。

文字列定数の表現

文字列定数を扱う方法として、memory があります。64Kib(64*1024バイト)単位で確保されるデータ領域で、名前をつけることができます。下記は3つの文字列定数を確保している例です。データ領域の先頭からのオフセットをi32定数で指定し、文字列の終端はNull文字(0x00)を付けています。

  (memory $string_area 1) ;; string_area 64KiB
  (data (i32.const 0) "abc\00")
  (data (i32.const 4) "ABCDEFG\00")
  (data (i32.const 12) "12345678901234567890123456789012345678901234567890\00")

対象となるJSコード内に文字列が出てきたら覚えておき、WATを生成する際に memory と data のブロックを書き出すことにします。

WASM内部から呼び出し元へ文字列を渡す

用意した文字列を出力するには、putn()の時と同様に呼び出し元のNode.jsで用意した関数をインポートして使う必要があります。文字列を渡すときには、次の情報を伝えます。

• WASMで確保した memory 領域をエクスポート
• その領域内での文字列の開始オフセット
• 文字列の長さ ... ※今回は直接長さを渡すのではなく、Null文字で終端する方式

memory 領域は次の様に名前(この例では"exported_string")をつけてエクスポートします。

  (memory $string_area 1) ;; string_area 64KiB
  (data (i32.const 0) "abc\00")
  (data (i32.const 4) "ABCDEFG\00")
  ; ... 省略 ...
  (export "exported_string" (memory $string_area))

あとはインポートした関数に文字列の先頭オフセットを渡して呼び出せば、出力したい文字列を渡すことができます。関数を $puts() という名前でインポートしているとすると、次の様になります。

(func $puts (import "imports" "imported_puts") (param i32)) ;; インポート
    ;; ... 省略 ...
    i32.const 4  ;; "ABCDEFG\00" のオフセット
    call $puts   ;; puts()を呼び出す

呼び出し元での puts() の準備

呼び出しもとのNode.jsでは、次の様に puts()を準備し、文字列を出力しています。

関数の準備

const imports = {
  imported_putn: function (arg) { // built-in function putn(): 32ビット整数の出力
    console.log(arg);
  },
  imported_puts: function (offset) { // built-in function puts(): 文字列の出力
    let str = '';
    let arr = new Uint8Array(exported_string.buffer);
    for (let i = offset; arr[i]; i++) {
      str += String.fromCharCode(arr[i]);
    }
    console.log(str);
  }
};

imported_puts() では、引数で渡されたオフセットから1バイトずつ取ってきて、UNICODE文字列に変換しています。Null文字(0x00)が登場したら変換を終了し、コンソールに出力します。

WASMの呼び出しとmemory領域の取得

WebAssembly.instantiate(typedArray,
  { imports: imports }
).then(result => {
  exported_string = result.instance.exports.exported_string; // WASMからエクスポートされたメモリー領域
  ret = result.instance.exports.exported_main();
  console.warn('ret code=' + ret);
  process.exit(ret);
}).catch(e => {
  console.log(e);
});

WASMを呼び出す際には、インスタンス化した際にエクスポートされるメモリー領域を exported_string に記憶しておき、先の imported_puts() で利用できるようにしています。

コンパイラーでの文字列定数の扱い

グローバルコンテキストの導入

03：ローカル変数を実装するでは変数を扱うためにローカルコンテキストを導入しましたが、今回は文字列定数を格納するためにグローバルコンテキストを導入します。言い換えれば、文字列定数はグローバルで共通のリソースということになります。

let g_ctx = {
  'strIdx': 0, // string index
  'strOffset': 0, // offset of next string
  'strList': {}, // string hash:  strList['$s_1'] = ['xxxxx', offset, length]
  'funcList': {},  // function hash: funcList['func1'] = [func_type, func_symbol, ret_type, args_count, func_body]
  //  ex) funcList['add'] = ['user_defined', '$add', 'i32', 2, '.....']
};

• strIdx ... 文字列定数の通し番号(0〜）。文字列の名前は $s_0, $s_1, ...
• strOffset ... 次の文字列が格納される先頭オフセット
• strList ... 文字列を保持するハッシュ（連想配列）
  • strList['$s_1'] = ['xxxxx', offset, length] という形で保持

また funcList は今回はまだ使いませんが、今後ユーザー定義関数の保持に使う予定です。

文字列定数の記録

文字列定数は、次の様にリテラルとして単純化ASTで表現されます。

[ 'lit', 'abc' ]

そのため、以前用意したリテラルを扱う処理を拡張します。

function generateLiteral(tree, indent, gctx, lctx) {
  const v = tree[1];
  const t = getTypeOf(v);

  if (t === 'number') {
    const block = TABs(indent) + 'i32.const ' + v;
    return block;
  }

  if (t === 'string') {
    // --- string literal ---
    const offset = addGlobalString(tree[1], gctx);
    const block = TABs(indent) + 'i32.const ' + offset;
    return block;
  }

  println('---ERROR: unknwon type of literal--:' + t);
  abort();
}

文字列定数を記憶しておく処理は addGlobalString() で行います。文字列の先頭オフセットを返すようにしています。

// -- add global string, return name of string --
function addGlobalString(str, gctx) {
  // -- strings --
  // '$s_1' : ['xxxxxxx', offset, len],

  // --- name of string
  let idx = gctx['strIdx'];
  const name = '$s_' + idx;
  idx = idx + 1;
  gctx['strIdx'] = idx;

  const len = getLength(str);
  const cstr = str + '\\00';
  const clen = len + 1;
  const coffset = gctx['strOffset'];
  const nextOffset = coffset + clen;
  gctx['strOffset'] = nextOffset;

  const globalString = [cstr, coffset, clen];
  let strList = gctx['strList'];
  strList[name] = globalString;

  return coffset;
}

文字列定数の利用

今回は文字列の変数への代入や連結などの操作は一切サポートしません。できるのは、puts()を使って標準出力に表示するだけです。そのため、puts()の引数に文字列の先頭オフセットを渡すことだけできるようにします。

文字列定数の利用例

puts("hello");

これに対応する単純化ASTはこちらです。

 [ 'func_call', 'puts', [ 'lit', 'hello' ] ]

対応するWATはこちら。

    i32.const 4  ;; memory領域における、文字列の先頭オフセット
    call $puts

先頭オフセットの値は先ほど用意した addGlobalString()を呼び出した際の戻り値を利用します。すでに示した様に、generateLiteral() では、addGlobalString()の戻り値を、i32.const の32ビット符号付整数としてスタックに積むコードを生成しています。

generateLiteral()の抜粋

    // --- string literal ---
    const offset = addGlobalString(tree[1], gctx);
    const block = TABs(indent) + 'i32.const ' + offset;

puts()関数の呼び出し部分は、簡易デバッグ関数を拡張して対応します。

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

  // === tentative func call for debug (putn, puts) ====
  if (tree[0] === 'func_call') {  // tree = ['func_call', 'name', arg1, arg2, ... ]
    const funcName = tree[1];
    if (funcName === 'putn') {
      return generateCallPutn(tree, indent, gctx, lctx);
    }
    if (funcName === 'puts') {
      return generateCallPuts(tree, indent, gctx, lctx);
    }

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

  // ... 省略 ...
}

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

  const valueBlock = generate(tree[2], indent, gctx, lctx);

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

  return block;
}

文字列定数の生成

WATを生成する際には、グローバルコンテキストに保持していた文字列定数をまとめて書き出します。

function compile(tree, gctx, lctx) {
  // ... 省略 ...

  // --- mempory segment (static string) --
  const stringBlock = generateGlobalString(gctx);
  block = block + LF();
  block = block + TAB() + ';; ---- export static string  ---' + LF();
  block = block + TAB() + '(memory $string_area 1) ;; string_area 64KiB' + LF();
  block = block + stringBlock;
  block = block + TAB() + '(export "exported_string" (memory $string_area))' + LF();

  // ... 省略 ...
}

// --- 文字列定数を書き出す ---
function generateGlobalString(gctx) {
  let block = '';
  const strList = gctx['strList'];
  const strings = getKeys(strList);
  const len = getLength(strings);
  let key;
  let i = 0;
  let gstr;
  let offset;
  let str;
  while (i < len) {
    key = strings[i];
    gstr = strList[key]; // ['xxxxxxx', offset, length]
    str = gstr[0];
    offset = gstr[1];

    block = block + TAB() + '(data (i32.const ' + offset + ') "' + str + '")' + LF();
    i = i + 1;
  }

  return block;
}

実行例

次のコードを用意します。

putn_puts.js

putn(123);
puts('abc');
putn(456);
puts('ABCDEFG');

1;

ここまでのコンパイラーのソースコードを、mininode_wasm_06.js とします。またputs()も使える様に準備した呼び出し用ソースは run_wasm_builtin.js として用意しています。

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

$ node mininode_wasm_06.js sample/putn_puts.js
$ cat generated.wat
cat generated.wat
(module
  ;; ---- builtin func imports ---
  (func $putn (import "imports" "imported_putn") (param i32))
  (func $puts (import "imports" "imported_puts") (param i32))

  ;; ---- export static string  ---
  (memory $string_area 1) ;; string_area 64KiB
  (data (i32.const 0) "abc\00")
  (data (i32.const 4) "ABCDEFG\00")
  (export "exported_string" (memory $string_area))

  ;; ---- export main function  ---
  (export "exported_main" (func $main))
  (func $main (result i32)

    i32.const 123
    call $putn

    i32.const 0
    call $puts

    i32.const 456
    call $putn

    i32.const 4
    call $puts

    i32.const 1

    return
  )
)
$ wat2wasm generated.wat
$ node run_wasm_builtin.js generated.wasm
Loading wasm file: generated.wasm
123
abc
456
ABCDEFG
ret code=1
$

無事、整数と文字列が出力されました。

FizzBuzzの実現

さて、いよいよ目標の1つであるFizzBuzzの実現です。ここまで用意したif, while, putn(), puts()を総動員します。

fizzbuzz_loop.js

let i = 1;
while (i <= 100) {
  if (i % (3*5) === 0) {
    puts('FizzBuzz');
  }
  else if (i % 3 === 0) {
    puts('Fizz');
  }
  else if (i % 5 === 0) {
    puts('Buzz');
  }
  else {
    putn(i);
  }

  i = i + 1;
}

0;

これをコンパイル、実行すると、FizzBuzzの達成です！

$ node mininode_wasm_06.js sample/fizzbuzz_loop.js 
$ wat2wasm generated.wat
$ node run_wasm_builtin.js generated.wasm
Loading wasm file: generated.wasm
1
2
Fizz
4
Buzz
Fizz
7
...省略...
94
Buzz
Fizz
97
98
Fizz
Buzz
ret code=0

次回は

次回は、ユーザー定義関数を実装する予定です。

ここまでのソース

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

• GitHubのレポジトリ ... https://github.com/mganeko/mini_node_wasm
• mininode_wasm_06.js ... 今回のWASMコンパイラー
• run_wasm_builtin.js ... WASMの実行につかうファイル
• sample/putn_puts.js ... 簡易デバッグ出力 putn() と puts() を利用するサンプル
• sample/fizzbuzz_loop.js ... FizzBuzzのサンプル