Automatically generating a program

• US 6,405,361 B1
• Filed: 08/19/1999
• Issued: 06/11/2002
• Est. Priority Date: 08/20/1998
• Status: Expired due to Term

• Current Assignee: Krüger, Ingolf, Manfred Broy, Radu Grosu
• Original Assignee: Krüger, Ingolf, Manfred Broy, Radu Grosu
• Inventors: Grosu, Radu, Krüger, Ingolf, Broy, Manfred
• Primary Examiner(s): Chaki, Kakali
• Application Number:
  US09/378,204
• Time in Patent Office: 1,027 Days
• Field of Search: 717/1, 717/2, 717/4, 714/35, 714/36, 714/38, 714/45, 703/27, 370/261, 379/205.01, 455/426, 455/416, 455/67.1
• US Class Current: 717/104
• CPC Class Codes: G06F 8/10 Requirements analysis; Specification techniques
• CPC Class Codes: G06F 8/30 Creation or generation of source code

Abstract

A method, an apparatus and a computer program product are described for automatically generating a state-based program for a component of a system consisting of a plurality of components communicating with each other, wherein the program is generated from a specification of the system, the specification comprising interaction-based sequence descriptions of the system. According to the present invention, all sequence descriptions of said component are determined, the sequence descriptions are normalized, a state-based specification of said component is determined from the normalized sequence descriptions, and the state-based program for the component is determined from the state-based specification. The present invention facilitates the process of program development since the costly, manual development of a state-based program from the specification of a system is automated at least to a substantial degree.

Claims

1. A method for automatically generating a state-based program for a component of a system consisting of a plurality of components communicating with each other, wherein said program is generated from a specification of said system, said specification comprising interaction-based sequence descriptions of said system, said method comprising the steps of:

a) determining all sequence descriptions of said component defined by said specification of said system,

b) normalizing said sequence descriptions of said component such that a normalized sequence description comprises exactly one initial condition and exactly one final condition and, between said initial condition and said final condition, communication actions only,

c) determining a state-based specification of said component by identifying all equal initial and final conditions of said normalized sequence descriptions of said component with a single state, and

d) determining said state-based program for said component, wherein each sequence description contained in said state-based specification of said component is replaced by a sequence of said communication actions of this sequence description, separated by additionally inserted states.

2. The method of claim 1, wherein in step a) each sequence description of said system concerning said component is limited to a corresponding sequence description of said component.

3. The method of claim 1, wherein step b) comprises the following sub-steps:

b1) inserting a condition prescribed in said specification of said system as an initial condition into each of those sequence descriptions of said component that begin with a communication action,

b2) inserting a condition prescribed in said specification of said system as a final condition into each of those sequence descriptions of said component that end with a communication action, and

b3) splitting all sequence descriptions of said component having more than two conditions into a plurality of sequence descriptions of said component, each of the split sequence descriptions having exactly two conditions.

4. The method of claim 3, wherein at least one of sub-steps b1) and b2) is/are repeated for each of a plurality of conditions to be inserted in order to obtain a corresponding number of sequence descriptions of said component.

5. The method of claim 1, wherein said interaction-based sequence descriptions of said system are represented by at least one of Message Sequence Charts and UML sequence diagrams.

6. The method of claim 1, wherein said state-based program for said component is represented by an automaton.

7. The method of claim 6, wherein said automaton is one of an SDL automaton and a Statechart automaton and a ROOM automaton.

8. The method of claim 1, wherein said state-based program is based on an extended state automaton whose state space comprises a control state and a data state, and wherein state transitions are performed depending on the current data state and are adapted to change this data state.

9. The method of claim 1, wherein step d) comprises the step of removing ε

-transitions from said state-based program.

10. The method of claim 1, wherein a deterministic state-based program is generated in step d).

11. The method of claim 1, further including a step of optimizing said state-based program generated in step d).

12. The method of claim 11, wherein the optimization is performed with respect to the number of states.

13. The method of claim 1, wherein non-local conditions in said sequence descriptions of said system are replaced in step a) by local conditions in accordance with a predetermined surjective mapping.

14. The method of claim 1, wherein the method is used for at least one of generating a state-based program for a telecommunication application and generating a state-based program for providing an error tolerant communication of data and generating a state-based program for providing an error tolerant communication of messages and generating a state-based program for a reactive system and generating a state-based program for a control system and generating a user interface program and generating a data base query schema program.

15. An apparatus for automatically generating a state-based program for a component of a system consisting of a plurality of components communicating with each other, wherein said program is generated from a specification of said system, said specification comprising interaction-based sequence descriptions of said system, said apparatus comprising a general purpose computer programmed for executing the steps of:

a) determining all sequence descriptions of said component defined by said specification of said system,

b) normalizing said sequence descriptions of said component such that a normalized sequence description comprises exactly one initial condition and exactly one final condition and, between said initial condition and said final condition, communication actions only,

c) determining a state-based specification of said component by identifying all equal initial and final conditions of said normalized sequence descriptions of said component with a single state, and

d) determining said state-based program for said component, wherein each sequence description contained in said state-based specification of said component is replaced by a sequence of said communication actions of this sequence description, separated by additionally inserted states.

16. The apparatus of claim 15, wherein step b) comprises the following sub-steps:

b1) inserting a condition prescribed in said specification of said system as an initial condition into each of those sequence descriptions of said component that begin with a communication action,

b2) inserting a condition prescribed in said specification of said system as a final condition into each of those sequence descriptions of said component that end with a communication action, and

b3) splitting all sequence descriptions of said component having more than two conditions into a plurality of sequence descriptions of said component, each of the split sequence descriptions having exactly two conditions.

17. The apparatus of claim 15, wherein said apparatus is used for at least one of generating a state-based program for a telecommunication application and generating a state-based program for providing an error tolerant communication of data and generating a state-based program for providing an error tolerant communication of messages and generating a state-based program for a reactive system and generating a state-based program for a control system and generating a user interface program and generating a data base query schema program.

18. A computer program product for execution by a general purpose computer for automatically generating a state-based program for a component of a system consisting of a plurality of components communicating with each other, wherein said program is generated from a specification of said system, said specification comprising interaction-based sequence descriptions of said system, said computer program product including instructions for making said general purpose computer perform the steps of:

a) determining all sequence descriptions of said component defined by said specification of said system,

b) normalizing said sequence descriptions of said component such that a normalized sequence description comprises exactly one initial condition and exactly one final condition and, between said initial condition and said final condition, communication actions only,

c) determining a state-based specification of said component by identifying all equal initial and final conditions of said normalized sequence descriptions of said component with a single state, and

d) determining said state-based program for said component, wherein each sequence description contained in said state-based specification of said component is replaced by a sequence of said communication actions of this sequence description, separated by additionally inserted states.

19. The computer program product of claim 18, wherein step b) comprises the following sub-steps:

b1) inserting a condition prescribed in said specification of said system as an initial condition into each of those sequence descriptions of said component that begin with a communication action,

b2) inserting a condition prescribed in said specification of said system as a final condition into each of those sequence descriptions of said component that end with a communication action, and

b3) splitting all sequence descriptions of said component having more than two conditions into a plurality of sequence descriptions of said component, each of the split sequence descriptions having exactly two conditions.

20. The computer program product of claim 18, said computer program product being used for at least one of generating a state-based program for a telecommunication application and generating a state-based program for providing an error tolerant communication of data and generating a state-based program for providing an error tolerant communication of messages and generating a state-based program for a reactive system and generating a state-based program for a control system and generating a user interface program and generating a data base query schema program.