teamwork.widgets.PsychGUI.prolog

1 #!/usr/bin/env python 2 # 3 # p r o l o g 3 . p y 4 # 5 import sys, copy, re, string 6 7 rules = [] 8 trace = 0 9 indent = "" 10

11 -def fatal (mesg) :

12 sys.stdout.write ("Fatal: %s\n" % mesg) 13 sys.exit(1)

14

15 -def split (l, sep, All=1) :

16 "Split l by sep but honoring () and []" 17 nest = 0 18 lsep = len(sep) 19 if l == "" : return [] 20 for i in range(len(l)) : 21 c = l[i] 22 if nest <= 0 and l[i:i+lsep] == sep : 23 if All : return [l[:i]]+split(l[i+lsep:],sep) 24 else : return [l[:i],l[i+lsep:]] 25 if c in ['[','('] : nest = nest+1 26 if c in [']',')'] : nest = nest-1 27 return [l]

28

29 -def isVariable(term) : return term.args == [] and term.pred[0:1] in string.uppercase

30 -def isConstant(term) : return term.args == [] and not term.pred[0:1] in string.uppercase

31 32 infixOps = ("*is*","==","<",">","+","--","*","/") # STacy

33 -def splitInfix(s) :

34 for op in infixOps: 35 p = split(s,op,All=0) 36 if len(p) > 1 : return (op,p) 37 return None

38

39 -def makeTerm (s) : return Term(s)

40

41 -class Term :

42 - def __init__ (self, s, args=None) :

43 if not args : parts = splitInfix(s) 44 if args : # Predicate and args seperately 45 self.pred = s 46 self.args = args 47 elif parts : 48 self.args = map(makeTerm,parts[1]) 49 self.pred = parts[0] 50 elif s[-1] == ']' : # Build list "term" 51 flds = split(s[1:-1],",") 52 fld2 = split(s[1:-1],"|") 53 if len(fld2) > 1 : 54 self.args = map(makeTerm,fld2) 55 self.pred = '.' 56 else : 57 flds.reverse() 58 l = Term('.',[]) 59 for fld in flds : l = Term('.',[Term(fld),l]) 60 self.pred = l.pred; self.args = l.args 61 elif s[-1] == ')' : # Compile from "pred(a,b,c)" string 62 flds = split(s,'(',All=0) 63 if len(flds) != 2 : fatal("Syntax error in term: %s" % [s]) 64 self.args = map(makeTerm,split(flds[1][:-1],',')) 65 self.pred = flds[0] 66 else : 67 self.pred = s # Simple constant or variable 68 self.args = []

69

70 - def __repr__ (self) :

71 if self.pred == '.' : 72 if len(self.args) == 0 : return "[]" 73 nxt = self.args[1] 74 if nxt.pred == '.' and nxt.args == [] : 75 return "[%s]" % str(self.args[0]) 76 elif nxt.pred == '.' : 77 return "[%s,%s]" % (str(self.args[0]),str(self.args[1])[1:-1]) 78 else : 79 return "[%s|%s]" % (str(self.args[0]),str(self.args[1])) 80 elif self.args : 81 return "<%s(%s)>" % (self.pred,string.join(map(str,self.args),",")) 82 else : return self.pred

83

84 -def procRule(sent):

85 s = re.sub("#.*","",sent[:-1]) # clip comments and newline 86 s = re.sub(" is ","*is*",s) # protect "is" operator 87 s = re.sub(" ", "" ,s) # remove spaces 88 if s[-1] in ['?','.'] : punc=s[-1]; s=s[:-1] 89 else : punc='.' 90 if punc == '?' : return search(Term(s)) 91 else : 92 rules.append(Rule(s)) 93 # print Rule(s) 94 return []

95

96 -def clearPrologRules():

97 global rules 98 rules = []

99 100

101 -class Rule :

102 - def __init__ (self, s) : # expect "term:-term,term,..."

103 flds = string.split(s,":-") 104 self.head = Term(flds[0]) 105 self.goals = [] 106 if len(flds) == 2 : 107 flds = split(flds[1],",") 108 for fld in flds : self.goals.append(Term(fld))

109

110 - def __repr__ (self) :

111 return "<Rule: %s :- %s>" % (self.head, self.goals)

112

113 -class Goal :

114 - def __init__ (self, rule, parent=None, env={}) :

115 self.rule = rule 116 self.parent = parent 117 self.env = copy.deepcopy(env) 118 self.inx = 0 # start search with 1st subgoal

119

120 - def __repr__ (self) :

121 return "<Goal:%s:%d:%s>" % (self.rule,self.inx,self.env)

122

123 -def main () :

124 for file in sys.argv[1:] : 125 if file == '.' : return # early out. no user interaction 126 procFile(open(file),'') # file on the command line 127 procFile (sys.stdin,'? ') # let the user have her say

128

129 -def procFile (f, prompt) :

130 global rules, trace 131 env = [] 132 while 1 : 133 if prompt : 134 sys.stdout.write(prompt) 135 sys.stdout.flush() 136 sent = f.readline() 137 if sent == "" : break 138 s = re.sub("#.*","",sent[:-1]) # clip comments and newline 139 s = re.sub(" is ","*is*",s) # protect "is" operator 140 s = re.sub(" ", "" ,s) # remove spaces 141 if s == "" : continue 142 143 if s[-1] in ['?','.'] : punc=s[-1]; s=s[:-1] 144 else : punc='.' 145 146 if s == 'trace' : trace = not trace 147 elif s == 'dump' : 148 for rule in rules : print rule 149 elif punc == '?' : search(Term(s)) 150 else : rules.append(Rule(s))

151 ## for rule in rules : print rule 152 153 # A Goal is a rule in at a certain point in its computation. 154 # env contains definitions (so far), inx indexes the current term 155 # being satisfied, parent is another Goal which spawned this one 156 # and which we will unify back to when this Goal is complete. 157 # 158

159 -def unify (src, srcEnv, dest, destEnv) :

160 "update dest env from src. return true if unification succeeds" 161 global trace, indent 162 if trace : print indent, "Unify", src, srcEnv, "to", dest, destEnv 163 indent = indent+" " 164 if src.pred == '_' or dest.pred == '_' : return sts(1,"Wildcard") 165 166 if isVariable(src) : 167 srcVal = eval(src, srcEnv) 168 if not srcVal : return sts(1,"Src unset") 169 else : return sts(unify(srcVal,srcEnv,dest,destEnv), "Unify to Src Value") 170 171 if isVariable(dest) : 172 destVal = eval(dest, destEnv) # evaluate destination 173 if destVal : return sts(unify(src,srcEnv,destVal,destEnv),"Unify to Dest value") 174 else : 175 destEnv[dest.pred] = eval(src,srcEnv) 176 return sts(1,"Dest updated 1") # unifies. destination updated 177 178 elif src.pred != dest.pred : return sts(0,"Diff predicates") 179 elif len(src.args) != len(dest.args) : return sts(0,"Diff # args") 180 else : 181 dde = copy.deepcopy(destEnv) 182 for i in range(len(src.args)) : 183 if not unify(src.args[i],srcEnv,dest.args[i],dde) : 184 return sts(0,"Arg doesn't unify") 185 destEnv.update(dde) 186 return sts(1,"All args unify")

187

188 -def sts(ok, why) :

189 global trace, indent 190 indent = indent[:-2] 191 if trace: print indent, ["No","Yes"][ok], why 192 return ok

193

194 -def search (term) :

195 global trace 196 res = [] 197 # pop will take item from end, insert(0,val) will push item onto queue 198 goal = Goal(Rule("all(done):-x(y)")) # Anything- just get a rule object 199 goal.rule.goals = [term] # target is the single goal 200 queue = [goal] # Start our search 201 while queue : 202 c = queue.pop() # Next goal to consider 203 if trace : print "Deque", c 204 if c.inx >= len(c.rule.goals) : # Is this one finished? 205 if c.parent == None : # Yes. Our original goal? 206 if c.env : 207 print c.env # Yes. tell user we 208 res.append(c.env) # 209 else : print "Yes" # have a solution 210 continue 211 parent = copy.deepcopy(c.parent) # Otherwise resume parent goal 212 unify (c.rule.head, c.env, 213 parent.rule.goals[parent.inx],parent.env) 214 parent.inx = parent.inx+1 # advance to next goal in body 215 queue.insert(0,parent) # let it wait its turn 216 if trace : print "Requeuing", parent 217 continue 218 219 # No. more to do with this goal. 220 term = c.rule.goals[c.inx] # What we want to solve 221 222 pred = term.pred # Special term? 223 if pred in ['*is*', 'cut','fail', 'diff', '<','=='] : 224 if pred == '*is*' : 225 ques = eval(term.args[0],c.env) 226 ans = eval(term.args[1],c.env) 227 if ques == None : 228 c.env[term.args[0].pred] = ans # Set variable 229 elif ques.pred != ans.pred : 230 continue # Mismatch, fail 231 elif pred == 'diff' : 232 ques = eval(term.args[0],c.env) 233 ans = eval(term.args[1],c.env) 234 if ques.pred == ans.pred : 235 continue 236 elif pred == 'cut' : queue = [] # Zap the competition 237 elif pred == 'fail': continue # Dont succeed 238 elif not eval(term,c.env) : continue # Fail if not true 239 c.inx = c.inx + 1 # Succeed. resume self. 240 queue.insert(0,c) 241 continue 242 243 for rule in rules : # Not special. Walk rule database 244 if rule.head.pred != term.pred : continue 245 if len(rule.head.args) != len(term.args) : continue 246 child = Goal(rule, c) # A possible subgoal 247 ans = unify (term, c.env, rule.head, child.env) 248 if ans : # if unifies, queue it up 249 queue.insert(0,child) 250 if trace : print "Queuing", child 251 return res

252

253 -def add (a,b) : return Term(str(int(a.pred)+int(b.pred)),[])

254 -def sub (a,b) : return Term(str(int(a.pred)-int(b.pred)),[])

255 -def mul (a,b) : return Term(str(int(a.pred)*int(b.pred)),[])

256 -def lt (a,b) : return int(a.pred) < int(b.pred)

257 -def eq (a,b) : return int(a.pred) == int(b.pred)

258

259 -def preport (a) :

260 print a 261 return 1

262 263 operators = {'+': add, '--':sub, '*':mul, '<':lt} 264

265 -def eval (term, env) : # eval all variables within a term to constants

266 special = operators.get(term.pred) 267 if special : 268 return special(eval(term.args[0],env),eval(term.args[1],env)) 269 if isConstant(term) : return term 270 if isVariable(term) : 271 ans = env.get(term.pred) 272 if not ans : return None 273 else : return eval(ans,env) 274 args = [] 275 for arg in term.args : 276 a = eval(arg,env) 277 if not a : return None 278 args.append(a) 279 return Term(term.pred, args) 280 281 if __name__ == "__main__" : main() 282

Source Code for Module teamwork.widgets.PsychGUI.prolog