krun --prove not generating correct proof obligations

[lucaspena]

I am trying to verify some simple programs in our semantics for Plutus Core (github.com/kframework/plutus-core-semantics). I am running into an issue using krun --prove where it appears as though incorrect or incomplete proof obligations are being generated.

Specifically, we were given a function const defined in a different file as lam x (lam y x) and I'm trying to prove that const X Y = X. This works great and as expected, but when trying to prove const X Y = Y, the prover also outputs true. In fact, when run in debug mode, the right hand side of the proof obligation is just true.

However, if I add any side condition mentioning Y, even something trivial like Y == 0 orBool Y =/= 0, the prover cannot prove it (the desired behavior). Now, the right hand side of the proof obligation is something equivalent to X == Y which is expected. I've copied the spec file below. All code is located at the github link mentioned above, under the verification-env branch.

module CONST-SPEC
  imports PLUTUS-CORE

  // Claim that const x y = y. Should fail.
  rule
    <k> (define result [((#parseToken("ModName@PLUTUS-CORE-SYNTAX", "ModConst"):>ModName) . const):QualN X:Int Y:Int]):Def => .K ... </k>
    <lenv> _ </lenv>
    <genv> E GENV => E GENV (MN . result) |-> Y </genv>
    <mod> MN:ModName </mod>
    requires notBool ((MN . result) in keys(E GENV)) andBool notBool (((#parseToken("ModName@PLUTUS-CORE-SYNTAX", "ModConst"):>ModName) . result) in keys(E))
             andBool (Y ==Int 0 orBool Y =/=Int 0)

endmodule

The obligation generated by the prover for this looks like

Attempting to prove:
    _andBool_(_==K_(Set:in(_._(_161:ModName@PLUTUS-CORE-SYNTAX,, Name@PLUTUS-CORE-SYNTAX(#"result")),, keys(_158:Map@MAP) _._(ModName@PLUTUS-CORE-SYNTAX(#"ModConst"),, Name@PLUTUS-CORE-SYNTAX(#"const"))),, Bool@BOOL-SYNTAX(#"false")),, _andBool_(_==K_(Set:in(_._(ModName@PLUTUS-CORE-SYNTAX(#"ModConst"),, Name@PLUTUS-CORE-SYNTAX(#"result")),, keys(_158:Map@MAP)),, Bool@BOOL-SYNTAX(#"false")),, _==K_(_orBool_(_==K_(_160:Int@INT-SYNTAX,, Int@INT-SYNTAX(#"0")),, notBool_(_==K_(_160:Int@INT-SYNTAX,, Int@INT-SYNTAX(#"0")))),, Bool@BOOL-SYNTAX(#"true"))))
  implies
    _==K_(_159:Int@INT-SYNTAX,, _160:Int@INT-SYNTAX)

This proof fails as expected. If the last conjunct in the side condition is removed (Y ==Int 0 orBool Y =/=Int 0), the obligation generated is

Attempting to prove:
    _andBool_(_==K_(Set:in(_._(_161:ModName@PLUTUS-CORE-SYNTAX,, Name@PLUTUS-CORE-SYNTAX(#"result")),, keys(_158:Map@MAP) _._(ModName@PLUTUS-CORE-SYNTAX(#"ModConst"),, Name@PLUTUS-CORE-SYNTAX(#"const"))),, Bool@BOOL-SYNTAX(#"false")),, _==K_(Set:in(_._(ModName@PLUTUS-CORE-SYNTAX(#"ModConst"),, Name@PLUTUS-CORE-SYNTAX(#"result")),, keys(_158:Map@MAP)),, Bool@BOOL-SYNTAX(#"false")))
  implies
    Bool@BOOL-SYNTAX(#"true")

which can be proved. @andreistefanescu, @msaxena2: Any ideas what could be causing this/ideas for how to fix it? Thanks, any help is appreciated.

[lucaspena]

Also @daejunpark

[lucaspena]

@msaxena2 and I figured out the root cause of the issue. Basically, matchImplies in the file ConstrainedTerm.java is trying to prove that the current term implies the target term. In doing this, it calculates the rightOnlyVariables, i.e. the variables present in the target term but not the current term. However, in this example, the current term no longer has the variable Y in scope as it is lost during execution. However, Y is not a right only variable, as it certainly appears in the initial term.