4 Firing rules
The bindings such that the antecedents are true are found by evaluating the antecedents clause. Clauses with primitive keywords are evaluated by executing code in the implementation language of SDML (currently Smalltalk); other clauses are evaluated by retrieving them from databases. How to evaluate a clause (whether to use a primitive or retrieve from a private or public database) is determined by a clause definition group. Evaluating any clause determines the conditions under which it is true, i.e. the bindings for variables such that the clause is true. The clause may succeed many times, with different combinations of bindings, until all solutions are found.
Rules often have several antecedents which must all be true, with consistent bindings for their variables, for the rule to fire. They are represented as subclauses of a clause with primitive keyword and. If the first subclause succeeds, the second subclause is evaluated with those bindings applied, the resulting bindings are applied to the third subclause, and so on. When the entire antecedents clause succeeds, the rule is fired. After a rule fires or a subclause fails, SDML backtracks to search for other bindings for clauses that have already succeeded.
Whenever the antecedents succeed, the bindings are applied to the consequents, which are then performed in order to fire this instance of the rule. Performing a clause notes that it is true, which usually entails asserting it to a database. If there are several consequents, they are also represented as subclauses of a clause with keyword and; this clause is performed by performing its subclauses. The keyword and is one of a small number of primitives that are permitted in consequents; others are used to assert clauses to specific databases (or rules to rulebases). For example, a clause with keyword permanent specifies that its subclause is permanently true from the current time to the end of the simulation, so this clause is performed by performing the subclause on a permanent database.
It would be possible to move on to a different rule as soon as a rule has fired for the first time. However, it is usually faster to backtrack to find further instances than to search again from scratch. It should be noted that this approach is not so suitable for imperative rules because firing one instance could cause the antecedents of another instance of the same rule to become false. Further checks would be required, and the overall results of the rulebase could be affected.
Imperative rule-based systems often allow the user to specify a conflict resolution strategy. This strategy is used when there is a choice of rules for which the antecedents are true, in order to decide which one to fire. Such a strategy can introduce large overheads. Firstly, many instances of rules may be found with true antecedents, but then discarded if they are not chosen. Secondly, comparing the instances in order to decide which to fire may take a considerable amount of time. To avoid these overheads, some imperative systems use the order in which rules appear in a rulebase and the order in which clauses are asserted to a database to resolve such conflicts. Needless to say, the latter approach is very ad hoc.
Such a trade-off between flexibility and speed is not an issue when rules are strictly declarative. The order in which instances fire can be solely determined by efficiency considerations. This gives SDML a lot of scope for optimisation, as explained in the next section.
There is, however, one aspect in which SDML modellers do have control over ordering when firing rules. Antecedents are evaluated in the order in which they appear in a rule, since the most efficient ordering would be hard to determine automatically (although some work has been done in this area, see [11]). Due to the declarative semantics of SDML, changing the order of antecedents cannot yield different results. Some primitives cannot be evaluated when certain arguments are uninstantiated because they have an infinite number of solutions (e.g. sum ?a ?b 4). Such antecedents have to be delayed until enough variables have been instantiated for them to be evaluated.*1
Generated with CERN WebMaker