From 0f2fcc40d37e0b185695341ecf972acf5e240a16 Mon Sep 17 00:00:00 2001 From: timv Date: Fri, 30 Nov 2012 13:09:03 -0500 Subject: [PATCH] anfviz - produces html output for an entire dyna program. added examples directory and a few example dyna programs. BUGFIX (minor) in normalize parse pretty printer (handled numbers in the result incorrectly). --- bin/anfviz.py | 209 ++++++++++++++++++++-------- examples/cky.dyna | 4 + examples/fib.dyna | 5 + examples/markov2.dyna | 1 + src/Dyna/Analysis/NormalizeParse.hs | 2 +- 5 files changed, 164 insertions(+), 57 deletions(-) mode change 100644 => 100755 bin/anfviz.py create mode 100644 examples/cky.dyna create mode 100644 examples/fib.dyna create mode 100644 examples/markov2.dyna diff --git a/bin/anfviz.py b/bin/anfviz.py old mode 100644 new mode 100755 index 49890e4..92877e8 --- a/bin/anfviz.py +++ b/bin/anfviz.py @@ -1,17 +1,19 @@ #!/usr/bin/env python """ -Generates a visual representation of a Dyna rule graphviz after the +Generates a visual representation of a Dyna program rules after the normalization process. - -TODO: to be useful as a script we should process entire *.dyna files. - """ +# TODO: add a directory of sample Dyna programs to repo (Fibonacci, CKY, +# second-order markov, shortest-path) + import re, os, sys from collections import defaultdict, namedtuple -from os.path import abspath +from pprint import pprint -red = '\033[31m%s\033[0m' + +black, red, green, yellow, blue, magenta, cyan, white = \ + map('\033[3%sm%%s\033[0m'.__mod__, range(8)) def convert(f): @@ -24,12 +26,10 @@ def convert(f): return h.read() -def toANF(code, f): +def toANF(code, f='/tmp/tmp.dyna'): with file(f, 'wb') as tmp: tmp.write(code) - anf = convert(tmp.name) - print anf - return evalthings(parse_sexpr(anf)) + return convert(tmp.name) # by George Sakkis (gsakkis at rutgers.edu) @@ -61,13 +61,28 @@ def parse_sexpr(e): def evalthings(t): if isinstance(t, str): try: - return eval(t) + return eval(t) # FIXME: dangerous way to do this. except: return t else: return [evalthings(x) for x in t] +def read_anf(e): + x = evalthings(parse_sexpr(e)) + + def g(x): + return [(var, val[0], val[1:]) for var, val in x] + + for (agg, head, side, evals, unifs, [_,result]) in x: + yield (agg, + head, + side[1:], + g(evals[1:]), + g(unifs[1:]), + result) + + Edge = namedtuple('Edge', 'head label body') @@ -91,8 +106,8 @@ class Hypergraph(object): return e def render(self, name): - dot = abspath('%s.dot' % name) - png = abspath('%s.png' % name) + dot = '%s.dot' % name + png = '%s.png' % name # write the dot file so that we can pass it to graphviz with file(dot, 'wb') as f: @@ -125,31 +140,91 @@ class Hypergraph(object): print >> f, '}' + print 'wrote', dot, 'compiling...' + # run graphviz to produce image - os.system('(dot -Tpng %s > %s)' % (dot, png)) + assert 0 == os.system('(dot -Tpng %s > %s)' % (dot, png)), 'graphviz failed.' + print 'created', png -def goo(x): - for var, val in x: - op, args = val[0], val[1:] - yield var, op, args + return png + def show(self, name='/tmp/tmp'): + os.system('gnome-open %s 2>/dev/null' % self.render(name)) -def circuit(anf): + def get_function(self, x): + """ + String of symbolic representation of ``x``, a variable or function, in + this expresion graph. + """ + + if isconst(x): + return str(x) + + elif not isinstance(x, Edge): + if x not in self.incoming or not self.incoming[x]: # input variable + return x + [e] = self.incoming[x] # only one incoming edge per variable in this type of graph + return self.get_function(e) + + else: + return '%s(%s)' % (x.label, ', '.join(map(self.get_function, x.body))) + + def toposort(self, root): + visited = set() + + def t(v): + if v not in visited: + visited.add(v) + for e in self.incoming[v]: + for u in e.body: + for b in t(u): # "yield from" recursive call + yield b + yield v + + return t(root) + + def plan(self, root): + + incoming = self.incoming + + [e] = incoming[root] + + q = [e] + c = {e: 0 for e in self.edges} - [(agg, head, side, evals, unifs, result)] = anf + while q: + e = q.pop() + print e - side = set(side[1:]) + c[e] = 1 - [_, result] = result + for c in (c for b in e.body for c in incoming[b]): # edge->node->edge + + # is edge traversable? + + q.append(c) + + pprint(e) + + +def isconst(x): + return isinstance(x, (float, int)) + + + +def circuit(anf): + + (agg, head, side, evals, unifs, result) = anf g = Hypergraph() - for var, op, args in goo(evals[1:]): + for var, op, args in evals: #if not args: args, op = [op], 'const' # todo: useless special case? g.edge(head=var, label=op, body=args) - for var, op, args in goo(unifs[1:]): - e = g.edge(head=var, label='& %s(%s)' % (op, ','.join(map(str, args))), body=args) + for var, op, args in unifs: +# e = g.edge(head=var, label='& %s(%s)' % (op, ','.join(map(str, args))), body=args) + e = g.edge(head=var, label=op, body=args) # distiguish unif edges g.sty[e].update({'style': 'filled', 'fillcolor': 'grey'}) @@ -158,58 +233,80 @@ def circuit(anf): for x in g.nodes: if not g.incoming[x]: g.sty[x].update({'style': 'filled', 'fillcolor': 'yellow'}) + + if isinstance(x,str) and (x.isupper() or x.startswith('_$')): # variables are bold + g.sty[x].update({'penwidth': '3'}) + if not g.outgoing[x]: - g.sty[x].update({'style': 'filled', 'fillcolor': 'red'}) + g.sty[x].update({'style': 'filled', 'fillcolor': 'salmon'}) if x in side: - g.sty[x].update({'style': 'filled', 'fillcolor': 'green'}) + g.sty[x].update({'style': 'filled', 'fillcolor': 'olivedrab2'}) # variables which are projected-out to the head -# g.sty[head].update({'penwidth': '3'}) - g.sty[head].update({'style': 'filled', 'fillcolor': 'blue'}) + g.sty[head].update({'style': 'filled', 'fillcolor': 'lightblue'}) + + g.head = head + g.result = result + g.inputs = [x for x in g.nodes if not g.incoming[x]] + g.outputs = [x for x in g.nodes if not g.outgoing[x]] + g.intermediate = [x for x in g.nodes if g.incoming[x] and g.outgoing[x]] + g.side = side return g -def test(): +def main(dynafile): + + with file(dynafile) as f: + code = f.read() + + d = dynafile + '.d' + os.system('mkdir -p %s' % d) - examples = { - # min-cost path in a second-order markov model - 'markov2': 'path(pair(Y,Z),V) min= path(pair(X,Y),U) + cost(X,Y,Z,U,V).', + with file(d + '/index.html', 'wb') as html: - # Fibonacci numbers: note `X-1` is evaluated even though `f` generally - # doesn't require it's arguments quoted - 'fib': 'f(X) := f(X-1) + f(X-2).', + print >> html, '' - # part of the cky program - 'cky': 'phrase(X,I,K) += phrase(Y,I,J) * phrase(Z,J,K) * rewrite(X,Y,Z) * f(X,X).', + print >> html, '

%s

' % dynafile - # example which build a lot of structure. - 'structure': 'x :- g(Y, f(X, h(Z, Y)), e(q(X, Y))).', + print >> html, '

Dyna source

' + print >> html, '
\n%s\n
' % code.strip() - # monster - 'monster': ('f(X,Y) += (g(X,"string",d) - h(X,X,Y) - c)^2 + f(Y,Z)/exp(3.0)' - ' whenever ?c, (d < 10), e(f(h(X)), g(X)).') + anf = toANF(code) - } + print >> html, '

ANF

' + print >> html, '
\n%s\n
' % anf.strip() - if not sys.argv[1:] or not all(x in examples for x in sys.argv[1:] if x != 'all'): - print 'usage:\n\t%s [%s]+' % (sys.argv[0], '|'.join(examples.keys())) - return + print >> html, '

Hyperedge templates

' - os.system('rm -f /tmp/*.png') + rules = [] - for name in (examples if 'all' in sys.argv[1:] else sys.argv[1:]): - print red % name + for i, x in enumerate(read_anf(anf)): + g = circuit(x) - code = examples[name] - print code + rules.append(g) - g = circuit(toANF(code, '/tmp/' + name + '.dyna')) + g.render(dynafile + '.d/rule-%s' % i) - g.render('/tmp/' + name) + png = 'rule-%s.png' % i # path relative (to html file) - os.system('gnome-open /tmp/*.png 2>/dev/null') + print >> html, '
' % png + + print 'wrote', html.name + + if argv.browser: + os.system('gnome-open %s 2>/dev/null >/dev/null' % html.name) if __name__ == '__main__': - test() + + from argparse import ArgumentParser + p = ArgumentParser(description=__doc__) + p.add_argument('input', help='Path to Dyna source file.') + p.add_argument('-x', dest='browser', action='store_false') + + argv = p.parse_args() + main(argv.input) diff --git a/examples/cky.dyna b/examples/cky.dyna new file mode 100644 index 0000000..f98aea9 --- /dev/null +++ b/examples/cky.dyna @@ -0,0 +1,4 @@ +% CKY-like parsing +phrase(X,I,K) += phrase(Y,I,K) * rewrite(X,Y). +phrase(X,I,K) += phrase(Y,I,J) * phrase(Z,J,K) * rewrite(X,Y,Z). + diff --git a/examples/fib.dyna b/examples/fib.dyna new file mode 100644 index 0000000..4ee625e --- /dev/null +++ b/examples/fib.dyna @@ -0,0 +1,5 @@ +% Fibonacci numbers +f(1) := 1+0 . +f(2) := 1+0 . +f(X) := f(X-1) + f(X-2). + diff --git a/examples/markov2.dyna b/examples/markov2.dyna new file mode 100644 index 0000000..cb58f36 --- /dev/null +++ b/examples/markov2.dyna @@ -0,0 +1 @@ +path(pair(Y,Z),V) min= path(pair(X,Y),U) + cost(X,Y,Z,U,V). diff --git a/src/Dyna/Analysis/NormalizeParse.hs b/src/Dyna/Analysis/NormalizeParse.hs index 89c32c8..a9909f1 100644 --- a/src/Dyna/Analysis/NormalizeParse.hs +++ b/src/Dyna/Analysis/NormalizeParse.hs @@ -302,7 +302,7 @@ pp ((Rule h a e result), AS {as_evals = evals, as_unifs = unifs}) = , parens $ text "side" <+> (valign $ map (text.show) e) , parens $ text "evals" <+> (q evals) , parens $ text "unifs" <+> (q unifs) - , parens $ text "result" <+> (text $ show result) + , parens $ text "result" <+> (p result) ] where p (UTerm (TFunctor fn args)) = parens $ hcat $ punctuate (text " ") $ (pretty fn : (map p args)) -- 2.50.1