Devlog 1: 2023-06-20

What was accomplished

Started working on making my own LISP following the guide from mal - Make a Lisp, programming in Rust. This is to help improve my Rust coding and learn how a language like LISP works to help with this month's #12in23 challenge (June - Summer of Sexps). Between June 10th and the 19th, I finished working on steps 0 to 5.

Step 0

Created a simple REPL (Read-Eval-Print-Loop) using the Rustyline crate. Not too much of an issue working on this step. Mostly spent time looking at what libraries to include.

For test cases, create a simple Python script to convert items in the test file to Rust #[test_case] (NOTE: #[test_case] using the test-crate crate, not the one built into Rust). Also moved code to a separate module to help isolate items between each step.

Step 1

Using the Logos crate, I created a simple parser for the language, which was straightforward to set up. I now understand the meaning of plumbing for parsers, seems tedious to pass and extract values, return what remains, and raise any issues. Parser combinators and generators provide a good way of handling that part and leaving the actual parsing idea up to you.

Modified some of the symbols to parse due to Logos' parsing precedence. No major changes to the implementation, just some things made easier to parse (such as splitting all the symbols into their own token variant).

Updated the source name to follow the guide's convention.

Step 2

Worked on the evaluation step of the program. Got a better idea of how LISP processes lists and functions. I remember trying to figure out how best to represent collection types. Initially landed on List being VecDequeue, Vector being Vector, and Map as Vector of tuples.

This is also the step where I started to add documentation. While not very descriptive, it did provide some context when hovering over the type.

Step 3

For this step, I worked on adding the environment and ways to assign items to it. Creating the environment structure and defining the special forms def! and let* were straightforward to set up, though it did require modifying much of the functionality and types. I also learned to create macros for the lifted functions (arithmetic operators). This would eventually lead to adding more operations and functions fairly easily (though the macro would change between each step). Once that was completed, I updated the test case to work from the file directly. Once I got the structure down, debugging with the test file became a lot simpler.

Step 4

Step 4 was the first one that felt somewhat harder than prior steps. This step focused on adding if, do, and fn*, alongside some additional core functions. The lisp function was a bit more tricky, mostly with figuring out how to handle storing the environment. I was able to figure it out by boxing the current environment and using that within the function. I also overhauled my macros for adding operators and symbols to the environment.

However, the biggest issue was working on implementing the string type correctly. Originally, I did no preprocessing or postprocessing for the strings, which lead to the test cases failing. Once I figured out what I need to escape (with help from the current Rust implementation of mal), I forgot that the way I printed items out was different from the implementation. I then did a rewrite for how to handle converting items to strings and made an update to the printing functionality for the test to make sure they all worked correctly.

Step 5

I initially wasn't going to include this step because I hadn't completed it, but once I rewrote the environment using what I learned from the Rust implementation, everything fell into place and all the tests passed.

Step 5 was both hard and easy. It was hard in that I had some trouble getting the TCO (Tail-Call Optimization) working for the eval function, which required a rewrite of the environment structure. However, it was easy, as once that was finished and the update following the guide was applied, nothing seemed to break and it was working correctly. I also did a slight rewrite of the List and Vector type to use Rust vectors directly, as I came to learn how to do vector destructing using slices.

What I learned

• Interior Mutability with Rc and RefCell
  • RefCell is used for the dynamically borrowed data value of the environment. This allows modifying the value of data (such as setting a new symbol-value pair) without requiring the environment itself be mutable.
  • Rc is for explicitly adding reference counting to an object, allowing multiple ownership. Used to allow holding multiple references for an environment when an environment is changed (such as let-bindings or function closures).
• Vector pattern matching using slices
  • This removes the need for using a VecDequeue data type, as I no longer need to use the pop_front function to get the first item.
  • I can do complex matching, such as on specific enum variants, which makes it much easier to process the meaning of the match (also reducing the number of if-statements needed to extract the values).

What is next

Finishing up the next set of steps from the guide. Once that is done, I might work on implementing the ideas from the Readable Lisp S-expressions Project.