1 | % (c) 2014-2019 Lehrstuhl fuer Softwaretechnik und Programmiersprachen, | |
2 | % Heinrich Heine Universitaet Duesseldorf | |
3 | % This software is licenced under EPL 1.0 (http://www.eclipse.org/org/documents/epl-v10.html) | |
4 | ||
5 | :- module(b_simplifier, [simplify_b_predicate/2, tcltk_simplify_b_predicate/2, tcltk_simplify_b_predicate_error/2]). | |
6 | ||
7 | /* Modules and Infos for the code coverage analysis */ | |
8 | :- use_module(probsrc(module_information)). | |
9 | :- module_info(group,model_checker). | |
10 | :- module_info(description,'This module provides predicates for simplifying B predicates'). | |
11 | ||
12 | % Classical B prolog modules | |
13 | :- use_module(probsrc(bsyntaxtree), [get_texpr_expr/2, get_texpr_type/2, create_texpr/4, | |
14 | same_texpr/2, different_texpr_values/2, | |
15 | is_truth/1, is_falsity/1, is_negation_of/2, | |
16 | is_a_conjunct/3, is_a_disjunct/3, is_an_implication/3, | |
17 | conjunct_predicates/2, disjunct_predicates/2, | |
18 | %% extract_info/3, | |
19 | create_negation/2, | |
20 | create_implication/3, create_equivalence/3, | |
21 | create_forall/3, create_exists/3]). | |
22 | :- use_module(probsrc(bmachine),[b_parse_machine_predicate/2]). | |
23 | :- use_module(probsrc(kernel_objects),[element_of_global_set/2]). | |
24 | ||
25 | %% :- use_module(probsrc(parsercall), [parse_predicate/2]). | |
26 | ||
27 | :- use_module(probsrc(preferences),[temporary_set_preference/3, reset_temporary_preference/2]). | |
28 | :- use_module(probsrc(translate), [translate_bexpression/2]). | |
29 | %% :- use_module(probsrc(debug), [debug_print/2, debug_println/2, debug_mode/1]). | |
30 | :- use_module(probsrc(error_manager),[add_internal_error/2]). | |
31 | ||
32 | % Importing unit tests predicates | |
33 | :- use_module(probsrc(self_check)). | |
34 | ||
35 | % SICSTUS libraries | |
36 | :- use_module(library(avl)). | |
37 | ||
38 | %% atom_codes(String,Codes), | |
39 | %% debug_println(20,parsing_as_predicate(Codes)), | |
40 | %% eval_strings: repl_typing_scope(TypingScope), | |
41 | %% b_parse_machine_predicate_from_codes_open(exists,Codes, % will also mark outer variables so that they are not removed | |
42 | %% [],TypingScope,Typed), | |
43 | %% debug_println(20,eval_predicate(Typed)), | |
44 | ||
45 | tcltk_simplify_b_predicate_error(String,StringResult) :- | |
46 | if(tcltk_simplify_b_predicate(String,StringResult),true, | |
47 | (StringResult = 'Error or User-Interrupt')). | |
48 | ||
49 | % exported for the Tcl/Tk interface | |
50 | tcltk_simplify_b_predicate(String,StringResult) :- | |
51 | % parse also boolean expressions as predicates | |
52 | temporary_set_preference(bool_expression_as_predicate,true,Chg), | |
53 | %% atom_codes(String,Codes), | |
54 | %% parse_predicate(Codes,Tree), | |
55 | call_cleanup((b_parse_machine_predicate(String,Tree), | |
56 | simplify_b_predicate(Tree,Res), | |
57 | translate_bexpression(Res,StringResult)), | |
58 | reset_temporary_preference(bool_expression_as_predicate,Chg)). | |
59 | %extract_type_information(Typed,TypeInfo). | |
60 | ||
61 | simplify_b_predicate(Pred,Res) :- | |
62 | get_texpr_expr(Pred,Expr), | |
63 | get_texpr_type(Pred,Type), | |
64 | simplify_b_predicate2(Expr,Type,Res). | |
65 | ||
66 | simplify_b_predicate2(truth,Type,Res) :- !, | |
67 | create_texpr(truth,Type,[],Res). | |
68 | simplify_b_predicate2(falsity,Type,Res) :- !, | |
69 | create_texpr(falsity,Type,[],Res). | |
70 | simplify_b_predicate2(negation(BExpr),_Type,Res) :- !, | |
71 | simplify_negation(BExpr,Res). | |
72 | simplify_b_predicate2(conjunct(LHS,RHS),Type,Res) :- !, | |
73 | simplify_b_predicate(LHS,SimplifiedLHS), | |
74 | ( is_false_constant(SimplifiedLHS) -> % FALSE & f == FALSE | |
75 | create_texpr(falsity,Type,[],Res) | |
76 | ; is_true_constant(SimplifiedLHS) -> % TRUE & f == f | |
77 | simplify_b_predicate(RHS,Res) | |
78 | ; otherwise -> | |
79 | simplify_b_predicate(RHS,SimplifiedRHS), | |
80 | ( is_false_constant(SimplifiedRHS) -> % f & FALSE == FALSE | |
81 | create_texpr(falsity,Type,[],Res) | |
82 | ; is_true_constant(SimplifiedRHS) -> % f & TRUE == f | |
83 | Res = SimplifiedLHS | |
84 | ; same_texpr(SimplifiedLHS,SimplifiedRHS) -> % f & f == f (idempotence) | |
85 | Res = SimplifiedLHS | |
86 | ; is_absorption_rule_conjunct(SimplifiedLHS,SimplifiedRHS,Res) -> % f & (f or g) == f (absorption) | |
87 | true | |
88 | ; test_transitivity(SimplifiedLHS,SimplifiedRHS,Res) -> % (f => g) & (g => h) == (f => h) | |
89 | true | |
90 | ; otherwise -> | |
91 | conjunct_predicates([SimplifiedLHS,SimplifiedRHS],Res) | |
92 | ) | |
93 | ). | |
94 | simplify_b_predicate2(disjunct(LHS,RHS),Type,Res) :- !, | |
95 | simplify_b_predicate(LHS,SimplifiedLHS), | |
96 | ( is_true_constant(SimplifiedLHS) -> % TRUE or f == TRUE | |
97 | create_texpr(truth,Type,[],Res) | |
98 | ; is_false_constant(SimplifiedLHS) -> % FALSE or f == f | |
99 | simplify_b_predicate(RHS,Res) | |
100 | ; otherwise -> | |
101 | simplify_b_predicate(RHS,SimplifiedRHS), | |
102 | ( is_true_constant(SimplifiedRHS) -> % f or TRUE == TRUE | |
103 | create_texpr(truth,Type,[],Res) | |
104 | ; is_false_constant(SimplifiedRHS) -> % f or FALSE == f | |
105 | Res = SimplifiedLHS | |
106 | ; same_texpr(SimplifiedLHS,SimplifiedRHS) -> % f or f == f (idempotence) | |
107 | Res = SimplifiedLHS | |
108 | ; is_absorption_rule_disjunct(LHS,RHS,Res) -> % f or (f & g) == f (absorption) | |
109 | true | |
110 | ; otherwise -> | |
111 | disjunct_predicates([SimplifiedLHS,SimplifiedRHS],Res) | |
112 | ) | |
113 | ). | |
114 | simplify_b_predicate2(implication(LHS,RHS),_Type,Res) :- !, | |
115 | simplify_b_predicate(RHS,SimplifiedRHS), | |
116 | simplify_implication(LHS,SimplifiedRHS,Res). | |
117 | simplify_b_predicate2(equivalence(LHS,RHS),Type,Res) :- !, | |
118 | simplify_b_predicate(LHS,SimplifiedLHS), | |
119 | simplify_b_predicate(RHS,SimplifiedRHS), | |
120 | ( same_texpr(SimplifiedLHS,SimplifiedRHS) -> % f <=> f == TRUE | |
121 | create_texpr(truth,Type,[],Res) | |
122 | ; is_negation_of(SimplifiedLHS,SimplifiedRHS) -> % f <=> not(f) == FALSE | |
123 | create_texpr(falsity,Type,[],Res) | |
124 | ; otherwise -> | |
125 | create_equivalence(SimplifiedLHS,SimplifiedRHS,Res) | |
126 | ). | |
127 | simplify_b_predicate2(equal(LHS,RHS),Type,Res) :- !, | |
128 | print(equal(LHS,RHS)),nl, | |
129 | simplify_b_predicate(LHS,SimplifiedLHS), | |
130 | simplify_b_predicate(RHS,SimplifiedRHS), | |
131 | (same_texpr(SimplifiedLHS,SimplifiedRHS) -> | |
132 | create_texpr(truth,Type,[],Res) | |
133 | ; different_texpr_values(SimplifiedLHS,SimplifiedRHS) -> | |
134 | create_texpr(falsity,Type,[],Res) | |
135 | ; otherwise -> | |
136 | compare('==',SimplifiedLHS,SimplifiedRHS,equal,Type,Res) | |
137 | %% extract_info(SimplifiedLHS,SimplifiedRHS,Info), | |
138 | %% create_texpr(equal(SimplifiedLHS,SimplifiedRHS),Type,Info,Res) | |
139 | ). | |
140 | simplify_b_predicate2(not_equal(LHS,RHS),Type,Res) :- !, | |
141 | simplify_b_predicate(LHS,SimplifiedLHS), | |
142 | simplify_b_predicate(RHS,SimplifiedRHS), | |
143 | (same_texpr(SimplifiedLHS,SimplifiedRHS) -> | |
144 | create_texpr(falsity,Type,[],Res) | |
145 | ; different_texpr_values(SimplifiedLHS,SimplifiedRHS) -> | |
146 | create_texpr(truth,Type,[],Res) | |
147 | ; otherwise -> | |
148 | compare('=\\=',SimplifiedLHS,SimplifiedRHS,not_equal,Type,Res) | |
149 | %% extract_info(SimplifiedLHS,SimplifiedRHS,Info), | |
150 | %% create_texpr(not_equal(SimplifiedLHS,SimplifiedRHS),Type,Info,Res) | |
151 | ). | |
152 | simplify_b_predicate2(greater(LHS,RHS),Type,Res) :- !, | |
153 | simplify_b_predicate(LHS,SimplifiedLHS), | |
154 | simplify_b_predicate(RHS,SimplifiedRHS), | |
155 | compare('>',SimplifiedLHS,SimplifiedRHS,greater,Type,Res). | |
156 | simplify_b_predicate2(greater_equal(LHS,RHS),Type,Res) :- !, | |
157 | simplify_b_predicate(LHS,SimplifiedLHS), | |
158 | simplify_b_predicate(RHS,SimplifiedRHS), | |
159 | compare('>=',SimplifiedLHS,SimplifiedRHS,greater_equal,Type,Res). | |
160 | simplify_b_predicate2(less(LHS,RHS),Type,Res) :- !, | |
161 | simplify_b_predicate(LHS,SimplifiedLHS), | |
162 | simplify_b_predicate(RHS,SimplifiedRHS), | |
163 | compare('<',SimplifiedLHS,SimplifiedRHS,less,Type,Res). | |
164 | simplify_b_predicate2(less_equal(LHS,RHS),Type,Res) :- !, | |
165 | simplify_b_predicate(LHS,SimplifiedLHS), | |
166 | simplify_b_predicate(RHS,SimplifiedRHS), | |
167 | compare('=<',SimplifiedLHS,SimplifiedRHS,less_equal,Type,Res). | |
168 | /* Add more sophisticated implementations for simplifying predicates with quatifiers: | |
169 | E.g.: !(x).(x:S => x<21) == max(S) < 21 | |
170 | !(x).(x:S => x/=3) == 3/:S */ | |
171 | % Quantified predcates | |
172 | % !(x).(P => Q) | |
173 | simplify_b_predicate2(forall(Ids,LHS,RHS),Type,Res) :- !, | |
174 | %% trace, | |
175 | simplify_b_predicate(RHS,SimplifiedRHS), | |
176 | (is_true_constant(SimplifiedRHS) -> | |
177 | create_texpr(truth,Type,[],Res) | |
178 | ; otherwise -> | |
179 | simplify_b_predicate(LHS,SimplifiedLHS), | |
180 | create_implication(SimplifiedLHS,SimplifiedRHS,ImplicationRes), | |
181 | create_forall(Ids,ImplicationRes,Res) | |
182 | ). | |
183 | % #(x).(P) | |
184 | simplify_b_predicate2(exists(Ids,Pred),Type,Res) :- !, | |
185 | simplify_b_predicate(Pred,SimplifiedPred), | |
186 | (is_true_constant(SimplifiedPred) -> | |
187 | create_texpr(truth,Type,[],Res) | |
188 | ; is_false_constant(SimplifiedPred) -> | |
189 | create_texpr(falsity,Type,[],Res) | |
190 | ; otherwise -> | |
191 | create_exists(Ids,SimplifiedPred,Res) | |
192 | ). | |
193 | % Simplifying membership relations | |
194 | simplify_b_predicate2(member(Element,Set),Type,Res) :- !, | |
195 | simplify_membership_predicate(Element,Set,Type,Res). | |
196 | simplify_b_predicate2(not_member(Element,Set),Type,Res) :- !, | |
197 | simplify_non_membership_predicate(Element,Set,Type,Res). | |
198 | % TODO: do we need to safe additional information about the predicates | |
199 | simplify_b_predicate2(BExpr,Type,Res) :- | |
200 | create_texpr(BExpr,Type,[],Res). | |
201 | %% (debug_mode(on) -> | |
202 | %% print('Construct not covered yet (b_simplifier):'),nl, | |
203 | %% print(BExpr),nl, | |
204 | %% translate:print_bexpr(Res),nl | |
205 | %% ; true). | |
206 | ||
207 | simplify_negation(negation(BExpr),Res) :- !, % double negation "not not f == f" | |
208 | simplify_b_predicate(BExpr,Res). | |
209 | simplify_negation(BExpr,Res) :- | |
210 | simplify_b_predicate(BExpr,SimplifiedBExpr), | |
211 | % Simplifications like "not(FALSE) == TRUE" and "not(TRUE) == FALSE" will be applied by create_negation/2 | |
212 | create_negation(SimplifiedBExpr,Res). | |
213 | ||
214 | simplify_implication(_LHS,SimplifiedRHS,Res) :- | |
215 | is_true_constant(SimplifiedRHS),!, % f => TRUE == TRUE | |
216 | create_texpr(truth,pred,[],Res). | |
217 | simplify_implication(LHS,SimplifiedRHS,Res) :- | |
218 | is_false_constant(SimplifiedRHS),!, % f => FALSE == neg(f) | |
219 | simplify_b_predicate(LHS,SimplifiedLHS), | |
220 | create_negation(SimplifiedLHS,Res). | |
221 | simplify_implication(LHS,SimplifiedRHS,Res) :- | |
222 | simplify_b_predicate(LHS,SimplifiedLHS), | |
223 | (is_false_constant(SimplifiedLHS) -> % FALSE => f == TRUE | |
224 | create_texpr(truth,pred,[],Res) | |
225 | ; is_true_constant(SimplifiedLHS) -> % TRUE => f == f | |
226 | Res = SimplifiedRHS | |
227 | ; same_texpr(SimplifiedLHS,SimplifiedRHS) -> % f => f == TRUE | |
228 | create_texpr(truth,pred,[],Res) | |
229 | ; otherwise -> | |
230 | create_implication(SimplifiedLHS,SimplifiedRHS,Res) | |
231 | ). | |
232 | ||
233 | ||
234 | %%%%%%%%% This is too trivial, we should consider the absorption and transition rules w.r.t. the origin predicate %%%%%%%%% | |
235 | % P or (P & Q) == P | |
236 | is_absorption_rule_disjunct(LHS,RHS,Res) :- | |
237 | is_a_conjunct(RHS,P,Q), | |
238 | (same_texpr(LHS,P); same_texpr(LHS,Q)),!, | |
239 | Res = LHS. | |
240 | % (P & Q) or P == P | |
241 | is_absorption_rule_disjunct(LHS,RHS,Res) :- | |
242 | is_a_conjunct(LHS,P,Q), | |
243 | (same_texpr(RHS,P); same_texpr(RHS,Q)),!, | |
244 | Res = RHS. | |
245 | ||
246 | % P & (P or Q) == P | |
247 | is_absorption_rule_conjunct(LHS,RHS,Res) :- | |
248 | is_a_disjunct(RHS,P,Q), | |
249 | (same_texpr(LHS,P); same_texpr(LHS,Q)),!, | |
250 | Res = LHS. | |
251 | % (P or Q) & P == P | |
252 | is_absorption_rule_conjunct(LHS,RHS,Res) :- | |
253 | is_a_disjunct(LHS,P,Q), | |
254 | (same_texpr(RHS,P); same_texpr(RHS,Q)),!, | |
255 | Res = RHS. | |
256 | ||
257 | % (P => Q) & (Q => R) == (P => R) | |
258 | test_transitivity(LHS,RHS,Res) :- | |
259 | is_an_implication(LHS,P,Q), | |
260 | is_an_implication(RHS,Q1,R), | |
261 | same_texpr(Q,Q1),!, | |
262 | create_implication(P,R,Res). | |
263 | % (Q => R) & (P => Q) == (P => R) | |
264 | test_transitivity(LHS,RHS,Res) :- | |
265 | is_an_implication(LHS,Q,R), | |
266 | is_an_implication(RHS,P,Q1), | |
267 | same_texpr(Q,Q1),!, | |
268 | create_implication(P,R,Res). | |
269 | ||
270 | ||
271 | simplify_non_membership_predicate(Element,Set,Type,Res) :- | |
272 | b_integer_value(Element,IsIntValue,EX,_NewElement), | |
273 | IsIntValue, | |
274 | test_integer_membership(Set,EX,Type,Res1),!, | |
275 | (is_true_constant(Res1) -> | |
276 | create_texpr(falsity,Type,[],Res) | |
277 | ; is_false_constant(Res1) -> | |
278 | create_texpr(truth,Type,[],Res) | |
279 | ; otherwise -> | |
280 | add_internal_error('Internal error: Unexpected result from test_integer_membership/4 predicate in simplify_membership_predicate/4: ',Res1) | |
281 | ). | |
282 | simplify_non_membership_predicate(Element,Set,Type,Res) :- | |
283 | b_integer_value(Element,_IsIntValue,_EX,NewElement), | |
284 | create_texpr(not_member(NewElement,Set),Type,[],Res). | |
285 | ||
286 | simplify_membership_predicate(Element,Set,Type,Res) :- | |
287 | b_integer_value(Element,IsIntValue,EX,_NewElement), | |
288 | IsIntValue, | |
289 | test_integer_membership(Set,EX,Type,Res),!. | |
290 | simplify_membership_predicate(Element,Set,Type,Res) :- | |
291 | b_integer_value(Element,_IsIntValue,_EX,NewElement), | |
292 | create_texpr(member(NewElement,Set),Type,[],Res). | |
293 | ||
294 | ||
295 | test_integer_membership(b(empty_set,set(integer),_),_X,Type,Res) :- !, | |
296 | create_texpr(falsity,Type,[],Res). | |
297 | test_integer_membership(b(value(avl_set(AVLSet)),set(integer),_),X,Type,Res) :- !, | |
298 | (avl_fetch(int(X),AVLSet) -> | |
299 | create_texpr(truth,Type,[],Res) | |
300 | ; otherwise -> | |
301 | create_texpr(falsity,Type,[],Res) | |
302 | ). | |
303 | test_integer_membership(Set,X,Type,Res) :- | |
304 | is_interval_set(Set,Low,Up),!, | |
305 | ((Low=<X,X=<Up) -> | |
306 | create_texpr(truth,Type,[],Res) | |
307 | ; otherwise -> | |
308 | create_texpr(falsity,Type,[],Res) | |
309 | ). | |
310 | test_integer_membership(Set,X,Type,Res) :- | |
311 | is_global_integer_set(Set,GlobalSet),!, | |
312 | (element_of_global_set(int(X),GlobalSet) -> | |
313 | create_texpr(truth,Type,[],Res) | |
314 | ; otherwise -> | |
315 | create_texpr(falsity,Type,[],Res) | |
316 | ). | |
317 | ||
318 | is_interval_set(b(interval(b(Low,integer,_),b(Up,integer,_)),set(integer),_),Low,Up). | |
319 | ||
320 | is_global_integer_set(Set,GlobalSet) :- | |
321 | get_texpr_expr(Set,SetExpr), | |
322 | SetExpr = integer_set(GlobalSet), | |
323 | memberchk(GlobalSet,['NATURAL','NAT','INTEGER','INT']). | |
324 | ||
325 | is_true_constant(Expr) :- | |
326 | (is_truth(Expr); Expr=boolean_true). | |
327 | ||
328 | is_false_constant(Expr) :- | |
329 | (is_falsity(Expr); Expr=boolean_false). | |
330 | ||
331 | compare(Operator,LHS,RHS,Functor,Type,Res) :- | |
332 | b_integer_value(LHS,IsIntValueX,EX,NewLHS), | |
333 | b_integer_value(RHS,IsIntValueY,EY,NewRHS), | |
334 | ((IsIntValueX,IsIntValueY) -> | |
335 | (memberchk(Operator,['<','>','=<','>=','==','=\\=']) -> | |
336 | Call =.. [Operator,EX,EY], | |
337 | (Call -> create_texpr(truth,Type,[],Res); create_texpr(falsity,Type,[],Res)) | |
338 | ; otherwise -> | |
339 | add_internal_error('Internal error: Unexpected arithmetic comparison Operator: ', Operator), | |
340 | BExpr =.. [Functor,NewLHS,NewRHS], | |
341 | create_texpr(BExpr,Type,[],Res) | |
342 | ) | |
343 | ; otherwise -> | |
344 | BExpr =.. [Functor,NewLHS,NewRHS], | |
345 | create_texpr(BExpr,Type,[],Res) | |
346 | ). | |
347 | ||
348 | b_integer_value(BExpr,IsIntValue,Res,NewBExpr) :- | |
349 | b_arithmetic_expression(BExpr,X),!, | |
350 | Res is X,IsIntValue=true, | |
351 | create_texpr(integer(Res),integer,[],NewBExpr). | |
352 | b_integer_value(BExpr,IsIntValue,Res,NewBExpr) :- | |
353 | Res = BExpr,IsIntValue=false, | |
354 | NewBExpr=BExpr. | |
355 | ||
356 | b_arithmetic_expression(BExpr,Res) :- | |
357 | get_texpr_expr(BExpr,Expr), | |
358 | get_texpr_type(BExpr,integer), % only an integer expression | |
359 | b_arithmetic_expression1(Expr,Res). | |
360 | ||
361 | b_arithmetic_expression1(integer(X),X) :- !, | |
362 | number(X). | |
363 | b_arithmetic_expression1(unary_minus(E),Res) :- !, | |
364 | b_arithmetic_expression(E,ERes), | |
365 | Res = '-'(ERes). | |
366 | b_arithmetic_expression1(add(E1,E2),Res) :- !, | |
367 | b_arithmetic_expression(E1,E1Res), | |
368 | b_arithmetic_expression(E2,E2Res), | |
369 | Res = '+'(E1Res,E2Res). | |
370 | b_arithmetic_expression1(minus(E1,E2),Res) :- !, | |
371 | b_arithmetic_expression(E1,E1Res), | |
372 | b_arithmetic_expression(E2,E2Res), | |
373 | Res = '-'(E1Res,E2Res). | |
374 | b_arithmetic_expression1(multiplication(E1,E2),Res) :- !, | |
375 | b_arithmetic_expression(E1,E1Res), | |
376 | b_arithmetic_expression(E2,E2Res), | |
377 | Res = '*'(E1Res,E2Res). | |
378 | % it is not the same div as in Prolog X/Y will be rounded down | |
379 | %% b_arithmetic_expression1(div(E1,E2),Res) :- !, | |
380 | %% b_arithmetic_expression(E1,E1Res), | |
381 | %% b_arithmetic_expression(E2,E2Res), | |
382 | %% Res = '//'(E1Res,E2Res). |