-
Notifications
You must be signed in to change notification settings - Fork 18
/
provers.scala
132 lines (114 loc) · 4.71 KB
/
provers.scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
package gapt.provers
import gapt.expr._
import gapt.expr.formula.Formula
import gapt.expr.formula.hol.existentialClosure
import gapt.proofs.epsilon.EpsilonProof
import gapt.proofs.epsilon.ExpansionProofToEpsilon
import gapt.proofs.expansion.ExpansionProof
import gapt.proofs.expansion.eliminateCutsET
import gapt.proofs.lk.LKProof
import gapt.proofs.HOLClause
import gapt.proofs.HOLSequent
import gapt.proofs.Sequent
import gapt.proofs.context.Context
import gapt.proofs.context.mutable.MutableContext
import gapt.proofs.lk.rules.macros.ContractionMacroRule
import gapt.proofs.lk.transformations.LKToExpansionProof
import gapt.proofs.lk.util.ExtractInterpolant
import gapt.provers.Session.Runners._
import gapt.provers.Session._
import gapt.utils.Maybe
import gapt.utils.Tree
/**
* A prover that is able to refute HOL sequents/formulas (or subsets
* of HOL, like propositional logic).
*
* TODO: exceptions to indicate that a formula is not supported (e.g.
* for propositional provers).
*
* Implementors may want to override isValid(seq) to avoid parsing
* proofs.
*/
trait Prover {
/**
* @param formula The formula whose validity should be checked.
* @return True if the formula is valid.
*/
def isValid( formula: Formula )( implicit ctx: Maybe[Context] ): Boolean = isValid( HOLSequent( Nil, formula :: Nil ) )
/**
* @param seq The sequent whose validity should be checked.
* @return True if the formula is valid.
*/
def isValid( seq: HOLSequent )( implicit ctx: Maybe[Context] ): Boolean = getLKProof( seq ) match {
case Some( _ ) => true
case None => false
}
/**
* Checks whether a formula is unsatisfiable.
*/
def isUnsat( formula: Formula )( implicit ctx: Maybe[Context] ): Boolean = isValid( -formula )
/**
* Checks whether a set of clauses is unsatisfiable.
*/
def isUnsat( cnf: Iterable[HOLClause] )( implicit ctx: Maybe[Context] ): Boolean = isValid( existentialClosure( cnf ++: Sequent() map { _.toDisjunction } ) )
/**
* @param formula The formula that should be proved.
* @return An LK-Proof of :- formula, or None if not successful.
*/
def getLKProof( formula: Formula )( implicit ctx: Maybe[MutableContext] ): Option[LKProof] =
getLKProof( HOLSequent( Nil, formula :: Nil ) )
/**
* @param seq The sequent that should be proved.
* @return An LK-Proof of the sequent, or None if not successful.
*/
def getLKProof( seq: HOLSequent )( implicit ctx: Maybe[MutableContext] ): Option[LKProof]
def getExpansionProof( formula: Formula )( implicit ctx: Maybe[MutableContext] ): Option[ExpansionProof] =
getExpansionProof( Sequent() :+ formula )
def getExpansionProof( seq: HOLSequent )( implicit ctx: Maybe[MutableContext] ): Option[ExpansionProof] =
getLKProof( seq ) map { LKToExpansionProof( _ ) } map { eliminateCutsET( _ ) }
def getEpsilonProof( seq: HOLSequent )( implicit ctx0: Maybe[MutableContext] ): Option[EpsilonProof] = {
implicit val ctx = ctx0.getOrElse( MutableContext.guess( seq ) )
getExpansionProof( seq )( ctx ).map( ExpansionProofToEpsilon( _ ) )
}
def getEpsilonProof( formula: Formula )( implicit ctx: Maybe[MutableContext] ): Option[EpsilonProof] =
getEpsilonProof( Sequent() :+ formula )
def getInterpolant( tree: Tree[Formula] )( implicit ctx: Maybe[Context] ): Option[Tree[Formula]] =
getLKProof( tree.postOrder ++: Sequent() )( ctx.map( _.newMutable ) ).
map( ContractionMacroRule( _ ) ).
map( p => ExtractInterpolant( p, tree.map( p.conclusion.indexOf ) ) )
/**
* Method for running a session.
* @param program A proof session.
* @tparam A The return type of the session.
* @return The result of running the session.
*/
def runSession[A]( program: Session[A] ): A
}
/**
* A prover that interprets Sessions as stack operations.
*/
trait OneShotProver extends Prover {
override def runSession[A]( program: Session[A] ): A = new StackSessionRunner( this.isValid ).run( program )
}
/**
* A prover that determines validity via an incremental proof session.
*/
trait IncrementalProver extends Prover {
def treatUnknownAsSat = false
/**
* Tests the validity of a sequent.
*/
def isValidProgram( seq: HOLSequent ): Session[Boolean] = {
val ( groundSeq, _ ) = groundFreeVariables( seq )
for {
_ <- declareSymbolsIn( groundSeq.elements )
_ <- assert( groundSeq.map( identity, -_ ).elements.toList )
unsat <- checkUnsat
} yield unsat.getOrElse {
if ( treatUnknownAsSat ) false
else throw new IllegalArgumentException
}
}
override def getLKProof( seq: HOLSequent )( implicit ctx: Maybe[MutableContext] ): Option[LKProof] = ???
override def isValid( seq: HOLSequent )( implicit ctx: Maybe[Context] ): Boolean = runSession( isValidProgram( seq ) )
}