class EvalObj(object):
def __str__(self):
return "#<Object>"
class UnspecObj(EvalObj):
def __str__(self):
return "#<Unspecified>"
def ext_repr(self):
return self.__str__()
class NumberObj(EvalObj):
def __str__(selfl):
return "#<Number>"
class IntObj(NumberObj):
def __init__(self, num):
self.val = int(num)
def __str__(self):
return "#<Integer>"
def ext_repr(self):
return str(self.val)
class FloatObj(NumberObj):
def __init__(self, num):
self.val = float(num)
def __str__(self):
return "#<Float>"
def ext_repr(self):
return str(self.val)
class StringObj(EvalObj):
def __init__(self, string):
self.val = string
def __str__(self):
return "#<String>"
def ext_repr(self):
return self.val
class BoolObj(EvalObj):
def __init__(self, b):
self.val = b
def __str__(self):
return "#<Boolean>"
def ext_repr(self):
if self.val:
return "#t"
else:
return "#f"
class OptObj(EvalObj):
pass
class ProcObj(OptObj):
def __init__(self, body, envt, para_list):
self.body = body
self.envt = envt
self.para_list = para_list
def ext_repr(self):
return "#<Procedure>"
def __str__(self):
return self.ext_repr()
class SpecialOptObj(OptObj):
def prepare(self):
pass
def call(self, arg_list, pc, envt, cont):
pass
class BuiltinProcObj():
def __init__(self, f, name):
self.handler = f
self.name = name
def ext_repr(self):
return "#<Builtin Procedure: " + self.name + ">"
def __str__(self):
return self.ext_repr()
def call(self, arg_list):
return self.handler(arg_list)
def to_bool(obj):
if obj.val is False:
return BoolObj(False)
else:
return BoolObj(True)
class _builtin_if(SpecialOptObj):
def prepare(self):
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 ext_repr(self):
return "#<Builtin Macro: if>"
def __str__(self):
return self.ext_repr()
class _builtin_lambda(SpecialOptObj):
def prepare(self):
# TODO: check number of arguments
return (False, False)
def call(self, arg_list, pc, envt, cont):
para_list = list()
par = pc.chd
if par.obj:
para_list.append(par.obj)
if par.chd:
par = par.chd
while par:
para_list.append(par.obj)
par = par.sib
body = pc.chd.sib
pc.chd.skip = body.skip = False
return (ProcObj(body, envt, para_list), False)
def ext_repr(self):
return "#<Builtin Macro: lambda>"
def __str__(self):
return self.ext_repr()
class _builtin_define(SpecialOptObj):
def prepare(self):
# TODO: check number of arguments
return (False, True)
def call(self, arg_list, pc, envt, cont):
# TODO: check identifier
id = pc.chd.obj
envt.add_binding(id, arg_list[0])
return (UnspecObj(), False)
def ext_repr(self):
return "#<Builtin Macro: define>"
def __str__(self):
return self.ext_repr()
class _builtin_set(SpecialOptObj):
def prepare(self):
# TODO: check number of arguments
return (False, True)
def call(self, arg_list, pc, envt, cont):
id = pc.chd.obj
if envt.has_obj(id):
envt.add_binding(id, arg_list[0])
return (UnspecObj(), False)
def ext_repr(self):
return "#<Builtin Macro: set!>"
def __str__(self):
return self.ext_repr()
class IdObj(EvalObj):
def __init__(self, string):
self.name = string
def __str__(self):
return "#<Identifier: " + self.name + ">"
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 __expr__(self):
return self.__str__()
def print_(self):
print \
"======================" + "\n" + \
"Obj: " + str(self.obj) + "\n" + \
"Sib: " + str(self.sib) + "\n" + \
"Chd: " + str(self.chd) + "\n" + \
"======================"
class RetAddr(object):
def __init__(self, addr):
self.addr = addr
def __str__(self):
return "#<Return Address>"
class AbsSynTree(EvalObj):
def to_obj(self, obj):
if isinstance(obj, Node): return obj
try: return IntObj(obj)
except Exception:
try: return FloatObj(obj)
except Exception: return IdObj(obj)
def to_node(self, obj):
if isinstance(obj, Node): return obj
return Node(obj)
# else the obj is a string
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]
if len(lst) > 0:
root = Node(lst[0])
if len(lst) > 1:
root.chd = self.to_node(lst[1])
ref = root.chd
for i in lst[2:]:
ref.sib = self.to_node(i)
ref = ref.sib
stack[-1] = root
else:
stack[-1] = self.to_node(None)
else:
stack.append(self.to_obj(token))
for i in range(len(stack)):
stack[i] = self.to_node(stack[i])
self.tree = stack[0]
def is_obj(string):
return isinstance(string, EvalObj)
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, RetAddr)
def is_builtin_proc(val):
return isinstance(val, BuiltinProcObj)
def is_special_opt(val):
return isinstance(val, SpecialOptObj)
def is_user_defined_proc(val):
return isinstance(val, ProcObj)
class Environment(object):
def __init__(self, prev_envt = None):
self.prev_envt = prev_envt
self.binding = dict()
def add_binding(self, id_obj, eval_obj):
self.binding[id_obj.name] = eval_obj
def has_obj(self, id_obj):
ptr = self
while ptr:
try:
t = ptr.binding[id_obj.name]
return True
except KeyError:
ptr = ptr.prev_envt
return False
def get_obj(self, id_obj):
if is_identifier(id_obj):
ptr = self
while ptr:
try:
return ptr.binding[id_obj.name]
except KeyError:
ptr = ptr.prev_envt
raise KeyError
else:
print "Not an id: " + str(id_obj)
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 = {
IdObj("+") : BuiltinProcObj(_builtin_plus, "+"),
IdObj("-") : BuiltinProcObj(_builtin_minus, "-"),
IdObj("*") : BuiltinProcObj(_builtin_times, "*"),
IdObj("/") : BuiltinProcObj(_builtin_div, "/"),
IdObj("<") : BuiltinProcObj(_builtin_lt, "<"),
IdObj(">") : BuiltinProcObj(_builtin_gt, ">"),
IdObj("=") : BuiltinProcObj(_builtin_eq, "="),
IdObj("lambda") : _builtin_lambda(),
IdObj("if") : _builtin_if(),
IdObj("define") : _builtin_define(),
IdObj("set!") : _builtin_set()}
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
ostack = [0] * 100 # Pending operators
pc = prog.tree # Set to the root
cont = Continuation(None, pc, None)
envt = self.envt
top = -1 # Stack top
otop = -1
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 nxt_addr(ret_addr, otop):
notop = otop
if otop > -1 and ret_addr is ostack[notop]:
notop -= 1
res = ostack[notop].chd
notop -= 1
else:
res = ret_addr.sib
return (res, notop)
def push(pc, top, otop):
ntop = top
notop = otop
if is_leaf(pc):
print "first"
ntop += 1
if pc.skip:
new_obj = pc.obj
else:
new_obj = envt.get_obj(pc.obj)
stack[ntop] = new_obj
npc = pc.sib
pc.print_()
#print "this val is: " + str(stack[ntop].val)
else:
print "second"
ntop += 1
stack[ntop] = RetAddr(pc) # Return address
if isinstance(pc.obj, Node):
print "Operator need to be resolved!"
notop += 1
ostack[notop] = pc
notop += 1
ostack[notop] = pc.obj
pc.obj.print_() # Step in to resolve operator
npc = pc.obj
else:
print "Getting operator: " + str(pc.obj.name)
ntop += 1
stack[ntop] = envt.get_obj(pc.obj)
if is_special_opt(stack[ntop]):
mask = stack[ntop].prepare()
mask_eval(pc, mask)
npc = pc.chd
return (npc, ntop, notop)
print " Pushing..."
print_stack()
(pc, top, otop) = push(pc, top, otop)
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:
if top > 0 and is_ret_addr(stack[top - 1]) and \
stack[top - 1].addr is False:
stack[top - 1] = stack[top]
top -= 1
envt = cont.envt
(pc, otop) = nxt_addr(cont.pc, otop)
cont = cont.old_cont
# Revert to the original cont.
else:
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
print "Arg List: " + str(arg_list)
opt = arg_list[0]
ret_addr = stack[top].addr
if is_builtin_proc(opt): # Built-in Procedures
print "builtin"
stack[top] = opt.call(arg_list[1:])
(pc, otop) = nxt_addr(ret_addr, otop)
elif is_special_opt(opt): # Sepecial Operations
print "specialopt"
(res, flag) = opt.call(arg_list[1:], ret_addr, 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, otop) = nxt_addr(ret_addr, otop)
elif is_user_defined_proc(opt): # User-defined Procedures
ncont = Continuation(envt, ret_addr, cont) # Create a new continuation
cont = ncont # Make chain
envt = Environment(opt.envt) # New ENV and recover the closure
#TODO: Compare the arguments to the parameters
for i in xrange(1, len(arg_list)):
envt.add_binding(opt.para_list[i - 1],
arg_list[i]) # Create bindings
stack[top] = RetAddr(False) # Mark the exit of the continuation
pc = opt.body # Get to the entry point
print_stack()
print "Poping done."
else:
print " Pushing..."
print_stack()
(pc, top, otop) = push(pc, top, otop)
print_stack()
print " Done...\n"
return stack[0]
t = Tokenizor()
e = Evaluator()
import sys, pdb
#ins_set = ("(define x 1)", "(set! x 3)")
#for ins in ins_set:
# print "TEST"
# t.feed(ins)
# print "Output: " + e.run_expr(AbsSynTree(t)).ext_repr()
#
while True:
sys.stdout.write("Syasi> ")
cmd = sys.stdin.readline()
t.feed(cmd)
print e.run_expr(AbsSynTree(t)).ext_repr()