DEV Community

Rust Your Own Lisp

Ben Lovy on June 04, 2019

This is a fuller walk-through of the code I talked about in a previous post, Solving Problems by Avoiding Them. The project is a translation of Bu...

Read full post

Yoandy Rodriguez Martinez • Jun 6 '19

Great stuff Ben!!!. A question from a fellow Rustling, why does Fun(LvalFun) works without deriving PartialEq?

Ben Lovy • Jun 6 '19 • Edited

Good eye :) It definitely doesn't, I fudged it:

impl PartialEq for LvalFun {
    fn eq(&self, other: &LvalFun) -> bool {
        match self {
            LvalFun::Builtin(name, _) => match other {
                LvalFun::Builtin(other_name, _) => name == other_name,
                _ => false,
            },
            LvalFun::Lambda(env, formals, body) => match other {
                LvalFun::Lambda(other_env, other_f, other_b) => {
                    formals == other_f && body == other_b && env == other_env
                }
                _ => false,
            },
        }
    }
}

Builtin functions are considered "equal" if they share a name, and because there are no name collisions in the environment I deemed it "good enough".

Can you think of reasons why this wouldn't be sufficient? It's on my "revisit later" list and for now seems to be working fine.

Yoandy Rodriguez Martinez • Jun 6 '19

Oooh, I missed the part where you implemented that, nice workaround :D

Ben Lovy • Jun 6 '19

workaround, cheat, who knows :)

baste-and-turkeypilled • Oct 7 '21

Hi Ben, I'm a neophyte programmer, so forgive the possibly stupid question: Since Rust is memory-safe, would a complete Rust implementation of Common Lisp even need a garbage collector (or other memory management on top of Rust) in order to be memory-safe? Can you point me to any resources that explain the answer to this question? Thank you

Ben Lovy • Oct 7 '21

Hi! Definitely not a stupid question. While Rust itself is memory-safe, a language interpreter like Common Lisp built on Rust would still need to implement some sort of garbage collection. The Rust program is implementing a runtime that still allocates objects to the heap. These objects will still need to be cleaned up. What Rust guarantees is that there are no memory safety errors in the implementation of this runtime itself. However, you can still envision a scenario where the runtime it implements doesn't clean up after itself, or uses reference counting, or mark-and-sweep, or whatever else you can think up to handle values the runtime itself creates.

For example, imagine this Lisp "boxes" every single value. There is no way in this Lisp to store something to a "stack". This means when you declare something like (def x 4), you actually get stored to x a pointer to some value on the heap. That value can live there forever, and even though the program that set up the code that knows how to box up values is itself memory-safe, that doesn't mean it inherently cleans up these higher-level constructs. It cleans up after itself in terms of values used internally in the interpreter, but the logic building the heap allocation for a Lisp programmer using the runtime is just that - part of the logic of your program.

Basically, if you want your Rust-implemented language to expose some sort of "stack", you need to actually implement that stack yourself. It's distinct from the stack you interact with when programming the interpreter in Rust. Somewhere in your Rust program there will be logic for what that stack is, how to push and pop values from it, etc. You, the compiler-writer, define all that logic.

I would highly recommend the book Crafting Interpreters. This book really peels back the magic - a written implementation of a language is nothing magic, it's just a program. Rust allows you to write that program safely, but you can still implement any logic on top of that, including languages that just let values sit around on the heap forever or values that get garbage-collected however you want. If an infinitely-growing heap is what you actually intended as a program-writer, that's totally fine. What Rust guarantees is that you didn't make any memory-safety issues in your implementation of that higher-level logic.

Does that help, or just confuse things further?

baste-and-turkeypilled • Oct 7 '21

Yes, that makes perfect sense. I can keep dusting off all the objects in my room, but if my room fills up with junk, I have a problem - no matter how clean that junk is. Thanks so much for the explanation and the book reccomendation.

Ben Lovy • Oct 7 '21

That's an awesome analogy, I'm gonna remember that. Book is totally free to read, btw, in case you missed it...I ended up purchasing a copy anyway, but you can get started with no commitment.

arj • Jun 4 '19

What an impressive article. Thanks for this! I taught building an interpreter as a TA at the university and this article is really good. Well done!

Ben Lovy • Jun 4 '19

Wow, that's super validating to hear, as a total novice who's never taught anything to anyone! I'm glad I'm on the right track, and learned so much from putting this together I think everyone should do it for themselves.