Interpreter: Inconsistencies in s-expression format

[jonas-db]

In the example 'simple' (https://cdn.rawgit.com/WebAssembly/wabt/e528a622caa77702209bf0c3654ca78456c41a52/demo/index.html) there is a prefix notation of operators:

(module
  (func $addTwo (param i32 i32) (result i32)
    (i32.add
      (get_local 0)
      (get_local 1)))
  (export "addTwo" (func $addTwo)))

However, when i convert a .wasm to a .wast with wasm -d module.wasm -o module.wast, i see code snippets where this is not the case:

      (get_local 0)
      (i32.const 44)
      (i32.add)

This makes parsing such s-based expressions hard since i32.add is expected to have 2 operands. This is also the case with other operators.

[binji]

Yes, the s-expression format can be "folded" or unfolded. Many have found that the folded format (pre-order) is easier to read than the unfolded format (post-order). Ultimately, the binary format is expressed as a stack machine, so the folded format is just sugar.

If you look at the grammar for the spec or wabt parsers, you'll see that for "plain instructions", the behavior is just to swap the order of the instruction with all the following child expressions. In other words, (X (A) (B) (C) ...) is sugar for (A) (B) (C) ... (X).

So for example,

All of these:

(i32.add (i32.const 1) (i32.const 2) (i32.const 3))
(i32.const 1) (i32.add (i32.const 2) (i32.const 3))
(i32.const 1) (i32.const 2) (i32.add (i32.const 3))
(i32.const 1) (i32.const 2) (i32.const 3) (i32.add)

Are sugar for:

i32.const 1
i32.const 2
i32.const 3
i32.add

Even though i32.add only has only two operands, all of these cases are valid in the s-expression format.

[jonas-db]

@binji I see and understand that this is syntactical sugar and boils down to instructions for the stack machine, but i don't really see how the 2nd and 3th would be correct and produce the result 6.

Anyways, can you think of anything that could cause a problem when I would convert the "plain instructions" to "real" s-expression instructions and interpret these, as opposed to directly interpreting the binary format (besides the unnecessary step)?

[binji]

I see and understand that this is syntactical sugar and boils down to instructions for the stack machine, but i don't really see how the 2nd and 3th would be correct and produce the result 6.

Sorry, I wasn't clear. None of these will produce the output 6 in isolation, in fact the function:

(func (result i32)
  i32.const 1
  i32.const 2
  i32.const 3
  i32.add)

Is not valid because it leaves two values on the stack: 1 and 5. You'd have to have an additional i32.add at the end for it to be valid.

Anyways, can you think of anything that could cause a problem when I would convert the "plain instructions" to "real" s-expression instructions and interpret these, as opposed to directly interpreting the binary format (besides the unnecessary step)?

You can convert from the "flat" format (no folding) to a folded format in most cases, and in fact this is what binaryen does, AFAIK. The stack machine is more expressive, though, as something like this:

i32.const 1  ;; first operand of i32.add
i32.const 2  ;; first operand of i32.store
i32.const 3  ;; second operand of i32.store
i32.store
i32.const 4  ;; second operand of i32.add
i32.addk

Cannot be folded into a two operand i32.add directly. Binaryen converts it to this:

  (func $0 (result i32)
    (local $0 i32)
    (i32.add
      (block i32
        (set_local $0
          (i32.const 1)
        )
        (i32.store
          (i32.const 2)
          (i32.const 3)
        )
        (get_local $0)
      )
      (i32.const 4)
    )
  )

[rossberg]

@jonas-db, in addition to @binji's explanation also note that we want to generalise Wasm to multiple return values soon. Once we do, the type of an operator does no longer coincide with the syntactic arity of its application. For example, imagine a function $f that returns two i32 values. Then

(i32.add (call $f))

is an expression you want to be able to write.

[rossberg]

Closing this, since question has been answered / working as intended. There now is PR #471 for specifying the text format.