-
WebKit
Home of the WebKit project, the browser engine used by Safari, Mail, App Store and many other applications on macOS, iOS and Linux.
-
uwm-masters-thesis
My thesis for my Master's in Computer Science degree from the University of Wisconsin - Milwaukee.
-
SurveyJS
Open-Source JSON Form Builder to Create Dynamic Forms Right in Your App. With SurveyJS form UI libraries, you can build and style forms in a fully-integrated drag & drop form builder, render them in your JS app, and store form submission data in any backend, inc. PHP, ASP.NET Core, and Node.js.
-
-
-
-
-
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
-
-
-
WebAssembly is a modern bytecode supported by all browsers and designed to be a compiler target for a wide variety of programming languages.
To effectively support some forms of Functional Programming support for tail-calls has been proposed as an extension to the WebAssembly standard.
This proposal has reached Phase3 of the standardization process years ago, but has since stalled.
Phase3 is known as "the implementation phase" and the prerequisite for advancing the proposal to Phase4 is to have support in two different browser engines. V8/Chrome support has been available for a long time, so another engine is required.
To unblock this situation we have contributed full support for WebAssembly Tail Calls to JavaScript/WebKit/Safari. The PR is available here:
https://github.com/WebKit/WebKit/pull/2065
An in-depth article about the challenges of implementing this feature is also available. This is intended both as documentation for our contribution, but also as a general explainer about how tails calls actually work, with a particular focus on stack space management.
https://leaningtech.com/fantastic-tail-calls-and-how-to-implement-them/
Neat! This proposal caused me a lot of headaches, mechanizing its specification was the primary contribution of my Master's thesis a couple years ago[1]. Glad to see it finally moving forward after stalling for so long! Excellent work!
[1]: https://github.com/jacobmischka/uwm-masters-thesis/releases/...
I'm waiting for constant time WASM. https://github.com/WebAssembly/constant-time/blob/main/propo...
It’s an expressive type system, but ime it allows developers to go crazy on type interdependencies and general entanglement, so you can’t just go to the “header” and quickly figure out what your method or a return value really is, despite TS has structural typing.
E.g. look at this: https://github.com/telegraf/telegraf/blob/v4/src/telegram-ty...
Heya,
(1) Thank you for implementing this in JSC!! I hope they take it, it makes it into Safari, and the tail-call proposal advances.
(2) I don't think you are exactly right about the call stack being observable via thrown exceptions. There's no formal spec for the v3 exceptions proposal yet, but in the documents and tests, there's nothing that would change in WebAssembly core to make the call stack observable. It's true that the proposal amends the JS API (but only the JS API) to describe a traceStack=true option; from Wasm's perspective I understand that's just an ordinary exception that happens to include an externref value (just like any other value) to which Wasm itself attaches no special significance. The engine can attach a stack trace if it wants, but there's no requirement (here) about what that stack trace contains or whether some frames might have been optimized out.
(3) I think the real reason that a Wasm engine can't implicitly make tail calls proper is that the spec tests forbid it, basically because they didn't want the implementation base to split by having some engines perform an optimization that changes the space complexity of a program, which some programs would have started to depend on (the spec tests say: "Implementations are required to have every call consume some abstract resource towards exhausting some abstract finite limit, such that infinitely recursive test cases reliably trap in finite time. This is because otherwise applications could come to depend on it on those implementations and be incompatible with implementations that don't do it (or don't do it under the same circumstances.)" More discussion here: https://github.com/WebAssembly/spec/issues/150
I've found it comes up pretty often. Sometimes because the logic I'm writing demands it—traversing over some kind of nested recursive structure, for example—but more often because it makes the code easier to read. A real-world example: I have a little interface description language which can generate code in a few different target languages. I want to factor out some of the more complex logic (eg dealing with record types) into self-contained, testable functions, which means that my top-level toDefinition function needs to call toRecord, which needs to call toDefinition for each of the record's fields[1].
(Sorry if it's hard to follow the code without context, but that's the problem with examples—either they're too trivial to be interesting, or they're complex enough to be a bit confusing!)
Additionally—and maybe even more importantly—tail call elimination also makes code written in continuation-passing style (CPS) more efficient. While CPS isn't something we usually want to write by hand, a lot of common abstractions (async libraries, promises, monads) map to CPS under the hood.
[1]: https://github.com/target/theta-idl/blob/stage/theta/src/The...
Finally :) My coworker back in 2017 implemented the WebAssembly backend for the Go compiler[0], and noted at the time that WASM doesn't have any equivalent to setjmp/longjmp. As a result, Go's WebAssembly implementation actually emulates a register machine on top of the WASM stack machine. Quoting him:
> [..] For example its architecture is a stack machine instead of a register machine. This means that it isn't immediately suitable as simply yet another target at the last stage of the Go compiler next to x86 and friends.
> [..]
> There might be an alternative: Emulate what we need. We may use the stack machine to emulate a register machine and hopefully do so in a reasonably performant way. WebAssembly has linear memory with load and store instructions, which is good. We would not use WebAssembly's call instruction at all and instead roll our own stack management and call mechanism. Stacks would live on that linear memory and be managed by the Go runtime. The stackpointer would be a global variable. All code would live in a single WebAssembly function. The toplevel would be a giant switch statement (or WebAssembly's br_table based equivalent) with one branch for each function. Each function would have another switch statement with one branch per SSA basic block. There are some details that I'm omitting here, but in the big picture this looks like a decent register machine to me. Of course the performance of this heavily depends on how well WebAssembly can transform these constructs into actual machine code.
[0] https://github.com/golang/go/issues/18892#issuecomment-30931...
LLVM and other compilers that use SSA but target a stack machine can run a stackification phase. Even without reordering instructions, it seems to work well in practice.
In Virgil I implemented this for both the JVM and Wasm. Here's the algorithm used for Wasm:
https://github.com/titzer/virgil/blob/master/aeneas/src/mach...
4. Proposed something else [ https://github.com/tc39/proposal-ptc-syntax ]
While apple is against Syntactic tail calls, they’re mainly just opposed to versions of it that would remove/unrequire the tail-call optimisation they already do: https://github.com/tc39/ecma262/issues/535
For the version of it that is backwards compatible, they wouldn’t need to do anything other than recognise it as valid syntax. Their main concern is that it "could add confusion with very little benefit."
4. Proposed something else [ https://github.com/tc39/proposal-ptc-syntax ]
While apple is against Syntactic tail calls, they’re mainly just opposed to versions of it that would remove/unrequire the tail-call optimisation they already do: https://github.com/tc39/ecma262/issues/535
For the version of it that is backwards compatible, they wouldn’t need to do anything other than recognise it as valid syntax. Their main concern is that it "could add confusion with very little benefit."