Show HN: A an R7RS Scheme Implementation in WebAssembly | Hacker News Reader

Show HN: A an R7RS Scheme Implementation in WebAssembly

github.com

84 pointspacaro11 comments

When I say implemented in WebAssembly, I mean that I wrote it in WebAssembly Text format, not in another language and compiled to WebAssembly. Because the text format is extremely unfriendly, I did need to write a simple macro language on top of the text format.

WebAssembly permits stack inspection to the degree that you could fully implement call/cc? Java of course does not. This would seem to be a security risk.

No. I use continuation passing and a trampoline in my eval core. This allows all sorts of manipulation of what would be the stack in a recursive model, call/cc exception-with-handler dynamic-wind they're all operations on continuation stacks

I don't do formal continuation passing, I return continuations where necessary. I believe that the Sussman and Steele used an actor model

So if a built-in needs to evaluate something, instead of recursively calling eval or apply, it returns an object that says, please call this function, with this environment and these args, and (if necessary) send the result to this other function with that env and those args etc.

In the eval, those continuations are just kept as a stack, the top is popped and evaluated, if it returns a stack, they are pushed onto the head of the stack, when the stack is empty the eval is complete.

Call/cc simply bundles that continuation stack into an object which can be called, and when it is called, it replaces whatever is in the continuation stack at that time with the stack that it was created with

The continuation stack frames are gc objects like everything else, so they're collected once nothing references them

I am far from an expert here, but it was my understanding that Kawa could only do "forward" continuations (or whatever they're properly called) because the JVM lacked stack manipulation. The only realistic alternative was to do everything interpreted so you could manage the stack yourself.

Do you have a similar restriction of some sort? Or is this a third way you're taking which can do full call/cc in the absence of sufficient stack manipulation facilities?

Currently everything is interpreted, which means everything is possible, WebAssembly has similar restrictions to the JVM if my understanding of JVM internals are correct (I haven't looked at the JVM in detail in 20 years or so), It's also much simpler.

I do plan/daydream about being able to compile scheme to webassembly, but I would then still have the same runtime underneath the compiled functions (to allow compiled and interpreted code to interact) at which point I imagine I'll be able to keep doing continuation passing and all that it entails correctly. (for example if you call call/cc from within a dynamic-wind call, then later call the continuation, it needs to call the before and after thunks whenever it enters and leaves respectively the main thunk, where entering and leaving include jumping in and out with continuations)

Interesting! Was there anything that you think came out significantly better than if you had written it in, say, C or Rust?

If I had to guess, it's because the WebAssembly Text Format is S-Expressions, similar to the target language, Scheme. Also, less tooling involved to build the binary, since the text format is pretty close to the binary format.

In practice though, it looks closer to C/ASM. The author even wrote comments in C. This is the first time I've looked at an actual program written in the wasm text format and it's pretty interesting to see how one would actually use it. Very neat.

I've definitely evolved my "style" as I've worked on it, the earliest code I was thinking in C and writing in WAT (hence the comment style), As I got more familiar I changed how I wrote it (adding the macro layer helped with that)

Almost the opposite probably, the webassembly text (WAT) format isn't really designed to be used as a human generated language, its almost actively hostile.

That being said there is definitely a benefit to writing in any assembly language that it imposes a discipline on the programmer, that is just as true for WAT, whenever you access data you are thinking about where it is stored, how it is loaded etc.

This is seriously impressive.

I'm curious if the implementation you put together here ended up more efficient in either speed or space considerations than an implementation written in, say, C, and compiled to WebAssembly?

Thank you!

That's an interesting question. godbolt supports webassembly as a target, so it is easy to check out what would be generated for given C or C++

The big difference that I'm aware of is that I don't need to worry about the C model. The code that emscripten generates has to allow for all the things that can be done on the stack that wasm doesn't support directly, so it has to provide an area in memory that acts as a stack and manage that. The flipside of this is that I have no way to get a return value from a function that is more than an (i|f)(32|64), there are a couple of places where I pack 2 32-bit ints into a 64-bit int to return two pieces of data at the same time, this is inconvenient. WASM has a proposal for multiple return values, but I'm not sure how well supported it is. I couldn't get it to work with Node for example.

Reply on news.ycombinator.com