Common Lisp Reasoner

Version 3.5

William Hounslow

Overview
Assumption-Based Truth-Maintenance System (ATMS)
Reasoning Extensions to the Object System
Object Creation
Ranges
Reading and Writing Slots
Cardinality
Composite Objects
Compound Objects
Assemblies
Class-Changing
Rule Language
Note on Lisp Propositions
Note on Use of Relational Propositions in Rules
Example Well-Formed Formulae
Automatically-Generated Rules
Rule Objects
Reasoning With Assumed Data
Appendix: XML Serialization and Deserialization
Appendix: RDF and OWL Compatibility

Overview

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.

Assumption-Based Truth-Maintenance System (ATMS)

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 pur­poses 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.

Manufactures an assumption.

Discards an assumption, and all internal ATMS data structures that mention it.

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.

Determines if the assumptions of e1 are a subset of those of e2.

Determines if a node holds in an environment (i.e., an environment in the label of n subsumes environment).

Determines if a node holds in the environment of no assumptions.

The distinguished environment of no assumptions.

Determines if an environment is contradictory.

The distinguished false node.

The ATMS used by the reasoning sub-system.

Reinitializes the above variables: recreates all data structures from scratch.

Reasoning Extensions to the Object System

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 alter­native metaclass is specified using the :metaclass option of defclass.)

The class extended-object is the instance of extended-class that is the super­class 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.

Object Creation

Creates and returns a new instance of a class; is described fully in the CLOS speci­fication. When applied to a subclass of the class extended-object, the following initialization arguments are valid:

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 be­lief status(es) of those antecedents.

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.

Implements initialization behaviour whereby values for slots are derived from typing information, where appropriate. See the CLOS specification.

Returns the instance named by a symbol. Works analogously to find-class, as de­scribed in the CLOS specification.

Returns the name of an instance.

If a single assumption has been used to justify instance, returns that assumption.

Ranges

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.

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 par­ticular, values may hold in differing belief states.

For types that are ranges, new values are combined by intersection with each ex­isting 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:

Returns the upper bound of a numeric range.

Returns the lower bound of a numeric range.

Reading and Writing Slots

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.

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 con­tradictions; 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).

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.

Records a contradiction; used by add-slot-value-using-class.

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.

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.

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*.

The distinguished value returned when slot values cannot be combined.

Predicate that tests for this value.

Returns the ATMS nodes in a slot that hold in an environment.

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 assump­tions, signals an error: one cannot remove an assumed datum except by explicitly removing the as­sumption, upon which all internal ATMS data structures that mention it are removed. See remove-node.

Removes node from its containing slot.

Removes node, and, optionally, all data justified solely by it (the default behaviour).

Indicates that assumption may be garbage-collected: the application will not use it further. Calls discard-assumption.

Returns the assumption corresponding to an assumed datum.

Returns the slot-value node corresponding to a datum.

Returns a list of the value(s) denoted by a slot-value node.

Cardinality

Where a slot holds (non-range) instances, it is possible to associate with it an ad­ditional slot that records the number of instances in that slot, being updated auto­matically 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 nu­meric-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.

Composite Objects

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.

Compound Objects

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.

Used to supply a part to a compound object at creation time.

Used to supply a list of parts to a compound object at creation time.

Assemblies

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

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:

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.

Finds class(es) most subordinate to class, under which instance falls (may fall). Returns a list of classes.

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.

Rule Language

The reasoning procedure takes as inputs values stored into slots and a corpus of im­plicitly 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 da­tum (slot value), along with a justification, which records the derivation of that da­tum.

A constraint is an arbitrary logical expression, from which all possible inferences are derived.

A rule has a distinguished head, the truth of which the rule acts to determine.

Note on Lisp Propositions

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.

Note on the Use of Relational Propositions in Rules

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.

Example Well-Formed Formulae


(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)

Automatically-Generated Rules

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 Objects

Compiles a well-formed formula; invoked automatically when a defconstraint or defrule form is evaluated.

Undoes the effects of a compilation: the wff no longer participates in reasoning.

Controls the printing of information about the point of failure during the evaluation of rules and constraints.

The stream to which trace information is printed; initially *trace-output*.

Returns the rules and constraints that notice data stored in the given slot.

Returns the rules that can affect the contents of the given slot. (A constraint, being non-directional, can affect all the slots it notices.)

Returns a list of attribute references denoting those slots noticed by a rule or con­straint.

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 fol­lowing accessor functions:

Returns the class-name component of an attribute reference.

Returns the slot-name component of an attribute reference.

Reasoning With Assumed Data

Problem solving with the ATMS requires the making of appropriate assumptions, followed by a search of the space of environments (i.e., combinations of assump­tions), 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.

Uses add-slot-value; no-check defaults to non-nil. If assumption is omitted or is nil, manufactures one with make-assumption. Returns assumption.

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.

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 order in which the assumption sets are created and the order in which they appear in control-disjunctions should be the same.

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.

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.

Called 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.

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.

The non-consing version of schedule. Environments are executed in size order and those of the same size in an arbitrary order.

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.

Describes the assumed data of environment, which may be an object or a list of assumptions.