Risp (in (Rust) (Lisp)) (2019)
stopa.ioNicely written article. I too attempted a Lisp interpreter to learn Rust, but gave up when I couldn’t figure out how to implement a linked list in Rust.
The key is to use reference-counters. If you think about it, no lisp is really going to fit the single-ownership model. Many of them are implemented on GC'd languages for this reason. Rc<> is the standard Rust answer for GC, and in practice means you don't really have to deal with ownership issues for those values.
I implemented my own Rust lisp if you want an example: https://github.com/brundonsmith/rust_lisp
And here's a more general resource (not written by me) on this class of problems and the surrounding subject matter: https://rust-unofficial.github.io/too-many-lists/
How does Rust reference counting handle cycles? Python is famously reference counted, and even it ended up having to strap on an occasional GC cycle to mop up after those. Or do you just accept that if it leaks, it leaks? Which for most finite-lived programs on generous modern hardware may be a sufficiently acceptable solution.
...
Still, I do idly† wonder if there could be better schemes[sic] than just slavishly refcounting everything? e.g. If you know which values never escape a given scope, maybe just dump them into a single-ownership pool that’s collected whenever execution finally leaves that scope. Which, for lists that compose the program itself, is the entire lifetime of the program (so no need to explicitly collect assuming the OS is happy to clean up after the program exits). It’s really just values that leave their originating scope that need to start refcounting (although, of course, there’s a raft of ways they can sneak out of that).
Although I think the most inventive answer to dynamic memory management was the language that simply tossed all newly created values into a single global cache, from which it periodically swept all values that weren’t touched again within a fixed period of time. (Obviously requiring 100% referential transparency, so that if an already-flushed value is needed again, it can simply be regenerated from scratch.) Alas, I can’t remember that language’s name (I think it’s an older and obscure one), but simple, effective, and sneaky AF? #MeLikes
--
† Alas, while I have considered implementing a scripting language in Rust (to teach myself Rust as much as anything else), I’m already painfully slow writing them in HLLs that do all that low-level stuff for me. #BoVLB :/
Rust-the-language doesn’t know anything about multiple ownership.
The standard library refcounted types don’t do anything special, if you get a cycle you leak. You can use weak refcounts to try and prevent this.
It's interesting, but here's the easiest way to evaluate if a Lisp/Scheme implementation article is interesting:
"Does it parse (2 . 3) vs (2 3) aka (2 3 . nil) correctly?"
That little dot which signifies a cons-pair makes implementing Lisp/Scheme oh-so-stupidly-much harder.
Suddenly your printing has to go all the way right before it can make decisions. Your recursions suddenly need to be robust against not being a list. etc.
> evaluate if a Lisp/Scheme implementation article is interesting
I guess Clojure doesn't count as interesting and/or a lisp then, as `(2 . 3)` would not be parsed correctly and instead throw a syntax error on that form.
I still thought the article was interesting and would have loved to see a section on macros. Maybe next time.
> I guess Clojure doesn't count as interesting and/or a lisp then
The Schemers and Common Lispers have been saying this about Clojure for years, you know ...
And, in the interest of full disclosure, I don't disagree with the choice that Clojure made. Not being able to process a "list" as a sequence is a PITA.
However, articles like these get written with "Look how easy it is to make a Lisp" without saying "Except that we didn't implement these really hard features that actually make a Lisp"
Aren't cons cells just an implementation detail? I have no problem calling "lisp" any language where s-expressions are imlemented by any other tree/list data structure, and thus it doesn't have the dot.
I believe that lists are generally defined in the "Lisp" standards as a set of cons pairs terminated by nil.
This makes things a lot harder than they need to be--you effectively MUST process lists by recursion as you don't know you have a list until you hit that far right "nil".
Good point, they are actually specified so both in common lisp and scheme
"Lisp" in fact refers to a set of details for implementing a programming environment. The requirements are wobbly, but not so wobbly that you can call anything "Lisp".
Note that "correctly" means that (2 3 . nil) comes out as (2 3).