Skip to content

Instantly share code, notes, and snippets.

@vgel

vgel/gist:3735180

Created September 17, 2012 02:06
Show Gist options
  • Save vgel/3735180 to your computer and use it in GitHub Desktop.
Save vgel/3735180 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.py
import re, logging, time, cProfile
class Word(object):
def __init__(self, function, name, types, inputs):
if name == '':
raise ValueError("Invalid name.")
self.name = name
self.function = function
self.types = types
self.inputs = inputs
class Parser(object):
def __init__(self):
self.S_NOP = lambda x, tok: ('w',None)
self.S_WRD = lambda x, tok: ('w',tok)
self.S_STR = lambda x, tok: ('s',str(tok[1:-1]))
self.S_INT = lambda x, tok: ('i',int(tok))
self.lex = re.Scanner([
(r"[a-zA-Z_][a-zA-Z0-9_]*", self.S_WRD),
(r"'(?:\\.|[^'])*'?", self.S_STR),
(r'"(?:\\.|[^"])*"?', self.S_STR),
(r"-?[0-9]+", self.S_INT),
(r"#[^\n\r]*", self.S_NOP),
(r".", self.S_WRD),
], re.M)
def do(self, prg):
c,leftovers = self.lex.scan(prg)
if leftovers: raise ValueError("Lexer fail.")
c = c[::-1]
logging.debug(c)
def recurse_blocks(inp):
s = []
while True:
i = c.pop()
if i == ('w','}'): return ("b",s)
elif i == ('w','{'): s.append(recurse_blocks(inp))
else: s.append(i)
raise ValueError("Blocks don't match.")
code = []
while c:
i = c.pop()
if i == ('w','{'): code.append(recurse_blocks(c))
elif i == ('w','}'): raise ValueError("Blocks don't match.")
else: code.append(i)
return code
class FunctionProfile(object):
def __init__(self):
self.time = 0
self.calls = 1
def called(self):
self.calls += 1
def __repr__(self):
return "calls:%10s\ttotal time:%.3f" % (self.calls, self.time)
class Interpreter(object):
def __init__(self):
self.parser = Parser()
self.words = {}
self.profile = {}
self.stack = []
self.construct_language()
def exec_ast(self, c):
def try_run(tm,ks):
logging.debug("try_run: %s %s %s" % (tm,ks,self.stack[-2:]))
for k in ks:
# go through possible type set and try to match
if len(k) <= len(self.stack):
t = get_types(len(k))
if t == k:
ex_func(tm,t)
return True
else:
raise ValueError("Stack underflow. ",self.stack)
def ex_func(tm,t):
ww = tm+t
self.profile[ww].called()
logging.debug("exec: %s %s stack: %s" % (tm,t,self.stack))
t1 = time.time()
sp = []
for _ in range(self.words[tm][t].inputs):
sp.append(self.stack.pop())
logging.debug("afte: %s %s stack: %s" % (tm,t,self.stack))
r = self.words[tm][t].function(*sp)
if r:
self.stack.extend(r)
t2 = time.time()
self.profile[ww].time += t2-t1
def get_types(i):
return ''.join([x[0] for x in self.stack[-i:]])
def do_op(op):
if len(self.stack)>1 and self.stack[-1][1] == ':':
# variable definition
self.stack.pop()
x = [self.stack[-1]]
logging.debug(x)
self.add_word(op, '', 0)(lambda: x)
logging.debug("set: %s %s" % (op,self.stack[-1]))
elif op in self.words:
# found token in wordlist
ks = self.words[op].keys()
if ks[0]: # word has typed parameters
if not try_run(op,ks):
# no match found, try and coerce the types to fit
if op in "+-|&^": # coerce only for these ops
self.stack[-1],self.stack[-2] = \
self._coerce(self.stack[-1],self.stack[-2])
ex_func(op,get_types(2))
elif op in "*/%<>=?": # don't care about order
self.stack[-1],self.stack[-2] = \
self.stack[-2],self.stack[-1]
ex_func(op,get_types(2))
else:
raise ValueError("Word %s not found for types %s."
% (op,get_types(2)))
else: # words with no types
ex_func(op,'')
else:
raise ValueError("Function not found: %s" % (i[1]))
logging.debug("exec_ast(): %s %s" % (self._quote(c)[0][1], self.stack))
for x,i in enumerate(c):
if i[0] == "w":
do_op(i[1])
else:
logging.debug("append: %s" % repr(i))
self.stack.append(i)
def compile(self, p):
self.exec_ast(self.parser.do(p))
return self.stack
def _new_word(self, f,n,t,inp):
self.profile[n+t] = FunctionProfile()
if n in self.words:
self.words[n][t] = Word(f,n,t,inp)
else:
self.words[n] = {t:Word(f,n,t,inp)}
def add_word(self, n, t, inp):
def dbg(f):
logging.debug("new word: %s %s %s" % (f,n,t))
return f
return lambda f: self._new_word(dbg(f),n,t,inp)
def construct_language(self):
self.add_word('+', 'ii', 2)(lambda a,b: [('i', a[1]+b[1])])
self.add_word('+', 'aa', 2)(lambda a,b: [('a', b[1]+a[1])])
self.add_word('+', 'ss', 2)(lambda a,b: [('s', b[1]+a[1])])
self.add_word('+', 'bb', 2)(lambda a,b: [('b', b[1]+[('w',' ')]+a[1])])
self.add_word('-', 'ii', 2)(lambda a,b: [('i', b[1]-a[1])])
self.add_word('-', 'aa', 2)(lambda a,b: [('a', [x for x in b[1]
if x not in a[1]])])
self.add_word('*', 'ii', 2)(lambda a,b: [('i', a[1]*b[1])])
@self.add_word('*', 'bi', 2)
def b_i_mul(a,b):
for _ in range(a[1]):
self.exec_ast(b[1])
self.add_word('*', 'ai', 2)(lambda a,b: [('a', b[1]*a[1])])
@self.add_word('*', 'as', 2)
def a_s_mul(a,b):
x = [self._quote([c])[0][1] for c in b[1]]
return [('s', a[1].join(x))]
@self.add_word('*', 'aa', 2)
def a_a_mul(a,b):
c = []
for x in range(len(b[1])-1):
c.extend([b[1][x]]+a[1])
return [('a',c+[b[1][-1]])]
self.add_word('*', 'ss', 2)(lambda a,b: [('s', a[1].join(list(b[1])))])
self.add_word('*', 'is', 2)(lambda a,b: [('s', b[1]*a[1])])
@self.add_word('*', 'ab', 2)
def a_b_mul(a,b):
self.stack.extend(b[1])
for _ in range(len(b[1])-1):
self.exec_ast(a[1])
@self.add_word('/', 'ii', 2)
def i_i_each(a,b): return [('i', b[1]/a[1])]
@self.add_word('/', 'aa', 2)
def a_a_each(a,b):
suba, maia = a[1], b[1]
x,y,i = [],[],0
while i < len(maia):
if maia[i] == suba[0]:
if maia[i:i+len(suba)] == suba:
i+=len(suba)
y.append(('a',x))
x = []
continue
x.append(maia[i])
i+=1
if x: y.append(('a',x))
return [('a', y)]
@self.add_word('/', 'ai', 2)
def a_i_each(a,b):
return [('a', [('a',b[1][x:a[1]+x])
for x in range(0,len(b[1]),a[1])])]
@self.add_word('/', 'bb', 2)
def b_b_each(a,b):
x = []
while 1:
x.append(self.stack[-1])
self.exec_ast(a[1])
self.stack.append(self.stack[-1])
self.exec_ast(b[1])
if self.stack.pop()[1] != 1: break
self.stack.pop()
self.stack.append(('a',x))
@self.add_word('/', 'ab', 2)
def a_b_each(a,b):
return self.exec_ast([b,a]+[('w','%'),('w','~')])
@self.add_word('/', 'ss', 2)
def s_s_each(a,b): return [('a',[('s', x) for x in b[1].split(a[1])])]
@self.add_word('%', 'ii', 2)
def i_i_mod(a,b): return [('i', b[1]%a[1])]
@self.add_word('%', 'aa', 2)
def a_a_mod(a,b): raise ValueError("Unimplemented.")
@self.add_word('%', 'ai', 2)
def a_i_mod(a,b): return [('a', b[1][::a[1]])]
@self.add_word('%', 'ab', 2)
def a_b_mod(a,b):
self.stack.append(('w', '['))
for i in b[1]:
self.exec_ast([i]+a[1])
self.exec_ast([('w', ']')])
self.add_word('?', 'ii', 2)(lambda a,b: [('i', b[1]**a[1])])
@self.add_word('?', 'ia', 2)
def i_a_poww(a,b):
for i,j in enumerate(a[1]):
if b[1] == j[1]:
return [('i', i)]
return [('i', -1)]
@self.add_word('?', 'ab', 2)
def a_b_poww(a,b):
for i in b[1]:
self.exec_ast([i]+a[1])
x = self.stack.pop()
if x == ('i', 1):
self.stack.append(i)
break
self.add_word('<', 'ii', 2)(lambda a,b: [('i', 0 if a[1]<b[1] else 1)])
self.add_word('<', 'ai', 2)(lambda a,b:
[('a', [i for i in b[1] if i[1]<=a[1]])])
self.add_word('>', 'ii', 2)(lambda a,b: [('i', 0 if a[1]>b[1] else 1)])
self.add_word('>', 'ai', 2)(lambda a,b:
[('a', [i for i in b[1] if i[1]>a[1]])])
self.add_word('<', 'si', 2)(lambda a,b: [('s',b[1][a[1]:])])
self.add_word('=', 'ii', 2)(lambda a,b: [('i', 1 if a[1]==b[1] else 0)])
self.add_word('=', 'ss', 2)(lambda a,b: [('i', 1 if a[1]==b[1] else 0)])
self.add_word('=', 'ai', 2)(lambda a,b: [b[1][a[1]]] if abs(a[1])<len(b[1]) else None)
self.add_word('=', 'bi', 2)(lambda a,b: [('i', ord(self._quote([b])[0][1][1:-1][a[1]]))])
self.add_word('~', 'i', 1)(lambda a: [('i', ~a[1])])
self.add_word('~', 's', 1)(lambda a: self.exec_ast(self.parser.do(a[1])))
self.add_word('~', 'b', 1)(lambda a: self.exec_ast(a[1]))
self.add_word('~', 'a', 1)(lambda a: a[1])
self.add_word(',', 'i', 1)(lambda a: [('a', [('i', x) for x in range(a[1])])])
self.add_word(',', 'a', 1)(lambda a: [('i', len(a[1]))])
@self.add_word(',', 'ab', 2)
def a_b_comma(a,b):
self.stack.append(('w', '['))
for i in b[1]:
self.exec_ast([i]+a[1])
if self._true(self.stack.pop()):
self.stack.append(i)
self.exec_ast([('w', ']')])
self.add_word(')', 'i', 1)(lambda a: [('i', a[1]+1)])
self.add_word(')', 'a', 1)(lambda a: [('a', a[1][:-1])]+[('i', a[1][-1][1])])
self.add_word('(', 'i', 1)(lambda a: [('i', a[1]-1)])
self.add_word('(', 'a', 1)(lambda a: [('a', a[1][1:])]+[('i', a[1][0][1])])
self.add_word('!', 'i', 1)(lambda a: [('i',1-a[1])])
self.add_word('\\', '', 2)(lambda a,b: [a,b])
self.add_word('.', '', 1)(lambda a: [a,a])
self.add_word(';', '', 1)(lambda a: None)
self.add_word('@', '', 3)(lambda a,b,c: [b,a,c])
self.add_word('`', '', 1)(lambda a: self._quote([a]))
self.add_word('[', '', 0)(lambda: [('w','[')])
@self.add_word(']', '', 0)
def bracke():
l = []
logging.debug("%s" % self.stack)
while len(self.stack)>0 and self.stack[-1][1] != '[':
l.append(self.stack.pop())
if len(self.stack)>0 and self.stack[-1][1] == '[':
self.stack.pop()
logging.debug("bracke: %s" % l)
self.stack.append(('a', l[::-1]))
@self.add_word('p', '', 1)
def pputs(a): print self._quote(a[1])[0][1]
self.add_word(' ', '', 0)(lambda: None)
self.add_word(':', '', 0)(lambda: [('w',':')])
@self.add_word('do', 'b', 1)
def b_doo(a):
while True:
self.exec_ast(a[1])
if not self._true(self.stack.pop()): break
self.add_word('$', 'i', 1)(lambda a: [self.stack[-(a[1]+1)]])
self.add_word('$', 'a', 1)(lambda a: [('a', sorted(a[1]))])
self.add_word('$', 's', 1)(lambda a: [('s', sorted(list(a[1])))])
self.add_word('$', 'ab', 2)(lambda a,b: [a])
self.add_word('if', '', 3)(lambda a,b,c: [b] if self._true(c) else [a])
self.add_word('abs','i', 1)(lambda a: [('i', abs(a[1]))])
@self.add_word('zip','a',1)
def a_zip(i):
a = i[1]
artype = a[0][0]
l2 = len(a[0][1])
l1 = len(a)
b = []
for x in range(l2):
if artype == 'a': b.append([('a',[])])
else: b.append([('s',"")])
for y in range(l1):
if artype == 'a': b[x][0] = ('a', b[x][0][1]+[a[y][1][x]])
else: b[x][0] = ('s', b[x][0][1]+a[y][1][x])
return [('a', [j[0] for j in b])]
# 0 [] "" {} = false, everything else = true
def _false(self, a):
return a == ('i', 0) or a == ('a', []) or \
a == ('s', '') or a == ('b', [])
def _true(self, a):
return not self._false(a)
def _quote(self, a):
logging.debug("quote:"+repr(a))
def ss(i): return '\\"' if i == '"' else i # escape inner string
def ww(i):
#logging.debug(" ww:"+repr(i))
if i[0] == 'i': return "%d" % i[1]
if i[0] == 's': return '"' + ''.join(ss(t) for t in i[1]) + '"'
if i[0] == 'w': return i[1]
if i[0] == 'a': return "[" + ' '.join([ww(x) for x in i[1]]) + "]"
if i[0] == 'b': return '{' + ''.join([ww(x) for x in i[1]]) + '}'
return [('s', ' '.join([ww(x) for x in a]))]
def _coerce(self,a,b):
def _raise(a):
if a[0] == 'i': return ('a', [a])
if a[0] == 'a': return ('s', ' '.join([repr(x[1]) for x in a[1]]))
if a[0] == 's': return ('b', [('w',a[1])])
order = {'i':0, 'a':1, 's':2, 'b':3}
logging.debug("coerce: %s %s" % (a,b))
while a[0] != b[0]:
if order[a[0]] > order[b[0]]: b = _raise(b)
elif order[b[0]] > order[a[0]]: a = _raise(a)
return a,b
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment