This document describes a reasoning tool that extends (and is implemented in) the Common Lisp Object System (CLOS) and that is intended to be used in a variety of practical search and reasoning tasks, including scheduling, planning, diagnosis and predictive reasoning. It should be read in conjunction with the CLOS specification. Certain features are implemented by means of the CLOS Metaobject Protocol (see Kiczales, des Rivieres and Bobrow, The Art of the Metaobject Protocol, MIT Press, 1991).
All symbols referred to below are accessible in the
package REASONER (nickname RS)
and external, unless otherwise indicated.
See: de Kleer, ‘An Assumption-Based TMS’, Artificial Intelligence, 28 (1986).
Note:
Those that wish to access data structures internal to the ATMS (for the purposes
of, say, following a chain of justifications, or obtaining the set of
assumptions denoted by an environment) should inherit from the package
ATMS in their working package.
The class core-atms is the common superclass of atms and basic-atms. For details of the distinction between the latter two classes, see Reasoning With Assumed Data.
| make-assumption | Primary Method |
| (tms core-atms) | |
| &optional name |
Manufactures an assumption.
| discard-assumption | Primary Method |
| (tms core-atms) | |
| (n assumption) |
Discards an assumption, and all internal ATMS data structures that mention it.
| uniquify-environment | Primary Method |
| (tms core-atms) | |
| (assumptions list) | |
| &optional dont-create ordered |
Returns the environment object corresponding to a list of assumptions. Unless ordered is non-nil, the assumptions are first sorted. If there is no such object and the dont-create argument is not supplied or is nil, an object is created; otherwise nil is returned.
| subsumesp | Primary Method |
| (e1 environment) | |
| (e2 environment) |
Determines if the assumptions of e1 are a subset of those of e2.
| contradictoryp | Primary Method |
| (environment environment) |
Determines if an environment is contradictory.
| in-p | Primary Method |
| (n node) | |
| environment |
Determines if a node holds in an environment (i.e., an environment in the label of n subsumes environment).
| truep | Primary Method |
| (n node) |
Determines if a node holds in the environment of no assumptions.
| *empty-environment* | Variable |
The distinguished environment of no assumptions.
| *atms* | Variable |
The ATMS used by the reasoning sub-system.
| reinitialize-atms | Function |
Reinitializes the above variables: recreates all data structures from scratch.
The basic object system is extended to support the treatment of values in slots of instances as data to be reasoned with: reasoning is initiated when a value is stored. This behaviour is provided by a special metaclass, extended-class. (This alternative metaclass is specified using the :metaclass option of defclass.)
The
class extended-object is the instance of extended-class that is the superclass of all other instances of
extended-class except itself; it is a subclass
of standard-object. A class defined with metaclass
extended-class
has extended-object as its default superclass. In the package
REASONER-USER,
the metaclass itself defaults to extended-class.
| make-instance | Generic Function |
| class-name &rest initargs |
Creates and returns a new instance of a class; is described fully in the CLOS specification. When applied to a subclass of the class extended-object, the following initialization arguments are valid:
| :antecedents | Initialization Argument |
A list of ATMS nodes such as might be supplied to add-slot-value. The new instance is justified by the antecedents, so that any values added to its slots will inherit the belief status(es) of those antecedents.
| :name | Initialization Argument |
Gives a name to the instance. The function find-instance returns the instance named by a symbol. The function instance-name returns the name of an instance.
| shared-initialize | Primary Method |
| (instance extended-object) | |
| slot-names | |
| &rest initargs |
Implements initialization behaviour whereby values for slots are derived from typing information, where appropriate. See the CLOS specification.
| find-instance | Function |
| name &optional errorp |
Returns the instance named by a symbol. Works analogously to find-class, as described in the CLOS specification.
| instance-name | Function |
| instance |
Returns the name of an instance.
| instance-assumption | Function |
| instance |
If a single assumption has been used to justify instance, returns that assumption.
A restriction can be placed on the values that may be stored in a slot, by supplying typing information in the slot specifier (a part of a class definition) as described in the CLOS specification. This must be a valid type specifier; if it is a class name, slot values must be instances of that class. (It may also be a compound type specifier, such as or, mentioning multiple classes.)
We
extend this mechanism by allowing the type to denote a range of values: either
an enumerated range of values, or a numeric sub-range (for instance,
(cerise crimson cyan) for a colour
slot, or (0 137) for an age
slot). Ranges over symbols (symbolic-range),
numbers (numeric-range) and truth values
(true-or-false, true,
false) are provided; the macro defrange is used to define specialized
ranges, such as age-range.
Besides numbers, the distinguished symbols big and -big may appear in a numeric range.
| defrange | Macro |
| name-and-options [documentation-string] &rest elements |
Defines a new range abbreviation: elements, a sequence of symbols, or between one and two values representing the lower and upper bounds of a numeric range, is associated with name, which may be used as the :type slot option of a slot specifier in a defclass form. Options take the form they do in defstruct; the options that can be given are :include, which takes an argument which is the name of another range definition, and :external-type, which is intended to facilitate the translation of numeric values into external formats, such as dates and times. The latter option is inherited.
If elements comprises symbols, and there is a range definition naming a superset of those symbols, it is located in the type hierarchy below the superset range; numeric ranges are always defined as direct sub-types of numeric-range. The :include option may be used to defeat this behaviour.
Mechanisms for combining and determining the inconsistency of values are factored out into methods defined on these types.
Slot values are sub-ranges (not elements) of the declared range; single values are converted to range format when they are stored. Each slot is given an initial value derived from its type (by the default shared-initialize method). This represents an initial set of possibilities that subsequent reasoning activity acts to narrow. Type checking is thus achieved by the consistency checking amongst values that happens whenever a new value is stored.
Generally, the new value will coexist with one or more existing value(s). In particular, values may hold in differing belief states.
For types that are ranges, new values are combined by intersection with each existing value: if two values are disjoint, they are contradictory. When a slot is read, its values (sub-ranges) are combined to yield the value returned.
For
instance, we may have deduced that a person is of sixteen years of age or above
and that they are under 65 from the intelligence that they are married and not
of pensionable age. Their age slot would contain the values (0 137)
(the initial value), (16 137), and (0 64);
combination of these values yields (16 64).
The following functions may be used to interpret programmatically the result of value combination:
| range-max | Function |
| x |
Returns the upper bound of a numeric range.
| range-min | Function |
| x |
Returns the lower bound of a numeric range.
| add-slot-value | Function |
| object slot-name new-value antecedents informant | |
| &key &allow-other-keys |
Adds a value to a slot of an instance, justifying it by antecedents, a list of ATMS nodes (i.e., slot values or assumptions). If antecedents is nil the value is true (i.e., it holds universally). If the value is already present, the existing node is re-justified. The informant argument is a problem-solver- (or user-) supplied description of the justification.
This behaviour is implemented by add-slot-value-using-class, which is also responsible for the processing of keyword arguments.
Returns the node corresponding to new-value.
| add-slot-value-using-class | Generic Function |
| class object slot new-value antecedents informant | |
| &key slot-name no-check no-count negated |
Implements the behaviour of add-slot-value. class is the class of object. slot is a slot definition object; the slot-name keyword argument defaults to its name.
No checking is done for gross type violations;
however, the function slot-value-typep is
provided for use by client programs. new-value is combined with each
existing value in order to detect contradictions; if the values are ranges,
and one is not a sub-range of the other, their intersection is added to the
slot. (This behaviour can be inhibited by means of the no-check keyword
argument; see also validate-combination.)
The no-count keyword argument inhibits the automatic updating
of a slot’s count; see Cardinality.
The negated keyword
argument is used to make an explicit assertion that some (non-range) instance does
not appear in a slot (e.g., that joe is not the spouse
of amelia).
| slot-definition-missing | Generic Function |
| class object slot-name operation value antecedents informant | |
| &key &allow-other-keys |
Called by add-slot-value-using-class if the slot definition corresponding to slot-name is missing from class. The default method signals an error.
| add-contradiction | Function |
| atms antecedents |
Records a contradiction; used by add-slot-value-using-class.
| validate-combination | Generic Function |
| new-node node nodes |
Called by add-slot-value-using-class to determine whether new-node should be combined with node, an existing node, for the purposes of detecting contradictions and creating intersections. nodes is a list of all the existing nodes, most recent arrival first.
Depending upon the nature of the application, much of this work may be both time-consuming and unnecessary; an application-specific method may be supplied to indicate such cases by returning nil. The system-supplied method returns non-nil constantly.
| slot-value-typep | Function |
| object type |
Determines if object satisfies type, where object is an instance, symbol, number or range and type a class, e.g.,
(slot-value-typep 'true 'true-or-false) ⇒ t (slot-value-typep '(0 100) 'numeric-range) ⇒ t
Automatically-generated reader methods may be specified in a defclass form.
| slot-value-reduce | Function |
| object slot-name | |
| &optional environment |
Combines all the slot values (nodes) that hold in environment, an object returned by the generic function uniquify-environment. If environment is t, all values contained in the slot are combined; if omitted, it defaults to *empty-environment*.
| contradictory-value | Constant |
The distinguished value returned when slot values cannot be combined.
| contradictory-value-p | Function |
| value |
Predicate that tests for this value.
| slot-values | Function |
| object slot-name environment |
Returns the ATMS nodes in a slot that hold in an environment.
| remove-slot-value | Function |
| object slot-name value | |
| &key negated recursive |
Removes a value from a slot, and, optionally, all data justified solely by it (the default behaviour). If the corresponding node does not hold in the environment of no assumptions, signals an error: one cannot remove an assumed datum except by explicitly removing the assumption, upon which all internal ATMS data structures that mention it are removed. See remove-node.
| remove-node :before | Method |
| (n standard-slot-value) | |
| &optional recursive |
Removes node from its containing slot.
| remove-node | Primary Method |
| (n node) | |
| &optional recursive |
Removes node, and, optionally, all data justified solely by it (the default behaviour).
| remove-node :after | Method |
| (n assumption) | |
| &optional recursive |
Indicates that assumption may be garbage-collected: the application will not use it further. Calls discard-assumption.
| fetch-assumption | Primary Method |
| (object extended-object) | |
| slot-name value | |
| &optional negated |
Returns the assumption corresponding to an assumed datum.
| fetch-node | Primary Method |
| (object extended-object) | |
| slot-name value | |
| &optional negated |
Returns the slot-value node corresponding to a datum.
| elements | Primary Method |
| (node standard-slot-value) |
Returns a list of the value(s) denoted by a slot-value node.
Where a slot holds (non-range) instances, it is possible to associate with it an additional slot that records the number of instances in that slot, being updated automatically each time a new instance is added. The additional slot is specified in the normal way (there must be a :type slot option that names a sub-range of numeric-range); the association is made by giving the name of the additional slot as the value of the :count option of the slot specifier of the original slot.
There are predefined ranges zero-or-one, zero-or-more, exactly-one and one-or-more.
Instances of the class composite-object have a parts slot referring to one or more closely-related but subordinate objects. The classes of these objects must be subclasses of the class part. Parts may be added either at instance creation time or subsequently.
The class has two subclasses: compound-object and assembly.
The compound-object subclass captures
the distinction between necessary and contingent membership of a class. For instance,
a person may also be a catholic or a
police-officer; these are simpler ideas out of which our
idea of a person as a whole is formed. This distinction is a useful organizing principle.
Were the subordinate classes to be defined as subclasses of
person, some means of stipulating the admissible compound classes
(e.g., catholic-police-officer but not catholic-buddhist), either by enumerating them or some other mechanism,
would be required. Moreover, new parts could not be added dynamically.
A compound object’s parts’ slots may be read or stored into as if they were slots of the object itself. However, within rules the parts must be referred to explicitly.
| :part | Initialization Argument |
Used to supply a part to a compound object at creation time.
| :parts | Initialization Argument |
Used to supply a list of parts to a compound object at creation time.
An assembly is a group of objects that are created together.
When an assembly instance is created, slots whose contents have been defined as of type component, and for which no value is specified in the initialization argument list, are filled automatically. The number of component instances that are created is determined by the lower bound of of the slot’s count (see Cardinality). If it has no count, one instance is created.
Each component, created or supplied, is added to the parts slot of the assembly.
A component can, of course, also be an assembly. Specialized initialize-instance methods may be written to detect circularities or to create shared parts.
Class-changing, in which the structure of an instance is modified to reflect a new class, may be employed, with the proviso that the target class be below the existing class in the inheritance hierarchy.
However, a value stored in a slot of an instance might not trigger an
inference as expected after its class is changed. For example, if a value is stored in the
children slot of a parent instance, and then
that instance is changed to a grandparent, a rule that refers to the
children of a grandparent will not succeed.
To enable such inferences, use:
| notice-slot-values | Primary Method |
| (instance extended-object) | |
| &optional predicate |
Intended to be called after changing the class of instance. Ensures that values stored in its slots that satisfy predicate (by default, all those that hold in a non-empty environment) have been noticed by the reasoning procedure.
| classify | Primary Method |
| (instance extended-object) | |
| (class extended-class) | |
| environment |
Finds class(es) most subordinate to class, under which instance falls (may fall). Returns a list of classes.
| map-slots | Function |
| class function | |
| &key direct from-end |
Applies function to each element of an ordered list of slot definitions for class; used by classify. direct indicates that slot definitions local to class only be used. from-end determines whether the most or least subordinate of those slot definitions with the same name be used; a type specifier in a subordinate slot definition should always be a subtype of one in a superior definition.
The reasoning procedure takes as inputs values stored into slots and a corpus of implicitly universally quantified logical expressions (rules and constraints, known collectively as well-formed formulae) written by the user, and produces unit steps called consumers, each of which represents an individual inference. A separate scheduling procedure (see schedule) takes each consumer and constructs a new datum (slot value), along with a justification, which records the derivation of that datum.
| defconstraint | Macro |
| name [qualifier] declarations &rest constraint-body |
A constraint is an arbitrary logical expression, from which all possible inferences are derived.
| defrule | Macro |
| name [qualifier] declarations &rest rule-body |
A rule has a distinguished head, the truth of which the rule acts to determine.
| qualifier::= | :assume |
| declarations::= | ({(variable-name class-name)}+) |
| constraint-body::= | [documentation-string] expression |
| rule-body::= | if-body | iff-body |
| if-body::= | [documentation-string] [disjunction ->] compound-head |
| iff-body::= | [documentation-string] disjunction <-> head |
| compound-head::= | head [and compound-head] |
| head::= | [not] proposition |
| expression::= | condition [-> expression] |
| condition::= | disjunction [<-> condition] |
| disjunction::= | conjunction [or disjunction] |
| conjunction::= | primary [and conjunction] |
| primary::= | proposition | not primary | (expression) |
| proposition::= | lisp-proposition | |
| literal-proposition | | |
| relational-proposition | | |
| numeric-or-arithmetic-proposition |
| lisp-proposition::= | lisp (function-name {arg}+) |
| arg::= | (variable-name class-name) | |
| attribute-reference | | |
| number | string |
| attribute-reference::= | variable-name slot-name |
| literal-proposition::= | attribute-reference { |
is symbol | |
|
is in ({symbol}+) | |
|
is in range-class-name | |
|
is [in] attribute-reference} |
| relational-proposition::= | attribute-reference [is | includes] variable-name |
| numeric-or-arithmetic-proposition::= | attribute-reference { |
is in numeric-range | |
|
is in range-class-name | |
|
is number | |
|
| relation arithmetic-rhs} |
| numeric-range::= | (number number) |
| relation::= | = | > | < | >= | <= | /= |
| arithmetic-rhs::= | arithmetic-expr | |
{ aggregate-min | aggregate-max | aggregate-sum } |
|
(relational-attribute-reference numeric-attribute-reference) | |
|
{ min | max } ({attribute-reference | number }+) |
| arithmetic-expr::= | mult-term [plus-op arithmetic-expr] |
| mult-term::= | factor [mult-op mult-term] |
| factor::= | (arithmetic-expr) | number | attribute-reference | - factor |
| plus-op::= | + | - |
| mult-op::= | * | / |
The function is applied to the arguments specified; variables and attribute references are de-referenced, but other arguments are not evaluated. If the proposition is in the head of a rule, the function will be passed two additional arguments: the antecedents that triggered the rule, and an informant, to use if it installs a justification (see add-slot-value). Not intended for use in constraints.
If the last defrule
example below, with a relational proposition in its body and a <-> connective, were written straightforwardly, the negation
of the head of the rule would never be inferred. (This is because the logical expressions
into which the compiler translates the rule do not exactly reflect the intention of the rule
writer.) The formulation used enables all the intended inferences, and is safe
provided the negation of the relational proposition in the body of the rule is
not asserted.
(defconstraint pensionable ((p person)) "Pensionable age rule."
p age > 64 or p sex is female and p age > 59
<->
p of-pensionable-age is true)
(defconstraint income ((p person))
p income = p benefit + p earnings)
(defrule paternity ((child person) (mum person) (dad person))
child mother is mum
and mum spouse is dad
and child eye-colour is dad eye-colour
-> child father is dad)
(defrule combined-age-of-children ((p person) (c person))
p children includes c
-> p combined-age-of-children = aggregate-sum (p children c age))
(defrule qualifying-accounts ((cb credit-balance)
(sa share-account))
cb accounts-held-in includes sa -> ; See note above.
cb accounts-held-in includes sa and
sa account-name is in qualifying-share-account-names
<->
cb qualifying-accounts-held-in includes sa)
defclass slot specifiers take two additional
options, :composition and :inverse, which
define a slot in terms of one or more others and sanction the derivation of values when those
slots are stored into. The latter option takes a single value, a (non-range-valued) slot name.
The former may be one of :symmetric or :transitive, or alternatively a list of one or more slot names, such as
(parent brother) for determining the value of an uncle slot.
| rule-compile | Primary Method |
| (wff well-formed-formula) |
Compiles a well-formed formula; invoked automatically when a defconstraint or defrule form is evaluated.
| uncompile | Primary Method |
| (wff well-formed-formula) |
Undoes the effects of a compilation: the wff no longer participates in reasoning.
| *trace-rule-failure* | Variable |
Controls the printing of information about the point of failure during the evaluation of rules and constraints.
| *rule-trace-output* | Variable |
The stream to which trace information is printed; initially *trace-output*.
| rules-using | Function |
| class slot-name |
Returns the rules and constraints that notice data stored in the given slot.
| rules-affecting | Function |
| class slot-name |
Returns the rules that can affect the contents of the given slot. (A constraint, being non-directional, can affect all the slots it notices.)
| slots-used | Primary Method |
| (wff well-formed-formula) |
Returns a list of attribute references denoting those slots noticed by a rule or constraint.
| slot-affected | Primary Method |
| (wff forward-rule) |
Returns an attribute reference denoting the slot affected by a rule. (A constraint can affect a slot if it notices it.)
The result of slot-affected and slots-used can be examined by means of the following accessor functions:
| attribute-reference-class | Function |
| attribute-reference |
Returns the class-name component of an attribute reference.
| attribute-name | Function |
| attribute-reference |
Returns the slot-name component of an attribute reference.
Problem solving with the ATMS requires the making of appropriate assumptions, followed by a search of the space of environments (i.e., combinations of assumptions), smallest first, for a solution.
The former task is accomplished using assume-slot-value, or, if the datum to be assumed is an arbitrary logical expression (this will appear in an inferred datum’s justification just like the other data that trigger an inference), by using the :assume qualifier accepted by the defconstraint and defrule macros.
The latter task is performed by backtrack or solutions. Both can be used with atms or basic-atms, which can be supplied by dynamically rebinding *atms*. basic-atms exploits incremental, ordered adding of assumptions to record significantly less information about contradictory environments.
| assume-slot-value | Function |
| object slot-name value | |
| &optional assumption no-check |
Uses add-slot-value; no-check defaults to non-nil. If assumption is omitted or is nil, manufactures one with make-assumption. Returns assumption.
| assume-slot-values | Function |
| object initargs | |
| &optional catchall-assumption no-check |
Utility function for assuming multiple slot values. Uses assume-slot-value. If catchall-assumption is supplied, it is used exclusively; if a value has previously been assumed (see fetch-assumption), that assumption is used; otherwise assumptions are created. Returns a list of assumptions.
| describe-data | Function |
| environment |
Describes the assumed data of environment, which may be an object or a list of assumptions.
| backtrack | Primary Method |
| (e environment) | |
| (control-disjunctions list) | |
| (tms core-atms) |
A recursive backtracking scheme appropriate where a solution must select exactly one choice from each of a number of sets, and where the solution does not depend on the order in which choices are made. See: de Kleer and Williams, ‘Back to Backtracking: Controlling the ATMS’, AAAI-86.
For optimal performance, the assumption sets should be created in the order in which they will appear in control-disjunctions. If basic-atms is used, they must be created in this order.
Uses nschedule.
| atms:oneof-disjunction | Primary Method |
| (assumptions list) | |
| &optional no-check ordered |
Records every pair from assumptions as contradictory. May be used to stipulate mutually-exclusive choices in addition to the control disjunctions. If no-check is non-nil (the default), no checking for previously-recorded conflicts is performed; if ordered is non-nil, any pair of assumptions is guaranteed to be added to an existing environment in the order supplied, so that less information need be recorded.
| order-control-disjunction | Generic Function |
| object e assumptions |
Called by backtrack. An application-specific method may reorder and return assumptions (a control disjunction). The first element of the returned value is then added to e (the partial solution). object is the instance of which the assumed datum of the first assumption is a slot value.
| added-assumption | Generic Function |
| object a assumptions tms |
Called by backtrack if a, the selected assumption, is successfully added to assumptions (i.e., a consistent environment results). object is as above. An application-specific method can be supplied to detect contradictions explicitly. See add-contradiction.
| solutions | Primary Method |
| (e environment) | |
| (choices list) | |
| (tms core-atms) | |
| &optional dont-create |
An ATMS-guided generate-and-test search regime. Supersets of e are enumerated by incorporating assumptions from choices and those that are consistent and maximal (i.e., with respect to choices) returned. No environment objects will be created if dont-create is non-nil.
Uses schedule.
| schedule | Primary Method |
| (tms core-atms) | |
| (e environment) |
Runs all consumers in all subsets of an environment. For the environment {A, B, C}, consumers are executed in the order: {A}, {B}, {A, B}, {C}, {A, C}, {B, C}, {A, B, C}. Returns a list of consistent subsets. See the paper by de Kleer and Williams.
| nschedule | Primary Method |
| (tms core-atms) | |
| (e environment) |
The non-consing version of schedule. Environments are executed in size order and those of the same size in an arbitrary order.