Methods and systems for generating a structured language model from a spreadsheet model6766512Abstract In one embodiment of the present invention, there is provided a method for easily allowing a user of little to no programming language knowledge to convert a computerized spreadsheet model to a structured programming language model, which method includes: (i) receiving, from the user via a computer input device, outputs and inputs of the computerized spreadsheet model desired to be processed for conversion; (ii) checking the user entries for errors; (iii) if an error is found, then requesting corrected user entry; (iv) if no error is found, then identifying all relevant spreadsheet model cells based on the user entries; (v) processing formulas used in the spreadsheet model for parsing; (vi) converting the formulas into final form and determining calculation priority order; and (vii) generating the structured programming language model. The method of the present invention is carried out by a system including a computer having a user interface, a microprocessor and a storage unit, an input device electronically coupled to the computer, and a software program stored in the storage unit, the software program being programmed to operate the microprocessor for carrying out the steps of the invention. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
Cell Formula Input/Output Parent
[Pat04.xls]Demo!I2 NPV(B7,F2:F4) _Bk1Wk1I2I2
[Pat04.xls]Demo!I4 I2-B8 _Bk1Wk1I4I4
The "Input/Output Parent" column in the Formula Stack corresponds to the following Output Parent Stack determined by the system: Output Parent Stack
Name Output Parent Range
_Bk1Wk1I2I2 [Pat04.xls]Demo!I2
_Bk1Wk1I4I4 [Pat04.xls]Demo!I4
The names used in the Output Parent Stack have no special significance. Bk1 stands for workbook 1 (in case more than one workbook is used) and Wk1 stands for worksheet 1 (in case more than one worksheet is used). Note that for the output cells 12 and I4, the Parent Range is only the individual output cell. This is because the user did not select cell 13 as a desired output in the example. Had cell 13 been selected as well, then the Parent Range would have been I2:I4. The cell names in the Formula Stack table above do not have any significance, other than to simply represent the appropriate cell of the spreadsheet model. The system goes through the Formula Stack to identify relevant cells based on the selected outputs' dependencies. For each output, all precedent cells are identified and unique precedent cells are placed onto the Formula Stack. That is, the system makes sure to only place new precedent cells on the Stack--if a precedent cell is already on the Stack, it is not placed again. In our example, cells B7, F2, F3 and F4 are placed on the Formula Stack for output cell I2. And cell B8 is placed on the Formula Stack for output cell I4. In the embodiment herein, the precedents are placed in a comma delimited format into the "Precedents" column. For each unique precedent cell, the system identifies relevant cells based on its dependencies. Thus, for F2, relevant cells E2 and B4 are identified and placed on the Stack. For F3, relevant cells E3 and B4 are identified, and E3 is placed on the Stack (note that B4 is not placed on the Stack because it has already been placed on the Stack for F2). For F4, relevant cells E4 and B4 are identified, and E4 is placed on the Stack. For B4, relevant cells B2 and B3 are identified and placed on the Formula Stack. In addition to adding precedent cells to the Formula Stack, the formulas are processed for parsing. In our example, the "#@" and "@#" characters are used as markers to break down the formulas for easy future parsing. It should be noted that there is no significance in the choice of the "#@" and "@#" characters as markers. Alternatively, the system may process formulas as the formulas are encountered. Optionally, the system may convert all 's to the xPow function, e.g., the formula 2 3 becomes xPow(2,3), and the system may wrap formula array functions inside the xArray function. For example, {SUM(IF(Y2:Y3,1,0))} becomes xArray(SUM(IF(#@Y2:Y3@#,1,0)),1) for cell Y2 and xArray(SUM(IF(#@Y2:Y3@#,1,0)),2) for cell Y3. Here is how the Stack looks at this point:
Input/Output
Cell Formula Precedents Parent
[Pat04.xls]Demo!I2 NPV(#@B7@#, B7,F2:F4 _Bk1Wk1I2I2
#@F2:F4@#)
[Pat04.xls]Demo!I4 #@I2@#-#@B8@# 12,B8 _Bk1Wk1I4I4
[Pat04.xls]Demo!B7 0.1
[Pat04.xls]Demo!F2 #@E2@#*(1-#@$B E2,B4
$4@#)
[Pat04.xls]Demo!F3 #@E3@#*(1-#@$B E3,B4
$4@#)
[Pat04.xls]Demo!F4 #@E4@#*(1-#@$B E4,B4
$4@#)
[Pat04.xls]Demo!B8 15000
[Pat04.xls]Demo!E2 10000
[Pat04.xls]Demo!E3 18000
[Pat04.xls]Demo!E4 24000
[Pat04.xls]Demo!B4 #@B2@#+#@B3@# B2,B3
[Pat04.xls]Demo!B2 0.12
[Pat04.xls]Demo!B3 0.3
At this point, the system in this example fills in the Main Parent column and the Main Parent Stack. Also, the system determines the Input Parent Stack and fills in the Input/Output Parent column of the Formula Stack accordingly. The Parent Stacks indicate which cells are adjacent to each other and will therefore be part of the same variable. Part of the reason for the Parent Stacks is to avoid allocating new memory in processing. The Parent Ranges can be determined using various techniques, e.g., recursion. For example, the system can search through the Formula Stack recursively to determine what other cells/inputs are adjacent and mark them as belonging to the same Parent Range. It should be noted that as used in this embodiment, Parent Ranges are rectangular. Therefore, not all the cells in the range may be used and/or displayed. Also, the Main Parent for a particular row may be the same as the Input/Output Parent, but it will not be smaller. In our example, the Formula Stack, the Main Parent Stack and the Input Parent Stack look as follows after this step: Formula Stack
Cell Formula Precedents Main Parent
Input/Output Parent
[Pat04.xls]Demo!I2 NPV(#@B7@#,#@F2:F4@#) B7,F2:F4 _Bk1Wk1I2I2
_Bk1Wk1I2I2
[Pat04.xls]Demo!I4 #@I2@#-#@B8@# 12,B8 _Bk1Wk1I4I4
_Bk1Wk1I4I4
[Pat04.xls]Demo!B7 0.1 _Bk1Wk1B7B8
_Bk1Wk1B7B8
[Pat04.xls]Demo!F2 #@E2@#*(1-#@$B$4@#) E2,B4 _Bk1Wk1E2F4
[Pat04.xls]Demo!F3 #@E3@#*(1-#@$B$4@#) E3,B4 _Bk1Wk1E2F4
[Pat04.xls]Demo!F4 #@E4@#*(1-#@$B$4@#) E4,B4 _Bk1Wk1E2F4
[Pat04.xls]Demo!B8 15000 _Bk1Wk1B7B8
_Bk1Wk1B7B8
[Pat04.xls]Demo!E2 10000 _Bk1Wk1E2F4
_Bk1Wk1E2E4
[Pat04.xls]Demo!E3 18000 _Bk1Wk1E2F4
_Bk1Wk1E2E4
[Pat04.xls]Demo!E4 24000 _Bk1Wk1E2F4
_Bk1Wk1E2E4
[Pat04.xls]Demo!B4 #@B2@#+#@B3@# B2,B3 _Bk1Wk1B2B4
[Pat04.xls]Demo!B2 0.12 _Bk1Wk1B2B4
[Pat04.xls]Demo!B3 0.3 _Bk1Wk1B2B4
Main Parent Stack
Name Parent Range
_Bk1Wk1I2I2 [Pat04.xls]Demo!I2
_Bk1Wk1I4I4 [Pat04.xls]Demo!I4
_Bk1Wk1B7B8 [Pat04.xls]Demo!B7:B8
_Bk1Wk1E2F4 [Pat04.xls]Demo!E2:F4
_Bk1Wk1B2B4 [Pat04.xls]Demo!B2:B4
Input Parent Stack
Name Input Range Range
_Bk1Wk1B7B8 [Pat04.xls]Demo!B7:B8
_Bk1Wk1E2E4 [Pat04.xls]Demo!E2:E4
The next step of the system is to verify with the user which of the non-formulaic cells are inputs and which are constants. In the example provided herein, the system reviews the Formula Stack, and for each row having no Precedents, the system asks the user if the corresponding cell is an input. If so, the system optionally requests the user to enter the names to be used for the inputs. The system may also optionally request the user to enter the names to be used for the outputs. Note that requesting the names for the outputs may instead be performed at the beginning, when the user is prompted to select the desired outputs. The system updates the Input and Output Parent Stacks with the names entered by the user and fills in the variable type column with "String" or "Double" (note that this is for a Java servlet that may call the structured language model generated pursuant to the present invention). In our example, the Formula Stack and the Input and Output Parent Stacks look as follows after this step: Formula Stack
Cell Formula Precedents Main Parent
Input/Output Parent
[Pat04.xls]Demo!I2 NPV(#@B7@#,#@F2:F4@#) B7,F2:F4 _Bk1Wk1I2I2
_PVofCash
[Pat04.xls]Demo!I4 #@I2@#-#@B8@# I2,B8 _Bk1Wk1I4I4
_NPVofInv
[Pat04.xls]Demo!B7 0.1 _Bk1Wk1B7B8
_DiscRate
[Pat04.xls]Demo!F2 #@E2@#*(1-#@$B$4@#) E2,B4 _Bk1Wk1E2F4
[Pat04.xls]Demo!F3 #@E3@#*(1-#@$B$4@#) E3,B4 _Bk1Wk1E2F4
[Pat04.xls]Demo!F4 #@E4@#*(1-#@$B$4@#) E4,B4 _Bk1Wk1E2F4
[Pat04.xls]Demo!B8 15000 _Bk1Wk1B7B8
_InitInv
[Pat04.xls]Demo!E2 10000 _Bk1Wk1E2F4
_EBITDA[0]
[Pat04.xls]Demo!E3 18000 _Bk1Wk1E2F4
_EBITDA[1]
[Pat04.xls]Demo!E4 24000 _Bk1Wk1E2F4
_EBITDA[2]
[Pat04.xls]Demo!B4 #@B2@#+#@B3@# B2,B3 _Bk1Wk1B2B4
[Pat04.xls]Demo!B2 0.12 _Bk1Wk1B2B4
[Pat04.xls]Demo!B3 0.3 _Bk1Wk1B2B4
Output Parent Stack
Name Output Parent Range Type
_PvofCash [Pat04.xls]Demo!I2 Double
_NPVofInv [Pat04.xls]Demo!I4 Double
Input Parent Stack
Name Input Parent Range Type
_DiscRate [Pat04.xls]Demo!B7 Double
_InitInv [Pat04.xls]Demo!B8 Double
_EBITDA [Pat04.xls]Demo!E2:E4 Double
The system next converts the formulas in the Formula Stack to their final form, specific to the target structured language, in this case Java, and figures out the calculation order for the cells. In the example embodiment provided herein, the system translates the Precedent ranges to their actual Parent equivalent, and adds the setVal( ), getval( ) and getArr( ) methods. Note that these methods are all part of a predefined class, "xlcV," which will accept strings, doubles and integers. The system uses a look-up matrix, which is a two-dimensional matrix, to determine the specific cell in the Main Parent Stack and follows it by an index representing the location of the cell in the parent range. For example, in the 1.sup.st row, B7 would be converted to _Bk1Wk1B7B8[0][0].getVal( ). In the case of a multiple cell entry, the entire Parent Range needs to be referred to, followed by coordinates representing the begin and end points of the multi-dimensional array. For example, in the 1.sup.st row, F2:F4 becomes _Bk1Wk1E2F4.getArr( ),0,1,2,1. This denotes that within the rectangular array spanning from E2 to F4, retrieve the cells in coordinates (0,1)--first row, second column or cell F2--through coordinates (2,1)--third row, second column or cell F4. Thus, cells F2, F3 and F4 are indicated. Note that in the two-dimensional convention adopted in this example, coordinates (0,0) indicate first row, first column or the top left corner cell. In the case of inputs, the Input Name is entered inside the setVal( ) method. Also, the system causes a copy of the input values to be placed in the Default Val column. In the case of outputs, the name to be used is entered in the Output Name column. Preferably, these methods are added to the formulas later, thereby allowing for easy conversion to Java or C. Alternatively, if desired, there can be two formula columns, 1 for the Java version and the other for the C version. Note that any formula which uses the OFFSET function needs to be adjusted so that its first argument is the entire parent range. Starting from the first row of the Formula Stack, move any row above the current row that has an equivalent cell in the Precedents column below the current row. That is, look in the Cell column of the current row, I2 in our example, and then look for I2 in the precedents column. If a row below the current row has I2 in its precedents column, then move that row above the current row. Since the row with Cell I4 has I2 as a precedent, that row is moved above the row of Cell I2. This is for proper calculation order of the cells. The Formula Stack looks as follows after this step: Formula Stack
Input/Output Default
Cell Formula Precedents Main
Parent Parent Value
[Pat04.xls]Demo!I4 _Bk1Wk1I4I4[0][0].setVal(_Bk1Wk1I2I2[0][0]. I2,B8
_Bk1Wk1I4I4 _PVofCash
getVal()-_Bk1Wk1B7B8[1][0].getVal());
[Pat04.xls]Demo!I2 _Bk1Wk1I2I2[0][0].setVal(NPV(_Bk1Wk1B7 B7,F2:F4
_Bk1Wk1I2I2 _NPVofInv
B8[0][0].getVal,
_Bk1Wk1E2F4.getArr(),0,1,2,1));
[Pat04.xls]Demo!B7 _Bk1Wk1B7B8[0][0].setVal(_DiscRate);
_Bk1Wk1B7B8 _DiscRate 0.1
[Pat04.xls]Demo!F2 _Bk1Wk1E2F4[0][1].setVal(_Bk1Wk1E2F4[0] E2,B4
_Bk1Wk1E2F4
[0].getVal()*(1-
_Bk1Wk1B2B4[2][0].getVal()));
[Pat04.xls]Demo!F3 _Bk1Wk1E2F4[1][1].setVal(_Bk1Wk1E2F4[1] E3,B4
_Bk1Wk1E2F4
[0].getVal()*(1-
_Bk1Wk1B2B4[2][0].getVal()));
[Pat04.xls]Demo!F4 _Bk1Wk1E2F4[2][1].setVal(_Bk1Wk1E2F4[2] E4,B4
_Bk1Wk1E2F4
[0].getVal()*(1-
Bk1Wk1B2B4[2][0].getVal()));
[Pat04.xls]Demo!B8 _Bk1Wk1B7B8[1][0].setVal(_InitInv);
_Bk1Wk1B7B8 _InitInv 15000
[Pat04.xls]Demo!E2 _Bk1Wk1E2F4[0][0].setVal(_EBITDA[0]);
_Bk1Wk1E2F4 .sub.-- 10000
EBITDA[0]
[Pat04.xls]Demo!E3 _Bk1Wk1E2F4[1][0].setVal(_EBITDA[1]);
_Bk1Wk1E2F4 .sub.-- 18000
EBITDA[1]
[Pat04.xls]Demo!E4 _Bk1Wk1E2F4[2][0].setVal(_EBITDA[2]);
_Bk1Wk1E2F4 .sub.-- 24000
EBITDA[2]
[Pat04.xls]Demo!B4 _Bk1Wk1B2B4[2][0].setVal(_Bk1Wk1B24[0] B2,B3
_Bk1Wk1B2B4
[0].getVal()+_Bk1Wk1B2B4[1][0].getVal());
[Pat04.xls]Demo!B2 _Bk1Wk1B2B4[0][0].setVal(0.12);
_Bk1Wk1B2B4 0.12
[Pat04.xls]Demo!B3 _Bk1Wk1B2B4[1][0].setVal(0.30);
_Bk1Wk1B2B4 0.3
At this point, the system generates the actual code for the model, in this case in Java. While it should be apparent to one of ordinary skill in the art that several ways may be employed at this point by the system to generate the actual structured language model, the following steps are provided herein for exemplary purposes: 1) Create a new file to write the Java code in. 2) Write the class header using the Java class name provided by the user. 3) Go through the Input Parent Stack and write the "Input Declarations" section. Make sure to declare input arrays only once. 4) Go through the Output Parent Stack and write the "Output Declarations" section. Make sure to declare output arrays only once. 5) Write the method header using the name provided by the user. 6) Go through the Main Parent Stack and write the "Range Variable Declaration" section. 7) Go through the Formula Stack in reverse and write the "Actual Formulas" section using the Formula column. 8) Go through the Formula Stack and write the "Actual Outputs" section using the Input/Output Parent and Formula columns. In the Formula column, all that is needed is everything left of the 1.sup.st period. Alternatively, this could be a separate column in the stack 9) End the method with a bracket. 10) Write the Main method's header. 11) Declare a new instance of the class just created using the name the user provided, modified to avoid conflict. In this example, prefix the class name with an "A". 12) Go through the Formula Stack and write the "Set the Input arguments" section using the Input Name and Default Val columns. 13) Call the method for the class (i.e., Patent), provide the outputs to the screen and write the ending brackets. For purposes of elucidation, it may make sense to think of the Formula Stack as a logical tree. For example, let's assume a spreadsheet employs the following formula: 5+3*(4+1). This formula is represented by the following logical tree: ##STR1## Calculations are performed going from bottom to top of this logical tree. Thus, the first function is the addition of 4 and 1. Next, this sum (i.e. 5) is multiplied to 3. Then this result (i.e. 15) is added to 5 to yield 20. The system of the present invention includes a computer or a like device having a microprocessor and a storage unit. As used herein, "computer" is meant to be a broadly defined term which includes any device with an interface capable of carrying out algorithms. The computer also includes an input device for receiving user input, such as a mouse, keyboard, touch-screen display, voice-command unit, or the like. A software program for carrying out the steps of the present invention is preferably stored in the storage unit. This software program operates the microprocessor to carry out the steps of the invention. The structured language model--such as in Java--generated by the system from a spreadsheet model can be provided interactively over the Internet without exposing the proprietary mathematical logic of the models. For example, the structured language model generated by the current system can be called by a Java servlet. A user can access the Java servlet over the World Wide Web via his computer, enter input values as prompted, and see the resulting outputs of the converted spreadsheet model, without referring to the original spreadsheet model.
|
Same subclass Same class Consider this |
||||||||||
