Abstract:
A constraint-based spreadsheet system includes a direction discrimination section, a dependence information generating section, a program execution process information generating section, and a display section. The direction discrimination section discriminates whether constraint information, which corresponds to a formula which is a basic structural element of a program, has direction of calculation. The dependence information generating section generates dependence information between tables and within a table based on the direction of calculation discriminated by the direction discrimination section. The program execution process information generating section generates program execution process information using the dependence information. The display section displays the program execution process information.

Description:
This application is a Continuation of application Ser. No. 08/365,803, filed on Dec. 29, 1994, now abandoned. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a spreadsheet system and, more specifically, to a constraint-based spreadsheet system and a method for displaying a process of execution of programs. 
     2. Description of the Related Art 
     A general spreadsheet system causes a planning simulation for business administration and the like to be executed by a computer using a spreadsheet with squares for accumulating and calculating information. This simulation is achieved by providing each cell with a series of items of computer information. 
     Since the computer information is usually serially evaluated in a predetermined direction, a user has to determine in advance the direction of the evaluation such that the cell has a value showing a correct result of the evaluation. If, therefore, a user wishes to describe a formula expressing certain information, he or she has to consider how to solve the formula in advance and, in other words, the user is required to describe computation procedures in sequence and determine (constrain) the direction of the computation. 
     If the procedures of computation are described, the computation assumes a direction. Thus, in order to enable bidirectional computation, a number of computation rules have to be described, and accordingly a high degree of knowledge is required (as shown in, for example, Computer Software Lexicon, pp. 358-366) MARUZEN, 1990 (In Japanese). 
     It is known that constraint programming has a strong affinity with the constraint-based spreadsheet system since the order of constraint processing does not influence an obtained solution. The constraint programming is featured in that a user simply describes an objective and need not describe any specific algorithm as to how the objective is attained. 
     Consequently, the spreadsheet system provides a flexible environment wherein a relationship between declarative targets having high-level description ability can be expressed, as the constraint programming having the above feature does. (Wm Leler, &#34;Constraint Programming Languages: Their Specification and Generation, Existing Constraint Languages,&#34; Addison-Wesley Publisher Company, 1988, chap. 4, pp. 69-86). 
     Though the foregoing constraint-based spreadsheet system describes languages well, it has a drawback in which a user has a difficulty in control of all programs and in debug, since a constraint processing section is considered as a black box. 
     Assume a constraint relationship where the multiplication of a value of cell A and that of cell B is equal to a value of cell C. In this case (A*B=C), the value of cell C is calculated by determining the values of cells A and B. However, the value of cell C can be determined before the values of cells A and B are determined. 
     In the constraint-based spreadsheet system, in accordance with how a value of a cell is determined as an input, a constraint processing section of the system determines a value of another cell so as to satisfy a constraint relationship between cells. A user was not able to see the process of determining the values of the cells at all. It was therefore difficult to understand the order of computation when the values of cells were increased or the computation was performed with respect to multiple spreadsheets having a constraint relationship. For example, it was difficult to know from what cell value the value of a certain cell was extracted. 
     When the constraint information handled by the constraint processing section is insufficient or excessive, a user has to take appropriate measures. Conventionally, however, there were no user interfaces for analyzing and displaying the insufficiency or excess of the constraint information. 
     SUMMARY OF THE INVENTION 
     A first object of the present invention is to provide a constraint-based spreadsheet system capable of performing an efficient programming operation by offering a user information on a process of execution of programs, which is indispensable to debugging, such as information on the direction of calculation of constraints between tables and within a table, and a method of displaying the information. 
     A second object of the present invention is to provide a constraint-based spreadsheet system capable of facilitating satisfaction of constraints for programming by determining the insufficiency/excess state of constraint information at the time of execution of a spreadsheet and offering a user a result of the determination, and a method of displaying the result. 
     To attain the above first object, there is provided a constraint-based spreadsheet system comprising: 
     discrimination means for discriminating whether constraint information has direction of calculation, the constraint information corresponding to a formula which is a basic structural element of a program; 
     first generating means for generating dependence information between tables and within a table based on the direction of calculation discriminated by the discrimination means; 
     second generating means for generating program execution process information using the dependence information generated by the first generating means; and 
     display means for displaying the program execution process information, generated by the second generating means, in a predetermined display fashion. 
     Furthermore, there is provided a method of displaying the program execution process information in the constraint-based spreadsheet system, comprising: 
     a discrimination step of discriminating whether constraint information has direction of calculation, the constraint information corresponding to a formula which is a basic structural element of a program; 
     a first generating step of generating dependence information between tables and within a table based on the direction of calculation discriminated in the discrimination step; 
     a second generating step of generating program execution process information using the dependence information generated in the first generating step; and 
     a display step of displaying the program execution process information, generated in the second generating step. 
     To attain the above second object, there is provided a constraint-based spreadsheet system comprising: 
     constraint readout means for obtaining a constraint information set, which is to be used for execution of a program, based on constraint information corresponding to a formula which is a basic structural element of the program; 
     constraint analysis means for obtaining dependence information of the constraint information between tables and within a table while applying a predetermined rule to the constraint information set obtained by the constraint readout means; 
     insufficiency/excess state analysis means for analyzing an insufficiency/excess state of the constraint information based on the dependence information obtained by the constraint analysis means; and 
     display means for displaying the insufficiency/excess state of the constraint information analyzed by the insufficiency/excess state analysis means. 
     Furthermore, there is provided a method of displaying the program execution process information in the constraint-based spreadsheet system, comprising: 
     a constraint readout step of obtaining a constraint information set, which is to be used for execution of a program, based on constraint information corresponding to a formula which is a basic structural element of the program; 
     a constraint analysis step of obtaining dependence information of the constraint information between tables and within a table while applying a predetermined rule to the constraint information set obtained in the constraint readout step; 
     an insufficiency/excess state analysis step of analyzing an insufficiency/excess state of the constraint information set based on the dependence information obtained in the constraint analysis step; and 
     a display step of displaying the insufficiency/excess state of the constraint information set analyzed in the insufficiency/excess state analysis step. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate presently preferred embodiments of the invention, and together with the general description given above and the detailed description of the preferred embodiments given below, serve to explain the principles of the invention. 
     FIG. 1 is a block diagram showing a structure of a constraint-based spreadsheet system according to a first embodiment of the present invention; 
     FIG. 2 is a view specifically showing cells of a table; 
     FIGS. 3A and 3B are views showing the dependence of constraint information among cells within a table and cells between tables in both cases where the direction is determined and it is not determined; 
     FIGS. 4A and 4B are views showing dependence information of all programs obtained from the dependence of constraint information shown in FIGS. 3A and 3B; 
     FIG. 5 is a flowchart showing a process of generating the process information of program execution from the dependence information in an analysis section; 
     FIG. 6 is a view of tables representing the process information of the program execution generated in the analysis section; 
     FIG. 7 is a view showing a display menu by which a user selects desired program execution process information; 
     FIG. 8 is a flowchart showing a process of displaying the program execution process information in accordance with the display menu; 
     FIGS. 9A to 9C are views each showing an example of displaying the program execution process information in case 1; 
     FIGS. 10A to 10C are views each showing an example of displaying the program execution process information in case 2; 
     FIG. 11 is a block diagram showing a structure of a constraint-based spreadsheet system according to a second embodiment of the present invention; 
     FIG. 12 is a view showing an example of a constraint information set used at the time of execution of a program; 
     FIG. 13 is a view showing a bipartite graph representing the constraint information set of FIG. 12; 
     FIGS. 14A and 14B are views of labeled constraint information; 
     FIG. 15 is a flowchart showing a process of generating program analysis information from the dependence information in a program information analysis section; 
     FIG. 16 is a view of tables representing the program analysis information generated in the program information analysis section; 
     FIG. 17 is a view showing a display menu from which program analysis information including information on an insufficiency/excess state is selected; 
     FIG. 18 is a flowchart showing a process of displaying the program analysis information in accordance with the display menu; 
     FIG. 19 is a view of an example of displaying the insufficiency/excess state when an input value is given to a cell variable; 
     FIG. 20 is a view of an example of displaying the insufficiency/excess state when an input value is given to another cell variable; 
     FIG. 21 is a view of an example of displaying the insufficiency/excess state when an input value is given to still another cell variable; and 
     FIG. 22 is a view of an example of displaying the insufficiency/excess state when an input value is given to yet another cell variable. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Embodiments of the present invention will now be described, with reference to the accompanying drawings. 
     FIG. 1 is a block diagram showing a structure of a constraint-based spreadsheet system according to a first embodiment of the present invention. As shown in FIG. 1, constraint information including the values of cells and the relationship between the cells supplied from an input section 1, which are represented by numeric expressions corresponding to fundamental constituents of programs, is stored in an execution data storage section 3 under control of an editing control section 2. The constraint information is also displayed on a display screen 400 of a display section 4 in the form of a table including of cells surrounded with ruled lines. In this table, the cells are referred to by coordinates of rows and columns. To refer to a cell of another table, the name of the table and the coordinate of the cell are required. 
     The cells can be used as cell variables. For example, &#34;X: A1&#34; represents a cell variable in row 1 and column A of table X. FIG. 2 shows table X in which cell variables are B2, B3, B4 and B5 and constraint information among the cell variables is that B2+B3=B4 and B2-B3=B5, and table Y in which cell variables are B10 and B11 and constraint information is that X: B2+X: B3=B10 and X: B4+X: B5=B11. 
     Returning to FIG. 1, a direction discrimination section 5 reads the constraint information stored in the execution data storage section 3 to discriminate whether the constraint information has a direction (or to discriminate whether the direction of the constraint information is determined). When the value of the constraint information is restricted by (n-1) of n cell variables within the constraint information, and the information can be executed as a function or a procedure without transforming the numeric expression thereof, the direction discrimination section 5 determines that the constraint information has a direction. In this case, an inference engine 6 executes the constraint information as a substitution. 
     If the value of the constraint information is restricted only by (n-2) or less of the n cell variables, the information cannot be executed as a function or a procedure. Therefore, the direction discrimination section 5 determines that the constraint information does not have a direction. The information free from direction is transmitted to a constraint processing section 7, and considered to be simultaneous equations. The constraint information is thus processed to remove the constraint therefrom. 
     The constraint information processed by the inference engine 6 or constraint processing section 7, is stored in a dependence storage section 8 as dependence information of constraint information indicative of the relationship among cells only within a table and that indicative of the relationship among cells covering several tables, as shown in FIGS. 3A and 3B. 
     FIG. 4A shows dependence information including both direction information (B2+B3→B4), which is obtained by the direction discrimination section 5 and inference engine 6 from input information 4 and 10 given to cell variables B2 and B3 of table X in FIG. 2 (B2=4, B3=10), and output information (B4=14). The dependence information represents that cell B4 is calculated by using (or referring to) cell variables B2 and B3. 
     FIG. 4B shows dependence information generated when the direction cannot be determined by the direction discrimination section 5 from input information 3 and 2 given to cells B4 and B5 of table X (B4=3, B5=2) and the constraint is removed using simultaneous equations by the constraint processing section 7. This dependence information includes both a constraint information set {B2-B3=B5, B2+B3=B4} and output information (B2=2.5, B3=0.5). 
     If a user inputs a display command from the input section 1 based on a display menu displayed on the display screen of the display section 4, an analysis mode monitor section 9 interprets the command and reports it to an analysis section 10. In accordance with the flowchart shown in FIG. 5, the analysis section 10 generates a table set management table, a table information management table, a cell (variable) management table, a constraint information management table, and a dependence information management table, each having a data structure as shown in FIG. 6, from the dependence information within each table stored in the dependence storage section 8 and the dependence information between tables stored therein. These tables are considered to be program execution process information. 
     First one element TBL1 is selected from a table set (TBL1S) defined as a program, and one element TBL is selected from a table set (TBLS) used for execution of programs (step S1). It is then determined whether or not the element TBL is empty (empty set). If not, a table set management table, a table information management table, a cell management table, a constraint information management table, and a dependence information management table are prepared and stored in a program execution process storage section 11, and TBLS-{TBL} is substituted into TBLS and the TBL is flagged (steps S2 and S3). The processing of step S3 is continued until the TBL becomes empty. When the TBL becomes empty, the flow jumps to step S4. 
     In step S4, it is determined whether TBL1 is flagged or not and whether TBL1 is empty or not. If TBL1 is neither flagged nor empty, a table set management table, a table information management table, a cell management table, and a constraint information management table, are prepared and stored in the program execution process storage section 11, and TBL1S-{TBL1} is substituted into TBL1S (step S5). 
     The processing of step S5 is continued until TBL1 is both flagged and empty. 
     Each of the tables so produced has an arrangement as shown in FIG. 6. More specifically, the table set management table includes a row showing a table set defined as a program and a row showing a table set used for execution of the program. The table information management table includes a row indicating a cell (variable) set including a table, a row indicating a constraint set defined in the table, and a row showing a dependence set, and is managed by a table name. The cell (variable) information management table includes a row indicating a cell value and a row indicating mode information, and is managed by a cell name. The constraint information management table includes of a row showing a cell (variable) set contained in constraint, a row showing mode information, and a row showing direction information, and is managed by a constraint name. The dependence information management table includes a row showing a constraint set for generating a dependence and a row showing a variable set, and is managed by a dependence name. 
     The program execution process information is read out from the program execution process storage section 11 by the editing control section 2 in response to a user&#39;s display command input from the input section 1 during the intermittence of execution of programs or after the execution of programs, and displayed as menu information on the display screen 400 of the display section 4. This menu information is shown in FIG. 7. 
     That information of the displayed program execution process information which is selected by the user, is displayed on the display section 4. FIG. 8 is a flowchart showing a process of displaying the program execution process information on the section 4. 
     First a menu is selected referring to the menu information as shown in FIG. 7 (steps ST1 and ST2). If information between tables is selected, a calling relationship between tables is displayed (step ST3), and it is determined whether or not information within a table is displayed (step ST4). If YES in step 4, the information within the table is displayed (step ST5). It is then determined whether cell, constraint, or dependence information is displayed (step ST6). If YES in step ST6, the information is displayed (step ST7). After that, it is confirmed whether or not the display is finished (step ST12). If YES in step ST12, the display operation ends. 
     When information is selected from the table in step ST2, it is displayed (step ST8). It is then determined whether cell, constraint, or dependence information is displayed (step ST9). If YES in step ST9, the information is displayed (step ST10). After that, it is confirmed whether or not the display is completed (step ST12). If YES in step ST12, the display operation ends. 
     If cell, constraint, or dependence information is selected in step ST2, this information is displayed immediately (step ST11), and it is confirmed whether or not the display is finished (step ST12). If YES in step ST12, the operation ends. 
     FIGS. 9A and 10A are views each showing how the program execution process information is displayed on the screen 400 of the display section 4, and FIGS. 9B-9C and 10B-10C are views showing in detail parts of the views of FIGS. 9A and 10A, respectively. 
     FIG. 9B shows an example of displaying program execution process information between tables X and Y in case 1 of FIG. 4A, where input information 4 and 10 are supplied to cell variables B2 and B3 in table X, respectively. 
     FIG. 9C shows an example of displaying of program execution process information within table in the case 1 of FIG. 4A. More specifically, FIG. 9C shows the dependence information of table X, &#34;B2+B3→B4 and B2-B3→B5,&#34; and the program execution process information obtained from the dependence information. The program execution process information is represented as input/output information between constraints and information concerning the use of (reference to) cells by using arrows. 
     FIG. 10B shows an example of displaying program execution process information between tables X and Y in case 2 of FIG. 4B, where input information 3 and 2 are supplied to cell variables B4 and B5 in table X, respectively. 
     FIG. 10C shows an example of displaying program execution process information within a table. More specifically, it shows information about input/output of cells in each table, the dependence of constraint information, and the calling relationship between the tables (==&gt;). 
     According to the first embodiment described above, a user can be provided with information concerning a program execution process indispensable to debugging, such as information on the direction of calculation of the constraint between tables and within a table. Consequently, a user&#39;s burden is lightened at the time of debugging, and an efficient operation can be performed. 
     FIG. 11 is a block diagram showing a structure of a constraint-based spreadsheet system according to a second embodiment of the present invention. In FIG. 11, the same components as those of FIG. 1 are indicated by the same reference numerals, and their descriptions are omitted. 
     A constraint readout section 18 reads out the constraint information, as shown in FIG. 12, from an execution data storage section 3, and a constraint information set is obtained from the read-out constraint information to use it at the time of execution of programs. FIG. 12 shows the constraint information set, {B2+B3=B4, B2-B3=B5, X: B2+X: B3=B10, X: B4+X: B5=B11}. The constraint information set is used at the time of execution of programs if the input values are given to the cells B2 and B3 in table X of FIG. 2 and to the cells B4 and B5 therein. 
     A constraint conversion section 12 converts the constraint information set read out from the constraint readout section 18 into a bipartite graph, and stored in a bipartite graph storage section 15. The bipartite graph of the constraint information set is shown in FIG. 13. In FIG. 13, the left-side node set V+ contains node elements indicative of names of the constraint information, and the right-side node set V-includes node elements indicative of variables of the constraint information. For example, the constraint information, &#34;B2+B3=B4  f1(B2, B3, B4)=0!&#34; is expressed as the relationship between constraint information and variables by the bipartite graph of FIG. 13. 
     A constraint analysis section 13 is designed to label the edges of the bipartite graph of the constraint set stored in the bipartite graph storage section 15 by employing the following five rules. 
     1) When the dependence between variables is provided in advance as causality (a function) by an explicit function, a table or the like, it has a first priority as a labeled rule. 
     2) If a node V- represents an input variable, it has an outward edge (an edge in the output direction) only. 
     3) If the node set V+ (constraint, predicate, etc.) includes N variables, one edge is set in the output direction, and (N-1) edges are set in the input direction. 
     4) In the node set V- of the other variables, one edge is set in the input direction, while the remaining edges are set in the output direction. 
     5) If the relationship of node set V+ including N variables is expressed by an inequality, and a value has to be known to every variable, all edges are set in the input direction. In other words, the nodes representing all the variables are set in the input mode. 
     The results of labeling are stored in the dependence storage section 8 as dependence information as shown in FIGS. 3A and 3B. 
     An insufficiency/excess state analysis section 14 computes the number of constraints and that of variables from the dependence information within a table and between tables stored in the dependence storage section 8, i.e., from the common information of variables and constraint information, and analyzes a result of the labeling performed by the constraint analysis section 13. In this analysis section 14, the nodes given as input variables and the outward edges from the nodes are eliminated, and the insufficiency/excess state of the constraint set is determined as to the following three cases. 
     (a) When the number of constraints and that of variables are equal to each other: 
     First, based on the result of labeling, a variable node having an outward edge is selected from the node set corresponding to the variables, and the selected node is regarded as a starting point. The labeled edge is then traced from the starting point to check constraint and variable nodes. If all constraint and variable nodes are checked after completion of tracing of the edge, it is determined that constraint is satisfied. If, however, an operation is returned to the variable node of the starting point, that is, if a route following the edge is closed, simultaneous equations have to be solved. If, furthermore, a variable node has only one input edge, it has to be supplied with a value. 
     (b) When the number of constraints is larger than that of variables: 
     First a variable node having an outward edge is selected, and the selected node is regarded as a starting point. Then the labeled edge is traced from the starting point to check constraint and variable nodes. If all constraint and variable nodes are checked after completion of tracing of the edge, it is determined that the constraint is satisfiable. If it is possible to return to the variable node of the starting point, simultaneous equations have to be solved. If there is an unchecked constraint node, it is determined that the constraint set is in the excess state and, in this case, the unchecked constraint node is considered to be redundant or contradictory, with the result that its corresponding constraint information needs to be removed in order to satisfy the constraint. 
     (c) When the number of constraints is smaller than that of the variables: 
     First a variable node having an outward edge is selected, and the selected node is regarded as a starting point. Then the labeled edge is traced from the starting point to check constraint and variable nodes. If all constraint and variable nodes are checked after completion of tracing of the edge, it is determined that the constraint is satisfied. To return to the variable node of the starting point, simultaneous equations have to be solved. If a variable node has only one input edge as in the case of (a), it is determined that the variable node lacks a constraint, and a value has to be supplied to the variable node. 
     In accordance with the flowchart shown in FIG. 15, a program information analysis section 17 generates a table set management table, a table information management table, a cell (variable) management table, a constraint information management table, a dependence information management table, and a program analysis information management table, each having a data structure as shown in FIG. 16, from the dependence information within each table stored in the dependence storage section 8 and the dependence information between tables stored therein. Since the flowchart of FIG. 15 is substantially the same as that of FIG. 5, its description is omitted. These tables are considered to be program analysis information and stored in a program analysis information storage section 16. 
     As shown in FIG. 16, the table set management table includes a row showing a table set defined as a program (execution data) and a row showing a planned table set used for execution of the program. The table information management table includes a row indicating a cell (variable) set including a table, a row indicating a constraint set defined in the table, and a row showing a dependence set, and is managed by a table name. The cell (variable) information management table includes a row indicating mode information. The constraint information management table includes of a row showing a variable set, a row showing a constraint set, and a row showing an edge set, and is managed by a constraint name. The program analysis information management table includes a row indicating a constraint set for generating a dependence and rows showing input and output variables, and is managed by an analysis information name. The dependence information management table includes a row showing a constraint set and a row showing labeling information. 
     The program analysis information stored in the program analysis information storage section 16 is read out under control of an editing control section 2, when a user inputs a specific display command from an input section 1 while referring to menu information displayed on a display section, as shown in FIG. 17. The read-out information is displayed on the display section 4 as information indicative of the insufficiency/excess state of constraint information. Since this display operation is carried out in accordance with the flowchart of FIG. 18 which is substantially the same as that of FIG. 8, its description is omitted. 
     FIG. 19 shows an example of display of program analysis information between tables when input values are given to cell variables B2 and B3 in FIG. 3A or table X. According to this example, when input variables &#34;X: B2&#34; and &#34;X: B3&#34; are given as a result of analysis of the insufficiency/excess state, the constraint information can be satisfied without solving the constraint. 
     FIG. 20 shows an example of display of program analysis information between tables when input variables are given to cell variables B4 and B5 in FIG. 3B or table X. According to this example, when input variables &#34;X: B4&#34; and &#34;X: B5&#34; are given as a result of analysis of the insufficiency/excess state, the constraint information can be satisfied by solving the constraint or simultaneous equations. 
     FIG. 21 shows an example of displaying program analysis information between tables X and Y on the supposition that a cell variable B2 in table X is input information. According to this example, information on variables becomes insufficient if &#34;X: B2&#34; is provided as an input variable. In this case, a value needs to be given to a variable &#34;X: B4&#34; in order to satisfy the constraint. This need is displayed as display information when an underconstraint-based state is judged by the dependence information. 
     FIG. 22 shows an example of an overconstraint-based state in which the number of constraints is larger than that of variables whose values are not determined when cell variables B2, B4 and B5 of table X are supplied as input information. According to this example, whether an unchecked constraint node is redundant or contradictory is displayed as display information, or whether a variable supplied with an input value is redundant or contradictory is displayed as display information. 
     According to the second embodiment described above, when execution mode information indicative of an analysis mode is input from the input section 1, the editing control section 2 detects the input and informs the constraint readout section 11 of it. The section 11 collects the constraint information, as shown in FIG. 12, which is called by execution of programs. The constraint information is then converted to the bipartite graph, as shown in FIG. 13, by the constraint conversion section 12. The constraint analysis section 13 extracts the constraint information (FIGS. 14A and 14B), and the extracted information is regarded as dependence information and stored in the dependence storage section 8. The insufficiency/excess state analysis section 14 analyzes the insufficiency/excess state of constraint information using the dependence of constraint information between tables and within a table. The result of the analysis is stored in the program analysis information storage section 16, and displayed on the display section 4 in accordance with a user&#39;s request. Since the insufficiency/excess state of constraint information can be provided, the execution of interactive programs can easily be supported, and an efficient operation can be performed accordingly. 
     Additional advantages and modifications will readily occur to those skilled in the art. Therefore, the invention in its broader aspects is not limited to the specific details, representative devices, and illustrated examples shown and described herein. Accordingly, various modifications may be made without departing from the spirit or scope of the general inventive concept as defined by the appended claims and their equivalents.