#! /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