Method and apparatus for executing control system functions in a computer system

A control system is implemented by provision of parts which are data structures with identities, properties, and references to other parts, and clusters which are structures of associated parts. Clusters are assembled into meanings, and contexts are built from meanings and logic components. A current behavior expression consisting of a cluster is established and a meaning analysis procedure searches a set of meanings in a current context for correspondence between one or more meanings and the current behavior expression. When correspondence is found, further analysis switches the current behavior expression to a meaning matched in the current context. The process continues, switching context if necessary, until no meaning can be matched to a portion of the current behavior expression. Those portions of the current behavior expression for which no meaning is found represent primitive actions which are executed to carry out a system intention.

BACKGROUND OF THE INVENTION 
The invention concerns the implementation of a control system function in a 
machine system. 
A conceptual representation of a control system implementation is 
illustrated in FIG. 1. The control system operates with respect to an 
environment which is external to a computer system by sensing external 
circumstances and performing operations on the external environment in 
response. The control system is implemented in the computer system, which 
has an internal environment and internal circumstances which can be 
perceived by a control component embodying the control system's intention. 
The control component can act upon both internal and external 
environments. The "sense" and "act" operations, both internal and 
external, embrace hugely differing types of environments. 
A control system functioning within the external environment of a factory, 
for example, will employ some means to sense pertinent physical properties 
of the factory process which is subject to control. Such physical 
properties might be temperature, pressure, fluid level, assembly line 
rate, color, and so on. The factory control system will have the ability 
to act on its external environment in ways also dictated by the nature of 
the process being controlled. Examples of such actions are the provision 
of electrical signals to affect the operation of electrical circuits such 
as relays and the provision of textual or graphical information for 
recognition and understanding by human users. Broadly, these are 
discernable indications of control system actions on the external 
environment. 
The comprehensive variety of means for implementing a control system 
includes digital or analog circuitry ("hardware"), the programming of 
digital systems ("software"), or a combination of hardware and software. 
In these days, the interactions between a computer and external users such 
as humans or electronic complexes are largely predetermined by specific 
programming. In effect, users can interact with a computer only in ways 
which are allowed by the software running in the computer. Adaptation to 
the needs and circumstances of a particular user or a particular external 
environment requires the building of new versions of old programs. 
Many techniques have come into widespread practice to meet the problem of 
extreme variability in user needs and environments. One response has been 
a move toward adoption of standards for all aspects of computer systems, 
both hardware and software. Another response involves modular 
decomposition of software systems into component parts so that new 
versions of old programs may be more rapidly constructed by combining a 
number of new components with a number of old components from previous 
versions. While the use of these techniques has been significantly 
beneficial to the practice of software production, the benefit has 
generally been in the productivity of software programmers. The benefit, 
therefore, is necessarily limited by the size of the programmer 
population. 
Another important technique which transcends this last limitation involves 
the construction of programs which permit specific predefined aspects of 
their behavior to be modified by a user without new programming. This 
technique does require the software programmer to define, at the time of 
program creation, the specific aspects which are to be made subject to 
user re-configuration. This additional effort pays off because it requires 
far less labor on the part of the programmer than that required to produce 
a large number of program versions. However, as computer systems become 
more complex, it is increasingly difficult to anticipate all dimensions in 
which a particular program may need to be adapted. Thus, despite 
industry's recognition of the problem and the adoption of a number of 
strategies aimed at overcoming it, the problem remains and, by some 
measures, becomes more grave every year. 
SUMMARY OF THE INVENTION 
The invention has the objective of increasing a user's ability to adapt a 
control system to more closely satisfy the user's requirements. 
The objective is achieved in a preferred embodiment of the invention by 
construction of a software program which allows a user's functional 
requirements to be expressed to the program in a manner determined by the 
user rather than the software programmer. The functional requirements 
represent the user's expression of a desired behavior of the system. The 
expression of desired behavior and the system's response take place in a 
particular input/output form commonly understood by user and system. Using 
the input form of expression, the user discloses the desired behavior to 
the system, the system analyzes the desired behavior in a system context 
which was preconstructed by the user in order to convey the meaning of the 
behavior expression to the computer system. Consideration of the behavior 
expression proceeds by a process of meaning analysis which involves 
searching a set of meanings in the current context for correspondence 
between one or more of those meanings and the current behavior expression. 
Whenever such a correspondence is found, further analysis switches the 
current behavior expression to the meaning matched in the current context. 
If necessary, the context is switched. The elements of the current 
behavior expression are recursively searched for lower-level meaning by 
repeated application of the same process until no meaning can be matched 
to a portion of the current behavior expression. Those portions of the 
current behavior expression for which no meaning is found represent 
primitive actions of the control system which are capable of being 
executed by the computer system. These primitive actions are executed and 
the process switches back to meaning analysis and continues until there 
are no more meaningful portions to be found in the behavior expression. 
In addition to allowing user/system interaction to occur in any form of 
input/output, the invention also provides for user adaptation of both 
meaning analysis and action execution phases. Resultantly, the user is 
afforded the ability to construct an expression of desired behavior which: 
(1) makes use of an input/output form of the user's own choosing, and (2) 
makes use of terms of expression whose meanings and corresponding actions 
are also subject to specification by the user. 
In a preferred embodiment, the invention is practiced in a computer system 
which executes a computer program, the computer system including a storage 
unit, a central processing unit, input means for providing input data to 
the storage unit and central processing unit, and output means for 
providing discernable indications of actions performed by the central 
processing unit. In this context, the invention is a method for 
implementing a control system, using: 
a plurality of parts, where each part includes a data object and has a 
first portion identifying the part, a second portion including a series of 
associated data items, and a third portion for referencing one or more 
other parts; and 
a plurality of clusters, each cluster including a data structure with a 
plurality of inter-related parts. 
In the method: 
at least one cluster is stored; 
a plurality of meanings are stored, each meaning including: 
a template having one or more parts; and 
a definition cluster; 
a plurality of logic components are stored, each logic component including 
an invocable procedure which is executable by the central processing unit; 
a plurality of contexts are built, each context including an associated set 
of meanings, an associated set of logic components and means for 
identifying another context; 
a first context is designated as a current context; 
a cluster is designated as a current behavior expression; 
(a) parts of the behavior expression are compared with templates in the set 
of meanings associated with the current context; 
(b) for each meaning of the set of meanings whose template matches parts of 
the behavior expression: 
the definition cluster of the meaning is designated as the current behavior 
expression; and 
a second context identified by the first context is designated as the 
current context; 
(c) steps (a) and (b) are performed until a part in the current behavior 
expression is found which does not match a part in a meaning template; 
a logic component associated with a current context and identified by a 
data item of the second portion of the part found in step (c) is invoked; 
a control system action is performed by executing the logic component; and 
a discernable indication of the control system action is provided. 
More particularly, in step (c) of the method, steps (a) and (b) are 
recursively performed until a plurality of primitive action parts in the 
behavior expression are found which do not match a meaning template, the 
invoking and performing steps are executed for each part of the plurality 
of primitive action parts, and the providing step is executed for one or 
more parts of the plurality of action parts.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
FIGS. 2-5 illustrate basic components of a control system built and 
operated according to the invention. FIG. 2 illustrates two interrelated 
"parts". A part is an element of a control system according to the 
invention which has a number of characteristics accessible to the 
invention. A part has: (1) an identity by which it may be referred to by 
other parts within the system; (2) a set of zero or more data items 
associated with the part; and (3) zero or more references to other parts 
in the system. Generally, a part includes a data object which, according 
to the IBM Dictionary of Computing, is "an element of data structure . . . 
that is needed for the execution of a program and that is named or 
otherwise specified by the allowable character set-of the language in 
which the program is coded". In this invention, a part can be identified 
by a storage address. The plurality of data items of a part is used to 
establish a set of action-specific attributes or parameters associated 
with a part. Last, the reference portion of a part is provided to link 
parts together into structured forms. 
In FIG. 2, a first part has portions 10, 14, 16, in which the portion 10 
includes an identification of the part. The identification can include an 
address locating the second portion 14 of the part in memory. The second 
portion 14 includes zero or more data items 15, each data item being 
provided to establish a respective attribute associated with the part. 
Last, the part's third portion 16 includes one or more references 18 to 
other parts 19. The second and third portions may overlap. That is, a 
reference to another part may be a data item in the group of one or more 
data items in the second portion. 
The two parts illustrated in FIG. 2 are said to be "interrelated" by virtue 
of the linkage by which the first part references the second part and the 
second part is referenced by the first part. 
FIG. 3 illustrates a cluster of interrelated parts. In the cluster of FIG. 
3, each part refers to or is referred to by at least one other part. Some 
parts refer to more than one succeeding part. The sense of FIG. 3 is that 
upper parts refer to lower parts, so that the part represented by the node 
21 refers to the part at node 25 and is referred to by the part at node 
24. Further, the part represented by the node 25 refers to parts at nodes 
26 and 27. 
Although FIG. 3 illustrates a uni-directional scheme of reference with the 
sense being downward, this is by way of example only, and is not intended 
to exclude clusters with oppositely-directed senses. Nor is FIG. 3 
intended to exclude bi-directional reference which would, for example, 
permit part 21 to refer to and be referred to by part 24. 
In general, then, a cluster is simply a set of parts in which each part is 
related to at least one other part in the cluster. According to the 
invention, every cluster has an primary part, which is the point at which 
processing of that cluster begins. 
FIG. 4 illustrates a data structure referred to as a "meaning". In FIG. 4, 
the meaning 30 includes a meaning template portion 31, a definition 
cluster portion 32, and a definition context portion 33. The meaning 
template portion includes a pointer 31a to a cluster 31b of interrelated 
parts forming the meaning template. The definition cluster portion of the 
meaning 30 includes a pointer 32b to a part cluster 32c referred to as the 
"definition cluster" of the meaning 30. The third portion 33 of the part 
30 includes a data object ("cntxt ID") 33a which identifies a definition 
context in which the definition cluster 32c is to be analyzed to give 
meaning to a current behavior expression. 
Last, the invention utilizes basic logical functions ("components") which 
may be implemented in software, in hardware, or in both. FIG. 5 
illustrates one such logic component in the form of a software procedure 
which may be invoked by name for execution. 
A subset of the logic components, termed "action primitives" together with 
basic input/output operations of the system of the invention permit the 
system to perform useful work on behalf of the user. Execution of one of 
these procedures is referred to as a control system "action". 
Useful work is performed by analysis of a behavior expression representing 
a desired behavior of the system. A behavior expression is essentially a 
cluster of parts which is given meaning in a specific context. A "context" 
for the purpose of this invention signifies a collection or set of 
meanings, together with a collection or set of logic components which are 
used in the context to apply the meanings to the behavior expression and 
to execute control system actions. FIG. 6 illustrates conceptually the 
structure of a context. 
In FIG. 6, a plurality of contexts are assumed, two of which are 
represented by contexts 32 and 34. The contexts have identical structures, 
but may include different structural elements. Thus, only the structure of 
the context 32 will be described, the assumption being that this 
description also applies to all other contexts of the control system. The 
context 32 has a specific name (CONTEXT 1) that names a structure 
embracing a set of meanings and a set of logic elements. The meanings have 
a structure described above with reference to FIG. 4, while the logic 
elements are presumed in this description to be invocable procedures as 
illustrated in FIG. 5. Meanings are included in a meaning pool 36, while 
the logic elements are included in logic pool 37. The context 32 has a 
meaning list listing specific meanings within the pool 36 which are 
considered to be included within the context. The inventors contemplate 
that the meaning sets of contexts may overlap or be exclusive. As FIG. 6 
shows, the meaning list of the context 32 includes the meaning 36a in the 
context. Observe that the third portion of the meaning 36a points to the 
context 34 thereby permitting a change of context during the operation of 
the invention. 
The context 32 also includes a logic list listing logic components in the 
logic pool 37 that are included in the context 32. In the preferred 
embodiment, the minimum complement of logic components for every context 
includes the following: meaning definition logic, part selection logic, 
meaning selection logic, cluster match loop logic, recursive match logic, 
match loop control logic, and primitive action logic. Variations of each 
of these seven types of logics may be found in the logic pool 37 so that 
any context may include a particular variation for each logic type. 
Context logic lists may be exclusive or overlapping. 
FIG. 7 illustrates a computer system configured according to the invention. 
The computer system consists of conventional components, including a 
central processing unit (CPU) 40, a storage facility including a working 
memory 42 and direct access storage 43, an input/output facility 45 and 
system/user interface devices including display 46, keyboard 47, and a 
mouse 48. 
The operation of the invention is controlled and orchestrated by an 
executor 50 that coordinates the operation of the various parts of the 
invention with an underlying operating system and maintains the 
invention's operation flow. The executor 50 oversees and controls a 
meaning analysis procedure 52 (described below) which determines the 
meanings of expressions of desired behavior of the control system, 
determines the meanings of terms which may appear in such expressions, and 
decides the type of primitive actions to take as a result of processing 
expressions and terms. 
The executor 50 also controls the operations of a storage management 
function 53. The storage management function 53 provides the ability to 
access and manipulate various data structures which are required in the 
operation of the invention. The primary data structures managed by this 
function are illustrated in the working memory 42 with the understanding 
that updating them may require access to direct storage 43. The primary 
structures managed by storage management function 53 are a set of data 
items called current circumstances 56, the current context 57, the current 
behavior expression 58 which consists of a part cluster undergoing meaning 
analysis, a current working pool 60, and a current match results pool 61. 
An action execution function 55 is also controlled by the executor 50. The 
purpose of the action execution function 55 is to perform a sequence of 
one or more primitive actions which is determined by the primitive action 
logic of the current context 57 in conjunction with the current 
circumstances 56 and any properties associated with a part specified by 
the meaning analysis 52. The range of possible primitive actions is 
determined by the nature of the underlying means of implementation. 
The executor 50 is connected conventionally to the input/output facilities 
45 of the computer system and may receive data and commands input by a 
user through the keyboard 47 and mouse 48. Any aspect of the current state 
of the control system of the invention is provided visually through the 
input/output facilities 45 by way of conventional display 46. Another 
input/output capability necessary for a specific example of operation of 
the invention (described below) includes a conventional message facility 
68 for receiving and transmitting messages. 
Meaning Analysis 
Refer now to FIGS. 7 and 8 for an understanding of the meaning analysis 
function. Initially, it is asserted that an intention consists of two 
elements: a current behavior expression and a context. The behavior 
expression is a cluster of parts whose purpose is to specify operational 
aspects of an intention. The purpose of the context is to define a 
specific set of meanings and associated logical components which are used 
by the invention in order to translate the behavior expression into 
action. Circumstances are general data structures containing information 
reflecting internal and external environmental conditions; circumstances 
are generated as a result of primitive action execution or as a result of 
meaning analysis. The storage management function 53 may actively keep 
some circumstances "up to date" with respect to a given environment. Such 
circumstances, therefore, reflect the current state of some conditions in 
the specified environment. Circumstances may also be created or modified 
as a consequence of the operations of the meaning analysis function 52 and 
the action execution function 55. 
The meaning analysis function 52 operates cooperatively with the storage 
management function 53, evaluating the current intention in the light of 
current circumstances so as to specify an appropriate set of actions which 
are to be performed by the action execution function 55. The meaning 
analysis function 52 operates by examining the behavior expression and 
identifying clusters of parts from the behavior expression which match 
meaning templates from the current context's set of meanings. Current 
circumstances are updated as may be required for the matching process. 
Meanings identified by this matching process may themselves be subjected 
to further meaning analysis. 
Further meaning analysis is performed on a given meaning by switching 
attention away from the current intention and applying the meaning 
analysis function to an intention associated with the given meaning. In 
this regard, recall that each meaning has a portion identifying a 
definition context. When a match is found between a cluster of the current 
behavior expression and a meaning template in the current context's set of 
meanings, the current context is replaced with the definition context 
identified in the matched meaning. In some cases, the contexts may be the 
same; in other cases, the contexts may be different and thus need to be 
switched. In addition, the current behavior expression is switched by 
temporarily replacing the cluster being analyzed with the definition 
cluster of the matched meaning. Thus, when a match occurs, a new intention 
is analyzed. The current circumstances in the light of which the new 
intention is analyzed may include additional information added by the 
matching step. Ultimately, meaning analysis of this new intention may, in 
turn, cause additional intentions to be subjected to meaning analysis. 
Consequently, the analysis of the overall significance of a particular 
intention can lead to an expanding number of additional intentions which 
must be analyzed. This expansion only begins to reverse itself when 
intentions are encountered whose behavior expressions contain parts that 
have no corresponding meaning in that intention's context. When a meaning 
cannot be found for a part in a behavior expression, the primitive action 
logic 55 is invoked on that part in the light of the current circumstances 
56. Based on the part and the circumstances, the primitive action logic 
decides what action to take. 
The meaning analysis function 52 of FIG. 7 is illustrated in more detail in 
FIG. 8. In FIG. 8, the initial inputs to the meaning analysis function 
prior to, or concurrent with, the entry step 69 are a behavior expression, 
a context, and a set of circumstances. During execution, the meaning 
analysis procedure of FIG. 8 may refer to other behavior expressions and 
contexts and may modify the current circumstances. The objective of the 
meaning analysis function is to identify those parts encountered in the 
access to behavior expressions for which no meaning can be assigned. Such 
parts are "primitive action specifiers". 
Upon entry into the meaning analysis function for the first time, a current 
context is specified with its set of meanings and its set of logic 
components and processing begins on the part cluster denoted as the 
behavior expression, with processing proceeding with reference to the 
current circumstances. Recall that each context has a particular set of 
meanings and logic components which are accessed and invoked as required 
by the meaning analysis function. 
As FIG. 8 shows, whenever meaning analysis is initiated on a behavior 
expression, the first part logic 70 of the current context is activated. 
The first part logic identifies a single part within the current behavior 
expression which is temporarily referred to as the "current candidate 
part". Next, the first meaning logic 72 of the current context is 
activated to select an initial meaning from the set of meanings 73 of the 
current context. This meaning is routed, along with the candidate part, to 
cluster matching logic 74, where an attempt is made to find a "candidate 
cluster" in the behavior expression that matches the meaning template of 
the selected meaning. In this regard, a "current candidate cluster" is any 
cluster in the behavior expression whose primary part is the current 
candidate part. Relatedly, a "primary part" is a part from which a 
candidate cluster emanates. If the match is successful, certain 
information concerning the match is assembled at step 76 into a match 
result item which is stored in the match results pool 78 for the context. 
Each match result item in the match results pool contains, at least: 
(1) a boundary list which identifies those parts in the behavior expression 
falling just outside the candidate cluster; 
(2) the definition cluster associated with the meaning whose meaning 
template matches the candidate cluster; and 
(3) the portion of the matched meaning containing the definition context 
identifier. 
Match loop control logic 79 is now activated to make two independent 
determinations: (1) when to process match result items from the match 
results pool 78, and (2) when to quit the cluster match loop 74, 76, 79, 
80. If the match loop control logic 79 decides to continue in the cluster 
match loop, it invokes the next meaning logic 80 of the current context to 
select from the set of meanings 73 the next meaning to be routed along 
with the current candidate part to the cluster matching logic 74 where 
another match attempt is made. Match result items accumulated in the match 
results pool 78 are processed at 82 at the discretion of the match loop 
control logic 79. As each match result item is processed by 82, the parts 
in its boundary list component which are not already in the working pool 
83 are added to it. For each new match result item, a new instance of the 
meaning analysis function will be entered at 85. Each new instance of the 
meaning analysis function will use the definition cluster as its behavior 
expression, will use the identified definition context as its current 
context, and will employ a new set of circumstances consisting of the 
circumstances of the previous meaning analysis instance. Once the match 
loop control logic 79 determines that there are no more meanings to be 
tested, it invokes the process match result in step 82 to perform a final 
evaluation of the match results pool 78, before leaving the cluster match 
loop 74, 76, 79, 80 and moving on to the next candidate part. In this 
final invocation of the result item processing step 82, any remaining 
match results in the match results pool 78 are processed and a meaning 
analysis is selectively launched at 85. If, at this point, it is 
determined that the cluster match loop was not successful in finding any 
match for the current candidate part among all the meanings selected from 
the current set of meanings, then the action execution step 87 is invoked 
to perform the action corresponding to the unmatched candidate part. When 
step 87 is performed for the current candidate part, its boundary list is 
computed and these parts are added to the working pool. It should be noted 
that the action execution step 87 is performed on a given candidate if, 
and only if, no meaning analysis is performed at 85 for this candidate 
part. When the match loop control logic 79 has finished this last 
increment of work, it activates the next part logic 89 of the current 
context. The next part logic 89 selects a new candidate part from the 
working pool 83 and loops back to the entry to the cluster match loop at 
step 72. If the next part logic 89 detects that the working pool 83 is 
exhausted, this instance of the meaning analysis process is concluded at 
90 and exited at 92. Upon exit, a meaning analysis suspense list is 
consulted to determine whether any prior instances of meaning analysis 
have been suspended. If so, the next most recent instance is reactivated, 
and so on, until the first instance has completed, in which case the 
overall meaning analysis function is exited. 
The cluster matching loop 74, 76, 79, 80 is given, as input, a candidate 
part and a meaning part. Naturally, from the candidate part, the cluster 
matching logic 74 is able to inspect smaller clusters in the cluster 
forming the behavior expression which have the candidate part as their 
primary part. Such clusters are referred to as "candidate clusters". 
Cluster matching is essentially embodied in a pattern-matching operation 
which seeks to determine if there is a candidate cluster in the behavior 
expression which matches a meaning's meaning template. In general, a 
cluster match involves comparing sets of attributes or properties 
contained in the data item portions of parts and a certain methodology by 
which those properties or attributes of parts in the meaning template are 
compared with corresponding properties or attributes of parts in a 
candidate cluster. This logic is required to examine candidate clusters in 
the behavior expression which might possibly match the meaning template. 
The inventors contemplate that the cluster match function may be 
implemented using any pattern-matching method which can verify that each 
part in the meaning template has a corresponding part within a candidate 
cluster in the behavior expression. If this necessary and sufficient 
condition cannot be verified, no match exists. If the condition can be 
verified, a match does exist. The cluster matching function must transmit 
certain information back to the meaning analysis instance responsible for 
its activation. The cluster matching logic must also indicate success or 
failure of the match attempt and provide the boundary list of parts 
directly related to the candidate cluster (or to the candidate part itself 
in the case of an unsuccessful match). Cluster matching logic may also 
include match-specific information produced by this particular attempt. If 
a particular set of match criteria establishes several different ways in 
which a correspondence can be said to exist between a part of the current 
behavior expression and a part in the meaning template, it may be 
desirable to indicate which of these different ways was used in a 
particular match. 
The action execution step 87 performs a sequence of one or more primitive 
action executions. Primitive actions are executed by the primitive action 
logic of the current context. This logic is given access to a specified 
part and the current circumstances. Based on this information, the 
primitive action logic executes a primitive action sequence. The range of 
possible primitive actions is limited only by the nature of the underlying 
means of implementation. It may be that some of these primitive actions 
are NO OP steps; it may be that other of these primitive actions produce 
results which are to be provided discernible form to a user. In this case, 
an output step 88 is invoked and a discernible indication of the action is 
provided to the user. When candidate part processing is completed, return 
is made to the match loop control 79. 
In Appendix F, in C++ language format, a pseudo-code expression is given 
for the meaning analysis function illustrated in FIG. 8. 
EXAMPLE: MESSAGE HANDLING 
Overview 
Consider applying the invention to the task of providing automated support 
for a routine office environment activity such as scheduling meetings. 
This example looks at a small part of this activity: namely, the handling 
of meeting requests. It is assumed that meeting requests are sent to 
prospective meeting participants via electronic mail (as through the 
message facility 68 in FIG. 7). Replies are also expected by electronic 
mail. The point of the example is to demonstrate: (1) how the invention 
may be used to specify the behavior of an automated system which assists a 
human user in the task of responding to electronically delivered meeting 
requests; and (2) how the invention may be used to adapt such a 
specification to the requirements of an individual user. 
For the sake of brevity, much of what would exist in an actual meeting 
scheduling system is not discussed in this example. The problem is 
explored in a simplified form and many complex elements of a real system 
are assumed to exist for the purposes of this example. In particular, it 
is assumed that an electronic mail system is in use within an organization 
whose members must make frequent meeting arrangements. In addition, it is 
assumed that each user makes use of an electronic calendar system which 
maintains a database of scheduled time commitments for that user and 
provides access to meeting room schedule information. It is also assumed 
that the basic operational capabilities of both the electronic mail system 
and the calendar system can be used as primitive elements by a 
higher-level system constructed in accordance with the method of the 
invention and described here. 
In this example, the invention is used to specify the steps to be taken by 
the system responsible for responding to a meeting request received via 
electronic mail. A request message is assumed to contain information items 
in a preordained order which indicate the who, what, where, when and why 
of an event. This example only considers events for which the "what" is "a 
meeting". The "who" field specifies the intended participants and may 
consist of a list of names of individuals and/or groups. It is assumed 
that when a group is named, the names of the individuals which comprise 
that group are also available to the system. The "where" field identifies 
the proposed location of the requested meeting. The "why" field gives the 
subject matter of the proposed meeting. And the "when" field gives the 
proposed meeting time. 
In this example, a meeting request can result in one of the following 
actions: accept request, decline request, propose alternate participants, 
or propose alternate time and place. Given a specific request and a 
database containing personal schedule information for a specific user and 
general information about the organization, the system must proceed 
through a series of logical steps to determine which of the above actions 
is appropriate. This series of steps will be defined in terms of a number 
of diagrams (which are more fully discussed below). There are two cases 
presented in this example. The first case gives what might be thought of 
as a "standard" or "default" method of handling a message request. For 
this case, the diagrams in FIGS. 9A thru 12E apply. The second case 
demonstrates how the desired behavior of the system can be changed. For 
this case, the diagram in FIG. 14 will be applied instead of the diagram 
in FIG. 10. 
Significance of Diagrams 
A diagram is a two-dimensional visual representation consisting of an 
organized collection of separate visual elements. This example presumes 
the existence of a diagram-editor (similar to a graphical tool such as a 
CAD/CAM system) which is a computer-based system that allows a user to 
create and store diagrams as well as access and modify previously stored 
diagrams. The diagram-editor (reference numeral 51 in FIG. 7) has the 
ability to manipulate both the on-screen visual diagrammatic elements as 
well as their corresponding, computer-oriented representations. For the 
purposes of this example, a number of diagrams will be used to define the 
intended behavior of the system. 
Machine Representation of Diagrams 
A diagram is represented within the machine as a collection of data objects 
known as parts. Every part has the three portions described above. In this 
example, the data items of the second portion of a part are properties, 
each of which consists of a "property-kind" and a "property-value". The 
property-kind identifies the nature and purpose of a given property while 
the property-value contains information in a form appropriate for a given 
property-kind. In this message handling example, there are only three 
basic forms by which a part is represented on-screen. A part may appear as 
either a box, a connector or a triangle and it may be drawn with either a 
solid, bold, or dashed line. These characteristics of a part are stored as 
properties with the following property-kinds and property-values: 
______________________________________ 
Property-Kind 
Property-Value 
______________________________________ 
type either "box", "connector" or "triangle". 
Each part must contain exactly one of 
these properties. 
style either "solid", "bold", or "dashed". 
Each part must contain exactly one of 
these properties. 
______________________________________ 
There are several notational conventions that are useful to introduce at 
this point: 
1. The property-kind of a property may be used to characterize or qualify a 
property. Thus, if a property within a part has a property-kind of "type", 
this property may be referred to as the "type property" of that part. 
Similarly, if a property within a part has a property-kind of "style", 
this property might be referred to as the "style property" of the part. 
2. Both the property-kind and the property-value can be expressed by a 
statement to the effect that a given part has a type property of "box". 
What is meant by this statement is that the given part contains a property 
whose property-kind is "type" and whose property-value is "box". 
3. A part may be characterized by its type property (since every part must 
contain such a property). Thus a part whose type property is box may be 
referred to as a "box". Similarly, a "connector" is a part whose type 
property is connector and a "triangle" is a part whose type property is 
triangle. 
4. A part described as a box, a connector or a triangle may be further 
qualified by its style property. Thus, a connector may be "solid", "bold", 
or "dashed". 
Making use of these short-hand conventions, additional constraints on 
properties can be described. A "connector" will always possess the 
following additional properties: 
______________________________________ 
Property-Kind 
Property-Value 
______________________________________ 
source the identity of the part from which the 
connector emanates. 
target the identity of the part at which the 
connector terminates. 
______________________________________ 
According to the above, a connector's source property is said to point at 
the part which is the source of the connector, and the target property 
points at the connector's target. A connector's source and target 
properties are matched by two additional properties: 
______________________________________ 
Property-Kind 
Property-Value 
______________________________________ 
source-of this property indicates the part is the 
source of a connector; the value of this 
property is a reference to the connector. 
Multiple source-of properties are 
permitted per part. 
target-of this property indicates the part is the 
target of a connector; the value of this 
property is a reference to the connector. 
Multiple target-of properties are 
permitted per part. 
______________________________________ 
Finally, there is one property whose existence is optional: 
______________________________________ 
Property-Kind 
Property-Value 
______________________________________ 
text a string of characters which are to be 
associated with the part. These are 
displayed inside the outline of a box or 
triangle and near the mid-point of a 
connector. Only one text property is 
permitted per part. 
______________________________________ 
Each part may also contain certain properties used by the diagram-editor 
such as those used to specify the on-screen coordinates of the 
corresponding visual element (the visible representation of a part). These 
properties will not be discussed further here. FIG. 9A is a diagrammatic 
representation of a collection of parts. Each box, triangle or connector 
which appears in diagram will also have a corresponding internal machine 
representation which conforms to the requirements set out above. Consider 
the parts 101, 102, 103, 103a, 103b, and 104 which appear at the top of 
FIG. 9A. The internal, machine representation of these parts would 
include: 
part (101): 
has a type property of box, 
has a style property of solid, 
has a text property of "handle request", 
has a source-of property which references (or points at) part (102), 
has a source-of property which points at part (103a) (the solid connector 
attached to the triangle). 
part (102): 
has a type property of connector, 
has a style property of dashed, 
has a text property of "what", 
has a source property which points at part (101), 
has a target property which points at part (103). 
part (103): 
has a type property of box, 
has a style property of solid, 
has a text property of "**details", 
has a target-of property which points at part (102). 
part (103a): 
has a type property of connector, 
has a style property of solid, 
has a source property which points at part (101), 
has a target property which points at part (103b). 
part (103b): 
has a type property of triangle, 
has a style property of solid, 
has a target-of property which points at part (103a). 
has a source-of property which points at part (104). 
has a text property of "C2" 
part (104): 
has a type property of connector, 
has a style property of solid, 
has a source property which points at part (103b), 
has a target property which points at part (117). 
The remaining diagrammatic elements in FIGS. 9A thru 12E and 14 will have 
internal representations which correspond in a similar fashion. 
DETAILED DISCUSSION OF THE EXAMPLE 
In accordance with the Detailed Description of the Preferred Embodiment, 
several things are required for a fully functioning system. The system's 
executor component must be able to construct and initialize one or more 
context data structures in which each context contains a series of 
meanings and a collection of logic components. It is assumed that the 
executor has the ability to access the diagrams necessary for each case of 
the example discussed here. Further, it is assumed that the executor has 
the ability to access the logic components described in detail below and 
to properly associate these logic components with the three contexts used 
in this example. When the executor begins operation, it must initialize 
all the parts of the system which are under its control. As part of 
initialization, the executor will initialize the default context C1 along 
with any other context it may detect. The default context is always 
assumed to exist. An additional context is designated by the existence of 
a part whose type is "box" and whose style is "bold". 
Meaning-Definition-Logic 
The meaning-definition-logic component for this context is found in the 
diagram editor, described above. The logic must: 
1. Search all diagrams for collections of parts which can be recognized as 
meanings by this meaning-definition-logic, 
2. For each meaning so identified, find and store the primary-part of the 
meaning-template, the primary-part of the definition-cluster and the 
definition-context to be used for the meaning. 
The definition-cluster-logic used in this example employs a simple set of 
conventions which permit these steps to be carried out. A user who wishes 
to create a new meaning uses the diagram-editor to construct a cluster of 
diagrammatic elements (parts) which is the desired meaning-template and 
another cluster of parts which is the desired definition-cluster. This 
logic employs a diagrammatic convention by which these two clusters may be 
associated together and identified as a meaning in such a way that their 
distinct roles are preserved. 
According to the simple convention used in this example, triangles are 
reserved for the purpose of identifying meanings. So, a triangle is not 
permitted to exist within either a meaning-template, a definition-cluster, 
or the system's initial behavior-expression. The user marks the existence 
of the new meaning by creating a triangle and two connectors. The 
meaning-template is designated by creating a connector whose source is the 
primary-part of the meaning-template and whose target is the triangle. The 
definition-cluster is designated by creating a connector whose source is 
the triangle and whose target is the primary-part of the 
definition-cluster. This simple convention unambiguously indicates the 
existence of a meaning and identifies the primary-parts of both the 
meaning-template and the definition-cluster. The text property of the 
triangle is used to designate the definition-context that is to be 
associated with the meaning. 
Given this convention, the meaning-definition-logic builds the context's 
meanings-list by searching the diagrams for triangles and then inspecting 
the two connectors which are, according to this convention, attached. It 
can be seen, then, that the primary-part of the meaning-template is the 
part pointed at by the source-of property of the connector whose target 
property points at the triangle. Looking at FIG. 9A, the triangle is part 
103b. This triangle is pointed at by the connector 103a. The source-of 
property of this connector points at part 101. Thus, part 101 is the 
primary-part of a meaning-template. The primary-part of the 
definition-cluster is the connector whose source property references the 
triangle. Looking again at FIG. 9A, part 104 is the primary-part of the 
definition-cluster. As each meaning is added to the meanings-list, the 
triangle and its two adjacent connectors must be identified in some way so 
that later processing will not erroneously consider them to be part of a 
meaning-template or a definition-cluster. This is done here by adding 
these parts to a list of parts already matched in this context. 
The definition-context saved with a meaning is the context designated by 
the text property of the triangle. Thus, for example, the triangle 103b of 
FIG. 9A includes a text property "C2", which identifies the context C2. 
This means that the definition cluster whose primary part is 104 is to be 
evaluated in context C2. It is assumed in this example, that the items 
identified as meanings are stored in a simple list in whatever order the 
they are encountered by the meaning-definition-logic. This simple list 
storage device constitutes the meanings-list for the context. 
Observe that in FIG. 10, the illustrated meanings (A and B) are enclosed in 
a single rectangle, together with the notation "C2::import C1". This 
indicates that these meanings are defined in context C2 and that context 
C2 "imports" the meanings from context C1. Similar notation is found in 
FIG. 14. 
Initial Behavior-Expression 
FIG. 9B shows the example's initial behavior-expression. It is assumed that 
the initial behavior-expression for a system begins with a box whose text 
is "start" (as with part 105). The point of this behavior-expression is to 
test the meaning of "handle request" with a sample request for a meeting 
at noon-wednesday, in the lunchroom, for the purpose of draft-product-spec 
with the members of the planning group as participants. Here, the executor 
is presumed to have initialized the text properties of parts 108, 110, 
112, 114, and 116 from the corresponding fields of the an electronic mail 
message like: 
______________________________________ 
what: meeting 
who: the planning group 
where: lunchroom 
why: draft-product-spec 
when: noon-wednesday 
______________________________________ 
Meaning Analysis Applied to the Example 
As discussed in the Detailed Description of the Preferred Embodiment, the 
system's intention is evaluated by the executor through a meaning analysis 
process which is presented with an initial behavior-expression, a context 
and a set of circumstances. In this case, the initial behavior-expression 
is given by FIG. 9B, the context is the global context (C1) which is 
assumed to exist for this example, and the set of circumstances is 
initially empty (that is, an internal machine data structure which is 
capable of storing various items of information but which has been 
initialized to contain no such items). It is also assumed that the 
meaning-definition-logic for each context has been activated so as to 
result in the construction of a meanings-list data structure for each 
context. For sake of the example, assume that the triangles in the 
diagrams are encountered in the order in which the figures are presented 
here. Thus, the meanings-list for context C1 will be ordered so as to 
correspond with FIGS. 9A, 11A, 11B, 12A, 12B, 12C, 12D, and 12E. The first 
two meanings in the meanings-list for context C2 will correspond with 
meanings A and B in FIG. 10. The remainder of C2's meanings-list will be 
copied from C1's meaning-list because "::import C1" appears in the text 
property of C2. Similarly, the meanings-list for context C3 will consist 
of the meaning that corresponds with FIG. 14 followed by the meanings from 
C1's meaning-list because "::import C1" also appears in the text property 
of C3. Note that FIG. 9B does not contain a triangle and so has no 
corresponding meaning in any meanings-list. 
The Example is next illustrated with a step-by-step description of the 
operation of the invention. This description is intended to be read with 
reference to FIGS. 9A-12E and to the logic descriptions which follow it. 
The following steps are now performed: 
1. The executor creates a new instance of the meaning analysis process 
shown in FIG. 8, and gives it references to the initial 
behavior-expression, the global context and the current circumstances. 
2. Next, C1's first-part-logic (see logic description 1.1.1) is activated 
in order to select an initial candidate part. When activated for the first 
time, the first-part-logic searches the behavior-expression for a box 
whose text is "start". Given the initial behavior-expression shown in FIG. 
9B, part 105 will be selected by the first-part-logic. 
3. With this part as the current candidate part, C1's first-meaning-logic 
is now activated (see logic description section 1.2.1). The 
first-meaning-logic will pick the first meaning on the context's 
meanings-list. This first meaning is the one represented in FIG. 9A. 
4. References to the primary-part of this meaning's meaning-template (part 
101) and the current candidate part (part 105) are routed to C1's 
cluster-match-logic (see logic description 1.3.1). 
5. Cluster-match-logic begins by invoking the match-parts-logic (see logic 
description 1.3.2) in order to compare parts 101 and 105. 
6. While parts 101 and 105 have matching type and style properties, their 
text properties fail to match. Match-parts-logic reports failure to 
cluster-match-logic. 
7. Cluster-match-logic notes the failure and calls C1's get-parts-logic 
(see logic description 1.3.4) passing it a reference to the current 
candidate part (part 105). 
8. Get-parts-logic inspects part 105 and notes that it has a source-of 
property. The connector referenced by this property (the connector 105a) 
is examined. Since the style property of this connector is "solid", a 
reference to this part (connector 105a) is added to the parts list being 
built (the "boundary list"). At this point get-parts-logic is finished 
because part 105 has no more properties of interest (see logic description 
1.3.4). Get-parts-logic returns a list containing only part 105a. 
9. Cluster-match-logic now returns to the instance of meaning analysis 
which invoked it, passing back the boundary list built by get-parts-logic 
and a failure indication. 
10. Meaning analysis now builds a result-item (the build step 76 in FIG. 8) 
consisting of the boundary-list (which contains part 105a only) and the 
failure indication. This result-item is stored in the results-pool for 
this instance of meaning analysis (see FIG. 8, step 78, and FIG. 15). 
11. Next, the match-loop-control-logic (FIG. 8, reference numeral 79) is 
activated. This logic functions by processing each result-item as it is 
generated (see logic description 1.3.5). In this case, since the 
result-item indicates failure, the next-meaning-logic is activated (see 
logic description 1.2.2). Given the earlier assumption as to the order of 
meanings in the meanings-list, the next-meaning-logic will return a 
reference to the meaning shown in FIG. 11A. 
12. Meaning analysis will now attempt another cluster-match (as in step 4 
above), this time with the current candidate part (part 105) and the 
primary-part of the next meaning found in the meanings-list (part 160). 
13. The above steps 4 through 11 will be repeated for each meaning in the 
meanings-list. By examining the diagrams involved in the example, it can 
be seen that there is no meaning that will match the part 105. These steps 
will be repeated essentially as described above until the 
match-loop-control-logic (step 11) is encountered after an uncessful 
attempt to match the last meaning. 
14. At this point, the example is in match-loop-control under conditions 
that will cause the next-meaning-logic to report that there are no more 
meanings to examine. As described below in logic description 1.3.5, 
match-loop-control will now activate the primitive-action-logic, giving it 
a reference to the current candidate part (part 105). 
15. The primitive-action-logic (see logic description 1.4) will examine 
each word in the text property of the part, looking for words which begin 
with the character "*". In this case, there is only one word ("start") and 
it does not begin with a "*", so the word "start" is written into the 
system's log file and control is returned to the match-loop-control-logic. 
Match-loop-control-logic now accesses the current result-item, copies its 
boundary-list (consisting of part 105a only) into the working-pool (FIG. 
15) and returns to meaning analysis with a result indicating that a new 
candidate part should be selected. 
16. Meaning analysis now activates the next-part-logic (FIG. 8, reference 
numeral 89). Next-part-logic (see logic description 1.1.2) takes a part 
from the working-pool (FIG. 15) and makes this part the current candidate 
part. In this case, the new candidate part will be the connector 105a. 
17. Meaning analysis once again sets about searching the meanings-list for 
a successful cluster-match. This is done by again invoking C1's 
first-meaning-logic. This corresponds to step 3 above (but this time with 
part 105a as the current candidate part). 
18. As was true previously, there is no meaning in the meanings-list that 
will successfully match the connector 105a. Therefore, meaning analysis 
will cycle through the meanings-list as it did before, with 
match-parts-logic failing every time. The only real difference in 
attempting to find a cluster match with connector 105a is that when 
get-parts-logic inspects this part (in accordance with logic description 
1.3.4), it will not find a source-of property. Instead, a source and a 
target property will be detected. When the source property is examined, 
get-parts-logic will note that the part referenced by this property (part 
105) has been marked as matched in the current meaning analysis instance 
and, consequently, part 105 will not be placed on get-part-logic's list. 
When the target property is examined, get-parts-logic will note that the 
part referenced by this property (part 106) has not been marked as matched 
and will, consequently, place part 106 on the list it returns to 
cluster-match-logic. As in steps 9 and 10, cluster-match-logic returns 
this list to meaning analysis where the list becomes the boundary-list in 
a new result-item which takes the place of the old one in the results-pool 
(FIG. 15). 
19. Control will finally arrive at match-loop-control-logic with the 
meanings-list having again been fully examined. As before in step 14 
above, match-loop-control-logic will activate the primitive-action-logic, 
giving it a reference to the current candidate part (this time part 105a). 
Primitive-action-logic (logic description 1.4) will attempt to examine 
each word in the part's text property. Since this part has no text 
property, primitive-action-logic returns, taking no action. 
Match-loop-control-logic now copies the current result-item's 
boundary-list (this time consisting of part 106 only) into the 
working-pool (FIG. 15) and returns to meaning analysis with a result 
indicating that a new candidate part should be selected. 
20. Meaning analysis now activates the next-part-logic. Next-part-logic 
(see logic description 1.1.2) takes a part from the working-pool (FIG. 15) 
and makes this part the current candidate part. In this case, the new 
candidate part will be the box 106. 
21. Meaning analysis again sets out to find a successful cluster-match. 
This is done by invoking C1's first-meaning-logic (reference numeral 72 in 
FIG. 8) which again corresponds to step 3 above (but now with part 106 as 
the current candidate part). 
22. In the case of the two candidate parts examined so far (parts 105 and 
105b), both parts failed all cluster-match attempts. With part 106 as the 
current candidate part, a successful cluster-match will occur. 
23. References to the current candidate part (part 106) and the 
primary-part of the first meaning (part 101) are routed to C1's 
cluster-match-logic (see logic description 1.3.1). 
24. Cluster-match-logic invokes match-parts-logic (logic description 1.3.2) 
to compare parts 101 and 106. Since parts 101 and 106 have matching type, 
style and text properties, match-parts-logic reports success to 
cluster-match-logic. 
25. Cluster-match-logic next invokes get-parts-logic (logic description 
1.3.4), passing it a reference to the candidate part, in order to build a 
"candidate.sub.-- list" of parts referenced by the candidate but excluding 
any parts previously matched. In this case, the candidate.sub.-- list will 
contain just one part, the connector identified as part 107 in FIG. 9B. 
26. Cluster-match-logic invokes get-parts-logic again, this time passing it 
a reference to the meaning part (part 101), in order to build a 
"meaning.sub.-- list" of parts referenced by the meaning part but 
excluding any parts already matched during this match attempt. The 
meaning.sub.-- list will also contain just one part, the connector 
identified as part 102 in FIG. 9A. 
27. Cluster-match-logic now invokes C1's recursive-match-logic, giving this 
logic access to the candidate.sub.-- list and the meaning.sub.-- list. 
28. Recursive-match-logic (logic description 1.3.3) performs the function 
of comparing a candidate.sub.-- list with a meaning.sub.-- list and 
invoking itself again (recursively) as many times as may be necessary to 
fully explore the meaning-template. Proceeding with logic description 
steps 1.3.3.A, recursive-match-logic determines that there is only one 
possible pairing of parts from the two lists (since each list contains 
only one part). At this point, the m-part is part 102, and the c-part is 
part 107. 
29. Proceeding with logic description steps 1.3.3.B and 1.3.3.C, 
recursive-match-logic applies get-parts-logic to the m-part (part 102) to 
build a "meaning.sub.-- grandchildren" list consisting of part 103. 
30. Next (1.3.3.D) match-parts-logic is invoked to determine if the m-part 
(part 102) and the c-part (part 107) match. 
31. Since these two parts match (their type, style and text properties are 
identical), recursive-match-logic (in accordance with step 1.3.3.E) now 
applies get-parts-logic to the c-part (part 107) to build a list of 
"candidate.sub.-- grandchildren" (here consisting solely of part 108). 
32. Advancing to step 1.3.3.F, recursive-match-logic determines that the 
meaning.sub.-- grandchildren list is not empty and so invokes itself, 
passing both the meaning.sub.-- grandchildren list and the 
candidate.sub.-- grandchildren list to the new instance of 
recursive-match-logic. While discussing the operation of this new 
instance, these two lists will be referred to as its meaning.sub.-- list 
and candidate list. 
33. The new invocation of recursive-match-logic begins at step 1.3.3.A, 
determining that there is only one possible pairing of parts from the two 
lists (since each list contains only one part). The m-part is part 103, 
and the c-part is part 108. 
34. Proceeding with steps 1.3.3.B and 1.3.3.C, get-parts-logic is applied 
to the m-part (part 103) to build a meaning.sub.-- grandchildren list. 
Since part 103 has no properties which refer to un-matched parts, this 
list is empty. 
35. Next (1.3.3.D) match-parts-logic is invoked to determine if the m-part 
(part 103) and the c-part (part 108) match. 
36. In this instance, match-parts-logic will identify this match as special 
since the text property of the m-part starts with "**" (see 1.3.2.A). 
Match-parts-logic reports a match along with an indication that this is a 
special match involving "**". Also in accord with 1.3.2.D, a 
circumstance-item is constructed and added to the current circumstances 
data structure (FIG. 16): 
______________________________________ 
Formal-String: "**details" 
Actual-String: 0 
Actual-Part: part 108 
Actual-Context: C1 
______________________________________ 
37. Recursive-match-logic (in accord with 1.3.3.E) responds to the special 
match condition by skipping ahead to 1.3.3.H where it is noted that the 
list of unmatched c-parts is empty and that all m-parts have been matched. 
38. Step 1.3.3.I has no effect since the candidate.sub.-- list is exhausted 
so, at step 1.3.3.J this instance of recursive-match-logic exits, 
reporting a match and returning an empty boundary-list. 
39. This brings the process back to the instance of recursive-match-logic 
which we left at step 32, above. In returning to this previous instance, 
we return to the point in 1.3.3.F following the invocation of 
recursive-match-logic. 
40. Continuing with 1.3.3.F, the returned boundary-list is saved. Step 
1.3.3.G has no effect since this boundary-list is empty. 
41. This instance of recursive-match-logic also moves quickly through steps 
1.3.3.H and 1.3.3.I because the list of unmatched c-parts is empty and all 
m-parts have been matched. 
42. At step 1.3.3.J, recursive-match-logic exits back to 
cluster-match-logic, reporting a match and returning an empty 
boundary-list. 
43. Cluster-match-logic continues in step 1.3.1 and also exits, reporting a 
match. This exit returns to step 74 in FIG. 8. 
44. Next, meaning analysis updates the results-pool (FIG. 15) by (1) 
discarding any old result-items that may be in the results-pool and (2) 
adding a new result-item which indicates that part 106 was matched by the 
meaning of FIG. 9A and which contains an empty boundary-list. 
45. Meaning analysis activates the match-loop-control-logic (1.3.5) which 
immediately processes the new result-item by invoking a new instance of 
meaning analysis. This instance of meaning analysis will evaluate this 
definition-cluster in the light of the circumstances data structure and a 
new context. The circumstances data structure currently contains a 
circumstance-item indicating that part 103 was matched by a cluster of 
parts, namely parts 108-116. The new context used by this instance of 
meaning analysis will be C2 (because the triangle associated with this 
meaning has a text property of "C2" which caused C2 to be the 
definition-context designated for this meaning). This change in the 
"current" context is called a context switch. When this new instance of 
meaning analysis completes, the executor will return control to the 
previous instance of meaning analysis which will resume processing using 
context C1. Thus, a switch to a new context is temporary and returns to 
the previous context once analysis in the new context has been completed. 
46. This instance of meaning analysis starts by invoking C2's 
first-part-logic (1.1.1) which designates the primary-part of the 
definition-cluster as the current candidate part (connector 104 in FIG. 
9A). Meaning analysis will proceed to search C2's meanings-list for a 
meaning-template which matches any cluster of parts emanating from part 
104. 
47. As was the case in step 18 when an attempt was made to find a match for 
connector 105b, there is no meaning-template that successfully matched 
connector 104. In this case, when get-parts-logic is applied to part 104, 
part 117 will be the only member of the list returned. This list will 
become the boundary-list in new result-item that replaces the old one in 
the results-pool (FIG. 15). As in step 19 above, primitive-action-logic 
will be invoked but will take no action since part 104 has no text 
property. Part 117 will be copied out of the result-item's boundary-list 
and into the working-pool by match-loop-control-logic who returns to 
meaning analysis a result indicating that a new candidate part should be 
selected. 
48. It should be clear by now that meaning analysis proceeds to invoke the 
next-part-logic (89, FIG. 8). In this case, the new candidate part will be 
the box 117. Meaning analysis once again sets out to find a successful 
cluster-match for the new candidate part (part 117). 
49. A match will be found with the meaning A in FIG. 10. 
50. The primary-part for this meaning's meaning-template is part 140 and 
will be found to match part 117. While the type and style properties of 
these two parts are identical, their text properties are not. The text 
property for part 117 is "appropriate subject for me?" while that for part 
140 is "appropriate subject for *individual?". 
51. The reason why these non-identical text properties are considered to 
match is to be found in the specification of match-parts-logic, in 
particular step 1.3.2.D. When this step is reached, the identical words in 
the two text properties have been found. 
52. The text property of part (140) is deemed to match the text of part 
(117) because the word "*individual" in the meaning-template is allowed to 
match the word "me" in the candidate-cluster. The convention employed here 
is that a word beginning with a single "*" is permitted to match any 
corresponding portion of text in the candidate-cluster not exactly matched 
by surrounding words or characters. Thus, 
"appropriate subject for me?" and 
"appropriate subject for *individual?" 
are considered to match, according to logic step 1.3.2.D. Also in accord 
with this step, a circumstance-item will be added to the current 
circumstances data structure (FIG. 16) that indicates that the word 
"*individual" was matched by the word "me": 
______________________________________ 
Formal-String: "*individual" 
Actual-String: "me" 
Actual-Part: 0 
Actual-Context: C2 
______________________________________ 
53. Once parts 140 and 117 have been matched, the cluster-match-logic will 
attempt to match the remaining parts in the meaning-template (141-148). It 
can be seen that the cluster (145,146) will match (118,120) because of the 
"**" at the start of the text property of part 146. Another 
circumstance-item will be added to current circumstances (FIG. 16) 
indicating that part 146 was matched by part 120: 
______________________________________ 
Formal-String: "**NO" 
Actual-String: 0 
Actual-Part: part 120 
Actual-Context: C2 
______________________________________ 
Similarly, parts 147, 148 and will match parts 119, 121, generating a 
circumstance-item indicating that part 148 was matched by part 121: 
______________________________________ 
Formal-String: "**YES" 
Actual-String: 0 
Actual-Part: part 121 
Actual-Context: C1 
______________________________________ 
Note that circumstance-items need not be generated for simple, literal 
matches such as that between part 147 and part 119. 
54. The reason that parts 141-144 and 130, 129 match is a bit more complex. 
In this case, parts 141 and 130 match. Connectors 130-136 are all examples 
of connectors which are routed from source to target via a right angle at 
their mid-point; where the arrowhead is positioned. Since these connectors 
emanate from the same source part (part 129), they are each initially 
routed downward from their source. Thus, their downward paths overlap and 
don't diverge until each connector's midpoint. (These connectors could be 
re-drawn as separate, curved connectors. However, the routing of a 
connector is not a property involved in comparison in this example.) The 
question now is how can part 129 be considered as a match for parts 
142-144? Part of the answer is that this match is valid only under present 
circumstances. 
55. When connector 130 is matched with part 141 as part of the cluster 
matching process, get-parts-logic is invoked in order to form the 
candidates.sub.-- list and candidate.sub.-- grandchildren lists used as 
part of the recursive matching process. As described in logic step 
1.3.4.C, both the source and target properties of connector 130 will be 
examined. If the text property of the part referenced by a connector's 
source or target property does not begin with "**" (the usual case), then 
this part itself is added to the list being built by get-parts-logic. 
However, according to step 1.3.4.C, whenever such text does start with 
"**", additional work is performed. Connector 130's source property points 
at part 129 whose text property starts with "**". So, at step 1.3.4.C in 
get-parts-logic, when part 129 is being examined to see if it should be 
added to the list, it will be noticed that its text starts with "**" and a 
part-substitution will be performed. 
56. Part-substitution for part 129 is performed by searching the 
circumstances data structure for the most recent circumstance-item whose 
formal-string field is "**details", the text of part 129. In this case, 
the circumstance-item found is the one built in step 36. As described in 
step 1.3.4.C, the part referenced by the actual-part field of this 
circumstance-item will be added to the list build by get-parts-logic 
instead of part 129. The substituted part is part 108. The result of this 
substitution is as if part 108 was connector 130's source instead of part 
129. (But also note that this effect is a consequence of the current state 
of the circumstances data structure. If a different part had been matched 
back in step 36, a different part would be substituted now.) 
57. So, as a result, the recursive match attempt actually continues by 
attempting to match clusters (142-144) and (108-116). Clearly a match-up 
can be made: 142 & 108, 143 & 113 and 144 & 114. An additional 
circumstance-item will also be added to the current circumstances data 
structure as a result of the match-up of parts 144 & 114: 
______________________________________ 
Formal-String: "*subject" 
Actual-String: "draft-product-spec" 
Actual-Part: 0 
Actual-Context: C1 
______________________________________ 
58. The remainder of this successful match will be conducted as before, 
finally causing another instance of the meaning analysis process to be 
created in order to evaluate the definition-cluster (whose primary part is 
part 149) that is associated with the meaning given in FIG. 10 (meaning 
A). (Note that this new instance of meaning analysis will operate in 
context C1 because the text property of the meaning triangle is "C1". Once 
this instance of meaning analysis has finished, control will be returned 
to the previous instance which was operating in context C2.) 
59. At this point, it should be clear how the matching process operates and 
adds circumstance-items to the circumstances data structure for the 
various kinds of matches that can occur involving text properties 
containing words starting with "*" and "**". Relying on this 
understanding, it can be seen that connector 149 will have no effect other 
than to bring us to box 150 and the cluster (150-156). 
60. This cluster will match the meaning-template shown in FIG. 11A as parts 
(160-166). The pairing of parts 150 and 160 in this match illustrates the 
handling of a single "*" in a text property within a candidate-cluster. As 
in the case of "**", a substitution is made but it is a textual 
substitution, not a part substitution. Since the circumstances data 
structure contains a circumstance-item which indicates a correspondence 
between the formal-string "*subject" and the actual-string 
"draft-product-spec", the appearance of the string "*subject" in the text 
of part 150 is replaced by "draft-product-spec". This, in turn, gets 
associated with the text "*subject" where it appears in part 160. This 
match-up will lead to the generation of another circumstance-item: 
______________________________________ 
Formal-String: "*subject" 
Actual-String: "draft-product-spec" 
Actual-Part: 0 
Actual-Context: C1 
______________________________________ 
The net effect of this is that the original string "draft-product-spec" 
from part 114 is propagated through a correspondence with the string 
"*subject" as it appears in part 144 and then part 150 and later in part 
160. (Note that the original Actual-Context field is maintained despite 
the fact that meaning analysis has switched from context C1 to context C2 
and then back again.) 
61. After parts 150 and 160 are matched, cluster-match-logic will generate 
a candidates.sub.-- list consisting of parts 151, 153 and 154 and a 
meanings.sub.-- list consisting of parts 161, 163 and 165 which will be 
given to recursive-match-logic to see if matches for all the parts in the 
meanings.sub.-- list can be found. The logic flow through 
recursive-match-logic has been described before. But considering the 
handling of part 151, for instance, it will be found to match-up only with 
part 163. This will cause a new instance of recursive-match-logic to be 
activated on a candidates.sub.-- list consisting only of part 152 and a 
meanings.sub.-- list consisting only of part 164. When match-text-logic is 
applied to these parts, it will recognize that both the m-part and c-part 
have text properties which start with "**". As described in logic step 
1.3.2.A, a new circumstance-item will be constructed in which the 
"actual-" fields are copied over from the circumstance-item built in step 
53. The new circumstance-item will be: 
______________________________________ 
Formal-String: "**YES" 
Actual-String: 0 
Actual-Part: part 121 
Actual-Context: C2 
______________________________________ 
This instance of recursive-match-logic will quit and return to the 
previous one which will continue by attempting to match-up the remaining 
parts (parts 161 and 165 on the meanings side, and parts 153 and 154 on 
the candidate side). Matches will be found here as well. Parts 153 and 161 
will match, adding nothing to current circumstances, but causing another 
invocation of recursive-match-logic to examine 155 and 162. These will 
match in the same way as parts 151 and 163. The following 
circumstance-item will result: 
______________________________________ 
Formal-String: "**NO" 
Actual-String: 0 
Actual-Part: part 120 
Actual-Context: C1 
______________________________________ 
Similarly, parts 154 and 165 will match, leading to a match between parts 
156 and 166. This last match will produce the following circumstance-item: 
______________________________________ 
Formal-String: "*item" 
Actual-String: "me" 
Actual-Part: 0 
Actual-Context: C1 
______________________________________ 
62. After a new instance of meaning analysis is applied to part 168 and it 
is found that there is no meaning that matches, primitive-action-logic is 
then applied to this part. 
63. The primitive-action-logic chosen for this example is very simple in 
operation. The text property of the part being processed is examined, 
word-by-word. (Here a word is any group of characters not including a 
space.) If a word does not start with a "*", it is simply copied to the 
output file. If a word starts with a "*", the current circumstances are 
searched for the most recent circumstance-item whose formal-string field 
matches the word. If the circumstance-item so found has a non-zero 
actual-string field, a string substitution is performed by copying the 
actual-string into the output file in place of the word. This sort of 
action execution, applied to part 168, results in the following output: 
if (draft-product-spec reasonable for me) { in which the string "*subject" 
has been replaced by "draft-product-spec" and the string "*item" has been 
replaced by "me". 
64. Since the character "{" of the text property of part 168 is followed by 
the word "**YES", primitive-action-logic will search for the most recent 
circumstance-item whose formal-string is "**YES". Since, the actual-string 
field of this item is zero, and the actual-part field of the 
circumstance-item is non-zero, the part referenced by the actual-part 
field is subjected to meaning analysis. In this case, it is part 121. 
Further processing of part 168 is suspended while part 121 is fully 
processed. A new instance of meaning analysis is created and part 121 is 
treated as the primary-part of a definition-cluster to be evaluated in the 
context specified by the actual-context field of the circumstance-item (in 
this case, context C2). In this case, the result is the processing of the 
remainder of FIG. 9A that flows from part 121. Whatever output is to be 
generated as a result of this new instance of meaning analysis will appear 
in the output file at this point. (This is discussed more fully in step 
65, below.) Once this part (and surrounding clusters) has been fully 
processed, this new meaning analysis instance concludes and returns to the 
one whose processing of part 168 was suspended. Any additional 
circumstance-items created during meaning analysis of part 121 are deleted 
from the circumstances data structure when this instance terminates. 
Primitive-action-logic's processing of part 168 will continue with what 
follows the word "**YES", giving: 
______________________________________ 
} 
else { 
______________________________________ 
followed by any output resulting from the word "**NO" which, in turn, is 
followed by a closing "}". When the word "**NO" is evaluated, the 
circumstances data structure will be the same as it was when "**YES" was 
evaluated (since any items added during "**YES" evaluation would have been 
removed). The evaluation of "**NO" and the closing "}" will actually 
produce the last lines of output generated by this example (see the full 
output listing following step 69). 
65. But returning to the processing of "**YES" in part 168, the cluster at 
121 will be evaluated in context C2 and will, therefore, be matched by the 
meaning-template at part 170 in FIG. 10. (Note that there would be no 
match for part 121 if it were evaluated in context C1). The word 
"*participants" in this cluster will be associated with the string "the 
planning group" (which appears as the text property of part 110 in FIG. 
9B). Similarly, the word "*subject" will again be associated with 
"draft-product-spec". 
66. The definition-cluster shown in FIG. 10 (meaning B) will be evaluated 
in context C1. (Note the text property of the triangle.) When the cluster 
at 171 is evaluated, it will not be matched by the meaning-template at 160 
because of the different directional orientation of parts 165 and 172. 
67. Looking more closely, it is observed that this means that part 171 has 
two source-of properties (referencing parts 173 and 174) and a target-of 
property that references part 172 while part 160 has three source-of 
properties (referencing parts 161, 163 and 165). 
68. So, even though their other properties match, these differences are 
enough to prevent parts 171 and 160 being considered as a match. Since 
these do not match, other matches will be attempted. Ultimately, it will 
be found that the candidate-cluster at part 171 does match the 
meaning-template at part 180) in FIG. 11B. 
69. The definition-cluster starting at 181 will then be evaluated. Meaning 
analysis is applied to this cluster and various matches will be made with 
meaning-templates appearing in FIG. 12A-E. It is worth noting that when 
part 182 becomes the candidate-part, it will be matched by part 160 
instead of part 180 because of the direction of the dashed-connector. 
Output 
The following is the output code generated by the invention as a result of 
processing the diagrams in the set of FIGS. 9A through 12E: 
______________________________________ 
start 
if (draft-product-spec reasonable for me) { 
make temporary lists { 
appropriate-list ; 
inappropriate-list }; 
while ( the planning group has more individual s) { 
examine next individual ; 
if ( draft-product-spec reasonable for individual ) { 
put this particular individual 
at the end of the " appropriate-list "; 
else { 
put this particular individual 
at the end of the " inappropriate-list "; 
} 
} 
if ( appropriate-list matches the planning group ) { 
if (time and place are ok) { 
accept request 
} 
else { 
propose alternate time and place. 
} 
} 
else { 
propose alternate participants. 
} 
} 
else { 
decline request 
} 
______________________________________ 
This output takes a form familiar to many computer software professionals: 
a highly-readable, pseudo-code patterned after a popular programming 
language called C. Since similar textual forms are routinely used to 
define programs which can be executed on general purpose computer systems, 
this form of output is taken to be, in effect, equivalent to machine 
execution. The primary difference between such pseudo-code actual source 
code in the C language is a line such as: 
______________________________________ 
if ( draft-product-spec reasonable for me ) { 
might appear as: 
if (reasonable("draft-product-spec", "me") { 
______________________________________ 
This latter would be appropriate given that elsewhere in the program a 
boolean function named "reasonable " is defined to accept two string 
arguments. The job of such a function would be to search a database (or a 
similar collection of data) for a correspondence between a subject whose 
name matched the first string and an individual whose name can be deduced 
from the second string and to return a boolean result of TRUE if such a 
correspondence is found or a boolean result of FALSE if it is not. The 
effect of this line in the program would thus be to perform a conditional 
branch based on whether or not the function reasonable returned a TRUE or 
a FALSE result. The point of using pseudo-code is to avoid the lengthy and 
tedious presentation of details whose construction can be reasonably 
considered to be feasible and whose function can be expressed in a short 
phrase. 
In summary then: (1) since it is known that the machine-language form of a 
program is executable on suitable hardware, and (2) it is known that the 
source-language form of a program can be converted into a machine-language 
form, and (3) this example illustrates that the source-language form of a 
program could be generated from a set of diagrams, therefore (4) this 
example illustrates a method of executing a set of diagrams. 
So far, this example has served to illustrate the operation of the basic 
mechanisms of the invention. A further point is to demonstrate how systems 
built along these lines may be altered or adapted in ways not easily done 
using conventional techniques. 
The FIGS. 9A through 12E have some additional characteristics. FIGS. 9A and 
B express, at the highest level, the desired behavior of the system. FIG. 
9A represents the highest level of meaning given to the concept "handle a 
request for a meeting". (FIG. 9B should be seen only as test-case used to 
explore the operation of the meaning in FIG. 9A for the purposes of this 
example.) The diagrams shown in FIG. 10 are transition diagrams, 
referenced from FIG. 9A above and making references to meanings below them 
in FIGS. 11A through 12E which represent the lower-level meanings or 
concepts in the system. This hierarchial view can be seen in FIG. 13 which 
shows only the primary-parts of the meaning-templates which appear in each 
of the previous figures. This layering of the levels-of-abstraction in a 
system is typical of modern-day systems design. 
What is of interest is the situation in which it is desired to alter such a 
hierarchial system. The logical flow captured in FIG. 9A, in combination 
with the meanings given in FIG. 10, has the characteristic of causing a 
request to be immediately declined as soon as the subject is judged not 
appropriate. Consider the user who would like to give consideration to the 
meeting participants prior to declining a request. As always, there are 
many ways in which the system could be modified to meet this new 
requirement. An approach that is uniquely supported by the invention is 
the following: 
The definition-cluster given in FIG. 9A could have different significance 
if evaluated in a different context. The evaluation context is determined 
by the text property of the meaning-triangle, part 103b. If the text in 
this triangle was changed to "C3", the meanings given in FIG. 10 would not 
be involved (since these meanings only appear in the meanings-list of 
context C2). Instead, the meaning given in FIG. 14 would be considered 
because it is on the meanings-list of context C3. The meaning-template 
starting with part 190 has been constructed so that it will match a larger 
candidate-cluster around part 117 in FIG. 9A. Specifically, FIG. 14 will 
do in one match what FIG. 10 did in two. Note that both parts 117 and 121 
will be included in the new match: part 117 will pair with 190 and part 
121 will pair with 191. Once this match has been made, the 
definition-cluster in FIG. 14 will be evaluated and meanings in FIGS. 11A 
and B and 12A-E will be activated. 
The following is the output generated as a result of processing the 
diagrams in FIGS. 9A and B, 14, and 11A through 12E according to the 
invention: 
______________________________________ 
start 
if (my boss is in " the planning group ") { 
if (time and place are ok) { 
accept request 
else { 
propose alternate time and place. 
} 
} 
else { 
make temporary lists { 
appropriate-list ; 
inappropriate-list }; 
while ( the planning group has more individual s) { 
examine next individual ; 
if ( draft-product-spec reasonable for individual ) { 
put this particular individual 
at the end of the " appropriate-list "; 
} 
else { 
put this particular individual 
at the end of the " inappropriate-list "; 
} 
} 
if ( appropriate-list matches the planning group ) { 
if (time and place are ok) { 
accept request } 
else { 
propose alternate time and place. } 
} 
else { 
decline request 
} 
______________________________________ 
In the first case, the case involving FIGS. 9A through 12E, the cluster of 
parts (117-121, and 129-132) were interpreted as two distinct operations, 
one following the other: "appropriate subject for me?" and "appropriate 
participants?". 
In the second case, in which FIG. 10 was replaced by FIG. 14, essentially 
the same cluster of parts (117-121, and 129-131) was interpreted as a 
single operation, whose meaning was then free to diverge totally from the 
significance of the meanings used in FIGS. 10 A and B. In particular, the 
definition-cluster in FIG. 14 makes reference to "*participants" before 
referencing the "*subject". 
Logic Descriptions 
Following are descriptions of meaning analysis logic components as needed 
to execute the example discussed above. Each description includes a 
narrative step-through of the logic function; most descriptions are 
followed by a code illustration of the logic or a reference to an appendix 
containing a code illustration. 
1.1 Part-Selection-Logic 
1.1.1. First-part-logic: If activated for the first time, search the 
diagram-set for a part whose text is "start" and identify this part as the 
first-part. Otherwise a definition-cluster is being evaluated, so identify 
the primary-part of the definition-cluster as the first-part. 
______________________________________ 
if meaning.sub.-- pointer is null then /* first-time */ 
result = find("start", BE); 
else result = 
meaning.sub.-- pointer.definition.sub.-- cluster.primary.sub.-- part; 
return result; 
______________________________________ 
1.1.2. Next-part-logic: take a part from the working-pool. If the part is a 
dashed-connector, ignore it and take another part from the working-pool. 
Once a box or a solid-connector has been taken, see if the part has 
previously been matched in this instance of meaning analysis. If the part 
has already been matched, ignore it and take another part from the 
working-pool. Once a part has been taken which has not yet been matched, 
identify this part as the next-part. If the working-pool is exhausted 
before a next-part can be identified, conclude this instance of the 
meaning analysis process. 
______________________________________ 
loop { 
if working.sub.-- pool is empty then terminate MA.sub.-- process; 
candidate.sub.-- part = remove(working.sub.-- pool); 
if candidate.sub.-- part is in 
this.sub.-- context.already.sub.-- matched.sub.-- list then 
continue; /* loop back to try another part */ 
until (candidate.sub.-- part.style is solid or 
candidate.sub.-- part.type is box); 
return candidate.sub.-- part; 
______________________________________ 
1.2 Meaning-Selection-Logic 
1.2.1. First-meaning-logic: identify as first-meaning the first item in the 
simple list structure that is the context's meanings-list. Make use of a 
location in working storage that can be used to advance through the 
current meanings-list. This location must be able to record the last item 
in the list that has been referenced by meaning-selection-logic while 
processing this candidate-part in this instance of meaning analysis. 
Initialize this location to refer to the first meaning in the list. 
______________________________________ 
this.sub.-- context.curr.sub.-- meaning = 
head.sub.-- of(this.sub.-- context.meanings.sub.-- list); 
______________________________________ 
1.2.2. Next-meaning-logic: identify as next-meaning the item in the 
meanings-list which follows the one identified by the location created 
above. Update this location. 
______________________________________ 
this.sub.-- context.curr.sub.-- meaning = 
this.sub.-- context.curr.sub.-- meaning.next.sub.-- meaning; 
______________________________________ 
1.3 Cluster-Match-Loop-Logic 
1.3.1. Cluster-match-logic: This logic is given a reference to the 
primary-part of a meaning-template and a reference to the current 
candidate-part. Invoke the match-parts-logic to check for a match between 
the meaning and candidate parts in the current context. If these two parts 
do NOT match, invoke the get-parts-logic on the candidate part and return 
the resulting boundary-list along with a report that no match exists. If 
these parts match, invoke the get-parts-logic to build a "candidate.sub.-- 
list" consisting of parts referenced by the candidate, excluding parts 
previously matched in this instance of meaning analysis. Mark the meaning 
and candidate parts as already-matched in this instance of meaning 
analysis. Invoke the get-parts-logic to build a "meanings.sub.-- list" 
consisting of parts referenced by the meaning part. Invoke the 
recursive-match-logic to see if each part in the meanings.sub.-- list has 
a corresponding part in the candidate.sub.-- list. If the 
recursive-match-logic reports a match, exit and report a MATCH and return 
a "boundary.sub.-- list" of un-matched parts. If a match is not indicated, 
exit and report NO MATCH. Appendix A contains a pseudo-code representation 
for cluster-match-logic. 
1.3.2. Match-parts-logic: compare the properties of two parts and report if 
they match. The part from the candidate-cluster will be referred to as the 
"c-part" and the part from the meaning-template will be referred to as the 
"m-part". Two parts match if (1) their type and style properties are the 
same, (2) their directional characteristics are the same and (3) their 
text properties can be said to match. While parts (in this example) don't 
have directional properties, their directional characteristics are 
considered the same if the parts are boxes or when the parts are 
connectors with the same source/target orientation. The following 
procedure is used to determine if two text properties match: 
A. The text property of the m-part is examined to see if it starts with 
"**" (double asterisks). If it does not, proceed with step B. If the text 
of the m-part does start with two "*"s, the text properties are considered 
to match and a circumstance-item is constructed and added to the current 
circumstances. Before this new circumstance-item can be built, it is 
determined whether or not the text of the c-part starts with a "*". If so, 
the circumstances data structure is searched for the most recent 
circumstance-item whose formal-string field matches the text property of 
the c-part. The actual-string, actual-part and actual-context fields of 
this circumstance-item are copied into the corresponding fields in the new 
circumstance-item. The formal-string field of this new item is then set 
equal to the text property of the m-part. In addition, this match is 
marked as a special-case match and match-parts-logic returns control to 
the logic element which activated it. 
B. (Performed only if the text of the m-part does not start with "**") the 
text property of the c-part is copied into an area of working storage and 
named the "candidate string". Similarly, the text property of the m-part 
is copied into an area of working storage and named the "meaning string". 
If these two are identical, they match; 
C. If there are words in the candidate string which start with "*" each 
such word must be replace by a string of substitute-text. The current 
circumstances are searched for the most recent circumstance-item which 
contains the word in question. If no such item is found, a textual match 
is not possible. If such an item is found, the text string stored in this 
item replaces the word in the candidate string. 
D. Once the substitution of words beginning with "*" in the candidate 
string has been completed, a match is considered to exist if the strings 
are identical except for words in the candidate string which can be 
matched with words in the meaning string starting with "*". Note that when 
such associations are made, any number of words in the candidate string 
may be associated with a single word (starting with "*") in the meaning 
string. For each such association made, a circumstance-item is 
constructed. Every circumstance-item has the following structure: 
______________________________________ 
Formal-String: 
&lt;the text of the meaning token&gt; 
Actual-String: 
&lt;the associated string, if any&gt; 
Actual-Part: 
&lt;the associated part, if any&gt; 
Actual-Context: 
&lt;the context in which the match occurred&gt; 
______________________________________ 
When the meaning token starts with a single "*", a string association is 
made and the actual-string field of the circumstance-item contains the 
matching string from the c-part and the actual-part field is empty. When 
the meaning token starts with a double "*", a part association is made and 
the actual-part field of the circumstance-item contains a pointer to the 
matching c-part and the actual-string field is empty. Appendix B contains 
a pseudo-code representation for match-parts-logic. 
1.3.3. Recursive-match-logic: compares a meanings.sub.-- list with a 
candidate.sub.-- list as follows: 
A. examine each possible pairing of an m-part from the meanings.sub.-- list 
and a c-part from the candidate list. 
B. for each paring proceed with step C. 
C. apply the get-parts-logic to the m-part to build a list of 
"meaning.sub.-- grandchildren", 
D. invoke match-parts-logic on the m-part and c-part to see if they match, 
E. if they DO NOT match, put the c-part on a list of unmatched c-parts, 
pick another c-part and continue with step D. (If all c-parts have been 
examined, a match is not possible--exit this invocation of 
recursive-match-logic, reporting NO MATCH). If step D resulted in a 
special match, continue processing with step H. Otherwise, step D must 
have resulted in an ordinary match, so apply the get-parts-logic to the 
c-part in order to build a list of "candidate.sub.-- grandchildren". 
F. if the list of meaning.sub.-- grandchildren is not empty, invoke the 
recursive-match-logic on the meaning.sub.-- grandchildren and 
candidate.sub.-- grandchildren lists and save the boundary.sub.-- list 
that was generated. If the list of meaning.sub.-- grandchildren is empty, 
apply the get-parts-logic to the c-part in order to build a 
boundary.sub.-- list. Exclude dashed-connectors from this list. 
G. add any parts in the boundary.sub.-- list build in step F to the 
result.sub.-- list being maintained for this invocation of the 
recursive-match-logic. 
H. move all parts in the list of unmatched c-parts back onto the 
candidate.sub.-- list (this will allow them to be paired with other parts 
from the meanings.sub.-- list). Advance to the next pair of m-parts and 
c-parts, and continue with step C. When all m-parts have been matched, 
continue with step I. 
I. add any c-parts that remain on the candidate.sub.-- list to the 
result.sub.-- list except for: (i) any dashed-connectors or (ii) 
solid-connectors whose target property references a part in the 
candidate-cluster explored so far. 
J. exit, report a MATCH, and return the result.sub.-- list as the 
boundary.sub.-- list computed by this invocation of recursive-match-logic. 
Appendix C contains a pseudo-code representation for 
Recursive-match-logic. 
1.3.4. Get-parts-logic: build a list of parts which are referenced by a 
given part, subject to given constraints. The list is built via the 
following procedure: 
A. loop through the properties of the given part. 
B. for each source-of or target-of property, examine the referenced 
connector. If it is a solid-connector or if the given constraints permit 
any style of connector, then add this connector to the list. 
C. for each source or target property, examine the referenced part. If the 
given constraints permit, examine the text property of the part. If the 
text starts with a word that begins with two "*"s, search the current 
circumstances for the most recent circumstance-item containing this word. 
Add to the list the part that is associated with this word in the 
circumstance-item (this how a part-substitution is performed). If the text 
does not start with two "*"s, add the part to the list. 
D. examine each part that has been added to the list and eliminate any part 
which has already been matched in this instance of meaning analysis. 
E. exit, returning the list as the result of the get-parts-logic. Appendix 
D contains a pseudo-code representation for Get-parts-logic. 
1.3.5. Match-loop-control-logic:process a new result-item each time through 
the cluster-match-loop. There are two cases: (1) when the result-item 
indicates failure, and (2) when the result-item indicates success. In the 
first case, when the result-item indicates failure, the next-meaning-logic 
is activated to see if there are more matches to be attempted. If another 
meaning is found, match-loop-control-logic returns to meaning analysis. If 
all meanings have been tried and no match has been found, activate the 
primitive-action-logic for the candidate-part. Once the 
primitive-action-logic has finished, it returns to 
match-loop-control-logic who copies the boundary-list from the result-item 
into the working-pool (doing this in a way which ensures that there are no 
duplicates). Finally, all circumstance-items built during the unsuccessful 
match attempt are discarded, and the match-loop-control-logic returns to 
meaning analysis with an indication that all meanings have been examined. 
If, in the second case, a result-item indicates success, the 
definition-cluster associated with the matched meaning will be immediately 
analyzed by a new instance of meaning analysis. Once this separate 
instance of meaning analysis has concluded, it returns here to 
match-loop-control-logic who now (1) copies the boundary-list from the 
result-item into the working-pool (ensuring no duplicates), (2) discards 
all circumstance-items built during the (successful) match just processed, 
(3) marks the current candidate part as having been matched in this 
instance of meaning analysis and (4) returns to meaning analysis with an 
indication that the match-loop is finished with the current 
candidate-part. 
1.4 Primitive-Action-Logic 
The text property of the part subjected to primitive-action-logic is 
examined, word-by-word. If a word does not start with a "*", it is simply 
copied to an output file If a word starts with a "*" the circumstances 
data structure is accessed for information associated with the word. If 
there is only one "*" at the start of the word, a textual substitution is 
made and the substitute text is copied to the output file. If the word 
begins with "**", the part associated with the word (via a 
circumstance-item stored in the current circumstances) is subjected to 
meaning analysis. Once this part has been fully processed, the 
primitive-action-logic continues processing with the word following the 
one beginning with "**". 
Best Mode 
The best mode of the invention is executed on a commercially available 
IBM/PC-compatible microcomputer and makes use of the following 
commercially available software products: 
1. The "Microsoft MS-DOS" operating system, version 3.3 from Microsoft 
Corporation, One Microsoft Way, Redmond, Wash. 98052-6399. 
2. The Microsoft Windows graphical Environment, version 3.0, also available 
from Microsoft Corp. 
3. The "Microsoft System Development Kit for Windows"; also from Microsoft. 
4. "Borland C++" and its associated windows libraries, object files, and 
Dynamic Link Libraries (DLLs) from Borland International, Inc., 1800 Green 
Hills Road, Scotts Valley, Calif. 95067-0001. 
5. The "TIER C++ Class Library for MS-Windows" and its associated object 
files and DLLs from Sturmer Hauss Corp. 685 W. Long St., Stephenville, 
Tex. 76401. 
System Decomposition into "Files" 
Clearly, systems constructed according to the invention have the potential 
to incorporate a very large number of individual parts. As a practical 
expedient, the current embodiment allows the collection of parts which 
make up a single system to be decomposed into a number of individual 
"files" (as defined by the MS-DOS operating system). The most fundamental 
type of file used by the prototype is known as a "rendition" or "rendition 
file". A rendition file is a collection of individual parts. Concurrently, 
the embodiment's diagram editor (also called the "rendition editor") 
permits only one file at a time to be edited. Another type of file known 
as a "library file" can be used to group together one or more other files 
in order to provide for more convenient file management. A library file 
can make reference to other library files as well as to rendition files. 
At the basic conceptual level, the decomposition of a large system into 
separate library and rendition files has little significance other than to 
limit the scope of diagram editing and to impose a restriction on the 
specification of contexts. This restriction has to do with the way that 
contexts other than the default context are diagrammatically defined. In 
the current embodiment, a default (or global) context is presumed to exist 
despite the fact that the user has not constructed a part to represent the 
default context. This context represents a special case because, in 
effect, every other part in a system is considered to be encompassed by 
this default context. The diagram editor permits the user to create 
additional contexts by drawing a solid, bold rectangular box. Meaning 
triangles placed within such a solid, bold box are deemed to be meanings 
contained within the context associated with the box. This approach has 
the effect of limiting all contexts other than the default context, to the 
file in which the box that represents the context appears. This limitation 
is largely mitigated by the "::import" facility that was described in the 
example. This facility makes use of the text property of a context (or 
rather the solid, bold box that represents a context) to specify: 
1. A Name: which is the textual identifier associated with the context; and 
2. An Import-List: which is a list of the identifiers of other contexts 
whose meaning-lists are to be added to this context's meaning-list. 
An alternate means of specifying a context-switch 
The example has described a means of specifying the definition-context 
component for a meaning. In the example, the text property of the 
meaning-triangle is used to specify the name of the context that is to be 
used as the definition-context. The sole purpose of a meaning's 
definition-context component is to identify the context that will be used 
by the meaning analysis procedure when evaluating the individual parts 
which make up the definition-cluster. The definition-context field is one 
way to provide the system with the ability to perform a "context-switch". 
Using this method, a context-switch is permitted whenever a new instance 
of the meaning analysis process is created. An alternative, and somewhat 
more general, method of providing the ability to change contexts can be 
achieved by adding this capability to one or more of the 
primitive-action-logic components used within a system. The existing 
embodiment uses such a technique. Specifically, the primitive-action-logic 
component of every context can recognize a text property of "::set.sub.-- 
context". Whenever primitive-action-logic is applied to a part whose text 
property equals "::set.sub.-- context" the system will switch to the 
smallest context which encloses this part. Note that only contexts which 
occur in the same file as the ::set.sub.-- context part are considered 
here. If a ::set.sub.-- context is encountered for which no explicitly 
enclosing context can be found, the global (or default) context is 
selected and a switch to this context occurs. One consequence of this 
approach is that the definition-context field of the meaning data 
structure is not required. Instead, the job of specifying a new context is 
left to the definition-cluster itself. While this is more burdensome and 
tedious to describe, it might be considered more flexible because it 
permits a single definition-cluster to switch to more than one context in 
the course of its evaluation. 
Optimization: Storing Match Information 
There are many opportunities to apply techniques which are well-known to 
computer science and whose application can result in significant 
improvements in the operational efficiency of the invention. One class of 
improvement involves generating supplemental information during the 
meaning analysis process and storing it for later use. An example of this 
class of improvement is implemented in the current embodiment. The basic 
approach is to store extra information with each part that has been 
evaluated as "current candidate-part" and subjected to cluster matching. 
This extra information is stored in such a way that it can be retrieved 
the next time the part becomes the current candidate-part. The information 
is then used to eliminate or reduce the search-time associated with 
finding the meaning or meanings which can be said to match this 
candidate-part. The embodiment calculates this information when it has 
finished processing a given candidate-part. It stores with this part 
additional properties which indicate whether or not a match occurred and, 
if so, what meaning was matched and in what context. The next time this 
part becomes the current candidate-part, these properties are accessed by 
the meaning analysis process prior to entering the match-loop and, in many 
cases, can be used to eliminate (or at least reduce) the cluster-matching 
that would otherwise need to occur. There are a variety of sophisticated 
compiler optimization techniques, for example, which can be readily 
applied to the invention. 
Optimization: Storing Primitive-Action Information 
Another type of optimization is based on the observation that systems will 
often be constructed in such a way that there are certain 
candidate-clusters which are repeatedly evaluated in the same context and 
in light of the same circumstances. There is a certain degree of 
processing required to discover all of the primitive-actions which will be 
executed as a result of a full meaning analysis of a given 
candidate-cluster. There are cases in which it is possible to avoid 
repetitive meaning analysis processing by storing a representation of the 
sequence of primitive-actions which result from a previous analysis. Such 
cases would be recognizable to an experienced compiler writer. In general, 
a sequence of primitive-actions can be stored as a property of the primary 
part of the candidate-cluster which generated that sequence. The next time 
this part becomes the current candidate-part, this sequence of 
primitive-actions can be executed instead of repeating the full meaning 
analysis. This should be thought of as an optimization because its purpose 
is not to alter the flow of primitive-actions performed by a system, but, 
rather to eliminate unnecessary and time-consuming processing. It should 
be noted that proper implementation of this optimization is not as easy as 
it sounds because, for example, it is possible that a match between a 
given candidate-cluster and a given meaning-template might depend upon the 
state of the circumstances data structure at the time that the match 
occurs. If this were to be the case, the sequence of stored 
primitive-actions might not be valid for a later match that took place 
under different conditions. A catalog of "match-dependencies" can be 
constructed by carefully considering the various situations under which 
circumstance-items are constructed and exactly how they contribute to a 
successful match. Given such a catalog for any particular implementation, 
one can analyze any particular match and determine its specific 
dependencies. The building of such "dependency graphs" is familiar to 
compiler writers. In many cases, it may be less costly to test for such 
dependencies than to unconditionally re-attempt the match. If the 
conditions upon which a previous match depended still exist, then the 
previously executed primitive-actions can be re-executed. If conditions 
have changed, it may be possible to appropriately modify the list of 
previously executed primitive-actions or it may be necessary to reattempt 
the match. 
Optimization: Storing Version Information 
The existing embodiment keeps track of a "version number" for each part, 
file and reference. This version information facilitates the 
implementation of the optimizations discussed above. When certain changes 
occur in a part, for example, its version number is increased. This 
permits the system to notice during later processing that a reference 
exists to a previous version of a part. When such an outdated reference is 
noted, the system can follow the appropriate dependency relationships and 
update stored relationships as may be necessary as a consequence of a 
particular change. 
Diagram Editor 
The example makes use of a specialized diagram editor. This editor is a 
Microsoft Windows application and is built in Borland C++ using the 
associated windows libraries, objects, and dynamic link libraries (DLLs) 
along with the TIER C++ class library, objects and DLLs for Windows and 
the Microsoft System Development Kit for Windows. The basic framework for 
this application can be derived from the example overlapped windows 
provided with the TIER system or one could also create the application 
framework utilizing a text such as "Programming Windows: the Microsoft 
Guide to Writing Applications for Windows 3" by Charles Petzold. Like the 
examples provided in these products, the editor takes advantage of the 
capabilities that Microsoft Windows system affords. Microsoft Windows 
monitors both the mouse and keyboard devices (Windows can monitor many 
different input and output devices, these two devices are used as 
examples). When Windows determines that the user has made a request by 
interacting with either of these devices, the Windows system will inform 
the diagram editor. Windows can also make specific system requests. 
The diagram editor operates on the messages or requests that are made of 
it. A user driver request might be to create a part, to create a 
relationship between two parts or to store the representation of an entire 
diagram on disk. In the following descriptions, Appendix E Diagram Editor 
Pseudo Code is referenced by line number. Note that like the pseudo code, 
the terms shape and part are used interchangeably. Using rectangular part 
creation as an example, this is how the system would behave: 
1. The user types the character "R" on the keyboard. 
2. The Windows system notices a keystroke event and sends a message to the 
diagram editor informing the editor of the event (character "R" has been 
struck). 
3. The editor's message loop receives the WM.sub.-- KEYUP message for an 
"R" and passes the information to its function Interp.sub.-- Keystroke 
(lines 404-406). Interp.sub.-- Keystroke would then post a message to the 
message loop instructing the message loop to prepare for the creation of a 
rectangle (lines 873-879). The message loop processes this information by 
changing the editor's state variable to State.sub.-- Start.sub.-- 
Create.sub.-- Rectangle (lines 450-452). 
4. The user positions the mouse cursor where he wants the left upper corner 
of the rectangle to be and then presses the left mouse button down. 
5. The Windows system notices a mouse event and sends a message to the 
diagram editor informing the editor of the event (left mouse button down 
at a particular coordinate on the screen). 
6. The message loop receives the WM.sub.-- LBUTTONDOWN message at the 
particular coordinate of the mouse down and passes the information to its 
function Interp.sub.-- Left.sub.-- Click (lines 412-414). Due to the state 
of the editor, start the creation of a rectangle, Interp.sub.-- 
Left.sub.-- Click will send the message loop an ID.sub.-- RECTANGLE.sub.-- 
CR message with the current mouse position (lines 795-798). The message 
loop will allocate a new rectangle object in memory--this will call the 
rectangle's constructor which will initialize the rectangle's draw pens, 
the shape tag, the file and shape handles, the center, left upper and 
right lower points and the context flag (lines 201-205)--set the state to 
State.sub.-- Create.sub.-- Rectangle and set the current shape to the 
newly allocated rectangle (lines 454-476). 
7. The user drags the mouse cursor to where he wants the right lower corner 
of the rectangle to be. 
8. The Windows system notices a mouse event and sends a message to the 
diagram editor informing the editor of the event (mouse movement across 
the screen). 
9. The message loop receives the WM.sub.-- MOUSEMOVE message at the 
particular coordinate of the mouse move and passes the information to its 
function Interp.sub.-- Mouse.sub.-- Move (lines 420-422). Interp.sub.-- 
Mouse.sub.-- Move will send the message loop an ID.sub.-- RECTANGLE.sub.-- 
CR with the new mouse position (lines 701-703). The message loop will 
adjust the right lower corner of the rectangle with a call to Move.sub.-- 
To (lines 454-476). Move.sub.-- To will erase the current image that is 
displayed, adjust the center, left upper and right lower points 
appropriately, redraw the image on the screen and notify any properties 
that might be affected by the movement (lines 223-225). 
10. The user may continue to drag the mouse, in which case steps 7, 8, and 
9 will be repeated until the user releases the left mouse button--step 11. 
11. The user releases the mouse left button at the final position of the 
right lower corner (note the right lower corner may truly be any corner of 
the rectangle in the diagram, the two point names are chosen to aid in the 
visualization of the rectangle). 
12. The Windows system notices a mouse event and sends a message to the 
diagram editor informing the editor of the event (left mouse button up). 
13. The message loop receives the WM.sub.-- LBUTTONUP message at the 
particular coordinate of the mouse up and passes the information to its 
function Interp-Left.sub.-- Up (lines 424-426). Due to the state of the 
editor, create a rectangle, Interp.sub.-- Left.sub.-- Up will send the 
message loop an ID..sub.-- RECTANGLE.sub.-- CR message with the current 
mouse position (lines 672-673). The message loop will adjust the rectangle 
as described in step 9 (lines 454-476). Upon return from the sent message, 
Interp.sub.-- Left.sub.-- Up will add the new rectangle to the library and 
update the editors state to shape selected (lines 674-676). The Add.sub.-- 
Ref function will actually place this new rectangle in the display list of 
the appropriate file record, add any new properties to the property list 
of the appropriate file record, assign appropriate persistent file and 
shape handles to the shape and will make sure that any necessary property 
manipulations required by the addition of the new shape are performed 
(lines 259-261). 
14. The editor will then wait in shape selected state for further messages 
to be sent to its message loop. 
From this process, one can see how a triangle would be created. The primary 
difference lies in the fact that three points must be selected (lines 
201-206, 226-227, 477-503, 800-814 and 884-889). Connector creation is 
also quite similar to rectangle creation, but instead of selecting one 
corner location and dragging to the second location, the user simply left 
clicks on first the source shape and then the target shape (lines 505-532, 
781-793 and 854-860). The constructor for the connector calls the base 
constructor just like other shapes, but it is different from the other 
shapes in that the connector itself does not determine its graphical end 
points, the source and the target shape positions force that choice. The 
constructor for the connector takes the source and target shapes as 
parameters (line 207). With this information, the constructor will assign 
these shapes to the appropriate member components, assign the default 
value to the directional component (TRUE), assign the default value to the 
point count component (2) and use the default pen (assigned in the shape 
base class constructor) to create a line image with a directional 
indicator from the center of the source shape to the center of the target 
shape. With the ability to create all of the shapes in memory and display 
them on the screen, it becomes clear that modifications will be required 
to these shapes to support meaningful diagrams. Operations such as 
associating text with a shape--accepting text from the user and then 
associating this text with the selected shape (lines 635-640 and 
867-872)--and modifying the source or target of a connector--allowing the 
user to use the mouse to select a new source or target, updating the 
appropriate source/target component and connection properties and then 
erasing the old connection and drawing the new connection (lines 232-237, 
562-582, and 771-793)--support this effort. There are other modifications 
that can be made, shape sizing and movement, as examples, that are clearly 
described in the pseudo code. 
Once a meaningful set of diagrams has been created in memory, it is only 
practical that the structures representing the diagrams would be written 
and then eventually read from disk (lines 332-341). To perform this 
operation, the data must be transformed from a memory representation to a 
disk representation. All of the disk shape, diagram (rendition file) and 
library data is represented in a format that encapsulates the memory 
structures. The primary difference lies in the references to properties 
and to other shapes. Instead of referencing a shape's machine address, a 
property or shape will reference the persistent handle pair (file handle, 
shape handle). With each shape disk reference, there is also a version 
number stored to assist in the maintenance and correctness of shapes and 
properties. Another difference is that a shape's property list is not 
stored explicitly with the shape. Instead, each property is stored with 
persistent references to its associated shapes. Thus, the property list of 
any shape can be built as each file is read into memory. Since every shape 
and property is stored with the appropriate rendition file, there is no 
difficulty in recreating the appropriate library/file associations. With 
the capability of storing and retrieving all pertinent diagram data, the 
editor can be used to support a host of tools operating on the robust 
diagram data. 
While a preferred embodiment of the invention is described, it should be 
understood that modifications and adaptations thereof will occur to 
persons skilled in the art. Therefore, the protection afforded the 
invention should only be limited in accordance with the scope of the 
following claims. 
##SPC1##