Tsonnet #30 - Dabbling with equality
A first-pass implementation of equality in Tsonnet
Welcome to the Tsonnet series!
If you’re not following along, check out how it all started in the first post of the series.
In the previous post, I implemented object inner references:
This time, we’re tackling equality. Fair warning: this won’t be the final implementation, just the first working version. Consider this post a field report from the trenches.
On implementing equality
I’ve been dabbling with equality in Tsonnet for the past few days. At first sight, equality doesn’t seem like an operation hiding too much complexity, but as we uncover the internal details of the language, and apply the design reasoning to it, things start showing up, and you can find yourself in a rabbit hole.
To start with, the AST change is minimal -- just one more variant added to the binary operator:
The lexer and parser follow suit, as boring as it might look like:
Type checking was also surprisingly simple:
No matter what’s on the left or right, the result must be a boolean type.
And then, comes the interpreter.
In my first iteration, it was as simple as that -- the interpret_bin_op function moved below for consistency and aesthetics:
The semantic equal operator =~ compares two expr and returns a boolean. Pretty simple... for simple values, like numbers, strings, and booleans! When we start comparing objects and arrays, it becomes muddy quite fast.
I had to account for RuntimeObject, that encapsulates its own environment, and Array, that can contain RuntimeObject. If you guessed that laziness (not mine, the language’s laziness) could be a source of pain here, you guessed right. These expressions aren’t fully evaluated yet. So, I had to fully evaluate each object field in order to be able to compare every single variant, ending with this:
I know. Ugly is a compliment, to say the least!
And the magic operator implementation:
It is just a function: semantic_equal. But there’s also an alias: =~.
Pretty straightforward -- until we get to runtime_object_semantic_equal:
There’s nothing wrong with it except that we can’t guarantee it has been previously evaluated.
This is bugging me, but I have some ideas to try.
For now, this ugly and messy code was able to parse and interpret successfully this sample file:
And the cram test:
Conclusion
Equality works -- all the test cases pass, from simple numbers to nested objects with expressions. But the implementation is messier than I’d like. The core issue is that RuntimeObject and Array can contain unevaluated expressions, which forces us to evaluate on-the-fly during comparison. That’s both inefficient and error-prone.
The real problem isn’t the equality logic itself, it’s that we’re mixing concerns. The semantic_equal function in the AST shouldn’t need to know about evaluation state -- that’s the interpreter’s job. We’re essentially doing interpretation work inside what should be a pure comparison function.
Phantom types would let us encode evaluation state at compile time: expr becomes 'a expr where 'a can be either Unevaluated or Evaluated. Then semantic_equal would have the signature Evaluated expr -> Evaluated expr -> bool, and the compiler would refuse to compile if we tried to compare unevaluated expressions. Push the evaluation concern back where it belongs. But that’s an experiment for later.
For now, though, equality works. The tests pass. I’ll clean this up when I tackle the broader evaluation state problem -- which will help the Json module too, since it also suffers from needing to evaluate things at serialization time. I just hope this clean up does not trigger a big refactoring. 🤞
The entire diff can be found here.