From 5f3fe73ea690c896e4f9290f9df45062ed36e13c Mon Sep 17 00:00:00 2001 From: Tim Vieira Date: Mon, 5 Aug 2013 17:58:24 -0400 Subject: [PATCH] BUGFIX in recompute backchain. Further improvements to code coverage. --- src/Dyna/Backend/Python/aggregator.py | 19 +++--- src/Dyna/Backend/Python/interpreter.py | 70 ++++++++++++++-------- src/Dyna/Backend/Python/stdlib.py | 26 ++++---- test/app/ptb.dynadoc | 17 +++--- test/repl/add-bc.dynadoc | 2 +- test/repl/aggregators.dynadoc | 83 +++++++++++++++++++++++++- test/repl/boolean-ops.dynadoc | 32 ++++++++++ test/repl/list.dynadoc | 13 ++++ test/repl/trace.dynadoc | 12 ++++ 9 files changed, 218 insertions(+), 56 deletions(-) diff --git a/src/Dyna/Backend/Python/aggregator.py b/src/Dyna/Backend/Python/aggregator.py index 685080d..d6f609c 100644 --- a/src/Dyna/Backend/Python/aggregator.py +++ b/src/Dyna/Backend/Python/aggregator.py @@ -151,24 +151,19 @@ class or_equals(BAggregator): raise TypeError('%s is not Boolean.' % _repr(val)) # TODO: can short circuit as soon as we get a true... but above we # check the types.. so we don't get the benefit. - for val in s: - if val is true: - return true - return false + return todyna(any(s)) class colon_dash(BAggregator): def fold(self): s = [x for x, m in self.iteritems() if m > 0] + for val in s: + if val is not true: + raise TypeError('%s is not true.' % _repr(val)) + # TODO: can short circuit as soon as we get a true... but above we check + # the types.. so we don't get the benefit. if len(s): - for val in s: - if val is not true: - raise TypeError('%s is not true.' % _repr(val)) - # TODO: can short circuit as soon as we get a true... but above we - # check the types.. so we don't get the benefit. - for val in s: - if val is true: - return true + return true class and_equals(BAggregator): diff --git a/src/Dyna/Backend/Python/interpreter.py b/src/Dyna/Backend/Python/interpreter.py index 4f5c50d..944fcfb 100644 --- a/src/Dyna/Backend/Python/interpreter.py +++ b/src/Dyna/Backend/Python/interpreter.py @@ -43,7 +43,7 @@ class Rule(object): return 1 def __repr__(self): - return 'Rule(%s, %r)' % (self.index, self.src) + return '%3s: %s' % (self.index, self.src) def render_ctx(self, ctx, indent=''): # TODO: highlight expression which caused the error. @@ -51,11 +51,11 @@ class Rule(object): c = Crux(head=None, rule=self, body=None, vs = ctx) return '\n'.join(indent + line for line in c.format()) - def debug(self): - import debug - with file(dotdynadir / 'tmp.dyna', 'wb') as f: - f.write(self.src) - debug.main(f.name) +# def debug(self): +# import debug +# with file(dotdynadir / 'tmp.dyna', 'wb') as f: +# f.write(self.src) +# debug.main(f.name) # TODO: yuck, hopefully temporary measure to support pickling the Interpreter's @@ -169,8 +169,6 @@ class Interpreter(object): Handle popping `item`: fold `item`'s aggregator to get it's new value (handle errors), propagate changes to the rest of the circuit. """ - if item.aggregator is None: - return item try: # compute item's new value now = item.aggregator.fold() @@ -279,14 +277,25 @@ class Interpreter(object): e.traceback = traceback.format_exc() errors.append((e, handler)) - if errors: - self.set_error(item, (None, errors)) - return Error() + if hasattr(self, 'was') and self.was: + was = self.was + if item in was: + if item.value != was[item]: + item.value = was[item] - for e in emits: - self.emit(*e) + if errors: + e = Error() + self.push(item, e, delete=False) - return self.pop(item) + # Force value to error, since aggregator might ignore it. This is + # not correct XREF:agg-error + self.replace(item, e) + self.set_error(item, (None, errors)) + return e + else: + for e in emits: + self.emit(*e) + return self.pop(item) def load_plan(self, filename): """ @@ -406,8 +415,6 @@ class Interpreter(object): del self.error[x] def set_error(self, x, e): - if not e: - self.clear_error(x) self.error[x] = e #___________________________________________________________________________ @@ -422,7 +429,7 @@ class Interpreter(object): head_fn = '%s/%d' % (ys[0], len(ys) - 1) break else: - assert False, 'did not find head' + raise AssertionError('Did not find head.') self.rules[index] = rule = Rule(index) rule.span = hide_ugly_filename(span) @@ -458,7 +465,7 @@ class Interpreter(object): self.recompute_gbc_memo(head_fn) else: - assert False, "Can't add rule with out an initializer or query handler." + raise AssertionError("Can't add rule with out an initializer or query handler.") if True: args = (index, @@ -522,6 +529,7 @@ class Interpreter(object): self.uninitialized_rules.remove(rule) else: + # Backchained rule -- # remove query handler self._gbc[rule.head_fn].remove(rule.query) @@ -544,8 +552,8 @@ class Interpreter(object): if not self.rule_by_head[rule.head_fn]: if rule.head_fn in self.chart: self.chart[rule.head_fn].set_aggregator(None) - if rule.head_fn in self.agg_name: - del self.agg_name[rule.head_fn] + #if rule.head_fn in self.agg_name: rule can't exist with out an aggregator + del self.agg_name[rule.head_fn] return self.changed @@ -554,15 +562,29 @@ class Interpreter(object): if visited is None: visited = set() - if fn not in self._gbc or fn in visited: + if fn not in self.bc or fn in visited: # don't refresh non-BC computation. Also, be careful not to get # stuck in an infinite loop if there is a cycle in the dep graph return visited.add(fn) + # YUCK: find some was to avoid this... + self.was = {x: x.value for x in self.chart[fn].intern.values()} + + for x in self.chart[fn].intern.values(): + x.value = None # avoid memo + for x in self.chart[fn].intern.values(): - self.force_gbc(x) + now = self.force_gbc(x) + + if now != self.was[x]: + self.changed[x] = now + else: + if x in self.changed: + del self.changed[x] + + self.was = None # recompute dependent BC memos for v in self.coarse_deps[fn]: @@ -723,9 +745,9 @@ class Interpreter(object): for i in sorted(self.rules): rule = self.rules[i] if rule.init is not None and not rule.initialized: - print '%3s: %s <-- uninitialized' % (i, rule.src) + print '%s <-- uninitialized' % rule else: - print '%3s: %s' % (i, rule.src) + print rule print diff --git a/src/Dyna/Backend/Python/stdlib.py b/src/Dyna/Backend/Python/stdlib.py index 7aa94f5..5bcbc15 100644 --- a/src/Dyna/Backend/Python/stdlib.py +++ b/src/Dyna/Backend/Python/stdlib.py @@ -89,12 +89,18 @@ def pycall(name, *args): x = eval(name)(*args) return todyna(x) +# TODO: should convert Term arguments def topython(x): if islist(x): return [topython(y) for y in x.aslist] elif isinstance(x, MapsTo): return tuple(x.args) - return x +# elif isinstance(x, Term): +# z = Term(x.fn, tuple(topython(y) for y in x.args)) +# z.value = topython(x.value) +# return z + else: + return x def todyna(x): if isinstance(x, (set, Counter)): @@ -115,27 +121,27 @@ def todyna(x): else: return x -def get(x, i): - return x[i] +#def get(x, i): +# return x[i] -def getkey(m, k): - return m[k] +#def getkey(m, k): +# return m[k] -def setkey(m, k, v): - m[k] = v - return m +#def setkey(m, k, v): +# m[k] = v +# return m def islist(x): return isinstance(x, Cons) or x is Nil def iter_cons(x): if not islist(x): - raise TypeError("Attemping to iterate something which isn't a list. %r" % (x,)) + raise TypeError("Attempting to iterate something which isn't a list. %r" % (x,)) return x.like_chart() def in_list(x, a): if not islist(a): - raise TypeError("Attemping to iterate something which isn't a list. %r" % (a,)) + raise TypeError("Attempting to iterate something which isn't a list. %r" % (a,)) return todyna(x in a.aslist) # should probably be done with memoized backchaining... diff --git a/test/app/ptb.dynadoc b/test/app/ptb.dynadoc index 0e0d7b9..9043331 100644 --- a/test/app/ptb.dynadoc +++ b/test/app/ptb.dynadoc @@ -117,11 +117,10 @@ | sentence(S) = reverse(s(S, slen(S))). | | goal(S) max= phrase(S, "ROOT", 0, length(sentence(S))). -| parse(S) = path(S, "ROOT", 0, length(sentence(S))). +| parse(S) := path(S, "ROOT", 0, length(sentence(S))). *ignore* - % very inefficient way to format trees (not required, just fun to see that we % can do it). % @@ -134,7 +133,8 @@ %| tostring([X,Y,Z]) := "(" + tostring(X) + " " + tostring(Y) + " " + tostring(Z) + ")". % collect errors -%> errors(S) = [tostring(parse(S)), tostring(b(tree(S)))] for parse(S) != b(tree(S)). +%> errors(S) = parse(S) != b(tree(S)) for tree(S). +% % *ignore* % report accuracy @@ -144,12 +144,15 @@ Changes ======= -accuracy = 0.9130434782608695. -correct = 21.0. +accuracy = 0.9565217391304348. +correct = 22.0. ntrees = 23. -% inspect errors -%> query errors(S) +% inspect errors -- can't get null parses. + +%> vquery parse(X) + +% query errors(X) %errors(12) = ["(ROOT (S (NP Laura) (VP (VP (V (V say) -s) (SBAR that (S (NP George) (VP (Modal might) (VP (V sleep)))))) (PP (P on) (NP (Det the) (N floor))))) !)", "(ROOT (S (NP Laura) (VP (V (V say) -s) (SBAR that (S (NP George) (VP (VP (Modal might) (VP (V sleep))) (PP (P on) (NP (Det the) (N floor)))))))) !)"]. %errors(21) = ["(ROOT (S (NP (NP (Det the) (N (Adj (Adj fine) (@Adj and (Adj blue))) (N woman))) (@NP and (NP (Det every) (N man)))) (VP (VP (Modal must) (VP (V have) (VP (V (V eat) -ed) (NP (Det two) (N (N sandwich) -s))))) (@VP and (VP (VP (V (V sleep) -ed)) (PP (P on) (NP (Det the) (N floor))))))) .)", "(ROOT (S (NP (NP (Det the) (N (Adj (Adj fine) (@Adj and (Adj blue))) (N woman))) (@NP and (NP (Det every) (N man)))) (VP (VP (Modal must) (VP (V have) (VP (VP (V (V eat) -ed) (NP (Det two) (N (N sandwich) -s))) (@VP and (VP (V (V sleep) -ed)))))) (PP (P on) (NP (Det the) (N floor))))) .)"]. diff --git a/test/repl/add-bc.dynadoc b/test/repl/add-bc.dynadoc index 08586da..f3e58e6 100644 --- a/test/repl/add-bc.dynadoc +++ b/test/repl/add-bc.dynadoc @@ -24,4 +24,4 @@ sum(9) = 10036. % sum(10) computation) if we'd defined like this: % sum(0) += 0. -% sum(N) += N + sum(N_1) for N > 0. \ No newline at end of file +% sum(N) += N + sum(N_1) for N > 0. diff --git a/test/repl/aggregators.dynadoc b/test/repl/aggregators.dynadoc index 312922c..f1c5d4e 100644 --- a/test/repl/aggregators.dynadoc +++ b/test/repl/aggregators.dynadoc @@ -1,3 +1,7 @@ + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% majority= + > a majority= 1. | a majority= 1. | a majority= 1. @@ -36,6 +40,9 @@ Changes a = null. +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% mean= + > a mean= 1. | a mean= 2. | a mean= 3. @@ -71,8 +78,8 @@ Changes a = null. - -% A few simple tests for `*=` +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% *= > a *= 3. | a *= 3. @@ -92,3 +99,75 @@ a = 3. Changes ======= a = null. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% |= + +> a |= false. + +Changes +======= +a = false. + +> retract_rule 10 + +Changes +======= +a = null. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% &= + +> a &= false. + +Changes +======= +a = false. + +> retract_rule 11 + +Changes +======= +a = null. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% set= + +> a set= "foo". + +Changes +======= +a = ["foo"]. + +> retract_rule 12 + +Changes +======= +a = null. + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% bag= + +> a bag= "foo". +| a bag= "foo". + +Changes +======= +a = ["foo", "foo"]. + +> retract_rule 13 + +Changes +======= +a = ["foo"]. + +> retract_rule 14 + +Changes +======= +a = null. diff --git a/test/repl/boolean-ops.dynadoc b/test/repl/boolean-ops.dynadoc index 460307c..086ecb9 100644 --- a/test/repl/boolean-ops.dynadoc +++ b/test/repl/boolean-ops.dynadoc @@ -24,3 +24,35 @@ y = "yes". > query f(X) == true f("bool") == true = true. + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Type errors + +> x1 := "a" & true. +| x2 := true & "a". + +>>> 2 new errors. Type `sol` for details. + +> y1 := "a" | true. +| y2 := true | "a". + +>>> 2 new errors. Type `sol` for details. + +> zzz := !"a". + +>>> 1 new errors. Type `sol` for details. + + + +% correct behavior + +> xx := true & true. +| yy := false | true. +| zz := !(!xx). + +Changes +======= +xx = true. +yy = true. +zz = true. diff --git a/test/repl/list.dynadoc b/test/repl/list.dynadoc index a742f34..ac02369 100644 --- a/test/repl/list.dynadoc +++ b/test/repl/list.dynadoc @@ -168,3 +168,16 @@ foobar([1, 3]) = true. foobar([]) = true. foobar(a,b) = true. foobar(a,c) = true. + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Errors + +> xxx = 1 for X in 1234. + +>>> 1 new errors. Type `sol` for details. + +> xxx = 1 in 1234. + +>>> 1 new errors. Type `sol` for details. diff --git a/test/repl/trace.dynadoc b/test/repl/trace.dynadoc index 047d24e..dd66336 100644 --- a/test/repl/trace.dynadoc +++ b/test/repl/trace.dynadoc @@ -70,6 +70,18 @@ b = 3 | └─ continue as before (shared structure) + + +> trace b --limit=1 + +b = 3 +| +└─ := 3 + b := f(3)=3. + | + └─ *max depth* + + > :- backchain foo/1. | :- backchain bar/2. | foo(X) = X+1. -- 2.50.1