This post is another slight digression in my series on building a Lisp interpreter in Rust. Because I’m writing the posts as I go, the shape of this series will follow the shape of my own path through learning Rust.
Anyway, Rust has memory safety. This safety means that I probably won’t have people attack my Rust applications via a buffer overflow, which is great, but it also means that the compiler is always yelling at me, which can be frustrating.
I decided I needed to learn how to do pointers or references or whatever in Rust at all before I could continue with my project. The Lisp syntax structures that I will build up will be trees whose exact shape isn’t known at compile time, so I need to know how to build reference-based structures in Rust. I googled “linked list in Rust,” and I found Learning Rust with Entirely Too Many Linked Lists. This is one of my favorite online tutorials. It’s quietly hilarious, easy to follow, and clearly built on a deep understanding of the Rust language. So before my next installment on the Lisp interpreter, I’m going to look at some of the lessons I’ve learned from all these lists.
Rust has different types of references. The simplest is a Box<T>. In Java and C#, the compiler does a pretty good job of hiding boxes from you. If I do something like put an integer on a List<Object>, C# will make a reference to the integer and put that on the list, and most of the time I don’t need to care.
Rust cares. For example, in the simples linked list implementation, we have type Link<T> = Option<Box<Node<T>>>;. In other words, I’m telling my program, “The type Link<T> really means that there might be a reference to a Node<T>.”
This is actually pretty neat. The Option<> is either Some<T> or None, instead of having a null pointer for the link of the last node in the list. The box lets Rust guarantee that links are all the same size – a reference to a node is the same size in memory as any other reference to a node. And, there’s good support for generics! That means we don’t have to cast or check types when we take something off the list.
It turns out that a bunch of linked lists is a good way to learn about Rust’s memory model, and the tutorial linked above does a great job of teaching that. I plan to finish that tutorial, then get back to building my Lisp interpreter.
Till next time, happy learning!