diff options
| -rwxr-xr-x[-rw-r--r--] | sketch.py | 396 |
1 files changed, 178 insertions, 218 deletions
diff --git a/sketch.py b/sketch.py index cf93022..36be406 100644..100755 --- a/sketch.py +++ b/sketch.py @@ -10,7 +10,6 @@ class UnspecObj(EvalObj): def ext_repr(self): return self.__str__() - class NumberObj(EvalObj): def __str__(selfl): return "#<Number>" @@ -31,14 +30,6 @@ class FloatObj(NumberObj): 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 @@ -50,6 +41,14 @@ class BoolObj(EvalObj): 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 @@ -80,31 +79,40 @@ class BuiltinProcObj(): 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): - self.state = 0 # prepare # 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 - # 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) + # 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: @@ -112,9 +120,12 @@ class _builtin_if(SpecialOptObj): 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): @@ -122,83 +133,85 @@ class _builtin_if(SpecialOptObj): 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 _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) + # Do not evaulate anything + _fill_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: + 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 - self._clear_marks(pc, False) - pc = pc.chd.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() + body = list() # store a list of expressions inside <body> + while pc: body.append(pc) - pc.next = None # Detach + pc.next = None # Make each expression a orphan + # in order to ease the exit checking pc = pc.sib - # Add exps + 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 _clear_marks(self, pc, flag): - pc = pc.chd - while pc: - pc.skip = flag - pc = pc.sib def prepare(self, pc): - if is_arg(pc.chd): # Normal Def - pc.chd.skip = True + if is_arg(pc.chd): # Simple value assignment + pc.chd.skip = True # Skip the identifier pc.chd.sib.skip = False - else: - self._clear_marks(pc, True) - return (None, True) # Re-eval + else: # Procedure definition + _fill_marks(pc, True) # Skip all parts def call(self, arg_list, pc, envt, cont): # TODO: check identifier - id = pc.chd.obj - if is_arg(pc.chd): + if is_arg(pc.chd): # Simple value assignment + id = pc.chd.obj obj = arg_list[0] - else: # Function definition + else: # Procedure definition + id = pc.chd.obj.obj + para_list = list() # Parameter list par = pc.chd - para_list = list() - if par.chd: + if par.chd: # If there's at least one parameter par = par.chd while par: para_list.append(par.obj) par = par.sib - # Collection para list - self._clear_marks(pc, False) - pc = pc.chd.sib - body = list() + + # 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) @@ -212,9 +225,9 @@ class _builtin_define(SpecialOptObj): class _builtin_set(SpecialOptObj): def prepare(self, pc): # TODO: check number of arguments - pc = pc.chd - pc.skip = True - pc.sib.skip = False + 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 @@ -227,55 +240,40 @@ class _builtin_set(SpecialOptObj): 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 = "" # 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: - if len(self.data) == 0: + 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 = "" - if len(self.tokenized) == 0: + 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): +class Node(object): # AST Node def __init__(self, obj, sib): self.obj = obj self.sib = sib - self.skip = None # delay calcuation - self.next = 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): +class ArgNode(Node): # AST Node (Argument) def __init__(self, obj, sib = None): super(ArgNode, self).__init__(obj, sib) def __str__(self): @@ -290,7 +288,7 @@ class ArgNode(Node): "Sib: " + str(self.sib) + "\n" + \ "======================" -class OptNode(Node): +class OptNode(Node): # AST Node (Operator) def __init__(self, obj, sib = None, chd = None): super(OptNode, self).__init__(obj, sib) self.chd = chd @@ -308,25 +306,24 @@ class OptNode(Node): "Chd: " + str(self.chd) + "\n" + \ "======================" -class RetAddr(object): +class RetAddr(object): # Return Adress (Refers to an AST Node) def __init__(self, addr): self.addr = addr def __str__(self): return "#<Return Address>" -class ASTree(EvalObj): +class ASTGenerator(EvalObj): # Abstract Syntax Tree Generator - def to_obj(self, obj): + 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): + def to_node(self, obj): # Try to convert an EvalObj to AST Node if isinstance(obj, Node): return obj return ArgNode(obj) - # else the obj is a string def __init__(self, stream): self.stream = stream @@ -336,34 +333,33 @@ class ASTree(EvalObj): stack = self.stack while True: if len(stack) > 0 and stack[0] != '(': - return self.to_node(stack.pop(0)) # Got an expression - token = self.stream.read() - if token is None: return None + 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 == ')': + elif token == ')': # A list is enclosed lst = list() while stack[-1] != '(': lst = stack[-1:] + lst del stack[-1] - if len(lst) > 0: - root = OptNode(lst[0]) + 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 = self.to_node(lst[1]) + root.chd = lst[1] ref = root.chd for i in lst[2:]: - ref.sib = self.to_node(i) + ref.sib = i ref.next = ref.sib ref = ref.sib stack[-1] = root - else: - stack[-1] = self.to_node(None) + else: # Null list + stack[-1] = OptNode(ArgNode(None)) else: - stack.append(self.to_obj(token)) + stack.append(ArgNode(self.to_obj(token))) # Found an EvalObj -def is_obj(string): - return isinstance(string, EvalObj) -def is_identifier(string): +def is_id(string): return isinstance(string, IdObj) def is_arg(node): return isinstance(node, ArgNode) @@ -376,50 +372,45 @@ def is_special_opt(val): def is_user_defined_proc(val): return isinstance(val, ProcObj) -class Environment(object): +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): + def add_binding(self, id_obj, eval_obj): # Bind id_obj to 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): + if is_id(id_obj): # Resolve the id ptr = self - while ptr: + while ptr: # Lookup the id in the chain 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 + return id_obj # id_obj is inherently an EvalObj -class Continuation(object): - def __init__(self, envt, pc, old_cont, proc_body, proc_body_cur = 0): - self.envt = envt - self.pc = pc - self.old_cont = old_cont - self.proc_body = proc_body - self.proc_body_cur = 0 - - def get_envt(self): - return self.envt - def get_cont(self): - return self.cont + 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: @@ -457,6 +448,7 @@ def _builtin_eq(arg_list): def _builtin_display(arg_list): print "Display: " + arg_list[0].ext_repr() return UnspecObj() +# Miscellaneous builtin procedures # _default_mapping = { IdObj("+") : BuiltinProcObj(_builtin_plus, "+"), @@ -482,13 +474,15 @@ class Evaluator(object): 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 # Set to the root - cont = Continuation(None, pc, None, None) - envt = self.envt - top = -1 # Stack top - otop = -1 + 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++++++++' @@ -497,136 +491,102 @@ class Evaluator(object): 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): + 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): + def push(pc, top, otop): # Push EvalObj to the stack ntop = top notop = otop - if is_arg(pc): - # print "first" + if is_arg(pc): # Pure operand ntop += 1 - if pc.skip: - new_obj = pc.obj - else: - new_obj = envt.get_obj(pc.obj) - stack[ntop] = new_obj - npc = pc.next - # pc.print_() - #print "this val is: " + str(stack[ntop].val) - else: - # print "second" + 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) # Return address - if isinstance(pc.obj, Node): - # print "Operator need to be resolved!" + 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 - # 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.next # Skip the masked branches - - if pc is None: + pc = pc.next # Skip the masked branches - # print "Poping..." + 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 - # Top is now pointing to the return address - # print "Arg List: " + str(arg_list) - opt = arg_list[0] - ret_addr = stack[top].addr + opt = arg_list[0] # the operator + ret_addr = stack[top].addr # Return address - if ret_addr is False: # Fake return + # Fake return (one of the expressions are evaluated) + if ret_addr is False: body = cont.proc_body - cont.proc_body_cur += 1 - ncur = cont.proc_body_cur + 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) = nxt_addr(cont.pc, otop) + (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 - # print "builtin" + if is_builtin_proc(opt): # Built-in Procedures stack[top] = opt.call(arg_list[1:]) - (pc, otop) = nxt_addr(ret_addr, otop) + (pc, otop) = next_addr(ret_addr, otop) - elif is_special_opt(opt): # Sepecial Operations - # print "specialopt" + elif is_special_opt(opt): # Sepecial Operations (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) + if flag: # Need to call again top += 1 - pc = ret_addr.chd # Again + pc = ret_addr.chd # Invoke 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, opt.body) # Create a new continuation - cont = ncont # Make chain - envt = Environment(opt.envt) # New ENV and recover the closure + 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) # Mark the exit of the continuation - pc = opt.body[0] # Get to the entry point - - # print_stack() - # print "Poping done." + 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: - # print " Pushing..." - # print_stack() (pc, top, otop) = push(pc, top, otop) - # print_stack() - # print " Done...\n" + return stack[0] t = Tokenizor() @@ -634,9 +594,9 @@ e = Evaluator() import sys, pdb -a = ASTree(t) +a = ASTGenerator(t) while True: - sys.stdout.write("Syasi> ") + sys.stdout.write("Sonsi> ") while True: exp = a.absorb() if exp: break |