diff options
| author | Teddy <[email protected]> | 2013-07-31 20:46:43 +0800 |
|---|---|---|
| committer | Teddy <[email protected]> | 2013-07-31 20:46:43 +0800 |
| commit | afdc71eaeffc760e5ceea76d35402fc2404bc80d (patch) | |
| tree | ef535316c61ce69a9595110e75cfcec81ae396a5 | |
| parent | 19d260020ca4025cf5d7d987966579c5d6276056 (diff) | |
use a simple and elegant way to represent the AST
| -rwxr-xr-x | sketch.py | 270 | ||||
| -rwxr-xr-x | sketch_obsolete.py | 608 |
2 files changed, 716 insertions, 162 deletions
@@ -88,40 +88,41 @@ def to_bool(obj): # Mark all children of pc as flag def _fill_marks(pc, flag): - pc = pc.chd - while pc: - pc.skip = flag - pc = pc.sib + pc = pc.cdr + while not (pc is empty_list): + pc.func.skip = flag + pc = pc.cdr class _builtin_if(SpecialOptObj): def prepare(self, pc): # TODO: check number of arguments # Evaluate the condition first self.state = 0 # Prepared - pc = pc.chd - pc.skip = False - pc.sib.skip = True - if pc.sib.sib: - pc.sib.sib.skip = True + pc = pc.cdr + pc.func.skip = False + pc.cdr.func.skip = True + if not (pc.cdr.cdr is empty_list): + pc.cdr.cdr.func.skip = True def pre_call(self, arg_list, pc, envt, cont): + pc = pc.car # Condition evaluated and the decision is made self.state = 1 if (to_bool(arg_list[0])).val: - pc = pc.chd - pc.skip = True - pc.sib.skip = False - if pc.sib.sib: + pc = pc.cdr + pc.func.skip = True + pc.cdr.func.skip = False + if not (pc.cdr.cdr is empty_list): # Eval the former - pc.sib.sib.skip = True + pc.cdr.cdr.func.skip = True return (None, True) # Re-eval else: - pc = pc.chd - pc.skip = True - pc.sib.skip = True - if pc.sib.sib: + pc = pc.cdr + pc.func.skip = True + pc.cdr.func.skip = True + if not (pc.cdr.cdr is empty_list): # Eval the latter - pc.sib.sib.skip = False + pc.cdr.cdr.func.skip = False return (None, True) # Re-eval def post_call(self, arg_list, pc, envt, cont): @@ -147,28 +148,26 @@ class _builtin_lambda(SpecialOptObj): _fill_marks(pc, True) def call(self, arg_list, pc, envt, cont): + pc = pc.car para_list = list() # paramter list - par = pc.chd # Switch to the first parameter - if par.obj.obj: # If there is at least one parameter - para_list.append(par.obj.obj) - if par.chd: # More paramters? - par = par.chd - while par: - para_list.append(par.obj) - par = par.sib + par = pc.cdr.car # Switch to the first parameter + if not (par is empty_list): # If there is at least one parameter + while not (par is empty_list): + para_list.append(par.car) + par = par.cdr # Clear the flag to avoid side-effects (e.g. proc calling) _fill_marks(pc, False) - pc = pc.chd.sib # Move pc to procedure body + pc = pc.cdr.cdr # Move pc to procedure body #TODO: check body body = list() # store a list of expressions inside <body> - while pc: + while not (pc is empty_list): body.append(pc) - pc.next = None # Make each expression a orphan - # in order to ease the exit checking - pc = pc.sib + pc.func.next = None # Make each expression a orphan + # in order to ease the exit checking + pc = pc.cdr return (ProcObj(body, envt, para_list), False) @@ -180,37 +179,39 @@ class _builtin_lambda(SpecialOptObj): class _builtin_define(SpecialOptObj): def prepare(self, pc): - if is_arg(pc.chd): # Simple value assignment - pc.chd.skip = True # Skip the identifier - pc.chd.sib.skip = False + if is_arg(pc.cdr): # Simple value assignment + pc.cdr.func.skip = True # Skip the identifier + pc.cdr.cdr.func.skip = False else: # Procedure definition _fill_marks(pc, True) # Skip all parts def call(self, arg_list, pc, envt, cont): + pc = pc.car # TODO: check identifier - if is_arg(pc.chd): # Simple value assignment - id = pc.chd.obj + if is_arg(pc.cdr): # Simple value assignment + id = pc.cdr.car obj = arg_list[0] else: # Procedure definition - id = pc.chd.obj.obj + id = pc.cdr.car.car para_list = list() # Parameter list - par = pc.chd - if par.chd: # If there's at least one parameter - par = par.chd - while par: - para_list.append(par.obj) - par = par.sib + par = pc.cdr.car + if not (par.cdr is empty_list): + # If there's at least one parameter + par = par.cdr + while not (par is empty_list): + para_list.append(par.car) + par = par.cdr # Clear the flag to avoid side-effects (e.g. proc calling) _fill_marks(pc, False) - pc = pc.chd.sib # Move pc to procedure body + pc = pc.cdr.cdr # Move pc to procedure body #TODO: check body body = list() # store a list of expressions inside <body> - while pc: + while not (pc is empty_list): body.append(pc) - pc.next = None - pc = pc.sib + pc.func.next = None + pc = pc.cdr obj = ProcObj(body, envt, para_list) @@ -225,12 +226,12 @@ class _builtin_define(SpecialOptObj): class _builtin_set(SpecialOptObj): def prepare(self, pc): # TODO: check number of arguments - pc = pc.chd - pc.skip = True # Skip the identifier - pc.sib.skip = False + pc.cdr.func.skip = True # Skip the identifier + pc.cdr.cdr.func.skip = False def call(self, arg_list, pc, envt, cont): - id = pc.chd.obj + pc = pc.car + id = pc.cdr.car if envt.has_obj(id): envt.add_binding(id, arg_list[0]) return (UnspecObj(), False) @@ -261,52 +262,36 @@ class Tokenizor(): return None return self.tokenized.pop(0) -class Node(object): # AST Node - def __init__(self, obj, sib): - self.obj = obj - self.sib = sib - self.skip = None # skip the current branch? (runtime) - self.next = sib # next instruction (runtime) +class Prog(object): + def __init__(self, skip = False, next = None): + self.skip = skip + self.next = next - def __str__(self): - return "#<AST Node>" - def __expr__(self): - return self.__str__() +class Data(object): + pass -class ArgNode(Node): # AST Node (Argument) - def __init__(self, obj, sib = None): - super(ArgNode, self).__init__(obj, sib) +class Cons(object): # Construction + def __init__(self, car, cdr, func = Data()): + self.car = car + self.cdr = cdr + self.func = func + def ext_repr(self): + return "#<Cons>" def __str__(self): - return "#<AST ArgNode>" - def __expr__(self): - return self.__str__() - + return self.ext_repr() def print_(self): - print \ - "======================" + "\n" + \ - "Obj: " + str(self.obj) + "\n" + \ - "Sib: " + str(self.sib) + "\n" + \ - "======================" - -class OptNode(Node): # AST Node (Operator) - def __init__(self, obj, sib = None, chd = None): - super(OptNode, self).__init__(obj, sib) - self.chd = chd + print "car: " + str(self.car) + "\n" + \ + "cdr: " + str(self.cdr) + "\n" +class EmptyList(object): + def ext_repr(self): + return "()" def __str__(self): - return "#<AST OptNode>" - def __expr__(self): - return self.__str__() + return self.ext_repr() - def print_(self): - print \ - "======================" + "\n" + \ - "Obj: " + str(self.obj) + "\n" + \ - "Sib: " + str(self.sib) + "\n" + \ - "Chd: " + str(self.chd) + "\n" + \ - "======================" - -class RetAddr(object): # Return Adress (Refers to an AST Node) +empty_list = EmptyList() + +class RetAddr(object): # Return Adress (Refers to an Cons) def __init__(self, addr): self.addr = addr def __str__(self): @@ -315,16 +300,11 @@ class RetAddr(object): # Return Adress (Refers to an AST Node) class ASTGenerator(EvalObj): # Abstract Syntax Tree Generator def to_obj(self, obj): # Try to convert a string to EvalObj - 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): # Try to convert an EvalObj to AST Node - if isinstance(obj, Node): return obj - return ArgNode(obj) - def __init__(self, stream): self.stream = stream self.stack = list() # Empty stack @@ -333,7 +313,8 @@ class ASTGenerator(EvalObj): # Abstract Syntax Tree Generator stack = self.stack while True: if len(stack) > 0 and stack[0] != '(': - return self.to_node(stack.pop(0)) # An AST is constructed + return Cons(stack.pop(0), empty_list, Prog(0)) + # An AST is constructed token = self.stream.read() # Read a new token if token is None: return None # Feed me! if token == '(': @@ -344,25 +325,24 @@ class ASTGenerator(EvalObj): # Abstract Syntax Tree Generator lst = stack[-1:] + lst del stack[-1] if len(lst) > 0: # At least one elem - root = OptNode(lst[0]) # The operator in the list + root = Cons(lst[0], None, Prog()) # The operator in the list # Collect the operands - if len(lst) > 1: - root.chd = lst[1] - ref = root.chd - for i in lst[2:]: - ref.sib = i - ref.next = ref.sib - ref = ref.sib + ref = root + for i in lst[1:]: + ref.cdr = Cons(i, None, Prog()) + ref.func.next = ref.cdr + ref = ref.cdr + ref.cdr = empty_list stack[-1] = root else: # Null list - stack[-1] = OptNode(ArgNode(None)) + stack[-1] = empty_list else: - stack.append(ArgNode(self.to_obj(token))) # Found an EvalObj + stack.append(self.to_obj(token)) # Found an EvalObj def is_id(string): return isinstance(string, IdObj) -def is_arg(node): - return isinstance(node, ArgNode) +def is_arg(pc): + return isinstance(pc.car, EvalObj) def is_ret_addr(val): return isinstance(val, RetAddr) def is_builtin_proc(val): @@ -475,66 +455,32 @@ class Evaluator(object): self._add_builtin_routines(self.envt) def run_expr(self, prog): stack = [0] * 100 # Eval Stack - ostack = [0] * 100 # Operator to be evaluated - top = -1 # stack top - otop = -1 # ostack top pc = prog # pc register cont = None # continuation register envt = self.envt # environment register - def print_stack(): - print '++++++++++STACK++++++++' - if len(stack) > 0: - for i in range(0, top + 1): - print stack[i] - print '----------STACK--------' - - def next_addr(ret_addr, otop): # Get the next instruction (after returning) - notop = otop - if otop > -1 and ret_addr is ostack[notop]: - # If the operator is evaluated successfully - # pc should point to its operand - notop -= 1 - res = ostack[notop].chd - notop -= 1 - else: - # Normal situation: move to the next operand - res = ret_addr.next - return (res, notop) - - - def push(pc, top, otop): # Push EvalObj to the stack + def push(pc, top): # Push EvalObj to the stack ntop = top - notop = otop - if is_arg(pc): # Pure operand + if is_arg(pc): # Pure operand ntop += 1 - stack[ntop] = envt.get_obj(pc.obj) # Try to find the binding - npc = pc.next # Move to the next instruction + stack[ntop] = envt.get_obj(pc.car) # Try to find the binding + if is_special_opt(stack[ntop]): + stack[ntop].prepare(pc) + npc = pc.func.next # Move to the next instruction else: # Found an Operator ntop += 1 - stack[ntop] = RetAddr(pc) # Push return address - if is_arg(pc.obj): # Getting operator - ntop += 1 - stack[ntop] = envt.get_obj(pc.obj.obj) - if is_special_opt(stack[ntop]): - stack[ntop].prepare(pc) - npc = pc.chd - else: # Operator need to be evaluated - notop += 1 - ostack[notop] = pc - notop += 1 - ostack[notop] = pc.obj - npc = pc.obj - - return (npc, ntop, notop) - - (pc, top, otop) = push(pc, top, otop) + stack[ntop] = RetAddr(pc) # Push return address + npc = pc.car + + return (npc, ntop) + + (pc, top) = push(pc, top) while is_ret_addr(stack[0]): # Still need to evaluate - while pc and pc.skip: - pc = pc.next # Skip the masked branches + while pc and pc.func.skip: + pc = pc.func.next # Skip the masked branches if pc is None: # All arguments are evaluated, exiting arg_list = list() @@ -553,7 +499,7 @@ class Evaluator(object): if ncur == len(body): # All exps in the body are evaled stack[top] = arg_list[0] envt = cont.envt - (pc, otop) = next_addr(cont.pc, otop) + pc = cont.pc.func.next cont = cont.old_cont else: pc = body[ncur] # Load the next exp @@ -562,16 +508,16 @@ class Evaluator(object): if is_builtin_proc(opt): # Built-in Procedures stack[top] = opt.call(arg_list[1:]) - (pc, otop) = next_addr(ret_addr, otop) + pc = ret_addr.func.next elif is_special_opt(opt): # Sepecial Operations (res, flag) = opt.call(arg_list[1:], ret_addr, envt, cont) if flag: # Need to call again top += 1 - pc = ret_addr.chd # Invoke again + pc = ret_addr.car.func.next # Invoke again else: stack[top] = res # Done - (pc, otop) = next_addr(ret_addr, otop) + pc = ret_addr.func.next elif is_user_defined_proc(opt): # User-defined Procedures # Create a new continuation @@ -585,7 +531,7 @@ class Evaluator(object): stack[top] = RetAddr(False) # Continuation mark pc = opt.body[0] # Move to the proc entry point else: - (pc, top, otop) = push(pc, top, otop) + (pc, top) = push(pc, top) return stack[0] diff --git a/sketch_obsolete.py b/sketch_obsolete.py new file mode 100755 index 0000000..36be406 --- /dev/null +++ b/sketch_obsolete.py @@ -0,0 +1,608 @@ +#! /bin/env python + +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 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 IdObj(EvalObj): + def __init__(self, string): + self.name = string + def __str__(self): + return "#<Identifier: " + self.name + ">" + def get_name(): + return self.name + +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, 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 "#<Builtin Procedure: " + self.name + ">" + def __str__(self): + return self.ext_repr() + def call(self, arg_list): + return self.handler(arg_list) + +# Convert an obj to boolean +def to_bool(obj): + if obj.val is False: + return BoolObj(False) + else: + return BoolObj(True) + +# Mark all children of pc as flag +def _fill_marks(pc, flag): + pc = pc.chd + while pc: + pc.skip = flag + pc = pc.sib + +class _builtin_if(SpecialOptObj): + def prepare(self, pc): + # TODO: check number of arguments + # Evaluate the condition first + self.state = 0 # Prepared + pc = pc.chd + pc.skip = False + pc.sib.skip = True + if pc.sib.sib: + pc.sib.sib.skip = True + + def pre_call(self, arg_list, pc, envt, cont): + # Condition evaluated and the decision is made + self.state = 1 + if (to_bool(arg_list[0])).val: + pc = pc.chd + pc.skip = True + pc.sib.skip = False + if pc.sib.sib: + # Eval the former + 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: + # Eval the latter + pc.sib.sib.skip = False + return (None, True) # Re-eval + + def post_call(self, arg_list, pc, envt, cont): + # Value already evaluated, so just return it + 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, pc): + # TODO: check number of arguments + # Do not evaulate anything + _fill_marks(pc, True) + + def call(self, arg_list, pc, envt, cont): + para_list = list() # paramter list + par = pc.chd # Switch to the first parameter + if par.obj.obj: # If there is at least one parameter + para_list.append(par.obj.obj) + if par.chd: # More paramters? + par = par.chd + while par: + para_list.append(par.obj) + par = par.sib + + # Clear the flag to avoid side-effects (e.g. proc calling) + _fill_marks(pc, False) + + pc = pc.chd.sib # Move pc to procedure body + #TODO: check body + body = list() # store a list of expressions inside <body> + + while pc: + body.append(pc) + pc.next = None # Make each expression a orphan + # in order to ease the exit checking + pc = pc.sib + + 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, pc): + if is_arg(pc.chd): # Simple value assignment + pc.chd.skip = True # Skip the identifier + pc.chd.sib.skip = False + else: # Procedure definition + _fill_marks(pc, True) # Skip all parts + + def call(self, arg_list, pc, envt, cont): + # TODO: check identifier + if is_arg(pc.chd): # Simple value assignment + id = pc.chd.obj + obj = arg_list[0] + else: # Procedure definition + id = pc.chd.obj.obj + para_list = list() # Parameter list + par = pc.chd + if par.chd: # If there's at least one parameter + par = par.chd + while par: + para_list.append(par.obj) + par = par.sib + + # Clear the flag to avoid side-effects (e.g. proc calling) + _fill_marks(pc, False) + pc = pc.chd.sib # Move pc to procedure body + #TODO: check body + body = list() # store a list of expressions inside <body> + + while pc: + body.append(pc) + pc.next = None + pc = pc.sib + + obj = ProcObj(body, envt, para_list) + + envt.add_binding(id, obj) + 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, pc): + # TODO: check number of arguments + pc = pc.chd + pc.skip = True # Skip the identifier + 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 "#<Builtin Macro: set!>" + def __str__(self): + return self.ext_repr() + +class Tokenizor(): + + def __init__(self): + self.data = "" # string buffer + self.tokenized = list() # tokens + + def feed(self, data): # Store the data in the buffer + self.data = data + + def read(self): + if len(self.tokenized) == 0: # no tokens available, let's produce + if len(self.data) == 0: # I'm hungry, feed me! + return None + self.tokenized = self.data.replace('(', '( ')\ + .replace(')', ' )')\ + .split() + self.data = "" # Clear the buffer + if len(self.tokenized) == 0: # You feed me with the air, bastard! + return None + return self.tokenized.pop(0) + +class Node(object): # AST Node + def __init__(self, obj, sib): + self.obj = obj + self.sib = sib + self.skip = None # skip the current branch? (runtime) + self.next = sib # next instruction (runtime) + + def __str__(self): + return "#<AST Node>" + def __expr__(self): + return self.__str__() + +class ArgNode(Node): # AST Node (Argument) + def __init__(self, obj, sib = None): + super(ArgNode, self).__init__(obj, sib) + def __str__(self): + return "#<AST ArgNode>" + def __expr__(self): + return self.__str__() + + def print_(self): + print \ + "======================" + "\n" + \ + "Obj: " + str(self.obj) + "\n" + \ + "Sib: " + str(self.sib) + "\n" + \ + "======================" + +class OptNode(Node): # AST Node (Operator) + def __init__(self, obj, sib = None, chd = None): + super(OptNode, self).__init__(obj, sib) + self.chd = chd + + def __str__(self): + return "#<AST OptNode>" + 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): # Return Adress (Refers to an AST Node) + def __init__(self, addr): + self.addr = addr + def __str__(self): + return "#<Return Address>" + +class ASTGenerator(EvalObj): # Abstract Syntax Tree Generator + + def to_obj(self, obj): # Try to convert a string to EvalObj + 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): # Try to convert an EvalObj to AST Node + if isinstance(obj, Node): return obj + return ArgNode(obj) + + def __init__(self, stream): + self.stream = stream + self.stack = list() # Empty stack + + def absorb(self): + stack = self.stack + while True: + if len(stack) > 0 and stack[0] != '(': + return self.to_node(stack.pop(0)) # An AST is constructed + token = self.stream.read() # Read a new token + if token is None: return None # Feed me! + if token == '(': + stack.append(token) + elif token == ')': # A list is enclosed + lst = list() + while stack[-1] != '(': + lst = stack[-1:] + lst + del stack[-1] + if len(lst) > 0: # At least one elem + root = OptNode(lst[0]) # The operator in the list + # Collect the operands + if len(lst) > 1: + root.chd = lst[1] + ref = root.chd + for i in lst[2:]: + ref.sib = i + ref.next = ref.sib + ref = ref.sib + stack[-1] = root + else: # Null list + stack[-1] = OptNode(ArgNode(None)) + else: + stack.append(ArgNode(self.to_obj(token))) # Found an EvalObj + +def is_id(string): + return isinstance(string, IdObj) +def is_arg(node): + return isinstance(node, ArgNode) +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): # Store all bindings + def __init__(self, prev_envt = None): + self.prev_envt = prev_envt + self.binding = dict() + + def add_binding(self, id_obj, eval_obj): # Bind id_obj to eval_obj + self.binding[id_obj.name] = eval_obj + + def get_obj(self, id_obj): + if is_id(id_obj): # Resolve the id + ptr = self + while ptr: # Lookup the id in the chain + try: + return ptr.binding[id_obj.name] + except KeyError: + ptr = ptr.prev_envt + raise KeyError + else: + return id_obj # id_obj is inherently an EvalObj + + 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 + +class Continuation(object): # Store the state of the interpreter + def __init__(self, envt, pc, old_cont, proc_body, body_cnt = 0): + self.envt = envt # envt pointer + self.pc = pc # pc pointer + self.old_cont = old_cont # previous state + self.proc_body = proc_body # procedure expression list + self.body_cnt = 0 # how many exp have been evaluated + +# Miscellaneous builtin procedures # +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 "Display: " + arg_list[0].ext_repr() + return UnspecObj() +# Miscellaneous builtin procedures # + +_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 # Eval Stack + ostack = [0] * 100 # Operator to be evaluated + + top = -1 # stack top + otop = -1 # ostack top + + pc = prog # pc register + cont = None # continuation register + envt = self.envt # environment register + + def print_stack(): + print '++++++++++STACK++++++++' + if len(stack) > 0: + for i in range(0, top + 1): + print stack[i] + print '----------STACK--------' + + def next_addr(ret_addr, otop): # Get the next instruction (after returning) + notop = otop + if otop > -1 and ret_addr is ostack[notop]: + # If the operator is evaluated successfully + # pc should point to its operand + notop -= 1 + res = ostack[notop].chd + notop -= 1 + else: + # Normal situation: move to the next operand + res = ret_addr.next + return (res, notop) + + + def push(pc, top, otop): # Push EvalObj to the stack + ntop = top + notop = otop + if is_arg(pc): # Pure operand + ntop += 1 + stack[ntop] = envt.get_obj(pc.obj) # Try to find the binding + npc = pc.next # Move to the next instruction + else: # Found an Operator + ntop += 1 + stack[ntop] = RetAddr(pc) # Push return address + if is_arg(pc.obj): # Getting operator + ntop += 1 + stack[ntop] = envt.get_obj(pc.obj.obj) + if is_special_opt(stack[ntop]): + stack[ntop].prepare(pc) + npc = pc.chd + else: # Operator need to be evaluated + notop += 1 + ostack[notop] = pc + notop += 1 + ostack[notop] = pc.obj + npc = pc.obj + + return (npc, ntop, notop) + + (pc, top, otop) = push(pc, top, otop) + + while is_ret_addr(stack[0]): # Still need to evaluate + while pc and pc.skip: + pc = pc.next # Skip the masked branches + + if pc is None: # All arguments are evaluated, exiting + arg_list = list() + # Collect all arguments + while not is_ret_addr(stack[top]): + arg_list = [stack[top]] + arg_list + top -= 1 + opt = arg_list[0] # the operator + ret_addr = stack[top].addr # Return address + + # Fake return (one of the expressions are evaluated) + if ret_addr is False: + body = cont.proc_body + cont.body_cnt += 1 + ncur = cont.body_cnt + if ncur == len(body): # All exps in the body are evaled + stack[top] = arg_list[0] + envt = cont.envt + (pc, otop) = next_addr(cont.pc, otop) + cont = cont.old_cont + else: + pc = body[ncur] # Load the next exp + continue + # Revert to the original cont. + + if is_builtin_proc(opt): # Built-in Procedures + stack[top] = opt.call(arg_list[1:]) + (pc, otop) = next_addr(ret_addr, otop) + + elif is_special_opt(opt): # Sepecial Operations + (res, flag) = opt.call(arg_list[1:], ret_addr, envt, cont) + if flag: # Need to call again + top += 1 + pc = ret_addr.chd # Invoke again + else: + stack[top] = res # Done + (pc, otop) = next_addr(ret_addr, otop) + + elif is_user_defined_proc(opt): # User-defined Procedures + # Create a new continuation + ncont = Continuation(envt, ret_addr, cont, opt.body) + cont = ncont # Add to the cont chain + envt = Environment(opt.envt) # Create local env and recall 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) # Continuation mark + pc = opt.body[0] # Move to the proc entry point + else: + (pc, top, otop) = push(pc, top, otop) + + return stack[0] + +t = Tokenizor() +e = Evaluator() + +import sys, pdb + +a = ASTGenerator(t) +while True: + sys.stdout.write("Sonsi> ") + while True: + exp = a.absorb() + if exp: break + cmd = sys.stdin.readline() + t.feed(cmd) + try: + print e.run_expr(exp).ext_repr() + except Exception as exc: + print exc |