From 392710b213c30b6e14e6a26e5d199350209aeef9 Mon Sep 17 00:00:00 2001 From: Teddy Date: Tue, 30 Jul 2013 14:07:01 +0800 Subject: simple evaluation --- sketch.py | 209 +++++++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 161 insertions(+), 48 deletions(-) diff --git a/sketch.py b/sketch.py index edd866c..a1c2a07 100644 --- a/sketch.py +++ b/sketch.py @@ -10,38 +10,43 @@ class ValObj(EvalObj): return "#" class NumberObj(ValObj): - def __str__(): + def __str__(selfl): return "#" class IntObj(NumberObj): def __init__(self, num): self.val = int(num) - def __str__(): + def __str__(self): return "#" class FloatObj(NumberObj): def __init__(self, num): self.val = float(num) - def __str__(): + def __str__(self): return "#" class StringObj(ValObj): def __init__(self, string): self.val = string - def __str__(): + def __str__(self): return "#" -class ProcObj(ValObj): - def __init__(self, env, prog): - self.val = proc +class OptObj(EvalObj): + pass +class ProcObj(OptObj): + def __init__(self, prog, env = None): + self.prog = prog + self.env = env - def __str__(): + def __str__(self): return "#" class IdObj(SyntaxObj): def __init__(self, string): self.name = string + def __str__(self): + return "#" def get_name(): return self.name @@ -72,26 +77,31 @@ class Tokenizor(): self.data = "" return self.tokenized.pop(0) -class AST(EvalObj): +class Node(object): + def __init__(self, syn_obj, sib = None, chd = None): + self.obj = syn_obj + self.sib = sib + self.chd = chd + self.typ = None # operator operand if-macro if-clause + def __str__(self): + return "#" + def print_(self): + print \ + "======================" + "\n" + \ + "Obj: " + str(self.obj) + "\n" + \ + "Sib: " + str(self.sib) + "\n" + \ + "Chd: " + str(self.chd) + "\n" + \ + "======================" - class Node(object): - def __init__(self, syn_obj, sib = None, chd = None): - self.obj = syn_obj - self.sib = sib - self.chd = chd - def __str__(self): - return \ - "Obj: " + str(self.obj) + " " + \ - "Sib: " + str(self.sib) + " " + \ - "Chd: " + str(self.chd) +class AbsSynTree(EvalObj): def to_node(self, obj): - if isinstance(obj, self.Node): return obj + if isinstance(obj, Node): return obj # else the obj is a string - try: return self.Node(IntObj(obj)) - except ValueError: - try: return self.Node(FloatObj(obj)) - except ValueError: return self.Node(IdObj(obj)) + try: return Node(IntObj(obj)) + except Exception: + try: return Node(FloatObj(obj)) + except Exception: return Node(IdObj(obj)) def __init__(self, stream): stack = list() @@ -105,25 +115,35 @@ class AST(EvalObj): while stack[-1] != '(': lst = stack[-1:] + lst del stack[-1] - root = self.to_node(lst[0]) + root = lst[0] 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 = ref.sib stack[-1] = root else: - stack.append(token) + stack.append(self.to_node(token)) self.tree = stack +def is_identifier(string): + return isinstance(string, IdObj) +def is_val(node): + return node.chd is None +def is_ret_addr(val): + return isinstance(val, Node) + class Environment(object): def __init__(self): self.binding = dict() - def add_entry(id_obj, eval_obj): - self.binding[id_obj] = eval_obj - def get_obj(id_obj): - return self.binding[id_obj] + 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): @@ -135,23 +155,116 @@ class Continuation(object): 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) + +_default_mapping = { + "+" : _builtin_plus, + "-" : _builtin_minus, + "*" : _builtin_times, + "/" : _builtin_div} + 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() - self.cont = None - self.pc = None - def run(self, prog): - self.stack = list() # object stack - self.flag = list() # call flag True for call False for value - self.pc = prog # Set to the root - self.top = 0 # Stack top - - while self.flag[0]: # Still need to evaluate - pass - + 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 push(pc, top): + ntop = top + if is_val(pc): + ntop += 1 + stack[ntop] = envt.get_obj(pc.obj) + npc = pc.sib + print "first" + print "this val is: " + str(pc.obj) + else: + ntop += 1 + stack[ntop] = pc # Return address + ntop += 1 + stack[ntop] = envt.get_obj(pc.obj) + npc = pc.chd + 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) + if pc is None: + print "Poping..." + arg_list = list() + while not is_ret_addr(stack[top]): + arg_list = [stack[top]] + arg_list + top -= 1 + if is_identifier(arg_list[0]): + arg_list[0] = envt.get_obj(arg_list[0]) + pc = stack[top].sib + stack[top] = arg_list[0](arg_list[1:]) + print_stack() + print "RET to: " + if pc: + pc.print_() + if is_identifier(pc.obj): + print pc.obj.name + else: + print pc.obj.val + else: print "NULL" + else: + print " Pushing..." + print_stack() + (pc, top) = push(pc, top) + print_stack() + print " Done...\n" + return stack[0] + t = Tokenizor() -t.feed("(lambda (x) (x * x))") -a = AST(t) -root = a.tree -print root.__str__() +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 -- cgit v1.2.3