[Why3-club] Is this goal really (un)tractable ?
frederic.besson at inria.fr
Wed Feb 22 15:53:07 CET 2012
I am trying to prove simple properties about an interpreter of a simple language.
My goals, which (to me) are straightforward, are not discharged by provers [alt-ergo, cvc3,eprover,vampire,yices].
This is the case for the following simplistic theory.
use import int.Int
use import option.Option
type value = Int int | Loc location
type pc = int
function evalcond (p:pc) (x:value) (jmp:pc) : option pc =
match x with
| Loc _ -> None
| Int i -> if i >= 0 then Some p else Some jmp
goal eval_case : forall p p':pc, x:value.
evalcond 1 x 4 = Some p' ->
p' = 1 \/ p' = 4
Could you tell me what I am doing wrong ?
This is so simple, I almost suspect a bug...
Actually, I also have a non-monotonicity problem.
* Provers do not discharge my initial problem
* Provers do discharge a cut-down version [alt-ergo.cvc3]
* Provers do not discharge the previous minimal goal
Are there known tricks to minimize the source of such erratic behaviors ?
Are there ways to provide hints to the provers.
For instance, is there a way to instruct the prover to
* recursively inline certain definitions (something like the simpl Coq tactic)
* when it is done, do a case analysis over the match statements
A that point, the previous goal is quantifier-free and falls in a decidable fragment...
I almost lost faith in those provers :(
Any insight would be much appreciated!
More information about the Why3-club