One year ago I decided to start working on a Lox interpreter in Swift following Bob Nystrom's book Crafting Interpreters. Today I'm happy to say that the work has been completed. Mission accomplished.
You can find the finished version of the interpreter in GitHub alexito4/slox. There are improvements, refactors and, I'm pretty sure, some bugs that could be fixed, but the interpreter is completed and can run real programs. So exciting!
The plan here is to follow Bob’s work on the book and implement the chapters one by one in Swift.
Having written an interpreter is a really cool thing but my personal goal of that year was more on the lines to have something I could say I finished. I have a tendency to start new projects and never finish them, I get pretty close but I get really bored in the last 20%, you already know that rule.
My hope back then was that by having a book to follow, but even more importantly, by following it at the same time new chapters were published, it would make me get involved enough with the project that I would always be hungry to work on it. And that resulted to be true.
I could have implemented the beginning following the book and then, tired of waiting, jump ahead and do my own thing, the lack of ideas was not an issue!. But I explicitly wanted to avoid that. That was the main challenge.
Because I’m not making up the language nor the compiler/interpreter but I’m following the book I don’t want to get into a point where in future chapters the book asks for some code changes and they get too complex because I was trying to be too smart.
If would have done my own thing without waiting for the chapters to come out there was a high risk of getting tired of it quickly. But also of there was a change of putting myself into a corner caused by my inexperience with this kind of software, a corner that would have been hard to get out of without requiring some big changes on the codebase. And it's not that it was not possible to improvise and to my own thing, but knowing myself I was sure that if that day came, I would just ignore the project and start something else. So the decision to follow chapter by chapter was done conscientiously and, in retrospective, it was a great decision. The technical challenge was high, but the psychological was even higher.
I’m really curious to see how Swift is suited for this kind of work.
I have to say that it has been a pleasure to work on an interpreter with Swift. Following the Java code from the book was easy, but seeing the nice changes and simplifications that could be done in Swift was even better.
That said, there are couple of things that I would refactor if I had more time to put in the project, both are totally my fault. You could expect that I would throw the excuse of "the language is still young" but no, Swift is more than production ready. My decisions are the ones that got me here.
And it's not really that bad, I've may gotten stuck no more than 1h on something caused by a bad decision. But nonetheless I think it still worth talking about the things that could be done better.
The first issue is that at some point I was undecided about using Swift error system in some parts due to the lack of typed throws. I have reasons for that, and I still think is a necessary evil sometimes. For this specific case, having a program with multiple well defined layers that need to propagate errors and is really important to handle them, I really missed the feature. So, as expected, I added Result and started using it in some places. That ended up making a lot of code weird and not Swifty at all, where I'm mixing try/catch syntax to create Result and returning it. I'm pretty sure that there are some patterns that could be factored out but, if I took the decision now, I would probably stick with Swift error system and see how painful it gets. It would be a nice experiment to compare them.
But the big issue with adding Result was not the mix between both error systems, but the fact that now the error path is part of the same return type. That's good in many occasions, but when writing this interpreter there are more Any types that in a usual program. This makes it really hard to keep track of what is being returned from a function, the majority of bugs I had were provoked by working with a variable that I thought it was the value that I expected when in reality it was a Result type waiting to be unwrapped. Of course the type checks were failing all over the place. I guess I'm too used to have the compiler helping me that so many Any and dynamism is too much for my little brain.
And using Any brings another difficulty caused by how it interacts with Optionals and nil. There is a bunch of unexpected behaviour and confusion around this, because obviously an Optional is also an Any, so sometimes when you want to differentiate between them it gets really hard. I ended up defining a constant for AnyNil that allowed me to have back a little of my sanity, but still, I don't recommend anyone to use Any in this way.
And following the natural path of this issue we finally get into the last big refactor that I think the interpreter needs: moving away from this Any into a structured values that the interpreter understand, an enum of supported types. This would also allow me to move away from the Visitor pattern and use a more natural Swift idiom with enums and extensions. I decided not to go this route in purpose to avoid diverging to much from the book, but now that the work is completed it would be a good exercise to clean up the implementation and see if it actually makes things simpler.
- Challenge 3: Add your own features!
On each chapter the book gives us some challenges to try different things or improve the language. I've been doing some of them, but it gets scary when you start modifying the interpreter too much knowing that in the next chapter those changes won't be there. So the majority of the challenges are just done in private branches that were not merged to master.
But apart from the challenges I also had my own ideas! During the implementation of the interpreter I've been taking notes of features that would be interesting to add, inspired by other languages or by watching Blow's streams. I'm not sure if I would ever do it but the notes for language features are always useful to keep around ^^
This project now uses SPM to manage the executables, framework and dependencies.
The project structure has evolved during this year and I have to say I'm really happy with the current incarnation. I moved to the SPM with the typical structure for command line Apps, with a core framework and a tiny layer for the executable. That has allowed me to tinker with having the interpreter running in a server so you can code lox online!
I'm now used to have a Makefile in all this kind of projects that I do. I think now I understand the purpose of Make, and I used it specially with this project to run the tests. Testing was interesting for this project as I'm not relying on unit tests at all. Instead I integrated Rob suite of tests, modified the Python script to run them after each chapter so I can be sure that at least the interpreter has the a sane behaviour.
This marks the end of Part II, but not the end of the book. Take a break. Maybe write a few fun Lox programs and run them in your interpreter. (You may want to add a few more native methods for things like reading user input.) When you’re refreshed and ready, we’ll embark on our next adventure.
The next adventure is writing a bytecode virtual machine and I'm really excited about it. As I said previously I have many projects that I would like to do this year so I'm not sure if I'm gonna compromise myself with this but it's something that I really wanted to explore.
With the current project structure I was hoping that it would be acceptable to have slox be able to run in different modes, as a AST interpreter, a bytecode interpreter and even a compiler using LLVM. It seems like the logical path to keep learning about this amazing world of programming languages. I don't understand why this was not part of the University curriculum!
And that's all, my slox interpreter has been completed. My goal of 2017 acomplished and I'm really happy to have energy to do more things this year. It reminds to be seen if I will come back to thid codebase, but I would like to keep working on the VM and even LLVM mode.
Huge thanks to Bob Nystrom for the book and to you for reading!