[Sbcl-devel] WASM GC i31ref, usefulness or lack thereof for Lisp

[Sabine Schmaltz]

Hello everyone,


For context: I'm working on compiling OCaml to WebAssembly, and I am
involved in the discussions of the WebAssembly community group. I know
only the basics of Lisp.

I've been looking at the WebAssembly garbage collector extension
specification.

The WASM GC specification tentatively has a type `i31ref`, which is a
31-bit integer embedded into a pointer:
https://github.com/WebAssemably/gc/blob/b2da61b6c444459a60e32a2e021f2631575b1795/proposals/gc/MVP.md#unboxed-scalars

I wonder,

1. would `i31ref` be of any use at all to Lisp, if Lisp were to compile
to WASM in a way that uses WASM's GC?

2. what would a built-in GC of WASM need to look like in order to be
useful as a compilation target, to Lisp? Is there such a thing that can
be realistically reconciled with a general-purpose GC such as WASM can
provide?

3. are there any efforts or interest to compile to WASM in a way that
uses a built-in GC? Or is the consensus here that the better solution is
to compile to linear memory and bring your own GC, because Lisp's memory
model is just too different from the mainstream?

4. is there someone specific I can contact to discuss this?


Best,
Sabine Schmaltz
--
Sofware Engineer @ Tarides


_______________________________________________
Sbcl-devel mailing list
Sbcl-...@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-devel

[Douglas Katzman via Sbcl-devel]

Hi, It's not clear what goal you're trying to achieve. Your email didn't say anything like "I would like for SBCL to compile to WASM" or "I would like some lisp implementation which compiles to WASM".

i.e. Are you asking about SBCL or are you asking about whether WASM could host a Lisp environment, potentially forked from SBCL?

As to answering the question "Could SBCL gain something (portability/speed) if it just compiled to WASM?" I would say that at first glance this is not an interesting angle to the SBCL project.

But note that I'm not saying it wouldn't improve the portability; I'm saying that wasm is not likely the route that SBCL would take to achieve it- LLVM is.

That's on the one hand.  On the other, if your position is "We desperately wish to retarget SBCL to compile to WASM as its VM", then I'd say, sure, that's possible in theory, and, sure, you might be able to leverage the builtin GC capability. The 31-bit integer format as an efficient integer type (not requiring heap allocation) would be a regression on the 64-bit platforms; SBCL's efficient integer type has anywhere between 60 to 63 significant bits depending on the CPU.

In terms of whom you could discuss this with, unless some user raises his/her hand saying "I want that!", the mailing list is really the best channel for discussion.

Doug

[Sabine Schmaltz]

Hello,

sorry, I haven't been very precise:

There are recurring discussions on the usefulness or importance of
`i31ref` on the WebAssembly community group. Some parties are very
reluctant with respect to committing to making `i31ref` a part of the
spec. Some are looking for better solutions that solve the same problem
(efficiently storing integers on the heap).

My goal is to find out if Lisp, not necessarily SBCL, can make use of
the `i31ref` spec of WebAssembly, if that Lisp were to be implemented on
WebAssembly and use WebAssembly's built-in GC.

That the likely route to WASM for SBCL is through LLVM is definitely an
interesting point. I take it that means that SBCL would definitely bring
its own GC to WASM?

For Ocaml, we would very much appreciate a 63-bit efficient integer type
on the WASM GC, as the 31-bit integer type only gives us a
reasonably-efficient 32-bit target on WASM. Efficient 63-bit integers,
however, are extremely unlikely to make it into the specification, as at
least some of the browser engine vendors cannot efficiently implement
that, due to choices in their existing codebase. 31-bit efficient
integers, however, the existing browser engines can support with
reasonable effort.

Lisp as a language is on the Tiobe index. In some people's ears that
makes Lisp's words more important than OCaml's. :)

Best,
Sabine

On 7/2/20 3:06 PM, Douglas Katzman wrote:
> Hi, It's not clear what goal you're trying to achieve. Your email didn't
> say anything like "I would like for SBCL to compile to WASM" or "I would

> like /some/ lisp implementation which compiles to WASM".

> <mailto:Sbcl-...@lists.sourceforge.net>
> https://lists.sourceforge.net/lists/listinfo/sbcl-devel

[Douglas Katzman via Sbcl-devel]

To make the kind of tight binding of lisp internals to the WASM vm that you're suggesting (to have GC as a builtin thing etc), you'd have to think about all the pieces of lisp, not just whether something like lisp's fixnum type would be directly implementable as 'i31ref'.    Personally I can't even guess about whether 'i31ref' would be useful. It may be, if the users of such a lisp are willing to have 31-bit integers as their fixnum type.   It would meet the spec, which says that fixnums are at least 16 bits.

Just to point out the range of implementation strategies, the KCL implementation (https://en.wikipedia.org/wiki/Kyoto_Common_Lisp) defined most-positive-fixnum as the machine word size (32 bits at the time), had most fixnums require heap allocation (contrary to the intent of fixnum), but also defined a small range of fixnums that would always point to a prebuilt table of the integers from -1024 to 1023 (or something).  So to produce a small fixnum, you could just load the pointer with the proper index into the table. The net effect was a completely uniform view of any lisp object as a pointer, without having to decode any bits or even figure out what address ranges could be reserved on this or that architecture for funny encodings.

If there aren't any SBCL-specific issues at hand, I don't know how else to help you.