forked from sympy/sympy
-
Notifications
You must be signed in to change notification settings - Fork 1
/
logic.py
326 lines (225 loc) · 7.19 KB
/
logic.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
"""Logic expressions handling
NOTE
----
at present this is mainly needed for facts.py , feel free however to improve
this stuff for general purpose.
"""
def fuzzy_not(v):
"""'not' in fuzzy logic"""
if v is None:
return v
else:
return not v
def name_not(k):
"""negate a name
>>> name_not('zero')
'!zero'
>>> name_not('!zero')
'zero'
"""
if k[:1] != '!':
return '!'+k
else:
return k[1:]
class Logic(object):
"""Logical expression"""
__slots__ = ['args']
# {} 'op' -> LogicClass
op_2class = {}
def __new__(cls, args):
obj = object.__new__(cls)
obj.args = tuple(args)
# XXX do we need this:
#print 'L: %s' % (obj.args,)
assert not isinstance(obj.args[0], tuple)
return obj
def __hash__(self):
return hash( (type(self).__name__, self.args) )
def __eq__(a, b):
if not isinstance(b, type(a)):
return False
else:
return a.args == b.args
def __ne__(a, b):
if not isinstance(b, type(a)):
return True
else:
return a.args != b.args
def __cmp__(a, b):
if type(a) is not type(b):
return cmp( str(type(a)), str(type(b)) )
else:
return cmp(a.args, b.args)
# XXX later, we may want to change how expressions are printed
def __str__(self):
return '%s(%s)' % (self.op, ', '.join(str(a) for a in self.args))
# XXX this is not good ...
__repr__ = __str__
@staticmethod
def fromstring(text):
"""Logic from string
e.g.
!a & !b | c
"""
# XXX this is not general, but good enough
terms = text.split()
lexpr = None # current logical expression
schedop = None # scheduled operation
while True:
# pop next term and exit loop if there is no terms left
try:
term = terms.pop(0)
except IndexError:
break
# operation symbol
if term in '&|':
if schedop is not None:
raise ValueError('double op forbidden: "%s %s"' % (term, schedop))
if lexpr is None:
raise ValueError('%s cannot be in the beginning of expression' % term)
schedop = term
continue
# already scheduled operation, e.g. '&'
if schedop:
lexpr = Logic.op_2class[schedop] ( *(lexpr, term) )
schedop = None
continue
# this should be atom
if lexpr is not None:
raise ValueError('missing op between "%s" and "%s"' % (lexpr, term))
lexpr = term
# let's check that we ended up in correct state
if schedop is not None:
raise ValueError('premature end-of-expression in "%s"' % text)
if lexpr is None:
raise ValueError('"%s" is empty' % text)
# everything looks good now
return lexpr
# XXX better name?
class AndOr_Base(Logic):
__slots__ = []
def __new__(cls, *args):
if len(args) == 0:
raise TypeError('%s requires at least one argument' % cls.__name__)
# process bool args early
bargs = []
for a in args:
# &(F, ...) -> F
# |(T, ...) -> T
if a == cls.op_x_notx:
return a
# &(T, ...) -> &(...)
# |(F, ...) -> |(...)
elif a == (not cls.op_x_notx):
continue # skip this argument
bargs.append(a)
args = bargs
# &(a, !a) -> F
# |(a, !a) -> T
# XXX suboptinal
for a in args:
if Not(a) in args:
return cls.op_x_notx
args = cls.flatten(args)
# canonicalize arguments
# XXX do we always need this?
# NB: this is needed to reduce number of &-nodes in beta-network
args = sorted(args)
# now let's kill duplicate arguments, e.g. &(a,a,b) -> &(a,b)
prev = None
uargs= []
for a in args:
if a != prev:
uargs.append(a)
prev = a
args = uargs
# &(a) -> a
# |(a) -> a
if len(args) == 1:
return args[0]
# when we are at this stage, it means that _all_ arguments were T/F and
# all arguments were accepted as "let's see what follows next", so at
# _this_ point the rule is:
# |() -> F (*not* T)
# &() -> T (*not* F)
elif len(args) == 0:
return not cls.op_x_notx
return Logic.__new__(cls, args)
@classmethod
def flatten(cls, args):
# quick-n-dirty flattening for And and Or
args_queue = list(args)
res = []
while True:
try:
arg = args_queue.pop(0)
except IndexError:
break
if isinstance(arg, Logic):
if arg.op == cls.op:
#print 'flattening...', fargs, i, arg.args
args_queue.extend( arg.args )
continue
# another op -- leave it as is
res.append( arg )
args = tuple(res)
return args
expand_lvl=0
class And(AndOr_Base):
op = '&'
op_x_notx = False
__slots__ = []
def _eval_propagate_not(self):
# !(a&b&c ...) == !a | !b | !c ...
return Or( *[Not(a) for a in self.args] )
# (a|b|...) & c == (a&c) | (b&c) | ...
def expand(self):
# first locate Or
for i in range(len(self.args)):
arg = self.args[i]
if isinstance(arg, Or):
arest = self.args[:i] + self.args[i+1:]
orterms = [And( *(arest + (a,)) ) for a in arg.args]
for j in range(len(orterms)):
if isinstance(orterms[j], Logic):
orterms[j] = orterms[j].expand()
res = Or(*orterms)
return res
else:
return self
def dbg_expand(self):
global expand_lvl
print '%sexpand %s' % (' '*expand_lvl, self)
expand_lvl += 1
try:
return self.old_expand()
finally:
expand_lvl -= 1
#old_expand = expand
#expand = dbg_expand
class Or(AndOr_Base):
op = '|'
op_x_notx = True
__slots__ = []
def _eval_propagate_not(self):
# !(a|b|c ...) == !a & !b & !c ...
return And( *[Not(a) for a in self.args] )
class Not(Logic):
op = '!'
__slots__ = []
def __new__(cls, arg):
if isinstance(arg, str):
return name_not(arg)
elif isinstance(arg, bool):
return not arg
elif isinstance(arg, Logic):
# XXX this is a hack to expand right from the beginning
arg = arg._eval_propagate_not()
return arg
obj = Logic.__new__(cls, (arg,))
return obj
else:
raise ValueError('Not: unknown argument %r' % (arg,))
Logic.op_2class['&'] = And
Logic.op_2class['|'] = Or
Logic.op_2class['!'] = Not