Рассуждение о недетерминированных концевых циклах

10

Вот вопрос «следа B», если таковой был. Резюме: первое, о чем я думаю, когда пытаюсь дать семантику недетерминированным программам, приводит к семантике, где я не могу доказать вещи о циклах, которые заканчивают только недетерминированно. Конечно, кто-то определил, что делать в этой ситуации, или, по крайней мере, указал, что это сложно, но я не знаю, как его искать (отсюда и тег «запрос ссылки»).

Фон

Я хочу смоделировать язык пока с недетерминизмом. Я думаю, что это очевидный (или, по крайней мере, наивный) способ моделировать такой язык с помощью домена силы Смита, но поправьте меня, если я ошибаюсь. Мы смоделируем значение команды на этом языке как функцию, чья область - это множество состояний S а кодовый домен - множество P(S)={}P(S) , где - наименьший элемент представляет не прекращение, а P(S) - набор состояний.

σ{σ1,σ2,}PQ

  • skipσ={σ}
  • x:=Eσ={σ[(Eσ)/x]}
  • abortσ=
  • if E then P else Qσ=Pσ если Eσ=true , в противном случае Qσ
  • PQσ= if Pσ= или Qσ= , в противном случае PσQσ
  • Р сг = Q т = т Р сг т Р сгВ тP;Qσ= if или для некоторого , в противном случаеPσ=Qτ=τPστPσQτ

Существует направленный полный частичный порядок , где для любого и если и являются собственными наборами, а , и мы можем расширить это до функций от до : если для каждой , и - это функция, которая отображает каждое состояние в .S S P ( S ) S 1S 2 S 1 S 2 S 1S 2 f SSSP(S)S1S2S1S2S1S2fSf 1f 2 f 1 ( σ ) f 2 ( σ ) σ f P(S)f1f2f1(σ)f2(σ)σf

Значение цикла - это - это наименьшая верхняя граница цепи , где если , в противном случае если или для некоторого , в противном случае . (Это определение предполагает , что я только что определил Скотт непрерывен, но я думаю , что это безопасно , чтобы оставить это в стороне.)ф ф ( е ) ф ( е ( ф ) ) ... е ( г ) ( σ ) = { σ } Е ( σ ) = F л ев еР сг = while E do Pσff(f)f(f(f))f(g)(σ)={σ}E(σ)=falsePσ=т Р сгg(τ)=τPσеτPσg(τ)f

Вопрос

Рассмотрим эту программу:

б : = т т у д ; ш х в я л е б д оx:=0;
b:=true;
while b do
x:=x+2;
b:=falseb:=true

Наглядно это цикл , который может возвращать любое положительное четное число или не прекращается, и что соответствует тому , что мы можем доказать , об этом цикле , используя самую слабую либеральную предпосылку (можно показать , что петля инвариант). Однако, поскольку цикл имеет возможность не завершаться (мы можем уточнить недетерминированный выбор с помощью программы, которая всегда выбирает правую ветвь), значение этой программы для любого начального состояния равно . (Менее неформально: функция, которая отображает любое состояние, где ложно, и любое состояние, где верно для является фиксированной точкой используемой для определения цикла.)b b fn.x=2nbbf

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

Роб Симмонс
источник
4
Я думаю, что используя в качестве кодовой области значения программы, вы фактически отказались от рассуждений о программе, которая может расходиться. Наивная мысль состоит в том, чтобы использовать , но я не знаю, вызовет ли это другую проблему. P ( S { } ){}P(S)P(S{})
Цуёси Ито
Да, вы абсолютно правы, что, глядя на набор уже очевидно, что надежда потеряна даже до того, как мы перейдем к примеру. Ваше предложение также пришло мне в голову, но я думаю, что вы столкнетесь с той же проблемой в этом примере, пока потенциальное отсутствие завершения моделируется не , и если мы выбрали последнее, что будет мешать нашей способности придавать смысл циклу как наименее фиксированной точке обычным способом. S { } { }{}P(S)S{}{}
Роб Симмонс
Вы смотрели на динамическую логику? Семантика дана в терминах отношений между состояниями и состояниями, и вы можете использовать логику, чтобы рассуждать о частичной и полной корректности, то есть о свойствах вычислений, которые заканчиваются, и что все вычисления заканчиваются с данным свойством.
Дэйв Кларк
Я не думал о динамической логике в этой обстановке, но я понимаю, как это может быть актуально - я увижу, что думают Платцер и его ученики, когда я вернусь в Питтсбург.
Роб Симмонс

Ответы:

10

В [dB80] доказано, что анализ Хичкоком и Паком свойств завершения рекурсии соответствует семантическому анализу, основанному на так называемой интерпретации отношений Эгли-Милнера [Egl75, Plo76], которая выражает ошибочный недетерминизм. Это понятие фиксирует, что недетерминированное объединение отношений является правильным, если оно генерирует, по крайней мере, одно вычисление, приводящее к желаемому результату (даже при наличии неопределенного вычисления). Похоже, это соответствует тому, что вы пытаетесь сделать.

Далее охарактеризуйте значение оператора как функции отображающей каждое начальное состояние в некоторый непустой набор состояний, возможно, содержащий , такой, что является строгим в том смысле, что . Недетерминированный выбор между операторами и описывается функцией, отображающей каждое начальное состояние в объединение отдельных результатов . Таким образом, всякий раз, когда илиf S σ f S f S ( ) = { } S 1 S 2 σ f S 1 ( σ ) f S 2 ( σ ) S 1 S 2SfSσfSfS()={}S1S2σfS1(σ)fS2(σ)S1S2имеет недетерминированную возможность получения нежелательного результата, как и их недетерминированный выбор. В качестве результирующих наборов конечных состояний в этом анализе получают так называемый набор состояний Эгли-Милнера:

PE--M(S)={ sS | s конечно и непусто, или содержит}

Почему бесконечные подмножества не рассматриваются как возможные множества конечных состояний в этой модели? В предположении, что все основные строительные блоки реляционных терминов производят только конечные непустые множества возможных конечных состояний, бесконечный набор возможных конечных состояний может быть сгенерирован только тогда, когда возможны бесконечные вычисления. Это можно увидеть следующим образом. Структурируйте множество всех возможных вычислений, начиная с заданного состояния как дерева с корнем и состояний как узлов. Множество листьев - это в точности набор возможных конечных состояний, достижимых из , за исключениемσ 0 σ 0 σ 0Sσ0σ0σ0, который может отсутствовать среди листьев, но представлен во множестве конечных состояний тем, что в дереве существует бесконечный путь. По предположению выше, и поскольку доступен только конечный недетерминированный выбор, это дерево конечно ветвится. Таким образом, на любой данной конечной глубине имеется только конечное число листов. Следовательно, бесконечное число возможных конечных состояний может быть сгенерировано только при наличии бесконечного вычисления (применение леммы Кенига [Kön32]).

Е - М ы ,(PE--M(S),E--M) является для определяется как: для ,E--Ms,tPE--M(S)

sE--Mt=(ss{}t)(ss=t) .

Здесь можно рассматривать как заполнитель, с помощью которого можно генерировать наборы , вставляя больше состояний вместо . Следовательно, является наименьшим элементом . Кроме того, у poset есть lub для -цепей. Точно так же строгие функции из в частично упорядочены поточечным расширением . Кроме того, наименее такая функцияЕ - М{ } ( Р Е - М ( С ) , Е - М ) ( Р Е - М ( С ) , Е - М ) ω S { } Р Е --M ( S ) E - M λ σ . { }E--M{}(PE--M(S),E--M)(PE--M(S),E--M)ωS{}PE--M(S)E--Mλσ.{} и lub's -цепей таких функций тоже существуют.ω

[dB80] Дж.В. де Баккер. Математическая теория корректности программы . Прентис Холл, 1980.

[Egl75] H Egli. Математическая модель для недетерминированных вычислений. Технический отчет, ETH Zürich, 1975.

[Kön32] D König. Theorie der endlichen und undndlichen Графен. Технический отчет, Лейпциг, 1932.

[Plo76] Г.Д. Плоткин. Энергетическая конструкция. Журнал SIAM по вычислениям , 5 (3): 452-487, 1976.

Отказ от ответственности: это взято почти дословно из книги, которую я когда-то в соавторстве:

WP де Ровер и К. Энгельхардт. Уточнение данных: модельно-ориентированные методы доказательства и их сравнение . Издательство Кембриджского университета, 1998.

Кай
источник
4
Фраза «это почти дословно взято из книги, которую я когда-то в соавторстве», вероятно, должна иметь префикс «Extra Awesomeness:», а не «Disclaimer:» :-D. Спасибо, это очень полезно.
Роб Симмонс
Один из подходов к недетерминизму (и к тому, что я хочу посмотреть на него) состоит в том, что это форма недоопределения: программа с недетерминированным выбором уточняется программой, которая всегда выбирает первый, всегда выбирает второй, или (см. обширную работу Макивера и Моргана в этой конкретной области) программу, которая выбирает один или другой с вероятностью .5 . Таким образом, цикл, который недетерминированно не заканчивается, уточняется циклом, который никогда не заканчивается, а также вашим циклом переворота монет, который завершается (с вероятностью 1)
Роб Симмонс