Building OPS5 in Go: Implementing the Rete Algorithm from Scratch

September 24, 2026

Disclaimer: Generated by AI, Gemini 3.8 through Antigravity

Work in Progress: This post is an evolving engineering log and retrospective on designing and implementing a pure Go OPS5 production rule engine from the ground up.

The Genesis: Why OPS5 and Why Go?

In the late 1970s and early 1980s, Charles Forgy at Carnegie Mellon University developed OPS5 (Official Production System 5) alongside the Rete algorithm. It became the intellectual cornerstone of expert systems, forward-chaining rule engines, and declarative knowledge representation.

Decades later, declarative production rule systems remain one of the most elegant ways to express complex, data-driven domain logic: instead of writing tangled imperative loops and state machines, you declare facts (Working Memory Elements or WMEs) and declarative production rules (if LHS then RHS). The engine takes care of matching patterns across dynamic facts at machine speed.

I set out to build a pure Go, zero-external-dependency implementation of OPS5: 👉 graemenewlands/ops5 on GitHub (and on pkg.go.dev)

My goal wasn’t just to build a toy interpreter—I wanted a robust, spec-compliant, and high-performance runtime that could take advantage of modern 64-bit multi-core architectures while preserving the classic semantics of Forgy’s original system.

Architectural Deep Dive

At the heart of the engine lies the classic Match-Resolve-Act cycle, backed by a dynamic Rete discrimination network:

+--------------------+        +---------------------+
| Dynamic Working    | -----> |  Rete Network       |
| Memory (WMEs)      |        |  (Alpha & Beta)     |
+--------------------+        +---------------------+
                                         |
                                         v
+--------------------+        +---------------------+
| RHS Execution      | <----- |  Conflict Set       |
| (Match-Resolve-Act)|        |  (LEX / MEA Heap)   |
+--------------------+        +---------------------+

1. The Rete Discrimination Network

Evaluating naive rule sets against thousands of dynamic facts is an $O(W^C)$ combinatorial nightmare. The Rete algorithm avoids redundant work by trading space for time:

Alpha Network (1-Input Filtering): Intra-element tests evaluate condition element attributes (e.g., ^type goal, ^status active). Tokens that satisfy alpha tests are indexed in Alpha Memories.
Beta Network (2-Input Joins): Inter-element tests join tokens from an incoming alpha memory with partial match tokens from a left beta parent. Matches form composite tokens stored in Beta Memories.
Structural Node Sharing: Identical tests and join sequences across distinct rules share identical network nodes, drastically reducing memory footprint and duplicate computation.
Negative Condition Elements (-): Conditions asserting that a pattern must not exist in working memory are handled via negative join nodes that track inhibiting match counters.

2. Conflict Resolution: LEX and MEA

When multiple rule instantiations are satisfied simultaneously, which rule fires first? OPS5 specifies two sophisticated conflict resolution strategies:

LEX (Lexicographic): Prioritizes recency by sorting instantiations based on the timetags of the matched WMEs, falling back to rule specificity (number of tests) and arbitrary tie-breaking.
MEA (Means-Ends Analysis): Tailored for goal-driven problem solving. It gives absolute precedence to the recency of the WME matching the first condition element ($C_1$), allowing the system to maintain focus on the active sub-goal before evaluating general recency.

A crucial invariant in this implementation is refraction: a rule will never fire more than once on the exact same tuple of WME timetags, preventing infinite execution loops while allowing rules to fire again if the underlying facts mutate.

The Seven Next-Generation Optimizations

As the engine took shape, standard textbook Rete implementations quickly revealed bottlenecks under heavy churn. To make the Go implementation blazing fast, I designed and implemented seven distinct optimizations:

Optimization	Technique	Impact
OPT-1	Token Prefix Spine Sharing	Replaced map cloning with an immutable linked ancestor spine; zero-allocation variable lookups and slice materialization.
OPT-2	Binary Heap Agenda	Indexed max-heap priority queue yielding $O(1)$ dominant activation peek and $O(\log K)$ activation management.
OPT-3	Alpha Switch Nodes	$O(1)$ constant-value hash switch dispatch with discrimination tree sharing across rules.
OPT-4	Static Heuristic Join Ordering	Compile-time LHS reordering using variable-binding graphs to eliminate Cartesian cross-products, while anchoring $C_1$ for MEA.
OPT-5	Memoryless Terminal Joins (Rete-NT)	Direct feeding to terminal nodes for final condition joins, bypassing intermediate beta memory allocations.
OPT-6	Precompiled RHS Action Closures	Actions precompile into typed Go closures, eliminating AST dispatch overhead during the execution cycle.
OPT-7	ParaOPS5 Partitioned Concurrency	Partitioned multi-core execution with subnetwork isolation, asynchronous message channels, and global quiescence detection.

Tooling & Experience

Beyond the algorithmic core, building this project was an exercise in developer ergonomics:

Interactive REPL: A full-featured terminal REPL (ops5) complete with readline support, command history, syntax auto-completion, cycle tracing, and working memory inspectors ((wm), (cs), (matches)).
Declarative Test Harness: An automated JSON test runner verifying classic AI benchmarks—including the famous Monkey and Bananas Problem, recursive ancestor resolution, and high-throughput vector modifications.
Benchmarking Suite: Continuous verification ensuring zero heap allocations on hot paths and race-detector clean concurrency (go test -race ./...).

Live Interactive Demo: Conway’s Game of Life in WebAssembly

To test the engine’s real-time capabilities in client-side interactive environments, I compiled the Go OPS5 runtime to WebAssembly and implemented John Conway’s Game of Life as a pure declarative rule system—with zero imperative grid loops:

👉 Launch Conway’s Game of Life (OPS5 WASM)

The application executes declarative production rules directly in your browser, managing neighbor votes, candidate tallying, cell births, and survivals within the Rete discrimination network. You can also inspect and live hot-reload active OPS5 rules directly from the in-browser inspector.

Source code: github.com/graemenewlands/go-ops5-apps

What’s Next?

This project has been an immensely rewarding dive into rule compilers, memory layouts, and algorithmic optimization in Go.

I’m currently working on:

Extending the S-expression parser with additional value functions.
Visualizing Rete network topologies via Graphviz export.
Expanding benchmarks against enterprise rule engines.

Check out the repository, run the REPL, and feel free to open issues or contribute: ⭐ GitHub: https://github.com/graemenewlands/ops5