Coherent object system architecture

[0002] This application claims the benefit of U.S. Provisional Application No. 60/083,779, filed Apr. 30, 1998, which is incorporated herein by reference.

[0003] This file contains a CD-ROM containing electronic copies of Appendices, A, B, C and D which are incorporated herein by reference.

[0004] Contained herein is material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent disclosure by any person as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all rights to the copyright whatsoever.

[0005] 1. Field of the Invention

[0006] The invention relates generally to the field of run-time execution engines and automated code generation. More particularly, the invention relates to a Coherent Object System Architecture (COSA) including a context free run-time execution engine and a control flow architecture useful for directing the execution of automatically and/or manually generated code.

[0007] 2. Description of the Related Art

[0008] Current run-time execution engines are characterized by complicated chains of logic and inefficiency. FIG. 1 is a simplified example of a prior art run-time execution engine that interprets bytecodes for a Java virtual machine. Assuming the bytecode interpreter 100 is to support even a subset of the 200+different instructions that make up such a virtual machine, the switch-case statement beginning at line 5 becomes large rather quickly. For purposes of this example, behavior is shown for only two exemplary opcodes, OPC_PUTS and OPC_EXIT.

[0009] Briefly, according to the present example, each bytecode that is received causes the bytecode interpreter 100 to sequentially interpret and process each byte in the bytecode parameter. Depending upon the sophistication of the compiler, the effect of the large switch-case statement is often the same as if a set of if-then-elses had been coded. For instance, chains of tests would be required for the 100^thopcode before arriving at the corresponding behavior. First, the interpreted opcode is compared to the first case, then the opcode is compared to the second case, and so on, until a successful comparison is made to the 100^thcase. One possible way to achieve more efficiency is to manipulate the switch-case statements in an intelligent manner. For example, the case statements may be arranged in an order that first evaluates those of the opcodes that are most commonly used or those that are able to be evaluated the fastest. Consequently, fewer tests will be performed during run-time and the code will execute faster. Of course, this shallow, code-tuning advice assumes run-time characteristics of the code to be executed can be anticipated with some level of certainty. In reality, the manner in which general purpose software will be exploited is far from predictable. As a result, unforeseen uses may hinder the intended optimizations and may actually degrade performance for some users.

[0010] Other limitations illustrated by this example include lack of maintainability and inflexibility both of which result from context dependencies. For example, when new opcodes are added, the bytecode interpreter 100 must be supplemented with multiple new case statements and it must be recompiled. In addition, prior art run-time execution engines have various other disadvantages that are overcome by aspects of the present invention, as described in the detailed description which follows.

[0011] A method and apparatus are described for controlling the execution of a software program. According to a first embodiment, control flow information including multiple states associated with a software program is made accessible. Each of the states includes information indicative of desired control flow of the software program and information indicative of desired behavior of the software program. A determination is made if a current status of the software program has a predetermined relationship with an expected state of execution of the software program. Based upon the result of the determination and the information indicative of desired behavior, the software program is caused to perform an action and caused to transition from the current state to a next state.

[0012] According to a second embodiment, specification of a control flow architecture associated with a software program is simplified to the provision of certain control flow information that is accessible to a control flow engine. The control flow information need only include information indicative of desired control flow of the software program and information indicative of desired behavior of the software program.

[0013] According to a third embodiment, a novel controller is provided. The controller includes a processor configured to execute instructions and a memory coupled to the processor. The memory has stored therein data representing sequences of instructions of a software program. The sequences of instructions when executed by the processor cause the processor to perform the steps described above for controlling the execution of the software program. In one embodiment, the controller is dynamically programmable allowing data representing one or more member functions, control flow information, and/or a control flow engine to be loaded into the memory.

[0014] According to a fourth embodiment, a run-time execution engine performs true dynamic binding. The run-time execution engine dynamically binds execution flow of a software program to one or more member functions of the software program by reading addresses of the one or more member functions out of a data segment of the software program.

[0015] According to a fifth embodiment of the present invention, an array may be initialized with dissimilar elements. An expansion macro replaces each function in an array of functions with a list of dissimilar parameters associated with the function. Additionally, addresses associated with one or more parameters are calculated as the expansion macro replaces the functions.

[0016] According to a sixth embodiment, an improved method of running a Java program is provided. A bytecode is received. If the bytecode has not previously been received, then the bytecode is translated into executable code, the executable code is run, and the executable code is stored. Otherwise, if the bytecode has previously been received, then the previously stored executable code for the bytecode is executed.

[0017] Other features of the present invention will be apparent from the accompanying drawings and from the detailed description which follows.

[0018] The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

[0019] FIG. 1 is a simplified example of a prior art run-time execution engine.

[0020] FIG. 2 is a high level flow diagram that conceptually illustrates steps involved in transforming a problem statement into executable software.

[0021] FIG. 3 is an example of a computer system upon which one embodiment of the present invention may be implemented.

[0022] FIG. 4 conceptually illustrates the components of a software program according to one embodiment of the present invention.

[0023] FIG. 5A conceptually illustrates control flow information components according to one embodiment of the present invention.

[0024] FIG. 5B conceptually illustrates control flow information components according to another embodiment of the present invention.

[0025] FIG. 6 is a flow diagram illustrating run-time processing according to one embodiment of the present invention.

[0026] FIGS. 7A, 7B, 7C, 7D, and 7E conceptually illustrate control flow information components according to alternative embodiments of the present invention.

[0027] FIG. 8 is an exemplary implementation of control flow information according to one embodiment of the present invention.

[0028] FIG. 9 is an exemplary implementation of a control flow engine according to one embodiment of the present invention.

[0029] FIG. 10 illustrates exemplary member functions according to one embodiment of the present invention.

[0030] FIG. 11 conceptually illustrates the code and data segments of executable software according to one embodiment of the present invention.

[0031] A method and apparatus for controlling the execution of a software program are described. Broadly stated, according to the present invention, a software program may be specified as a control flow architecture and data flow information. Exemplary control flow architecture may include control flow information in the form of a table comprising rule states including desired control flow and desired behavior. According to one embodiment, the data flow information may comprise one or more member functions associated with the control flow information. During execution of the software program, an engine may cause one of the member functions to carry out the desired behavior based upon the current execution status of the program and the control flow information. In this manner, the engine may direct the execution of the software program by dynamically binding control flow to the software program components during run-time. According to another aspect of the present invention, the control flow information facilitates production of error free code and promotes good coding practices by forcing the model to consider desired behavior for all possible states of the software program. These and other enhancements seek to provide a powerful and flexible run-time system for automatically and/or manually generated code.

[0032] In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without some of these specific details. In other instances, well-known structures and devices are shown in block diagram form.

[0033] The present invention includes various steps, which will be described below. The steps of the present invention may be performed by hardware components or may be embodied in machine-executable instructions, which may be used to cause a general-purpose or special-purpose processor or logic circuits programmed with the instructions to perform the steps. Alternatively, the steps may be performed by a combination of hardware and software.

[0034] The present invention may be provided as a computer program product which may include a machine-readable medium having stored thereon instructions which may be used to program a computer (or other electronic devices) to perform a process according to the present invention. The machine-readable medium may include, but is not limited to, floppy diskettes, optical disks, CD-ROMs, and magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, magnet or optical cards, flash memory, or other type of media/machine-readable medium suitable for storing electronic instructions. Moreover, the present invention may also be downloaded as a computer program product, wherein the program may be transferred from a remote computer (e.g., a server) to a requesting computer (e.g., a client) by way of data signals embodied in a carrier wave or other propagation medium via a communication link (e.g., a modem or network connection). Accordingly, herein, a carrier wave shall be regarded as comprising a machine-readable medium.

[0035] Importantly, while embodiments of the present invention will be described with reference to an exemplary C++ implementation, the method and apparatus described herein are equally applicable to other types of software, hardware, and hybrid implementations.

[0036] Terminology

[0037] Before describing the context in which various embodiments of the present invention may be employed, some terms that will be used throughout this application will briefly be defined.

[0038] A “class” typically defines data, data types, and operations on the data. The realization of a specific case of a class or classes is an instance of the class or classes which is referred to as an “object.”

[0039] According to one embodiment, a class comprises the definition of one or more “program elements” including an engine, control flow information, and one or more member functions.

[0040] An “engine” is code that dynamically determines the “execution flow” of a software program by navigating through the control flow structure of the program element.

[0041] The control flow structure of a program element is typically defined in terms of centralized control flow information comprising one or more collections of states, referred to as “rules.” Each state may include information indicative of desired behavior and/or desired state transitions. Although embodiments of the present invention will be described with reference to a particular table structure referred to as the Coherent Object Table (COTable), no particular organization of the control flow information is required in terms of data structure. Various other data structures, such as databases of relational data, tree structures, linked lists, and the like, may be employed. In the past, control flow information has resided in the code segment of a software program and was therefore static. However, according to one embodiment of the present invention, control flow information may reside in the data segment of a software program thereby allowing it to be modified during run-time.

[0042] In contrast to the relatively static control flow information, “execution flow” refers to the dynamic flow of execution during run-time. That is, execution flow is what happens during run-time, e.g., the actual paths taken through the various branches of the software program code.

[0043] Objects or their program elements may communicate with each other preferably by a “member function” of one calling the engine of another. Member functions are routines that implement the behavior associated with a particular state. According to one embodiment, member functions are invoked by an associated control flow engine by way of the control flow information. For example, the address of the desired member function may be dynamically bound based upon the current status of the execution of a software program. Alternatively, the control flow information may be statically bound. For example, the control flow information may comprise a virtual table (v-table) containing the addresses of the member functions.

[0044] “Status” typically refers to dynamic state information. For example, information concerning the condition or circumstances of the software program, e.g., current status, or an engine, e.g., engine status, at a particular instance in time. Hereinafter, “current status” will refer to the current status of the software program being directed unless otherwise indicated.

[0045] The meaning of the term “state” depends upon the context of its usage. In the context of a variable, e.g., expected state, state refers to a relatively static indication of the condition or circumstances of an engine or the software program. In contrast, when used with reference to a table of control flow information, such as a COTable, a state refers to a table entry, e.g., a row or column of the table.

[0046] An “attribute” of a state is information associated with the state. For example, in the context of a COTable, an attribute is an element of a table entry, e.g., a behavior, an expected state, a trace value, next state, the address of a behavior, the ordinal of the next state, etc.

[0047] “Binding” commonly refers to the resolution of addresses in a software program. Herein, the phrase “dynamic binding” refers to repeated binding that takes place during run-time as opposed to during the linking and loading stages of software generation, for example, when source code is converted into executable software. According to one embodiment dynamic binding is achieved by allowing a run-time execution engine to execute out of the data segment of the executable software program.

[0048] “Context Free” as it is used herein refers to the control flow engines being independent of the particular software program that they direct. That is, no application information is embedded in the control flow engines. All information for directing the execution flow of the software program is preferably contained within the control flow information and/or the member functions.

[0049] Overview: Transformation of a Problem Statement into Executable Software

[0050] While not limited to the field of automatic code generation, various aspects of the present invention are particularly useful in connection with achieving this objective/goal. Therefore, to put the present invention in context, it may be helpful to describe the process of transforming a problem statement/specification into executable software with reference to FIG. 2. At step 210, problem or process modeling is performed. In order to create a solution to a problem, or to automate a process, there must first typically be a clear statement of the problem or process. The problem/process statement should enumerate all processing procedural requirements and associated information relevant to the problem and necessary to perform the processing. An exemplary problem specification is illustrated in Appendix A. Tools are currently available for some problem domains that can automate the specification of a problem or process model. However, the use of such tools is not necessary to achieving automated code generation nor is it necessary to utilization of embodiments of the present invention.

[0051] At step 220, the model generated during step 210 may be translated into a Standard Canonical Form (SCF) to describe the problem or process as a grammar, or set of rules. According to one embodiment, the SCF is Backus-Naur Form (BNF) also referred to as Backus-Normal Form. An exemplary BNF specification is illustrated in Appendix B.

[0052] At step 230, the SCF is translated into a control flow architecture that defines the flow of control for the software program. Importantly, generation of an SCF, such as BNF is not required. Many other ways of generating the control flow architecture, both automated and manual exist. For example, a classical state table approach, such as used in circuit design, may be employed. In any event, the means by which the control flow architecture is generated is of little consequence so long as a logically coherent and consistent representation can be produced. As will be discussed in more detail below, the control flow architecture may be defined in terms of a centralized data structure. Preferably, the centralized data structure allows run-time navigation by a run-time execution engine.

[0053] In alternative embodiments, control flow architecture generation need not take place. Rather, the SCF may be translated into one of several different forms, such as a compiler for converting high-level programming language statements into machine-readable object code. Also, the control flow architecture may be manually generated.

[0054] In general, code may be created for use on a variety of platforms or targeted for a particular platform. At step 240, machine dependent code is generated. For example, data representing the control flow architecture and sequences of instructions for navigating the control flow architecture may be compiled, linked and loaded with a development tool set for execution on a particular processor architecture. Alternatively, at step 250, interpreted code may be generated. Regardless of the type of code, executable code or interpreted code, control flow may be dynamically bound to the software program components at run-time during step 260.

[0055] The focus of the present application will be on various elements of a software program, embedded hardware controller, or hybrid that accomplish step 260. However, it is important to note that various aspect of the present invention are useful completely separate and apart from automatic code generation and execution. For example, COSA may be used to enforce one or more desirable software engineering disciplines or methodologies thereby enforcing good coding practices and facilitating program correctness and the generation of error-free code to be generated.

[0056] Current software engineering methodologies tend to focus primarily on gathering information about the project to be developed. The information is sorted and ordered into models and a requirements document. The model and requirements document are then “thrown over the wall” to the development team. While the development team may employ a set of standards for writing the code, typically each programmer creates an independent architectural structure in their own style. Consequently, ten ad hoc developers will produce ten different coding styles for the same problem.

[0057] COSA places the emphasis on subject matter knowledge, e.g., telling the story of how the business works, and structure rather than technical knowledge. The format of the requirements document is dictated by the structure of the control flow information, e.g., the Coherent Object Table. In this manner, COSA may serve as an enforcement mechanism for good coding practices. Exemplary software engineering rules for COSA are illustrated in Appendix C.

[0058] As will be discussed further below, a COTable may contain two or more columns and as many rows as the problem's solution requires. COSA also specifies the structure of a novel run-time execution engine, referred to as the control flow engine, which provides iterative control for the software program and the rules for implementing member functions, e.g., Coherent Object Members.

[0059] An Exemplary Computer System

[0060] Having briefly described the context in which the present invention may be employed, an exemplary machine in the form of a computer system 300 in which features of the present invention may be implemented will now be described with reference to FIG. 3. Computer system 300 comprises a bus or other communication means 301 for communicating information, and a processing means such as processor 302 coupled with bus 301 for processing information. Computer system 300 further comprises a random access memory (RAM) or other dynamic storage device 304 (referred to as main memory), coupled to bus 301 for storing information and instructions to be executed by processor 302. Main memory 304 also may be used for storing temporary variables or other intermediate information during execution of instructions by processor 302. Computer system 300 also comprises a read only memory (ROM) and/or other static storage device 306 coupled to bus 301 for storing static information and instructions for processor 302.

[0061] A data storage device 307 such as a magnetic disk or optical disc and its corresponding drive may also be coupled to computer system 300 for storing information and instructions. Computer system 300 can also be coupled via bus 301 to a display device 321, such as a cathode ray tube (CRT) or Liquid Crystal Display (LCD), for displaying information to a computer user. For example, a GUI may facilitate problem or process modeling or results of executing an automatically generated software program may be presented on the display device 321.

[0062] Typically, an alphanumeric input device 322, including alphanumeric and other keys, is coupled to bus 301 for communicating information and/or command selections to processor 302. Another type of user input device is cursor control 323, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 302 and for controlling cursor movement on display 321.

[0063] A communication device 325 is also coupled to bus 301 for providing access from/to clients/servers via the Internet, for example. The communication device 325 may include a modem, a network interface card, or other well known interface devices, such as those used for coupling to Ethernet, token ring, or other types of networks. In any event, in this manner, the computer system 300 may be coupled to a number of clients/servers via a conventional network infrastructure, such as an enterprise's Intranet (e.g., WAN) and/or the Internet, for example.

[0064] The present invention is related to the use of computer system 300 to direct the execution of a software program that is manually or automatically generated using a particular set of disciplines discussed herein. As computer system 300 executes the software program, the processor 302 may access control flow information stored in a COTable within main memory 304, ROM 306, or other storage device to determine the desired control flow of the software program. Importantly, the present invention is not limited to having all engines, control flow information, or member functions located on the same computer system. Rather, individual objects, program elements, or portions thereof may be spread over a distributed network of computer systems. Additionally, it is appreciated that a lesser or more equipped computer system than the example described above may be desirable for certain implementations. Therefore, the configuration of computer system 300 will vary from implementation to implementation depending upon numerous factors, such as price constraints, performance requirements, and/or other circumstances. For example, according to one embodiment of the present invention, an embedded controller may comprise only a processor and a memory for storing static or dynamically loaded instructions and/or data.

[0065] An Exemplary Software Program Architecture

[0066] FIG. 4 conceptually illustrates the components of a software program 400 according to one embodiment of the present invention. A software program may be specified in terms of a collection of control flow and data flow information. According to this example, this information is distributed among one or more classes 410. The classes 410 typically define a collection of data and the routines that act on the data. In this example, the routines and data may be represented by one or more program elements 420. Each program element further includes an engine 430, control flow information 440, and one or more member functions 450. Briefly, as will be discussed further below, the engine 430 may cause a particular execution flow as a result of control flow defined by the control flow information 440. In addition, data flow may be provided by the member function(s) 450.

[0067] According to one embodiment, the engine 430 serves as a driver or main loop providing iterative control for the software program and implementing the rules for determining whether or not to invoke member function(s) 450 based upon the control flow information 440.

[0068] In one embodiment of the present invention, the software program 400 may be implemented as a table-driven method that allows information to be looked up in a data structure, such as a multi-dimensional lookup table or a database of relational information, rather than using logic statements, such as if-then-elses and switch-case statements. As will be described further below, in this manner, code size can be greatly reduced and increased run-time efficiency can be achieved.

[0069] At any rate, the engine 430 may interface with the control flow information 440 to receive information about a rule associated with the current execution status of the software program 400. Based upon the rule and its relationship with the current execution status of the software program, the flow of execution and flow of control of the software program may be determined.

[0070] The control flow information 440 may additionally provide the engine 430 with information for direct and/or indirect access to the member function(s) 450. For example, as one feature of the present invention, the control flow information may comprise a table of addresses of member functions thereby providing the engine 430 with access to the member function(s) 450 through dynamic bindings at run-time.

[0071] The member function(s) 450 are routines that may implement behavior(s) associated with a particular state of the software program 400. The member function(s) also provide data flow. By way of illustration, the member function(s) 450 may perform state testing and updating state information associated with the execution of the software program 400.

[0072] According to one embodiment, member function(s) are invoked by the engine 430 by way of the control flow information 440. For example, the control flow information may include addresses of one or more of the member function(s) 450 and the address of the appropriate member function may be bound at run-time (e.g., true dynamic binding) based upon the status of execution of the software program. Alternatively, traditional static binding approaches may be employed in which case the control flow information 440 may comprise a virtual table (v-table) containing the addresses of one or more of the member function(s) 450. The member function(s) 450 may also provide status to the engine 430 by returning such information through the class structure, for example. As will be described further below, as an additional feature of the present embodiment, member function(s) 450 may optionally modify the control flow information 440 thereby affecting the future flow of the software program. Finally, it is important to understand that (instances of) classes 410 or their program elements 420 may communicate with each other. While, in terms of good coding practices, it may be preferable to limit such communication to a member function 450 of one (instance of) a class 410 calling the engine 430 of another, in alternative embodiments, this communication may be between any two program elements 420. For example, the control flow information 440 of one class 410 may specify a member function of another class 410, an engine 430 of one class 410 may invoke an engine 430 of another class 410, etc. Further details regarding the engine 430, the control flow information 440, and the member function(s) 450 are be provided below.

[0073] The use of state objects provides for reentrancy. That is, state objects allow the instantiation and dynamic assignment of new and different control flow information 440 to new state objects at run-time, while permitting continuing use of previous control flow information 440 for existing state objects.

[0074] Exemplary Control Flow Information Representation

[0075] FIG. 5A conceptually illustrates control flow information components according to one embodiment of the present invention. According to this example, the control flow architecture 510 is represented as a plurality of rules. The rules may be contained in any of a number of possible data structures. For example, the rules may be stored as elements of a multi-dimensional lookup table or may be distributed among two or more lookup tables. Importantly, the table entries themselves may be simple or complex data types. Alternatively, the rules may be stored as part of a database of relational information, such as a relational database.

[0076] In any event, each rule in turn may be represented as a collection of one or more states. The state defines possible behaviors and subsequent states. According to the embodiment depicted, each state has seven attributes: (1) an ordinal rule name, (2) an expected state, (3) a true next state, (4) a false next state, (5) a true behavior, (6) a false behavior, and (7) a trace value. The ordinal rule name is a unique ordinal identifier which identifies the position of the rule in the control flow architecture 510 and facilitates human-readability of the data structure or structures containing the control flow information.

[0077] The expected state is a state which the execution of the software program is expected to achieve before the true behavior will be carried out. Evaluation of the rule includes evaluating the relationship between the expected state and the current status of the execution of the software program.

[0078] The true next state identifies the next ordinal rule to which the software program should transition if evaluation of the rule is true. The false next state identifies the next ordinal rule to which the software program should transition if evaluation of the rule is false.

[0079] The true behavior identifies the action or behavior that is to be carried out if the rule evaluation is true. The false behavior identifies the action or behavior that is to be carried out if the rule evaluation is false. Preferably, the actions or behaviors comprise subroutine calls or method invocations to routines which perform the desired actions. In addition, an attempt is made to keep parameter passing to a minimum. Preferably, no parameter data is passed in subroutine calls or method invocations. Rather, as discussed further below, to minimize the coupling among subroutines or methods, data is communicated by way of the class structure.

[0080] The trace value provides information about the execution of each state/rule. This trace information may be used if tracing of state transitions is desired, typically for debugging or performance analysis. When tracing is activated (an execution option), the control flow engine captures the trace information associated with each state to which a transition is made. Importantly, this method of trace implementation obviates the need for tracing tools, and thereby eliminates the potential to perturb the software program when tracing is in effect.

[0081] It is contemplated that several alternative organizational formats of the control flow information may be employed. Therefore, the organization of the control flow information, in terms of the number of attributes, ordering of the attributes, the meaning and content of the attributes, distribution of attributes among various data structures, etc., may be other than that depicted in the examples herein.

[0082] FIG. 5B illustrates a more generalized view of control flow information of FIG. 5A. In this example, the content of the control flow information is generally the same except that N different next states are possible and N different behaviors are possible. For example, a tri-state COTable may include three possible next states, each with a corresponding transition action or behavior.

[0083] As will be illustrated, alternative embodiments may exclude various attributes or include additional attributes. For example, trace values may be excluded from a final product after software testing is completed, if tracing is not needed. In addition, specification of desired behavior may be associated with only a subset of possible rule evaluations. For example, a behavior may be associated with either a true evaluation condition or a false evaluation condition, but not both. Other alternative implementations might be motivated by a variety of considerations, such as final object code size or performance.

[0084] Exemplary Run-Time Processing

[0085] FIG. 6 is a flow diagram illustrating run-time processing according to one embodiment of the present invention. According to the present example, a control flow engine may direct the execution flow of a software program based upon the current state of execution of the software program and control flow information. As will be emphasized further below, in one embodiment, the control flow engine is context free. That is, the control flow engine is independent of the particular software program that is being directed. In this manner, the same or similar run-time execution engine may be reused with various other sets of control flow information. In one embodiment, the steps described below may be performed under the control of a programmed processor, such as processor 302. However, in alternative embodiments, the steps may be fully or partially implemented by any programmable or hardcoded logic, such as Field Programmable Gate Arrays (FPGAs), TTL logic, or Application Specific Integrated Circuits (ASICs), for example.

[0086] At step 610, an initial status of the execution of the software program is determined and initial engine status is determined. According to one embodiment, initialization may be achieved by the caller of the engine. In alternative embodiments, initial status values may be predetermined.

[0087] At step 620, the engine status is queried. If the engine status indicates the engine is to continue running, then processing proceeds to step 630. Otherwise, if the engine status indicates the engine is to stop executing, then run-time processing for this engine terminates. Many possible mechanisms are available for terminating the engine. By way of example, the engine may take the form of a loop which continues so long as the engine status satisfies a predetermined conditional relationship. In this manner, one or more of the member functions may signal the engine to terminate by modifying the engine status. Alternatively, an interrupt may be employed to signal the engine. For example, the engine may continue indefinitely until an interrupt handler is triggered by a terminate interrupt.

[0088] At step 630, a determination is made if a conditional relationship is satisfied between the current status of execution of the software program and the expected status of the software program. Assuming the control flow information has the form illustrated by FIG. 5A, the value of expected state associated with the current rule/state may be compared to the current status of execution of the software program. According to this example, if the current status is equal to the expected status, then processing continues with step 640; otherwise processing continues with step 660. As should already be apparent with reference to FIG. 5B, the conditional relationship evaluated at step 630 is not limited to choosing one of two branches, such as the yes/no result show in FIG. 6. In alternative embodiments, evaluation of the conditional relationship may select more than two options. For example, the conditional relationship may be expressed as <,=, or >, in which case one of three behaviors could be selected based upon the result.

[0089] Returning to the present example, at step 640, the true behavior is performed. Subsequently, during step 650, the software program transitions from the current state to the true next state. Of course, in alternative embodiments, the order of performance of the behavior and the state transition could be interchanged. However, because the behavior might depend upon the current status, it is preferable to transition after the behavior has been completed. It should be noted that the behavior may alter one or both of the engine status and the software program's current execution status. Additionally, the behavior may include modification of the control flow information. In any case, after step 650, processing returns to step 620 where it is determined whether or not to perform another iteration of the engine.

[0090] At step 660, the false behavior is performed. Subsequently, during step 670, the software program transitions from the current state to the false next state. As above, in alternative embodiments, the state transition may occur before performing the false behavior. Also, as explained above, the false behavior may include modification of the control flow information. After step 670, processing returns to step 620 where it is determined whether or not to perform another iteration of the engine.

[0091] In alternative embodiments, if tracing of state transitions is desired, trace information may additionally be provided in the control flow information for each state. Then, each iteration of the control flow engine, the control flow engine, may capture the trace information associated with each state to which a transition is made. This trace processing may be performed prior to performing the behavior, after performing the behavior and prior to the transition to the next state, or after the transition. Advantageously, in this manner, there is no need for traditional tracing tools, which have the potential to perturb the software program.

[0092] Alternative Control Flow Information Representations

[0093] FIGS. 7A, 7B, 7C, 7D, and 7E conceptually illustrate control flow information components according to alternative embodiments of the present invention. As the preferred complete set of attributes has been described in detail above with reference to FIGS. 5A and 5B, only the differences will be briefly pointed out.

[0094] In the exemplary control flow information representation of FIG. 7A, a two attribute state is employed. Only information indicative of desired behavior is included in the control flow information. If needed, expected state and desired control flow can be maintained elsewhere, such as in the control flow engine or member functions.

[0095] FIG. 7B illustrates an alternative subset of control flow information which includes only information indicative of desired true behavior and desired true control flow. This representation may be useful in situations where the desired false behavior is to take no action or situations in which the desired false next state may be represented by a simple expression based upon the current state. For example, the desired false next state may simply be the state stored subsequent to the current state in the COTable.

[0096] According to the example of FIG. 7C, state attributes include: an expected state, a true next state, a true behavior, and a false behavior. As in the example of FIG. 7B, the false next state may be readily determined with reference to a simple expression.

[0097] FIG. 7D includes all the state attributes of FIG. 5A with the exception of trace information.

[0098] FIG. 7E includes all the state attributes of FIG. 5A with the exception of trace information and the ordinal rule name, which is provided in FIG. 5A merely as a convenience for readability.

[0099] Exemplary Table-Based Control Flow Information Implementation

[0100] FIG. 8 is an exemplary implementation of control flow information 800 according to one embodiment of the present invention. In this example, the control flow information 800 comprises a two-dimensional table. The table's rows are rules/states and the columns are attributes of the rules/states. Although the order of appearance within the table has been slightly modified, this example includes each of the state attributes described above with reference to FIG. 5A.

[0101] One aspect of the present invention illustrated by this example is the novel mechanism employed to initialize an array of dissimilar elements. At line 15, an expansion macro is defined that substitutes what looks to be a function definition with the parameter list of the function. The table, beginning at line 17, is then fooled into believing it comprises an array of functions. Subsequently, however, each occurrence of:

[0102] Cs(<Rule>,<State>,<TMemr>, <TRule>,<FMem>,<FRule>,<TraceVal>)

[0103] is replaced with:

[0104] <Rule>, <State>,address₁,address₂, address₃, address₄, <TraceVal>

[0105] Where: address₁, is the address of the true member function that performs the true behavior; address₂is the address/index of the true next state to which the software program transitions after determining that the expected state meets a predetermined relationship with the current state of execution of the software program; address₃is the address of the false member function that performs the false behavior; and address₄is the address/index of the false next state to which the software program transitions after determining that the expected state does not meet the predetermined relationship with the current state of execution of the software program. Importantly, the addresses are automatically calculated during the macro expansion as a result of this novel table definition. Advantageously, as will be discussed further below, control flow information defined in this manner allows run-time modification of the software program's control flow without the need for recompilation and additionally allows execution out of the executable software program's data segment.

[0106] According to the embodiment depicted, naming conventions seek to improve the readability and understandability of the structure and logic of the software program. In addition, the novel naming conventions help avoid naming conflicts. As a result, the naming conventions are expected to facilitate automated code generation. In this example, there is consistency in the prefixes of names of variables, objects, states, etc. Table 1 illustrates the meaning of the particular prefixes according to the present example.

[0107] Although correct software can be generated without adhering to strict naming conventions, such software tends to be more difficult to maintain and modify.

[0108] Evolution of a Control Flow Engine

[0109] The exemplary control flow engine illustrated in the code listing of Table 2 consists of loop control and status testing of the current state. As an example, a single loop control with a single status test is shown in the next section, although these are not to be limited, and are dictated by the problem to be solved. An important aspect to understand about COSA control flow engines, to maximize coherency, the control flow engine should replace all control flow if-then-else and switch-case statements. Preferably, if-then-else statements and switch-case statements are only included in control flow engines. In this manner, all of the logic and all of the traversal code is handled by the control flow engines and the control flow information, e.g., the Coherent Object Table. The following engine replaces more lines of code than there are rows in the COTable, on a typical large project this can mean the reduction of several thousand lines of code.

[0110] According to the example depicted by Table 2, the Engine State (line 1) is initialized to true to start the engine running. Engine is an element of this class and can be turned off by any appropriate member function and depending on how Engine is inherited it may be turned off by sibling objects. The Rule name (line 3) is initially set to zero or a valid value created by the parent of this object engine. Status (line 3) is similar to Engine when it comes to access privileges, the application will dictate these privileges. Status may be determined and set within each member function for use by the control flow engine during the next Status vs. State test. The True Function (line 5) is called when the Status is equal to the State for this Rule name. Upon return for the true member, the next Rule name (line 6) is selected from the current True Rule name. When Status is not equal to the current Rule name State, the else condition is executed and the process continues until the Engine is turned off by one of the terminating member functions.

[0111] In the prior art, control flow logic that is context dependent (e.g., related to the particular application) is used to make the decision about whether an execution path will be taken or not. However, according to the preferred COSA implementation, control flow decisions are made by the main loop, the control flow engine, or passed to a subordinate engine. That is, application specific information is sought to be removed from the engine.

[0112] This next section will describe how most code is written today. However, the code will be placed in the context of a basic preferred control flow engine format. In this manner, the ad hoc code's actions may be more easily compared and contrasted to the COSA implementation and the evolution to COSA will be made more clear.

[0113] Inside the mechanism for stopping the process (the while engine is true) the Status is tested to see if it is equal to the State, if that is true, then the True member function is executed at this rule name and the next rule name pointer is setup. If the Status is not equal to the State, then the next rule name pointer skips to the next sequential rule name. Line 6 of the code fragment of Table 3 limits this kind of coding to the cascade in the model when the expected state is false. Line 4 in the code fragment is equivalent to a <goto> Statement allowing the code traversal to other than a sequential thread created by line 6. In reality, line 4 provides the index for the next virtual table (v-table) entry.

[0114] The code fragment of Table 2 is equivalent in functionality to a coding sequence of if Statements shown in the code fragment of Table 4.

[0115] By adding a False rule name column as shown in the code fragment of Table 5, line six now allows the model to have a peer alternative control flow but not an associated member function.

[0116] The additional control provided by adding the False rule name column is to having a ‘go to’ Statement in every if and else Statement in the traditional traversal code shown in Table 5. The False rule name column is the else goto ordx; Statement.

[0117] While the code fragment of Table 6 provides additional control and better representation with the Cognitive Model it is not complete because there is usually additional work that can be done when a True or False condition exists in a State. To gain the maximum benefit in the False State another column may be added, e.g., False Rule Name.

[0118] This last code fragment in Table 7 allows the model to represent activities that can cascade, proceed or call down to lower levels of activity, and have peer activities that can be executed during the same state.

[0119] Exemplary Control Flow Engine Implementation

[0120] FIG. 9 is an exemplary implementation of a control flow engine according to one embodiment of the present invention. This example is similar to that described above with reference to the last code fragment in Table 7. However, in addition, rule initialization and initialization of both the software program state and the engine state are performed (lines 2-4). Also, tracing of state transitions is performed (lines 7 and 11). As one feature of the embodiment depicted, the address of the desired member function, i.e., TrueMember or FalseMember, may be dynamically bound during each iteration of the control flow engine 900 at line 8 or 12 depending upon the current status of the execution of the software program, i.e., sToken. The member function addresses in the expressions of lines 8 and 12 are treated like data until these lines are evaluated at run-time. When one of the expressions is evaluated, the address of the appropriate member function is read out of the control flow information 440 into a register and then execution flow of the software program branches to that member function. Some very powerful features result from this form of dynamic binding (execution out of the data segment). For example, the control flow information 440 may be dynamically modified during run-time without the need for recompilation.

[0121] Exemplary Member Function Implementations

[0122] FIG. 10 illustrates exemplary member functions according to one embodiment of the present invention. As one feature of the present embodiment, an attempt is made to minimize coupling among subroutines or methods by using the class structure to communicate rather than parameter lists. As another feature of the present embodiment, an attempt is made to maximize cohesion by performing related operations within a member function. In this example, member functions perform the strongly related operations of the desired behavior and additionally cause the software program to transition from the current state to the next state.

[0123] True Dynamic Binding

[0124] FIG. 11 conceptually illustrates where various program elements reside in the code and data segments 1110 and 1120, respectively, of an executable software program 1100 according to one embodiment of the present invention. Executable software 1100 includes a code segment 1110 and a data segment 1120. The code segment 1110 contains compiled machine instructions in a non-modifiable portion of the executable software's address space. In contrast, the data segment 1120 typically contains data that may be freely updated by the instructions in the code segment 1110. According to one embodiment, the compiled machine instructions, engine instructions 1130 and member function instructions 1150 associated with the control flow engines 430 and the member functions 450, respectively, reside in the code segment 1110. However, the control flow information data 1140 resulting from the compilation of the control flow information 440 is stored in the data segment 1120. As a result, true dynamic binding may be achieved because the control flow engine 430 may execute routines whose addresses are specified as data in the data segment 1120. This means that the software program's execution flow may be dynamically altered during run-time by allowing the control flow engine 440 to effectively execute out of the data segment 1120.

[0125] Improved Java Virtual Machine

[0126] The final executable software of a COSA application can take many forms. One embodiment is executable object code, generated with an industry-standard code generation tool, such as a C++ compiler, which links the compiled subroutine calls or method invocations with library functions that accomplish the specific actions. An alternative embodiment is the generation of control flow information which includes interpretable subroutine or method references, similar to the pseudo-code of Pascal language compilers or BASIC language interpreters. The control flow engine, then dynamically translates the references to subroutine calls or method invocations within the control flow engine. As an example, in a Java environment, one or more COTables could be translated into Java objects. For its part, the control flow engine could be implemented in Java or any other implementation language.

[0127] Another alternative embodiment may include COTable entries that are dynamically linked subroutine calls or method invocations to actual subroutines or methods by the control flow engine. In this embodiment, there is not interpretation in the sense of run-time parsing or token evaluation, which results in performance improvement over existing interpretive execution engines. For example, the assignee of the present invention has implemented a prototype Java virtual machine, the COSA Virtual Machine (CVM). In one embodiment, CVM includes one or more COTables populated with compiled bytecodes (compiled executable code). The COTables may be manually or automatically generated. For example, the COTables may be automatically generated by translating bytecodes into executable code the first time they are encountered and loading them into the one or more COTables. Subsequently, when the same bytecodes are encountered again, the bytecode may be executed from the previously generated executable code in the COTables. In this respect, the CVM may be though of as a “bytecode executer” rather than a typical bytecode interpreter. Consequently, a platform independent virtual machine that runs at compiled speeds may be achieved. An exemplary control flow engine, member functions, and COTable for a CVM is attached in Appendix D. In one embodiment, the CVM may run under the control of a programmed processor, such as processor 302. However, it is contemplated that the CVM may be embodied in an embedded controller comprising a processor and a memory for storing static or dynamically loaded instructions and/or data. Alternatively, the CVM may be fully or partially implemented by any programmable or hardcoded logic, such as Field Programmable Gate Arrays (FPGAs), TTL logic, or Application Specific Integrated Circuits (ASICs), for example.

[0128] In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.