Creating a Computer Algebra System

Computer, do my math homework

One of the first programs I wrote in middle school was a fraction calculator with the four basic arithmetic operations. Part of what attracted me to programming in the first place was the ability to automate out repetitive tasks. I probably spent ten times as long on that homework as was necessary, but it actually gave me a better understanding of fractions (which was certainly not my original intent).

When I got to calculus I had a new target for automation: algebra. I was familiar, of course, with systems like Wolfram Alpha which can perform almost any algebraic act you can think of, but I wanted to make my own. Just to see if I could.

What's in an expression?

That which we write (x+3)(y+2), in any other representation would graph just the same.

For example, we might want to expand this out to x*y+3y+2x+6. A successful CAS will need to recognize that these are equivalent expressions.

There are two big problems with doing computerized algebra. The first is figuring out an efficient data structure to represent expressions, and the second is determining when expressions are equivalent.

The answer to the first question is to use trees, my single favorite data structure by a wide margin. The internal nodes are operations and the leaf nodes are either numbers or variables. Here is an example tree for (x+3)(x+2):

The answer to the second question is a lot trickier and took me a couple of months to reason through. Part of the answer is to simplify all expressions as much as possible. We can do this by writing a set of rules which we apply to all expressions. This would include operations like expanding multiplication over addition, combining constant terms when possible, and rewriting subtraction as adding a negative number.

Wait, what? Why would you rewrite subtraction as adding a negative number? We need to be able to tell if x-y and x+(-1)*y are equivalent, so one of them has to be rewritten. If we standardize to x-y, then any rule which applies to addition would need to have a second form to apply to subtraction. If we standardize to x+(-1)*y, then we can just reuse our addition rules.

If you think about it, we do this same thing as humans, but often we are a lot less consistent about which forms we choose to standardize to, depending on the problem at hand. Our brains are great at creating shortcuts whereas a machine has to apply each rule in order, possibly multiple times, in order to guarantee a correct solution.

Hacky Workarounds

Another problem is being able to tell if x*y*z is the same as z*x*y. Spoiler alert, it is. My solution to this is to sort the terms according to their hash. The benefit of this approach is that we can apply this even to more complicated terms by converting the expressions to a string and hashing that string.

One problem born out of the use of trees is that there are sometimes multiple trees representing the same expression due to associativity. Here's an example:

As long as you choose a standard way of writing it, this problem can be dealt with, you just have to be careful.

Okay that's great, but how do you actually code this?

My implementation uses binary expression trees to represent all operations, and a symbol class to represent variables. To create rules, I decided to create a set of find-and-replace objects.

But the way I did it is quite clever I think. Just as regular expressions which operate on text just as they are written in text, I reused the binary expression instances to represent the structure of the rules and I used symbol instances to represent capture groups. I then added an extra layer of filtering over capture groups to do things like detecting constants.

Implementation

My implementation in Python is available on my GitHub. This includes the full set of rules necessary for evaluating addition, subtraction, multiplication, division, and exponentiation, as well as a suite of fairly comprehensive test cases.

Truth be told, I don't use this system often if at all. But now when I go to Wolfram Alpha, I feel more comfortable letting the computer do the work, secure in the knowledge of how it works.

And that's what this really was about: learning. Just as in middle school, I have come away with a better understanding of how both humans and computers do algebra.

So remember kids, eat your fractions!