From 599128e31f27654cba55693555f976518ea4636b Mon Sep 17 00:00:00 2001 From: Tim Vieira Date: Thu, 27 Jun 2013 14:39:12 -0400 Subject: [PATCH] First pass implementation of Jason's `trace` debugger. Fixed source line selection in ./debug Moved a few things around. compiler dumps anf by default (right beside the .plan.py). --- examples/geom.dyna | 2 +- examples/papa2.dyna | 3 +- src/Dyna/Backend/Python/Backend.hs | 6 +- src/Dyna/Backend/Python/Selftest.hs | 2 +- src/Dyna/Backend/Python/debug.py | 52 +++--- src/Dyna/Backend/Python/defn.py | 2 + src/Dyna/Backend/Python/interpreter.py | 22 ++- src/Dyna/Backend/Python/post/__init__.py | 2 +- src/Dyna/Backend/Python/post/draw_circuit.py | 178 ++++++++++++++++++- src/Dyna/Backend/Python/repl.py | 29 +-- src/Dyna/Backend/Python/term.py | 16 +- src/Dyna/Backend/Python/utils.py | 64 ++++++- 12 files changed, 287 insertions(+), 91 deletions(-) diff --git a/examples/geom.dyna b/examples/geom.dyna index 4e7c057..802b98c 100644 --- a/examples/geom.dyna +++ b/examples/geom.dyna @@ -1,2 +1,2 @@ a += 1. -a += a/2. +a += a / 2. diff --git a/examples/papa2.dyna b/examples/papa2.dyna index d081936..27f0400 100644 --- a/examples/papa2.dyna +++ b/examples/papa2.dyna @@ -2,7 +2,8 @@ % CKY-like parsing phrase(X,I,K, &t(X,TY)) max= phrase(Y,I,K,TY) * rewrite(X,Y). -phrase(X,I,K, &t(X,TY,TZ)) max= phrase(Y,I,J,TY) * phrase(Z,J,K,TZ) * rewrite(X,Y,Z). +phrase(X,I,K, &t(X,TY,TZ)) max= + phrase(Y,I,J,TY) * phrase(Z,J,K,TZ) * rewrite(X,Y,Z). goal(P) max= phrase("S", 0, length, P). diff --git a/src/Dyna/Backend/Python/Backend.hs b/src/Dyna/Backend/Python/Backend.hs index d6ea0f2..337f743 100644 --- a/src/Dyna/Backend/Python/Backend.hs +++ b/src/Dyna/Backend/Python/Backend.hs @@ -280,7 +280,7 @@ pdope_ _ (OPEmit h r i vs) = do -- A python map of variable name to value let varmap = brackets $ align $ fillPunct (comma <> space) $ - parens ("'nodes'" <> comma <> (encloseSep lbracket rbracket comma $ map (("d"<>).pretty) [0..ds-1])) + parens ("'nodes'" <> comma <> parens (hcat $ map (\x -> ("d" <> pretty x <> ",")) [0..ds-1])) : (map (\v -> let v' = pretty v in parens (dquotes v' <> comma <+> v')) vs) return $ "emit" <> tupled [ pretty h @@ -373,6 +373,9 @@ printQuery fh bc (f,a) rule vs cost dope = do driver :: BackendDriver PyDopeBS driver am um is bc qp pr fh = do + + hPutStrLn fh "from __future__ import division" + -- Parser resume state hPutStrLn fh "parser_state = \"\"\"" hPutStrLn fh $ show pr @@ -382,7 +385,6 @@ driver am um is bc qp pr fh = do $ M.toList am hPutStrLn fh "\"\"\"" hPutStrLn fh "" - hPutStrLn fh $ "queries = []" hPutStrLn fh $ "agg_decl = {}" hPutStrLn fh $ "updaters = []" diff --git a/src/Dyna/Backend/Python/Selftest.hs b/src/Dyna/Backend/Python/Selftest.hs index 4104b75..3d28e4d 100644 --- a/src/Dyna/Backend/Python/Selftest.hs +++ b/src/Dyna/Backend/Python/Selftest.hs @@ -77,7 +77,7 @@ mkExample name = -- will be broken. ;) test_End_To_End :: [Test] test_End_To_End = map mkExample - [ "simple", "equalities", "fib-limit", "dijkstra", "papa2", "matrixops" ] + [ "simple", "equalities", "fib-limit", "dijkstra", "papa2", "matrixops", "geom" ] test_REPL :: [Test] test_REPL = map (\n -> testProgramRuns n ("./test/repl/"++n) []) diff --git a/src/Dyna/Backend/Python/debug.py b/src/Dyna/Backend/Python/debug.py index 0759efc..9823e42 100644 --- a/src/Dyna/Backend/Python/debug.py +++ b/src/Dyna/Backend/Python/debug.py @@ -120,10 +120,17 @@ class Hypergraph(object): String of symbolic representation of ``x``, a variable or function, in this expresion graph. """ + if isinstance(x, Edge): + label = re.sub('@\d+$', '', x.label) if not x.body: # arity 0 - return x.label - return '%s(%s)' % (x.label, ', '.join(map(self.get_function, x.body))) + return label + + if not label[0].isalpha() and len(x.body) == 2: + [a,b] = map(self.get_function, x.body) + return '(%s %s %s)' % (a, label, b) + + return '%s(%s)' % (label, ', '.join(map(self.get_function, x.body))) else: if not self.incoming[x]: # input variable return x @@ -151,9 +158,10 @@ def isvar(x): def circuit(anf): - (agg, head, evals, unifs, result) = anf - g = Hypergraph() + + (g.source_lines, g.ruleix, g.aggregator, head, evals, unifs, result) = anf + for var, op, args in evals: g.edge(head=var, label=op, body=args) @@ -249,19 +257,17 @@ body { background: black; color: white; } @@ -302,24 +308,22 @@ function selectline(lineno) { print >> html, '
' with file(d + '/anf') as f: - anf = f.read() - - # Suppress this since we display ANF graphically instead. - # print >> html, '

ANF

' - # print >> html, '
\n%s\n
' % anf.strip() - - print >> html, '

Hyperedge templates

' - - linenos = re.findall(';; (.*?):(\d+):\d+-.*?:(\d+):\d+', anf) - rules = [circuit(x) for x in read_anf(anf)] + rules = [circuit(x) for x in read_anf(f.read())] - assert len(rules) == len(linenos), 'missing line number in ANF.' + # output map from source lines to rule index + print >> html, '' - for (i, ((_, lineno, _), g)) in enumerate(zip(linenos, rules)): + for g in rules: sty = graph_styles(g) - svg = g.render(dynafile + '.d/rule-%s' % i, sty) - print >> html, '
%s
' % (lineno, svg) + svg = g.render(dynafile + '.d/rule-%s' % g.ruleix, sty) + print >> html, '
%s
' % (g.ruleix, svg) # find "update plans" -- every term (edge) in a rule must have code to # handle an update to it's value. diff --git a/src/Dyna/Backend/Python/defn.py b/src/Dyna/Backend/Python/defn.py index cbcd7c5..1859ee3 100644 --- a/src/Dyna/Backend/Python/defn.py +++ b/src/Dyna/Backend/Python/defn.py @@ -1,3 +1,5 @@ +from __future__ import division + # TODO: codegen should produce specialized Term with inc/dec methods baked # in. This seems nicer than having a separate aggregator object. diff --git a/src/Dyna/Backend/Python/interpreter.py b/src/Dyna/Backend/Python/interpreter.py index 2d7d5a3..5eb2aec 100644 --- a/src/Dyna/Backend/Python/interpreter.py +++ b/src/Dyna/Backend/Python/interpreter.py @@ -49,6 +49,8 @@ TODO - sheebang + - loader for importing rules + - Errors: - Should errors be maintained by dyna? I guess that's an (implicit?) program @@ -196,7 +198,7 @@ import load, post from chart import Chart, Term, _repr from defn import aggregator from utils import ip, red, green, blue, magenta, yellow, parse_attrs, \ - ddict, dynac + ddict, dynac, read_anf from prioritydict import prioritydict from config import dotdynadir @@ -312,7 +314,9 @@ class Interpreter(object): assert self.agg_name[fn] == agg, (fn, self.agg_name[fn], agg) - def dump_charts(self, out=sys.stdout): + def dump_charts(self, out=None): + if out is None: + out = sys.stdout print >> out print >> out, 'Solution' print >> out, '========' @@ -333,7 +337,9 @@ class Interpreter(object): print >> out, y self.dump_errors(out) - def dump_errors(self, out=sys.stdout): + def dump_errors(self, out=None): + if out is None: + out = sys.stdout # We only dump the error chart if it's non empty. if not self.error: return @@ -559,8 +565,9 @@ class Interpreter(object): A rule is bad if the compiler rejects it or it's initializer fails. """ assert os.path.exists(filename) +# assert os.path.exists(filename + '.anf') - env = imp.load_source('module.name', filename) + env = imp.load_source('dynamically_loaded_module', filename) for k,v in [('chart', self.chart), ('build', self.build), @@ -609,6 +616,11 @@ class Interpreter(object): for e in emits: self.emit(*e, delete=False) + if path(filename + '.anf').exists(): # XXX: should have codegen provide this in plan.py + with file(filename + '.anf') as f: + for anf in read_anf(f.read()): + self.rules[anf.ruleix].anf = anf + return self.go() def dynac_code(self, code): @@ -665,7 +677,7 @@ def main(): help='`source` specifies output of the compiler instead of dyna source code.') parser.add_argument('-o', '--output', dest='output', type=argparse.FileType('wb'), - help='Output chart.') + help='Write solution to file.') parser.add_argument('--post-process', nargs='*', help='run post-processor.') parser.add_argument('--load', nargs='*', diff --git a/src/Dyna/Backend/Python/post/__init__.py b/src/Dyna/Backend/Python/post/__init__.py index 3168473..68121c7 100644 --- a/src/Dyna/Backend/Python/post/__init__.py +++ b/src/Dyna/Backend/Python/post/__init__.py @@ -6,6 +6,6 @@ from dump_solution import dump_solution def run(interp, line): - [(name, args)] = _re.findall('([a-z][a-zA-Z_0-9]*)\((.*)\)$', line) + [(name, args)] = _re.findall('([a-z][a-zA-Z_0-9]*)\((.*)\)$', line.strip()) m = globals()[name](interp) eval('m.main(%s)' % args) diff --git a/src/Dyna/Backend/Python/post/draw_circuit.py b/src/Dyna/Backend/Python/post/draw_circuit.py index a6884c4..d249fc3 100644 --- a/src/Dyna/Backend/Python/post/draw_circuit.py +++ b/src/Dyna/Backend/Python/post/draw_circuit.py @@ -1,13 +1,15 @@ +# -*- coding: utf-8 -*- + import webbrowser from debug import Hypergraph from cStringIO import StringIO - +from utils import lexer, subst def circuit(edges): # create hypergraph object g = Hypergraph() for e in edges: - head, label, body = e + head, label, body, _vs = e g.edge(str(head), str(label), map(str, body)) return g @@ -17,10 +19,11 @@ def infer_edges(interp): # Use rule initializers to find all active hyperedges in the current Chart. def _emit(item, _, ruleix, variables): - b = dict(variables)['nodes'] + b = list(dict(variables)['nodes']) b.sort() - b = tuple(b) - edges.add((item, ruleix, b)) + # variable values not needed to name the edge, but adding them doesn't + # change anything. + edges.add((item, ruleix, tuple(b), variables)) for r in interp.rules.values(): r.init(emit=_emit) @@ -37,6 +40,7 @@ class draw_circuit(object): self.interp = interp def main(self, outfile): + global interp interp = self.interp es = infer_edges(interp) @@ -73,4 +77,166 @@ class draw_circuit(object): print >> f, '' - webbrowser.open(f.name) +# webbrowser.open(f.name) + + # group edges by head then ruleindex + global groups + groups = groupby(lambda x: x[0], es) + for a in groups: + groups[a] = groupby(lambda x: x[1], groups[a]) + + for head in groups: + dig(head, set()) + + +from collections import defaultdict +def groupby(key, data): + g = defaultdict(list) + for x in data: + g[key(x)].append(x) + return dict(g) + + +groups = None + + + +def dig(head, visited, indent='', first=False, last=False): + + if last and first: + xxx = '└─ ' + elif last: + xxx = '└─ ' + elif first: + xxx = '├─ ' + else: + xxx = '├─ ' + + if head in visited: + print indent[:-4] + xxx + red % '*CYCLE*' + return + + if head not in groups: + return + visited.add(head) + + print indent[:-4] + xxx + '%s = %s' % (yellow % head, _repr(head.value)) + + if last: + indent = indent[:-4] + ' ' + else: + indent = indent + ' ' + + for ruleix in groups[head]: + + contrib = groups[head][ruleix] + for (i, (_, _, body, vs)) in enumerate(contrib): + + rule = interp.rules[ruleix] + + # TODO: nwf remove comments from rule source + crux = Crux(head, rule, body, dict(vs)) + + for line in crux.format(): + print indent + line + + print indent + + for i, x in enumerate(body): + dig(x, visited, indent=indent + ' │ ', first=i==0, last=i==len(body)-1) + + print indent[:-2] + + +""" +def branch(*xs): + + for i, x in enumerate(xs): + first = i == 0 + last = i == len(contrib)-1 + if last and first: + xxx = '└─ ' + elif last: + xxx = '└─ ' + elif first: + xxx = '├─ ' + else: + xxx = '├─ ' +""" + + + +class Crux(object): + + def __init__(self, head, rule, body, vs): + self.head = head + self.rule = rule + self.body = body + self.vs = vs + self.graph = debug.circuit(rule.anf) + + def values(self, x): + if x in self.vs: + return _repr(self.vs[x]) + try: + return _repr(eval(x.replace('\\"', '"'))) + except (SyntaxError, NameError): + return x + + def format(self): + rule = self.rule + src = rule.src.replace('\n',' ').strip() + graph = self.graph + user_vars = dict(defn.user_vars(self.vs.items())) + side = [' side: ' + self.get_function(x) for x in graph.outputs if x != rule.anf.result and x != rule.anf.head] + return [('%s %s' % (red % rule.anf.agg, self.values(rule.anf.result))), + (green % (' # %s' % src)), + (green % (' # %s' % subst(src, user_vars))), + (green % (' # %s' % drepr(user_vars))), + (' head: %s' % self.get_function(rule.anf.head)), + (' result: %s' % self.get_function(rule.anf.result))] \ + + side + + def get_function(self, x): + """ + String of symbolic representation of ``x``, a variable or function, in + this expresion graph. + """ + g = self.graph + if isinstance(x, debug.Edge): + label = re.sub('@\d+$', '', x.label) + label = re.sub('^& ', '&', label) + + if label == '=': + [b] = x.body + return self.get_function(b) + + if not x.body: # arity 0 + return label + + fn_args = [self.get_function(y) for y in x.body] + if not label.isalpha() and not label.startswith('& ') and len(fn_args) == 2: # infix + [a,b] = fn_args + return '(%s %s %s)' % (a, label, b) + return '%s(%s)' % (label, ', '.join(fn_args)) + else: + if not g.incoming[x]: # input variable + return self.values(x) + if len(g.incoming[x]) > 1: + return 'UNIF ' + ' === '.join(self.get_function(e) + (red % '=%s' % self.values(e.head)) for e in g.incoming[x]) + [e] = g.incoming[x] + + if e.label == '=': + return self.get_function(e) + + if e.label.startswith('&'): + return self.get_function(e) + + return self.get_function(e) + (red % '=%s' % self.values(x)) + + +import re +from utils import yellow, green, red +from defn import drepr +from term import _repr +import debug, defn diff --git a/src/Dyna/Backend/Python/repl.py b/src/Dyna/Backend/Python/repl.py index d222eed..3af4120 100644 --- a/src/Dyna/Backend/Python/repl.py +++ b/src/Dyna/Backend/Python/repl.py @@ -3,7 +3,7 @@ TODO: unsubscribe TODO: should probably remove the new rule after we get the results. -TODO: probably should show "changed" +TODO: subscriptions probably should only show "changes" TODO: queries are all maintained... should probably toss out the query rule. If users want queries to be kept up-to-date user should subscribe instead. @@ -11,12 +11,13 @@ users want queries to be kept up-to-date user should subscribe instead. TODO: help should print call signature of loads and post-processors in addition to help. +TODO: $include load rules from a file. """ import re, os, cmd, readline import debug, interpreter -from utils import ip +from utils import ip, lexer, subst from errors import DynaCompilerError, DynaInitializerException from chart import _repr from config import dotdynadir @@ -30,30 +31,6 @@ from term import _repr from defn import drepr -def lexer(term): - return re.findall('"[^"]*"' # string - '|[a-z][a-zA-Z_0-9]*' # functor - '|[A-Z][a-zA-Z0-9_]*' # variable - '|[(), ]' # parens and comma - '|[^(), ]+', term) # everything else - - -def subst(term, v): - """ - >>> subst('f("asdf",*g(1,X, Y), X+1)', {'X': 1234}) - 'f("asdf",*g(1,1234, Y), 1234+1)' - - >>> subst('f("asdf",*g(1,X, Y), XX+1)', {'X': 1234}) - 'f("asdf",*g(1,1234, Y), XX+1)' - - >>> subst('f("asdf",*g(1,uX, Y), X_+1)', {'X': 1234}) - 'f("asdf",*g(1,uX, Y), X_+1)' - - """ - assert isinstance(v, dict) - return ''.join((_repr(v[x]) if x in v else x) for x in lexer(term)) - - class REPL(cmd.Cmd, object): def __init__(self, interp, hist=dotdynadir / 'dyna.hist'): diff --git a/src/Dyna/Backend/Python/term.py b/src/Dyna/Backend/Python/term.py index 6efaf4d..f03d600 100644 --- a/src/Dyna/Backend/Python/term.py +++ b/src/Dyna/Backend/Python/term.py @@ -1,5 +1,5 @@ from errors import notimplemented - +from utils import _repr # TODO: codegen should output a derived Term instance for each functor class Term(object): @@ -45,20 +45,6 @@ class Term(object): # return Term(self.fn, tuple(x if isconst(x) else x.subst(v) for x in self.args)) -def _repr(x): - if x is True: - return 'true' - elif x is False: - return 'false' - elif x is None: - return 'null' - elif isinstance(x, basestring): - # dyna doesn't accept single-quoted strings - return '"%s"' % x.replace('"', r'\"') - else: - return repr(x) - - def isconst(x): return not isinstance(x, (Variable, Term)) diff --git a/src/Dyna/Backend/Python/utils.py b/src/Dyna/Backend/Python/utils.py index c678b2d..7e6d0cd 100644 --- a/src/Dyna/Backend/Python/utils.py +++ b/src/Dyna/Backend/Python/utils.py @@ -1,9 +1,24 @@ import re, sys +from path import path from subprocess import Popen, PIPE from IPython.frontend.terminal.embed import InteractiveShellEmbed from config import dynahome, dotdynadir import signal from contextlib import contextmanager +from collections import namedtuple + +def _repr(x): + if x is True: + return 'true' + elif x is False: + return 'false' + elif x is None: + return 'null' + elif isinstance(x, basestring): + # dyna doesn't accept single-quoted strings + return '"%s"' % x.replace('"', r'\"') + else: + return repr(x) # interactive IPython shell @@ -20,7 +35,9 @@ def dynac(f, out): ``DynaCompilerError`` on failure. """ from errors import DynaCompilerError + p = Popen(['%s/dist/build/dyna/dyna' % dynahome, + '--dump-anf=' + out + '.anf', # timv: don't like this filename... '-B', 'python', '-o', out, f], stdout=PIPE, stderr=PIPE) stdout, stderr = p.communicate() if p.returncode: @@ -28,6 +45,31 @@ def dynac(f, out): raise DynaCompilerError(stderr) +def lexer(term): + return re.findall('"[^"]*"' # string + '|[a-z][a-zA-Z_0-9]*' # functor + '|[A-Z][a-zA-Z0-9_]*' # variable + '|[(), ]+' # parens and comma + '|[^(), ]+', term) # everything else + + +def subst(term, v): + """ + >>> subst('f("asdf",*g(1,X, Y), X+1)', {'X': 1234}) + 'f("asdf",*g(1,1234, Y), 1234+1)' + + >>> subst('f("asdf",*g(1,X, Y), XX+1)', {'X': 1234}) + 'f("asdf",*g(1,1234, Y), XX+1)' + + >>> subst('f("asdf",*g(1,uX, Y), X_+1)', {'X': 1234}) + 'f("asdf",*g(1,uX, Y), X_+1)' + + """ + assert isinstance(v, dict) + return ''.join((_repr(v[x]) if x in v else x) for x in lexer(term)) + + + @contextmanager def interrupt_after(): @@ -90,9 +132,10 @@ def parse_sexpr(e): return es -def read_anf(e): - x = parse_sexpr(e) +class ANF(namedtuple('ANF', 'lines ruleix agg head evals unifs result')): + pass +def read_anf(e): def _g(x): # return [(var, val[0], val[1:]) for var, val in x] for var, val in x: @@ -103,12 +146,15 @@ def read_anf(e): def g(x): return list(_g(x)) - for (agg, head, evals, unifs, [_,result]) in x: - yield (agg, - head, - g(evals[1:]), - g(unifs[1:]), - result) + for lines, ruleix, anf in re.findall('^;; (.*)\n;; index (\d+)\n(\([\w\W]+?)\n(?:\n|$)', e, re.MULTILINE): + for (agg, head, evals, unifs, [_,result]) in parse_sexpr(anf): + yield ANF(lines, + int(ruleix), + agg, + head, + g(evals[1:]), + g(unifs[1:]), + result) def parse_attrs(fn): @@ -136,7 +182,7 @@ def rule_source(span, src=None): if len(rlines) > 1: s = rlines[0][bc-1:] m = rlines[1:-1] - e = rlines[-1][:ec] + e = rlines[-1][:ec-1] return s + ''.join(m) + e else: -- 2.50.1