4 Inference Control (Basic)

The PLT Scheme Inference Collection provides functions for basic inference control.

The underlying structure of the inference engine is a rule network whose nodes store information about the state of the inference. For forward chaining, (non-goal) match nodes store the results of unifying assertions (i.e., facts) against rule precondition patterns. Goal match nodes are used to initiate backward chaining. A chain of join nodes stores the results of joining successive precondition matches for a rule. The join chain terminates with a rule node. Matches that propagate to a rule node result in rule instances that are added to the agenda. The order or rule instances on the agenda and based on priority and, for rule instances of equal priority, the current conflict resolution strategy.

The inference loop itself is very simple. It continually removes the first rule instance from the agenda and executes it using the bindings reulting from the successive matches and joins in the join node chain. This continues until either the inference loop is explicitly exited by a call to stop-inference or the agenda is empty.

Most of the forward chaining inference work is done in response to facts being asserted or retracted. When a fact is asserted, it is matched against the patterns (in the match nodes). Matches (and non-matches) are propagated to the join nodes. Successful matches result in a set of bindings for the pattern variables. [Note that non-matches have to be propagated to allow existential processing by the join nodes.] Interior join nodes accept matches from exactly one match node and one prior join node. The matches are pair-wise joined and successful joins (i.e., those with compatible bindings) result in a match that is, in turn, propagated to the next join or rule node.

A variable is bound by the first pattern clause in which it appears in a rule. A variable is local to the pattern in which it is bound and global to any other patterns. Variable contraints may be checked at either the match node or its paired rule node. If a variable constraint clause involves only local variables (and constants), it is checked at the match node. Otherwise, the check must be delayed to the paired join node. Existential pattern processing always takes place at the paired join node.

Backward chaining inference uses the same rule network as forward chaining. Backward chaining is initiated either explicitly by a call to check, or implicitly by a forward chaining inference when it needs the value of a fact that can be inferred by backward chaining. Facts inferred by a backward chaining inference are propagated through the rule network and thereby affect the forward chaining inference. [While there are explicit forward and backward chaining rules, the inference engine itself is bidirectional and backward chaining and forward chaining as needed in the inference.]

4.1 Rule Set Activation

Rule set activation is the process by which a ruke network corresponding to the rules in a specified ruleset is created and associated with the current inference environment. A rule set must be activated before the rules in the rule set are available to the inference engine. Multiple rule sets may be active simultaneously.

4.2 Forward Chaining Control

The following procedures are defined here (instead of in Chapter 5, Assertions) because they implement most of the actual forward chaining inferencing.

4.3 Backward Chaining Control

Backward chaining is initiated by a call to check.

The check function is also called internally to initiate backward chaining when the inference engine needs to get the truth value of a fact that has not been asserted and there are backward chaining rule to (potentially) determine it.

4.4 Inference Control

By convention, a return value of false, #f, means that the inference failed or terminated because there were no more rule instances to execute. The following function provide explicit function to terminate the inference loop and to indicate success or failure.