import collections
class Environment:
def __init__(self):
self.parameter = {}
self.sum = {}
self.sigmoid = {}
self.input = {}
self.system_variable = {}
self.exponent = {}
self.product = {}
self.sum_partial = {}
self.product_partial = {}
self.sigmoid_partial = {}
self.exponent_partial = {}
def _negate(self, nodes):
return tuple(item.negate(self) for item in nodes)
def make_sum(self, minus, constant, nodes):
assert type(nodes) is tuple
assert type(minus) is bool
for node in nodes:
assert isinstance(node, Product), node
if len(nodes) == 0 and minus:
result = self.make_sum(False, -constant, nodes)
else:
result = Sum(minus, constant, nodes)
return self.sum.setdefault((minus, constant, nodes), result)
def make_product(self, constant, nodes):
assert constant != 0
assert len(nodes) > 0
return self.product.setdefault((constant, nodes),
Product(constant, nodes))
def make_exponent(self, node, exponent):
assert exponent > 0
return self.exponent.setdefault((node, exponent),
Exponent(node, exponent))
def make_system_variable(self, index):
return self.system_variable.setdefault(index, SystemVariable(index))
def make_parameter(self, name):
return self.parameter.setdefault(name, Parameter(name))
def make_input(self, index):
return self.input.setdefault(index, Input(index))
def add(self, left, right):
left_sum = left.to_sum(self)
right_sum = right.to_sum(self)
constant = left_sum.at_zero() + right_sum.at_zero()
if not left_sum.nodes:
if right_sum.minus:
constant = -constant
return self.make_sum(right_sum.minus, constant, right_sum.nodes)
if not right_sum.nodes:
if left_sum.minus:
constant = -constant
return self.make_sum(left_sum.minus, constant, left_sum.nodes)
if left_sum.minus:
left_nodes = self._negate(left_sum.nodes)
else:
left_nodes = left_sum.nodes
if right_sum.minus:
right_nodes = self._negate(right_sum.nodes)
else:
right_nodes = right_sum.nodes
left_length = len(left_sum.nodes)
right_length = len(right_sum.nodes)
node_list = []
left_index = 0
right_index = 0
while left_index < left_length and right_index < right_length:
left_node = left_nodes[left_index]
right_node = right_nodes[right_index]
comparison = left_node.fuzzy_cmp(right_node)
if comparison == -1:
node_list.append(left_node)
left_index += 1
elif comparison == 0:
sum_constant = left_node.constant + right_node.constant
if sum_constant != 0:
node_list.append(self.make_product(
sum_constant, left_node.nodes))
left_index += 1
right_index += 1
else:
node_list.append(right_node)
right_index += 1
if left_index == left_length:
node_list.extend(right_nodes[right_index:])
if right_index == right_length:
node_list.extend(left_nodes[left_index:])
if len(node_list) > 0 and node_list[0].constant < 0:
minus = True
node_list = self._negate(node_list)
else:
node_list = tuple(node_list)
minus = False
return self.make_sum(minus, constant, node_list)
def multiply(self, left, right):
left_sum = left.to_sum(self)
right_sum = right.to_sum(self)
minus = left_sum.minus != right_sum.minus
first = self.make_sum(
minus, left_sum.constant * right_sum.constant, ())
outer_nodes = []
if left_sum.constant:
for node in right_sum.nodes:
outer_node = self.make_product(
left_sum.constant * node.constant, node.nodes)
if left_sum.constant < 0:
outer_node = outer_node.negate(self)
outer_nodes.append(outer_node)
outer = self.make_sum(
(left_sum.constant < 0) != minus, 0, tuple(outer_nodes))
inner_nodes = []
if right_sum.constant:
for node in left_sum.nodes:
inner_node = self.make_product(
right_sum.constant * node.constant, node.nodes)
if right_sum.constant < 0:
inner_node = inner_node.negate(self)
inner_nodes.append(inner_node)
inner = self.make_sum(
(right_sum.constant < 0) != minus, 0, tuple(inner_nodes))
last = self.number(0)
for left_node in left_sum.nodes:
for right_node in right_sum.nodes:
combined_terms = self._combine_terms(
left_node.nodes, right_node.nodes)
assert len(combined_terms) > 0
last = self.add(
last,
self.make_product(left_node.constant * right_node.constant,
combined_terms))
return self.add(self.add(self.add(first, outer), inner), last)
def make_sigmoid(self, minus, node):
if node.minus or (not node.nodes and node.constant < 0):
result = self.make_sigmoid(not minus, node.negate(self))
else:
result = Sigmoid(minus, node)
return self.sigmoid.setdefault((minus, node), result)
def _combine_terms(self, left, right):
left_length = len(left)
right_length = len(right)
assert left_length
assert right_length
node_list = []
left_index = 0
right_index = 0
while left_index < left_length and right_index < right_length:
left_node = left[left_index]
right_node = right[right_index]
comparison = left_node.node.cmp(right_node.node)
if comparison == -1:
node_list.append(left_node)
left_index += 1
elif comparison == 0:
sum_constant = left_node.exponent + right_node.exponent
assert sum_constant != 0
node_list.append(self.make_exponent(left_node.node,
sum_constant))
left_index += 1
right_index += 1
else:
node_list.append(right_node)
right_index += 1
if left_index == left_length:
node_list.extend(right[right_index:])
if right_index == right_length:
node_list.extend(left[left_index:])
return tuple(node_list)
def number(self, number):
return self.make_sum(False, number, ())
def cmp(left, right):
return (left > right) - (left < right)
class State(collections.namedtuple('State', ['input variables parameters'])):
def read_only(self):
parameters = tuple(sorted(self.parameters.iteritems()))
return self.input, self.variables, parameters
class Node(tuple):
minus = False
def __eq__(self, other):
return type(self) == type(other) and tuple(self) == tuple(other)
def __hash__(self):
return super().__hash__()
def to_sum(self, environment):
raise NotImplementedError
def partial_derivative(self, variable, environment):
raise NotImplementedError
class Sum(collections.namedtuple('Sum', 'minus constant nodes'), Node):
def to_sum(self, environment):
return self
def at_zero(self):
if self.minus:
return -self.constant
else:
return self.constant
def negate(self, environment):
return environment.make_sum(not self.minus, self.constant, self.nodes)
def partial_derivative(self, variable, environment):
result = environment.sum_partial.get((self, variable))
if result is not None:
return result
result = environment.number(0)
for node in self.nodes:
result = environment.add(
result, node.partial_derivative(variable, environment))
if self.minus:
result = result.negate(environment)
return environment.sum_partial.setdefault((self, variable), result)
def sum_cmp(self, other):
cmp_result = cmp(self.constant, other.constant)
if cmp_result:
return cmp_result
for self_node, other_node in zip(self.nodes, other.nodes):
cmp_result = self_node.cmp(other_node)
if cmp_result:
return cmp_result
cmp_result = cmp(len(self.nodes), len(other.nodes))
if cmp_result:
return cmp_result
return cmp(self.minus, other.minus)
class NonSum(Node):
def to_product(self, environment):
raise NotImplementedError
def to_sum(self, environment):
product = self.to_product(environment)
if product.constant < 0:
product = product.negate(environment)
minus = True
else:
minus = False
return environment.make_sum(minus, 0, (product,))
class Product(collections.namedtuple('Product', 'constant nodes'), NonSum):
def to_product(self, environment):
return self
def negate(self, environment):
return environment.make_product(-self.constant, self.nodes)
def cmp(self, other):
cmp_result = self.fuzzy_cmp(other)
if cmp_result:
return cmp_result
else:
return cmp(self.constant, other.constant)
def fuzzy_cmp(self, other):
for self_node, other_node in zip(self.nodes, other.nodes):
cmp_result = self_node[0].cmp(other_node[0])
if cmp_result:
return cmp_result
cmp_result = cmp(self_node[1], other_node[1])
if cmp_result:
return cmp_result
return cmp(len(self.nodes), len(other.nodes))
def partial_derivative(self, variable, environment):
result = environment.product_partial.get((self, variable))
if result is not None:
return result
if len(self.nodes) == 1:
result = self.nodes[0].partial_derivative(variable, environment)
else:
result = environment.number(0)
for index, focus in enumerate(self.nodes):
remainder = environment.make_product(
1,
self.nodes[:index] + self.nodes[index + 1:])
result = environment.add(
result,
environment.multiply(
remainder,
focus.partial_derivative(variable, environment)))
result = environment.multiply(
result,
environment.make_sum(False, self.constant, ()))
return environment.product_partial.setdefault((self, variable), result)
class Exponent(collections.namedtuple('Exponent', 'node exponent'), NonSum):
def to_product(self, environment):
return environment.make_product(1, (self,))
def partial_derivative(self, variable, environment):
result = environment.exponent_partial.get((self, variable))
if result is not None:
return result
if self.exponent == 1:
result = self.node.partial_derivative(variable, environment)
else:
result = environment.multiply(
environment.number(self.exponent),
environment.multiply(
self.node.partial_derivative(variable, environment),
environment.make_exponent(self.node, self.exponent - 1)))
return environment.exponent_partial.setdefault(
(self, variable), result)
class NonExponent(NonSum):
priority = -1
def to_exponent(self, environment):
return environment.make_exponent(self, 1)
def class_cmp(self, other):
raise NotImplementedError
def cmp(self, other):
if self.priority == -1 or other.priority == -1:
raise NotImplementedError
cmp_result = cmp(self.priority, other.priority)
if cmp_result:
return cmp_result
return self.class_cmp(other)
class Atom(NonExponent):
def to_product(self, environment):
return environment.make_product(1, (self.to_exponent(environment),))
def partial_derivative(self, variable, environment):
return environment.number(0)
class Indexed(collections.namedtuple('Indexed', 'index'), Atom):
def class_cmp(self, other):
return cmp(self.index, other.index)
class Input(Indexed):
pass
class SystemVariable(Indexed):
def partial_derivative(self, variable, environment):
if self.index == variable:
return environment.number(1)
else:
return environment.number(0)
class Parameter(collections.namedtuple('Parameter', 'name'), Atom):
def class_cmp(self, other):
return cmp(self.name, other.name)
class Sigmoid(collections.namedtuple('Sigmoid', 'minus node'), NonExponent):
def negate(self, environment):
return environment.make_sigmoid(not self.minus, self.node)
def to_product(self, environment):
if self.minus:
return environment.make_product(
-1, (self.negate(environment).to_exponent(),))
else:
return environment.make_product(1, (self.to_exponent(),))
def class_cmp(self, other):
cmp_result = self.node.sum_cmp(other.node)
if cmp_result:
return cmp_result
return cmp(self.minus, other.minus)
def partial_derivative(self, variable, environment):
result = environment.sigmoid_partial.get((self, variable))
if result is not None:
return result
result = environment.multiply(
self.node.partial_derivative(variable),
environment.make_sum(
self.minus, 1, (environment.make_product(-1, ((self, 2),)),)))
return environment.setdefault((self, variable), result)
for index, cls in enumerate((Input, SystemVariable, Parameter, Sigmoid)):
cls.priority = index
Comments