[Tutor] Re: Algebraic symbol manipulation program idea

[Roeland Rengelink]

Danny Yoo wrote:
> 
> Pythonica seems pretty interesting!  I'm taking a closer look at this now.
> Does anyone have a formal context free grammar for Pythonica or
> Mathematica?  I'm working on a Pythonica recursive descent parser now to
> fix this bug.  Here's the link to what I have so far:
> 
>     http://hkn.eecs.berkeley.edu/~dyoo/python/pythonica/
> 
[snip]

Hi Danny,

Somewhat coincidentally I'm working at something similar. My own
Symbolic package. I wrote a tokenizer/parser that turns an expression
given in a string, into an expression object. Basically something like:

'1+2' -> Add(Number(1), Number(2))
'cos(3*x)' -> Cos(Multiply(Number(3), Variable('x'))

The class hierarchy for this is something like:

Expression      # abstract
   +--BinaryFunction 
   |     +--Add
   |     +--Subtract
   |     +--Multiply
   |     +--Divide
   |     +--Power
   |
   +--UnaryFunction
   |     +--Minus
   |     +--Sin
   |     +--Cos
   |     +--Log
   |     +--...
   |
   +--Atom
         +--Number
         +--Variable

Basically, an Expression is a tree of Expression objects where
BinaryFunctions have two children and UnaryFunctions have one child. The
leaves of the tree are Atoms

As I said. the tokenizer/parser works. But, since it is not based on a
formal grammar, it is rather uninteresting (i.e. not reusable)

The interesting thing is of course the symbolic manipulation of the
expression themselves. For example differentiation, which can be handled
by recursive decent:

class Add(BinaryFunction):
    def differentiate(self, var):
        return Add(self.lhs.differentiate(var),
self.rhs.differentiate(var))

class Variable(Atom):
    def differentiate(self, var):
        if self is var:
             return ONE   # Number(1)
        else:
             return ZERO  # Number(0)
      
I've got that implemented.

Another interesting one is integration, which is of course in many cases
not solvable at all, and for the cases that are solvable, you have to
rely on trying a number of different heuristics. This has gotten me
stumped, but I expected that.

Another problem, which is much harder than I expected, is rewriting
expression. For example:

Add(Add(Number(1), Variable(x)), Number(2)) -> 
Add(Add(Number(1), Number(2)), Variable(x)) ->
Add(Number(3), Variable(x))

which you have to do in order to meaningfully compare expressions.

For example, it's easy to see that:

Subtract(Variable(x), Variable(x)) -> Number(0)

using something like:

class Subtract(BinaryFunction):
    def rewrite(self):
        if self.lhs == self.rhs:
            return ZERO  
        ...other rewrite rules skipped...

However, this one in itself doesn't deal with (easy notation):

(1+x)-(x+1)

Unless I make the comparison function really smart. One rewriting
heuristic may be:

(1+x)-(x+1) --> (1+x)-(1+x) --> 0 , 

but what rule tells us that we should change the order of terms in the
second term?

Well, I tried putting some rewriting heuristics in the Expression
classes, and basically ran into more and more special cases that needed
extra code.

In other words, I'm stuck. As far as I can tell expression rewriting and
integration can only really be handled by looking at the Expression tree
as a whole. Something I would have liked to avoid.

Still, I like this problem a lot. One reason is that I am quite happy
with some of the solutions I did find. I've therefore considered
cleaning up the code that I do have (including documentation) and
submitting it to Useless Python. However, I've now decided to use this
problem as the basis for a tutorial on OO design, illustrating
incremental development of code, refactoring techniques and unittest
practices. No idea where it will lead yet. But I'm having fun writing
that.

In the mean time, anybody that's interested should drop me a line, and
I'll send them the code I have.

Cheers,

Roeland

-- 
r.b.rigilink@chello.nl

"Half of what I say is nonsense. Unfortunately I don't know which half"