WAT(WebAssembly Text Format)のスタック

webassembly text format の文法について書きます

いくつかの書き方

Wasmはスタック構造を持っています。また、S式のように書く方法もあります。
Additionリンク先でどっちも実行できます

• スタックマシンっぽい書き方

(module
  (import "console" "log" (func $log (param i32)))
  (func $main
    ;; load `10` and `3` onto the stack
    i32.const 10
    i32.const 3

    i32.add ;; add up both numbers
    call $log ;; log the result
  )
  (start $main)
)

• S式的な書き方

(module
  (import "console" "log" (func $log (param i32)))
  (func $main
    (i32.add (i32.const 10) (i32.const 3))
    ;; add up both numbers
    call $log ;; log the result
  )
  (start $main)
)

今回はスタックマシン的な書き方について話してみます。

書いてみる

例えば、

def calc(a:i32,b:i32 ,c:i32) -> i32:
    return a - b * c

みたいな計算をwasmに変換したいとしましょう。

まず1つずつ追っていきましょう！

最初に、a - b * cという式について見ていきましょう。これらの計算の順番をわかりやすくするためにまずは括弧をつけてみます。そうすると...

a - (b * c)

掛け算が先なのでこうなります。

次に演算子を2つの引数をとる関数のように捉えて、書き直してみます。そうすると

(- a (* b c))

S式になりました！

そして、すこし順番を変えます。今は(<関数名> <引数1> <引数2>)の順番ですがこれを
(<引数1> <引数2> <関数名>)という順番に並び替えてみます。すると...

(a (b c *) -)

そして、これを先頭から順にwasmの言葉に変換すると

local.get $a ;; (a
local.get $b ;; (b
local.get $c ;;  c
i32.mul      ;;  *)
i32.sub      ;;  -)

そしたらあとは、moduleやfuncの書き方にしたがって必要なものを付け加えて

(module
  (func $calc
    ;; 引数
    (param $a i32)
    (param $b i32)
    (param $c i32)

    ;; 返り値の型
    (result i32)

    local.get $a ;; (a
    local.get $b ;; (b
    local.get $c ;;  c
    i32.mul      ;;  *)
    i32.sub      ;;  -)
    return 
  )
)

完成です！

何をしたのか

スタックデータは最後に入れたデータを一番最初に取り出せるデータ構造のことです。
イメージとしては、よく、積み重ねた皿に例えられたりします。

先程何をしたのかというと、一般的な数式を、RPN(Reverse Polish Notation:逆ポーランド記法)に置き換える操作をしました。普段の慣れた書き方からすると不思議に見える書き方かもしれないですが、RPNは、スタック構造との相性がとてもいいです。
RPNの順番でwasmに変換していけば、期待した計算を実行できます。

もう一度コードを見てみます

(module
  (func $calc
    ;; 引数
    (param $a i32)
    (param $b i32)
    (param $c i32)

    ;; 返り値の型
    (result i32)

    local.get $a ;; [a]         <- $aの内容をスタックに積む(#1)
    local.get $b ;; [a][b]      <- $bの内容をスタックに積む(#2)
    local.get $c ;; [a][b][c]   <- $cの内容をスタックに積む(#3)
    i32.mul      ;; [a][b*c]    <- スタックの上2つのデータを掛け算する(#4)
    i32.sub      ;; [a-[b*c]]   <- スタックの上2つのデータを引き算する(#5)
    return 
  )
)

以下はスタックの状態になります。(#n)はプログラム中のコメント注釈と対応します。

                        +-----+
                        |  c  |
            +-----+     +-----+    +---------+ 
        ->  |  b  | ->  |  b  | -> |  b * c  | ->
+-----+     +-----+     +-----+    +---------+    +-----------+
|  a  |     |  a  |     |  a  |    |    a    |    | a - b * c |
+-----+     +-----+     +-----+    +---------+    +-----------+
   #1          #2          #3           #4              #5

上の図から、なんとなくスタックデータがどんな感じで変化していくかがわかると思います。
スタックにデータを積むことと、上の２つのデータに対して演算する操作だけで、最初に実現しようとしていた計算ができました。

これらの概念をやんわりでも理解して、wasmの命令がスタックに対してどんな動作を要請をするのか想像できると見通しが良くなる気がします。

簡単なプログラムは以下に貼ったmozillaのリンクで簡単に実行することができてとても便利です。

普段から参考にしているリンク

• WebAssembly instruction reference
  mozillaのはすごくわかりやすい。自分で書いてその場で実行することもできる。
• wasm spec
  仕様は、難しめ。最初に読むと爆発するかも
• wat2wasm
  watをwasmにコンパイルできる。wabtを自分の環境にinstallしたくない場合に使えそう