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

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

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

Самые слабые предпосылки

Определение

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

Пропускать

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

Прервать

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

Назначение

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

• версия 1:

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

• версия 2:

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

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

Пример действительного расчета WP (с использованием версии 2) для присваиваний с целочисленной переменной Икс является:

${\displaystyle {\begin{array}{rcl}wp(x:=x-5,x>10)&=&x-5>10\\&\Leftrightarrow &x>15\end{array}}}$

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

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

${\displaystyle wp(S_{1};S_{2},R)\ =\ wp(S_{1},wp(S_{2},R))}$

Например,

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

Условный

${\displaystyle wp({\textbf {if}}\ E\ {\textbf {then}}\ S_{1}\ {\textbf {else}}\ S_{2}\ {\textbf {end}},R)\ =\ (E\Rightarrow wp(S_{1},R))\wedge (\neg E\Rightarrow wp(S_{2},R))}$

Например:

${\displaystyle {\begin{array}{rcl}wp({\textbf {if}}\ x<y\ {\textbf {then}}\ x:=y\ {\textbf {else}}\;\;{\textbf {skip}}\;\;{\textbf {end}},\ x\geq y)&=&(x<y\Rightarrow wp(x:=y,x\geq y))\ \wedge \ (\neg (x<y)\Rightarrow wp({\textbf {skip}},x\geq y))\\&=&(x<y\Rightarrow y\geq y)\ \wedge \ (\neg (x<y)\Rightarrow x\geq y)\\&\Leftrightarrow &{\textbf {true}}\end{array}}}$

Пока цикл

Частичная корректность

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

${\displaystyle wlp({\textbf {while}}\ E\ {\textbf {do}}\ S\ {\textbf {done}},R)\ =\ {\begin{array}{l}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]\end{array}}}$

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

Полная правильность

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

${\displaystyle wp({\textbf {while}}\ E\ {\textbf {do}}\ S\ {\textbf {done}},R)\ =\ {\begin{array}{l}I\\\wedge \ \forall y,((E\wedge I)\Rightarrow wp(S,I\wedge x<y))[x\leftarrow y]\\\wedge \ \forall y,((\neg E\wedge I)\Rightarrow R)[x\leftarrow y]\end{array}}}$ куда у свежий набор переменных

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

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

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

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

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

• инвариантный я как предикат ${\displaystyle \exists k,x\in A_{k}}$.
• вариант ${\displaystyle y<z}$ как предложение ${\displaystyle \exists i,y\in A_{i}\wedge (\forall j,z\in A_{j}\Rightarrow i<j)}$

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

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

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

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

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

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

Выбор

Выбор - это обобщение если утверждение:

${\displaystyle wp(\mathbf {if} \ E_{1}\rightarrow S_{1}\ [\!]\ \ldots \ [\!]\ E_{n}\rightarrow S_{n}\ \mathbf {fi} ,R)\ ={\begin{array}{l}(E_{1}\vee \ldots \vee E_{n})\\\wedge \ (E_{1}\Rightarrow wp(S_{1},R))\\\ldots \\\wedge \ (E_{n}\Rightarrow wp(S_{n},R))\\\end{array}}}$

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

Репетиция

Повторение - это обобщение пока заявление аналогичным образом.

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

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

${\displaystyle P\ |}$ @${\displaystyle y.\ Q\rightarrow x:=y}$

куда

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

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

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

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

${\displaystyle \forall x_{0},(P\Rightarrow wp(S,Q[x\leftarrow x_{0}][y\leftarrow x]))[x\leftarrow x_{0}]}$ куда ${\displaystyle x_{0}}$ это новое имя (обозначающее начальное состояние)

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

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

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

Другие преобразователи предикатов

Самая слабая либеральная предпосылка

Важным вариантом самого слабого предусловия является слабейшее либеральное предварительное условие ${\displaystyle wlp(S,R)}$, что дает наиболее слабое условие, при котором S либо не прекращает, либо устанавливает р. Поэтому он отличается от WP в том, что не гарантирует прекращения. Следовательно, это соответствует Логика Хоара в частичной корректности: для указанного выше языка операторов wlp отличается от WP только на цикл while, не требуя варианта (см. выше).

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

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

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

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

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

Например, по заданию у нас есть:

${\displaystyle sp(x:=E,R)\ =\ \exists y,x=E[x\leftarrow y]\wedge R[x\leftarrow y]}$ куда у свежий

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

${\displaystyle sp(x:=x-5,x>15)\ =\ \exists y,x=y-5\wedge y>15\ \Leftrightarrow \ x>10}$

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

${\displaystyle sp(S_{1};S_{2}\ ,\ R)\ =\ sp(S_{2},sp(S_{1},R))}$

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

Лесли Лэмпорт предложил победить и грех в качестве преобразователи предикатов за параллельное программирование.^[1]

Свойства предикатных трансформаторов

В этом разделе представлены некоторые характерные свойства преобразователей предикатов.^[2] Ниже, Т обозначает преобразователь предикатов (функция между двумя предикатами в пространстве состояний) и п предикат. Например, Т (П) может обозначать wp (S, P) или же sp (S, P). Мы продолжаем Икс как переменная пространства состояний.

Монотонный

Предикатные преобразователи, представляющие интерес (WP, wlp, и зр) находятся монотонный. Преобразователь предикатов Т является монотонный если и только если:

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

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

Строгий

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

${\displaystyle T(\mathbf {false} )\ \Leftrightarrow \ \mathbf {false} }$

Например, WP строго, тогда как wlp вообще нет. В частности, если оператор S не может прекратиться тогда${\displaystyle wlp(S,\mathbf {false} )}$ выполнимо. У нас есть

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

В самом деле, истинный - допустимый инвариант этого цикла.

Прекращение

Преобразователь предикатов Т является прекращение iff:

${\displaystyle T(\mathbf {true} )\ \Leftrightarrow \ \mathbf {true} }$

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

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

Конъюнктивный

Преобразователь предикатов Т является соединительный iff:

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

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

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

Преобразователь предикатов Т является дизъюнктивный iff:

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

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

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

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

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

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

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

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

Приложения

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

Помимо преобразователей предикатов

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

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

Среди них, Теория типа Хора сочетает Логика Хоара для Haskell -подобный язык, логика разделения и теория типов.^[6]Эта система в настоящее время реализована как Coq библиотека называется У не.^[7] На этом языке оценка выражений соответствует расчетам сильнейшие постусловия.

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

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

Смотрите также

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

Примечания

1. Лэмпорт, Лесли (Июль 1990 г.). "победить и грех: Преобразователи предикатов для параллелизма ". ACM Trans. Программа. Lang. Syst. 12 (3): 396–428. CiteSeerX  10.1.1.33.90. Дои:10.1145/78969.78970. S2CID  209901.
2. Назад, Ральф-Йохан; Райт, Йоаким (2012) [1978]. Исчисление уточнения: систематическое введение. Тексты по информатике. Springer. ISBN  978-1-4612-1674-2.
3. Дейкстра, Эдсгер В. (1968). «Конструктивный подход к проблеме корректности программы». BIT вычислительная математика. 8 (3): 174–186. Дои:10.1007 / bf01933419. S2CID  62224342.
4. Вирт, Н. (Апрель 1971 г.). «Разработка программы поэтапной доработкой» (PDF). Comm. ACM. 14 (4): 221–7. Дои:10.1145/362575.362577. HDL:20.500.11850/80846. S2CID  13214445.
5. Учебник по логике Хоара: а Coq библиотека, дающая простое, но формальное доказательство того, что Логика Хоара здраво и полно в отношении операционная семантика.
6. Наневский, Александар; Моррисетт, Грег; Биркедал, Ларс (сентябрь 2008 г.). "Теория типа Хора, полиморфизм и разделение" (PDF). Журнал функционального программирования. 18 (5–6): 865–911. Дои:10.1017 / S0956796808006953.
7. У не а Coq библиотека, реализующая теорию типов Хоара.
8. Морган, Кэрролл; МакИвер, Аннабель; Зайдель, Карен (май 1996 г.). "Вероятностные преобразователи предикатов" (PDF). ACM Trans. Программа. Lang. Syst. 18 (3): 325–353. CiteSeerX  10.1.1.41.9219. Дои:10.1145/229542.229547. S2CID  5812195.

Рекомендации

• де Баккер, Дж. У. (1980). Математическая теория корректности программ. Прентис-Холл. ISBN  978-0-13-562132-5.
• Bonsangue, Marcello M .; Кок, Йост Н. (ноябрь 1994 г.). «Самое слабое исчисление предусловий: рекурсия и двойственность». Формальные аспекты вычислений. 6 (6): 788–800. CiteSeerX  10.1.1.27.8491. Дои:10.1007 / BF01213603. S2CID  40323488.
• Дейкстра, Эдсгер В. (август 1975 г.). «Защищенные команды, неопределенность и формальная производность программ». Comm. ACM. 18 (8): 453–7. Дои:10.1145/360933.360975. S2CID  1679242.
• Дейкстра, Эдсгер В. (1976). Дисциплина программирования. Прентис Холл. ISBN  978-0-613-92411-5. - Систематическое введение в версию защищенного командного языка с множеством отработанных примеров
• Dijkstra, Edsger W .; Шолтен, Карел С. (1990). Исчисление предикатов и семантика программ. Тексты и монографии по информатике. Springer-Verlag. ISBN  978-0-387-96957-2. - Более абстрактный, формальный и окончательный подход
• Грис, Дэвид (1981). Наука программирования. Springer-Verlag. ISBN  978-0-387-96480-5.