From 8a2853d83efd616d2abaf5a0cd10bc27b38a511b Mon Sep 17 00:00:00 2001 From: Tim Vieira Date: Mon, 1 Jul 2013 00:46:35 -0400 Subject: [PATCH] Many changes * changed repl prompt * commented out failed attempt at providing 'for X in [1,2,3]' * hid developer tools from repl. * trace: - fixed cycle detection - terser information printed for each edge. item => value | += val1 | | instantiated rule with subexpressions and variable values shown | inline. | | RECURSE on items in rule. | | += val2 - changed color coding. - documentation, `> help trace` * No more barfing on empty input to trace, query, vquery. --- examples/expected/lists.py.out | 2 +- src/Dyna/Backend/Python/Backend.hs | 33 +++ src/Dyna/Backend/Python/interpreter.py | 85 +++----- src/Dyna/Backend/Python/post/trace.py | 61 ++++-- src/Dyna/Backend/Python/repl.py | 270 ++++++++++++++++++------- src/Dyna/Backend/Python/term.py | 12 ++ src/Dyna/Backend/Python/utils.py | 6 +- 7 files changed, 315 insertions(+), 154 deletions(-) diff --git a/examples/expected/lists.py.out b/examples/expected/lists.py.out index a6bb6ca..e5a6168 100644 --- a/examples/expected/lists.py.out +++ b/examples/expected/lists.py.out @@ -9,5 +9,5 @@ f([1, 2]) => true. goal/1 ====== -goal([2]) := true +goal([2]) => true. diff --git a/src/Dyna/Backend/Python/Backend.hs b/src/Dyna/Backend/Python/Backend.hs index 8d697d9..8645c6b 100644 --- a/src/Dyna/Backend/Python/Backend.hs +++ b/src/Dyna/Backend/Python/Backend.hs @@ -119,6 +119,28 @@ builtins (f,is,o) = case () of [(x^.mv_var, nuniv)] _ -> Left True + {- + -- XXX Argh, same as above. + _ | f == "in" + -> case is of + [x,y] | isFree x && isGround y + -> let + call _ vs = "iter" <> (parens $ sepBy comma $ mpv vs) <> colon -- for some reason on colon get put at the end of this line. + cdop = [OPIter x [y] "iter" DetNon (Just $ PDBS call)] + cmod = [(x^.mv_var, nuniv)] + in if isFree o + then Right $ BAct (OPWrap (o^.mv_var) [] "true" : cdop) + ((o^.mv_var, nuniv) : cmod) + else if isGround o + then let _chk = "_chk" + in Right $ BAct ( OPWrap _chk [] "true" + : OPCheq _chk (o^.mv_var) + : cdop) + cmod + else Left True + _ -> Left True + -} + _ | MA.isJust (constants (f,length is)) -> Left True _ -> Left False @@ -155,6 +177,8 @@ constants = go go ("int", _) = Just $ PDBS $ call "int" [] go ("pycall", _) = Just $ PDBS $ call "pycall" [] +-- go ("in",2) = Just $ PDBS $ call " in " [] + go ("<=",2) = Just $ PDBS $ infixOp "<=" go ("<",2) = Just $ PDBS $ infixOp "<" go ("=",2) = Just $ PDBS $ infixOp "==" @@ -249,6 +273,15 @@ pdope_ _ (OPIter v vs _ Det (Just (PDBS c))) = return $ pretty (v^.mv_var) <+> equals <+> c v vs +pdope_ _ (OPIter v vs _ DetNon (Just (PDBS c))) = do + i <- incState + return $ "for" <+> "d" <> pretty i + <> comma + <> piterate vs + <> comma + <> (ground2underscore v) + <+> "in" <+> c v vs + pdope_ _ (OPIter v vs f d (Just (PDBS c))) = dynacPanic $ "Unexpected determinism flag (at python code gen):" <+> pretty v diff --git a/src/Dyna/Backend/Python/interpreter.py b/src/Dyna/Backend/Python/interpreter.py index dace1f1..9ef289e 100644 --- a/src/Dyna/Backend/Python/interpreter.py +++ b/src/Dyna/Backend/Python/interpreter.py @@ -135,7 +135,7 @@ from utils import ip, red, green, blue, magenta, yellow, parse_attrs, \ from prioritydict import prioritydict from config import dotdynadir -from errors import crash_handler, DynaInitializerException, AggregatorError +from errors import crash_handler, DynaInitializerException, AggregatorError, DynaCompilerError class Rule(object): @@ -161,10 +161,6 @@ class foo(dict): self.agg_name = agg_name super(foo, self).__init__() def __missing__(self, fn): - - if fn == 'contains/2': - return Contains() - arity = int(fn.split('/')[-1]) self[fn] = c = Chart(fn, arity, self.agg_name[fn]) return c @@ -174,38 +170,6 @@ def none(): return None -class Contains(object): - - def __init__(self): - self.name = 'contains' - self.arity = 2 - - def __repr__(self): - return 'contains/2' - - def __getitem__(self, s): - assert len(s) == self.arity + 1, \ - 'Chart %r: item width mismatch: arity %s, item %s' % (self.name, self.arity, len(s)) - [x, xs], val = s[:-1], s[-1] - #assert val is True - if isinstance(x, slice): - assert not isinstance(xs, slice) - for a in xs.tolist(): - term = Term('contains/2', (a, xs)) - term.value = True - yield term, term.args, term.value - - else: - # all bound membership test - assert not isinstance(x, slice) and not isinstance(xs, slice) - term = Term('contains/2', (x, xs)) - term.value = (x in xs.tolist()) - yield term, term.args, term.value - - def insert(self, args): - assert False - - class Interpreter(object): def __init__(self): @@ -569,6 +533,7 @@ class Interpreter(object): self.files.append(filename) out = self.tmp / filename.read_hexhash('sha1') + '.plan.py' +# out = filename + '.plan.py' dynac(filename, out) self.files.append(out) @@ -628,8 +593,8 @@ def main(): help='run post-processor.') parser.add_argument('--load', nargs='*', help='run loaders.') - parser.add_argument('--profile', action='store_true', - help='run profiler.') +# parser.add_argument('--profile', action='store_true', +# help='run profiler.') args = parser.parse_args() @@ -658,25 +623,35 @@ def main(): else: #plan = args.source + '.plan.py' #interp.dynac(args.source, plan) - plan = interp.dynac(args.source) - - if args.profile: - # When profiling, its common practice to disable the garbage collector. - import gc - gc.disable() - from cProfile import Profile - p = Profile() - p.runctx('interp.do(plan)', globals(), locals()) - p.dump_stats('prof') - - interp.dump_charts() + try: + plan = interp.dynac(args.source) + except DynaCompilerError as e: + print e + exit(1) + +# if args.profile: +# # When profiling, its common practice to disable the garbage collector. +# import gc +# gc.disable() +# +# from cProfile import Profile +# p = Profile() +# p.runctx('interp.do(plan)', globals(), locals()) +# p.dump_stats('prof') +# +# interp.dump_charts() +# +# os.system('gprof2dot.py -f pstats prof | dot -Tsvg -o prof.svg && eog prof.svg &') +# os.system('pkill snakeviz; snakeviz prof &') +# return - os.system('gprof2dot.py -f pstats prof | dot -Tsvg -o prof.svg && eog prof.svg &') - os.system('pkill snakeviz; snakeviz prof &') - return + try: + interp.do(plan) + except DynaInitializerException as e: + print e + exit(1) - interp.do(plan) interp.dump_charts(args.output) # should be a post-processor if args.load: diff --git a/src/Dyna/Backend/Python/post/trace.py b/src/Dyna/Backend/Python/post/trace.py index 2bcdcfc..51029af 100644 --- a/src/Dyna/Backend/Python/post/trace.py +++ b/src/Dyna/Backend/Python/post/trace.py @@ -7,7 +7,7 @@ TODO: shared substructure. """ import re -from utils import yellow, green, red, _repr, drepr +from utils import yellow, green, cyan, red, _repr, drepr import debug, defn from cStringIO import StringIO from utils import lexer, subst @@ -28,7 +28,7 @@ class trace(object): tracer = Tracer(self.interp) for item in tracer.items: print - print tracer(item) + tracer(item) class Tracer(object): @@ -46,7 +46,7 @@ class Tracer(object): if item not in self.items: print print 'no trace for', item - print '\n'.join(dig(item, set(), self.items, self.interp)) + print '\n'.join(dig(item, set(), tuple(), self.items, self.interp)) def groupby(key, data): @@ -56,10 +56,13 @@ def groupby(key, data): return dict(g) -def dig(head, visited, groups, interp): +def dig(head, visited, tail, groups, interp): + + if head in tail: + return [yellow % head + ': ' + red % '*cycle*'] if head in visited: - return [red % '*CYCLE*'] + return [yellow % head + ': ' + red % 'shared structure see above'] if head not in groups: return [] @@ -72,14 +75,14 @@ def dig(head, visited, groups, interp): for (_, _, body, vs) in groups[head][ruleix]: crux = Crux(head, interp.rules[ruleix], body, dict(vs)) - block = branch([dig(x, visited, groups, interp) for x in body]) + block = branch([dig(x, visited, tail + (head,), groups, interp) for x in body]) if block: contribs.append(crux.format() + ['|'] + block) else: contribs.append(crux.format()) - return ['%s = %s' % (yellow % head, _repr(head.value))] \ + return ['%s => %s' % (yellow % head, cyan % _repr(head.value))] \ + ['|'] \ + branch(contribs) + [''] @@ -125,16 +128,31 @@ class Crux(object): def format(self): rule = self.rule - src = rule.src.replace('\n',' ').strip() + #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 where %s' % (subst(src, user_vars), drepr(user_vars)))), - ('head: %s' % self.get_function(rule.anf.head)), - ('result: %s' % self.get_function(rule.anf.result))] \ - + side + #user_vars = dict(defn.user_vars(self.vs.items())) + + side = [self.get_function(x) for x in graph.outputs if x != rule.anf.result and x != rule.anf.head] + + explode = ('%s %s %s' % (self.get_function(rule.anf.head)[1:], # drop quote on head + green % rule.anf.agg, + self.get_function(rule.anf.result))) + + if side: + side = ' ' + ', '.join('%s %s' % ('for', x,) for x in side) + '.' + explode += ',' + else: + explode += '.' + + lines = ['%s %s' % (green % rule.anf.agg, self.values(rule.anf.result)), + '', + explode] + + if side: + lines.append(side) + + return lines + def get_function(self, x): """ @@ -154,16 +172,19 @@ class Crux(object): 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 + 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 + if not g.incoming[x]: # input + if re.match('u[A-Z].*', x): # user variable + return x[1:] + (cyan % '=%s' % self.values(x)) return self.values(x) + if len(g.incoming[x]) > 1: - return 'UNIFICATION ' + ' === '.join(self.get_function(e) + (red % '=%s' % self.values(e.head)) for e in g.incoming[x]) + return ' = '.join('(%s%s)' % (self.get_function(e), (cyan % '=%s' % self.values(e.head))) for e in g.incoming[x]) [e] = g.incoming[x] if e.label == '=': @@ -172,4 +193,4 @@ class Crux(object): if e.label.startswith('&'): return self.get_function(e) - return self.get_function(e) + (red % '=%s' % self.values(x)) + return self.get_function(e) + (cyan % '=%s' % self.values(x)) diff --git a/src/Dyna/Backend/Python/repl.py b/src/Dyna/Backend/Python/repl.py index 0d1debb..2b47573 100644 --- a/src/Dyna/Backend/Python/repl.py +++ b/src/Dyna/Backend/Python/repl.py @@ -40,7 +40,7 @@ class REPL(cmd.Cmd, object): @property def prompt(self): - return ':- ' + return '> ' def do_rules(self, _): """ @@ -52,11 +52,11 @@ class REPL(cmd.Cmd, object): """ Retract rule from program by rule index. - :- a += 1. - :- b += 1. - :- c += a*b. + > a += 1. + > b += 1. + > c += a*b. - :- rules + > rules Rules ===== @@ -64,12 +64,12 @@ class REPL(cmd.Cmd, object): 1: b += 1. 2: c += a * b. - :- retract_rule 0 + > retract_rule 0 This removes rule 0 from the program. Now, let's inspect the changes to the solution. - :- sol + > sol Solution ======== @@ -112,26 +112,26 @@ class REPL(cmd.Cmd, object): """Do nothing on empty input line""" pass - def do_ip(self, _): - """ - Development tool. Jump into an interactive python shell. - """ - ip() - - def do_debug(self, line): - """ - Development tool. Used for view Dyna's intermediate representations. - """ - import debug - with file(dotdynadir / 'repl-debug-line.dyna', 'wb') as f: - f.write(line) - debug.main(f.name) +# def do_ip(self, _): +# """ +# Development tool. Jump into an interactive python shell. +# """ +# ip() + +# def do_debug(self, line): +# """ +# Development tool. Used for view Dyna's intermediate representations. +# """ +# import debug +# with file(dotdynadir / 'repl-debug-line.dyna', 'wb') as f: +# f.write(line) +# debug.main(f.name) def do_run(self, filename): """ Load dyna rules from `filename`. - :- run examples/papa.dyna + > run examples/papa.dyna """ try: @@ -142,6 +142,11 @@ class REPL(cmd.Cmd, object): self._changed(changed) def _query(self, q): + + if not q.strip(): + print 'No query specified. Type `help query` for usage.' + return + if q.endswith('.'): print "Queries don't end with a dot." return @@ -186,23 +191,26 @@ class REPL(cmd.Cmd, object): Consider the following example; - :- f(1) := 1. - :- f(2) := 4. + > f(1) := 1. + > f(2) := 4. There a few versions of query: - `vquery` shows variable bindings - :- vquery f(X) + > vquery f(X) 1 where {X=1} 4 where {X=1} - `query` shows variable bindings applied to query - :- query f(X) + > query f(X) 1 =* f(1) 4 =* f(2) + - `trace` is an introspection tool for visualizing the derivation of an + item and its value. Type `help trace` for more information. + """ results = self._query(q) if results is None: @@ -243,21 +251,21 @@ class REPL(cmd.Cmd, object): for x, v in sorted(changed.items()): print '%s => %s.' % (x, _repr(v)) - def _changed_subscriptions(self, changed): - - # TODO: this doesn't show changes - it redumps everything. - - if not changed: - return - for x, _ in sorted(changed.items()): - if x.fn == '$subscribed/2': - [i, q] = x.args - if x.value: - print '%s: %s' % (i, q) - for result in x.value: - print ' ', _repr(result.value), 'where', drepr(dict(result.variables)) - print - self.interp.dump_errors() +# def _changed_subscriptions(self, changed): +# +# # TODO: this doesn't show changes - it redumps everything. +# +# if not changed: +# return +# for x, _ in sorted(changed.items()): +# if x.fn == '$subscribed/2': +# [i, q] = x.args +# if x.value: +# print '%s: %s' % (i, q) +# for result in x.value: +# print ' ', _repr(result.value), 'where', drepr(dict(result.variables)) +# print +# self.interp.dump_errors() def cmdloop(self, _=None): try: @@ -270,42 +278,42 @@ class REPL(cmd.Cmd, object): finally: readline.write_history_file(self.hist) - def do_subscribe(self, line): - """ - Establish a subscription to the results of a query. - - For example, - - :- subscribe f(X,X) - :- f(1,1) := 1. f(1,2) := 2. f(2,2) := 3. - Changes - ======= - f(X,X): - 1 where {X=1} - - To view all subscriptions: - - :- subscriptions - f(X): - 1 where {X=1} - 2 where {X=2} - - """ - if line.endswith('.'): - print "Queries don't end with a dot." - return - # subscriptions are maintained via forward chaining. - query = '$subscribed(%s, %s) dict= %s.' % (self.lineno, _repr(line), line) - self.default(query) - - def do_subscriptions(self, _): - "List subscriptions. See subscribe." - for (_, [_, q], results) in self.interp.chart['$subscribed/2'][:,:,:]: - if results: - print q - for result in results: - print ' ', _repr(result.value), 'where', drepr(dict(result.variables)) - print +# def do_subscribe(self, line): +# """ +# Establish a subscription to the results of a query. +# +# For example, +# +# : subscribe f(X,X) +# :- f(1,1) := 1. f(1,2) := 2. f(2,2) := 3. +# Changes +# ======= +# f(X,X): +# 1 where {X=1} +# +# To view all subscriptions: +# +# :- subscriptions +# f(X): +# 1 where {X=1} +# 2 where {X=2} +# +# """ +# if line.endswith('.'): +# print "Queries don't end with a dot." +# return +# # subscriptions are maintained via forward chaining. +# query = '$subscribed(%s, %s) dict= %s.' % (self.lineno, _repr(line), line) +# self.default(query) +# +# def do_subscriptions(self, _): +# "List subscriptions. See subscribe." +# for (_, [_, q], results) in self.interp.chart['$subscribed/2'][:,:,:]: +# if results: +# print q +# for result in results: +# print ' ', _repr(result.value), 'where', drepr(dict(result.variables)) +# print def do_help(self, line): mod = line.split() @@ -381,6 +389,114 @@ class REPL(cmd.Cmd, object): readline.write_history_file(self.hist) def do_trace(self, q): + """ + Trace helps you answer the question "why does the item have this + value". It is a debugging and introspection tool. The easiest way to + understand what trace does is by example: + + We'll start with something very simple: + + :- a :- b. + :- b :- c. + :- c. + + + In our solution we see that `a` is true. + + :- sol + a => true. + b => true. + c => true. + + Now we want to find out why + + :- trace a + + a => true + | + └─ :- true + + a :- b=true. + | + └─ b => true + | + └─ :- true + + b :- c=true. + | + └─ c => true + | + └─ |= true + + c |= &true. + + + The trace shows which rules fired and contributed to the value we + eventually get for `a`. + + + Trace does a few interesting things when substructure is present or + programs involve cyclic computation. + + + Consider the following dyna program: + + % shared substructure + :- backchain foo/1. + :- backchain bar/2. + foo(X) = X+1. + bar(A,B) += foo(A)*B. + bar(A,B) += A*foo(B). + + % geometric series + a += 1. + a += a/2. + + Now if we run the example interactively and inspect our results with + trace we see a that rather than print in an infinite loop or print the + same derivation over and over, only prints one derivation. + + The way trace lets you know that it has omitted something is with a + message `item: shared structure see above` or `item: *cycle*`. + + :- trace bar(10,10) + + bar(10,10) => 220 + | + ├─ += 110 + │ + │ bar(A=10, B=10) += (foo(A=10)=11 * B=10)=110. + │ | + │ └─ foo(10) => 11 + │ | + │ └─ = 11 + │ + │ foo(X=10) = (X=10 + 1)=11. + │ + └─ += 110 + + bar(A=10, B=10) += (A=10 * foo(B=10)=11)=110. + | + └─ foo(10): shared structure see above + + :- trace a + + a => 2.0 + | + ├─ += 1 + │ + │ a += 1. + └─ += 1.0 + + a += (a=2.0 / 2)=1.0. + | + └─ a: *cycle* + + """ + + if not q.strip(): + print 'No query specified. Type `help trace` for usage information.' + return if q.endswith('.'): print "Queries don't end with a dot." diff --git a/src/Dyna/Backend/Python/term.py b/src/Dyna/Backend/Python/term.py index bc968e8..c0bf6da 100644 --- a/src/Dyna/Backend/Python/term.py +++ b/src/Dyna/Backend/Python/term.py @@ -47,6 +47,7 @@ class Term(object): __add__ = __sub__ = __mul__ = notimplemented +from term import Term class Cons(Term): def __init__(self, head, tail): @@ -59,6 +60,17 @@ class Cons(Term): return [self.head] + self.tail.tolist() def __repr__(self): return repr(self.tolist()) + + def __iter__(self): +# return iter([(x,(x,),x) for x in self.tolist()]) + for a in self.tolist(): + + if not isinstance(a, Term): + yield a, (None,), a + + else: + yield a, (None,), a + def __eq__(self, other): try: return self.tolist() == other.tolist() diff --git a/src/Dyna/Backend/Python/utils.py b/src/Dyna/Backend/Python/utils.py index 958f4ab..9e96aac 100644 --- a/src/Dyna/Backend/Python/utils.py +++ b/src/Dyna/Backend/Python/utils.py @@ -84,7 +84,7 @@ def lexer(term): '|[^(), ]+', term) # everything else -def subst(term, v): +def subst(term, v, show_vars=False): """ >>> subst('f("asdf",*g(1,X, Y), X+1)', {'X': 1234}) 'f("asdf",*g(1,1234, Y), 1234+1)' @@ -97,6 +97,10 @@ def subst(term, v): """ assert isinstance(v, dict) + + if show_vars: + return ''.join((x + (red % ('=' + _repr(v[x]))) if x in v else x) for x in lexer(term)) + return ''.join((_repr(v[x]) if x in v else x) for x in lexer(term)) -- 2.50.1