Home

NOTE: This wiki has been copied from a gitlab instance. Many links are kind of broken, but you can find all the content through the list of pages.

---

Rule reasoner based on the RETE algorithm

This wiki documents my implementation of the RETE algorithm and a rule based reasoner built on top of it. It presents shortly what all this is intended to be used for, how it can be used, how it works under the hood and -- probably the most interesting part -- how it can be extended to support more datatypes and operations.

This wiki

1. The RETE algorithm
   1. Overview
   2. Implementation notes
   3. How to construct a network
2. The reasoner
   1. Overview
   2. How to use it
   3. How to extend it

Features

The goal of this project is to create a system that allows you to insert your data and infers new information based on a set of specified rules. The main data to process are semantic, in the form of rdf triples, but the system should be easily extensible to also process other datatypes with custom operations. Furthermore it should handle non-monotonic updates: It must be possible to retract and change information and automatically retract inferred knowledge that no longer holds.

Though it is probably far from perfect, this project has already reached the above goals:

• You can ASSERT, RETRACT and UPDATE working memory elements in the rete network
• You can specify rules as strings which the included rule parser takes to create the corresponding rete network for you
• The reasoner keeps track of where all the information came from, so that...
  • ... it can retract previously inferred information if the conditions that lead to its deduction do not hold anymore
  • ... it can detect and remove inference-circles, where a set of data infers each other with no grounded, externally asserted base
  • ... it can explain to you how it came to a given conclusion
• Everything is designed to be extensible, so you can add custom data types, preconditions, computations and effects, and register them at the rule parser to easily use them in your rules

Limitations

The system is not designed for speed; at least not yet. The main focus lies on creating a feature rich and easy to use system. Also, it is not multi-threaded. There are some ideas on how to include the reasoner in a bigger, multi-threaded system, but I do not intend to parallelize the rete network itself.

Code structure

The code itself is split into three parts:

• The rete-core contains the base classes needed for every rete network: alpha- and beta-nodes and -memories, production-nodes, the agenda, tokens and an abstract working memory element (WME). It is explained in more detail in [rete algorithm](rete/Rete algorithm in C++) and rete implementation notes.

• rete-rdf contains classes based on rete-core which can be used to process rdf data.

• The rete-reasoner is probably why you are here. It adds everything needed for a rule based forward reasoner: A parser that constructs a rete network from a string representation of rules; the reasoner itself that also keeps track of how things were inferred, and thus can tear down cycles and give an explanation of why a WME holds; and all those little utilities that make all this possible, and extensible.