The Design and an Example Use of Hearsay-III

1. Introduction

Hearsay-Ill is a domain-independent framework for knowledge­ based expert systems. That is. rather than addressing the problems in a specific application domain. Hearsay-Ill provides a "bare " architecture in which to cast an expert problem solver for a chosen domain. In this sense, it is similar in S;Jirit to EMYCIN [van Melle 79] and AGE (Nii 79] , and other "expert-system-building systems". However. Hearsay-Ill differs substantially in the specific representation and control regimes it makes available to the expert-system builder.

Although Hearsay-Ill is specifically nor a speech-understanding system (and we know of no one who expects to use it for building a speech-understanding system) . it draws strongly on the architectures of the Hearsay-I [Reddy 73] and Hearsay- II [Erman 80] speech -understanding systems. As was intended by the choice of its name, Hearsay-Ill can be viewed as an extension along some dimensions of the Hearsay-II architectural style. and as a generalization of it along others. The concepts of large­ grained, modular knowledge sources and system-wide communication via a structured global blackboard were attractive to us because they provide a major first step toward achieving our design goals for Hearsay-Ill.

This paper presents the motivations behind the design of Hearsay-Ill. ·a detailed overview of its architecture and facilities . and illustrations. via examples. of use of its features Although we concen trate on the novel aspects of Hearsay-Ill . we do not attempt to classify each feature as being new or from Hearsay-II : [Balzer 80a] presents an overview of Hearsay-Ill with such an orientation.

1 Th1s research was supported b~ Defense Advanced Researct1 ProJects Ag~nq contract DAHC15 72 C 0308 V1ews and concluSIOn~ contamed 1n lhts doc ument are those of the authors and should not be mterpreted as represent1ng the official op· n1on or policy of -DARPA the U.S �o~· ernment. or an :,- other pe-rscn or c.; ~~ :- :, c::mnected ;:1 th them

Stephen F. Fickas

USC/Information Sciences !nst . Marina del Rey. CA 90291 and UC Irvine Irvine. CA 92717

The overall design goal for Hearsay-Ill is the developr.1ent of representation and control facilities with which a user can construct an expert system for his chosen domain. The specific attributes we want our system-ouilding system to embody include:

• -Facilities to support codification of diverse sources of knowledge. We have avoided building into Hearsay- Ill any commitment to a class of appl ication domains (such as medical diagnosis) which m1ght allow some speci ficity in the language for describing sources of knowledge. Instead. we attempt to provide as much generality as possible in the types of knowledge that might be brought to bear on a problem from the chosen application domain .
• -Facilities to support application of these diverse sources of knowledge. Beyond mere application of the knowledge sources. an important design goal is to allow flexible coordination of the knowledge sources in their pursuit of an acceptable solution.
• -Facilities to represent and manipulate competing solutions which are incrementally constructed. This aspect of the Hearsay-Ill architecture distinguishes it from the "diagnosis-system-building system" , such as KAS [Dud a 78]. EMYCIN [van Melle 79] , and EXPERT [Weiss 79] .
• -Facilities for reasoning about partial solutions. That is. not only does Hearsay-Ill allow for incremental construction of competing solutions. but it also supports in a straightforward way the ability to reason about and manipulate those solutions during the various stages of their construction .
• -Facilities for describing and applying domain -dependent consistency constraints to the competing partial solutions Thus. the system supports application of knowledge globally so as to aid in reducing the search for a solution
• -Support for long-term. large system development . and in particular . experimentation with varying knowledge for the application domain. and varying schemes for applying that knowledge.

In summary. our goal for Hearsay-Ill is to develop. debug. and experiment with theories of domain expertice. One important area we do not emphasize as a goal for the Hearsay-Ill design is performance of the application system. It is intended that one use Hearsay-Ill to gain an understanding of the problem-solving principles of a chosen domain .. to study the domain . Later. it may be necessary to use a more efficient formalism to construct a performance system for the domain

2. The Architecture of Hearsay-Ill

2.1. The Underlying Relational Database

Hearsay·lll is built on a foundation consisting of a relational database system and its corresponding control facilities. The database language is called AP3 [Goldman 78] and is embedded in lnterlisp (Teitelman 78]. As will be seen in subsequent sections Hearsay· Ill relies critically on the facilities provided within AP3

The AP3 database is similar in structure to those available 1n the PLANNER-like languages [Hew1tt 72] . but it also includes strong typing on assertion. retrieval . and parameter passing in function calls. The type facility in AP3 is available to a Hearsay· Ill user for application domain modeling in addition to being used to advantage within the Hearsay·lll system itself. The Hearsay·lll blackboard (Sec. 2.2) and all publicly accessible Hearsay·lll data structures are represented in the AP3 database. Additional annotations required by the appiication knowledge sources may also be placed in the AP3 database. Because knowledge source triggers are implemented as uniformly represented AP3 demons. modification to the database gives rise to knowledge·source activity (as described in Sec. 2.3) .

AP3 also makes available to Hearsay-Ill applications a context mechanism similar to those found in AI programming languages such as QA4 [Rulifson 72] and CONNIVER [McDermott 74]. Hearsay-Ill supports contexts in such a way as to make them an integrated part of the reasoning mechanisms made available to an application. This feature is somewhat unique among expert· system writing systems. The context mechanism supported in Hearsay-Ill allows reasoning along independent paths which may arise both from a choice among competing knowledge sources and from a choice among competing partial solutions.

The AP3 database system also provides facilities for inference rules and constraints. These facilities. in addition to being used in the implementation of Hearsay-Ill itself, are also available to the user for encoding global domain-dependent relationships. The interaction of constraints and contexts is supported by Hearsay· Ill in that reasoning in a context that produces a constraint violat1on results in the context being flagged as poisoned (see Sec. 2.3)

2.2. Blackboard Structure

The blackboard is the central communication medium provided by Hearsay· Ill. It is used by an application program as a repository for a domain model , for representation of partial solutions, and for representation of pending activities. Hearsay-Ill supports the representation on the blackboard of graph structures consisting of structured nodes called units and labeled arcs called roles. The blackboard is segmented into two: the domain blackboard and the scheduling blackboard . The domain blackboard is intended as the site for competence reasoning, while the scheduling blackboard is intended as the site for performance reasoning. The application writer can further subdivide each of these blackboards.

2.2 . 1. Units

Blackboard units are the fundamental components of the representations built by application programs in Hearsay-Ill. Units are typed AP3 objects: their types are called unit-classes . In fact. the segmentation of the reasoning space into distinct blackboards is accomplished simply as the decomposition of the unit-cl<>ss Unit into several distinct subclasses. Thus, the domain blackboard consists solely of units of class Domain- Unit (and its subclasses): the scheduling blackboard -::onsists solely of units of class ScheduJ.ng·Unit . When desired . access can be restricted to a given blackboard simply by using type·restr1cted AP3 database retrievals

2.2 .2 . Choice Sets

Units have structure in addition to their types. One interesting feature of units is that they can be augmented to expliCitly represent unresolved deCISIOns Such units are called cho ,ce sets . Associated with a choice· set unit is a set of alternatives or a generator of alternatives (or both) . A choice set can be viewed as a partial elaboration of a decision point; the alternatives represent still further elaborations (and they themselves might be choice sets). Thus, competing problem solutions may be represented with a single locus. Furthermore. structure common to all alternatives may be factored out and associated with the choice· set unit itself . The choice·set representation allows for the representation of decisions to be data about which the system can reason .

Hearsay·lll provides two mechanisms for resolving the ambiguity represented by a choice set. These mechanisms interact in an integrated fashion with the context mechanism of AP3. The first mechanism is called a deduce-mode Choose of the choice set . An application program may perform a deduce·mode Choose when it has conclusive evidence that one alternative is tile correct solution for the problem represented by the choice set and that there will be no desire to retract that choice based on further evidence. In this case. the choice set is replaced by the alternative (i.e . their properties are merged) in the context in which the choice is made. In this context. all evidence that the choice set ever existed is eliminated and the blackboard structure appears as if this choice set was never there

The second choice mechanism is called an assume·mode Choose. An assume-mode Choose also replaces the choice set with a unit which represents a merge of the properties of the choice set and the chosen alternative. However. an assume·mode Choose makes these changes in a newly created context that is a child of the one in which the choice was made. The appearance of the blackboard structure in the ne!w context is identical to that resulting from a deduce-mode Choose. The choice-set unit still exists in the parent context with structure modified only to eliminate the alternative just chosen. Thus. if subsequent reasoning indicates this alternative may not be best. it is possible to return to the original context and select a different alternative.

2.2.3. Acceptance

Units have associated with thern a further attribute called acceptance. Acceptance can be thought of as the process of assimilating a unit into larger structure and venfymg that it is appropriate in that structure. More simply. Hearsay·lll allows the application writer to associate with each unit ·class. a collection of procedurally defined predicates. ca led va :,dator . Canon,calizer. Uniqueness-Determiner. Conllict·Dt?term1ner. and lntegrator. 2 Each time a unit is created or is marked unaccepted by a KS. the acceptance routines defined for the unit's class are run . If all succeed. the unit is marked as accepted. If any fai l. the unit is marked as being unacceptable : this usually results in the currently active context being poisoned (see Sec. 2.3) Until a un1t has been

accepted. Hearsay·lll prevents KSs from triggenng on 1t

2 rhe names are merel y 1ntended to be suggeSt I've of no ·. tr-.ey are to bE used

2.2 .4 . Component Roles

As mentioned earlier . Hearsay·lll supports the construct1on of labeled graphs on the blackboard. Units are the nodes in those graphs. The labeled arcs are called component rotes (or simply roles ). and are represented as typed relat1ons connecting two units. The typing of roles is of significant convenience. because it allows the use of type-restricted AP3 retrievals to simplify searching the structure. Roles. in ad·jition to being typed. are also placed in classes called role sets . Role sets are used lor two purposes. First. they define distinct component hierarchies in which units are related by the trans1tive closure of the roles in a given role set . This allows the supression of detail along chosen dimensions when examining the blackboard structure. The second use of role sets relates to consumption. discussed next.

2.2.5 . Consumption

Hearsay-Ill supports a facility lor describing mutual exclusion of units in an aggregated blackboard structure. This is accomplished by prohibiting any structure in which two units are both components of a third unit (by transit1ve closure over a role set) , while at the same time those two units are declared to consume a fourth This facility allows a convenient form lor expressing the undesirability of using the same part1al solution or interpretation lor different purposes in an overall solution.

2. 3. Knowledge Sources

The domain-specific knowledge lor an application built in Hearsay-Ill is embodied in knowledge sources (KSs) . Each KS can be thought of as a large-grained production rule: it reacts to blackboard changes produced by other KS executions and in turn produces new changes.

To define a KS, the user provides a triggeflng pattern. immediate code, and a body. Whenever the pattern is matchable on the blackboard. Hearsay-Ill creates an activat ion record unit lor the blackboard and runs the immediate code. At some later time. the activation record may be selected (see Sec. 2.4 about scheduling) and executed. i.e .. the body. which is arbitrary Lisp code. is run. In more detail :

• -The triggering pattern is expressed as an AP3 pattern. As such. it is a predicate whose primitives can be AP3 fact templates and arbitrary Lisp predicates. composed with AND and OR operators. Whenever the AP3 database (which includes the Hearsay·lll blackboard. i.e .. the units and roles) is modified such that any of the AP3 templatEs in the pattern is matched. the entire pattern is evaluated. II the entire pattern matches. an activation record is created and has stored in it the :<s·s name. the AP3 context in which the pattern matched 3 (called the tr iggering context) . and the values of the variables instantiated by the match.
• -At the point the activation record is created . the immediate code of the KS IS executed This code which also is arbitrary lisp code. may associate information with the act ivation record that may be of value later in deciding when to select this act ivat ion for execution. In addition. the immediate code must return as its value the name of some unit class of the scheduling blackboard. The activation record is then placed on the blackboard as a unit of that class The immed1ate code 1s executed in the triggering context and has ava1lable to it the instantiated pattern vanables.

3 1n AP3. lh! conlexl on ,.-hoch a pan·rn "'-IChes os ~·'"'·d to De th<' ,.ast g~n~ral conte·l·r -.·, h·ch ttach of the paf1t-H" parts has miltc. P\ed

• -At some subseQuent time. the system·s base scheduler (see below) may call the Hearsay-Ill Execute action on the activation record. The usual result of this is lor the body of the KS to be run in the triggering context and with the pattern variables instantiated. II, however. at the point of execution. the triggering context of the activation is poisoned and the KS has not been marked as a poison handler . the body ia not run: rather. the activation record is marked aa awaiting unpoisoning . and will have its status reverted to ready if the poison status of the context is ever removed.

Each KS execution is indivisible: 11 runs to completion and is not onterrupted for the execution of any other KS activat1on This 1nsulates tne KS execution and simplifies the coding of the body there need be no concern that during a KS execution anything on the blackboard is modified except as effected by the KS itself .

2.4. Scheduling

Hearsay-Ill is intended lor use in domains in which scheduling schemes are likely to be complex. Also. the application writer 1s not expected to have a good a priori notion how to accomplish the scheduling. Thus he will need to be able to experiment freely with various schemes. Since we view the scheduling problem itself as having characteristics similar to the domain problem. we feel the Hearsay-Ill blackboard-oriented knowledge-based approach is appropriate for its solution as well and thus supply the same mechanisms for its solution.

Because of the indivisibility of KS execution. the scheduling problem in Hearsay-Ill can be stated as follows: At the end of each KS e"<ecution. determine. from the state of the system. the KS activation to execute next. To help solve this problem. several concepts. features. and mechanisms are useful :

• As described above. the time of execution of a KS body 1s delayed arbitranly long from its triggering . w1th the activation record unit. on the scheduling blackboard as the mechanism for represent1ng the activation. Also . the immed1ate code of the KS 1s run on creat1on of the activat1on record. allowong KS·spec1fic scheduling information to be added to the activation record
• -Some knowledge·sources. termed sc nEavtmg I"S~ . may make additional changes to the schedulong blacw,board to facilitate the se1ect1on of act1vation records. Scheduling KSs may respond to changes both on the domain blackboards and on the scheduling blackboard. including the creation of act1vation records. The actions they may take include associating information with act ivat ion records (e.g.. assigning and modifying priorities) and creating new units to represent meta· information about the domain blackboards (e.g .. pointers to the current highest· rated units on the domain blackboard) . The scheduling blackboard is the database for solving the scheduling problem.
• -The application writer provides a base scheduler procedure that is called by Hearsay-Ill after startup and actually calls the primitive Execute operation lor executing each selected KS activation. We intend the base scheduler to be very simple: most of the knowledge about scheduling should be embod1ed in the scheduling KSs. For example. the base scheduler might consist simply of a loop that removes the first element from a Queue. maintained by scheduling KSs. and calls for its execution. If the aueue is

ever empty. the base scheduler simply terminates mark1ng the end of system execution

Hearsay·lll prov1des a default base scheduler It IS comoosed of two functions. either of which can t:· replaced by the application writer. The default outer base scheduler repeatedly calls the default inner base scheduler and expects it to return a list of activation record units. (When the inner base scheduler returns the empty list. the outer base scheduler exits. halting system execution.) The · outer base scheduler executes each activation record in turn . If the KS executed is a scheduling KS and its execution returns a list of (non-scheduling) activation records. the outer base scheduler immediately executes each of those activation records in turn. Each time the default inner base scheduler is called it non­ deterministically chooses one ready scheduling KS activation record. or. if there are none. one non-scheduling KS activation record. The default inner base scheduler is particularly trivial and is expected to be replaced in any serious application: the default outer base scheduler is likely to be a reasonable skeleton for many applications.

3. An Example of Use

To illustrate the use of Hearsay-Ill as an implementation language for expert systems. we describe here the implementation of the Jitterer problem-solvm!J system (Fickes 80). The problem addressed by the J1tterer is the automatiC transformation of program parse trees. The Jitterer maps a given parse tree (initial state) into a new parse tree (the goal state) by the application of a seQuence of eQuivalence-preserving transformations. The initial parse tree and the intermediate and final parse trees generated by the transformation seQuence are called program development states. The description of the goal state is supplied by the user.

The Jitterer is one component of a Transformational Implementation system (Balzer SOb) which allows a user to semi· automatically refine and optimize a high-level program specification into an efficient implementation. An example of an optimization step a Transformational Implementation user might attempt is the merging of two set enumeration loops. Before actually executing the merge step. the user might call on the Jitterer to reach a (goal) state m which the two loops a) are adJacent. b) generate the same sets. and c) do not rely upon or affect the enumeration order of the set elements. If the Jitterer is successful. the user can execute the merge step and achieve the desired optimization.

Each transformation is composed of 1) a left-hand-side pattern (or simply LHS) that must match a portion of the current program development state. 2) zero or more enabling conditions that must hold in the LHS match context. and 3} a set of actions to perform when 1 and 2 have been satisfied. The application of a transformation generates a new. semantically eQuivalent. program development state.

The Jittering system faces several interesting problems:

-Many transformations in the catalog may be applicable in a given development state. Further. many transformations have a corresponding inverse transformation. allowing infinite seQuences.

-Establishing the enabling conditions of a transformation may be costly. in both machine time and user effort.

• Each Jittenng problem has m general more than one solution (seQuence of transformation appllcat1ons lea<hng to the goal state) Metrics must be identif1ed for order~ng competing solutions 4

3.1. Design of the Jitterer

The Jitterer's basic problem-solving mechanism is a backward· chaining. best-first search . This choice helps alleviate the problems associated with the large transformation fan -out. the potentially high cost of establishing enabling conditions. infinite paths. and solution ordering.

The J11terer makes two types of control dec1s1ons a selection from among the competing partial solution paths of the nE·l<t path to extend. and a selection from among competing transformations of a transformation for continuing the chosen path. In order to limit search. rules are used to guide both ~<·nds of decis1ons A~ example of a path selection rule is "If a ;:la!h s lenc;:~" excee:s Path Threshold . suspend it'' . where Path Threshold has been determmed expenmentally. An example of a transfo·mat1on selection rule is "If a transformat1on has Side-effect X. lower (ra1sel its des~rabihty"

These selection rules reference features extracted fr::>m the current state as well as features predicted about the eflects of poss1ble select·ons Features referenced by the path SE!Iect1on rules mclude current path cost pred1cted cost to solution number of transformations applied predicted number of total transformations needed. current status (dead. suspended. alive. complete solut1on). and solution compatabihty. For transfo·mation selection. features of interest include transformation side-effects and prediCted transformation cost. as computed in both machine time and user effort Feature information can be computed on demand or stored and maintained explicitly: the latter a~proach was chosen because of perceived recomputation costs.

A transformation can be applied to a program devel::>pment state only after its LHS has been matched and its enabl1ng conditions have been established. A straightforward approach to establishing these conditions for a single transfo·mat1on application would lump all tests into a single schedulable activity. Given the potentially high cost of establishing enabling conditions. this approach is too inflexible. It may be more efficient to order the establishing of the enabling conditions: an attempt to establish one enabling condition may provide informat1on which will lead to the suspension or abandonment of the transformation application. Thus. we reQuire that the establishment of each enabling condition be a separate. schedulable activity

3.2. Hearsay-Ill Implementation of the Jitterer

In this section. we describe how each component of the Jitterer is implemented in Hearsay-Ill.

3.2. 1. State/Space Representation

The Jitterer design reQuires two collateral spaces: the program development space. generated by transformation applications and representing various program development states. and the reasoning space. generated by the best-first and backward· chaining search and representing partial solution paths and goal /

-'One SOiut·On mttnc t$ ho~ well I SCiuhon fttS .,., .:· tl"'' tt'le user$ 'T\.:'rE g;::- ~ development strateg) f='or e~~.ample . an> J·tterer .produ:ed soluhC",.. .. ~ . ,' ... nd~~5 · Prt!\IOUS oot·m·zahon 01 preyents a future oct·mizat·cr. must be gt\en lc :. pnor :t) To comoute th1s metnc the J·tterer must be able tc. analyzE' past de\ ~lopment Slell$ and pred·ct lulure developmer'lt steps. the lat:er prese"l · n~ o~ : ·'' probiem!t

subgoal relationships . By using Hearsay-Ill's unit-class mechanism. the class of Domain -Units can be subdivided into Reason.ng-Units and Development- Units . and thus we implement the two spaces as a segmentation of the domain blackboard . Although the reasoning space references un1ts in the development space the two spaces are essentially independent .

A state in the reasoning space is an AND/ OR goal tree. The goal tree is built from Reasoning -Units (goa '·unit, transformation · umt) and component roles (sub-goal. achteves ). An OR node represents the choice among competmg transformations. An AND node represents the set of goals (transformation applicability checks) that must be satisfied m order to apply a particular transformation . The Hearsay- Ill choice-set mechanism (see Sec . 2.2.2) provides a framewor~ both for structuring the set of competing transformations and for manag1ng child contexts assoc.ated w1th the choice. An assume-mode choose is used. spawn1ng new reasonmg states !contexts) when a transformation is chosen.

A state in the program development space represents the entire program parse tree at a particular stage of development. The parse tree is built from Development -Units (e.g .. loop-unit. assignment-un i t) and component roles (e.g .. predicate . then ­ clause . loop-body). In the development space. there is no notion of a choice set , rather, simply a recording of various program development paths. The appl ication of a transformation generates a new Hearsay -lfi / AP3 context. Note that there is no need to copy the program development state (i.e .. the syntax tree) into the new context: the Jitterer relies on the context inheritance mechanism and thus needs to represent explicitly only those portions of the structure that are new or modified.

3 .2.2 . Transformation Representation

Each transformation is implemented as a domain KS (henceforth . transformation KS) . Because of the Jitterer's backward-chaining control. the trigger of a transformation KS corresponds to the action port1on (translated so to match the goals of the reasoning space) of the corresponding transformat ,on . The immediate code of a transformat ion KS is respons1ble for settmg up as subgoals the LHS pattern to be matched and the enabling conditions to be established : we describe th1s further 1n me next section The body. when executed . creates a new context (program develoj.lment state) and makes the appropriate modifications.

3 .2 .3 . Control Knowledge

As described in Sec . 3.1. the Jitterer uses rule-based selection knowledge to control search . Each selectiOn rule is implemented as a scheduling KS (see Sec. 2.4) . For example. one selection rule treats the desirability of a transformation as a function of the side· effects 11 produces . Figure 3-1 shows the scheduling KS form for one instance of th1s rule. namely that a transformation that unfolds a funct1on m-line has the deleterious side-effect of flatten1ng the program structure 5

(Declare - SKS structural-flatten lnc ( Op ) Tr igger: (AND (CompetingOperat or OP ) (SideEffect Op UnfoldsFunction)) /mmedtare Code: Operator-ordering-level Boov : ( De creaseDesirabilityOP ))

5 rne actual AP3 t H~a rsa ~ · lll syntax has been modtl·eC r.ere to· et a··!:

Earlier . we mentioned a rule that checks for a path growmg beyond a PathThreshold . Figure 3·2 shows the scheduling KS form of th is rule. Note that the evaluation of the 1mmed1ate code of the two scheduling KSs places their corresponding activat1on records on separate scheduling levels . The Jitterers base scheduler gives Path-state-change-level priority over Operator-ordering -level. and hence path suspension is attempted before transformation ordering .

(Declare-SKS lengthy-path ( Path) Tngger: (AND (CompetingPath Path) ( > (CurrentPathlength Path ) PathThreshold )) Immediate Code: Path-state-change-level Body : (MarkAsSuspended Path))

As discussed in Sec. 3.1. the Jitterer's selection rules reference certain computed problem-solving features This information is stored as auxiliary reasoning structures attached to the relevant units on the scheduling and domain blackboards. For example, an auxiliary reasoning structure for path selection is attached to each goal -unit in the reasoning space 6 The scheduling KS in Fig . 3·2 makes reference to the path length of Path. Current path length information is stored in and retrieved from the auxiliary structure associated with Path 's frontier goal.

To descibe the auxiliary reasoning structure used for transformation selection . we must look more closely at the implementation of transformations as KSs. Hearsay-Ill div1des a KS application between triggering and execution . As des·:ribed Sec. 2.4. once a KS is triggered . an activation record is crea·ted on the scheduling blackboard where it resides until executed oy the application's base scheduler. The Jitterer selects from among the set of activation records of triggered transformation KSs. Thus. this set that must be ordered . The immediate code of each transformation KS is responsible for attaching an auxiliary reasoning structure to the corresponding activation record . For example. the scheduling KS in Fig. 3·1 makes reference to the side-effects of a transformation . These side-effects are amo'lg the information stored in the auxiliary reasoning structure attacl1ed to the corresponding activation record. The immediate code is also responsible for adding the activat1on record to the choice set of the appropriate OR goal in the reasoning space.

3.2 .4 . The Scheduling of Enabling Conditions

The Jitterer design calls for the separate scheduling ol each enabling condition . This is implemented in Hearsay-Ill in the same manner described for auxiliary reasoning structures in the previous sect1on : the immed iate code of a transformation KS augments the activation record wi th the set of enablin~ cond1t1ons. The scheduling KSs and the base scheduler order the set and determine when to attempt establishment of the individual cond1t1ons. In some cases it may be undesirable to execute an activat1on record even though all enabling conditions have been established . A few scheduling KSs look for these cases ard flag the act1vation record accordingly In general. the ability to divide problem solving into such fine ·grained acti vi t1es has been helpful for the J1tterer

6E3ch gcat t5 ·· e .-. ed as the lrcnt·~ r cf a pa tr-. from th~ 'C·ot goal

3 .2 .5 . The Scheduling of Scheduling KSs

The Jitterer·s selection rules . implemented as schedulin\l KSs. help order the path and transformation search space. However . we are left wi th the problem of scheduling the schedulin9 KSs. The Jitterer's schedul ing blackboard is divided into a set of mutually exclusive. prioritized scheduling levels. Each scheduling KS is assigned to a single level by its immediate code . The Jitterer's base scheduler returns. for execution . an activation record from the highest level on which activation records reside.

For many levels. intra·level scheduling consists simply of executing activation records in arbitrary order until none remain on the particular level. Operator·ordering·level . referenced in Fig . 3· 1. is scheduled in this way. However. some scheduling levels provide structures for ordering their activation re::ords. One example is the level on which the activation records of competing transformations are placed: the transformation selection rules maintain an ordered list. Another level . Reporr­ sotur,on·level. discussed below. provides a queue for recording the order of activation record appearance. When an activation record is placed on this level , a "queue maintenance" scheduling KS adds it to the end of the queue. Given the best-first search . the final queue will contain spokesmen for all solutions found by the Jitterer in their order of preference.

We have previously seen in Fig. 3·1 and Fig. 3·2. two of the defined scheduling levels. Another example is the scheduling blackboard's highest priority level . 7 Reporr-soturion-level. Because the KS that detects complete solutions is assigned to this level by its immediate code. its activation records are executed immediately following any KS activation that satisfies its triggering pattern. Thus. the Jitterer reports a solution to the user as soon as it is found . If instead the Jitterer was to find all solutions to a problem before reporting any. Report -solution -level should be made the lowest priority scheduling level.

3.2 .6 . Use of the Acceptance Routines

The Jitterer's scheduling KSs normally determine the difficulty of achieving a particular goal. attaching appropriate information to the goal's auxiliary structure. However, detecting Jittering goals that are inherently impossible is performed by a Validator acceptance routine. When a new Jittering goal is posted in the reasoning space. the appropriate Validator determines whether it falls into this special class. If so. the goal is marked as impossible before being considered by the rest of the system. Currently. only easily determined impossible goals are handled by the Validator routines. Thus. more sophisticated tests about impossible goal states are not included in the Validator routines because we want the system to be able to schedule these costly activities. Once a goal unit is created . al l Validator routines pertaining to that goal are run .

The Jitterer applies a set of normalization and simplification rules each time a new program development state is generated (i.e .. whenever a parse tree is changed).a This clean -up process has been implemented in Hearsay-Ill through the Canonicalizer acceptors each node type (unlt ·class) of a parse tree (e.g .. loop­ unit . assignment -un it. conditiOnal -unit) has an associated Canonicalizer: each Canonicallzer embodies the set of clean-up rules for its node-type. It is the responsibility of a transformat ion changing the parse tree to mark the relevant nodes (units) for (re­ )acceptance (see Sec. 2.2 3) .

7 Th1s is actually not Qu>te the h>ghest level even h>gher are those used b1· the schedul·ng KSs that do ·ntra·level struc tur.n~

8 WhLie these rules also make changes tc the parse tree they do not ca L· ~: ~ .... ~ gEner at ·:>n :;I ne :. dE\ elopment states

4. Conclusion

Hearsay-Ill was exercised initially on two small test cases. a cryptarithmatic problem and a cryptogram decoding problem. In addition to the Jitterer . two major implementation efforts are currently underway. The first of these is the reimplementation of SAFE. a system for constructing formal specifications of programs from informal specifications [Balzer 78) . Second . Hearsay-Ill is being used as the basis for a system for producing natural language descript1ons of expert system data structures fMann 79) .

In some problem domains. the major implementation effort will be the encoding of the competency portion of the problem-solving system in the form of KSs. The performance portion of the system may not require sophisticated scheduling techniques. sufficing on a reasonably tunable set of hard -wi red scheduling regimes. such as the AGE system provides. In these cases. the Hearsay-I ll system may seem less useful since the user will have to build- up all but the most primitive control structures from scratch . Although such is currently the case. as more and more projects use Hearsay-Ill. the stock of different appl ication schedulers will grow. It seems reasonable to assume that with a little wor~ these schedulers can be generalized to provide a new user with a library of Hearsay-Ill schedulers from which to choose. A new problem domain may be able to use an existing scheduler directly or as the foundation for a more application-specific scheduler

Our experience to date supports our belief that the Hearsay-Ill architecture is a helpful one. The separation of competence knowledge from performance knowledge helps in rapidly formulating the expert knowledge required for a solution. The flexibility that the Hearsay· ill architecture gives toward developing scheduling algorithms will undoubtably go a long way toward simpl1fymg this d1ff1cult aspect of the overall problem-solving process.

Acknowledgments

Hearsay-Ill was originally des1gned was by Bob Balzer. Lee Erman . and Chuck Williams. w1th contribut1ons by Jeff Barnett. Mark Fox. and Bill Mann . Subsequently. Phil London and Neil Goldman contributed Sign ificant design modificat ions. Lee Erman and Phil London implemented and maintain Hearsay- Ill . AP3 was designed. implemented. and mamtamed by Neil Goldman . Steve Fickas designed and implemented the Jitterer Neil Goldman. Bill Mann. Jim Moore. and Dave Wile have also served as helpfu l and patient initial users of the Hearsay· ill system.