无法证明在Dafny 4中对对象序列的更改。

huangapple go评论53阅读模式
英文:

Cannot prove alterations to a sequence of objects in Dafny 4

问题

这个方法在 Main() 中调用时无法验证。

你如何调用它:

carPark.Spaces := carPark.closeCarPark(carPark.Spaces);

我的停车位构造函数:

class ParkingSpace {
    var SpaceID: int
    var Occupied: int
    var Reservation: string
    var Location: string
    var Car: Car?
    ghost var repr: set<object>

    constructor(id: int, filled: int, reservation: string, location: string)
        requires id != 0
        requires filled == 0 || filled == 1
        requires (location == "Regular" || location == "Subscription") && location != ""
        requires (reservation == "None" || |reservation| == 7) && reservation != ""
        requires forall i :: 0 <= i < |reservation| ==> ('a' <= reservation[i] <= 'z' || 'A' <= reservation[i] <= 'Z' || '0' <= reservation[i] <= '9')
    {
        SpaceID := id;
        Occupied := filled;
        Reservation := reservation;
        Location := location;
        Car := null;

        this.repr := this.repr + {this};
    }

    method setOccupied(count: int)
        modifies this
        ensures this.Occupied == count;
    {
        this.Occupied := count;
    }
}

我收到一个错误,通知我声明无法证明。更具体地说,移除 'modifies Spaces' 和修改对象属性的代码会启用验证,为什么它无法证明 Spaces 被修改了?

英文:

This method is not able to be verified when called within Main().

method closeCarPark(Spaces: seq&lt;ParkingSpace&gt;) returns (newSpaces: seq&lt;ParkingSpace&gt;)
      modifies set space | space in Spaces
   {
      var i := 0;

      while i &lt; |Spaces|
         invariant 0 &lt;= i &lt;= |Spaces|
      {

         Spaces[i].setOccupied(0);

         i := i + 1;
      }

      return Spaces;
   }

How im calling that:

carPark.Spaces := carPark.closeCarPark(carPark.Spaces);

My parking space constructor:

class ParkingSpace {    var SpaceID: int    var Occupied: int    var Reservation: string    var Location: string    var Car: Car?    ghost var repr: set&lt;object&gt;
    
       constructor(id: int, filled: int, reservation: string, location: string) 
          requires id != 0
          requires filled == 0 || filled == 1
          requires (location == &quot;Regular&quot; || location == &quot;Subscription&quot;) &amp;&amp; location != &quot;&quot;
          requires (reservation == &quot;None&quot; || |reservation| == 7) &amp;&amp; reservation != &quot;&quot; 
          requires forall i :: 0 &lt;= i &lt; |reservation| ==&gt; (&#39;a&#39; &lt;= reservation[i] &lt;= &#39;z&#39; || &#39;A&#39; &lt;= reservation[i] &lt;= &#39;Z&#39; || &#39;0&#39; &lt;= reservation[i] &lt;= &#39;9&#39;)    {
          SpaceID := id;
          Occupied := filled;
          Reservation := reservation;
          Location := location;
          Car := null;
    
          this.repr := this.repr + {this};    }
    
       method setOccupied(count: int) 
            modifies this
            ensures this.Occupied == count;
        {
            this.Occupied := count;
        }
    
    }

I get an error informing me that the declaration could not be proved. More specifically, removing 'modifies Spaces' and the code which changes the objects property enables verification, why cant it prove that Spaces is being Modified?

答案1

得分: 0

在Dafny中,Sets和seqs无论版本如何都是不可变的。类不是不可变的,通常被期望是堆对象,所以你必须指定它们将被修改。

class ParkingSpace {
    var Occupied: int;
    ghost var repr: set&lt;object&gt;

    constructor(val: int)
    {
        this.Occupied := val;
        this.repr := this.repr + {this};
    }

    method setOccupied(count: int) 
        modifies this
        ensures this.Occupied == count;
    {
        this.Occupied := count;
    }
}

//Edit:
method closeCarPark(Spaces: seq&lt;ParkingSpace&gt;) returns (newSpaces: seq&lt;ParkingSpace&gt;)
        requires forall i :: 0 &lt;= i &lt; |Spaces| ==&gt; Spaces[i].Occupied != 0;
      modifies set space | space in Spaces
      ensures forall i :: 0 &lt;= i &lt; |Spaces| ==&gt; Spaces[i].Occupied == 0
   {
      var i := 0;

      while i &lt; |Spaces|
        invariant 0 &lt;= i &lt;= |Spaces|
        invariant forall k :: 0 &lt;= k &lt; i ==&gt; Spaces[k].Occupied == 0
      {

         Spaces[i].setOccupied(0);

         i := i + 1;
      }

      return Spaces;
   }

编辑:关于你的第二个问题,"modifies"不是一个需要被证明的断言。它是一种许可,允许一个方法修改一组堆对象。在Dafny中,你可以使用"old()"操作符来断言一个值已经改变。你也可以直接断言一个值不同。在Dafny中,要求是它所知道的一切。因此,我创建了一个版本,它要求"Occupied"的初始值不为零,然后我们可以验证"closeCarPark"将所有的值都设置为零。

英文:

Sets and seqs are immutable in Dafny regardless of versions. Classes are not immutable and are expected to be heap objects so you have to specify that they will be modified.

class ParkingSpace {
    var Occupied: int;
    ghost var repr: set&lt;object&gt;

    constructor(val: int)
    {
        this.Occupied := val;
        this.repr := this.repr + {this};
    }

    method setOccupied(count: int) 
        modifies this
        ensures this.Occupied == count;
    {
        this.Occupied := count;
    }
}

//Edit:
method closeCarPark(Spaces: seq&lt;ParkingSpace&gt;) returns (newSpaces: seq&lt;ParkingSpace&gt;)
        requires forall i :: 0 &lt;= i &lt; |Spaces| ==&gt; Spaces[i].Occupied != 0;
      modifies set space | space in Spaces
      ensures forall i :: 0 &lt;= i &lt; |Spaces| ==&gt; Spaces[i].Occupied == 0
   {
      var i := 0;

      while i &lt; |Spaces|
        invariant 0 &lt;= i &lt;= |Spaces|
        invariant forall k :: 0 &lt;= k &lt; i ==&gt; Spaces[k].Occupied == 0
      {

         Spaces[i].setOccupied(0);

         i := i + 1;
      }

      return Spaces;
   }

Edit: To your second question, modifies is not an assertion to be proved. It is a permission that allows a method to modify a set of heap objects. In Dafny, you can make an assertion that a value as changed with the old() operator. You can also just assert that a value is different. In Dafny, the requirements are all that it knows. So I made a version where it requires the occupied to start out as not zero and then we can verify that closeCarPark sets all the values to 0.

huangapple
  • 本文由 发表于 2023年3月12日 18:31:46
  • 转载请务必保留本文链接:https://go.coder-hub.com/75712513.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定