tools/exprCreator.py

   1 #!env python
   2 # vim: set fileencoding=utf8
   3 # Created: April 22, 2008
   4 #
   5 # Expression creator
   6 #   Currently produces list of functions to apply.
   7 #   Use get_unary to find a unary funcion.
   8 #       ie. get_unary("ii0")
   9 #   Use get_dyadic to find a dyadic funcion.
  10 #       ie. get_dyadic("ii0111001")
  11 #   Todo: add utf support names and return string expression
  12
  13 import sys, os
  14 import Trits
  15
  16 sd  = Trits.Trits("ii0") # shift down
  17 su  = Trits.Trits("011") # shift up
  18 s01 = Trits.Trits("i10") # swap 0/1
  19 si0 = Trits.Trits("0i1") # swap i/0
  20 ru  = Trits.Trits("01i") # rotate up
  21 rd  = Trits.Trits("1i0") # rotate down
  22 inv = Trits.Trits("10i") # inverter
  23
  24 buf = Trits.Trits("i01") # identity
  25 ci  = Trits.Trits("iii") # constant i
  26 c0  = Trits.Trits("000") # constant 0
  27 c1  = Trits.Trits("111") # constant 1
  28
  29 valid_chars = ("i", "0", "1")
  30 map_t = {False:0, None:1, True:2}
  31 map_str = {False:"i", None:"0", True:"1"}
  32
  33 basic = {"}":sd, "{":su, ">":s01, "<":si0, "[":ru,
  34              "]":rd, "/":inv}
  35 easy = {"B":buf, "i":ci, "0":c0, "1":c1}
  36
  37
  38 def get_dyadic(desired):
  39     ''' get_dyadic: get expression for a dyadic function
  40         desired: string representation of desired function
  41         returns: Returns a tuple.  True or false (if function was not found).
  42             A list of expressions for each unary function needed to build
  43             the desired function.
  44     '''
  45
  46     if len(desired) != 9:
  47         print "truth table must be 9 chars wide"
  48         raise SystemExit
  49
  50     for i in range(0, 9):
  51         if not desired[i] in valid_chars:
  52             print "%s not a valid character" % desired[i]
  53             raise SystemExit
  54
  55     goal_1 = desired[0:3]
  56     goal_2 = desired[3:6]
  57     goal_3 = desired[6:9]
  58
  59     result_1, gates_1 = get_unary(goal_1)
  60     result_2, gates_2 = get_unary(goal_2)
  61     result_3, gates_3 = get_unary(goal_3)
  62
  63     if result_1 and result_2 and result_3:
  64         return True, gates_1, gates_2, gates_3
  65
  66     return False, [], [], []
  67
  68
  69 def get_unary(desired):
  70     ''' get_unary: get expression for a unary function
  71         desired: string representation of desired function
  72         returns: Returns a tuple. True or false (if function was not found)
  73             and a list of functions to apply to get the desired function.
  74             The list is read from left to right.
  75     '''
  76
  77     # do some input error checking
  78     if len(desired) != 3:
  79         print "truth table must be 3 chars wide"
  80         raise SystemExit
  81
  82     for i in range(0, 3):
  83         if not desired[i] in valid_chars:
  84             print "%s not a valid character" % desired[i]
  85             raise SystemExit
  86
  87     goal = Trits.Trits(desired)
  88     crnt = Trits.Trits("i01")
  89     l_gates = []
  90
  91     for i in easy:
  92         if goal.equals(easy[i]):
  93             return True, [i]
  94
  95     count = 0
  96     end_cond = True
  97     while end_cond and count < 4:
  98         end_cond, l_gates = recurse_unary(crnt, goal, [], count)
  99         end_cond = not end_cond
 100         count = count + 1
 101
 102     return (not end_cond, l_gates)
 103
 104 def recurse_unary(crnt, goal, l_gates, depth):
 105     ''' recurse_unary: attempt to locate a function sequence that makes the
 106             goal function
 107         crnt: current function result
 108         goal: the desired function result
 109         l_gates: list of gates to apply to get to crnt
 110         count: the number of gate levels
 111         returns: true and list of gates if goal is met, else false and []
 112     '''
 113
 114     # check the basic gates for an answer
 115     if depth == 0:
 116         return test_all(crnt, goal, l_gates)
 117
 118     else:
 119         # for each basic gate attempt to find the desired function
 120         for i in basic:
 121             cndt = eval_one(crnt, i)
 122             l_gates.append(i)
 123
 124             if cndt.equals(goal):
 125                 return True, l_gates
 126
 127             status, gates = recurse_unary(cndt, goal, l_gates, depth - 1)
 128
 129             if status:
 130                 return True, gates
 131
 132             l_gates.pop()
 133
 134     return (False, [])
 135
 136 def test_all(crnt, goal, l_gates):
 137     ''' test_all: attempt to find a basic function that fulfills the desired
 138             gate.
 139         crnt: the current evaluation of the function
 140         goal: the desired function result
 141         l_gates: list of gates currently applied to crnt
 142         returns: true and list of gates if goal is met, else false and []
 143     '''
 144
 145     for i in basic:
 146         cndt = eval_one(crnt, i)
 147
 148         # if desired function is found then return true and the list of gates
 149         # to apply
 150         if cndt.equals(goal):
 151             l_gates.append(i)
 152             return True, l_gates
 153
 154     return False, []
 155
 156 def eval_one(crnt, func):
 157     ''' eval_one: the input given in crnt with function 'func'
 158         crnt: Trits object as input
 159         func: function to apply
 160         return: Trist object containing result
 161     '''
 162
 163     next = ""
 164     for i in range(0, 3):
 165         next = next + map_str[basic[func][map_t[crnt[i]]]]
 166
 167     return Trits.Trits(next)
 168
 169 if __name__ == "__main__":
 170     result, gates = get_unary("11i")
 171     if result:
 172         print gates
 173
 174     result, gates1, gates2, gates3 = get_dyadic("i0111000i")
 175     if result:
 176         print gates1, gates2, gates3
 177
 178     print "At prompt '>>' type unary (010) or dyadic (1010i1ii0)"
 179
 180     while True:
 181         valid = True
 182         print ">> ",
 183         line = sys.stdin.readline()
 184         line = line.strip()
 185         print
 186
 187         if len(line) == 3 or len(line) == 9:
 188
 189             for i in range(0, len(line)):
 190                 if not line[i] in valid_chars:
 191                     valid = False
 192
 193             if valid:
 194                 if len(line) == 3:
 195                     result, gates = get_unary(line)
 196                     print gates
 197                 if len(line) == 9:
 198                     result, gates1, gates2, gates3 = get_dyadic(line)
 199                     print gates1, gates2, gates3
 200