aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTeddy <ted.sybil@gmail.com>2013-07-31 20:46:43 +0800
committerTeddy <ted.sybil@gmail.com>2013-07-31 20:46:43 +0800
commitafdc71eaeffc760e5ceea76d35402fc2404bc80d (patch)
treeef535316c61ce69a9595110e75cfcec81ae396a5
parent19d260020ca4025cf5d7d987966579c5d6276056 (diff)
use a simple and elegant way to represent the AST
-rwxr-xr-xsketch.py270
-rwxr-xr-xsketch_obsolete.py608
2 files changed, 716 insertions, 162 deletions
diff --git a/sketch.py b/sketch.py
index 36be406..8e623b7 100755
--- a/sketch.py
+++ b/sketch.py
@@ -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