From 806abd8dca71f95b05756cef0d9b79257ff8b9a4 Mon Sep 17 00:00:00 2001 From: timv Date: Tue, 11 Dec 2012 16:04:36 -0500 Subject: [PATCH] stdlib: "Papa" example works. --- bin/stdlib.py | 276 ++++++++++++++++++++++++++++---------------------- 1 file changed, 155 insertions(+), 121 deletions(-) diff --git a/bin/stdlib.py b/bin/stdlib.py index 8c9e98d..29ddb19 100644 --- a/bin/stdlib.py +++ b/bin/stdlib.py @@ -27,6 +27,7 @@ Call indirection import math, operator from collections import defaultdict, Counter +from utils import red, green, blue, magenta # Call indirection tables defines mathematical operators and the like. @@ -34,86 +35,31 @@ call = {'*/2': operator.mul, '//2': operator.div, '-/2': operator.sub, '+/2': operator.add, - 'log': math.log, - 'exp': math.exp, - '^/2': math.pow} - - -# Update handler indirection -- a true hack. Allow us to have many handlers on -# the same functor/arity - -# TODO: fuse update handlers instead of dispatching to each one independently. - -def register(functor_arity): - """ - Decorator for registering update handlers. Used by update dispatcher. - - Note: registration is with a global/mutable table. - - For testing purposes clear current handlers - >>> register.handlers.clear() - - >>> @register("test") - ... def _(H, V): - ... return 'OK', H, V - ... - >>> [h] = register.handlers['test'] - >>> h("head", "value") - ('OK', 'head', 'value') - - """ - - def wrap(handler): - register.handlers[functor_arity].append(handler) - # you can't call these guys directly. Must go thru handler - # indirection table - return None - - return wrap - -# NOTE: global & mutable -register.handlers = defaultdict(list) - - -def update_dispatcher(fn, idx, value): - """ - Passes update to relevant handlers. - """ - print 'dispatching update', (fn, idx, value) - for handler in register.handlers[fn]: - print 'sending update to handler' - handler(idx, value) + '-/1': operator.neg, -def emit(item, value): - (fn, idx) = item - row = chart[fn].data[idx] - args = row[:-1] - was = row[-1] +# '~/1': operator.inv, # differs +# '|/1': operator.or_, +# '&/2': operator.and_, - print 'emit: %s %s%s <== %s (current value: %s)' % (item, fn, args, value, was) - aggregator[item][value] += 1 # timv: retract passes in -1? - agenda.append(item) + # comparisons + '/2': operator.gt, + '>=/2': operator.ge, + '!=/2': operator.ne, + '==/2': operator.eq, +# '<>/2': operator.rshift, -def peel(fn, (fa, idx)): - """ - Lookup `idx` in the intern table. Asserts that idx matches - `functor_arity`. Returns arguments of term as a arity-tuple of intern idxs and - constants. - """ - assert fa == fn - return chart[fn].data[idx][:-1] # minus value - - -def build(fn, *args): + 'mod/1': operator.mod, + 'abs/1': operator.abs, + 'log': math.log, + 'exp': math.exp, - idx = chart[fn].lookup(*args) # lookup doesn't require value? - - if idx is None: - idx = chart[fn].insert(args + (None,)) # don't know value yet. - - return (fn, idx) + '**/2': math.pow, + '^/2': math.pow} # differs from python # TODO: as soon as we have safe names for these things we can get rid of this. @@ -153,22 +99,30 @@ class Chart(object): nonslice = [(i, val) for i, val in enumerate(item) if not isinstance(val, slice)] slices = [i for i, val in enumerate(item) if isinstance(val, slice)] - for row in self.data.itervalues(): # XXX: very inefficient + for row in self.data.values(): # XXX: very inefficient + if row[-1] is None: + continue if all(row[i] == val for i, val in nonslice): yield tuple(row[i] for i in slices) def lookup(self, *args): "find index for these args" - assert len(args) == self.ncols - 1 # XXX: lookup doesn't want value? + assert len(args) == self.ncols - 1 # XXX: lookup doesn't want val? + args = list(args) for idx, row in self.data.iteritems(): # XXX: very inefficient if row[:-1] == args: return idx # stop on first def update(self, ix, args): "Update chart" + assert len(args) == self.ncols and isinstance(args, list) self.data[ix] = args def insert(self, args): + + # debug: simple integrity check + assert self.lookup(*args[:-1]) is None, '%s already in chart' % (args,) + idx = self.next_id() self.update(idx, list(args)) return idx @@ -188,8 +142,8 @@ def pretty(item): fn = ''.join(fn.split('/')[:-1]) # drop arity from name. return '%s%s' % (fn, tuple(args)) # TODO: need to recurse. -def prettify(x): +def prettify(x): if isinstance(x, tuple): return pretty(x) elif isinstance(x, list): @@ -200,80 +154,160 @@ def prettify(x): raise ValueError("Don't know what to do with %r" % x) -aggregator = defaultdict(Counter) -agenda = [] +# Update handler indirection -- a true hack. Allow us to have many handlers on +# the same functor/arity +# TODO: fuse update handlers instead of dispatching to each one independently. -def run_agenda(): - "the main loop" - while agenda: - item = agenda.pop() - new = aggregate(item) # compute new value for item - propagate(item, new) +def register(functor_arity): + """ + Decorator for registering update handlers. Used by update dispatcher. + Note: registration is with a global/mutable table. -def aggregate(item): - print 'aggregate:', pretty(item), aggregator[item], + For testing purposes clear current handlers + >>> register.handlers.clear() - val = 0.0 - for k,v in aggregator[item].iteritems(): - val += k*v # value*multiplicity; TODO: use correct aggregator + >>> @register("test") + ... def _(H, V): + ... return 'OK', H, V + ... + >>> [h] = register.handlers['test'] + >>> h("head", "val") + ('OK', 'head', 'val') - print 'result:', val + """ - return val + def wrap(handler): + register.handlers[functor_arity].append(handler) + # you can't call these guys directly. Must go thru handler + # indirection table + return None + return wrap -def delete(item, val): - print 'TODO: implement deletion.' +# NOTE: global & mutable +register.handlers = defaultdict(list) + + +def update_dispatcher((fn, idx), val): + """ + Passes update to relevant handlers. + """ + print 'dispatch', pretty((fn, idx)), '=', val + for handler in register.handlers[fn]: + print 'handler' + handler((fn, idx), val) + + +def peel(fn, (fa, idx)): + """ + Lookup `idx` in the intern table. Asserts that idx matches + `functor_arity`. Returns arguments of term as a arity-tuple of intern idxs and + constants. + """ + assert fa == fn + return chart[fn].data[idx][:-1] # minus val +def build(fn, *args): + idx = chart[fn].lookup(*args) # lookup doesn't require val? + if idx is None: + idx = chart[fn].insert(args + (None,)) # don't know val yet. + return (fn, idx) -def propagate(item, now): - fn, idx = item +_delete = False - was = chart[fn].data[idx][-1] # last is value +def emit(item, val): + (fn, idx) = item + row = chart[fn].data[idx] + was = row[-1] - print 'propagate: %-30s was %s now %s' % (pretty(item), was, now) + print (red if _delete else green) \ + % 'emit %s (val %s; was: %s)' % (pretty(item), val, was) - if was == now: - return + if _delete: + aggregator[item][val] -= 1 + else: + aggregator[item][val] += 1 - if was is not None: - delete(item, was) + agenda.add(item) - chart[fn].data[idx][-1] = now - aggregator[item][now] += 1 - # enqueue work to the agenda - agenda.append(item) +aggregator = defaultdict(Counter) +agenda = set() + + +def run_agenda(): + "the main loop" + while agenda: + (fn, idx) = item = agenda.pop() + + print + print 'pop', pretty(item) + + was = chart[fn].data[idx][-1] # last cell is val + + if was is not None: + delete(item, was) + + now = aggregate(item) # compute new val for item + + print ' was %s now %s' % (was, now) + + if was == now: + print ' unchanged' + return + + chart[fn].data[idx][-1] = now + + update_dispatcher(item, now) + + +def aggregate(item): + print ' aggregate:', pretty(item), aggregator[item], + val = 0.0 + for k,v in aggregator[item].iteritems(): + val += k*v # val*multiplicity; TODO: use correct aggregator + print 'result:', val + return val + + +def delete(item, val): + # XXX: very ugly handling of deletion + global _delete + _delete = True + update_dispatcher(item, val) + _delete = False + def papa_example(): map(chart['rewrite/3'].insert, - [( "S", "S", ".", 1), - ( "S", "NP", "VP", 1), - ("NP", "Det", "N", 1), - ("NP", "NP", "PP", 1), - ("VP", "V", "NP", 1), - ("VP", "VP", "PP", 1), - ("PP", "P", "NP", 1)]) + [( "S", "S", ".", 1.), + ( "S", "NP", "VP", 1.), + ("NP", "Det", "N", 1.), + ("NP", "NP", "PP", 1.), + ("VP", "V", "NP", 1.), + ("VP", "VP", "PP", 1.), + ("PP", "P", "NP", 1.)]) map(chart['rewrite/2'].insert, - [( "NP", "Papa", 1), - ( "N", "caviar", 1), - ( "N", "spoon", 1), - ( "V", "ate", 1), - ( "P", "with", 1), - ("Det", "the", 1), - ("Det", "a", 1)]) + [( "NP", "Papa", 1.), + ( "N", "caviar", 1.), + ( "N", "spoon", 1.), + ( "V", "ate", 1.), + ( "P", "with", 1.), + ("Det", "the", 1.), + ("Det", "a", 1.)]) for i, word in enumerate('Papa ate the caviar with a spoon .'.split()): idx = chart['phrase/3'].insert((word, i, i + 1, None)) - propagate(('phrase/3', idx), 1) + + emit(('phrase/3', idx), 1.0) -- 2.50.1