Python Problem:
Staring Code:
class Expr:
"""Abstract class representing expressions"""
def __init__(self, *args):
self.children = list(args)
self.child_values = None
def eval(self, env=None):
"""Evaluates the value of the expression with respect to a given
environment."""
# First, we evaluate the children.
# This is done here using a list comprehension,
# but we also could have written a for loop.
child_values = [c.eval(env=env) if isinstance(c, Expr) else c
for c in self.children]
# Then, we evaluate the expression itself.
if any([isinstance(v, Expr) for v in child_values]):
# Symbolic result.
return self.__class__(*child_values)
else:
# Concrete result.
return self.op(*child_values)
def op(self, *args):
"""The op method computes the value of the expression, given the
numerical value of its subexpressions. It is not implemented in
Expr, but rather, each subclass of Expr should provide its
implementation."""
raise NotImplementedError()
def __repr__(self):
"""Represents the expression as the name of the class,
followed by all the children in parentheses."""
return "%s(%s)" % (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 __pow__(self, other):
return Power(self, other)
def __rpow__(self, other):
return Power(other, self)
def __neg__(self):
return Negative(self)
class V(Expr):
"""Variable."""
def __init__(self, *args):
"""Variables must be of type string."""
assert len(args) == 1
assert isinstance(args[0], str)
super().__init__(*args)
def eval(self, env=None):
"""If the variable is in the environment, returns the
value of the variable; otherwise, returns the expression."""
if env is not None and self.children[0] in env:
return env[self.children[0]]
else:
return self
class Plus(Expr):
def op(self, x, y):
return x + y
class Minus(Expr):
def op(self, x, y):
return x - y
class Multiply(Expr):
def op(self, x, y):
return x * y
class Divide(Expr):
def op(self, x, y):
return x / y
class Power(Expr):
def op(self, x, y):
return x ** y
class Negative(Expr):
def op(self, x):
return -x
Problem:
Test:
try:
from nose.tools import assert_equal, assert_almost_equal
from nose.tools import assert_true, assert_false
from nose.tools import assert_not_equal, assert_greater_equal
except:
!pip install nose
from nose.tools import assert_equal, assert_almost_equal
from nose.tools import assert_true, assert_false
from nose.tools import assert_not_equal, assert_greater_equal
Expressions as Classes During lecture, we saw a way to represent expressions making use of Python's class system. 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 below cell (which you should run) contains the definition of the Expr class, and definitions of its subclasses V, Plus, Minus, Multiply. Divide, Power, and Negative. class Expr: **Abstract class representing expressions def __init__(self, *args): self.children = list(args) self.child_values = None def eval(self, env=None): ** Evaluates the value of the expression with respect to a given environment." First, we evaluate the children. This is done here using a list comprehension, but we also could have written a for loop. child_values = [c.eval(env=env) if isinstance(C, Expr) else C for c in self.children] Then, we evaluate the expression itself. if any([isinstance(v, Expr) for v in child_values]): # Symbolic result. return self._class_ child_values else: # Concrete result. return self.op('child_values) def op(self, *args): "The op method computes the value of the expression, given the numerical value of its subexpressions. It is not implemented in Expr, but rather, each subclass of Expr should provide its implementation." raise NotImplementedError() def __repr_(self): "Represents the expression as the name of the class, followed by all the children in parentheses." return "X(S)" % (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): # 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 _pow_(self, other): return Power(self, other) def _rpow__(self, other): return Power(other, self) def __neg_(self): return Negative(self) class V(Expr): ***Variable." def __init__(self, *args): Variables must be of type string." assert len(args) == 1 assert isinstance(args[@], str) super() __init_(*args) def eval(self, env=None): "If the variable is in the environment, returns the value of the variable; otherwise, returns the expression." if en is not None and self.children[@] in env: return env[self.children[@]] else: return self class Plus (Expr): def op(self, x, y): return x + y class Minus (Expr): def op(self, x, y): return x-Y class Multiply(Expr): def op(self, x, y): return x*y class Divide (Expr): def op(self, x, y): return x/y class Power (Expr): def op(self, x, y): return x ** y class Negative (Expr): def op (self, x): return - Although we can take the derivatives of various expressions, the results might not be exactly what we were hoping for. For example, the derivative of 5y +1 with respect to y should be 5, but it comes out as Plus (Plus (Multiply(@, VCy')), 5), 0). This is equivalent to 5 (because 0 xy=0,0+5=5, and 5 +0= 5), but it is rather ugly to read: [] e = 5 * Vy') + 1 e. derivative ('y') Although calling eval() would help in many cases, in this situation calling eval() on e. derivative (y') would not help, because we do not have a value for the variable vi'y'). But what we can do instead is implement a method to simplify expressions like this one. For this problem, you will write methods implementing simplification of expressions for each subclass of Expr. You should implement the following simplifications: Plus (@, e) and Plus(e, o) should simplify to e, for any e. Minus(e, ) should simplify to e, for any e. Minus(@, e) should simplify to Negative(e). Multiply(e, e) and Multiply(e, ) should simplify to e, for any e. Multiply(1, e) and Multiply(e, 1) should simplify to e, for any e. Divide(e, e) should simplify to e, for any e. Divide(e, 1) should simplify to e, for any e. Power(1, e) should simplify to 1, for any e. Power(e, o) should simplify to 1, for any e. Power(e, 1) should simplify to e, for any e. Logarithm(1) should simplify to m. Negative() should simplify to o. The simplification rules should be applied recursively over the expression, so that v('x') * (1 + VC'y') * @) should be simplifed to v('x'). To get you started, we have implemented a simplify method for the Expr class, which relies on each subclass having implemented a simplify op method. Your task is to implement these simplify op methods for the Plus, Minus, Multiply, Divide, Logarithm, Power, and Negative classes. The methods you write should implement the simplifications described above for each expression type, and return a simplified expression. If none of the above simplifications are possible, each simplify op method should call eval() on the expression. Finally, in order to test your simplify op implementations, we need to be able to check for expression equality, with a more lenient notion of equality than Python's "same object" notion. The below cell should do the job; be sure to run it before you test your code. [] def equality_as_same_types_and_attributes(self, other): return type(self) == type(other) and self.__dict_ == other. _dict_ Expr. _eq__ = equality_as_Same_types_and_attributes def expr_simplify(self): children = (c.simplify if isinstance(C, Expr) else c for c in self.children] e = self._class_('children) return e.simplify_op() Expr.simplify = expr_simplify def expr_simplify_op(self): return self.eval() Expr.simplify_op = expr_simplify_op def plus simplify_op(self): ***"Simplification of Plus expressions." # YOUR CODE HERE raise Not ImplementedError() def minus_simplify_op(self): ***Simplification of Minus expressions." # YOUR CODE HERE raise Not ImplementedError() def multiply_simplify_op(self): ***Simplification of Multiply expressions." # YOUR CODE HERE raise Not ImplementedError() def divide_simplify_op(self): ***Simplification of Divide expressions." # YOUR CODE HERE raise Not ImplementedError() def power simplify op(self): "Simplification of Power expressions." # YOUR CODE HERE raise Not ImplementedError() def logarithm_simplify_op(self): ***Simplification of Logarithm expressions. *** # YOUR CODE HERE raise Not ImplementedError() def negative_simplify_op(self): ***Simplification of Negative expressions. # YOUR CODE HERE raise NotImplementedError() Plus.simplify_op = plus_simplify_op Minus.simplify_up = ninus_simplify_op Multiply.simplify_up = multiply_simplify_op Divide. Simplify_op= divide_simplify_op Logarithm. simplify_op= logarithm_simplify_op Power.simplify_up = power_simplify_op Negative.simplify_op = negative_simplify_op e = V('x') + @ assert_equal(e. simplify(), V(x)) e = @= V('x') assert_equal(e.simplify(), V('x')) e = + (+ V('x')) + V y ') assert_equal(e.simplify(), V('x') + V('Y')) e = 2 + 3 + V('x') + B assert_equal(e.simplify(), 5 + V('x')) [ ] Tests for simplification of Minus expressions e = V('x') - assert_equal(e. simplify(), V('*')) e = @ - V('x') # Must evaluate to Negative(V('x')) assert_equal(e.simplify(), V('x')) [ ] Tests for simplification of Multiply expressions e = V('x') *1 assert_equal(e.simplify(), V(x)) e = 1 *V('x')*1*1* 1 assert_equal(e.simplify(), V('x')) e = 1 * V('x')*1**V('y') assert_equal(e.simplify(), ) [ ] Tests for simplification of Divide expressions e = @* V('x') / 3 assert_equal(e. simplify(), e) e = V('x') / 1 assert_equal(e.simplify(), V("x")) [ ] Tests for simplification of Power expressions e = V('x') ** assert_equal(e.simplify(), 1) e = V('2') ** 1 assert_equal(e.simplify(), V('2')) e = 1 ** (V('x') + 2) assert_equal(e. simplify(), 1) [] Tests for simplification of Logarithm expressions e = Logarithm(1) assert_equal(e.simplify(), ) e = Logarithm(1) + @* 3 assert_equal(e. simplify(), e) e = Logarithm(1) + Logarithm(0.5) assert_almost_equal(e.simplify(), math.log(0.5)) I l Overall tests e = ((3 - 3) ((('x') - 2) / (V'y") - 2))) = (('x') - 1) / (3 - 2) assert_equal(e. simplify(), V('') - 1) Expressions as Classes During lecture, we saw a way to represent expressions making use of Python's class system. 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 below cell (which you should run) contains the definition of the Expr class, and definitions of its subclasses V, Plus, Minus, Multiply. Divide, Power, and Negative. class Expr: **Abstract class representing expressions def __init__(self, *args): self.children = list(args) self.child_values = None def eval(self, env=None): ** Evaluates the value of the expression with respect to a given environment." First, we evaluate the children. This is done here using a list comprehension, but we also could have written a for loop. child_values = [c.eval(env=env) if isinstance(C, Expr) else C for c in self.children] Then, we evaluate the expression itself. if any([isinstance(v, Expr) for v in child_values]): # Symbolic result. return self._class_ child_values else: # Concrete result. return self.op('child_values) def op(self, *args): "The op method computes the value of the expression, given the numerical value of its subexpressions. It is not implemented in Expr, but rather, each subclass of Expr should provide its implementation." raise NotImplementedError() def __repr_(self): "Represents the expression as the name of the class, followed by all the children in parentheses." return "X(S)" % (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): # 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 _pow_(self, other): return Power(self, other) def _rpow__(self, other): return Power(other, self) def __neg_(self): return Negative(self) class V(Expr): ***Variable." def __init__(self, *args): Variables must be of type string." assert len(args) == 1 assert isinstance(args[@], str) super() __init_(*args) def eval(self, env=None): "If the variable is in the environment, returns the value of the variable; otherwise, returns the expression." if en is not None and self.children[@] in env: return env[self.children[@]] else: return self class Plus (Expr): def op(self, x, y): return x + y class Minus (Expr): def op(self, x, y): return x-Y class Multiply(Expr): def op(self, x, y): return x*y class Divide (Expr): def op(self, x, y): return x/y class Power (Expr): def op(self, x, y): return x ** y class Negative (Expr): def op (self, x): return - Although we can take the derivatives of various expressions, the results might not be exactly what we were hoping for. For example, the derivative of 5y +1 with respect to y should be 5, but it comes out as Plus (Plus (Multiply(@, VCy')), 5), 0). This is equivalent to 5 (because 0 xy=0,0+5=5, and 5 +0= 5), but it is rather ugly to read: [] e = 5 * Vy') + 1 e. derivative ('y') Although calling eval() would help in many cases, in this situation calling eval() on e. derivative (y') would not help, because we do not have a value for the variable vi'y'). But what we can do instead is implement a method to simplify expressions like this one. For this problem, you will write methods implementing simplification of expressions for each subclass of Expr. You should implement the following simplifications: Plus (@, e) and Plus(e, o) should simplify to e, for any e. Minus(e, ) should simplify to e, for any e. Minus(@, e) should simplify to Negative(e). Multiply(e, e) and Multiply(e, ) should simplify to e, for any e. Multiply(1, e) and Multiply(e, 1) should simplify to e, for any e. Divide(e, e) should simplify to e, for any e. Divide(e, 1) should simplify to e, for any e. Power(1, e) should simplify to 1, for any e. Power(e, o) should simplify to 1, for any e. Power(e, 1) should simplify to e, for any e. Logarithm(1) should simplify to m. Negative() should simplify to o. The simplification rules should be applied recursively over the expression, so that v('x') * (1 + VC'y') * @) should be simplifed to v('x'). To get you started, we have implemented a simplify method for the Expr class, which relies on each subclass having implemented a simplify op method. Your task is to implement these simplify op methods for the Plus, Minus, Multiply, Divide, Logarithm, Power, and Negative classes. The methods you write should implement the simplifications described above for each expression type, and return a simplified expression. If none of the above simplifications are possible, each simplify op method should call eval() on the expression. Finally, in order to test your simplify op implementations, we need to be able to check for expression equality, with a more lenient notion of equality than Python's "same object" notion. The below cell should do the job; be sure to run it before you test your code. [] def equality_as_same_types_and_attributes(self, other): return type(self) == type(other) and self.__dict_ == other. _dict_ Expr. _eq__ = equality_as_Same_types_and_attributes def expr_simplify(self): children = (c.simplify if isinstance(C, Expr) else c for c in self.children] e = self._class_('children) return e.simplify_op() Expr.simplify = expr_simplify def expr_simplify_op(self): return self.eval() Expr.simplify_op = expr_simplify_op def plus simplify_op(self): ***"Simplification of Plus expressions." # YOUR CODE HERE raise Not ImplementedError() def minus_simplify_op(self): ***Simplification of Minus expressions." # YOUR CODE HERE raise Not ImplementedError() def multiply_simplify_op(self): ***Simplification of Multiply expressions." # YOUR CODE HERE raise Not ImplementedError() def divide_simplify_op(self): ***Simplification of Divide expressions." # YOUR CODE HERE raise Not ImplementedError() def power simplify op(self): "Simplification of Power expressions." # YOUR CODE HERE raise Not ImplementedError() def logarithm_simplify_op(self): ***Simplification of Logarithm expressions. *** # YOUR CODE HERE raise Not ImplementedError() def negative_simplify_op(self): ***Simplification of Negative expressions. # YOUR CODE HERE raise NotImplementedError() Plus.simplify_op = plus_simplify_op Minus.simplify_up = ninus_simplify_op Multiply.simplify_up = multiply_simplify_op Divide. Simplify_op= divide_simplify_op Logarithm. simplify_op= logarithm_simplify_op Power.simplify_up = power_simplify_op Negative.simplify_op = negative_simplify_op e = V('x') + @ assert_equal(e. simplify(), V(x)) e = @= V('x') assert_equal(e.simplify(), V('x')) e = + (+ V('x')) + V y ') assert_equal(e.simplify(), V('x') + V('Y')) e = 2 + 3 + V('x') + B assert_equal(e.simplify(), 5 + V('x')) [ ] Tests for simplification of Minus expressions e = V('x') - assert_equal(e. simplify(), V('*')) e = @ - V('x') # Must evaluate to Negative(V('x')) assert_equal(e.simplify(), V('x')) [ ] Tests for simplification of Multiply expressions e = V('x') *1 assert_equal(e.simplify(), V(x)) e = 1 *V('x')*1*1* 1 assert_equal(e.simplify(), V('x')) e = 1 * V('x')*1**V('y') assert_equal(e.simplify(), ) [ ] Tests for simplification of Divide expressions e = @* V('x') / 3 assert_equal(e. simplify(), e) e = V('x') / 1 assert_equal(e.simplify(), V("x")) [ ] Tests for simplification of Power expressions e = V('x') ** assert_equal(e.simplify(), 1) e = V('2') ** 1 assert_equal(e.simplify(), V('2')) e = 1 ** (V('x') + 2) assert_equal(e. simplify(), 1) [] Tests for simplification of Logarithm expressions e = Logarithm(1) assert_equal(e.simplify(), ) e = Logarithm(1) + @* 3 assert_equal(e. simplify(), e) e = Logarithm(1) + Logarithm(0.5) assert_almost_equal(e.simplify(), math.log(0.5)) I l Overall tests e = ((3 - 3) ((('x') - 2) / (V'y") - 2))) = (('x') - 1) / (3 - 2) assert_equal(e. simplify(), V('') - 1)
