Rerum: A Pattern Matching and Term Rewriting Library for Python

#opensource #computerscience #programming #python

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.

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:

Syntax	Meaning
`?x`	Match anything, bind to x
`?x:const`	Match only numbers
`?x:var`	Match only symbols
`?x:free(v)`	Match expressions not containing v
`?x...`	Variadic - capture remaining arguments

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)))

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

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