Implementation

In this chapter you will find some details on the internals of the rete implementation. Please read the overview over rete 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.

You should also notice yet another, recently introduced type of node: The BetaBetaNode. This type of nodes has two parents, which are both a BetaMemory. They are used whenever two groups of individually evaluated conditions need to be compared. This is not the norm: The general approach of constructing the network is still to add the alpha conditions into the pattern one by one through join nodes. The only use case for these BetaBetaNodes are complex noValue- conditions. So far, it was only possible to check for the absence of a single fact by setting a join node to negative, so that it only passes the previous token if there is no match in the connected alpha memory. With the BetaBetaNode, and the rete::NoValue node in particular, you can now create complex noValue conditions in which you check for the absence of a greater pattern. To do so, you can just add the part of your conditions that you want to be "negated" as usual, and afterwards connect a NoValue node to the beginning and end of the "negated" part. The NoValue node searches for token in its left parent that are also part of tokens in its right parent (pointer comparison!), and only passes those entries of its left parent that have no such match on the right side. It adds an EmptyWME as usual, just like some builtins or negative join nodes do. Nesting noValue conditions is straight forward using this technique. Just keep in mind that "noValue" is not the same as "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.

Abstraction from WME types: Accessors

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 accessors. 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::AccessorBase

To allow the most flexibility, a combination of Accessor and Interpretation is used to implement some kind of type erasure to get rid of the type of accessor and focus on the type of data we can retrieve.

The base of all this is AccessorBase. It is the base class for all accessor implementations and holds the following information:

• Where in a token the WME is located that can be asked for data. This is not WME specific, but a value stored by the rule parser and incremented whenever a node that adds a WME to the partial match is added to the network.
• What type of data it can provide. This refers to a single property of the WME. If you have e.g. a Person WME with a name and an age field, you would have an accessor that explicitely returns the value of the age field. This accessor could support returning the value as either an int or an std::string, or whatever other datatype you might like. To do so, the accessor manages a list of its possible Interpretation<T>s.

For convenience, the AccessorBase supports to explicitly ask for a specific interpretation, or the preferred interpretation from a set of types specified as a template parameter. It can also return interpretations it has in common with another accessor instance, which is necessary for join nodes to compare values pointed to by accessors.

rete::InterpretationBase and rete::Interpretation<T>

To achieve a good decoupling of the WME-specific accessor type from the data types it can provide, a separate class called rete::Interpretation<T> is used. It is derived from rete::InterpretationBase and represents the capability of getting a value of type T from a WME::Ptr / Token::Ptr. It holds a pointer to a function that extracts that data from a WME, and a pointer to the AccessorBase it belongs to, to make use of its index value. Since it is only valid as long as its parent accessor is alive, it can be made persistent by calling makePersistent(), which returns a PersistentInterpretation<T> holding a clone of the original accessor.

rete::Accessor<T, I...>

So far, what you need to implement accessors for your own datatypes is to inherit from AccessorBase , implement functions to access the data and register them properly via Interpretation<T> instances at the base class.

The rete::Accessor<class T, class... Is> template serves to simplify this process. For every interface type I in class... Is, it injects a pure virtual method to extract said I from an std::shared_ptr<T>:

virtual void getValue(std::shared_ptr<T>, I&) const = 0;

These methods are automatically registered at the base class, so all you need to do is implement them. So, if we look back at our fictional Person-WME and an accessor to get its age, you could write:

class PersonAgeAccessor : public Accessor<Person, int, std::string> {
    void getValue(Person::Ptr p, int& value) const override
    {
    	value = p.age;
    }
    
    void getValue(Person::Ptr p, std::string& value) const override
    {
    	value = std::to_string(p.age);
    }
    
    PersonAgeAccessor* clone() const override
    {
    	auto p = new PersonAgeAccessor();
        p->index_ = index_;
    }
    
    bool equals(const AccessorBase& other) const override
    {
        auto o = dynamic_cast<const PersonAgeAccessor*>(&other);
        if (o)
            return true;
        else
            return false;
    }
};

Note that accessors must be cloneable to properly keep track of the index values during rule construction, and the equals method is used to check if two join nodes are equal by pairwise comparison of their used accessors. Also, by specifying int before std::string in the template argument list, the Interpretation<int> gets a higher priority than Interpretation<std::string>!

Supporting multiple interpretations in builtins and productions

There may be situations in which you need to work with a very specific datatype, but want to support multiple different types being provided. E.g., when a triple needs to be inferred, everything is stored in std::strings for the subject, predicate and object. However, a triple can not only represent strings, but also resources (which are basically strings, but interpreted semantically differently) and different number types. You could just expect the given accessors to have a Interpretation<TriplePart>, where TriplePart is simply a wrapper around std::string signaling that it can be inserted into subject/predicate/object of a triple verbatim. But this too restricting, since simple computations may only support e.g. Interpretation<float> and maybe Interpretation<std::string>, but don't know of triples!

So, support for multiple interpretations is needed, and conversions to the destination type must be specified. But how to decide which interpretation to use when the intersection of supported types by the accessor and the the available types for conversion contains more than one entry, and how to make all this convenient to use?

rete::AccessorConversion

This is where the AccessorConversion<class Destination, class... Sources> becomes useful: Similar to rete::Accessor<class T, class... Is>, this is only a utility template that again injects a list of pure virtual methods to be implemented for the conversions, and some glue-code-logic that deals with selecting the right interpretation to use when provided with an accessor.

Upon its creation, the AccessorConversion becomes owner of an AccessorBase* and determines the interpretation which should be used for the conversion:

• If the Destination type is directly supported by the accessor, it is used, regardless of the order of priorities in the accessors interpretations.
• Else, the type with the highest priority in the accessor which is also supported by the AccessorConversion is selected.

Internally, all this happens during construction of the AccessorConversion, and the selection of the conversion method is done by setting a function pointer.

Have a look at the ToTriplePartConversion declared in rete-rdf/InferTriple.hpp:

class ToTriplePartConversion
    : public AccessorConversion<TriplePart, std::string, float, double, int, long> {
public:
    // ...
    void convert(const std::string& src, TriplePart& dest) const override;
    // ... float, double, int
    void convert(const long& src, TriplePart& dest) const override;
};

You only need to implement the conversion methods and use the conversion object by initializing it with an accessor and handing it to your node in your node builder class. Within your computations you can then use the conversion object to directly get your destination type, in this case TriplePart, from a WME/token.

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 InterpretationBase has the method:

bool valuesEqual(const InterpretationBase& other, Token::Ptr token, WME::Ptr wme);

And the AccessorBase can be asked to

std::pair<InterpretationBase*, InterpretationBase*>
    getCommonInterpretation(const AccessorBase& other) const;