class SyntaxObj(object):
pass
class EvalObj(SyntaxObj):
def __str__(self):
return "#<Object>"
class ValObj(EvalObj):
def __str__(self):
return "#<Value>"
class NumberObj(ValObj):
def __str__(selfl):
return "#<Number>"
class IntObj(NumberObj):
def __init__(self, num):
self.val = int(num)
def __str__(self):
return "#<Integer>"
class FloatObj(NumberObj):
def __init__(self, num):
self.val = float(num)
def __str__(self):
return "#<Float>"
class StringObj(ValObj):
def __init__(self, string):
self.val = string
def __str__(self):
return "#<String>"
class OptObj(EvalObj):
pass
class ProcObj(OptObj):
def __init__(self, prog, env = None):
self.prog = prog
self.env = env
def __str__(self):
return "#<Procedure>"
class IdObj(SyntaxObj):
def __init__(self, string):
self.name = string
def __str__(self):
return "#<Identifier>"
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.typ = None # operator operand if-macro if-clause
def __str__(self):
return "#<AST Node>"
def print_(self):
print \
"======================" + "\n" + \
"Obj: " + str(self.obj) + "\n" + \
"Sib: " + str(self.sib) + "\n" + \
"Chd: " + str(self.chd) + "\n" + \
"======================"
class AbsSynTree(EvalObj):
def to_node(self, obj):
if isinstance(obj, Node): return obj
# else the obj is a string
try: return Node(IntObj(obj))
except Exception:
try: return Node(FloatObj(obj))
except Exception: return Node(IdObj(obj))
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]
root = lst[0]
if len(lst) > 1:
root.chd = lst[1]
ref = root.chd
for i in lst[2:]:
ref.sib = i
ref = ref.sib
stack[-1] = root
else:
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_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):
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)
_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() # 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("(+ (- (* 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