3 ms·

Nominal Types in WebAssembly

39 points by ingve 7mo ago

beepbooptheory 7mo ago
> field access is a bit odd; unlike structs which have struct.get, nominal types receive all their values via a catch handler. I know this is meant to be silly, and I am no expert, but I kinda do like this syntax. Its like shaking the struct and seeing what falls out.
tlively 7mo ago
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. [0]: https://github.com/WebAssembly/binaryen/blob/main/src/passes/TypeMerging.cpp https://github.com/WebAssembly/binaryen/blob/main/src/passes... [1]: https://github.com/WebAssembly/binaryen/blob/main/src/passes/MinimizeRecGroups.cpp https://github.com/WebAssembly/binaryen/blob/main/src/passes...
- flohofwoe 7mo ago
  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?
  - tlively 7mo ago
    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.
  - lioeters 7mo ago
    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/papers/pldi2017.pdf 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.
kjksf 7mo ago
Good lord. WebAssembly was sold as "portable assembly for the web". It's in the fricking name. Web. Assembly. Assembly for the web. It was supposed to solve the problem of: some computers run x86, some arm, we need something that is equivalent, but portable across different cpus What business is it for WebAssembly to know about complex types? What x86 instructions is there for `(type $t (struct i32))` ? Or doing garbage collection. We would be better off standardizing on a subset of x86 and writing translators to arm etc. Or standardize on arm and translate to x86. We know it can work. Apple did it with rosetta. Microsoft did it with Prism. I don't think WebAssembly implementation generate faster code than rosetta or prism. QEMU did it simply (albeit slowly). WebAssembly is becoming another JVM. It's not simple. It's not fast. It's not easy to use. But now we're stuck with it and the only path is to add and add and add.
- flohofwoe 7mo ago
  I guess you didn't read to the end? > Friends, as I am sure is abundantly clear, this is a troll post :)
- zffr 7mo ago
  > It's not fast. Not disagreeing with you, but here’s an article from Akamai about how using WASM can minimize cold startup time for serverless functions. https://www.akamai.com/blog/developers/build-serverless-functions-zero-cold-starts-webassembly-spin https://www.akamai.com/blog/developers/build-serverless-func...
- flohofwoe 7mo ago
  > It's not fast. My emulators here have roughly the same performance as the same code compiled as native executable (e.g. within around 5%) - this is mostly integer bit twiddling code. Unless you hand-optimize your code beyond what portable C provides (like manually tuned SIMD intrinsics), WASM code pretty much runs at native speed these days: https://floooh.github.io/tiny8bit/ https://floooh.github.io/tiny8bit/
- mavdol04 7mo ago
  I mean standardizing on an x86 subset would replace wasm's native portability with a kind of 'emulated' compatibility, and this is one of wasm's strengths. If we do that, non-x86 hardware(mobile etc.) will pay the translation tax. So, keeping Wasm agnostic makes more sense anyway.
rusakov-field 7mo ago
Not familiar with WebAssembly, but from the namesake was expecting the syntax to kind of resemble assembly. He is showing S-expressions ? That is its' syntax ? I am intrigued now.
- flohofwoe 7mo ago
  Real-world WAT (WASM text format) looks more like this (e.g. it looks like a 'structured assembly' type of thing): i32.const 27512 i32.load local.tee $var1 if i32.const 27404 i32.load local.get $var1 call_indirect (param i32) end S-expressions are only used outside such instruction blocks for the 'program-structure' (e.g. see: https://developer.mozilla.org/en-US/docs/WebAssembly/Reference/Variables/local https://developer.mozilla.org/en-US/docs/WebAssembly/Referen...). IIRC early pre-release-versions of WASM were entirely built from S-expressions and as a 'pure stack machine' (I may remember wrong though). To see what a complete WASM blob looks like in WAT format you can go here: https://floooh.github.io/sokol-html5/clear-sapp.html https://floooh.github.io/sokol-html5/clear-sapp.html, open the browser devtools, go to the 'Sources' tab and click the `clear-sapp.wasm` file).
  - tlively 7mo ago
    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.
elophanto_agent 7mo ago
[dead]

39 points by ingve 7mo ago

> field access is a bit odd; unlike structs which have struct.get, nominal types receive all their values via a catch handler. I know this is meant to be silly, and I am no expert, but I kinda do like this syntax. Its like shaking the struct and seeing what falls out.

tlively 7mo ago

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. [0]: https://github.com/WebAssembly/binaryen/blob/main/src/passes/TypeMerging.cpp https://github.com/WebAssembly/binaryen/blob/main/src/passes... [1]: https://github.com/WebAssembly/binaryen/blob/main/src/passes/MinimizeRecGroups.cpp https://github.com/WebAssembly/binaryen/blob/main/src/passes...

flohofwoe 7mo ago
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?
- tlively 7mo ago
  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.
- lioeters 7mo ago
  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/papers/pldi2017.pdf 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.

kjksf 7mo ago

Good lord. WebAssembly was sold as "portable assembly for the web". It's in the fricking name. Web. Assembly. Assembly for the web. It was supposed to solve the problem of: some computers run x86, some arm, we need something that is equivalent, but portable across different cpus What business is it for WebAssembly to know about complex types? What x86 instructions is there for `(type $t (struct i32))` ? Or doing garbage collection. We would be better off standardizing on a subset of x86 and writing translators to arm etc. Or standardize on arm and translate to x86. We know it can work. Apple did it with rosetta. Microsoft did it with Prism. I don't think WebAssembly implementation generate faster code than rosetta or prism. QEMU did it simply (albeit slowly). WebAssembly is becoming another JVM. It's not simple. It's not fast. It's not easy to use. But now we're stuck with it and the only path is to add and add and add.

flohofwoe 7mo ago
I guess you didn't read to the end? > Friends, as I am sure is abundantly clear, this is a troll post :)
zffr 7mo ago
> It's not fast. Not disagreeing with you, but here’s an article from Akamai about how using WASM can minimize cold startup time for serverless functions. https://www.akamai.com/blog/developers/build-serverless-functions-zero-cold-starts-webassembly-spin https://www.akamai.com/blog/developers/build-serverless-func...
flohofwoe 7mo ago
> It's not fast. My emulators here have roughly the same performance as the same code compiled as native executable (e.g. within around 5%) - this is mostly integer bit twiddling code. Unless you hand-optimize your code beyond what portable C provides (like manually tuned SIMD intrinsics), WASM code pretty much runs at native speed these days: https://floooh.github.io/tiny8bit/ https://floooh.github.io/tiny8bit/
mavdol04 7mo ago
I mean standardizing on an x86 subset would replace wasm's native portability with a kind of 'emulated' compatibility, and this is one of wasm's strengths. If we do that, non-x86 hardware(mobile etc.) will pay the translation tax. So, keeping Wasm agnostic makes more sense anyway.

rusakov-field 7mo ago

Not familiar with WebAssembly, but from the namesake was expecting the syntax to kind of resemble assembly. He is showing S-expressions ? That is its' syntax ? I am intrigued now.

flohofwoe 7mo ago
Real-world WAT (WASM text format) looks more like this (e.g. it looks like a 'structured assembly' type of thing): i32.const 27512 i32.load local.tee $var1 if i32.const 27404 i32.load local.get $var1 call_indirect (param i32) end S-expressions are only used outside such instruction blocks for the 'program-structure' (e.g. see: https://developer.mozilla.org/en-US/docs/WebAssembly/Reference/Variables/local https://developer.mozilla.org/en-US/docs/WebAssembly/Referen...). IIRC early pre-release-versions of WASM were entirely built from S-expressions and as a 'pure stack machine' (I may remember wrong though). To see what a complete WASM blob looks like in WAT format you can go here: https://floooh.github.io/sokol-html5/clear-sapp.html https://floooh.github.io/sokol-html5/clear-sapp.html, open the browser devtools, go to the 'Sources' tab and click the `clear-sapp.wasm` file).
- tlively 7mo ago
  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.

elophanto_agent 7mo ago

[dead]