Implementation

In this chapter you will find some details on the internals of the rete implementation. Please read the [overview over rete](./Rete algorithm in C++) to get a general overview on how the algorithm works.

[[TOC]]

Code

The code is structured to resemble the rete network structure. You will find the classes

• rete::Network
• rete::WME
• rete::Token
• rete::AlphaNode
• rete::AlphaMemory
• rete::BetaNode
• rete::BetaMemory
• rete::AlphaBetaAdapter
• rete::ProductionNode, rete::AgendaNode
• rete::Agenda

which are directly related to the structure of the rete network as described before. There are also a few yet unmentioned classes, especially:

• rete::Builtin
• rete::Accessor

The following sections will give some additional information on some of these classes.

General remarks

Of course this library makes some assumptions and is not perfectly easy to use yet still universally applicable.

The basic view of a rete network is very simple: The alpha network implements criteria on single data blobs, the beta network joins multiple criteria until all conditions are combined. Alpha memories are used as the interface between alpha and beta network, while beta memories are inserted only when the results of a join are used in another join, and in the end comes the production node. Alpha nodes have exactly one input, namely from another alpha node, while beta nodes have exactly two, one alpha memory and one beta memory, and always implement a join.

Well, this implementation differs a bit from this view. There are actually two types of beta nodes, namely joins (as described before) and builtins. The latter have exactly one input, namely from a beta memory, and implement computations or checks on the partial matches that are passing through. They may add new information (like the result of a mathematical operation on the so-far matched data), or implement "join" criteria different from equality constraints (like comparison operators). "Join" criteria in quotes, as the join happened in a join node before, and the builtin only decides if it wants to let the match pass or not.

Furthermore, we assume that every beta node has its output connected to a beta memory. But be aware: Due to the structure of the graph you still need to add every single node yourself when constructing networks manually, including the memory nodes. The reason lies in the pointer-structure of the graph.

Graph pointer structure

WMEs need to be processed top down. They start at the root node of the network and are propagated to the nodes children, which in turn propagate them further down if the implemented checks pass. Hence, all nodes need pointers to their child-nodes. But on the other hand every check, builtin, join or memory node is only needed if it has a path down to a production node that actually makes use of the found matches.

Therefore all nodes only have std::weak_ptr to their children, and a single std::shared_ptr to their parent. The network contains a list where you should add the production nodes. As soon as a production is removed and deconstructed, the nodes that do no longer have a child that keeps them alive are deconstructed, too, until the network only contains the nodes it needs to serve the remaining productions. This also means that you need to make sure to not let your node pointers run out of scope too soon while constructing a network.

rete::Network

While the rete network is constructed implicitely by connecting nodes, the Network-class contains a single node which should be used as the top-level entry point into the network. It also provides a method to create a description of the current state of the network in a dot-file format. Whenever you see an image of a rete nework in this wiki, it was created through the dot-export of the network class.

rete::WME

This is the base class for all WMEs you want to process through the network and defines an interface to be implemented by them.

rete::TupleWME

The TupleWME is a template class which can be used to easily implement simple WMEs that hold multiple values. It was implemented as a utility class to support custom builtins that need to store one or more computed values.

rete::AlphaNode

This is the base class for all AlphaNodes. If you want to use your own data types and implement checks on them, this is the interface to use.

rete::Builtin

The builtin classes are additional operations that are executed on some variables. Note: Not on WMEs, not on tokens, but variables. A variable points to some part of a WME inside a token, e.g. the object-part of a triple. With builtins you can implement computations or checks that are different than the aforementioned ones. You could e.g. check if the numeric values in two different WMEs are equal, or which one is bigger, or you could add/subtract/multiply/... them and access the result further down in the network.

Currently only a few builtins are actually implemented, namely some math operations and comparisons.

rete::Accessor and derived classes

When a builtin (or any other node) wants to check some property of a WME, it does not really need to know the type of WME, only the type of the property to check. To grant access to the internals of WMEs without exactly knowing its type I use the concept of acccessors. The accessors in rete-core are simply interfaces to be implemented for the different WME types.

The idea is the following: On construction of the network you know exactly which types of WMEs the tokens that arrive at the different nodes contain. Thus you can provide an accessor specifically for this type of WME, which grants access to a value of a type that the node needs for its check. E.g., a TripleAccessor can currently interpret subject, predicate or object of a Triple as a string or a numeric value. A node might want to check if a value is greater than a given constant, so you hand it the TripleAccessor you configured accordingly -- the node has no idea of triples, just of numeric values.

In general you probably don't want to mess with these things directly, but rather use the rule parser to generate them for you. That is actually the reason they were implemented in the first case: To make the parser and reasoner extensible.

rete::StringAccessor, NumberAccessor, TupleWMEAccessor, ...

Currently, there are two interfaces of accessors:

The rete::StringAccessor interfaces generally provides access to strings, while rete::NumberAccessor lets to access numbers. Note that the latter also implements the string accessor interface, so that numbers can also be interpreted as strings.

You can use accessor->canAs<rete::NumberAccessor>() to check the type, and

auto numAcc = accessor->as<rete::NumberAccessor>();
if (numAcc->canGetFloat())
{
    float value = numAcc->getFloat();
}

To extract a value. The canGetFloat() check is optional: It determines if the underlying datatype can be (more or less) safely cast to a float. canGetFloat() returns false if the underlying datatype is a double, just as canGetInt() does if it would try to convert from long, float or double, etc., you get the idea.

One implementation of this interface is the rete::TupleWMEAccessor, which simply returns the n-th value from a rete::TupleWME. Please be aware that the accessor itself does not check of the given WME is of correct type.

rete::GenericJoin

When I started this project, everything was focused an triples only to get a first version running, and there were special TripleJoin-nodes etc. But by now, since the introduction of aforementioned accessors, one generic join class suffices for all join operations. It accepts pairs of accessor objects, which are then applied to the respective token and WME to extract and compare values. This is also the reason why the accessors need to implement the methods

bool canCompareValues(const Accessor& other); # and
bool valuesEqual(Accessor& other, Token::Ptr token, WME::Ptr wme);