Qiita
You are not logged in to any team
Log in to Qiita:Team...
Community
List of all usersList of all organizatioinsAdvent Calendar
Qiitadon (β)
Community GuidelineHow to write good articles
Sign upLog in
1473681608 @uehaj
Edited at
WebAssembly Advent Calendar 2017 Day 11

WebAssemblyへのコンパイラ言語を簡単に実装

JavaScriptpegjsWebAssemblybrainfuckwasm

後入りですみませんが、WebAssemblyアドベントカレンダー未投稿のところ埋めさせて頂きます。

本記事では、WebAssemblyをターゲットとするコンパイラ処理系を実装します。

方針

WebAssemblyへのコンパイル言語処理系を最も簡単に 1実装するための方針は以下のとおり。

  • 言語は「コンパイラがなるべく小さくなる言語として考案」されたBrainf*ckを採用
  • 文法はPEG(Parsing Expression Grammar)で記述し、生成系PEG.jsでパーサを実行時に生成する
  • WebAssemblyコード生成では文字列でWAST形式を生成し、wast2wasm2で変換する(直接WASMを生成しない)。またEmscriptenやbinaryenは使用しない
  • WASTの表現ではflat形式ではなくs-expression形式を使用する
  • ブラウザ上ではなくNode上で実行する。なのでWebAssemblyを実行できるバージョンのNode.jsが必要。Node8以降では普通に実行できる

コードはこちらに。
NPMに登録されているので以下で実行できます。

% cat hello.bf
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.

% npx bf-compiler-webassembly hello.bf
npx: 5個のパッケージを1.592秒でインストールしました。
Hello, world!

% npx bf-compiler-webassembly -e '+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.'
npx: 5個のパッケージを2.06秒でインストールしました。
Hello, world!

% npx bf-compiler-webassembly --help
npx: 5個のパッケージを1.506秒でインストールしました。

  Usage: bf-compiler-webassembly [options] [file...]


  Options:

    -V, --version         output the version number
    -e,--script [script]  run script from command line
    -v,--verbose          verbose output
    -h, --help            output usage information


  Examples:

    $ npx bf-compiler-webassembly -e "+++"
    $ npx bf-compiler-webassembly hello.bf

実行例

bf2.mov.gif

以降、コードの説明をしていきます。

全体の流れ

driver.js
// compile from string
async function compileAndRunString(bfSource, opts) {
  const bfAst = bfParser.parse(bfSource, opts);
  const wast = bfCompiler.compile(bfAst, opts);
  const wasm = await wast2wasm.convert(wast, opts);
  return wasmRuner.run(wasm, opts);
}

driver.jsでコンパイル・実行の全体の流れを制御しています。以下の順で処理が実行されます。

  1. Brainf*ckコードの構文解析(パース)、ASTの生成。(bfParser.parse())
  2. ASTをwastに変換する(コード生成)。(bfCompiler.compile())
  3. wast形式をwasmに変換するさらに内部形式にコンパイル。(wast2wasm.convert())
  4. wasmコードを実行する。(wasmRunner.run())

それぞれ以下のように処理ごとにモジュール化しています。

driver.js
const bfParser = require('./bfParser');
const bfCompiler = require('./bfCompiler');
const wast2wasm = require('./wast2wasm');
const wasmRuner = require('./wasmRunner');

パーサ

PEG.jsでASTを生成します。

bfParser.js
const peg = require('pegjs');

const syntax = `
code = (normal_insn / block_insn / otherchar) *

normal_insn = ch:[><+-.,] { return ch }
block_insn = '[' brk:block ']' { return brk  }

block = cod:code {
  return cod;
}

otherchar = [^><+-.,\\[\\]] {
  return undefined
}
`;

const parser = peg.generate(syntax);

syntaxという文字列変数にPEG文法を与えてpeg.generate()でパーサを生成しています。
PEGでBNFのように構文を表現します。PEGでは構文解析と字句解析を分ける必要がありません。

bfParser.js
function parse(bfSource, opts) {
  const bfAst = parser.parse(bfSource);
  return bfAst;
}

生成したパーサにBrainf*ckのコードを与えて抽象構文木を返します。
PEGのJS実装であるPEG.jsが生成するパーサは、JSONで抽象構文木を返してくれます。
抽象構文木(という程のものでもありませんが)では、[と]で表現されるブロックは配列、それ以外はその文字の配列が返ります。

,[->+<]>+.

であれば、以下のようなJSONが返ります。

[ ',', [ '-', '>', '+', '<' ], '>', '+', '.' ]

[と]の対応は静的にコンパイル時チェックされることになります。

コード生成

抽象構文木を再帰的に辿ってWAST形式テキストを生成します。
先のBFコードは以下を生成します。

(module
  (func $getchar (import "imports" "getchar") (result i32))
  (func $putchar (import "imports" "putchar") (param i32))
  (memory $0 (export "memory") 1 1)

  (func (export "main") (local $ptr i32)
    (i32.store8 (get_local $ptr) (call $getchar)) ;; ,
    (block ;; [
      (loop
        (br_if 1 (i32.eqz (i32.load8_s (get_local $ptr))))
        (i32.store8 (get_local $ptr) (i32.sub (i32.load8_s (get_local $ptr)) (i32.const 1))) ;; -
        (set_local $ptr (i32.add (get_local $ptr) (i32.const 1))) ;; >
        (i32.store8 (get_local $ptr) (i32.add (i32.load8_s (get_local $ptr)) (i32.const 1))) ;; +
        (set_local $ptr (i32.sub (get_local $ptr) (i32.const 1))) ;; <
        (br 0)
      )
    ) ;; ]
    (set_local $ptr (i32.add (get_local $ptr) (i32.const 1))) ;; >
    (i32.store8 (get_local $ptr) (i32.add (i32.load8_s (get_local $ptr)) (i32.const 1))) ;; +
    (i32.load8_s (get_local $ptr)) (call $putchar) ;; .
  )
)
)

生成コードの説明

冒頭のいくつかの宣言

  (func $getchar (import "imports" "getchar") (result i32))
  (func $putchar (import "imports" "putchar") (param i32))

BFでの入出力を行うためのgetchar、putcharを外部JS関数として供給します。

  (memory $0 (export "memory") 1 1)

memoryでWebAssemby側でメモリ領域をリニアメモリとして確保。サイズと最大サイズをブロックサイズで指定。ここではいずれも1ブロック(64 KiB)を指定。

コード本体の定義

  (func (export "main") (local $ptr i32)

JSから呼べる関数としてWebAssembly関数をmainという名前でexport。

以降、関数本体となる実行命令の説明をしていきます。

'['と']'に対応するコード

    (block ;; [
      (loop
        (br_if 1 (i32.eqz (i32.load8_s (get_local $ptr))))
:
        (br 0)
      )
    ) ;; ]

whileループに相当する[〜]のブロックがコンパイルされたコード。ptrの内容がゼロならループを抜け(br_if 1)、loop末尾でloopの先頭にジャンプ(br 0)しています。brはbranchの略で、分岐もしくは条件付き分岐命令です。
wast2wasmではなぜかbrの飛び先をラベルで指定できなかったので、ネストレベルの相対指定3で飛び先を指定しています。「0」は最内周のloopもしくはblock、「1」は1段外側のレベルのloopもしくはblockを意味します。ラベルを管理する必要がないので、ここでは好都合です。

brやbr_ifのジャンプの動作は、指定したネストレベルに対応するものがloopであればloop冒頭にジャンプ(ここではwhileループ内でのcontinue文の動作)、blockであればblockの末尾にジャンプ(ここではwhileループのbreak)をします。

'+'と'-'に対応するコード

(i32.store8 (get_local $ptr) (i32.add (i32.load8_s (get_local $ptr)) (i32.const 1))) ;; +
(i32.store8 (get_local $ptr) (i32.sub (i32.load8_s (get_local $ptr)) (i32.const 1))) ;; -

$ptrで間接参照したリニアメモリの指す先の内容を1バイトloadして加減算してリニアメモリにstoreし戻します。i32.load8は拡幅になるので符号付きと無しがあり、この場合は符号付きで処理するように注意します。

'>'と'<'に対応するコード

(set_local $ptr (i32.add (get_local $ptr) (i32.const 1))) ;; >
(set_local $ptr (i32.sub (get_local $ptr) (i32.const 1))) ;; <

$ptrを増減させます。

'.'と','に対応するコード

(i32.load8_s (get_local $ptr)) (call $putchar) ;; .
(i32.store8 (get_local $ptr) (call $getchar)) ;; ,

importsで宣言されているJS関数を指定して呼び出します。ここで用意したのはいずれも同期的な関数です。非同期関数を呼ぶ際にはコールバック関数を指定する必要がありますが、ここでは簡単さを優先するために同期関数で以下のように実装しておいたものを呼び出しています。

wast2wasm.js
const readlineSync = require('readline-sync');
 :
function putchar(ch) {
  process.stdout.write(String.fromCharCode(ch));
}

let buf = '';
function getchar() {
  if (buf === '') {
    buf = buf + readlineSync.question() + '\n';
  }
  const result = buf.charCodeAt(0);
  buf = buf.substring(1);
  return result;
}

WAST→WASM変換

wast2wasm.js
async function convert(wasmTextCode, opts) {
  const wasm = await wast2wasm(wasmTextCode, true);
  const uint8array = wasm.buffer;
  const results = await WebAssembly.instantiate(uint8array, {
    imports: {
      getchar,
      putchar,
    },
  });
  return results.instance;

wastをwasmに変換した上で、WebAssembly.instantiate()で実際のコンパイルを行います。通常のWebAssembly実行であれば、wasm生成までは事前コンパイルでできていて、wasmのロードから始まるところ。

実行

wastRunner.js
'use strict';

function run(wasm, opts) {
  const result = wasm.exports.main();
  if (opts.verbose || process.env.NODE_ENV === 'debug') {
    const memory = new Uint8Array(wasm.exports.memory.buffer);
    console.log(memory);
  }
  return result;
}

exportされた関数(ここではmainで固定)を呼び出すだけです。

コマンドラインの処理

commanderを使用して簡潔に。

index.js
const program = require('commander');
const driver = require('../lib/driver');

function main(argv) {
  program
    .version('0.1.0')
    .option('-e,--script [script]', 'run script from command line')
    .option('-v,--verbose', 'verbose output')
    .arguments('[file...]', 'Brainf*ck file')
    .action(function(files, opts) {
      for (const file of files) {
        driver
          .compileAndRunFile(file, { verbose: opts.verbose })
          .catch(e => console.log('error:' + e));
      }
    })
    .on('--help', function() {
      console.log(`

  Examples:

    $ npx bf-compiler-webassembly -e "+++"
    $ npx bf-compiler-webassembly hello.bf

`);
    })
    .parse(argv);

  // for -e,--script option
  if (program.script) {
    driver
      .compileAndRunString(program.script, { verbose: program.verbose })
      .catch(e => console.log('error:' + e));
  } else {
    program.args.length !== 0 || program.help();
  }
}

main(process.argv);

WASM所感

スタックマシンで変数も使え命令の対称性も高くわかりやすい。JVMのようにクラスベースではなく関数ベースであることが様々な効果を発揮しすっきりしている。
呼び出しスタックを(引数やローカル変数を通じないで)直接見ることも書くこともできないのでスタック上をバッファオーバーフローで書き壊したり、リターンアドレス書き換えてコード呼び出される攻撃について安全。ヒープは別問題だが、間接参照呼び出しはtableという構造のインデックスのみで実現されるので列挙される関数の範囲に限定されるので比較的安全。引数や返り値の型や個数を指定する必要があり、軽くバイトコードベリファイがなされスタックズレなどは防止される。

WAST形式所感

WAST形式のS-expressionはLispっぽいですが、バイナリフォーマットとしてのWASMでの実際のバイト配置としてはFORTHのような逆ポーランド記法であり、これに対応するflat形式という記法もあるそうです(併用もできる?)。引数の評価順が決まっているのでS-Expressionとflat形式は1対1対応です。

最適化

していませんが、本来なら種々の最適化を実行することができるでしょう。たとえば複数連続する+や-、>や<をまとめて計算するなどは効果的だろうし、BFの個々の命令をテーブルジャンプとか間接参照にすることも考えられます。

まとめ

  • WebAssemblyはコンパイラの勉強のターゲットとしてモチベーションが高まるし、しきいも低いのでぜひどうぞ。
  • ただし現時点ではドキュメント不足、今後仕様が変化していくだろう、という予測もできます。
  • PEG.jsは便利。

  1. 主観です。 ↩

  2. wast2wabtはたぶんWABT(The WebAssembly Binary Toolkit)からEmscriptenか何かでJSに変換されている。 ↩

  3. ネストレベルの外側向きの相対指定であることがドキュメント上読み取れず、ものすごく苦労した。 ↩

Report article

Help us understand the problem. What is going on with this item?


Feedback

We don't reply to any feedback.
If you need help with Qiita, please send a support request from here.