英文:
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<ParkingSpace>) returns (newSpaces: seq<ParkingSpace>)
modifies set space | space in Spaces
{
var i := 0;
while i < |Spaces|
invariant 0 <= i <= |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<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;
}
}
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<object>
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<ParkingSpace>) returns (newSpaces: seq<ParkingSpace>)
requires forall i :: 0 <= i < |Spaces| ==> Spaces[i].Occupied != 0;
modifies set space | space in Spaces
ensures forall i :: 0 <= i < |Spaces| ==> Spaces[i].Occupied == 0
{
var i := 0;
while i < |Spaces|
invariant 0 <= i <= |Spaces|
invariant forall k :: 0 <= k < i ==> 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<object>
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<ParkingSpace>) returns (newSpaces: seq<ParkingSpace>)
requires forall i :: 0 <= i < |Spaces| ==> Spaces[i].Occupied != 0;
modifies set space | space in Spaces
ensures forall i :: 0 <= i < |Spaces| ==> Spaces[i].Occupied == 0
{
var i := 0;
while i < |Spaces|
invariant 0 <= i <= |Spaces|
invariant forall k :: 0 <= k < i ==> 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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论