class SyntaxObj(object):
pass
class EvalObj(SyntaxObj):
def __str__(self):
return "#<Object>"
class ValObj(EvalObj):
def __str__(self):
return "#<Value>"
class NumberObj(ValObj):
def __str__(selfl):
return "#<Number>"
class IntObj(NumberObj):
def __init__(self, num):
self.val = int(num)
def __str__(self):
return "#<Integer>"
class FloatObj(NumberObj):
def __init__(self, num):
self.val = float(num)
def __str__(self):
return "#<Float>"
class StringObj(ValObj):
def __init__(self, string):
self.val = string
def __str__(self):
return "#<String>"
class BoolObj(ValObj):
def __init__(self, b):
self.val = b
def __str__(self):
return "#<Boolean>"
class OptObj(EvalObj):
pass
class ProcObj(OptObj):
def __init__(self, prog, env = None):
self.prog = prog
self.env = env
def __str__(self):
return "#<Procedure>"
class SpecialOptObj(OptObj):
def prepare(self, pc):
pass
def call(self, arg_list, pc, envt, cont):
pass
class BuiltinProcObj():
def __init__(self, f, ext_name):
self.handler = f
self.ext_name = ext_name
def __str__(self):
return self.ext_name
def call(self, arg_list):
return self.handler(arg_list)
def to_bool(obj):
if obj.val == False:
return BoolObj(False)
else:
return BoolObj(True)
class _builtin_if(SpecialOptObj):
def prepare(self, pc):
self.state = 0 # prepare
# TODO: check number of arguments
return (True, False, False)
# Delay the calculation
def pre_call(self, arg_list, pc, envt, cont):
self.state = 1 # calling
print "Received if signal: " + str(arg_list[0].val)
print "And it is regared as: " + str(to_bool(arg_list[0]).val)
if (to_bool(arg_list[0])).val:
return ((False, True, False), True) # Re-eval
else:
return ((False, False, True), True) # Re-eval
def post_call(self, arg_list, pc, envt, cont):
return (arg_list[0], False)
def call(self, arg_list, pc, envt, cont):
if self.state == 0:
return self.pre_call(arg_list, pc, envt, cont)
else:
return self.post_call(arg_list, pc, envt, cont)
def __str__(self):
return "#<builtint opt if>"
class _builtin_lambda(SpecialOptObj):
def prepare(self, pc):
# TODO: check number of arguments
return [ False, False ]
class IdObj(SyntaxObj):
def __init__(self, string):
self.name = string
def __str__(self):
return "#<Identifier>"
def get_name():
return self.name
class Tokenizor():
def __init__(self):
self.data = ""
self.tokenized = list()
self.extended_chars = "!$%&*+-./:<=>?@^_~"
def is_identifier(self, string):
if string[0].isdigit(): return False
for i in string[1:]:
if not (i.isalnum() or i in self.extended_chars):
return False
return True
def feed(self, data):
self.data = data
def read(self):
if len(self.tokenized) == 0:
if len(self.data) == 0:
return None
self.tokenized = self.data.replace('(', '( ')\
.replace(')', ' )')\
.split()
self.data = ""
return self.tokenized.pop(0)
class Node(object):
def __init__(self, syn_obj, sib = None, chd = None):
self.obj = syn_obj
self.sib = sib
self.chd = chd
self.skip = None # delay calcuation
def __str__(self):
return "#<AST Node>"
def print_(self):
print \
"======================" + "\n" + \
"Obj: " + str(self.obj) + "\n" + \
"Sib: " + str(self.sib) + "\n" + \
"Chd: " + str(self.chd) + "\n" + \
"======================"
class AbsSynTree(EvalObj):
def to_node(self, obj):
if isinstance(obj, Node): return obj
# else the obj is a string
try: return Node(IntObj(obj))
except Exception:
try: return Node(FloatObj(obj))
except Exception: return Node(IdObj(obj))
def __init__(self, stream):
stack = list()
while True:
token = stream.read()
if token is None: break
if token == '(':
stack.append(token)
elif token == ')':
lst = list()
while stack[-1] != '(':
lst = stack[-1:] + lst
del stack[-1]
root = lst[0]
if len(lst) > 1:
root.chd = lst[1]
ref = root.chd
for i in lst[2:]:
ref.sib = i
ref = ref.sib
stack[-1] = root
else:
stack.append(self.to_node(token))
self.tree = stack
def is_identifier(string):
return isinstance(string, IdObj)
def is_leaf(node):
return node.chd is None
def is_ret_addr(val):
return isinstance(val, Node)
def is_builtin_proc(val):
return isinstance(val, BuiltinProcObj)
def is_special_opt(val):
return isinstance(val, SpecialOptObj)
class Environment(object):
def __init__(self):
self.binding = dict()
def add_binding(self, name, eval_obj):
self.binding[name] = eval_obj
def get_obj(self, id_obj):
if is_identifier(id_obj):
return self.binding[id_obj.name]
else:
return id_obj
class Continuation(object):
def __init__(self, envt, pc, old_cont):
self.envt = envt
self.pc = pc
self.old_cont = old_cont
def get_envt(self):
return self.envt
def get_cont(self):
return self.cont
def _builtin_plus(arg_list):
res = 0
for i in arg_list:
res += i.val
return IntObj(res)
def _builtin_minus(arg_list):
res = arg_list[0].val
for i in arg_list[1:]:
res -= i.val
return IntObj(res)
def _builtin_times(arg_list):
res = 1
for i in arg_list:
res *= i.val
return IntObj(res)
def _builtin_div(arg_list):
res = arg_list[0].val
for i in arg_list[1:]:
res /= i.val
return IntObj(res)
def _builtin_lt(arg_list):
#TODO: need support to multiple operands
return BoolObj(arg_list[0].val < arg_list[1].val)
def _builtin_gt(arg_list):
return BoolObj(arg_list[0].val > arg_list[1].val)
def _builtin_eq(arg_list):
return BoolObj(arg_list[0].val == arg_list[1].val)
_default_mapping = {
"+" : BuiltinProcObj(_builtin_plus, "builtin proc +"),
"-" : BuiltinProcObj(_builtin_minus, "builtin proc -"),
"*" : BuiltinProcObj(_builtin_times, "builtin proc *"),
"/" : BuiltinProcObj(_builtin_div, "builtin proc /"),
"<" : BuiltinProcObj(_builtin_lt, "builtin proc <"),
">" : BuiltinProcObj(_builtin_gt, "builtin proc >"),
"=" : BuiltinProcObj(_builtin_eq, "builtin proc ="),
"if" : _builtin_if()
}
class Evaluator(object):
def _add_builtin_routines(self, envt):
for sym in _default_mapping:
envt.add_binding(sym, _default_mapping[sym])
def __init__(self):
self.envt = Environment() # Top-level Env
self._add_builtin_routines(self.envt)
def run_expr(self, prog):
stack = [0] * 100 # Stack
pc = prog.tree[0] # Set to the root
cont = None
envt = self.envt
top = -1 # Stack top
def print_stack():
print '++++++++++STACK++++++++'
if len(stack) > 0:
for i in range(0, top + 1):
print stack[i]
print '----------STACK--------'
def mask_eval(pc, mask):
pc = pc.chd
for i in mask:
print i
print pc
pc.skip = not i
pc = pc.sib
def push(pc, top):
ntop = top
if is_leaf(pc):
ntop += 1
stack[ntop] = envt.get_obj(pc.obj)
npc = pc.sib
print "first"
print "this val is: " + str(stack[ntop].val)
else:
ntop += 1
stack[ntop] = pc # Return address
ntop += 1
stack[ntop] = envt.get_obj(pc.obj)
npc = pc.chd
if is_special_opt(stack[ntop]):
mask = stack[ntop].prepare(pc)
mask_eval(pc, mask)
print "second"
return (npc, ntop)
print " Pushing..."
print_stack()
(pc, top) = push(pc, top)
print_stack()
print " Done...\n"
while is_ret_addr(stack[0]): # Still need to evaluate
print "- Top: " + str(stack[top])
print "- Pc at: " + str(pc)
while pc and pc.skip:
print "skipping masked branch: " + str(pc)
pc = pc.sib # Skip the masked branches
if pc is None:
print "Poping..."
arg_list = list()
while not is_ret_addr(stack[top]):
arg_list = [stack[top]] + arg_list
top -= 1
# Top is now pointing to the return address
opt = arg_list[0]
ret_addr = stack[top]
if is_builtin_proc(opt):
stack[top] = opt.call(arg_list[1:])
pc = ret_addr.sib
elif is_special_opt(opt):
(res, flag) = opt.call(arg_list[1:], pc, envt, cont)
if flag: # Need to call again
print "AGAIN with the mask: " + str(res)
mask_eval(ret_addr, res)
top += 1
pc = ret_addr.chd # Again
else:
stack[top] = res # Done
pc = ret_addr.sib
print_stack()
else:
print " Pushing..."
print_stack()
(pc, top) = push(pc, top)
print_stack()
print " Done...\n"
return stack[0]
t = Tokenizor()
t.feed("(if (> 2 1) 0 1)")
#t.feed("(+ (- (* 10 2) (+ x 4)) (+ 1 2) (/ 25 5))")
#t.feed("((lambda (x) (x * x)) 2)")
a = AbsSynTree(t)
e = Evaluator()
e.envt.add_binding("x", IntObj(100))
print e.run_expr(a).val