aboutsummaryrefslogtreecommitdiff
path: root/sketch_obsolete.py
diff options
context:
space:
mode:
Diffstat (limited to 'sketch_obsolete.py')
-rwxr-xr-xsketch_obsolete.py608
1 files changed, 0 insertions, 608 deletions
diff --git a/sketch_obsolete.py b/sketch_obsolete.py
deleted file mode 100755
index 36be406..0000000
--- a/sketch_obsolete.py
+++ /dev/null
@@ -1,608 +0,0 @@
-#! /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