Дафни - Dafny

Дафни
ПарадигмаИмператив, Функциональный
РазработаноК. Рустан М. Лейно
РазработчикMicrosoft Research
Впервые появился2009; 11 лет назад (2009)
Стабильный выпуск
2.3.0 / 7 мая 2019 г.; 18 месяцев назад (2019-05-07)
Печатная дисциплинаСтатичный, сильный, безопасный
ЛицензияЛицензия MIT
Интернет сайтисследование.microsoft.com/ dafny

Дафни это императив компилируемый язык это нацелено C # и поддерживает формальная спецификация через предварительные условия, постусловия, инварианты цикла и варианты петли. Язык сочетает в себе идеи, прежде всего функциональный и императив парадигм и включает ограниченную поддержку объектно-ориентированного программирования. Особенности включают общие классы, динамическое размещение, индуктивные типы данных и вариант логика разделения известный как неявные динамические кадры[1] для рассуждения о побочных эффектах.[2] Дафни был создан Рустаном Лейно в Microsoft Research после его предыдущей работы по разработке ESC / Modula-3, ESC / Java, и Спецификация #. Dafny широко используется в обучении и регулярно участвует в соревнованиях по проверке программного обеспечения (например, VSTTE'08,[3] VSCOMP'10,[4] COST'11,[5] и VerifyThis'12[6]).

Dafny был разработан, чтобы обеспечить простое введение в формальную спецификацию и проверку, и широко используется в обучении. Дафни основывается на буги-вуги промежуточный язык который использует Z3 автоматическое доказательство теорем для выполнения обязательств по доказательству.[7][8]

Типы данных

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

Императивные особенности

Дафни поддерживает доказательства императивных программ, основанные на идеях Логика Хоара. Ниже показано множество таких функций в Dafny, включая использование предварительных условий, постусловий, инвариантов цикла и вариантов цикла.

метод Максимум(обр:множество<int>) возвращается(Максимум:int) // В массиве должен быть хотя бы один элемент требует обр!=ноль && обр.Длина > 0; // Возврат не может быть меньше любого элемента в массиве обеспечивает (для всех j :int :: (j >= 0 && j < обр.Длина ==> Максимум >= обр[j])); // Возврат должен соответствовать некоторому элементу в массиве обеспечивает (существуют j : int :: j>=0 && j < обр.Длина && Максимум==обр[j]);{  Максимум:=обр[0];  вар я:int :=1;  //  пока(я < обр.Длина)  // Отступ не более arr.Length (необходим для отображения i == arr.Length после цикла)  инвариантный (я<=обр.Длина);  // Ни один элемент не замечен настолько большим, чем max  инвариантный (для всех j:int :: j>=0 && j<я ==> Максимум >= обр[j]);  // Некоторый элемент, который мы видели до сих пор, соответствует max  инвариантный (существуют j:int :: j>=0 && j<я && Максимум == обр[j]);  // Завершаем, когда i == arr.Length  уменьшается (обр.Длина-я);   {    // Обновляем max, если встречается более крупный элемент    если(обр[я] > Максимум){Максимум := обр[я];}    // Продолжаем через массив    я := я + 1;  }}

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

Инварианты цикла

Обработка инвариантов петель в Dafny отличается от традиционной Логика Хоара. Переменные, измененные в цикле, обрабатываются таким образом, что (большая часть) информации, известной о них до цикла, отбрасывается. Информация, необходимая для доказательства свойств таких переменных, должна быть явно выражена в инварианте цикла. Напротив, переменные, не измененные в цикле, сохраняют всю информацию, известную о них заранее. Следующее обеспечивает иллюстрирует:

метод sumAndZero(нс:множество<int>) возвращается (сумма:нац)  требует нс != ноль  требует для всех я :: 0 <= я < нс.Длина ==> нс[я] >= 0  изменяет нс {  вар я:int := 0;  вар обр:множество<int> := нс; // потому что параметры не могут быть назначены  сумма := 0;  //  пока(я < обр.Длина) {    сумма := сумма + обр[я];    обр[я] := обр[я];    я := я + 1;  }}

Это не подтверждается, потому что Дафни не может установить, что (сумма + arr [i])> = 0 держит на задании. Из предварительного условия интуитивно forall i :: 0 <= i arr [i]> = 0 выполняется в цикле, поскольку arr [i]: = arr [i]; это NOP. Однако это задание заставляет Дафни лечить обр как изменяемая переменная и удалить информацию, известную о ней до цикла. Чтобы проверить эту программу в Dafny, мы можем: удалить избыточное назначение arr [i]: = arr [i];; или добавьте инвариант цикла инвариант для всех i :: 0 <= i arr [i]> = 0

Дафни дополнительно нанимает статический анализ чтобы вывести простые инварианты цикла, где это возможно. В приведенном выше примере кажется, что цикл инвариантен инвариант i> = 0 также требуется как переменная я мутирует внутри цикла. Хотя базовая логика действительно требует такого инварианта, Дафни автоматически делает это, и, следовательно, его можно опустить на уровне источника.

Особенности доказательства

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

тип данных Список = Ноль | Связь(данные:int,следующий:Список)функция сумма(л:Список): int {  матч л    дело Ноль => 0    дело Связь(d,п) => d + сумма(п)}предикат isNatList(л:Список) {  матч л    дело Ноль => истинный    дело Связь(d,п) => d >= 0 && isNatList(п)}призрак метод NatSumLemma(л:Список, п:int)требует isNatList(л) && п == сумма(л)обеспечивает п >= 0 {  матч л    дело Ноль =>      // Разряжается автоматически    дело Связь(данные,следующий) => {      // Применяем индуктивную гипотезу      NatSumLemma(следующий,сумма(следующий));      // Проверяем, что известно Дафни      утверждать данные >= 0;    }}

Здесь, NatSumLemma доказывает полезное свойство между сумма () и isNatList () (т.е. что isNatList (l) ==> (сумма (l)> = 0)). Использование призрачный метод для кодирования леммы и теоремы является стандартным в Dafny с рекурсией, используемой для индукции (обычно, структурная индукция ). Анализ случая выполняется с использованием матч заявления и неиндуктивные дела часто выписываются автоматически. Проверяющий также должен иметь полный доступ к содержимому функция или же предикат чтобы при необходимости развернуть их. Это имеет значение при использовании вместе с модификаторы доступа. В частности, скрытие содержимого функция с использованием защищенный модификатор может ограничивать, какие свойства могут быть установлены относительно него.

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

  1. ^ Сманс, Ян; Джейкобс, Барт; Писсенс, Франк (2009). Неявные динамические кадры: объединение динамических кадров и логики разделения. Труды конференции Европейской конференции по объектно-ориентированному программированию. С. 148–172. Дои:10.1007/978-3-642-03013-0_8.
  2. ^ Лейно, Рустан (2010). Dafny: автоматическая программа проверки функциональной корректности. Труды конференции по логике программирования, искусственного интеллекта и рассуждений. С. 348–370. Дои:10.1007/978-3-642-17511-4_20.
  3. ^ Лейно, Рустань; Монахан, Розмари (2010). Дафни отвечает требованиям контрольных тестов (PDF). Международная конференция по проверенному программному обеспечению: теории, инструменты и эксперименты. С. 112–116. Дои:10.1007/978-3-642-15057-9_8.
  4. ^ Клебанов, Владимир; и другие. (2011). Первый конкурс проверенного программного обеспечения: отчет об опыте. Материалы конференции по формальным методам. С. 154–168. CiteSeerX  10.1.1.221.6890. Дои:10.1007/978-3-642-21437-0_14.
  5. ^ Бормер, Торстен; и другие. (2011). Конкурс проверки COST IC0701 2011. Материалы конференции по формальной верификации объектно-ориентированного программного обеспечения. С. 3–21. CiteSeerX  10.1.1.396.6170. Дои:10.1007/978-3-642-31762-0_2.
  6. ^ Хейсман, Мариеке; Клебанов, Владимир; Монахан, Розмари (2015). «VerifyThis 2012: Конкурс по проверке программ» (PDF). Журнал программных средств для передачи технологий. 17 (6): 647–657. Дои:10.1007 / s10009-015-0396-8.
  7. ^ "Домашняя страница Z3". 2019-02-07.
  8. ^ де Моура, Леонардо; Бьёрнер, Николай (2008). Z3: эффективный решатель SMT. Материалы конференции по инструментам и алгоритмам построения и анализа. С. 337–340. Дои:10.1007/978-3-540-78800-3_24.

внешняя ссылка