Share to: share facebook share twitter share wa share telegram print page

Dafny

Dafny
ParadigmImperative, functional
Designed byK. Rustan M. Leino
DeveloperMicrosoft Research, AWS[citation needed]
First appeared2009; 15 years ago (2009)
Stable release
3.7.2 / July 14, 2022; 2 years ago (2022-07-14)
Typing disciplineStatic, strong, safe
LicenseMIT License
Filename extensions.dfy
Websitedafny.org

Dafny is an imperative and functional compiled language that compiles to other programming languages, such as C#, Java, JavaScript, Go and Python. It supports formal specification through preconditions, postconditions, loop invariants, loop variants, termination specifications and read/write framing specifications. The language combines ideas from the functional and imperative paradigms; it includes support for object-oriented programming. Features include generic classes, dynamic allocation, inductive datatypes and a variation of separation logic known as implicit dynamic frames[1] for reasoning about side effects.[2] Dafny was created by Rustan Leino at Microsoft Research after his previous work on developing ESC/Modula-3, ESC/Java, and Spec#.

Dafny is widely used in teaching[citation needed] because it provides a simple, integrated introduction to formal specification and verification; it is regularly featured in software verification competitions (e.g. VSTTE'08,[3] VSCOMP'10,[4] COST'11,[5] and VerifyThis'12[6]).

Dafny was designed as a verification-aware programming language, requiring verification along with code development. It thus fits the "Correct by Construction" software development paradigm. Verification proofs are supported by a mathematical toolbox that includes mathematical integers and reals, bit-vectors, sequences, sets, multisets, infinite sequences and sets, induction, co-induction, and calculational proofs. Verification obligations are discharged automatically, given sufficient specification. Dafny uses some program analysis to infer many specification assertions, reducing the burden on the user of writing specifications. The general proof framework is that of Hoare logic.

Dafny builds on the Boogie intermediate language which uses the Z3 automated theorem prover for discharging proof obligations.[7][8]

Data types

Dafny provides methods for implementation which may have side-effects and functions for use in specification which are pure.[9] Methods consist of sequences of statements following a familiar imperative style whilst, in contrast, the body of a function is simply an expression. Any side-effecting statements in a method (e.g. assigning an element of an array parameter) must be accounted for by noting which parameters can be mutated, using the modifies clause. Dafny also provides a range of immutable collection types including: sequences (e.g. seq<int>), sets (e.g. set<int>), maps (map<int,int>), tuples, inductive datatypes and mutable arrays (e.g. array<int>).

Imperative features

The following illustrates many of the features in Dafny, including the use of preconditions, postconditions, loop invariants and loop variants.

method max(arr:array<int>) returns (max:int)
 // Array must have at least one element
 requires arr.Length > 0
 // Return cannot be smaller than any element in array
 ensures forall j : int ::   j >= 0 && j < arr.Length  ==>  max >= arr[j]
 // Return must match some element in array
 ensures exists j : int ::   j>=0 && j < arr.Length && max == arr[j]
{
  max := arr[0];
  var i: int := 1;
  //
  while(i < arr.Length)
  // Index at most arr.Length (needed to show i==arr.Length after loop)
  invariant i <= arr.Length
  // No element seen so far larger than max
  invariant forall j:int :: j >= 0 && j < i  ==>  max >= arr[j]
  // Some element seen so far matches max
  invariant exists j:int :: j >= 0 && j < i && max == arr[j]
  // arr.Length - i decreases at every step and is lower-bounded by 0
  decreases arr.Length - i
  {
    // Update max if larger element encountered
    if (arr[i] > max) {
      max := arr[i];
    }
    // Continue through array
    i := i + 1;
  }
}

This example computes the maximum element of an array. The method's precondition and postcondition are given with the requires and ensures clauses (respectively). Likewise, the loop invariant and loop variant are given through the invariant and decreases clauses (respectively).

Loop invariants

The treatment of loop invariants in Dafny differs from traditional Hoare logic. Variables mutated in a loop are treated such that (most) information known about them prior to the loop is discarded. Information required to prove properties of such variables must be expressed explicitly in the loop invariant. In contrast, variables not mutated in the loop retain all information known about them beforehand. The following example illustrates using loops:

method sumAndZero(arr: array<int>) returns (sum: nat)
  requires forall i :: 0 <= i < arr.Length  ==>  arr[i] >= 0
  modifies arr
{
  var i: int := 0;
  sum := 0;
  //
  while(i < arr.Length) {
    sum := sum + arr[i];
    arr[i] := arr[i];
    i := i + 1;
  }
}

This fails verification because Dafny cannot establish that (sum + arr[i]) >= 0 holds at the assignment. From the precondition, intuitively, forall i :: 0 <= i < arr.Length ==> arr[i] >= 0 holds in the loop since arr[i] := arr[i]; is a NOP. However, this assignment causes Dafny to treat arr as a mutable variable and drop information known about it from before the loop. To verify this program in Dafny we can either (a) remove the redundant assignment arr[i] := arr[i];; or (b) add the loop invariant invariant forall i :: 0 <= i < arr.Length ==> arr[i] >= 0

Dafny additionally employs limited static analysis to infer simple loop invariants where possible. In the example above, it would seem that the loop invariant invariant i >= 0 is also required as variable i is mutated within the loop. Whilst the underlying logic does require such an invariant, Dafny automatically infers this and, hence, it can be omitted at the source level.

Proof features

Dafny includes features which further support its use as a proof assistant. Although proofs of simple properties within a function or method (as shown above) are not unusual for tools of this nature, Dafny also allows the proof of properties between one function and another. As is common for a proof assistant, such proofs are often inductive in nature. Dafny is perhaps unusual in employing method invocation as a mechanism for applying the inductive hypothesis. The following illustrates:

datatype List = Nil | Link(data: int, next: List)

function sum(l: List): int {
  match l
    case Nil => 0
    case Link(d, n) => d + sum(n)
}

predicate isNatList(l: List) {
  match l
    case Nil => true
    case Link(d, n) => d >= 0 && isNatList(n)
}

lemma NatSumLemma(l: List, n: int)
  requires isNatList(l) && n == sum(l)
  ensures n >= 0 
{
  match l
    case Nil =>
      // Discharged Automatically
    case Link(data, next) => {
      // Apply Inductive Hypothesis
      NatSumLemma(next, sum(next));
      // Check what known by Dafny
      assert data >= 0;
    }
}

Here, NatSumLemma proves a useful property between sum() and isNatList() (i.e. that isNatList(l) ==> (sum(l) >= 0)). The use of a ghost method for encoding lemmas and theorems is standard in Dafny with recursion employed for induction (typically, structural induction). Case analysis is performed using match statements and non-inductive cases are often discharged automatically. The verifier must also have complete access to the contents of a function or predicate in order to unroll them as necessary. This has implications when used in conjunction with access modifiers. Specifically, hiding the contents of a function using the protected modifier can limit what properties can be established about it.

See also

References

  1. ^ Smans, Jan; Jacobs, Bart; Piessens, Frank (2009). Implicit Dynamic Frames: Combining Dynamic Frames and Separation Logic (PDF). Proceedings of the Conference on European Conference on Object Oriented Programming. pp. 148–172. doi:10.1007/978-3-642-03013-0_8.
  2. ^ Leino, Rustan (2010). Dafny: An Automatic Program Verifier for Functional Correctness. Proceedings of the Conference on Logic for Programming, Artificial Intelligence, and Reasoning. pp. 348–370. doi:10.1007/978-3-642-17511-4_20.
  3. ^ Leino, Rustan; Monahan, Rosemary (2010). Dafny Meets the Verification Benchmarks Challenge (PDF). International Conference on Verified Software: Theories, Tools, and Experiments. pp. 112–116. doi:10.1007/978-3-642-15057-9_8.
  4. ^ Klebanov, Vladimir; et al. (2011). The 1st Verified Software Competition: Experience Report. Proceedings of the Conference on Formal Methods. pp. 154–168. CiteSeerX 10.1.1.221.6890. doi:10.1007/978-3-642-21437-0_14.
  5. ^ Bormer, Thorsten; et al. (2011). The COST IC0701 Verification Competition 2011. Proceedings of the Conference on Formal Verification of Object-Oriented Software. pp. 3–21. CiteSeerX 10.1.1.396.6170. doi:10.1007/978-3-642-31762-0_2.
  6. ^ Huisman, Marieke; Klebanov, Vladimir; Monahan, Rosemary (2015). "VerifyThis 2012" (PDF). International Journal on Software Tools for Technology Transfer. 17 (6): 647–657. doi:10.1007/s10009-015-0396-8. S2CID 14301377.
  7. ^ "Z3 Homepage". GitHub. 2019-02-07.
  8. ^ de Moura, Leonardo; Bjørner, Nikolaj (2008). Z3: An Efficient SMT Solver. Proceedings of the Conference on Tools and Algorithms for the Construction and Analysis. pp. 337–340. doi:10.1007/978-3-540-78800-3_24.
  9. ^ "Dafny Programming Language". 2022-07-14.

Further reading

  • Meyer, Bertrand; Nordio, Martin, eds. (2012). Tools for Practical Software Verification: International Summer School, LASER 2011, Elba Island, Italy, Revised Tutorial Lectures. Springer. ISBN 978-3642357459.
  • Sitnikovski, Boro (2022). Introducing Software Verification with Dafny Language: Proving Program Correctness. Apress. ISBN 978-1484279779.

Read other articles:

Kusu-tanah Raffray[1] Peroryctes raffrayana Status konservasiRisiko rendahIUCN16711 TaksonomiKerajaanAnimaliaFilumChordataKelasMammaliaOrdoPeramelemorphiaFamiliPeramelidaeGenusPeroryctesSpesiesPeroryctes raffrayana DistribusiRaffray's bandicoot range lbs Kusu-tanah Raffray ( Peroryctes raffrayana ) adalah spesies marsupial dalam keluarga Peroryctidae . Ia dijumpai di Indonesia dan Papua Nugini. Habitat aslinya adalah hutan kering subtropis atau tropis. [3] Ia dikenal sebagai paka…

Katedral Penyelamat Mahakudus, Angra do Heroísmo Ini adalah daftar katedral di Azores: Katolik Katedral Gereja Katolik di Azores:[1] Katedral Penyelamat Mahakudus, Angra do Heroísmo Lihat juga Gereja Katolik Roma Gereja Katolik di Azores Gereja Katolik di Portugal Daftar katedral Referensi ^ Noé, Paula (2002). SIPA, ed. Sé de Angra do Heroísmo/Catedral do Santíssimo Salvador (n.PT071901160028) (dalam bahasa Portugis). Lisbon, Portugal: SIPA – Sistema de Informação para o Patrim…

إمره بلوز أوغلو (بالتركية: Emre Belözoğlu)‏  معلومات شخصية الميلاد 7 سبتمبر 1980 (العمر 43 سنة)إسطنبول  الطول 1.70 م (5 قدم 7 بوصة) مركز اللعب لاعب وسط الجنسية تركي معلومات النادي النادي الحالي إسطنبول باشاكشهير (مدرب) مسيرة الشباب سنوات فريق 1992–1996 غلطة سراي 1992–1996 غلطة سراي ا…

American politician For other people named Edward Wade, see Edward Wade (disambiguation). Edward WadeMember of the U.S. House of Representativesfrom Ohio's 19th districtIn officeMarch 4, 1853 – March 3, 1861Preceded byEben NewtonSucceeded byAlbert G. Riddle Personal detailsBorn(1802-11-22)November 22, 1802West Springfield, MassachusettsDiedAugust 13, 1866(1866-08-13) (aged 63)East Cleveland, OhioPolitical partyRepublican Edward Wade (November 22, 1802 – August 13, 1…

Pulau Grand Bé, dilihat dari tembok Saint-Malo Grand Bé merupakan sebuah pulau gelombang di dekat Saint-Malo, Prancis. Terletak di mulut Sungai Rance, beberapa ratus meter dari tembok Saint-Malo. Ketika gelombang surut pulau dapat dicapai dengan berjalan kaki dari pantai Bon-Secours. Di pulau itu terdapat sisa-sisa benteng masa lampau. François-René de Chateaubriand, seorang penulis Prancis dari Saint-Malo, dimakamkan di pulau itu, pada sebuah makam yang menghadap ke laut. Lihat pula Petit B…

كأس هولندا 2011–12 تفاصيل الموسم كأس هولندا  النسخة 94  البلد هولندا  التاريخ بداية:24 أغسطس 2011  نهاية:8 أبريل 2012  المنظم الاتحاد الملكي الهولندي لكرة القدم  البطل بي إس في آيندهوفن  مباريات ملعوبة 91   عدد المشاركين 92   الموقع الرسمي الموقع الرسمي  كأس هولن…

Community Shield FA 2002TurnamenCommunity Shield FA Arsenal Liverpool 1 0 Tanggal11 Agustus 2002StadionStadion Millennium, Cardiff← 2001 2003 → Community Shield FA 2002 adalah pertandingan sepak bola antara Arsenal dan Liverpool yang diselenggarakan pada 11 Agustus 2002 di Stadion Millennium, Cardiff. Pertandingan ini merupakan pertandingan ke-80 dari penyelenggaraan Community Shield FA. Pertandingan ini dimenangkan oleh Arsenal dengan skor 1–0.[1] Pertandingan Arsenal v Li…

Paul Joseph WatsonWatson pada tahun 2013Informasi pribadiLahir24 Mei 1982 (umur 41)[1]Jessop Hospital, Sheffield, South Yorkshire, Inggris[1]PekerjaanPenulis, penyunting, penyiar YouTubeInformasi YouTubeNama samaranPJW, Paul J. Watson, PropagandaMatrix (dulunya), Anything GoesKanal PrisonPlanetLive Tahun aktif2011–sekarang (sebagaiYouTuber)GenreKritisisme politikTeori konspirasiKonservatisme Amerika SerikatTotal tayang413 jutaArtis terkait Alex Jones (Infowars) C…

John Lawrence Ashbery Premio Pulitzer nel 1976 John Lawrence Ashbery (Rochester, 28 luglio 1927 – Hudson, 3 settembre 2017) è stato un poeta statunitense. Indice 1 Biografia 2 Raccolte poetiche 3 Note 4 Altri progetti 5 Collegamenti esterni Biografia Considerato il massimo esponente della scuola poetica newyorkese, svolge la propria opera artistica principalmente in un ambito meditativo, nel quale riesce a far confluire linguaggi e stili contemporanei, sovente derivati dal mondo dei mass-medi…

Renang padaPekan Olahraga Nasional XIX Gaya bebas 50 m putra putri 100 m putra putri 200 m putra putri 400 m putra putri 800 m putra putri 1500 m putra putri Gaya punggung 50 m putra putri 100 m putra putri 200 m putra putri Gaya dada 50 m putra putri 100 m putra putri 200 m putra putri Gaya kupu-kupu 50 m putra putri 100 m putra putri 200 m putra putri Gaya ganti perorangan 200 m putra putri 400 m putra putri Gaya bebas estafet 4×100 m putra putri 4×200 m putra putri Gaya ganti estafet 4×100…

For related races, see 1916 United States gubernatorial elections. 1916 Utah gubernatorial election ← 1912 November 7, 1916 1920 →   Nominee Simon Bamberger Nephi L. Morris Party Democratic Republican Popular vote 78,502 59,529 Percentage 55.12% 41.80% Governor before election William Spry Republican Elected Governor Simon Bamberger Democratic Elections in Utah Federal government Presidential elections 1896 1900 1904 1908 1912 1916 1920 1924 1928 1932 1936 1940 19…

Major League Baseball team season 1994 Los Angeles DodgersLeagueNational LeagueDivisionWestBallparkDodger StadiumCityLos AngelesRecord58–56 (.509)Divisional place1stOwnersPeter O'MalleyGeneral managersFred ClaireManagersTommy LasordaTelevisionKTLA (5)RadioKABC Vin Scully, Ross Porter, Rick Monday KWKW Jaime Jarrín, René Cárdenas ← 1993 Seasons 1995 → The 1994 Los Angeles Dodgers season was the 105th for the franchise in Major League Baseball and their 37th season …

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方)出典検索?: コルク – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL(2017年4月) コルクを打ち抜いて作った瓶の栓 コルク(木栓、蘭&…

Запрос «Гусь» перенаправляется сюда; для терминов «Гусь» и «Гуси» см. также другие значения. Гуси Домашний гусь (Эмденский) Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:Хордовые…

Wu XiaTakeshi Kaneshiro dan Donnie Yen dalam poster film Wuxia [2011]SutradaraPeter ChanProduserPeter ChanPemeranDonnie YenTakeshi KaneshiroTang WeiKara HuiSinematograferJake PollockTanggal rilis Agustus 2011 (2011-08) NegaraChinaHong KongBahasaMandarinAnggaranAS$ 20juta Wu Xia adalah sebuah film Mandarin tahun 2011 yang disutradarai Peter Chan. Film ini akan dibintangi oleh Donnie Yen, Takeshi Kaneshiro, Tang Wei. Film ini rencananya akan dirilis bulan agustus 2011. Alur Liu Jin Xi (Donnie…

Tanjong Dawai redirects here. For the state constituency, see Tanjong Dawai (state constituency). This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Tanjung Dawai – news · newspapers · books · scholar · JSTOR (February 2016) (Learn how and when to remove this message) Tanjung Dawai in Kuala Muda District Tanjung Dawai is a small to…

هنودمعلومات عامةنسبة التسمية الهند التعداد الكليالتعداد قرابة 1.21 مليار[1][2]تعداد الهند عام 2011ق. 1.32 مليار[3]تقديرات عام 2017ق. 30.8 مليون[4]مناطق الوجود المميزةبلد الأصل الهند البلد الهند  الهند نيبال 4,000,000[5] الولايات المتحدة 3,982,398[6] الإمارا…

Location of Goliad County in Texas This is a list of the National Register of Historic Places listings in Goliad County, Texas. This is intended to be a complete list of properties and districts listed on the National Register of Historic Places in Goliad County, Texas. There are one National Historic Landmark, five districts, and seven other individually listed properties on the National Register in the county. Among these, either among individual properties or contained within districts, are t…

Major road in San Francisco This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Octavia Boulevard – news · newspapers · books · scholar · JSTOR (September 2019) (…

Airport serving the San Francisco Castro Area, California, United States Oakland International Airport and Oakland Airport redirect here. For other uses, see Oakland Airport (disambiguation). Not to be confused with San Francisco International Airport. San Francisco Bay Oakland International AirportIATA: OAKICAO: KOAKFAA LID: OAKWMO: 72493SummaryAirport typePublicOwner/OperatorPort of OaklandServesEast Bay, San Francisco Bay AreaLocationOakland, CaliforniaOpenedSeptember 17, 1927; 9…

Kembali kehalaman sebelumnya