[Pythonmac-SIG] Algebraic symbol manipulation program idea

[Shelley Walsh]

I am a mathematics instructor and lately I have been learning Python partly
out of fascination with its potential for helping to explain algebra.
Yesterday I downloaded a symbol manipulation program called Pythonica and
got to thinking that there ought to be an easier way to make such a program.
After giving it some thought I think I may have come up with one, but
particularly with being relatively new to Python, it would take me a while
to work out the details, and right now I don't have the time. I might
eventually get around to it, so writing down a sketch of it in this post is
partly simply an excuse to get it down so that I don't forget it, but I
would like to find out if it has been done before and if not if those of you
who are more experienced with Python think it is feasible. You are also more
than welcome to use the idea and develop the thing yourself if you think it
is a good one, provided you at the very least give me a discount if you sell
it. :-)

The idea is to have the computer to algebra a bit more like at least I would
like for students to do it, by thinking of x as an unknown number and using
simple rules one at a time. No expression ever needs to be dealt with as
more than a single operation at once. At the outer most level all algebraic
expressions are single operations. For simplicity assume for the time being
that we are only dealing with expressions that can be made out of one
variable, the real numbers, and the four basic arithmetic operations. (I
would probably start by leaving out division, but for the present discussion
that doesn't matter.)

I have just learned about classes, and about the polymorphic nature of
Python, so forgive me if I get carried away with both, but it seems that
they can both be put to very good use in this project. We define a class of
algebraic expressions, call it expr. Through it we can general any algebraic
expression we want essentially by only creating one truly new object, the
object that corresponds to the variable, and the user can even call it x if
they want, x=expr(). x is the only instance that has no attributes. All
other instance will have three attributes, left, right, and op. Left and
right are the two operands, and op is the operation. You can get any
expression this way, because the operands can themselves be instances of the
expressions class. They can be expressions or numbers, and the expressions
can themselves either have left and rights or the attributeless x.

class expr:
    pass # for now
    # Among other things define how to do arithmetic operations.
    # See * below.
    # a representation method

x=expr()
a=expr()
a.left=x
a.op="plus"
a.right=1

a represents x+1

b=expr()
b.left=x
b.op="plus"
b.right=2

b represents x+2

c=expr()
c.left=a
c.op="times"
c.right=b

c represents (x+1)(x+2)

* On the simplest level this would be the way the way the operations would
be defined. a+b would be a new object with (a+b).left=a, (a+b).op="plus",
and (a+b).right=b, but there would be also rules for applying the field
properties to simplify when doing the operations. The rules would
effectively define one operation in terms of another so pass to the
definition for that case, possible uses of subclasses for this. At the
outside level all expressions are single operations, so this needn't be too
complicated. You might, for example have a left distributivity rule saying
that when multiplying a*b if a.op="plus" a*b=a.left*b+a.right*b. This would
then pass the job down to the addition definition again. The buck keeps
getting passed until there is nothing more left to do. When no further
properties will help, the unsimplified definitions hold.

For example once the addition and multiplication rules were defined the
forming of c might go something like this.

x=expr()
c=(x+1)*(x+2)

The built in operation priority would be used here so that c would at the
outer be a product of two expression, and each of those expressions would be
a sum of two simpler expressions. No parsing of the expression would be
necessary, because the built in precedence of operations would take care of
it. Python would automatically know that the first thing it needs to do is
the addition x+1. An addition rule for adding the attributeless expression
to a number would apply so that x+1 would become the instance a with
dictionary {left:x, op:"plus", right:1}. Then the same would happen for x+2
giving it a dictionary of {left:x, op:"plus", right:2}. Next would be the
task of multiplying these two objects, and for that multiplication the
program would detect that the left operand had an op of "plus", so a left
distributivity rule would kick in converting the operation to

x*(x+2)+1*(x+2). 

For this again the normal precedence of operations would be used, so no
programming would be necessary to see that what needs to be done is first do
the multiplications and then do the additions. For each of the
multiplications a right distributivity would be applied, so they would be
converted to 

x*x+x*2+1*x+1*2. 

Then there would be a rule for multiplying x by itself that would turn

x*x into an object with dictionary {left:x, op:power:, right:2}

(Yes, I lied, I want to use powers, at least natural number powers as well
as +,-,*,/) For x*2 there would be a rule for putting it in standard order
that would turn it into

2*x 

and then 

2*x would be the object with dictionary {left:2, op:"times", right:x},

and similarly with 1*x.

1*2 would just revert to normal arithmetic, and then we would be looking at
the sum of four things. Normal precedence says this goes from left to right,
so the first thing that is happening is

x^2+2*x. 

Since no simplification rule applies here, this becomes the expression with
dictionary {left:x^2, op:"plus", right: 2*x}, which I will call

(x^2+2x), 

and the next task is to add this to the 1x object (or x object if the
identity rule has been used, if the identity rule has been used, it would
have to be reversed for the next step) For this we need an associativity
rule to convert this to

x^2+(2x+1x) 

(some details of when to use it to be filled in). For 2x+1x a reverse
distributivity rule would be used to convert it to

(2+1)*x, and then the 2+1 would be done according to number arithmetic and
then this would finally become the completed object with dictionary

{left:3, op:"times", right:x} which would be added to x^2 to make

(x^2+3x), 

bringing us to the finally operation of

(x^2+3x)+2. 

Here we might try a associative rule and see if it produced a further
simplification, and when it didn't either leave it that way or bring it back
giving as a final answer either

(x^2+5x)+6 (dictionary {left:(x^2+3x), op:"plus"})

or 

x^2+(3x+2) (dictionary {left:(x^2), op:"plus", right:(3x+2)}).

Probably the former would be best, since it reflects left to right order,
but it may not matter, because in the representation method there might be
some kind of rule for  getting rid of unnecessary parentheses.

One problem with this thinking is that I am kind of thinking in APL, where
you can define a function in terms of itself, when I am thinking about it,
and I don't think you can do that in Python. But perhaps there is a way
around that. I may also have that problem with my ideas for writing a
representation method in very simple way, because they seem to depend on it
being able to call itself.

One goal I would want for this, besides it working would be for it to be
object oriented/modularized in a way that would make the code itself
understandable to algebra students with little knowledge of python by doing
such things as giving the standard mathematical names to the properties
being used in the simplifications, so for example one might define a
distributivity function and call it when doing the above conversion
a*b=a.left*b+a.right*b. I would also be interesting to make this a project
that could be gradually built on, and maybe students could build it
themselves in the course of their algebra class as an extra credit project,
adding new simplification tricks as they learn them.

Thank you for listening.
-- 
Shelley Walsh
Shelley@shells.demon.co.uk
http://homepage.mac.com/shelleywalsh