From f4d6dd03ab18161809c3f40e7dc08eee16df12ae Mon Sep 17 00:00:00 2001 From: Tim Vieira Date: Wed, 17 Jul 2013 17:18:29 -0400 Subject: [PATCH] refactored code, resolved asymmetries between FC and BC (and within each) -- code now has fewer special cases and should have fixed a bunch of bugs we didn't even know we had :-X don't show BC items in changes. (BC retraction has improved, but it's still not 100% correct thanks to stale memos) --- src/Dyna/Backend/Python/interpreter.py | 172 +++++++++++++++---------- src/Dyna/Backend/Python/repl.py | 2 + src/Dyna/Backend/Python/term.py | 5 + test/repl/recursion-limit.dynadoc | 36 +++++- test/repl/retract-bc-2.dynadoc | 5 - test/repl/retract-bc.dynadoc | 38 +++++- 6 files changed, 171 insertions(+), 87 deletions(-) diff --git a/src/Dyna/Backend/Python/interpreter.py b/src/Dyna/Backend/Python/interpreter.py index da2fcb4..6f17887 100644 --- a/src/Dyna/Backend/Python/interpreter.py +++ b/src/Dyna/Backend/Python/interpreter.py @@ -5,7 +5,7 @@ from collections import defaultdict from hashlib import sha1 from path import path -from term import Term, Cons, Nil, MapsTo +from term import Term, Cons, Nil, MapsTo, Error from chart import Chart from utils import red, parse_attrs, ddict, dynac, read_anf, strip_comments, \ _repr, hide_ugly_filename, true, false @@ -100,7 +100,7 @@ class Interpreter(object): c = self.chart[fn] assert c.agg_name is None c.agg_name = agg - for item in c.intern.itervalues(): + for item in c.intern.values(): assert item.aggregator is None item.aggregator = c.new_aggregator(item) # check for aggregator conflict. @@ -122,7 +122,7 @@ class Interpreter(object): self.new_fn(fn, None) return self.chart[fn].insert(args) - def delete_emit(self, item, val, ruleix, variables): + def delete(self, item, val, ruleix, variables): self.emit(item, val, ruleix, variables, delete=True) def emit(self, item, val, ruleix, variables, delete): @@ -133,60 +133,72 @@ class Interpreter(object): self.agenda[item] = self.time_step self.time_step += 1 - def run_agenda(self, changed=None): + def replace(self, item, now): + "replace current value of ``item``, propagate any changes." + was = item.value + if was == now: + # nothing to do. + return + # delete existing value before so we can replace it + if was is not None: + self.push(item, was, delete=True) + # clear existing errors -- we only care about errors at new value. + if item in self.error: + del self.error[item] + # new value enters in the chart. + item.value = now + # push changes + if now is not None: + self.push(item, now, delete=False) + # make note of change + self.changed[item] = now + + def run_agenda(self): + self.changed = {} + self._agenda() + return self.changed + + def _agenda(self): "the main loop" - if changed is None: - changed = {} agenda = self.agenda - error = self.error - push = self.push - - def replace(item, now): - "replace current value of ``item``, propagate any changes." - was = item.value - if was == now: - # nothing to do. - return - # delete existing value before so we can replace it - if was is not None: - push(item, was, delete=True) - # clear existing errors -- we only care about errors at new value. - if item in self.error: - del self.error[item] - # new value enters in the chart. - item.value = now - # push changes - if now is not None: - push(item, now, delete=False) - # make not of change - changed[item] = now + while agenda: + item = self.agenda.pop_smallest() + self.pop(item) + # after draining the agenda, try to initialize pending rules. + self.run_uninitialized() + if self.agenda: + self._agenda() + def pop(self, item): + """ + Handle popping `item`: fold `item`'s aggregator to get it's new value + (handle errors), propagate changes to the rest of the circuit. + """ - while agenda: - item = agenda.pop_smallest() + if item.aggregator is None: + return item - try: - now = item.aggregator.fold() + try: + # compute item's new value + now = item.aggregator.fold() - except (AggregatorError, ZeroDivisionError, TypeError, KeyboardInterrupt, OverflowError) as e: - now = self.build('$error/0') - replace(item, now) - error[item] = (None, [(e, None)]) + except (AggregatorError, ZeroDivisionError, TypeError, KeyboardInterrupt, OverflowError) as e: + # handle error in aggregator + now = Error() + self.replace(item, now) + self.error[item] = (None, [(e, None)]) - else: - # special handling for with_key, forks into two updates - if hasattr(now, 'fn') and now.fn == 'with_key/2': - now, key = now.args - replace(self.build('$key/1', item), key) + else: + # issue replacement update - replace(item, now) + # special handling for with_key, forks into two updates + if hasattr(now, 'fn') and now.fn == 'with_key/2': + now, key = now.args + self.replace(self.build('$key/1', item), key) - # after draining the agenda, try to initialize pending rules - self.run_uninitialized() - if self.agenda: - self.run_agenda(changed) + self.replace(item, now) - return changed + return now def push(self, item, val, delete): """ @@ -218,35 +230,53 @@ class Interpreter(object): self.error[item] = (val, error) return - # no exception, accept emissions. + # no exceptions, accept emissions. for e in emittiers: - # an error could happen here, but we assume (by contract) that - # this is not possible. + # an error could happen here, but we assume (by contract) that this + # is not possible. self.emit(*e) def gbc(self, fn, *args): - # TODO: need to distinguish `unknown` from `null` when we move to mixed - # chaining. - head = self.build(fn, *args) + item = self.build(fn, *args) - if head.value is not None: - return head.value + # TODO: we will need to distinguish `unknown` from `null` when we move + # to mixed chaining. + if item.value is not None: + return item.value - if head.aggregator is None: # we might not have a rule defining this subgoal. + if item.aggregator is None: # we might not have a rule defining this subgoal. return - head.aggregator.clear() + item.aggregator.clear() - def _emit(item, val, ruleix, variables): - item.aggregator.inc(val, ruleix, variables) + emits = [] + def t_emit(item, val, ruleix, variables): + emits.append((item, val, ruleix, variables, False)) + + error = [] - for h in self._gbc[fn]: - h(*args, emit=_emit) + for handler in self._gbc[item.fn]: + try: + handler(*args, emit=t_emit) + except (ZeroDivisionError, TypeError, KeyboardInterrupt, RuntimeError, OverflowError) as e: + e.exception_frame = rule_error_context() + e.traceback = traceback.format_exc() + error.append((e, handler)) - head.value = head.aggregator.fold() + if error: + self.error[item] = (None, error) + now = Error() + return now + + else: + # no exceptions, accept emissions. + for e in emits: + # an error could happen here, but we assume (by contract) that this + # is not possible. + self.emit(*e) + return self.pop(item) - return head.value def load_plan(self, filename): """ @@ -340,7 +370,6 @@ class Interpreter(object): assert False, 'did not find head' assert head_fn is not None - span = hide_ugly_filename(parse_attrs(init or query)['Span']) dyna_src = strip_comments(parse_attrs(init or query)['rule']) @@ -374,11 +403,9 @@ class Interpreter(object): todyna([anf.head, anf.agg, anf.result, anf.evals, anf.unifs]), init, query) - fn = '$rule/%s' % len(args) if self.agg_name[fn] is None: self.new_fn(fn, ':=') - rule.item = self.build(fn, *args) self.emit(rule.item, true, ruleix=None, variables=None, delete=False) @@ -405,7 +432,7 @@ class Interpreter(object): # remove $rule if hasattr(rule, 'item'): - self.delete_emit(rule.item, true, ruleix=None, variables=None) + self.delete(rule.item, true, ruleix=None, variables=None) if rule.init is not None: # Forward chained rule -- @@ -418,7 +445,7 @@ class Interpreter(object): if rule.initialized: # run initializer in delete mode try: - rule.init(emit=self.delete_emit) + rule.init(emit=self.delete) except (ZeroDivisionError, TypeError, KeyboardInterrupt, RuntimeError, OverflowError): # TODO: what happens if there's an error? pass @@ -429,11 +456,16 @@ class Interpreter(object): # Backchained rule -- # 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: # update values before propagating - for head in self.chart[rule.head_fn].intern.itervalues(): + for head in self.chart[rule.head_fn].intern.values(): + + if head in self.error: + del self.error[head] + def _emit(item, val, ruleix, variables): item.aggregator.dec(val, ruleix, variables) try: @@ -443,7 +475,7 @@ class Interpreter(object): pass # propagate new values - for head in self.chart[rule.head_fn].intern.itervalues(): + for head in self.chart[rule.head_fn].intern.values(): self.agenda[head] = self.time_step self.time_step += 1 diff --git a/src/Dyna/Backend/Python/repl.py b/src/Dyna/Backend/Python/repl.py index 334c1c3..dfdc097 100644 --- a/src/Dyna/Backend/Python/repl.py +++ b/src/Dyna/Backend/Python/repl.py @@ -278,6 +278,8 @@ class REPL(cmd.Cmd, object): print 'Changes' print '=======' for x in sorted(changed): + if x.fn in self.interp._gbc: # skip BC + continue print '%s = %s.' % (x, _repr(x.value)) print diff --git a/src/Dyna/Backend/Python/term.py b/src/Dyna/Backend/Python/term.py index 0df5fca..38a3ea9 100644 --- a/src/Dyna/Backend/Python/term.py +++ b/src/Dyna/Backend/Python/term.py @@ -99,6 +99,11 @@ class Cons(Term): # return +class Error(Term): + def __init__(self): + Term.__init__(self, '$error/0', ()) + + class _Nil(Term): def __init__(self): diff --git a/test/repl/recursion-limit.dynadoc b/test/repl/recursion-limit.dynadoc index b20995a..1dbe2d7 100644 --- a/test/repl/recursion-limit.dynadoc +++ b/test/repl/recursion-limit.dynadoc @@ -8,22 +8,48 @@ % add this rule separately to make sure its an initialization failure > a = f(3). +Changes +======= +a = $error. + +> b = a + 1. + > rules Rules ===== 0: f(X) = f(X-1). - 1: a = f(3). <-- uninitialized + 1: a = f(3). + 2: b = a + 1. <-- uninitialized > sol -Solution empty. +Solution +======== +a = $error. Errors ====== +Error(s) in rule: + f(X) = f(X-1). + RuntimeError: + when `f(-323)` = null + maximum recursion depth exceeded + f(X=-323) = f((X=-323 - 1)=-324)=?. + Uninitialized rules =================== Failed to initialize rule: - a = f(3). - due to `maximum recursion depth exceeded` - a = f(3)=?. + b = a + 1. + due to `unsupported operand type(s) for +: 'Error' and 'int'` + b = (a=$error + 1)=?. + +> retract_rule 0 + +Changes +======= +a = null. + +> sol + +Solution empty. \ No newline at end of file diff --git a/test/repl/retract-bc-2.dynadoc b/test/repl/retract-bc-2.dynadoc index b5a9d5e..c5fa45e 100644 --- a/test/repl/retract-bc-2.dynadoc +++ b/test/repl/retract-bc-2.dynadoc @@ -47,11 +47,6 @@ c(2) = null. c(3) = null. c(4) = null. c(5) = null. -g(1) = null. -g(2) = null. -g(3) = null. -g(4) = null. -g(5) = null. % as in `retract-bc.dynadoc`, `a(X)` did not change even tho it ought to. The % `c(X)` values get blasted because the don't have an oblivious memoized item diff --git a/test/repl/retract-bc.dynadoc b/test/repl/retract-bc.dynadoc index 4b52c07..91e24c0 100644 --- a/test/repl/retract-bc.dynadoc +++ b/test/repl/retract-bc.dynadoc @@ -31,10 +31,6 @@ a(2) = null. a(3) = null. a(4) = null. a(5) = null. -f(2) = null. -f(3) = null. -f(4) = null. -f(5) = null. s = 1. @@ -61,12 +57,40 @@ a(1) = 1. | f(0) := 1. | b(X) = f(X) for X in range(6). -% oh no! a(x) doesn't know that we have a new definition! for `f`, unlike the -% rule defining `b(X)` which we use the new version of `f` when we run it's -% initializer. +% Check that `a(x)` and `s`, know that we have a new definition! for `f`, just +% like added a new rule Changes ======= +a(2) = 2. +a(3) = 6. +a(4) = 24. +a(5) = 120. +b(0) = 0. +b(1) = 1. +b(2) = 2. +b(3) = 6. +b(4) = 24. +b(5) = 120. +s = 153. + +> sol + +Solution +======== +s = 153. + +a/1 +=== +a(0) = 0. +a(1) = 1. +a(2) = 2. +a(3) = 6. +a(4) = 24. +a(5) = 120. + +b/1 +=== b(0) = 0. b(1) = 1. b(2) = 2. -- 2.50.1