Rete

Documentation for Rete.

Rete currently implements memory for Julia types, forward chaining joins, and backward chaining filter and extrema operations.

Facts

The facts in our reasoning system can be arbitrary Julia objects. It's best to restrict facts to immutable objects though so that they can't be altered once they're stored in the network or conclusions have been made. There is no mechanism for retracting a conclusion if a fact object is modified.

The Network

The reasoning is performed by a network of nodes. Facts flow through the network from node to node.

Each node has a set of input nodes (those that send it facts), and a set of outputs (those nodes to which it sends facts). connect is used to construct the network by linking nodes together.

Some nodes filter the facts and only pass through those that satisfy some predicate or are instances of a certain type.

Some nodes store facts.

Join nodes have multiple distinct input streams. A function is applied to all possible combinations of facts coming in from these streams. The function can call emit to assert a new fact to the network.

That's the theory. In practice, its simpler if a given node performs more than one of these roles. One such example is IsaMemoryNode, which filters facts that match a type parameter and remember only those facts.

We assume that the network is fully constructed before any facts are asserted. Adding inputs to a JoinNode doesn't cause existing facts from those inputs to be processed.

Layers

The network might best be constructed in layers. A single root node forms the top layer. It serves as the recipient of new facts. It distributes those facts to the next layer, which consists of memory nodes. A third layer consists of join nodes, typically defined by rules. The join nodes might conclude new facts which they pass to the root node.

Flow of Facts through the Network

A node receives a fact via its receive method.

A node distributes a fact to its outputs using its emit method, which calls receive for each of the node's outputs.

Rules

The @rule macro makes it easier to create rules and add them to a Rete.

As a contrived exanple, lets create a network that creates pairs of letters when the second letter in the pair is the next letter of the alphabet from the first.

using Rete

@rule PairConsectutiveLettersRule(a::Char, b::Char, ::String) begin
    if codepoint(a) + 1 == codepoint(b)
        emit(a * b)
    end
end

@rule will define a singleton type named PairConsectutiveLettersRule to represent the rule. @rule defines an install method that will add the rule to a network. The instance of PairConsectutiveLettersRule implements the join function of the JoinNode.

# Create the knowledgebase:
root = ReteRootNode("root")
install(root, PairConsectutiveLettersRule())

# Assert the characters 'a' through 'e' into the knowledgebase:
for c in 'a':'e'
    receive(root, c)
end

askc(Collector{String}(), root)
4-element Vector{String}:
 "ab"
 "bc"
 "cd"
 "de"

Backward Chaining

Rete currently provides limited support for backward chaining by using the BackwardFilterNode and BackwardExtremumNode node types.

There is not yet any facility to make it easier to integrate these nodes into the network. You will need to use the node constructors and connect to add them by hand.

Querying and Aggregation

The function askc can be used to query the network. askc takes either a continuation function or an Aggregator as its first argument.

askc also takes either a node that supports it, e.g. memory nodes or backweard chaining nodes; or an AbstractReteRootNode representing your knowledge base, and a fact type. In this latter case, find_memory_for_type is used to find the appropriate memory node for the specified type.

The continuation function is callled on each fact that askc finds.

Normally, askc has no return value. If an aggregator is passed as the first argument then it will perform the specified aggregation over the course of the query and that call to askc will return the aggregation result.

The currenty supported aggregators are:

using Rete
kb = ReteRootNode("My Knowledge Base")
connect(kb, IsaMemoryNode{Int}())
receive.([kb], 1:5)
nothing
askc(Counter(), kb, Int)
5
askc(Collector{Int}(), kb)
5-element Vector{Int64}:
 1
 2
 3
 4
 5

Note from the latter example that askc can infer the fact type argument from the Collector.

Customization

All custom node types are expected to inherit from AbstractReteNode.

We provide some support for the definition of custom node types.

Connectivity

The discrimination network is built from nodes using connect.

Most node types have a single set of inputs and single set of outputs.

To simplify node customization, any subtype of AbstractReteNode that includes the field definition

    inputs::Set{AbstractReteNode}

will be given the HasSetOfInputsTrait trait, and as such can serve as an output for other nodes without additional method support.

Any subtype of AbstractReteNode that includes the field definition

    outputs::Set{AbstractReteNode}

will be given the HasSetOfOutputsTrait trait, and as such can serve as an input for other nodes without additional method support.

This is suitable for most nodes where all of the inputs receive the same treatment, but is not suitable for join nodes, which inherently have multiple sets of inputs of different types that are treated differently. Currently there is no customization support for join nodes.

Custom Root Nodes

All custom root nodes are expected to inherit from AbstractReteRootNode.

Custom root nodes should also be given the CanInstallRulesTrait trait:

Rete.CanInstallRulesTrait(::Type{<:MyKindOfRootNode}) = CanInstallRulesTrait()

Custom Memory Nodes

You might find it useful to define your own type of memory node. All such types should inherit from AbstractMemoryNode. See its documentation for general requirements on memory nodes.

Each custom memory node will need to implement receive to store a new fact in that node. It will also need a custom method for askc.

Custom memory nodes should have their own is_memory_for_type method.

Normally, memory nodes are created by ensure_memory_node when a type appears as the input or output of a rule and the network does not yet include a memory for that type. Some applications might include references to custom memory node types in a custom root node. It this case, it is helpful to define a method for find_memory_for_type

function Rete.find_memory_for_type(root::MyTypeOfRootNode,
                                   typ::Type{MyTypeThatNeedsACustomMemoryNode})
    # code to return the custom memory node for MyTypeThatNeedsACustomMemoryNode.
end

Index

Definitions

Rete.AbstractMemoryNode — Type

AbstractMemoryNode is the abstract supertype of all Rete memory nodes.

Each concrete subtype should implement is_memory_for_type to determine if it stores that type of fact.

A memory node should remember exactly one copy of each fact it receives and return each fact it has remembered exactly once for any given call to askc.

A memory node should only remember facts which match the type that the memory node is defined to store. Not any of its subtypes.

source
Rete.BackwardExtremumNode — Type

BackwardExtremumNode(comparison, extractor, label)

When askced, provides one value: the fact with the most extreme value (based on comparison) of extractor applied to each input fact at the time askc was called.

source
Rete.BackwardFilterNode — Type
 BackwardFilterNode(filter_function, label)

When askced, passes through from its inputs only those facts which satisfy predicate.

source
Rete.CanInstallRulesTrait — Type
CanInstallRulesTrait

Having this trait gives the root node of a knowledge base the install method to facilitate adding rules to the network.

You can add this trait to YourType with

CanInstallRulesTrait(::Type{<:YourType}) = CanInstallRulesTrait())
source
Rete.Collector — Type
Collector{T}()

returns an Aggregator that can be passed as the "continuation" function of askc so that askc will return a vector of the objects that it found.

source
Rete.Counter — Type
Counter()

returns an Aggregator that can be passed as the "continuation" function of askc so that askc will return the number of objects that it found.

source
Rete.HasSetOfInputsTrait — Type
HasSetOfInputsTrait(type)

A Rete node type with the HasSetOfInputsTrait stores its inputs as a set.

Any struct that is a subtype of AbstractReteNode with the field

    inputs::Set{AbstractReteNode}

will have this trait.

source
Rete.HasSetOfOutputsTrait — Type
HasSetOfOuputsTrait(type)

A Rete node type with the HasSetOfOutputsTrait stores its outputs as a set.

Any struct that is a subtype of AbstractReteNode with the field

    outputs::Set{AbstractReteNode}

will have this trait.

source
Rete.IsaMemoryNode — Type
IsaMemoryNode{T}()

IsaMemoryNode is a type of memory node that only stores facts of the specified type (or subtype, as tested by isa). Facts of other types are ignored.

source
Rete.JoinNode — Type

JoinNode implements a join operation between multiple streams of inputs. The first argiment of join_function is the JoinNode itself. The remaining arguments come from the input streams of the join node. join_function should call emit for each new fact it wants to assert.

source
Rete._add_input — Function
_add_input(from, to)

adds from as an input to to.

User code should never call _add_input directly, only through connect. Users might specialize _add_input if implementing a node that needs to specialize how it stores its inputs.

source
Rete._add_output — Function
_add_output(from, to)

adds to as an output of from.

User code should never call _add_output directly, only through connect. Users might specialize _add_output if implementing a node that needs to specialize how it stores its outputs.

source
Rete.add_forward_trigger — Method
add_forward_trigger(n::JoinNode, from::AbstractReteNode)

adds from as a forward trigger of the JoinNode.

When a JoinNode receives a fact from one of its forward trigger inputs, it joins that input with all combinations of facts from other inputs and performs its join_function. Otherwise the JoinNode is not triggered.

source
Rete.askc — Function
askc(continuation::Function, node)

Calls continuation on each fact available from node.

source
Rete.askc — Method
askc(continuation, root::AbstractReteRootNode, t::Type)

calls continuation on every fact of the specified type that are stored in the network rooted at root.

Does not consider subtypes because that could lead to continuation being called on the same fact more than once (from the memory node for the type itself and from the memory nodes of subtypes).

Assumes all memory nodes are direct outputs of root.

Also assumes that every output of root implements is_memory_for_type.

source
Rete.copy_facts — Method
copy_facts(from_kb::AbstractReteRootNode, to_kb::AbstractReteRootNode, fact_types)

Copues facts if the specified fact_type from from_kb to to_kb.

for multiple fact types, one can broadcast over a collection of fact types.

source
Rete.emit — Function
emit(node, fact)

Distribute's fact to each of node's outputs by calling receive on the output node and fact.

source
Rete.emits — Method
emits(rule::Type)

Returns a Tuple of the types which rule is declared to emit.

source
Rete.ensure_memory_node — Method
ensure_memory_node(root::AbstractReteRootNode, typ::Type)::IsaTypeNode

Find a memory node for the specified type, or make one and add it to the network.

The default is to make an IsaMemoryNode. Specialize this function for a Type to control what type of memory node should be used for that type.

source
Rete.fact_count — Method
fact_count(node)

For memory nodes, return the number of facts currently stored in the node's memory, otherwise return nothing.

source
Rete.find_memory_for_type — Method
find_memory_for_type(root, typ::Type)::Union(Nothing, AbstractMemoryNode}

If there's a memory node in the Rete represented by root that stores objects of the specified type then return it. Otherwise return nothing.

source
Rete.input_count — Method
input_count(node)

returns the number of inputs to the node.

Note that for join nodes, this is the number of parameters rather than the number of nodes that emit facts to the join.

source
Rete.inputs — Function
inputs(node)

Returns the inputs of node – those nodes which can send it facts – as an iterable collection.

source
Rete.install — Method
install(root, rule::Type)

Installs the rule or rule group into the Rete rooted at root.

source
Rete.is_forward_trigger — Method
is_forward_trigger(::JoinNode, from::AbstractReteNode)

returns true if from is a forward trigger input of the JoinNode.

source
Rete.kb_counts — Method
kb_counts(root::AbstractReteRootNode)

Returns a Dict{Type, Int} of the number of facts of each type.

source
Rete.kb_stats — Method
kb_stats(io, root)

Show the input count, output count, fact count and label for each node.

source
Rete.outputs — Function
outputs(node)

Returns the outputs of node – those nodes to which it can send facts – as an iterable collection.

source
Rete.receive — Function
receive(node, fact)

receive is how node is given a new fact.

An application calls receive on the root node to assert a new fact to the network.

source
Rete.walk_by_outputs — Method

walkbyoutputs(func, node::AbstractReteNode)

Walks the network rooted at `root', applying func to each node.

source
Rete.@rule — Macro
@rule Rulename(a::A_Type, b::B_Type, ...) begin ... end

Defines a rule named Rulename. A singleton type named Rulename will be defined to represent the rule. An install method is defined for that type which can be used to add the necessary nodes and connections to a Rete to implement the rule.

The default supertype of a rule struct is Rule. When it is desirable to group rules together, one can define an abstract type that is a type descendant of Rule and use that as a dotted prefix to RuleName. The RuleName in the @rule invocation is MyGroup.MyRule then the supertype of MyRule will be MyGroup, rather than Rule.

A rule can have arbitrarily many parameters. The parameter list can also include clauses with no variable name. Such clauses identify the types of facts that the rule might assert. Memory nodes for these types will be added to the Rete if not already present. They will be added by the automatically generated install method. See CUSTOM_INSTALL below. There is no enforcement that all types that are emitted by the rule are listed here, but various introspective tools, as well as proper rule installation depend on this.

The body of the @rule expression implements the behavior of the rule. It can perform any tests that are necessary to determine which, if any facts should be asserted. This code is included in a function that has the same name as the rule itself. This function is used as the join_function of the JoinNode that implements the rule. The function declares a keyword argument named emit whose default value calls emit. For testing and debugging purposes, the rule function can be invoked from the Julia REPL, perhaps passing emit=println to try the rule function independent of the rest of the network.

Within the body, @reject, @rejectif and @continueif can be used.

@reject will exit the rule body unconditionally and issue a debug log message.

The other two take a conditional expression.

@rejectif will exit the rule body and log a message if the condition succeeds.

@continueif will exit and log if the condition returns false.

The first expression of the rule can be a call-like expression of RULE_DECLARATIONS. Its "parameters" can be declarations of one of the forms

FORWARDTRIGGERS(argumentnames...)`

Only the inputs for the specified argument names will serve as forward triggers. For backward compatibility, if there is no RULE_DECLARATIONS expression then all inputs are forward triggers.

Note that if a RULE_DECLARATIONS clause is included then any forwarde triggers must be explicitly declared.

CUSTOM_INSTALL()`

No install method will be automatically generated. The developer must implement an install method for this rule.

source