Why I'm writing a Scheme implementation in 2025: Async Rust
86 comments
·February 17, 2025reikonomusha
maplant
Very cool! I saw a number of projects pretty similar to this one, typed racket for example. I didn’t really talk about it too much but what I want to do is flip the direction. Coalton is based on CL, but what I would like is scheme to essentially be a set of Gouki function with the signature top … -> top. Then, i want to see how fast I can make the interaction between them be using different analysis like k-CFA
anonzzzies
Coalton is great. Indeed often it's much easier to just implement on top of either SBCL or ChezScheme; they are very fast and chances are you are not going to make anything as or more performant, better documented etc. However, reimplementation in Rust is not too bad as that's were we need to be for small, fast, low level runtimes. If the goal was 'just' their own language, I feel just a an implementation on top of CL/SBCL + Coalton would've been faster to build, easier to maintain and probably far more performant. Less fun though!
perrygeo
Also a shout out to Steel (https://github.com/mattwparas/steel), another Scheme-on-Rust which is more active.
The Rust community has given us at least two Scheme runtimes, several JS runtimes, but no Clojure interpreter yet that I'm aware of. There are a few zombie projects squatting on the name (seems common in Rust) but no viable releases.
Jeaye
I expect that jank will be migrating from C++ to Rust, at some point. https://github.com/jank-lang/jank
jwhitlark
That’s really interesting, as a long time clojurist and recent rust user. Can you expand on that, or is it too early days?
Jeaye
jank is the native Clojure dialect on LLVM, with seamless C++ interop. You get full interactive dev, REPL support, etc while having native binaries, ability to JIT compile C++ code along with your Clojure sources, ability to load arbitrary .o and .so files, etc.
It'll have its first alpha release this year. It's currently written in C++, but will be migrated to Rust piece by piece, either once we find a champion to lead it or once we reach Clojure parity and I can focus on it. C++ interop will remain, but we'll benefit from Rust's memory safety and improved dev tooling.
harrison_clarke
there's no reason you couldn't do a clojure in rust
but the main implementation benefits from GC and making it easy to call host (java) methods. as far as i know, the core clojure data structures are kinda hard if you don't have a GC
JonChesterfield
The hashed trie structure is definitely more annoying to write without a general garbage collector. Reference counting it works though, and comes with the magic trick that a reference count of one means you're the only reference to it, i.e. only one thread can see it, thus mutation is safe. Encoding that in the lifetime rules of rust might be a nuisance. Works very well in C.
kibwen
Rust has provisions for safely existing outside of the lifetime rules, which exist largely to accommodate refcounting schemes. You'd likely be using an Arc<RwLock<T>> here. Otherwise you can implement something on your own and express whatever C-style shenanigans you have in mind via the primitives in std::cell or std::sync.
packetlost
Lisps almost universally require or expect GC.
pjmlp
Yes, although the Common Lisp derived ones, and the old ones from Xerox, Symbolics, TI and co, also have other capabilities available, especially for the low level programming part, and all common data structures, not only lists.
TransAtlToonz
The only mature, production-used exception of which I can think is Naughty Dog's Game Oriented Object Lisp/Game Oriented Assembly Lisp. EDIT: I was wrong, wikipedia claims there are basic GC functions. I can't speak to the details, but I imagine that whatever they have would attempt to lift allocations out of the hot path/use arena allocation or some similar mechanism.
That said, people have strong opinions on whether reference counting counts as GC. I say it does, but others are vehement that it does not. If it does not count as GC, I think Interlisp-D would qualify.
no_wizard
The Clojure community hasn't even closed the gap on the CLR implementation they been working on for years, as far as I am aware.
markstos
The Helix editor, a popular alternative to Vim, is going to implementing it's plugin system in a Scheme-like language. Helix is also written in Rust.
https://github.com/helix-editor/helix/discussions/3806#discu...
MathMonkeyMan
Nice work! It's a good write-up, too.
Hygienic macro expansion is one of the things I still haven't implemented before. I remember a [talk][1] where Matthew Flatt illustrates the idea of sets of scopes, and choosing the largest intersection. I see in your implementation there are sets of "marks" in syntax objects, is that what's going on there?
I haven't played with rust, but when I do I'll be able to play with this scheme too.
maplant
I probably should have looked at this talk! Instead my reference was this PhD thesis[1] cited in the R6RS spec. I can’t say I read the whole thing, but my takeaway was to use a system of marks/antimarks. The basic idea is that at the point of macro expansion, the syntax object is “marked” (i.e. added to the set of marks) with a random integer. The environment of the macro is recorded at that point as well, along with the mark used. After expansion, the resulting syntax object is again marked with the same mark. When an identifier is marked twice with the same mark, the marks cancel each other out. The result of this is that identifier that are introduced into the expander and those introduced by the expander are distinguishable.
[1]: https://www2.ccs.neu.edu/racket/pubs/dissertation-kohlbecker...
lygaret
The talk goes line by line through this code [1]; I've been transcribing and taking notes on this for the last week, for a somewhat similar project actually.
If you're interested, I've got a huge pile of papers and links collected here [2] that you might enjoy. I've read everything, but right now it's still a big ol' mush; there's a _ton_ of prior art!
Enjoy, good hacking!
[1]: https://github.com/mflatt/expander/tree/pico [2]: https://github.com/lygaret/gigi?tab=readme-ov-file#reading
-__---____-ZXyw
Lovely pipe of papers and links, thanks for sharing!
bjoli
I have said this before, but it deserves repeating: When people say scheme is a simple language, they do not mean the hygienic macro system. Especially not something like psyntax/syntax-case.
I am very impressed! The implementation is crazy clear.
maplant
Thank you! I’m very proud of the macro expander, so comments like yours are really invigorating and justify the work I put into it
leftyspook
I think you make a pretty bad case for how embedding a Scheme interpreter is going to help with the pain points of async. Listing "stack traces full of tokio code" and then seemingly proposing to solve that by adding more glue to pollute the stack traces is especially weird.
maplant
Not an interpreter! A compiler :-)
Have you seen a stack trace originating from somewhere within tokio? Nearly all useful information is lost. My contention is that by isolating the functions that are required to be written in Rust and then doing orchestration, spawning, etc in Scheme the additional debug information at runtime will make the source of errors much more clear.
I could be wrong! But hey there’s other reasons too. Being able to debug Rust functions dynamically is pretty cool, as well as being able to start/stop them like daemons.
giancarlostoro
On the other hand, you might wind up with an impressive Scheme implementation.
kanbankaren
luajit gets you almost all of scheme features except macros. Speed of luajit is very close to native C.
dapperdrake
Sounds like Greenspun's tenth rule.
dapperdrake
It seems like the intended application is live debugging. Lisp and Smalltalk have a rather nice history here. C, C++ boost and Rust tend more to be lands of contrasts.
Chris Kohlhepp has a great write up of embedding ECL in C++. The trick is to know about the C++ configure flag for building ECL. [0 with terminal screenshots, 1 on web archive without terminal screenshots]
Haskell people seem to like Lua. Just look at pandoc.
[0] https://isocpp.org/blog/2014/09/embedding-lisp
[1] https://web.archive.org/web/20200307212433/https://chriskohl...
StilesCrisis
I thought the same thing. It's a hard pivot from "async rust is hard" to "but if we add in Scheme it will be good!" With no real justification for it. I'm not a Scheme guy but I don't see the connection.
ilrwbwrkhv
What would be really nice is a new lisp which actually allows for incredibly interactive programming similar to common lisp, but which targets a runtime like the v8 engine maybe. Because I think a lot of people are missing out on the Smalltalk / Common Lisp experience.
Even Clojure and other lisps do not enable that level of interactive programming which the break loop in Common Lisp does.
homarp
if you are curious about the breakloop as I was: https://news.ycombinator.com/item?id=35693916
ilrwbwrkhv
I actually built one of my earlier startups on Steelbank Common Lisp and I absolutely love the break loop. To build up a program by iterating on the break loop is just a magical experience and I think one can go even much further with a modern version of it where you can sort of jump around the stack and you can almost do a bunch of these things in common lisp as well but it is something that needs a little bit of work and it doesn't look and feel as modern as some of the other languages so I feel like therelisp as well but it is something that needs a little bit of work and it doesn't look and feel as modern as some of the other languages so I feel like there is an opportunity for a new language.
packetlost
I'm more of a R7RS kinda guy but I appreciate this, especially the types. Scheme allows for extremely non-linear memory access which means you necessarily need dynamic memory management and garbage collection. IMO once you're to that spot, there's little reason to stick with Rust, though it being the implementation language is interesting in itself. That being said, there are battle tested Scheme implementations out there that have fantastic FFI APIs that would probably work just as well if you don't mind a small bit of C to glue things together.
mightyham
This seems like a great idea and I support the effort. It was not clear to me on first read though that what was being proposed is not an extension to current async rust (compiling code to a series of state machines), but a completely alternative design utilizing a context switching runtime like Erlang or Go. If I interpreted that wrong please correct me.
Part of me wonders, considering that rust is a systems programming language, how difficult would it be to write a runtime like that in rust so that there is no need to use a second language?
whitten
So your goal for the runtime would just be a different runtime for Rust ?
mightyham
To be clear, in this comment, I am referring to async in the broadest sense. I am specifically NOT referring to the Rust compiler keyword and runtimes (like tokio) that work with rust future state machines.
If I understand OP correctly his current proposal is to create a different runtime for rust. That runtime happens to be written in scheme using his own compiler. It is meant to make writing async rust applications easier by having simple rust interop.
Given the authors implicit argument that an async runtime with a stack-based context switching model can provide better debugging. Is it possible to write something like that in rust? That may be better for some use cases, as it wouldn't result in a multi-language project.
dapperdrake
Unlikely. C and Rust have run-time environments. Just not as elaborate as the JVM for Java or a web browser for JS and WASM.
It could only be about adding a second run-time environment to the same operating system process. That’s what the questions seems to be enquiring about.
And it’s about instrumenting the Rust run-time environment with a REPL and human-friendly run-time data structures.
dapperdrake
Doesn’t seem like it.
It’s about interactive instrumentation of the runtime. Think lua in Haskell adding slight reflection and a REPL. In another comment I referenced Chris Kohlhepp’s write up.
valorzard
Is the name Gouki a Street Fighter Reference? (For those not in the know, Gouki is the Japanese name for Akuma)
giancarlostoro
To the author, if you're reading this:
> But while I thing that async Rust is well designed
At least one typo, thank you for not using an LLM to spit out an article. :)
api
I wonder if people are in a way misusing Rust by trying to use it to build everything. It's designed to be a systems language, one for writing OSes, drivers, core system services, low level parsers, network protocols, compilers, runtimes, etc.
There's no way a low-level systems language like this is going to be quite as ergonomic as a higher level more abstract garbage collected language.
hardwaresofton
IMO you've stumbled into one of the reasons Rust is amazing -- it can go to higher levels, for many good reasons. Whether you should is another question, and it will arguably never be as easy to write as python or javascript (to be fair it's also easy to write inconsistent code in those languages), but it can.
I wouldn't argue that Rust is as ergonomic as other languages, but it has enough pieces to build DSLs that make it look as ergonomic as other languages. An example of this is the front-end frameworks that have been spun in Rust, like Leptos[0].
Rust probably has no business being on the frontend, but the code snippets are convincing and look pretty reasonable. If the macro machinery and type stuff never blows up/forces you to touch internals, then does anyone care that it's a system language underneath?
UncleEntity
> Rust probably has no business being on the frontend...
I would argue it this were more common they would have a lot of incentive to iron out the rough spots. Well, hopefully not in the way that makes it easier to have you download a 100+ megabyte wasm bundle to read a static blogpost, but anyways.
Personally, if I'm writing a script for an actual purpose (as opposed to just coding for coding's sake) I reach for python and if that's too slow I write a wrapper around some C code to speed things up. If I'm just messing around I use C(++) because that's what I know -- which is where rust could easily fit if the learning curve wasn't so high that I don't see the effort as worth it.
dapperdrake
Luckily, neither CPython, nor Lua, nor Perl, nor PHP, nor Ruby, nor Google Chrome are written in C.
Oh, wait.
hardwaresofton
Glad to see more language runtimes be available from Rust!
Looking forward to scheme-rs being able to benefit from the safety and speed Rust allows
dapperdrake
It’s about instrumenting Rust’s existing run-time.
hardwaresofton
Are we reading the same article? It's about this project:
dapperdrake
So? There is instrumentation for Async Rust being added. Just not in the Rust compiler and not in tokio. More in application level code. So as far as the user is concerned to "their" Rust run-time. A distinction that is mostly useless when programming lisp. Hence lisp.
Lisp is about solving your problem and getting the "language" out of the way. So you add what is missing. As long as it works it doesn’t even matter where it’s added.
Even C has a barebones runtime environment when compiled for a machine with an MMU and an OS, so not a microcontroller.
Coalton [1] is a Lisp language that has Hindley-Milner type inference with type classes. Its syntax actually resembles the prototype syntax from TFA pretty closely. The Coalton syntax-equivalent would be:
Of course types and classes like Option and Eq are built-in already.Coalton is based on Common Lisp (and allows free mixing with CL code) instead of Scheme however, though Coalton is a Lisp-1 and would feel relatively at-home to any Scheme programmer.
[1] https://github.com/coalton-lang/coalton