Nary a week ago, I typed a harmless expression into my Memphis REPL: 4 == 4 == 4.
My REPL’s response? False.
I’m glad it can speak its mind, but the gall!
Apparently, you can’t just treat a chain of comparison operators like a tree of binary expressions. According to my BlueSky timestamps, it took me 13 minutes to figure this out. And I’m here today so you don’t make the same misunderstanding I did.
Fixing the parser
Expressions in Python are parsed in a left-associative way, meaning something like 2 + 3 + 4 will be parsed as (2 + 3) + 4. This works fine for numerical operations like addition, and we can rely on operator precedence and parentheses to control evaluation order.
If you apply this same approach to comparison operators, like I was doing, you get this: (4 == 4) == 4. Which reduces to True == 4. Which is False. Where I thought my REPL was giving me sass, it was just doing math.
How can we fix this? We need to move from my tree-based approach to a flat structure, something that records all the operators and operands in order. I ended up introducing a new Expr variant to represent these chains.
enum Expr {
...
BinaryOperation {
left: Box<Expr>,
op: BinOp,
right: Box<Expr>,
},
ComparisonChain {
left: Box<Expr>,
ops: Vec<(CompareOp, Expr)>,
},
....
}
You may be wondering why we need to store the CompareOp in between each right operand. My first thought was that we’d only need to store it once! As I looked more into the Python rules (AKA asked ChatGPT for test cases), I learned that Python allows you to write heterogeneous chains. Take these examples.
a = 1 < 2 == 2 < 3 # True
b = 1 == 2 != 3 # False
c = 2 in [1,2,3] in [[1,2,3],[4,5,6]] # True
Honestly, I’d be pretty annoyed if I saw any of these in code. But Python allows them, so we must fall in line.
Here are my new parser tests, along with a Rust macro to make it easier to build these expressions.
fn operator_chaining() {
let input = "a == b == c";
let expected_ast = cmp_chain!(var!("a"), [(Equals, var!("b")), (Equals, var!("c")),]);
assert_ast_eq!(input, expected_ast, Expr);
let input = "a == b < c > d";
let expected_ast = cmp_chain!(
var!("a"),
[
(Equals, var!("b")),
(LessThan, var!("c")),
(GreaterThan, var!("d")),
]
);
assert_ast_eq!(input, expected_ast, Expr);
}
Now that the parser knows how to build these chains, we can begin to interpret them correctly.
Fixing the treewalk interpreter
The treewalk implementation is closest to my mental model, so I began there. The main trick is to reuse the right-hand side of each evaluation in the next comparison. Once we hit the first False result, we can short-circuit the entire operation. If we got to the end without seeing any False results, we are free to return True.
fn evaluate_comparison_chain(
&self,
left: &Expr,
ops: &[(CompareOp, Expr)],
) -> TreewalkResult<TreewalkValue> {
let mut left = self.evaluate_expr(left)?;
for (op, right) in ops {
let right = self.evaluate_expr(right)?;
// ideally, we wouldn't need to clone `right` here, but this requires ownership for now.
let result = self.evaluate_compare_op(left, op, right.clone())?;
if !result.as_boolean() {
return Ok(TreewalkValue::Bool(false));
}
left = right;
}
Ok(TreewalkValue::Bool(true))
}
The other fun part about the treewalk interpreter is that it’s further along, which means I support operator overloading. Each time a comparison chain evaluates a particular operation, under the hood it is calling a dunder method on an object.
fn evaluate_compare_op(
&self,
left: TreewalkValue,
op: &CompareOp,
right: TreewalkValue,
) -> TreewalkResult<TreewalkValue> {
use CompareOp::*;
match op {
In => self.invoke_method(&left, &Dunder::Contains, args![right]),
NotIn => {
let contains = self.invoke_method(&left, &Dunder::Contains, args![right])?;
Ok(contains.not())
}
Equals => self.invoke_method(&left, &Dunder::Eq, args![right]),
NotEquals => self.invoke_method(&left, &Dunder::Ne, args![right]),
LessThan => self.invoke_method(&left, &Dunder::Lt, args![right]),
GreaterThan => self.invoke_method(&left, &Dunder::Gt, args![right]),
LessThanOrEqual => self.invoke_method(&left, &Dunder::Le, args![right]),
GreaterThanOrEqual => self.invoke_method(&left, &Dunder::Ge, args![right]),
Is => Ok(TreewalkValue::Bool(left.is(&right))),
IsNot => Ok(TreewalkValue::Bool(!left.is(&right))),
}
}
This part technically already existed, but there’s something satisfying about watching a new feature click into an old mechanism. These comparisons used to live inside my binary operator evaluation, back when CompareOp didn’t exist and comparison chains and I didn’t yet understand each other.
With the treewalk interpreter working smoothly, it was time to bring the same behavior to the bytecode VM.
Fixing the bytecode VM
When I sat down to write this section, I read through my code to begin to explain it. In classic rubber-duck fashion, I realized I’d overcomplicated the whole thing. I now present the simplified pseudocode of how the bytecode looks for operator chaining.
evaluate left
for each (op, right):
evaluate right
compare op
if false: goto end
if not last iteration: pop true
else: leave it
end:
Remember how we had to save the right-hand side for the next comparison? That’s what we’re still missing in this pseudocode. The line compare op will pop two operands off the stack and compare them, consuming both operands in the process. If we want the right operand to still be around afterwards, we’re gonna need to intervene.
We can do this by running a DupTop and a RotThree before we do the actual comparison. (CPython uses COPY and SWAP.) The former makes a copy of the right-hand operand, while the latter moves it to the third spot on the stack (hence the rotate three).
Here’s what this looks like in Rust.
fn compile_comparison_chain(
&mut self,
left: &Expr,
ops: &[(CompareOp, Expr)],
) -> CompilerResult<()> {
if ops.is_empty() {
panic!("Comparison chain must have >= 1 op.");
}
self.compile_expr(left)?;
let mut false_jumps = vec![];
for (i, (op, right)) in ops.iter().enumerate() {
let last_op = i == ops.len() - 1;
self.compile_expr(right)?;
// Preserve the right-hand side for the next comparison
if !last_op {
self.emit(Opcode::DupTop)?;
self.emit(Opcode::RotThree)?;
}
self.emit(Opcode::from(op))?;
// If any comparison evaluates to False, jump to end.
// Otherwise, pop the True and continue the chain.
// Unless it's the last operation, and we should leave the result on the stack.
if !last_op {
// At the end of the loop, we will patch this with a JumpIfFalse
false_jumps.push(self.emit_placeholder()?);
self.emit(Opcode::PopTop)?;
}
}
// Patch all fail jumps to here
for placeholder in false_jumps {
let offset = self.forward_offset_to(placeholder)?;
self.emit_at(placeholder, Opcode::JumpIfFalse(offset))?;
}
Ok(())
}
The updates to the VM itself were minimal, we just needed to support the new DupTop and RotThree.
Opcode::DupTop => {
let x = self.peek()?;
self.push(x)?;
}
Opcode::RotThree => {
// Before:
// c <- TOS
// b
// a
//
// After:
// b <- TOS
// a
// c
let c = self.pop()?;
let b = self.pop()?;
let a = self.pop()?;
self.push(c)?;
self.push(a)?;
self.push(b)?;
}
My initial implementation only worked when all the operands were equal, like 2 == 2 == 2. That told me I had a bug in the RotThree implementation which I corrected (and left better notes behind for future-me).
Putting it all together
With both interpreter engines updated, it was time to add tests to crosscheck. Here’s a subset of the chaining tests which are run through both engines.
#[test]
fn operator_chaining() {
let input = "2 == 2 == 2";
assert_crosscheck_return!(input, MemphisValue::Boolean(true));
let input = "2 == 2 == 22";
assert_crosscheck_return!(input, MemphisValue::Boolean(false));
let input = "2 == 2 == 2 < 3";
assert_crosscheck_return!(input, MemphisValue::Boolean(true));
let input = "1 < 2 < 3 < 4";
assert_crosscheck_return!(input, MemphisValue::Boolean(true));
let input = "1 < 2 < -3 < 4";
assert_crosscheck_return!(input, MemphisValue::Boolean(false));
let input = "1 < 2.0 < 3";
assert_crosscheck_return!(input, MemphisValue::Boolean(true));
let input = "2 in [1,2,3] in [[1,2,3],[4,5,6]]";
assert_crosscheck_return!(input, MemphisValue::Boolean(true));
let input = "2 in [1,2,3] in [[4,5,6]]";
assert_crosscheck_return!(input, MemphisValue::Boolean(false));
}
👉 Curious what these examples compile to? Try it live in the Interactive Bytecode Compiler: fromscratchcode.com/bytecode-compiler
Sometimes I get lazy and/or scared and don’t add the full test suite to crosscheck, but I was determined to do this feature right. (hence the blog post.)
Along the way, I realized I’d implemented 2 < 2.5 but not 2.5 < 3. The first calls Dunder::Lt on int, while the second calls it on float. It’s fun to catch and quickly fix oversights like this. In addition, 2 == 2.0 never returned True. This was because I’d assumed that any cross-type comparison should always return False.
The end
Operator chaining isn’t a flashy feature, yet implementing it reminded me what I love about continuing to develop Memphis: the more Python behaviors I properly model—across two engines—the purer my abstractions become. And what is expertise in software, if not fluency in abstractions? That’s what keeps me coming back to build this interpreter no one asked for.
Subscribe & Save [on nothing]
Want a software career that actually feels meaningful? I wrote a free 5-day email course on honing your craft, aligning your work with your values, and building for yourself. Or just not hating your job! Get it here.
Build [With Me]
I mentor software engineers to navigate technical challenges and career growth in a supportive, sometimes silly environment. If you’re interested, you can explore my mentorship programs.
Elsewhere [From Scratch]
I also write essays and fiction about neurodivergence, meaningful work, and building a life that fits. My novella Lake-Effect Coffee is a workplace satire about burnout, friendship, and a coffee van. Read the first chapter or grab the ebook.
Top comments (0)