From 96ef5f25163a04ba13142555cf90a9289c38fbce Mon Sep 17 00:00:00 2001 From: timv Date: Tue, 18 Dec 2012 14:46:57 -0500 Subject: [PATCH] REPL uses dyna compiler to get plans; suppports (to some extent) the addition of new rules (deletion or rules should be pretty easy to add). improvements to code load and compile. Python codegen no longer uses call indirection table. 'and_equals' and 'or_equals' use python 'and' and 'or' instead of python '&' and '|', which are bit-twiddling operations. --- bin/defn.py | 58 +++++---------- bin/interpreter.py | 142 +++++++++++++++--------------------- bin/utils.py | 3 + src/Dyna/Analysis/ANF.hs | 6 +- src/Dyna/Backend/Python.hs | 55 ++++++++++++-- src/Dyna/ParserHS/Parser.hs | 4 + 6 files changed, 136 insertions(+), 132 deletions(-) diff --git a/bin/defn.py b/bin/defn.py index df5e4b6..23d189e 100644 --- a/bin/defn.py +++ b/bin/defn.py @@ -23,43 +23,10 @@ Call indirection import math, operator from collections import defaultdict, Counter +from utils import red -# Call indirection tables defines mathematical operators and the like. -call = {'*/2': operator.mul, - '//2': operator.div, - '-/2': operator.sub, - '+/2': operator.add, - '-/1': operator.neg, - - '~/1': lambda x: not x, - '|/1': lambda x,y: x or y, - '&/2': lambda x,y: x and y, - - 'true/0': lambda: True, - 'false/0': lambda: False, - - # comparisons - '/2': operator.gt, - '>=/2': operator.ge, - '!=/2': operator.ne, - '==/2': operator.eq, - -# '<>/2': operator.rshift, - - 'mod/1': operator.mod, - 'abs/1': operator.abs, - 'log': math.log, - 'exp': math.exp, - - '**/2': math.pow, - '^/2': math.pow} # differs from python - - -def agg_bind(agg_decl, table): +def agg_bind(agg, agg_decl, table): """ Bind declarations (map functor->string) to table (storing values) and aggregator definition (the fold funciton, which gets executed). @@ -88,12 +55,13 @@ def agg_bind(agg_decl, table): def and_equals(item): s = [k for k, m in table[item].iteritems() if m > 0] if len(s): - return reduce(operator.and_, s) + return reduce(lambda x,y: x and y, s) def or_equals(item): s = [k for k, m in table[item].iteritems() if m > 0] if len(s): - return reduce(operator.or_, s) + return reduce(lambda x,y: x or y, s) + # map names to functions agg_defs = { @@ -107,8 +75,18 @@ def agg_bind(agg_decl, table): } # commit functors to an aggregator definition to avoid unnecessary lookups. - agg = {} for fn in agg_decl: - agg[fn] = agg_defs[agg_decl[fn]] - return agg +# if agg_decl[fn] == ':=': # XXX: leaves previous version??? +# raise NotImplementedError("aggregator ':=' not implemented yet.") +# continue + + if fn in agg: + if agg[fn].__name__ != agg_defs[agg_decl[fn]].__name__: + print red % 'conflicting aggregators. %s and %s' % (agg[fn], agg_defs[agg_decl[fn]]) + + # XXX: ignores conflicts with aggregator, might lead to confusion. + + # TODO: as soon as we ':=' we probably won't want this behavior and we + # can restor the assertion that aggregator hasn't changed. + agg[fn] = agg_defs[agg_decl[fn]] diff --git a/bin/interpreter.py b/bin/interpreter.py index 470c808..4832800 100644 --- a/bin/interpreter.py +++ b/bin/interpreter.py @@ -1,12 +1,35 @@ #!/usr/bin/env python +""" + + - "initializers" aren't just initializers, they are the fully-naive bottom-up + inference rules. + + - TODO: routines from probing the chart. + + - XXX: maybe the chart should store pretty printed term and a reference to the + aggregator (each item get's its own aggregator to avoid a hash lookup). + + - XXX: should we store value and aggregators separate from others columns? that + is, separate the chart and intern table. + + - TODO: should probably make a Term object. + + - XXX: we should probably fuse update handlers instead of dispatching to each + one independently. + + - TODO: deletion of a rule should be running the initializer for the rule in + deletion mode. + +""" + #from debug import ultraTB2; ultraTB2.enable() #from debug import saverr; saverr.enable(editor=True) import os, sys from collections import defaultdict, Counter from argparse import ArgumentParser -from utils import red, green, blue, magenta +from utils import ip, red, green, blue, magenta from defn import agg_bind, call @@ -15,8 +38,7 @@ class chart_indirect(dict): def __missing__(self, key): print 'creating chart indirect for:', key arity = int(key.split('/')[-1]) - c = self[key] = Chart(name = key, - ncols = arity + 1) # add one for output variable + c = self[key] = Chart(name = key, ncols = arity + 1) # +1 for value return c @@ -24,6 +46,8 @@ chart = chart_indirect() _delete = False agenda = set() aggregator = defaultdict(Counter) +agg = {} +agg_decl = None # filled in after exec, this only here to satisfy lint checker. def dump_charts(out=sys.stdout): @@ -38,8 +62,6 @@ def dump_charts(out=sys.stdout): print >> out, chart[x] print >> out -# maybe the chart should store pretty printed term and a reference to the -# aggregator (each item get's its own aggregator to avoid a hash lookup w). class Chart(object): @@ -137,8 +159,6 @@ def prettify(x): # 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(fn): """ Decorator for registering update handlers. Used by update dispatcher. @@ -190,7 +210,6 @@ def update_dispatcher(item, val): (fn, _) = item print 'dispatch', pretty(item), '=', val for handler in register.handlers[fn]: - print 'handler' handler(item, val) @@ -238,10 +257,7 @@ def delete(item, val): def aggregate(item): (fn, _) = item - v = agg[fn](item) - if v is None: - print 'aggregator empty' - return v + return agg[fn](item) def lookup(item): @@ -251,11 +267,12 @@ def lookup(item): def _go(): "the main loop" + while agenda: (fn, idx) = item = agenda.pop() print - print 'pop', pretty(item) + print 'pop', pretty(item), was = lookup(item) now = aggregate(item) @@ -286,90 +303,51 @@ def go(): dump_charts(f) -parser = ArgumentParser(description=__doc__) -parser.add_argument('source', help='Path to Dyna source file.') -argv = parser.parse_args() - - -cmd = """ghc -isrc Dyna.Backend.Python -e 'processFile "%s"' """ % argv.source -assert 0 == os.system(cmd), 'command failed:\n\t' + cmd - -agg_decl = None # filled in after exec, this only here to satisfy lint checker. - -# load generated code. -execfile(argv.source + '.plan') +def dynac(f): + cmd = """ghc -isrc Dyna.Backend.Python -e 'processFile "%s"' """ % f + assert 0 == os.system(cmd), 'command failed:\n\t' + cmd + return f + '.plan' -# bind aggregators to definitions -agg = agg_bind(agg_decl, aggregator) +def load(f, verbose=True): -# run initializers -for init in initializer.handlers: - init() + if verbose: + with file(f) as h: + print h.read() -# start running the agenda -go() + # load generated code. + execfile(f, globals()) + # bind aggregators to definitions + agg_bind(agg, agg_decl, aggregator) -#_____________ -# REPL stuff. +def dump(code, filename='/tmp/tmp.dyna'): + "Write code to file." + with file(filename, 'wb') as f: + f.write(code) + return filename -class UserChart(object): - def __init__(self, _chart): - self.ncols = _chart.ncols - self.data = _chart.data - self.name = _chart.name - self._chart = _chart +def do(filename): + "Compile, load, and execute dyna code." - def __getitem__(self, item): - assert isinstance(item, tuple) and len(item) == self.ncols - 1 - nonslice = [(i, v) for i, v in enumerate(item) if not isinstance(v, slice)] - for idx, row in self.data.iteritems(): - val = row[-1] - if val is None: - continue - if all(row[i] == val for i, val in nonslice): -# yield (self.name, idx) - print pretty((self.name, idx)), ':=', val + assert os.path.exists(filename) - def __setitem__(self, args, now): + initializer.handlers = [] # XXX: do we really want to clear? - assert isinstance(args, tuple) and len(args) == self.ncols - 1 - nonslice = [(i, v) for i, v in enumerate(args) if not isinstance(v, slice)] + load(dynac(filename)) - foundone = False - for idx, row in self.data.iteritems(): - if all(row[i] == val for i, val in nonslice): - item = (self.name, idx) - # timv: technically, should restrict to ":=" and extensional - colon_equals(item, now) - foundone = True + for init in initializer.handlers: # assumes we have cleared + init() - if not foundone and len(nonslice) == len(args): - idx = self._chart.insert(args, None) - item = (self.name, idx) - colon_equals(item, now) + go() - go() - - -def colon_equals(item, now): - # timv: technically, should restrict to ":=" and extensional - aggregator[item].clear() - if now is not None: - aggregator[item][now] += 1 - agenda.add(item) # XXX: probably shouldn't queue automatically. +parser = ArgumentParser(description=__doc__) +parser.add_argument('source', help='Path to Dyna source file.') +argv = parser.parse_args() -for _fn in chart: - try: - exec '%s = UserChart(chart[%r])' % (_fn.replace('/', ''), _fn) - except: - pass - +do(argv.source) -from IPython.frontend.terminal.embed import InteractiveShellEmbed -ipshell = InteractiveShellEmbed(banner1 = 'Dropping into IPython\n') -ipshell() +ip() diff --git a/bin/utils.py b/bin/utils.py index 3f164c3..0170cd4 100644 --- a/bin/utils.py +++ b/bin/utils.py @@ -1,5 +1,8 @@ import re, os +from IPython.frontend.terminal.embed import InteractiveShellEmbed +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)) diff --git a/src/Dyna/Analysis/ANF.hs b/src/Dyna/Analysis/ANF.hs index d2f62b3..695dac2 100644 --- a/src/Dyna/Analysis/ANF.hs +++ b/src/Dyna/Analysis/ANF.hs @@ -189,7 +189,9 @@ dynaFunctorArgDispositions x = case x of -- evaluate arithmetic / math ("exp", 1) -> [ADEval] ("log", 1) -> [ADEval] - -- logic + ("mod", 2) -> [ADEval, ADEval] + ("abs", 1) -> [ADEval] + -- logic ("and", 2) -> [ADEval, ADEval] ("or", 2) -> [ADEval, ADEval] ("not", 1) -> [ADEval] @@ -292,7 +294,7 @@ normTerm_ c ss (P.TFunctor "is" [x T.:~ sx, v T.:~ sv]) = do _ -> do NTVar `fmap` newAssign "_u" (Right ("is",[nx,nv])) --- Annotations +-- Annotations -- -- XXX this is probably the wrong thing to do normTerm_ c ss (P.TAnnot a (t T.:~ st)) = do diff --git a/src/Dyna/Backend/Python.hs b/src/Dyna/Backend/Python.hs index 7f3cad8..d094a18 100644 --- a/src/Dyna/Backend/Python.hs +++ b/src/Dyna/Backend/Python.hs @@ -50,16 +50,20 @@ constants = S.fromList , ("%",2) , ("**",2) , ("<",2) + , ("<=",2) , (">",2) - , ("<<",2) - , (">>",2) - , ("~",2) + , (">=",2) + , ("!",2) + , ("mod",1) + , ("abs",1) , ("log",1) , ("exp",1) , ("and",2) , ("or",2) , ("not",1) , ("true",0) + , ("false",0) + , ("null",0) -- XXX is this right? ] data PyDopeBS = PDBAsIs @@ -82,7 +86,7 @@ builtin (f,is,o) = case () of ([MFree,MBound],MBound) -> Right (Det, PDBRewrite $ \([x,y],o) -> [OPIter x [o,y] "-" Det $ Just PDBAsIs]) _ -> Left True - + _ | f == "-" -> case (is,o) of ([MBound,MFree],MBound) -> Right (Det, @@ -120,11 +124,10 @@ pdope (OPIter v vs f _ (Just b)) = case b of PDBAsIs -> Right $ pretty (varOfMV v) <+> equals - <+> functorIndirect "call" f vs - <> (tupled $ map (pretty . varOfMV) vs) + <+> pycall "call" f vs PDBRewrite rf -> Left $ rf (vs,v) - + pdope (OPIter o m f _ Nothing) = Right $ let mo = m ++ [o] in @@ -144,6 +147,42 @@ filterBound = map (\(MF v) -> pretty v) . filter (not.isBound) functorIndirect table f vs = table <> (brackets $ dquotes $ (pretty f <> "/" <> (text $ show $ length vs))) + +pycall table f vs = case (f, length vs) of + ( "*", 2) -> infixOp " * " + ( "+", 2) -> infixOp " + " + ( "-", 2) -> infixOp " - " + ( "/", 2) -> infixOp " / " + ( "^", 2) -> infixOp " ** " + ( "&", 2) -> infixOp " and " -- note: python's 'and' and 'or' operate on more than bool + ( "|", 2) -> infixOp " or " + ( "<", 2) -> infixOp " < " + ( "<=", 2) -> infixOp " <= " + ( ">", 2) -> infixOp " > " + ( ">=", 2) -> infixOp " >= " + ( "==", 2) -> infixOp " == " + ( "!=", 2) -> infixOp " != " + ("mod", 2) -> infixOp " % " + + ("eval", 1) -> call "eval" -- note: security hole. + + ( "abs", 1) -> call "abs" + ( "log", 1) -> call "log" + ( "exp", 1) -> call "exp" + ( "!", 1) -> call "not" + + ( "null", 0) -> "None" + ( "true", 0) -> "True" + ("false", 0) -> "False" + + -- fall back use the call indirection table... for now non-exhaustive pattern match error + -- TODO: add useful error message. +-- _ -> functorIndirect "call" f vs <> (tupled $ pretty_vs) + + where pretty_vs = map (pretty . varOfMV) vs + call name = name <> (parens $ sepBy ", " $ pretty_vs) + infixOp op = sepBy op $ pretty_vs + pf f vs = pretty f <> (tupled $ map pretty vs) ------------------------------------------------------------------------}}} @@ -167,7 +206,7 @@ combinePlans = go (M.empty) go' xs _ [] m = go m xs go' xs fr ((fa,mca):ys) m = case mca of - Nothing -> throw $ UserProgramError + Nothing -> throw $ UserProgramError $ "No update plan for " <+> (pretty fa) <+> "in rule at" diff --git a/src/Dyna/ParserHS/Parser.hs b/src/Dyna/ParserHS/Parser.hs index c7bf314..6eae106 100644 --- a/src/Dyna/ParserHS/Parser.hs +++ b/src/Dyna/ParserHS/Parser.hs @@ -331,7 +331,11 @@ rule = choice [ <*> texpr) -- HEAD . + -- timv: using ':-' as the "default" aggregator for facts is + -- probably incorrect because it conflicts with '&=' and other + -- logical aggregators. , (\h@(_ :~ s) -> Rule h ":-" [] $ (TFunctor "true" [] :~ s)) <$> term + ] <* optional (char '.') where -- 2.50.1