From 817401d29ca919c46188314243690c92b59552fc Mon Sep 17 00:00:00 2001 From: timv Date: Thu, 6 Jun 2013 23:37:43 -0400 Subject: [PATCH] New features and cleanup. New feature: support for rule retraction - rules are indexed by `Interpreter` and stored in a `Rule` instance. - REPL features to list rules, retract rule by it'd rule index. New features: item retraction - this is an experimental feature, which is very inefficient. Update python deps in readme chart dumps and trace output use dyna-style double quoted strings and lower case Booleans. better output formatting for REPL/query --- README.md | 13 +- src/Dyna/Backend/Python/chart.py | 21 +-- src/Dyna/Backend/Python/config.py | 3 + src/Dyna/Backend/Python/debug.py | 3 +- src/Dyna/Backend/Python/interpreter.py | 179 +++++++++++++++++-------- src/Dyna/Backend/Python/repl.py | 35 +++-- src/Dyna/Backend/Python/utils.py | 105 +++------------ 7 files changed, 195 insertions(+), 164 deletions(-) diff --git a/README.md b/README.md index 288deea..e605139 100644 --- a/README.md +++ b/README.md @@ -19,14 +19,16 @@ Building -------- First, ensure that you have the Haskell platform 2012.2 or later installed, -either through your favorite package manager or by installing it -stand-alone. You'll want to have the following programs installed, too: +either through your favorite package manager or by installing it stand-alone. +You'll want to have the following programs installed: * Python 2.7 or compatible - * IPython - * Pygments (for pretty code output in our compiler-debugging tools) * graphviz +The python modules required + + $ easy_install path.py ipython pygments + You should probably run cabal update @@ -48,8 +50,7 @@ And read up on the documentation: At this point, the code is still rather "in the works" so you probably want to... -* Run the python backend interactively (leave off the "-i" for bulk -operation): +* Run the python backend interactively (leave off the "-i" for bulk operation): ./dyna -i examples/papa2.dyna diff --git a/src/Dyna/Backend/Python/chart.py b/src/Dyna/Backend/Python/chart.py index 8c06640..70b8868 100644 --- a/src/Dyna/Backend/Python/chart.py +++ b/src/Dyna/Backend/Python/chart.py @@ -32,13 +32,18 @@ class Term(object): __add__ = __sub__ = __mul__ = notimplemented -#def _repr(x): -# if isinstance(x, basestring): -# # dyna doesn't accept single-quoted strings -# return '"%s"' % x.replace('"', r'\"') -# else: -# return repr(x) -_repr = repr +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) class Chart(object): @@ -52,7 +57,7 @@ class Chart(object): def __repr__(self): rows = [term for term in self.intern.values() if term.value is not None] - x = '\n'.join('%-30s := %r' % (term, term.value) for term in sorted(rows)) + x = '\n'.join('%-30s := %s' % (term, _repr(term.value)) for term in sorted(rows)) return '%s\n=================\n%s' % (self.name, x) def __getitem__(self, s): diff --git a/src/Dyna/Backend/Python/config.py b/src/Dyna/Backend/Python/config.py index 5f5993b..a504281 100644 --- a/src/Dyna/Backend/Python/config.py +++ b/src/Dyna/Backend/Python/config.py @@ -1,5 +1,8 @@ +import os from path import path dotdynadir = path('~/.dyna').expand() if not dotdynadir.exists(): dotdynadir.mkdir() + +dynahome = os.getenv('DYNAHOME', '.') diff --git a/src/Dyna/Backend/Python/debug.py b/src/Dyna/Backend/Python/debug.py index 5a89edc..1d69906 100644 --- a/src/Dyna/Backend/Python/debug.py +++ b/src/Dyna/Backend/Python/debug.py @@ -7,7 +7,8 @@ normalization process. import re, os, shutil, webbrowser from collections import defaultdict, namedtuple from cStringIO import StringIO -from utils import magenta, red, green, yellow, white, read_anf, dynahome +from utils import magenta, red, green, yellow, white, read_anf +from config import dynahome from pygments import highlight from pygments.lexers import get_lexer_by_name diff --git a/src/Dyna/Backend/Python/interpreter.py b/src/Dyna/Backend/Python/interpreter.py index 4e8a24f..7346956 100644 --- a/src/Dyna/Backend/Python/interpreter.py +++ b/src/Dyna/Backend/Python/interpreter.py @@ -6,21 +6,21 @@ MISC - TODO: faster charts (dynamic argument types? jason's trie data structure) - - TODO: write files to ~/.dyna + - TODO: write all files to ~/.dyna + + - TODO: `None` does not propagate, eventually it will becase of the `?` prefix + operator. - TODO: (@nwf) String quoting (see example/stringquote.py) + - TODO: (@nwf) mode planning failures are slient + - TODO: filter and bulk loader - TODO: make sure interpreter uses the right exceptions. The codegen catches a few things -- I think assertionerror is one them... we should probably do whatever this is doing with a custom exception. - - TODO: (@nwf) mode planning failures are slient - - - TODO: deleting a rule: (1) remove update handlers (2) run initializers in - delete mode (3) remove initializers. - - TODO: hooks from introspection, eval, and prioritization. What's the default prioritization? @@ -90,11 +90,12 @@ from collections import defaultdict from argparse import ArgumentParser import debug -from chart import Chart, Term +from chart import Chart, Term, _repr from defn import aggregator -from utils import ip, red, green, blue, magenta, yellow, dynahome, \ - notimplemented, prioritydict, parse_attrs -from config import dotdynadir +from utils import ip, red, green, blue, magenta, yellow, \ + notimplemented, parse_attrs, ddict, dynac +from prioritydict import prioritydict +from config import dotdynadir, dynahome class AggregatorConflict(Exception): @@ -118,6 +119,21 @@ class DynaCompilerError(Exception): pass +class Rule(object): + def __init__(self, idx): + self.idx = idx + self.init = None + self.updaters = [] + @property + def span(self): + return self.init.dyna_attrs['Span'] + @property + def src(self): + return self.init.dyna_attrs['rule'] + def __repr__(self): + return 'Rule(%s, %r)' % (self.idx, self.src) + + class Interpreter(object): def __init__(self): @@ -125,30 +141,26 @@ class Interpreter(object): self.agg_name = {} self.edges = defaultdict(set) self.updaters = defaultdict(list) - self.initializers = [] # data structures self.agenda = prioritydict() self.parser_state = '' - agg = self.agg_name - class dd(dict): - def __missing__(self, fn): - arity = int(fn.split('/')[-1]) - self[fn] = c = Chart(fn, arity, lambda: aggregator(agg[fn])) - return c - self.chart = dd() + def newchart(fn): + arity = int(fn.split('/')[-1]) + return Chart(fn, arity, lambda: aggregator(self.agg_name[fn])) + self.chart = ddict(newchart) + self.rules = ddict(Rule) self.errors = {} # misc self.trace = file(dotdynadir / 'trace', 'wb') def new_fn(self, fn, agg): - if fn in self.agg_name: - # check for aggregator conflict. - if self.agg_name[fn] != agg: - raise AggregatorConflict(fn, self.agg_name[fn], agg) - return - self.agg_name[fn] = agg + # check for aggregator conflict. + if fn not in self.agg_name: + self.agg_name[fn] = agg + if self.agg_name[fn] != agg: + raise AggregatorConflict(fn, self.agg_name[fn], agg) def collect_edges(self): """ @@ -161,8 +173,8 @@ class Interpreter(object): b.sort() b = tuple(b) edges[item].add((ruleix, b)) - for init in self.initializers: - init(emit=_emit) + for r in self.rules.values(): + r.init(emit=_emit) def dump_charts(self, out=sys.stdout): print >> out @@ -183,11 +195,15 @@ class Interpreter(object): print >> out, 'Errors' print >> out, '============' for item, (val, es) in self.errors.items(): - print >> out, 'because %r is %r:' % (item, val) + print >> out, 'because %r is %s:' % (item, _repr(val)) for e in es: print >> out, ' ', e print >> out + def dump_rules(self): + for i in sorted(self.rules, key=int): + print self.rules[i] + def build(self, fn, *args): # TODO: codegen should handle true/0 is True and false/0 is False if fn == "true/0": @@ -205,6 +221,65 @@ class Interpreter(object): term = self.chart[fn].insert(args, None) # don't know val yet. return term + def retract_item(self, item): + """ + For the moment we only correctly retract leaves. + + If you retract a non-leaf item, you run the risk of it being + rederived. In the case of cyclic programs the derivation might be the + same or different. + """ + + # and now, for something truely horrendous -- look up an item by it's + # string value! + items = {} + for c in self.chart.values(): + for i in c.intern.values(): + items[str(i)] = i + try: + item = items[item] + except KeyError: + print 'item not found.' + return + + print item + + while item.value: + print item.value + self.emit(item, item.value, None, sys.maxint, delete=True) + self.go() + + def retract_rule(self, idx): + "Retract rule and all of it's edges." + assert isinstance(idx, str) + + try: + rule = self.rules.pop(idx) + except KeyError: + print 'Rule %s not found.' % idx + return + + # Step 1: remove update handlers + print 'removing rule', rule + print ' removing updaters' + for u in rule.updaters: + print ' ', u.__doc__ + deleted = False + for hs in self.updaters.values(): + for i, h in enumerate(hs): + if u is h: + del hs[i] + assert not u in hs + deleted = True + assert deleted, 'should always find handler.' + deleted = False + + # Step 2: run initializer in delete mode + rule.init(emit=self.delete_emit) + + # Step 3; go! + self.go() + def go(self): "the main loop" @@ -220,7 +295,7 @@ class Interpreter(object): print >> trace, magenta % 'pop ', item, was = item.value - print >> trace, '(was: %r,' % (was,), + print >> trace, '(was: %s,' % (_repr(was),), try: now = item.aggregator.fold() @@ -229,7 +304,7 @@ class Interpreter(object): # TODO: Are we sure there is never a reason to requeue this item. continue - print >> trace, 'now: %r)' % (now,) + print >> trace, 'now: %s)' % (_repr(now),) if was == now: print >> trace, yellow % 'unchanged' @@ -260,8 +335,6 @@ class Interpreter(object): """ Passes update to relevant handlers. """ - - # XXX: fix for `?` prefix operator assert val is not None # store emissions, make sure all of them succeed before propagating @@ -297,18 +370,26 @@ class Interpreter(object): def new_updater(self, fn, handler): self.updaters[fn].append(handler) + i = handler.dyna_attrs['RuleIx'] + rule = self.rules[i] + rule.updaters.append(handler) + def new_initializer(self, init): - self.initializers.append(init) + i = init.dyna_attrs['RuleIx'] + rule = self.rules[i] + assert rule.init is None + rule.init = init + + def delete_emit(self, item, val, ruleix, variables): + self.emit(item, val, ruleix, variables, delete=True) def emit(self, item, val, ruleix, variables, delete): print >> self.trace, (red % 'delete' if delete else green % 'update'), \ '%s (val %s; curr: %s)' % (item, val, item.value) - if delete: item.aggregator.dec(val, ruleix, variables) else: item.aggregator.inc(val, ruleix, variables) - self.agenda[item] = 0 # everything is high priority def repl(self, hist): @@ -316,8 +397,15 @@ class Interpreter(object): repl.REPL(self, hist).cmdloop() def do(self, filename): - "Compile, load, and execute dyna code." + """ + Compile, load, and execute new dyna rules. + To support the REPL, we try do load these new rules in a transaction -- + if any rule in the newly loaded code is "bad," we simple reject the + addition of all these the new rules. + + A rule is bad if the compiler rejects it or it's initializer fails. + """ assert os.path.exists(filename) # for debuggging @@ -325,9 +413,6 @@ class Interpreter(object): print >> self.trace, magenta % 'Loading new code' print >> self.trace, yellow % h.read() - # TODO: loading new code should be atomic. if we fail for some reason we - # need to revert. - env = {'_initializers': [], '_updaters': [], '_agg_decl': {}, 'chart': self.chart, 'build': self.build, 'peel': peel, 'parser_state': None} @@ -358,17 +443,15 @@ class Interpreter(object): # add new updaters for fn, h in env['_updaters']: self.new_updater(fn, h) - # add new initializers for h in env['_initializers']: self.new_initializer(h) - + # accept the new parser state + self.parser_state = env['parser_state'] # process emits for e in emits: self.emit(*e, delete=False) - self.parser_state = env['parser_state'] - return self.go() def draw(self): @@ -407,18 +490,6 @@ def peel(fn, item): return item.args -def dynac(f, out): - return os.system('%s/dist/build/dyna/dyna -B python -o "%s" "%s"' % (dynahome, out, f)) - - - -def dump(code, filename='/tmp/tmp.dyna'): - "Write code to file." - with file(filename, 'wb') as f: - f.write(code) - return filename - - def main(): parser = ArgumentParser(description="The dyna interpreter!") diff --git a/src/Dyna/Backend/Python/repl.py b/src/Dyna/Backend/Python/repl.py index 460bd5e..34e60a1 100644 --- a/src/Dyna/Backend/Python/repl.py +++ b/src/Dyna/Backend/Python/repl.py @@ -1,8 +1,9 @@ import os, sys import cmd, readline from utils import blue, yellow, green, magenta, ip - +from chart import _repr from interpreter import AggregatorConflict +from config import dotdynadir import debug class REPL(cmd.Cmd, object): @@ -23,6 +24,15 @@ class REPL(cmd.Cmd, object): def prompt(self): return ':- ' #% self.lineno + def do_rules(self, _): + self.interp.dump_rules() + + def do_retract_rule(self, idx): + self.interp.remove_rule(idx) + + def do_retract_item(self, item): + self.interp.retract_item(item) + def do_exit(self, _): readline.write_history_file(self.hist) return -1 @@ -74,8 +84,10 @@ class REPL(cmd.Cmd, object): else: print 'Did not understand argument %r please use (on or off).' % args -# def do_debug(self, line): -# dynac_code(line, debug=True, run=False) + def do_debug(self, line): + with file(dotdynadir / 'tmp.dyna', 'wb') as f: + f.write(line) + debug.main(f.name) def do_query(self, line): @@ -83,15 +95,18 @@ class REPL(cmd.Cmd, object): print "Queries don't end with a dot." return - query = 'out(%s) dict= _VALUE is (%s), _VALUE.' % (self.lineno, line) - - print blue % query + query = 'out(%s) dict= %s.' % (self.lineno, line) self.default(query) - for (_, results) in self.interp.chart['out/1'][self.lineno,:]: - for result in results: - print result + try: + [(_, (_, results))] = self.interp.chart['out/1'][self.lineno,:] + except ValueError: + print 'No results.' + return + + for val, bindings in results: + print ' ', val, 'when', bindings print def default(self, line): @@ -116,7 +131,7 @@ class REPL(cmd.Cmd, object): return print '=============' for x, v in sorted(changed.items()): - print '%s := %r' % (x, v) + print '%s := %s' % (x, _repr(v)) print self.interp.dump_errors() diff --git a/src/Dyna/Backend/Python/utils.py b/src/Dyna/Backend/Python/utils.py index aa6d2fc..7fd086e 100644 --- a/src/Dyna/Backend/Python/utils.py +++ b/src/Dyna/Backend/Python/utils.py @@ -1,13 +1,31 @@ import re, os - from IPython.frontend.terminal.embed import InteractiveShellEmbed +from config import dynahome + + +# interactive IPython shell ip = InteractiveShellEmbed(banner1 = 'Dropping into IPython\n') + black, red, green, yellow, blue, magenta, cyan, white = \ map('\033[3%sm%%s\033[0m'.__mod__, range(8)) -dynahome = os.getenv('DYNAHOME', '.') +def dynac(f, out): + return os.system('%s/dist/build/dyna/dyna -B python -o "%s" "%s"' % (dynahome, out, f)) + + +def notimplemented(*_,**__): + raise NotImplementedError + + +class ddict(dict): + def __init__(self, f): + self.f = f + super(ddict, self).__init__() + def __missing__(self, x): + self[x] = y = self.f(x) + return y def parse_sexpr(e): @@ -62,89 +80,6 @@ def read_anf(e): result) -def notimplemented(*_,**__): - raise NotImplementedError - - -from heapq import heapify, heappush, heappop - -class prioritydict(dict): - """Dictionary that can be used as a priority queue. - - Keys of the dictionary are items to be put into the queue, and values - are their respective priorities. All dictionary methods work as expected. - The advantage over a standard heapq-based priority queue is - that priorities of items can be efficiently updated (amortized O(1)) - using code as 'thedict[item] = new_priority.' - - The 'smallest' method can be used to return the object with lowest - priority, and 'pop_smallest' also removes it. - - The 'sorted_iter' method provides a destructive sorted iterator. - - This implemented is based on: - - Matteo Dell'Amico's implementation - http://code.activestate.com/recipes/522995-priority-dict-a-priority-queue-with-updatable-prio/ - - which is based on David Eppstein's implementation - http://code.activestate.com/recipes/117228/ - - """ - - def __init__(self, *args, **kwargs): - super(prioritydict, self).__init__(*args, **kwargs) - self._rebuild_heap() - - def _rebuild_heap(self): - self._heap = [(v, k) for k, v in self.iteritems()] - heapify(self._heap) - - def smallest(self): - """ - Return the item with the lowest priority. - - Raises IndexError if the object is empty. - """ - - heap = self._heap - v, k = heap[0] - while k not in self or self[k] != v: - heappop(heap) - v, k = heap[0] - return k - - def pop_smallest(self): - """ - Return the item with the lowest priority and remove it. - - Raises IndexError if the object is empty. - """ - - heap = self._heap - v, k = heappop(heap) - while k not in self or self[k] != v: - v, k = heappop(heap) - del self[k] - return k - - def __setitem__(self, key, val): - # We are not going to remove the previous value from the heap, - # since this would have a cost O(n). - - super(prioritydict, self).__setitem__(key, val) - - if len(self._heap) < 2 * len(self): - heappush(self._heap, (val, key)) - else: - # When the heap grows larger than 2 * len(self), we rebuild it - # from scratch to avoid wasting too much memory. - self._rebuild_heap() - - setdefault = None - update = None - - def parse_attrs(fn): attrs = dict(re.findall('\s*(\S+):\s*(.*)\s*\n', fn.__doc__.strip())) if 'Span' in attrs: -- 2.50.1