Rerum: Pattern Matching and Term Rewriting in Python

Rerum (Rewriting Expressions via Rules Using Morphisms) is a Python library for pattern matching and term rewriting. It makes symbolic computation accessible through a readable DSL while keeping a clean separation between trusted and untrusted code.

The Problem

Traditional symbolic math systems tend toward two extremes. Monolithic systems like Mathematica bundle everything in. Lighter tools force you to write complex recursive traversals every time you want to transform an expression. I wanted something in between: a simple, extensible system where transformation rules are data that can be loaded, combined, and inspected.

The SICP Connection

This design reflects a core idea from Structure and Interpretation of Computer Programs: when a problem domain is complex enough, the right move is to build a language for it. Rerum’s rule DSL makes transformation logic inspectable, composable, and safe.

The engine composition operators (>> for sequencing, | for union) ensure closure: combining engines yields an engine. Same principle that makes Scheme’s procedures powerful. You can pass them, return them, combine them, no special cases. Transformation strategies are first-class.

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:

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 purely declarative.

The Security Model: Rules vs. Preludes

A key architectural decision: 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 load rules from untrusted sources safely. They can only invoke operations you’ve explicitly allowed. No arbitrary code execution.

Conditional Guards

Rules can have guards, conditions that must hold 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 traversals:

# 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 compose:

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:

$ 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

Related Projects

Rerum is part of a family:

• 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: 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

Full documentation is at the GitHub repository. The examples/ directory has complete rulesets for algebra, calculus, and number theory.

Why “Rerum”?

From the Latin “rerum natura” (the nature of things), Lucretius’s work on atomic theory and natural philosophy. Felt right for a library about transforming the fundamental structure of expressions.