Recently I’ve been researching some operating systems and programming language design and wanted to try out a few of the newer options for an implementation substrate.
I decided that writing a simple Tcl interpreter would be a fun project to get a better idea of what’s out there. Making a little scripting language helps you exercise a number of important basics (string handling, reasonably complex structures, memory management, first class or not so first class functions) and at the end of it you have a fun program that you can also exercise the language’s ecosystem with.
Pictured: not this Tcl implementation
My background here is some hobby experience with C and C++. I’m definitely interested in knowing where I could’ve done better, please send your roasts to my email.
If you want to skip to the end, here’s the code: C++, Zig, Rust.
#Tcl and picol
Tcl is a programming language where everything is a string. This puts it into the Lisp/Forth category where uncompromising simplicity also makes it relatively easy to implement a kernel that can then be metaprogrammed upward until you have some pretty high level constructs on humble beginnings.
antirez’s picol is a fantastic exemplar of a small Tcl which gets to a working Tcl interpreter in 556 LoC of C. To give an idea of what picol/Tcl can do, the fibonacci number sequence calculator:
proc fib {x} {
if {<= $x 1} {
return 1
} else {
+ [fib [- $x 1]] [fib [- $x 2]]
}
}
puts [fib 20]#How a simple Tcl interpreter works
I used picol as the main reference for how to write a Tcl implementation. In Picol and my three implementations here, there are three major components:
- Parser: tokenizes the source code
- Interpreter: evaluates the source code by building arrays of strings to be called with commands
- Standard library: Even primitives like
procandifare defined as simple functions rather than syntactic forms that need to be special cased
While the above code sample has a lot of familiar looking syntax (braces and brackets and so on), it’s actually mostly strings. Braces are a sort of string, so it parses to something like this:
escape token: proc
separator token
escape token: fib
separator token
string token: x
separator token
string token: ...fibonacci function bodyOnce we have this stream of tokens, the interpreter handles executing them. One aspect of Tcl that was a little mystifying to me initially is that the interpreter doesn’t really behave like an AST-walking interpreter that goes into a tree and comes out with a value.
In Tcl, it’s more of a string concatenation engine. Evaluating the tokens results in an
array of strings, and each line is a command that gets called with that array of strings
as its argument. The output of all this can be read at a central result string.
While there’s a little bit of syntax for common tasks like getting a variable’s value
($x), the simplicity and stringiness is what enables Tcl’s wild metaprogramming. In the
above fibonacci example, proc and if are just given their bodies as a string, and call
the interpreter on that string when appropriate.
#C++
Plunging ahead without understanding the Tcl very well and learning new languages like Zig at the same time proved to be a little confusing. So I started with a C++ version.
As antirez points out, a lot of the C code is simply string and container
handling functions that aren’t provided in the standard library. If you’re
willing to lower yourself to using the STL you can avoid
needing to deal with reallocing arrays and such.
Using std::string refs and std::string_view removed some unnecessary string
cloning in the interpreter, making it a couple seconds faster on calculating
fib(35). Most manual string allocation and copying is gone because of RAII,
and it’d be possible to further reduce the usage of new/delete.
Binding to C and adding dependencies
One little wrinkle I decided to throw into my interpreters was using a third party library (for argument parsing) and linenoise (for the REPL) to see how using dependencies and calling out to C code feels.
In C++, using Linenoise was trivial since it’s written in C and even includes header guards to make sure it’s C++ safe.
Then I pulled in the argh single header library. Header-only and especially single header libraries are popular in C/C++ world; due to the lack of a commonly accepted package manager and build system, it can be painful to include libraries with non-trivial builds in another project.
#Zig
I started off with Ziglings which is a fun little way of learning a language. I was able to get through it in a few hours and retained syntax a lot better than my usual method of trying to do things and then searching after running into errors.
Allocator choice and memory management
Zig comes with a couple of in-built allocators to choose from. It turns out the
default allocator, GeneralPurposeAllocator is not written with performance in
mind (and in fact has been renamed to DebugAllocator in 0.15).
My impression from reading this GitHub issue and others was that Zig’s creator and community prefer to use other memory management strategies:
as you become an advanced programmer you start to learn about better memory management techniques that makes GPA (ed note: General Purpose Allocator) performance irrelevant
It hardly matters for our toy interpreter but it is an interesting thought exercise. Which allocation strategy to use for an interpreter is really dictated by the use case. So I decided to do as the Zig standard library does and let the user specify the allocator.
Binding to C and adding dependencies
Adding a dependency was easy; I added clap and just did what the README told me to.
Zig includes a full on wrapper of Clang so adding Linenoise was trivial. With about 3 lines of build config and 2 lines of Zig code I was able to use it with no fuss.
Overall thoughts
Comparing the C++ and Zig versions, I think the Zig code comes out a lot cleaner.
We get to use an error union on return types which allows us to more easily
propagate some helpful information about the error, including errors that come
from Zig’s standard library. Zig has a nice try shorthand for not having to
unwind the stack by hand as in Go’s if err != nil.
I was pleased to learn that Zig supports tail call optimization and using labelled blocks anywhere; while I only used tail calls once, for writing parsers and interpreters these are serious quality of life boosts.
And then there’s just things like having a built in enum-to-string converter so
it doesn’t need to be added by hand for each enum. Or getting to use standard
library containers like ArrayList instead of needing to self-roll or pull in
library, as in C.
I found the return to manual memory management over RAII a little tedious and got tripped up in a few places because of it. But no hidden memory allocations is an explicit philosophical goal of Zig, so this is take it or leave it.
Zig also comes with a lot of built in debugging that requires external tooling
in C/C++ — one of which is that the GeneralPurposeAllocator has leak
detection.
I was bitten by versioning twice: first when trying to use Ziglings, which is already on 0.15. The nightly build of Zig didn’t run for me, so I downgraded Ziglings to 0.14. And again when adding the clap dependency; there was no tag for 0.14 so I had to find the right commit by hand. Various online resources were also already out of date for 0.15 or even 0.14.
I also found the pointer and slice syntax to be a bit cumbersome.
👍 Would Zig again.
#Rust
From the Ziglings README I learned about Rustlings. Rustlings doesn’t include instructional material directly in the file like Ziglings, but recommends following the Rust Book. I mostly consulted a half-hour to learn Rust.
I definitely experienced a steeper learning curve here. While I was able to get through Rustlings without too much help, it was often less clear to me why something was or should be done in a particular way, particularly around lifetimes.
For example, the first chunk of code here gives an error:
eprintln!(
"{{\"token\": \"TK_{:?}\", \"begin\": {}, \"end\": {}, \"body\": \"{}\"}}",
tk,
self.begin,
self.end,
self.token_body()
);And the fix:
let begin = self.begin;
let end = self.end;
eprintln!(
"{{\"token\": \"TK_{:?}\", \"begin\": {}, \"end\": {}, \"body\": \"{}\"}}",
tk,
begin,
end,
self.token_body()
);Maybe this makes perfect sense once you’ve been working with the borrow checker and this particular family of macros for a while, but it was surprising to me.
That being said having only read about Rust for many years, I was prepared for a struggle with the borrow checker that never materialized when writing the interpreter. Maybe it’s the straightforward nature of this program but it seemed that Rustlings equipped me well enough to reason about what needed to be done. As I wanted the parser to remain allocation free, it got a lifetime annotation. Other than that and figuring out how to handle procedure data destruction there weren’t any real stumbling blocks.
Binding to C and adding dependencies
Adding a dependency was once again pretty easy and it turned out zig-clap was (I assume) inspired by clap-rs.
There’s a bit more ceremony around compiling and accessing C than in Zig. There’s a cc crate that handles compiling and linking C, and C code needs to be wrapped in unsafe blocks.
Overall thoughts
I think the Rust program ends up being pretty similar to the Zig one, aside from borrow checking instead of manual memory management. Pattern matching is exceptionally helpful for writing interpreters & compilers but here doesn’t get used in a way that’s different from Zig switch. While Rustlings did take me longer to get through than Ziglings, once I was past that it didn’t take me any longer to write this than the Zig version.
👍 Would Rust again.
#In the end
This was a fun exercise that helped me get a taste of each language without committing to a big project. The implementations could probably use a lot more polish to make them Rusty. Or Ziggy. Or Rustonic or whatever you’d term it, but I’m stopping here.
I was also surprised that both the Rust and Zig versions are a couple seconds
faster than C++ on the silly fib(35) benchmark. I intentionally didn’t change
much about how the code works, so I’m curious why that is.
There’s a few ways in which this falls short of really getting at the differing philosophies of each language.
Simple Tcl interpreters avoid the expression problem because everything is a string. Since strings don’t have cyclical references and can just be copied everywhere, they also don’t need garbage collection.
We also didn’t get into metaprogramming (comptime or macros) but I can definitely see cases for this shape of program where they’d really improve safety and maintenance over what I generally end up doing in C.
Something like an R4RS Scheme interpreter with an extensible type system would get you into this territory while still being manageable within ~weeks of work but was more than I wanted to bite off.
Because of this and because I enjoy not having my house TP’d and egged, I also don’t have a hot take on which of these is better nor have I decided which to use yet. I really liked:
- Actual dependency management and build systems as first class citizens
- Built in tests, error handling, syntax, quality of life is so much better
- The language servers for both Just Worked (TM) so I got a nice editor experience
- Null safety 🙏🙏🙏
Lots of progress has been made since I last experimented with this in 2018 which in retrospect feels almost like the dark ages. Thanks to the implementers and communities for pushing forward.