import sys
import unittest
import time
EOF = ""
SEGMENT_GAP = "\xff"
INCOMPLETE, COMPLETE = range(0,2)
class TracError(Exception):
pass
class Io(object):
def __init__(self, s=""):
self.buffer = []
self.buffer += s
def pop(self, default=EOF):
try:
return self.buffer.pop(0)
except:
return default
def push(self, s):
self.buffer[0:0] += s
def delete(self, i, j):
del self.buffer[i:j]
def peek(self, count=1):
try:
chars = self.buffer[0:0 + count]
except:
chars = [EOF]
return "".join(chars)
def get_trac_protected_string(self):
chars = []
paren_count = 0
matched = False
c = self.pop()
while c != EOF and not matched:
if c == '(':
paren_count += 1
elif c == ')':
paren_count -= 1
chars.append(c)
if paren_count != 0:
c = self.pop()
else:
matched = True
if not matched:
raise TracError, "%s: can't find matching end parenthesis" %("get_trac_protected_string")
s = "".join(chars[1:-1])
return s
def list_get(list_, index, default=""):
try:
return list_[index]
except:
return default
class Expr(object):
def __init__(self):
self.chars = []
def value(self):
return "".join(self.chars)
def append(self, c):
self.chars.append(c)
def process_char(self, c):
self.append(c)
return INCOMPLETE
def __repr__(self):
return '%s(%s)' % (self.__class__.__name__, self.chars)
class Root(Expr):
def __init__(self):
Expr.__init__(self)
class Protected(Expr):
def __init__(self):
Expr.__init__(self)
class Function(Expr):
def __init__(self):
Expr.__init__(self)
self.args = []
def process_char(self, c):
if c == ',' or c == ')':
arg = self.value()
self.args.append(arg)
del self.chars[:]
if c == ')':
return COMPLETE
else:
self.append(c)
return INCOMPLETE
def __repr__(self):
return '%s(%s %s)' % (self.__class__.__name__, self.chars, self.args)
class Active(Function):
def __init__(self):
Function.__init__(self)
class Neutral(Function):
def __init__(self):
Function.__init__(self)
class Processor(object):
def __init__(self, program=""):
self.io = Io(program)
self.forms = {} # key-value storage for program variables
self.output = "" # last string printed to output by ps for unit testing
self.trace = True # flag for printing trace results of function evaluation
def tn(self, args):
self.trace = True
return ""
def tf(self, args):
self.trace = False
return ""
def ds(self, args):
key = list_get(args, 0)
value = list_get(args, 1)
self.forms[key] = value
return ""
def ps(self, args):
try:
s = list_get(args, 0)
print s
self.output = s
except:
pass
return ""
def ad(self, args):
try:
num1 = int(list_get(args, 0))
num2 = int(list_get(args, 1))
return str(num1 + num2)
except:
return ""
def su(self, args):
try:
num1 = int(list_get(args, 0))
num2 = int(list_get(args, 1))
return str(num1 - num2)
except:
return ""
def ml(self, args):
try:
num1 = int(list_get(args, 0))
num2 = int(list_get(args, 1))
return str(num1 * num2)
except:
return ""
def dv(self, args):
try:
num1 = int(list_get(args, 0))
num2 = int(list_get(args, 1))
return str(num1 / num2)
except:
return ""
def eq(self, args):
try:
s1 = list_get(args, 0)
s2 = list_get(args, 1)
eq_result = list_get(args, 2)
neq_result = list_get(args, 3)
if s1 == s2:
return eq_result
else:
return neq_result
except:
return ""
def ss(self, args):
try:
form_key = args.pop(0)
form = self.forms[form_key]
form_marked = form
for i in range(len(args)):
arg = args[i]
marker = "%s%s" % (SEGMENT_GAP, chr(i))
form_marked = form_marked.replace(arg, marker)
self.forms[form_key] = form_marked
form_list = []
form_list += form_marked
#print "ss: %s" % (form_list)
return ""
except:
return ""
def cl(self, args):
try:
form_key = args.pop(0)
form = self.forms[form_key]
form_processed = form
for i in range(len(args)):
arg = args[i]
marker = "%s%s" % (SEGMENT_GAP, chr(i))
form_processed = form_processed.replace(marker, arg)
return form_processed
except:
return ""
def initialize(self, program=""):
self.forms = {}
self.io = Io(program)
self.primitives = {"ds":self.ds, \
"ps":self.ps, \
"ss":self.ss, \
"cl":self.cl, \
"ad":self.ad, \
"su":self.su, \
"ml":self.ml, \
"dv":self.dv, \
"tn":self.tn, \
"tf":self.tf, \
"eq":self.eq \
}
self.output = []
self.stack = []
self.cur_expr = Root()
self.stack.append(self.cur_expr)
return self
def push(self, expr):
self.stack.append(expr)
self.cur_expr = expr
def pop(self):
if self.stack:
expr = self.stack.pop()
self.cur_expr = self.stack[-1]
return expr
return None
def eval(self, func_expr):
result = ""
try:
func_name = func_expr.args[0]
args = func_expr.args[1:]
primitive = self.primitives.get(func_name, None)
if primitive:
result = primitive(args)
if self.trace:
print "eval: %s %s -> [%s]" % (func_name, args, result)
except Exception, e:
raise TracError, "%s: failed - %s" %("eval", e)
return result
def run(self):
while self.io.buffer:
# print "Stack: %s" % self.stack
c = self.io.pop()
if c == '(':
self.io.push(c)
s = self.io.get_trac_protected_string()
self.cur_expr.chars += s
elif c == '#' and self.io.peek(1) == '(':
self.io.delete(0,1)
self.push(Active())
elif c == '#' and self.io.peek(2) == '#(':
self.io.delete(0,2)
self.push(Neutral())
elif c == ',':
self.cur_expr.process_char(c)
elif c in "\n\r\t":
pass
elif c == ')':
complete = self.cur_expr.process_char(c)
if complete == COMPLETE:
func_expr = self.pop()
func_result = self.eval(func_expr)
if isinstance(func_expr, Active):
self.io.push(func_result)
else:
self.cur_expr.chars += func_result
else:
self.cur_expr.process_char(c)
if self.trace:
print "Stack: %s" % self.stack
print "Forms: %s" % self.forms
print "Output: %s" % self.output
class TestTrac(unittest.TestCase):
def setUp(self):
pass
def __setup(self, program, correct=""):
self.processor = Processor()
self.processor.initialize(program)
self.processor.run()
print str(self.processor.stack)
def __test(self, program, output):
self.processor = Processor()
self.processor.initialize(program)
self.processor.run()
self.assertEqual(self.processor.output, output)
def test_1_ps(self):
self.__test("#(ps,Hello world)", "Hello world")
def test_2_equal(self):
self.__test("#(ps,#(eq,Cat,Cat,equal,not equal))", "equal")
def test_3_not_equal(self):
self.__test("#(ps,#(eq,Cat,Dog,equal,not equal))", "not equal")
def test_4_ds(self):
self.__test("#(ds,AA,Cat)#(ps,#(cl,AA))", "Cat")
def test_5_protect_parens(self):
self.__test("#(ds,AA,Cat)#(ds,BB,(#(cl,AA)))#(ps,(#(cl,BB)))", "#(cl,BB)")
def test_6_neutral_func(self):
self.__test("#(ds,AA,Cat)#(ds,BB,(#(cl,AA)))#(ps,##(cl,BB))", "#(cl,AA)")
def test_7_indirection(self):
self.__test("#(ds,AA,Cat)#(ds,BB,(#(cl,AA)))#(ps,#(cl,BB))", "Cat")
def test_8_ss(self):
self.__test("#(ds,AA,Hello X)#(ss,AA,X)#(ps,#(cl,AA,world))", "Hello world")
def test_9_factorial(self):
self.__test("""
#(ds,Factorial,(#(eq,X,1,1,(#(ml,X,#(cl,Factorial,#(su,X,1)))))))
#(ss,Factorial,X)
#(ps,#(cl,Factorial,5))
""", "120")
if __name__ == "__main__":
print __file__
unittest.main()
