Lychee Technology Inc.

Appearance

From Lambda to Bytecode: Inside the LTSeq Expression System ​

Summary: Python lambdas are not serializable and cannot cross language boundaries. LTSeq still turns lambda r: r.age > 18 into a cross-language executable expression tree, using SchemaProxy interception, operator overloading, and AST transformation. This article traces the expression pipeline from Python through Rust to DataFusion.

1. The problem: why can't we just pass a lambda? ​

A Python lambda is a closure object. You can pickle a simple lambda, but you cannot pass it to Rust, which doesn't understand Python's bytecode format, let alone which external variables the closure captured. The usual workaround is to make users write strings, the way SQL does, at the cost of IDE completion and type safety.

LTSeq takes a different route. It doesn't execute the lambda; it stages a performance of an execution and captures the user's intent along the way.

2. Layer one: SchemaProxy interception ​

When a user writes t.filter(lambda r: r.age > 18), LTSeq doesn't pass real data to r. Instead, it creates a SchemaProxy object (py-ltseq/ltseq/expr/proxy.py:8):

python
class SchemaProxy:
    def __init__(self, schema: Dict[str, str]):
        self._schema = schema  # {"age": "int64", "name": "string", ...}

    def __getattr__(self, name: str):
        if name in self._schema:
            return ColumnExpr(name)  # Returns an expression node, not a value
        raise AttributeError(f"Column '{name}' not found in schema")

r is not a row of data. It's a trap. When Python executes r.age, __getattr__ fires and returns a ColumnExpr("age") expression node rather than 42 or any actual value.

This is straightforward metaprogramming: use Python's dynamic nature to turn execution into description.

For linked tables, NestedSchemaProxy (proxy.py:80) handles the prefix-based naming convention:

python
class NestedSchemaProxy:
    def __init__(self, alias: str, prefixed_columns: Dict[str, str]):
        self._alias = alias
        prefix = f"{alias}_"
        self._column_map = {
            col.replace(prefix, "", 1): col for col in prefixed_columns.keys()
        }

    def __getattr__(self, name: str) -> ColumnExpr:
        full_col_name = self._column_map[name]
        return ColumnExpr(full_col_name)  # r.prod.name -> ColumnExpr("prod_name")

3. Layer two: operator overloading builds the AST ​

ColumnExpr inherits from the Expr base class (py-ltseq/ltseq/expr/base.py:219), which overloads 22 operators:

python
class Expr(ABC):
    def __gt__(self, other):
        return BinOpExpr("Gt", self, self._coerce(other))

    def __add__(self, other):
        return BinOpExpr("Add", self, self._coerce(other))

    def __and__(self, other):
        return BinOpExpr("And", self, self._coerce(other))

    @staticmethod
    def _coerce(value):
        if isinstance(value, Expr):
            return value
        return LiteralExpr(value)  # Auto-wrap Python constants

So r.age > 18 executes as:

  1. r.age -> ColumnExpr("age")
  2. ColumnExpr("age").__gt__(18) is called
  3. _coerce(18) -> LiteralExpr(18)
  4. Returns BinOpExpr("Gt", ColumnExpr("age"), LiteralExpr(18))

The lambda's whole "execution" produces an expression tree, not a boolean value.

The complete operator table ​

CategoryOperatorsReturn Type
Arithmetic+, -, *, /, //, %BinOpExpr
Comparison==, !=, <, <=, >, >=BinOpExpr
Logical&, |BinOpExpr
Unary~, abs()UnaryOpExpr / CallExpr
Right-hand__radd__, __rsub__, etc.BinOpExpr

Note that __eq__ and __ne__ deliberately override object.__eq__ to return Expr instead of bool. This is an intentional design choice with # type: ignore annotations acknowledging the violation.

The is None problem and AST transformation ​

Python's is operator cannot be overridden. r.age is None always returns False, because a ColumnExpr object is not None, which produces silent bugs.

LTSeq fixes this with AST transformation (py-ltseq/ltseq/expr/transforms.py:11):

python
class IsNoneTransformer(ast.NodeTransformer):
    """Rewrites `x is None` to `x == None`, which CAN be intercepted by __eq__"""
    def visit_Compare(self, node):
        for i, op in enumerate(node.ops):
            if isinstance(op, ast.Is):
                node.ops[i] = ast.Eq()      # is -> ==
            elif isinstance(op, ast.IsNot):
                node.ops[i] = ast.NotEq()    # is not -> !=
        return node

Before calling the lambda, LTSeq obtains the lambda's source code, parses and transforms it via the ast module, then recompiles it with exec. This way, r.age is None becomes r.age == None, triggering __eq__ to return CallExpr("is_null", ...).

4. Method chaining: expressions of any depth ​

ColumnExpr's __getattr__ handles both column access and method calls (py-ltseq/ltseq/expr/types.py:41):

python
class ColumnExpr(Expr):
    def __getattr__(self, method_name):
        def method_call(*args, **kwargs):
            return CallExpr(method_name, args, kwargs, on=self)
        return method_call

So r.price.shift(1) executes as:

  1. r.price -> ColumnExpr("price")
  2. .shift -> triggers __getattr__("shift"), returns a closure
  3. (1) -> calls the closure, returns CallExpr("shift", args=(1,), on=ColumnExpr("price"))

CallExpr also has __getattr__, enabling chained calls:

python
r.price.rolling(3).mean()
# -> CallExpr("mean", on=CallExpr("rolling", args=(3,), on=ColumnExpr("price")))

Accessors: type-aware method sets ​

Accessors provide domain-specific method collections. r.name.s returns a StringAccessor, and r.date.dt returns a TemporalAccessor:

python
# String operations (13 methods)
r.url.s.starts_with("/product")    # prefix check
r.name.s.lower()                    # to lowercase
r.text.s.regex_match(r"\d+")       # regex matching
r.name.s.lower().s.contains("test") # chaining works because CallExpr also has .s

# Temporal operations (8 methods)
r.date.dt.year()                    # extract year
r.date.dt.add(days=30)             # date arithmetic
r.start.dt.diff(r.end)             # difference in days

Chaining works because both ColumnExpr and CallExpr define the .s and .dt properties, each returning the appropriate accessor wrapping the expression.

5. Serialization: expression tree to JSON dict ​

Every Expr subclass implements .serialize(), recursively converting the tree structure into nested dictionaries:

python
# CallExpr.serialize() see py-ltseq/ltseq/expr/types.py:93
def serialize(self):
    def serialize_value(v):
        if isinstance(v, Expr):
            return v.serialize()
        return LiteralExpr(v).serialize()

    return {
        "type": "Call",
        "func": self.func,
        "args": [serialize_value(arg) for arg in self.args],
        "kwargs": {k: serialize_value(v) for k, v in self.kwargs.items()},
        "on": self.on.serialize() if self.on else None,
    }

A complex expression's serialized form:

python
# lambda r: r.eventtime - r.eventtime.shift(1) > 1800

{
  "type": "BinOp", "op": "Gt",
  "left": {
    "type": "BinOp", "op": "Sub",
    "left": {"type": "Column", "name": "eventtime"},
    "right": {
      "type": "Call", "func": "shift",
      "args": [{"type": "Literal", "value": 1, "dtype": "Int64"}],
      "on": {"type": "Column", "name": "eventtime"}
    }
  },
  "right": {"type": "Literal", "value": 1800, "dtype": "Int64"}
}

Automatic type inference ​

LiteralExpr (core_types.py:8) automatically infers the dtype from the Python value:

python
def _infer_dtype(self) -> str:
    if isinstance(self.value, bool): return "Boolean"
    elif isinstance(self.value, int): return "Int64"
    elif isinstance(self.value, float): return "Float64"
    elif isinstance(self.value, str): return "String"
    elif self.value is None: return "Null"
    else: return "String"

Note that bool is checked before int because in Python, bool is a subclass of int.

6. Rust side: deserialization and optimization ​

6.1 The PyExpr Enum (src/types.rs:10) ​

Rust receives expressions via a six-variant enum:

rust
pub enum PyExpr {
    Column(String),
    Literal { value: String, dtype: String },
    BinOp { op: String, left: Box<PyExpr>, right: Box<PyExpr> },
    UnaryOp { op: String, operand: Box<PyExpr> },
    Call { func: String, args: Vec<PyExpr>, kwargs: HashMap<String, PyExpr>, on: Box<PyExpr> },
    Window { expr: Box<PyExpr>, partition_by: Option<Box<PyExpr>>, ... },
}

dict_to_py_expr() (src/types.rs:280) recursively deserializes PyDict into this enum:

rust
pub fn dict_to_py_expr(dict: &Bound<'_, PyDict>) -> Result<PyExpr, PyExprError> {
    let expr_type = dict.get_item("type")...extract::<String>()?;
    match expr_type.as_str() {
        "Column"  => parse_column_expr(dict),
        "Literal" => parse_literal_expr(dict),
        "BinOp"   => parse_binop_expr(dict),   // recursive
        "UnaryOp" => parse_unaryop_expr(dict),  // recursive
        "Call"    => parse_call_expr(dict),      // recursive
        "Window"  => parse_window_expr(dict),    // recursive
        _         => Err(PyExprError::UnknownVariant(expr_type)),
    }
}

6.2 Optimization Pass (src/transpiler/optimization.rs) ​

Before transpiling to DataFusion Expr, LTSeq runs an expression optimization pass:

Constant folding evaluates constant expressions at compile time.

rust
// try_fold_binop()
// 1 + 2 -> 3
// 10 / 2 -> 5 (with divide-by-zero guard)
// 3 > 2 -> true

Boolean simplification eliminates redundant logical operations.

rust
// try_simplify_boolean()
// x & True  -> x       x & False -> False
// x | False -> x       x | True  -> True

Literal construction is type-aware: when integer division yields a whole number, the result keeps its Int64 type instead of being promoted to Float64.

rust
fn make_literal_f64(value: f64) -> PyExpr {
    if value.fract() == 0.0 && value.abs() < i64::MAX as f64 {
        PyExpr::Literal { value: (value as i64).to_string(), dtype: "Int64".to_string() }
    } else {
        PyExpr::Literal { value: value.to_string(), dtype: "Float64".to_string() }
    }
}

6.3 Transpiling to DataFusion Expr (src/transpiler/mod.rs) ​

The optimized PyExpr is converted to DataFusion's Expr:

rust
pub fn pyexpr_to_datafusion(py_expr: PyExpr, schema: &ArrowSchema) -> Result<Expr, String> {
    let optimized = optimize_expr(py_expr);  // Optimization pass
    pyexpr_to_datafusion_inner(optimized, schema)
}

The transpiler handles 30+ function call types, including:

  • Conditional: if_else -> DataFusion CASE WHEN
  • String ops: str_contains -> strpos(col, pattern) > 0, str_slice -> substring(col, start+1, len) (note the 0-based to 1-based index conversion)
  • Temporal ops: dt_add -> col + IntervalMonthDayNano
  • NULL handling: fill_null -> coalesce(col, default)

7. Window functions: dual-path execution ​

Window functions are the most complex expression type. contains_window_function() (src/transpiler/mod.rs:431) recursively detects them in the expression tree, and once detected a specialized window path takes over.

Primary path: native window Expr (src/transpiler/window_native.rs) ​

Directly constructs DataFusion's Expr::WindowFunction, staying lazy without materialization:

rust
// shift(1) -> LAG(col, 1)
fn convert_shift(on_expr, args, sort_exprs, schema) -> Result<Expr, String> {
    let shift_n = extract_shift_amount(args)?;
    if shift_n > 0 {
        // LAG: look backward
        Expr::WindowFunction(lag(col, shift_n, default))
    } else {
        // LEAD: look forward
        Expr::WindowFunction(lead(col, -shift_n, default))
    }
}

There's a critical DataFusion API limitation to work around (window_native.rs:102): DataFusion's builder API cannot directly convert an AggregateFunction to a WindowFunction. LTSeq manually destructures the aggregate function's UDF and re-wraps it:

rust
pub fn aggregate_to_window(agg_expr: Expr, ...) -> Result<Expr, String> {
    match agg_expr {
        Expr::AggregateFunction(agg_func) => {
            // Manually extract AggregateUDF, re-wrap as WindowFunction
            Ok(Expr::WindowFunction(Box::new(WindowFunctionExpr {
                fun: WindowFunctionDefinition::AggregateUDF(agg_func.func),
                params: WindowFunctionParams {
                    args, partition_by, order_by, window_frame, ...
                },
            })))
        }
    }
}

Fallback path: SQL string (src/transpiler/sql_gen.rs) ​

When the native path fails, LTSeq falls back to generating a SQL string and executing via session.sql(). Rolling aggregations use encoded markers:

rust
// rolling(3).mean() -> "__ROLLING_AVG__(price)__3"
// Later decoded in window.rs to:
// AVG(price) OVER (ORDER BY ... ROWS BETWEEN 2 PRECEDING AND CURRENT ROW)

8. The expression type hierarchy ​

                    Expr (abstract)
                     |
        +------------+-------------+-------------+
        |            |             |             |
   ColumnExpr   LiteralExpr   BinOpExpr    UnaryOpExpr
   r.age        18, "hello"   r.a > r.b    ~r.flag
        |
        +-- .s -> StringAccessor
        |         .contains(), .lower(), .split(), ...
        |
        +-- .dt -> TemporalAccessor
        |          .year(), .month(), .add(), .diff()
        |
        +-- .__getattr__() -> CallExpr
             .shift(1), .rolling(3), .fill_null(0), ...
                  |
                  +-- .over() -> WindowExpr
                       row_number().over(partition_by=r.dept)

Standalone expression functions (expr/base.py:7-217) ​

Beyond operator-based expressions, LTSeq provides top-level functions:

python
from ltseq.expr import if_else, count_if, row_number, rank, dense_rank, ntile

# Conditional
result = if_else(r.age > 18, "adult", "minor")

# Conditional aggregation
count_if(r.status == "active")
sum_if(r.status == "active", r.amount)

# Ranking (with window specification)
row_number().over(partition_by=r.department, order_by=r.salary, descending=True)
dense_rank().over(partition_by=r.region, order_by=r.revenue)
ntile(4).over(order_by=r.score)

9. The end-to-end pipeline ​

The full path of t.filter(lambda r: r.age > 18):

Step 1: User writes lambda
  lambda r: r.age > 18

Step 2: TransformMixin.filter() calls _capture_expr()
  expr_dict = self._capture_expr(predicate)

Step 3: _capture_expr() calls _lambda_to_expr()
  -> Applies IsNoneTransformer (AST rewrite)
  -> Creates SchemaProxy from self._schema
  -> Calls fn(proxy) to "execute" the lambda

Step 4: Operator overloading builds expression tree
  proxy.age -> ColumnExpr("age")
  ColumnExpr("age") > 18 -> BinOpExpr("Gt", ColumnExpr("age"), LiteralExpr(18))

Step 5: .serialize() produces nested dict
  {"type": "BinOp", "op": "Gt",
   "left": {"type": "Column", "name": "age"},
   "right": {"type": "Literal", "value": 18, "dtype": "Int64"}}

Step 6: Dict crosses the Python-Rust boundary
  self._inner.filter(expr_dict)

Step 7: Rust processes the dict
  dict_to_py_expr() -> PyExpr::BinOp { op: "Gt", ... }
  optimize_expr()   -> (no optimization needed for this simple case)
  pyexpr_to_datafusion() -> col("age").gt(lit(18))

Step 8: DataFusion creates a new lazy plan
  df.filter(expr) -> new DataFrame (not yet executed)

Step 9: Result wrapped in new LTSeqTable
  LTSeqTable::from_df_with_schema() -> new table with same schema

10. Pitfalls ​

and/or vs &/| ​

Python's and/or cannot be overridden. They short-circuit and never call __and__/__or__:

python
# WRONG: Python directly short-circuits, no operator overloading triggered
t.filter(lambda r: r.age > 18 and r.name != "test")

# CORRECT: Use & and |, which trigger __and__/__or__
t.filter(lambda r: (r.age > 18) & (r.name != "test"))

== ambiguity ​

After __eq__ is overloaded, Expr objects can't be used in Python logic like if expr == something, since that returns an Expr rather than a bool. It's an intentional trade-off.

Window functions require sorting ​

Window function semantics depend on row order. Call .sort() or .assume_sorted() before using shift(), rolling(), or diff(), or the results are meaningless.

Lookup expression memory ​

LookupExpr uses a class-level table registry (_table_registry) to maintain references to target tables. The registry is cleared after derive() completes to prevent memory leaks, but be aware that constructing many LookupExpr objects without calling derive() will accumulate references.

11. Summary ​

LTSeq's expression system is a cross-language expression compiler:

Python Lambda (source language)
  -> SchemaProxy interception (lexical analysis)
  -> Operator overloading (parsing, AST construction)
  -> .serialize() (code generation, produces JSON IR)
  -> dict_to_py_expr() (deserialization to Rust IR)
  -> optimize_expr() (optimization pass)
  -> pyexpr_to_datafusion() (final code generation, DataFusion Expr)

Users write Pythonic lambdas and get Rust-level execution performance. Python's dynamic nature, usually treated as a performance liability, turns into an asset when used as a metaprogramming tool for expression capture.

Next article: LTSeq's most complex component, the 2,400-line linear scan bytecode engine and the parallel pattern matching algorithms.