1(* ========================================================================= *) 2(* THE TPTP PROBLEM FILE FORMAT *) 3(* Copyright (c) 2001 Joe Hurd, distributed under the BSD License *) 4(* ========================================================================= *) 5 6structure Tptp :> Tptp = 7struct 8 9open Useful; 10 11(* ------------------------------------------------------------------------- *) 12(* Default TPTP function and relation name mapping. *) 13(* ------------------------------------------------------------------------- *) 14 15val defaultFunctionMapping = 16 [(* Mapping TPTP functions to infix symbols *) 17 {name = "~", arity = 1, tptp = "negate"}, 18 {name = "*", arity = 2, tptp = "multiply"}, 19 {name = "/", arity = 2, tptp = "divide"}, 20 {name = "+", arity = 2, tptp = "add"}, 21 {name = "-", arity = 2, tptp = "subtract"}, 22 {name = "::", arity = 2, tptp = "cons"}, 23 {name = "@", arity = 2, tptp = "append"}, 24 {name = ",", arity = 2, tptp = "pair"}, 25 (* Expanding HOL symbols to TPTP alphanumerics *) 26 {name = ":", arity = 2, tptp = "has_type"}, 27 {name = ".", arity = 2, tptp = "apply"}]; 28 29val defaultRelationMapping = 30 [(* Mapping TPTP relations to infix symbols *) 31 {name = "=", arity = 2, tptp = "="}, (* this preserves the = symbol *) 32 {name = "==", arity = 2, tptp = "equalish"}, 33 {name = "<=", arity = 2, tptp = "less_equal"}, 34 {name = "<", arity = 2, tptp = "less_than"}, 35 {name = ">=", arity = 2, tptp = "greater_equal"}, 36 {name = ">", arity = 2, tptp = "greater_than"}, 37 (* Expanding HOL symbols to TPTP alphanumerics *) 38 {name = "{}", arity = 1, tptp = "bool"}]; 39 40(* ------------------------------------------------------------------------- *) 41(* Interpreting TPTP functions and relations in a finite model. *) 42(* ------------------------------------------------------------------------- *) 43 44val defaultFunctionModel = 45 [{name = "~", arity = 1, model = Model.negName}, 46 {name = "*", arity = 2, model = Model.multName}, 47 {name = "/", arity = 2, model = Model.divName}, 48 {name = "+", arity = 2, model = Model.addName}, 49 {name = "-", arity = 2, model = Model.subName}, 50 {name = "::", arity = 2, model = Model.consName}, 51 {name = "@", arity = 2, model = Model.appendName}, 52 {name = ":", arity = 2, model = Term.hasTypeFunctionName}, 53 {name = "additive_identity", arity = 0, model = Model.numeralName 0}, 54 {name = "app", arity = 2, model = Model.appendName}, 55 {name = "complement", arity = 1, model = Model.complementName}, 56 {name = "difference", arity = 2, model = Model.differenceName}, 57 {name = "divide", arity = 2, model = Model.divName}, 58 {name = "empty_set", arity = 0, model = Model.emptyName}, 59 {name = "identity", arity = 0, model = Model.numeralName 1}, 60 {name = "identity_map", arity = 1, model = Model.projectionName 1}, 61 {name = "intersection", arity = 2, model = Model.intersectName}, 62 {name = "minus", arity = 1, model = Model.negName}, 63 {name = "multiplicative_identity", arity = 0, model = Model.numeralName 1}, 64 {name = "n0", arity = 0, model = Model.numeralName 0}, 65 {name = "n1", arity = 0, model = Model.numeralName 1}, 66 {name = "n2", arity = 0, model = Model.numeralName 2}, 67 {name = "n3", arity = 0, model = Model.numeralName 3}, 68 {name = "n4", arity = 0, model = Model.numeralName 4}, 69 {name = "n5", arity = 0, model = Model.numeralName 5}, 70 {name = "n6", arity = 0, model = Model.numeralName 6}, 71 {name = "n7", arity = 0, model = Model.numeralName 7}, 72 {name = "n8", arity = 0, model = Model.numeralName 8}, 73 {name = "n9", arity = 0, model = Model.numeralName 9}, 74 {name = "nil", arity = 0, model = Model.nilName}, 75 {name = "null_class", arity = 0, model = Model.emptyName}, 76 {name = "singleton", arity = 1, model = Model.singletonName}, 77 {name = "successor", arity = 1, model = Model.sucName}, 78 {name = "symmetric_difference", arity = 2, 79 model = Model.symmetricDifferenceName}, 80 {name = "union", arity = 2, model = Model.unionName}, 81 {name = "universal_class", arity = 0, model = Model.universeName}]; 82 83val defaultRelationModel = 84 [{name = "=", arity = 2, model = Atom.eqRelationName}, 85 {name = "==", arity = 2, model = Atom.eqRelationName}, 86 {name = "<=", arity = 2, model = Model.leName}, 87 {name = "<", arity = 2, model = Model.ltName}, 88 {name = ">=", arity = 2, model = Model.geName}, 89 {name = ">", arity = 2, model = Model.gtName}, 90 {name = "divides", arity = 2, model = Model.dividesName}, 91 {name = "element_of_set", arity = 2, model = Model.memberName}, 92 {name = "equal", arity = 2, model = Atom.eqRelationName}, 93 {name = "equal_elements", arity = 2, model = Atom.eqRelationName}, 94 {name = "equal_sets", arity = 2, model = Atom.eqRelationName}, 95 {name = "equivalent", arity = 2, model = Atom.eqRelationName}, 96 {name = "less", arity = 2, model = Model.ltName}, 97 {name = "less_or_equal", arity = 2, model = Model.leName}, 98 {name = "member", arity = 2, model = Model.memberName}, 99 {name = "subclass", arity = 2, model = Model.subsetName}, 100 {name = "subset", arity = 2, model = Model.subsetName}]; 101 102(* ------------------------------------------------------------------------- *) 103(* Helper functions. *) 104(* ------------------------------------------------------------------------- *) 105 106fun isHdTlString hp tp s = 107 let 108 fun ct 0 = true 109 | ct i = tp (String.sub (s,i)) andalso ct (i - 1) 110 111 val n = size s 112 in 113 n > 0 andalso hp (String.sub (s,0)) andalso ct (n - 1) 114 end; 115 116fun stripSuffix pred s = 117 let 118 fun f 0 = "" 119 | f n = 120 let 121 val n' = n - 1 122 in 123 if pred (String.sub (s,n')) then f n' 124 else String.substring (s,0,n) 125 end 126 in 127 f (size s) 128 end; 129 130fun variant avoid s = 131 if not (StringSet.member s avoid) then s 132 else 133 let 134 val s = stripSuffix Char.isDigit s 135 136 fun var i = 137 let 138 val s_i = s ^ Int.toString i 139 in 140 if not (StringSet.member s_i avoid) then s_i else var (i + 1) 141 end 142 in 143 var 0 144 end; 145 146(* ------------------------------------------------------------------------- *) 147(* Mapping to legal TPTP names. *) 148(* ------------------------------------------------------------------------- *) 149 150local 151 fun nonEmptyPred p l = 152 case l of 153 [] => false 154 | c :: cs => p (c,cs); 155 156 fun existsPred l x = List.exists (fn p => p x) l; 157 158 fun isTptpChar #"_" = true 159 | isTptpChar c = Char.isAlphaNum c; 160 161 fun isTptpName l s = nonEmptyPred (existsPred l) (String.explode s); 162 163 fun isRegular (c,cs) = 164 Char.isLower c andalso List.all isTptpChar cs; 165 166 fun isNumber (c,cs) = 167 Char.isDigit c andalso List.all Char.isDigit cs; 168 169 fun isDefined (c,cs) = 170 c = #"$" andalso nonEmptyPred isRegular cs; 171 172 fun isSystem (c,cs) = 173 c = #"$" andalso nonEmptyPred isDefined cs; 174in 175 fun mkTptpVarName s = 176 let 177 val s = 178 case List.filter isTptpChar (String.explode s) of 179 [] => [#"X"] 180 | l as c :: cs => 181 if Char.isUpper c then l 182 else if Char.isLower c then Char.toUpper c :: cs 183 else #"X" :: l 184 in 185 String.implode s 186 end; 187 188 val isTptpConstName = isTptpName [isRegular,isNumber,isDefined,isSystem] 189 and isTptpFnName = isTptpName [isRegular,isDefined,isSystem] 190 and isTptpPropName = isTptpName [isRegular,isDefined,isSystem] 191 and isTptpRelName = isTptpName [isRegular,isDefined,isSystem]; 192 193 val isTptpFormulaName = isTptpName [isRegular,isNumber]; 194end; 195 196(* ------------------------------------------------------------------------- *) 197(* Mapping to legal TPTP variable names. *) 198(* ------------------------------------------------------------------------- *) 199 200datatype varToTptp = VarToTptp of StringSet.set * string NameMap.map; 201 202val emptyVarToTptp = VarToTptp (StringSet.empty, NameMap.new ()); 203 204fun addVarToTptp vm v = 205 let 206 val VarToTptp (avoid,mapping) = vm 207 in 208 if NameMap.inDomain v mapping then vm 209 else 210 let 211 val s = variant avoid (mkTptpVarName (Name.toString v)) 212 213 val avoid = StringSet.add avoid s 214 and mapping = NameMap.insert mapping (v,s) 215 in 216 VarToTptp (avoid,mapping) 217 end 218 end; 219 220local 221 fun add (v,vm) = addVarToTptp vm v; 222in 223 val addListVarToTptp = List.foldl add; 224 225 val addSetVarToTptp = NameSet.foldl add; 226end; 227 228val fromListVarToTptp = addListVarToTptp emptyVarToTptp; 229 230val fromSetVarToTptp = addSetVarToTptp emptyVarToTptp; 231 232fun getVarToTptp vm v = 233 let 234 val VarToTptp (_,mapping) = vm 235 in 236 case NameMap.peek mapping v of 237 SOME s => s 238 | NONE => raise Bug "Tptp.getVarToTptp: unknown var" 239 end; 240 241(* ------------------------------------------------------------------------- *) 242(* Mapping from TPTP variable names. *) 243(* ------------------------------------------------------------------------- *) 244 245fun getVarFromTptp s = Name.fromString s; 246 247(* ------------------------------------------------------------------------- *) 248(* Mapping to TPTP function and relation names. *) 249(* ------------------------------------------------------------------------- *) 250 251datatype nameToTptp = NameToTptp of string NameArityMap.map; 252 253local 254 val emptyNames : string NameArityMap.map = NameArityMap.new (); 255 256 fun addNames ({name,arity,tptp},mapping) = 257 NameArityMap.insert mapping ((name,arity),tptp); 258 259 val fromListNames = List.foldl addNames emptyNames; 260in 261 fun mkNameToTptp mapping = NameToTptp (fromListNames mapping); 262end; 263 264local 265 fun escapeChar c = 266 case c of 267 #"\\" => "\\\\" 268 | #"'" => "\\'" 269 | #"\n" => "\\n" 270 | #"\t" => "\\t" 271 | _ => str c; 272 273 val escapeString = String.translate escapeChar; 274in 275 fun singleQuote s = "'" ^ escapeString s ^ "'"; 276end; 277 278fun getNameToTptp isTptp s = if isTptp s then s else singleQuote s; 279 280fun getNameArityToTptp isZeroTptp isPlusTptp (NameToTptp mapping) na = 281 case NameArityMap.peek mapping na of 282 SOME s => s 283 | NONE => 284 let 285 val (n,a) = na 286 val isTptp = if a = 0 then isZeroTptp else isPlusTptp 287 val s = Name.toString n 288 in 289 getNameToTptp isTptp s 290 end; 291 292(* ------------------------------------------------------------------------- *) 293(* Mapping from TPTP function and relation names. *) 294(* ------------------------------------------------------------------------- *) 295 296datatype nameFromTptp = NameFromTptp of (string * int, Name.name) Map.map; 297 298local 299 val stringArityCompare = prodCompare String.compare Int.compare; 300 301 val emptyStringArityMap = Map.new stringArityCompare; 302 303 fun addStringArityMap ({name,arity,tptp},mapping) = 304 Map.insert mapping ((tptp,arity),name); 305 306 val fromListStringArityMap = 307 List.foldl addStringArityMap emptyStringArityMap; 308in 309 fun mkNameFromTptp mapping = NameFromTptp (fromListStringArityMap mapping); 310end; 311 312fun getNameFromTptp (NameFromTptp mapping) sa = 313 case Map.peek mapping sa of 314 SOME n => n 315 | NONE => 316 let 317 val (s,_) = sa 318 in 319 Name.fromString s 320 end; 321 322(* ------------------------------------------------------------------------- *) 323(* Mapping to and from TPTP variable, function and relation names. *) 324(* ------------------------------------------------------------------------- *) 325 326datatype mapping = 327 Mapping of 328 {varTo : varToTptp, 329 fnTo : nameToTptp, 330 relTo : nameToTptp, 331 fnFrom : nameFromTptp, 332 relFrom : nameFromTptp}; 333 334fun mkMapping mapping = 335 let 336 val {functionMapping,relationMapping} = mapping 337 338 val varTo = emptyVarToTptp 339 val fnTo = mkNameToTptp functionMapping 340 val relTo = mkNameToTptp relationMapping 341 342 val fnFrom = mkNameFromTptp functionMapping 343 val relFrom = mkNameFromTptp relationMapping 344 in 345 Mapping 346 {varTo = varTo, 347 fnTo = fnTo, 348 relTo = relTo, 349 fnFrom = fnFrom, 350 relFrom = relFrom} 351 end; 352 353fun addVarListMapping mapping vs = 354 let 355 val Mapping 356 {varTo, 357 fnTo, 358 relTo, 359 fnFrom, 360 relFrom} = mapping 361 362 val varTo = addListVarToTptp varTo vs 363 in 364 Mapping 365 {varTo = varTo, 366 fnTo = fnTo, 367 relTo = relTo, 368 fnFrom = fnFrom, 369 relFrom = relFrom} 370 end; 371 372fun addVarSetMapping mapping vs = 373 let 374 val Mapping 375 {varTo, 376 fnTo, 377 relTo, 378 fnFrom, 379 relFrom} = mapping 380 381 val varTo = addSetVarToTptp varTo vs 382 in 383 Mapping 384 {varTo = varTo, 385 fnTo = fnTo, 386 relTo = relTo, 387 fnFrom = fnFrom, 388 relFrom = relFrom} 389 end; 390 391fun varToTptp mapping v = 392 let 393 val Mapping {varTo,...} = mapping 394 in 395 getVarToTptp varTo v 396 end; 397 398fun fnToTptp mapping fa = 399 let 400 val Mapping {fnTo,...} = mapping 401 in 402 getNameArityToTptp isTptpConstName isTptpFnName fnTo fa 403 end; 404 405fun relToTptp mapping ra = 406 let 407 val Mapping {relTo,...} = mapping 408 in 409 getNameArityToTptp isTptpPropName isTptpRelName relTo ra 410 end; 411 412fun varFromTptp (_ : mapping) v = getVarFromTptp v; 413 414fun fnFromTptp mapping fa = 415 let 416 val Mapping {fnFrom,...} = mapping 417 in 418 getNameFromTptp fnFrom fa 419 end; 420 421fun relFromTptp mapping ra = 422 let 423 val Mapping {relFrom,...} = mapping 424 in 425 getNameFromTptp relFrom ra 426 end; 427 428val defaultMapping = 429 let 430 fun lift {name,arity,tptp} = 431 {name = Name.fromString name, arity = arity, tptp = tptp} 432 433 val functionMapping = List.map lift defaultFunctionMapping 434 and relationMapping = List.map lift defaultRelationMapping 435 436 val mapping = 437 {functionMapping = functionMapping, 438 relationMapping = relationMapping} 439 in 440 mkMapping mapping 441 end; 442 443(* ------------------------------------------------------------------------- *) 444(* Interpreting TPTP functions and relations in a finite model. *) 445(* ------------------------------------------------------------------------- *) 446 447fun mkFixedMap funcModel relModel = 448 let 449 fun mkEntry {name,arity,model} = ((Name.fromString name, arity), model) 450 451 fun mkMap l = NameArityMap.fromList (List.map mkEntry l) 452 in 453 {functionMap = mkMap funcModel, 454 relationMap = mkMap relModel} 455 end; 456 457val defaultFixedMap = mkFixedMap defaultFunctionModel defaultRelationModel; 458 459val defaultModel = 460 let 461 val {size = N, fixed = fix} = Model.default 462 463 val fix = Model.mapFixed defaultFixedMap fix 464 in 465 {size = N, fixed = fix} 466 end; 467 468local 469 fun toTptpMap toTptp = 470 let 471 fun add ((src,arity),dest,m) = 472 let 473 val src = Name.fromString (toTptp (src,arity)) 474 in 475 NameArityMap.insert m ((src,arity),dest) 476 end 477 in 478 fn m => NameArityMap.foldl add (NameArityMap.new ()) m 479 end; 480 481 fun toTptpFixedMap mapping fixMap = 482 let 483 val {functionMap = fnMap, relationMap = relMap} = fixMap 484 485 val fnMap = toTptpMap (fnToTptp mapping) fnMap 486 and relMap = toTptpMap (relToTptp mapping) relMap 487 in 488 {functionMap = fnMap, 489 relationMap = relMap} 490 end; 491in 492 fun ppFixedMap mapping fixMap = 493 Model.ppFixedMap (toTptpFixedMap mapping fixMap); 494end; 495 496(* ------------------------------------------------------------------------- *) 497(* TPTP roles. *) 498(* ------------------------------------------------------------------------- *) 499 500datatype role = 501 AxiomRole 502 | ConjectureRole 503 | DefinitionRole 504 | NegatedConjectureRole 505 | PlainRole 506 | TheoremRole 507 | OtherRole of string; 508 509fun isCnfConjectureRole role = 510 case role of 511 NegatedConjectureRole => true 512 | _ => false; 513 514fun isFofConjectureRole role = 515 case role of 516 ConjectureRole => true 517 | _ => false; 518 519fun toStringRole role = 520 case role of 521 AxiomRole => "axiom" 522 | ConjectureRole => "conjecture" 523 | DefinitionRole => "definition" 524 | NegatedConjectureRole => "negated_conjecture" 525 | PlainRole => "plain" 526 | TheoremRole => "theorem" 527 | OtherRole s => s; 528 529fun fromStringRole s = 530 case s of 531 "axiom" => AxiomRole 532 | "conjecture" => ConjectureRole 533 | "definition" => DefinitionRole 534 | "negated_conjecture" => NegatedConjectureRole 535 | "plain" => PlainRole 536 | "theorem" => TheoremRole 537 | _ => OtherRole s; 538 539val ppRole = Print.ppMap toStringRole Print.ppString; 540 541(* ------------------------------------------------------------------------- *) 542(* SZS statuses. *) 543(* ------------------------------------------------------------------------- *) 544 545datatype status = 546 CounterSatisfiableStatus 547 | TheoremStatus 548 | SatisfiableStatus 549 | UnknownStatus 550 | UnsatisfiableStatus; 551 552fun toStringStatus status = 553 case status of 554 CounterSatisfiableStatus => "CounterSatisfiable" 555 | TheoremStatus => "Theorem" 556 | SatisfiableStatus => "Satisfiable" 557 | UnknownStatus => "Unknown" 558 | UnsatisfiableStatus => "Unsatisfiable"; 559 560val ppStatus = Print.ppMap toStringStatus Print.ppString; 561 562(* ------------------------------------------------------------------------- *) 563(* TPTP literals. *) 564(* ------------------------------------------------------------------------- *) 565 566datatype literal = 567 Boolean of bool 568 | Literal of Literal.literal; 569 570fun destLiteral lit = 571 case lit of 572 Literal l => l 573 | _ => raise Error "Tptp.destLiteral"; 574 575fun isBooleanLiteral lit = 576 case lit of 577 Boolean _ => true 578 | _ => false; 579 580fun equalBooleanLiteral b lit = 581 case lit of 582 Boolean b' => b = b' 583 | _ => false; 584 585fun negateLiteral (Boolean b) = (Boolean (not b)) 586 | negateLiteral (Literal l) = (Literal (Literal.negate l)); 587 588fun functionsLiteral (Boolean _) = NameAritySet.empty 589 | functionsLiteral (Literal lit) = Literal.functions lit; 590 591fun relationLiteral (Boolean _) = NONE 592 | relationLiteral (Literal lit) = SOME (Literal.relation lit); 593 594fun literalToFormula (Boolean true) = Formula.True 595 | literalToFormula (Boolean false) = Formula.False 596 | literalToFormula (Literal lit) = Literal.toFormula lit; 597 598fun literalFromFormula Formula.True = Boolean true 599 | literalFromFormula Formula.False = Boolean false 600 | literalFromFormula fm = Literal (Literal.fromFormula fm); 601 602fun freeVarsLiteral (Boolean _) = NameSet.empty 603 | freeVarsLiteral (Literal lit) = Literal.freeVars lit; 604 605fun literalSubst sub lit = 606 case lit of 607 Boolean _ => lit 608 | Literal l => Literal (Literal.subst sub l); 609 610(* ------------------------------------------------------------------------- *) 611(* Printing formulas using TPTP syntax. *) 612(* ------------------------------------------------------------------------- *) 613 614fun ppVar mapping v = 615 let 616 val s = varToTptp mapping v 617 in 618 Print.ppString s 619 end; 620 621fun ppFnName mapping fa = Print.ppString (fnToTptp mapping fa); 622 623fun ppConst mapping c = ppFnName mapping (c,0); 624 625fun ppTerm mapping = 626 let 627 fun term tm = 628 case tm of 629 Term.Var v => ppVar mapping v 630 | Term.Fn (f,tms) => 631 case length tms of 632 0 => ppConst mapping f 633 | a => 634 Print.inconsistentBlock 2 635 [ppFnName mapping (f,a), 636 Print.ppString "(", 637 Print.ppOpList "," term tms, 638 Print.ppString ")"] 639 in 640 fn tm => Print.inconsistentBlock 0 [term tm] 641 end; 642 643fun ppRelName mapping ra = Print.ppString (relToTptp mapping ra); 644 645fun ppProp mapping p = ppRelName mapping (p,0); 646 647fun ppAtom mapping (r,tms) = 648 case length tms of 649 0 => ppProp mapping r 650 | a => 651 Print.inconsistentBlock 2 652 [ppRelName mapping (r,a), 653 Print.ppString "(", 654 Print.ppOpList "," (ppTerm mapping) tms, 655 Print.ppString ")"]; 656 657local 658 val neg = Print.sequence (Print.ppString "~") Print.break; 659 660 fun fof mapping fm = 661 case fm of 662 Formula.And _ => assoc_binary mapping ("&", Formula.stripConj fm) 663 | Formula.Or _ => assoc_binary mapping ("|", Formula.stripDisj fm) 664 | Formula.Imp a_b => nonassoc_binary mapping ("=>",a_b) 665 | Formula.Iff a_b => nonassoc_binary mapping ("<=>",a_b) 666 | _ => unitary mapping fm 667 668 and nonassoc_binary mapping (s,a_b) = 669 Print.ppOp2 (" " ^ s) (unitary mapping) (unitary mapping) a_b 670 671 and assoc_binary mapping (s,l) = Print.ppOpList (" " ^ s) (unitary mapping) l 672 673 and unitary mapping fm = 674 case fm of 675 Formula.True => Print.ppString "$true" 676 | Formula.False => Print.ppString "$false" 677 | Formula.Forall _ => quantified mapping ("!", Formula.stripForall fm) 678 | Formula.Exists _ => quantified mapping ("?", Formula.stripExists fm) 679 | Formula.Not _ => 680 (case total Formula.destNeq fm of 681 SOME a_b => Print.ppOp2 " !=" (ppTerm mapping) (ppTerm mapping) a_b 682 | NONE => 683 let 684 val (n,fm) = Formula.stripNeg fm 685 in 686 Print.inconsistentBlock 2 687 [Print.duplicate n neg, 688 unitary mapping fm] 689 end) 690 | Formula.Atom atm => 691 (case total Formula.destEq fm of 692 SOME a_b => Print.ppOp2 " =" (ppTerm mapping) (ppTerm mapping) a_b 693 | NONE => ppAtom mapping atm) 694 | _ => 695 Print.inconsistentBlock 1 696 [Print.ppString "(", 697 fof mapping fm, 698 Print.ppString ")"] 699 700 and quantified mapping (q,(vs,fm)) = 701 let 702 val mapping = addVarListMapping mapping vs 703 in 704 Print.inconsistentBlock 2 705 [Print.ppString q, 706 Print.ppString " ", 707 Print.inconsistentBlock (String.size q) 708 [Print.ppString "[", 709 Print.ppOpList "," (ppVar mapping) vs, 710 Print.ppString "] :"], 711 Print.break, 712 unitary mapping fm] 713 end; 714in 715 fun ppFof mapping fm = Print.inconsistentBlock 0 [fof mapping fm]; 716end; 717 718(* ------------------------------------------------------------------------- *) 719(* Lexing TPTP files. *) 720(* ------------------------------------------------------------------------- *) 721 722datatype token = 723 AlphaNum of string 724 | Punct of char 725 | Quote of string; 726 727fun isAlphaNum #"_" = true 728 | isAlphaNum c = Char.isAlphaNum c; 729 730local 731 open Parse; 732 733 infixr 9 >>++ 734 infixr 8 ++ 735 infixr 7 >> 736 infixr 6 || 737 738 val alphaNumToken = 739 atLeastOne (some isAlphaNum) >> (AlphaNum o String.implode); 740 741 val punctToken = 742 let 743 val punctChars = "<>=-*+/\\?@|!$%&#^:;~()[]{}.," 744 in 745 some (Char.contains punctChars) >> Punct 746 end; 747 748 val quoteToken = 749 let 750 val escapeParser = 751 some (equal #"'") >> singleton || 752 some (equal #"\\") >> singleton 753 754 fun stopOn #"'" = true 755 | stopOn #"\n" = true 756 | stopOn _ = false 757 758 val quotedParser = 759 some (equal #"\\") ++ escapeParser >> op:: || 760 some (not o stopOn) >> singleton 761 in 762 exactChar #"'" ++ many quotedParser ++ exactChar #"'" >> 763 (fn (_,(l,_)) => Quote (String.implode (List.concat l))) 764 end; 765 766 val lexToken = alphaNumToken || punctToken || quoteToken; 767 768 val space = many (some Char.isSpace) >> K (); 769 770 val space1 = atLeastOne (some Char.isSpace) >> K (); 771in 772 val lexer = 773 (space ++ lexToken) >> (fn ((),tok) => [tok]) || 774 space1 >> K []; 775end; 776 777(* ------------------------------------------------------------------------- *) 778(* TPTP clauses. *) 779(* ------------------------------------------------------------------------- *) 780 781type clause = literal list; 782 783val clauseFunctions = 784 let 785 fun funcs (lit,acc) = NameAritySet.union (functionsLiteral lit) acc 786 in 787 List.foldl funcs NameAritySet.empty 788 end; 789 790val clauseRelations = 791 let 792 fun rels (lit,acc) = 793 case relationLiteral lit of 794 NONE => acc 795 | SOME r => NameAritySet.add acc r 796 in 797 List.foldl rels NameAritySet.empty 798 end; 799 800val clauseFreeVars = 801 let 802 fun fvs (lit,acc) = NameSet.union (freeVarsLiteral lit) acc 803 in 804 List.foldl fvs NameSet.empty 805 end; 806 807fun clauseSubst sub lits = List.map (literalSubst sub) lits; 808 809fun clauseToFormula lits = Formula.listMkDisj (List.map literalToFormula lits); 810 811fun clauseFromFormula fm = List.map literalFromFormula (Formula.stripDisj fm); 812 813fun clauseFromLiteralSet cl = 814 clauseFromFormula 815 (Formula.listMkDisj (LiteralSet.transform Literal.toFormula cl)); 816 817fun clauseFromThm th = clauseFromLiteralSet (Thm.clause th); 818 819fun ppClause mapping = Print.ppMap clauseToFormula (ppFof mapping); 820 821(* ------------------------------------------------------------------------- *) 822(* TPTP formula names. *) 823(* ------------------------------------------------------------------------- *) 824 825datatype formulaName = FormulaName of string; 826 827datatype formulaNameSet = FormulaNameSet of formulaName Set.set; 828 829fun compareFormulaName (FormulaName s1, FormulaName s2) = 830 String.compare (s1,s2); 831 832fun toTptpFormulaName (FormulaName s) = 833 getNameToTptp isTptpFormulaName s; 834 835val ppFormulaName = Print.ppMap toTptpFormulaName Print.ppString; 836 837val emptyFormulaNameSet = FormulaNameSet (Set.empty compareFormulaName); 838 839fun memberFormulaNameSet n (FormulaNameSet s) = Set.member n s; 840 841fun addFormulaNameSet (FormulaNameSet s) n = FormulaNameSet (Set.add s n); 842 843fun addListFormulaNameSet (FormulaNameSet s) l = 844 FormulaNameSet (Set.addList s l); 845 846(* ------------------------------------------------------------------------- *) 847(* TPTP formula bodies. *) 848(* ------------------------------------------------------------------------- *) 849 850datatype formulaBody = 851 CnfFormulaBody of literal list 852 | FofFormulaBody of Formula.formula; 853 854fun destCnfFormulaBody body = 855 case body of 856 CnfFormulaBody x => x 857 | _ => raise Error "destCnfFormulaBody"; 858 859val isCnfFormulaBody = can destCnfFormulaBody; 860 861fun destFofFormulaBody body = 862 case body of 863 FofFormulaBody x => x 864 | _ => raise Error "destFofFormulaBody"; 865 866val isFofFormulaBody = can destFofFormulaBody; 867 868fun formulaBodyFunctions body = 869 case body of 870 CnfFormulaBody cl => clauseFunctions cl 871 | FofFormulaBody fm => Formula.functions fm; 872 873fun formulaBodyRelations body = 874 case body of 875 CnfFormulaBody cl => clauseRelations cl 876 | FofFormulaBody fm => Formula.relations fm; 877 878fun formulaBodyFreeVars body = 879 case body of 880 CnfFormulaBody cl => clauseFreeVars cl 881 | FofFormulaBody fm => Formula.freeVars fm; 882 883fun ppFormulaBody mapping body = 884 case body of 885 CnfFormulaBody cl => ppClause mapping cl 886 | FofFormulaBody fm => ppFof mapping (Formula.generalize fm); 887 888(* ------------------------------------------------------------------------- *) 889(* TPTP formula sources. *) 890(* ------------------------------------------------------------------------- *) 891 892datatype formulaSource = 893 NoFormulaSource 894 | StripFormulaSource of 895 {inference : string, 896 parents : formulaName list} 897 | NormalizeFormulaSource of 898 {inference : Normalize.inference, 899 parents : formulaName list} 900 | ProofFormulaSource of 901 {inference : Proof.inference, 902 parents : formulaName list}; 903 904fun isNoFormulaSource source = 905 case source of 906 NoFormulaSource => true 907 | _ => false; 908 909fun functionsFormulaSource source = 910 case source of 911 NoFormulaSource => NameAritySet.empty 912 | StripFormulaSource _ => NameAritySet.empty 913 | NormalizeFormulaSource data => 914 let 915 val {inference = inf, parents = _} = data 916 in 917 case inf of 918 Normalize.Axiom fm => Formula.functions fm 919 | Normalize.Definition (_,fm) => Formula.functions fm 920 | _ => NameAritySet.empty 921 end 922 | ProofFormulaSource data => 923 let 924 val {inference = inf, parents = _} = data 925 in 926 case inf of 927 Proof.Axiom cl => LiteralSet.functions cl 928 | Proof.Assume atm => Atom.functions atm 929 | Proof.Subst (sub,_) => Subst.functions sub 930 | Proof.Resolve (atm,_,_) => Atom.functions atm 931 | Proof.Refl tm => Term.functions tm 932 | Proof.Equality (lit,_,tm) => 933 NameAritySet.union (Literal.functions lit) (Term.functions tm) 934 end; 935 936fun relationsFormulaSource source = 937 case source of 938 NoFormulaSource => NameAritySet.empty 939 | StripFormulaSource _ => NameAritySet.empty 940 | NormalizeFormulaSource data => 941 let 942 val {inference = inf, parents = _} = data 943 in 944 case inf of 945 Normalize.Axiom fm => Formula.relations fm 946 | Normalize.Definition (_,fm) => Formula.relations fm 947 | _ => NameAritySet.empty 948 end 949 | ProofFormulaSource data => 950 let 951 val {inference = inf, parents = _} = data 952 in 953 case inf of 954 Proof.Axiom cl => LiteralSet.relations cl 955 | Proof.Assume atm => NameAritySet.singleton (Atom.relation atm) 956 | Proof.Subst _ => NameAritySet.empty 957 | Proof.Resolve (atm,_,_) => NameAritySet.singleton (Atom.relation atm) 958 | Proof.Refl tm => NameAritySet.empty 959 | Proof.Equality (lit,_,_) => 960 NameAritySet.singleton (Literal.relation lit) 961 end; 962 963fun freeVarsFormulaSource source = 964 case source of 965 NoFormulaSource => NameSet.empty 966 | StripFormulaSource _ => NameSet.empty 967 | NormalizeFormulaSource data => NameSet.empty 968 | ProofFormulaSource data => 969 let 970 val {inference = inf, parents = _} = data 971 in 972 case inf of 973 Proof.Axiom cl => LiteralSet.freeVars cl 974 | Proof.Assume atm => Atom.freeVars atm 975 | Proof.Subst (sub,_) => Subst.freeVars sub 976 | Proof.Resolve (atm,_,_) => Atom.freeVars atm 977 | Proof.Refl tm => Term.freeVars tm 978 | Proof.Equality (lit,_,tm) => 979 NameSet.union (Literal.freeVars lit) (Term.freeVars tm) 980 end; 981 982local 983 val GEN_INFERENCE = "inference" 984 and GEN_INTRODUCED = "introduced"; 985 986 fun nameStrip inf = inf; 987 988 fun ppStrip mapping inf = Print.skip; 989 990 fun nameNormalize inf = 991 case inf of 992 Normalize.Axiom _ => "canonicalize" 993 | Normalize.Definition _ => "canonicalize" 994 | Normalize.Simplify _ => "simplify" 995 | Normalize.Conjunct _ => "conjunct" 996 | Normalize.Specialize _ => "specialize" 997 | Normalize.Skolemize _ => "skolemize" 998 | Normalize.Clausify _ => "clausify"; 999 1000 fun ppNormalize mapping inf = Print.skip; 1001 1002 fun nameProof inf = 1003 case inf of 1004 Proof.Axiom _ => "canonicalize" 1005 | Proof.Assume _ => "assume" 1006 | Proof.Subst _ => "subst" 1007 | Proof.Resolve _ => "resolve" 1008 | Proof.Refl _ => "refl" 1009 | Proof.Equality _ => "equality"; 1010 1011 local 1012 fun ppTermInf mapping = ppTerm mapping; 1013 1014 fun ppAtomInf mapping atm = 1015 case total Atom.destEq atm of 1016 SOME (a,b) => ppAtom mapping (Name.fromString "$equal", [a,b]) 1017 | NONE => ppAtom mapping atm; 1018 1019 fun ppLiteralInf mapping (pol,atm) = 1020 Print.sequence 1021 (if pol then Print.skip else Print.ppString "~ ") 1022 (ppAtomInf mapping atm); 1023 in 1024 fun ppProofTerm mapping = 1025 Print.ppBracket "$fot(" ")" (ppTermInf mapping); 1026 1027 fun ppProofAtom mapping = 1028 Print.ppBracket "$cnf(" ")" (ppAtomInf mapping); 1029 1030 fun ppProofLiteral mapping = 1031 Print.ppBracket "$cnf(" ")" (ppLiteralInf mapping); 1032 end; 1033 1034 val ppProofVar = ppVar; 1035 1036 val ppProofPath = Term.ppPath; 1037 1038 fun ppProof mapping inf = 1039 Print.inconsistentBlock 1 1040 [Print.ppString "[", 1041 (case inf of 1042 Proof.Axiom _ => Print.skip 1043 | Proof.Assume atm => ppProofAtom mapping atm 1044 | Proof.Subst _ => Print.skip 1045 | Proof.Resolve (atm,_,_) => ppProofAtom mapping atm 1046 | Proof.Refl tm => ppProofTerm mapping tm 1047 | Proof.Equality (lit,path,tm) => 1048 Print.program 1049 [ppProofLiteral mapping lit, 1050 Print.ppString ",", 1051 Print.break, 1052 ppProofPath path, 1053 Print.ppString ",", 1054 Print.break, 1055 ppProofTerm mapping tm]), 1056 Print.ppString "]"]; 1057 1058 val ppParent = ppFormulaName; 1059 1060 fun ppProofSubst mapping = 1061 Print.ppMap Subst.toList 1062 (Print.ppList 1063 (Print.ppBracket "bind(" ")" 1064 (Print.ppOp2 "," (ppProofVar mapping) 1065 (ppProofTerm mapping)))); 1066 1067 fun ppProofParent mapping (p,s) = 1068 if Subst.null s then ppParent p 1069 else Print.ppOp2 " :" ppParent (ppProofSubst mapping) (p,s); 1070in 1071 fun ppFormulaSource mapping source = 1072 case source of 1073 NoFormulaSource => Print.skip 1074 | StripFormulaSource {inference,parents} => 1075 let 1076 val gen = GEN_INFERENCE 1077 1078 val name = nameStrip inference 1079 in 1080 Print.inconsistentBlock (size gen + 1) 1081 [Print.ppString gen, 1082 Print.ppString "(", 1083 Print.ppString name, 1084 Print.ppString ",", 1085 Print.break, 1086 Print.ppBracket "[" "]" (ppStrip mapping) inference, 1087 Print.ppString ",", 1088 Print.break, 1089 Print.ppList ppParent parents, 1090 Print.ppString ")"] 1091 end 1092 | NormalizeFormulaSource {inference,parents} => 1093 let 1094 val gen = GEN_INFERENCE 1095 1096 val name = nameNormalize inference 1097 in 1098 Print.inconsistentBlock (size gen + 1) 1099 [Print.ppString gen, 1100 Print.ppString "(", 1101 Print.ppString name, 1102 Print.ppString ",", 1103 Print.break, 1104 Print.ppBracket "[" "]" (ppNormalize mapping) inference, 1105 Print.ppString ",", 1106 Print.break, 1107 Print.ppList ppParent parents, 1108 Print.ppString ")"] 1109 end 1110 | ProofFormulaSource {inference,parents} => 1111 let 1112 val isTaut = List.null parents 1113 1114 val gen = if isTaut then GEN_INTRODUCED else GEN_INFERENCE 1115 1116 val name = nameProof inference 1117 1118 val parents = 1119 let 1120 val sub = 1121 case inference of 1122 Proof.Subst (s,_) => s 1123 | _ => Subst.empty 1124 in 1125 List.map (fn parent => (parent,sub)) parents 1126 end 1127 in 1128 Print.inconsistentBlock (size gen + 1) 1129 ([Print.ppString gen, 1130 Print.ppString "("] @ 1131 (if isTaut then 1132 [Print.ppString "tautology", 1133 Print.ppString ",", 1134 Print.break, 1135 Print.inconsistentBlock 1 1136 [Print.ppString "[", 1137 Print.ppString name, 1138 Print.ppString ",", 1139 Print.break, 1140 ppProof mapping inference, 1141 Print.ppString "]"]] 1142 else 1143 [Print.ppString name, 1144 Print.ppString ",", 1145 Print.break, 1146 ppProof mapping inference, 1147 Print.ppString ",", 1148 Print.break, 1149 Print.ppList (ppProofParent mapping) parents]) @ 1150 [Print.ppString ")"]) 1151 end 1152end; 1153 1154(* ------------------------------------------------------------------------- *) 1155(* TPTP formulas. *) 1156(* ------------------------------------------------------------------------- *) 1157 1158datatype formula = 1159 Formula of 1160 {name : formulaName, 1161 role : role, 1162 body : formulaBody, 1163 source : formulaSource}; 1164 1165fun nameFormula (Formula {name,...}) = name; 1166 1167fun roleFormula (Formula {role,...}) = role; 1168 1169fun bodyFormula (Formula {body,...}) = body; 1170 1171fun sourceFormula (Formula {source,...}) = source; 1172 1173fun destCnfFormula fm = destCnfFormulaBody (bodyFormula fm); 1174 1175val isCnfFormula = can destCnfFormula; 1176 1177fun destFofFormula fm = destFofFormulaBody (bodyFormula fm); 1178 1179val isFofFormula = can destFofFormula; 1180 1181fun functionsFormula fm = 1182 let 1183 val bodyFns = formulaBodyFunctions (bodyFormula fm) 1184 and sourceFns = functionsFormulaSource (sourceFormula fm) 1185 in 1186 NameAritySet.union bodyFns sourceFns 1187 end; 1188 1189fun relationsFormula fm = 1190 let 1191 val bodyRels = formulaBodyRelations (bodyFormula fm) 1192 and sourceRels = relationsFormulaSource (sourceFormula fm) 1193 in 1194 NameAritySet.union bodyRels sourceRels 1195 end; 1196 1197fun freeVarsFormula fm = 1198 let 1199 val bodyFvs = formulaBodyFreeVars (bodyFormula fm) 1200 and sourceFvs = freeVarsFormulaSource (sourceFormula fm) 1201 in 1202 NameSet.union bodyFvs sourceFvs 1203 end; 1204 1205val freeVarsListFormula = 1206 let 1207 fun add (fm,vs) = NameSet.union vs (freeVarsFormula fm) 1208 in 1209 List.foldl add NameSet.empty 1210 end; 1211 1212val formulasFunctions = 1213 let 1214 fun funcs (fm,acc) = NameAritySet.union (functionsFormula fm) acc 1215 in 1216 List.foldl funcs NameAritySet.empty 1217 end; 1218 1219val formulasRelations = 1220 let 1221 fun rels (fm,acc) = NameAritySet.union (relationsFormula fm) acc 1222 in 1223 List.foldl rels NameAritySet.empty 1224 end; 1225 1226fun isCnfConjectureFormula fm = 1227 case fm of 1228 Formula {role, body = CnfFormulaBody _, ...} => isCnfConjectureRole role 1229 | _ => false; 1230 1231fun isFofConjectureFormula fm = 1232 case fm of 1233 Formula {role, body = FofFormulaBody _, ...} => isFofConjectureRole role 1234 | _ => false; 1235 1236fun isConjectureFormula fm = 1237 isCnfConjectureFormula fm orelse 1238 isFofConjectureFormula fm; 1239 1240(* Parsing and pretty-printing *) 1241 1242fun ppFormula mapping fm = 1243 let 1244 val Formula {name,role,body,source} = fm 1245 1246 val gen = 1247 case body of 1248 CnfFormulaBody _ => "cnf" 1249 | FofFormulaBody _ => "fof" 1250 in 1251 Print.inconsistentBlock (size gen + 1) 1252 ([Print.ppString gen, 1253 Print.ppString "(", 1254 ppFormulaName name, 1255 Print.ppString ",", 1256 Print.break, 1257 ppRole role, 1258 Print.ppString ",", 1259 Print.break, 1260 Print.consistentBlock 1 1261 [Print.ppString "(", 1262 ppFormulaBody mapping body, 1263 Print.ppString ")"]] @ 1264 (if isNoFormulaSource source then [] 1265 else 1266 [Print.ppString ",", 1267 Print.break, 1268 ppFormulaSource mapping source]) @ 1269 [Print.ppString ")."]) 1270 end; 1271 1272fun formulaToString mapping = Print.toString (ppFormula mapping); 1273 1274local 1275 open Parse; 1276 1277 infixr 9 >>++ 1278 infixr 8 ++ 1279 infixr 7 >> 1280 infixr 6 || 1281 1282 fun someAlphaNum p = 1283 maybe (fn AlphaNum s => if p s then SOME s else NONE | _ => NONE); 1284 1285 fun alphaNumParser s = someAlphaNum (equal s) >> K (); 1286 1287 val lowerParser = someAlphaNum (fn s => Char.isLower (String.sub (s,0))); 1288 1289 val upperParser = someAlphaNum (fn s => Char.isUpper (String.sub (s,0))); 1290 1291 val stringParser = lowerParser || upperParser; 1292 1293 val numberParser = someAlphaNum (List.all Char.isDigit o String.explode); 1294 1295 fun somePunct p = 1296 maybe (fn Punct c => if p c then SOME c else NONE | _ => NONE); 1297 1298 fun punctParser c = somePunct (equal c) >> K (); 1299 1300 val quoteParser = maybe (fn Quote s => SOME s | _ => NONE); 1301 1302 local 1303 fun f [] = raise Bug "symbolParser" 1304 | f [x] = x 1305 | f (h :: t) = (h ++ f t) >> K (); 1306 in 1307 fun symbolParser s = f (List.map punctParser (String.explode s)); 1308 end; 1309 1310 val definedParser = 1311 punctParser #"$" ++ someAlphaNum (K true) >> (fn ((),s) => "$" ^ s); 1312 1313 val systemParser = 1314 punctParser #"$" ++ punctParser #"$" ++ someAlphaNum (K true) >> 1315 (fn ((),((),s)) => "$$" ^ s); 1316 1317 val nameParser = 1318 (stringParser || numberParser || quoteParser) >> FormulaName; 1319 1320 val roleParser = lowerParser >> fromStringRole; 1321 1322 local 1323 fun isProposition s = isHdTlString Char.isLower isAlphaNum s; 1324 in 1325 val propositionParser = 1326 someAlphaNum isProposition || 1327 definedParser || 1328 systemParser || 1329 quoteParser; 1330 end; 1331 1332 local 1333 fun isFunction s = isHdTlString Char.isLower isAlphaNum s; 1334 in 1335 val functionParser = 1336 someAlphaNum isFunction || 1337 definedParser || 1338 systemParser || 1339 quoteParser; 1340 end; 1341 1342 local 1343 fun isConstant s = isHdTlString Char.isLower isAlphaNum s; 1344 in 1345 val constantParser = 1346 someAlphaNum isConstant || 1347 definedParser || 1348 numberParser || 1349 systemParser || 1350 quoteParser; 1351 end; 1352 1353 val varParser = upperParser; 1354 1355 val varListParser = 1356 (punctParser #"[" ++ varParser ++ 1357 many ((punctParser #"," ++ varParser) >> snd) ++ 1358 punctParser #"]") >> 1359 (fn ((),(h,(t,()))) => h :: t); 1360 1361 fun mkVarName mapping v = varFromTptp mapping v; 1362 1363 fun mkVar mapping v = 1364 let 1365 val v = mkVarName mapping v 1366 in 1367 Term.Var v 1368 end 1369 1370 fun mkFn mapping (f,tms) = 1371 let 1372 val f = fnFromTptp mapping (f, length tms) 1373 in 1374 Term.Fn (f,tms) 1375 end; 1376 1377 fun mkConst mapping c = mkFn mapping (c,[]); 1378 1379 fun mkAtom mapping (r,tms) = 1380 let 1381 val r = relFromTptp mapping (r, length tms) 1382 in 1383 (r,tms) 1384 end; 1385 1386 fun termParser mapping input = 1387 let 1388 val fnP = functionArgumentsParser mapping >> mkFn mapping 1389 val nonFnP = nonFunctionArgumentsTermParser mapping 1390 in 1391 fnP || nonFnP 1392 end input 1393 1394 and functionArgumentsParser mapping input = 1395 let 1396 val commaTmP = (punctParser #"," ++ termParser mapping) >> snd 1397 in 1398 (functionParser ++ punctParser #"(" ++ termParser mapping ++ 1399 many commaTmP ++ punctParser #")") >> 1400 (fn (f,((),(t,(ts,())))) => (f, t :: ts)) 1401 end input 1402 1403 and nonFunctionArgumentsTermParser mapping input = 1404 let 1405 val varP = varParser >> mkVar mapping 1406 val constP = constantParser >> mkConst mapping 1407 in 1408 varP || constP 1409 end input; 1410 1411 fun binaryAtomParser mapping tm input = 1412 let 1413 val eqP = 1414 (punctParser #"=" ++ termParser mapping) >> 1415 (fn ((),r) => (true,("$equal",[tm,r]))) 1416 1417 val neqP = 1418 (symbolParser "!=" ++ termParser mapping) >> 1419 (fn ((),r) => (false,("$equal",[tm,r]))) 1420 in 1421 eqP || neqP 1422 end input; 1423 1424 fun maybeBinaryAtomParser mapping (s,tms) input = 1425 let 1426 val tm = mkFn mapping (s,tms) 1427 in 1428 optional (binaryAtomParser mapping tm) >> 1429 (fn SOME lit => lit 1430 | NONE => (true,(s,tms))) 1431 end input; 1432 1433 fun literalAtomParser mapping input = 1434 let 1435 val fnP = 1436 functionArgumentsParser mapping >>++ 1437 maybeBinaryAtomParser mapping 1438 1439 val nonFnP = 1440 nonFunctionArgumentsTermParser mapping >>++ 1441 binaryAtomParser mapping 1442 1443 val propP = propositionParser >> (fn s => (true,(s,[]))) 1444 in 1445 fnP || nonFnP || propP 1446 end input; 1447 1448 fun atomParser mapping input = 1449 let 1450 fun mk (pol,rel) = 1451 case rel of 1452 ("$true",[]) => Boolean pol 1453 | ("$false",[]) => Boolean (not pol) 1454 | ("$equal",[l,r]) => Literal (pol, Atom.mkEq (l,r)) 1455 | (r,tms) => Literal (pol, mkAtom mapping (r,tms)) 1456 in 1457 literalAtomParser mapping >> mk 1458 end input; 1459 1460 fun literalParser mapping input = 1461 let 1462 val negP = 1463 (punctParser #"~" ++ atomParser mapping) >> 1464 (negateLiteral o snd) 1465 1466 val posP = atomParser mapping 1467 in 1468 negP || posP 1469 end input; 1470 1471 fun disjunctionParser mapping input = 1472 let 1473 val orLitP = (punctParser #"|" ++ literalParser mapping) >> snd 1474 in 1475 (literalParser mapping ++ many orLitP) >> (fn (h,t) => h :: t) 1476 end input; 1477 1478 fun clauseParser mapping input = 1479 let 1480 val disjP = disjunctionParser mapping 1481 1482 val bracketDisjP = 1483 (punctParser #"(" ++ disjP ++ punctParser #")") >> 1484 (fn ((),(c,())) => c) 1485 in 1486 bracketDisjP || disjP 1487 end input; 1488 1489 val binaryConnectiveParser = 1490 (symbolParser "<=>" >> K Formula.Iff) || 1491 (symbolParser "=>" >> K Formula.Imp) || 1492 (symbolParser "<=" >> K (fn (f,g) => Formula.Imp (g,f))) || 1493 (symbolParser "<~>" >> K (Formula.Not o Formula.Iff)) || 1494 (symbolParser "~|" >> K (Formula.Not o Formula.Or)) || 1495 (symbolParser "~&" >> K (Formula.Not o Formula.And)); 1496 1497 val quantifierParser = 1498 (punctParser #"!" >> K Formula.listMkForall) || 1499 (punctParser #"?" >> K Formula.listMkExists); 1500 1501 fun fofFormulaParser mapping input = 1502 let 1503 fun mk (f,NONE) = f 1504 | mk (f, SOME t) = t f 1505 in 1506 (unitaryFormulaParser mapping ++ 1507 optional (binaryFormulaParser mapping)) >> mk 1508 end input 1509 1510 and binaryFormulaParser mapping input = 1511 let 1512 val nonAssocP = nonAssocBinaryFormulaParser mapping 1513 1514 val assocP = assocBinaryFormulaParser mapping 1515 in 1516 nonAssocP || assocP 1517 end input 1518 1519 and nonAssocBinaryFormulaParser mapping input = 1520 let 1521 fun mk (c,g) f = c (f,g) 1522 in 1523 (binaryConnectiveParser ++ unitaryFormulaParser mapping) >> mk 1524 end input 1525 1526 and assocBinaryFormulaParser mapping input = 1527 let 1528 val orP = orFormulaParser mapping 1529 1530 val andP = andFormulaParser mapping 1531 in 1532 orP || andP 1533 end input 1534 1535 and orFormulaParser mapping input = 1536 let 1537 val orFmP = (punctParser #"|" ++ unitaryFormulaParser mapping) >> snd 1538 in 1539 atLeastOne orFmP >> 1540 (fn fs => fn f => Formula.listMkDisj (f :: fs)) 1541 end input 1542 1543 and andFormulaParser mapping input = 1544 let 1545 val andFmP = (punctParser #"&" ++ unitaryFormulaParser mapping) >> snd 1546 in 1547 atLeastOne andFmP >> 1548 (fn fs => fn f => Formula.listMkConj (f :: fs)) 1549 end input 1550 1551 and unitaryFormulaParser mapping input = 1552 let 1553 val quantP = quantifiedFormulaParser mapping 1554 1555 val unaryP = unaryFormulaParser mapping 1556 1557 val brackP = 1558 (punctParser #"(" ++ fofFormulaParser mapping ++ 1559 punctParser #")") >> 1560 (fn ((),(f,())) => f) 1561 1562 val atomP = 1563 atomParser mapping >> 1564 (fn Boolean b => Formula.mkBoolean b 1565 | Literal l => Literal.toFormula l) 1566 in 1567 quantP || 1568 unaryP || 1569 brackP || 1570 atomP 1571 end input 1572 1573 and quantifiedFormulaParser mapping input = 1574 let 1575 fun mk (q,(vs,((),f))) = q (List.map (mkVarName mapping) vs, f) 1576 in 1577 (quantifierParser ++ varListParser ++ punctParser #":" ++ 1578 unitaryFormulaParser mapping) >> mk 1579 end input 1580 1581 and unaryFormulaParser mapping input = 1582 let 1583 fun mk (c,f) = c f 1584 in 1585 (unaryConnectiveParser ++ unitaryFormulaParser mapping) >> mk 1586 end input 1587 1588 and unaryConnectiveParser input = 1589 (punctParser #"~" >> K Formula.Not) input; 1590 1591 fun cnfParser mapping input = 1592 let 1593 fun mk ((),((),(name,((),(role,((),(cl,((),())))))))) = 1594 let 1595 val body = CnfFormulaBody cl 1596 val source = NoFormulaSource 1597 in 1598 Formula 1599 {name = name, 1600 role = role, 1601 body = body, 1602 source = source} 1603 end 1604 in 1605 (alphaNumParser "cnf" ++ punctParser #"(" ++ 1606 nameParser ++ punctParser #"," ++ 1607 roleParser ++ punctParser #"," ++ 1608 clauseParser mapping ++ punctParser #")" ++ 1609 punctParser #".") >> mk 1610 end input; 1611 1612 fun fofParser mapping input = 1613 let 1614 fun mk ((),((),(name,((),(role,((),(fm,((),())))))))) = 1615 let 1616 val body = FofFormulaBody fm 1617 val source = NoFormulaSource 1618 in 1619 Formula 1620 {name = name, 1621 role = role, 1622 body = body, 1623 source = source} 1624 end 1625 in 1626 (alphaNumParser "fof" ++ punctParser #"(" ++ 1627 nameParser ++ punctParser #"," ++ 1628 roleParser ++ punctParser #"," ++ 1629 fofFormulaParser mapping ++ punctParser #")" ++ 1630 punctParser #".") >> mk 1631 end input; 1632in 1633 fun formulaParser mapping input = 1634 let 1635 val cnfP = cnfParser mapping 1636 1637 val fofP = fofParser mapping 1638 in 1639 cnfP || fofP 1640 end input; 1641end; 1642 1643(* ------------------------------------------------------------------------- *) 1644(* Include declarations. *) 1645(* ------------------------------------------------------------------------- *) 1646 1647fun ppInclude i = 1648 Print.inconsistentBlock 2 1649 [Print.ppString "include('", 1650 Print.ppString i, 1651 Print.ppString "')."]; 1652 1653val includeToString = Print.toString ppInclude; 1654 1655local 1656 open Parse; 1657 1658 infixr 9 >>++ 1659 infixr 8 ++ 1660 infixr 7 >> 1661 infixr 6 || 1662 1663 val filenameParser = maybe (fn Quote s => SOME s | _ => NONE); 1664in 1665 val includeParser = 1666 (some (equal (AlphaNum "include")) ++ 1667 some (equal (Punct #"(")) ++ 1668 filenameParser ++ 1669 some (equal (Punct #")")) ++ 1670 some (equal (Punct #"."))) >> 1671 (fn (_,(_,(f,(_,_)))) => f); 1672end; 1673 1674(* ------------------------------------------------------------------------- *) 1675(* Parsing TPTP files. *) 1676(* ------------------------------------------------------------------------- *) 1677 1678datatype declaration = 1679 IncludeDeclaration of string 1680 | FormulaDeclaration of formula; 1681 1682val partitionDeclarations = 1683 let 1684 fun part (d,(il,fl)) = 1685 case d of 1686 IncludeDeclaration i => (i :: il, fl) 1687 | FormulaDeclaration f => (il, f :: fl) 1688 in 1689 fn l => List.foldl part ([],[]) (List.rev l) 1690 end; 1691 1692local 1693 open Parse; 1694 1695 infixr 9 >>++ 1696 infixr 8 ++ 1697 infixr 7 >> 1698 infixr 6 || 1699 1700 fun declarationParser mapping = 1701 (includeParser >> IncludeDeclaration) || 1702 (formulaParser mapping >> FormulaDeclaration); 1703 1704 fun parseChars parser chars = 1705 let 1706 val tokens = Parse.everything lexer chars 1707 in 1708 Parse.everything (parser >> singleton) tokens 1709 end; 1710in 1711 fun parseDeclaration mapping = parseChars (declarationParser mapping); 1712end; 1713 1714(* ------------------------------------------------------------------------- *) 1715(* Clause information. *) 1716(* ------------------------------------------------------------------------- *) 1717 1718datatype clauseSource = 1719 CnfClauseSource of formulaName * literal list 1720 | FofClauseSource of Normalize.thm; 1721 1722type 'a clauseInfo = 'a LiteralSetMap.map; 1723 1724type clauseNames = formulaName clauseInfo; 1725 1726type clauseRoles = role clauseInfo; 1727 1728type clauseSources = clauseSource clauseInfo; 1729 1730val noClauseNames : clauseNames = LiteralSetMap.new (); 1731 1732val allClauseNames : clauseNames -> formulaNameSet = 1733 let 1734 fun add (_,n,s) = addFormulaNameSet s n 1735 in 1736 LiteralSetMap.foldl add emptyFormulaNameSet 1737 end; 1738 1739val noClauseRoles : clauseRoles = LiteralSetMap.new (); 1740 1741val noClauseSources : clauseSources = LiteralSetMap.new (); 1742 1743(* ------------------------------------------------------------------------- *) 1744(* Comments. *) 1745(* ------------------------------------------------------------------------- *) 1746 1747fun mkLineComment "" = "%" 1748 | mkLineComment line = "% " ^ line; 1749 1750fun destLineComment cs = 1751 case cs of 1752 [] => "" 1753 | #"%" :: #" " :: rest => String.implode rest 1754 | #"%" :: rest => String.implode rest 1755 | _ => raise Error "Tptp.destLineComment"; 1756 1757val isLineComment = can destLineComment; 1758 1759(* ------------------------------------------------------------------------- *) 1760(* TPTP problems. *) 1761(* ------------------------------------------------------------------------- *) 1762 1763type comments = string list; 1764 1765type includes = string list; 1766 1767datatype problem = 1768 Problem of 1769 {comments : comments, 1770 includes : includes, 1771 formulas : formula list}; 1772 1773fun hasCnfConjecture (Problem {formulas,...}) = 1774 List.exists isCnfConjectureFormula formulas; 1775 1776fun hasFofConjecture (Problem {formulas,...}) = 1777 List.exists isFofConjectureFormula formulas; 1778 1779fun hasConjecture (Problem {formulas,...}) = 1780 List.exists isConjectureFormula formulas; 1781 1782fun freeVars (Problem {formulas,...}) = freeVarsListFormula formulas; 1783 1784local 1785 fun bump n avoid = 1786 let 1787 val s = FormulaName (Int.toString n) 1788 in 1789 if memberFormulaNameSet s avoid then bump (n + 1) avoid 1790 else (s, n, addFormulaNameSet avoid s) 1791 end; 1792 1793 fun fromClause defaultRole names roles cl (n,avoid) = 1794 let 1795 val (name,n,avoid) = 1796 case LiteralSetMap.peek names cl of 1797 SOME name => (name,n,avoid) 1798 | NONE => bump n avoid 1799 1800 val role = Option.getOpt (LiteralSetMap.peek roles cl, defaultRole) 1801 1802 val body = CnfFormulaBody (clauseFromLiteralSet cl) 1803 1804 val source = NoFormulaSource 1805 1806 val formula = 1807 Formula 1808 {name = name, 1809 role = role, 1810 body = body, 1811 source = source} 1812 in 1813 (formula,(n,avoid)) 1814 end; 1815in 1816 fun mkProblem {comments,includes,names,roles,problem} = 1817 let 1818 fun fromCl defaultRole = fromClause defaultRole names roles 1819 1820 val {axioms,conjecture} = problem 1821 1822 val n_avoid = (0, allClauseNames names) 1823 1824 val (axiomFormulas,n_avoid) = maps (fromCl AxiomRole) axioms n_avoid 1825 1826 val (conjectureFormulas,_) = 1827 maps (fromCl NegatedConjectureRole) conjecture n_avoid 1828 1829 val formulas = axiomFormulas @ conjectureFormulas 1830 in 1831 Problem 1832 {comments = comments, 1833 includes = includes, 1834 formulas = formulas} 1835 end; 1836end; 1837 1838type normalization = 1839 {problem : Problem.problem, 1840 sources : clauseSources}; 1841 1842val initialNormalization : normalization = 1843 {problem = {axioms = [], conjecture = []}, 1844 sources = noClauseSources}; 1845 1846datatype problemGoal = 1847 NoGoal 1848 | CnfGoal of (formulaName * clause) list 1849 | FofGoal of (formulaName * Formula.formula) list; 1850 1851local 1852 fun partitionFormula (formula,(cnfAxioms,fofAxioms,cnfGoals,fofGoals)) = 1853 let 1854 val Formula {name,role,body,...} = formula 1855 in 1856 case body of 1857 CnfFormulaBody cl => 1858 if isCnfConjectureRole role then 1859 let 1860 val cnfGoals = (name,cl) :: cnfGoals 1861 in 1862 (cnfAxioms,fofAxioms,cnfGoals,fofGoals) 1863 end 1864 else 1865 let 1866 val cnfAxioms = (name,cl) :: cnfAxioms 1867 in 1868 (cnfAxioms,fofAxioms,cnfGoals,fofGoals) 1869 end 1870 | FofFormulaBody fm => 1871 if isFofConjectureRole role then 1872 let 1873 val fofGoals = (name,fm) :: fofGoals 1874 in 1875 (cnfAxioms,fofAxioms,cnfGoals,fofGoals) 1876 end 1877 else 1878 let 1879 val fofAxioms = (name,fm) :: fofAxioms 1880 in 1881 (cnfAxioms,fofAxioms,cnfGoals,fofGoals) 1882 end 1883 end; 1884 1885 fun partitionFormulas fms = 1886 let 1887 val (cnfAxioms,fofAxioms,cnfGoals,fofGoals) = 1888 List.foldl partitionFormula ([],[],[],[]) fms 1889 1890 val goal = 1891 case (List.rev cnfGoals, List.rev fofGoals) of 1892 ([],[]) => NoGoal 1893 | (cnfGoals,[]) => CnfGoal cnfGoals 1894 | ([],fofGoals) => FofGoal fofGoals 1895 | (_ :: _, _ :: _) => 1896 raise Error "TPTP problem has both cnf and fof conjecture formulas" 1897 in 1898 {cnfAxioms = List.rev cnfAxioms, 1899 fofAxioms = List.rev fofAxioms, 1900 goal = goal} 1901 end; 1902 1903 fun addClauses role clauses acc : normalization = 1904 let 1905 fun addClause (cl_src,sources) = 1906 LiteralSetMap.insert sources cl_src 1907 1908 val {problem,sources} : normalization = acc 1909 val {axioms,conjecture} = problem 1910 1911 val cls = List.map fst clauses 1912 val (axioms,conjecture) = 1913 if isCnfConjectureRole role then (axioms, cls @ conjecture) 1914 else (cls @ axioms, conjecture) 1915 1916 val problem = {axioms = axioms, conjecture = conjecture} 1917 and sources = List.foldl addClause sources clauses 1918 in 1919 {problem = problem, 1920 sources = sources} 1921 end; 1922 1923 fun addCnf role ((name,clause),(norm,cnf)) = 1924 if List.exists (equalBooleanLiteral true) clause then (norm,cnf) 1925 else 1926 let 1927 val cl = List.mapPartial (total destLiteral) clause 1928 val cl = LiteralSet.fromList cl 1929 1930 val src = CnfClauseSource (name,clause) 1931 1932 val norm = addClauses role [(cl,src)] norm 1933 in 1934 (norm,cnf) 1935 end; 1936 1937 val addCnfAxiom = addCnf AxiomRole; 1938 1939 val addCnfGoal = addCnf NegatedConjectureRole; 1940 1941 fun addFof role (th,(norm,cnf)) = 1942 let 1943 fun sourcify (cl,inf) = (cl, FofClauseSource inf) 1944 1945 val (clauses,cnf) = Normalize.addCnf th cnf 1946 val clauses = List.map sourcify clauses 1947 val norm = addClauses role clauses norm 1948 in 1949 (norm,cnf) 1950 end; 1951 1952 fun addFofAxiom ((_,fm),acc) = 1953 addFof AxiomRole (Normalize.mkAxiom fm, acc); 1954 1955 fun normProblem subgoal (norm,_) = 1956 let 1957 val {problem,sources} = norm 1958 val {axioms,conjecture} = problem 1959 val problem = {axioms = List.rev axioms, conjecture = List.rev conjecture} 1960 in 1961 {subgoal = subgoal, 1962 problem = problem, 1963 sources = sources} 1964 end; 1965 1966 val normProblemFalse = normProblem (Formula.False,[]); 1967 1968 fun splitProblem acc = 1969 let 1970 fun mk parents subgoal = 1971 let 1972 val subgoal = Formula.generalize subgoal 1973 1974 val th = Normalize.mkAxiom (Formula.Not subgoal) 1975 1976 val acc = addFof NegatedConjectureRole (th,acc) 1977 in 1978 normProblem (subgoal,parents) acc 1979 end 1980 1981 fun split (name,goal) = 1982 let 1983 val subgoals = Formula.splitGoal goal 1984 val subgoals = 1985 if List.null subgoals then [Formula.True] else subgoals 1986 1987 val parents = [name] 1988 in 1989 List.map (mk parents) subgoals 1990 end 1991 in 1992 fn goals => List.concat (List.map split goals) 1993 end; 1994 1995 fun clausesToGoal cls = 1996 let 1997 val cls = List.map (Formula.generalize o clauseToFormula o snd) cls 1998 in 1999 Formula.listMkConj cls 2000 end; 2001 2002 fun formulasToGoal fms = 2003 let 2004 val fms = List.map (Formula.generalize o snd) fms 2005 in 2006 Formula.listMkConj fms 2007 end; 2008in 2009 fun goal (Problem {formulas,...}) = 2010 let 2011 val {cnfAxioms,fofAxioms,goal} = partitionFormulas formulas 2012 2013 val fm = 2014 case goal of 2015 NoGoal => Formula.False 2016 | CnfGoal cls => Formula.Imp (clausesToGoal cls, Formula.False) 2017 | FofGoal goals => formulasToGoal goals 2018 2019 val fm = 2020 if List.null fofAxioms then fm 2021 else Formula.Imp (formulasToGoal fofAxioms, fm) 2022 2023 val fm = 2024 if List.null cnfAxioms then fm 2025 else Formula.Imp (clausesToGoal cnfAxioms, fm) 2026 in 2027 fm 2028 end; 2029 2030 fun normalize (Problem {formulas,...}) = 2031 let 2032 val {cnfAxioms,fofAxioms,goal} = partitionFormulas formulas 2033 2034 val acc = (initialNormalization, Normalize.initialCnf) 2035 val acc = List.foldl addCnfAxiom acc cnfAxioms 2036 val acc = List.foldl addFofAxiom acc fofAxioms 2037 in 2038 case goal of 2039 NoGoal => [normProblemFalse acc] 2040 | CnfGoal cls => [normProblemFalse (List.foldl addCnfGoal acc cls)] 2041 | FofGoal goals => splitProblem acc goals 2042 end; 2043end; 2044 2045local 2046 datatype blockComment = 2047 OutsideBlockComment 2048 | EnteringBlockComment 2049 | InsideBlockComment 2050 | LeavingBlockComment; 2051 2052 fun stripLineComments acc strm = 2053 case strm of 2054 Stream.Nil => (List.rev acc, Stream.Nil) 2055 | Stream.Cons (line,rest) => 2056 case total destLineComment line of 2057 SOME s => stripLineComments (s :: acc) (rest ()) 2058 | NONE => (List.rev acc, Stream.filter (not o isLineComment) strm); 2059 2060 fun advanceBlockComment c state = 2061 case state of 2062 OutsideBlockComment => 2063 if c = #"/" then (Stream.Nil, EnteringBlockComment) 2064 else (Stream.singleton c, OutsideBlockComment) 2065 | EnteringBlockComment => 2066 if c = #"*" then (Stream.Nil, InsideBlockComment) 2067 else if c = #"/" then (Stream.singleton #"/", EnteringBlockComment) 2068 else (Stream.fromList [#"/",c], OutsideBlockComment) 2069 | InsideBlockComment => 2070 if c = #"*" then (Stream.Nil, LeavingBlockComment) 2071 else (Stream.Nil, InsideBlockComment) 2072 | LeavingBlockComment => 2073 if c = #"/" then (Stream.Nil, OutsideBlockComment) 2074 else if c = #"*" then (Stream.Nil, LeavingBlockComment) 2075 else (Stream.Nil, InsideBlockComment); 2076 2077 fun eofBlockComment state = 2078 case state of 2079 OutsideBlockComment => Stream.Nil 2080 | EnteringBlockComment => Stream.singleton #"/" 2081 | _ => raise Error "EOF inside a block comment"; 2082 2083 val stripBlockComments = 2084 Stream.mapsConcat advanceBlockComment eofBlockComment 2085 OutsideBlockComment; 2086in 2087 fun read {mapping,filename} = 2088 let 2089 (* Estimating parse error line numbers *) 2090 2091 val lines = Stream.fromTextFile {filename = filename} 2092 2093 val {chars,parseErrorLocation} = Parse.initialize {lines = lines} 2094 in 2095 (let 2096 (* The character stream *) 2097 2098 val (comments,chars) = stripLineComments [] chars 2099 2100 val chars = Parse.everything Parse.any chars 2101 2102 val chars = stripBlockComments chars 2103 2104 (* The declaration stream *) 2105 2106 val declarations = Stream.toList (parseDeclaration mapping chars) 2107 2108 val (includes,formulas) = partitionDeclarations declarations 2109 in 2110 Problem 2111 {comments = comments, 2112 includes = includes, 2113 formulas = formulas} 2114 end 2115 handle Parse.NoParse => raise Error "parse error") 2116 handle Error err => 2117 raise Error ("error in TPTP file \"" ^ filename ^ "\" " ^ 2118 parseErrorLocation () ^ "\n" ^ err) 2119 end; 2120end; 2121 2122local 2123 val newline = Stream.singleton "\n"; 2124 2125 fun spacer top = if top then Stream.Nil else newline; 2126 2127 fun mkComment comment = mkLineComment comment ^ "\n"; 2128 2129 fun mkInclude inc = includeToString inc ^ "\n"; 2130 2131 fun formulaStream _ _ [] = Stream.Nil 2132 | formulaStream mapping top (h :: t) = 2133 Stream.append 2134 (Stream.concatList 2135 [spacer top, 2136 Stream.singleton (formulaToString mapping h), 2137 newline]) 2138 (fn () => formulaStream mapping false t); 2139in 2140 fun write {problem,mapping,filename} = 2141 let 2142 val Problem {comments,includes,formulas} = problem 2143 2144 val includesTop = List.null comments 2145 val formulasTop = includesTop andalso List.null includes 2146 in 2147 Stream.toTextFile 2148 {filename = filename} 2149 (Stream.concatList 2150 [Stream.map mkComment (Stream.fromList comments), 2151 spacer includesTop, 2152 Stream.map mkInclude (Stream.fromList includes), 2153 formulaStream mapping formulasTop formulas]) 2154 end; 2155end; 2156 2157local 2158 fun refute {axioms,conjecture} = 2159 let 2160 val axioms = List.map Thm.axiom axioms 2161 and conjecture = List.map Thm.axiom conjecture 2162 val problem = {axioms = axioms, conjecture = conjecture} 2163 val resolution = Resolution.new Resolution.default problem 2164 in 2165 case Resolution.loop resolution of 2166 Resolution.Contradiction _ => true 2167 | Resolution.Satisfiable _ => false 2168 end; 2169in 2170 fun prove filename = 2171 let 2172 val problem = read filename 2173 val problems = List.map #problem (normalize problem) 2174 in 2175 List.all refute problems 2176 end; 2177end; 2178 2179(* ------------------------------------------------------------------------- *) 2180(* TSTP proofs. *) 2181(* ------------------------------------------------------------------------- *) 2182 2183local 2184 fun newName avoid prefix = 2185 let 2186 fun bump i = 2187 let 2188 val name = FormulaName (prefix ^ Int.toString i) 2189 val i = i + 1 2190 in 2191 if memberFormulaNameSet name avoid then bump i else (name,i) 2192 end 2193 in 2194 bump 2195 end; 2196 2197 fun lookupClauseSource sources cl = 2198 case LiteralSetMap.peek sources cl of 2199 SOME src => src 2200 | NONE => raise Bug "Tptp.lookupClauseSource"; 2201 2202 fun lookupFormulaName fmNames fm = 2203 case FormulaMap.peek fmNames fm of 2204 SOME name => name 2205 | NONE => raise Bug "Tptp.lookupFormulaName"; 2206 2207 fun lookupClauseName clNames cl = 2208 case LiteralSetMap.peek clNames cl of 2209 SOME name => name 2210 | NONE => raise Bug "Tptp.lookupClauseName"; 2211 2212 fun lookupClauseSourceName sources fmNames cl = 2213 case lookupClauseSource sources cl of 2214 CnfClauseSource (name,_) => name 2215 | FofClauseSource th => 2216 let 2217 val (fm,_) = Normalize.destThm th 2218 in 2219 lookupFormulaName fmNames fm 2220 end; 2221 2222 fun collectProofDeps sources ((_,inf),names_ths) = 2223 case inf of 2224 Proof.Axiom cl => 2225 let 2226 val (names,ths) = names_ths 2227 in 2228 case lookupClauseSource sources cl of 2229 CnfClauseSource (name,_) => 2230 let 2231 val names = addFormulaNameSet names name 2232 in 2233 (names,ths) 2234 end 2235 | FofClauseSource th => 2236 let 2237 val ths = th :: ths 2238 in 2239 (names,ths) 2240 end 2241 end 2242 | _ => names_ths; 2243 2244 fun collectNormalizeDeps ((_,inf,_),fofs_defs) = 2245 case inf of 2246 Normalize.Axiom fm => 2247 let 2248 val (fofs,defs) = fofs_defs 2249 val fofs = FormulaSet.add fofs fm 2250 in 2251 (fofs,defs) 2252 end 2253 | Normalize.Definition n_d => 2254 let 2255 val (fofs,defs) = fofs_defs 2256 val defs = StringMap.insert defs n_d 2257 in 2258 (fofs,defs) 2259 end 2260 | _ => fofs_defs; 2261 2262 fun collectSubgoalProofDeps subgoalProof (names,fofs,defs) = 2263 let 2264 val {subgoal,sources,refutation} = subgoalProof 2265 2266 val names = addListFormulaNameSet names (snd subgoal) 2267 2268 val proof = Proof.proof refutation 2269 2270 val (names,ths) = 2271 List.foldl (collectProofDeps sources) (names,[]) proof 2272 2273 val normalization = Normalize.proveThms (List.rev ths) 2274 2275 val (fofs,defs) = 2276 List.foldl collectNormalizeDeps (fofs,defs) normalization 2277 2278 val subgoalProof = 2279 {subgoal = subgoal, 2280 normalization = normalization, 2281 sources = sources, 2282 proof = proof} 2283 in 2284 (subgoalProof,(names,fofs,defs)) 2285 end; 2286 2287 fun addProblemFormula names fofs (formula,(avoid,formulas,fmNames)) = 2288 let 2289 val name = nameFormula formula 2290 2291 val avoid = addFormulaNameSet avoid name 2292 2293 val (formulas,fmNames) = 2294 if memberFormulaNameSet name names then 2295 (formula :: formulas, fmNames) 2296 else 2297 case bodyFormula formula of 2298 CnfFormulaBody _ => (formulas,fmNames) 2299 | FofFormulaBody fm => 2300 if not (FormulaSet.member fm fofs) then (formulas,fmNames) 2301 else (formula :: formulas, FormulaMap.insert fmNames (fm,name)) 2302 in 2303 (avoid,formulas,fmNames) 2304 end; 2305 2306 fun addDefinitionFormula avoid (_,def,(formulas,i,fmNames)) = 2307 let 2308 val (name,i) = newName avoid "definition_" i 2309 2310 val role = DefinitionRole 2311 2312 val body = FofFormulaBody def 2313 2314 val source = NoFormulaSource 2315 2316 val formula = 2317 Formula 2318 {name = name, 2319 role = role, 2320 body = body, 2321 source = source} 2322 2323 val formulas = formula :: formulas 2324 2325 val fmNames = FormulaMap.insert fmNames (def,name) 2326 in 2327 (formulas,i,fmNames) 2328 end; 2329 2330 fun addSubgoalFormula avoid subgoalProof (formulas,i) = 2331 let 2332 val {subgoal,normalization,sources,proof} = subgoalProof 2333 2334 val (fm,pars) = subgoal 2335 2336 val (name,i) = newName avoid "subgoal_" i 2337 2338 val number = i - 1 2339 2340 val (subgoal,formulas) = 2341 if List.null pars then (NONE,formulas) 2342 else 2343 let 2344 val role = PlainRole 2345 2346 val body = FofFormulaBody fm 2347 2348 val source = 2349 StripFormulaSource 2350 {inference = "strip", 2351 parents = pars} 2352 2353 val formula = 2354 Formula 2355 {name = name, 2356 role = role, 2357 body = body, 2358 source = source} 2359 in 2360 (SOME (name,fm), formula :: formulas) 2361 end 2362 2363 val subgoalProof = 2364 {number = number, 2365 subgoal = subgoal, 2366 normalization = normalization, 2367 sources = sources, 2368 proof = proof} 2369 in 2370 (subgoalProof,(formulas,i)) 2371 end; 2372 2373 fun mkNormalizeFormulaSource fmNames inference fms = 2374 let 2375 val fms = 2376 case inference of 2377 Normalize.Axiom fm => fm :: fms 2378 | Normalize.Definition (_,fm) => fm :: fms 2379 | _ => fms 2380 2381 val parents = List.map (lookupFormulaName fmNames) fms 2382 in 2383 NormalizeFormulaSource 2384 {inference = inference, 2385 parents = parents} 2386 end; 2387 2388 fun mkProofFormulaSource sources fmNames clNames inference = 2389 let 2390 val parents = 2391 case inference of 2392 Proof.Axiom cl => [lookupClauseSourceName sources fmNames cl] 2393 | _ => 2394 let 2395 val cls = List.map Thm.clause (Proof.parents inference) 2396 in 2397 List.map (lookupClauseName clNames) cls 2398 end 2399 in 2400 ProofFormulaSource 2401 {inference = inference, 2402 parents = parents} 2403 end; 2404 2405 fun addNormalizeFormula avoid prefix ((fm,inf,fms),acc) = 2406 let 2407 val (formulas,i,fmNames) = acc 2408 2409 val (name,i) = newName avoid prefix i 2410 2411 val role = PlainRole 2412 2413 val body = FofFormulaBody fm 2414 2415 val source = mkNormalizeFormulaSource fmNames inf fms 2416 2417 val formula = 2418 Formula 2419 {name = name, 2420 role = role, 2421 body = body, 2422 source = source} 2423 2424 val formulas = formula :: formulas 2425 2426 val fmNames = FormulaMap.insert fmNames (fm,name) 2427 in 2428 (formulas,i,fmNames) 2429 end; 2430 2431 fun isSameClause sources formulas inf = 2432 case inf of 2433 Proof.Axiom cl => 2434 (case lookupClauseSource sources cl of 2435 CnfClauseSource (name,lits) => 2436 if List.exists isBooleanLiteral lits then NONE 2437 else SOME name 2438 | _ => NONE) 2439 | _ => NONE; 2440 2441 fun addProofFormula avoid sources fmNames prefix ((th,inf),acc) = 2442 let 2443 val (formulas,i,clNames) = acc 2444 2445 val cl = Thm.clause th 2446 in 2447 case isSameClause sources formulas inf of 2448 SOME name => 2449 let 2450 val clNames = LiteralSetMap.insert clNames (cl,name) 2451 in 2452 (formulas,i,clNames) 2453 end 2454 | NONE => 2455 let 2456 val (name,i) = newName avoid prefix i 2457 2458 val role = PlainRole 2459 2460 val body = CnfFormulaBody (clauseFromLiteralSet cl) 2461 2462 val source = mkProofFormulaSource sources fmNames clNames inf 2463 2464 val formula = 2465 Formula 2466 {name = name, 2467 role = role, 2468 body = body, 2469 source = source} 2470 2471 val formulas = formula :: formulas 2472 2473 val clNames = LiteralSetMap.insert clNames (cl,name) 2474 in 2475 (formulas,i,clNames) 2476 end 2477 end; 2478 2479 fun addSubgoalProofFormulas avoid fmNames (subgoalProof,formulas) = 2480 let 2481 val {number,subgoal,normalization,sources,proof} = subgoalProof 2482 2483 val (formulas,fmNames) = 2484 case subgoal of 2485 NONE => (formulas,fmNames) 2486 | SOME (name,fm) => 2487 let 2488 val source = 2489 StripFormulaSource 2490 {inference = "negate", 2491 parents = [name]} 2492 2493 val prefix = "negate_" ^ Int.toString number ^ "_" 2494 2495 val (name,_) = newName avoid prefix 0 2496 2497 val role = PlainRole 2498 2499 val fm = Formula.Not fm 2500 2501 val body = FofFormulaBody fm 2502 2503 val formula = 2504 Formula 2505 {name = name, 2506 role = role, 2507 body = body, 2508 source = source} 2509 2510 val formulas = formula :: formulas 2511 2512 val fmNames = FormulaMap.insert fmNames (fm,name) 2513 in 2514 (formulas,fmNames) 2515 end 2516 2517 val prefix = "normalize_" ^ Int.toString number ^ "_" 2518 val (formulas,_,fmNames) = 2519 List.foldl (addNormalizeFormula avoid prefix) 2520 (formulas,0,fmNames) normalization 2521 2522 val prefix = "refute_" ^ Int.toString number ^ "_" 2523 val clNames : formulaName LiteralSetMap.map = LiteralSetMap.new () 2524 val (formulas,_,_) = 2525 List.foldl (addProofFormula avoid sources fmNames prefix) 2526 (formulas,0,clNames) proof 2527 in 2528 formulas 2529 end; 2530in 2531 fun fromProof {problem,proofs} = 2532 let 2533 val names = emptyFormulaNameSet 2534 and fofs = FormulaSet.empty 2535 and defs : Formula.formula StringMap.map = StringMap.new () 2536 2537 val (proofs,(names,fofs,defs)) = 2538 maps collectSubgoalProofDeps proofs (names,fofs,defs) 2539 2540 val Problem {formulas,...} = problem 2541 2542 val fmNames : formulaName FormulaMap.map = FormulaMap.new () 2543 val (avoid,formulas,fmNames) = 2544 List.foldl (addProblemFormula names fofs) 2545 (emptyFormulaNameSet,[],fmNames) formulas 2546 2547 val (formulas,_,fmNames) = 2548 StringMap.foldl (addDefinitionFormula avoid) 2549 (formulas,0,fmNames) defs 2550 2551 val (proofs,(formulas,_)) = 2552 maps (addSubgoalFormula avoid) proofs (formulas,0) 2553 2554 val formulas = 2555 List.foldl (addSubgoalProofFormulas avoid fmNames) formulas proofs 2556 in 2557 List.rev formulas 2558 end 2559(*MetisDebug 2560 handle Error err => raise Bug ("Tptp.fromProof: shouldn't fail:\n" ^ err); 2561*) 2562end; 2563 2564end 2565