Семантика преобразователя предикатов

Семантика преобразователя предикатов была представлена ​​Эдсгером Дейкстра в его основополагающей статье «Защищено команды, неопределенность и формальное происхождение программ ". Они определяют семантику парадигмы императивного программирования , присваивая каждому оператору на этом языке соответствующий преобразователь предикатов: итоговую функцию между двумя предикатами в пространстве состояний. заявления. В этом смысле семантика преобразователя предикатов является разновидностью денотационной семантики. Фактически, в защищенных командах Дейкстра использует только один вид преобразователя предикатов: хорошо известные самые слабые предусловия (см. Ниже).

Более того, семантика преобразователя предикатов - это переформулировка логики Флойда – Хоара. В то время как логика Хоара представлена ​​как дедуктивная система, семантика преобразователя предикатов (либо слабыми-предусловиями, либо сильнейшими-постусловиями см. Ниже) завершена стратегии для построения правильных выводов логики Хоара. Другими словами, они предоставляют эффективный алгоритм для сведения проблемы проверки тройки Хоара к проблеме доказательства формулы первого порядка. Технически семантика преобразователя предикатов выполняет своего рода символическое выполнение операторов в предикаты: выполнение выполняется в обратном направлении в случае самых слабых предварительных условий или вперед в случае сильных постусловий.

• 1 Наименьшие предварительные условия
  • 1.1 Определение
  • 1.2 Пропустить
  • 1.3 Прерывание
  • 1.4 Присвоение
  • 1.5 Последовательность
  • 1.6 Условное
  • 1.7 Цикл while
    • 1.7.1 Частичная правильность
    • 1.7.2 Полная корректность
  • 1.8 Недетерминированные защищенные команды
    • 1.8.1 Выбор
    • 1.8.2 Повторение
  • 1.9 Заявление спецификации (или самое слабое предварительное условие вызова процедуры)
• 2 Другие преобразователи предикатов
  • 2.1 Наименьшее либеральное предусловие
  • 2.2 Самое сильное постусловие
  • 2.3 Преобразователи предикатов Win и sin
• 3 Свойства преобразователей предикатов
  • 3.1 Монотонный
  • 3.2 Строгий
  • 3.3 Завершение
  • 3.4 Конъюнктив
  • 3.5 Дизъюнктив
• 4 Приложения
• 5 За пределами преобразователей предикатов
  • 5.1 Самые слабые предусловия и самые сильные постусловия императивных выражений
  • 5.2 Вероятностные преобразователи предикатов
• 6 См. Также
• 7 Примечания
• 8 Ссылки

Определение

Для оператора S и постусловия R, a самое слабое предусловие - это предикат Q такой, что для любого предусловия $P\; \{\backslash \; displaystyle\; P\}$, $\{P\}\; S\; \{R\}\; \{\backslash \; displaystyle\; \backslash \; \{P\; \backslash \}\; S\; \backslash \; \{R\; \backslash \}\}$тогда и только тогда, когда $P\; \Rightarrow \; Q\; \{\backslash \; displaystyle\; P\; \backslash \; Rightarrow\; Q\}$. Уникальность легко следует из определения: если и Q, и Q 'являются самыми слабыми предусловиями, то по определению $\{Q\; \prime \}\; S\; \{R\}\; \{\backslash \; displaystyle\; \backslash \; \{Q\text{'}\; \backslash \}\; S\; \backslash \; \{R\; \backslash \}\}$так $Q\; \text{'}\Rightarrow \; Q\; \{\backslash \; displaystyle\; Q\text{'}\; \backslash \; Rightarrow\; Q\}$и $\{Q\}\; S\; \{R\}\; \{\backslash \; displaystyle\; \backslash \; \{Q\; \backslash \}\; S\; \backslash \; \{R\; \backslash \}\}$поэтому $Q\; \Rightarrow \; Q\; \prime \; \{\backslash \; displaystyle\; Q\; \backslash \; Rightarrow\; Q\; \text{'}\}$, и, следовательно, $Q\; =\; Q\; \prime \; \{\backslash \; displaystyle\; Q\; =\; Q\text{'}\}$. Обозначим $wp\; (S,\; R)\; \{\backslash \; displaystyle\; wp\; (S,\; R)\}$самое слабое предусловие для оператора S и постусловия R.

Skip

$wp\; (skip,\; R)\; =\; R\; \{\backslash \; displaystyle\; wp\; (\{\backslash \; textbf\; \{skip\}\},\; R)\; \backslash \; =\; \backslash \; R\}$

Abort

$wp\; (abort,\; R)\; =\; false\; \{\backslash \; displaystyle\; wp\; (\{\backslash \; textbf\; \{abort\; \}\},\; R)\; \backslash \; =\; \backslash \; \{\backslash \; textbf\; \{false\}\}\}$

Присваивание

Ниже мы приводим два эквивалентных самых слабых предварительных условия для оператора присваивания. В этих формулах $R\; [x\; \leftarrow \; E]\; \{\backslash \; displaystyle\; R\; [x\; \backslash \; leftarrow\; E]\}$является копией R, где свободные вхождения x заменены на E Следовательно, здесь выражение E неявно приводится к допустимому термину базовой логики: таким образом, это чистое выражение, полностью определенное, завершающееся и без побочных эффектов.

• версия 1:

$wp\; (x:\; =\; E,\; R)\; =\; \forall \; y,\; y\; =\; E\; \Rightarrow \; R\; [x\; \leftarrow \; y]\; \{\backslash \; displaystyle\; wp\; (x:\; =\; E,\; R)\; \backslash \; =\; \backslash \; \backslash \; forall\; y,\; y\; =\; E\; \backslash \; Rightarrow\; R\; [x\; \backslash \; leftarrow\; y]\}$ где y - новая переменная (представляющая окончательное значение переменной x)

• версия 2:

$wp\; (x:\; =\; E,\; R)\; =\; R\; [x\; \leftarrow \; E]\; \{\backslash \; displaystyle\; wp\; (x:\; =\; E,\; R)\; \backslash \; =\; \backslash \; R\; [x\; \backslash \; leftarrow\; E]\}$

Первая версия избегает потенциального дублирования E в R, тогда как вторая версия проще, когда x встречается не более одного раза в R. Первая версия также обнаруживает глубокую двойственность между самым слабым предусловием и самым сильным постусловием (см. ниже).

Пример правильного вычисления wp (с использованием версии 2) для присвоений с целочисленной переменной x:

$wp\; (x:\; =\; x\; -\; 5,\; x>10)\; =\; x\; -\; 5>10\; \iff \; Икс>15\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{array\}\; \{rcl\}\; wp\; (x:\; =\; x-5,\; x>10)\; =\; x-5>10\; \backslash \backslash \; \backslash \; Leftrightarrow\; x>15\; \backslash \; end\; \{array\}\}\; \}$

Это означает, что для того, чтобы постусловие x>10 было истинным после присвоения, предварительное условие x>15 должно быть истинным. перед присваиванием. Это также «самое слабое предусловие», так как это «самое слабое» ограничение на значение x, которое делает x>10 истинным после присваивания.

Последовательность

$wp\; (S\; 1;\; S\; 2,\; R)\; =\; wp\; (S\; 1,\; wp\; (S\; 2,\; R))\; \{\backslash \; displaystyle\; wp\; (S\_\; \{1\};\; S\_\; \{2\},\; R)\; \backslash \; =\; \backslash \; wp\; (S\_\; \{1\},\; wp\; (\; S\_\; \{2\},\; R))\}$

Например,

$wp\; (x:\; =\; x\; -\; 5;\; x:\; =\; x\; \ast \; 2,\; x>20)\; =\; wp\; (x:\; =\; x\; -\; 5,\; wp\; (\; х:\; =\; х\; *\; 2,\; x>20))\; =\; wp\; (x:\; =\; x\; -\; 5,\; x\; \ast \; 2>20)\; =\; (x\; -\; 5)\; \ast \; 2>20\; =\; x>15\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{rcl\}\; wp\; (x:\; =\; x-5;\; x:\; =\; x\; *\; 2\; \backslash ,\; \backslash \; x>20)\; =\; wp\; (x:\; =\; x-5,\; wp\; (x:\; =\; x\; *\; 2,\; x>20))\; \backslash \backslash \; =\; wp\; (x:\; =\; x-5,\; x\; *\; 2>20)\; \backslash \backslash \; =\; (x-5)\; *\; 2>20\; \backslash \backslash \; =\; x>15\; \backslash \; end\; \{array\}\}$

Условный

$wp\; (если\; E,\; то\; S\; 1,\; иначе\; S\; 2\; end,\; R)\; =\; (E\; \Rightarrow \; wp\; (S\; 1,\; R))\; \wedge \; (\neg \; E\; \Rightarrow \; wp\; (S\; 2,\; R))\; \{\backslash \; displaystyle\; wp\; (\{\backslash \; textbf\; \{if\}\}\; \backslash \; E\; \backslash \; \{\backslash \; textbf\; \{then\}\}\; \backslash \; S\_\; \{1\}\; \backslash \; \{\backslash \; textbf\; \{else\}\}\; \backslash \; S\_\; \{2\}\; \backslash \; \{\backslash \; textbf\; \{end\}\},\; R)\; \backslash \; =\; \backslash \; (E\; \backslash \; Rightarrow\; wp\; (S\_\; \{1\},\; R))\; \backslash \; wedge\; (\backslash \; neg\; E\; \backslash \; Rightarrow\; wp\; (S\_\; \{2\},\; R))\}$

Как пример:

while loop

Partial Correctness

Игнорируя завершение на мгновение, мы можем определить правило для самого слабого либерального предусловия, обозначенного wlp, используя предикат I, называемый циклом в вариант, обычно предоставляется программистом:

$wlp\; (в\; то\; время\; как\; E\; do\; S\; done,\; R)\; =\; I\; \wedge \; \forall \; y,\; ((E\; \wedge \; I)\; \Rightarrow \; wlp\; (S,\; I))\; [x\; \leftarrow \; y]\; \wedge \; \forall \; Y,\; ((\neg \; E\; \wedge \; I)\; \Rightarrow \; R)\; [x\; \leftarrow \; y]\; \{\backslash \; displaystyle\; wlp\; (\{\backslash \; textbf\; \{while\}\}\; \backslash \; E\; \backslash \; \{\backslash \; textbf\; \{do\}\}\; \backslash \; S\; \backslash \; \{\backslash \; textbf\; \{done\}\},\; R)\; \backslash \; =\; \backslash \; \{\backslash \; begin\; \{array\}\; \{l\}\; I\; \backslash \backslash \backslash \; wedge\; \backslash \; \backslash \; forall\; y,\; ((E\; \backslash \; wedge\; I)\; \backslash \; Rightarrow\; wlp\; (S,\; I))\; [x\; \backslash \; leftarrow\; y]\; \backslash \backslash \backslash \; wedge\; \backslash \; \backslash \; forall\; y,\; ((\backslash \; neg\; E\; \backslash \; wedge\; I)\; \backslash \; Rightarrow\; R)\; [x\; \backslash \; leftarrow\; y]\; \backslash \; end\; \{array\}\}\}$

Это просто утверждает, что (1) инвариант должен удерживаться в начале петля; (2) кроме того, для любого начального состояния y инвариант и защита, вместе взятые, должны быть достаточно сильными, чтобы установить самое слабое предварительное условие, необходимое для того, чтобы тело цикла могло восстановить инвариант; (3) наконец, если и когда цикл завершается в заданном состоянии y, тот факт, что защита цикла ложна вместе с инвариантом, должен иметь возможность установить требуемое постусловие.

Полная корректность

Чтобы показать полную корректность, мы также должны показать, что цикл завершается. Для этого мы определяем обоснованное отношение в пространстве состояний, обозначенное «<" and called вариантом цикла. Следовательно, мы имеем:

, где y - свежий набор переменных

Неформально, в приведенном выше соединении трех формул:

• первая означает, что инвариант, который я должен изначально придерживаться;
• второй означает, что тело цикла (например, оператор S) должно сохранять инвариант и уменьшать вариант: здесь переменная y представляет начальное состояние выполнения тела;
• последнее означает, что R должен быть установлен в конце цикла: здесь переменная y представляет конечное состояние цикла.

В семантике преобразователей предикатов, инвариант и вариант создаются путем имитации Теорема Клини о неподвижной точке. Ниже эта конструкция в общих чертах описана в теории множеств. Мы предполагаем, что U - это множество, обозначающее пространство состояний. Сначала мы определяем семейство подмножеств U, обозначенное $(A\; k)\; k\; \in \; N\; \{\backslash \; displaystyle\; (A\_\; \{k\})\; \_\; \{k\; \backslash \; in\; \backslash \; mathbb\; \{N\}\}\}$индукцией по натуральному числу k. Неформально $A\; k\; \{\backslash \; displaystyle\; A\_\; \{k\}\}$представляет набор начальных состояний, которые удовлетворяют R после менее чем k итераций цикла:

$A\; 0\; =\; \varnothing \; A\; k\; +\; 1\; =\; \{y\; \in \; U\; |\; ((E\; \Rightarrow \; wp\; (S,\; x\; \in \; A\; k))\; \wedge \; (\neg \; E\; \Rightarrow \; R))\; [x\; \leftarrow \; y]\}\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{rcl\}\; A\_\; \{0\}\; =\; \backslash \; emptyset\; \backslash \; \backslash \; A\_\; \{k\; +\; 1\}\; =\; \backslash \; left\; \backslash \; \{\backslash \; y\; \backslash \; in\; U\; \backslash \; |\; \backslash \; ((E\; \backslash \; Rightarrow\; wp\; (S,\; x\; \backslash \; in\; A\_\; \{k\}))\; \backslash \; wedge\; (\backslash \; neg\; E\; \backslash \; Rightarrow\; R))\; [x\; \backslash \; leftarrow\; y]\; \backslash \; \backslash \; right\; \backslash \}\; \backslash \backslash \backslash \; end\; \{array\}\}\}$

Затем мы определяем:

• инвариант I как предикат $\exists \; k,\; x\; \in \; A\; k\; \{\backslash \; displaystyle\; \backslash \; существует\; k,\; x\; \backslash \; в\; A\_\; \{k\}\}$.
• варианте как предложение

С этими определениями, $wp\; (пока\; E\; do\; S\; готово,\; R)\; \{\backslash \; displaystyle\; wp\; (\{\backslash \; textbf\; \{while\}\}\; \backslash \; E\; \backslash \; \{\backslash \; textbf\; \{do\}\}\; \backslash \; S\; \backslash \; \{\backslash \; textbf\; \{done\}\},\; R)\}$сводится к формуле $\exists \; k,\; x\; \in \; A\; k\; \{\backslash \; displaystyle\; \backslash \; exists\; k,\; x\; \backslash \; in\; A\_\; \{k\}\}$.

Однако на практике такая абстрактная конструкция не может быть эффективно обработана с помощью Средства доказательства теорем. Следовательно, инварианты и варианты цикла предоставляются пользователями или выводятся с помощью некоторой абстрактной интерпретации процедуры.

Недетерминированные охраняемые команды

Фактически, Дейкстры Охраняемая команда L anguage (GCL) - это расширение простого императивного языка, данного до сих пор, с недетерминированными операторами. Действительно, GCL стремится быть формальной записью для определения алгоритмов. Недетерминированные операторы представляют собой выбор, оставленный фактической реализации (на эффективном языке программирования): свойства, доказанные на недетерминированных операторах, гарантируются для всех возможных вариантов реализации. Другими словами, самые слабые предварительные условия недетерминированных операторов гарантируют

• , что существует завершающее выполнение (например, существует реализация),
• и что конечное состояние всего завершающего выполнения удовлетворяет постусловию.

Обратите внимание на то, что приведенные выше определения самого слабого предусловия (в частности, для while-loop ) сохраняют это свойство.

Выбор

Выбор является обобщением оператора if :

$wp\; (if\; E\; 1\; \to \; S\; 1\; []\dots \; []\; E\; n\; \to \; S\; nfi,\; R)\; =\; (E\; 1\; \vee \dots \; \vee \; E\; n)\; \wedge \; (E\; 1\; \Rightarrow \; wp\; (S\; 1,\; R))\dots \; \wedge \; (E\; n\; \Rightarrow \; wp\; (S\; n,\; R))\; \{\backslash \; displaystyle\; wp\; (\backslash \; mathbf\; \{if\}\; \backslash \; E\_\; \{1\}\; \backslash \; rightarrow\; S\_\; \{1\}\; \backslash \; [\backslash !]\; \backslash \; \backslash \; Ldots\; \backslash \; [\backslash !]\; \backslash \; E\_\; \{n\}\; \backslash \; rightarrow\; S\_\; \{n\}\; \backslash \; \backslash \; mathbf\; \{fi\},\; R)\; \backslash \; =\; \{\backslash \; begin\; \{array\}\; \{l\}\; (E\_\; \{1\}\; \backslash \; vee\; \backslash \; ldots\; \backslash \; vee\; E\_\; \{n\})\; \backslash \backslash \backslash \; клин\; \backslash \; (E\_\; \{1\}\; \backslash \; Rightarrow\; wp\; (S\_\; \{1\},\; R))\; \backslash \backslash \backslash \; ldots\; \backslash \backslash \backslash \; клин\; \backslash \; (E\_\; \{n\}\; \backslash \; Rightarrow\; wp\; (S\_\; \{n\},\; R))\; \backslash \backslash \backslash \; end\; \{array\}\}\}$

Здесь, когда два охранника $E\; i\; \{\backslash \; displaystyle\; E\_\; \{i\}\}$и $E\; j\; \{\backslash \; displaystyle\; E\_\; \{j\}\}$одновременно истинны, тогда выполнение этого оператора может запускать любой из связанных операторов $S\; i\; \{\backslash \; displaystyle\; S\_\; \{i\; \}\}$или $S\; j\; \{\backslash \; displaystyle\; S\_\; \{j\}\}$.

Повторение

Повторение - это аналогичное обобщение оператора while .

Оператор спецификации (или самое слабое предварительное условие вызова процедуры)

Исчисление уточнения расширяет недетерминированные операторы понятием оператора спецификации. Неформально этот оператор представляет собой вызов процедуры в черном ящике, где тело процедуры неизвестно. Обычно при использовании синтаксиса, близкого к B-методу, оператор спецификации записывается как

$P\; |\; \{\backslash \; displaystyle\; P\; \backslash \; |\}$@$у.\; Q\; \to \; x:\; =\; y\; \{\backslash \; displaystyle\; y.\; \backslash \; Q\; \backslash \; rightarrow\; x:\; =\; y\}$

где

• x - глобальная переменная, измененная оператором,
• P - предикат, представляющий предварительное условие,
• y - это новая логическая переменная, связанная в Q, которая представляет новое значение x, недетерминированно выбранное оператором,
• Q - предикат, представляющий постусловие, или, точнее, охранник: в Q переменная x представляет начальное состояние, а y обозначает конечное состояние.

Самым слабым предварительным условием инструкции спецификации является:

$wp\; (P\; |\; \{\backslash \; displaystyle\; wp\; (P\; \backslash \; |\}$@$y.\; Q\; \to \; x:\; =\; y,\; R)\; =\; P\; \wedge \; \forall \; z,\; Q\; [y\; \leftarrow \; z]\; \Rightarrow \; R\; [x\; \leftarrow \; z]\; \{\backslash \; displaystyle\; y.\; \backslash \; Q\; \backslash \; rightarrow\; x:\; =\; y\; \backslash ,\; \backslash \; R)\; \backslash \; =\; \backslash \; P\; \backslash \; wedge\; \backslash \; forall\; z,\; Q\; [y\; \backslash \; leftarrow\; z]\; \backslash \; Rightarrow\; R\; [x\; \backslash \; leftarrow\; z]\}$ где z - новое имя

Кроме того, оператор S реализует такой оператор спецификации тогда и только тогда, когда следующий предикат является тавтологией:

$\forall \; x\; 0,\; (P\; \Rightarrow \; wp\; (S,\; Q\; [x\; \leftarrow \; x\; 0]\; [y\; \leftarrow \; x]))\; [x\; \leftarrow \; x\; 0]\; \{\backslash \; displayst\; yle\; \backslash \; forall\; x\_\; \{0\},\; (P\; \backslash \; Rightarrow\; wp\; (S,\; Q\; [x\; \backslash \; leftarrow\; x\_\; \{0\}]\; [y\; \backslash \; leftarrow\; x]))\; [x\; \backslash \; leftarrow\; x\_\; \{0\}]\}$ где $x\; 0\; \{\backslash \; displaystyle\; x\_\; \{0\}\}$- новое имя (обозначающее начальное состояние)

Действительно, в таком случае для всех постусловий R обеспечивается следующее свойство (это прямое следствие монотонности wp, см. ниже):

$wp\; (P\; |\; \{\backslash \; displaystyle\; wp\; (P\; \backslash \; |\}$@$y.\; Q\; \to \; x:\; =\; y,\; R)\; \Rightarrow \; wp\; (S,\; R)\; \{\backslash \; displaystyle\; y.\; \backslash \; Q\; \backslash \; rightarrow\; x:\; =\; y\; \backslash ,\; \backslash \; R)\; \backslash \; Rightarrow\; wp\; (S,\; R)\}$

Неформально, это последнее свойство гарантирует, что любое доказательство некоторого оператора, включающего спецификацию, остается действительным при замене этой спецификации любой из ее реализаций.

Наименьшее либеральное предусловие

Важным вариантом самого слабого предусловия является самое слабое либеральное предусловие $wlp\; (S,\; R)\; \{\backslash \; displaystyle\; wlp\; (S,\; R)\}$, что дает самое слабое условие, при котором S либо не завершается, либо устанавливает R. Следовательно, он отличается от wp тем, что не гарантирует завершения. Следовательно, он частично соответствует логике Хоара : для языка операторов, приведенного выше, wlp отличается от wp только на while-loop, не требуя варианта (см. Выше).

Сильнейшее постусловие

Если S - оператор и R - предусловие (предикат начального состояния), то $sp\; (S,\; R)\; \{\backslash \; displaystyle\; sp\; (S,\; R)\}$является их самым сильным постусловием : оно подразумевает любое постусловие, удовлетворяемое конечным состоянием любого выполнения S, для любого начального состояния, удовлетворяющего R. Другими словами, тройка Хоара $\{P\}\; S\; \{Q\}\; \{\backslash \; displaystyle\; \backslash \; \{P\; \backslash \}\; S\; \backslash \; \{Q\; \backslash \}\}$доказуема в логике Хора тогда и только тогда, когда выполняется следующий предикат:

$\forall \; x,\; sp\; (S,\; P)\; \Rightarrow \; Q\; \{\backslash \; displaystyle\; \backslash \; forall\; x,\; sp\; (S,\; P)\; \backslash \; Rightarrow\; Q\}$

Обычно сильнейшие постусловия используются для частичной корректности. Следовательно, мы имеем следующую связь между самыми слабыми-либеральными-предусловиями и самыми сильными-постусловиями:

$(\forall \; x,\; P\; \Rightarrow \; wlp\; (S,\; Q))\; \iff \; (\forall \; x,\; sp\; (S,\; P)\; \Rightarrow \; Q)\; \{\backslash \; displaystyle\; (\backslash \; forall\; x,\; P\; \backslash \; Rightarrow\; wlp\; (S,\; Q))\; \backslash \; \backslash \; Leftrightarrow\; \backslash \; (\backslash \; forall\; x,\; sp\; (S,\; P)\; \backslash \; Rightarrow\; Q)\}$

Например, при назначении мы имеем:

$sp\; (Икс:\; =\; E,\; R)\; знак\; равно\; \exists \; Y,\; x\; =\; E\; [x\; \leftarrow \; y]\; \wedge \; R\; [x\; \leftarrow \; y]\; \{\backslash \; displaystyle\; sp\; (x:\; =\; E,\; R)\; \backslash \; =\; \backslash \; \backslash \; существует\; y,\; x\; =\; E\; [x\; \backslash \; leftarrow\; y]\; \backslash \; wedge\; R\; [x\; \backslash \; leftarrow\; y]\}$ где y свежий

Выше логическая переменная y представляет начальное значение переменной x. Следовательно,

$sp\; (x:\; =\; x\; -\; 5,\; x>15)\; =\; \exists \; y,\; x\; =\; y\; -\; 5\; \wedge \; y>15\; \iff \; x>10\; \{\backslash \; displaystyle\; sp\; (x:\; =\; x-5,\; x>15)\; \backslash \; =\; \backslash \; \backslash \; существует\; y,\; x\; =\; y-5\; \backslash \; wedge\; y>15\; \backslash \; \backslash \; Leftrightarrow\; \backslash \; x>10\}$

В последовательности оказывается, что sp бежит вперед (тогда как wp - назад):

$sp\; (S\; 1;\; S\; 2,\; R)\; =\; sp\; (S\; 2,\; sp\; (S\; 1,\; R))\; \{\backslash \; displaystyle\; sp\; (\; S\_\; \{1\};\; S\_\; \{2\}\; \backslash ,\; \backslash \; R)\; \backslash \; =\; \backslash \; sp\; (S\_\; \{2\},\; sp\; (S\_\; \{1\},\; R))\}$

Преобразователи предикатов Win и sin

Лесли Лэмпорт предложил win и sin в качестве преобразователей предикатов для параллельного программирования.

В этом разделе представлены некоторые характерные свойства преобразователей предикатов. Ниже T обозначает преобразователь предикатов (функция между двумя предикатами на пространстве состояний), а P - предикат. Например, T (P) может обозначать wp (S, P) или sp (S, P). Мы сохраняем x как переменную пространства состояний.

Монотонный

Представляющие интерес преобразователи предикатов (wp, wlp и sp) являются монотонными. Преобразователь предикатов T является монотонным тогда и только тогда, когда:

$(\forall \; x,\; P\; \Rightarrow \; Q)\; \Rightarrow \; (\forall \; x,\; T\; (P)\; \Rightarrow \; T\; (Q))\; \{\backslash \; displaystyle\; (\backslash \; forall\; x,\; P\; \backslash \; Rightarrow\; Q)\; \backslash \; Rightarrow\; (\backslash \; forall\; x,\; T\; (P)\; \backslash \; Rightarrow\; T\; (Q))\}$

Это свойство связано с правилом следствия логики Хоара.

Строгий

Преобразователь предикатов T является строгим iff:

$T\; (false)\; \iff \; false\; \{\backslash \; displaystyle\; T\; (\backslash \; mathbf\; \{false\})\; \backslash \; \backslash \; Leftrightarrow\; \backslash \; \backslash \; mathbf\; \{false\}\}$

Для Например, wp является строгим, тогда как wlp обычно нет. В частности, если оператор S не может завершиться, то $w\; l\; p\; (S,\; f\; a\; l\; s\; e)\; \{\backslash \; displaystyle\; wlp\; (S,\; \backslash \; mathbf\; \{false\})\}$является выполнимым. У нас есть

$wlp\; (whiletruedoskipdone,\; false)\; \iff \; true\; \{\backslash \; displaystyle\; wlp\; (\backslash \; mathbf\; \{while\}\; \backslash \; \backslash \; mathbf\; \{true\}\; \backslash \; \backslash \; mathbf\; \{do\}\; \backslash \; \backslash \; mathbf\; \{skip\}\; \backslash \; \backslash \; mathbf\; \{done\},\; \backslash \; mathbf\; \{false\})\; \backslash \; \backslash \; Leftrightarrow\; \backslash \; mathbf\; \{true\}\}$

Действительно, true является допустимым инвариантом этого цикла.

Завершение

Преобразователь предикатов T завершение iff:

$T\; (true)\; \iff \; true\; \{\backslash \; displaystyle\; T\; (\backslash \; mathbf\; \{true\})\; \backslash \; \backslash \; Leftrightarrow\; \backslash \; \backslash \; mathbf\; \{true\}\}$

Фактически, эта терминология имеет смысл только для строгих преобразователей предикатов: действительно, $wp\; (S,\; true)\; \{\backslash \; displaystyle\; wp\; (S,\; \backslash \; mathbf\; \{true\})\}$является самым слабым предварительным условием, обеспечивающим прекращение S.

Похоже, что наименование этого свойства без прерывания было бы более подходящим: в полной правильности, непрекращение - это аборт, тогда как в частичной правильности это не так.

Конъюнктив

Преобразователь предиката T является конъюнктивом тогда и только тогда, когда:

$T\; (P\; \wedge \; Q)\; \iff \; (T\; (P)\; \wedge \; T\; (Q))\; \{\backslash \; displaystyle\; T\; (P\; \backslash \; wedge\; Q)\; \backslash \; \backslash \; Leftrightarrow\; \backslash \; (T\; (P)\; \backslash \; wedge\; T\; (Q))\}$

Это относится к $wp\; (S,.)\; \{\backslash \; displaystyle\; wp\; (S,.)\}$, даже если оператор S недетерминирован как оператор выбора или оператор спецификации.

Дизъюнктивный

Преобразователь предикатов T является дизъюнктивным тогда и только тогда, когда:

$T\; (P\; \vee \; Q)\; \iff \; (T\; (P)\; \vee \; T\; (Q))\; \{\backslash \; displaystyle\; T\; (P\; \backslash \; vee\; Q)\; \backslash \; \backslash \; Leftrightarrow\; \backslash \; (T\; (P)\; \backslash \; vee\; T\; (Q))\}$

Обычно это не относится к $wp\; (S,.)\; \{\backslash \; displaystyle\; wp\; (S,.)\}$, когда S недетерминировано. В самом деле, рассмотрим недетерминированный оператор S, выбирающий произвольное логическое значение. Этот оператор представлен здесь как следующий оператор выбора:

$S\; =\; iftrue\; \to \; x:\; =\; 0\; []\; true\; \to \; x:\; =\; 1\; fi\; \{\backslash \; displaystyle\; S\; \backslash \; =\; \backslash \; \backslash \; mathbf\; \{if\}\; \backslash \; \backslash \; mathbf\; \{true\}\; \backslash \; rightarrow\; x:\; =\; 0\; \backslash \; [\backslash !]\; \backslash \; \backslash \; mathbf\; \{true\}\; \backslash \; rightarrow\; x:\; =\; 1\; \backslash \; mathbf\; \{fi\}\}$

Затем $wp\; (S,\; R)\; \{\backslash \; displaystyle\; wp\; (S,\; R)\}$сводится к формуле $R\; [x\; \leftarrow \; 0]\; \wedge \; R\; [x\; \leftarrow \; 1]\; \{\backslash \; displaystyle\; R\; [x\; \backslash \; leftarrow\; 0]\; \backslash \; wedge\; R\; [x\; \backslash \; leftarrow\; 1]\}$.

Следовательно, $wp\; (S,\; x\; =\; 0\; \vee \; x\; =\; 1)\; \{\backslash \; displaystyle\; wp\; (S,\; \backslash \; x\; =\; 0\; \backslash \; vee\; x\; =\; 1)\}$сводится к тавтологии $(0\; знак\; равно\; 0\; \vee \; 0\; знак\; равно\; 1)\; \wedge \; (1\; знак\; равно\; 0\; \vee \; 1\; =\; 1)\; \{\backslash \; Displaystyle\; (0\; =\; 0\; \backslash \; vee\; 0\; =\; 1)\; \backslash \; клин\; (1\; =\; 0\; \backslash \; vee\; 1\; =\; 1)\}$

Принимая во внимание, что формула $wp\; (S,\; x\; =\; 0)\; \vee \; wp\; (S,\; x\; =\; 1)\; \{\backslash \; displaystyle\; wp\; (S,\; x\; =\; 0)\; \backslash \; vee\; wp\; (S,\; x\; =\; 1)\}$сводится к неверному утверждению $(0\; =\; 0\; \wedge \; 1\; =\; 0)\; \vee \; (1\; =\; 0\; \wedge \; 1\; =\; 1)\; \{\backslash \; displaystyle\; (0\; =\; 0\; \backslash \; wedge\; 1\; =\; 0)\; \backslash \; vee\; (1\; =\; 0\; \backslash \; wedge\; 1\; =\; 1)\}$.

Тот же контрпример можно воспроизвести, используя вместо этого оператор спецификации (см. Выше):

$S\; =\; true\; |\; \{\backslash \; Displaystyle\; S\; \backslash \; =\; \backslash \; \backslash \; mathbf\; \{true\}\; \backslash \; |\}$@$у.\; y\; \in \; \{0,\; 1\}\; \to \; x:\; =\; y\; \{\backslash \; displaystyle\; y.\; \backslash \; y\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; \backslash \; rightarrow\; x:\; =\; y\}$

• В основном используются вычисления самых слабых предварительных условий для статической проверки утверждений в программах с помощью средства доказательства теорем (например, SMT-решателей или помощников по доказательству ): см. Frama-C или ESC / Java2.
• В отличие от многих других семантических формализмов, семантика преобразователя предикатов не разрабатывалась как исследование основ вычислений. Скорее, он был предназначен для того, чтобы предоставить программистам методологию разработки своих программ как «правильных по построению» в «стиле вычислений». Этот «нисходящий» стиль пропагандировали Дейкстра и Н. Вирт. Он был формализован Р.-Дж. Вернемся к и другим в исчислении уточнения. Некоторые инструменты, такие как B-Method, теперь предоставляют автоматизированное рассуждение для продвижения этой методологии.
• В мета-теории логики Хоара, самые слабые предварительные условия появляются как ключевое понятие в доказательстве относительной полноты.

Самые слабые предварительные условия и самые сильные постусловия императивных выражений

В семантике преобразователей предикатов, выражения ограничены терминами логики (см. выше). Однако это ограничение кажется слишком сильным для большинства существующих языков программирования, где выражения могут иметь побочные эффекты (вызов функции, имеющей побочный эффект), не могут завершаться или прерваться (например, деление на ноль). Есть много предложений по расширению самых слабых предусловий или сильнейших постусловий для императивных языков выражения и, в частности, для монад.

Среди них теория типов Хоара объединяет логику Хора для Haskell -подобный язык, логика разделения и теория типов. Эта система в настоящее время реализована как библиотека Coq с именем Ynot . В этом языке оценка выражений соответствует вычислению самых сильных постусловий.

Вероятностные преобразователи предикатов

Вероятностные преобразователи предикатов - это расширение преобразователей предикатов для вероятностных программ. Действительно, такие программы имеют множество приложений в криптографии (сокрытие информации с помощью некоторого рандомизированного шума), распределенных системах (нарушение симметрии).

• Аксиоматическая семантика - включает семантику преобразователя предикатов
• Динамическая логика - где преобразователи предикатов отображаются как модальности
• Формальная семантика языков программирования - обзор