class EvalObj(object): def __str__(self): return "#" class UnspecObj(EvalObj): def __str__(self): return "#" def ext_repr(self): return self.__str__() class NumberObj(EvalObj): def __str__(selfl): return "#" class IntObj(NumberObj): def __init__(self, num): self.val = int(num) def __str__(self): return "#" def ext_repr(self): return str(self.val) class FloatObj(NumberObj): def __init__(self, num): self.val = float(num) def __str__(self): return "#" def ext_repr(self): return str(self.val) class StringObj(EvalObj): def __init__(self, string): self.val = string def __str__(self): return "#" def ext_repr(self): return self.val class BoolObj(EvalObj): def __init__(self, b): self.val = b def __str__(self): return "#" 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 "#" def __str__(self): return self.ext_repr() class SpecialOptObj(OptObj): def prepare(self, pc): 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 "#" 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, pc): self.state = 0 # prepare # TODO: check number of arguments pc = pc.chd pc.skip = False pc.sib.skip = True if pc.sib.sib: pc.sib.sib.skip = True # 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: pc = pc.chd pc.skip = True pc.sib.skip = False if pc.sib.sib: pc.sib.sib.skip = True return (None, True) # Re-eval else: pc = pc.chd pc.skip = True pc.sib.skip = True if pc.sib.sib: pc.sib.sib.skip = False return (None, 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 "#" def __str__(self): return self.ext_repr() class _builtin_lambda(SpecialOptObj): def _clear_marks(self, pc, flag): pc = pc.chd while pc: pc.skip = flag pc = pc.sib def prepare(self, pc): # TODO: check number of arguments self._clear_marks(pc, True) 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 self._clear_marks(pc, False) return (ProcObj(body, envt, para_list), False) def ext_repr(self): return "#" def __str__(self): return self.ext_repr() class _builtin_define(SpecialOptObj): def prepare(self, pc): # TODO: check number of arguments pc = pc.chd pc.skip = True pc.sib.skip = False 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 "#" def __str__(self): return self.ext_repr() class _builtin_set(SpecialOptObj): def prepare(self, pc): # TODO: check number of arguments pc = pc.chd pc.skip = True pc.sib.skip = False 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 "#" def __str__(self): return self.ext_repr() class IdObj(EvalObj): def __init__(self, string): self.name = string def __str__(self): return "#" 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 "#" 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 "#" 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) def _builtin_display(arg_list): # print arg_list[0].ext_repr() return UnspecObj() _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("display") : BuiltinProcObj(_builtin_display, "display"), 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]): stack[ntop].prepare(pc) #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: # 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 ret_addr is False: # Fake return stack[top] = arg_list[0] envt = cont.envt (pc, otop) = nxt_addr(cont.pc, otop) cont = cont.old_cont continue # Revert to the original cont. 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() if cmd == "": break t.feed(cmd) print e.run_expr(AbsSynTree(t)).ext_repr()