This is partially true, but the standard text format also allows the instructions to be nested as S-expressions, for example:
(i32.add
(i32.const 0)
(i32.const 1))
Many projects, including the official spec test suite and the Binaryen test suite, primarily use this format.
> IIRC early pre-release-versions of WASM were entirely built from S-expressions and as a 'pure stack machine' (I may remember wrong though).
Yes, the S-expressions predate WebAssembly even being a stack machine. Originally the design was that it encoded an AST, so the folded S-expression format was the only option.
There was a lot of discussion back in the day (before my time) about creating a better text format, but no one could agree on what it should be, so they just defaulted to the S-expression idea and focused on getting WebAssembly out the door.
Andy jests, but I would actually like to add nominal types to Wasm (along with type imports to make them usable). No proposal yet, but maybe later this year.
This blog post mentions that you can kind of emulate nominal types by putting all your types in one rec group, but then it brushes that off as inferior to using exceptions. (Which is hilarious! Good work, Andy.) What it doesn’t make clear is that people actually use this rec group trick in practice. There are two ways to do it: you can put literally all your types in one rec group, or you can emit minimal rec groups with additional “brand types” that serve no purpose but to ensure the groups have different structures. The former solution is better for code size when the entire application is one module, but the latter solution is better if there are multiple modules involved. You don’t want to repeat every type definition in every module, and using smaller rec groups lets you define only the types that are (transitively) used in each module.
The Binaryen optimizer has to ensure that it does not accidentally give distinct types the same structural identity because that would generally be observable by casts. Most of its type optimizations therefore put all the types in one rec group. However, it does have a type merging optimization that takes the casts into account[0]. That optimization is fun because it reuses the DFA minimization code from the original equirecursive type system we were experimenting with for Wasm GC. We also have a rec group minimization optimization[1] that creates minimal rec groups (by finding strongly connected components of the type definition graph), then ensures the types remain distinct first by using different permutations of the types within a rec group and then only as necessary by adding brand types.
I'm using WASM via Emscripten almost since the beginning but have never encountered 'rec' or 'struct' (or generally types beyond integers and floats). Why would WASM even need to know how structs are composed internally, instead of 'dissolving' them at compile time into offsets? Was this stuff coming in via the GC feature?
I've been learning to use WebAssembly directly, by hand-writing the Lisp-like assembly text, and also compiling C to Wasm without Emscripten or LLVM. It's given me a deeper appreciation for the original specification, version 1. Its technical design is a solid foundation, a lot of good thought went into it: Briging the Web Up to Speed With WebAssembly - https://github.com/WebAssembly/spec/raw/refs/tags/wg-1.0/pap...
In a way it's a complete instruction set and bytecode format, that could have been frozen in time and still be a useful addition to x86, ARM, RISC-V. It's great that the Wasm v1 specs is small enough for various implementations to arise. There are Wasm interpreters written in C, Zig, Go, Rust, as well as Wasm to C compiler, disassembler, little languages that compile to Wasm.. I see great value in that simplicity and smallness, it contributes to easier cross-platform and cross-language compatibility.
That's why newer features in the specs after v1, like garbage collection, components, interfaces, feel like they're higher-level abstractions that are not so relevant for my use case. Some feel like they could be developed outside of Wasm specs, like you said, dissolved at compile time to existing primitives. I'm guessing much of the benefit is for integrating with Rust ecosystem, and perhaps other languages gradually.
Yes, this is all part of Wasm GC. WebAssembly needs to know the structures of heap objects so that a GC can trace them and also to preserve type safety when accessing them. Treating the heap objects as uninterpreted bags of bytes wouldn't have worked because so many of their fields are references, which must remain opaque in Wasm.
The end of the related work section cites both wasm-smith and the Binaryen fuzzer (https://github.com/WebAssembly/binaryen/wiki/Fuzzing) and says, "They both provide a fuzzer that turns a stream of bytes into a WebAssembly module in order to test implementations. Their fuzzers always generate semantically valid test cases, but lack the targeting and tuning that Xsmith provides."
I look forward to reading more about how they do the targeting and tuning.
Hi! Author here. Xsmith provides a lot of ways to tune the choices it makes during program generation. By far the easiest, and the one used a lot in Wasmlike (the fuzzer in this thesis), is adjusting the weight of each AST node. It doesn’t just have to be a static weight though! It can be a function of any number of attributes present in the AST so far when that choice is made!
For example, to get a nice spread of function sizes, Wasmlike limits the AST depth of new functions based on how many were generated so far. If the maximum depth isn’t limited, program size and generation time explodes. If the depth is just a simple continuation of where the function was first called from, the resulting program will have a ridiculous number of one liner functions without any medium sized ones.
Do you do swarm testing, where you random disable some fraction of the kinds of choices for generating program fragments before generating the AST? If so, how did that help?
Come to think of it, there is something similar that Xsmith can do with parametric randomness, where it can change just one small choice in the chain of decisions that made a random program. It’s a library developed by a previous masters student at the research lab, and it’s called Clotho: https://docs.racket-lang.org/clotho/index.html.
The idea is to enable feedback directed fuzzing for a senantically valid random program generator. I believe that adding this to the Wasm fuzzer is the ‘next step’ in the ongoing research.
So not quite swarm testing, but a bit closer in terms of focused fuzzing instead of a shotgun approach.
Short answer: no. The focus was on always generating semantically valid programs. That said, there is a lot of work on avoiding nondeterministic or undefined behavior, like division by zero or negative square roots.
There are also a few ‘feature’ flags to enable/disable things like floating point operations in the case that it would affect results, but that never actually came up in testing, and the tests runs we did used roughly the same configurations.
The GC proposal recently moved to phase 2 and has a lot of momentum. Teams working on compiling Java, Kotlin, and Dart to Wasm are closely involved in the standardization effort and implementations are under way in V8 and other Web engines. Right now the bulk of the effort on the standardization side is in tweaking the instruction set to simplify it and improve performance and on the implementation side the focus is heavily on optimizations, both offline and in the engines.
The simplest way to get involved is to start attending the biweekly standardization meetings. The agendas are organized here: https://github.com/WebAssembly/meetings
To attend the meetings, first join the W3C WebAssembly Community Group here: https://www.w3.org/groups/cg/webassembly, then email the CG chairs at webassembly-cg-chair@chromium.org to ask for an invite.
From there you'll get a sense of who folks are so you can pair names with faces when contributing to the various proposal discussions on the many proposal repos listed here: https://github.com/webassembly/proposals.
To get a sense of how things are run and decided, read the process documents here: https://github.com/WebAssembly/meetings/tree/main/process. The TL;DR is that the community group and its subgroups decide everything by consensus via votes during the meetings.
One of the precursors of WebAssembly was Portable Native Client (PNaCl)[1], which did use a frozen subset of LLVM IR as its program representation. But LLVM IR was designed to be a compiler IR, not a program binary format. WebAssembly was specifically designed for the Web use case, and unlike LLVM IR it supports streaming compilation and requires structured control flow, which makes it easier and less risky to implement in JS engines.
Other commenters are correct that LLVM IR has more information in it than WebAssembly, but that is working as intended. The idea is that toolchains will do the heavy optimization work so that WebAssembly engines can be simpler and just do the final code generation.
Yes, although part of the fun the demo is that the LLVM tools are themselves running in the browser. Note that the demo is from 2015, so it predates WebAssembly.
I am currently working on multivalue in both LLVM and Binaryen. Watch for celebratory tweets when I finish ;)
Rust will be able to benefit immediately once LLVM has multivalue function support since they use their own ABI internally. But C, C++, and Rust extern functions will not be able to benefit until we additionally define a new C ABI that takes advantage of multivalue returns.
It's also worth noting that multivalue blocks only bring a code size win of a couple percent on real wasm modules, so those are much lower priority.
WebAssembly features are all different in how difficult they are to add to the specification, engines, and tools. Multivalue is unique in that it is trivial for the spec and for engines, but is extremely difficult to implement in tools.
> IIRC early pre-release-versions of WASM were entirely built from S-expressions and as a 'pure stack machine' (I may remember wrong though).
Yes, the S-expressions predate WebAssembly even being a stack machine. Originally the design was that it encoded an AST, so the folded S-expression format was the only option.
There was a lot of discussion back in the day (before my time) about creating a better text format, but no one could agree on what it should be, so they just defaulted to the S-expression idea and focused on getting WebAssembly out the door.