Последовательность TLA + не обновляется вызовами Append или Tail - PullRequest
Новая
       60

Последовательность TLA + не обновляется вызовами Append или Tail

0 голосов
/ 07 января 2019

Проблема

Я играю с TLA + и думал, что напишу следующую явно ложную спецификацию в PlusCal: 

---- MODULE transfer ----
EXTENDS Naturals, TLC, Sequences

(* --algorithm transfer

\* Simple algorithm:
\*  1. Start with a shared-memory list with one element.
\*  2. A process adds arbitrary numbers of elements to the list.
\*  3. Another process removes arbitrary numbers of elements from the list, 
\*     but only if the list has more than one item in it. This check is 
\*     applied just before trying to removing an element. 
\* Is it true that the list will always have a length of 1? 
\* You would expect this to be false, since the adder process can add more elements 
\* than the remover process can consume.

variables stack = <<0>>

process Adder = 0
  begin
      AddElement:
        stack := Append(stack, Len(stack));
        either goto AddElement
        or skip
        end either;
end process;

process Remover = 1
  begin
      RemoveElement:
        \* Pop from the front of the stack
        if Len(stack) > 1 then
            stack := Tail(stack);
        end if;
        either goto RemoveElement
        or skip
        end either;
end process;

end algorithm *)

IsStackAlwaysUnitLength == Len(stack) = 1

====

После проверки IsStackAlwaysUnitLength как одного из временных свойств для отчета я ожидал, что TLA + пометит это свойство как невыполненное.

Однако все состояния пройдены! Почему не выходит из строя?

Попытки отладки

При отладке с помощью операторов print я заметил следующее странное поведение: 

process Adder = 0
  begin
      AddElement:
        print stack;
        print "Adder applied!";
        stack := Append(stack, Len(stack));
        print stack;
        print "Adder task complete!";
        \* Force 
        either goto AddElement
        or skip
        end either;
end process;

process Remover = 1
  begin
      RemoveElement:
        \* Pop from the front of the stack
        print stack;
        print "Remover applied!";
        if Len(stack) > 1 then
            stack := Tail(stack);
            print stack;
            print "Remover task complete!";
        else
            print "Remover task complete!";
        end if;
        either goto RemoveElement
        or skip
        end either;
end process;

выходы в панели отладки 

<<0>>
"Adder applied!"
<<0>>
"Adder task complete!"
<<0>>
<<0>>
"Remover applied!"
"Remover applied!"
"Remover task complete!"
"Remover task complete!"
<<0>>
"Adder applied!"
<<0>>
"Adder task complete!"

Я не уверен, почему stack := Append(stack, Len(stack)); и stack := Tail(stack); не обновляют глобальную переменную stack.

Создана полная спецификация TLA 

---- MODULE transfer ----
EXTENDS Naturals, TLC, Sequences

(* --algorithm transfer

variables stack = <<0>>

process Adder = 0
  begin
      AddElement:
        stack := Append(stack, Len(stack));
        either goto AddElement
        or skip
        end either;
end process;

process Remover = 1
  begin
      RemoveElement:
        \* Pop from the front of the stack
        if Len(stack) > 1 then
            stack := Tail(stack);
        end if;
        either goto RemoveElement
        or skip
        end either;
end process;

end algorithm *)
\* BEGIN TRANSLATION
VARIABLES stack, pc

vars == << stack, pc >>

ProcSet == {0} \cup {1}

Init == (* Global variables *)
        /\ stack = <<0>>
        /\ pc = [self \in ProcSet |-> CASE self = 0 -> "AddElement"
                                        [] self = 1 -> "RemoveElement"]

AddElement == /\ pc[0] = "AddElement"
              /\ stack' = [stack EXCEPT ![0] = Append(stack, Len(stack))]
              /\ \/ /\ pc' = [pc EXCEPT ![0] = "AddElement"]
                 \/ /\ TRUE
                    /\ pc' = [pc EXCEPT ![0] = "Done"]

Adder == AddElement

RemoveElement == /\ pc[1] = "RemoveElement"
                 /\ IF Len(stack) > 1
                       THEN /\ stack' = [stack EXCEPT ![1] = Tail(stack)]
                       ELSE /\ TRUE
                            /\ stack' = stack
                 /\ \/ /\ pc' = [pc EXCEPT ![1] = "RemoveElement"]
                    \/ /\ TRUE
                       /\ pc' = [pc EXCEPT ![1] = "Done"]

Remover == RemoveElement

Next == Adder \/ Remover
           \/ (* Disjunct to prevent deadlock on termination *)
              ((\A self \in ProcSet: pc[self] = "Done") /\ UNCHANGED vars)

Spec == Init /\ [][Next]_vars

Termination == <>(\A self \in ProcSet: pc[self] = "Done")

\* END TRANSLATION

IsStackAlwaysUnitLength == Len(stack) = 1

====

1 Ответ

0 голосов
/ 07 января 2019

Поздравляем, вы попали в ошибку PlusCal! И также крайний случай, который не ошибка, но все еще не интуитивный. Давайте начнем с ошибки.

Иногда при использовании PlusCal мы хотим, чтобы несколько процессов совместно использовали метки. Мы делаем это с помощью процедуры . Чтобы все это заработало, переводчик PlusCal добавляет дополнительную переменную учета, называемую stack. Обычно , если пользователь определяет переменную foo, которая конфликтует с сгенерированной переменной foo, перевод переименовывает одну в foo_. В этом случае, поскольку не было никакого конфликта, не было никакого переименования. * Ошибка в том, что переводчик запутался и перевел переменную , как будто это должна была быть бухгалтерия stack. Вы можете видеть это, поскольку это превратило приложение в 

stack' = [stack EXCEPT ![0] = Append(stack, Len(stack))]

Когда это должно быть просто 

stack' = Append(stack, Len(stack))

Вы можете исправить это, переименовав stack в mystack. Это должно привести к правильной работе спецификации. Но это все равно пройдет: это потому, что вы положили IsStackAlwaysUnitLength как свойство , а не инвариант . Как временное свойство, IsStackAlwaysUnitLength имеет значение true, если оно истинно в исходном состоянии. Как инвариант, IsStackAlwaysUnitLength истинно, если оно истинно в всех состояниях. ** Вы можете получить ошибочную спецификацию спецификации, изменив IsStackAlwaysUnitLength с временного свойства на инвариант на странице "что такое модель".

* На самом деле в этом случае переводчик не будет переименовывать stack, если вы добавите процедуру, он просто выдаст ошибку. Но это все еще безотказно.

** Это связано с тем, что TLC (средство проверки модели) обрабатывает инвариант P как временное свойство []P. Это синтаксический сахар, в основном.

...