Кадровое правило как хранитель изменений?

18

Правило рамки , как приведенному ниже, отражает идею , что, учитывая программу cс предварительным условием , pчто имеет место , прежде чем он работает и постусловии qчто держит позже, некоторые непересекающиеся условие rследует держать как до , так и после того, как cработает. ( *Соединение требует, чтобы его аргументы были непересекающимися.) Часто предварительные и постусловия являются состояниями кучи и cпредставляют собой эффективную программу, которая каким-то образом модифицирует кучу.

    {p} c {q}
----------------- (where no free variable in r is modified by c)
{p * r} c {q * r}

Обсуждение правила фрейма, которое я видел, всегда фокусируется на том r, как сохраняется непересекающаяся часть кучи . Это позволяет «локально рассуждать»: рассуждая о влиянии, cкоторое мы имеем, мы можем игнорировать rчасть кучи и заботиться только о той части, которая действительно изменяется. Но другой способ взглянуть на это состоит в том, что изменение с pнаq сохраняется, даже если rсейчас там сидят. Другими словами, важно, чтобы мы в конечном итоге получили постусловие {q * r}, а не {q' * r}какое-то другое q'.

Итак, мой вопрос , есть ли какое - либо лечение правила кадра, обсуждаемые или используют сохранение его изменения-from- p-До- qвещи.

Линдси Купер
источник
Один ответ на мой собственный вопрос находится в этой статье: software.imdea.org/~gotsman/papers/interproc-sas06.pdf , в предложении (выделено мной): «Если P обеспечивает выделение C, то в соответствии с Frame, выполняя C при наличии дополнительной памяти R приводит к тому же поведению , а C не затрагивает дополнительную память ». Это то, что «приводит к тому же самому поведению», которое я искал для кого-то, чтобы указать, в дополнение к просто «C не затрагивает дополнительную память». (Спасибо @kaosjester за ссылку.)
Линдси Купер
1
Если вы прочтете доказательства правильности правила кадра и других правил логики разделения, вы обнаружите, что они делают именно то, что вам нужно, т. Е. Они говорят о том, как сохраняется изменение от к q . Обратите внимание на местность и свойства рамы, упомянутые там. pq
Удай Редди

Ответы:

11

Но это без изменений в qсобственности на самом деле не имеет места!

Посмотрим {emp} x := alloc(0) {x |-> 0}. Теперь, если я в кадре y |-> 3, я получаю

{y |-> 3} x := alloc(0) {x |-> 0 * y |-> 3}

но по правилу следствия я мог изменить постусловие на

{y |-> 3} x := alloc(0) {(x |-> 0 /\ x != y) * y |-> 3}

Чтобы сделать это более конкретным, предположим, что yэто число 37. Когда я запускаю команду выделения в совершенно пустой куче, возможно, что я в конечном итоге выделю адрес 37, так что x = 37. Но если я вместо этого начну с кучи, содержащей одну ячейку по адресу y = 37, этот результат больше невозможен! Добавление рамки к предварительному условию исключило некоторые недетерминированности в постусловии.

Статья «Локальное действие и абстрактная логика разделения» (Calcagno, O'Hearn и Yang) посвящена пониманию правила фрейма с более глубокой, семантической точки зрения. Ключевым определением статьи является локальность для «действий», где действие - это (семантическое представление) программы. Локальность говорит, что когда вы добавляете кучу кадров, единственный способ изменить исходное постусловие - это обрезать некоторый недетерминизм, как описано выше. И, на самом деле, обрезка возникает только из-за выделения.

Аарон Турон
источник
Спасибо за пример и за ссылку! Ваш пример имеет смысл. Справедливо ли, однако, сказать, что это qможет измениться только на " q, а также ..."? И, кроме того, если распределение - это единственное, что может обрезать недетерминизм в постусловии (что само по себе является крутым результатом), то, если есть некоторая часть постусловия, которая не зависит от местоположения, то эта часть постусловия гарантированно останется прежним? Можно ли сказать, что постусловие остается неизменным вплоть до альфа-переименования местоположений? (Я имею в виду пример, но, возможно, это лучше объяснить по электронной почте.)
Линдси Купер
1
Да, qможет измениться только на " q, а также ..." Другими словами, постусловие может только стать сильнее : оно будет означать исходное постусловие. Это часть определения местности для действий. Однако неверно, что изменение постусловия связано только с переименованием. В приведенном мною примере тот факт, что xи yявляются различными, является истинным независимо от выбранного адреса y. В этом примере фиксируется свежесть распределения, которая инвариантна при переименовании.
Аарон Турон
11

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

PR{h1h2|час1пчас2рdом(час1)dом(час2)знак равно}

Так в правиле кадра

{п}с{Q}{п*р}с{Q*р}

P и Q ) не говорят о конкретных кучах - они являютсясвойствамикуч (поскольку подмножества и предикаты эквивалентны). Лучший способ понять, что происходит - взглянуть на определение значения тройки Хоара:рпQ

{п}с{Q}час1п,час'ЧАСеaпулицачас'#час1,час2Q,час1час';с*час2час';sКяп

Это определение в основном говорит, что (1) если вы запустите с любым h 1 в P , то вы закончите в каком-то конечном состоянии h 2счас1пчас2 в , и (2) если вы добавите в любую дополнительную память h , эта память будет быть неизменным в конце пробега. Но обратите внимание, что конкретное значение h 2, которое вы получаете, может различаться для разных вариантов выбора h --- что гарантировано, так это то, что свойства P и Q будут продолжать сохраняться при расширении, а не то, что вы получите точно такую ​​же кучу результатов.Qчас' час2час' пQ

Это не слишком сложно, но все же стоит потрудиться, чтобы увидеть, как это определение тройки Хоара подразумевает, что правило фрейма выполнено. Как вы заметили, это своего рода свойство «сохранения изменений», и оно особенно ярко выражено в формулировке правила параллельной композиции в логике параллельного разделения:

{п1}с1{Q1}{п2}с2{Q2}{п1*п2}с1||с2{Q1*Q2}

Если и c 2 действуют на непересекающиеся области памяти, то каждый из них не будет мешать свойствам выполнения другого, когда они выполняются параллельно.с1с2

Об этом говорится в статье Хоара и др. « О локальности и законе обмена для параллельных процессов» , где они показывают, как дать объединенную алгебру программ и утверждений.

Нил Кришнасвами
источник
Определение троек Хоара выглядит неверно: в нем должно быть сказано, что выполнение не является ошибкой, должно учитываться отсутствие завершения, вероятно, оно не должно исключать модели, которые не имеют монотонности безопасности. (Но да, я согласен, что совершенно разумно говорить о «сохранении изменений» по причинам, которые вы объясняете.)
Раду ГРИГОР,
3
(1) Я дал семантику для троек полной корректности, и поэтому он утверждает, что команда завершается благополучно - я считаю, что полная корректность делает более понятным объяснение типа «полный / существующий» до и после условий. (2) Эта семантика троек была фактически изобретена (IIRC Биркедалом и Янгом) для обработки языков, которые не имеют монотонности безопасности в языковой семантике, встроив ее в значение троек. В результате вы можете иметь немонотонные конструкции (например, запросы о размере кучи) в языке, сохраняя при этом правило фрейма для логики Хоара.
Нил Кришнасвами
(1) Хорошо, но эти тройки написаны по-другому. (2) Я этого не знал. Перефразируя то, что вы сказали: без монотонности вы можете потерять правило фрейма и продолжать использовать тройки Хоара, как обычно, к чему я и пришел в первом комментарии:с
1
Спасибо, Нил! Вы правы, я совмещал свойства P и Q с конкретными кучами. Итак, подведем итог вашего комментария: Q сохраняется, но конкретная куча, которую вы получаете в конце, может быть другой кучей, удовлетворяющей Q, чем вы получали раньше. Да?
Линдси Купер
1
@RaduGRIGore: да, я предполагал, что язык был детерминированным, и это предположение потерпит неудачу, когда мы добавим параллелизм. Хорошо поймал!
Нил Кришнасвами
2

Хотя это не связано на 100%, это имеет вид идемпотентности контракта.

Если мы будем думать о {p} как о предварительном условии на c и {q} как о постусловии на c, эта идея правила фрейма обеспечит выполнение предварительных и постусловий в любом контексте вычисления, а не простой случай, когда ничего не существует.

Тем не менее, я не могу сказать, что я видел такое рамочное правило, представленное в любом из десятков контрактных документов, которые я прочитал. Это, безусловно, отличная идея, и требование такого изменения может многое сделать для выработки разумного, осязаемого понимания идемпотентных контрактов.

kaosjester
источник
Спасибо за комментарий. Хм, интересно - интересно, кто-нибудь еще читает это знает о контрактных документах, в которых указываются свойства фрейма.
Линдси Купер