> 5@ wbjbj22 %XXjjjjk2l ooooApdqQrX$RDT)Q{=pAp{{)oo;z{R 8oo{ar߷ol`RR&j- k`t0˶M0߷߷rRtvTwrrr))8W}WSpreadsheet Algebra
Jocelyn Paine,
HYPERLINK "http://www.j-paine.org/"http://www.j-paine.org/
ABSTRACT
We introduce spreadsheet algebra. This treats spreadsheets as mathematical objects and operates on expressions containing spreadsheets, giving us rules for expanding, factorising, simplifying and rearranging them. We implemented it in our spreadsheet analysis program Model Master, and demonstrate by reverse engineering one of Pankos spreadsheets, producing a concise listing of the formulae with cells renamed to meaningful identifiers derived from the labels. This is useful when error-checking. We have also used it to automatically add numerical differentiation code to a process-control spreadsheet, and to generate new spreadsheets by joining existing ones.
We take a relativist approach, believing there is no one "right" way to display spreadsheet expressions. Different tasks need different presentations. In this, we imitate conventional computer algebra, supporting the trial and error needed during reverse-engineering.
1 INTRODUCTION
In 1953, while IBM were busy inventing Fortran, Kahrimanian and Nolan independently wrote the first programs that could differentiate symbolically. Fortran, seeing the world in terms of numbers, only lets you differentiate numerically; by using arrays of the things, you can lay a grid over your variables and get a numerical answer to their rate of change, to as fine a degree of accuracy as you want. But what Kahrimanian and Nolan had realised was that the process of symbolically differentiating the expression x3+2x to make 3x2+2 is as much about "getting an answer" as is that of numerically evaluating the expression (x[1]-x[0])/dt to get 5. Their work kicked off the development of computer algebra systems. And since then, computer algebra has pushed this notion of "getting an answer" ever further into mathematical territory, capturing the behaviour of polynomials, series, tensors, .
One of the things about such objects is that they exist in pieces. There is a single symbol for the number 5, but not for the polynomial (1+x)n. The polynomial doesn t even have a single presentation. Sometimes, we prefer to write it as 1+nx+n(n-1)x2/2+..., 1+n!x/1!(n-1)!+n!x2/2!(n-2)!+..., or as "C(n,k)xk. It all depends on which particular patterns we want to make explicit and how far we are trying to squeeze the expression down to fit into the rudimentary capacity of human short-term memory. Computer algebra designers know the importance of rearranging and re-presenting expressions, and have put years of effort into algorithns for factorisation, expansion and simplification. We shall argue the need to extend this work to spreadsheets.
While computer algebra was extending the range of mathematical objects we can compute with, computer science was extending the range of computational entities we can mathematise about. Not least of these were computer programs themselves. It took computing some time to understand programs mathematically; but once it had, it realised that they too could be the objects of computer manipulation. Spreadsheets are programs; and in this paper, we describe a computer algebra system for "spreadsheet algebra", where the fundamental mathematical components are spreadsheets.
The rest of this paper is structured as follows. The next section illustrates conventional computer algebra. We then introduce "spreadsheet algebra", starting with an introduction to the idea of computer programs as mathematical entities. This is followed by a section on how spreadsheet algebra relates to our spreadsheet-analysis program Model Master and the longest section in the paper a demonstration of reverse engineering, generating a comprehensible listing from one of Pankos spreadsheets. This is followed by two smaller examples, in one of which we used spreadsheet algebra to insert numerical-differentiation code into a process-control spreadsheet. We finish with a section on further work.
2 COMPUTER ALGEBRA
For those unfamiliar with it, we introduce computer algebra via a short session with the Maple algebra system [ HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "hart" Hart and Wolfe]. We shall go on to compare it with our spreadsheet algebra system. The lines ending in semicolons below are the users input; they are followed by indented lines showing Maples responses:
p := (a+b)^2;
p := (a + b)2
q := expand(p);
q := a2 + 2 a b + b2
r := factor(q);
r := (a + b)2
The first command assigns the expression (a+b)^2 to the Maple "expression variable" p. If you saw a similar statement in Fortran, you would expect it to evaluate the expression, adding a to b, squaring the result, and assigning the resulting number to p. However, like other computer algebra systems, Maple is about computing with expressions, not just numbers. One adds, subtracts, squares numbers; one simplifies, factorises, expands expressions. So Maple needs variables, like p, in which expressions can be held.
In the second command, the user passes this variable to expand, a Maple function that treats its argument as an expression and expands it out as far as possible. The result is assigned to variable q.
Finally, we call another built-in,factor, to refactorise it, showing that we can get back to the original expression. The key points to take away are:
Computer algebra systems manipulate algebraic expressions without evaluating them into numbers.
You can display the same expression in different ways, for example by factorising or expanding it.
You can store expressions in variables.
You can have several versions of an expression on the go at the same time.
3 SPREADSHEET ALGEBRA
As we have said, programs and spreadsheets are mathematical entities, and we can do algebra with them too. In this section, we explain.
3.1 Doing algebra with programs
What does it mean, to do algebra with programs? Consider the following program, which assigns the numbers 1 to 10 to the arrays p and q,
for i := 1 to 10 do
p[i] := i;
for i := 1 to 10 do
q[i] := i;
Now, this has the same effect as
for i := 1 to 10 do
a[i] := i;
b[i] := i;
From this, it's tempting to propose a general law of programs which says
for I := L to U do
S1;
for I := L to U do
S2;
always has the same effect as
for I := L to U do
S1;
S2;
where S1 and S2 are arbitrary statements.
Notice how this resembles the distributive law a(b+c)=ab+ac for numbers. Why is this useful? Well, were this law always true, it would help in optimising our code, because it would give us a rule we could follow to merge loops, thus reducing the time spent testing and incrementing loop counters.
As it happens, this law is not universally applicable: consider what would happen if S2 were a statement that halted the program, or if S1 and S2 both updated the same array but with different values. Such problems arise, for example, arises with variables and assignment when different statements find themselves updating the same piece of store. However, that doesnt destroy the validity of program algebra laws; its just that conventional languages are complicated and its hard to give simple examples here. The topic id discussed in [Bowen; Visser et. al.].
The good news for EuSpRIG is that spreadsheets are actually simpler to handle in this way, as we shall see..
3.2 Doing algebra with spreadsheets
So if spreadsheets are programs, and we can do algebra on programs, we can do algebra with spreadsheets. But why bother?
The answer is that we want to achieve quality through reverse engineering. In its raw or unrefined state, a spreadsheet file is about as legible as a stretch of DNA or the inside of an amoeba. We think we can make out some parts because of the boundaries between them; others, we reveal by staining with powerful dyes. But point mutations have corrupted evolution's drag-and-drop copying; different dyes disagree on the regions they delimit; much of what we find looks suspiciously like left-over junk from previous versions; and the Author wrote no comments and won't pick up His phone. In such circumstances, it's essential to carry out trial dissections, saving useful parts in killing bottles or pinning them labelled to a board; bracketting repeated patterns in a database and comparing them for matches. We need to classify, clean, label and store parts for later reuse; to store, as well, different dissections; and to transpose component parts from one to another. Spreadsheet algebra lets us do this.
The slogan is: preserve meaning while maximising utility. In our program algebra example, utility was efficiency: the program with merged loops was faster than that without. In other contexts, it could be memory occupancy or ease of data entry or, as in our big example later on, readability. Preserve meaning, but dont preserve presentation if utility is better served by a different presentation.
4 SPREADSHEET ALGEBRA AND MODEL MASTER
At EuSpRIG 2001, we presented a HYPERLINK "http://www.j-paine.org/eusprig2001_as_html/eusprig2001.html" paper on Model Master (MM), a spreadsheet design language and its compiler [ HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "paine" Paine, 2001]. The MM language enables spreadsheets to be described in concise mathematical notation. Meaningful identifiers can be used in place of cell names; programs can be divided into modules which can be stored in files and reused from one spreadsheet to another; cells to which the same calculation is being applied can be grouped so that the calculation appears only once; formatting commands can be used to display the same program in many different layouts.
To demonstrate, we reimplemented one of Tom Grossman's queueing simulations HYPERLINK "http://www.j-paine.org/eusprig2001_as_html/eusprig2001.html" \l "grossman" in MM. Our program appears at the end of [ HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "paine" Paine, 2001], and implements a 4-server queue. Grossman's original spreadsheet represents each server as a column in which successive rows represent successive transactions. To alter the number of servers in the simulation entails changing the number of columns, a major structural change. We were able to do this in MM just by editing one constant in our code.
MM also lets us decompile spreadsheets into MM programs, regardless of whether they were originally generated in MM. The program will lack much of the structure intended by its spreadsheet's author - for example, in an accounts spreadsheet where one column tracks income over several years, there's nothing to indicate that all these cells are "doing the same thing". However, MM can transform the program into one that maps the entire column onto one multi-cell attribute. Discovering though which cells should be grouped, how they should be named, and what their indices are, can take a lot of trial and error. Spreadsheet algebra supports this, allowing users to put a spreadsheet through a gamut of transformations until they find the one that best reveals its structure.
5 SPREADSHEET ALGEBRA EXAMPLE: REVERSE ENGINEERING
This, the main section, demonstrates spreadsheet algebra for reverse engineering. We started with a spreadsheet sent by Steve Davis of Clemson University, who is evaluating MM as a debugging tool. The spreadsheet turned out to have been written by Ray Panko for the work reported in HYPERLINK "http://panko.cba.hawaii.edu/papers/ss/2phase.htm" "Applying code inspection to spreadsheet testing" [ HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "panko" Panko]. We show it below in value view, omitting to save space some labels found below and to the right of the calculation area. These all described errors - for example, cell J28 contained the string F5;; living costs summer;; cells in sum should be f14..f20 - and were evidently not part of the original problem.
Cash BudgetAssume:2%inflation/semesterFallSpringSummerCash, beginning$1,000 $1,360 $673 Outflows - School costs$4,468 $4,474 $4,480 Living costs$4,172 $4,213 $4,485 Inflows-Loans300030003000Support from home$6,000 $5,000 $6,000 Cash,end$1,360 $673 $980 =====================School (contractual) -Tuition$4,115 $4,115 $4,115 Fees$53 $53 $53 $300 306312Living (contractual)MonthlyMonthsHousing$450 4$1,800 $1,800 $1,800 Insurance$53 4$212 $212 $212 Living Costs (other)Food$330 4$1,320 13461373Entertainment$150 4$600 612624Transportation$40 4$160 $161 164Clothing$21 4$80 82845.1 Stage 1
The following sections show some spreadsheet algebra manipulations, and should be compared with the Maple session in Section 2.
Our first step was to start the spreadsheet algebra system and load the spreadsheet:
panko := load( "Panko.slk" );
Because of the file's extension, load assumes it to be a spreadsheet and automatically decompiles it into an MM program. The ":=" assigns this program to the variable panko. Just as p, q and r in the Maple session are variables which hold algebraic expressions, so panko is a variable which holds a spreadsheet expression. And, just as Maple automatically lists the expression resulting from the commands typed at it, so MM displays the spreadsheet resulting from the load command, listing it as an MM program:
where
A1 = "Cash Budget"
B1 = " Assume:"
D1 = 0.02
E1 = "inflation/semester"
H1 = "Panko, R.R. Applying code inspection to spreadsheet testing, Journal of Management Information Systems, (in press?)"
D2 = "Fall"
E2 = "Spring"
F2 = "Summer"
A3 = "Cash, beginning"
D3 = 1000
D9 = "======="
E9 = "======="
F9 = "======="
I27 = "4 mechanical errors in formulas with 3 opns and cell references"
J28 = "F5;; living costs summer;; cells in sum should be f14..f20"
The program contains a bracketed list of attribute declarations followed by the equations (some omitted to save space). As always in MM, all attributes referenced in the equations are declared. This provides redundancy for the compiler (when error-checking) and for the reader (when struggling to make sense of other people's code).
5.2 Stage 2
The next step was to remove the labels, as they are not part of the calculations. We did this by calling detach_labels, which removes all cells containing string constants not referenced by other cells. These can fairly be assumed to be labels:
panko_delabelled := detach_labels( panko );
MM then displays the result:
where
D1 = 0.02
D3 = 1000
E3 = D8
F3 = E8
D4 = SUM(D10:D12)
E4 = SUM(E10:E12)
F4 = SUM(F10:F12)
D5 = SUM(D14:D20)
E5 = SUM(E14:E20)
F5 = SUM(F12:F19)
D6 = 3000
E6 = 3000
F6 = 3000
D7 = ROUND(1000+D4+D5-D3-D6,-3)
E7 = ROUND(1000+E4+E5-E3-E6,-3)
F7 = ROUND(1000+F4+F5-F3-F6,-3)
D8 = D3-D4-D5+D6+D7
E8 = E3-E4-E5+E6+E7
F8 = F3-F4-E5+F6+F7
D10 = 4115
Note that the labels have been removed. Note also that we now have two versions of the spreadsheet on the go simultaneously, just as our Maple session had several versions of an expression.
5.3 Stage 3
When MM loads a spreadsheet, it gives all attributes the same name as the cell they came from. We wanted to rename them to make the code easier to understand. Inspection suggested the labels in columns A and B might make meaningful names for the cells in columns D, E and F, so to test this, we sliced columns A and B out of the labels and then joined them:
labels := panko without panko_delabelled;
col_A := by_row( slice( labels, A1:A20 ) );
col_B := by_row( slice( labels, B1:B20 ) );
cols_AB := zip( col_A, col_B, append );
cols_AB_cleaned := zip( cols_AB, mangle );
Here, the first line subtracts the spreadsheet without labels from the entire spreadsheet, giving just the labels. The next two lines extract columns A and B (up to row 20, the final one of importance). The by_row function modifies slice's result to be a function from row number to label rather than from cell address (i.e. row and column) to label.
Next, in the fourth command, we zip together corresponding rows of columns A and B. We use MM's zip function, which runs down the columns passed in the first two arguments, taking corresponding cells from each and applying the third argument, itself a function, to them. Here, this function is append: it joins or appends two strings. So the effect is to append the A and B labels of each row.
We then had to clean up the results. The problem is that we want to use the labels as identifiers. As in most languages, these can contain letters and digits, but not such things as minus signs, brackets, and spaces. So we ran down the joined names, passing each through the mangle function. This "mangles" each name (the word is commonly used by compiler writers) to remove or replace unwanted characters. Thus the labels Cash Budget and Assume become Cash_BudgetAssume, for example. The next thing is to pair the cell names of column D with the new identifiers that replace them:
renamings := make_map( by_row(col_D), cols_AB_cleaned );
giving us
D3 > Cash_beginning
D4 > Outflows_School_costs
D5 > Living_costs
D6 > Inflows_Loans
D7 > Support_from_home
D8 > Cash_end
D10 > School_contractual_Tuition
D11 > Fees
D14 > Housing
D15 > Insurance
D17 > Food
D18 > Entertainment
D19 > Transportation
D20 > Clothing
where the listing uses > to mean "maps to". So what this listing shows is meaningful names suggested for the cells in column D.
5.5 Stage 5
Columns D, E and F are obviously related, reporting the same quantities for the three school terms autumn ("fall"), spring and summer. A feature of MM - indeed, a key point - is that an attribute can name not just one cell as in the examples so far, but an entire collection of cells. So for example, assume we have a spreadsheet where column A represents the income of some company, with rows 1 (for 1990) up to 14 (for 2003). We could declare this in MM as
and write references such as Income[1995] in the equations.
In the previous paragraph, the multi-cell attribute Income had numeric indices. MM also allows symbolic indices akin to Pascal's enumerated types. We use these when building tables whose cells do not have a natural ordering; for example the branches of a department store or the colours a dress can be bought in. Thus we might have a business with branches in Oxford, Cambridge and London. To store the income for each branch at one particular time, we would declare:
while to hold income for these branches from 1990 onwards, the attribute would gain a dimension, becoming:
We now show how we applied multi-cell attributes and enumerated types to our running example. Since our renaming of the cells in column D made sense, we decided to do the same to columns E and F. But we also decided the three cells D1, E1 and F1 should be treated as part of one attribute, indexed by the symbolic indices fall, spring and summer. Thus any reference to D1 would be replaced by Cash_BudgetAssume[fall]; reference to E1 by Cash_BudgetAssume[spring]; and so on. We did the same for all the other attributes in these three columns.
cols_DEF := slice( panko_delabelled, D1:F20 );
cols_DEF_merged := merge(cols_DEF, cols_AB_cleaned, D:F, [fall,spring,summer] );
which gave:
where
Cash_BudgetAssume[fall] = 0.02
Cash_beginning[fall] = 1000
Cash_beginning[spring] = Cash_end[fall]
Cash_beginning[summer] = Cash_end[spring]
Cash_end[fall] = Cash_beginning[fall]-Outflows_School_costs[fall]-
Living_costs[fall]+Inflows_Loans[fall]+Support_from_home[fall]
Cash_end[spring] = Cash_beginning[spring]-Outflows_School_costs[spring]-
Living_costs[spring]+Inflows_Loans[spring]+Support_from_home[spring]
Cash_end[summer] = Cash_beginning[summer]-Outflows_School_costs[summer]-
Living_costs[spring]+Inflows_Loans[summer]+Support_from_home[summer]
Clothing[fall] = C20*20
Clothing[spring] = ROUND(Clothing[fall]*(1+Cash_BudgetAssume[fall]),0)
Clothing[summer] = ROUND(Clothing[spring]*(1+Cash_BudgetAssume[fall]),0)
D12 = 300
E12 = ROUND(D12*(1+Cash_BudgetAssume[fall]),0)
Entertainment[fall] = C18*B18
Entertainment[spring] = ROUND(Entertainment[fall]*(1+Cash_BudgetAssume[fall]),0)
Entertainment[summer] = ROUND(Entertainment[spring]*(1+Cash_BudgetAssume[fall]),0)
F12 = ROUND(E12*(1+Cash_BudgetAssume[fall]),0)
Fees[fall] = 53
Fees[spring] = 53
Fees[summer] = 53
Food[fall] = C17*B17
Food[spring] = ROUND(Food[fall]*(1+Cash_BudgetAssume[fall]),0)
Food[summer] = ROUND(Food[spring]*(1+Cash_BudgetAssume[fall]),0)
Housing[fall] = C14*B14
Housing[spring] = Housing[fall]
Housing[summer] = Housing[fall]
Inflows_Loans[fall] = 3000
Inflows_Loans[spring] = 3000
Inflows_Loans[summer] = 3000
Insurance[fall] = C15*B15
Insurance[spring] = Insurance[fall]
Insurance[summer] = Insurance[fall]
Living_costs[fall] = SUM(Housing[fall]:Clothing[fall])
Living_costs[spring] = SUM(Housing[spring]:Clothing[spring])
Living_costs[summer] = SUM(F12:Transportation[summer])
Outflows_School_costs[fall] = SUM(School_contractual_Tuition[fall]:D12)
Outflows_School_costs[spring] = SUM(School_contractual_Tuition[spring]:E12)
Outflows_School_costs[summer] = SUM(School_contractual_Tuition[summer]:F12)
School_contractual_Tuition[fall] = 4115
School_contractual_Tuition[spring] = 4115
School_contractual_Tuition[summer] = 4115
Support_from_home[fall] = ROUND(1000+Outflows_School_costs[fall]+
Living_costs[fall]-Cash_beginning[fall]-Inflows_Loans[fall],-3)
Support_from_home[spring] = ROUND(1000+Outflows_School_costs[spring]+
Living_costs[spring]-Cash_beginning[spring]-Inflows_Loans[spring],-3)
Support_from_home[summer] = ROUND(1000+Outflows_School_costs[summer]+
Living_costs[summer]-Cash_beginning[summer]-Inflows_Loans[summer],-3)
Transportation[fall] = C19*B19
Transportation[spring] = ROUND(Transportation[fall]+1+Cash_BudgetAssume[fall],0)
Transportation[summer] = ROUND(Transportation[spring]*(1+Cash_BudgetAssume[fall]),0)
Not bad, is it?
Recall that we made the new attribute names by concatenating labels from corresponding rows in columns A and B. That isn't actually quite good enough, because the column A labels sometimes qualify more than one cell in column B. A4 - Outflows - appears to qualify both B4 and B5, so we should have prefixed it to both. Even so, our transformation has worked pretty well.
6 ERROR DETECTION
We aim to make spreadsheets easier to read, and, of course, to check, so we ought to say something about error detection. Our example spreadsheet originated in Panko's work on detecting errors via code inspection, for which he seeded it with eight errors. Four were in columns D, E and F:
E19=ROUND(D19+(1+$D$1),0). D19+ should be D19*.
F3=F4-F5+E6+E7. Should be F3=F4-E5+E6+E7.
D20=C20*20. Should be C20*B20.
F5=SUM(F12..F19). Should be SUM(F14..F20).
Has our listing, with its renamed cells, helped us detect them?
These formulae correspond to the equations for HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "E19" Transportation[spring], HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "F8" Cash_end[summer], HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "D20" Clothing[fall] and HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "F5" Living_costs[summer]. The first error is relatively easy to spot by inspection, helped by the way the listing groups together the elements of an attribute, making it easy to compare the spring and summer equations. Likewise, the second error stands out because the right hand side refers to Living_costs[spring], not Living_costs[summer]. The third error, C20*20 is not obvious (though it might be had we worked out a good replacement name for C20), but the fourth error stands out because the attribute F12 in the right hand side of Living_costs[summer] should, by comparison with the other elements of Living_costs, be Housing[summer].
7 SPREADSHEET ALGEBRA EXAMPLE: NEW SPREADSHEETS FROM OLD
Boolean algebra, linear algebra, and the ordinary algebra that operates on numbers, all possess primitive operators such as set union, addition, or matrix multiplication, and fundamental laws that define how these behave. Boolean algebra has De Morgan's law; numerical algebra has the distributive law, amongst others. So far, we haven't seen such things in spreadsheet algebra, where the functions have been ad-hocced up for convenience in reverse engineering: rename, merge, slice, detach_labels. We did, however, invent some, and the others are based on them. They include:
spreadsheet addition, which joins together two spreadsheets or MM programs, concatenating their attributes and equations;
spreadsheet extension, an analogue to drag-and-drop copying, which extends attributes and calculations over a range;
spreadsheet division, which "divides" a set of identical attributes by their range.
We have used these operators to combine spreadsheets. For example, we built two spreadsheets, one detailing the profits of the Oxford branch of an imaginary company, and one detailing the profits of the Cambridge branch. Using the spreadsheet addition operator, we were able to glue the two together into one new spreadsheet. Space in these proceedings prohibits us from showing any examples.
These two spreadsheets reported profits at yearly intervals. In another demonstration, we loaded them, combined them as above, and added a new column reporting profits monthly. In Excel, this would require cell-by-cell formula copying; we were able to do it more simply by typing one equation and indicating which column attributes it should take its input from. One might say that MM understands time.
Incidentally, we can also generate spreadsheet templates where the attributes' bounds (such as 1990 and 2003) are not wired in as above but passed as parameters. This process of generalisation enables us to produce a module that can be glued into any spreadsheet, regardless of the size of row or column we are attaching it to.
8 SPREADSHEET ALGEBRA EXAMPLE: ADDING CODE FOR NUMERICAL DIFFERENTIATION
Finally, we cite an example inspired by work with Jack Ponton of Edinburgh University's Chemical Engineering Department. Suppose we have a spreadsheet that calculates the concentration x of some chemical at various timepoints, and we want the rate of change of concentration, x_dot. If we assume the difference between timepoints is always the same - 1000, say - we can approximate the rate of change by dividing this into the successive differences in concentration. To do this with MM simply entailed loading the spreadsheet and adding to it a new attribute x_dot together with an equation for how x_dot depends on x and t. Space again prevents us showing the example.
We can do more ambitious transformations in the same way, for example adding various schemes for numerical integration. Since we can store these in libraries and parameterise them to fit any range of attribute, spreadsheet algebra gives us a powerful generic way to add them to any spreadsheet we could want.
9 FURTHER WORK AND CONNECTIONS TO OTHER RESEARCH
9.1 Automatic structure discovery
Listings much bigger than our example would become tedious to inspect, and there is a risk of overlooking errors even in small listings. Can we automatically compare formulae and flag a warning when they differ? Markus Clermont reported his research into this at EuSpRIG 2002 [ HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "clermont" Clermont,2003]. His program "stains" the raw spreadsheet, proposing sets of cells that might be grouped to become elements of a single attribute. Some cells get proposed because they contain similar formulae, but he uses other means too, for example proposing that cells mentioned in a cell range should be grouped. In our example, this is like saying that D14 to D20 should be considered for grouping, as should D10 to D12. In MM, we have independently experimented with something similar, using unification and inverse unification as a way to detect related formulae. [Our next paper in this series, on structure discovery and logic programming, takes this further.]
There are other methods worth investigating. Discrete Fourier transforms might help discover repeating patterns of related but non-contiguous cells like these:
XYZ XYZ XYZ
It might be worth looking in general into the perceptual techniques developed in computer vision, and certainly at blackboard systems and other methods that artificial intelligence has developed for fusing knowledge from different sources.
Another possibility is parallel terraced scans, a technique Hofstadter's Fluid Analogy Research Group have used in solving analogy problems [ HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "hofstadter" Hofstadter, 1996; Hofstadter, 1998], and one we believe promising for resolving tensions between different ways to view a problem. With spreadsheets, one such tension is that between lumping and splitting: grouping too coarsely (the extreme being to cover the entire worksheet with just one attribute) versus dividing too finely (the extreme being to split the spreadsheet into one attribute for every cell).
The most promising technique is HYPERLINK "http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/ilp.html" inductive logic programming [ HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "ilp" ILP]. This learns, given logical descriptions of examples of a concept, general rules describing the concept itself. Unlike neural nets and other machine learning techniques, the learnt concepts are easy to translate into English and to use in programs. ILP has convincing industrial applications - drug companies use it to learn the relation between biological activity and 3D structure in vast collections of molecules - and we believe it could be invalauable in learning libraries of common patterns.
9.2 A standard for interchange of structure-discovery data
There are so many structure-discovery techniques, we are unlikely to find them all in the same program. This means we need a standard representation of patterns, errors and other information, and a way to share it between structure-discovery tools and other programs. What kind of information should be exchanged? We suggest: high-level specification of what a spreadsheet, or regions therein, is doing; semantically related regions and the reasons for believing them to be related, together with a description of how they map onto the worksheet; names proposed for regions; errors, such as a cell where an equation "ought" to resemble those around it but doesn't; and proposed corrections for errors.
9.3 The algebra language
Is our algebra language appropriate? We had to give the user a means of performing element-by-element manipulation of rows and columns, as when appending the cells in columns A and B to make attribute names. We provided a functional language, partly because we liked it and partly because it mapped cleanly onto our implementation language Kawa, a dialect of Scheme. However, this requires expertise the average user will certainly lack.
It is worth asking whether a graphical interface might help - something along the lines of HYPERLINK "http://science.uniserve.edu.au/pubs/callab/vol3/tintarev.html" MINOS: Steps Towards a Syntax-free Computer Algebra Program [ HYPERLINK "http://www.j-paine.org/spreadsheet_algebra.html" \l "tintarev" Tintarev, 1999], where the author adopts a desktop metaphor, with different icons on the desktop representing different expressions to be manipulated.
9.4 Incremental reverse-engineering
We are working on algorithms by which a user can compile MM code to a spreadsheet, change the compiled spreadsheet, then calculate the equivalent change to the MM program. This would be useful if you develop a spreadsheet in MM and then want to change cell styles and formats from Excel, having the changes reflected back to your MM program. Doing so involves some reverse-engineering of the kind described earlier, but under constraints that the new MM program constructed by decompiling the modified spreadsheet resemble the original as much as possible. In general, this is not easy because changes to the spreadsheet may cut across parts of the MM program, rather as though we were to translate a sentence into French, throw a random eror into it, and then try to translate the result back into an English sentence with the "same" error. We are experimenting with an appropriate formalisation of the notion of "part", so that if we change something in the compiled spreadsheet, we can find the minimal enclosing entity in the MM code that it is a part of, and adjust the code accordingly. This may be a new approach to reverse engineering.
10 REFERENCES
Bowen,J., HYPERLINK "http://vmoc.museophile.com/algebra/section3_6.html" Recent Developments in the Algebra of Programs, HYPERLINK "http://vmoc.museophile.com/algebra/section3_6.html" http://vmoc.museophile.com/algebra/section3_6.html, 21:51 19/4/04.
Clermont,M. (2003),. A Scalable Approach to Spreadsheet Visualisation, Dissertation, FakultFt fr Wirtschaftswissenschaften und Informatik, Universitt Klagenfurt,, HYPERLINK "http://www.ifi.uni-klu.ac.at/Publications/Dissertations/pubfiles/pdffiles/2003-0175-MC.pdf" http://www.ifi.uni-klu.ac.at/Publications/Dissertations/pubfiles/pdffiles/2003-0175-MC.pdf, 21:52 19/4/04.
Hart,D. and Wolfe,C., HYPERLINK "http://www.indiana.edu/~statmath/math/maple/algebra/index.html" Basic Algebra in Maple, HYPERLINK "http://www.indiana.edu/~statmath/math/maple/algebra/index.html" http://www.indiana.edu/~statmath/math/maple/algebra/index.html, 21:49 19/4/04
Hofstadter,D. (1996), Analogies and Roles in Human and Machine Thinking, Metamagical Themas: Questing for the Essence of Mind and Pattern, Basic Books.
Hofstadter,D. (1998), Fluid Concepts and Creative Analogies: Computer Models of the Fundamental Mechanisms of Thought, Penguin..
Inductive Logic Programming, HYPERLINK "http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/ilp.html" http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/ilp.html, 21:48 19/4/04.
Paine,J. (2001), Ensuring Spreadsheet Integrity with Model Master, Proceedings of EuSpRIG 2001, HYPERLINK "http://www.j-paine.org/eusprig2001_as_html/eusprig2001.html" http://www.j-paine.org/eusprig2001_as_html/eusprig2001.html, 21:47 19/4/04.
Panko,R (1999), HYPERLINK "http://panko.cba.hawaii.edu/papers/ss/2phase.htm" Applying Code Inspection to Spreadsheet Testing, Journal of Management Information Systems, 16(2).
Tintarev,K. (1999), HYPERLINK "http://science.uniserve.edu.au/pubs/callab/vol3/tintarev.html" MINOS: Steps Towards a Syntax-free Computer Algebra Program, CAL-laborate, Volume 3, HYPERLINK "http://science.uniserve.edu.au/pubs/callab/vol3/tintarev.html" #$%HIJ`abcdͿ~jVC7h#ECJOJQJaJ%hhDB6>*CJOJQJ]aJ&hhDB0Je6CJOJQJ]aJ&hh0Je6CJOJQJ]aJ1jhhs?6CJOJQJU]aJ"hhs?6CJOJQJ]aJ+jhhDB6CJOJQJU]aJh6>*CJOJQJ]!hhDB6>*CJOJQJ]h#EhDBCJaJh5CJ$OJQJhDB5CJ$OJQJ$cden,3BR\Ksssss::ss sss22kgd[$^a$gd[i$a$gd[i$a$gdaui$a$gd"^i$a$gd$^a$$^a$$^a$gd$a$tvdemnq|}V \ h m X
g
l
9:s,
ʾujhuhhqeCJaJhuhDB5CJOJQJaJhuh6CJaJh6CJaJhuh46CJaJhuhB6CJaJhuh6CJaJhuh#E6CJaJ0huhDB5@B*CJEHKHOJQJphhuhDB5CJOJQJh#Eh#ECJOJQJaJ(
/01?@vGT2xz6NP=/L&23hih[h[5CJ\aJhwR]CJaJhuhC2CJaJhCJaJhuhhqe0JjCJaJhuhhqeCJH*aJh"CJaJhuhhqeCJaJhC2CJaJ<dest23PQop|}8@XY]^Fjk幱yh hhCJOJQJ^JaJhCJaJhuh[6CJ]aJhC2h[0JjCJ^JaJhuh[CJaJhC2CJaJhuh[H*huh[#huh[0Je>*CJOJQJaJ%jhuh[CJOJQJUaJhuh[CJOJQJaJhC2CJOJQJaJ(RSg~md:Q !222222Τ ggMMsss2222ss2^gdhqekgdhqei$a$gdaui$
&F2a$gdC2i$a$gd[kgd[klt:;OPQ 5 G N y z wlll_l_lXLhC2CJOJQJaJhuhhqehuhhqe0JjCJaJhuhhqeCJaJhuhwR]CJaJhuhwR]5CJaJhC2hC2CJaJh[5CJaJh[h[5CJaJh[h[5CJ\aJh[5CJ\aJhC2h[0JjCJ^JaJhC2h[CJOJQJaJhuh[CJaJhC2CJaJhCJaJ $!%!o!!!!!!!!!""M"W"}"""""""@#A#C#######$ %x%%%%%%ЌЌЌЄ||tkh[5OJQJh[CJaJhCJaJhC2CJaJhuhhqe0JjCJaJh[CJOJQJaJhCJOJQJaJhC2CJOJQJaJ$huhhqe0JjCJOJQJ^JaJhuhhqeCJaJhuhm CJOJQJaJhuhhqehuhhqeCJOJQJaJ(!!$!%!o!!!!!!!!!""C#x%% &&v*,/,/122ss2222s222ssspssssssssgdhqegdMi$a$gdau$^a$gdau^gdhqekgdhqe%%& &w&&&[''N*u*v*+,, ,
,.,/,O,P,,,,,,,0-1-6-7-=-./R/S/////Թ{{m{{{m{e{{m{huCJaJhuhhqe0Je>*CJaJjhuhhqeCJUaJhuhhqe5OJQJaJh[5OJQJaJhR)5OJQJaJhuhC2CJaJhhqeCJaJhCJaJhuhhqeCJaJhC2CJaJhMhM5OJQJaJhM5OJQJhMhM5OJQJ'///0 0%0&0,0?0I0P0g00112223]3g3r3y334444444444,5?5j5555!6"6S6T6V6W66666j777huhhqe0JjCJaJhuhhqe5OJQJaJhuhhB5OJQJaJhR)5OJQJaJhMCJaJh5YCJaJhR)CJaJhuCJaJhuhhqe0Je>*CJaJjhuhhqeCJUaJhuhhqeCJaJ414477777 88 ssw
$If^gdm
$If^gdM $Ifgds?
$If^gdX=gdhqei$a$gdau 7788`:l:m:::::T;;;;;;;F<G<ޚzrg\MB5BMBhR)hhqe0JjCJaJhR)hhqeOJQJhR)hhqeCJOJQJaJh5YhhqeCJaJhuhhqeCJaJhR)CJaJhuhhqe5CJOJQJaJhuh7NY5CJOJQJaJhR)5CJOJQJaJ$h5Yh"@CJOJQJ^JaJ$h5Yh"@CJOJQJ^JaJ hdyh7NYCJOJQJ^JaJ hdyhhqeCJOJQJ^JaJ hdyhm CJOJQJ^JaJ8888888%8`WWWJJwJ
$If^gdX= $Ifgds?kd$$IfTKֈ[
7nnsO#44
la"T%8&86888:8B8J8`SJJ==w
$If^gdM $Ifgds?
$If^gdX=kdJ$$IfTKֈ[
7nnsO#44
la"TJ8P8Q8]8j8l8t8SFF= $Ifgds?
$If^gdX=kd$$IfTKֈ[
7nnsO#44
la"T
$If^gdMt8|888888wSJ=J
$If^gdX= $Ifgds?kd$$IfTKֈ[
7nnsO#44
la"T
$If^gdM8888888wSFF
$If^gdX=kdE$$IfTKֈ[
7nnsO#44
la"T
$If^gdM8888888wJkd$$IfTKֈ[
7nnsO#44
la"T
$If^gdM $Ifgds?8888888w=kd$$IfTKֈ[
7nnsO#44
la"T
$If^gdM $Ifgds?
$If^gdX=89
9999 9w
$If^gdM $Ifgds?
$If^gdX= 9!9#9%9'9/979?9`WWWJJwJ
$If^gdM $Ifgds?kd@$$IfTKֈ[
7nnsO#44
la"T?9@9W9_9a9i9q9`SSJ==w
$If^gdM $Ifgds?
$If^gdX=kd$$IfTKֈ[
7nnsO#44
la"Tq9y9z9|9999SJ=J
$If^gdX= $Ifgds?kd$$IfTKֈ[
7nnsO#44
la"T
$If^gdM999999999wSJJJw $Ifgds?kd;$$IfTKֈ[
7nnsO#44
la"T
$If^gdM9999999SFFF
$If^gdX=kd$$IfTKֈ[
7nnsO#44
la"T
$If^gdM9999999wWJ==
$If^gdM
$If^gdX=kd$$IfTKֈ[
7nnsO#44
la"T $Ifgds?99999::
::wSF
$If^gdX=kd6 $$IfTKֈ[
7nnsO#44
la"T
$If^gdM::: :5:7:9:wSF== $Ifgds?
$If^gdX=kd $$IfTKֈ[
7nnsO#44
la"T
$If^gdM9:;:=:?:@:E:K:wJ=
$If^gdX=kd
$$IfTKֈ[
7nnsO#44
la"T
$If^gdM $Ifgds?K:M:U:Z:_:`:n:t:v:wSF
$If^gd"kd1$$IfTKֈ[
7nnsO#44
la"T
$If^gdMv:|::::::::wSF
$If^gdX=kd$$IfTKֈ[
7nnsO#44
la"T
$If^gdM:::::::::wSFw
$If^gdX=kd$$IfTKֈ[
7nnsO#44
la"T
$If^gdM::::T;;;SJsEsEs@kgdhqeigdhqe^gd7NYkd1
$$IfTKֈ[
7nnsO#44
la"T
$If^gdMG<H<J<K<L<p<q<v<x<<<<<<<<<<<<<<<<=:=j=l=o=====~A^B~BBȉȉzo``huhhqeCJOJQJaJhdyhhqeCJaJhR)hhqeCJOJQJaJhCJOJQJaJhR)CJOJQJaJhR)hR)CJOJQJaJhR)hR)OJQJhR)hhqe0JjCJaJhR)hhqeCJOJQJaJhR)hhqeOJQJhR)hhqe0JjCJ^JaJhR)hR)CJOJQJaJ$;=>8>X>>>?(?H?p?y?}??????Q@_@o@@@@@@@@ߙkgdhqe$^a$gdR)@@1AvA~ABBCCD6DRDDDEEEE&E0E:ENEbEvEEssv s^gdX=i$a$gdau^gdB$^a$gdaukgdhqeBBBBACNCCCCCCDFFQGRGSGTGVGWG]G^G_GdHeHgHpHHHǺǳznaaaYYQh5YCJaJhR)CJaJh"5CJOJQJaJhR)CJOJQJaJhL"CJOJQJaJhdyhhqeCJaJhuhhqeCJOJQJaJh5YCJaJh5YhhqeCJaJhuhhqehuhhqe0JjCJaJhuhhqeCJaJhuhhqe5CJOJQJaJhuh7NY5CJOJQJaJhR)5CJOJQJaJEEEEEEEF9kgdhqe$
&F1a$gd9>9i$
&F3a$gdi$a$gd9>9gdhqei$a$gd^}$^a$gdau
&F-dd[$\$gdhqe^gdBi$a$gdauOgXgsgggggh(h+h,hAhChFhGhQhRhVhYhghihrhshhhhhhhhhhhhhhhhhhhi@iAiiiiii彪{!huhhqe0JjB*CJaJphjhuhhqeCJUaJhuhhqeCJOJQJaJ$huhhqe0JjCJOJQJ^JaJhuhhqe0JjCJaJhCJOJQJ^JaJhhhqe0JjCJaJh^}CJaJhuhhqeCJaJhR)CJaJ0iiiiiiiiBjCjQjRjWjXjjjjjkAkkkkkl l l4l8l:l[l^llllllmmmmm mVmWmfmmmm̿嵨|hdyCJaJhCJaJhuhhqe5OJQJaJhuh7NY5OJQJaJhuh7NYOJQJaJhR)OJQJaJhuhhqe0JjCJaJh^}CJaJ!huhhqe0JjB*CJaJphhuhhqeCJaJjhuhhqeCJUaJ0mhnn%o+o-o2o4o9o;oHoPo\oaooopp,pgppppppppppqr'r-rirjrkrrvvo`hvhvCJOJQJaJh9>9hdyh9>9CJOJQJ^JaJ hvhvCJOJQJ^JaJ hvhdyCJOJQJ^JaJhuhhqehuhhqeCJOJQJaJh9>9CJOJQJaJh9>9CJaJhR)CJaJh5YCJaJhuhhqe0JjCJaJhCJaJhuhhqeCJaJ$rs8ssssu!uHuIuKuuuuuKvLvfvvvvgwwwwwwxxټٱzoboobozobZIZI h9>9h9>9CJOJQJ^JaJh9>9CJaJhuhhqe0JjCJaJhuhhqeCJaJhR)CJaJh5YCJaJhuhhqe5OJQJaJhuh7NY5OJQJaJh5Y5OJQJaJhL"5OJQJaJhCJOJQJaJ hvhhqeCJOJQJ^JaJhvhhqeCJOJQJaJh5YCJOJQJaJhR)CJOJQJaJkrssHuIuu1xgyyy}\~t~e܁wBsssss?sssss2ssssssssk$a$gdUQi$a$gddy^gds?i$a$gdaui$a$gd9>9gdhqe$^a$gdaukgdhqe$^a$gdvx0x1x8xy#y.yGygyhyzyyyyyyy#zSzqzzzzz{{${%{*{i{t{n|~vggYgQ~hCJaJhuhhqe0Je>*CJaJjhuhhqeCJUaJhuCJaJh5YCJaJhuhhqe5CJOJQJaJhuhs?5CJOJQJaJhR)5CJOJQJaJhuhhqe5OJQJaJhuhs?5OJQJaJh9>95OJQJaJhR)5OJQJaJhR)CJaJhuhhqeCJaJh9>9CJaJn|q|X}x}}}}^~t~ek|@AKLd܁݁LMhiklοuehuhhqe5CJOJQJaJhuhs?5CJOJQJaJhUQ5CJOJQJaJhuCJaJhuhhqe0Je>*CJaJjhuhhqeCJUaJhdyCJaJhuhhqeCJOJQJaJhuhhqehUQCJaJh5YCJaJhCJaJhuhhqeCJaJhR)CJaJ'./z}%')bЇIL*GQvw҉Ӊҽ~p~pp~aajhuhhqeCJUaJhCJOJQJ^JaJ h&hhqeCJOJQJ^JaJhUQCJOJQJ^JaJhuhhqe5CJOJQJaJhuhs?5CJOJQJaJhUQ5CJOJQJaJhCJaJhL"hhqeCJaJhdyCJaJhUQCJaJh5YCJaJhuhhqeCJaJ$Z[]^@ABCFf' Iَߏגגגגגׇyk`X`XhCJaJhhhqeCJaJhuhhqe5OJQJaJhuhs?5OJQJaJh5Y5OJQJaJhUQCJaJhuhhqe5CJOJQJaJhuhs?5CJOJQJaJh5Y5CJOJQJaJhdyCJaJhuCJaJhuhhqeCJaJjhuhhqeCJUaJhuhhqe0Je>*CJaJ!Bfߏ!>ؕ\ ҘOstuvwsss`^gds?igdUdd^gdigdhqegdhqei$a$gdau^gds?9:hijklmy 9:Ͷͤ̀tt_M"hB*CJOJQJ]aJph(h hB*CJOJQJ]aJphhCJOJQJaJh hCJOJQJaJhUCJaJhch0JeCJaJ#j
hchCJUaJhhCJaJjhCJUaJhCJaJhhhqe0Je>*CJ]aJhhhqeCJaJjhhhqeCJUaJRbfhj !%-26789ĸĂzogogogXoXHXgohhhqe0Je>*CJ]aJjhhhqeCJUaJhCJaJhhhqeCJaJhUCJaJ hchU0JeCJOJQJaJ+jhchUCJOJQJUaJh hUCJOJQJaJhUCJOJQJaJjhUCJOJQJUaJhCJOJQJaJh hCJOJQJaJh hCJOJQJZaJ͔-.=HSTUɕ֕וNOXY\]xy{|붮rcSjhUCJOJQJUaJh hCJOJQJaJ(h hB*CJOJQJ]aJph"hB*CJOJQJ]aJphhCJ]aJhhhqeCJ]aJhCJaJhhhqeCJaJhchU0JeCJaJ#jhchUCJUaJhhUCJaJhUCJaJjhUCJUaJ|ɖ˖̖͖(/12bceʗ̗ϿvdTh hCJOJQJ]aJ"hB*CJOJQJ]aJph(h hB*CJOJQJ]aJphhCJOJQJaJh hCJOJQJaJhUCJaJ hchU0JeCJOJQJaJjhUCJOJQJUaJ+jmhchUCJOJQJUaJh hUCJOJQJaJhUCJOJQJaJ̗͗Η
"+,-.lmјҘ٘ټxxhxYNFhCJaJhhhqeCJaJhUhUB*CJaJphhUhhqe0Je>*CJ]aJjhUhhqeCJUaJhUhUCJaJhUhCJaJhUhhqeCJaJhCJOJQJaJhUCJaJhUCJOJQJaJ hchU0JeCJOJQJaJjhUCJOJQJUaJ+jhchUCJOJQJUaJ34opqsՙיؙٙ=>NOUYbcd!"#abrs͵嵭o#jhchUCJUaJhchU0JeCJaJU#jOhchUCJUaJhhUCJaJhUCJaJjhUCJUaJhhhqeCJ]aJhCJaJhhhqe0Je>*CJ]aJhhhqeCJaJjhhhqeCJUaJ*http://science.uniserve.edu.au/pubs/callab/vol3/tintarev.html, 21:46 19/4/04.
Visser,E., et. al. HYPERLINK "http://www.program-transformation.org/twiki/bin/view/Transform" The Program Transformation Wiki, HYPERLINK "http://www.program-transformation.org/twiki/bin/view/Transform" http://www.program-transformation.org/twiki/bin/view/Transform, 21:45 19/4/04.
stuvwhDBhhuhDBCJOJQJaJ# 0&P . A!k"#$%DyKyK0http://www.j-paine.org/$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O56a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"T$$If!vh55n5n5s5O5#v#vn#vs#vO#v:VK#55n5s5O5a"TADyK3http://vmoc.museophile.com/algebra/section3_6.htmlyKfhttp://vmoc.museophile.com/algebra/section3_6.htmlDyK[http://www.ifi.uni-klu.ac.at/Publications/Dissertations/pubfiles/pdffiles/2003-0175-MC.pdfyKhttp://www.ifi.uni-klu.ac.at/Publications/Dissertations/pubfiles/pdffiles/2003-0175-MC.pdfqDyK?http://www.indiana.edu/~statmath/math/maple/algebra/index.htmlyK~http://www.indiana.edu/~statmath/math/maple/algebra/index.html}DyKBhttp://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/ilp.htmlyKhttp://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/ilp.htmleDyK<http://www.j-paine.org/eusprig2001_as_html/eusprig2001.htmlyKxhttp://www.j-paine.org/eusprig2001_as_html/eusprig2001.htmlmDyK>http://science.uniserve.edu.au/pubs/callab/vol3/tintarev.htmlyK|http://science.uniserve.edu.au/pubs/callab/vol3/tintarev.htmlqDyK?http://www.program-transformation.org/twiki/bin/view/TransformyK~http://www.program-transformation.org/twiki/bin/view/TransformlL@LNormal
8^8@OJQJ_HmH sH tH z@qz Heading 11xd$d0%d&d-D@&^x@B*CJEHKHOJQJT@qT Heading 2d@&^@OJQJP@qP Heading 3d@&@CJOJQJ@@q@ Heading 4d@&H@qH Heading 5d@&^CJB@qB Heading 6
@&^6CJ6@q6 Heading 7@&CJ:@q: Heading 8@&6CJ6 @q6 Heading 9 @&CJDA@DDefault Paragraph FontVi@VTable Normal :V44
la(k(No List~O~Block Quotation>$Xd$d%d&d'd-D]^Xa$OJQJ>B@> Body Text$da$DC@DBody Text Indent
^<O"<Body Text Keep$.OB.Picture$P"1PCaption
&Fd<@CJOJQJOR
Part LabelG$dE&#$$d%d+D8-D/0$]^a$@B*CJEHOb
Part TitleE$dlE&#$%d+D8-D/0$]^a$@B*CJTEHOJQJPOPHeading Base$$d@CJKHR>@qRTitled@<$d^@CJ(OJQJPJ@PSubtitledT<x$d@CJ OJQJ<O<Chapter SubtitlevOvCompany Name/$$d&P#$+DH/0$^@CJ KHOJQJO
Chapter Title:$dlE&#$%d+D8-D/]a$@B*CJTEHOJQJJ'JComment ReferenceCJOJQJkHDOD
Footnote Base$dCJ44Comment Text@O@
Table Text <^CJrOqrTitle Cover.!
d$d0]^5@CJ@OJQJ8O"8Document Label"<X@1<Emphasis@CJOJQJkH>*>Endnote ReferenceH*4+R4Endnote Text%NObNHeader Base&$d
!;CJ( @ar(Footer'<Oq<Footer Even(X$d>Oq>Footer First)X$d:Oq:
Footer Odd*X$d@&@Footnote ReferenceH*66
Footnote Text,(@a(Header-OHeader Evenj.
&
FX&d>T @O@Header First/$$da$O
Header Oddj0
&
FX&d>T JOJ
Index Base1hd^h`CJ*
"*
Index 12828
Index 23d^8B8
Index 348d^88
R8
Index 45d^8b8
Index 56d^`!q"`
Index Heading7$d^@CJKHOJQJLOLLead-in Emphasis@CJOJQJkH2(@2Line NumberCJ4/@4List:^`02@0List 2
;^03@0List 3
<p^p04@0List 4
= ^ 05@0List 5
>@^@@0@@
List Bullet?
&F
>6@>
List Bullet 2
@^>7@>
List Bullet 3
Ap^p>8@">
List Bullet 4
B ^ >9@2>
List Bullet 5
C@^@D@B
List ContinuehD
&F>T.`BE@ARBList Continue 2
Ep^pBF@AbBList Continue 3
F ^ BG@ArBList Continue 4
G@^@BH@ABList Continue 5
H^:1@:List Number I
&F
>:@>
List Number 2
J^>;@>
List Number 3
Kp^p><@>
List Number 4
L ^ >=@>
List Number 5
M@^@RORTable HeaderN$<^a$CJOJQJnI@nMessage Header0O$$
H@@pdx]p`a$@CJ>@>
Normal Indent
P^B)@BPage Number@CJOJQJkHNON
Part Subtitle
R$hx6CJKHrO2rReturn Address4S$
pd(&#$+DH0$^@CJ:OB:Section HeadingT\Oq\
Section LabelUh&d^@CJ6OJQJ0Oa0Slogan6@CJxOxSubtitle Cover-W
d$d]^5@CJ0OJQJ4O4Superscript5H*\,\Table of AuthoritiesY
^`FOFTOC BaseZ
P
d^L#LTable of Figures[^`P.PTOA Heading\$d5@KHOJQJ**
TOC 1]@..
TOC 2
^h^h..
TOC 3
_h^h..
TOC 4
`h^h..
TOC 5
ah^h,OA",code
b^@Y2@Document Mapc-D OJQJ8Z@B8
Plain TextdOJQJ0U@Q0 Hyperlink>*B*@V@a@FollowedHyperlink>*B*@Or@Logo
g^@OJQJtH u8O8heading1hmHnHuj^@jNormal (Web)idd[$\$^ @CJOJPJQJaJnHtHBb@Bhqe HTML CodeCJOJPJQJ^JaJe@hqeHTML Preformatted?k
2(
Px4 #\'*.25@9^@OJPJQJ^JnHtH$cden,
3BRSg~md:Q$%oCx v!#/#&(++..... ////////%/&/6/8/:/B/J/P/Q/]/j/l/t/|////////////////////////0
0000 0!0#0%0'0/070?0@0W0_0a0i0q0y0z0|000000000000000000000000000011
1111 1517191;1=1?1@1E1K1M1U1Z1_1`1n1t1v1|1111111111111111111T2224585X5556(6H6p6y6}666666Q7_7o77777777718v8~899::;6;R;;;<<<<&<0<:<N<b<v<<<<<<<<=<=R=h=~===R>S>_>?? @N@x@@BCEEFF5FRFfF{FFFFFFFGG0GAGGGIIIKKXLLNN3O@OXOtOOOOP
PP:PBP_P{PPPPQ3QfQQQQQQR*RVRRR)SrSST TiTTTTUdUUUUV$V;V|VVVVW:WYWxWWWWXXXXX)YwYYYY=ZZZ[[[[[\p\\]^(_Y____`dWdfgggggjikijjHlIll1ogpppt\utuevx{{~~wBf߆q(pk"x0000000i0i00i0i0i0i0i00k0k0k0k0k0k0k0k0i0i0i02 i02 i02 i02 i0i0i0i0i0k0k0k0k000k0k0k000k0k0k0k00k0k0k0000i0i00i0i0i00i0#i0#i0#0i0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0+(0+i01i01k0101k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k01k0101(0+i09k0909k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k09k0909(0+(0+i0S>k0S>k0S>k0S>k0S>k0S>i0S>i0S>i0S>k0S>k0S>0S>k0S>k0S>k0S>k0S>k0S>k0S>k0S>k0S>k0S>k0S>k0S>k0S>k0S>k0S>0S>(0+i0Gk0G0Gi0Gk0G0Gk0Gi0Gk0Gk0G0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0Gk0G0Gi0G(0+i0]- 0]- 0]- 0]- 0]0]i0]0i0d3 i0d1 0dk0d1 0dk0dk0dk0d0dk0d0d00i0Ili0Il0(0gpi0pi0pk0p0pi0pi0p(0gpi0{(0gpk0~i0~(0gpi0B0i0߆0߆i0߆pi0߆i0߆0߆0߆i0߆i0߆i0߆0߆00en+..... ////////%/&/6/8/:/B/J/P/Q/]/j/l/t/|////////////////////////0
0000 0!0#0%0'0/070?0@0W0_0a0i0q0y0z0|000000000000000000000000000011
1111 1517191;1=1?1@1E1K1M1U1Z1_1`1n11111111p\\]^(_Y____`dWdgggggx{{k"Oy00Oy00O900O900O900x
0O9000O900O900O900O900O900O900@0 Oy0 0Oy0 0Oy0 0Oy0 0Oy0 0Oy0 0@0 Oy00Oy00Oy00Oy00Oy00Oy00@0 Oy0
0Oy0
0Oy0
0Oy0
0Oy0
0Oy0
0@0 Oy00Oy00Oy00Oy00Oy00Oy00@0 Oy00Oy00Oy00Oy00Oy00Oy00@0 Oy00 Oy00 Oy00 Oy00 Oy00 Oy00 @0 Oy00 Oy00 Oy00 Oy00 Oy00 Oy00 @0 Oy00 Oy00 Oy00 Oy00 Oy00 Oy00 @0 Oy00 Oy00 Oy00 Oy00 Oy00 Oy00 @0 Oy00 Oy00 Oy00 Oy00 Oy00 Oy00 @0 Oy0!0 Oy0!0 Oy0!0 Oy0!0 Oy0!0 Oy0!0 @0 Oy0#0 Oy0#0 Oy0#0 Oy0#0 Oy0#0 Oy0#0 @0 Oy0%0 Oy0%0 Oy0%0 Oy0%0 Oy0%0 Oy0%0 @0 O90'0 O90'0 O90'0 O90'0 O90'0 Oy0'0 @0 Oy0)0 Oy0)0 Oy0)0 Oy0)0 Oy0)0 Oy0)0 @0 Oy0+0 Oy0+0 Oy0+0 Oy0+0 Oy0+0 Oy0+0 @0 Oy0-0 Oy0-0$6@0w Oy0/0\6@0w Oy0106@0w 0<00-@<00O900<00O900O900O900O900O900O900O900O90000000<001@<000M90`00d
k %/7G<BHROgimrxn||̗swMPQRTUWXZpsuw|}~R!18%8J8t88888 9?9q99999:9:K:v:::;@ENTZ_ekrBwNSVY[\]^_`abcdefghijklmnoqrtvxyz{vO$IadsO####0$6$R&&&&'%',!-S-V---@```````BaQaWaaaqr$rv@wKwxLyhykyyyҀZ]9hl_Չ>}ˋ^ҌY}7ێ(fُKXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX /Xb$
)Dǒk7
CBMb$|Ag'M5=@0(
Z
B
S ?_Hlt69818105
maple_examplerevengstage_2stage_4stage_5F8D20F5E19automatic_pattern_recognitionbowenclermonthart
hofstadterhofstadter2ilppankotintarevvisservla[t+9R>GtSTZX[p("g@
\+9]>GTTX\p(|)*]P,#^Pl#_P#`P#aP#bP$#cPd#dP#eP#fP$#gPd#hP#iP#jP$#kPd#lP#mP#nP$#oPd#pP#qP#rP$#sPd#tP#uP#vP$#wPd#xP#yP#zP#{PT#|P#}P#~P<#P̹#Pt#P#P#P<#P#Pt#P#N,N,V,XKXK`K`KnKnKKKKKKKeLeLlLlLvLvL`h`hhhlllbhag\bio
!"#$%&'()U,`,`,^K^KiKiKtKtKKKKKKKkLkLuLuL|L|Lfhfhhhlllgofnainv
!"#$%&'()=)*urn:schemas-microsoft-com:office:smarttags PlaceName=(*urn:schemas-microsoft-com:office:smarttags PlaceType8*urn:schemas-microsoft-com:office:smarttagstime8&*urn:schemas-microsoft-com:office:smarttagsCity8
*urn:schemas-microsoft-com:office:smarttagsdate9**urn:schemas-microsoft-com:office:smarttagsplace19200421445464748495152DayHourMinuteMonthYear*)(*&*&*&*&*&*&*&*&*&*&*&*)(
\g!
+
@K9<
!"JMOTgma l 2#9#&&&=&E&,,--/02222q3v3336688A:N:::::::???????@"@'@+@1@P@W@`@e@g@l@z@@@@tAzA`BdBUEfEEEEEEEEEFF&F4F8y8|8::<
<A<E<U<Y<i<m<}<<<<<<<<<=!='===}??????&@)@U@Y@@@BB+C1CEEFFAGFGIIIIKKKK[LcLN)NNNNN3O8O|OOOOOOOOP&PEPJPbPgP~PPPPPPPPQQIQQQvQ{QQQQQQQQQRR1R;R]RaRRRRR4S:SyS}SSSTT"T+TkTtTTTTUU!UfUtUUUUUUVVV&V+V=VBV~VVVVVVVW'W-WDWJWcWiWzWWWWWWWW"X(XaXgXXXXX;YAYYYYYYYZ
ZHZNZZZZZ"['[f[l[[[[[\*\+],],_2_____``bbcc;fAfgg%r*rnsvs||%~.~,3ق,puw24ouwpr*,~3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333,p3DGm:Q rP!u!.199S>_>F!FGG3OBO_C_Y_i_____ff~~BfxJ PaineJ PaineJ PaineJ PaineJ Paine
Administrator
AdministratorTERMINAL 10readersamir-|⧤}YRA~-xڗ:(8W Řj #$
[ZV"sUE Ilr 8} po MƋCWG! dm# {, m1K<41wk5 7 .9nO=X=#EUOUQlKV7NYc[wR]hqeauvdy^}02L"DBs?5YBu4;"U&hB..... ////////%/&/6/8/:/B/J/P/Q/]/j/l/t/|////////////////////////0
0000 0!0#0%0'0/070?0@0W0_0a0i0q0y0z0|000000000000000000000000000011
1111 1517191;1=1?1@1E1K1M1U1Z1_1`1n1t1v1|111111111111111111@`L PP)`@``$@``(@`0@Unknown Gz Times New Roman5Symbol3&z Arial?5 z Courier New?&
Arial BlackA&Arial Narrow5&z!TahomaG5
hMS Mincho-3 fg;Wingdings"qhu&&
{I{I$24dTT
3QH?DB AbstractJ Painesamir-
!"#$%&'()*+,Oh+'0\
$
0<DLT
Abstract AbsJ Paine PaNormal.dotsamir.d3miMicrosoft Word 10.0@e@^LP&@2lAR&{՜.+,D՜.+,4hp|
IFSITA
AbstractTitle 8@_PID_HLINKSAx#(W?http://www.program-transformation.org/twiki/bin/view/Transform#(T?http://www.program-transformation.org/twiki/bin/view/TransformI_Q>http://science.uniserve.edu.au/pubs/callab/vol3/tintarev.htmlI_N>http://science.uniserve.edu.au/pubs/callab/vol3/tintarev.htmlEK1http://panko.cba.hawaii.edu/papers/ss/2phase.htm]H<http://www.j-paine.org/eusprig2001_as_html/eusprig2001.htmlUEBhttp://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/ilp.html|<B?http://www.indiana.edu/~statmath/math/maple/algebra/index.html|<??http://www.indiana.edu/~statmath/math/maple/algebra/index.htmlhd<[http://www.ifi.uni-klu.ac.at/Publications/Dissertations/pubfiles/pdffiles/2003-0175-MC.pdf693http://vmoc.museophile.com/algebra/section3_6.html663http://vmoc.museophile.com/algebra/section3_6.html.30http://www.j-paine.org/spreadsheet_algebra.html tintarevI_0>http://science.uniserve.edu.au/pubs/callab/vol3/tintarev.htmlj[-0http://www.j-paine.org/spreadsheet_algebra.htmlilpU*Bhttp://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/ilp.htmlxL'0http://www.j-paine.org/spreadsheet_algebra.htmlhofstadter2$0http://www.j-paine.org/spreadsheet_algebra.html clermonte!0http://www.j-paine.org/spreadsheet_algebra.htmlF5g0http://www.j-paine.org/spreadsheet_algebra.htmlD20e0http://www.j-paine.org/spreadsheet_algebra.htmlF8f0http://www.j-paine.org/spreadsheet_algebra.htmlE19=0http://www.j-paine.org/spreadsheet_algebra.htmlpankoE1http://panko.cba.hawaii.edu/papers/ss/2phase.htm80http://www.j-paine.org/spreadsheet_algebra.htmlpaineG<http://www.j-paine.org/eusprig2001_as_html/eusprig2001.html grossman8 0http://www.j-paine.org/spreadsheet_algebra.htmlpaine]<http://www.j-paine.org/eusprig2001_as_html/eusprig2001.html"0http://www.j-paine.org/spreadsheet_algebra.htmlhart.5http://www.j-paine.org/
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
Root Entry FRR&Data
-1TableXWordDocument%SummaryInformation(DocumentSummaryInformation8CompObjj
FMicrosoft Word Document
MSWordDocWord.Document.89q