Skip to content

Instantly share code, notes, and snippets.

@mgronhol

mgronhol/libModel.py

Last active August 29, 2016 18:14
Show Gist options
  • Save mgronhol/0e12f630f973c1daef27c5f8dba8fe46 to your computer and use it in GitHub Desktop.
Save mgronhol/0e12f630f973c1daef27c5f8dba8fe46 to your computer and use it in GitHub Desktop.
Download ZIP
Dataflow + stack machine
Raw
libModel.py
#!/usr/bin/env python
import math
_next_id = -1
def generate_id():
global _next_id
_next_id += 1
return _next_id
class Blocks( object ):
class Constant( object ):
def __init__( self, inputs, output, value ):
self.inputs = inputs
self.output = output
self.value = value
def init( self ):
out = []
out.append( ("CONST", self.value) )
out.append( ("STORE", self.output) )
return out
def emit(self):
return []
def __str__( self ):
return "Const (%s) -> %s" % (str(self.value), self.output)
class Addition( object ):
def __init__( self, inputs, output ):
self.inputs = inputs
self.output = output
def init( self ):
return []
def emit( self ):
out = []
for inp in self.inputs:
out.append( ("LOAD", inp) )
for i in range( len(self.inputs) - 1 ):
out.append( ("ADD", ) )
out.append( ("STORE", self.output) )
return out
def __str__( self ):
return "Add (%s) -> %s" % (",".join(self.inputs), self.output)
class Substraction( object ):
def __init__( self, inputs, output ):
self.inputs = inputs
self.output = output
def init( self ):
return []
def emit( self ):
out = []
for inp in self.inputs:
out.append( ("LOAD", inp) )
for i in range( len(self.inputs) - 1 ):
out.append( ("SUB", ) )
out.append( ("STORE", self.output) )
return out
def __str__( self ):
return "Sub (%s) -> %s" % (",".join(self.inputs), self.output)
class Multiplication( object ):
def __init__( self, inputs, output ):
self.inputs = inputs
self.output = output
def init( self ):
return []
def emit( self ):
out = []
for inp in self.inputs:
out.append( ("LOAD", inp) )
for i in range( len(self.inputs) - 1 ):
out.append( ("MUL", ) )
out.append( ("STORE", self.output) )
return out
def __str__( self ):
return "Mul (%s) -> %s" % (",".join(self.inputs), self.output)
class Division( object ):
def __init__( self, inputs, output ):
self.inputs = inputs
self.output = output
def init( self ):
return []
def emit( self ):
out = []
for inp in self.inputs:
out.append( ("LOAD", inp) )
for i in range( len(self.inputs) - 1 ):
out.append( ("DIV", ) )
out.append( ("STORE", self.output) )
return out
def __str__( self ):
return "Div (%s) -> %s" % (",".join(self.inputs), self.output)
class Integrator( object ):
def __init__( self, inputs, output, initial = 0.0, delta = 1.0 ):
self.inputs = inputs
self.input = self.inputs[0]
self.output = output
self.initial = initial
self.delta = delta
self.accumulator = "ACC-%03i" % generate_id()
def init( self ):
out = []
out.append( ("CONST", self.initial) )
out.append( ("STORE", self.accumulator ) )
return out
def emit( self ):
out = []
out.append( ("LOAD", self.input) )
out.append( ("CONST", self.delta ) )
out.append( ("MUL", ) )
out.append( ("LOAD", self.accumulator ) )
out.append( ("ADD", ) )
out.append( ("DUP", ) )
out.append( ("STORE", self.accumulator) )
out.append( ("STORE", self.output) )
return out
def __str__( self ):
return "Int (%s) -> %s" % (",".join(self.inputs), self.output)
class Derivator( object ):
def __init__( self, inputs, output, initial = 0.0, delta = 1.0 ):
self.inputs = inputs
self.input = self.inputs[0]
self.output = output
self.initial = initial
self.delta = delta
self.prev_value = "PREV-%03i" % generate_id()
def init( self ):
out = []
out.append( ("CONST", self.initial) )
out.append( ("STORE", self.prev_value ) )
return out
def emit( self ):
out = []
out.append( ("LOAD", self.input) )
out.append( ("LOAD", self.prev_value) )
out.append( ("SWAP", ) )
out.append( ("DUP", ) )
out.append( ("STORE", self.prev_value) )
out.append( ("SUB",) )
out.append( ("CONST", self.delta) )
out.append( ("DIV", ) )
out.append( ("STORE", self.output ) )
return out
def __str__( self ):
return "Deriv (%s) -> %s" % (",".join(self.inputs), self.output)
class MathFunc( object ):
def __init__( self, inputs, output, func ):
self.inputs = inputs
self.input = self.inputs[0]
self.output = output
self.func = func
def init( self ):
return []
def emit( self ):
out = []
out.append( ("LOAD", self.input) )
out.append( ("MATH", self.func) )
out.append( ("STORE", self.output) )
return out
def __str__( self ):
return "Math.%s (%s) -> %s" % (self.func, ",".join(self.inputs), self.output)
class Multiplexer( object ):
def __init__( self, inputs, output, mux ):
self.inputs = inputs
self.output = output
self.mux = mux
def init( self ):
return []
def emit( self ):
out = []
for inp in self.inputs:
out.append( ("LOAD", inp) )
out.append( ("LOAD", self.mux ) )
out.append( ("ROLL", ) )
out.append( ("STORE", self.output ) )
for i in range( len(self.inputs) - 1 ):
out.append( ("DROP", ) )
return out
def __str__( self ):
return "Mux (%s : %s) -> %s" % (",".join(self.inputs), self.mux, self.output)
class Comparator( object ):
def __init__( self, inputs, output, operation ):
self.inputs = inputs
self.output = output
self.operation = operation
def init( self ):
return []
def emit( self ):
out = []
for inp in self.inputs:
out.append( ("LOAD", inp) )
for i in range( len(self.inputs) - 1 ):
out.append( ("CMP", self.operation) )
out.append( ("STORE", self.output ) )
return out
def __str__( self ):
return "Cmp.%s (%s) -> %s" % (self.operation, ",".join(self.inputs), self.output)
class Deadband( object ):
def __init__( self, inputs, output, band ):
self.inputs = inputs
self.input = self.inputs[0]
self.output = output
self.band = band
def init( self ):
return []
def emit( self ):
out = []
out.append( ("CONST", 0) )
out.append( ("LOAD", self.input) )
out.append( ("DUP", ) )
out.append( ("MATH", "ABS") )
out.append( ("CONST", self.band) )
out.append( ("CMP", ">" ) )
out.append( ("ROLL", ) )
out.append( ("STORE", sef.output ) )
out.append( ("DROP", ) )
return out
def __str__( self ):
return "Deadband (%s) -> %s" % (",".join(self.inputs), self.output)
class Lowpass( object ):
def __init__( self, inputs, output, gain, initial = 0.0 ):
self.inputs = inputs
self.input = self.inputs[0]
self.output = output
self.gain = gain
self.initial = initial
self.accumulator = "ACC-%03i" % generate_id()
def init( self ):
out = []
out.append( ("CONST", self.initial) )
out.append( ("STORE", self.accumulator) )
return out
def emit( self ):
out = []
# (1-t)*current + t*acc
out.append( ("LOAD", self.input) )
out.append( ("CONST", 1.0 ) )
out.append( ("CONST", self.gain ) )
out.append( ("SUB", ) )
out.append( ("MUL", ) )
out.append( ("LOAD", self.accumulator ) )
out.append( ("CONST", self.gain) )
out.append( ("MUL", ) )
out.append( ("ADD", ) )
out.append( ("DUP", ) )
out.append( ("STORE", self.accumulator ) )
out.append( ("STORE", self.output ) )
return out
def __str__( self ):
return "Lowpass (%s) -> %s" % (",".join(self.inputs), self.output)
class Highpass( object ):
def __init__( self, inputs, output, gain, initial = 0.0 ):
self.inputs = inputs
self.input = self.inputs[0]
self.output = output
self.gain = gain
self.initial = initial
self.accumulator = "ACC-%03i" % generate_id()
def init( self ):
out = []
out.append( ("CONST", self.initial) )
out.append( ("STORE", self.accumulator) )
return out
def emit( self ):
out = []
# (1-t)*current + t*acc
out.append( ("LOAD", self.input) )
out.append( ("DUP", ) )
out.append( ("CONST", 1.0 ) )
out.append( ("CONST", self.gain ) )
out.append( ("SUB", ) )
out.append( ("MUL", ) )
out.append( ("LOAD", self.accumulator ) )
out.append( ("CONST", self.gain) )
out.append( ("MUL", ) )
out.append( ("ADD", ) )
out.append( ("DUP", ) )
out.append( ("STORE", self.accumulator ) )
out.append( ("SUB", ) )
out.append( ("STORE", self.output ) )
return out
def __str__( self ):
return "Highpass (%s) -> %s" % (",".join(self.inputs), self.output)
def execute( code ):
memory = {}
stack = []
for entry in code:
op = entry[0]
if op == "CONST":
stack.append( entry[1] )
elif op == "LOAD":
stack.append( memory[entry[1]] )
elif op == "STORE":
value = stack.pop()
memory[entry[1]] = value
elif op == "ADD":
value0 = stack.pop()
value1 = stack.pop()
stack.append( value0 + value1 )
elif op == "SUB":
value0 = stack.pop()
value1 = stack.pop()
stack.append( value1 - value0 )
elif op == "MUL":
value0 = stack.pop()
value1 = stack.pop()
stack.append( value0 * value1 )
elif op == "DIV":
value0 = stack.pop()
value1 = stack.pop()
stack.append( value1 / value0 )
elif op == "DUP":
value = stack.pop()
stack.append( value )
stack.append( value )
elif op == "SWAP":
value0 = stack.pop()
value1 = stack.pop()
stack.append( value0 )
stack.append( value1 )
elif op == "DROP":
stack.pop()
elif op == "ROLL":
n = int( stack.pop() )
for i in range( n ):
value = stack.pop()
stack.insert(0, value)
elif op == "CMP":
value0 = stack.pop()
value1 = stack.pop()
if entry[1] == "=":
if value0 == value1:
stack.append( 1 )
else:
stack.append( 0 )
elif entry[1] == "!=":
if value0 != value1:
stack.append( 1 )
else:
stack.append( 0 )
if entry[1] == "<":
if value1 < value0:
stack.append( 1 )
else:
stack.append( 0 )
if entry[1] == ">":
if value1 > value0:
stack.append( 1 )
else:
stack.append( 0 )
if entry[1] == "<=":
if value1 <= value0:
stack.append( 1 )
else:
stack.append( 0 )
if entry[1] == ">=":
if value1 >= value0:
stack.append( 1 )
else:
stack.append( 0 )
elif op == "MATH":
value0 = stack.pop()
if entry[1] == "ABS":
stack.append( abs(value0) )
elif entry[1] == "SQRT":
stack.append( math.sqrt(value0) )
elif entry[1] == "SIN":
stack.append( math.sin(value0) )
elif entry[1] == "COS":
stack.append( math.cos(value0) )
elif entry[1] == "TAN":
stack.append( math.tan(value0) )
elif entry[1] == "ATAN":
stack.append( math.atan(value0) )
elif entry[1] == "EXP":
stack.append( math.exp(value0) )
return memory
def toposort( blocks ):
L = []
temporary = set()
permanent = set()
unmarked = []
index = {}
edges = {}
def visit( n ):
if n in temporary:
return
if n not in permanent:
temporary.add( n )
for n2 in edges[n]:
visit( n2 )
permanent.add( n )
temporary.remove( n )
L.insert(0, n)
unmarked.remove( n )
for i in range( len( blocks ) ):
index[i] = blocks[i]
unmarked.append( i )
for i in range( len( blocks ) ):
edges[i] = []
for j in range( len( blocks ) ):
if i != j:
if blocks[i].output in blocks[j].inputs:
edges[i].append(j)
#print "edges", edges
while len(unmarked) > 0:
node = unmarked[0]
visit(node)
return [index[n] for n in L]
def optimizations( code ):
out = []
# remove unnecessary store-load pairs
pos = 0
while pos < len(code) - 1:
op0 = code[pos]
op1 = code[pos+1]
if op0[0] == "STORE" and op1[0] == "LOAD":
if op0[1] == op1[1]:
pos += 2
else:
out.append( op0 )
pos += 1
else:
out.append( op0 )
pos += 1
out.append( code[-1] )
return out
_wires = -1
def Wire():
global _wires
_wires += 1
return "WIRE-%03i" % _wires
_terminals = -1
def Terminal():
global _terminals
_terminals += 1
return "TERM-%03i" % _terminals
w1 = Wire()
w2 = Wire()
const_1 = Blocks.Constant([], w1, 1 )
const_2 = Blocks.Constant([], w2, 1336 )
out = Terminal()
adder = Blocks.Addition([w1,w2], out )
blocks = toposort( [adder, const_1, const_2] )
print ""
print "Order of execution:"
for block in blocks:
print block
print ""
print "Intermediate representation:"
code = []
for block in blocks:
code.extend( block.init() )
for block in blocks:
code.extend( block.emit() )
code = optimizations( code )
#print code
for c in code:
print " ".join([str(x) for x in c])
print ""
print "Memory map after execution:"
print execute( code )
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment