Слабейшее предусловие

Преобразователи предикатов — расширение логики Флойда-Хоара, сделанное Э. Дейкстрой. Впервые появившись в [1], с помощью этого метода определяется семантика императивного программирования и соответствующего языка. В нём каждой команде языка программирования соответствует преобразователь предиката, т. е. полное функциональное соответствие между двумя предикатами в пространстве состояний программы.

Основной преобразователь предикатов в последовательном императивном программировании называется слабейшее предусловие (от англ. weakest precondition), обозначаемый wp(S,R). Здесь S — список инструкций (команд), а R — предикат состояния, называемый также постусловие. Результат применения этой функции и даёт нам «слабейшее предусловие» для списка S, прерывающийся когда R будет истинным. Например,

<math> wp(x := E, R)\ =\ R_E^x </math>,

получая предикат-копию R со значением x заменённым на E.

Важным вариантом wp является так называемое слабейшее свободное предусловие (weakest liberal precondition — перевод даётся по [2]), обозначаемое wlp(S,R). Свободное предусловие является более слабым, т. е. получаемый результат (конечное состояние, удовлетворяющее R) не обязательно «правильный» — гарантируется лишь, что система не выдаст «неправильного» результата (не достигнет такого конечного состояния, которое не удовлетворяло бы R), однако не исключает возможность незавершения работы системы.

Таким образом, выражение

<math> wp(S, R)\ =\ ( wlp(S, R)\ and\ wp(S, T))</math>,

где Т — терминальное (конечное) состояние системы, всегда обеспечит истинность R.

С помощью wp Дейкстра определил альтернативный (if) и итерационный (do) операторы, а также оператор композиция (;).

Назначением указанных преобразователей предикатов сам Дейкстра указывал создание методологии для программистов по разработке «правильно построенных» программ. Стиль программирования Дейкстры был развит в логике высшего порядка Ральфа-Йохана Бэка в статье Refinement Calculus.

Можно отметить также другой предикат — сильнейшее постусловие, описывающий максимально сильные ограничения на состояние программы S, которые могут быть получены при данном предусловии.

Влияние метода

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

Ссылки

• [www.ctc.msiu.ru/materials/Book/node41.html Спецификация программы и преобразователь предикатов wp]

Отрывок, характеризующий Слабейшее предусловие

Однажды в Москве, в присутствии княжны Марьи (ей казалось, что отец нарочно при ней это сделал), старый князь поцеловал у m lle Bourienne руку и, притянув ее к себе, обнял лаская. Княжна Марья вспыхнула и выбежала из комнаты. Через несколько минут m lle Bourienne вошла к княжне Марье, улыбаясь и что то весело рассказывая своим приятным голосом. Княжна Марья поспешно отерла слезы, решительными шагами подошла к Bourienne и, видимо сама того не зная, с гневной поспешностью и взрывами голоса, начала кричать на француженку: «Это гадко, низко, бесчеловечно пользоваться слабостью…» Она не договорила. «Уйдите вон из моей комнаты», прокричала она и зарыдала.
На другой день князь ни слова не сказал своей дочери; но она заметила, что за обедом он приказал подавать кушанье, начиная с m lle Bourienne. В конце обеда, когда буфетчик, по прежней привычке, опять подал кофе, начиная с княжны, князь вдруг пришел в бешенство, бросил костылем в Филиппа и тотчас же сделал распоряжение об отдаче его в солдаты. «Не слышат… два раза сказал!… не слышат!»
«Она – первый человек в этом доме; она – мой лучший друг, – кричал князь. – И ежели ты позволишь себе, – закричал он в гневе, в первый раз обращаясь к княжне Марье, – еще раз, как вчера ты осмелилась… забыться перед ней, то я тебе покажу, кто хозяин в доме. Вон! чтоб я не видал тебя; проси у ней прощенья!»
Княжна Марья просила прощенья у Амальи Евгеньевны и у отца за себя и за Филиппа буфетчика, который просил заступы.
В такие минуты в душе княжны Марьи собиралось чувство, похожее на гордость жертвы. И вдруг в такие то минуты, при ней, этот отец, которого она осуждала, или искал очки, ощупывая подле них и не видя, или забывал то, что сейчас было, или делал слабевшими ногами неверный шаг и оглядывался, не видал ли кто его слабости, или, что было хуже всего, он за обедом, когда не было гостей, возбуждавших его, вдруг задремывал, выпуская салфетку, и склонялся над тарелкой, трясущейся головой. «Он стар и слаб, а я смею осуждать его!» думала она с отвращением к самой себе в такие минуты.


В 1811 м году в Москве жил быстро вошедший в моду французский доктор, огромный ростом, красавец, любезный, как француз и, как говорили все в Москве, врач необыкновенного искусства – Метивье. Он был принят в домах высшего общества не как доктор, а как равный.
Князь Николай Андреич, смеявшийся над медициной, последнее время, по совету m lle Bourienne, допустил к себе этого доктора и привык к нему. Метивье раза два в неделю бывал у князя.
В Николин день, в именины князя, вся Москва была у подъезда его дома, но он никого не велел принимать; а только немногих, список которых он передал княжне Марье, велел звать к обеду.
Метивье, приехавший утром с поздравлением, в качестве доктора, нашел приличным de forcer la consigne [нарушить запрет], как он сказал княжне Марье, и вошел к князю. Случилось так, что в это именинное утро старый князь был в одном из своих самых дурных расположений духа. Он целое утро ходил по дому, придираясь ко всем и делая вид, что он не понимает того, что ему говорят, и что его не понимают. Княжна Марья твердо знала это состояние духа тихой и озабоченной ворчливости, которая обыкновенно разрешалась взрывом бешенства, и как перед заряженным, с взведенными курками, ружьем, ходила всё это утро, ожидая неизбежного выстрела. Утро до приезда доктора прошло благополучно. Пропустив доктора, княжна Марья села с книгой в гостиной у двери, от которой она могла слышать всё то, что происходило в кабинете.