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 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
First, let’s look at the leaves of this tree. We got here instances
of the Symbol
class and the Diofant
version of integers, instance of the
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
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
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
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 Add
and the commutative
arguments of 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')))"
Similarly to subtraction, there is no division class
>>> repr(x/y)
"Mul(Symbol('x'), Pow(Symbol('y'), Integer(-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 func
and
args
.
The head of the object is encoded in the 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 __new__()
class
constructor, which, unlike __init__()
, allows a
different class to be returned from the constructor.
The children of a node in the tree are held in the
args
attribute
>>> expr.args
(2, x⋅y)
Note
Every expression with non-empty args
can
be reconstructed, using
>>> expr.func(*expr.args)
x⋅y + 2
Empty 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)