Синтаксическая ошибка Dafny в функции

Я борюсь с синтаксисом дафни.

searchAndReplace получает три массива символов. Давайте представим, что line это [s][n][a][k][e]; pat равно [n][a], а dst равно [h][i]. Я хочу найти все вхождения pat в line и заменить его на dst, в результате чего получится [s][h][i][k][e]

Метод find вернет индекс первой буквы в line, равный pat.

Метод deleteудалит pat из line в переменной at, возвращенной в find, и переместит все остальные элементы после at+p влево, чтобы заполнить нулевые пробелы.

Метод insertосвободит место, чтобы dst добавить к lineв atпутем перемещения всех символов между atи at + p pпозициями вправо.

Я создал вспомогательную функцию, которая будет сравнивать patи dst, чтобы убедиться, что они не равны (если бы они были, это заменяло бы бесконечное время dstв line в случае, если patсуществовал в line). Сейчас я получаю сообщение об ошибке "then expected" на следующий раздел кода внутри функции checkIfEqual:

if(pat.Length != dst.Length) {
    return false;
   }

Полный код:

    method searchAndReplace(line:array<char>, l:int,
        pat:array<char>, p:int,
        dst:array<char>, n:int)returns(nl:int)
        requires line != null && pat!=null && dst!=null;
        requires !checkIfEqual(pat, dst);
        requires 0<=l<line.Length;
        requires 0<=p<pat.Length;
        requires 0<=n<dst.Length;

        modifies line;
        {
          var at:int := 0;
          var p:int := n;

          while(at != -1 )
          invariant -1<=at<=l;
          {
            at := find(line, l, dst, n);
            delete(line, l, at, p);
            insert(line, l, pat, p, at);
          }

          var length:int := line.Length;

          return length;
        }

        function checkIfEqual(pat:array<char>, dst:array<char>):bool
        requires pat!=null && dst!=null;
        reads pat;
        reads dst;
         {

          var i:int := 0;

          if(pat.Length != dst.Length) {
           return false;
           }

          while(i<dst.Length) {
            if(pat[i] != dst[i]){
              return false;
            }
            i := i + 1;
          }
          return true;

        }

        method insert(line:array<char>, l:int, nl:array<char>, p:int, at:int)
          requires line != null && nl != null;
          requires 0 <= l+p <= line.Length && 0 <= p <= nl.Length ;
          requires 0 <= at <= l;
          modifies line;
          ensures forall i :: (0<=i<p) ==> line[at+i] == nl[i]; // error
        {
          var i:int := 0;
          var positionAt:int := at;
          while(i<l && positionAt < l)
            invariant 0<=i<l+1;
            invariant at<=positionAt<=l;
          {
            line[positionAt+p] := line[positionAt];
            line[positionAt] := ' ';
            positionAt := positionAt + 1;
            i := i + 1;
          }

          positionAt := at;
          i := 0;
          while(i<p && positionAt < l)
            invariant 0<=i<=p;
            invariant at<=positionAt<=l;
          {
            line[positionAt] := nl[i];
            positionAt := positionAt + 1;
            i := i + 1;
          }
        }

        method find(line:array<char>, l:int, pat:array<char>, p:int) returns (pos:int)
          requires line!=null && pat!=null
          requires 0 <= l < line.Length
          requires 0 <= p < pat.Length
          ensures 0 <= pos < l || pos == -1
        {
          var iline:int := 0;
          var ipat:int  := 0;
          pos := -1;

          while(iline<l && ipat<pat.Length)
            invariant 0<=iline<=l
            invariant 0<=ipat<=pat.Length
            invariant -1 <= pos < iline
          {
              if(line[iline]==pat[ipat] && (line[iline]!=' ' && pat[ipat]!=' ')){
                  if(pos==-1){
                      pos := iline;
                  }
                  ipat:= ipat + 1;
              } else {
                if(ipat>0){
                  if(line[iline] == pat[ipat-1]){
                    pos := pos + 1;
                  }
                }
                ipat:=0;
                pos := -1;
              }
              if(ipat==p) {
                  return; 
              }
              iline := iline + 1; 
          }
          return;
        }
  method delete(line:array<char>, l:nat, at:nat, p:nat)
  requires line!=null
  requires l <= line.Length
  requires at+p <= l
  modifies line
  ensures line[..at] == old(line[..at])
  ensures line[at..l-p] == old(line[at+p..l])
{
  var i:nat := 0;
  while(i < l-(at+p))
    invariant i <= l-(at+p)
    invariant at+p+i >= at+i 
    invariant line[..at] == old(line[..at])
    invariant line[at..at+i] == old(line[at+p..at+p+i])
    invariant line[at+i..l] == old(line[at+i..l]) // future is untouched
  { 
    line[at+i] := line[at+p+i];
    i := i+1;
  }
}

person pmpc    schedule 20.04.2016    source источник


Ответы (1)


functions в Dafny являются чистыми, индуктивно определенными и используют синтаксис, отличный от императивного methods. Вы не можете использовать императивные функции языка внутри функции. В этом случае вам не разрешено использовать:

  • Условный оператор if cond { s1* } else { s2* }

  • Оператор цикла while cond { s1* }

Вместо этого тело функции должно быть выражением:

predicate checkIfEqual(pat:array<char>, dst:array<char>)
  requires pat!=null && dst!=null;
  reads pat;
  reads dst;
{
     pat.Length == dst.Length 
  && forall i:nat :: i < pat.Length ==> pat[i] == dst[i]
}

Хотя здесь это не нужно, у Дафни есть условное выражение (ите):

predicate checkIfEqual(pat:array<char>, dst:array<char>)
  requires pat!=null && dst!=null;
  reads pat;
  reads dst;
{
  if pat.Length != dst.Length then false 
  else forall i:nat :: i < pat.Length ==> pat[i] == dst[i]
}

Обратите внимание, что:

  • Вы не можете поместить цикл в тело функции, но вы можете использовать рекурсию

  • predicate — это сокращение для function, которое возвращает bool.

person lexicalscope    schedule 22.04.2016