Instructions
Objective
Write a program to solve variable and expression problems in python.
Requirements and Specifications
Question 1: Evaluating expressions with respect to a variable valuation.
The function `simplify` above can perform all numerical computations, but stops whenever it encounters a variable. It cannot do any better, in fact, because it does not know the values of variables.
If we specify values for variables, we can then use those values in the computation, replacing each variable whose value is specified with the value itself.
A _variable valuation_ is a mapping from variables to their values; we can represent it simply as a dictionary associating to each variable a number:
Question 2: Variable Occurrences
Let us start by writing the function `variables` such that, if `e` is an expression, `variables(e)` is the set of variables that appear in it.
Question 3: Value equality
Now we let you write the `value_equality` method.
Given the two expressions $e$ and $f$, first compute the set of variables $V$ that appear in either $e$ or $f$.
Then, the idea consists in performing `num_sample` times the following test for equality:
* First, produce a variable assignment (a dictionary) mapping each variable in $V$ to a random value. Choose these random values from the gaussian distribution centered around 0 and with standard deviation 10 (for instance; any continuous distribution with infinite domain would work). You can obtain such numbers using [`random.gauss(0, 10)`](https://docs.python.org/3/library/random.html#random.gauss).
* Then, compute the values of $e$ and $f$ with respect to that variable evaluation. If the values are closer than a specified tolerance `tolerance`, you consider $e$ and $f$ equal (for that variable valuation). Otherwise, you can stop and return that $e$ and $f$ are different.
If you can repeat the process `num_sample` times, and $e$ and $f$ are considered equal every time, then you declare them equal.
Source Code
# -*- coding: utf-8 -*-
"""Copy of Homework_9_test.ipynb
Automatically generated by Colaboratory.
Original file is located at
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 = ""
"""---
# CSE 30 Winter 2022 - Homework 9
### Instructions
Please disregard the YOUR NAME and COLLABORATORS above. They are put there atomatically by the grading tool.
You can find instructions on how to work on a homework on Canvas. Here is a short summary:
### Submitting your work
To submit your work:
* First, click on "Runtime > Restart and run all", and check that you get no errors. This enables you to catch any error you might have introduced, and not noticed, due to your running cells out of order.
* Second, download the notebook in .ipynb format (File > Download .ipynb) and upload the .ipynb file to [this form](https://docs.google.com/forms/d/e/1FAIpQLSdGYnfVzHtzq5gtNDJu9zN1ysB2-OMi4-9Mfk5sayovAWpOgQ/viewform?usp=sf_link).
You can submit multiple times; the last submission before the deadline is the one that counts. This homework is due by **11:59pm on Wednesday 9 February, 2022**.
### Homework format
For each question in this notebook, there is:
* A text description of the problem.
* One or more places where you have to insert your solution. You need to complete every place marked:
`# YOUR CODE HERE`
and you should not modify any other place.
* One or more test cells. Each cell is worth some number of points, marked at the top. You should not modify these tests cells. The tests pass if no error is printed out: when there is a statement that says, for instance:
`assert x == 2`
then the test passes if `x` has value 2, and fails otherwise. You can insert a `print(x)` (for this case!) somewhere if you want to debug your work; it is up to you.
### Notes:
* Your code will be tested both according to the tests you can see (the `assert` statements you can see), _and_ additional tests. This prevents you from hard-coding the answer to the particular questions posed. Your code should solve the _general_ intended case, not hard-code the particular answer for the values used in the tests.
* **Please do not delete or add cells!** The test is autograded, and if you modify the test by adding or deleting cells, even if you re-add cells you delete, you may not receive credit.
* **Please do not import modules that are not part of the [standard library](https://docs.python.org/3/library/index.html).** You do not need any, and they will likely not available in the grading environment, leading your code to fail.
* **If you are inactive too long, your notebook might get disconnected from the back-end.** Your work is never lost, but you have to re-run all the cells before you continue.
* You can write out print statements in your code, to help you test/debug it. But remember: the code is graded on the basis of what it outputs or returns, not on the basis of what it prints.
* **TAs and tutors have access to this notebook,** so if you let them know you need their help, they can look at your work and give you advice.
### Grading
Each cell where there are tests is worth a certain number of points. You get the points allocated to a cell only if you pass _all_ the tests in the cell.
The tests in a cell include both the tests you can see, and other, similar, tests that are used for grading only. Therefore, you cannot hard-code the solutions: you really have to solve the essence of the problem, to receive the points in a cell.
### Code of Conduct
* Work on the test yourself, alone.
* You can search documentation on the web, on sites such as the Python documentation sites, Stackoverflow, and similar, and you can use the results.
* You cannot share your work with others or solicit their help.
We will develop a data structure to represent arithmetic expressions containing variables, such as $3 + 4$ or $2 + x * (1 - y)$.
What is an expression? An expression consists of one of these:
- A number
- A variable
- If $e_1$ and $e_2$ are expressions, then $e_1 + e_2$, $e_1 - e_2$, $e_1 * e_2$, and $e_1 / e_2$ are also expressions.
Formally, the set of expressions is the _least_ set constructed according to the rules above.
Thus, an expression can be either a constant, representing numbers and variables, or a composite expression, consisting of an operator, a left expression, and a right expression.
There are (at least) two ways of representing expressions. The simplest way is to represent expressions as trees, and define operations on them.
The more sophisticated way consists in representing expressions via classes: there will be one class for variable and constants, and one class representing composite expressions; both of these classes will be subclasses of a generic "expression" class.
In this chapter, we will represent expression as trees, to gain experience with writing recursive functions on trees; in the next chapter, we will show how to represent them more elegantly as classes.
We will represent expressions as trees. A number will be represented via a number; a variable via a string, and the expression $e_1 \odot e_2$ via the tuple $(\odot, e_1, e_2)$, for $\odot \in \{+, -, *, / \}$.
For example, we will represent $2 * (x + 1)$ via:
('*', 2, ('+', 'x', 1))
"""
e = ('*', 2, ('+', 'x', 1))
"""In particular, we will consider expressions built out of the four arithmetic operators `"+"`, `"-"`, `"*"`, `"/"`.
### A compute function
Let us define a function compute() that takes one such expression, and returns the expression obtained by performing all possible numerical computation.
We consider first the simple case of an expression where the only operators that can appear are `+` and `-`, and where there are no variables.
Let us create an exception to raise when we cannot interpret an expression.
"""
class IllegalOperator(Exception):
pass
"""Let us define a helper function `calc`, which takes as argument an operator and two numbers, and computes the required operation. It will make it easier to write the rest of the code. """
def calc(op, left, right):
if op == "+":
return left + right
elif op == "-":
return left - right
elif op == "*":
return left * right
elif op == "/":
return left / right
else:
raise IllegalOperator(op)
"""With this, we can write our compute method as follows. """
def compute(e):
if isinstance(e, tuple):
# We have an expression.
op, l, r = e
# We compute the subexpressions.
ll = compute(l)
rr = compute(r)
# And on the basis of those, the whole expression.
return calc(op, ll, rr)
else:
# base expression; just return the number.
return e
compute(("+", 4, 5))
compute(("+", ("-", 3, 1), ("+", 4, 9)))
"""## Expressions with variables
If an expression can have variables, we can distinguish three types of expressions:
- Numbers
- Variables
- Composite expressions.
To facilitate writing code, let us define for you three helper functions that tell us the type of an expression.
"""
from numbers import Number # The mother class of all numbers.
def isnumber(e):
return isinstance(e, Number)
def isvariable(e):
return isinstance(e, str)
def iscomposite(e):
return isinstance(e, tuple)
"""The idea we use to simplify an expression is the following:
* If the expression is a Number, you return a number: it's already simplified.
* If the expression is a variable, you return the variable (that is, the expression unchanged); there is nothing to be done.
* If the expression is an operation, such as "+", "-", ..., then you consider the right and left children, and you reason:
* If all the two children are numbers, then you can compute the operation and return the result.
* Otherwise, again, there is nothing that can be done, and you return the expression unchanged.
"""
def simplify(e):
if isinstance(e, tuple):
op, l, r = e
# We simplify the children expressions.
ll = simplify(l)
rr = simplify(r)
# We compute the expression if we can.
if isnumber(ll) and isnumber(rr):
return calc(op, ll, rr)
else:
return (op, ll, rr)
else:
# Leaf. No simplification is possible.
return e
"""Let's see how this works."""
simplify(3)
simplify(("+", "x", 1))
"""Yes, there was nothing we could simplify. Let's try now with something we can simplify: """
simplify(('-', 5, 4))
"""Can we simplify bigger expressions? """
simplify( ('+', 6, ('-', 7, 2)) )
"""## Question 1: Evaluating expressions with respect to a variable valuation.
The function `simplify` above can perform all numerical computations, but stops whenever it encounters a variable. It cannot do any better, in fact, because it does not know the values of variables.
If we specify values for variables, we can then use those values in the computation, replacing each variable whose value is specified with the value itself.
A _variable valuation_ is a mapping from variables to their values; we can represent it simply as a dictionary associating to each variable a number:
"""
varval = {'x': 3, 'y': 8}
"""You can extend the evaluation function to take as input a variable valuation. The idea is that, when you find a variable, you try to see whether its value is specified in the variable valuation. If it is, you can replace the variable with the value, and carry on. If it is not, you leave the variable as it is, since you cannot evaluate it.
To check if a variable (a string) `s` is in a dictionary `d`, you can test
s in d
and to get the value, in case it is present, you can just do `d[s]` of course. We let you develop the code.
"""
### Evaluating an expression with respect to a variable evaluation
def compute(e, varval={}):
if isinstance(e, tuple):
op, l, r = e
ll = compute(l, varval)
rr = compute(r, varval)
if isnumber(ll) and isnumber(rr):
return calc(op, ll, rr)
else:
return (op, ll, rr)
else:
if isinstance(e, str) and e in varval:
return varval[e]
return e
"""Let us play with this. """
## You can modify this cell to test your code.
e = ('*', 2, ('+', 'x', ('-', 3, 2)))
print(compute(e))
print(compute(e, varval={'x': 6}))
"""If we provide the values for only some of the variables, the compute function defined above, will plug in the values for those variables and perform all computations possible. Of course, if the expression contains variables for which the valuation does not specify a value, the resulting expression will still contain those variables: it will not be simply a number. In computer science, evaluating an expression as far as possible using the values for a subset of the variables is knwon as _partial evaluation_."""
## Tests for compute. 10 points.
e = 'x'
assert compute(e) == 'x'
assert compute(e, varval={'x': 3}) == 3
e = ('*', 2, ('+', 'x', ('-', 3, 2)))
assert compute(e) == ('*', 2, ('+', 'x', 1))
assert compute(e, varval={'x': 6}) == 14
assert compute(e, varval={'y': 10}) == ('*', 2, ('+', 'x', 1))
e = ('+', ('-', 'yy', 3), ('*', 'x', 4))
assert compute(e, varval={'x': 2}) == ('+', ('-', 'yy', 3), 8)
assert compute(e, varval={'yy': 3}) == ('+', 0, ('*', 'x', 4))
assert compute(e, varval={'x': 2, 'yy': 3}) == 8
### Hidden tests for compute. 10 points.
"""## When are two expressions equal?
> _Or: it's better to be lucky than to be smart._
> _Or: if you don't know how to do it right, do it at random._
> _Or: the power of randomization._
We now consider the following problem: given two expressions $e$ and $f$, how can we decide whether they are equal in value, that is, whether they yield always the same value for all values of the variables?
This _"value equality"_ is a different notion from the structural equality we defined before. For instance, the two expressions `("+", "x", 1)` and `("-", (*, 2, "x"), "x")` are not structurally equal, but they are equal in values.
How can we test for value equality of expressions? There are two ways: the high road, and the pirate road. Of course, we take the pirate road.
The high-road approach consists in trying to demonstrate, in some way, that the two expressions are equal. One way of doing so would be to define a set of [rewriting rules](https://en.wikipedia.org/wiki/Rewriting) for expressions, that try to transform one expression into the other; this would mimick the process often done by hand to show that two expressions are equal. Another way would be to use theorem provers that can reason about expressions and real numbers, such as [PVS](https://pvs.csl.sri.com). The problem is that these approaches are a lot of work. Is there a way to be lazy, and still get the job done?
There is, it turns out. Suppose you have two expressions $f, g$ containing variable $x$ only. The idea is that if $f$ and $g$ are built with the usual operators of algebra, it is exceedingly unlikely for $f$ and $g$ to give the same value many values of $x$, and yet not be always equal. This would not be true if our expressions could contain if-then-else statements, but for the operators we defined so far, it holds. Indeed, one could be more precise, and try to come up with a theorem of the form:
> If $f$ and $g$ have "zerosity" $n$, and are equal for $n+1$ values of $x$, then they are equal for all values of $x$.
We could then try to define the "zerosity" of an expression to make this hold: for example, for two polynomials of degree at most $d$, once you show that they are equal for $d+1$ points, they must be equal everywhere ([why?](https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra)). But this again would be a smart approach, and we are trying to see if we can solve the problem while being as stupid as possible. So our idea will simply be: pick 1000 values of $x$ at random; if the two expressions are equal for all the values, then they must be equal everywhere. This is a somewhat special case of a [Monte Carlo method](https://en.wikipedia.org/wiki/Monte_Carlo_method), a method used to estimate the probability of complex phenomena (where expression equality is our phenomenon).
There are only two wrinkles with this. The first is that an expression can contain many variables, and we have to try to value assignments for all of the variables. This is easy to overcome; we just need some helper function that gives us the set of variables in a function. The second wrinkle is: how do we generate the possible value assignments? How big do these values need to be on average? According to what probability distribution? We could dive into a lot of theory and reasoning about how to compute appropriate probability distributions, but since our goal is to be stupid, we will use one of the simplest distributions with infinite domain: the Gaussian one.
## Question 2: Variable Occurrences
Let us start by writing the function `variables` such that, if `e` is an expression, `variables(e)` is the set of variables that appear in it.
"""
### Exercise: define `variables`
def variables(e):
if isinstance(e, tuple):
op, l, r = e
ll = variables(l)
rr = variables(r)
return ll | rr
else:
res = set()
if isinstance(e, str):
res.add(e)
return res
### Here you can write your own test code.
### 10 points. Tests for `Expr.variables`
e = ('*', ('+', 'x', 2), ('/', 'x', 'yay'))
assert variables(e) == {'x', 'yay'}
"""## Question 3: Value equality
Now we let you write the `value_equality` method.
Given the two expressions $e$ and $f$, first compute the set of variables $V$ that appear in either $e$ or $f$.
Then, the idea consists in performing `num_sample` times the following test for equality:
* First, produce a variable assignment (a dictionary) mapping each variable in $V$ to a random value. Choose these random values from the gaussian distribution centered around 0 and with standard deviation 10 (for instance; any continuous distribution with infinite domain would work). You can obtain such numbers using [`random.gauss(0, 10)`](https://docs.python.org/3/library/random.html#random.gauss).
* Then, compute the values of $e$ and $f$ with respect to that variable evaluation. If the values are closer than a specified tolerance `tolerance`, you consider $e$ and $f$ equal (for that variable valuation). Otherwise, you can stop and return that $e$ and $f$ are different.
If you can repeat the process `num_sample` times, and $e$ and $f$ are considered equal every time, then you declare them equal.
"""
### Exercise: implementation of value equality
import random
def value_equality(e, f, num_samples=1000, tolerance=1e-6):
"""Return True if the two expressions self and other are numerically
equivalent. Equivalence is tested by generating
num_samples assignments, and checking that equality holds
for all of them. Equality is checked up to tolerance, that is,
the values of the two expressions have to be closer than tolerance.
It can be done in less than 10 lines of code."""
ve = variables(e)
vf = variables(f)
vs = ve | vf
for _ in range(num_samples):
assignment = {}
for v in vs:
assignment[v] = random.uniform(0.001, 1000000)
res_e = compute(e, assignment)
res_f = compute(f, assignment)
if abs(res_e - res_f) > tolerance:
return False
return True
### Here you can test your solution.
### 5 points: Tests for value equality
assert value_equality('x', 'x')
assert value_equality(3, 3)
assert not value_equality(3, 'x')
e1 = ('+', ('*', 'x', 1), ('*', 'y', 0))
e2 = 'x'
assert value_equality(e1, e2)
e3 = ('/', ('*', 'x', 'x'), ('*', 'x', 1))
e3b = ('/', ('*', 'x', 'y'), ('*', 'x', 1))
assert value_equality(e1, e3)
assert not value_equality(e1, e3b)
e4 = ('/', 'y', 2)
assert not value_equality(e1, e4)
assert not value_equality(e3, e4)
e5 = ("+", "cat", ("-", "dog", "dog"))
assert value_equality(e5, "cat")
## 10 points: hidden tests for value equality.
"""## Symbolic Expressions
The notation we developed enables the representation of _symbolic expressions:_ expressions in which not only numbers appear, but also symbols. Accordingly, we can perform _symbolic_ operations on the expressions: operations that encode what you do with pencil and paper when you work on an expression.
Our first symbolic operations will be the implementation of _derivatives._
### Derivatives
Given an expression $f$ and a variable $x$, we can compute symbolically the (partial) derivative
$$
\frac{\partial f}{\partial x}
$$
of $f$ with respect to $x$.
For instance:
$$
\begin{align*}
\frac{\partial}{\partial x}(x^2 + 3y + 4) & = 2x \\[1ex]
\frac{\partial}{\partial x}(x^2y + xy^2 + z) & = 2yx + y^2 + z \; .
\end{align*}
$$
Here, the "partial" in partial derivative simply means: if you need to take the derivative with respect to a specific variable, simply treat all other variables as constants.
Computing symbolic derivatives seems complicated, but we can take it in steps. Our expression trees have leaves, consisting of
* numerical constants
* variables
and operators, corresponding to `+`, `-`, `*`, `/`.
Therefore, we break down the task into the computation of the symbolic derivative for numerical constants, variables, and arithmetic operators. The cases for the leaf nodes are:
* 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*}
$$
## Question 4: Derivative of a leaf expression
Let's start from a leaf expression. The function `derivate_leaf` takes as argument an expression that is a leaf, and a variable, and returns the symbolic derivative of the leaf writh respect to the variable.
"""
### Derivation of a leaf expression
def derivate_leaf(e, x):
"""This function takes as input an expression e and a variable x,
and returns the symbolic derivative of e wrt. x, as an expression."""
if isinstance(e, str):
if e == x:
return 1
else:
return 0
else:
return 0
### You can play here with your code.
"""Here are some tests. """
# 5 points.
assert derivate_leaf("x", "x") == 1
assert derivate_leaf("x", "y") == 0
assert derivate_leaf("y", "z") == 0
assert derivate_leaf(4, "x") == 0
"""## Question 5: Derivative of an expression
We now let you implement the derivative of a general expression. The function is recursive: for instance, if the expression is (`*`, $f$, $g$), to compute its derivative with respect to a variable $x$, we use:
$$
\frac{\partial}{\partial x}(f \cdot g) = \frac{\partial f}{\partial x} \cdot g + f \cdot \frac{\partial g}{\partial x}
$$
and so we need to recursively call symbolic derivation on the $f$ and $g$ sub-expressions, to obtain $\partial f / \partial x$ and $\partial g / \partial x$, and then produce and return an expression representing the result.
**Important:** The code for checking expression equality is _not_ able to cope with the commutativity of `+` and `*`. So, in your solution, please use _exactly_ these forms:
$$
\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*}
$$
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}$, which is mathematically equivalent, but would be considered different by the tests.
"""
### Implement `derivate`
def derivate(e, x):
"""Returns the derivative of e wrt x.
It can be done in less than 15 lines of code."""
if isinstance(e, tuple):
op, l, r = e
if op == '+' or op == '-':
return (op, derivate(l, x), derivate(r, x))
elif op == '*':
return ('+', ('*', derivate(l, x), r), ('*', l, derivate(r, x)))
else:
return ('/', ('-', ('*', derivate(l, x), r), ('*', l, derivate(r, x))), ('*', r, r))
else:
return derivate_leaf(e, x)
### You can play here with your code.
### 5 points: Tests for `derivate` for single-operator expressions
assert derivate(('+', 'x', 'x'), 'x') == ('+', 1, 1)
assert derivate(('-', 4, 'x'), 'x') == ('-', 0, 1)
assert derivate(('*', 2, 'x'), 'x') == ('+', ('*', 0, 'x'), ('*', 2, 1))
assert derivate(('/', 2, 'x'), 'x') == ('/', ('-', ('*', 0, 'x'), ('*', 2, 1)), ('*', 'x', 'x'))
### 5 points: Hidden tests for `derivate` for single-operator expressions
### 10 points: Tests for `derivate` for composite expressions
e1 = ('*', 'x', 'x')
e2 = ('*', 3, 'x')
num = ('-', e1, e2)
e3 = ('*', 'a', 'x')
den = ('+', e1, e3)
e = ('/', num, den)
f = ('/',
('-',
('*',
('-',
('+', ('*', 1, 'x'), ('*', 'x', 1)),
('+', ('*', 0, 'x'), ('*', 3, 1))),
('+', ('*', 'x', 'x'), ('*', 'a', 'x'))),
('*',
('-', ('*', 'x', 'x'), ('*', 3, 'x')),
('+',
('+', ('*', 1, 'x'), ('*', 'x', 1)),
('+', ('*', 0, 'x'), ('*', 'a', 1))))),
('*',
('+', ('*', 'x', 'x'), ('*', 'a', 'x')),
('+', ('*', 'x', 'x'), ('*', 'a', 'x'))))
assert derivate(e, 'x') == f