Я пытаюсь создать метод в Dafny, который позволяет мне вводить содержимое одного массива в другой. Например, если Array1= [1,2,3], Array2 = [6,7,8,9,0] и index = 1, выходной массив будет [1,6,7,8,9,0 ,2,3], так как метод вставляет содержимое Array2 в Array1 с заданным индексом вставки.
Код указан ниже:
method insertArrayIntoIndex(a: array<int>, index: int, add_these: array<int>) returns (result: array<int>)
requires 0 <= index < a.Length;
ensures result.Length == a.Length + add_these.Length;
ensures forall i :: 0 <= i < index ==> a[i] == result[i];
ensures forall i :: 0 <= i < add_these.Length ==> add_these[i] == result[i + index];
ensures forall i :: index <= i < a.Length ==> a[i] == result[i + add_these.Length];
{
result := new int[a.Length + add_these.Length];
// copy first part in
var pos := 0;
while (pos < index)
invariant 0 <= pos <= index
invariant 1 <= pos < index ==> result[pos-1] == a[pos-1]
{
result[pos] := a[pos];
pos := pos + 1;
}
// copy in the addition
pos := 0;
while (pos < add_these.Length)
invariant 0 <= pos <= add_these.Length
invariant 1 <= pos < add_these.Length ==> result[index + pos-1] == add_these[pos-1]
{
result[index + pos] := add_these[pos];
pos := pos + 1;
}
// copy the last part in
pos := index;
while (pos < a.Length)
invariant index <= pos <= a.Length
invariant index < pos < a.Length ==> result[pos-1 + add_these.Length] == a[pos-1]
{
result[pos + add_these.Length] := a[pos];
pos := pos + 1;
}
}
У меня возникли проблемы с написанием правильных инвариантов цикла, чтобы заставить код работать. Я попытался добавить утверждения в конце каждого раздела, чтобы доказать, что каждая часть работает, как показано ниже, но я не уверен, почему они терпят неудачу. Любая помощь будет принята с благодарностью. Я также добавил дополнительные утверждения в первый раздел, но все они, кажется, проходят, что сбивает меня с толку, почему утверждения снаружи терпят неудачу.
method insertArrayIntoIndex(a: array<int>, index: int, add_these: array<int>) returns (result: array<int>)
requires 0 <= index < a.Length;
ensures result.Length == a.Length + add_these.Length;
ensures forall i :: 0 <= i < index ==> a[i] == result[i];
ensures forall i :: 0 <= i < add_these.Length ==> add_these[i] == result[i + index];
ensures forall i :: index <= i < a.Length ==> a[i] == result[i + add_these.Length];
{
result := new int[a.Length + add_these.Length];
// copy first part in
var pos := 0;
while (pos < index)
invariant 0 <= pos <= index
invariant 1 <= pos < index ==> result[pos-1] == a[pos-1]
{
result[pos] := a[pos];
assert result[pos] == a[pos];
assert pos >1 ==> result[pos-1] == a[pos-1];
assert forall i :: 0 <= i < pos ==> result[i] == a[i];
pos := pos + 1;
}
assert forall i :: 0 <= i < index ==> a[i] == result[i];
// copy in the addition
pos := 0;
while (pos < add_these.Length)
invariant 0 <= pos <= add_these.Length
invariant 1 <= pos < add_these.Length ==> result[index + pos-1] == add_these[pos-1]
{
result[index + pos] := add_these[pos];
pos := pos + 1;
}
assert forall i :: 0 <= i < add_these.Length ==> result[index + i] == add_these[i];
// copy the last part in
pos := index;
while (pos < a.Length)
invariant index <= pos <= a.Length
invariant index < pos < a.Length ==> result[pos-1 + add_these.Length] == a[pos-1]
{
result[pos + add_these.Length] := a[pos];
pos := pos + 1;
}
assert forall i :: index <= i < a.Length ==> result[add_these.Length + i] == a[i];
}
Дафни использует инвариант цикла, чтобы рассуждать о петлях. Давайте поймем, что это влечет за собой.
Допустим, вы написали следующий цикл
idx := 0;
while idx < a.Length
invariant 0 <= idx <= a.Length
{
a[idx] := 1;
idx := idx + 1;
}
После цикла факты, доступные дафни, чтобы рассуждать об остальных
программа 0 <= idx <= a.Length && idx >= a.Length
(вторая часть
условие завершения цикла). Внутри цикла вы можете добавить assert a[idx] == 1
после назначения, и это проверит. Но
assert forall m :: 0 <= m < a.Length ==> a[m] == 1
цикл after не будет проверяться, так как нет инварианта, подтверждающего этот факт.
Допустим, мы хотим доказать, что все элементы массива равны 1 и пишем следующую программу
idx := 0;
while idx < a.Length
invariant 0 <= idx <= a.Length
invariant 1 <= idx <= a.Length ==> a[idx-1] == 1
{
a[idx] := 1;
idx := idx + 1;
}
Факты, доступные dafny после цикла
0 <= idx <= a.Length && 1 <= idx <= a.Length ==> a[idx-1] == 1 && idx >= a.Length
.
Используя вышеизложенное, невозможно получить, что
assert forall m :: 0 <= m < a.Length ==> a[m] == 1
. На самом деле возможно только
чтобы доказать, что последний элемент равен 1.
Нам нужно попросить Дафни запомнить использование forall.
idx := 0;
while idx < a.Length
invariant 0 <= idx <= a.Length
invariant forall m :: 0 <= m < idx ==> a[m] == 1
{
a[idx] := 1;
idx := idx + 1;
}
После цикла факт, доступный для dafny,
forall m :: 0 <= m < idx ==> a[m] == 1 && idx >= a.Length && 0 <= idx <= a.Length
.
Теперь можно доказать forall m :: 0 <= m < a.Length ==> a[m] == 1
Позаботившись об этом, вы можете проверить свою функцию вставки.
method insert(a: array<int>, idx: int, b: array<int>)
returns (r: array<int>)
requires 0 <= idx < a.Length
ensures r.Length == a.Length + b.Length
ensures forall m :: 0 <= m < idx ==> r[m] == a[m]
ensures forall m :: 0 <= m < b.Length ==> r[idx + m] == b[m]
ensures forall m :: idx <= m < a.Length ==> r[b.Length + m] == a[m]
{
var i := 0;
r := new int[a.Length + b.Length];
while i < idx
invariant 0 <= i <= idx
invariant forall m :: 0 <= m < i ==> r[m] == a[m]
{
r[i] := a[i];
i := i + 1;
}
if b.Length != 0 {
i := 0;
while i < b.Length
invariant 0 <= i <= b.Length
invariant forall m :: 0 <= m < i ==> r[idx + m] == b[m]
invariant forall m :: 0 <= m < idx ==> r[m] == a[m]
{
r[idx + i] := b[i];
i := i + 1;
}
}
i := idx;
while i < a.Length
invariant idx <= i <= a.Length
invariant forall m :: 0 <= m < idx ==> r[m] == a[m]
invariant forall m :: 0 <= m < b.Length ==> r[idx + m] == b[m]
invariant forall m :: idx <= m < i ==> r[b.Length + m] == a[m]
{
r[b.Length + i] := a[i];
i := i + 1;
}
return;
}
Теперь я могу проголосовать ^^
Не могли бы вы заменить «∙» на «::», «≔» на «: = " и «⟹» на «==>» в вашем коде? Вы должны использовать Emacs, но эти символы не подходят для анализа кода в VSCode. Это сделало бы ваши решения более легко проверяемыми для всех. Спасибо