Automatic consistency checking of computer programs

Abstract

A method, for use with a computer having memory, for structuring a program segment, is described. A series of program blocks in the segment are identified. Each block is a functional piece of code in the segment and has at least one point corresponding to at least one of entry and exit, in such a manner that the entire segment is divided into blocks with each block being situated in an execution path along which the segment executes in a downstream direction. With respect to each block, a block representative is associated. The block representative allocates computer memory for data elements that are needed for the associated block to execute. The block representative also assigns a value to any data element required by the associated block to have a value. Additionally, the block representative calls the associated block for execution, receives return of control after execution of the block, and passes control based on available data.

1 . A method, for use with a computer having memory, for structuring a program segment, the method comprising: 
 a. identifying a series of program blocks in the segment, each block being a functional piece of code in the segment and having at least one point corresponding to at least one of entry and exit, in such a manner that the entire segment is divided into blocks with each block being situated in an execution path along which the segment executes in a downstream direction; and    b. with respect to each block, associating a block representative, the block representative (i) allocating computer memory for data elements that are needed for the associated block to execute, (ii) assigning value to any data element required by the associated block to have a value; (iii) calling the associated block for execution, (iv) receiving return of control after execution of the block, and (v) passing control based on available data.    
     
     
         2 . A method according to  claim 1 , further comprising: 
 c. treating a block of interest as a sub-segment, and performing steps (a) and (b) as to the sub-segment, including 
 (i) identifying a series of program sub-blocks in the block, each sub-block being a functional piece of code in the block and having at least one point corresponding to at least one of entry and exit, in such a manner that the entire block is divided into sub-blocks with each sub-block being situated in an execution path along which the block executes in a downstream direction; and  
 (ii) with respect to each sub-block, associating a sub-block representative, the sub-block representative (i) allocating computer memory for data elements that are needed for the associated sub-block to execute, (ii) assigning value to any data element required by the associated sub-block to have a value, (iii) calling the associated sub-block for execution, (iv) receiving return of control after execution of the sub-block, and (v) passing control based on available data.  
   
     
     
         3 . A method according to  claim 1 , wherein the block representative includes a virtual page, the virtual page being a virtual entry page when associated with an entry point and performing functions (i), (ii), and (iii) of the block representative, and being a virtual exit page when associated with an exit point and performing functions (iv) and (v) of the block representative.  
     
     
         4 . A method according to  claim 1 , wherein the block representative also validates all data elements that are assigned values by the associated block.  
     
     
         5 . A method according to  claim 1 , wherein the step (ii) of assigning value by the block representative includes evaluating expressions that depend on data elements created by upstream block representatives.  
     
     
         6 . A method according to  claim 1 , wherein the step (v) of passing control based on available data includes executing a decision to identify a downstream block to be executed next by evaluating an expression that depends on data elements created by an upstream block representative or by the associated block itself.  
     
     
         7 . A method according to  claim 2 , wherein the sub-block representative includes a virtual page associated with each sub-block, the virtual page being a virtual entry page when associated with an entry point and performing functions (I), (ii), and (iii) of the sub-block representative, and being a virtual exit page when associated with an exit point and performing functions (iv) and (v) of the sub-block representative.  
     
     
         8 . A method according to  claim 3 , for identifying inconsistencies in a software program, the method further comprising: 
 c. for each given virtual entry page, identifying all data elements, from upstream virtual pages, on which the data elements of the given virtual entry page are logically dependent, any upstream pages containing such data elements being ancestor pages.    
     
     
         9 . A method according to  claim 5 , for identifying inconsistencies in a software program, the method further comprising: 
 c. for each virtual entry page, determining with respect to each data element appearing in any of the expressions whether such data element has been created in an upstream virtual page, any such upstream page being an ancestor page.    
     
     
         10 . A method according to  claim 8 , the method further comprising: 
 identifying as inconsistent a virtual entry page that includes a data element that is logically dependent on a data element that does not appear in an ancestor page.    
     
     
         11 . A method according to  claim 9 , the method further comprising: 
 identifying as inconsistent a block associated with a virtual entry page that is identified as inconsistent.    
     
     
         12 . A method according to  claim 8 , wherein any given entry page may lie in any number of execution paths and each data element of the given entry page is expressed as a function of one or more data elements occurring in one or more ancestor pages along any of the execution paths.  
     
     
         13 . A method according to  claim 7 , wherein the software program includes a loop, so that in execution a given point is passed more than once, and wherein in determining whether a given page is upstream of another page, a page is indexed according to the number of times that it occurs in execution of the program, and a page of a first index is regarded as upstream of the same page of an index greater than the first index.  
     
     
         14 . A method according to  claim 13 , wherein for a given entry page in an execution path after at least one occurrence of the loop, each data element of the given entry page is expressed as a function of one or more data elements occurring only in a predetermined number of ancestor pages in previous iterations of the loop.  
     
     
         15 . A method according to  claim 8 , for identifying inconsistencies in a software program, further comprising: 
 d. in a case wherein a block is modified in such a way as to require a modification in a virtual exit page associated with the block, using the results of step (c) to identify all data elements, in downstream entry pages, that are affected by the modification.    
     
     
         16 . A method according to  claim 8 , for identifying inconsistencies in a software program, further comprising: 
 d. in a case wherein a block is modified in such a way as to require a modification in a virtual entry page associated with the block, using the results of step (c) to examine upstream pages to identify any data element, in the virtual entry page, that lacks a logical dependency on one or more data elements occurring in one or more ancestor pages.    
     
     
         17 . A method according to  claim 8 , for identifying inconsistencies in a software program, further comprising: 
 d. in a case wherein a block is subject to a move from its current position within the segment to a new position within the segment, using the results of step (c) to identify all downstream entry pages that are affected by the move.    
     
     
         18 . A method according to  claim 8 , for identifying inconsistencies in a software program, further comprising: 
 d. in a case wherein a block is subject to a move from its current position within the segment to a new position within the segment, using the results of step (c) to identify all downstream entry pages that are affected by the move and to check all upstream exit pages to identify whether as a result of the move there are any data elements associated with the virtual entry page for the block that are not available from an upstream exit page so that logical consistency may be maintained.    
     
     
         19 . A method according to  claim 8 , further comprising: 
 d. in a case wherein a block is subject to a move from its current execution path within the segment to a new execution path within the segment, using the results of step (c) to identify all downstream entry pages in the new execution path that are affected by the move and to check all upstream exit pages in the new execution path to identify whether as a result of the move there are any data elements associated with the virtual entry page for the block that are not available from an upstream exit page so that logical consistency may be maintained.    
     
     
         20 . A method according to  claim 8 , further comprising: 
 d. in a case wherein a block is subject to a move from its current execution path within the segment to a new execution path within the segment, using the results of step (c) to identify all downstream entry pages that are affected in the current execution path by the move to the new execution path and to check all upstream exit pages in the current execution path to identify whether as a result of the move to the new execution path there are any data elements associated with the virtual entry page for the block that are not available from an upstream exit page so that logical consistency may be maintained.    
     
     
         21 . A method according to  claim 8 , wherein a function defines the dependency of a given data element of the given entry page on one or more data elements occurring in one or more ancestor pages, the method further comprising: 
 d. assigning a sense to a selected set of data elements occurring in virtual pages of the segment;    e. assigning a sense to a selected set of functions, which affect the selected set of data elements, that are implemented in the segment;    f. determining whether the function, applied to the one or more data elements occurring in one or more ancestor pages, has a sense that is compatible with the sense of the data element of the given entry page or a superset of the sense of the data element of the given entry page.    
     
     
         22 . A method according to  claim 21 , wherein in step (d) data elements represented by an identical data structure are assigned the same sense and have an identical set of data validation rules.  
     
     
         23 . A method according to  claim 21 , further comprising: 
 g. arranging the senses of the one or more data elements into hierarchical levels so that data elements having the same sense level or a higher sense level are compatible and higher sense levels are a superset of lower sense levels.    
     
     
         24 - 39 . Cancel.