Learning Wasm

2025-03-17, then 2025-06-08

I wanted to try writing wasm manually (wat format). I then wanted to try generating wasm programatically (wat format).

1 Lox test code#

Since I had been reading Crafting Interpreters where I wrote an interpreter for a language called Lox, I decided to try manually translating my Lox test code into wasm. Here’s the Lox:

print "# Testing scope";
var a = 5;
print "outer a";
print a;
{
  var a = 10;
  print "inner a";
  print a;
}
print "outer a";
print a;

print "# Testing expressions";
print true;
print 2 + 1;
print !((3 + 5 / 10) == 3.5);

print "# Testing if statements";
if (false) {
  print "N true";
} else {
  print "Y false";
}
if (true) {
  print "Y true";
}

print "# Testing logical operators";
print "hi" or 2; // "hi"
print "hi" and 2; // 2
print nil or "yeh"; // "yeh"
print nil or nil; // nil

print "# Testing while loops";
var i = 3;
while (i > 0) {
  print i;
  i = i - 1;
}

print "# Testing for loops, Fibonacci sequence";
var a = 0;
var temp;
for (var b = 1; a < 10000; b = temp + b) {
  print a;
  temp = a;
  a = b;
}

and here’s the wat I wrote manually:

(module
  (import "js" "memory" (memory $heap 1))
  (import "print" "i32" (func $print_i32 (param i32)))
  (import "print" "str" (func $print_str (param i32)))
  
  (func $add (param $a i32) (param $b i32) (result i32)
    (local.get $a)
    (local.get $b)
    (i32.add)
  )

  (func $main
    (local $a i32)
    (local $b i32)
    (local $a_inner i32)
    (local $i i32)
    (local $temp i32)
    
    (local.set $a (i32.const 5))        ;; var a = 5;
    (i32.const 0)                
    (call $print_str)                   ;; print "outer a";
    (local.get $a)               
    (call $print_i32)                   ;; print a;
    (local.set $a_inner (i32.const 10)) ;; var a = 10;
    (i32.const 100)
    (call $print_str)                   ;; print "inner a";
    (local.get $a_inner)
    (call $print_i32)                   ;; print a;
    (i32.const 0)
    (call $print_str)                   ;; print "outer a";
    (local.get $a)
    (call $print_i32)                   ;; print a;

    (i32.const 200)
    (call $print_str)                   ;; print "# Testing expressions";

    (i32.const 2)
    (i32.const 1)
    (i32.add)
    (call $print_i32)                   ;; print 2 + 1;

    (f32.const 3)
    (f32.const 5)
    (f32.const 10)
    (f32.div)                           ;; 5 / 10
    (f32.add)                           ;; 3 + 5 / 10
    (f32.const 3.5)
    (f32.eq)                            ;; (3 + 5 / 10) == 3.5
    (i32.eqz)                           ;; !((3 + 5 / 10) == 3.5)
    (call $print_i32)

    (i32.const 300)
    (call $print_str)                   ;; print "# Testing if statements";
    (i32.const 0)
    (if
      (then
      (i32.const 400)
      (call $print_str)
        )
        (else
      (i32.const 500)
      (call $print_str)
        )
    )
    (i32.const 1)
    (if
      (then
      (i32.const 600)
      (call $print_str)
        )
    )

    (i32.const 700)
    (call $print_str)                   ;; print "# Testing while loops"
    (local.set $i (i32.const 3))
    (block $while_1_end
      (loop $while_1_start
        (local.get $i)
        (i32.const 0)
        (i32.gt_s)                      ;; i > 0
        (i32.eqz)                       ;; invert
        (br_if $while_1_end)            ;; break if NOT true

        (local.get $i)
        (call $print_i32)

        (local.get $i)
        (i32.const 1)
        (i32.sub)
        (local.set $i)
        (br $while_1_start)
      )
    )

    (i32.const 800)
    (call $print_str)                   ;; print "# Testing for loops, Fibonacci sequence"
    (local.set $a (i32.const 0))
    (local.set $b (i32.const 1))
    (block $for_1_end
      (loop $for_1_start
        (local.get $a)
        (i32.const 10000)
        (i32.lt_s)                      ;; a < 10000
        (i32.eqz)                       ;; invert
        (br_if $for_1_end)              ;; break if NOT true

        (local.get $a)
        (call $print_i32)               ;; print a;
        (local.get $a)
        (local.set $temp)               ;; temp = a;
        (local.get $b)
        (local.set $a)                  ;; a = b;

        (local.get $temp)
        (local.get $b)
        (i32.add)
        (local.set $b)                  ;; b = temp + b
        (br $for_1_start)
      ))
  )

  (func $loop (param $seed i32) (param $N i32) (result i32)
    (local $i i32)
    (local.set $i (i32.const 0))
    (block $for_2_end
      (loop $for_2_start
        (local.get $i)    ;; test !(i < N)
        (local.get $N)
        (i32.ge_s)
        (br_if $for_2_end)

        (local.get $seed)
        (i32.const 1103515245)
        (i32.mul)
        (i32.const 12345)
        (i32.add)
        (i32.const 0x7fff)
        (i32.and)
        (local.set $seed) ;; seed = (a * seed + c) & m

        (local.get $i)
        (i32.const 1)
        (i32.add)
        (local.set $i)    ;; i++
        (br $for_2_start)
      )
    )
    (local.get $seed)
  )

  (func $assembly/index/main (param $seed i32) (param $N i32) (result i32)
    (local $i i32)
    i32.const 0
    local.set $i
    loop $for-loop|0
      local.get $i
      local.get $N
      i32.lt_s
      if
        i32.const 1103515245
        local.get $seed
        i32.mul
        i32.const 12345
        i32.add
        i32.const 32767
        i32.and
        local.set $seed
        local.get $i
        i32.const 1
        i32.add
        local.set $i
        br $for-loop|0
      end
    end
    local.get $seed
    return
  )

  (export "add" (func $add))
  (export "main" (func $main))
  (export "loop" (func $loop))
  (export "loop2" (func $assembly/index/main))

  ;; don't need this after all
  ;; (memory $stack 1)

  ;; NOTE: I make my strings NUL-terminated so I don't have to
  ;; write the length in the code
  (data (memory $heap) (i32.const 0) "outer a\00")
  (data (memory $heap) (i32.const 100) "inner a\00")
  (data (memory $heap) (i32.const 200) "# Testing expressions\00")
  (data (memory $heap) (i32.const 300) "# Testing if statements\00")
  (data (memory $heap) (i32.const 400) "N true\00")
  (data (memory $heap) (i32.const 500) "Y false\00")
  (data (memory $heap) (i32.const 600) "Y true\00")
  (data (memory $heap) (i32.const 700) "# Testing while loops\00")
  (data (memory $heap) (i32.const 800) "# Testing for loops, Fibonacci sequence\00")
)

Writing it out manually helped me understand what a compiler would do.

https://developer.mozilla.org/en-US/docs/WebAssembly/Guides/Understanding_the_text_format^[1] was useful
https://stanford-cs242.github.io/f18/lectures/04-1-webassembly-practice.html^[2] too
https://webassembly.github.io/spec/core/text/instructions.html^[3] has a list of all wasm instructions
https://developer.mozilla.org/en-US/docs/WebAssembly/Reference/Control_flow^[4]

Some things I don’t understand:

why (local.get 0) vs local.get 0, and similarly (i32.add) vs i32.add?
- “flat” vs “folded” formats, seems like folded allows nested subexpressions
- https://nishtahir.com/the-wasm-text-format/^[5] shows parentheses and then shows without parentheses
- some pages like https://developer.mozilla.org/en-US/docs/WebAssembly/Guides/Understanding_the_text_format^[6] show parentheses only sometimes — look at the logAllMemory function which uses both in the same function

other:

wasmtime can compile wasm into x86 assembly; I tried this on godbolt^[7]
the loop construct in wasm^[8] is more like do-while, so I need to turn while(a) { b } into if(a) do { b } while (a), or block Y { loop X { if (!a) break Y; b; branch X; } . After seeing the output of assemblyscript and wasm-opt, I see that it could instead be loop X { if (a) { b ; branch X; } }

Source: learning-wasm.js

2 Javascript vs Wasm#

I’m going to convert this js code to wasm:

function main(seed, N) {
    const m = 0x7fff;
    const a = 1103515245;
    const c = 12345;

    for (let i = 0; i < N; i++) {
        seed = (a * seed + c) & m;
    }
    return seed;
}

  (func $loop (param $seed i32) (param $N i32) (result i32)
    (local $i i32)
    (local.set $i (i32.const 0))
    (block $for_2_end
      (loop $for_2_start
        (local.get $i)    ;; test !(i < N)
        (local.get $N)
        (i32.ge_s)
        (br_if $for_2_end)

        (local.get $seed)
        (i32.const 1103515245)
        (i32.mul)
        (i32.const 12345)
        (i32.add)
        (i32.const 0x7fff)
        (i32.and)
        (local.set $seed) ;; seed = (a * seed + c) & m

        (local.get $i)
        (i32.const 1)
        (i32.add)
        (local.set $i)    ;; i++
        (br $for_2_start)
      )
    )
    (local.get $seed)
  )

I also tried AssemblyScript^[9]:

export function main(seed: i32, N: i32): i32 {
    const m: i32 = 0x7fff;
    const a: i32 = 1103515245;
    const c: i32 = 12345;

    for (let i = 0; i < N; i++) {
        seed = (a * seed + c) & m;
    }
    return seed;
}

which generated this wasm:

 (func $assembly/index/main (param $seed i32) (param $N i32) (result i32)
  (local $i i32)
  i32.const 0
  local.set $i
  loop $for-loop|0
   local.get $i
   local.get $N
   i32.lt_s
   if
    i32.const 1103515245
    local.get $seed
    i32.mul
    i32.const 12345
    i32.add
    i32.const 32767
    i32.and
    local.set $seed
    local.get $i
    i32.const 1
    i32.add
    local.set $i
    br $for-loop|0
   end
  end
  local.get $seed
  return
 )

and that ran in the same speed as my hand-written wasm, 725ms for js and 145ms for wasm in Firefox; 660ms for js and 145ms for wasm in Chrome. My test code doesn’t work in safari yet.

I also tried wasm2c and ran the c code (with optimizer on) on my machine, and it took 116ms, so wasm wasn’t much slower than native code.

3 Programatically generating wasm#

Since I had been reading Crafting Interpreters, I decided I could use my scanner and parser from there to compile some code to wasm. I decided to keep the scope small by only handling simple arithmetic expressions, and not full expressions, or statements, or declarations. I think this is enough to teach me what I want to know: how to dynamically construct wasm at run time, and run it.

this doesn’t handle parse errors

Expression:
Tokens:
Evaluated:

WAT text

wasm binary

Steps:

Lex: input text into tokens
Parse: tokens into reverse-polish, then immediately generate assembly instructions
Wrap the instructions into a module (WAT text format)
Compile the WAT to WASM (binary format), using the wat2wasm library^[10] (Apache v2 license) (their demo^[11])
Load the WASM module at run time
Import and run the compiled function

curl -O https://webassembly.github.io/wabt/demo/libwabt.js

1 Lox test code#

2 Javascript vs Wasm#

3 Programatically generating wasm#

Links