Permalink
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
247 lines (177 sloc) 7.26 KB

Expression Trees

Most generic interface to represent a mathematical expression in Diofant is a tree. Let us take the expression

>>> x*y + x**2
 2
x  + x⋅y

We can see what this expression looks like internally by using :func:`repr`

>>> repr(_)
"Add(Pow(Symbol('x'), Integer(2)), Mul(Symbol('x'), Symbol('y')))"

The easiest way to tear this apart is to look at a diagram of the expression tree

.. graphviz::

    digraph{

    # Graph style
    "bgcolor"="transparent"
    "ordering"="out"
    "rankdir"="TD"

    #########
    # Nodes #
    #########

    "Add(Pow(Symbol('x'), Integer(2)), Mul(Symbol('x'), Symbol('y')))_()" ["color"="black", "label"="Add", "shape"="ellipse"];
    "Pow(Symbol('x'), Integer(2))_(0,)" ["color"="black", "label"="Pow", "shape"="ellipse"];
    "Symbol('x')_(0, 0)" ["color"="black", "label"="Symbol('x')", "shape"="ellipse"];
    "Integer(2)_(0, 1)" ["color"="black", "label"="Integer(2)", "shape"="ellipse"];
    "Mul(Symbol('x'), Symbol('y'))_(1,)" ["color"="black", "label"="Mul", "shape"="ellipse"];
    "Symbol('x')_(1, 0)" ["color"="black", "label"="Symbol('x')", "shape"="ellipse"];
    "Symbol('y')_(1, 1)" ["color"="black", "label"="Symbol('y')", "shape"="ellipse"];

    #########
    # Edges #
    #########

    "Add(Pow(Symbol('x'), Integer(2)), Mul(Symbol('x'), Symbol('y')))_()" -> "Pow(Symbol('x'), Integer(2))_(0,)";
    "Add(Pow(Symbol('x'), Integer(2)), Mul(Symbol('x'), Symbol('y')))_()" -> "Mul(Symbol('x'), Symbol('y'))_(1,)";
    "Pow(Symbol('x'), Integer(2))_(0,)" -> "Symbol('x')_(0, 0)";
    "Pow(Symbol('x'), Integer(2))_(0,)" -> "Integer(2)_(0, 1)";
    "Mul(Symbol('x'), Symbol('y'))_(1,)" -> "Symbol('x')_(1, 0)";
    "Mul(Symbol('x'), Symbol('y'))_(1,)" -> "Symbol('y')_(1, 1)";
    }

First, let's look at the leaves of this tree. We got here instances of the :class:`~diofant.core.symbol.Symbol` class and the Diofant version of integers, instance of the :class:`~diofant.core.numbers.Integer` class, even technically we input integer literal 2.

What about x*y? As we might expect, this is the multiplication of x and y. The Diofant class for multiplication is :class:`~diofant.core.mul.Mul`

>>> repr(x*y)
"Mul(Symbol('x'), Symbol('y'))"

Thus, we could have created the same object by writing

>>> Mul(x, y)
x⋅y

When we write x**2, this creates a :class:`~diofant.core.power.Pow` class instance

>>> repr(x**2)
"Pow(Symbol('x'), Integer(2))"

We could have created the same object by calling

>>> Pow(x, 2)
 2
x

Now we get to our final expression, x*y + x**2. This is the addition of our last two objects. The Diofant class for addition is :class:`~diofant.core.add.Add`, so, as you might expect, to create this object, we also could use

>>> Add(Pow(x, 2), Mul(x, y))
 2
x  + x⋅y

Note

The arguments of :class:`~diofant.core.add.Add` and the commutative arguments of :class:`~diofant.core.mul.Mul` are stored in an order, which is independent of the order inputted.

There is no subtraction class. x - y is represented as x + (-1)*y

>>> repr(x - y)
"Add(Symbol('x'), Mul(Integer(-1), Symbol('y')))"
.. graphviz::

    digraph{

    # Graph style
    "bgcolor"="transparent"
    "ordering"="out"
    "rankdir"="TD"

    #########
    # Nodes #
    #########

    "Add(Symbol('x'), Mul(Integer(-1), Symbol('y')))_()" ["color"="black", "label"="Add", "shape"="ellipse"];
    "Symbol('x')_(0,)" ["color"="black", "label"="Symbol('x')", "shape"="ellipse"];
    "Mul(Integer(-1), Symbol('y'))_(1,)" ["color"="black", "label"="Mul", "shape"="ellipse"];
    "Integer(-1)_(1, 0)" ["color"="black", "label"="Integer(-1)", "shape"="ellipse"];
    "Symbol('y')_(1, 1)" ["color"="black", "label"="Symbol('y')", "shape"="ellipse"];

    #########
    # Edges #
    #########

    "Add(Symbol('x'), Mul(Integer(-1), Symbol('y')))_()" -> "Symbol('x')_(0,)";
    "Add(Symbol('x'), Mul(Integer(-1), Symbol('y')))_()" -> "Mul(Integer(-1), Symbol('y'))_(1,)";
    "Mul(Integer(-1), Symbol('y'))_(1,)" -> "Integer(-1)_(1, 0)";
    "Mul(Integer(-1), Symbol('y'))_(1,)" -> "Symbol('y')_(1, 1)";
    }

Similarly to subtraction, there is no division class

>>> repr(x/y)
"Mul(Symbol('x'), Pow(Symbol('y'), Integer(-1)))"
.. graphviz::

    digraph{

    # Graph style
    "bgcolor"="transparent"
    "ordering"="out"
    "rankdir"="TD"

    #########
    # Nodes #
    #########

    "Mul(Symbol('x'), Pow(Symbol('y'), Integer(-1)))_()" ["color"="black", "label"="Mul", "shape"="ellipse"];
    "Symbol('x')_(0,)" ["color"="black", "label"="Symbol('x')", "shape"="ellipse"];
    "Pow(Symbol('y'), Integer(-1))_(1,)" ["color"="black", "label"="Pow", "shape"="ellipse"];
    "Symbol('y')_(1, 0)" ["color"="black", "label"="Symbol('y')", "shape"="ellipse"];
    "Integer(-1)_(1, 1)" ["color"="black", "label"="Integer(-1)", "shape"="ellipse"];

    #########
    # Edges #
    #########

    "Mul(Symbol('x'), Pow(Symbol('y'), Integer(-1)))_()" -> "Symbol('x')_(0,)";
    "Mul(Symbol('x'), Pow(Symbol('y'), Integer(-1)))_()" -> "Pow(Symbol('y'), Integer(-1))_(1,)";
    "Pow(Symbol('y'), Integer(-1))_(1,)" -> "Symbol('y')_(1, 0)";
    "Pow(Symbol('y'), Integer(-1))_(1,)" -> "Integer(-1)_(1, 1)";
    }

We see that x/y is represented as x*y**(-1).

But what about x/2? Following the pattern of the previous example, we might expect to see Mul(x, Pow(Integer(2), -1)). But instead, we have

>>> repr(x/2)
"Mul(Rational(1, 2), Symbol('x'))"

Rational numbers are always combined into a single term in a multiplication, so that when we divide by 2, it is represented as multiplying by 1/2.

Walking the Tree

Let's look at how to dig our way through an expression tree, using a very generic interface --- attributes :attr:`~diofant.core.basic.Basic.func` and :attr:`~diofant.core.basic.Basic.args`.

The head of the object is encoded in the :attr:`~diofant.core.basic.Basic.func` attribute

>>> expr = 2 + x*y; expr
x⋅y + 2
>>> expr.func
<class 'diofant.core.add.Add'>

The class of an object need not be the same as the one used to create it

>>> Add(x, x)
2⋅x
>>> _.func
<class 'diofant.core.mul.Mul'>

Note

Diofant classes heavy use of the :meth:`~object.__new__` class constructor, which, unlike :meth:`~object.__init__`, allows a different class to be returned from the constructor.

The children of a node in the tree are held in the :attr:`~diofant.core.basic.Basic.args` attribute

>>> expr.args
(2, x⋅y)

Note

Every expression with non-empty :attr:`~diofant.core.basic.Basic.args` can be reconstructed, using

>>> expr.func(*expr.args)
x⋅y + 2

Empty :attr:`~diofant.core.basic.Basic.args` signal that we have hit a leaf of the expression tree

>>> x.args
()
>>> Integer(2).args
()

This interface allows us to write recursive generators that walk expression trees either in post-order or pre-order fashion

>>> tuple(preorder_traversal(expr))
(x⋅y + 2, 2, x⋅y, x, y)
>>> tuple(postorder_traversal(expr))
(2, x, y, x⋅y, x⋅y + 2)