Дафни
Язык программирования
Дафни
ПарадигмаИмперативный , функциональный
РазработаноК. Рустан М. Лейно
РазработчикMicrosoft Research , AWS [ требуется ссылка ]
Впервые появился2009 ; 15 лет назад ( 2009 )
Стабильный релиз
3.7.2 / 14 июля 2022 г. ; 2 года назад ( 2022-07-14 )
Дисциплина набора текстаСтатичный, сильный, безопасный
ЛицензияЛицензия Массачусетского технологического института
Расширения имени файла.dfy
Веб-сайтdafny.org

Dafny — это императивный и функциональный компилируемый язык , который компилируется в другие языки программирования , такие как C# , Java , JavaScript , Go и Python . Он поддерживает формальную спецификацию через предусловия , постусловия , инварианты циклов , варианты циклов , спецификации завершения и спецификации фрейминга чтения/записи. Язык объединяет идеи из функциональной и императивной парадигм; он включает поддержку объектно-ориентированного программирования . Возможности включают универсальные классы , динамическое распределение , индуктивные типы данных и вариацию логики разделения, известную как неявные динамические фреймы [1] для рассуждений о побочных эффектах. [2] Dafny был создан Растаном Лейно в Microsoft Research после его предыдущей работы по разработке ESC/Modula-3, ESC/Java и Spec#.

Dafny широко используется в обучении [ требуется ссылка ] , поскольку он обеспечивает простое, комплексное введение в формальную спецификацию и верификацию; он регулярно участвует в конкурсах по верификации программного обеспечения (например, VSTTE'08, [3] VSCOMP'10, [4] COST'11, [5] и VerifyThis'12 [6] ).

Dafny был разработан как язык программирования, поддерживающий проверку, требующий проверки вместе с разработкой кода. Таким образом, он соответствует парадигме разработки программного обеспечения «Correct by Construction». Доказательства проверки поддерживаются математическим набором инструментов, который включает в себя математические целые и действительные числа, битовые векторы, последовательности, множества, мультимножества, бесконечные последовательности и множества, индукцию, коиндукцию и вычислительные доказательства. Обязательства по проверке выполняются автоматически при наличии достаточной спецификации. Dafny использует некоторый программный анализ для вывода многих утверждений спецификации, что снижает нагрузку на пользователя по написанию спецификаций. Общая структура доказательства — это логика Хоара .

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

Типы данных

Dafny предоставляет методы для реализации, которые могут иметь побочные эффекты , и функции для использования в спецификации, которые являются чистыми . [9] Методы состоят из последовательностей операторов, следующих знакомому императивному стилю, в то время как, напротив, тело функции представляет собой просто выражение. Любые операторы с побочными эффектами в методе (например, назначение элемента параметра массива) должны быть учтены путем указания того, какие параметры могут быть изменены, с помощью modifiesпредложения. Dafny также предоставляет ряд неизменяемых типов коллекций, включая: последовательности (например, seq<int>), наборы (например, set<int>), карты ( map<int,int>), кортежи, индуктивные типы данных и изменяемые массивы (например, array<int>).

Императивные черты

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

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

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

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

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

метод sumAndZero ( arr : array <int> ) возвращает ( sum : nat ) требует forall i :: 0 < = i < arr.Length == > arr [ i ] > = 0 изменяет arr { var i : int : = 0 ; sum : = 0 ; // while ( i < arr.Length ) { sum : = sum + arr [ i ] ; arr [ i ] : = arr [ i ] ; i : = i + 1 ; } }​​​

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

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

Доказательства особенностей

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

тип данных Список = Ноль | Ссылка ( данные : целое число , следующее : Список )        функция сумма ( l : Список ): int { match l case Nil => 0 case Link ( d , n ) => d + сумма ( n ) }                 предикат isNatList ( l : List ) { совпадение l case Nil => true case Link ( d , n ) => d >= 0 && isNatList ( n ) }                  лемма NatSumLemma ( l : List , n : int ) требует isNatList ( l ) && n == sum ( l ) гарантирует n >= 0 { match l case Nil => // Выполняется автоматически case Link ( data , next ) => { // Применяем индуктивную гипотезу NatSumLemma ( next , sum ( next )); // Проверяем, что известно Dafny assert data >= 0 ; } }

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

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

Ссылки

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

Дальнейшее чтение

  • Мейер, Бертран; Нордио, Мартин, ред. (2012). Инструменты для практической проверки программного обеспечения: Международная летняя школа, LASER 2011, остров Эльба, Италия, пересмотренные учебные лекции . Springer . ISBN 978-3642357459.
  • Ситниковски, Боро (2022). Знакомство с проверкой программного обеспечения с помощью языка Dafny: доказательство корректности программы . Apress. ISBN 978-1484279779.
  • Dafny: верификатор языка и программ для функциональной корректности - Microsoft Research
  • GitHub - dafny-lang/dafny: Dafny — это язык программирования, поддерживающий проверку
Взято с "https://en.wikipedia.org/w/index.php?title=Dafny&oldid=1147041505"