Instructions
Requirements and Specifications
Source Code
# -*- coding: utf-8 -*-
"""Homework_10_Expressions_as_Classes_test.ipynb
Automatically generated by Colaboratory.
Original file is located at
https://colab.research.google.com/drive/1RJb9uiRcfvcg1sG6weTJW9bOafBuOpxM
Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\rightarrow$Run All).
Make sure you fill in any place that says `YOUR CODE HERE` or "YOUR ANSWER HERE", as well as your name and collaborators below:
"""
NAME = ""
COLLABORATORS = ""
"""---
# Homework 10: Expressions as Classes
Copyright Luca de Alfaro, 2019-21.
License: [CC-BY-NC-ND](https://creativecommons.org/licenses/by-nc-nd/4.0/).
## About This Homework
The homework consists of 9 questions, for a total of 69 points.
The instructions for working on homework assignments are available on Canvas; as a summary:
* Write your code only where indicated via `#YOUR CODE HERE`. If you write code in other places, it will be discarded during grading.
* Do not add/remove cells.
* The tests are implemented with `assert` statements: if they fail, you will see an error (a Python exception). If you see no error, you can assume that they pass.
Once you are done working on it, you can download the .ipynb and [submit it to this form](https://docs.google.com/forms/d/e/1FAIpQLSfuAjv9zfBmo-9hRpcoyWPDzxl3uy7gzv8CePJtcFbg0XP5NQ/viewform?usp=sf_link). This homework is due at **11:59pm on Friday 11 February 2022**.
We will now describe a more sophisticated representation for an expression, based on a hierarchy of classes. The class **Expr** is the generic class denoting an expression. It is an _abstract_ class: only its subclasses will be instantiated. For every operator, such as `+`, there will be a subclass, such as `Plus`. Variables will correspond to a special subclass, called `V`. Numerical constants will be just represented by numbers, and not by subclasses of `Expr`.
## The `Expr` class
The `Expr` class implements the various [methods used to emulate numerical types](https://docs.python.org/3/reference/datamodel.html?#emulating-numeric-types), such as `__add__`, `__sub__`, and so forth. In this way, we can build an expression simply by writing
x = V()
x * 3 / 2
In the above, `V()` creates a variable (an object of class `V`), and assigns it to `x`. Then,
x * 3
will also be an expression, composed of a multiplication node, with children the variable in `x`, and `3`.
The multiplication node is implemented via a subclass `Multiply` of `Expr`.
To make this work, we will define the [`__mul__`](https://docs.python.org/3/reference/datamodel.html#object.__mul__) method of `Expr` so that it produces a `Multiply` object, with as children the two operands being multiplied.
Similarly,
x * 3 / 2
will create an object of class `Divide`, with as left child the `Multiply` node for `x * 3`, and as right child, the number 2. Thus, the [`__truediv__`](https://docs.python.org/3/reference/datamodel.html#object.__truediv__) method of `Expr` will create a `Divide` node.
Expressions can be evaluated. You can assign a value to variables either when you create them:
x = V(value=2)
e = x * 3 / 2
e.eval()
which yields `3`. Or you can assign a value to a variable later:
x = V()
e = x * 3 / 2
x.assign(3)
e.eval()
which again yields `3`.
## Benefits of class-based representation
Compared with the representation of expressions seen in the previous chapter, this class-based representation offers several advantages.
First, we can build expressions in a natural way as shown above, via the over-riding of the usual arithmetic operators.
Second, if we introduce a new operator, all we need is provide the implementation of the new operator: we do not need to modify the shared code that traverses the tree, and add one more case to a long case-analysis. In other words, the code is far more modular. This may seem a small point, but if one were to extend the representation of expressions to involve tensors (matrices) and operations on tensors, as is done in the symbolic representation of expressions used in machine-learning, the number of operators could easily grow to a hundred or more, making a modular approach the only reasonable one.
Third, it becomes possible to attach methods to the expression objects, and as we will see in the next chapter, this can be very useful to implement machine learning frameworks. But later about that.
## Defining an expression class
We define an abstract class `Expr`, representing a generic expression. This generic class has as subclasses the classes that represent the various operators, such as `Plus`, `Minus`, `Multiply`, as well as the variable class `V`. Here is our basic implementation.
"""
class Expr(object):
"""Abstract class representing expressions"""
name = "expr" # Not used, but just to define it.
def __init__(self, *args):
"""An object is created by passing to the constructor the children"""
self.children = args
self.value = None # The value of the expression
self.child_values = None # The values of the children; useful to have
def eval(self):
"""Evaluates the expression."""
# First, we evaluate the children.
self.child_values = [c.eval() if isinstance(c, Expr) else c
for c in self.children]
# Then, we evaluate the expression itself.
self.value = self.op(*self.child_values)
return self.value
def op(self):
"""This operator must be implemented in subclasses; it should
compute self.value from self.values, thus implementing the
operator at the expression node."""
raise NotImplementedError()
def __repr__(self):
"""Represents the expression in a somewhat readable way."""
if len(self.children) == 1:
# Unary operators
return "({}{})".format(self.__class__.name, self.children[0])
elif len(self.children) == 2:
return "({} {} {})".format(
self.children[0], self.__class__.name, self.children[1]
)
# Catch-all.
return "{}({})".format(self.__class__.__name__,
', '.join(repr(c) for c in self.children))
# Expression constructors
def __add__(self, other):
return Plus(self, other)
def __radd__(self, other):
return Plus(self, other)
def __sub__(self, other):
return Minus(self, other)
def __rsub__(self, other):
return Minus(other, self)
def __mul__(self, other):
return Multiply(self, other)
def __rmul__(self, other):
return Multiply(other, self)
def __truediv__(self, other):
return Divide(self, other)
def __rtruediv__(self, other):
return Divide(other, self)
def __neg__(self):
return Negative(self)
"""Variables are created specifying a name, and an initial value. If nothing is specified, variables have random initial values. You can assign a value to a variable using the `assign` method. The `eval` method of a variable simply returns its value. """
import random
import string
class V(Expr):
"""Variable."""
def __init__(self, value=None):
super().__init__()
self.children = []
self.value = random.gauss(0, 1) if value is None else value
self.name = ''.join(
random.choices(string.ascii_letters + string.digits, k=3))
def eval(self):
return self.value
def assign(self, value):
self.value = value
def __repr__(self):
return "V({}, value={})".format(self.name, self.value)
"""Here are the constructors for the other operators; for them, we just need to provide an implementation for `op`, since all the rest is inherited from `Expr`. We actually also define a name, as a class attribute, that we use in the representation method."""
class Plus(Expr):
name = "+"
def op(self, x, y):
return x + y
class Minus(Expr):
name = "-"
def op(self, x, y):
return x - y
class Multiply(Expr):
name = "*"
def op(self, x, y):
return x * y
class Divide(Expr):
name = "/"
def op(self, x, y):
return x / y
class Negative(Expr):
name = "-"
def op(self, x):
return -x
"""We can build and evaluate expressions quite simply."""
e = V(2) + 3
print(e)
print(e.eval())
e = (V() + V(2)) * (2 + V(1))
print(e)
print(e.eval())
"""If we want to be able to assign values to variables, or refer to them in our code later, we need to assign our variable objects to Python variables: """
x = V()
y = V()
e = x + y
print(e.eval()) # This uses the initial random values.
x.assign(2)
y.assign(3)
print(e.eval())
"""### Defining Expression Equality
If we test equality between expressions, we are in for a surprise.
"""
x = V()
e1 = x + 4
e2 = x + 4
e1 == e2
"""Why is the result False?
Python knows how to compare objects that belong to its own types. So you can do comparisons between strings, numbers, tuples, and more, and it all works as expected. This is why we could check equality of expressions represented as trees: those expression trees are composed entirely of standard Python types, namely, strings, numbers, and tuples.
However, `Expr`, `V`, etc, are classes we defined, and Python has no idea of what it means for objects of user-defined classes to be equal.
In this case, Python defaults to considering equal two objects if they are the _same_ object.
The two expressions _e1_ and _e2_ above are not the same object: they are two distinct objects, which just happen to represent the same expression.
If we want to have a notion of expression equality that represents our idea that "two expression objects are equal if they represent the same expression", we need to define equality ourselves.
This can be easily done, by defining an _ _ eq _ _ method. This method [has the form](https://docs.python.org/3/reference/datamodel.html#object.__eq__):
def __eq__(self, other):
...
return
Here, self is the object on which the method is called, and other is another object -- any other object. Our job is to define when the object self is equal to the object other. This can be easily done; using again our way of adding methods to existing classes, we write:
"""
def expr_eq(self, other):
if isinstance(other, Expr):
# The operators have to be the same
if self.__class__ != other.__class__:
return False
# and their corresponding children need to be equal
if len(self.children) != len(other.children):
return False
for c1, c2 in zip(self.children, other.children):
if c1 != c2: return False
return True
else:
return False
Expr.__eq__ = expr_eq
"""If we did not define equality for variables, two variables would be considered equal according to `Expr.__eq__`, since `V` is a subclass of `Expr`. This would yield non-intended consequences (all variables would be considered equal).
Thus, we define equality for variables to be the basic equality for objects: two variables are equal iff they are the same object. In the definition below, `object.__eq__` is this primitive notion of equality, defined over the class `object` of Python, which is the base class for all classes.
"""
V.__eq__ = object.__eq__
x = V()
y = V()
z = x
print(x == y)
print(x == z)
"""Once expression equality is thus defined, we get the expected result when we compare expressions:"""
x = V()
e1 = x + 4
e2 = x + 4
e1 == e2
"""Having to define equality "by hand" is very pedantic, but it does give us the flexibility of defining precisely what it means for two expressions to be equal.
## Variable Occurrence
Now that we have expressions, let us play with them. First, as a warm-up exercise, let us write an `occurs` method for expressions, which checks if a given variable occurs in the expression. First we define it for a variable: of course, a variable occurs in itself only if the variable is the same as the one whose occurrence we are checking.
## Question 1: Variable occurrence in variables
"""
### Variable occurrence in a variable
def v_contains(self, var):
"""Returns True of var is the same as self, and False otherwise."""
# YOUR CODE HERE
return self.name == var.name and self.value == var.value
V.__contains__ = v_contains
## Here you can also test your code.
x = V()
y = V()
print(x in x)
print(x in y)
### Tests for variable occurrence
x = V()
y = V()
assert x in x
assert not x in y
z = x
assert x in z
"""## Question 2: Occurrence of a variable in an expression
Once we define occurrence of a variable in a variable, we can define occurrence in a variable in a general expression. Of course, a variable appears in an expression if it appears in some of its children.
"""
### Occurrence of a variable in an expression
def expr_contains(self, var):
for v in self.children:
f v.name == var.name:
return True
elif var in v.children:
return True
return False
Expr.__contains__ = expr_contains
## Here you can also test your code.
x = V()
y = V()
z = V()
e = x + (2 * y)
print(x in e)
print(y in e)
print(z in e)
## Tests for occurrence: 5 points.
x = V()
y = V()
z = V()
e = x + (2 * y)
assert x in e
assert y in e
assert z not in e
## Hidden tests for occurrence: 5 points.
"""## Variable Substitution
Another fun thing we can do is substitute a variable with an expression. Suppose you define an expression:
x = V()
y = V()
e = (x + 1) * (y + 1)
Suppose you also have another expression:
z = V()
f = y + z
Then, you can replace all occurrences of variable `x` in `e` with expression `f`:
new_e = e.replace(x, f)
and `new_e` should be then equal to:
((x + z) + 1) * (y + 1)
Let us implement variable substitution. Let us begin by defining variable substitution for variables.
## Question 3: Variable replacement for variables
"""
### Variable replacement in variables
def v_replace(self, x, e):
"""If self is x, replaces all occurrences of x with e."""
# YOUR CODE HERE
if self is x:
self = e
return self
V.replace = v_replace
## Here you can also test your code
x = V()
y = V()
z = V()
print(x == x.replace(x, x))
print(y == x.replace(x, y))
print(x == x.replace(y, z))
## Tests for variable replacement in variables. 2 points.
x = V()
y = V()
z = V()
assert x == x.replace(x, x)
assert y == x.replace(x, y)
assert x == x.replace(y, z)
assert x.replace(x, y).replace(y, z) == z
## Other tests for variable replacement. 2 points.
x = V()
y = V()
e = x.replace(x, y + 3 * x)
x.assign(2)
y.assign(3)
assert e.eval() == 9
## Hidden tests for variable replacement. 2 points.
"""We now define variable replacement for expressions. Consider a simple expression:"""
x = V()
y = V()
z = V()
e = x + y
"""Suppose we want to return `e.replace(x, z)`. The idea is:
* carry out the replacement for each child (via a recursive call, as usual),
* then return an expression built out of the replacements.
For instance, consider `e = x + y`. To compute
e.replace(x, z)
we first replace `x` with `z`, and then we return `Plus(z, y)`.
The problem is exactly in the last sentence. A `Plus` object, after carrying out the replacement in the children, should return a `Plus` object with the new children. Similarly, a `Minus` object should return a `Minus` object, a `Multiply` object should return a `Multiply` object, and so forth. If we implement this in the straightforward way, we need to add a `replace` method to all of these classes, so that they can return an object of the appropriate type. This is a lot of work.
Is there a better way? It turns out, yes. In an object,
self.__class__
is the class of the object. So if you want to return a new object of the same class, created say with arguments `x` and `y`, all you need to do is:
self.__class__(x, y)
In this way, if you are in a `Plus` object, `self.__class__` is `Plus`, and everything works.
Using this idea, we, that is, you, can implement the replacement method directly for the `Expr` class.
## Question 4: Replacement for expressions
"""
### Replacement for expressions
def expr_replace(self, x, e):
# YOUR CODE HERE
f, g = self.children
if isinstance(f, Expr):
f = f.replace(x, e)
if isinstance(g, Expr):
g = g.replace(x, e)
return self.__class__(f, g)
Expr.replace = expr_replace
### Here you can debug your code.
x = V()
y = V()
z = V()
e = (1 + x) * (1 + y)
f = e.replace(x, x + z)
print(f)
### Tests for expression replacement. 7 points.
x = V()
y = V()
z = V()
e = (1 + x) * (1 + y)
f = e.replace(x, x + z)
assert f == (1 + (x + z)) * (1 + y)
x.assign(1)
y.assign(2)
z.assign(3)
assert e.eval() == 6
assert f.eval() == 15
e = (x + y) / (x - y)
f = e.replace(x, 2 * x).replace(y, 3 * y)
assert f.eval() == (2 + 6) / (2 - 6)
### Hidden tests for expression replacement. 8 points.
"""## Expression Derivation
We will develop here a method `derivate` such that, for an expression `e`, the method call `e.derivate(x)` returns the derivative of the expression with respect to the variable `x`. As in the previous chapter, we use the following derivation formulas:
* For a constant $c$, $\partial c / \partial x = 0$.
* For a variable $y \neq x$, $\partial y / \partial x = 0$.
* $\partial x / \partial x = 1$.
For operators, we can use:
$$
\begin{align*}
\frac{\partial}{\partial x}(f \pm g) & = \frac{\partial f}{\partial x} \pm \frac {\partial g}{\partial x}, \\[1ex]
\frac{\partial}{\partial x}(f \cdot g) & = \frac{\partial f}{\partial x} \cdot g + f \cdot \frac{\partial g}{\partial x}, \\[1ex]
\frac{\partial}{\partial x}\left(\frac{f}{g}\right) & = \frac{\frac
{\partial f}{\partial x} \cdot g - f \cdot \frac{\partial g}{\partial x}}{g^2}.
\end{align*}
$$
Let us begin with implementing derivation for variables.
## Question 5. Derivation for a variable
"""
### Derivation of variables
def v_derivate(self, x):
# YOUR CODE HERE
if self is x:
return 1
elif isinstance(self, int) or isinstance(self, float):
return 0
else:
return 0
V.derivate = v_derivate
## Here you can debug your code.
x = V()
y = V()
print(x.derivate(x))
print(x.derivate(y))
## Tests for variable derivation
x = V()
y = V()
assert x.derivate(x) == 1
assert x.derivate(y) == 0
"""### Derivation for expressions
This time, there is no clever trick to implement `derivate` as a method of `Expr`, because the derivative behaves in a different way for the different operators. Hence, we will need to implement `derivate` for each individual operator. We let you do it. There are two things to be careful about:
* Children of an operator may not be expressions; they can also be constants such as 2.3 or 4.1.
* If the _new_ children of an expression are all numbers, return the numerical result of the expression rather than a symbolic expression. For example, do not return `Plus(1, 0)`; rather, just return `1`. Note that, if you put the derivatives of the two children in, say, `df` and `dg`, you can simplify automatically by returning `df + dg`, which will return an expression if one of `df` or `dg` is an expression, and a number otherwise.
We give you the solution for `Plus`, mainly because it might be difficult to believe that the solution is this simple.
"""
def plus_derivate(self, x):
f, g = self.children
df = f.derivate(x) if isinstance(f, Expr) else 0
dg = g.derivate(x) if isinstance(g, Expr) else 0
return df + dg
Plus.derivate = plus_derivate
"""## Question 6: Derivation for Minus
You can now work out the case for Minus, which is very similar.
"""
### Derivative of Minus
def minus_derivate(self, x):
# YOUR CODE HERE
f, g = self.children
df = f.derivate(x) if isinstance(f, Expr) else 0
dg = g.derivate(x) if isinstance(g, Expr) else 0
return df - dg
Minus.derivate = minus_derivate
### Here you can debug your code.
x = V()
y = V()
z = V()
e = x - y
e.derivate(y)
### Tests for derivatives of Plus and Minus. 3 points.
x = V()
y = V()
z = V()
e = x + y
assert e.derivate(x) == 1
f = x - y
assert f.derivate(x) == 1
assert f.derivate(y) == -1
h = e + f
assert h.derivate(x) == 2
u = x + 4
assert u.derivate(x) == 1
v = 3 - y
assert v.derivate(x) == 0
assert v.derivate(y) == -1
"""## Question 7: derivative of Negative
Since we are at it, let us take care of unary minus, or `Negative`.
"""
### Derivative of Negative
def negative_derivate(self, x):
# YOUR CODE HERE
f = self.children[0]
if f is x:
return -1
return 0
Negative.derivate = negative_derivate
### Here you can debug your code.
x = V()
y = V()
e = x + (-y)
e.derivate(y)
### Tests for negative. 4 points.
x = V()
y = V()
e = -x
assert e.derivate(x) == -1
assert e.derivate(y) == 0
"""Now for multiplication and divisions. Be careful to use the formulas exactly as given, otherwise the result may not match. E.g. use
$$
\frac{\partial}{\partial x}(f \cdot g) = \frac{\partial f}{\partial x} \cdot g + f \cdot \frac{\partial g}{\partial x}
$$
and _not_, for instance, $\frac{\partial}{\partial x}(f \cdot g) = g \cdot \frac{\partial f}{\partial x} + f \cdot \frac{\partial g}{\partial x}$ (note the swap of the factors in the first term).
We would like you to return simplified expressions. You can again use the trick that, if you have two expressions `df` and `g` (or similar), then `df * g` will be an expression if one of `df` and `g` are expressions, and a number if both `df` and `g` are numbers.
## Question 8: Derivation of multiplication
"""
### Derivative of multiplication.
def multiply_derivate(self, x):
# YOUR CODE HERE
f, g = self.children
df = f.derivate(x) if isinstance(f, Expr) else 0
dg = g.derivate(x) if isinstance(g, Expr) else 0
return df*g+f*dg
Multiply.derivate = multiply_derivate
"""If you did the above right, it will be 4-5 lines wrong. If you wrote much more than that, please think at it again. The solution is quite simple; you can just trust that the operators `*` and `+` will build it. """
## Here you can debug your code.
x = V()
e = x * x
de = e.derivate(x)
de
## Tests for derivative of multiplication. 4 points.
x = V()
y = V(value=2)
e = x * y
# This is ugly. It is. We have not implemented 0, 1 simplifications.
assert e.derivate(x) == 1 * y + x * 0
# To remedy ugliness, we now test numerically.
f = x * x
x.assign(3)
assert f.derivate(x).eval() == 6, f.derivate(x).eval()
x.assign(4)
assert f.derivate(x).eval() == 8, f.derivate(x).eval()
h = 3 * x
assert h.derivate(x).eval() == 3
u = x * 3
assert u.derivate(x).eval() == 3
"""## Question 9: Derivative of division
For division, the expression is:
$$
\frac{\partial}{\partial x}\left(\frac{f}{g}\right) = \frac{\frac
{\partial f}{\partial x} \cdot g - f \cdot \frac{\partial g}{\partial x}}{g^2}.
$$
Note that you can obtain the denominator just by doing `g * g`, if `g` is the second child. Again, the correct solution is quite short.
"""
### Derivative of division
def divide_derivate(self, x):
# YOUR CODE HERE
f, g = self.children
df = f.derivate(x) if isinstance(f, Expr) else 0
dg = g.derivate(x) if isinstance(g, Expr) else 0
return (df*g-f*dg)/(Multiply(g,g))
Divide.derivate = divide_derivate
## Here you can debug your code.
x = V()
y = V()
print("x:", x)
print("y:", y)
e = x / y
e.derivate(y)
### Tests for derivative of division. 4 points.
x = V()
y = V()
e = x / 2
f = e.derivate(x)
x.assign(3)
assert f.eval() == 1/2
g = 1 / x
assert g.derivate(x).eval() == - 1 / 9
assert g.derivate(y).eval() == 0
## Miscellaneous tests. 3 points.
x = V(value=2)
y = V(value=3)
f = (x + 1) * (y + 1) / (x - 1) * (y - 1)
df = f.derivate(x)
assert df.eval() == -16
x.assign(0.5)
y.assign(0.5)
assert df.eval() == 6
## Miscellaneous tests. 3 points.
x = V(value=0)
f = (3 * x * x + 2 * x + 4) / (5 * x * x - 7 * x + 12)
df = f.derivate(x)
assert abs(df.eval() - 0.3611) < 0.01
x.assign(1)
assert df.eval() == 0.53
x.assign(1000)
assert abs(df.eval()) < 0.001
x.assign(-0.5)
assert abs(df.eval() - 0.1) < 0.01
## Final hidden tests on everything. 10 points.