Hacker News new | ask | show | jobs
by gumby 1478 days ago
Great work! You write,

> …wasm has a few poor decisions in its design that make it less-than-conducive to being a target for Common Lisp…

Could you say a bit more about those design decisions?

4 comments

Not OP, but as a fellow Lisp-on-wasm developer one problem is that the current release doesn't support tail call elimination. There's a proposal for it (a tail_call instruction), and Chrome has implemented it, but the Firefox/Spidermonkey team hasn't prioritized it, so it's sat for a couple years. At least two implementations (maybe two browser implementations? I don't recall) are needed for standardization, so things remain.

You know, I wonder how seriously I could be taken if I duck-taped a wasm-capable browser together out of Servo and Wasmtime to make a second implementation and push it forwards...

There is no branch instruction at all?
There is, but all control flow is structured and the argument/return address stack is out of your control. You have blocks, loops, and if/else statements. The behavior of a branch instruction differs based on context - in a block, it jumps out of the block, in a loop it jumps to the beginning of the loop.

If you really wanted full tail-call behavior, you would either have to compile every function into the same mega-function in a loop and have some sort of if/else tree, or use trampolines (which would additionally require either storing parameters in memory somewhere or using the same type signature for all functions, since function calls are typed).

Overall, it's not a super great situation for true tail-call elimination. For now, I've implemented limited tail-call elimination for single-function recursive calls (transforming them into an in-function loop), and that's patched things up enough for me to continue working for now until I either need to come up with an optimized trampoline or the tail_call instruction finally gets standardized.

Thanks, that is pretty dreadful.
The spec people have been very rude to the Lisp people every time something has been brought up. I'm not going to look up everything that's been written, but here's an example:

https://sourceforge.net/p/sbcl/mailman/message/34821303/

I wouldn't call their responses rude, but they are somewhat dismissive.
I believe there are challenges related to nonlocal transfer of control, as well as multiple return values. More damningly, if I recall correctly, lisp implementors were consulted and their feedback ignored (just like apl implementors with .net, back in the latter's infancy).
I think a major limitation is that a WebAssembly module can’t run dynamically generated code, which is a huge part of typical Common Lisp implementations.
I was thinking about this, and one solution that came to my mind was serializing the heap into a temporary image and restarting the environment from an updated Wasm module with new code. This would also collect all garbage at the point of transitioning to the new code. You might need to be very careful to do this reasonably quickly, but in principle I don't see why this wouldn't work. The idea came to me when I was thinking about how an interactive-but-native-speed Oberon environment could be implemented in Wasm.
You could certainly generate a new Wasm module on the fly and then execute it from Javascript. Linking and sharing of memory should be possible.

Pyodide can dynamically load libraries that are separate Wasm modules so it is worth checking out how that works.

IIRC inter-module calls are more expensive than intra-module calls though.

WASM also doesn't allow for functions with variadic return counts.

"a WebAssembly module can’t run dynamically generated code"

Why does it have that limitation, and is there any hope that it will someday be overcome?

On your computer, heap, stack, code, and global data all share the same address space. On the WASM virtual machine, only heap and global data share the same address space. Code and stack are abstracted away by the machine.

It was designed to support C-like languages, so you can do the equivalent of loading a DLL (or dynamic shared object). However in Lisp it is not unusual to compile just one function at a time. It's definitely possible to create a DLL for each function and load each DLL, but it requires a completely different architecture than most Lisp implementations use (in which, when you compile a function, it just writes the machine code to the heap).

There are similar impedance mismatches with so-called W^X systems (where you are disallowed from having a page be both (W)ritable and e(X)ecutable.

Thanks for the only compliment in the thread! I appreciate it, especially given I've been such a fan of your writing and life for such a long time.

I think that the people who responded to you covered much of it, but you can find more by doing a web search for it. I'd find you links myself, but it's early in the morning and I'm a little tired.