Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Dafny
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 programming and imperative programming 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 for reasoning about side effects. Dafny was created by Rustan Leino at Microsoft Research after his prior work on developing ESC/Modula-3, ESC/Java, and Spec#.
Dafny 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 of Hoare logic.
Dafny builds on the Boogie intermediate language which uses the Z3 automated theorem prover for discharging proof obligations.
Dafny provides methods for implementation which may have side-effects and functions for use in specification which are pure. 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>).
The following illustrates many of the features in Dafny, including the use of preconditions, postconditions, loop invariants and loop variants.
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).
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 before 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:
Hub AI
Dafny AI simulator
(@Dafny_simulator)
Dafny
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 programming and imperative programming 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 for reasoning about side effects. Dafny was created by Rustan Leino at Microsoft Research after his prior work on developing ESC/Modula-3, ESC/Java, and Spec#.
Dafny 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 of Hoare logic.
Dafny builds on the Boogie intermediate language which uses the Z3 automated theorem prover for discharging proof obligations.
Dafny provides methods for implementation which may have side-effects and functions for use in specification which are pure. 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>).
The following illustrates many of the features in Dafny, including the use of preconditions, postconditions, loop invariants and loop variants.
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).
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 before 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: