From 9f5a30bfca132762a88ed7f1afe5a5b08e2b2643 Mon Sep 17 00:00:00 2001 From: Tim Vieira Date: Fri, 5 Jul 2013 13:06:40 -0400 Subject: [PATCH] added `with_key` infix operator for (Issue #29 Backpointers) and argument disposition for `$key/1`. Removed previous version of `argmin=/argmax=`. --- examples/dijkstra-backpointers.dyna | 8 +++---- examples/matrixops.dyna | 2 +- examples/ptb.dyna | 9 ++++---- src/Dyna/Backend/Python/Backend.hs | 2 +- src/Dyna/Backend/Python/aggregator.py | 4 ++-- src/Dyna/Backend/Python/interpreter.py | 32 +++++++++++--------------- src/Dyna/Backend/Python/term.py | 12 +++++++++- src/Dyna/Term/SurfaceSyntax.hs | 8 +++++++ 8 files changed, 45 insertions(+), 32 deletions(-) diff --git a/examples/dijkstra-backpointers.dyna b/examples/dijkstra-backpointers.dyna index 1d89948..b550665 100644 --- a/examples/dijkstra-backpointers.dyna +++ b/examples/dijkstra-backpointers.dyna @@ -1,7 +1,7 @@ % single source shortest path with optimal path extraction. -path(start) argmin= [0, start]. -path(B) argmin= [path(A) + edge(A,B), A]. -goal argmin= [path(end), end]. +path(start) min= 0 with_key start. +path(B) min= path(A) + edge(A,B) with_key A. +goal min= path(end) with_key end. % expensive path edge("a","b") := 1. @@ -18,7 +18,7 @@ end := "d". % extract cheapest path by following backpointers from each vertex. bestpath(start) := [start]. -bestpath(V) := U is $key(&path(V)), [V | bestpath(U)] for V != start. +bestpath(V) := U is $key(path(V)), [V | bestpath(U)] for V != start. % the optimal path is the one from the `end`. optimalpath = reverse(bestpath(end)). diff --git a/examples/matrixops.dyna b/examples/matrixops.dyna index 10a4186..4dc21d5 100644 --- a/examples/matrixops.dyna +++ b/examples/matrixops.dyna @@ -1,5 +1,5 @@ % A and B are names of matrices -times(A, B, I, J) += m(A, I, K) * m(B, K, J) whenever _ is product(A,B). +times(A, B, I, J) += m(A, I, K) * m(B, K, J) for _ is product(A,B). m(P, I, J) += shape(A,R,C), % pair(R, C) is shape(A), shape(B,C,_), % pair(C, D) is shape(B), diff --git a/examples/ptb.dyna b/examples/ptb.dyna index a05bd99..46ec6bc 100644 --- a/examples/ptb.dyna +++ b/examples/ptb.dyna @@ -61,12 +61,13 @@ b([X,Y,Z|Xs]) := [X, b(Y), b([&'@'(X), Z|Xs])]. b([X,Y,Z]) := [X,b(Y),b(Z)]. % CKY parser -phrase(X,I,K) argmax= [phrase(Y,I,J) * phrase(Z,J,K) * p(X,Y,Z), [[Y,I,J], [Z,J,K]]]. -phrase(X,I,K) argmax= [phrase(Y,I,K) * p(X,Y), [[Y,I,K]]]. -phrase(X,I,I+1) argmax= [1, X] for [I,X] in enumerate(sentence). +phrase(X,I,K) max= phrase(Y,I,J) * phrase(Z,J,K) * p(X,Y,Z) with_key [[Y,I,J], [Z,J,K]]. +phrase(X,I,K) max= phrase(Y,I,K) * p(X,Y) with_key [[Y,I,K]]. +phrase(X,I,I+1) max= 1 with_key X + for [I,X] in enumerate(sentence). % backpointers -bk(X,I,K) = $key(&phrase(X,I,K)). +bk(X,I,K) = $key(phrase(X,I,K)). % extract path from backpointers path(X,I,K) := W is bk(X,I,K), W. diff --git a/src/Dyna/Backend/Python/Backend.hs b/src/Dyna/Backend/Python/Backend.hs index 00fc65d..a6d194e 100644 --- a/src/Dyna/Backend/Python/Backend.hs +++ b/src/Dyna/Backend/Python/Backend.hs @@ -49,7 +49,7 @@ import Text.PrettyPrint.Free aggrs :: S.Set String aggrs = S.fromList - [ "max=" , "min=", "argmax=", "argmin=" + [ "max=" , "min=" , "+=" , "*=" , "and=" , "or=" , "&=" , "|=" , ":-" diff --git a/src/Dyna/Backend/Python/aggregator.py b/src/Dyna/Backend/Python/aggregator.py index 39a6ba4..d1cbe33 100644 --- a/src/Dyna/Backend/Python/aggregator.py +++ b/src/Dyna/Backend/Python/aggregator.py @@ -232,8 +232,8 @@ defs = { 'set=': set_equals, 'bag=': bag_equals, 'mean=': mean_equals, - 'argmax=': maxwithkey_equals, - 'argmin=': minwithkey_equals, +# 'argmax=': maxwithkey_equals, +# 'argmin=': minwithkey_equals, } def aggregator(name, term): diff --git a/src/Dyna/Backend/Python/interpreter.py b/src/Dyna/Backend/Python/interpreter.py index 3d53092..806e958 100644 --- a/src/Dyna/Backend/Python/interpreter.py +++ b/src/Dyna/Backend/Python/interpreter.py @@ -194,7 +194,6 @@ class Interpreter(object): self.do(self.dynac_code(code), initialize=False) def new_fn(self, fn, agg): - # check for aggregator conflict. if self.agg_name[fn] is None: self.agg_name[fn] = agg @@ -289,12 +288,6 @@ class Interpreter(object): print >> out, ' %s' % (e) print >> out -# for item, (val, es) in self.error.items(): -# print >> out, 'because %r is %s:' % (item, _repr(val)) -# for e, h in es: -# if h is not None: -# r = h.rule -# print >> out, ' %s\n in rule %s\n %s' % (e, r.span, r.src) print >> out def dump_rules(self): @@ -318,10 +311,14 @@ class Interpreter(object): return Cons(*args) if fn == 'nil/0': return Nil + + if fn == '$key/1': + self.new_fn(fn, '=') + if fn not in self.agg_name: - # item has no aggregator (e.g purely structural stuff) -- what - # happens if we add one later? + # item has no aggregator and this is the first time we're seeing it. self.new_fn(fn, None) + return self.chart[fn].insert(args) # def retract_item(self, item): @@ -396,20 +393,17 @@ class Interpreter(object): item.value = now continue + if hasattr(now, 'fn') and now.fn == 'with_key/2': + val, key = now.args + now = val + dkey = self.build('$key/1', item) + self.delete_emit(dkey, dkey.value, None, None) + self.emit(dkey, key, None, None, delete=False) + if was == now: continue - # aggregator with special key - if hasattr(item.aggregator, 'key'): - key = self.build('$key/1', item) - if key.aggregator is None: - from aggregator import aggregator - key.aggregator = aggregator('=', key) - self.delete_emit(key, key.value, None, None) - self.emit(key, item.aggregator.key, None, None, delete=False) - - was_error = False if item in error: # clear error was_error = True diff --git a/src/Dyna/Backend/Python/term.py b/src/Dyna/Backend/Python/term.py index 1c4a487..8b36489 100644 --- a/src/Dyna/Backend/Python/term.py +++ b/src/Dyna/Backend/Python/term.py @@ -41,7 +41,17 @@ class Term(object): def __setstate__(self, state): (self.fn, self.args, self.value, self.aggregator) = state - __add__ = __sub__ = __mul__ = notimplemented + def __add__(self, _): + raise TypeError("Can't subtract terms.") + + def __sub__(self, _): + raise TypeError("Can't add terms.") + + def __mul__(self, _): + raise TypeError("Can't multiply terms.") + + def __div__(self, _): + raise TypeError("Can't divide terms.") class Cons(Term): diff --git a/src/Dyna/Term/SurfaceSyntax.hs b/src/Dyna/Term/SurfaceSyntax.hs index 1d5a3b2..38753cc 100644 --- a/src/Dyna/Term/SurfaceSyntax.hs +++ b/src/Dyna/Term/SurfaceSyntax.hs @@ -79,6 +79,8 @@ defOperSpec = foldr (\(k,v) -> mapInOrCons k v) def more , ("in" ,[(4,PFIn AssocNone ) ]) + , ("with_key" ,[(4,PFIn AssocNone ) ]) + , ("<=" ,[(4,PFIn AssocNone ) ]) , ("<" ,[(4,PFIn AssocNone ) ]) , ("=" ,[(4,PFIn AssocNone ) ]) @@ -171,6 +173,9 @@ disposTab_prologish t = DisposTab s a , (("pair" ,2),(SDQuote,[ADEval,ADEval])) , (("true" ,0),(SDQuote,[])) , (("false",0),(SDQuote,[])) + -- key + , (("$key" ,1),(SDEval,[ADQuote])) + , (("with_key",2),(SDQuote,[ADEval, ADQuote])) -- lists , (("nil", 0),(SDQuote,[])) , (("cons", 2),(SDQuote,[ADEval,ADEval])) @@ -201,6 +206,9 @@ disposTab_dyna t = DisposTab s a -- lists , (("nil", 0),(SDQuote,[])) , (("cons", 2),(SDQuote,[ADEval,ADEval])) + -- key + , (("$key" ,1),(SDEval,[ADQuote])) + , (("with_key",2),(SDQuote,[ADEval, ADQuote])) ] ------------------------------------------------------------------------}}} -- 2.50.1