{Begin SubSec Introduction to Rule-Oriented Programming in LOOPS}
{Title Introduction to Rule-Oriented Programming in LOOPS}
{Text 


The core of decision-making expertise in many kinds of problem solving can be expressed succinctly in terms of rules.  The following sections describe facilities in Loops for representing rules, and for organizing knowledge-based systems with rule-oriented programming.  The Loops rule language provides an experimental framework for developing knowledge-based systems.  The rule language and programming environment are integrated with the object-oriented, data-oriented, and procedure-oriented parts of Loops.

Rules in Loops are organized into production systems (called RuleSets) with specified control structures for selecting and executing the rules.  The work space for RuleSets is an arbitrary Loops object.

Decision knowledge can be factored from control knowledge to enhance the perspicuity of rules.  The rule language separates decision knowledge from meta-knowledge such as control information, rule descriptions, debugging instructions, and audit trail descriptions.  An audit trail records inferential support in terms of the rules and data that were used.  Such trails are important for knowledge-based systems that must be able to account for their results.  They are also essential for guiding belief revision in programs that need to reason with incomplete information.



{Begin SubSec Introduction}
{Title Introduction}
{Text 

Production rules have been used in expert systems to represent decision-making knowledge for many kinds of problem-solving.  Such rules (also called {it if-then} rules) specify actions to be taken when certain conditions are satisfied.  Several rule languages (e.g., {lisp OPS5} [Forgy81], {lisp ROSIE} [Fain81], {lisp AGE} [Aiello81]) have been developed in the past few years and used for building expert systems.  The following sections describe the concepts and facilities for rule-oriented programming in Loops.

Loops has the following major features for rule-oriented programming:

{Begin NumberedList Loops features for rule-oriented programming}

{Text
Rules in Loops are organized into ordered sets of rules (called RuleSets) with specified control structures for selecting and executing the rules.  Like subroutines, RuleSets are building blocks for organizing programs hierarchically.  
}

{Text
The work space for rules in Loops is an arbitrary Loops object.  The names of the instance variables provide a name space for variables in the rules.
}

{Text
Rule-oriented programming is integrated with object-oriented, data-oriented, and procedure-oriented programming in Loops.  
}

{Text
RuleSets can be invoked in several ways:  In the object-oriented paradigm, they can be invoked as methods by sending messages to objects.  In the data-oriented paradigm, they can be invoked as a side-effect of fetching or storing data in active values.  They can also be invoked directly from LISP programs.  This integration makes it convenient to use the other paradigms to organize the interactions between RuleSets.
}

{Text
RuleSets can also be invoked from rules either as predicates on the LHS of rules, or as actions on the RHS of rules.  This provides a way for RuleSets to control the execution of other RuleSets.    
}

{Text
Rules can automatically leave an audit trail.  An audit trail is a record of inferential support in terms of rules and data that were used.  Such trails are important for programs that must be able to account for their results.  They can also be used to guide belief revision in programs that must reason with incomplete information.     
}

{Text
Decision knowledge can be separated from control knowledge to enhance the perspicuity of rules.  The rule language separates decision knowledge from meta-knowledge such as control information, rule descriptions, debugging instructions, and audit trail descriptions.
}

{Text
The invocation of RuleSets can also be organized in terms of tasks, that can be executed, suspended, and restarted.  Using task primitives it is convenient to specify many varieties of agenda-based control mechanisms.
}

{Text
The rule language provides a concise syntax for the most common operations.
}

{Text
There is a fast and efficient compiler for translating RuleSets into Interlisp functions.
}

{Text
Loops provides facilities for debugging rule-oriented programs.
}

{Text
The rule language is being extended to support concurrent processing.
}

{End NumberedList Loops features for rule-oriented programming}


The following sections are organized as follows:  This section outlines the basic concepts of rule-oriented programming in Loops.  It contains many examples that illustrate techniques of rule-oriented programming.  The next section describes the rule syntax.  The next section discusses the facilities for creating, editing, and debugging RuleSets in Loops.  

}{End SubSec Introduction}



{Begin SubSec Basic Concepts}
{Title Basic Concepts}
{Text 

Rules express the conditional execution of actions.  They are important in programming because they can capture the core of decision-making for many kinds of problem-solving.  Rule-oriented programming in Loops is intended for applications to expert and knowledge-based systems.

The following sections outline some of the main concepts of rule-oriented programming.  Loops provides a special language for rules because of their central role, and because special facilities can be associated with rules that are impractical for procedural programming languages.  For example, Loops can save specialized audit trails of rule execution.  Audit trails are important in knowledge systems that need to explain their conclusions in terms of the knowledge used in solving a problem.  This capability is essential in the development of large knowledge-intensive systems, where a long and sustained effort is required to create and validate knowledge bases.  Audit trails are also important for programs that do non-monotonic reasoning.  Such programs must work with incomplete information, and must be able to revise their conclusions in response to new information.  

}{End SubSec Basic Concepts}



{Begin SubSec Organizing a Rule-Oriented Program}
{Title Organizing a Rule-Oriented Program}
{Text 

In any programming paradigm, it is important to have an organizational scheme for composing large systems from smaller ones.  Stated differently, it is important to have a method for partitioning large programs into nearly-independent and manageably-sized pieces.  In the procedure-oriented paradigm, programs are decomposed into procedures.  In the object-oriented paradigm, programs are decomposed into objects.  In the rule-oriented paradigm, programs are decomposed into {it RuleSets}.{index RuleSets}  A Loops program that uses more than one programming paradigm is factored across several of these dimensions.


{Begin Figure}
{Tag CheckWashingMachine}
{Text
{lispcode
RuleSet Name: CheckWashingMachine;
WorkSpace Class: WashingMachine;
Control Structure: while1 ;
While Condition: ruleApplied;

(* What a consumer should do when a washing machine fails.)

      IF .Operational THEN (STOP T 'Success 'Working);

      IF load>1.0 THEN .ReduceLoad;

      IF ~pluggedInTo THEN .PlugIn;

{1}    IF pluggedInTo:voltage=0 THEN breaker.Reset;

{1}    IF pluggedInTo:voltage<110 THEN $PGE.Call;

{1}    THEN dealer.RequestService;

{1}    THEN manufacturer.Complain; 

{1}    THEN $ConsumerBoard.Complain;

{1}    THEN (STOP T 'Failed 'Unfixable);}
}
{Caption
RuleSet of consumer instructions for testing a washing machine.  The work space for the RuleSet is a Loops object of the class {lisp WashingMachine}.  The control structure {lisp While1} loops through the rules trying an escalating sequence of actions, starting again at the beginning if some rule is applied.  Some rules, called one-shot rules, are executed at most once.  These rules are indicated by the preceding one in braces.    
}
{End Figure}


There are three approaches to organizing the invocation of RuleSets in Loops:

{it Procedure-oriented Approach.}  This approach is analogous to the use of subroutines in procedure-oriented programming.  Programs are decomposed into RuleSets that call each other and return values when they are finished.  {it SubRuleSets}{index SubRuleSets} can be invoked from multiple places.  They are used to simplify the expression in rules of complex predicates, generators, and actions. 

{it Object-oriented Approach.}  In this approach, RuleSets are installed as methods for objects.  They are invoked as methods when messages are sent to the objects.  The method RuleSets are viewed analogously to other procedures that implement object message protocols.  The value computed by the RuleSet is returned as the value of the message sending operation.  

{it Data-oriented Approach.}  In this approach, RuleSets are installed as access functions in active values.  A RuleSet in an active value is invoked when a program gets or puts a value in the Loops object.  As with active values with Lisp functions for the {it getFn} or {it putFn}, these RuleSet active values can be triggered by any Loops program, whether rule-oriented or not.  

These approaches for organizing RuleSets can be combined to control the interactions between bodies of decision-making knowledge expressed in rules.

}{End SubSec Organizing a Rule-Oriented Program}



{Begin SubSec Control Structures for Selecting Rules}
{Title Control Structures for Selecting Rules}
{Text 

RuleSets in Loops consist of an ordered list of rules and a control structure.  Together with the contents of the rules and the data, a RuleSet control structure determines which rules are executed.  Execution is determined by the contents of rules in that the conditions of a rule must be satisfied for it to be executed.  Execution is also controlled by data in that different values in the data allow different rules to be satisfied.  Criteria for iteration and rule selection are specified by a RuleSet control structure.  There are two primitive control structures for RuleSets in Loops which operate as follows:  

{Def {Type (RuleSet Control Structure)} {Name Do1}
{Text
The first rule in the RuleSet whose conditions are satisfied is executed.  The value of the RuleSet is the value of the rule.  If no rule is executed, the RuleSet returns {lisp NIL}.

The {lisp Do1} control structure is useful for specifying a set of mutually exclusive actions, since at most one rule in the RuleSet will be executed for a given invocation.  When a RuleSet contains rules for specific and general situations, the specific rules should be placed before the general rules.
}}

{Def {Type (RuleSet Control Structure)} {Name DoAll}
{Text
Starting at the beginning of the RuleSet, every rule is executed whose conditions are satisfied.  The value of the RuleSet is the value of the last rule executed.  If no rule is executed, the RuleSet returns {lisp NIL}.

The {lisp DoAll} control structure is useful when a variable number of additive actions are to be carried out, depending on which conditions are satisfied.  In a single invocation of the RuleSet, all of the applicable rules are invoked.
}}


{FigureRef SimulateWashingMachine} illustrates the use of a {lisp Do1} control structure to specify three mutually exclusive actions.


{Begin Figure}
{Tag SimulateWashingMachine}
{Text
{LispCode
RuleSet Name: SimulateWashingMachine;
WorkSpace Class: WashingMachine;
Control Structure: Do1 ;

(* Rules for controlling the wash cycle of a washing machine.)

   IF controlSetting='RegularFabric 
   THEN .Fill .Wash .Pause .SpinAndDrain
        .SprayAndRinse .SpinAndDrain
        .Fill .DeepRinse .Pause .DampDry;

   IF controlSetting='PermanentPress
   THEN .Fill .Wash .Pause .SpinAndPartialDrain
        .FillCold .SpinAndPartialDrain
        .FillCold .Pause .SpinAndDrain
        .FillCold .DeepRinse .Pause .DampDry;

   IF controlSetting='DelicateFabric 
   THEN .Fill .Soak1 .Agitate .Soak4 .Agitate
        .Soak1 .SpinAndDrain .SprayAndRinse
        .SpinAndDrain .Fill .DeepRinse .Pause .DampDry;}
}
{Caption
Rules to simulate the control of the wash cycle of a washing machine.  These rules illustrate the use of the {lisp Do1} control structure to select one of three mutually exclusive actions.  These rules were abstracted from [Maytag] for the Maytag A510 washing machine.    
}
{End Figure}


There are two control structures in Loops that specify iteration in the execution of a RuleSet.  These control structures use an explicit while-condition associated with the RuleSet.  They are direct extensions of the two primitive control structures above.  

{Def {Type (RuleSet Control Structure)} {Name While1}
{Text
This is a cyclic version of {lisp Do1}.  If the while-condition is satisfied, the first rule is executed whose conditions are satisfied.  This is repeated as long as the while condition is satisfied or until a {lisp Stop} statement or transfer call is executed (see {PageRef (RuleSet Statement) Stop}).  The value of the RuleSet is the value of the last rule that was executed, or {lisp NIL} if no rule was executed.
}}


{Def {Type (RuleSet Control Structure)} {Name WhileAll}
{Text
This is a cyclic version of {lisp DoAll}.  If the while-condition is satisfied, every rule is executed whose conditions are satisfied.  This is repeated as long as the while condition is satisfied or until a {lisp Stop} statement is executed.  The value of the RuleSet is the value of the last rule that was executed, or {lisp NIL} if no rule was executed. 
}}


The "while-condition" is specified in terms of the variables and constants accessible from the RuleSet.  The constant {lisp T} can be used to specify a RuleSet that iterates forever (or until a {lisp Stop} statement or transfer is executed).  The special variable {var ruleApplied}{index ruleApplied Var} is used to specify a RuleSet that continues as long as some rule was executed in the last iteration.  {FigureRef FillTub} illustrates a simple use of the {lisp WhileAll} control structure to specify a sensing/acting feedback loop for controlling the filling of a washing machine tub with water.


{Begin Figure}
{Tag FillTub}
{Text
{LispCode
RuleSet Name: FillTub;
WorkSpace Class: WashingMachine;
Control Structure: WhileAll ;
Temp Vars: waterLimit;
While Cond: T;

   (* Rules for controlling the filling of a washing machine
      tub with water.)

{1!} IF loadSetting='Small THEN waterLimit_10;
{1!} IF loadSetting='Medium THEN waterLimit_13.5;
{1!} IF loadSetting='Large THEN waterLimit_17;
{1!} IF loadSetting='ExtraLarge THEN waterLimit_20;

   (* Respond to a change of temperature setting at any time.)

     IF temperatureSetting='Hot
     THEN HotWaterValve.Open ColdWaterValve.Close;

     IF temperatureSetting='Warm
     THEN HotWaterValve.Open ColdWaterValve.Open;

     IF temperatureSetting='Cold
     THEN ColdWaterValve.Open HotWaterValve.Close;

   (* Stop when the water reaches its limit.)

     IF waterLevelSensor.Test >= waterLimit
     THEN HotWaterValve.Close ColdWaterValve.Close
          (Stop T 'Done 'Filled);}
}
{Caption
Rules to simulate filling the tub in a washing machine with water.  These rules illustrate the use of the {lisp WhileAll} control structure to specify an infinite sense-act loop that is terminated by a {lisp Stop} statement.  These rules were abstracted from [MayTag].
}
{End Figure}


}{End SubSec Control Structures for Selecting Rules}



{Begin SubSec One-Shot Rules}
{Title One-Shot Rules}
{Text


{Tag OneShotRules}


One of the design objectives of Loops is to clarify the rules by factoring out control information whenever possible.  This objective is met in part by the declaration of a control structure for RuleSets.


Another important case arises in cyclic control structures which some of the rules should be executed only once.  This was illustrated in the WashingMachine example in {FigureRef CheckWashingMachine} where we wanted to prevent the RuleSet from going into an infinite loop of resetting the breaker, when there was a short circuit in the Washing Machine.  Such rules are also useful for initializing data for RuleSets as in the example in {FigureRef FillTub}.

In the absence of special syntax, it would be possible to encode the information that a rule is to be executed only once as follows:

{LispCode
Control Structure: While1
Temporary Vars:  triedRule3;
...
IF ~triedRule3 {arg condition{sub 1}} {arg condition{sub 2}} THEN triedRule3_T {arg action{sub 1}};}

In this example, the variable {lisp triedRule3} is used to control the rule so that it will be executed at most once in an invocation of a RuleSet.  However, the prolific use of rules with such control clauses in large systems has led to the common complaint that control clauses in rule languages defeat the expressiveness and conciseness of the rules.  For the case above, Loops provides a shorthand notation as follows:

{lispcode
{1}	IF {arg condition{sub 1}} {arg condition{sub 2}} THEN {arg action{sub 1}};}

The brace notation means exactly the same thing in the example above, but it more concisely and clearly indicates that the rule executes only once.  These rules are called "one shot" or "execute-once" rules.

In some cases, it is desired not only that a rule be executed at most once, but that it be tested at most once.  This corresponds to the following:

{lispcode
Control Structure: While1
Temporary Vars:  triedRule3;
...
IF ~triedRule3 triedRule3_T {arg condition{sub 1}} {arg condition{sub 2}} THEN {arg action{sub 1}};}

In this case, the rule will not be tried more than once even if some of the conditions fail the first time that it is tested.  The Loops shorthand for these rules (pronounced "one shot bang") is

{lispcode
{1!}	IF {arg condition{sub 1}} {arg condition{sub 2}} THEN {arg action{sub 1}};}

These rules are called "try-once" rules.

The two kinds of one-shot rules are our first examples of the use of meta-descriptions preceding the rule body in braces.  See {PageRef Tag MetaDescriptions} for information on using meta-descriptions for describing the creation of audit trails.

}{End SubSec One-Shot Rules}



{Begin SubSec Task-Based Control for RuleSets}
{Title Task-Based Control for RuleSets}
{Text 

* * * Tasks are Not Fully Implemented Yet * * *

Flexible control of reasoning is generally recognized as critical to the success of recent problem-solving programs.  Examples of flexible control are:

{Begin NumberedList}

{Text
In planning and design tasks, it is important to generate multiple alternatives.  These alternatives may be carried to different degrees of completion, depending on success, resource limitations, and information gained during a problem-solving process.  In some cases, an alternative may be temporarily set aside, only to be revived later in light of new information.
}

{Text
In analysis tasks, it is important to pursue multiple hypotheses in parallel.  As evidence and conclusions accumulate, some hypotheses may be abandoned but revived later.
}

{Text
Search and discovery tasks can be organized as opportunistic best-first searches.  At each step only the most promising avenues are pursued.  As some avenues fail to work out and new information accumulates, the other avenues can be re-evaluated and sometimes raised in priority.
}

{End NumberedList}



These examples require the ability (1) to suspend parts of a computation with the possibility of restarting them later, and (2) to reason about the control of computational resources.    

Loops provides a set of language features to support these capabilities, based on the representation of the execution of a RuleSet as a {it Task}.{index Tasks}  A Task is a Loops object with much the same structure as an item in an agenda (see {FigureRef RepairTask5}).  It represents the RuleSet being invoked, the data on which it is operating, and the status of its execution.


{Begin Figure}
{Tag RepairTask5}
{Text
{LispCode
RepairTask5:

ruleNumber:   NIL doc (* Number of the next rule to be executed.
                         Used for doNext and cycleNext.)
rs:           #$RepairWashingMachine
                  doc (* RuleSet that was invoked.)
self:         #&(FixitJob "uid1")
                  doc (* work space given to the RuleSet.)
value:        #&(MotorBrushes "uid2")
                  doc (* value returned by the RuleSet)
status:       Suspended
                  doc (* Execution status.  Examples: Started,
                         Done, Aborted, Suspended.)
reason:       TooExpensive
                  doc (* Reason for the status.  Examples: Success,
                         NoSpace, Blocked)
caller:       #$(RuleSet "uid3")
                  doc (* Caller of the RuleSet.)
priority:     300}
}
{Caption
An example of a Task object.  This Task could have been created for an invocation of the RuleSet in {FigureRef RepairWashingMachine}.  The Task records the RuleSet, its data, and its execution status.  The instance variable {lisp ruleNumber} is used only for the control structures {lisp DoNext} and {lisp CycleNext} as described in the next section.  The instance variable priority was created in response to the Task Vars declaration in the RuleSet.    
}
{End Figure}



{FigureRef RepairWashingMachine} illustrates a RuleSet for a task that can be suspended.  This RuleSet represents part of the behavior of a washing machine repair man.  The repair task may be suspended after it has started on a particular {lisp FixitJob} object if the failure is not diagnosed or is too expensive.

{Begin Figure}
{Tag RepairWashingMachine}
{Text
{LispCode
RuleSet Name: RepairWashingMachine;
WorkSpace Class: FixitJob;
Compiler Options: S ;  (* S for Task Stepping.)
Control Structure: doAll ;
Task Vars: priority;

(* Rules for washing machine repair.)

{1}   priority_300;
...
{1}   IF ~(replacementPart_motor.FindBrokenPart) 
   THEN (STOP T 'Suspended 'NoDiagnosis);

   IF replacementPart.Availability='NotInTruck hoursLimit < 1
   THEN (STOP badPart 'Suspended 'UnavailablePart);

   IF replacementPart:cost > dollarLimit 
   THEN (STOP badPart 'Suspended 'TooExpensive);
...}
}
{Caption
A suspendable Task.  This RuleSet characterizes part of the behavior of a repair man of washing machines.  The Stop statements specify how the RuleSet may report failure after it has been started on a particular {lisp FixitJob}.  Information in task variables (like priority) are saved in the Task record.  In this example, the machine failure may not be diagnosed or may be too expensive to fix.
}
{End Figure}


{FigureRef RePlanRepairWork} illustrates a RuleSet for controlling suspendable tasks.  This RuleSet represents part of the behavior of the owner of a washing machine repair business.  This RuleSet may restart any suspended task by the repairman RuleSet after getting more information about the customer.


{Begin Figure}
{Tag RePlanRepairWork}
{Text
{LispCode
RuleSet Name: RePlanRepairWork;
WorkSpace Class: JobSchedule;
Control Structure: cycleAll ;
RuleVars: currentTask customer substitutePart;

(* Sample Rules -- part of the behavior of a manager of a
   Washing Machine repair business.)

...
   IF currentTask:status='Success 
   THEN (STOP T 'Done 'Success);

   IF currentTask:reason='UnavailablePart
      substitutePart_expert.AskForSubstitutePart
   THEN currentTask:self:replacementPart_substitutePart
        (Start currentTask);

   IF customer:category='VIP
      currentTask:reason='TooExpensive
   THEN currentTask:self:dollarLimit _ VIP:dollarLimit
        currentTask:priority _ 100
        (Start currentTask);
...}
}
{Caption
Control of Tasks.  This RuleSet characterizes part of the behavior of the manager of a washing machine repair business.  When a repair task fails, the manager RuleSet may change some resource limits and start the repair task going again (e.g., if the customer is a {lisp VIP}).
}
{End Figure}


Loops has facilities for creating Task objects, starting and waiting for tasks, stepping and suspending Tasks.  Task variables are used for saving state information.  Distinct Tasks can refer to distinct invocations of the same RuleSet in different states of execution.  The language features supporting Tasks are described later.

}{End SubSec Task-Based Control for RuleSets}



{Begin SubSec Control Structures for Generators}
{Title Control Structures for Generators}
{Text 

Since Tasks represent suspended processes with local state, it is natural to use them for describing generators.  For the concise specification of generators, two additional control structures have been provided in Loops.  To use these control structures, a Task is first created that associates a RuleSet and a work space.  The Task is then invoked repeatedly.  At each invocation at most one rule is activated and the Task records which rule was activated.  At the next invocation, the search for the next rule to apply starts with the rule following the rule that was last executed.


{Def {Type (RuleSet Control Structure)} {Name DoNext}
{Text
At each invocation of the Task, the next rule is executed whose conditions are satisfied.  The value of the RuleSet is the value of the executed rule, or {lisp NIL} if no rule was executed.  After the last rule of the RuleSet has been tried, the Task will always return {lisp NIL}.

This control structure is convenient for specifying a generator of a limited number of items.  At each invocation, the remaining rules are tried until the next item is generated.  The generator returns {lisp NIL} after all of the rules have been tried.
}}


{Def {Type (RuleSet Control Structure)} {Name WhileNext}
{Text
At each invocation of the Task, the generator first checks whether the while condition of the RuleSet is satisfied.  If yes, then the next rule is executed whose conditions are satisfied.  The rules can be visualized as forming a circle, so that after the last rule of the RuleSet has been tried, the generator goes back to the beginning.  During a single invocation, no rule is tried more than once and the while-condition is tested only once at the beginning of the Step.  The value of the RuleSet is the value of the last rule executed or {lisp NIL} if no rule was executed. 

This control structure is convenient for specifying a generator that repeats itself periodically, and which has an extra condition that is factored from all of the rules.
}}


If a RuleSet with one of these control structures is invoked directly (instead of through a Task), its behavior is equivalent to that of a {lisp Do1} control structure.

The variable {var ruleApplied},{index ruleApplied Var} which can be used in the while-condition of {lisp While1} and {lisp WhileAll} control structures, is not meaningful with the {lisp WhileNext} control structure since at most one rule is applied in a given invocation. 


}{End SubSec Control Structures for Generators}



{Begin SubSec Saving an Audit Trail of Rule Invocation}
{Title Saving an Audit Trail of Rule Invocation}
{Text 

A basic property of knowledge-based systems is that they use knowledge to infer new facts from older ones.  (Here we use the word "facts" as a neutral term, meaning any information derived or given, that is used by a reasoning system.)  Over the past few years, it has become evident that reasoning systems need to keep track not only of their conclusions, but also of their reasoning steps.  Consequently, the design of such systems has become an active research area in AI.  The audit trail facilities of Loops support experimentation with systems that can not only use rules to make inferences, but also keep records of the inferential process itself.


{Begin SubSec Motivations and Applications}
{Title Motivations and Applications}
{Text

{it Debugging.}  In most expert systems, knowledge bases are developed over time and are the major investment.  This places a premium on the use of tools and methods for identifying and correcting bugs in knowledge bases.  By connecting a system's conclusions with the knowledge that it uses to derive them, audit trails can provide a substantial debugging aid.  Audit trails provide a focused means of identifying potentially errorful knowledge in a problem solving context.    

{it Explanation Facilities.}  Expert systems are often intended for use by people other than their creators, or by a group of people {it pooling} their knowledge.  An important consideration in validating expert systems is that reasoning should be {it transparent}, that is, that a system should be able to give an account of its reasoning process.  Facilities for doing this are sometimes called {it explanation systems} and the creation of powerful explanation systems is an active research area in AI and cognitive science.  The audit trail mechanism provides an essential computational prerequisite for building such systems.   

{it Belief Revision.}  Another active research area is the development of systems that can "change their minds".  This characteristic is critical for systems that must reason from incomplete or errorful information.  Such systems get leverage from their ability to make assumptions, and then to recover from bad assumptions by efficiently reorganizing their beliefs as new information is obtained.  Research in this area ranges from work on non-monotonic logics, to a variety of approaches to belief revision.  The facilities in the rule language make it convenient to use a user-defined calculus of belief revision, at whatever level of abstraction is appropriate for an application. 

}{End SubSec Motivations and Applications}



{Begin SubSec Overview of Audit Trail Implementation}
{Title Overview of Audit Trail Implementation}
{Text 

When {it audit mode}{index audit mode} is specified for a RuleSet, the compilation of assignment statements on the right-hand sides of rules is altered so that audit records are created as a side-effect of the assignment of values to instance variables.  Audit records are Loops objects, whose class is specified in RuleSet declarations.  The audit records are connected with associated instance variables through the value of the {lisp reason}{index reason Prop} properties of the variables.  

Audit descriptions can be associated with a RuleSet as a whole, or with specific rules.  Rule-specific audit information is specified in a property-list format in the meta-description associated with a rule.  For example, this can include {it certainty factor} information, categories of inference, or categories of support.  Rule-specific information overrides RuleSet information. 

During rule execution in audit mode, the audit information is evaluated after the rule's LHS has been satisfied and before the rule's RHS is applied.  For each rule applied, a single audit record is created and then the audit information from the property list in the rule's meta-description is put into the corresponding instance variables of the audit record.  The audit record is then linked to each of the instance variables that have been set on the RHS of the rule by way of the {lisp reason}{index reason Prop} property of the instance variable.

Additional computations can be triggered by associating active values with either the audit record class or with the instance variables. For example, active values can be specified in the audit record classes in order to define a uniform set of side-effects for rules of the same category.  In the following example, such an active value is used to carry out a "certainty factor" calculation.


}{End SubSec Overview of Audit Trail Implementation}



{Begin SubSec An Example of Using Audit Trails}
{Title An Example of Using Audit Trails}
{Text 

The following example illustrates one way to use the audit trail facilities.  {FigureRef EvaluateWashingMachine} illustrates a RuleSet which is intended to capture the decisions for evaluating the potential purchase of a washing machine.  As with any purchasing situation, this one includes the difficulty of incomplete information about the product.  The meta-descriptions for the rules categorize them in terms of the {it basis of belief} (fact or estimate) and a {it certainty factor} that is supposed to measure the "implication power" of the rule.  (Realistic belief revision systems are usually more sophisticated than this example.)

{Begin Figure}
{Tag EvaluateWashingMachine}
{Text
{LispCode
RuleSet Name: EvaluateWashingMachine;
WorkSpace Class: EvaluationReport;
Control Structure: doAll ;
Audit Class: CFAuditRecord ;
Compiler Options: A;        

(* Rules for evaluating a potential washing machine for a purchase.)

   ...

   {(basis_'Fact cf_1)}
   IF buyer:familySize>2  machine:capacity<20
   THEN suitability_'Poor;

   {(basis_'Fact cf_.8)}
   reliability_(_ $ConsumerReports GetFacts machine);

   {(basis_'Estimate cf_.4)}
   IF ~reliability THEN reliability_.5;
   ...}
}
{Caption
RuleSet for evaluating a washing machine for purchase.  Like many kinds of problems, a purchase problem requires making decisions in the absence of complete information.  For example, in this RuleSet the reliability of the washing machine is estimated to be .5 in the absence of specific information from {lisp ConsumerReports}.  The meta-description in braces in front of each rule characterizes the rule in terms of a {lisp cf} (certainty factor) and a {lisp basis} (basis of belief).  Within the braces, the variable on the left of the assignment statement is always interpreted as meaning a variable in the audit record, and the variables on the right are always interpreted as variables accessible within the RuleSet.  This makes it straightforward to experiment with user-defined audit trails and experimental methods of belief revision.
}
{End Figure}

The result of running the RuleSet is an evaluation report for each candidate machine.  Since the RuleSet was run in audit mode, each entry in the evaluation report is tagged with a reason that points to an audit record.  {FigureRef EvaluationReport} illustrates the evaluation report for one machine and one of its audit records.

{Begin Figure}
{Tag EvaluationReport}
{Text
{LispCode
EvaluationReport "uid1"
expense:       510
suitability:    Poor  cc 1 reason ...
reliability:       .5 cc .6 reason "uid2"
...
                                                           

AuditRec "uid2"
rule:          "uid3"
basis:          Estimate;
cf:            #(.4 NIL PutCumulativeCertainty)
   ...}
}
{Caption
Example of an audit trail.  The object for the expense report was prepared by the RuleSet in {FigureRef EvaluateWashingMachine}.  In this example, each of the entries in the report has a {lisp reason} and a {lisp cc} (for cumulative certainty) property in addition to the value.  The value of the {lisp reason} properties are {it audit records}{index audit records} created as a side effect of running the RuleSet.  The auditing process records the meta-description information of each rule in its audit record.  This information can be used later for generating explanations or as a basis for belief revision.  The auditing process can have side effects.  For example, the active value in the {lisp cf} variable of the audit record performs a computation to maintain a calculated cumulative certainty in the {lisp reliability} variable of the evaluation report. 
}
{End Figure}


The result of running the RuleSet is an evaluation report for each candidate machine.  The meta-descriptions for {lisp basis} and {lisp cf} are saved directly in the audit record.  The {it certainty factor} calculation in this combines information from the audit description with other information already associated with the object.  To do this, the {lisp cf} description triggers an active value inherited by the audit record from its class.  This active value computes a {it cumulative certainty} in the evaluation report.  (Other variations on this idea would include certainty information descriptive of the premises of the rule.)

}{End SubSec An Example of Using Audit Trails}

}{End SubSec Saving an Audit Trail of Rule Invocation}



{Begin SubSec Comparison with other Rule Languages}
{Title Comparison with other Rule Languages}
{Text

This section considers the rationale behind the design of the Loops rule language, focusing on ways that it diverges from other rule languages.  In general, this divergence was driven by the following observation:  

{it
When a rule is heavy with control information, it obscures the domain knowledge that the rule is intended to convey.
}

Rules are harder to create, understand, and modify when they contain too much control information.  This observation led us to find ways to factor control information out of the rules. 


{Begin SubSec The Rationale for Factoring Meta-Level Syntax}
{Title The Rationale for Factoring Meta-Level Syntax}
{Text

One of the most striking features of the syntax of the Loops rule language is the factored syntax for meta-descriptions, which provides information about the rules themselves.  Traditional rule languages only factor rules into conditions on the left hand side (LHS) and actions on the right hand side (RHS), without general provisions for meta-descriptions.

Decision knowledge expressed in rules is most perspicuous when it is not mixed with other kinds knowledge, such as control knowledge.  For example, the following rule:

{lispcode
IF ~triedRule4 pluggedInTo:voltage=0
THEN triedRule4_T breaker.Reset;}

is more obscure than the corresponding one-shot rule from {FigureRef CheckWashingMachine}:

{lispcode
{1}   IF pluggedInTo:voltage=0 THEN breaker.Reset;}


which factors the control information (that the rule is to be applied at most once) from the domain knowledge (about voltages and breakers).  In the Loops rule language, a meta-description (MD) is specified in braces in front of the LHS of a rule.  For another example, the following rule from {FigureRef EvaluateWashingMachine}:

{lispcode
{(basis_'Fact cf_.8)}
IF buyer:familySize>2  machine:capacity<20
THEN suitability_'Poor;}

uses an MD to indicate that the rule has a particular {lisp cf} ("certainty factor") and {lisp basis} category for belief support.  The MD in this example factors the description of the inference category of the rule from the action knowledge in the rule.  

In a large knowledge-based system, a substantial amount of control information must be specified in order to preclude combinatorial explosions.  Since earlier rule languages fail to provide a means for factoring meta-information, they must either mix it with the domain knowledge or express it outside the rule language.  In the first option, perspecuity is degraded.  In the second option, the transparency of the system is degraded because the knowledge is hidden. 


}{End SubSec The Rationale for Factoring Meta-Level Syntax}



{Begin SubSec The Rationale for RuleSet Hierarchy}
{Title The Rationale for RuleSet Hierarchy}
{Text

Some advocates of production systems have praised the flatness of traditional production systems, and have resisted the imposition of any organization to the rules.  The flat organization is sometimes touted as making it {it easy to add rules}.  The argument is that other organizations diminish the power of pattern-directed invocation and make it more complicated to add a rule.  

In designing Loops, we have tended to discount these arguments.  We observe that there is no inherent property of production systems that can make rules additive.  Rather, {it additivity} is a consequence of the independence of particular sets of rules.  Such independence is seldom achieved in large {it sets} of rules.  When rules are dependent, rule invocation needs to be carefully ordered.  

Advocates of a flat organization tend to organize large programs as a single very large production system.  In practice, most builders of production systems have found it essential to create groups of rules.

Grouping of rules in flat systems can be achieved in part by using {it context} clauses in the rules.  Context clauses are clauses inserted into the rules which are used to alter the flow of control by naming the context explicitly.  Rules in the same "context" all contain an extra clause in their conditions that compares the context of the rules with a current context.  Other rules redirect control by switching the current context.  Unfortunately, this approach does not conveniently lend itself to the reuse of groups of rules by different parts of a program.  Although context clauses admit the creation of "subroutine contexts", they require a user to explicitly program a stack of return locations in cases where contexts are invoked from more than one place.  The decision to use an implicit calling-stack for RuleSet invocation in Loops is another example of the our desire to simplify the rules by factoring out control information.  

}{End SubSec The Rationale for RuleSet Hierarchy}


{Begin SubSec The Rationale for RuleSet Control Structures}
{Title The Rationale for RuleSet Control Structures}
{Text

Production languages are sometimes described as having a {it recognize-act cycle}, which specifies how rules are selected for execution.  An important part of this cycle is the {it conflict resolution strategy}, which specifies how to choose a production rule when several rules have conditions that are satisfied.  For example, the {lisp OPS5} production language [Forgy81] has a conflict resolution strategy ({lisp MEA}) which prevents rules from being invoked more than once, prioritizes rules according to the recency of a change to the data, and gives preference to production rules with the most specific conditions.

In designing the rule language for Loops, we have favored the use of a small number of specialized control structures to the use of a single complex conflict resolution strategy.  In so doing, we have drawn on some control structures in common use in familiar programming languages.  For example, {lisp Do1} is like Lisp's {fn COND}, {lisp DoAll} is like Lisp's {fn PROG}, {lisp WhileAll} is similar to {lisp WHILE} statements in many programming languages.  

The specialized control structures are intended for concisely representing programs with different control relationships among the rules.  For example, the {lisp DoAll} control structure is useful for rules whose effects are intended to be additive and the {lisp Do1} control structure is appropriate for specifying mutually exclusive actions.  Without some kind of iterative control structure that allows rules to be executed more than once, it would be impossible to write a simulation program such as the washing machine simulation in {FigureRef FillTub}.  

We have resisted a reductionist argument for having only one control structure for all programming.  For example, it could be argued that the control structure {lisp Do1} is not strictly necessary because any RuleSet that uses {lisp Do1} could be rewritten using {lisp DoAll}.  For example, the rules

{lispcode
Control Structure: Do1;

IF {arg a{sub 1}} {arg b{sub 1}} {arg c{sub 1}} THEN {arg d{sub 1}} {arg e{sub 1}};
IF {arg a{sub 2}} {arg b{sub 2}} {arg c{sub 2}} THEN {arg d{sub 2}} {arg e{sub 2}};
IF {arg a{sub 3}} {arg b{sub 3}} {arg c{sub 3}} THEN {arg d{sub 3}} {arg e{sub 3}};}

could be written alternatively as

{lispcode
Control Structure: DoAll;
Task Vars: firedSomeRule;

IF {arg a{sub 1}} {arg b{sub 1}} {arg c{sub 1}} THEN firedSomeRule_T {arg d{sub 1}} {arg e{sub 1}};
IF ~firedSomeRule {arg a{sub 2}} {arg b{sub 2}} {arg c{sub 2}} THEN firedSomeRule_T {arg d{sub 2}} {arg e{sub 2}};
IF ~firedSomeRule {arg a{sub 3}} {arg b{sub 3}} {arg c{sub 3}} THEN firedSomeRule_T {arg d{sub 3}} {arg e{sub 3}};}

However, the {lisp Do1} control structure admits a much more concise expression of mutually exclusive actions.  In the example above, the {lisp Do1} control structure makes it possible to abbreviate the rule conditions to reflect the assumption that earlier rules in the RuleSet were not satisfied.  

For some particular sets of rules the conditions are naturally mutually exclusive.  Even for these rules {lisp Do1} can yield additional conciseness.  For example, the rules:

{lispcode
Control Structure: Do1;

IF  {arg a{sub 1}}  {arg b{sub 1}} {arg c{sub 1}} THEN {arg d{sub 1}} {arg e{sub 1}};
IF ~{arg a{sub 1}}  {arg b{sub 1}} {arg c{sub 1}} THEN {arg d{sub 2}} {arg e{sub 2}};
IF ~{arg a{sub 1}} ~{arg b{sub 1}} {arg c{sub 1}} THEN {arg d{sub 3}} {arg e{sub 3}};}

can be written as

{lispcode
Control Structure: Do1;

IF {arg a{sub 1}} {arg b{sub 1}} {arg c{sub 1}} THEN {arg d{sub 1}} {arg e{sub 1}};
IF    {arg b{sub 1}} {arg c{sub 1}} THEN {arg d{sub 2}} {arg e{sub 2}};
IF       {arg c{sub 1}} THEN {arg d{sub 3}} {arg e{sub 3}};}

Similarly it could be argued that the {lisp Do1} and {lisp DoAll} control structures are not strictly necessary because such RuleSets can always be written in terms of {lisp While1} and {lisp WhileAll}.  Following this reductionism to its end, we can observe that every RuleSet could be re-written in terms of {lisp WhileAll}.  

}{End SubSec The Rationale for RuleSet Control Structures}



{Begin SubSec The Rationale for an Integrated Programming Environment}
{Title The Rationale for an Integrated Programming Environment}
{Text

RuleSets in Loops are integrated with procedure-oriented, object-oriented, and data-oriented programming paradigms.  In contrast to single-paradigm rule systems, this integration has two major benefits.  It facilitates the construction of programs which don't entirely fit the rule-oriented paradigm.  Rule-oriented programming can be used selectively for representing just the appropriate decision-making knowledge in a large program.  Integration also makes it convenient to use the other paradigms to help organize the interactions between RuleSets.  

Using the object-oriented paradigm, RuleSets can be invoked as methods for Loops objects.  {FigureRef DEFCLASSWashingMachine} illustrates the installation of the RuleSet {lisp SimulateWashingMachineRules} to carry out the {lisp Simulate} method for instances of the class {lisp WashingMachine}.  The use of object-oriented paradigm is facilitated by special RuleSet syntax for sending messages to objects, and for manipulating the data in Loops objects.  In addition, RuleSets, work spaces, and tasks are implemented as Loops objects.



{Begin Figure}
{Tag DEFCLASSWashingMachine}
{Text
{LispCode
[DEFCLASS WashingMachine 
   (MetaClass Class Edited (* "mjs: 25-Nov-82 16:42")
            doc (* Home appliance for washing clothes.))
   (Supers ElectricalDevice PlumbedDevice CleaningDevice)
   (ClassVariables)
   (InstanceVariables 
      (controlSetting Medium
            doc (* One of Small, Medium, Large, ExtraLarge)) ...)
   (Methods 
      (Fill WashingMachine.Fill doc (* Fill the tub with water.))
      (Wash WashingMachine.Wash doc (* Perform the wash cycle.))
      (Simulate UseRuleSet RuleSet SimulateWashingMachineRules)
	...]}
}
{Caption
Example of using a RuleSet as a method for object-oriented invocation.  This definition of the class {lisp WashingMachine} specifies that Lisp functions are to be invoked for {lisp Fill} and {lisp Wash} messages.  For example, the Lisp function {lisp WashingMachine.Fill} is to be applied when a {lisp Fill} message is received.  When a {lisp Simulate} message is received, the RuleSet {lisp SimulateWashingMachineRules} is to be invoked with the washing machine as its work space.  {lisp Simulate} messages to invoke the RuleSet may be sent by any Loops program, including other RuleSets.
}
{End Figure}


Using the data-oriented paradigm, RuleSets can be installed in active values so that they are triggered by side-effect when Loops programs get or put data in objects.  For example:


{LispCode
(DEFINST WashingMachine (StefiksMaytagWasher "uid2") 
   (controlSetting RegularFabric)
   (loadSetting #(Medium NIL RSPut) RSPutFn CheckOverLoadRules)
   (waterLevelSensor "uid3")
]}

The above code illustrates a RuleSet named {lisp CheckOverLoadRules} which is triggered whenever a program changes the {lisp loadSetting} variable in the {lisp WashingMachine} instance in the figure.  This data-oriented triggering can be caused by any Loops program when it changes the variable, whether or not that program is written in the rules language.


}{End SubSec The Rationale for an Integrated Programming Environment}


}{End SubSec Comparison with other Rule Languages}


}{End SubSec Introduction to Rule-Oriented Programming in LOOPS}