src/mjacob/algorithms/deduction_iterator.py

   1 # This Python file uses the following encoding: utf-8
   2 '''
   3 Created on Apr 27, 2011
   4
   5 Code which iterates possible paths for logical deductions.
   6 For chart parsing, this is potentially useful for discovering ambiguities in a tree,
   7 but as the Earley Tag rules are far from optimal, much more ambiguity is discovered
   8 than actually results in different parses.
   9
  10 More generally, this code is interesting as I haven't seen anything like it before.
  11 There's potentially some interesting combinatorics going on here - we're counting
  12 the number of DAGs as sub-graphs of a directed hypergraph.
  13
  14 @author: mjacob
  15 '''
  16 from functools import reduce
  17 def deductions(result,
  18                get_anteceding_rules,
  19                get_antecedents=lambda x: x,
  20                working_on=set(),
  21                resolved=set()):
  22     """
  23     given a collections of lemmas
  24       A1, A2, A3
  25
  26     and logical deductions of the type
  27       A1,A2 -> A3   (read: A1 and A2 imply A3)
  28
  29     iterate over all possible relevant deductive pathways which result in C{result}
  30
  31     arguments:
  32         result: an object which represents the final lemma of a deduction
  33         get_anteceding_rules: a callable item (e.g., a function) of the form
  34                 f(lemma) -> deductions
  35             where each deduction directly generates the supplied lemma
  36         get_antecedents: a callable item (e.g., a function) of the form
  37                 f(rule) -> lemmas
  38             where the resulting lemmas are the antecedents of the rule
  39
  40     result:
  41         a generator which iterates deductions of the form
  42               ((A, (B, C)), (B, ()), (C, ()))
  43           where each element represents a deduction rule, consisting of a resulting lemma and its antecedents.
  44     """
  45
  46     def mark_resolved():
  47         working_on.remove(result)
  48         resolved.add(result)
  49
  50     def mark_unresolved():
  51         resolved.remove(result)
  52         working_on.add(result)
  53
  54     def begin_resolution():
  55         working_on.add(result)
  56
  57     def finish_resolution():
  58         working_on.remove(result)
  59
  60     def is_recursive_rule(rule):
  61         for lemma in get_antecedents(rule):
  62             if lemma in working_on:
  63                 return True
  64         return False
  65
  66     def resolve_antecedents(unresolved_antecedents):
  67         """iterate over all possible combinations of further productions (v)
  68         this method was created because python's itertools.product method had side effects."""
  69         first, rest = unresolved_antecedents[0], unresolved_antecedents[1:]
  70
  71         for deduction_of_first in deductions(first,
  72                                              get_anteceding_rules,
  73                                              get_antecedents,
  74                                              working_on,
  75                                              resolved):
  76             if rest:
  77                 for deduction_of_rest in resolve_antecedents(rest):
  78                     yield (deduction_of_first,) + deduction_of_rest
  79
  80             else:
  81                 yield (deduction_of_first,)
  82
  83     if result in resolved:
  84         """if there is a merging dependency"""
  85         yield ()
  86
  87     else:
  88         begin_resolution()
  89
  90         for rule in get_anteceding_rules(result):
  91
  92             if is_recursive_rule(rule):
  93                 """ignore looping deductions"""
  94                 continue
  95
  96             unresolved_antecedents = tuple(lemma
  97                                            for lemma in get_antecedents(rule)
  98                                            if lemma not in resolved)
  99
 100             if not unresolved_antecedents:
 101                 mark_resolved()
 102                 yield ((result, rule),)
 103                 mark_unresolved()
 104
 105             else:
 106                 for deductions_of_antecedents in resolve_antecedents(unresolved_antecedents):
 107                     mark_resolved()
 108                     yield ((result, rule),) + reduce(tuple.__add__,
 109                                                      deductions_of_antecedents)
 110                     mark_unresolved()
 111
 112         finish_resolution()
 113
 114
 115 if __name__ == "__main__":
 116     """test functionality"""
 117     #start, A = 1, {1: ((2,),(2,3,),(3,),), 2: ((3,),(4,),), 3: ((4,),(5,),(6,),), 4: ((),), 5: ((6,),), 6: ((),)}
 118     start, A = 1, {1: ((2,3,),), 2: ((3,), (4,),), 3: ((2,), (4,), (4,5,),), 4: ((),), 5: ((),)}
 119     #start, A = 1, {1: ((2,3,),), 2: ((3,), (4,),), 3: ((2,), (2,4,), (4,),), 4: ((),)}
 120     #start, A = 12, {0: ((),), 1: ((2,),), 2: ((10, 11),), 3: ((),), 4: ((5, 6),), 5: ((8, 9),), 6: ((2, 18),), 7: ((5, 1),), 8: ((),), 9: ((),), 10: ((),), 11: ((),), 12: ((13, 6),), 13: ((3,),), 14: ((13,),), 15: ((5,),), 16: ((),), 17: ((13, 1),), 18: ((37,),), 19: ((),), 20: ((21,),), 21: ((),), 22: ((20,),), 23: ((24,),), 24: ((),), 25: ((23,),), 26: ((),), 27: ((),), 28: ((),), 29: ((30, 31),), 30: ((),), 31: ((),), 32: ((29,),), 33: ((30, 34),), 34: ((),), 35: ((10, 16),), 36: ((35,),), 37: ((30, 0),), 38: ((35, 32),), 39: ((20, 32),), 40: ((33,),)}
 121     for deduction in deductions(start, A.__getitem__):
 122         print("%s," % (deduction,))
 123         #print ", ".join("%s -> %s" % (antecedents, consequent) for consequent, antecedents in reversed(deduction))
 124