39348
|
1 |
(* ========================================================================= *)
|
|
2 |
(* THE ACTIVE SET OF CLAUSES *)
|
39349
|
3 |
(* Copyright (c) 2002-2006 Joe Hurd, distributed under the BSD License *)
|
39348
|
4 |
(* ========================================================================= *)
|
|
5 |
|
|
6 |
structure Active :> Active =
|
|
7 |
struct
|
|
8 |
|
|
9 |
open Useful;
|
|
10 |
|
|
11 |
(* ------------------------------------------------------------------------- *)
|
|
12 |
(* Helper functions. *)
|
|
13 |
(* ------------------------------------------------------------------------- *)
|
|
14 |
|
|
15 |
(*MetisDebug
|
|
16 |
local
|
|
17 |
fun mkRewrite ordering =
|
|
18 |
let
|
|
19 |
fun add (cl,rw) =
|
|
20 |
let
|
|
21 |
val {id, thm = th, ...} = Clause.dest cl
|
|
22 |
in
|
|
23 |
case total Thm.destUnitEq th of
|
|
24 |
SOME l_r => Rewrite.add rw (id,(l_r,th))
|
|
25 |
| NONE => rw
|
|
26 |
end
|
|
27 |
in
|
|
28 |
foldl add (Rewrite.new (KnuthBendixOrder.compare ordering))
|
|
29 |
end;
|
|
30 |
|
|
31 |
fun allFactors red =
|
|
32 |
let
|
|
33 |
fun allClause cl =
|
|
34 |
List.all red (cl :: Clause.factor cl) orelse
|
|
35 |
let
|
|
36 |
val () = Print.trace Clause.pp
|
|
37 |
"Active.isSaturated.allFactors: cl" cl
|
|
38 |
in
|
|
39 |
false
|
|
40 |
end
|
|
41 |
in
|
|
42 |
List.all allClause
|
|
43 |
end;
|
|
44 |
|
|
45 |
fun allResolutions red =
|
|
46 |
let
|
|
47 |
fun allClause2 cl_lit cl =
|
|
48 |
let
|
|
49 |
fun allLiteral2 lit =
|
|
50 |
case total (Clause.resolve cl_lit) (cl,lit) of
|
|
51 |
NONE => true
|
|
52 |
| SOME cl => allFactors red [cl]
|
|
53 |
in
|
|
54 |
LiteralSet.all allLiteral2 (Clause.literals cl)
|
|
55 |
end orelse
|
|
56 |
let
|
|
57 |
val () = Print.trace Clause.pp
|
|
58 |
"Active.isSaturated.allResolutions: cl2" cl
|
|
59 |
in
|
|
60 |
false
|
|
61 |
end
|
|
62 |
|
|
63 |
fun allClause1 allCls cl =
|
|
64 |
let
|
|
65 |
val cl = Clause.freshVars cl
|
|
66 |
|
|
67 |
fun allLiteral1 lit = List.all (allClause2 (cl,lit)) allCls
|
|
68 |
in
|
|
69 |
LiteralSet.all allLiteral1 (Clause.literals cl)
|
|
70 |
end orelse
|
|
71 |
let
|
|
72 |
val () = Print.trace Clause.pp
|
|
73 |
"Active.isSaturated.allResolutions: cl1" cl
|
|
74 |
in
|
|
75 |
false
|
|
76 |
end
|
|
77 |
|
|
78 |
in
|
|
79 |
fn [] => true
|
|
80 |
| allCls as cl :: cls =>
|
|
81 |
allClause1 allCls cl andalso allResolutions red cls
|
|
82 |
end;
|
|
83 |
|
|
84 |
fun allParamodulations red cls =
|
|
85 |
let
|
|
86 |
fun allClause2 cl_lit_ort_tm cl =
|
|
87 |
let
|
|
88 |
fun allLiteral2 lit =
|
|
89 |
let
|
|
90 |
val para = Clause.paramodulate cl_lit_ort_tm
|
|
91 |
|
|
92 |
fun allSubterms (path,tm) =
|
|
93 |
case total para (cl,lit,path,tm) of
|
|
94 |
NONE => true
|
|
95 |
| SOME cl => allFactors red [cl]
|
|
96 |
in
|
|
97 |
List.all allSubterms (Literal.nonVarTypedSubterms lit)
|
|
98 |
end orelse
|
|
99 |
let
|
|
100 |
val () = Print.trace Literal.pp
|
|
101 |
"Active.isSaturated.allParamodulations: lit2" lit
|
|
102 |
in
|
|
103 |
false
|
|
104 |
end
|
|
105 |
in
|
|
106 |
LiteralSet.all allLiteral2 (Clause.literals cl)
|
|
107 |
end orelse
|
|
108 |
let
|
|
109 |
val () = Print.trace Clause.pp
|
|
110 |
"Active.isSaturated.allParamodulations: cl2" cl
|
|
111 |
val (_,_,ort,_) = cl_lit_ort_tm
|
|
112 |
val () = Print.trace Rewrite.ppOrient
|
|
113 |
"Active.isSaturated.allParamodulations: ort1" ort
|
|
114 |
in
|
|
115 |
false
|
|
116 |
end
|
|
117 |
|
|
118 |
fun allClause1 cl =
|
|
119 |
let
|
|
120 |
val cl = Clause.freshVars cl
|
|
121 |
|
|
122 |
fun allLiteral1 lit =
|
|
123 |
let
|
|
124 |
fun allCl2 x = List.all (allClause2 x) cls
|
|
125 |
in
|
|
126 |
case total Literal.destEq lit of
|
|
127 |
NONE => true
|
|
128 |
| SOME (l,r) =>
|
|
129 |
allCl2 (cl,lit,Rewrite.LeftToRight,l) andalso
|
|
130 |
allCl2 (cl,lit,Rewrite.RightToLeft,r)
|
|
131 |
end orelse
|
|
132 |
let
|
|
133 |
val () = Print.trace Literal.pp
|
|
134 |
"Active.isSaturated.allParamodulations: lit1" lit
|
|
135 |
in
|
|
136 |
false
|
|
137 |
end
|
|
138 |
in
|
|
139 |
LiteralSet.all allLiteral1 (Clause.literals cl)
|
|
140 |
end orelse
|
|
141 |
let
|
|
142 |
val () = Print.trace Clause.pp
|
|
143 |
"Active.isSaturated.allParamodulations: cl1" cl
|
|
144 |
in
|
|
145 |
false
|
|
146 |
end
|
|
147 |
in
|
|
148 |
List.all allClause1 cls
|
|
149 |
end;
|
|
150 |
|
|
151 |
fun redundant {subsume,reduce,rewrite} =
|
|
152 |
let
|
|
153 |
fun simp cl =
|
|
154 |
case Clause.simplify cl of
|
|
155 |
NONE => true
|
|
156 |
| SOME cl =>
|
|
157 |
Subsume.isStrictlySubsumed subsume (Clause.literals cl) orelse
|
|
158 |
let
|
|
159 |
val cl' = cl
|
|
160 |
val cl' = Clause.reduce reduce cl'
|
|
161 |
val cl' = Clause.rewrite rewrite cl'
|
|
162 |
in
|
|
163 |
not (Clause.equalThms cl cl') andalso
|
|
164 |
(simp cl' orelse
|
|
165 |
let
|
|
166 |
val () = Print.trace Clause.pp
|
|
167 |
"Active.isSaturated.redundant: cl'" cl'
|
|
168 |
in
|
|
169 |
false
|
|
170 |
end)
|
|
171 |
end
|
|
172 |
in
|
|
173 |
fn cl =>
|
|
174 |
simp cl orelse
|
|
175 |
let
|
|
176 |
val () = Print.trace Clause.pp
|
|
177 |
"Active.isSaturated.redundant: cl" cl
|
|
178 |
in
|
|
179 |
false
|
|
180 |
end
|
|
181 |
end;
|
|
182 |
in
|
|
183 |
fun isSaturated ordering subs cls =
|
|
184 |
let
|
|
185 |
val rd = Units.empty
|
|
186 |
val rw = mkRewrite ordering cls
|
|
187 |
val red = redundant {subsume = subs, reduce = rd, rewrite = rw}
|
|
188 |
in
|
|
189 |
(allFactors red cls andalso
|
|
190 |
allResolutions red cls andalso
|
|
191 |
allParamodulations red cls) orelse
|
|
192 |
let
|
|
193 |
val () = Print.trace Rewrite.pp "Active.isSaturated: rw" rw
|
|
194 |
val () = Print.trace (Print.ppList Clause.pp)
|
|
195 |
"Active.isSaturated: clauses" cls
|
|
196 |
in
|
|
197 |
false
|
|
198 |
end
|
|
199 |
end;
|
|
200 |
end;
|
|
201 |
|
|
202 |
fun checkSaturated ordering subs cls =
|
|
203 |
if isSaturated ordering subs cls then ()
|
|
204 |
else raise Bug "Active.checkSaturated";
|
|
205 |
*)
|
|
206 |
|
|
207 |
(* ------------------------------------------------------------------------- *)
|
|
208 |
(* A type of active clause sets. *)
|
|
209 |
(* ------------------------------------------------------------------------- *)
|
|
210 |
|
|
211 |
type simplify = {subsume : bool, reduce : bool, rewrite : bool};
|
|
212 |
|
|
213 |
type parameters =
|
|
214 |
{clause : Clause.parameters,
|
|
215 |
prefactor : simplify,
|
|
216 |
postfactor : simplify};
|
|
217 |
|
|
218 |
datatype active =
|
|
219 |
Active of
|
|
220 |
{parameters : parameters,
|
|
221 |
clauses : Clause.clause IntMap.map,
|
|
222 |
units : Units.units,
|
|
223 |
rewrite : Rewrite.rewrite,
|
|
224 |
subsume : Clause.clause Subsume.subsume,
|
|
225 |
literals : (Clause.clause * Literal.literal) LiteralNet.literalNet,
|
|
226 |
equations :
|
|
227 |
(Clause.clause * Literal.literal * Rewrite.orient * Term.term)
|
|
228 |
TermNet.termNet,
|
|
229 |
subterms :
|
|
230 |
(Clause.clause * Literal.literal * Term.path * Term.term)
|
|
231 |
TermNet.termNet,
|
|
232 |
allSubterms : (Clause.clause * Term.term) TermNet.termNet};
|
|
233 |
|
|
234 |
fun getSubsume (Active {subsume = s, ...}) = s;
|
|
235 |
|
|
236 |
fun setRewrite active rewrite =
|
|
237 |
let
|
|
238 |
val Active
|
|
239 |
{parameters,clauses,units,subsume,literals,equations,
|
|
240 |
subterms,allSubterms,...} = active
|
|
241 |
in
|
|
242 |
Active
|
|
243 |
{parameters = parameters, clauses = clauses, units = units,
|
|
244 |
rewrite = rewrite, subsume = subsume, literals = literals,
|
|
245 |
equations = equations, subterms = subterms, allSubterms = allSubterms}
|
|
246 |
end;
|
|
247 |
|
|
248 |
(* ------------------------------------------------------------------------- *)
|
|
249 |
(* Basic operations. *)
|
|
250 |
(* ------------------------------------------------------------------------- *)
|
|
251 |
|
|
252 |
val maxSimplify : simplify = {subsume = true, reduce = true, rewrite = true};
|
|
253 |
|
|
254 |
val default : parameters =
|
|
255 |
{clause = Clause.default,
|
|
256 |
prefactor = maxSimplify,
|
|
257 |
postfactor = maxSimplify};
|
|
258 |
|
|
259 |
fun empty parameters =
|
|
260 |
let
|
|
261 |
val {clause,...} = parameters
|
|
262 |
val {ordering,...} = clause
|
|
263 |
in
|
|
264 |
Active
|
|
265 |
{parameters = parameters,
|
|
266 |
clauses = IntMap.new (),
|
|
267 |
units = Units.empty,
|
|
268 |
rewrite = Rewrite.new (KnuthBendixOrder.compare ordering),
|
|
269 |
subsume = Subsume.new (),
|
|
270 |
literals = LiteralNet.new {fifo = false},
|
|
271 |
equations = TermNet.new {fifo = false},
|
|
272 |
subterms = TermNet.new {fifo = false},
|
|
273 |
allSubterms = TermNet.new {fifo = false}}
|
|
274 |
end;
|
|
275 |
|
|
276 |
fun size (Active {clauses,...}) = IntMap.size clauses;
|
|
277 |
|
|
278 |
fun clauses (Active {clauses = cls, ...}) =
|
|
279 |
let
|
|
280 |
fun add (_,cl,acc) = cl :: acc
|
|
281 |
in
|
|
282 |
IntMap.foldr add [] cls
|
|
283 |
end;
|
|
284 |
|
|
285 |
fun saturation active =
|
|
286 |
let
|
|
287 |
fun remove (cl,(cls,subs)) =
|
|
288 |
let
|
|
289 |
val lits = Clause.literals cl
|
|
290 |
in
|
|
291 |
if Subsume.isStrictlySubsumed subs lits then (cls,subs)
|
|
292 |
else (cl :: cls, Subsume.insert subs (lits,()))
|
|
293 |
end
|
|
294 |
|
|
295 |
val cls = clauses active
|
|
296 |
val (cls,_) = foldl remove ([], Subsume.new ()) cls
|
|
297 |
val (cls,subs) = foldl remove ([], Subsume.new ()) cls
|
|
298 |
|
|
299 |
(*MetisDebug
|
|
300 |
val Active {parameters,...} = active
|
|
301 |
val {clause,...} = parameters
|
|
302 |
val {ordering,...} = clause
|
|
303 |
val () = checkSaturated ordering subs cls
|
|
304 |
*)
|
|
305 |
in
|
|
306 |
cls
|
|
307 |
end;
|
|
308 |
|
|
309 |
(* ------------------------------------------------------------------------- *)
|
|
310 |
(* Pretty printing. *)
|
|
311 |
(* ------------------------------------------------------------------------- *)
|
|
312 |
|
|
313 |
val pp =
|
|
314 |
let
|
|
315 |
fun toStr active = "Active{" ^ Int.toString (size active) ^ "}"
|
|
316 |
in
|
|
317 |
Print.ppMap toStr Print.ppString
|
|
318 |
end;
|
|
319 |
|
|
320 |
(*MetisDebug
|
|
321 |
local
|
|
322 |
fun ppField f ppA a =
|
|
323 |
Print.blockProgram Print.Inconsistent 2
|
|
324 |
[Print.addString (f ^ " ="),
|
|
325 |
Print.addBreak 1,
|
|
326 |
ppA a];
|
|
327 |
|
|
328 |
val ppClauses =
|
|
329 |
ppField "clauses"
|
|
330 |
(Print.ppMap IntMap.toList
|
|
331 |
(Print.ppList (Print.ppPair Print.ppInt Clause.pp)));
|
|
332 |
|
|
333 |
val ppRewrite = ppField "rewrite" Rewrite.pp;
|
|
334 |
|
|
335 |
val ppSubterms =
|
|
336 |
ppField "subterms"
|
|
337 |
(TermNet.pp
|
|
338 |
(Print.ppMap (fn (c,l,p,t) => ((Clause.id c, l, p), t))
|
|
339 |
(Print.ppPair
|
|
340 |
(Print.ppTriple Print.ppInt Literal.pp Term.ppPath)
|
|
341 |
Term.pp)));
|
|
342 |
in
|
|
343 |
fun pp (Active {clauses,rewrite,subterms,...}) =
|
|
344 |
Print.blockProgram Print.Inconsistent 2
|
|
345 |
[Print.addString "Active",
|
|
346 |
Print.addBreak 1,
|
|
347 |
Print.blockProgram Print.Inconsistent 1
|
|
348 |
[Print.addString "{",
|
|
349 |
ppClauses clauses,
|
|
350 |
Print.addString ",",
|
|
351 |
Print.addBreak 1,
|
|
352 |
ppRewrite rewrite,
|
|
353 |
(*MetisTrace5
|
|
354 |
Print.addString ",",
|
|
355 |
Print.addBreak 1,
|
|
356 |
ppSubterms subterms,
|
|
357 |
*)
|
|
358 |
Print.skip],
|
|
359 |
Print.addString "}"];
|
|
360 |
end;
|
|
361 |
*)
|
|
362 |
|
|
363 |
val toString = Print.toString pp;
|
|
364 |
|
|
365 |
(* ------------------------------------------------------------------------- *)
|
|
366 |
(* Simplify clauses. *)
|
|
367 |
(* ------------------------------------------------------------------------- *)
|
|
368 |
|
|
369 |
fun simplify simp units rewr subs =
|
|
370 |
let
|
|
371 |
val {subsume = s, reduce = r, rewrite = w} = simp
|
|
372 |
|
|
373 |
fun rewrite cl =
|
|
374 |
let
|
|
375 |
val cl' = Clause.rewrite rewr cl
|
|
376 |
in
|
|
377 |
if Clause.equalThms cl cl' then SOME cl else Clause.simplify cl'
|
|
378 |
end
|
|
379 |
in
|
|
380 |
fn cl =>
|
|
381 |
case Clause.simplify cl of
|
|
382 |
NONE => NONE
|
|
383 |
| SOME cl =>
|
|
384 |
case (if w then rewrite cl else SOME cl) of
|
|
385 |
NONE => NONE
|
|
386 |
| SOME cl =>
|
|
387 |
let
|
|
388 |
val cl = if r then Clause.reduce units cl else cl
|
|
389 |
in
|
|
390 |
if s andalso Clause.subsumes subs cl then NONE else SOME cl
|
|
391 |
end
|
|
392 |
end;
|
|
393 |
|
|
394 |
(*MetisDebug
|
|
395 |
val simplify = fn simp => fn units => fn rewr => fn subs => fn cl =>
|
|
396 |
let
|
|
397 |
fun traceCl s = Print.trace Clause.pp ("Active.simplify: " ^ s)
|
|
398 |
(*MetisTrace4
|
|
399 |
val ppClOpt = Print.ppOption Clause.pp
|
|
400 |
val () = traceCl "cl" cl
|
|
401 |
*)
|
|
402 |
val cl' = simplify simp units rewr subs cl
|
|
403 |
(*MetisTrace4
|
|
404 |
val () = Print.trace ppClOpt "Active.simplify: cl'" cl'
|
|
405 |
*)
|
|
406 |
val () =
|
|
407 |
case cl' of
|
|
408 |
NONE => ()
|
|
409 |
| SOME cl' =>
|
|
410 |
case
|
|
411 |
(case simplify simp units rewr subs cl' of
|
|
412 |
NONE => SOME ("away", K ())
|
|
413 |
| SOME cl'' =>
|
|
414 |
if Clause.equalThms cl' cl'' then NONE
|
|
415 |
else SOME ("further", fn () => traceCl "cl''" cl'')) of
|
|
416 |
NONE => ()
|
|
417 |
| SOME (e,f) =>
|
|
418 |
let
|
|
419 |
val () = traceCl "cl" cl
|
|
420 |
val () = traceCl "cl'" cl'
|
|
421 |
val () = f ()
|
|
422 |
in
|
|
423 |
raise
|
|
424 |
Bug
|
|
425 |
("Active.simplify: clause should have been simplified "^e)
|
|
426 |
end
|
|
427 |
in
|
|
428 |
cl'
|
|
429 |
end;
|
|
430 |
*)
|
|
431 |
|
|
432 |
fun simplifyActive simp active =
|
|
433 |
let
|
|
434 |
val Active {units,rewrite,subsume,...} = active
|
|
435 |
in
|
|
436 |
simplify simp units rewrite subsume
|
|
437 |
end;
|
|
438 |
|
|
439 |
(* ------------------------------------------------------------------------- *)
|
|
440 |
(* Add a clause into the active set. *)
|
|
441 |
(* ------------------------------------------------------------------------- *)
|
|
442 |
|
|
443 |
fun addUnit units cl =
|
|
444 |
let
|
|
445 |
val th = Clause.thm cl
|
|
446 |
in
|
|
447 |
case total Thm.destUnit th of
|
|
448 |
SOME lit => Units.add units (lit,th)
|
|
449 |
| NONE => units
|
|
450 |
end;
|
|
451 |
|
|
452 |
fun addRewrite rewrite cl =
|
|
453 |
let
|
|
454 |
val th = Clause.thm cl
|
|
455 |
in
|
|
456 |
case total Thm.destUnitEq th of
|
|
457 |
SOME l_r => Rewrite.add rewrite (Clause.id cl, (l_r,th))
|
|
458 |
| NONE => rewrite
|
|
459 |
end;
|
|
460 |
|
|
461 |
fun addSubsume subsume cl = Subsume.insert subsume (Clause.literals cl, cl);
|
|
462 |
|
|
463 |
fun addLiterals literals cl =
|
|
464 |
let
|
|
465 |
fun add (lit as (_,atm), literals) =
|
|
466 |
if Atom.isEq atm then literals
|
|
467 |
else LiteralNet.insert literals (lit,(cl,lit))
|
|
468 |
in
|
|
469 |
LiteralSet.foldl add literals (Clause.largestLiterals cl)
|
|
470 |
end;
|
|
471 |
|
|
472 |
fun addEquations equations cl =
|
|
473 |
let
|
|
474 |
fun add ((lit,ort,tm),equations) =
|
|
475 |
TermNet.insert equations (tm,(cl,lit,ort,tm))
|
|
476 |
in
|
|
477 |
foldl add equations (Clause.largestEquations cl)
|
|
478 |
end;
|
|
479 |
|
|
480 |
fun addSubterms subterms cl =
|
|
481 |
let
|
|
482 |
fun add ((lit,path,tm),subterms) =
|
|
483 |
TermNet.insert subterms (tm,(cl,lit,path,tm))
|
|
484 |
in
|
|
485 |
foldl add subterms (Clause.largestSubterms cl)
|
|
486 |
end;
|
|
487 |
|
|
488 |
fun addAllSubterms allSubterms cl =
|
|
489 |
let
|
|
490 |
fun add ((_,_,tm),allSubterms) =
|
|
491 |
TermNet.insert allSubterms (tm,(cl,tm))
|
|
492 |
in
|
|
493 |
foldl add allSubterms (Clause.allSubterms cl)
|
|
494 |
end;
|
|
495 |
|
|
496 |
fun addClause active cl =
|
|
497 |
let
|
|
498 |
val Active
|
|
499 |
{parameters,clauses,units,rewrite,subsume,literals,
|
|
500 |
equations,subterms,allSubterms} = active
|
|
501 |
val clauses = IntMap.insert clauses (Clause.id cl, cl)
|
|
502 |
and subsume = addSubsume subsume cl
|
|
503 |
and literals = addLiterals literals cl
|
|
504 |
and equations = addEquations equations cl
|
|
505 |
and subterms = addSubterms subterms cl
|
|
506 |
and allSubterms = addAllSubterms allSubterms cl
|
|
507 |
in
|
|
508 |
Active
|
|
509 |
{parameters = parameters, clauses = clauses, units = units,
|
|
510 |
rewrite = rewrite, subsume = subsume, literals = literals,
|
|
511 |
equations = equations, subterms = subterms,
|
|
512 |
allSubterms = allSubterms}
|
|
513 |
end;
|
|
514 |
|
|
515 |
fun addFactorClause active cl =
|
|
516 |
let
|
|
517 |
val Active
|
|
518 |
{parameters,clauses,units,rewrite,subsume,literals,
|
|
519 |
equations,subterms,allSubterms} = active
|
|
520 |
val units = addUnit units cl
|
|
521 |
and rewrite = addRewrite rewrite cl
|
|
522 |
in
|
|
523 |
Active
|
|
524 |
{parameters = parameters, clauses = clauses, units = units,
|
|
525 |
rewrite = rewrite, subsume = subsume, literals = literals,
|
|
526 |
equations = equations, subterms = subterms, allSubterms = allSubterms}
|
|
527 |
end;
|
|
528 |
|
|
529 |
(* ------------------------------------------------------------------------- *)
|
|
530 |
(* Derive (unfactored) consequences of a clause. *)
|
|
531 |
(* ------------------------------------------------------------------------- *)
|
|
532 |
|
|
533 |
fun deduceResolution literals cl (lit as (_,atm), acc) =
|
|
534 |
let
|
|
535 |
fun resolve (cl_lit,acc) =
|
|
536 |
case total (Clause.resolve cl_lit) (cl,lit) of
|
|
537 |
SOME cl' => cl' :: acc
|
|
538 |
| NONE => acc
|
|
539 |
(*MetisTrace4
|
|
540 |
val () = Print.trace Literal.pp "Active.deduceResolution: lit" lit
|
|
541 |
*)
|
|
542 |
in
|
|
543 |
if Atom.isEq atm then acc
|
|
544 |
else foldl resolve acc (LiteralNet.unify literals (Literal.negate lit))
|
|
545 |
end;
|
|
546 |
|
|
547 |
fun deduceParamodulationWith subterms cl ((lit,ort,tm),acc) =
|
|
548 |
let
|
|
549 |
fun para (cl_lit_path_tm,acc) =
|
|
550 |
case total (Clause.paramodulate (cl,lit,ort,tm)) cl_lit_path_tm of
|
|
551 |
SOME cl' => cl' :: acc
|
|
552 |
| NONE => acc
|
|
553 |
in
|
|
554 |
foldl para acc (TermNet.unify subterms tm)
|
|
555 |
end;
|
|
556 |
|
|
557 |
fun deduceParamodulationInto equations cl ((lit,path,tm),acc) =
|
|
558 |
let
|
|
559 |
fun para (cl_lit_ort_tm,acc) =
|
|
560 |
case total (Clause.paramodulate cl_lit_ort_tm) (cl,lit,path,tm) of
|
|
561 |
SOME cl' => cl' :: acc
|
|
562 |
| NONE => acc
|
|
563 |
in
|
|
564 |
foldl para acc (TermNet.unify equations tm)
|
|
565 |
end;
|
|
566 |
|
|
567 |
fun deduce active cl =
|
|
568 |
let
|
|
569 |
val Active {parameters,literals,equations,subterms,...} = active
|
|
570 |
|
|
571 |
val lits = Clause.largestLiterals cl
|
|
572 |
val eqns = Clause.largestEquations cl
|
|
573 |
val subtms =
|
|
574 |
if TermNet.null equations then [] else Clause.largestSubterms cl
|
|
575 |
(*MetisTrace5
|
|
576 |
val () = Print.trace LiteralSet.pp "Active.deduce: lits" lits
|
|
577 |
val () = Print.trace
|
|
578 |
(Print.ppList
|
|
579 |
(Print.ppMap (fn (lit,ort,_) => (lit,ort))
|
|
580 |
(Print.ppPair Literal.pp Rewrite.ppOrient)))
|
|
581 |
"Active.deduce: eqns" eqns
|
|
582 |
val () = Print.trace
|
|
583 |
(Print.ppList
|
|
584 |
(Print.ppTriple Literal.pp Term.ppPath Term.pp))
|
|
585 |
"Active.deduce: subtms" subtms
|
|
586 |
*)
|
|
587 |
|
|
588 |
val acc = []
|
|
589 |
val acc = LiteralSet.foldl (deduceResolution literals cl) acc lits
|
|
590 |
val acc = foldl (deduceParamodulationWith subterms cl) acc eqns
|
|
591 |
val acc = foldl (deduceParamodulationInto equations cl) acc subtms
|
|
592 |
val acc = rev acc
|
|
593 |
|
|
594 |
(*MetisTrace5
|
|
595 |
val () = Print.trace (Print.ppList Clause.pp) "Active.deduce: acc" acc
|
|
596 |
*)
|
|
597 |
in
|
|
598 |
acc
|
|
599 |
end;
|
|
600 |
|
|
601 |
(* ------------------------------------------------------------------------- *)
|
|
602 |
(* Extract clauses from the active set that can be simplified. *)
|
|
603 |
(* ------------------------------------------------------------------------- *)
|
|
604 |
|
|
605 |
local
|
|
606 |
fun clause_rewritables active =
|
|
607 |
let
|
|
608 |
val Active {clauses,rewrite,...} = active
|
|
609 |
|
|
610 |
fun rewr (id,cl,ids) =
|
|
611 |
let
|
|
612 |
val cl' = Clause.rewrite rewrite cl
|
|
613 |
in
|
|
614 |
if Clause.equalThms cl cl' then ids else IntSet.add ids id
|
|
615 |
end
|
|
616 |
in
|
|
617 |
IntMap.foldr rewr IntSet.empty clauses
|
|
618 |
end;
|
|
619 |
|
|
620 |
fun orderedRedexResidues (((l,r),_),ort) =
|
|
621 |
case ort of
|
|
622 |
NONE => []
|
|
623 |
| SOME Rewrite.LeftToRight => [(l,r,true)]
|
|
624 |
| SOME Rewrite.RightToLeft => [(r,l,true)];
|
|
625 |
|
|
626 |
fun unorderedRedexResidues (((l,r),_),ort) =
|
|
627 |
case ort of
|
|
628 |
NONE => [(l,r,false),(r,l,false)]
|
|
629 |
| SOME _ => [];
|
|
630 |
|
|
631 |
fun rewrite_rewritables active rewr_ids =
|
|
632 |
let
|
|
633 |
val Active {parameters,rewrite,clauses,allSubterms,...} = active
|
|
634 |
val {clause = {ordering,...}, ...} = parameters
|
|
635 |
val order = KnuthBendixOrder.compare ordering
|
|
636 |
|
|
637 |
fun addRewr (id,acc) =
|
|
638 |
if IntMap.inDomain id clauses then IntSet.add acc id else acc
|
|
639 |
|
|
640 |
fun addReduce ((l,r,ord),acc) =
|
|
641 |
let
|
|
642 |
fun isValidRewr tm =
|
|
643 |
case total (Subst.match Subst.empty l) tm of
|
|
644 |
NONE => false
|
|
645 |
| SOME sub =>
|
|
646 |
ord orelse
|
|
647 |
let
|
|
648 |
val tm' = Subst.subst (Subst.normalize sub) r
|
|
649 |
in
|
|
650 |
order (tm,tm') = SOME GREATER
|
|
651 |
end
|
|
652 |
|
|
653 |
fun addRed ((cl,tm),acc) =
|
|
654 |
let
|
|
655 |
(*MetisTrace5
|
|
656 |
val () = Print.trace Clause.pp "Active.addRed: cl" cl
|
|
657 |
val () = Print.trace Term.pp "Active.addRed: tm" tm
|
|
658 |
*)
|
|
659 |
val id = Clause.id cl
|
|
660 |
in
|
|
661 |
if IntSet.member id acc then acc
|
|
662 |
else if not (isValidRewr tm) then acc
|
|
663 |
else IntSet.add acc id
|
|
664 |
end
|
|
665 |
|
|
666 |
(*MetisTrace5
|
|
667 |
val () = Print.trace Term.pp "Active.addReduce: l" l
|
|
668 |
val () = Print.trace Term.pp "Active.addReduce: r" r
|
|
669 |
val () = Print.trace Print.ppBool "Active.addReduce: ord" ord
|
|
670 |
*)
|
|
671 |
in
|
|
672 |
List.foldl addRed acc (TermNet.matched allSubterms l)
|
|
673 |
end
|
|
674 |
|
|
675 |
fun addEquation redexResidues (id,acc) =
|
|
676 |
case Rewrite.peek rewrite id of
|
|
677 |
NONE => acc
|
|
678 |
| SOME eqn_ort => List.foldl addReduce acc (redexResidues eqn_ort)
|
|
679 |
|
|
680 |
val addOrdered = addEquation orderedRedexResidues
|
|
681 |
|
|
682 |
val addUnordered = addEquation unorderedRedexResidues
|
|
683 |
|
|
684 |
val ids = IntSet.empty
|
|
685 |
val ids = List.foldl addRewr ids rewr_ids
|
|
686 |
val ids = List.foldl addOrdered ids rewr_ids
|
|
687 |
val ids = List.foldl addUnordered ids rewr_ids
|
|
688 |
in
|
|
689 |
ids
|
|
690 |
end;
|
|
691 |
|
|
692 |
fun choose_clause_rewritables active ids = size active <= length ids
|
|
693 |
|
|
694 |
fun rewritables active ids =
|
|
695 |
if choose_clause_rewritables active ids then clause_rewritables active
|
|
696 |
else rewrite_rewritables active ids;
|
|
697 |
|
|
698 |
(*MetisDebug
|
|
699 |
val rewritables = fn active => fn ids =>
|
|
700 |
let
|
|
701 |
val clause_ids = clause_rewritables active
|
|
702 |
val rewrite_ids = rewrite_rewritables active ids
|
|
703 |
|
|
704 |
val () =
|
|
705 |
if IntSet.equal rewrite_ids clause_ids then ()
|
|
706 |
else
|
|
707 |
let
|
|
708 |
val ppIdl = Print.ppList Print.ppInt
|
|
709 |
val ppIds = Print.ppMap IntSet.toList ppIdl
|
|
710 |
val () = Print.trace pp "Active.rewritables: active" active
|
|
711 |
val () = Print.trace ppIdl "Active.rewritables: ids" ids
|
|
712 |
val () = Print.trace ppIds
|
|
713 |
"Active.rewritables: clause_ids" clause_ids
|
|
714 |
val () = Print.trace ppIds
|
|
715 |
"Active.rewritables: rewrite_ids" rewrite_ids
|
|
716 |
in
|
|
717 |
raise Bug "Active.rewritables: ~(rewrite_ids SUBSET clause_ids)"
|
|
718 |
end
|
|
719 |
in
|
|
720 |
if choose_clause_rewritables active ids then clause_ids else rewrite_ids
|
|
721 |
end;
|
|
722 |
*)
|
|
723 |
|
|
724 |
fun delete active ids =
|
|
725 |
if IntSet.null ids then active
|
|
726 |
else
|
|
727 |
let
|
|
728 |
fun idPred id = not (IntSet.member id ids)
|
|
729 |
|
|
730 |
fun clausePred cl = idPred (Clause.id cl)
|
|
731 |
|
|
732 |
val Active
|
|
733 |
{parameters,
|
|
734 |
clauses,
|
|
735 |
units,
|
|
736 |
rewrite,
|
|
737 |
subsume,
|
|
738 |
literals,
|
|
739 |
equations,
|
|
740 |
subterms,
|
|
741 |
allSubterms} = active
|
|
742 |
|
|
743 |
val clauses = IntMap.filter (idPred o fst) clauses
|
|
744 |
and subsume = Subsume.filter clausePred subsume
|
|
745 |
and literals = LiteralNet.filter (clausePred o #1) literals
|
|
746 |
and equations = TermNet.filter (clausePred o #1) equations
|
|
747 |
and subterms = TermNet.filter (clausePred o #1) subterms
|
|
748 |
and allSubterms = TermNet.filter (clausePred o fst) allSubterms
|
|
749 |
in
|
|
750 |
Active
|
|
751 |
{parameters = parameters,
|
|
752 |
clauses = clauses,
|
|
753 |
units = units,
|
|
754 |
rewrite = rewrite,
|
|
755 |
subsume = subsume,
|
|
756 |
literals = literals,
|
|
757 |
equations = equations,
|
|
758 |
subterms = subterms,
|
|
759 |
allSubterms = allSubterms}
|
|
760 |
end;
|
|
761 |
in
|
|
762 |
fun extract_rewritables (active as Active {clauses,rewrite,...}) =
|
|
763 |
if Rewrite.isReduced rewrite then (active,[])
|
|
764 |
else
|
|
765 |
let
|
|
766 |
(*MetisTrace3
|
|
767 |
val () = trace "Active.extract_rewritables: inter-reducing\n"
|
|
768 |
*)
|
|
769 |
val (rewrite,ids) = Rewrite.reduce' rewrite
|
|
770 |
val active = setRewrite active rewrite
|
|
771 |
val ids = rewritables active ids
|
|
772 |
val cls = IntSet.transform (IntMap.get clauses) ids
|
|
773 |
(*MetisTrace3
|
|
774 |
val ppCls = Print.ppList Clause.pp
|
|
775 |
val () = Print.trace ppCls "Active.extract_rewritables: cls" cls
|
|
776 |
*)
|
|
777 |
in
|
|
778 |
(delete active ids, cls)
|
|
779 |
end
|
|
780 |
(*MetisDebug
|
|
781 |
handle Error err =>
|
|
782 |
raise Bug ("Active.extract_rewritables: shouldn't fail\n" ^ err);
|
|
783 |
*)
|
|
784 |
end;
|
|
785 |
|
|
786 |
(* ------------------------------------------------------------------------- *)
|
|
787 |
(* Factor clauses. *)
|
|
788 |
(* ------------------------------------------------------------------------- *)
|
|
789 |
|
|
790 |
local
|
|
791 |
fun prefactor_simplify active subsume =
|
|
792 |
let
|
|
793 |
val Active {parameters,units,rewrite,...} = active
|
|
794 |
val {prefactor,...} = parameters
|
|
795 |
in
|
|
796 |
simplify prefactor units rewrite subsume
|
|
797 |
end;
|
|
798 |
|
|
799 |
fun postfactor_simplify active subsume =
|
|
800 |
let
|
|
801 |
val Active {parameters,units,rewrite,...} = active
|
|
802 |
val {postfactor,...} = parameters
|
|
803 |
in
|
|
804 |
simplify postfactor units rewrite subsume
|
|
805 |
end;
|
|
806 |
|
|
807 |
val sort_utilitywise =
|
|
808 |
let
|
|
809 |
fun utility cl =
|
|
810 |
case LiteralSet.size (Clause.literals cl) of
|
|
811 |
0 => ~1
|
|
812 |
| 1 => if Thm.isUnitEq (Clause.thm cl) then 0 else 1
|
|
813 |
| n => n
|
|
814 |
in
|
|
815 |
sortMap utility Int.compare
|
|
816 |
end;
|
|
817 |
|
|
818 |
fun factor_add (cl, active_subsume_acc as (active,subsume,acc)) =
|
|
819 |
case postfactor_simplify active subsume cl of
|
|
820 |
NONE => active_subsume_acc
|
|
821 |
| SOME cl =>
|
|
822 |
let
|
|
823 |
val active = addFactorClause active cl
|
|
824 |
and subsume = addSubsume subsume cl
|
|
825 |
and acc = cl :: acc
|
|
826 |
in
|
|
827 |
(active,subsume,acc)
|
|
828 |
end;
|
|
829 |
|
|
830 |
fun factor1 (cl, active_subsume_acc as (active,subsume,_)) =
|
|
831 |
case prefactor_simplify active subsume cl of
|
|
832 |
NONE => active_subsume_acc
|
|
833 |
| SOME cl =>
|
|
834 |
let
|
|
835 |
val cls = sort_utilitywise (cl :: Clause.factor cl)
|
|
836 |
in
|
|
837 |
foldl factor_add active_subsume_acc cls
|
|
838 |
end;
|
|
839 |
|
|
840 |
fun factor' active acc [] = (active, rev acc)
|
|
841 |
| factor' active acc cls =
|
|
842 |
let
|
|
843 |
val cls = sort_utilitywise cls
|
|
844 |
val subsume = getSubsume active
|
|
845 |
val (active,_,acc) = foldl factor1 (active,subsume,acc) cls
|
|
846 |
val (active,cls) = extract_rewritables active
|
|
847 |
in
|
|
848 |
factor' active acc cls
|
|
849 |
end;
|
|
850 |
in
|
|
851 |
fun factor active cls = factor' active [] cls;
|
|
852 |
end;
|
|
853 |
|
|
854 |
(*MetisTrace4
|
|
855 |
val factor = fn active => fn cls =>
|
|
856 |
let
|
|
857 |
val ppCls = Print.ppList Clause.pp
|
|
858 |
val () = Print.trace ppCls "Active.factor: cls" cls
|
|
859 |
val (active,cls') = factor active cls
|
|
860 |
val () = Print.trace ppCls "Active.factor: cls'" cls'
|
|
861 |
in
|
|
862 |
(active,cls')
|
|
863 |
end;
|
|
864 |
*)
|
|
865 |
|
|
866 |
(* ------------------------------------------------------------------------- *)
|
|
867 |
(* Create a new active clause set and initialize clauses. *)
|
|
868 |
(* ------------------------------------------------------------------------- *)
|
|
869 |
|
|
870 |
fun new parameters {axioms,conjecture} =
|
|
871 |
let
|
|
872 |
val {clause,...} = parameters
|
|
873 |
|
|
874 |
fun mk_clause th =
|
|
875 |
Clause.mk {parameters = clause, id = Clause.newId (), thm = th}
|
|
876 |
|
|
877 |
val active = empty parameters
|
|
878 |
val (active,axioms) = factor active (map mk_clause axioms)
|
|
879 |
val (active,conjecture) = factor active (map mk_clause conjecture)
|
|
880 |
in
|
|
881 |
(active, {axioms = axioms, conjecture = conjecture})
|
|
882 |
end;
|
|
883 |
|
|
884 |
(* ------------------------------------------------------------------------- *)
|
|
885 |
(* Add a clause into the active set and deduce all consequences. *)
|
|
886 |
(* ------------------------------------------------------------------------- *)
|
|
887 |
|
|
888 |
fun add active cl =
|
|
889 |
case simplifyActive maxSimplify active cl of
|
|
890 |
NONE => (active,[])
|
|
891 |
| SOME cl' =>
|
|
892 |
if Clause.isContradiction cl' then (active,[cl'])
|
|
893 |
else if not (Clause.equalThms cl cl') then factor active [cl']
|
|
894 |
else
|
|
895 |
let
|
|
896 |
(*MetisTrace2
|
|
897 |
val () = Print.trace Clause.pp "Active.add: cl" cl
|
|
898 |
*)
|
|
899 |
val active = addClause active cl
|
|
900 |
val cl = Clause.freshVars cl
|
|
901 |
val cls = deduce active cl
|
|
902 |
val (active,cls) = factor active cls
|
|
903 |
(*MetisTrace2
|
|
904 |
val ppCls = Print.ppList Clause.pp
|
|
905 |
val () = Print.trace ppCls "Active.add: cls" cls
|
|
906 |
*)
|
|
907 |
in
|
|
908 |
(active,cls)
|
|
909 |
end;
|
|
910 |
|
|
911 |
end
|