import sys
import unittest
BEGIN_ACTIVE_FUNC = "\x80"
BEGIN_NEUTRAL_FUNC = "\x81"
END_FUNC = "\x8f"
END_ARG = "\x8e"
SEGMENT_GAP = "\xff"
class TracError(Exception):
pass
def list_get(list_, index, default=""):
try:
return list_[index]
except:
return default
def scan_char(list_, pos):
return list_get(list_, pos)
def scan_chars(list_, pos, n):
chars = []
for i in range(n):
c = scan_char(list_, pos + i)
if c:
chars.append(c)
return "".join(chars)
class Processor(object):
def __init__(self, program=""):
self.work = [] # workspace containing current TRAC program
self.sp = 0 # position of scanning pointer in workspace
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
self.primitives = {} # dictionary containing bound methods for TRAC primitives
self.initialize(program)
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.work = []
self.reset()
self.work += 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 \
}
def run(self):
args = []
handler = self.scan_next_char
while handler:
try:
next_handler, args = handler(args)
except TracError, e:
sys.stderr.write("TracError: %s\n" % e )
next_handler, args = self.reset, []
handler = next_handler
def scan_next_char(self, args): # Rule 1
args = []
#self.db("scan_next_char")
c = scan_char(self.work, self.sp)
if c:
if c == '(':
handler = self.handle_begin_paren
elif c in "\n\r\t":
handler = self.handle_tab_return
elif c == ',':
handler = self.handle_comma
elif c == '#' and scan_chars(self.work, self.sp, 2) == '#(':
handler = self.handle_begin_active_func
elif c == '#' and scan_chars(self.work, self.sp, 3) == '##(':
handler = self.handle_begin_neutral_func
elif c == '#':
handler = self.handle_sharp_sign
elif c == ')':
handler = self.handle_end_paren
else:
args.append(c)
handler = self.handle_char
else:
self.db("exit")
print "Forms: %s" % (self.forms)
print "Output: [%s]" % (self.output)
handler = None
return handler, args
def handle_begin_paren(self, args): # Rule 2
args = []
nested_count = 1
chars = []
matched = False
del self.work[self.sp]
c = scan_char(self.work, self.sp)
while c and not matched:
if c == ')':
nested_count -= 1
if nested_count == 0:
matched = True
break
if not matched:
if c == '(':
nested_count += 1
chars.append(c)
self.sp += 1
c = scan_char(self.work, self.sp)
if matched:
del self.work[self.sp]
else:
raise TracError, "%s: can't find matching end parenthesis" %("handle_begin_paren")
return self.scan_next_char, []
def handle_tab_return(self, args): # Rule 3
args = []
del self.work[self.sp]
self.sp -= 1
return self.inc_scan_pointer_continue, args
def handle_comma(self, args): # Rule 4
args = []
self.work[self.sp] = END_ARG
return self.inc_scan_pointer_continue, args
def handle_begin_active_func(self, args): # Rule 5
args = []
del self.work[self.sp:self.sp + 2]
self.work.insert(self.sp, BEGIN_ACTIVE_FUNC)
self.sp += 1
return self.scan_next_char, args
def handle_begin_neutral_func(self, args): # Rule 6
args = []
del self.work[self.sp:self.sp + 3]
self.work.insert(self.sp, BEGIN_NEUTRAL_FUNC)
self.sp += 1
return self.scan_next_char, args
def handle_sharp_sign(self, args): # Rule 7
args = []
return self.inc_scan_pointer_continue, args
def handle_end_paren(self, args): # Rule 8
#self.db("end_paren_0")
args = []
self.work[self.sp] = END_FUNC
func_begin = self.get_func_begin()
func_result = self.eval_func(func_begin)
func_marker = self.work[func_begin]
args.append(func_begin)
if func_result == "":
handler = self.handle_null_func_result # Rule 10
elif func_marker == BEGIN_ACTIVE_FUNC:
args.append(func_result)
handler = self.handle_active_func_result # Rule 11
elif func_marker == BEGIN_NEUTRAL_FUNC:
args.append(func_result)
handler = self.handle_neutral_func_result # Rule 12
else:
raise TracError, "%s: invalid func_marker" %("handle_end_paren")
#self.db("end_paren_1")
return handler, args
def get_func_begin(self):
pos = self.sp - 1
c = self.work[pos]
while c:
if c == BEGIN_ACTIVE_FUNC or c == BEGIN_NEUTRAL_FUNC:
break
pos -= 1
if pos >= 0:
c = self.work[pos]
else:
raise TracError, "%s: can't find begin function marker" %("get_func_begin")
return pos
def get_func_end(self, func_begin):
pos = func_begin
c = self.work[pos]
while c:
if c == END_FUNC:
break
pos += 1
c = self.work[pos]
return pos
def get_func_args(self, func_begin):
args = []
cur_arg = []
pos = func_begin
c = self.work[pos]
db = []
while c:
db.append(c)
if c == BEGIN_ACTIVE_FUNC or c == BEGIN_NEUTRAL_FUNC:
pass
elif c == END_ARG or c == END_FUNC:
arg = "".join(cur_arg)
args.append(arg)
cur_arg = []
else:
cur_arg.append(c)
if c != END_FUNC:
pos += 1
c = self.work[pos]
db = []
else:
break
return args
def eval_func(self, func_begin):
result = ""
try:
args = self.get_func_args(func_begin)
func_name = args[0]
primitive = self.primitives.get(func_name, None)
if primitive:
result = primitive(args[1:])
if self.trace:
print "eval_func: %s %s -> [%s]" % (func_name, args[1:], result)
except Exception, e:
raise TracError, "%s: failed - %s" %("eval_func", e)
return result
def handle_char(self, args): # Rule 9
c = args[0]
args = []
return self.inc_scan_pointer_continue, args
def handle_null_func_result(self, args): # Rule 10
return self.handle_func_cleanup, args
def handle_active_func_result(self, args): # Rule 11
func_begin = args[0]
func_result = args[1]
args = []
self.work[self.sp+1:self.sp+1] += func_result
args.append(func_begin)
#self.db("handle_active_func_result")
return self.handle_func_cleanup, args
def handle_neutral_func_result(self, args): # Rule 12
func_begin = args[0]
func_result = args[1]
args = []
self.work[self.sp+1:self.sp+1] += func_result
func_end = self.sp
del self.work[func_begin:func_end + 1]
self.sp = func_begin + len(func_result) - 1
#self.db("handle_neutral_func_result")
return self.inc_scan_pointer_continue, args
def handle_func_cleanup(self, args): # Rule 13
if args:
func_begin = args[0]
func_end = self.get_func_end(func_begin)
args = []
del self.work[func_begin:func_end + 1]
self.sp = func_begin - 1
#self.db("handle_func_cleanup")
return self.inc_scan_pointer_continue, args
def reset(self, args=[]): # Rule 14
args = []
self.work = []
self.sp = 0
return self.scan_next_char, args
def inc_scan_pointer_continue(self, args): # Rule 15
args = []
self.sp += 1
return self.scan_next_char, args
def db(self, msg="db"):
print "%s: %s SP:%d %s" % (msg, self.work[0:self.sp], self.sp, self.work[self.sp:])
class TestTrac(unittest.TestCase):
def setUp(self):
pass
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()
