From 6817ec973ee46723efedad40b85e77a4ea198780 Mon Sep 17 00:00:00 2001 From: Tim Vieira Date: Fri, 19 Jul 2013 14:37:32 -0400 Subject: [PATCH] Big improvments to memoized BC rule retraction. We now correctly update transitive dependents (before we didn't refresh the memos, so we were getting incorrect behavior). Catch ^C again.. Minor tweak to make fewer replacement updates to $key. --- examples/force.dyna | 5 +- src/Dyna/Backend/Python/interpreter.py | 72 +++++++++++++++----------- test/app/ptb.dynadoc | 12 ++--- test/repl/retract-bc-2.dynadoc | 52 +++++-------------- 4 files changed, 63 insertions(+), 78 deletions(-) diff --git a/examples/force.dyna b/examples/force.dyna index 2c4abb8..589384e 100644 --- a/examples/force.dyna +++ b/examples/force.dyna @@ -21,10 +21,9 @@ forceY(V,T) += f(U,V,T) * (y(U,T) - y(V,T)). % Constants a := 0.15. -niter := 20. -edgelen := 4.0. % "the unit edge length" +niter := 100. +edgelen := 1.0. % "the unit edge length" -% should `a` be negative? x(U,T) += a * forceX(U,T-1). y(U,T) += a * forceY(U,T-1). diff --git a/src/Dyna/Backend/Python/interpreter.py b/src/Dyna/Backend/Python/interpreter.py index c97fa46..33a9e41 100644 --- a/src/Dyna/Backend/Python/interpreter.py +++ b/src/Dyna/Backend/Python/interpreter.py @@ -140,7 +140,9 @@ class Interpreter(object): # nothing to do. return # special handling for with_key, forks a second update - self.replace(self.build('$key/1', item), None) # always clear $key + k = self.build('$key/1', item) + if k.value is not None: + self.replace(k, None) if hasattr(now, 'fn') and now.fn == 'with_key/2': now, key = now.args self.replace(self.build('$key/1', item), key) @@ -159,7 +161,10 @@ class Interpreter(object): def run_agenda(self): self.changed = {} - self._agenda() + try: + self._agenda() + except KeyboardInterrupt: + print '^C' return self.changed def _agenda(self): @@ -186,7 +191,7 @@ class Interpreter(object): # compute item's new value now = item.aggregator.fold() - except (AggregatorError, ZeroDivisionError, TypeError, KeyboardInterrupt, OverflowError) as e: + except (AggregatorError, ZeroDivisionError, TypeError, OverflowError) as e: # handle error in aggregator now = Error() self.replace(item, now) @@ -218,7 +223,7 @@ class Interpreter(object): try: handler(item, val, emit=t_emit) - except (ZeroDivisionError, TypeError, KeyboardInterrupt, RuntimeError, OverflowError) as e: + except (ZeroDivisionError, TypeError, RuntimeError, OverflowError) as e: e.exception_frame = rule_error_context() e.traceback = traceback.format_exc() error.append((e, handler)) @@ -256,7 +261,7 @@ class Interpreter(object): for handler in self._gbc[item.fn]: try: handler(*args, emit=t_emit) - except (ZeroDivisionError, TypeError, KeyboardInterrupt, RuntimeError, OverflowError) as e: + except (ZeroDivisionError, TypeError, RuntimeError, OverflowError) as e: e.exception_frame = rule_error_context() e.traceback = traceback.format_exc() errors.append((e, handler)) @@ -273,7 +278,6 @@ class Interpreter(object): self.emit(*e) return self.pop(item) - def load_plan(self, filename): """ Compile, load, and execute new dyna rules. @@ -332,7 +336,7 @@ class Interpreter(object): self.clear_error(rule) # clear errors on rule, if any rule.init(emit=_emit) - except (ZeroDivisionError, TypeError, KeyboardInterrupt, RuntimeError, OverflowError) as e: + except (ZeroDivisionError, TypeError, RuntimeError, OverflowError) as e: e.exception_frame = rule_error_context() e.traceback = traceback.format_exc() self.set_error(rule, e) @@ -398,8 +402,6 @@ class Interpreter(object): else: assert False, "Can't add rule with out an initializer or query handler." - # XXX: all rules should eventually have ANF tacked on, but until then... - #if anf is not None: if True: args = (index, dyna_src, @@ -416,7 +418,8 @@ class Interpreter(object): self.rule_by_head[rule.head_fn].append(rule) for (_, label, ys) in rule.anf.evals: [(label, _evalix)] = re.findall('^(.*)@(\d+)$', label) # remove evaluation index - self.coarse_deps[rule.head_fn].add('%s/%d' % (label, len(ys))) + b = '%s/%d' % (label, len(ys)) + self.coarse_deps[b].add(rule.head_fn) def recompute_coarse(self): self.rule_by_head.clear() @@ -427,6 +430,8 @@ class Interpreter(object): def retract_rule(self, idx): "Retract rule and all of it's edges." + self.changed = {} + try: rule = self.rules.pop(idx) except KeyError: @@ -444,12 +449,11 @@ class Interpreter(object): for xs in self.updaters.values(): if u in xs: xs.remove(u) - assert u not in xs, 'Several occurrences of u in xs' if rule.initialized: # run initializer in delete mode try: rule.init(emit=self.delete) - except (ZeroDivisionError, TypeError, KeyboardInterrupt, RuntimeError, OverflowError): + except (ZeroDivisionError, TypeError, RuntimeError, OverflowError): # TODO: what happens if there's an error? pass else: @@ -460,31 +464,37 @@ class Interpreter(object): # remove query handler self._gbc[rule.head_fn].remove(rule.query) - # blast the memo entries for items this rule may have helped derive. - if rule.head_fn in self.chart: + # recompute memos and dependent memos + self.recompute_gbc_memo(rule.head_fn) - # update values before propagating - for head in self.chart[rule.head_fn].intern.values(): + self.recompute_coarse() - self.clear_error(head) + self._agenda() + return self.changed - def _emit(item, val, ruleix, variables): - item.aggregator.dec(val, ruleix, variables) - try: - rule.query(*head.args, emit=_emit) - except (ZeroDivisionError, TypeError, KeyboardInterrupt, RuntimeError, OverflowError): - # TODO: what happens if there's an error? - pass + def recompute_gbc_memo(self, fn, visited=None): - # propagate new values - for head in self.chart[rule.head_fn].intern.values(): - self.agenda[head] = self.time_step - self.time_step += 1 + if visited is None: + visited = set() - self.recompute_coarse() - # todo: need coarse deps transitive closure + if fn not in self._gbc or fn in visited: + # don't refresh non BC computation be careful not to get stuck in an + # infinite loop if there is a cycle in the dep graph + return + + visited.add(fn) + + for x in self.chart[fn].intern.values(): + self.clear_error(x) + was = x.value # remember old value we can do proper replacement update + x.value = None # ignore memo + now = self.gbc(fn, *x.args) + x.value = was + self.replace(x, now) - return self.run_agenda() + # recompute dependent BC memos + for v in self.coarse_deps[fn]: + self.recompute_gbc_memo(v, visited) def new_updater(self, fn, ruleix, handler): self.updaters[fn].append(handler) diff --git a/test/app/ptb.dynadoc b/test/app/ptb.dynadoc index 4581fc5..0e0d7b9 100644 --- a/test/app/ptb.dynadoc +++ b/test/app/ptb.dynadoc @@ -123,15 +123,15 @@ % very inefficient way to format trees (not required, just fun to see that we -% can do it). +% can do it). % % TODO: unbinarize % -> :- backchain tostring/1. -| tostring(X) := X. -| tostring(&'@'(X)) := "@" + X. -| tostring([X,Y]) := "(" + tostring(X) + " " + tostring(Y) + ")". -| tostring([X,Y,Z]) := "(" + tostring(X) + " " + tostring(Y) + " " + tostring(Z) + ")". +%> :- backchain tostring/1. +%| tostring(X) := X. +%| tostring(&'@'(X)) := "@" + X. +%| tostring([X,Y]) := "(" + tostring(X) + " " + tostring(Y) + ")". +%| 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)). diff --git a/test/repl/retract-bc-2.dynadoc b/test/repl/retract-bc-2.dynadoc index 0e7d6d5..90a4519 100644 --- a/test/repl/retract-bc-2.dynadoc +++ b/test/repl/retract-bc-2.dynadoc @@ -3,27 +3,20 @@ | :- backchain f/1. | h(X) += g(X)/2. | h(X) += f(X)/2. -| a(X) = h(X) for X in range(6). +| a(X) = h(X) for X in range(1,6). | | g(X) = X*f(X-1) for X > 0. | f(X) = X*g(X-1) for X > 0. | f(0) = 1. | g(0) = 1. -| c(X) = (f(X) + g(X)) / 2 for X in range(1,6). % skip the base case. Changes ======= -a(0) = 1.0. a(1) = 1.0. a(2) = 2.0. a(3) = 6.0. a(4) = 24.0. a(5) = 120.0. -c(1) = 1.0. -c(2) = 2.0. -c(3) = 6.0. -c(4) = 24.0. -c(5) = 120.0. > rules @@ -31,60 +24,43 @@ Rules ===== 0: h(X) += g(X)/2. 1: h(X) += f(X)/2. - 2: a(X) = h(X) for X in range(6). + 2: a(X) = h(X) for X in range(1,6). 3: g(X) = X*f(X-1) for X > 0. 4: f(X) = X*g(X-1) for X > 0. 5: f(0) = 1. 6: g(0) = 1. - 7: c(X) = (f(X) + g(X)) / 2 for X in range(1,6). > retract_rule 3 Changes ======= -c(1) = null. -c(2) = null. -c(3) = null. -c(4) = null. -c(5) = null. +a(1) = 0.5. +a(2) = null. +a(3) = null. +a(4) = null. +a(5) = null. % TODO (bug): `a(X)` did not change even tho it ought to. The `c(X)` values get % blasted because the don't have an obliviously memoized item inbetween, `h(X)`. -> b(X) = h(X) for X in range(6). - -Changes -======= -b(0) = 1.0. -b(1) = 1.0. -b(2) = 2.0. -b(3) = 6.0. -b(4) = 24.0. -b(5) = 120.0. +> b(X) = h(X) for X in range(1,6). % Just to hammer the point home, the rule above shows that `h(X)` values are % still memoized! It doesn't know that one of it's antecedents has changed. +Changes +======= +b(1) = 0.5. + > sol Solution ======== a/1 === -a(0) = 1.0. -a(1) = 1.0. -a(2) = 2.0. -a(3) = 6.0. -a(4) = 24.0. -a(5) = 120.0. - +a(1) = 0.5. b/1 === -b(0) = 1.0. -b(1) = 1.0. -b(2) = 2.0. -b(3) = 6.0. -b(4) = 24.0. -b(5) = 120.0. +b(1) = 0.5. % TODO: redefine `g` see if the other rules pick up the new definition. -- 2.50.1