added comments and adjusted the construction of AST

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