CODEWITHSUNDEEP
scalaformal-verificationleon
user1868607
user1868607

Reputation: 2600

Proving properties of sets in Inox/Welder

I would like to proof some properties of sets on Inox/Welder but I'm lacking examples that help me to figure out how to do so. Say I want to proof:

content(y::xs).contains(x) && x != y ==> content(xs).contains(x)

I define the property:

def property(xs: Expr) =
  forall("x"::A,"y"::A){case (x,y) 
    content(ConsA(y,xs)).contains(x) && x !== y ==> content(xs).contains(x)
  }

But it turns out that this property will not compile because it is not well formulated (apparently the wrong parts are .contains, &&, !==...)

So, what is the right way to formulate the property?. Here I'm assuming I have a content function defined as:

val contentFunction = mkFunDef(contentID)("A") { case Seq(aT) => (
    Seq("l" :: T(list)(aT)), SetType(aT), { case Seq(l) =>
      if_ (l.isInstOf(T(cons)(aT))) {
        SetAdd(E(contentID)(aT)(l.asInstOf(T(cons)(aT)).getField(tail)), l.asInstOf(T(cons)(aT)).getField(head))
        } else_ {
          FiniteSet(Seq.empty, aT)
        }
    })
  }

Regarding the proof part imagine I'm given the function:

def without(x: A, xs: List[A]) = xs match{
   case Nil() => Nil()
   case y :: ys if(x == y) => without(x,ys)
   case y :: ys if(x != y) => y :: without(x,ys)  
}

that should remove x from list xs and say I want to proof that

content(without(x,l)) == content(l) -- Set(x)

Can you give a sketch of how to do it? Should I be using the BuiltInNames such as SetDifference?

Upvotes: 0

Views: 66

Answers (1)

Romain Edelmann
Romain Edelmann

Reputation: 71

Compilation Error

The compilation error you are seeing might come from the missing arrow after the case in your formulation of the property. Also, be sure to use the right identifier for content.

def property(xs: Expr) =
  forall("x"::A,"y"::A) { case (x,y) =>
    contentID(ConsA(y,xs)).contains(x) && x !== y ==> contentID(xs).contains(x)
  }

Otherwise, the property looks correctly encoded using the Inox DSL.

Proof of Property

Regarding the proof itself, it don't think the without function is entirely necessary. The proof should go smoothly by structural induction on the list xs.

structuralInduction(property(_), "xs" :: T(List)(A)) { case (ihs, goal) =>
  ihs.expression match {
    case C(`Cons`, head, tail) => // Your case for Cons here.
    case C(`Nil`)              => // Your case for Nil here.
  }
}

The ListAndTrees showcases many such proofs.

BuiltInName

Regarding the BuiltInNames class, it is used in the parser of Inox expressions that is currently being developed within Welder. This very likely will be put in a separate project very soon.

This parser is used within Welder so that you can write Inox expressions using a somewhat friendlier syntax. For instance, your property could be stated as:

def property(xs: Expr) =
  e"forall x, y. contains(content(Cons(y, $xs)), x) && x != y ==> contains(content($xs), x)"

Inox Expressions

One last point. If you are looking for an exhaustive list of the different constructs available in Inox, have a look at the Expressions file in Inox.

Upvotes: 1

Related Questions