Rerum: A Pattern Matching and Term Rewriting Library

Rerum (Rewriting Expressions via Rules Using Morphisms) is a Python library I’ve been developing for pattern matching and term rewriting. It’s designed to make symbolic computation accessible through a readable DSL while maintaining a security-conscious architecture.

The Problem with Symbolic Computation

Traditional symbolic math systems often have two problems: either they’re monolithic (like Mathematica) with everything built-in, or they require writing complex recursive traversals every time you want to transform an expression. What I wanted was something in between: a simple, extensible system where transformation rules are data that can be loaded, combined, and reasoned about.

The SICP Connection

This design reflects a core insight from Structure and Interpretation of Computer Programs: when a problem domain is complex enough, the solution is often to build a language for that domain. Rerum’s rule DSL doesn’t just simplify symbolic computation—it makes the transformation logic inspectable, composable, and safe.

The engine composition operators (>> for sequencing, | for union) ensure closure: combining engines yields an engine. This is the same principle that makes Scheme’s procedures powerful—you can pass them, return them, and combine them without special cases. In rerum, transformation strategies are first-class citizens.

A Readable DSL

At the heart of rerum is a domain-specific language for defining rewrite rules:

# Algebraic simplification
@add-zero[100] "x + 0 = x": (+ ?x 0) => :x
@mul-one[100]:  (* ?x 1) => :x
@mul-zero[100]: (* ?x 0) => 0

Each rule has:

• A name: @add-zero for debugging and tracing
• Optional priority: [100] determines firing order when multiple rules match
• Optional description: Human-readable explanation
• A pattern: (+ ?x 0) matches addition with zero
• A skeleton: :x is the replacement

The pattern syntax is expressive:

Symbolic Differentiation in 15 Lines

Here’s a calculus ruleset that computes symbolic derivatives:

[basic-derivatives]
@dd-const[100]: (dd ?c:const ?v:var) => 0
@dd-var-same[100]: (dd ?x:var ?x) => 1
@dd-var-diff[90]: (dd ?y:var ?x:var) => 0

[rules]
@dd-sum: (dd (+ ?f ?g) ?v:var) => (+ (dd :f :v) (dd :g :v))
@dd-product: (dd (* ?f ?g) ?v:var) => (+ (* (dd :f :v) :g) (* :f (dd :g :v)))
@dd-power: (dd (^ ?f ?n:const) ?v:var) => (* :n (* (^ :f (- :n 1)) (dd :f :v)))
@dd-exp: (dd (exp ?f) ?v:var) => (* (exp :f) (dd :f :v))
@dd-log: (dd (ln ?f) ?v:var) => (/ (dd :f :v) :f)
@dd-sin: (dd (sin ?f) ?v:var) => (* (cos :f) (dd :f :v))
@dd-cos: (dd (cos ?f) ?v:var) => (* (- (sin :f)) (dd :f :v))

With these rules loaded:

from rerum import RuleEngine, E

engine = RuleEngine.from_file("calculus.rules")

# d/dx(x^2) = 2x
engine(E("(dd (^ x 2) x)"))  # => (* 2 (* (^ x 1) 1))

The result needs simplification (another ruleset), but the differentiation itself is completely declarative.

The Security Model: Rules vs. Preludes

A key architectural decision in rerum is the separation between rules (untrusted, serializable) and preludes (trusted Python code). Rules define structural transformations; they can reference operations via the (! op args...) compute form, but those operations must be explicitly provided by the host.

from rerum import RuleEngine, ARITHMETIC_PRELUDE

engine = (RuleEngine()
    .with_prelude(ARITHMETIC_PRELUDE)  # Enables +, -, *, /, ^
    .load_dsl('''
        @fold-add: (+ ?a ?b) => (! + :a :b)
                   when (! and (! const? :a) (! const? :b))
    '''))

engine(E("(+ 1 2)"))  # => 3 (computed by prelude)
engine(E("(+ x 2)"))  # => (+ x 2) (no change - x isn't const)

This means you can safely load rules from untrusted sources. They can only invoke operations you’ve explicitly allowed. No arbitrary code execution.

Conditional Guards

Rules can have guards - conditions that must be satisfied for the rule to fire:

@abs-pos: (abs ?x) => :x when (! > :x 0)
@abs-neg: (abs ?x) => (! - 0 :x) when (! < :x 0)
@abs-zero: (abs ?x) => 0 when (! = :x 0)

Guards use the same (! ...) compute syntax as skeletons, with access to predicates like const?, var?, list?, and comparison operators.

Rewriting Strategies

Different problems need different traversal strategies:

# exhaustive (default): Apply rules until no more apply
result = engine(expr, strategy="exhaustive")

# once: Apply at most one rule anywhere
result = engine(expr, strategy="once")

# bottomup: Simplify children before parents
result = engine(expr, strategy="bottomup")

# topdown: Try parent before children
result = engine(expr, strategy="topdown")

Engine Composition

Engines can be combined in various ways:

expand = RuleEngine.from_dsl("@square: (square ?x) => (* :x :x)")
simplify = RuleEngine.from_file("algebra.rules")

# Sequence: expand first, then simplify
normalize = expand >> simplify
normalize(E("(square 3)"))  # => 9

# Union: combine all rules
combined = algebra | calculus

Interactive REPL

The CLI includes an interactive mode for exploration:

$ rerum
rerum> @add-zero: (+ ?x 0) => :x
Added 1 rule(s)
rerum> (+ y 0)
y
rerum> :load examples/calculus.rules
Loaded 12 rule(s)
rerum> :trace on
rerum> (dd (^ x 3) x)
=> (* 3 (* (^ x 2) 1))
Trace: dd-power

Scripts can be run directly or piped:

$ rerum calc.rerum
$ echo "(+ 1 2)" | rerum -r algebra.rules -p full -q
3

Connection to Other Projects

Rerum is part of a family of related projects:

• xtk - Expression Toolkit with MCP server integration for Claude Code
• symlik - Symbolic likelihood models using term rewriting for automatic differentiation of statistical models
• jsl - A network-native language where code is JSON, using similar s-expression structure

The common thread is treating symbolic expressions as first-class citizens that can be transformed, serialized, and reasoned about programmatically.

Getting Started

pip install rerum

from rerum import RuleEngine, E

engine = RuleEngine.from_dsl('''
    @add-zero: (+ ?x 0) => :x
    @mul-one: (* ?x 1) => :x
    @mul-zero: (* ?x 0) => 0
''')

print(engine(E("(* (+ x 0) 0)")))  # => 0

The full documentation is at the GitHub repository. Check out the examples/ directory for complete rulesets covering algebra, calculus, and number theory.

Why “Rerum”?

The name comes from the Latin phrase “rerum natura” (the nature of things) - Lucretius’s famous work on atomic theory and natural philosophy. It felt fitting for a library about transforming the fundamental structure of expressions.