Method for using a data flow net to specify and assemble computer software

• US 6,694,505 B1
• Filed: 12/07/1999
• Issued: 02/17/2004
• Est. Priority Date: 11/25/1999
• Status: Expired due to Fees

• Current Assignee: Kim Seng Holdings Pte Ltd.
• Original Assignee: Kim Seng Holdings Pte Ltd.
• Inventors: Tan, Hee Beng Kuan
• Primary Examiner(s): Zhen, Wei
• Assistant Examiner(s): DAS, CHAMELI
• Application Number:
  US09/457,107
• Time in Patent Office: 1,533 Days
• Field of Search: 717/100, 717/101, 717/107, 717/114, 717/104, 717/102, 717/103, 717/116, 709/318, 709/332, 709/331, 709/315, 710/2, 710/3, 710/20, 710/30
• US Class Current: 717/100
• CPC Class Codes: G06F 8/70 Software maintenance or management
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A method for specifying computer software called the Data Flow Net (“DF Net”) which enables the reusability of portions of the software. Computer software is specified by combining sets of code fragments which implement some coherent functionalities. A method to represent a set of code fragments is provided. A method for combining sets of code fragments specified according to the DF Net method is described. A method for transforming software specified according to the DF Net method into executable instructions is further provided.

Claims

1. A method for specifying computer software comprising:

designating a source procedure;

designating a plurality of hierarchical dependencies;

for each of a plurality of transitions, designating

(i) at least one input place and at least one output place from a plurality of places, wherein the transition produces said at least one output place from said at least one input place, and wherein said at least one input place is a main input place,

(ii) a process including a set of reference procedures and a main procedure, said main procedure to execute upon the firing of the transition to which the process is designated;

designating a plurality of sink procedures;

wherein for each of said plurality of transitions, further designating a predicate including a set of reference procedures and a main procedure;

assigning to each place no more than one token, wherein said token represents an instance of a data flow and wherein said data flow represents a set of variables accessible at a statement in the software, wherein a plurality of main input places are designated for at least one transition, and

wherein the reference procedures only refer to;

(a) variables represented by attributes of the place to which the reference procedure is registered,

(b) variables represented by attributes of;

(i) any main input places of the transition that are ancestor places of the place to which the reference procedure is registered,

(ii) any ancestor places of main input places of the transition that are ancestor places of the place to which the reference procedure is registered, if the place is not a main input place, or

(iii) any ancestor places of the place to which the reference procedure is registered, if the place is a main input place,

(c) if the reference procedure is included in a process, variables defined in other reference procedures of the process of the transition registered to;

(i) any main input places of the transition that are ancestor places of the place to which the reference procedure is registered,

(ii) any ancestor places of main input places of the transition that are ancestor places of the place to which the reference procedure is registered, if the place is not a main input place, or

(iii) any ancestor places of the place to which the reference procedure is registered if the place is a main input place, and

(d) if the reference procedure is included in a predicate, variables defined in other reference procedures of the predicate of the transition registered to;

(i) any main input places of the transition that are ancestor places of the place to which the reference procedure is registered,

(ii) any ancestor places of main input places of the transition that are ancestor places of the place to which the reference procedure is registered, if the place is not a main input place, or

(iii) any ancestor places of the place to which the reference procedure is registered if the place is a main input place.

2. A method for specifying computer software comprising:

designating a source procedure;

designating a plurality of hierarchical dependencies;

for each of a plurality of transitions, designating

(i) at least one input place and at least one output place from a plurality of places, wherein the transition produces said at least one output place from said at least one input place, and wherein said at least one input place is a main input place,

(ii) a process including a set of reference procedures and a main procedure, said main procedure to execute upon the firing of the transition to which the process is designated;

designating a plurality of sink procedures;

wherein for each of said plurality of transitions, further designating a predicate including a set of reference procedures and a main procedure and executing the main procedure of the process of the transition after the execution of the main procedure of the predicate of the transition;

assigning to each place no more than one token, wherein said token represents an instance of a data flow and wherein said data flow represents a set of variables accessible at a statement in the software, wherein a plurality of main input places are designated for at least one transition, and

wherein the predicate;

defines a Boolean variable for the transition such that the main procedure of the transition executes only when the Boolean variable is evaluated as TRUE;

produces no tokens;

defines no attributes of any places; and

for each of the plurality of transitions, executing the main procedure of the process of the transition after the execution of the main procedure of the predicate of the transition,

wherein executing the main procedure of the process begins when;

(a) if the transition has one main input place, at least one token of the main input place has not participated in any execution of the main procedure;

if the transition has multiple main input places combined by AND logic, at least one token of each main input has not participated in other execution of the main procedure;

if the transition has multiple main input places combined by OR logic, at least one of the main input places must have at least one token which has not participated in other execution of the main procedure; and

(b) all the tokens of the non-main input places that are descendant places of any main place of the transition that can be produced as a result of the tokens involved in (a) have been produced; and

(c) the Boolean variable for the transition is set to true.

3. A method for specifying computer software comprising:

designating a source procedure;

designating a plurality of hierarchical dependencies;

for each of a plurality of transitions, designating

(i) at least one input place and at least one output place from a plurality of places, wherein the transition produces said at least one output place from said at least one input place. and wherein said at least one input place is a main input place,

(ii) a process including a set of reference procedures and a main procedure, said main procedure to execute upon the firing of the transition to which the process is designated;

designating a plurality of sink procedures,

wherein those parts that are influenced by a plurality of functionalities or influence the plurality of functionalities are extracted from a computer software specification,

wherein extracting is achieved by forward slicing comprising;

(a) defining a forward slice and a temporary part as parts of the computer software specification;

(b) initializing the forward slice to empty;

(c) initializing the temporary part to include the part of the computer software specification that implements the plurality of functionalities; and

(d) for each place in the temporary part that is either an output place of a transition in the temporary part or a place for which tokens are produced by the source procedure of the temporary part, including the following in the forward slice

(i) each transition in the computer software specification which has the place as an input place, until no further transitions in the computer software specification can be included,

(ii) the place, if the place has not already been included, and

(iii) each sink procedure registered to the place in the computer software specification.

4. A method for specifying computer software comprising:

designating a source procedure;

designating a plurality of hierarchical dependencies;

for each of a plurality of transitions designating

(i) at least one input place and at least one output place from a plurality of places, wherein the transition produces said at least one output place from said at least one input place, and wherein said at least one input place is a main input place,

(ii) a process including a set of reference procedures and a main procedure, said main procedure to execute upon the firing of the transition to which the process is designated;

designating a plurality of sink procedures,

wherein those parts that are influenced by a plurality of functionalities or influence the plurality of functionalities are extracted from a computer software specification,

wherein extracting is achieved by backward slicing comprising;

(a) defining a backward slice and a temporary part as parts of the computer software specification;

(b) initializing the backward slice to empty;

(c) initializing the temporary part to include the part of the computer software specification that implements the plurality of functionalities;

(d) for each sink procedure in the temporary part, including in both the backward slice and the temporary part each transition in the computer software specification, if any, in which one of the output places of the transition is registered with the sink procedure;

(e) for each of a plurality of first transitions from the temporary part, including in both the backward slice and the temporary part each of a plurality of second transitions from the computer software specification that satisfies at least one of the following conditions;

i) any input place of the first transition is an output place of the second transition,

ii) any reference procedure of the first transition is registered to any output place of the second transition, and

iii) the main procedure or any reference procedure of the first transition refers to any output place of the second transition;

(f) for each of the first transitions in the temporary part, including in the backward slice each source place that is an input place of the first transition or that is referred to by the main procedure or any reference procedure of the first transition; and

(g) including the source procedure from the computer software specification in the backward slice if there is a source place in the backward slice.

5. A method for assembling a third part of computer software from a first part of computer software and a second part of computer software wherein the first part, the second part and the third part are specified according to a method for specifying computer software comprising:

designating a source procedure;

designating a plurality of hierarchical dependencies;

for each of a plurality of transitions, designating

(i) at least one input place and at least one output place from a plurality, of places, wherein the transition produces said at least one output place from said at least one input place, and wherein said at least one input place is a main input place,

(ii) a process including a set of reference procedures and a main procedure, said main procedure to execute upon the firing of the transition to which the process is designated;

designating a plurality of sink procedures;

wherein for each of said plurality of transitions, further designating a predicate including a set of reference procedures and a main procedure;

assigning to each place no more than one token, wherein said token represents an instance of a data flow and wherein said data flow represents a set of variables accessible at a statement in the software, wherein a plurality of main input places are designated for at least one transition, wherein the first part includes a first set of input places, a first set of output places, a first set of transitions, a first set of hierarchical dependencies, a first source procedure, a first set of reference procedures, and a first set of sink procedures;

the second part includes a second set of input places, a second set of output places, a second set of transitions, a second set of hierarchical dependencies, a second source procedure, a second set of reference procedures and a second set of sink procedures; and

the third part includes a third set of input places, a third set of output places, a third set of transitions, a third set of hierarchical dependencies, a third source procedure, a third set of reference procedures and a third set of sink procedures, said method comprising;

defining a shared set of places as those input places of the second set of input places which correspond to one of the output places of the first set of output places;

determining the third source procedure by asynchronously combining the first source procedure and second source procedure;

mapping each input place of the second set of input places in the shared set to a corresponding output place of the first set of output places, said mapping designated an IP mapping;

mapping each attribute of each input place of the second said set of input places in the shared set of places to a compatible attribute of the place corresponding to IP mapping of each place in the shared set, said mapping designated an AIP mapping;

determining the third set of input places as the union of the first set of input places and those input places in the second set of input places which are not in the shared set;

deriving the third set of transitions from the union of the first set of transitions and the second set of transitions, said third set of transitions further comprising those transitions in the second set of transitions involving places in the shared set wherein to each transition of the second set of transitions involving places in the shared set the following modifications are made before inclusion in the third set of transitions;

replacing each input place in the shared set with the place corresponding to the IP mapping the input place,

replacing each variable of each reference procedure and each variable of each main procedure that is an attribute of a place in the shared set with the attribute corresponding to the AIP mapping of the attribute of the place, and

registering each of the reference procedures registered to a place in the shared set with the place corresponding to the IP mapping of the place in the shared set;

deriving a third set of sink procedures from the union of the first set of sink procedures and the second set of sink procedures such that the following modifications are made before inclusion in the third set of sink procedures;

replacing each variable of each sink procedure that is an attribute of any place in the shared set with the attribute corresponding to the AIP mapping of the attribute of the place,

registering each of the sink procedures that is registered to any place in the shared set with the place corresponding to the IP mapping of the place;

deriving the third set of hierarchical dependencies as the union of the first set of hierarchical dependencies and the second set of hierarchical dependencies such that the hierarchical dependencies between places in the shared set are removed; and

maintaining the ancestor place and descendant place relationships between places in the third set of places among those places that were incorporated from the second set of input places.

6. The method of claim 5 wherein maintaining the ancestor place and descendant place relationships between places includes:

ensuring that the IP mapping of each first place of the second set of places that is in the shared set which was an ancestor place of a second place in the set of second input places which is not in the shared set remains an ancestor place of the second place;

ensuring that a first place of the second set of places that is not in the shared set which was an ancestor place of a second place in the set of second input places which is in the shared set becomes an ancestor place of the IP mapping of the second place;

ensuring that a first place of the second set of places that is in the shared set which was an ancestor place of a second place in the set of second input places which is also in the shared set maintains its hierarchy such that the IP mapping of the first place is a ancestor place of the IP mapping of the second place.

7. A method of transforming computer software specified into an object oriented programming language according to a method, specifying computer software comprising:

designating a source procedure;

designating a plurality of hierarchical dependencies;

for each of a plurality of transitions, designating

(i) at least one input place and at least one output place from a plurality of places, wherein the transition produces said at least one output place from said at least one input place, and wherein said at least one input place is a main input place,

(ii) a process including a set of reference procedures and a main procedure, said main procedure to execute upon the firing of the transition to which the process is designated;

designating a plurality of sink procedures;

wherein for each of said plurality of transitions, further designating a predicate including a set of reference procedures and a main procedure;

assigning to each place no more than one token, wherein said token represents an instance of a data flow and wherein said data flow represents a set of variables accessible at a statement in the software, wherein a plurality of main input places are designated for at least one transition,

renaming each variable of each transition if the variable is not unique among all transitions;

designating a source program,

allocating a transitions-processed variable to store transitions that have been processed and initializing the transitions-processed variable to empty, and

allocating an input-places-to-process variable to store the input places of transitions when the input place of any transition is ready to be processed, and initializing the input-places-to-process variable to the set of all source places that serve as input places to the transitions;

forming the source program by merging the source procedure, the main procedure, the reference procedures and the sink procedures by processing each transition when all its input places are in input-places-to-place, said processing including;

inserting each sink procedure before the reference port for the place to which the sink procedure is registered,

inserting each reference procedure before the reference port for the place to which the reference procedure is registered, and

inserting the main procedure responsive to the number of input places and whether any input places are descendents of a main input place; and

synchronizing each maximal sequence of threads.

8. The method of claim 7 wherein renaming includes prefixing non-unique variables with the name of the transition in which the variable is declared.

9. The method of claim 7 wherein inserting the main procedure includes:

if there is a single main input place and at least one input place is a descendent of the main input place, inserting the main procedure before the main port of the main input place;

if there is a single main input place and no input places are descendents of the main input place, designating the main procedure as a thread and inserting the main procedure thread before the main port of the main input place;

if there are multiple main input places, naming the main procedure and appending it at the end of the main program.

10. The method of claim 7 wherein if there are multiple main input places further includes:

if one or more input places is a descendant of the main input places and the main input places are combined by OR logic, inserting the main procedure as a statement before the main port of each main input place;

if no input place is a descendant of the main input places and the main input places are combined by OR logic, inserting the main procedure as a thread before the main port of each main input place;

if one or more input place is a descendant of the main input places and the main input places are combined by AND logic, inserting statements before the main port of each main input place (a) to define a status variable reflecting the status of each of two or more conjunctive main input places, and (b) to execute the main procedure such that the main procedure will not begin execution until all status variables are set to ready;

if no input place is a descendant of the main input places and the main input places are combined by AND logic, inserting a thread containing statements before the main port of each main input place (a) to define a status variable reflecting the status of each of two or more conjunctive main input places, and (b) to execute the main procedure such that (1) the main procedure will not begin execution until all status variables are set to ready, and (2) the status variables are reset to not ready when the main procedure begins.

11. The method of claim 7, wherein synchronizing includes:

if the sequence has one thread, replacing the thread by the statements in the thread; and

if the sequence has more than one thread, synchronizing the threads such that a statement after all of the threads will only be executed when all the threads have completed execution.