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