US 20070050180 A1
Disclosed herein are techniques for generating textual descriptions of a graphic model and vice-versa. The techniques may be used, for example, in conjunction with a scheme that models objects and processes as independent entities. The techniques have a wide variety of applications including automatic code generation, system simulation, and language translation.
35. A computer-implemented method of architecting, engineering, lifecycle support and/or modeling of a system, the method comprising:
receiving an input specifying textually requirements of the system;
modeling the system using meta-libraries containing metamodels for domain-specific artifacts as templates for standardized design;
linking the requirements to elements of a model of the system;
receiving feedback on coverage of the requirements by the model;
simulating the model of the system qualitatively and quantitatively;
modeling one or more tests for accepting the system;
automatically generating one or more test scripts related to said one or more tests;
feeding one or more test inputs to the system being modeled and feeding results back to the model;
receiving feedback relating quality of the system;
based on the model, computing one or more costs and one or more risks associated with the system; and
automatically generating documentation and one or more courses of action for one or more parameters of the system at one or more stages of the system lifecycle.
This relates to and claims priority from co-pending U.S. Provisional Patent Application Ser. No. 60/201,860, filed May 4, 2000; and co-pending U.S. Provisional Patent Application Ser. No. 60/216,532, filed Jul. 5, 2000. Both applications are incorporated by reference herein in their entirety.
Many system designs begin as ad hoc sketches on the back of a napkin. These crude diagrams attest to the value of diagramming as a design tool. A relatively simple diagram can depict important interactions and relationships between different system components. Oftentimes, however, a drawing may later appear confusing or ambiguous to its own author. This problem often stems from a lack of notational consistency in a diagram.
A wide variety of modeling methodologies attempt to formalize the meaning associated with different diagram symbols. For example, UML (Unified Modeling Language) provides a general-purpose notational language for specifying and visualizing complex software and other systems. In particular, UML proponents advocate an approach that represents a system as a collection of objects. Different types of UML diagrams can portray various views of the system.
Many different vendors offer design tools that ease construction of system diagrams. For example, Rational Rose® provides a suite of tools that ease construction of UML diagrams. These tools provide a user interface that features a palette of UML graphic symbols for placement on a diagram.
In general, in one aspect, the invention features a computer-implemented method of modeling. The method includes receiving input specifying at least one graphic element of a model diagram. The diagram can include graphic elements representing a process and graphic elements representing an object. Based on the received input, the method generates a textual description of the diagrammed model.
Embodiments may include one or more of the following features. The graphic elements may correspond to a graphical notation, such as OPM (Object-Process Methodology), that models objects and processes as independent elements.
Generating the textual description may include determining one or more context-free grammar production rules corresponding to the input, and generating a context-free grammar expression from the one or more context-free grammar production rules. The production rules may be consistent with a natural language such as English.
The received input may be user input. For example, the textual description may be generated as a real-time response to user input manipulating, adding, or deleting graphic elements. Generating the textual description may also proceed in a batch mode.
The received input may specify a level of detail to depict. Additionally, the method may include determining a portion of the textual description to display based on the received input specifying the level of detail.
The method may include translating a label of a graphic element from a first natural language to a second natural language. Such a method may use production rules of a context-free grammar for the second natural language.
The method may also include using the generated text to automatically generate software instructions to implement the model or to provide a visual simulation of a modeled system.
In general, in another aspect, the invention features a computer-implemented method of modeling. The method includes receiving a textual description of a model and, based on the received description, generating a model diagram composed of different graphic elements. The different graphic elements can include a graphic element representing a process and a graphic element representing an object.
In general, in another aspect, the invention features a method of translating text from a first natural language to a second natural language. The method includes receiving input specifying a diagram including elements labeled in accordance with a first natural language, translating the element labels from the first natural language to the second natural language, and generating text in the second natural language in accordance with a grammar associated with the diagram elements.
In general, in another aspect, the invention features a computer program product, disposed on a computer readable medium, for modeling. The computer program includes instructions for causing a processor to receive input specifying at least one graphic element of a model diagram. Different graphic elements in the diagram can include a first graphic element representing a process and a second graphic element representing an object. Based on the received input, the instructions can generate a textual description of the diagrammed model.
In general, in another aspect, the invention features a computer program product, disposed on a computer readable medium, for modeling. The computer program includes instructions for causing a processor to receive a textual description of a model, and, based on the received description, generate a model diagram composed of different graphic elements that can include a first graphic element representing a process and a second graphic element representing an object.
Advantages will become apparent in view of the following description, including the figures and the claims.
FIGS. 1 to 20 are screenshots of a modeling tool that expresses a system model both graphically and textually.
FIGS. 1 to 20 illustrate a user interface provided by a modeling tool. Each user interface screen 100 shown features a graphic design workspace 102 (“DiagraMaker”). The workspace 102 enables a user to assemble and interconnect graphic elements to model a system. As shown, the tool's user interface may provide a palette 101 of graphic symbols representing model elements. For example, the tool enables a user to drag-and-drop model elements from the palette 101 onto the workspace 102 for configuration into a system model. The model elements shown in the palette 101 of
Object-Process Methodology enables a user to define processes and objects as independent entities. Independent representation of objects and processes reflects the thought process of many designers, and, thus, facilitates rapid model development. Additionally, even those initially unfamiliar with OPM can quickly grasp components and behavior represented by an OPM model.
The tool can maintain the equivalence of the script window 104 description and the workspace 102 diagram, whether a user alters the diagram in the workspace 102 or changes the text in the script window 104. That is, the tool can alter or add graphic model elements to conform to the text description in the script window 104 and can automatically generate sentences reflecting changes or additions to a diagram. Hence, the informational content of the text description and graphic diagram remains equivalent. Additionally, one may be completely reconstructed from the other.
The precise description of a modeled system provided by the text permits review of the design by domain experts or managers who may have little technological experience or prior experience with graphic models. Additionally, even though easily digested by lay people, the text provides an unambiguous specification for system implementation, for example, by programmers.
In general, to maintain equivalence between diagram and text, the tool associates model elements and model element combinations with formal English sentence types. As user input graphically specifies model elements and their relationships, the modeling tool can automatically generate the corresponding text sentences. Such real-time feedback can quickly alert users to unintended design errors as they occur.
The text shown conforms to a context-free grammar defined to generate natural language (e.g., English) sentences. Appendix B includes a listing of the context free grammar production rules. Production rules can be expressed in a wide variety of formats, such as BNF (Backus-Naur Format), EBNF (Extended Backus-Naur format) and so forth. While the rules shown feature English words and syntax, other production rules may reflect other natural languages.
The equivalence of the text and graphic model representations is, again, a two-way street. That is, instead of generating the text from a diagram, the tool can automatically generate a system diagram from text. That is, the modeling system can use the production rules, such as the rules shown in Appendix B, to parse a given statement and construct a corresponding diagram. For example, as a user translates prose systems requirements specification into the modeling system's context-free grammar expressions, the tool can depict the equivalent diagram elements in the diagram window 102. Again, the tool's use of ordinary English text to describe a system increases operator familiarity, eases use, and can speed system design. To provide a better understanding of the correspondence between graphics and text, the tool can highlight graphic constructs corresponding to a sentence when the user rests a cursor on the sentence, and vice-versa.
Though shown as a system that responds to user input in real-time, the system may operate in batch-mode. For example, a user may submit, or open, a script of formal English sentences arranged in paragraphs and be presented with the corresponding set of diagram(s), one for each paragraph. Formal English sentences, described below, can indicate the links between the different diagrams. Similarly, a user may completely draw a set of diagrams that specify a system before requesting automatic generation of the corresponding text. Either the real-time or batch-modes may be implemented as an interpreter and/or a compiler. Additionally, rather than presenting a generated script or set of diagrams, the system may instead save such information as a file.
To illustrate OPM features and the equivalence of the graphic and text expressions of a model,
As shown, to model a wedding system a designer created an object 106 labeled “Person” in the workspace 102. For example, the designer may have selected a graphic symbol of an object 103, a rectangle, from the palette 101 and positioned the object 106 on the workspace 102.
An object 106 can have different states. A “rountangle” (“rounded-corners rectangle”) graphically depicts an object's state inside the object's box. As shown, a designer has specified that a person 106 object includes a state 108 labeled “single” 108 and a state 110 labeled “married”. Additionally, as indicated by the bolding of the “single” 108 state's border, the designer has specified that a “Person” 106 object initially assumes the “single” 108 state.
The scripting window 104 presents the formal English sentences 200, 202 corresponding to the diagram depicted in the workspace 102. Other configurations present the information shown in the workspace 102 and scripting window 104 in different ways. For example, the system may permit user configuration and arrangement of the windows 102, 104, menu bars, palettes 101, and so forth. Additionally, the tool need not display the workspace 102 and scripting window 104 simultaneously. The tool may also feature other windows, such as those containing hierarchical lists of previously defined objects and/or processes and their attributes, software instructions or database schemas automatically generated from the script and/or diagram, and so forth.
The tool constructs the sentences presented in the scripting window 104 by combining the graphic element labels with reserved phrases of one or more words associated with a graphic element. For example, a “state enumeration” sentence according to the production rules in Appendix B can be expressed as “Object can be State List” where the Object is replaced by the object 106 label “Person” and State List is replaced by a list of the object's states' labels (i.e., “single” and “married”). Thus, as shown, the scripting window includes a text sentence 200 of “Person can be single or married”.
The tool can use text formatting to bold labeled elements while reserved phrases (e.g., “can be”) appear in a normal, non-bolded font. This convention emphasizes the elements of the system rather than the reserved phrases that may appear again and again in a script. The convention also enables a user to quickly identify relationships between domain-specific names of objects, processes, and states. Additionally, the system may enable a user to color code diagram elements and format the text to color terms to match the color of their corresponding diagram elements.
Again, while described as generation of text based on manipulation of elements in the workspace 102, the tool can also accept text and modify the graphic depiction to reflect this text. For example, formatting a text term as a specific color can cause the system to correspondingly color associated diagram elements.
The tool can provide feedback to guard against illegal constructs. For example, if a user attempts to insert a formal English sentence that does not conform to the formal English syntax, the system can generate a list of the closest legal options for user selection. Likewise, if the user attempts to insert a graphical construct not recognized by the system as legal, the tool can generate a list of the closest legal graphical arrangements for user selection. In either case, the tool can direct the user to an appropriate part of a tool help/tutorial facility.
OPM permits alternate representations of similar system features. For example, as shown in
As shown, the designer also used a “non-comprehensive” symbol 112 that indicates that a person features other characteristics which are not depicted in the diagram. The “non-comprehensive” symbol 112 appears as a line segment crossing a connection between the person object 106 and the graphic element 112 (i.e., the “exhibition-characterization” symbol) defining the relationship between the objects 106, 116. As shown in sentence 204, the text associated with this symbol features the words “and more”. The “non-comprehensive” symbol can also be used to characterize other symbols such as “aggregation” and “specialization” symbols described below.
While a bit more involved than
As shown in
In greater detail, after adding and labeling the “Wedding” process 126, a user specified the transformation of the “Person” object 106 provided by the “Wedding” process 126 by a pair of links 122, 124. Each link 122, 124 appears as a line terminating in hollow arrowhead. The links 122, 124 have different sources and destinations. That is, link 122 leads from the “single” state 108 to the “Wedding” process 126, while link 124 leads from the “Wedding” process 126 to the “married” state 124. In OPM terminology, link 122 forms an “input link” that represents the leaving of the “single” state 108. Similarly, link 124 forms an output link that represents entry into the “married” state 124. The pair of links 122, 124 identify the “Wedding” process as changing a “Person” 106 from the “single” 108 state to “married” 110 state. As shown, the pair of links 122, 124 can share a thread label (e.g., “a”) that can distinguish this pair 122, 124 from others in a diagram. Thread labels permit identification of potentially parallel threads of execution.
As shown in
OPM and the tool can distinguish between different categories of enablers. For example, one type of enabler is known as an “agent.” An agent, such as a human or organizational unit, exhibits discretion. Other types of enabler's are deemed “instruments”. Blackened lollipops identify agents while hollow lollipops identify instruments.
While terms like “enablers”, “agents”, and “instruments” may require a bit of explaining to those unfamiliar to OPM, the text sentences 212-214 eschew this terminology in favor of simpler descriptions. For example, the text generated for the agent relationship between the “Justice” object 130 and the “Wedding” process 126 simply states “Justice handles Wedding.” 212. This concise phrasing clearly communicates the design depicted by the diagram to those unfamiliar with OPM notation or its terminology.
As previously described, processes transform objects by changing their states. For example,
Just as a wedding creates a couple, a divorce destroys it. Thus,
A model often changes over the lifecycle of a system. Such changes occur frequently during the initial design as users try different model configurations. Such changes also occur during maintenance phases, for example, after practice reveals deficiencies in an original model. The tool reflects changes in the diagram or equivalent text to maintain equivalence between the two. For example, user removal of the “Divorcing” process 142 from the diagram causes removal of consumption link 140 and the corresponding text sentence 218. Similarly elimination of sentence 218 causes removal of the “Divorcing” process 142 and consumption link 140 from the diagram.
Returning to the design of the wedding system model, generally, a wedding joins a man and a woman. As shown in
As shown, OPM depicts the “specialization” symbol 140 as a hollow triangle. The text sentence 220 associated with the specialization includes the reserved term “are”, as in “Man and Woman are Persons.” 220. The text sentence 220 also illustrates that the tool can pluralize words as contextually needed. For example, a sentence of “Man and Woman are Person” is both awkward and grammatically incorrect. Thus, the tool pluralizes the object label “Person” by adding a “s” suffix. The tool can maintain a dictionary for words not pluralized by convention “s” and “es” suffixes (e.g., “goose” pluralized is “geese”).
OPM provides not only for specializations of objects, but also specializations of processes. For example, “Secular Wedding” and “Religious Wedding” (not shown) could be specializations of the process “Wedding” just as “Man” and “Woman” are specializations of the object Person.
In addition to representing specializations of a generic person, a couple typically includes a man and woman.
OPM can distinguish between physical and informatical things. Shadowed (3-dimensional) or double-bordered boxes and ellipses denote physical objects and processes, respectively. As shown, the “Sam” 152 and “Jane” 154 objects both appear as double-bordered rectangles. An “informatical” entity conceptually exists independently of its physical embodiment. For example, a song remains the same whether scored on music sheets or recorded on vinyl. Thus, a song is an informatical entity. However, physical entities, such as a rock or body, do not have existence separate from its physical, space-occupying form. In practice, system designers often ignore this distinction and use the single bordered informatical graphic symbols for informatical and physical entities alike. OPM, nevertheless, provides such symbols if needed. In addition to its usefulness as a modeling symbol, this enables the separation of sentences that need to be coded from those that do not (e.g., hardware portions of a system).
As shown, an instance of an object 152, 154 is denoted as a rectangle with a truncated upper left corner. Likewise, an instance of a process is denoted as an ellipse with a small part of its left part truncated (not shown). This provides a distinction between a thing (object or process) and its instances when an attachment between the instance and thing does not appear or has not yet been established.
Again, the system provides many different complexity management features for use at a user's discretion, for example, when a diagram appears too populated with objects, processes, and links. The complexity management features include state suppression/revelation, in-zooming/out-zooming, and folding/unfolding (described below). After using a complexity management feature such as a scaling feature, the tool presents a new depiction showing more or fewer details.
As stated above, the system provides a “state suppression/revelation” mechanism where state suppression hides object states and state revelation reveals them. For instance, in
It should be noted that a user can add an effect link 156 without suppressing object states. For example, the effect link 156 may appear in the graphic element palette. This is useful when the states of an object are known but it has not yet been determined how exactly the affecting process changes the states of the affected object.
The tool can enable a user to toggle between suppressed or revealed states of an object, for example, by double-clicking or right-clicking on the object. Similarly, entering text of “Suppress States of Person” or “Reveal States of Person” in a command window may perform the same task. Additionally, using similar techniques, a user may suppress or reveal the states of one, several, or all objects in a diagram.
In addition to state suppression/revelation, the tool may provide users with the ability to “zoom” into and out-of particular elements. To illustrate,
A user can navigate from the high level diagram of
As depicted in
In greater detail, the “Wedding” process 126 includes “License Verifying” 162, “Postponing” 170, “Ceremony Conducting” 172, and “Dining” 180 processes. In general, in OPM, control flows from top to bottom. That is, the relative positioning of the processes indicates that the “License Verifying” process 162 should occur prior to any of the other processes. Processes appearing at the same horizontal level indicate processes that can, potentially, proceed in parallel.
The “Wedding” process 112 includes an object 164 labeled “License is Legal?”. The question mark indicates that the object 164 constitutes a Boolean object. A Boolean object has two mutually exclusive states 166, 168. A link 160 from the “License Verifying” process 162 to the “License is Legal?” object 164, again, features a line terminating in a hollow arrowpoint. In this context (i.e., a link from a process 162 to a Boolean object 164), however, the link specifies that the process 162 determines the state 166, 168 of the Boolean object 162 as reflected in the corresponding text “License Verifying determines whether License is Legal” 238.
Another link connects the “yes” state 168 of the “License is Legal” Boolean object 164 to the “Ceremony Conducting” process 172. A similar link connects the “no” state 166 to the “Postponing” 170 process. Like “instrument” links, the links terminate in hollow lollipops. In the context of connecting states to processes, the links form flow-of-control “conditional” links. Additionally, since the “License is Legal?” Boolean object 164 can only be in one state at a time, the links represent mutually exclusive conditions. The relationships established by these links are appropriately explained by the corresponding text 240, “Ceremony Conducting occurs if License is Legal, otherwise Postponing occurs”. In programming language terms, the above is an “if-then-else” type statement. A diagram, or the corresponding text, can also specify other flow-of-control constructs. For example, a user can construct a “case” statement construct by including more than two states, each being a condition for triggering a process.
Again, as described above, a user can zoom-into and out-of diagram elements. For example, double-clicking the “Wedding” process 126 in
For example, the tool can present multiple diagrams of a system model simultaneously. For example,
The tool may also present a system map window 186 that can be shown or hidden. As shown, the map 186 presents “thumbnails” 188-190 of different model diagrams. Selecting one of the “thumbnails” 188-190 causes the tool to present the selected diagram in the workspace 102. The map 186, thus, provides easy navigation among the, potentially, numerous diagrams in a diagram set and allows a user to see the “big picture” while looking in greater detail at some portion of the system.
In addition to the complexity management features illustrated above, the tool also provides a folding/unfolding feature that remove/reveal aggregation, specialization, exhibition, and instantiation symbols and related entities (e.g., “sub-objects” aggregated by another object).
Again, the design example above illustrated relationships provided by the tool and OPM. Additionally, the tool and OPM also allow a user to define a relationship between entities of their own creation. For example,
In greater detail,
By default, structural relationships form a one-to-one relationship, however, structural relationships, particularly in database schemas, often form one-to-many, many-to-one, and many-to-many relationships. As shown in
The number of “Child” objects 302 need not be a range. For example, a user may simply specify a number (e.g., 3) or parameter (e.g., “n”). Additionally, either end of structural link may specify cardinality.
As shown in
As an alternative to intricate annotations, OPM and the tool provide a diagrammatic way of expressing relationships to, potentially, reduce diagram congestion. For example, as shown in
As described above, OPM provides a number of different ways of expressing system logic. In addition, OPM also enables a designer to express Boolean logic or a “compound condition”. As shown in
Again, the tool and OPM can model a wide variety of systems. In fact, OPM & OPL can completely specify themselves. For example,
Automatic generation of future versions of OPM/OPL illustrates the flexibility and extensibility of OPM/OPL design. On a less grand scale, the tool may provide a “learning mode” that enables a user or group to define their own symbols and sentences. For example, in the vertical domain of a continuous chemical process industry one may define a “sampling” relation shaped like a triangle within which a pie is drawn with a slice taken out of it. This slice symbolizes the sample, which is a small amount of a large lot that is analyzed for exact composition. The resulting composition is also the composition of the large lot, with its amount practically unchanged. An example sentence would be “Sample represents Mixture.” Here, “represents” is the reserved phrase analogous to “consists of” for the aggregation-participation relation.
The user also linked a “Ship” object 616 to the “water” state 610 and an “Airplane” object 618 to the “air” state 608 via hollow triangles 612, 614. As described above, hollow triangles 612, 614 represent specialization when connecting things or Boolean “OR”-ing when connecting object states, however, in learning mode the tool may temporarily permit different constructs. After diagramming, the user can enter a text sentence 626 corresponding to the diagram. Similarly, after entering a new type of sentence 626, the user can draw the corresponding diagram 600. By identifying reserved words entered by the user and identifying element labels, the tool can store a diagramming configuration and the corresponding sentence syntax, for example, by automatically generating new production rules. Thus, the tool can learn a new configuration of model elements and their corresponding new sentence. Thereafter, upon detecting a diagram construct, the tool can generate a sentence in accordance with the newly defined syntax. Similarly, upon detecting a text sentence having the newly defined syntax, the tool can generate the corresponding diagram. Thus, the learning mode gives a user flexibility in using the tool to express new modeling constructs and concepts. Use of the learning mode may not be available to all users, and may be restricted to experts.
OPM can also offer temporal-features, for example, for specification of systems that exhibit complex dynamic behavior involving time constraints. For example, real-time systems often handle issues like concurrency, synchronization among processes, and expression of events, conditions, and timing constraints. OPM provides graphic and text constructs to include these features in a model.
OPM also permits representation of temporal constraints and timing exceptions. Temporal constraints are minimum and maximum time bounds on a time interval. Temporal constraints include a process duration constraint (a constraint on the time spent in executing a process), a state duration constraint (a constraint on the duration of the time spent in an object's state), and a reaction-time constraint (a constraint on the time elapsed between a triggering event and the execution of the triggered process). In addition to minimum and maximum time constraints, a probability distribution function can be specified and used for purpose of simulating the entire system. Each entity (object, process, or state) is associated with a multimedia object (image, video clip, audio file, CAD drawing, 3-D hologram, line drawing, schematic, etc.) that goes in action when its time of execution or creation or destruction comes. Hence, OPM allows for vivid simulations.
Temporal constraints are attributes of the process or state or transition. They can be expressed by the usual exhibition symbol or by specifying an interval, Tmin . . . Tmax, where 0≦Tmin≦Tmax. Tmin and Tmax represent the lower and upper bounds of the interval, respectively.
Processes take time to execute, and states are situations at which objects exist for some period. To be able to specify the time executing a process and being in a state take, both processes and states have an implicit attribute called Duration, which is the amount of time it takes for a process to execute or for an object to be at a state.
We can view the requirement that D be between Dmin and Dmax as one of the post-process conditions and abstract out the entire exception handling mechanism specified in
Before outputting its result, a “Timed Processing” for which Tmax<∞, i.e., one that has a non-infinite maximum timing constraint, checks whether this maximum timing constraint is met. If not, i.e., if the processing time exceeded Tmax, then it does not output its result. If an exception link emanates from that process, a time exception event, i.e., an event signaling the exception of the maximum duration constraint, is registered.
Again, the temporal features described above have equivalent text (OPL) descriptions in accordance with production rules. For example, a triggering event sentence can take the form “Event event-name of type [event-type] triggers process-name <with a reaction time that is at least Tmin and at most Tmax>.” This sentence specifies which event triggers the process process-name, and optionally, what the reaction time constraints are. As described above, OPM/OPL can model virtually any system. In addition to its usefulness as a modeling tool, the legibility and compactness of the OPL text description of a system enables smooth and direct transformation from original requirements all the way to executable code that materializes the system's functionality through software (e.g., C++, Java, or other software instructions), database schema definitions, and so forth. Not only is OPL more readable to non-programmer domain experts, but, due to its high level of abstraction, OPL is also an order of magnitude shorter than the resulting code.
To illustrate automated code generation,
In greater detail,
Again, the OPL compiler accepts an OPL script that specifies a system and automatically converts the OPL script file into C++ code. The OPL compiler includes modules symbolTable, lexer, parser, emitter, error, and init, which initializes the symbolTable. To allow for efficient compilation, a pre-processing pass on the OPL script arranges the OPL sentences in depth-first search (DFS) order. In addition to the usual DFS requirements of a tree structure, this DFS order pre-supposes a particular order of the types of OPL sentences. For example, the features of a thing (object or process) should be specified before its parts. For example, in the OPL script of
The OPL compiler parses the arranged input file in two passes. During the first pass, it generates an intermediate file (simplestate.def), which contains names of stateless objects (objects that do not have states), along with the path leading to their root. During the second pass the compiler uses this file to distinguish between two types of triggering events: state-change events and value-change events. It also writes the compiled specification-dependent C++ code into the appropriate C++ output files in an append-only manner.
When the compiler encounters a thing (object or process) it recursively parses the OPL sentences that specify that thing. The first OPL sentences processed are structure sentences, which include specialization sentences, generalization sentences, state enumeration sentences, exhibition sentences, and finally, aggregation sentences. In the case of a process, the behavior sentences, which include triggering event sentences, guarding conditions sentences, enabling sentences, result sentences, consumption sentences, and effect sentences, are processed in this order.
The OPL-to-C++ compiler may proceed according to compilation rules. These rules can handle such issues as the scope of each thing (object or process) and its members, the parameters of each method, and so forth. An extended discussion of one example set of compilation rules follows.
All objects inherit, either directly or indirectly, from the abstract-Object class. Major processes can be defined as stand-alone processes, which inherit from the generic Process class, while other processes are defined as methods of other classes. A process can be defined as a method of an object B if and only if it affects values or states of objects that are internal to B (i.e., attributes or parts of B) and has no side effect on objects that are external to B.
Each stand-alone process has two methods—Trigger and Execute, and the attribute Name. The Trigger method checks the process preconditions, and if they hold, calls the Execute method.
The fundamental structural relationships of aggregation and characterization are both converted in the same way: If an object B has a part or a feature (where a feature is an attribute or a method), that part or feature is declared as a private member of B. This rule also applies to both simple and complex parts and features.
Each complex object is translated into a C++ class. A complex object is derived, either directly or indirectly (if it is a specialization of another object class) from the generic built-in Object class. As shown in the C++ listing of
Simple (i.e., non-complex) OPL objects, such as the object “ID” of type short, are defined as private members of the classes to which they belong (either as features or as parts). The public methods get and set, are defined for each simple object, as shown for “ID” in lines 6-9 of
A compound process B has the methods Trigger and Execute, which correspond to the sub-processes “Triggering” and “Executing” of
A simple (i.e., non-complex) OPL process is compiled into two methods: process-nameTrigger and process-nameExecute. Like the Trigger and Execute methods of a compound process, the process-nameTrigger method checks the process guarding conditions. If they hold, the process-nameExecute, which implements the specific process behavior, method is called.
If a complex thing G constitutes a part or a feature of another thing, H, then it is declared as a private class within H. For example, since “Elevator” is part of “Building”, the class “Elevator” is declared within the class “Building”, as shown in line 3 of
Instances are created for each C++ class, be it an object class or a process class. Lines 33, 38, 42 and 45 in
An OPL state-containing object (i.e., an object that has states) has a C++ pointer to each one of its possible states. Each state belongs to the generic State class (or its specialized TimedState class, if the state is timed). For example, line 14 shows the C++ pointer generated for the state “closed” of “Door”. For each state, the methods set_statename (e.g., set_closed) and enter_statename (e.g., enter_closed) are defined. A set_statename method initializes the state of an object, (e.g., set_closed initializes state “closed” of “Door”) while enter_statename is used when an object changes its state (e.g., when “Door” leaves state “open” and enters state “closed”).
For each state-containing object, a get_state ContainingObject method is defined, which returns its current state. For example, get_Door returns the current state of “Door”, which can be either “open” or “closed”. Lines 14-19 show the C++ code generated for the state “closed” of “Door”.
The OPL guarding conditions sentence is checked by the Trigger method. If the guarding conditions hold, Trigger calls the Execute method. Execute uses the enablers of the process, which are specified in the enabling object sentence. Execute transforms objects that are specified in the OPL effect, consumption and yield sentences. For example, the guarding condition sentence “Process Closing is guarded by “Door is open”, “OutstandingRequests of Elevator is yes” and “LocationStatus of Elevator is atFloor” is translated into the Trigger method of “Closing”, as shown in
An OPL triggering event sentence is translated into part of the C++ method “EventProcessTable::TriggerAllProcesses(Event *e)” that builds an Event-ProcessTable that specifies the triggered process(es) for each event.
The code generated by the OPL compiler relies on predefined C++ modules. These modules serve as instruments for a variety of processes.
The predefined modules include the Event and EventQueue Modules for Handling Events and Timeout Events. Each time an event occurs, a record of it is created and inserted into the EventHistory and into the EventQueue. The event can be internal (e.g., an object entering a new state) or external (e.g., a user hitting a keyboard character).
An event features the event name and type, the identifier of the object that triggered the event, Tocc—the time at which the event occurred, and Tins—the time at which the event was inserted into the event queue. Tocc can be used to check whether reaction time constraints (i.e., constraints on the time elapsed between the event occurrence and the process triggering) are met. Tins can be used in order to allow the insertion of future events (such as future timeout events) into the EventQueue.
The EventQueue contains Event objects ordered by Tins. When an Event first occurs, both its Tocc and Tins are given the value of the current time and the Event is inserted into the EventQueue.
If the Event e1 that is about to be inserted into the EventQueue has a Tins1 that is equal to a Tins2 of another event, e2, which already exists in the EventQueue, then Event e1 is inserted after Event e2.
When an Event marking an entrance into a time-constrained state occurs, two Events are inserted into the Event Queue: a state-entrance Event and a future state-timeout Event. The Event of type state-entrance is assigned values such that Tocc=Tins=Tnow. That is, both the time of event occurrence. Tocc, and the time the event was inserted into the EventQueue, Tins, are equal to the present time, Tnow.
The Event of type state-timeout is assigned future time values such that Tocc=Tins=Tnow+Tmax. That is, both the time of timeout event occurrence, Tocc, and the time the timeout event, Tins, are equal to the present time plus the maximum time, Tmax, that should be spent in the time-constrained state.
If the time-constrained state is exited before the maximum time that should be spent in the time-constrained state, Tmax, is exceeded, then the future state-timeout Event is deleted from the EventQueue. Otherwise, when the timeout materializes, i.e., the future point in time equals Tmax, then the state-timeout Event marking this timeout is popped from the EventQueue.
The predefined modules also include a process module. The generic compound Process class has a Name attribute, and it contains a constructor and the two methods Trigger and Execute. Each time the Execute method is executed, a record of an occurrence of Process is inserted into its HistoryRecordSet.
The C++ code generated for the classes TimedProcess and DelayedProcess is based on the generic TimedProcessing process. Process-nameWait and Process-nameOutput are the C++ names of the “Waiting” and “Outputting” processes, respectively. If Texecution is supplied, then the minimal and maximal waiting times of Process-nameWait are Tw min=Tw max=Tmin−Texecution, as are the waiting times of “Waiting”. Otherwise, Tw min=Tw max=Tmin−δ; where δ is a small number, in the order of milliseconds, to allow some time for the Process-nameOutput to execute.
Process-nameWait generates a process termination event, whose Tins=Tocc=Tnow+Tw min−δ. This process termination event is inserted into the EventQueue, and when popped, triggers Process-nameOutput. In order to simulate a time exception of Process-nameWait, in some small number of randomly selected cases, the process termination event of Process-nameWait is given the values Tins=Tocc=Tnow+Tw min+Tpenalty, where Tpenalty is the amount of time that the process is simulated to be late. In addition, a process timeout event of Process-nameWait is also inserted into the EventQueue at the time that the process was supposed to end, at the latest, namely Tins=Tocc=Tnow+Tw max.
Since the Process-nameWait method takes close to zero time, the only time that the TimedProcesses actually consumes is the time needed for it to compute its output results via the Process-nameOutput method. The scheduler enables a certain extent of concurrency by using the time elapsed between the completion of the execution of the Process-nameWait method and the beginning of the execution of the Process-nameOutput method.
Before outputting its result, a TimedProcess for which Tmax<∞, i.e., one that has a non-infinite maximum timing constraint, checks whether this maximum timing constraint is met, allowing a deviation of δ from Tmax. If not, i.e., if the processing time exceeded Tmax, then it does not output its result. If the timing constraint is hard, i.e., if an exception link emanates from that process, a time exception event, i.e., an event signaling the exception of the maximum duration constraint, is registered. A better hard time constraint scheme is for a TimedProcess to check the maximum bound during its execution, and if it is violated, register the exception event and terminate the process. This scheme is not implemented in the current version of our compiler.
The predefined modules include a state module. The State class models a state. Each State has the following methods:
(a) The set_state-name method, which sets the attributes (parameters) of the state. The attributes include Temporal order, i.e., whether the state is an initial state (source), a terminal state (sink) or a regular state; and a Triggering object, i.e., which object (if it is knows ahead of time) triggers the event of entering the state; and
(b) The enter_state-name method which checks if it is possible to leave the state in which the object is currently in and enter the new state. In case the entrance into the state constitutes a triggering event, then the enter_state-name method inserts this triggering event into the EventQueue. This event is deleted from the EventQueue when the state is exited.
A TimedState is a time-constraint State. It has the attributes Tmin and Tmax for the minimum and maximum timing constraints, respectively, and Tlast for keeping the time in which the state was last entered. If the TimedState has a minimum duration constraint, then the TimedState cannot be exited before this time has elapsed. This time constraint, Tnow≧Tlast+Tmin−δ3, is checked by the TimedState TryToLeave method, which is called by the enter_state-name method.
The predefined modules also include a Scheduler module. The Scheduler loops between accepting any arriving external Event (represented by keyboard strokes or any other external stimuli), and popping an Event from the EventQueue. An Event is always popped from the beginning of the EventQueue, so Events that were inserted earliest into the EventQueue are popped first. An Event can be popped out of the EventQueue only if the time of its occurrence, Tocc, is earlier than the present time, Tnow. Once an event is popped from the EventQueue, it is passed to the Event-Process Table, which tries to trigger the appropriate Process. If the reaction-time constraints and the guarding conditions of the Process are met, then the Process is triggered. Once a Process is triggered it is not preempted, i.e., it continues its execution without interruption until finally, it terminates.
The Event-Process Table specifies the Process that should be triggered by each Event, and the reaction-time constraints on the time elapsed between the time of the occurrence of the event, Tocc, and the time the appropriate Process is triggered.
If Tnow−Tocc<Tmin, that is, the time elapsed from the time the Event occurred until it is presently popped from the EventQueue, ready to trigger a process, Tnow−Tocc, is less than the minimum reaction time constraint, Tmin, then the Event is inserted back into the EventQueue. Its Tocc does not change, but its Tins is given the present time, Tnow.
If Tnow−Tocc>Tmax then it is too late to trigger the process linked to the triggering event. In this case, the Event is ignored and is not inserted back into the EventQueue.
If the present time, Tnow, is within the bounds of the reaction-time constraints, then the Trigger method of the process that should be triggered by this triggering Event can be executed. Trigger checks the guarding conditions of the process, and if they hold, it calls the Execute method of the process.
If the guarding conditions do not hold but the present time, Tnow, is still within the bounds of the reaction time constraints (i.e., it will still be possible to check the guarding conditions at a later time) then the Event is inserted back into the Event Queue. The Event now has a Tins value that is equal to the present time, Tnow.
A History module deals with recording the history of Events that were generated and Processes that were executed, in the course of the application execution. The Mtime class is the time-class used by applications. Its time granularity is of the order of milliseconds. It contains operators for comparing two Mtime objects (e.g., =, ≠, >, <, ≧and ≦) and methods for increasing an Mtime object by a given amount of time.
Enablers, who are Agents and/or Instruments, optionally enable the entire Processing process. Their possible involvement in the two sub-processes of Processing can be inferred from the fact that they touch the outer circumference of the process, rather than just one of its sub-processes.
Each process has a (possibly empty) Pre-condition Set—a set of logical conditions that are checked by the process Triggering. A condition can be a Boolean expression, a test as to whether particular objects are in specific states required for Execution to take place, and so forth.
The Pre-condition Set can be in a True or False state. The sub-process Triggering checks each condition in the Pre-condition Set. If the Pre-condition Set is evaluated to True, then Executing is allowed to start. The sub-process Executing constitutes the particular behavior of Processing (the “body” of the procedure/function/routine/operation/method). Executing transforms the Transformees of the Processing process. It can change the state of the Affectees via the effect link, it can create the generated Resultees via the result link, and it can consume the Consumees via the consumption link. Executing may require the involvement of one more Enablers of Processing—Instruments as well as Agents.
In addition to automatic code generation, the system can provide other helpful design features. For example, the tool can use the generic processing model of
The simulation can be continuous or step-controlled by the user. The simulation starts by the user selecting a subset of things (objects and/or processes) and specifying states of objects that trigger some process. The simulation can depict the state(s) of an object by changing the color of the current state(s) and use various colors for things (objects and processes) that are in the past, present or future. The simulation can indicate continued execution of a process by flashing and/or changing colors of the process ellipse. As soon as the process terminates, all the post-process effects take place (e.g., new objects can be generated, input objects consumed, change of states, and so forth). The time duration of a process can be fixed or randomly drawn from a pre-specified distribution function with given parameters. In addition, multimedia artifacts can be switched on or off along with generation or destruction of objects or
As an example, consider a simulation of the Wedding process of
Automatic code generation and the system simulation features described above illustrate potential benefits from the formal expression of a system in OPM/OPL. Again, at the heart of the system are techniques for generating formal text sentences for graphic constructs, and vice-versa. Another benefit of this bi-modal graphic-textual representation of the system is the ability of people with various backgrounds and preferences to relate to the system specification by inspecting either the graphics or the text and in case some point is unclear at one, the other can be consulted. No programming background is required as the language is a subset of English and the symbol set is small and intuitive.
As described above, some symbols are graphically overloaded, i.e., they perform “double” duty. For example, a blackened triangle may indicate aggregation or a Boolean AND, depending on the triangle connections. Thus, the process 450 may determine 454 the context of the symbol, for example, by identifying other connected or linked symbols. Based on the symbol and determined 454 context (e.g., pattern recognized from the lookup table), the process 450 identifies 456 a corresponding sentence type and outputs or updates 450 a formal English sentence using the identified sentence type and the relevant symbol labels.
After parsing, the process 460 can identify 464 text elements already depicted in a diagram. For elements not yet depicted, the process 360 attempts to identify available workspace area for the addition of new elements. Such attempts may be based on legibility metrics, such as the size of a closed shape (object, process, state) required to contain its label, a penalty for the amount of overlapping of closed shapes, containment requirements (such as states within object, sub-processes within a zoomed-in process, etc.), intra-symbol distances, the number of intersecting links caused by a particular placement, link lengths and number of bendings, and so forth. Each metric has a weight and a value. A score is calculated and an objective function is attempted to be optimized. If a satisfactory space exists 468 (e.g., if the calculated weighted score of the metric values exceed a threshold), the process 460 can add 472 the symbol to the diagram in the identified space and inter-connect 474 the symbol to other elements as specified by the text. If no satisfactory space exists 468, the process 460 can attempt to move existent graphic elements to create room. For example, the process 460 can identify spaces having the relative best metric scores and attempt to move bordering graphic elements away from these spaces. Each moving of elements is judged again the same set of criteria and a weighted score of the metric values is calculated.
As described above, OPM/OPL can model a wide variety of systems and potentially generate/simulate such systems. Additionally, the system can provide capabilities beyond the realm of modeling. For example, the system can aid in translating text from one natural language to another. For instance,
Thus, as shown in
The platform 500 also includes a network connection 512 to send and receive information such as models and model fragments to other networked devices. For example, the system can work in a collaborative mode using a coordinated distributed database of the formal English and/or corresponding diagram. Users distributed geographically and can check-out parts of the model that they can modify and then check-in, while other team members can work on other parts of the system.
The techniques described herein are not limited to any particular hardware or software configuration; they may find applicability in any computing or processing environment. The techniques may be implemented in hardware or software, or a combination of the two. Preferably, the techniques are implemented in computer programs executing on programmable computers, each including a processor, a storage medium readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device, and one or more output devices.
Each program is preferably implemented in high level procedural or object oriented programming language to communicate with a computer system. However, the programs can be implemented in assembly or machine language, if desired. In any case the language may be compiled or interpreted language.
Each such computer program is preferably stored on a storage medium or device (e.g., CD-ROM, hard disk, or magnetic disk) that is readable by a general or special purpose programmable computer for configuring and operating the computer when the storage medium or device is read by the computer to perform the procedures described herein. The system may also be considered to be implemented as a computer-readable storage medium, configured with a computer program, where the storage medium so configured causes a computer to operate in a specific and predefined manner.
Other embodiments are within the scope of the following claims.