Dafny

Dafny

Paradigm	Imperative,functional
Designed by	K. Rustan M. Leino
Developer	Microsoft Research,AWS
First appeared	2009(2009)
Stable release	3.7.2 / July 14, 2022(2022-07-14)
Typing discipline	Static, strong, safe
License	MIT License
Filename extensions	.dfy
Website	dafny.org

Dafnyis animperativeandfunctionalcompiled languagethat compiles to otherprogramming languages,such asC#,Java,JavaScript,GoandPython.It supportsformal specificationthroughpreconditions,postconditions,loop invariants,loop variants,termination specifications and read/write framing specifications. The language combines ideas from thefunctionalandimperativeparadigms; it includes support forobject-oriented programming.Features includegeneric classes,dynamic allocation,inductive datatypesand a variation ofseparation logicknown asimplicit dynamic framesfor reasoning about side effects.Dafny was created by Rustan Leino atMicrosoft Researchafter his previous work on developing ESC/Modula-3,ESC/Java,and Spec#.

Dafny is widely used in teachingbecause it provides a simple, integrated introduction to formal specification and verification; it is regularly featured in software verification competitions (e.g. VSTTE'08,VSCOMP'10,COST'11,and VerifyThis'12).

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 ofHoare logic.

Dafny builds on the Boogieintermediate languagewhich uses theZ3 automated theorem proverfor discharging proof obligations.

Data types

Dafny provides methods for implementation which may haveside-effectsand functions for use in specification which arepure.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 themodifiesclause. Dafny also provides a range ofimmutablecollection types including: sequences (e.g.seq<int>), sets (e.g.set<int>), maps (map<int,int>), tuples, inductive datatypes andmutablearrays (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.

methodmax(arr:array<int>)returns(max:int)
// Array must have at least one element
requiresarr.Length>0
// Return cannot be smaller than any element in array
ensuresforallj:int::j>=0&&j<arr.Length==>max>=arr[j]
// Return must match some element in array
ensuresexistsj:int::j>=0&&j<arr.Length&&max==arr[j]
{
max:=arr[0];
vari:int:=1;
//
while(i<arr.Length)
// Index at most arr.Length (needed to show i==arr.Length after loop)
invarianti<=arr.Length
// No element seen so far larger than max
invariantforallj:int::j>=0&&j<i==>max>=arr[j]
// Some element seen so far matches max
invariantexistsj:int::j>=0&&j<i&&max==arr[j]
// arr.Length - i decreases at every step and is lower-bounded by 0
decreasesarr.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 therequiresandensuresclauses (respectively). Likewise, the loop invariant and loop variant are given through theinvariantanddecreasesclauses (respectively).

Loop invariants

The treatment of loop invariants in Dafny differs from traditionalHoare 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:

methodsumAndZero(arr:array<int>)returns(sum:nat)
requiresforalli::0<=i<arr.Length==>arr[i]>=0
modifiesarr
{
vari: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]) >= 0holds at the assignment. From the precondition, intuitively,forall i:: 0 <= i < arr.Length ==> arr[i] >= 0holds in the loop sincearr[i]:= arr[i];is aNOP.However, this assignment causes Dafny to treatarras 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 assignmentarr[i]:= arr[i];;or (b) add the loop invariantinvariant forall i:: 0 <= i < arr.Length ==> arr[i] >= 0

Dafny additionally employs limitedstatic analysisto infer simple loop invariants where possible. In the example above, it would seem that the loop invariantinvariant i >= 0is also required as variableiis 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 aproof assistant.Although proofs of simple properties within afunctionormethod(as shown above) are not unusual for tools of this nature, Dafny also allows the proof of properties between onefunctionand another. As is common for aproof assistant,such proofs are ofteninductivein nature. Dafny is perhaps unusual in employing method invocation as a mechanism for applying the inductive hypothesis. The following illustrates:

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

functionsum(l:List):int{
matchl
caseNil=>0
caseLink(d,n)=>d+sum(n)
}

predicateisNatList(l:List){
matchl
caseNil=>true
caseLink(d,n)=>d>=0&&isNatList(n)
}

lemmaNatSumLemma(l:List,n:int)
requiresisNatList(l)&&n==sum(l)
ensuresn>=0
{
matchl
caseNil=>
// Discharged Automatically
caseLink(data,next)=>{
// Apply Inductive Hypothesis
NatSumLemma(next,sum(next));
// Check what known by Dafny
assertdata>=0;
}
}

Here,NatSumLemmaproves a useful propertybetweensum()andisNatList()(i.e. thatisNatList(l) ==> (sum(l) >= 0)). The use of aghost methodfor encodinglemmas and theoremsis standard in Dafny with recursion employed for induction (typically,structural induction).Case analysisis performed usingmatchstatements and non-inductive cases are often discharged automatically. The verifier must also have complete access to the contents of afunctionorpredicatein order to unroll them as necessary. This has implications when used in conjunction withaccess modifiers.Specifically, hiding the contents of afunctionusing theprotectedmodifier can limit what properties can be established about it.

See also

• Design by contract

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.ISBN978-3642357459.
• Sitnikovski, Boro (2022).Introducing Software Verification with Dafny Language: Proving Program Correctness.Apress.ISBN978-1484279779.

External links

• Dafny: A Language and Program Verifier for Functional Correctness - Microsoft Research
• GitHub - dafny-lang/dafny: Dafny is a verification-aware programming language