ARTICLE

Working with Symbolic Expressions

From Math for Programmers by Paul Orland

from math import sin
def f(x):
return (3*x**2 + x) * sin(x)
Figure 1: Can we write an “expand” function that expands a mathematical expression according to the rules of algebra?
Figure 2: A goal is to write a derivative function in Python, taking an expression for a function and returning an expression for its derivative.

Modeling algebraic expressions

Let’s look closer at the function f(x) = (3x2 + x) sin(x), and see how we can break it down into pieces. Once we’ve gone through this exercise conceptually, we’ll see how to translate our results to Python code.

Breaking an expression into pieces

We can start to model algebraic expressions by breaking them up into smaller expressions. There’s only one meaningful way to break up the expression (3x2 + x) sin(x) it’s the product of 3x2 + x and sin(x).

Figure 3: A meaningful way to break up an algebraic expression into two smaller expressions.
Figure 4: It doesn’t make sense to split the expression up around the plus sign. The original expression isn’t the sum of 3x2 and x · sin(x).
  • 3x2 is the product of the expressions “3” and “x2”
  • x2 is a power — one expression “x” raised to the power of another expression “2”.
  • The expression sin(x) is a function application. Given the expression “sin” and the expression “x”, sin(x) is a new expression.

Building an expression tree

The elements “3,” “x,” “2,” and “sin,” along with the combinators of adding, multiplying, raising to a power, and applying a function, are sufficient to rebuild the whole of the expression (3x2 + x) sin(x). Let’s go through the steps and draw the structure we end up building.

Figure 5: Combining x and 2 with the power combinator to represent the bigger expression x2.
Figure 6: Combining the number 3 with a power to model the product 3x2.
Figure 7: Combining the expression 3x2 with the element x with the sum combinator to get 3x2 + x.
Figure 8: A complete picture showing how to build (3x2 + x) · sin(x) from elements and combinators.

Translating the expression tree to Python

We can think of each combinator as a function which takes one or more expressions as inputs and returns a new expression as an output. In practice, it is also useful to think of a combinator as a named container that holds its inputs. For instance, the result of applying the power combinator to x and 2 should be some object that holds both x and 2 as data. For a power expression like x2, x is called the base and 2 is called the exponent. A Python class equipped to hold a base and an exponent might look like this:

class Power():
def __init__(self,base,exponent):
self.base = base
self.exponent = exponent
class Number():
def __init__(self,number):
self.number = number

class Variable():
def __init__(self,symbol):
self.symbol = symbol
Power(Variable("x"),Number(2))
class Product():
def __init__(self, exp1, exp2):
self.exp1 = exp1
self.exp2 = exp2
Product(Number(3),Power(Variable("x"),Number(2)))
class Sum():
def __init__(self, *exps): #<1>
self.exps = exps
  1. We allow a Sum of any number of terms, meaning we could add two or more expressions together at once.
  2. A Function object stores a string which is its name, like “sin”.
  3. An Apply combinator stores a function and the argument it’s applied to.
  4. I used extra whitespace to make the structure of the expression clearer to see.
Apply(Function("cos"),Sum(Power(Variable("x"),Number("3")), Number(-5)))

Exercises

Exercise: Draw the expression ln(yz) as a tree built out of elements and combinators from this section.

Figure: The structure of the expression ln(yz).
from math import log
def f(y,z):
return log(y**z)
Apply(Function("ln"), Power(Variable("y"), Variable("z")))
class Quotient(Expression):
def __init__(self,numerator,denominator):
self.numerator = numerator
self.denominator = denominator
Quotient(Sum(Variable("a"),Variable("b")),Number(2))
class Difference(Expression):
def __init__(self,exp1,exp2):
self.exp1 = exp1
self.exp2 = exp2
Difference(
Power(Variable('b'),Number(2)),
Product(Number(4),Product(Variable('a'), Variable('c'))))
class Negative():
def __init__(self,exp):
Negative(Sum(Power(Variable("x"),Number(2)),Variable("y")))
A = Variable('a')
B = Variable('b')
C = Variable('c')
Sqrt = Function('sqrt')
Quotient(
Sum(
Negative(B),
Apply(
Sqrt,
Difference(
Power(B,Number(2)),
Product(Number(4), Product(A,C))))),
Product(Number(2), A))
def f(x):
return (3*x**2 + x)*sin(x)

Finding all the variables in an expression

It’s clear that the output value of f(x) depends on the input value

>>> distinct_variables(Variable("z"))
{'z'}
def distinct_variables(exp):
if isinstance(exp, Variable):
return set(exp.symbol)
elif isinstance(exp, Number):
return set()
elif isinstance(exp, Sum):
return set().union(*[distinct_variables(exp) for exp in exp.exps])
elif isinstance(exp, Product):
return distinct_variables(exp.exp1).union(distinct_variables(exp.exp2))
elif isinstance(exp, Power):
return distinct_variables(exp.base).union(distinct_variables(exp.exponent))
elif isinstance(exp, Apply):
return distinct_variables(exp.argument)
else:
raise TypeError("Not a valid expression.")
>>> distinct_variables(f_expression)
{'x'}

Evaluating an expression

Now we’ve got two representations of the same mathematical function f(x). One is the Python function, f, which is good for evaluating the function at a given input value of x. The new one is this tree data structure that describes the structure of the expression defining f(x). It turns out the latter representation has the best of both worlds — we can use it to evaluate f(x) as well, with only a little more work.

from abc import ABC, abstractmethod

class Expression(ABC):
@abstractmethod
def evaluate(self, **bindings):
pass
>>> z.evaluate(x=3,y=2)
48
class Number(Expression):
def __init__(self,number):
self.number = number
def evaluate(self, **bindings):
return self.number
class Variable(Expression):
def __init__(self,symbol):
self.symbol = symbol
def evaluate(self, **bindings):
try:
return bindings[self.symbol]
except:
raise KeyError("Variable '{}' is not bound.".format(self.symbol))
class Product(Expression):
def __init__(self, exp1, exp2):
self.exp1 = exp1
self.exp2 = exp2
def evaluate(self, **bindings):
return self.exp1.evaluate(**bindings) * self.exp2.evaluate(**bindings)
>>> Product(Variable("x"), Variable("y")).evaluate(x=2,y=5)
10
_function_bindings = {
"sin": math.sin,
"cos": math.cos,
"ln": math.log
}

class Apply(Expression):
def __init__(self,function,argument):
self.function = function
self.argument = argument
def evaluate(self, **bindings):
return _function_bindings[self.function.name](self.argument.evaluate(**bindings))
>>>  f_expression.evaluate(x=5)
-76.71394197305108
>>> f(x)
-76.71394197305108

Expanding an expression

Many other things can be done with our expression data structures. In the exercises, you can try your hand building a few more Python functions which manipulate expressions in different ways. I’ll show you one more example for now, which I mentioned at the beginning of the article: expanding an expression. What I mean by this is taking any product or power of sums and carrying it out.

class Expression(ABC):
...
@abstractmethod
def expand(self):
pass
class Number(Expression):
...
def expand(self):
return self
class Sum(Expression):
...
def expand(self):
return Sum(*[exp.expand() for exp in self.exps])
class Apply(Expression):
...
def expand(self):
return Apply(self.function, self.argument.expand())
class Product(Expression):
...
def expand(self):
expanded1 = self.exp1.expand() #<1>
expanded2 = self.exp2.expand()
if isinstance(expanded1, Sum): #<2>
return Sum(*[Product(e,expanded2).expand() for e in expanded1.exps])
elif isinstance(expanded2, Sum): #<3>
return Sum(*[Product(expanded1,e) for e in expanded2.exps])
else:
return Product(expanded1,expanded2) #<4>
  1. First, expand both terms of the product
  2. If the first term of the product is a Sum, take the product with each of its terms multiplied by the second term of the product. Call expand on the result in case the second term of the product is also a Sum.
  3. If the second term of the product is a Sum, multiply each of its terms by the first term of the product.
  4. Otherwise, neither term is a Sum, and the distributive law doesn’t need to be invoked.
>>> Product(Sum(A,B),Sum(Y,Z)).expand()
Product(Sum(Variable("a"),Variable("b")),Sum(Variable("x"),Variable("y")))
>>> f_expression
Sum(Product(Product(3,Power(Variable("x"),2)),Apply(Function("sin"),Variable("x"))),Product(Variable("x"),Apply(Function("sin"),Variable("x"))))

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Manning Publications

Follow Manning Publications on Medium for free content and exclusive discounts.