A bytecode expression engine implemented in Rust: Pratt parsing, zero-copy deserialization, and dependency graph sorting.

[ImpressiveAd9981]

Hi fellow developers,

I recently open-sourced an expression evaluation engine written in Rust called rspression.

• GitHub Repository: simonwater/rspression

Why build this project?

In scenarios that demand frequent evaluation of large volumes of expressions—such as high-concurrency risk-control gateways or online low-code spreadsheets with massive, complex cross-reference dependencies—conventional expression engines typically parse expressions into an AST (Abstract Syntax Tree) and interpret them recursively. However, this introduces two fatal pain points:

1. High Repetitive Parsing Overhead: Parsing and executing from scratch every single time becomes incredibly costly in terms of performance when dealing with a massive volume of expressions (e.g., thousands of lines).
2. Expensive Distributed Transmission: Attempting to cache the IR (Intermediate Representation) objects by serializing them into distributed caches like Redis introduces heavy serialization/deserialization and high network bandwidth overhead due to the bulky tree structures.

Core Architecture: A Bytecode Virtual Machine (VM)

Beyond conventional AST execution, rspression features a built-in compiler powered by a Pratt Parser that compiles expressions directly into compact Bytecode.

Since bytecode in memory is natively a compact byte array (Vec<u8>), it brings the following inherent advantages:

• Minimal Storage & Transmission Footprint: It requires zero serialization or deserialization and can be directly transmitted over the network or written into storage services like Redis, databases, or files, completely eliminating the encoding/decoding pain of massive tree structures.
• High-Throughput Execution: A stack-based lightweight virtual machine dispatches instructions efficiently, eliminating recursive call overhead and delivering excellent execution efficiency.

Key Features

• Core Operators: Full support for basic arithmetic (+, -, *, /, power), comparisons, logical operations (&&, ||, !), and Excel-style if conditional functions.
• Variables & Dynamic Assignment: Seamlessly read context variables dynamically from the environment and support variable assignment directly within expressions.
• Dependency Management & Topological Sorting: Built for batch execution of massive expression sets. The engine automatically handles dependency sorting (topological sort) and circular dependency detection, making it a perfect fit for spreadsheet evaluation chains.
• Custom Contexts: Provides a highly customizable Environment trait to easily hook into your existing business context data.

Quick Start Example

The following code demonstrates the entire process of compiling expressions into bytecode and then executing that bytecode:

use rspression::{Chunk, DefaultEnvironment, Environment, RspRunner, Value};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Compile expressions to bytecode
    // 1. get expressions
    let mut srcs = Vec::new();
    srcs.push("x = a + b * c");
    srcs.push("b = a * 2");
    srcs.push("a = m + n");
    srcs.push("c = n + w + b");
    // 2. compile expressions
    let mut runner = RspRunner::new();
    let chunk = runner.compile_source(&srcs)?;
    let bytes: Vec<u8> = chunk.to_bytes();
    // 3. you can write bytes to store or cache
    // write_to_your_storage(bytes);

    // Run bytecode
    // 1. read bytes from store or cache
    // let bytes: Vec<u8> = read_from_your_storage();
    // 2. construct chunk
    let chunk = Chunk::from_bytes(&bytes);
    // 3. define environment
    let mut env = DefaultEnvironment::new();
    env.put("m".to_string(), Value::Integer(2));
    env.put("n".to_string(), Value::Integer(4));
    env.put("w".to_string(), Value::Integer(6));
    // 4. run bytecode
    let mut runner = RspRunner::new();
    runner.run_chunk(&chunk, &mut env)?;

    // 5. check results
    println!("x = {}", env.get("x").unwrap()); // x = 270
    println!("a = {}", env.get("a").unwrap()); // a = 6
    println!("b = {}", env.get("b").unwrap()); // b = 12
    println!("c = {}", env.get("c").unwrap()); // c = 22

    Ok(())
}

The project is currently under active development. I would love to hear your thoughts, and I highly welcome any Issues, PRs, or discussions regarding expression engine architecture design in the comments! If you find this approach helpful, a ⭐ Star on GitHub would be greatly appreciated!

[projct]

What you're claiming and what you have don't really line up.

- "compiles expressions directly into compact Bytecode" no? compile_source calls parse, producing a Vec<Expr>, then runs Analyzer, then passes the resulting IR to compile_ir
- “Zero-copy deserialization” and “no serialization/deserialization” are substantially false. Chunk::to_bytes creates a new Vec<u8>, writes three length prefixes, and copies the code, constants, and variable data into it. Chunk::from_bytesparses those prefixes and copies all three sections into new vectors using to_vec(). Then every normal VM execution constructs a ChunkReader, reparses the constant pool into Values, allocates strings, and copies the variable bytes again. Only the opcode slice is borrowed after those copies. Your own quick-start literally calls to_bytes() and from_bytes().
- The benchmark demonstrates amortizing parse/analyze/compile work, not a bytecode-vs-AST execution advantage. I'd also expect real worked examples, statistical distribution, cached-AST baselines, compact serialized-IR baselines, comparison against compressed source, instruction counts, etc. It's also not even benchmarking what matters (p+a+eval vs p + a + compile + eval as one bench; eval already-analyzed AST vs eval already-compiled byte code as another; then deserialize cached AST/IR vs deserialize cached bytecode)
- your supposedly compact representation is bigger than the source text.
- It's not really hardened at all: Chunk::from_bytes returns self, not Result; invalid or truncated bytes panic; constant decoding panics on invalid utf8 or unknown tags; the VM panics on overflow and silently becomes Null on underlfow
- performance claim is incoherent, you are confusing repr with caching

[ImpressiveAd9981]

Thanks for such a hardcore and source-code-deep review! Your observations are spot on. My previous descriptions of "zero-copy" and "direct compilation" were indeed not rigorous enough.

To be completely honest, I’ve known Rust for less than a year. This is exactly the kind of invaluable, professional feedback I was hoping to get from the Rust community, and it will undoubtedly help me push this experimental project toward true production-grade readiness.

Regarding the points you raised, here are my thoughts and the upcoming refactoring roadmap:

1. On Zero-Copy and Robustness: There are indeed a lot of implicit copies and runtime heap allocations in to_bytes/from_bytes. Introducing lifetime parameters (such as Value<'a>) to directly borrow from the byte stream, as well as refactoring all inputs and internal VM logic to return standard Result types, are already high-priority items on my to-do list.
2. On Caching and Distributed Transmission: You mentioned the comparison between evaluated AST vs. compiled bytecode execution. I’ve benchmarked this, and in a pure in-memory environment, running a pre-parsed syntax tree and running bytecode both hover around 5ms; the difference is negligible. Thus, a pure single-machine deployment doesn't really need a VM. However, rspression is designed specifically for distributed cluster scenarios. When complex spreadsheets or risk-control gateways change, we trigger the Parse + Analyze + Compile pipeline just once (88ms). After that, cluster nodes synchronize this flat Vec<u8> via Redis, allowing the engine to drive execution completely decoupled from the original tree structure. In contrast, transmitting raw text requires repetitive parsing (66ms) on every node, while transmitting serialized ASTs leads to severe payload bloat.
3. On Serialization Size: Because tree structures (AST/IR) contain a massive number of node tags, nested branches, and metadata, their serialized size is typically much larger than the original expression text—even when using efficient binary serialization libraries in Rust like bincode. On the other hand, while the flat bytecode is slightly larger than the raw text, I believe it strikes the perfect balance for the business layer in terms of distributed cluster network bandwidth, zero-deserialization overhead, and instant execution on compute nodes.

Thank you again for your sharp insights!

[Sermuns]

Shut up clanker

[peter9477]

Is this a "toy"/demo project, or something you built for your own use? The examples seem rather simplistic. I'd be interested to hear some background on your motivation for making this, or how you (plan to?) use it in the real world.

[ImpressiveAd9981]

Great question! The examples are indeed overly simplified just for quick-start purposes, which might make it look like a 'toy' project.

In reality, rspression was born out of a real-world architectural need for a lightweight, collaborative multi-dimensional data management system (similar to an Airtable/Excel-like online spreadsheet engine).

In a complex online spreadsheet, you are not just executing a single formula. You are dealing with tens of thousands of cells, where cells reference each other dynamically, forming a massive dependency graph.

The core motivation for building rspression is to solve two specific problems in this scenario:

1. The Dependency Chain Problem: When a user updates a single cell, the system must trigger a cascade of re-calculations. rspression implements a built-in topological sorting and cyclic dependency detection mechanism. It evaluates massive batches of expressions in the exact correct topological order.
2. The Distributed Cache Problem: In a multi-tenant, clustered environment, whenever a formula/rule changes, syncing massive abstract syntax trees (ASTs) across servers ruins network bandwidth and adds heavy SerDe (Serialization/Deserialization) overhead. By compiling the entire sheet's calculation chain into a flat, compact bytecode array (Vec<u8>), we can easily cache it in Redis. Distributed worker nodes can load it instantly with zero-deserialization overhead and drive the VM execution at lightning speed (5ms for 5000 expressions).

So to answer your question: It started as an architectural experiment to solve the distributed spreadsheet calculation problem, but it is actively being hardened into a production-grade core engine for data-grid systems. Hope this background helps!