aboutsummaryrefslogtreecommitdiff
path: root/sketch.py
diff options
context:
space:
mode:
Diffstat (limited to 'sketch.py')
-rwxr-xr-x[-rw-r--r--]sketch.py396
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
Powered by cgit, Themed by Ted Yin.