Dafny Reference Manual

The dafny-lang community

Development version

Abstract: This is the Dafny reference manual; it describes the Dafny programming language and how to use the Dafny verification system. Parts of this manual are more tutorial in nature in order to help the user understand how to do proofs with Dafny.

(Link to current document as html)

1. Introduction

Dafny [@Leino:Dafny:LPAR16] is a programming language with built-in specification constructs, so that verifying a program’s correctness with respect to those specifications is a natural part of writing software. The Dafny static program verifier can be used to verify the functional correctness of programs. This document is a reference manual for the programming language and a user guide for the dafny tool that performs verification and compilation to an executable form.

The Dafny programming language is designed to support the static verification of programs. It is imperative, sequential, supports generic classes, inheritance and abstraction, methods and functions, dynamic allocation, inductive and coinductive datatypes, and specification constructs. The specifications include pre- and postconditions, frame specifications (read and write sets), and termination metrics. To further support specifications, the language also offers updatable ghost variables, recursive functions, and types like sets and sequences. Specifications and ghost constructs are used only during verification; the compiler omits them from the executable code.

The dafny verifier is run as part of the compiler. As such, a programmer interacts with it in much the same way as with the static type checker—when the tool produces errors, the programmer responds by changing the program’s type declarations, specifications, and statements.

(This document typically uses “Dafny” to refer to the programming language and dafny to refer to the software tool that verifies and compiles programs in the Dafny language.)

The easiest way to try out the Dafny language is to download the supporting tools and documentation and run dafny on your machine as you follow along with the Dafny tutorial. The dafny tool can be run from the command line (on Linux, MacOS, Windows or other platforms) or from IDEs such as emacs and VSCode, which can provide syntax highlighting and code manipulation capabilities.

The verifier is powered by Boogie [@Boogie:Architecture;@Leino:Boogie2-RefMan;@LeinoRuemmer:Boogie2] and Z3 [@deMouraBjorner:Z3:overview].

From verified programs, the dafny compiler can produce code for a number of different backends: the .NET platform via intermediate C# files, Java, Javascript, Go, and C++. Each language provides a basic Foreign Function Interface (through uses of :extern) and a supporting runtime library.

This reference manual for the Dafny verification system is based on the following references: [@Leino:Dafny:LPAR16], [@MSR:dafny:main], [@LEINO:Dafny:Calc], [@LEINO:Dafny:Coinduction], Co-induction Simply.

The main part of the reference manual is in top down order except for an initial section that deals with the lowest level constructs.

The details of using (and contributing to) the dafny tool are described in the User Guide (Section 13).

1.1. Dafny 4.0

The most recent major version of the Dafny language is Dafny 4.0, released in February 2023. It has some backwards incompatibilities with Dafny 3, as decribed in the migration guide.

The user documentation has been expanded with more examples, a FAQ, and an error explanation catalog. There is even a new book, Program Proofs by Dafny designer Rustan Leino.

The IDE now has a framework for showing error explanation information and corresponding quick fixes are being added, with refactoring operations on the horizon.

More details of 4.0 functionality are described in the release notes.

1.2. Dafny Example

To give a flavor of Dafny, here is the solution to a competition problem.

// VSComp 2010, problem 3, find a 0 in a linked list and return
// how many nodes were skipped until the first 0 (or end-of-list)
// was found.
// Rustan Leino, 18 August 2010.
//
// The difficulty in this problem lies in specifying what the
// return value 'r' denotes and in proving that the program
// terminates.  Both of these are addressed by declaring a ghost
// field 'List' in each linked-list node, abstractly representing
// the linked-list elements from the node to the end of the linked
// list.  The specification can now talk about that sequence of
// elements and can use 'r' as an index into the sequence, and
// termination can be proved from the fact that all sequences in
// Dafny are finite.
//
// We only want to deal with linked lists whose 'List' field is
// properly filled in (which can only happen in an acyclic list,
// for example).  To that end, the standard idiom in Dafny is to
// declare a predicate 'Valid()' that is true of an object when
// the data structure representing that object's abstract value
// is properly formed.  The definition of 'Valid()' is what one
// intuitively would think of as the ''object invariant'', and
// it is mentioned explicitly in method pre- and postconditions.
//
// As part of this standard idiom, one also declares a ghost
// variable 'Repr' that is maintained as the set of objects that
// make up the representation of the aggregate object--in this
// case, the Node itself and all its successors.
module {:options "--function-syntax:4"} M {
class Node {
  ghost var List: seq<int>
  ghost var Repr: set<Node>
  var head: int
  var next: Node? // Node? means a Node value or null

  ghost predicate Valid()
    reads this, Repr
  {
    this in Repr &&
    1 <= |List| && List[0] == head &&
    (next == null ==> |List| == 1) &&
    (next != null ==>
      next in Repr && next.Repr <= Repr && this !in next.Repr &&
      next.Valid() && next.List == List[1..])
  }

  static method Cons(x: int, tail: Node?) returns (n: Node)
    requires tail == null || tail.Valid()
    ensures n.Valid()
    ensures if tail == null then n.List == [x]
                            else n.List == [x] + tail.List
  {
    n := new Node;
    n.head, n.next := x, tail;
    if (tail == null) {
      n.List := [x];
      n.Repr := {n};
    } else {
      n.List := [x] + tail.List;
      n.Repr := {n} + tail.Repr;
    }
  }
}

method Search(ll: Node?) returns (r: int)
  requires ll == null || ll.Valid()
  ensures ll == null ==> r == 0
  ensures ll != null ==>
            0 <= r && r <= |ll.List| &&
            (r < |ll.List| ==>
              ll.List[r] == 0 && 0 !in ll.List[..r]) &&
            (r == |ll.List| ==> 0 !in ll.List)
{
  if (ll == null) {
    r := 0;
  } else {
    var jj,i := ll,0;
    while (jj != null && jj.head != 0)
      invariant jj != null ==>
            jj.Valid() &&
            i + |jj.List| == |ll.List| &&
            ll.List[i..] == jj.List
      invariant jj == null ==> i == |ll.List|
      invariant 0 !in ll.List[..i]
      decreases |ll.List| - i
    {
      jj := jj.next;
      i := i + 1;
    }
    r := i;
  }
}

method Main()
{
  var list: Node? := null;
  list := list.Cons(0, list);
  list := list.Cons(5, list);
  list := list.Cons(0, list);
  list := list.Cons(8, list);
  var r := Search(list);
  print "Search returns ", r, "\n";
  assert r == 1;
}
}

2. Lexical and Low Level Grammar

As with most languages, Dafny syntax is defined in two levels. First the stream of input characters is broken up into tokens. Then these tokens are parsed using the Dafny grammar.

The Dafny grammar is designed as an attributed grammar, which is a conventional BNF-style set of productions, but in which the productions can have arguments. The arguments control some alternatives within the productions, such as whether an alternative is allowed or not in a specific context. These arguments allow for a more compact and understandable grammar.

The precise, technical details of the grammar are presented together in Section 17. The expository parts of this manual present the language structure less formally. Throughout this document there are embedded hyperlinks to relevant grammar sections, marked as grammar.

2.1. Dafny Input

Dafny source code files are readable text encoded in UTF-8. All program text other than the contents of comments, character, string and verbatim string literals consists of printable and white-space ASCII characters, that is, ASCII characters in the range ! to ~, plus space, tab, carriage return and newline (ASCII 9, 10, 13, 32) characters. (In some past versions of Dafny, non-ASCII, unicode representations of some mathematical symbols were permitted in Dafny source text; these are no longer recognized.)

String and character literals and comments may contain any unicode character, either directly or as an escape sequence.

2.2. Tokens and whitespace

The characters used in a Dafny program fall into four groups:

Except for string and character literals, each Dafny token consists of a sequence of consecutive characters from just one of these groups, excluding white-space. White-space is ignored except that it separates tokens and except in the bodies of character and string literals.

A sequence of alphanumeric characters (with no preceding or following additional alphanumeric characters) is a single token. This is true even if the token is syntactically or semantically invalid and the sequence could be separated into more than one valid token. For example, assert56 is one identifier token, not a keyword assert followed by a number; ifb!=0 begins with the token ifb and not with the keyword if and token b; 0xFFFFZZ is an illegal token, not a valid hex number 0xFFFF followed by an identifier ZZ. White-space must be used to separate two such tokens in a program.

Somewhat differently, operator tokens need not be separated. Only specific sequences of operator characters are recognized and these are somewhat context-sensitive. For example, in seq<set<int>>, the grammar knows that >> is two individual > tokens terminating the nested type parameter lists; the right shift operator >> would never be valid here. Similarly, the sequence ==> is always one token; even if it were invalid in its context, separating it into == and > would always still be invalid.

In summary, except for required white space between alphanumeric tokens, adding or removing white space between tokens can never result in changing the meaning of a Dafny program. For most of this document, we consider Dafny programs as sequences of tokens.

2.3. Character Classes

This section defines character classes used later in the token definitions. In this section

name description
letter ASCII upper or lower case letter; no unicode characters
digit base-ten digit (“0123456789”)
posDigit digits, excluding 0 (“123456789”)
posDigitFrom2 digits excluding 0 and 1 (“23456789”)
hexdigit a normal hex digit (“0123456789abcdefABCDEF”)
special `?_”
cr carriage return character (ASCII 10)
lf line feed character (ASCII 13)
tab tab character (ASCII 9)
space space character (ASCII 32)
   
nondigitIdChar characters allowed in an identifier, except digits (letter + special)
idchar characters allowed in an identifier (nondigitIdChar + digits)
nonidchar characters not in identifiers (ANY - idchar)
charChar characters allowed in a character constant (ANY - ‘'’ - ‘\’ - cr - lf)
stringChar characters allowed in a string constant (ANY - ‘”’ - ‘\’ - cr - lf)
verbatimStringChar characters allowed in a verbatim string constant (ANY - ‘”’)

The special characters are the characters in addition to alphanumeric characters that are allowed to appear in a Dafny identifier. These are

A nonidchar is any character except those that can be used in an identifier. Here the scanner generator will interpret ANY as any unicode character. However, nonidchar is used only to mark the end of the !in token; in this context any character other than whitespace or printable ASCII will trigger a subsequent scanning or parsing error.

2.4. Comments

Comments are in two forms.

A comment is identified as a token during the tokenization of input text and is then discarded for the purpose of interpreting the Dafny program. (It is retained to enable auto-formatting and provide accurate source locations for error messages.) Thus comments are token separators: a/*x*/b becomes two tokens a and b.

Comments may be nested, but note that the nesting of multi-line comments is behavior that is different from most programming languages. In Dafny, 

method m() {
  /* comment
     /* nested comment
     */
     rest of outer comment
  */
}

is permitted; this feature is convenient for commenting out blocks of program statements that already have multi-line comments within them. Other than looking for end-of-comment delimiters, the contents of a comment are not interpreted. Comments may contain any characters.

Note that the nesting is not fool-proof. In 

method m() {
  /* var i: int;
     // */ line comment
     var j: int;
  */
}

and 

method m() {
  /* var i: int;
     var s: string := "a*/b";
     var j: int;
   */
}

the */ inside the line comment and the string are seen as the end of the outer comment, leaving trailing text that will provoke parsing errors.

2.5. Documentation comments

Like many other languages, Dafny permits documentation comments in a program file. Such comments contain natural language descriptions of program elements and may be used by IDEs and documentation generation tools to present information to users.

In Dafny programs.

Here are examples: 

const c0 := 8
/** docstring about c0 */

/** docstring about c1 */
const c1 := 8

/** first line of docstring */
const c2 := 8
/** second line of docstring */

const c3 := 8
// docstring about c3
// on two lines

const c4 := 8

// just a comment


// just a comment
const c5 := 8

Datatype constructors may also have comments: 

datatype T =  // Docstring for T
  | A(x: int,
      y: int) // Docstring for A
  | B()       /* Docstring for B */ |
    C()       // Docstring for C

/** Docstring for T0*/
datatype T0 =
  | /** Docstring for A */
    A(x: int,
      y: int)
  | /** Docstring for B */
    B()
  | /** Docstring for C */
    C()

As can export declarations: 

module M {
const A: int
const B: int
const C: int
const D: int

export
  // This is the eponymous export set intended for most clients
  provides A, B, C


export Friends extends M
  // This export set is for clients who need to know more of the
  // details of the module's definitions.
  reveals A
  provides D
}

2.6. Tokens (grammar)

The Dafny tokens are defined in this section.

2.6.1. Reserved Words

Dafny has a set of reserved words that may not be used as identifiers of user-defined entities. These are listed here.

In particular note that

2.6.2. Identifiers

In general, an ident token (an identifier) is a sequence of idchar characters where the first character is a nondigitIdChar. However tokens that fit this pattern are not identifiers if they look like a character literal or a reserved word (including array or bit-vector type tokens). Also, ident tokens that begin with an _ are not permitted as user identifiers.

2.6.3. Digits

A digits token is a sequence of decimal digits (digit), possibly interspersed with underscores for readability (but not beginning or ending with an underscore). Example: 1_234_567.

A hexdigits token denotes a hexadecimal constant, and is a sequence of hexadecimal digits (hexdigit) prefaced by 0x and possibly interspersed with underscores for readability (but not beginning or ending with an underscore). Example: 0xffff_ffff.

A decimaldigits token is a decimal fraction constant, possibly interspersed with underscores for readability (but not beginning or ending with an underscore). It has digits both before and after a single period (.) character. There is no syntax for floating point numbers with exponents. Example: 123_456.789_123.

2.6.4. Escaped Character

The escapedChar token is a multi-character sequence that denotes a non-printable or non-ASCII character. Such tokens begin with a backslash characcter (\) and denote a single- or double-quote character, backslash, null, new line, carriage return, tab, or a Unicode character with given hexadecimal representation. Which Unicode escape form is allowed depends on the value of the --unicode-char option.

If --unicode-char:false is stipulated, \uXXXX escapes can be used to specify any UTF-16 code unit.

If --unicode-char:true is stipulated, \U{X..X} escapes can be used to specify any Unicode scalar value. There must be at least one hex digit in between the braces, and at most six. Surrogate code points are not allowed. The hex digits may be interspersed with underscores for readability (but not beginning or ending with an underscore), as in \U{1_F680}. The braces are part of the required character sequence.

Note that although Unicode letters are not allowed in Dafny identifiers, Dafny does support Unicode in its character, string, and verbatim strings constants and in its comments.

2.6.5. Character Constant Token

The charToken token denotes a character constant. It is either a charChar or an escapedChar enclosed in single quotes.

2.6.6. String Constant Token

A stringToken denotes a string constant. It consists of a sequence of stringChar and escapedChar characters enclosed in double quotes.

A verbatimStringToken token also denotes a string constant. It is a sequence of any verbatimStringChar characters (which includes newline characters), enclosed between @" and ", except that two successive double quotes represent one quote character inside the string. This is the mechanism for escaping a double quote character, which is the only character needing escaping in a verbatim string. Within a verbatim string constant, a backslash character represents itself and is not the first character of an escapedChar.

2.6.7. Ellipsis

The ellipsisToken is the character sequence ... and is typically used to designate something missing that will later be inserted through refinement or is already present in a parent declaration.

2.7. Low Level Grammar Productions

2.7.1. Identifier Variations

2.7.1.1. Identifier

A basic ordinary identifier is just an ident token.

It may be followed by a sequence of suffixes to denote compound entities. Each suffix is a dot (.) and another token, which may be

Note that

2.7.1.2. No-underscore-identifier

A NoUSIdent is an identifier except that identifiers with a leading underscore are not allowed. The names of user-defined entities are required to be NoUSIdents or, in some contexts, a digits. We introduce more mnemonic names for these below (e.g. ClassName).

A no-underscore-identifier is required for the following:

A variation, a no-underscore-identifier or a digits, is allowed for

All user-declared names do not start with underscores, but there are internally generated names that a user program might use that begin with an underscore or are just an underscore.

2.7.1.3. Wild identifier

A wild identifier is a no-underscore-identifier except that the singleton _ is allowed. The _ is replaced conceptually by a unique identifier distinct from all other identifiers in the program. A _ is used when an identifier is needed, but its content is discarded. Such identifiers are not used in expressions.

Wild identifiers may be used in these contexts:

2.7.2. Qualified Names

A qualified name starts with the name of a top-level entity and then is followed by zero or more DotSuffixs which denote a component. Examples:

The identifiers and dots are separate tokens and so may optionally be separated by whitespace.

2.7.3. Identifier-Type Combinations

Identifiers are typically declared in combination with a type, as in 

var i: int

However, Dafny infers types in many circumstances, and in those, the type can be omitted. The type is required for field declarations and formal parameters of methods, functions and constructors (because there is no initializer). It may be omitted (if the type can be inferred) for local variable declarations, pattern matching variables, quantifiers,

Similarly, there are circumstances in which the identifier name is not needed, because it is not used. This is allowed in defining algebraic datatypes.

In some other situations a wild identifier can be used, as described above.

2.7.4. Quantifier Domains (grammar)

Several Dafny constructs bind one or more variables to a range of possible values. For example, the quantifier forall x: nat | x <= 5 :: x * x <= 25 has the meaning “for all integers x between 0 and 5 inclusive, the square of x is at most 25”. Similarly, the set comprehension set x: nat | x <= 5 :: f(x) can be read as “the set containing the result of applying f to x, for each integer x from 0 to 5 inclusive”. The common syntax that specifies the bound variables and what values they take on is known as the quantifier domain; in the previous examples this is x: nat | x <= 5, which binds the variable x to the values 0, 1, 2, 3, 4, and 5.

Here are some more examples.

A quantifier domain declares one or more quantified variables, separated by commas. Each variable declaration can be nothing more than a variable name, but it may also include any of three optional elements:

  1. The optional syntax : T declares the type of the quantified variable. If not provided, it will be inferred from context.

  2. The optional syntax <- C attaches a collection expression C as a quantified variable domain. Here a collection is any value of a type that supports the in operator, namely sets, multisets, maps, and sequences. The domain restricts the bindings to the elements of the collection: x <- C implies x in C. The example above can also be expressed as var c := [0, 1, 2, 3, 4, 5]; forall x <- c :: x * x <= 25.

  3. The optional syntax | E attaches a boolean expression E as a quantified variable range, which restricts the bindings to values that satisfy this expression. In the example above x <= 5 is the range attached to the x variable declaration.

Note that a variable’s domain expression may reference any variable declared before it, and a variable’s range expression may reference the attached variable (and usually does) and any variable declared before it. For example, in the quantifier domain i | 0 <= i < |s|, y <- s[i] | i < y, the expression s[i] is always well-formed because the range attached to i ensures i is a valid index in the sequence s.

Allowing per-variable ranges is not fully backwards compatible, and so it is not yet allowed by default; the --quantifier-syntax:4 option needs to be provided to enable this feature (See Section 13.9.5).

2.7.5. Numeric Literals (grammar)

Integer and bitvector literals may be expressed in either decimal or hexadecimal (digits or hexdigits).

Real number literals are written as decimal fractions (decimaldigits).

3. Programs (grammar)

At the top level, a Dafny program (stored as files with extension .dfy) is a set of declarations. The declarations introduce (module-level) constants, methods, functions, lemmas, types (classes, traits, inductive and coinductive datatypes, newtypes, type synonyms, abstract types, and iterators) and modules, where the order of introduction is irrelevant. Some types, notably classes, also may contain a set of declarations, introducing fields, methods, and functions.

When asked to compile a program, Dafny looks for the existence of a Main() method. If a legal Main() method is found, the compiler will emit an executable appropriate to the target language; otherwise it will emit a library or individual files. The conditions for a legal Main() method are described in the User Guide (Section 3.4). If there is more than one Main(), Dafny will emit an error message.

An invocation of Dafny may specify a number of source files. Each Dafny file follows the grammar of the Dafny non-terminal.

A file consists of

3.1. Include Directives (grammar)

Examples: 

include "MyProgram.dfy"
include @"/home/me/MyFile.dfy"

Include directives have the form "include" stringToken where the string token is either a normal string token or a verbatim string token. The stringToken is interpreted as the name of a file that will be included in the Dafny source. These included files also obey the Dafny grammar. Dafny parses and processes the transitive closure of the original source files and all the included files, but will not invoke the verifier on the included files unless they have been listed explicitly on the command line or the --verify-included-files option is specified.

The file name may be a path using the customary /, ., and .. punctuation. The interpretation of the name (e.g., case-sensitivity) will depend on the underlying operating system. A path not beginning with / is looked up in the underlying file system relative to the location of the file in which the include directive is stated. Paths beginning with a device designator (e.g., C:) are only permitted on Windows systems. Better style advocates using relative paths in include directives so that groups of files may be moved as a whole to a new location.

Paths of files on the command-line or named in --library options are relative the the current working directory.

3.2. Top Level Declarations (grammar)

Examples: 

abstract module M { }
trait R { }
class C { }
datatype D = A | B
newtype pos = i: int | i >= 0
type T = i: int | 0 <= i < 100
method m() {}
function f(): int
const c: bool

Top-level declarations may appear either at the top level of a Dafny file, or within a (sub)module declaration. A top-level declaration is one of various kinds of declarations described later. Top-level declarations are implicitly members of a default (unnamed) top-level module.

Declarations within a module or at the top-level all begin with reserved keywords and do not end with semicolons.

These declarations are one of these kinds:

Methods, functions and const declarations are placed in an implicit class declaration that is in the top-level implicit module. These declarations are all implicitly static (and may not be declared explicitly static).

3.3. Declaration Modifiers (grammar)

Examples: 

abstract module M {
  class C {
    static method m() {}
  }
}
ghost opaque const c : int

Top level declarations may be preceded by zero or more declaration modifiers. Not all of these are allowed in all contexts.

The abstract modifier may only be used for module declarations. An abstract module can leave some entities underspecified. Abstract modules are not compiled.

The ghost modifier is used to mark entities as being used for specification only, not for compilation to code.

The opaque modifier may be used on const declarations and functions.

The static modifier is used for class members that are associated with the class as a whole rather than with an instance of the class. This modifier may not be used with declarations that are implicitly static, as are members of the top-level, unnamed implicit class.

The following table shows modifiers that are available for each of the kinds of declaration. In the table we use already-ghost (already-non-ghost) to denote that the item is not allowed to have the ghost modifier because it is already implicitly ghost (non-ghost).

Declaration allowed modifiers
module abstract
class -
trait -
datatype or codatatype -
field (const) ghost opaque
newtype -
synonym types -
iterators -
method ghost static
lemma already-ghost static
least lemma already-ghost static
greatest lemma already-ghost static
constructor ghost
function ghost static opaque (Dafny 4)
function method already-non-ghost static opaque (Dafny 3)
function (non-method) already-ghost static opaque (Dafny 3)
predicate ghost static opaque (Dafny 4)
predicate method already-non-ghost static opaque (Dafny 3)
predicate (non-method) already-ghost static opaque (Dafny 3)
least predicate already-ghost static opaque
greatest predicate already-ghost static opaque

3.4. Executable programs

Dafny programs have an important emphasis on verification, but the programs may also be executable.

To be executable, the program must have exactly one Main method and that method must be a legal main entry point.

Any abstract modules are not searched for candidate entry points, but otherwise the entry point may be in any module or type. In addition, an entry-point candidate must satisfy the following conditions:

Note, however, that the following are allowed:

If no legal candidate entry point is identified, dafny will still produce executable output files, but they will need to be linked with some other code in the target language that provides a main entry point.

If the Main method takes an argument (of type seq<string>), the value of that input argument is the sequence of command-line arguments, with the first entry of the sequence (at index 0) being a system-determined name for the executable being run.

The exit code of the program, when executed, is not yet specified.

4. Modules (grammar)

Examples: 

module N  { }
import A
export A reveals f

Structuring a program by breaking it into parts is an important part of creating large programs. In Dafny, this is accomplished via modules. Modules provide a way to group together related types, classes, methods, functions, and other modules, as well as to control the scope of declarations. Modules may import each other for code reuse, and it is possible to abstract over modules to separate an implementation from an interface.

Module declarations are of three types:

Module definitions and imports each declare a submodule of its enclosing module, which may be the implicit, undeclared, top-level module.

4.1. Declaring New Modules (grammar)

Examples: 

module P { const i: int }
abstract module A.Q { method m() {} }
module M { module N { } }

A module definition

A module body consists of any declarations that are allowed at the top level: classes, datatypes, types, methods, functions, etc.

module Mod {
  class C {
    var f: int
    method m()
  }
  datatype Option = A(int) | B(int)
  type T
  method m()
  function f(): int
}

You can also put a module inside another, in a nested fashion:

module Mod {
  module Helpers {
    class C {
      method doIt()
      var f: int
    }
  }
}

Then you can refer to the members of the Helpers module within the Mod module by prefixing them with “Helpers.”. For example:

module Mod {
  module Helpers {
    class C {
      constructor () { f := 0; }
      method doIt()
      var f: int
    }
  }
  method m() {
    var x := new Helpers.C();
    x.doIt();
    x.f := 4;
  }
}

Methods and functions defined at the module level are available like classes, with just the module name prefixing them. They are also available in the methods and functions of the classes in the same module.

module Mod {
  module Helpers {
    function addOne(n: nat): nat {
      n + 1
    }
  }
  method m() {
    var x := 5;
    x := Helpers.addOne(x); // x is now 6
  }
}

Note that everything declared at the top-level (in all the files constituting the program) is implicitly part of a single implicit unnamed global module.

4.2. Declaring nested modules standalone

As described in the previous section, module declarations can be nested. It is also permitted to declare a nested module outside of its “containing” module. So instead of 

module A {
  module B {
  }
}

one can write 

module A {
}
module A.B {
}

The second module is completely separate; for example, it can be in a different file. This feature provides flexibility in writing and maintenance; for example, it can reduce the size of module A by extracting module A.B into a separate body of text.

However, it can also lead to confusion, and program authors need to take care. It may not be apparent to a reader of module A that module A.B exists; the existence of A.B might cause names to be resolved differently and the semantics of the program might be (silently) different if A.B is present or absent.

4.3. Importing Modules (grammar)

Examples: 

import A
import opened B
import A = B
import A : B
import A.B
import A`E
import X = A.B`{E,F}

Sometimes you want to refer to things from an existing module, such as a library. In this case, you can import one module into another. This is done via the import keyword, which has two forms with different meanings. The simplest form is the concrete import, which has the form import A = B. This declaration creates a reference to the module B (which must already exist), and binds it to the new local name A. This form can also be used to create a reference to a nested module, as in import A = B.C. The other form, using a :, is described in Section 4.6.

As modules in the same scope must have different names, this ability to bind a module to a new name allows disambiguating separately developed external modules that have the same name. Note that the new name is only bound in the scope containing the import declaration; it does not create a global alias. For example, if Helpers was defined outside of Mod, then we could import it:

module Helpers {
  function addOne(n: nat): nat {
    n + 1
  }
}
module Mod {
  import A = Helpers
  method m() {
    assert A.addOne(5) == 6;
  }
}

Note that inside m(), we have to use A instead of Helpers, as we bound it to a different name. The name Helpers is not available inside m() (or anywhere else inside Mod), as only names that have been bound inside Mod are available. In order to use the members from another module, that other module either has to be declared there with module or imported with import. (As described below, the resolution of the ModuleQualifiedName that follows the = in the import statement or the refines in a module declaration uses slightly different rules.)

We don’t have to give Helpers a new name, though, if we don’t want to. We can write import Helpers = Helpers to import the module under its own name; Dafny even provides the shorthand import Helpers for this behavior. You can’t bind two modules with the same name at the same time, so sometimes you have to use the = version to ensure the names do not clash. When importing nested modules, import B.C means import C = B.C; the implicit name is always the last name segment of the module designation.

The first identifier in the dot-separated sequence of identifers that constitute the qualified name of the module being imported is resolved as (in order)

Import statements may occur at the top-level of a program (that is, in the implicit top-level module of the program) as well. There they serve as a way to give a new name, perhaps a shorthand name, to a module. For example,

module MyModule { } // declare MyModule
import MyModule  // error: cannot add a module named MyModule
                 // because there already is one
import M = MyModule // OK. M and MyModule are equivalent

4.4. Opening Modules

Sometimes, prefixing the members of the module you imported with its name is tedious and ugly, even if you select a short name when importing it. In this case, you can import the module as opened, which causes all of its members to be available without adding the module name. The opened keyword, if present, must immediately follow import. For example, we could write the previous example as:

module Helpers {
  function addOne(n: nat): nat {
    n + 1
  }
}
module Mod {
  import opened Helpers
  method m() {
    assert addOne(5) == 6;
  }
}

When opening modules, the newly bound members have lower priority than local definitions. This means if you define a local function called addOne, the function from Helpers will no longer be available under that name. When modules are opened, the original name binding is still present however, so you can always use the name that was bound to get to anything that is hidden.

module Helpers {
  function addOne(n: nat): nat {
    n + 1
  }
}
module Mod {
  import opened H = Helpers
  function addOne(n: nat): nat {
    n - 1
  }
  method m() {
    assert addOne(5) == 6; // this is now false,
                           // as this is the function just defined
    assert H.addOne(5) == 6; // this is still true
  }
}

If you open two modules that both declare members with the same name, then neither member can be referred to without a module prefix, as it would be ambiguous which one was meant. Just opening the two modules is not an error, however, as long as you don’t attempt to use members with common names. However, if the ambiguous references actually refer to the same declaration, then they are permitted. The opened keyword may be used with any kind of import declaration, including the module abstraction form.

An import opened may occur at the top-level as well. For example, 

module MyModule {  } // declares MyModule
import opened MyModule // does not declare a new module, but does
                       // make all names in MyModule available in
                       // the current scope, without needing
                       // qualification
import opened M = MyModule // names in MyModule are available in
                       // the current scope without qualification
                       // or qualified with either M (because of this
                       // import) or MyModule (because of the original
                       // module definition)

The Dafny style guidelines suggest using opened imports sparingly. They are best used when the names being imported have obvious and unambiguous meanings and when using qualified names would be verbose enough to impede understanding.

There is a special case in which the behavior described above is altered. If a module M declares a type M and M is import opened without renaming inside another module X, then the rules above would have, within X, M mean the module and M.M mean the type. This is verbose. So in this somewhat common case, the type M is effectively made a local declaration within X so that it has precedence over the module name. Now M refers to the type. If one needs to refer to the module, it will have to be renamed as part of the import opened statement.

This special-case behavior does give rise to a source of ambiguity. Consider the example 

module Option {
  const a := 1
  datatype Option = A|B { static const a := 2 }
}

module X {
  import opened Option
  method M() { print Option.a; }
}

Option.a now means the a in the datatype instead of the a in the module. To avoid confusion in such cases, it is an ambiguity error if a name that is declared in both the datatype and the module is used when there is an import open of the module (without renaming).

4.5. Export Sets and Access Control (grammar)

Examples: 

export E extends F reveals f,g provides g,h
export E reveals *
export reveals f,g provides g,h
export E
export E ... reveals f

In some programming languages, keywords such as public, private, and protected are used to control access to (that is, visibility of) declared program entities. In Dafny, modules and export sets provide that capability. Modules combine declarations into logically related groups. Export sets then permit selectively exposing subsets of a module’s declarations; another module can import the export set appropriate to its needs. A user can define as many export sets as are needed to provide different kinds of access to the module’s declarations. Each export set designates a list of names, which must be names that are declared in the module (or in a refinement parent).

By default (in the absence of any export set declarations) all the names declared in a module are available outside the module using the import mechanism. An export set enables a module to disallow the use of some declarations outside the module.

An export set has an optional name used to disambiguate in case of multiple export sets; If specified, such names are used in import statements to designate which export set of a module is being imported. If a module M has export sets E1 and E2, we can write import A = M`E1 to create a module alias A that contains only the names in E1. Or we can write import A = M`{E1,E2} to import the union of names in E1 and E2 as module alias A. As before, import M`E1 is an abbreviation of import M = M`E1.

If no export set is given in an import statement, the default export set of the module is used.

There are various defaults that apply differently in different cases. The following description is with respect to an example module M:

M has no export sets declared. Then another module may simply import Z = M to obtain access to all of M’s declarations.

M has one or more named export sets (e.g., E, F). Then another module can write import Z = M`E or import Z = M`{E,F} to obtain access to the names that are listed in export set E or to the union of those in export sets E and F, respectively. If no export set has the same name as the module, then an export set designator must be used: in that case you cannot write simply import Z = M.

M has an unnamed export set, along with other export sets (e.g., named E). The unnamed export set is the default export set and implicitly has the same name as the module. Because there is a default export set, another module may write either import Z = M or import Z = M`M to import the names in that default export set. You can also still use the other export sets with the explicit designator: import Z = M`E

M declares an export set with the same name as the module. This is equivalent to declaring an export set without a name. import M and import M`M perform the same function in either case; the export set with or without the name of the module is the default export set for the module.

Note that names of module aliases (declared by import statements) are just like other names in a module; they can be included or omitted from export sets. Names brought into a module by refinement are treated the same as locally declared names and can be listed in export set declarations. However, names brought into a module by import opened (either into a module or a refinement parent of a module) may not be further exported. For example, 

module A {
  const a := 10
  const z := 10
}
module B {
  import opened Z = A // includes a, declares Z
  const b := Z.a // OK
}
module C {
  import opened B // includes b, Z, but not a
  method m() {
    //assert b == a; // error: a is not known
    //assert b == B.a; // error: B.a is not valid
    //assert b == A.a; // error: A is not known
    assert b == Z.a; // OK: module Z is known and includes a
  }
}

However, in the above example,

The default export set is important in the resolution of qualified names, as described in Section 4.8.

There are a few unusual cases to be noted:

4.5.1. Provided and revealed names

Names can be exported from modules in two ways, designated by provides and reveals in the export set declaration.

When a name is exported as provided, then inside a module that has imported the name only the name is known, not the details of the name’s declaration.

For example, in the following code the constant a is exported as provided. 

module A {
  export provides a
  const a := 10
  const b := 20
}

module B {
  import A
  method m() {
    assert A.a == 10; // a is known, but not its value
    // assert A.b == 20; // b is not known through A`A
  }
}

Since a is imported into module B through the default export set A`A, it can be referenced in the assert statement. The constant b is not exported, so it is not available. But the assert about a is not provable because the value of a is not known in module B.

In contrast, if a is exported as revealed, as shown in the next example, its value is known and the assertion can be proved. 

module A {
  export reveals a
  const a := 10
  const b := 20
}

module B {
  import A
  method m() {
    assert A.a == 10; // a and its value are known
    // assert A.b == 20; // b is not known through A`A
  }
}

The following table shows which parts of a declaration are exported by an export set that provides or reveals the declaration.

 declaration         | what is exported    | what is exported
                     | with provides       | with reveals
---------------------|---------------------|---------------------
 const x: X := E     | const x: X          | const x: X := E
---------------------|---------------------|---------------------
 var x: X            | var x: X            | not allowed
---------------------|---------------------|---------------------
 function F(x: X): Y | function F(x: X): Y | function F(x: X): Y
   specification...  |   specification...  |   specification...
 {                   |                     | {
   Body              |                     |   Body
 }                   |                     | }
---------------------|---------------------|---------------------
 method M(x: X)      | method M(x: X)      | not allowed
   returns (y: Y)    |   returns (y: Y)    |
   specification...  |   specification...  |
 {                   |                     |
   Body;             |                     |
 }                   |                     |
---------------------|---------------------|---------------------
 type Opaque         | type Opaque         | type Opaque
 {                   |                     |
   // members...     |                     |
 }                   |                     |
---------------------|---------------------|---------------------
 type Synonym = T    | type Synonym        | type Synonym = T
---------------------|---------------------|---------------------
 type S = x: X       | type S              | type S = x: X
   | P witness E     |                     |   | P witness E
---------------------|---------------------|---------------------
 newtype N = x: X    | type N              | newtype N = x: X
   | P witness E     |                     |   | P witness E
 {                   |                     |
   // members...     |                     |
 }                   |                     |

---------------------|---------------------|---------------------
 datatype D =        | type D              | datatype D =
     Ctor0(x0: X0)   |                     |    Ctor0(x0: X0)
   | Ctor1(x1: X1)   |                     |  | Ctor1(x1: X1)
   | ...             |                     |  | ...
 {                   |                     |
   // members...     |                     |
 }                   |                     |
---------------------|---------------------|---------------------
 class Cl            | type Cl             | class Cl
   extends T0, ...   |                     |   extends T0, ...
 {                   |                     | {
   constructor ()    |                     |   constructor ()
     spec...         |                     |     spec...
   {                 |                     |
     Body;           |                     |
   }                 |                     |
   // members...     |                     |
 }                   |                     | }
---------------------|---------------------|---------------------
 trait Tr            | type Tr             | trait Tr
   extends T0, ...   |                     |   extends T0, ...
 {                   |                     |
   // members...     |                     |
 }                   |                     |
---------------------|---------------------|---------------------
 iterator Iter(x: X) | type Iter           | iterator Iter(x: X)
   yields (y: Y)     |                     |   yields (y: Y)
   specification...  |                     |   specification...
 {                   |                     |
   Body;             |                     |
 }                   |                     |
---------------------|---------------------|---------------------
 module SubModule    | module SubModule    | not allowed
   ...               |   ...               |
 {                   | {                   |
   export SubModule  |   export SubModule  |
     ...             |     ...             |
   export A ...      |                     |
   // decls...       |   // decls...       |
 }                   | }                   |
---------------------|---------------------|---------------------
 import L = MS       | import L = MS       | not allowed
---------------------|---------------------|---------------------

Variations of functions (e.g., predicate, twostate function) are handled like function above, and variations of methods (e.g., lemma and twostate lemma) are treated like method above. Since the whole signature is exported, a function or method is exported to be of the same kind, even through provides. For example, an exported twostate lemma is exported as a twostate lemma (and thus is known by importers to have two implicit heap parameters), and an exported least predicate P is exported as a least predicate P (and thus importers can use both P and its prefix predicate P#).

If C is a class, trait, or iterator, then provides C exports the non-null reference type C as an abstract type. This does not reveal that C is a reference type, nor does it export the nullable type C?.

In most cases, exporting a class, trait, datatype, codatatype, or abstract type does not automatically export its members. Instead, any member to be exported must be listed explicitly. For example, consider the type declaration

trait Tr {
  function F(x: int): int { 10 }
  function G(x: int): int { 12 }
  function H(x: int): int { 14 }
}

An export set that contains only reveals Tr has the effect of exporting

trait Tr {
}

and an export set that contains only provides Tr, Tr.F reveals Tr.H has the effect of exporting

type Tr {
  function F(x: int): int
  function H(x: int): int { 14 }
}

There is no syntax (for example, Tr.*) to export all members of a type.

Some members are exported automatically when the type is revealed. Specifically:

For a class, a constructor member can be exported only if the class is revealed. For a class or trait, a var member can be exported only if the class or trait is revealed (but a const member can be exported even if the enclosing class or trait is only provided).

When exporting a sub-module, only the sub-module’s eponymous export set is exported. There is no way for a parent module to export any other export set of a sub-module, unless it is done via an import declaration of the parent module.

The effect of declaring an import as opened is confined to the importing module. That is, the ability of use such imported names as unqualified is not passed on to further imports, as the following example illustrates:

module Library {
  const xyz := 16
}

module M {
  export
    provides Lib
    provides xyz // error: 'xyz' is not declared locally

  import opened Lib = Library

  const k0 := Lib.xyz
  const k1 := xyz
}

module Client {
  import opened M

  const a0 := M.Lib.xyz
  const a1 := Lib.xyz
  const a2 := M.xyz // error: M does not have a declaration 'xyz'
  const a3 := xyz // error: unresolved identifier 'xyz'
}

As highlighted in this example, module M can use xyz as if it were a local name (see declaration k1), but the unqualified name xyz is not made available to importers of M (see declarations a2 and a3), nor is it possible for M to export the name xyz.

A few other notes:

4.5.2. Extends list

An export set declaration may include an extends list, which is a list of one or more export set names from the same module containing the declaration (including export set names obtained from a refinement parent). The effect is to include in the declaration the union of all the names in the export sets in the extends list, along with any other names explicitly included in the declaration. So for example in 

module M {
  const a := 10
  const b := 10
  const c := 10
  export A reveals a
  export B reveals b
  export C extends A, B
    reveals c
}

export set C will contain the names a, b, and c.

4.6. Module Abstraction

Sometimes, using a specific implementation is unnecessary; instead, all that is needed is a module that implements some interface. In that case, you can use an abstract module import. In Dafny, this is written import A : B. This means bind the name A as before, but instead of getting the exact module B, you get any module which adheres to B. Typically, the module B may have abstract type definitions, classes with bodiless methods, or otherwise be unsuitable to use directly. Because of the way refinement is defined, any refinement of B can be used safely. For example, suppose we start with these declarations:

abstract module Interface {
  function addSome(n: nat): nat
    ensures addSome(n) > n
}
abstract module Mod {
  import A : Interface
  method m() {
    assert 6 <= A.addSome(5);
  }
}

We can be more precise if we know that addSome actually adds exactly one. The following module has this behavior. Further, the postcondition is stronger, so this is actually a refinement of the Interface module.

module Implementation {
  function addSome(n: nat): nat
    ensures addSome(n) == n + 1
  {
    n + 1
  }
}

We can then substitute Implementation for A in a new module, by declaring a refinement of Mod which defines A to be Implementation.

abstract module Interface {
  function addSome(n: nat): nat
    ensures addSome(n) > n
}
abstract module Mod {
  import A : Interface
  method m() {
    assert 6 <= A.addSome(5);
  }
}
module Implementation {
  function addSome(n: nat): nat
    ensures addSome(n) == n + 1
  {
    n + 1
  }
}
module Mod2 refines Mod {
  import A = Implementation
  ...
}

When you refine an abstract import into a concrete one Dafny checks that the concrete module is a refinement of the abstract one. This means that the methods must have compatible signatures, all the classes and datatypes with their constructors and fields in the abstract one must be present in the concrete one, the specifications must be compatible, etc.

A module that includes an abstract import must be declared abstract.

4.7. Module Ordering and Dependencies

Dafny isn’t particular about the textual order in which modules are declared, but they must follow some rules to be well formed. In particular, there must be a way to order the modules in a program such that each only refers to things defined before it in the ordering. That doesn’t mean the modules have to be given textually in that order in the source text. Dafny will figure out that order for you, assuming you haven’t made any circular references. For example, this is pretty clearly meaningless:

import A = B
import B = A // error: circular

You can have import statements at the toplevel and you can import modules defined at the same level:

import A = B
method m() {
  A.whatever();
}
module B { method whatever() {} }

In this case, everything is well defined because we can put B first, followed by the A import, and then finally m(). If there is no permitted ordering, then Dafny will give an error, complaining about a cyclic dependency.

Note that when rearranging modules and imports, they have to be kept in the same containing module, which disallows some pathological module structures. Also, the imports and submodules are always considered to be before their containing module, even at the toplevel. This means that the following is not well formed:

method doIt() { }
module M {
  method m() {
    doIt(); // error: M precedes doIt
  }
}

because the module M must come before any other kind of members, such as methods. To define global functions like this, you can put them in a module (called Globals, say) and open it into any module that needs its functionality. Finally, if you import via a path, such as import A = B.C, then this creates a dependency of A on B, and B itself depends on its own nested module B.C.

4.8. Name Resolution

When Dafny sees something like A<T>.B<U>.C<V>, how does it know what each part refers to? The process Dafny uses to determine what identifier sequences like this refer to is name resolution. Though the rules may seem complex, usually they do what you would expect. Dafny first looks up the initial identifier. Depending on what the first identifier refers to, the rest of the identifier is looked up in the appropriate context.

In terms of the grammar, sequences like the above are represented as a NameSegment followed by 0 or more Suffixes. The form shown above contains three instances of AugmentedDotSuffix_.

The resolution is different depending on whether it is in a module context, an expression context or a type context.

4.8.1. Modules and name spaces

A module is a collection of declarations, each of which has a name. These names are held in two namespaces.

In addition names can be classified as local or imported.

Within each namespace, the local names are unique. Thus a module may not reuse a name that a refinement parent has declared (unless it is a refining declaration, which replaces both declarations, as described in Section 10).

Local names take precedence over imported names. If a name is used more than once among imported names (coming from different imports), then it is ambiguous to use the name without qualification.

4.8.2. Module Id Context Name Resolution

A qualified name may be used to refer to a module in an import statement or a refines clause of a module declaration. Such a qualified name is resolved as follows, with respect to its syntactic location within a module Z:

  1. The leading identifier of the qualified name is resolved as a local or imported module name of Z, if there is one with a matching name. The target of a refines clause does not consider local names, that is, in module Z refines A.B.C, any contents of Z are not considered in finding A.

  2. Otherwise, it is resolved as a local or imported module name of the most enclosing module of Z, iterating outward to each successive enclosing module until a match is found or the default toplevel module is reached without a match. No consideration of export sets, default or otherwise, is used in this step. However, if at any stage a matching name is found that is not a module declaration, the resolution fails. See the examples below.

3a. Once the leading identifier is resolved as say module M, the next identifier in the quallified name is resolved as a local or imported module name within M. The resolution is restricted to the default export set of M.

3b. If the resolved module name is a module alias (from an import statement) then the target of the alias is resolved as a new qualified name with respect to its syntactic context (independent of any resolutions or modules so far). Since Z depends on M, any such alias target will already have been resolved, because modules are resolved in order of dependency.

  1. Step 3 is iterated for each identifier in the qualified module id, resulting in a module that is the final resolution of the complete qualified id.

Ordinarily a module must be imported in order for its constituent declarations to be visible inside a given module M. However, for the resolution of qualified names this is not the case.

This example shows that the resolution of the refinement parent does not use any local names: 

module A {
  const a := 10
}

module B refines A { // the top-level A, not the submodule A
  module A { const a := 30 }
  method m() { assert a == 10; } // true
}

In the example, the A in refines A refers to the global A, not the submodule A.

4.8.3. Expression Context Name Resolution

The leading identifier is resolved using the first following rule that succeeds.

  1. Local variables, parameters and bound variables. These are things like x, y, and i in var x;, ... returns (y: int), and forall i :: .... The declaration chosen is the match from the innermost matching scope.

  2. If in a class, try to match a member of the class. If the member that is found is not static an implicit this is inserted. This works for fields, functions, and methods of the current class (if in a static context, then only static methods and functions are allowed). You can refer to fields of the current class either as this.f or f, assuming of course that f is not hidden by one of the above. You can always prefix this if needed, which cannot be hidden. (Note that a field whose name is a string of digits must always have some prefix.)

  3. If there is no Suffix, then look for a datatype constructor, if unambiguous. Any datatypes that don’t need qualification (so the datatype name itself doesn’t need a prefix) and also have a uniquely named constructor can be referred to just by name. So if datatype List = Cons(List) | Nil is the only datatype that declares Cons and Nil constructors, then you can write Cons(Cons(Nil)). If the constructor name is not unique, then you need to prefix it with the name of the datatype (for example List.Cons(List.Nil))). This is done per constructor, not per datatype.

  4. Look for a member of the enclosing module.

  5. Module-level (static) functions and methods

In each module, names from opened modules are also potential matches, but only after names declared in the module. If an ambiguous name is found or a name of the wrong kind (e.g. a module instead of an expression identifier), an error is generated, rather than continuing down the list.

After the first identifier, the rules are basically the same, except in the new context. For example, if the first identifier is a module, then the next identifier looks into that module. Opened modules only apply within the module it is opened into. When looking up into another module, only things explicitly declared in that module are considered.

To resolve expression E.id:

First resolve expression E and any type arguments.

4.8.4. Type Context Name Resolution

In a type context the priority of identifier resolution is:

  1. Type parameters.

  2. Member of enclosing module (type name or the name of a module).

To resolve expression E.id:

5. Types

A Dafny type is a (possibly-empty) set of values or heap data-structures, together with allowed operations on those values. Types are classified as mutable reference types or immutable value types, depending on whether their values are stored in the heap or are (mathematical) values independent of the heap.

Dafny supports the following kinds of types, all described in later sections of this manual:

5.1. Kinds of types

5.1.1. Value Types

The value types are those whose values do not lie in the program heap. These are:

Data items having value types are passed by value. Since they are not considered to occupy memory, framing expressions do not reference them.

The nat type is a pre-defined subset type of int.

Dafny does not include types themselves as values, nor is there a type of types.

5.1.2. Reference Types

Dafny offers a host of reference types. These represent references to objects allocated dynamically in the program heap. To access the members of an object, a reference to (that is, a pointer to or object identity of) the object is dereferenced.

The reference types are class types, traits and array types. Dafny supports both reference types that contain the special null value (nullable types) and reference types that do not (non-null types).

5.1.3. Named Types (grammar)

A Named Type is used to specify a user-defined type by a (possibly module- or class-qualified) name. Named types are introduced by class, trait, inductive, coinductive, synonym and abstract type declarations. They are also used to refer to type variables. A Named Type is denoted by a dot-separated sequence of name segments (Section 9.32).

A name segment (for a type) is a type name optionally followed by a generic instantiation, which supplies type parameters to a generic type, if needed.

The following sections describe each of these kinds of types in more detail.

5.2. Basic types

Dafny offers these basic types: bool for booleans, char for characters, int and nat for integers, real for reals, ORDINAL, and bit-vector types.

5.2.1. Booleans (grammar)

There are two boolean values and each has a corresponding literal in the language: false and true.

Type bool supports the following operations:

operator precedence description
<==> 1 equivalence (if and only if)
==> 2 implication (implies)
<== 2 reverse implication (follows from)
&& 3 conjunction (and)
|| 3 disjunction (or)
== 4 equality
!= 4 disequality
! 10 negation (not)

Negation is unary; the others are binary. The table shows the operators in groups of increasing binding power, with equality binding stronger than conjunction and disjunction, and weaker than negation. Within each group, different operators do not associate, so parentheses need to be used. For example, 

A && B || C    // error

would be ambiguous and instead has to be written as either 

(A && B) || C

or 

A && (B || C)

depending on the intended meaning.

5.2.1.1. Equivalence Operator

The expressions A <==> B and A == B give the same value, but note that <==> is associative whereas == is chaining and they have different precedence. So, 

A <==> B <==> C

is the same as 

A <==> (B <==> C)

and 

(A <==> B) <==> C

whereas 

A == B == C

is simply a shorthand for 

A == B && B == C

Also, 

A <==> B == C <==> D

is 

A <==> (B == C) <==> D
5.2.1.2. Conjunction and Disjunction

Conjunction and disjunction are associative. These operators are short circuiting (from left to right), meaning that their second argument is evaluated only if the evaluation of the first operand does not determine the value of the expression. Logically speaking, the expression A && B is defined when A is defined and either A evaluates to false or B is defined. When A && B is defined, its meaning is the same as the ordinary, symmetric mathematical conjunction &. The same holds for || and |.

5.2.1.3. Implication and Reverse Implication

Implication is right associative and is short-circuiting from left to right. Reverse implication B <== A is exactly the same as A ==> B, but gives the ability to write the operands in the opposite order. Consequently, reverse implication is left associative and is short-circuiting from right to left. To illustrate the associativity rules, each of the following four lines expresses the same property, for any A, B, and C of type bool: 

A ==> B ==> C
A ==> (B ==> C) // parentheses redundant, ==> is right associative
C <== B <== A
(C <== B) <== A // parentheses redundant, <== is left associative

To illustrate the short-circuiting rules, note that the expression a.Length is defined for an array a only if a is not null (see Section 5.1.2), which means the following two expressions are well-formed: 

a != null ==> 0 <= a.Length
0 <= a.Length <== a != null

The contrapositives of these two expressions would be: 

a.Length < 0 ==> a == null  // not well-formed
a == null <== a.Length < 0  // not well-formed

but these expressions might not necessarily be well-formed, since well-formedness requires the left (and right, respectively) operand, a.Length < 0, to be well-formed in their context.

Implication A ==> B is equivalent to the disjunction !A || B, but is sometimes (especially in specifications) clearer to read. Since, || is short-circuiting from left to right, note that 

a == null || 0 <= a.Length

is well-formed by itself, whereas 

0 <= a.Length || a == null  // not well-formed

is not if the context cannot prove that a != null.

In addition, booleans support logical quantifiers (forall and exists), described in Section 9.31.4.

5.2.2. Numeric Types (grammar)

Dafny supports numeric types of two kinds, integer-based, which includes the basic type int of all integers, and real-based, which includes the basic type real of all real numbers. User-defined numeric types based on int and real, either subset types or newtypes, are described in Section 5.6.3 and Section 5.7.

There is one built-in subset type, nat, representing the non-negative subrange of int.

The language includes a literal for each integer, like 0, 13, and 1985. Integers can also be written in hexadecimal using the prefix “0x”, as in 0x0, 0xD, and 0x7c1 (always with a lower case x, but the hexadecimal digits themselves are case insensitive). Leading zeros are allowed. To form negative literals, use the unary minus operator, as in -12, but not -(12).

There are also literals for some of the reals. These are written as a decimal point with a nonempty sequence of decimal digits on both sides, optionally prefixed by a - character. For example, 1.0, 1609.344, -12.5, and 0.5772156649. Real literals using exponents are not supported in Dafny. For now, you’d have to write your own function for that, e.g. 

// realExp(2.37, 100) computes 2.37e100
function realExp(r: real, e: int): real decreases if e > 0 then e else -e {
  if e == 0 then r
  else if e < 0 then realExp(r/10.0, e+1)
  else realExp(r*10.0, e-1)
}

For integers (in both decimal and hexadecimal form) and reals, any two digits in a literal may be separated by an underscore in order to improve human readability of the literals. For example: 

const c1 := 1_000_000        // easier to read than 1000000
const c2 := 0_12_345_6789    // strange but legal formatting of 123456789
const c3 := 0x8000_0000      // same as 0x80000000 -- hex digits are
                             // often placed in groups of 4
const c4 := 0.000_000_000_1  // same as 0.0000000001 -- 1 Angstrom

In addition to equality and disequality, numeric types support the following relational operations, which have the same precedence as equality:

operator description
< less than
<= at most
>= at least
> greater than

Like equality and disequality, these operators are chaining, as long as they are chained in the “same direction”. That is, 

A <= B < C == D <= E

is simply a shorthand for 

A <= B && B < C && C == D && D <= E

whereas 

A < B > C

is not allowed.

There are also operators on each numeric type:

operator precedence description
+ 6 addition (plus)
- 6 subtraction (minus)
* 7 multiplication (times)
/ 7 division (divided by)
% 7 modulus (mod) – int only
- 10 negation (unary minus)

The binary operators are left associative, and they associate with each other in the two groups. The groups are listed in order of increasing binding power, with equality binding less strongly than any of these operators. There is no implicit conversion between int and real: use as int or as real conversions to write an explicit conversion (cf. Section 9.10).

Modulus is supported only for integer-based numeric types. Integer division and modulus are the Euclidean division and modulus. This means that modulus always returns a non-negative value, regardless of the signs of the two operands. More precisely, for any integer a and non-zero integer b, 

a == a / b * b + a % b
0 <= a % b < B

where B denotes the absolute value of b.

Real-based numeric types have a member Floor that returns the floor of the real value (as an int value), that is, the largest integer not exceeding the real value. For example, the following properties hold, for any r and r' of type real: 

method m(r: real, r': real) {
  assert 3.14.Floor == 3;
  assert (-2.5).Floor == -3;
  assert -2.5.Floor == -2; // This is -(2.5.Floor)
  assert r.Floor as real <= r;
  assert r <= r' ==> r.Floor <= r'.Floor;
}

Note in the third line that member access (like .Floor) binds stronger than unary minus. The fourth line uses the conversion function as real from int to real, as described in Section 9.10.

5.2.3. Bit-vector Types (grammar)

Dafny includes a family of bit-vector types, each type having a specific, constant length, the number of bits in its values. Each such type is distinct and is designated by the prefix bv followed (without white space) by a positive integer without leading zeros or zero, stating the number of bits. For example, bv1, bv8, and bv32 are legal bit-vector type names. The type bv0 is also legal; it is a bit-vector type with no bits and just one value, 0x0.

Constant literals of bit-vector types are given by integer literals converted automatically to the designated type, either by an implicit or explicit conversion operation or by initialization in a declaration. Dafny checks that the constant literal is in the correct range. For example, 

const i: bv1 := 1
const j: bv8 := 195
const k: bv2 := 5 // error - out of range
const m := (194 as bv8) | (7 as bv8)

Bit-vector values can be converted to and from int and other bit-vector types, as long as the values are in range for the target type. Bit-vector values are always considered unsigned.

Bit-vector operations include bit-wise operators and arithmetic operators (as well as equality, disequality, and comparisons). The arithmetic operations truncate the high-order bits from the results; that is, they perform unsigned arithmetic modulo 2^{number of bits}, like 2’s-complement machine arithmetic.

operator precedence description
<< 5 bit-limited bit-shift left
>> 5 unsigned bit-shift right
+ 6 bit-limited addition
- 6 bit-limited subtraction
* 7 bit-limited multiplication
& 8 bit-wise and
| 8 bit-wise or
^ 8 bit-wise exclusive-or
- 10 bit-limited negation (unary minus)
! 10 bit-wise complement
.RotateLeft(n) 11 rotates bits left by n bit positions
.RotateRight(n) 11 rotates bits right by n bit positions

The groups of operators lower in the table above bind more tightly.1 All operators bind more tightly than equality, disequality, and comparisons. All binary operators are left-associative, but the bit-wise &, |, and ^ do not associate together (parentheses are required to disambiguate). The +, |, ^, and & operators are commutative.

The right-hand operand of bit-shift operations is an int value, must be non-negative, and no more than the number of bits in the type. There is no signed right shift as all bit-vector values correspond to non-negative integers.

Bit-vector negation returns an unsigned value in the correct range for the type. It has the properties x + (-x) == 0 and (!x) + 1 == -x, for a bitvector value x of at least one bit.

The argument of the RotateLeft and RotateRight operations is a non-negative int that is no larger than the bit-width of the value being rotated. RotateLeft moves bits to higher bit positions (e.g., (2 as bv4).RotateLeft(1) == (4 as bv4) and (8 as bv4).RotateLeft(1) == (1 as bv4)); RotateRight moves bits to lower bit positions, so b.RotateLeft(n).RotateRight(n) == b.

Here are examples of the various operations (all the assertions are true except where indicated): 

const i: bv4 := 9
const j: bv4 := 3

method m() {
  assert (i & j) == (1 as bv4);
  assert (i | j) == (11 as bv4);
  assert (i ^ j) == (10 as bv4);
  assert !i == (6 as bv4);
  assert -i == (7 as bv4);
  assert (i + i) == (2 as bv4);
  assert (j - i) == (10 as bv4);
  assert (i * j) == (11 as bv4);
  assert (i as int) / (j as int) == 3;
  assert (j << 1) == (6 as bv4);
  assert (i << 1) == (2 as bv4);
  assert (i >> 1) == (4 as bv4);
  assert i == 9; // auto conversion of literal to bv4
  assert i * 4 == j + 8 + 9; // arithmetic is modulo 16
  assert i + j >> 1 == (i + j) >> 1; // + - bind tigher than << >>
  assert i + j ^ 2 == i + (j^2);
  assert i * j & 1 == i * (j&1); // & | ^ bind tighter than + - *
}

The following are incorrectly formed: 

const i: bv4 := 9
const j: bv4 := 3

method m() {
  assert i & 4 | j == 0 ; // parentheses required
}

const k: bv4 := 9

method p() {
  assert k as bv5 == 9 as bv6; // error: mismatched types
}

These produce assertion errors: 

const i: bv4 := 9

method m() {
  assert i as bv3 == 1; // error: i is out of range for bv3
}

const j: bv4 := 9

method n() {
  assert j == 25; // error: 25 is out of range for bv4
}

Bit-vector constants (like all constants) can be initialized using expressions, but pay attention to how type inference applies to such expressions. For example, 

const a: bv3 := -1

is legal because Dafny interprets -1 as a bv3 expression, because a has type bv3. Consequently the - is bv3 negation and the 1 is a bv3 literal; the value of the expression -1 is the bv3 value 7, which is then the value of a.

On the other hand, 

const b: bv3 := 6 & 11

is illegal because, again, the & is bv3 bit-wise-and and the numbers must be valid bv3 literals. But 11 is not a valid bv3 literal.

5.2.4. Ordinal type (grammar)

Values of type ORDINAL behave like nats in many ways, with one important difference: there are ORDINAL values that are larger than any nat. The smallest of these non-nat ordinals is represented as $\omega$ in mathematics, though there is no literal expression in Dafny that represents this value.

The natural numbers are ordinals. Any ordinal has a successor ordinal (equivalent to adding 1). Some ordinals are limit ordinals, meaning they are not a successor of any other ordinal; the natural number 0 and $\omega$ are limit ordinals.

The offset of an ordinal is the number of successor operations it takes to reach it from a limit ordinal.

The Dafny type ORDINAL has these member functions:

In addition,

In Dafny, ORDINALs are used primarily in conjunction with extreme functions and lemmas.

5.2.5. Characters (grammar)

Dafny supports a type char of characters.
Its exact meaning is controlled by the command-line switch --unicode-char:true|false.

If --unicode-char is disabled, then char represents any UTF-16 code unit. This includes surrogate code points.

If --unicode-char is enabled, then char represents any Unicode scalar value. This excludes surrogate code points.

Character literals are enclosed in single quotes, as in 'D'. To write a single quote as a character literal, it is necessary to use an escape sequence. Escape sequences can also be used to write other characters. The supported escape sequences are the following:

escape sequence meaning
\' the character '
\" the character "
\\ the character \
\0 the null character, same as \u0000 or \U{0}
\n line feed
\r carriage return
\t horizontal tab
\uxxxx UTF-16 code unit whose hexadecimal code is xxxx, where each x is a hexadecimal digit
\U{x..x} Unicode scalar value whose hexadecimal code is x..x, where each x is a hexadecimal digit

The escape sequence for a double quote is redundant, because '"' and '\"' denote the same character—both forms are provided in order to support the same escape sequences in string literals (Section 5.5.3.5).

In the form \uxxxx, which is only allowed if --unicode-char is disabled, the u is always lower case, but the four hexadecimal digits are case insensitive.

In the form \U{x..x}, which is only allowed if --unicode-char is enabled, the U is always upper case, but the hexadecimal digits are case insensitive, and there must be at least one and at most six digits. Surrogate code points are not allowed. The hex digits may be interspersed with underscores for readability (but not beginning or ending with an underscore), as in \U{1_F680}.

Character values are ordered and can be compared using the standard relational operators:

operator description
< less than
<= at most
>= at least
> greater than

Sequences of characters represent strings, as described in Section 5.5.3.5.

Character values can be converted to and from int values using the as int and as char conversion operations. The result is what would be expected in other programming languages, namely, the int value of a char is the ASCII or Unicode numeric value.

The only other operations on characters are obtaining a character by indexing into a string, and the implicit conversion to string when used as a parameter of a print statement.

5.3. Type parameters (grammar)

Examples: 

type G1<T>
type G2<T(0)>
type G3<+T(==),-U>

Many of the types, functions, and methods in Dafny can be parameterized by types. These type parameters are declared inside angle brackets and can stand for any type.

Dafny has some inference support that makes certain signatures less cluttered (described in Section 12.2).

5.3.1. Declaring restrictions on type parameters

It is sometimes necessary to restrict type parameters so that they can only be instantiated by certain families of types, that is, by types that have certain properties. These properties are known as type characteristics. The following subsections describe the type characteristics that Dafny supports.

In some cases, type inference will infer that a type-parameter must be restricted in a particular way, in which case Dafny will add the appropriate suffix, such as (==), automatically.

If more than one restriction is needed, they are either listed comma-separated, inside the parentheses or as multiple parenthesized elements: T(==,0) or T(==)(0).

When an actual type is substituted for a type parameter in a generic type instantiation, the actual type must have the declared or inferred type characteristics of the type parameter. These characteristics might also be inferred for the actual type. For example, a numeric-based subset or newtype automatically has the == relationship of its base type. Similarly, type synonyms have the characteristics of the type they represent.

An abstract type has no known characteristics. If it is intended to be defined only as types that have certain characteristics, then those characteristics must be declared. For example, 

class A<T(00)> {}
type Q
const a: A<Q>

will give an error because it is not known whether the type Q is non-empty (00). Instead, one needs to write 

class A<T(00)> {}
type Q(00)
const a: A?<Q> := null
5.3.1.1. Equality-supporting type parameters: T(==)

Designating a type parameter with the (==) suffix indicates that the parameter may only be replaced in non-ghost contexts with types that are known to support run-time equality comparisons (== and !=). All types support equality in ghost contexts, as if, for some types, the equality function is ghost.

For example, 

method Compare<T(==)>(a: T, b: T) returns (eq: bool)
{
  if a == b { eq := true; } else { eq := false; }
}

is a method whose type parameter is restricted to equality-supporting types when used in a non-ghost context. Again, note that all types support equality in ghost contexts; the difference is only for non-ghost (that is, compiled) code. Coinductive datatypes, arrow types, and inductive datatypes with ghost parameters are examples of types that are not equality supporting.

5.3.1.2. Auto-initializable types: T(0)

At every access of a variable x of a type T, Dafny ensures that x holds a legal value of type T. If no explicit initialization is given, then an arbitrary value is assumed by the verifier and supplied by the compiler, that is, the variable is auto-initialized, but to an arbitrary value. For example, 

class Example<A(0), X> {
  var n: nat
  var i: int
  var a: A
  var x: X

  constructor () {
    new; // error: field 'x' has not been given a value`
    assert n >= 0; // true, regardless of the value of 'n'
    assert i >= 0; // possibly false, since an arbitrary 'int' may be negative
    // 'a' does not require an explicit initialization, since 'A' is auto-init
  }
}

In the example above, the class fields do not need to be explicitly initialized in the constructor because they are auto-initialized to an arbitrary value.

Local variables and out-parameters are however, subject to definite assignment rules. The following example requires --relax-definite-assignment, which is not the default. 

method m() {
  var n: nat; // Auto-initialized to an arbitrary value of type `nat`
  assert n >= 0; // true, regardless of the value of n
  var i: int;
  assert i >= 0; // possibly false, arbitrary ints may be negative
}

With the default behavior of definite assignment, n and i need to be initialized to an explicit value of their type or to an arbitrary value using, for example, var n: nat := *;.

For some types (known as auto-init types), the compiler can choose an initial value, but for others it does not. Variables and fields whose type the compiler does not auto-initialize are subject to definite-assignment rules. These ensure that the program explicitly assigns a value to a variable before it is used. For more details see Section 12.6 and the --relax-definite-assignment command-line option. More detail on auto-initializing is in this document.

Dafny supports auto-init as a type characteristic. To restrict a type parameter to auto-init types, mark it with the (0) suffix. For example, 

method AutoInitExamples<A(0), X>() returns (a: A, x: X)
{
  // 'a' does not require an explicit initialization, since A is auto-init
  // error: out-parameter 'x' has not been given a value
}

In this example, an error is reported because out-parameter x has not been assigned—since nothing is known about type X, variables of type X are subject to definite-assignment rules. In contrast, since type parameter A is declared to be restricted to auto-init types, the program does not need to explicitly assign any value to the out-parameter a.

5.3.1.3. Nonempty types: T(00)

Auto-init types are important in compiled contexts. In ghost contexts, it may still be important to know that a type is nonempty. Dafny supports a type characteristic for nonempty types, written with the suffix (00). For example, with --relax-definite-assignment, the following example happens:

method NonemptyExamples<B(00), X>() returns (b: B, ghost g: B, ghost h: X)
{
  // error: non-ghost out-parameter 'b' has not been given a value
  // ghost out-parameter 'g' is fine, since its type is nonempty
  // error: 'h' has not been given a value
}

Because of B’s nonempty type characteristic, ghost parameter g does not need to be explicitly assigned. However, Dafny reports an error for the non-ghost b, since B is not an auto-init type, and reports an error for h, since the type X could be empty.

Note that every auto-init type is nonempty.

In the default definite-assignment mode (that is, without --relax-definite-assignment) there will be errors for all three formal parameters in the example just given.

For more details see Section 12.6.

5.3.1.4. Non-heap based: T(!new)

Dafny makes a distinction between types whose values are on the heap, i.e. references, like classes and arrays, and those that are strictly value-based, like basic types and datatypes. The practical implication is that references depend on allocation state (e.g., are affected by the old operation) whereas non-reference values are not. Thus it can be relevant to know whether the values of a type parameter are heap-based or not. This is indicated by the mode suffix (!new).

A type parameter characterized by (!new) is recursively independent of the allocation state. For example, a datatype is not a reference, but for a parameterized data type such as 

datatype Result<T> = Failure(error: string) | Success(value: T)

the instantiation Result<int> satisfies (!new), whereas Result<array<int>> does not.

Note that this characteristic of a type parameter is operative for both verification and compilation. Also, abstract types at the topmost scope are always implicitly (!new).

Here are some examples: 

datatype Result<T> = Failure(error: string) | Success(v: T)
datatype ResultN<T(!new)> = Failure(error: string) | Success(v: T)

class C {}

method m() {
  var x1: Result<int>;
  var x2: ResultN<int>;
  var x3: Result<C>;
  var x4: ResultN<C>; // error
  var x5: Result<array<int>>;
  var x6: ResultN<array<int>>; // error
}

5.3.2. Type parameter variance

Type parameters have several different variance and cardinality properties. These properties of type parameters are designated in a generic type definition. For instance, in type A<+T> = ... , the + indicates that the T position is co-variant. These properties are indicated by the following notation:

notation variance cardinality-preserving
(nothing) non-variant yes
+ co-variant yes
- contra-variant not necessarily
* co-variant not necessarily
! non-variant not necessarily

Cardinality preserving means that the cardinality of the type being defined never exceeds the cardinality of any of its type parameters. For example type T<X> = X -> bool is illegal and returns the error message formal type parameter 'X' is not used according to its variance specification (it is used left of an arrow) (perhaps try declaring 'X' as '-X' or '!X') The type X -> bool has strictly more values than the type X. This affects certain uses of the type, so Dafny requires the declaration of T to explicitly say so. Marking the type parameter X with - or ! announces that the cardinality of T<X> may by larger than that of X. If you use -, you’re also declaring T to be contravariant in its type argument, and if you use !, you’re declaring that T is non-variant in its type argument.

To fix it, we use the variance !:

type T<!X> = X -> bool

This states that T does not preserve the cardinality of X, meaning there could be strictly more values of type T<E> than values of type E for any E.

A more detailed explanation of these topics is here.

5.4. Generic Instantiation (grammar)

A generic instantiation consists of a comma-separated list of 1 or more Types, enclosed in angle brackets (< >), providing actual types to be used in place of the type parameters of the declaration of the generic type. If there is no instantion for a generic type, type inference will try to fill these in (cf. Section 12.2).

5.5. Collection types

Dafny offers several built-in collection types.

5.5.1. Sets (grammar)

For any type T, each value of type set<T> is a finite set of T values.

Set membership is determined by equality in the type T, so set<T> can be used in a non-ghost context only if T is equality supporting.

For any type T, each value of type iset<T> is a potentially infinite set of T values.

A set can be formed using a set display expression, which is a possibly empty, unordered, duplicate-insensitive list of expressions enclosed in curly braces. To illustrate, 

{}        {2, 7, 5, 3}        {4+2, 1+5, a*b}

are three examples of set displays. There is also a set comprehension expression (with a binder, like in logical quantifications), described in Section 9.31.5.

In addition to equality and disequality, set types support the following relational operations:

operator precedence description
< 4 proper subset
<= 4 subset
>= 4 superset
> 4 proper superset

Like the arithmetic relational operators, these operators are chaining.

Sets support the following binary operators, listed in order of increasing binding power:

operator precedence description
!! 4 disjointness
+ 6 set union
- 6 set difference
* 7 set intersection

The associativity rules of +, -, and * are like those of the arithmetic operators with the same names. The expression A !! B, whose binding power is the same as equality (but which neither associates nor chains with equality), says that sets A and B have no elements in common, that is, it is equivalent to 

A * B == {}

However, the disjointness operator is chaining though in a slightly different way than other chaining operators: A !! B !! C !! D means that A, B, C and D are all mutually disjoint, that is 

A * B == {} && (A + B) * C == {} && (A + B + C) * D == {}

In addition, for any set s of type set<T> or iset<T> and any expression e of type T, sets support the following operations:

expression precedence result type description
e in s 4 bool set membership
e !in s 4 bool set non-membership
|s| 11 nat set cardinality (not for iset)

The expression e !in s is a syntactic shorthand for !(e in s).

(No white space is permitted between ! and in, making !in effectively the one example of a mixed-character-class token in Dafny.)

5.5.2. Multisets (grammar)

A multiset is similar to a set, but keeps track of the multiplicity of each element, not just its presence or absence. For any type T, each value of type multiset<T> is a map from T values to natural numbers denoting each element’s multiplicity. Multisets in Dafny are finite, that is, they contain a finite number of each of a finite set of elements. Stated differently, a multiset maps only a finite number of elements to non-zero (finite) multiplicities.

Like sets, multiset membership is determined by equality in the type T, so multiset<T> can be used in a non-ghost context only if T is equality supporting.

A multiset can be formed using a multiset display expression, which is a possibly empty, unordered list of expressions enclosed in curly braces after the keyword multiset. To illustrate, 

multiset{}   multiset{0, 1, 1, 2, 3, 5}   multiset{4+2, 1+5, a*b}

are three examples of multiset displays. There is no multiset comprehension expression.

In addition to equality and disequality, multiset types support the following relational operations:

operator precedence description
< 4 proper multiset subset
<= 4 multiset subset
>= 4 multiset superset
> 4 proper multiset superset

Like the arithmetic relational operators, these operators are chaining.

Multisets support the following binary operators, listed in order of increasing binding power:

operator precedence description
!! 4 multiset disjointness
+ 6 multiset sum
- 6 multiset difference
* 7 multiset intersection

The associativity rules of +, -, and * are like those of the arithmetic operators with the same names. The + operator adds the multiplicity of corresponding elements, the - operator subtracts them (but 0 is the minimum multiplicity), and the * has multiplicity that is the minimum of the multiplicity of the operands. There is no operator for multiset union, which would compute the maximum of the multiplicities of the operands.

The expression A !! B says that multisets A and B have no elements in common, that is, it is equivalent to 

A * B == multiset{}

Like the analogous set operator, !! is chaining and means mutual disjointness.

In addition, for any multiset s of type multiset<T>, expression e of type T, and non-negative integer-based numeric n, multisets support the following operations:

expression precedence result type description
e in s 4 bool multiset membership
e !in s 4 bool multiset non-membership
|s| 11 nat multiset cardinality
s[e] 11 nat multiplicity of e in s
s[e := n] 11 multiset<T> multiset update (change of multiplicity)

The expression e in s returns true if and only if s[e] != 0. The expression e !in s is a syntactic shorthand for !(e in s). The expression s[e := n] denotes a multiset like s, but where the multiplicity of element e is n. Note that the multiset update s[e := 0] results in a multiset like s but without any occurrences of e (whether or not s has occurrences of e in the first place). As another example, note that s - multiset{e} is equivalent to: 

if e in s then s[e := s[e] - 1] else s

5.5.3. Sequences (grammar)

For any type T, a value of type seq<T> denotes a sequence of T elements, that is, a mapping from a finite downward-closed set of natural numbers (called indices) to T values.

5.5.3.1. Sequence Displays

A sequence can be formed using a sequence display expression, which is a possibly empty, ordered list of expressions enclosed in square brackets. To illustrate, 

[]        [3, 1, 4, 1, 5, 9, 3]        [4+2, 1+5, a*b]

are three examples of sequence displays.

There is also a sequence comprehension expression (Section 9.28): 

seq(5, i => i*i)

is equivalent to [0, 1, 4, 9, 16].

5.5.3.2. Sequence Relational Operators

In addition to equality and disequality, sequence types support the following relational operations:

operator precedence description
< 4 proper prefix
<= 4 prefix

Like the arithmetic relational operators, these operators are chaining. Note the absence of > and >=.

5.5.3.3. Sequence Concatenation

Sequences support the following binary operator:

operator precedence description
+ 6 concatenation

Operator + is associative, like the arithmetic operator with the same name.

5.5.3.4. Other Sequence Expressions

In addition, for any sequence s of type seq<T>, expression e of type T, integer-based numeric index i satisfying 0 <= i < |s|, and integer-based numeric bounds lo and hi satisfying 0 <= lo <= hi <= |s|, noting that bounds can equal the length of the sequence, sequences support the following operations:

expression precedence result type description
e in s 4 bool sequence membership
e !in s 4 bool sequence non-membership
|s| 11 nat sequence length
s[i] 11 T sequence selection
s[i := e] 11 seq<T> sequence update
s[lo..hi] 11 seq<T> subsequence
s[lo..] 11 seq<T> drop
s[..hi] 11 seq<T> take
s[slices] 11 seq<seq<T>> slice
multiset(s) 11 multiset<T> sequence conversion to a multiset<T>

Expression s[i := e] returns a sequence like s, except that the element at index i is e. The expression e in s says there exists an index i such that s[i] == e. It is allowed in non-ghost contexts only if the element type T is equality supporting. The expression e !in s is a syntactic shorthand for !(e in s).

Expression s[lo..hi] yields a sequence formed by taking the first hi elements and then dropping the first lo elements. The resulting sequence thus has length hi - lo. Note that s[0..|s|] equals s. If the upper bound is omitted, it defaults to |s|, so s[lo..] yields the sequence formed by dropping the first lo elements of s. If the lower bound is omitted, it defaults to 0, so s[..hi] yields the sequence formed by taking the first hi elements of s.

In the sequence slice operation, slices is a nonempty list of length designators separated and optionally terminated by a colon, and there is at least one colon. Each length designator is a non-negative integer-based numeric; the sum of the length designators is no greater than |s|. If there are k colons, the operation produces k + 1 consecutive subsequences from s, with the length of each indicated by the corresponding length designator, and returns these as a sequence of sequences. If slices is terminated by a colon, then the length of the last slice extends until the end of s, that is, its length is |s| minus the sum of the given length designators. For example, the following equalities hold, for any sequence s of length at least 10: 

method m(s: seq<int>) {
  var t := [3.14, 2.7, 1.41, 1985.44, 100.0, 37.2][1:0:3];
  assert |t| == 3 && t[0] == [3.14] && t[1] == [];
  assert t[2] == [2.7, 1.41, 1985.44];
  var u := [true, false, false, true][1:1:];
  assert |u| == 3 && u[0][0] && !u[1][0] && u[2] == [false, true];
  assume |s| > 10;
  assert s[10:][0] == s[..10];
  assert s[10:][1] == s[10..];
}

The operation multiset(s) yields the multiset of elements of sequence s. It is allowed in non-ghost contexts only if the element type T is equality supporting.

5.5.3.5. Strings (grammar)

A special case of a sequence type is seq<char>, for which Dafny provides a synonym: string. Strings are like other sequences, but provide additional syntax for sequence display expressions, namely string literals. There are two forms of the syntax for string literals: the standard form and the verbatim form.

String literals of the standard form are enclosed in double quotes, as in "Dafny". To include a double quote in such a string literal, it is necessary to use an escape sequence. Escape sequences can also be used to include other characters. The supported escape sequences are the same as those for character literals (Section 5.2.5). For example, the Dafny expression "say \"yes\"" represents the string 'say "yes"'. The escape sequence for a single quote is redundant, because "\'" and "\'" denote the same string—both forms are provided in order to support the same escape sequences as do character literals.

String literals of the verbatim form are bracketed by @" and ", as in @"Dafny". To include a double quote in such a string literal, it is necessary to use the escape sequence "", that is, to write the character twice. In the verbatim form, there are no other escape sequences. Even characters like newline can be written inside the string literal (hence spanning more than one line in the program text).

For example, the following three expressions denote the same string: 

"C:\\tmp.txt"
@"C:\tmp.txt"
['C', ':', '\\', 't', 'm', 'p', '.', 't', 'x', 't']

Since strings are sequences, the relational operators < and <= are defined on them. Note, however, that these operators still denote proper prefix and prefix, respectively, not some kind of alphabetic comparison as might be desirable, for example, when sorting strings.

5.5.4. Finite and Infinite Maps (grammar)

For any types T and U, a value of type map<T,U> denotes a (finite) map from T to U. In other words, it is a look-up table indexed by T. The domain of the map is a finite set of T values that have associated U values. Since the keys in the domain are compared using equality in the type T, type map<T,U> can be used in a non-ghost context only if T is equality supporting.

Similarly, for any types T and U, a value of type imap<T,U> denotes a (possibly) infinite map. In most regards, imap<T,U> is like map<T,U>, but a map of type imap<T,U> is allowed to have an infinite domain.

A map can be formed using a map display expression (see Section 9.30), which is a possibly empty, ordered list of maplets, each maplet having the form t := u where t is an expression of type T and u is an expression of type U, enclosed in square brackets after the keyword map. To illustrate, 

map[]
map[20 := true, 3 := false, 20 := false]
map[a+b := c+d]

are three examples of map displays. By using the keyword imap instead of map, the map produced will be of type imap<T,U> instead of map<T,U>. Note that an infinite map (imap) is allowed to have a finite domain, whereas a finite map (map) is not allowed to have an infinite domain. If the same key occurs more than once in a map display expression, only the last occurrence appears in the resulting map.2 There is also a map comprehension expression, explained in Section 9.31.8.

For any map fm of type map<T,U>, any map m of type map<T,U> or imap<T,U>, any expression t of type T, any expression u of type U, and any d in the domain of m (that is, satisfying d in m), maps support the following operations:

expression precedence result type description
t in m 4 bool map domain membership
t !in m 4 bool map domain non-membership
|fm| 11 nat map cardinality
m[d] 11 U map selection
m[t := u] 11 map<T,U> map update
m.Keys 11 (i)set<T> the domain of m
m.Values 11 (i)set<U> the range of m
m.Items 11 (i)set<(T,U)> set of pairs (t,u) in m

|fm| denotes the number of mappings in fm, that is, the cardinality of the domain of fm. Note that the cardinality operator is not supported for infinite maps. Expression m[d] returns the U value that m associates with d. Expression m[t := u] is a map like m, except that the element at key t is u. The expression t in m says t is in the domain of m and t !in m is a syntactic shorthand for !(t in m).3

The expressions m.Keys, m.Values, and m.Items return, as sets, the domain, the range, and the 2-tuples holding the key-value associations in the map. Note that m.Values will have a different cardinality than m.Keys and m.Items if different keys are associated with the same value. If m is an imap, then these expressions return iset values. If m is a map, m.Values and m.Items require the type of the range U to support equality.

Here is a small example, where a map cache of type map<int,real> is used to cache computed values of Joule-Thomson coefficients for some fixed gas at a given temperature: 

if K in cache {  // check if temperature is in domain of cache
  coeff := cache[K];  // read result in cache
} else {
  coeff := ComputeJTCoefficient(K); // do expensive computation
  cache := cache[K := coeff];  // update the cache
}

Dafny also overloads the + and - binary operators for maps. The + operator merges two maps or imaps of the same type, as if each (key,value) pair of the RHS is added in turn to the LHS (i)map. In this use, + is not commutative; if a key exists in both (i)maps, it is the value from the RHS (i)map that is present in the result.

The - operator implements a map difference operator. Here the LHS is a map<K,V> or imap<K,V> and the RHS is a set<K> (but not an iset); the operation removes from the LHS all the (key,value) pairs whose key is a member of the RHS set.

To avoid causing circular reasoning chains or providing too much information that might complicate Dafny’s prover finding proofs, not all properties of maps are known by the prover by default. For example, the following does not prove: 

method mmm<K(==),V(==)>(m: map<K,V>, k: K, v: V) {
    var mm := m[k := v];
    assert v in mm.Values;
  }

Rather, one must provide an intermediate step, which is not entirely obvious: 

method mmm<K(==),V(==)>(m: map<K,V>, k: K, v: V) {
    var mm := m[k := v];
    assert k in mm.Keys;
    assert v in mm.Values;
  }

5.5.5. Iterating over collections

Collections are very commonly used in programming and one frequently needs to iterate over the elements of a collection. Dafny does not have built-in iterator methods, but the idioms by which to do so are straightforward. The subsections below give some introductory examples; more detail can be found in this power user note.

5.5.5.1. Sequences and arrays

Sequences and arrays are indexable and have a length. So the idiom to iterate over the contents is well-known. For an array: 

method m(a: array<int>) {
  var i := 0;
  var sum := 0;
  while i < a.Length {
    sum := sum + a[i];
    i := i + 1;
  }
}

For a sequence, the only difference is the length operator: 

method m(s: seq<int>) {
  var i := 0;
  var sum := 0;
  while i < |s| {
    sum := sum + s[i];
    i := i + 1;
  }
}

The forall statement (Section 8.21) can also be used with arrays where parallel assignment is needed: 

method m(s: array<int>) {
  var rev := new int[s.Length];
  forall i | 0 <= i < s.Length {
    rev[i] := s[s.Length-i-1];
  }
}

See Section 5.10.2 on how to convert an array to a sequence.

5.5.5.2. Sets

There is no intrinsic order to the elements of a set. Nevertheless, we can extract an arbitrary element of a nonempty set, performing an iteration as follows: 

method m(s: set<int>) {
  var ss := s;
  while ss != {}
    decreases |ss|
  {
    var i: int :| i in ss;
    ss := ss - {i};
    print i, "\n";
  }
}

Because isets may be infinite, Dafny does not permit iteration over an iset.

5.5.5.3. Maps

Iterating over the contents of a map uses the component sets: Keys, Values, and Items. The iteration loop follows the same patterns as for sets:

method m<T(==),U(==)> (m: map<T,U>) {
  var items := m.Items;
  while items != {}
    decreases |items|
  {
    var item :| item in items;
    items := items - { item };
    print item.0, " ", item.1, "\n";
  }
}

There are no mechanisms currently defined in Dafny for iterating over imaps.

5.6. Types that stand for other types (grammar)

It is sometimes useful to know a type by several names or to treat a type abstractly. There are several mechanisms in Dafny to do this:

5.6.1. Type synonyms (grammar)

type T = int
type SS<T> = set<set<T>>

A type synonym declaration: 

type Y<T> = G

declares Y<T> to be a synonym for the type G. If the = G is omitted then the declaration just declares a name as an uninterpreted abstract type, as described in Section 5.6.2. Such types may be given a definition elsewhere in the Dafny program.

Here, T is a nonempty list of type parameters (each of which optionally has a type characteristics suffix), which can be used as free type variables in G. If the synonym has no type parameters, the “<T>” is dropped. In all cases, a type synonym is just a synonym. That is, there is never a difference, other than possibly in error messages produced, between Y<T> and G.

For example, the names of the following type synonyms may improve the readability of a program: 

type Replacements<T> = map<T,T>
type Vertex = int

The new type name itself may have type characteristics declared, and may need to if there is no definition. If there is a definition, the type characteristics are typically inferred from the definition. The syntax is like this: 

type Z(==)<T(0)>

As already described in Section 5.5.3.5, string is a built-in type synonym for seq<char>, as if it would have been declared as follows: 

type string_(==,0,!new) = seq<char>

If the implicit declaration did not include the type characteristics, they would be inferred in any case.

Note that although a type synonym can be declared and used in place of a type name, that does not affect the names of datatype or class constructors. For example, consider 

datatype Pair<T> = Pair(first: T, second: T)
type IntPair = Pair<int>

const p: IntPair := Pair(1,2) // OK
const q: IntPair := IntPair(3,4) // Error

In the declaration of q, IntPair is the name of a type, not the name of a function or datatype constructor.

5.6.2. Abstract types (grammar)

Examples: 

type T
type Q { function toString(t: T): string }

An abstract type is a special case of a type synonym that is underspecified. Such a type is declared simply by: 

type Y<T>

Its definition can be stated in a refining module. The name Y can be immediately followed by a type characteristics suffix (Section 5.3.1). Because there is no defining RHS, the type characteristics cannot be inferred and so must be stated. If, in some refining module, a definition of the type is given, the type characteristics must match those of the new definition.

For example, the declarations 

type T
function F(t: T): T

can be used to model an uninterpreted function F on some arbitrary type T. As another example, 

type Monad<T>

can be used abstractly to represent an arbitrary parameterized monad.

Even as an abstract type, the type may be given members such as constants, methods or functions. For example, 

abstract module P {
  type T {
    function ToString(): string
  }
}

module X refines P {
  newtype T = i | 0 <= i < 10 {
    function ToString(): string {  "" }
  }
}

The abstract type P.T has a declared member ToString, which can be called wherever P.T may be used. In the refining module X, T is declared to be a newtype, in which ToString now has a body.

It would be an error to refine P.T as a simple type synonym or subset type in X, say type T = int, because type synonyms may not have members.

5.6.3. Subset types (grammar)

Examples: 

type Pos = i: int | i > 0 witness 1
type PosReal = r | r > 0.0 witness 1.0
type Empty = n: nat | n < 0 witness *
type Big = n: nat | n > 1000 ghost witness 10000

A subset type is a restricted use of an existing type, called the base type of the subset type. A subset type is like a combined use of the base type and a predicate on the base type.

An assignment from a subset type to its base type is always allowed. An assignment in the other direction, from the base type to a subset type, is allowed provided the value assigned does indeed satisfy the predicate of the subset type. This condition is checked by the verifier, not by the type checker. Similarly, assignments from one subset type to another (both with the same base type) are also permitted, as long as it can be established that the value being assigned satisfies the predicate defining the receiving subset type. (Note, in contrast, assignments between a newtype and its base type are never allowed, even if the value assigned is a value of the target type. For such assignments, an explicit conversion must be used, see Section 9.10.)

The declaration of a subset type permits an optional witness clause, to declare that there is a value that satisfies the subset type’s predicate; that is, the witness clause establishes that the defined type is not empty. The compiler may, but is not obligated to, use this value when auto-initializing a newly declared variable of the subset type.

Dafny builds in three families of subset types, as described next.

5.6.3.1. Type nat

The built-in type nat, which represents the non-negative integers (that is, the natural numbers), is a subset type: 

type nat = n: int | 0 <= n

A simple example that puts subset type nat to good use is the standard Fibonacci function: 

function Fib(n: nat): nat
{
  if n < 2 then n else Fib(n-2) + Fib(n-1)
}

An equivalent, but clumsy, formulation of this function (modulo the wording of any error messages produced at call sites) would be to use type int and to write the restricting predicate in pre- and postconditions: 

function Fib(n: int): int
  requires 0 <= n  // the function argument must be non-negative
  ensures 0 <= Fib(n)  // the function result is non-negative
{
  if n < 2 then n else Fib(n - 2) + Fib(n - 1)
}
5.6.3.2. Non-null types

Every class, trait, and iterator declaration C gives rise to two types.

One type has the name C? (that is, the name of the class, trait, or iterator declaration with a ? character appended to the end). The values of C? are the references to C objects, and also the value null. In other words, C? is the type of possibly null references (aka, nullable references) to C objects.

The other type has the name C (that is, the same name as the class, trait, or iterator declaration). Its values are the references to C objects, and does not contain the value null. In other words, C is the type of non-null references to C objects.

The type C is a subset type of C?: 

type C = c: C? | c != null

(It may be natural to think of the type C? as the union of type C and the value null, but, technically, Dafny defines C as a subset type with base type C?.)

From being a subset type, we get that C is a subtype of C?. Moreover, if a class or trait C extends a trait B, then type C is a subtype of B and type C? is a subtype of B?.

Every possibly-null reference type is a subtype of the built-in possibly-null trait type object?, and every non-null reference type is a subtype of the built-in non-null trait type object. (And, from the fact that object is a subset type of object?, we also have that object is a subtype of object?.)

Arrays are references and array types also come in these two flavors. For example, array? and array2? are possibly-null (1- and 2-dimensional) array types, and array and array2 are their respective non-null types.

Note that ? is not an operator. Instead, it is simply the last character of the name of these various possibly-null types.

5.6.3.3. Arrow types: ->, -->, and ~>

For more information about arrow types (function types), see Section 5.12. This section is a preview to point out the subset-type relationships among the kinds of function types.

The built-in type

More precisely, type constructors exist for any arity (() -> X, A -> X, (A, B) -> X, (A, B, C) -> X, etc.).

For a list of types TT and a type U, the values of the arrow type (TT) ~> U are functions from TT to U. This includes functions that may read the heap and functions that are not defined on all inputs. It is not common to need this generality (and working with such general functions is difficult). Therefore, Dafny defines two subset types that are more common (and much easier to work with).

The type (TT) --> U denotes the subset of (TT) ~> U where the functions do not read the (mutable parts of the) heap. Values of type (TT) --> U are called partial functions, and the subset type (TT) --> U is called the partial arrow type. (As a mnemonic to help you remember that this is the partial arrow, you may think of the little gap between the two hyphens in --> as showing a broken arrow.)

Intuitively, the built-in partial arrow type is defined as follows (here shown for arrows with arity 1): 

type A --> B = f: A ~> B | forall a :: f.reads(a) == {}

(except that what is shown here left of the = is not legal Dafny syntax and that the restriction could not be verified as is). That is, the partial arrow type is defined as those functions f whose reads frame is empty for all inputs. More precisely, taking variance into account, the partial arrow type is defined as 

type -A --> +B = f: A ~> B | forall a :: f.reads(a) == {}

The type (TT) -> U is, in turn, a subset type of (TT) --> U, adding the restriction that the functions must not impose any precondition. That is, values of type (TT) -> U are total functions, and the subset type (TT) -> U is called the total arrow type.

The built-in total arrow type is defined as follows (here shown for arrows with arity 1): 

type -A -> +B = f: A --> B | forall a :: f.requires(a)

That is, the total arrow type is defined as those partial functions f whose precondition evaluates to true for all inputs.

Among these types, the most commonly used are the total arrow types. They are also the easiest to work with. Because they are common, they have the simplest syntax (->).

Note, informally, we tend to speak of all three of these types as arrow types, even though, technically, the ~> types are the arrow types and the --> and -> types are subset types thereof. The one place where you may need to remember that --> and -> are subset types is in some error messages. For example, if you try to assign a partial function to a variable whose type is a total arrow type and the verifier is not able to prove that the partial function really is total, then you’ll get an error saying that the subset-type constraint may not be satisfied.

For more information about arrow types, see Section 5.12.

5.6.3.4. Witness clauses

The declaration of a subset type permits an optional witness clause. Types in Dafny are generally expected to be non-empty, in part because variables of any type are expected to have some value when they are used. In many cases, Dafny can determine that a newly declared type has some value. For example, in the absence of a witness clause, a numeric type that includes 0 is known by Dafny to be non-empty. However, Dafny cannot always make this determination. If it cannot, a witness clause is required. The value given in the witness clause must be a valid value for the type and assures Dafny that the type is non-empty. (The variation witness * is described below.)

For example, 

type OddInt = x: int | x % 2 == 1

will give an error message, but 

type OddInt = x: int | x % 2 == 1 witness 73

does not. Here is another example: 

type NonEmptySeq = x: seq<int> | |x| > 0 witness [0]

If the witness is only available in ghost code, you can declare the witness as a ghost witness. In this case, the Dafny verifier knows that the type is non-empty, but it will not be able to auto-initialize a variable of that type in compiled code.

There is even room to do the following: 

type BaseType
predicate RHS(x: BaseType)
type MySubset = x: BaseType | RHS(x) ghost witness MySubsetWitness()

function {:axiom} MySubsetWitness(): BaseType
  ensures RHS(MySubsetWitness())

Here the type is given a ghost witness: the result of the expression MySubsetWitness(), which is a call of a (ghost) function. Now that function has a postcondition saying that the returned value is indeed a candidate value for the declared type, so the verifier is satisfied regarding the non-emptiness of the type. However, the function has no body, so there is still no proof that there is indeed such a witness. You can either supply a, perhaps complicated, body to generate a viable candidate or you can be very sure, without proof, that there is indeed such a value. If you are wrong, you have introduced an unsoundness into your program.

In addition though, types are allowed to be empty or possibly empty. This is indicated by the clause witness *, which tells the verifier not to check for a satisfying witness. A declaration like this produces an empty type: 

type ReallyEmpty = x: int | false witness *

The type can be used in code like 

method M(x: ReallyEmpty) returns (seven: int)
  ensures seven == 7
{
  seven := 10;
}

which does verify. But the method can never be called because there is no value that can be supplied as the argument. Even this code 

method P() returns (seven: int)
  ensures seven == 7
{
  var x: ReallyEmpty;
  seven := 10;
}

does not complain about x unless x is actually used, in which case it must have a value. The postcondition in P does not verify, but not because of the empty type.

5.7. Newtypes (grammar)

Examples: 

newtype I = int
newtype D = i: int | 0 <= i < 10
newtype uint8 = i | 0 <= i < 256

A newtype is like a type synonym or subset type except that it declares a wholly new type name that is distinct from its base type. It also accepts an optional witness clause.

A new type can be declared with the newtype declaration, for example: 

newtype N = x: M | Q

where M is a type and Q is a boolean expression that can use x as a free variable. If M is an integer-based numeric type, then so is N; if M is real-based, then so is N. If the type M can be inferred from Q, the “: M” can be omitted. If Q is just true, then the declaration can be given simply as: 

newtype N = M

Type M is known as the base type of N. At present, Dafny only supports int and real as base types of newtypes.

A newtype is a type that supports the same operations as its base type. The newtype is distinct from and incompatible with other types; in particular, it is not assignable to its base type without an explicit conversion. An important difference between the operations on a newtype and the operations on its base type is that the newtype operations are defined only if the result satisfies the predicate Q, and likewise for the literals of the newtype.

For example, suppose lo and hi are integer-based numeric bounds that satisfy 0 <= lo <= hi and consider the following code fragment: 

var mid := (lo + hi) / 2;

If lo and hi have type int, then the code fragment is legal; in particular, it never overflows, since int has no upper bound. In contrast, if lo and hi are variables of a newtype int32 declared as follows: 

newtype int32 = x | -0x8000_0000 <= x < 0x8000_0000

then the code fragment is erroneous, since the result of the addition may fail to satisfy the predicate in the definition of int32. The code fragment can be rewritten as 

var mid := lo + (hi - lo) / 2;

in which case it is legal for both int and int32.

An additional point with respect to arithmetic overflow is that for (signed) int32 values hi and lo constrained only by lo <= hi, the difference hi - lo can also overflow the bounds of the int32 type. So you could also write: 

var mid := lo + (hi/2 - lo/2);

Since a newtype is incompatible with its base type and since all results of the newtype’s operations are members of the newtype, a compiler for Dafny is free to specialize the run-time representation of the newtype. For example, by scrutinizing the definition of int32 above, a compiler may decide to store int32 values using signed 32-bit integers in the target hardware.

The incompatibility of a newtype and its basetype is intentional, as newtypes are meant to be used as distinct types from the basetype. If numeric types are desired that mix more readily with the basetype, the subset types described in Section 5.6.3 may be more appropriate.

Note that the bound variable x in Q has type M, not N. Consequently, it may not be possible to state Q about the N value. For example, consider the following type of 8-bit 2’s complement integers: 

newtype int8 = x: int | -128 <= x < 128

and consider a variable c of type int8. The expression 

-128 <= c < 128

is not well-defined, because the comparisons require each operand to have type int8, which means the literal 128 is checked to be of type int8, which it is not. A proper way to write this expression is to use a conversion operation, described in Section 5.7.1, on c to convert it to the base type: 

-128 <= c as int < 128

If possible, Dafny compilers will represent values of the newtype using a native type for the sake of efficiency. This action can be inhibited or a specific native data type selected by using the {:nativeType} attribute, as explained in Section 11.1.2.

Furthermore, for the compiler to be able to make an appropriate choice of representation, the constants in the defining expression as shown above must be known constants at compile-time. They need not be numeric literals; combinations of basic operations and symbolic constants are also allowed as described in Section 9.39.

5.7.1. Conversion operations

For every type N, there is a conversion operation with the name as N, described more fully in Section 9.10. It is a partial function defined when the given value, which can be of any type, is a member of the type converted to. When the conversion is from a real-based numeric type to an integer-based numeric type, the operation requires that the real-based argument have no fractional part. (To round a real-based numeric value down to the nearest integer, use the .Floor member, see Section 5.2.2.)

To illustrate using the example from above, if lo and hi have type int32, then the code fragment can legally be written as follows: 

var mid := (lo as int + hi as int) / 2;

where the type of mid is inferred to be int. Since the result value of the division is a member of type int32, one can introduce yet another conversion operation to make the type of mid be int32: 

var mid := ((lo as int + hi as int) / 2) as int32;

If the compiler does specialize the run-time representation for int32, then these statements come at the expense of two, respectively three, run-time conversions.

The as N conversion operation is grammatically a suffix operation like .field and array indexing, but binds less tightly than unary operations: - x as int is (- x) as int; a + b as int is a + (b as int).

The as N conversion can also be used with reference types. For example, if C is a class, c is an expression of type C, and o is an expression of type object, then c as object and c as object? are upcasts and o is C is a downcast. A downcast requires the LHS expression to have the RHS type, as is enforced by the verifier.

For some types (in particular, reference types), there is also a corresponding is operation (Section 9.10) that tests whether a value is valid for a given type.

5.8. Class types (grammar)

Examples: 

trait T {}
class A {}
class B extends T {
  const b: B?
  var v: int
  constructor (vv: int) { v := vv; b := null; }
  function toString(): string { "a B" }
  method m(i: int) { var x := new B(0); }
  static method q() {}
}

Declarations within a class all begin with keywords and do not end with semicolons.

A class C is a reference type declared as follows: 

class C<T> extends J1, ..., Jn
{
  _members_
}

where the <>-enclosed list of one-or-more type parameters T is optional. The text “extends J1, ..., Jn” is also optional and says that the class extends traits J1 … Jn. The members of a class are fields, constant fields, functions, and methods. These are accessed or invoked by dereferencing a reference to a C instance.

A function or method is invoked on an instance of C, unless the function or method is declared static. A function or method that is not static is called an instance function or method.

An instance function or method takes an implicit receiver parameter, namely, the instance used to access the member. In the specification and body of an instance function or method, the receiver parameter can be referred to explicitly by the keyword this. However, in such places, members of this can also be mentioned without any qualification. To illustrate, the qualified this.f and the unqualified f refer to the same field of the same object in the following example: 

class C {
  var f: int
  var x: int
  method Example() returns (b: bool)
  {
    var x: int;
    b := f == this.f;
  }
}

so the method body always assigns true to the out-parameter b. However, in this example, x and this.x are different because the field x is shadowed by the declaration of the local variable x. There is no semantic difference between qualified and unqualified accesses to the same receiver and member.

A C instance is created using new. There are three forms of new, depending on whether or not the class declares any constructors (see Section 6.3.2):

c := new C;
c := new C.Init(args);
c := new C(args);

For a class with no constructors, the first two forms can be used. The first form simply allocates a new instance of a C object, initializing its fields to values of their respective types (and initializing each const field with a RHS to its specified value). The second form additionally invokes an initialization method (here, named Init) on the newly allocated object and the given arguments. It is therefore a shorthand for 

c := new C;
c.Init(args);

An initialization method is an ordinary method that has no out-parameters and that modifies no more than this.

For a class that declares one or more constructors, the second and third forms of new can be used. For such a class, the second form invokes the indicated constructor (here, named Init), which allocates and initializes the object. The third form is the same as the second, but invokes the anonymous constructor of the class (that is, a constructor declared with the empty-string name).

The details of constructors and other class members are described in Section 6.3.2.

5.9. Trait types (grammar)

A trait is an abstract superclass, similar to an “interface” or “mixin”. A trait can be extended only by another trait or by a class (and in the latter case we say that the class implements the trait). More specifically, algebraic datatypes cannot extend traits.4

The declaration of a trait is much like that of a class: 

trait J
{
  _members_
}

where members can include fields, constant fields, functions, methods and declarations of nested traits, but no constructor methods. The functions and methods are allowed to be declared static.

A reference type C that extends a trait J is assignable to a variable of type J; a value of type J is assignable to a variable of a reference type C that extends J only if the verifier can prove that the reference does indeed refer to an object of allocated type C. The members of J are available as members of C. A member in J is not allowed to be redeclared in C, except if the member is a non-static function or method without a body in J. By doing so, type C can supply a stronger specification and a body for the member. There is further discussion on this point in Section 5.9.2.

new is not allowed to be used with traits. Therefore, there is no object whose allocated type is a trait. But there can of course be objects of a class C that implement a trait J, and a reference to such a C object can be used as a value of type J.

5.9.1. Type object (grammar)

There is a built-in trait object that is implicitly extended by all classes and traits. It produces two types: the type object? that is a supertype of all reference types and a subset type object that is a supertype of all non-null reference types. This includes reference types like arrays and iterators that do not permit explicit extending of traits. The purpose of type object is to enable a uniform treatment of dynamic frames. In particular, it is useful to keep a ghost field (typically named Repr for “representation”) of type set<object>.

It serves no purpose (but does no harm) to explicitly list the trait object as an extendee in a class or trait declaration.

Traits object? and object contain no members.

The dynamic allocation of objects is done using new C…, where C is the name of a class. The name C is not allowed to be a trait, except that it is allowed to be object. The construction new object allocates a new object (of an unspecified class type). The construction can be used to create unique references, where no other properties of those references are needed. (new object? makes no sense; always use new object instead because the result of new is always non-null.)

5.9.2. Inheritance

The purpose of traits is to be able to express abstraction: a trait encapsulates a set of behaviors; classes and traits that extend it inherit those behaviors, perhaps specializing them.

A trait or class may extend multiple other traits. The traits syntactically listed in a trait or class’s extends clause are called its direct parents; the transitive parents of a trait or class are its direct parents, the transitive parents of its direct parents, and the object trait (if it is not itself object). These are sets of traits, in that it does not matter if there are repetitions of a given trait in a class or trait’s direct or transitive parents. However, if a trait with type parameters is repeated, it must have the same actual type parameters in each instance. Furthermore, a trait may not be in its own set of transitive parents; that is, the graph of traits connected by the directed extends relationship may not have any cycles.

A class or trait inherits (as if they are copied) all the instance members of its transitive parents. However, since names may not be overloaded in Dafny, different members (that is, members with different type signatures) within the set of transitive parents and the class or trait itself must have different names.5 This restriction does mean that traits from different sources that coincidentally use the same name for different purposes cannot be combined by being part of the set of transitive parents for some new trait or class.

A declaration of member C.M in a class or trait overrides any other declarations of the same name (and signature) in a transitive parent. C.M is then called an override; a declaration that does not override anything is called an original declaration.

Static members of a trait may not be redeclared; thus, if there is a body it must be declared in the trait; the compiler will require a body, though the verifier will not.

Where traits within an extension hierarchy do declare instance members with the same name (and thus the same signature), some rules apply. Recall that, for methods, every declaration includes a specification; if no specification is given explicitly, a default specification applies. Instance method declarations in traits, however, need not have a body, as a body can be declared in an override.

For a given non-static method M,

The last restriction above is the current implementation. It effectively limits inheritance of a method M to a single “chain” of declarations and does not permit mixins.

Each of any method declarations explicitly or implicitly includes a specification. In simple cases, those syntactically separate specifications will be copies of each other (up to renaming to take account of differing formal parameter names). However they need not be. The rule is that the specifications of M in a given class or trait must be as strong as M’s specifications in a transitive parent. Here as strong as means that it must be permitted to call the subtype’s M in the context of the supertype’s M. Stated differently, where P and C are a parent trait and a child class or trait, respectively, then, under the precondition of P.M,

Non-static const and field declarations are also inherited from parent traits. These may not be redeclared in extending traits and classes. However, a trait need not initialize a const field with a value. The class that extends a trait that declares such a const field without an initializer can initialize the field in a constructor. If the declaring trait does give an initial value in the declaration, the extending class or trait may not either redeclare the field or give it a value in a constructor.

When names are inherited from multiple traits, they must be different. If two traits declare a common name (even with the same signature), they cannot both be extendees of the same class or trait.

5.9.3. Example of traits

As an example, the following trait represents movable geometric shapes: 

trait Shape
{
  function Width(): real
    reads this
    decreases 1
  method Move(dx: real, dy: real)
    modifies this
  method MoveH(dx: real)
    modifies this
  {
    Move(dx, 0.0);
  }
}

Members Width and Move are abstract (that is, body-less) and can be implemented differently by different classes that extend the trait. The implementation of method MoveH is given in the trait and thus is used by all classes that extend Shape. Here are two classes that each extend Shape: 

class UnitSquare extends Shape
{
  var x: real, y: real
  function Width(): real 
    decreases 0
  {  // note the empty reads clause
    1.0
  }
  method Move(dx: real, dy: real)
    modifies this
  {
    x, y := x + dx, y + dy;
  }
}

class LowerRightTriangle extends Shape
{
  var xNW: real, yNW: real, xSE: real, ySE: real
  function Width(): real
    reads this
    decreases 0
  {
    xSE - xNW
  }
  method Move(dx: real, dy: real)
    modifies this
  {
    xNW, yNW, xSE, ySE := xNW + dx, yNW + dy, xSE + dx, ySE + dy;
  }
}

Note that the classes can declare additional members, that they supply implementations for the abstract members of the trait, that they repeat the member signatures, and that they are responsible for providing their own member specifications that both strengthen the corresponding specification in the trait and are satisfied by the provided body. Finally, here is some code that creates two class instances and uses them together as shapes: 

method m() {
  var myShapes: seq<Shape>;
  var A := new UnitSquare;
  myShapes := [A];
  var tri := new LowerRightTriangle;
  // myShapes contains two Shape values, of different classes
  myShapes := myShapes + [tri];
  // move shape 1 to the right by the width of shape 0
  myShapes[1].MoveH(myShapes[0].Width());
}

5.10. Array types (grammar)

Dafny supports mutable fixed-length array types of any positive dimension. Array types are (heap-based) reference types.

arrayToken is a kind of reserved token, such as array, array?, array2, array2?, array3, and so on (but not array1). The type parameter suffix giving the element type can be omitted if the element type can be inferred, though in that case it is likely that the arrayToken itself is also inferrable and can be omitted.

5.10.1. One-dimensional arrays

A one-dimensional array of n T elements may be initialized by any expression that returns a value of the desired type. Commonly, array allocation expressions are used. Some examples are shown here: 

type T(0)
method m(n: nat) {
  var a := new T[n];
  var b: array<int> := new int[8];
  var c: array := new T[9];
}

The initial values of the array elements are arbitrary values of type T. A one-dimensional array value can also be assigned using an ordered list of expressions enclosed in square brackets, as follows: 

a := new T[] [t1, t2, t3, t4];

The initialization can also use an expression that returns a function of type nat -> T: 

a := new int[5](i => i*i);

In fact, the initializer can simply be a function name for the right type of function: 

a := new int[5](Square);

The length of an array is retrieved using the immutable Length member. For example, the array allocated with a := new T[n]; satisfies: 

a.Length == n

Once an array is allocated, its length cannot be changed.

For any integer-based numeric i in the range 0 <= i < a.Length, the array selection expression a[i] retrieves element i (that is, the element preceded by i elements in the array). The element stored at i can be changed to a value t using the array update statement: 

a[i] := t;

Caveat: The type of the array created by new T[n] is array<T>. A mistake that is simple to make and that can lead to befuddlement is to write array<T> instead of T after new. For example, consider the following: 

type T(0)
method m(n: nat) {
  var a := new array<T>;
  var b := new array<T>[n];
  var c := new array<T>(n);  // resolution error
  var d := new array(n);  // resolution error
}

The first statement allocates an array of type array<T>, but of unknown length. The second allocates an array of type array<array<T>> of length n, that is, an array that holds n values of type array<T>. The third statement allocates an array of type array<T> and then attempts to invoke an anonymous constructor on this array, passing argument n. Since array has no constructors, let alone an anonymous constructor, this statement gives rise to an error. If the type-parameter list is omitted for a type that expects type parameters, Dafny will attempt to fill these in, so as long as the array type parameter can be inferred, it is okay to leave off the “<T>” in the fourth statement above. However, as with the third statement, array has no anonymous constructor, so an error message is generated.

5.10.2. Converting arrays to sequences

One-dimensional arrays support operations that convert a stretch of consecutive elements into a sequence. For any array a of type array<T>, integer-based numeric bounds lo and hi satisfying 0 <= lo <= hi <= a.Length, noting that bounds can equal the array’s length, the following operations each yields a seq<T>:

expression description
a[lo..hi] subarray conversion to sequence
a[lo..] drop
a[..hi] take
a[..] array conversion to sequence

The expression a[lo..hi] takes the first hi elements of the array, then drops the first lo elements thereof and returns what remains as a sequence, with length hi - lo. The other operations are special instances of the first. If lo is omitted, it defaults to 0 and if hi is omitted, it defaults to a.Length. In the last operation, both lo and hi have been omitted, thus a[..] returns the sequence consisting of all the array elements of a.

The subarray operations are especially useful in specifications. For example, the loop invariant of a binary search algorithm that uses variables lo and hi to delimit the subarray where the search key may still be found can be expressed as follows: 

key !in a[..lo] && key !in a[hi..]

Another use is to say that a certain range of array elements have not been changed since the beginning of a method: 

a[lo..hi] == old(a[lo..hi])

or since the beginning of a loop: 

ghost var prevElements := a[..];
while // ...
  invariant a[lo..hi] == prevElements[lo..hi]
{
  // ...
}

Note that the type of prevElements in this example is seq<T>, if a has type array<T>.

A final example of the subarray operation lies in expressing that an array’s elements are a permutation of the array’s elements at the beginning of a method, as would be done in most sorting algorithms. Here, the subarray operation is combined with the sequence-to-multiset conversion: 

multiset(a[..]) == multiset(old(a[..]))

5.10.3. Multi-dimensional arrays

An array of 2 or more dimensions is mostly like a one-dimensional array, except that new takes more length arguments (one for each dimension), and the array selection expression and the array update statement take more indices. For example: 

matrix := new T[m, n];
matrix[i, j], matrix[x, y] := matrix[x, y], matrix[i, j];

create a 2-dimensional array whose dimensions have lengths m and n, respectively, and then swaps the elements at i,j and x,y. The type of matrix is array2<T>, and similarly for higher-dimensional arrays (array3<T>, array4<T>, etc.). Note, however, that there is no type array0<T>, and what could have been array1<T> is actually named just array<T>. (Accordingly, array0 and array1 are just normal identifiers, not type names.)

The new operation above requires m and n to be non-negative integer-based numerics. These lengths can be retrieved using the immutable fields Length0 and Length1. For example, the following holds for the array created above: 

matrix.Length0 == m && matrix.Length1 == n

Higher-dimensional arrays are similar (Length0, Length1, Length2, …). The array selection expression and array update statement require that the indices are in bounds. For example, the swap statement above is well-formed only if: 

0 <= i < matrix.Length0 && 0 <= j < matrix.Length1 &&
0 <= x < matrix.Length0 && 0 <= y < matrix.Length1

In contrast to one-dimensional arrays, there is no operation to convert stretches of elements from a multi-dimensional array to a sequence.

There is however syntax to create a multi-dimensional array value using a function: see Section 9.16.

5.11. Iterator types (grammar)

See Section 7.5 for a description of iterator specifications.

An iterator provides a programming abstraction for writing code that iteratively returns elements. These CLU-style iterators are co-routines in the sense that they keep track of their own program counter and control can be transferred into and out of the iterator body.

An iterator is declared as follows: 

iterator Iter<T>(_in-params_) yields (_yield-params_)
  _specification_
{
  _body_
}

where T is a list of type parameters (as usual, if there are no type parameters, “<T>” is omitted). This declaration gives rise to a reference type with the same name, Iter<T>. In the signature, in-parameters and yield-parameters are the iterator’s analog of a method’s in-parameters and out-parameters. The difference is that the out-parameters of a method are returned to a caller just once, whereas the yield-parameters of an iterator are returned each time the iterator body performs a yield. The body consists of statements, like in a method body, but with the availability also of yield statements.

From the perspective of an iterator client, the iterator declaration can be understood as generating a class Iter<T> with various members, a simplified version of which is described next.

The Iter<T> class contains an anonymous constructor whose parameters are the iterator’s in-parameters: 

predicate Valid()
constructor (_in-params_)
  modifies this
  ensures Valid()

An iterator is created using new and this anonymous constructor. For example, an iterator willing to return ten consecutive integers from start can be declared as follows: 

iterator Gen(start: int) yields (x: int)
  yield ensures |xs| <= 10 && x == start + |xs| - 1
{
  var i := 0;
  while i < 10 invariant |xs| == i {
    x := start + i;
    yield;
    i := i + 1;
  }
}

An instance of this iterator is created using 

iter := new Gen(30);

It is used like this: 

method Main() {
  var i := new Gen(30);
  while true
    invariant i.Valid() && fresh(i._new)
    decreases 10 - |i.xs|
  {
    var m := i.MoveNext();
    if (!m) {break; }
    print i.x;
  }
}

The predicate Valid() says when the iterator is in a state where one can attempt to compute more elements. It is a postcondition of the constructor and occurs in the specification of the MoveNext member: 

method MoveNext() returns (more: bool)
  requires Valid()
  modifies this
  ensures more ==> Valid()

Note that the iterator remains valid as long as MoveNext returns true. Once MoveNext returns false, the MoveNext method can no longer be called. Note, the client is under no obligation to keep calling MoveNext until it returns false, and the body of the iterator is allowed to keep returning elements forever.

The in-parameters of the iterator are stored in immutable fields of the iterator class. To illustrate in terms of the example above, the iterator class Gen contains the following field: 

const start: int

The yield-parameters also result in members of the iterator class: 

var x: int

These fields are set by the MoveNext method. If MoveNext returns true, the latest yield values are available in these fields and the client can read them from there.

To aid in writing specifications, the iterator class also contains ghost members that keep the history of values returned by MoveNext. The names of these ghost fields follow the names of the yield-parameters with an “s” appended to the name (to suggest plural). Name checking rules make sure these names do not give rise to ambiguities. The iterator class for Gen above thus contains: 

ghost var xs: seq<int>

These history fields are changed automatically by MoveNext, but are not assignable by user code.

Finally, the iterator class contains some special fields for use in specifications. In particular, the iterator specification is recorded in the following immutable fields: 

ghost var _reads: set<object>
ghost var _modifies: set<object>
ghost var _decreases0: T0
ghost var _decreases1: T1
// ...

where there is a _decreases(i): T(i) field for each component of the iterator’s decreases clause.6 In addition, there is a field: 

ghost var _new: set<object>;

to which any objects allocated on behalf of the iterator body are added. The iterator body is allowed to remove elements from the _new set, but cannot by assignment to _new add any elements.

Note, in the precondition of the iterator, which is to hold upon construction of the iterator, the in-parameters are indeed in-parameters, not fields of this.

reads clauses on iterators have a different meaning than they do on functions and methods. Iterators may read any memory they like, but because arbitrary code may be executed whenever they yield control, they need to declare what memory locations must not be modified by other code in order to maintain correctness. The contents of an iterator’s reads clauses become part of the reads clause of the implicitly created Valid() predicate. This means if client code modifies any of this state, it will not be able to establish the precondition for the iterator’s MoveNext() method, and hence the iterator body will never resume if this state is modified.

It is regrettably tricky to use iterators. The language really ought to have a foreach statement to make this easier. Here is an example showing a definition and use of an iterator.

iterator Iter<T(0)>(s: set<T>) yields (x: T)
  yield ensures x in s && x !in xs[..|xs|-1]
  ensures s == set z | z in xs
{
  var r := s;
  while (r != {})
    invariant r !! set z | z in xs
    invariant s == r + set z | z in xs
  {
    var y :| y in r;
    assert y !in xs;
    r, x := r - {y}, y;
    assert y !in xs;
    yield;
    assert y == xs[|xs|-1]; // a lemma to help prove loop invariant
  }
}

method UseIterToCopy<T(0)>(s: set<T>) returns (t: set<T>)
  ensures s == t
{
  t := {};
  var m := new Iter(s);
  while (true)
    invariant m.Valid() && fresh(m._new)
    invariant t == set z | z in m.xs
    decreases s - t
  {
    var more := m.MoveNext();
    if (!more) { break; }
    t := t + {m.x};
  }
}

The design of iterators is under discussion and may change.

5.12. Arrow types (grammar)

Examples: 

(int) -> int
(bool,int) ~> bool
() --> object?

Functions are first-class values in Dafny. The types of function values are called arrow types (aka, function types). Arrow types have the form (TT) ~> U where TT is a (possibly empty) comma-delimited list of types and U is a type. TT is called the function’s domain type(s) and U is its range type. For example, the type of a function 

function F(x: int, arr: array<bool>): real
  requires x < 1000
  reads arr

is (int, array<bool>) ~> real.

As seen in the example above, the functions that are values of a type (TT) ~> U can have a precondition (as indicated by the requires clause) and can read values in the heap (as indicated by the reads clause). As described in Section 5.6.3.3,

A function declared without a reads clause is known by the type checker to be a partial function. For example, the type of 

function F(x: int, b: bool): real
  requires x < 1000

is (int, bool) --> real. Similarly, a function declared with neither a reads clause nor a requires clause is known by the type checker to be a total function. For example, the type of 

function F(x: int, b: bool): real

is (int, bool) -> real. In addition to functions declared by name, Dafny also supports anonymous functions by means of lambda expressions (see Section 9.13).

To simplify the appearance of the basic case where a function’s domain consists of a list of exactly one non-function, non-tuple type, the parentheses around the domain type can be dropped in this case. For example, you may write just T -> U for a total arrow type. This innocent simplification requires additional explanation in the case where that one type is a tuple type, since tuple types are also written with enclosing parentheses. If the function takes a single argument that is a tuple, an additional set of parentheses is needed. For example, the function 

function G(pair: (int, bool)): real

has type ((int, bool)) -> real. Note the necessary double parentheses. Similarly, a function that takes no arguments is different from one that takes a 0-tuple as an argument. For instance, the functions 

function NoArgs(): real
function Z(unit: ()): real

have types () -> real and (()) -> real, respectively.

The function arrows are right associative. For example, A -> B -> C means A -> (B -> C), whereas the other association requires explicit parentheses: (A -> B) -> C. As another example, A -> B --> C ~> D means A -> (B --> (C ~> D)).

Note that the receiver parameter of a named function is not part of the type. Rather, it is used when looking up the function and can then be thought of as being captured into the function definition. For example, suppose function F above is declared in a class C and that c references an object of type C; then, the following is type correct: 

var f: (int, bool) -> real := c.F;

whereas it would have been incorrect to have written something like: 

var f': (C, int, bool) -> real := F;  // not correct

The arrow types themselves do not divide a function’s parameters into ghost versus non-ghost. Instead, a function used as a first-class value is considered to be ghost if either the function or any of its arguments is ghost. The following example program illustrates: 

function F(x: int, ghost y: int): int
{
  x
}

method Example() {
  ghost var f: (int, int) -> int;
  var g: (int, int) -> int;
  var h: (int) -> int;
  var x: int;
  f := F;
  x := F(20, 30);
  g := F; // error: tries to assign ghost to non-ghost
  h := F; // error: wrong arity (and also tries to assign ghost to non-ghost)
}

In addition to its type signature, each function value has three properties, described next.

Every function implicitly takes the heap as an argument. No function ever depends on the entire heap, however. A property of the function is its declared upper bound on the set of heap locations it depends on for a given input. This lets the verifier figure out that certain heap modifications have no effect on the value returned by a certain function. For a function f: T ~> U and a value t of type T, the dependency set is denoted f.reads(t) and has type set<object>.

The second property of functions stems from the fact that every function is potentially partial. In other words, a property of a function is its precondition. For a function f: T ~> U, the precondition of f for a parameter value t of type T is denoted f.requires(t) and has type bool.

The third property of a function is more obvious—the function’s body. For a function f: T ~> U, the value that the function yields for an input t of type T is denoted f(t) and has type U.

Note that f.reads and f.requires are themselves functions. Without loss of generality, suppose f is defined as: 

function f<T,U>(x: T): U
  reads R(x)
  requires P(x)
{
  body(x)
}

where P, R, and body are declared as: 

predicate P<T>(x: T)
function R<T>(x: T): set<object>
function body<T,U>(x: T): U

Then, f.reads is a function of type T ~> set<object?> whose reads and requires properties are given by the definition: 

function f.reads<T>(x: T): set<object>
  reads R(x)
  requires P(x)
{
  R(x)
}

f.requires is a function of type T ~> bool whose reads and requires properties are given by the definition: 

predicate f_requires<T>(x: T)
  requires true
  reads if P(x) then R(x) else *
{
  P(x)
}

where * is a notation to indicate that any memory location can be read, but is not valid Dafny syntax.

In these examples, if f instead had type T --> U or T -> U, then the type of f.reads is T -> set<object?> and the type of f.requires is T -> bool.

Dafny also supports anonymous functions by means of lambda expressions. See Section 9.13.

5.13. Tuple types

TupleType = "(" [ [ "ghost" ] Type { "," [ "ghost" ] Type } ] ")"

Dafny builds in record types that correspond to tuples and gives these a convenient special syntax, namely parentheses. For example, for what might have been declared as 

datatype Pair<T,U> = Pair(0: T, 1: U)

Dafny provides the type (T, U) and the constructor (t, u), as if the datatype’s name were “” (i.e., an empty string) and its type arguments are given in round parentheses, and as if the constructor name were the empty string. Note that the destructor names are 0 and 1, which are legal identifier names for members. For an example showing the use of a tuple destructor, here is a property that holds of 2-tuples (that is, pairs): 

method m(){
  assert (5, true).1 == true;
}

Dafny declares n-tuples where n is 0 or 2 or more. There are no 1-tuples, since parentheses around a single type or a single value have no semantic meaning. The 0-tuple type, (), is often known as the unit type and its single value, also written (), is known as unit.

The ghost modifier can be used to mark tuple components as being used for specification only: 

const pair: (int, ghost int) := (1, ghost 2)

5.14. Algebraic Datatypes (grammar)

Dafny offers two kinds of algebraic datatypes, those defined inductively (with datatype) and those defined coinductively (with codatatype). The salient property of every datatype is that each value of the type uniquely identifies one of the datatype’s constructors and each constructor is injective in its parameters.

5.14.1. Inductive datatypes

The values of inductive datatypes can be seen as finite trees where the leaves are values of basic types, numeric types, reference types, coinductive datatypes, or arrow types. Indeed, values of inductive datatypes can be compared using Dafny’s well-founded < ordering.

An inductive datatype is declared as follows: 

datatype D<T> = _Ctors_

where Ctors is a nonempty |-separated list of (datatype) constructors for the datatype. Each constructor has the form:

C(_params_)

where params is a comma-delimited list of types, optionally preceded by a name for the parameter and a colon, and optionally preceded by the keyword ghost. If a constructor has no parameters, the parentheses after the constructor name may be omitted. If no constructor takes a parameter, the type is usually called an enumeration; for example: 

datatype Friends = Agnes | Agatha | Jermaine | Jack

For every constructor C, Dafny defines a discriminator C?, which is a member that returns true if and only if the datatype value has been constructed using C. For every named parameter p of a constructor C, Dafny defines a destructor p, which is a member that returns the p parameter from the C call used to construct the datatype value; its use requires that C? holds. For example, for the standard List type 

datatype List<T> = Nil | Cons(head: T, tail: List<T>)

the following holds: 

method m() {
  assert Cons(5, Nil).Cons? && Cons(5, Nil).head == 5;
}

Note that the expression 

Cons(5, Nil).tail.head

is not well-formed by itself, since Cons(5, Nil).tail does not necessarily satisfy Cons?.

A constructor can have the same name as the enclosing datatype; this is especially useful for single-constructor datatypes, which are often called record types. For example, a record type for black-and-white pixels might be represented as follows: 

datatype Pixel = Pixel(x: int, y: int, on: bool)

To call a constructor, it is usually necessary only to mention the name of the constructor, but if this is ambiguous, it is always possible to qualify the name of constructor by the name of the datatype. For example, Cons(5, Nil) above can be written 

List.Cons(5, List.Nil)

As an alternative to calling a datatype constructor explicitly, a datatype value can be constructed as a change in one parameter from a given datatype value using the datatype update expression. For any d whose type is a datatype that includes a constructor C that has a parameter (destructor) named f of type T, and any expression t of type T, 

d.(f := t)

constructs a value like d but whose f parameter is t. The operation requires that d satisfies C?. For example, the following equality holds: 

method m(){
  assert Cons(4, Nil).(tail := Cons(3, Nil)) == Cons(4, Cons(3, Nil));
}

The datatype update expression also accepts multiple field names, provided these are distinct. For example, a node of some inductive datatype for trees may be updated as follows:

node.(left := L, right := R)

The operator < is defined for two operands of the same datataype. It means is properly contained in. For example, in the code 

datatype X = T(t: X) | I(i: int)
method comp() {
  var x := T(I(0));
  var y := I(0);
  var z := I(1);
  assert x.t < x;
  assert y < x;
  assert !(x < x);
  assert z < x; // FAILS
}

x is a datatype value that holds a T variant, which holds a I variant, which holds an integer 0. The value x.t is a portion of the datatype structure denoted by x, so x.t < x is true. Datatype values are immutable mathematical values, so the value of y is identical to the value of x.t, so y < x is true also, even though y is constructed from the ground up, rather than as a portion of x. However, z is different than either y or x.t and consequently z < x is not provable. Furthermore, < does not include ==, so x < x is false.

Note that only < is defined; not <= or > or >=.

Also, < is underspecified. With the above code, one can prove neither z < x nor !(z < x) and neither z < y nor !(z < y). In each pair, though, one or the other is true, so (z < x) || !(z < x) is provable.

5.14.2. Coinductive datatypes

Whereas Dafny insists that there is a way to construct every inductive datatype value from the ground up, Dafny also supports coinductive datatypes, whose constructors are evaluated lazily, and hence the language allows infinite structures. A coinductive datatype is declared using the keyword codatatype; other than that, it is declared and used like an inductive datatype.

For example, 

codatatype IList<T> = Nil | Cons(head: T, tail: IList<T>)
codatatype Stream<T> = More(head: T, tail: Stream<T>)
codatatype Tree<T> = Node(left: Tree<T>, value: T, right: Tree<T>)

declare possibly infinite lists (that is, lists that can be either finite or infinite), infinite streams (that is, lists that are always infinite), and infinite binary trees (that is, trees where every branch goes on forever), respectively.

The paper Co-induction Simply, by Leino and Moskal[@LEINO:Dafny:Coinduction], explains Dafny’s implementation and verification of coinductive types. We capture the key features from that paper in the following section but the reader is referred to that paper for more complete details and to supply bibliographic references that are omitted here.

5.14.3. Coinduction

Mathematical induction is a cornerstone of programming and program verification. It arises in data definitions (e.g., some algebraic data structures can be described using induction), it underlies program semantics (e.g., it explains how to reason about finite iteration and recursion), and it is used in proofs (e.g., supporting lemmas about data structures use inductive proofs). Whereas induction deals with finite things (data, behavior, etc.), its dual, coinduction, deals with possibly infinite things. Coinduction, too, is important in programming and program verification: it arises in data definitions (e.g., lazy data structures), semantics (e.g., concurrency), and proofs (e.g., showing refinement in a coinductive big-step semantics). It is thus desirable to have good support for both induction and coinduction in a system for constructing and reasoning about programs.

Co-datatypes and co-recursive functions make it possible to use lazily evaluated data structures (like in Haskell or Agda). Greatest predicates, defined by greatest fix-points, let programs state properties of such data structures (as can also be done in, for example, Coq). For the purpose of writing coinductive proofs in the language, we introduce greatest and least lemmas. A greatest lemma invokes the coinduction hypothesis much like an inductive proof invokes the induction hypothesis. Underneath the hood, our coinductive proofs are actually approached via induction: greatest and least lemmas provide a syntactic veneer around this approach.

The following example gives a taste of how the coinductive features in Dafny come together to give straightforward definitions of infinite matters. 

// infinite streams
codatatype IStream<T> = ICons(head: T, tail: IStream<T>)

// pointwise product of streams
function Mult(a: IStream<int>, b: IStream<int>): IStream<int>
{ ICons(a.head * b.head, Mult(a.tail, b.tail)) }

// lexicographic order on streams
greatest predicate Below(a: IStream<int>, b: IStream<int>)
{ a.head <= b.head &&
  ((a.head == b.head) ==> Below(a.tail, b.tail))
}

// a stream is Below its Square
greatest lemma Theorem_BelowSquare(a: IStream<int>)
  ensures Below(a, Mult(a, a))
{ assert a.head <= Mult(a, a).head;
  if a.head == Mult(a, a).head {
    Theorem_BelowSquare(a.tail);
  }
}

// an incorrect property and a bogus proof attempt
greatest lemma NotATheorem_SquareBelow(a: IStream<int>)
  ensures Below(Mult(a, a), a) // ERROR
{
  NotATheorem_SquareBelow(a);
}

The example defines a type IStream of infinite streams, with constructor ICons and destructors head and tail. Function Mult performs pointwise multiplication on infinite streams of integers, defined using a co-recursive call (which is evaluated lazily). Greatest predicate Below is defined as a greatest fix-point, which intuitively means that the co-predicate will take on the value true if the recursion goes on forever without determining a different value. The greatest lemma states the theorem Below(a, Mult(a, a)). Its body gives the proof, where the recursive invocation of the co-lemma corresponds to an invocation of the coinduction hypothesis.

The proof of the theorem stated by the first co-lemma lends itself to the following intuitive reading: To prove that a is below Mult(a, a), check that their heads are ordered and, if the heads are equal, also prove that the tails are ordered. The second co-lemma states a property that does not always hold; the verifier is not fooled by the bogus proof attempt and instead reports the property as unproved.

We argue that these definitions in Dafny are simple enough to level the playing field between induction (which is familiar) and coinduction (which, despite being the dual of induction, is often perceived as eerily mysterious). Moreover, the automation provided by our SMT-based verifier reduces the tedium in writing coinductive proofs. For example, it verifies Theorem_BelowSquare from the program text given above—no additional lemmas or tactics are needed. In fact, as a consequence of the automatic-induction heuristic in Dafny, the verifier will automatically verify Theorem_BelowSquare even given an empty body.

Just like there are restrictions on when an inductive hypothesis can be invoked, there are restrictions on how a coinductive hypothesis can be used. These are, of course, taken into consideration by Dafny’s verifier. For example, as illustrated by the second greatest lemma above, invoking the coinductive hypothesis in an attempt to obtain the entire proof goal is futile. (We explain how this works in the section about greatest lemmas) Our initial experience with coinduction in Dafny shows it to provide an intuitive, low-overhead user experience that compares favorably to even the best of today’s interactive proof assistants for coinduction. In addition, the coinductive features and verification support in Dafny have other potential benefits. The features are a stepping stone for verifying functional lazy programs with Dafny. Coinductive features have also shown to be useful in defining language semantics, as needed to verify the correctness of a compiler, so this opens the possibility that such verifications can benefit from SMT automation.

5.14.3.1. Well-Founded Function/Method Definitions

The Dafny programming language supports functions and methods. A function in Dafny is a mathematical function (i.e., it is well-defined, deterministic, and pure), whereas a method is a body of statements that can mutate the state of the program. A function is defined by its given body, which is an expression. To ensure that function definitions are mathematically consistent, Dafny insists that recursive calls be well-founded, enforced as follows: Dafny computes the call graph of functions. The strongly connected components within it are clusters of mutually recursive definitions; the clusters are arranged in a DAG. This stratifies the functions so that a call from one cluster in the DAG to a lower cluster is allowed arbitrarily. For an intra-cluster call, Dafny prescribes a proof obligation that is taken through the program verifier’s reasoning engine. Semantically, each function activation is labeled by a rank—a lexicographic tuple determined by evaluating the function’s decreases clause upon invocation of the function. The proof obligation for an intra-cluster call is thus that the rank of the callee is strictly less (in a language-defined well-founded relation) than the rank of the caller. Because these well-founded checks correspond to proving termination of executable code, we will often refer to them as “termination checks”. The same process applies to methods.

Lemmas in Dafny are commonly introduced by declaring a method, stating the property of the lemma in the postcondition (keyword ensures) of the method, perhaps restricting the domain of the lemma by also giving a precondition (keyword requires), and using the lemma by invoking the method. Lemmas are stated, used, and proved as methods, but since they have no use at run time, such lemma methods are typically declared as ghost, meaning that they are not compiled into code. The keyword lemma introduces such a method. Control flow statements correspond to proof techniques—case splits are introduced with if statements, recursion and loops are used for induction, and method calls for structuring the proof. Additionally, the statement: 

forall x | P(x) { Lemma(x); }

is used to invoke Lemma(x) on all x for which P(x) holds. If Lemma(x) ensures Q(x), then the forall statement establishes 

forall x :: P(x) ==> Q(x).
5.14.3.2. Defining Coinductive Datatypes

Each value of an inductive datatype is finite, in the sense that it can be constructed by a finite number of calls to datatype constructors. In contrast, values of a coinductive datatype, or co-datatype for short, can be infinite. For example, a co-datatype can be used to represent infinite trees.

Syntactically, the declaration of a co-datatype in Dafny looks like that of a datatype, giving prominence to the constructors (following Coq). The following example defines a co-datatype Stream of possibly infinite lists.

codatatype Stream<T> = SNil | SCons(head: T, tail: Stream)
function Up(n: int): Stream<int> { SCons(n, Up(n+1)) }
function FivesUp(n: int): Stream<int>
  decreases 4 - (n - 1) % 5
{
  if (n % 5 == 0) then
    SCons(n, FivesUp(n+1))
  else
    FivesUp(n+1)
}

Stream is a coinductive datatype whose values are possibly infinite lists. Function Up returns a stream consisting of all integers upwards of n and FivesUp returns a stream consisting of all multiples of 5 upwards of n . The self-call in Up and the first self-call in FivesUp sit in productive positions and are therefore classified as co-recursive calls, exempt from termination checks. The second self-call in FivesUp is not in a productive position and is therefore subject to termination checking; in particular, each recursive call must decrease the rank defined by the decreases clause.

Analogous to the common finite list datatype, Stream declares two constructors, SNil and SCons. Values can be destructed using match expressions and statements. In addition, like for inductive datatypes, each constructor C automatically gives rise to a discriminator C? and each parameter of a constructor can be named in order to introduce a corresponding destructor. For example, if xs is the stream SCons(x, ys), then xs.SCons? and xs.head == x hold. In contrast to datatype declarations, there is no grounding check for co-datatypes—since a codatatype admits infinite values, the type is nevertheless inhabited.

5.14.3.3. Creating Values of Co-datatypes

To define values of co-datatypes, one could imagine a “co-function” language feature: the body of a “co-function” could include possibly never-ending self-calls that are interpreted by a greatest fix-point semantics (akin to a CoFixpoint in Coq). Dafny uses a different design: it offers only functions (not “co-functions”), but it classifies each intra-cluster call as either recursive or co-recursive. Recursive calls are subject to termination checks. Co-recursive calls may be never-ending, which is what is needed to define infinite values of a co-datatype. For example, function Up(n) in the preceding example is defined as the stream of numbers from n upward: it returns a stream that starts with n and continues as the co-recursive call Up(n + 1).

To ensure that co-recursive calls give rise to mathematically consistent definitions, they must occur only in productive positions. This says that it must be possible to determine each successive piece of a co-datatype value after a finite amount of work. This condition is satisfied if every co-recursive call is syntactically guarded by a constructor of a co-datatype, which is the criterion Dafny uses to classify intra-cluster calls as being either co-recursive or recursive. Calls that are classified as co-recursive are exempt from termination checks.

A consequence of the productivity checks and termination checks is that, even in the absence of talking about least or greatest fix-points of self-calling functions, all functions in Dafny are deterministic. Since there cannot be multiple fix-points, the language allows one function to be involved in both recursive and co-recursive calls, as we illustrate by the function FivesUp.

5.14.3.4. Co-Equality

Equality between two values of a co-datatype is a built-in co-predicate. It has the usual equality syntax s == t, and the corresponding prefix equality is written s ==#[k] t. And similarly for s != t and s !=#[k] t.

5.14.3.5. Greatest predicates

Determining properties of co-datatype values may require an infinite number of observations. To that end, Dafny provides greatest predicates which are function declarations that use the greatest predicate keyword phrase. Self-calls to a greatest predicate need not terminate. Instead, the value defined is the greatest fix-point of the given recurrence equations. Continuing the preceding example, the following code defines a greatest predicate that holds for exactly those streams whose payload consists solely of positive integers. The greatest predicate definition implicitly also gives rise to a corresponding prefix predicate, Pos#. The syntax for calling a prefix predicate sets apart the argument that specifies the prefix length, as shown in the last line; for this figure, we took the liberty of making up a coordinating syntax for the signature of the automatically generated prefix predicate (which is not part of Dafny syntax).

greatest predicate Pos[nat](s: Stream<int>)
{
  match s
  case SNil => true
  case SCons(x, rest) => x > 0 && Pos(rest)
}

The following code is automatically generated by the Dafny compiler: 

predicate Pos#[_k: nat](s: Stream<int>)
  decreases _k
{ if _k == 0 then true else
  match s
  case SNil => true
  case SCons(x, rest) => x > 0 && Pos#[_k-1](rest)
}

Some restrictions apply. To guarantee that the greatest fix-point always exists, the (implicit functor defining the) greatest predicate must be monotonic. This is enforced by a syntactic restriction on the form of the body of greatest predicates: after conversion to negation normal form (i.e., pushing negations down to the atoms), intra-cluster calls of greatest predicates must appear only in positive positions—that is, they must appear as atoms and must not be negated. Additionally, to guarantee soundness later on, we require that they appear in continous positions—that is, in negation normal form, when they appear under existential quantification, the quantification needs to be limited to a finite range7. Since the evaluation of a greatest predicate might not terminate, greatest predicates are always ghost. There is also a restriction on the call graph that a cluster containing a greatest predicate must contain only greatest predicates, no other kinds of functions.

extreme predicates and lemmas, one in which _k has type nat and one in which it has type ORDINAL (the default). The continuous restriction applies only when _k is nat. Also, higher-order function support in Dafny is rather modest and typical reasoning patterns do not involve them, so this restriction is not as limiting as it would have been in, e.g., Coq.

A greatest predicate declaration of P defines not just a greatest predicate, but also a corresponding prefix predicate P#. A prefix predicate is a finite unrolling of a co-predicate. The prefix predicate is constructed from the co-predicate by

For example, for greatest predicate Pos, the definition of the prefix predicate Pos# is as suggested above. Syntactically, the prefix-length argument passed to a prefix predicate to indicate how many times to unroll the definition is written in square brackets, as in Pos#[k](s). In the Dafny grammar this is called a HashCall. The definition of Pos# is available only at clusters strictly higher than that of Pos; that is, Pos and Pos# must not be in the same cluster. In other words, the definition of Pos cannot depend on Pos#.

5.14.3.6. Coinductive Proofs

From what we have said so far, a program can make use of properties of co-datatypes. For example, a method that declares Pos(s) as a precondition can rely on the stream s containing only positive integers. In this section, we consider how such properties are established in the first place.

5.14.3.6.1. Properties of Prefix Predicates

Among other possible strategies for establishing coinductive properties we take the time-honored approach of reducing coinduction to induction. More precisely, Dafny passes to the SMT solver an assumption D(P) for every greatest predicate P, where:

D(P) = forall x • P(x) <==> forall k • P#[k](x)

In other words, a greatest predicate is true iff its corresponding prefix predicate is true for all finite unrollings.

In Sec. 4 of the paper [Co-induction Simply] a soundness theorem of such assumptions is given, provided the greatest predicates meet the continous restrictions. An example proof of Pos(Up(n)) for every n > 0 is shown here:

lemma UpPosLemma(n: int)
  requires n > 0
  ensures Pos(Up(n))
{
  forall k | 0 <= k { UpPosLemmaK(k, n); }
}

lemma UpPosLemmaK(k: nat, n: int)
  requires n > 0
  ensures Pos#[k](Up(n))
  decreases k
{
  if k != 0 {
    // this establishes Pos#[k-1](Up(n).tail)
    UpPosLemmaK(k-1, n+1);
  }
}

The lemma UpPosLemma proves Pos(Up(n)) for every n > 0. We first show Pos#[k](Up(n )), for n > 0 and an arbitrary k, and then use the forall statement to show forall k • Pos#[k](Up(n)). Finally, the axiom D(Pos) is used (automatically) to establish the greatest predicate.

5.14.3.6.2. Greatest lemmas

As we just showed, with help of the D axiom we can now prove a greatest predicate by inductively proving that the corresponding prefix predicate holds for all prefix lengths k. In this section, we introduce greatest lemma declarations, which bring about two benefits. The first benefit is that greatest lemmas are syntactic sugar and reduce the tedium of having to write explicit quantifications over k. The second benefit is that, in simple cases, the bodies of greatest lemmas can be understood as coinductive proofs directly. As an example consider the following greatest lemma.

greatest lemma UpPosLemma(n: int)
  requires n > 0
  ensures Pos(Up(n))
{
  UpPosLemma(n+1);
}

This greatest lemma can be understood as follows: UpPosLemma invokes itself co-recursively to obtain the proof for Pos(Up(n).tail) (since Up(n).tail equals Up(n+1)). The proof glue needed to then conclude Pos(Up(n)) is provided automatically, thanks to the power of the SMT-based verifier.

5.14.3.6.3. Prefix Lemmas

To understand why the above UpPosLemma greatest lemma code is a sound proof, let us now describe the details of the desugaring of greatest lemmas. In analogy to how a greatest predicate declaration defines both a greatest predicate and a prefix predicate, a greatest lemma declaration defines both a greatest lemma and prefix lemma. In the call graph, the cluster containing a greatest lemma must contain only greatest lemmas and prefix lemmas, no other methods or function. By decree, a greatest lemma and its corresponding prefix lemma are always placed in the same cluster. Both greatest lemmas and prefix lemmas are always ghost code.

The prefix lemma is constructed from the greatest lemma by

Note that this rewriting removes all co-recursive calls of greatest lemmas, replacing them with recursive calls to prefix lemmas. These recursive calls are, as usual, checked to be terminating. We allow the pre-declared identifier _k to appear in the original body of the greatest lemma.8

We can now think of the body of the greatest lemma as being replaced by a forall call, for every k , to the prefix lemma. By construction, this new body will establish the greatest lemma’s declared postcondition (on account of the D axiom, and remembering that only the positive continuous occurrences of greatest predicates in the greatest lemma’s postcondition are rewritten), so there is no reason for the program verifier to check it.

The actual desugaring of our greatest lemma UpPosLemma is in fact the previous code for the UpPosLemma lemma except that UpPosLemmaK is named UpPosLemma# and modulo a minor syntactic difference in how the k argument is passed.

In the recursive call of the prefix lemma, there is a proof obligation that the prefixlength argument _k - 1 is a natural number. Conveniently, this follows from the fact that the body has been wrapped in an if _k != 0 statement. This also means that the postcondition must hold trivially when _k == 0, or else a postcondition violation will be reported. This is an appropriate design for our desugaring, because greatest lemmas are expected to be used to establish greatest predicates, whose corresponding prefix predicates hold trivially when _k = 0. (To prove other predicates, use an ordinary lemma, not a greatest lemma.)

It is interesting to compare the intuitive understanding of the coinductive proof in using a greatest lemma with the inductive proof in using a lemma. Whereas the inductive proof is performing proofs for deeper and deeper equalities, the greatest lemma can be understood as producing the infinite proof on demand.

5.14.3.7. Abstemious and voracious functions

Some functions on codatatypes are abstemious, meaning that they do not need to unfold a datatype instance very far (perhaps just one destructor call) to prove a relevant property. Knowing this is the case can aid the proofs of properties about the function. The attribute {:abstemious} can be applied to a function definition to indicate this.

TODO: Say more about the effect of this attribute and when it should be applied (and likely, correct the paragraph above).

6. Member declarations

Members are the various kinds of methods, the various kinds of functions, mutable fields, and constant fields. These are usually associated with classes, but they also may be declared (with limitations) in traits, newtypes and datatypes (but not in subset types or type synonyms).

6.1. Field Declarations (grammar)

Examples: 

class C {
  var c: int  // no initialization
  ghost var 123: bv10  // name may be a sequence of digits
  var d: nat, e: real  // type is required
}

A field declaration is not permitted in a value type nor as a member of a module (despite there being an implicit unnamed class).

The field name is either an identifier (that is not allowed to start with a leading underscore) or some digits. Digits are used if you want to number your fields, e.g. “0”, “1”, etc. The digits do not denote numbers but sequences of digits, so 0, 00, 0_0 are all different.

A field x of some type T is declared as: 

var x: T

A field declaration declares one or more fields of the enclosing class. Each field is a named part of the state of an object of that class. A field declaration is similar to but distinct from a variable declaration statement. Unlike for local variables and bound variables, the type is required and will not be inferred.

Unlike method and function declarations, a field declaration is not permitted as a member of a module, even though there is an implicit class. Fields can be declared in either an explicit class or a trait. A class that inherits from multiple traits will have all the fields declared in any of its parent traits.

Fields that are declared as ghost can only be used in specifications, not in code that will be compiled into executable code.

Fields may not be declared static.

6.2. Constant Field Declarations (grammar)

Examples: 

const c: int
ghost const d := 5
class A {
  const e: bool
  static const f: int
}

A const declaration declares a name bound to a value, which value is fixed after initialization.

The declaration must either have a type or an initializing expression (or both). If the type is omitted, it is inferred from the initializing expression.

6.3. Method Declarations (grammar)

Examples: 

method m(i: int) requires i > 0 {}
method p() returns (r: int) { r := 0; }
method q() returns (r: int, s: int, t: nat) ensures r < s < t { r := 0; s := 1; t := 2; }
ghost method g() {}
class A {
  method f() {}
  constructor Init() {}
  static method g<T>(t: T) {}
}
lemma L(p: bool) ensures p || !p {}
twostate lemma TL(p: bool) ensures p || !p {}
least lemma LL[nat](p: bool) ensures p || !p {}
greatest lemma GL(p: bool) ensures p || !p {}
abstract module M { method m(i: int) }
module N refines M { method m ... {} }

Method declarations include a variety of related types of methods:

A method signature specifies the method generic parameters, input parameters and return parameters. The formal parameters are not allowed to have ghost specified if ghost was already specified for the method. Within the body of a method, formal (input) parameters are immutable, that is, they may not be assigned to, though their array elements or fields may be assigned, if otherwise permitted. The out-parameters are mutable and must be assigned in the body of the method.

An ellipsis is used when a method or function is being redeclared in a module that refines another module. (cf. Section 10) In that case the signature is copied from the module that is being refined. This works because Dafny does not support method or function overloading, so the name of the class method uniquely identifies it without the signature.

See Section 7.2 for a description of the method specification.

Here is an example of a method declaration.

method {:att1}{:att2} M<T1, T2>(a: A, b: B, c: C)
                                        returns (x: X, y: Y, z: Z)
  requires Pre
  modifies Frame
  ensures Post
  decreases Rank
{
  Body
}

where :att1 and :att2 are attributes of the method, T1 and T2 are type parameters of the method (if generic), a, b, c are the method’s in-parameters, x, y, z are the method’s out-parameters, Pre is a boolean expression denoting the method’s precondition, Frame denotes a set of objects whose fields may be updated by the method, Post is a boolean expression denoting the method’s postcondition, Rank is the method’s variant function, and Body is a list of statements that implements the method. Frame can be a list of expressions, each of which is a set of objects or a single object, the latter standing for the singleton set consisting of that one object. The method’s frame is the union of these sets, plus the set of objects allocated by the method body. For example, if c and d are parameters of a class type C, then

modifies {c, d}
modifies {c} + {d}
modifies c, {d}
modifies c, d

all mean the same thing.

If the method is an extreme lemma ( a least or greatest lemma), then the method signature may also state the type of the k parameter as either nat or ORDINAL. These are described in Section 12.5.3 and subsequent sections.

6.3.1. Ordinary methods

A method can be declared as ghost by preceding the declaration with the keyword ghost and as static by preceding the declaration with the keyword static. The default is non-static (i.e., instance) for methods declared in a type and non-ghost. An instance method has an implicit receiver parameter, this. A static method M in a class C can be invoked by C.M(…).

An ordinary method is declared with the method keyword; the section about constructors explains methods that instead use the constructor keyword; the section about lemmas discusses methods that are declared with the lemma keyword. Methods declared with the least lemma or greatest lemma keyword phrases are discussed later in the context of extreme predicates (see the section about greatest lemmas).

A method without a body is abstract. A method is allowed to be abstract under the following circumstances:

6.3.2. Constructors

To write structured object-oriented programs, one often relies on objects being constructed only in certain ways. For this purpose, Dafny provides constructor (method)s. A constructor is declared with the keyword constructor instead of method; constructors are permitted only in classes. A constructor is allowed to be declared as ghost, in which case it can only be used in ghost contexts.

A constructor can only be called at the time an object is allocated (see object-creation examples below). Moreover, when a class contains a constructor, every call to new for a class must be accompanied by a call to one of its constructors. A class may declare no constructors or one or more constructors.

In general, a constructor is responsible for initializating the instance fields of its class. However, any field that is given an initializer in its declaration may not be reassigned in the body of the constructor.

6.3.2.1. Classes with no explicit constructors

For a class that declares no constructors, an instance of the class is created with 

c := new C;

This allocates an object and initializes its fields to values of their respective types (and initializes each const field with a RHS to its specified value). The RHS of a const field may depend on other const or var fields, but circular dependencies are not allowed.

This simple form of new is allowed only if the class declares no constructors, which is not possible to determine in every scope. It is easy to determine whether or not a class declares any constructors if the class is declared in the same module that performs the new. If the class is declared in a different module and that module exports a constructor, then it is also clear that the class has a constructor (and thus this simple form of new cannot be used). (Note that an export set that reveals a class C also exports the anonymous constructor of C, if any.) But if the module that declares C does not export any constructors for C, then callers outside the module do not know whether or not C has a constructor. Therefore, this simple form of new is allowed only for classes that are declared in the same module as the use of new.

The simple new C is allowed in ghost contexts. Also, unlike the forms of new that call a constructor or initialization method, it can be used in a simultaneous assignment; for example 

c, d, e := new C, new C, 15;

is legal.

As a shorthand for writing 

c := new C;
c.Init(args);

where Init is an initialization method (see the top of the section about class types), one can write 

c := new C.Init(args);

but it is more typical in such a case to declare a constructor for the class.

(The syntactic support for initialization methods is provided for historical reasons. It may be deprecated in some future version of Dafny. In most cases, a constructor is to be preferred.)

6.3.2.2. Classes with one or more constructors

Like other class members, constructors have names. And like other members, their names must be distinct, even if their signatures are different. Being able to name constructors promotes names like InitFromList or InitFromSet (or just FromList and FromSet). Unlike other members, one constructor is allowed to be anonymous; in other words, an anonymous constructor is a constructor whose name is essentially the empty string. For example: 

class Item {
  constructor I(xy: int) // ...
  constructor (x: int, y: int)
  // ...
}

The named constructor is invoked as 

  i := new Item.I(42);

The anonymous constructor is invoked as 

  m := new Item(45, 29);

dropping the “.”.

6.3.2.3. Two-phase constructors

The body of a constructor contains two sections, an initialization phase and a post-initialization phase, separated by a new; statement. If there is no new; statement, the entire body is the initialization phase. The initialization phase is intended to initialize field variables that were not given values in their declaration; it may not reassign to fields that do have initializers in their declarations. In this phase, uses of the object reference this are restricted; a program may use this

A const field with a RHS is not allowed to be assigned anywhere else. A const field without a RHS may be assigned only in constructors, and more precisely only in the initialization phase of constructors. During this phase, a const field may be assigned more than once; whatever value the const field has at the end of the initialization phase is the value it will have forever thereafter.

For a constructor declared as ghost, the initialization phase is allowed to assign both ghost and non-ghost fields. For such an object, values of non-ghost fields at the end of the initialization phase are in effect no longer changeable.

There are no restrictions on expressions or statements in the post-initialization phase.

6.3.3. Lemmas

Sometimes there are steps of logic required to prove a program correct, but they are too complex for Dafny to discover and use on its own. When this happens, we can often give Dafny assistance by providing a lemma. This is done by declaring a method with the lemma keyword. Lemmas are implicitly ghost methods and the ghost keyword cannot be applied to them.

Syntactically, lemmas can be placed where ghost methods can be placed, but they serve a significantly different function. First of all, a lemma is forbidden to have modifies clause: it may not change anything about even the ghost state; ghost methods may have modifies clauses and may change ghost (but not non-ghost) state. Furthermore, a lemma is not allowed to allocate any new objects. And a lemma may be used in the program text in places where ghost methods may not, such as within expressions (cf. Section 21.1).

Lemmas may, but typically do not, have out-parameters.

In summary, a lemma states a logical fact, summarizing an inference that the verifier cannot do on its own. Explicitly “calling” a lemma in the program text tells the verifier to use that fact at that location with the actual arguments substituted for the formal parameters. The lemma is proved separately for all cases of its formal parameters that satisfy the preconditions of the lemma.

For an example, see the FibProperty lemma in Section 12.5.2.

See the Dafny Lemmas tutorial for more examples and hints for using lemmas.

6.3.4. Two-state lemmas and functions

The heap is an implicit parameter to every function, though a function is only allowed to read those parts of the mutable heap that it admits to in its reads clause. Sometimes, it is useful for a function to take two heap parameters, for example, so the function can return the difference between the value of a field in the two heaps. Such a two-state function is declared by twostate function (or twostate predicate, which is the same as a twostate function that returns a bool). A two-state function is always ghost. It is appropriate to think of these two implicit heap parameters as representing a “current” heap and an “old” heap.

For example, the predicate 

class Cell { var data: int  constructor(i: int) { data := i; } }
twostate predicate Increasing(c: Cell)
  reads c
{
  old(c.data) <= c.data
}

returns true if the value of c.data has not been reduced from the old state to the current. Dereferences in the current heap are written as usual (e.g., c.data) and must, as usual, be accounted for in the function’s reads clause. Dereferences in the old heap are enclosed by old (e.g., old(c.data)), just like when one dereferences a method’s initial heap. The function is allowed to read anything in the old heap; the reads clause only declares dependencies on locations in the current heap. Consequently, the frame axiom for a two-state function is sensitive to any change in the old-heap parameter; in other words, the frame axiom says nothing about two invocations of the two-state function with different old-heap parameters.

At a call site, the two-state function’s current-heap parameter is always passed in as the caller’s current heap. The two-state function’s old-heap parameter is by default passed in as the caller’s old heap (that is, the initial heap if the caller is a method and the old heap if the caller is a two-state function). While there is never a choice in which heap gets passed as the current heap, the caller can use any preceding heap as the argument to the two-state function’s old-heap parameter. This is done by labeling a state in the caller and passing in the label, just like this is done with the built-in old function.

For example, the following assertions all hold: 

method Caller(c: Cell)
  modifies c
{
  c.data := c.data + 10;
  label L:
  assert Increasing(c);
  c.data := c.data - 2;
  assert Increasing(c);
  assert !Increasing@L(c);
}

The first call to Increasing uses Caller’s initial state as the old-heap parameter, and so does the second call. The third call instead uses as the old-heap parameter the heap at label L, which is why the third call returns false. As shown in the example, an explicitly given old-heap parameter is given after an @-sign (which follows the name of the function and any explicitly given type parameters) and before the open parenthesis (after which the ordinary parameters are given).

A two-state function is allowed to be called only from a two-state context, which means a method, a two-state lemma (see below), or another two-state function. Just like a label used with an old expression, any label used in a call to a two-state function must denote a program point that dominates the call. This means that any control leading to the call must necessarily have passed through the labeled program point.

Any parameter (including the receiver parameter, if any) passed to a two-state function must have been allocated already in the old state. For example, the second call to Diff in method M is illegal, since d was not allocated on entry to M: 

twostate function Diff(c: Cell, d: Cell): int
  reads d
{
  d.data - old(c.data)
}

method M(c: Cell) {
  var d := new Cell(10);
  label L:
  ghost var x := Diff@L(c, d);
  ghost var y := Diff(c, d); // error: d is not allocated in old state
}

A two-state function may declare that it only assumes a parameter to be allocated in the current heap. This is done by preceding the parameter with the new modifier, as illustrated in the following example, where the first call to DiffAgain is legal: 

twostate function DiffAgain(c: Cell, new d: Cell): int
  reads d
{
  d.data - old(c.data)
}

method P(c: Cell) {
  var d := new Cell(10);
  ghost var x := DiffAgain(c, d);
  ghost var y := DiffAgain(d, c); // error: d is not allocated in old state
}

A two-state lemma works in an analogous way. It is a lemma with both a current-heap parameter and an old-heap parameter, it can use old expressions in its specification (including in the precondition) and body, its parameters may use the new modifier, and the old-heap parameter is by default passed in as the caller’s old heap, which can be changed by using an @-parameter.

Here is an example of something useful that can be done with a two-state lemma: 

function SeqSum(s: seq<Cell>): int
  reads s
{
  if s == [] then 0 else s[0].data + SeqSum(s[1..])
}

twostate lemma IncSumDiff(s: seq<Cell>)
  requires forall c :: c in s ==> Increasing(c)
  ensures old(SeqSum(s)) <= SeqSum(s)
{
  if s == [] {
  } else {
    calc {
      old(SeqSum(s));
    ==  // def. SeqSum
      old(s[0].data + SeqSum(s[1..]));
    ==  // distribute old
      old(s[0].data) + old(SeqSum(s[1..]));
    <=  { assert Increasing(s[0]); }
      s[0].data + old(SeqSum(s[1..]));
    <=  { IncSumDiff(s[1..]); }
      s[0].data + SeqSum(s[1..]);
    ==  // def. SeqSum
      SeqSum(s);
    }
  }
}

A two-state function can be used as a first-class function value, where the receiver (if any), type parameters (if any), and old-heap parameter are determined at the time the first-class value is mentioned. While the receiver and type parameters can be explicitly instantiated in such a use (for example, p.F<int> for a two-state instance function F that takes one type parameter), there is currently no syntactic support for giving the old-heap parameter explicitly. A caller can work around this restriction by using (fancy-word alert!) eta-expansion, meaning wrapping a lambda expression around the call, as in x => p.F<int>@L(x). The following example illustrates using such an eta-expansion: 

class P {
  twostate function F<X>(x: X): X
}

method EtaExample(p: P) returns (ghost f: int -> int) {
  label L:
  f := x => p.F<int>@L(x);
}

6.4. Function Declarations (grammar)

6.4.1. Functions

Examples: 

function f(i: int): real { i as real }
function g(): (int, int) { (2,3) }
function h(i: int, k: int): int requires i >= 0 { if i == 0 then 0 else 1 }

Functions may be declared as ghost. If so, all the formal parameters and return values are ghost; if it is not a ghost function, then individual parameters may be declared ghost as desired.

See Section 7.3 for a description of the function specification. A Dafny function is a pure mathematical function. It is allowed to read memory that was specified in its reads expression but is not allowed to have any side effects.

Here is an example function declaration: 

function {:att1}{:att2} F<T1, T2>(a: A, b: B, c: C): T
  requires Pre
  reads Frame
  ensures Post
  decreases Rank
{
  Body
}

where :att1 and :att2 are attributes of the function, if any, T1 and T2 are type parameters of the function (if generic), a, b, c are the function’s parameters, T is the type of the function’s result, Pre is a boolean expression denoting the function’s precondition, Frame denotes a set of objects whose fields the function body may depend on, Post is a boolean expression denoting the function’s postcondition, Rank is the function’s variant function, and Body is an expression that defines the function’s return value. The precondition allows a function to be partial, that is, the precondition says when the function is defined (and Dafny will verify that every use of the function meets the precondition).

The postcondition is usually not needed, since the body of the function gives the full definition. However, the postcondition can be a convenient place to declare properties of the function that may require an inductive proof to establish, such as when the function is recursive. For example:

function Factorial(n: int): int
  requires 0 <= n
  ensures 1 <= Factorial(n)
{
  if n == 0 then 1 else Factorial(n-1) * n
}

says that the result of Factorial is always positive, which Dafny verifies inductively from the function body.

Within a postcondition, the result of the function is designated by a call of the function, such as Factorial(n) in the example above. Alternatively, a name for the function result can be given in the signature, as in the following rewrite of the example above.

function Factorial(n: int): (f: int)
  requires 0 <= n
  ensures 1 <= f
{
  if n == 0 then 1 else Factorial(n-1) * n
}

Pre v4.0, a function is ghost by default, and cannot be called from non-ghost code. To make it non-ghost, replace the keyword function with the two keywords “function method”. From v4.0 on, a function is non-ghost by default. To make it ghost, replace the keyword function with the two keywords “ghost function”. (See the –function-syntax option for a description of the migration path for this change in behavior.}

Like methods, functions can be either instance (which they are by default when declared within a type) or static (when the function declaration contains the keyword static or is declared in a module). An instance function, but not a static function, has an implicit receiver parameter, this.
A static function F in a class C can be invoked by C.F(…). This provides a convenient way to declare a number of helper functions in a separate class.

As for methods, a ... is used when declaring a function in a module refinement (cf. Section 10). For example, if module M0 declares function F, a module M1 can be declared to refine M0 and M1 can then refine F. The refinement function, M1.F can have a ... which means to copy the signature from M0.F. A refinement function can furnish a body for a function (if M0.F does not provide one). It can also add ensures clauses.

If a function definition does not have a body, the program that contains it may still be verified. The function itself has nothing to verify. However, any calls of a body-less function are treated as unverified assumptions by the caller, asserting the preconditions and assuming the postconditions. Because body-less functions are unverified assumptions, Dafny will not compile them and will complain if called by dafny translate, dafny build or even dafny run

6.4.2. Predicates

A function that returns a bool result is called a predicate. As an alternative syntax, a predicate can be declared by replacing the function keyword with the predicate keyword and possibly omitting a declaration of the return type (if it is not named).

6.4.3. Function-by-method

A function with a by method clause declares a function-by-method. A function-by-method gives a way to implement a (deterministic, side-effect free) function by a method (whose body may be nondeterministic and may allocate objects that it modifies). This can be useful if the best implementation uses nondeterminism (for example, because it uses :| in a nondeterministic way) in a way that does not affect the result, or if the implementation temporarily makes use of some mutable data structures, or if the implementation is done with a loop. For example, here is the standard definition of the Fibonacci function but with an efficient implementation that uses a loop:

function Fib(n: nat): nat {
  if n < 2 then n else Fib(n - 2) + Fib(n - 1)
} by method {
  var x, y := 0, 1;
  for i := 0 to n
    invariant x == Fib(i) && y == Fib(i + 1)
  {
    x, y := y, x + y;
  }
  return x;
}

The by method clause is allowed only for non-ghost function or predicate declarations (without twostate, least, and greatest, but possibly with static); it inherits the in-parameters, attributes, and requires and decreases clauses of the function. The method also gets one out-parameter, corresponding to the function’s result value (and the name of it, if present). Finally, the method gets an empty modifies clause and a postcondition ensures r == F(args), where r is the name of the out-parameter and F(args) is the function with its arguments. In other words, the method body must compute and return exactly what the function says, and must do so without modifying any previously existing heap state.

The function body of a function-by-method is allowed to be ghost, but the method body must be compilable. In non-ghost contexts, the compiler turns a call of the function-by-method into a call that leads to the method body.

Note, the method body of a function-by-method may contain print statements. This means that the run-time evaluation of an expression may have print effects. If --track-print-effects is enabled, this use of print in a function context will be disallowed.

6.4.4. Function Hiding

A function is said to be revealed at a location if the body of the function is visible for verification at that point, otherwise it is considered hidden.

Functions are revealed by default, but can be hidden using the hide statement, which takes either a specific function or a wildcard, to hide all functions. Hiding a function can speed up verification of a proof if the body of that function is not needed for the proof. See the hide statement for more information.

Although mostly made obsolete by the hide statement, a function can also be hidden using the opaque keyword, or using the option default-function-opacity. Here are the rules regarding those:

Inside the module where the function is declared:

Outside the module where the function is declared, the function is visible only if it was listed in the export set by which the contents of its module was imported. In that case, if the function was exported with reveals, the rules are the same within the importing module as when the function is used inside its declaring module. If the function is exported only with provides it is always hidden and is not permitted to be used in a reveal statement.

More information about the Boogie implementation of opaquenes is here.

6.4.5. Extreme (Least or Greatest) Predicates and Lemmas

See Section 12.5.3 for descriptions of extreme predicates and lemmas.

6.4.6. older parameters in predicates

A parameter of any predicate (more precisely, of any boolean-returning, non-extreme function) can be marked as older. This specifies that the truth of the predicate implies that the allocatedness of the parameter follows from the allocatedness of the non-older parameters.

To understand what this means and why this attribute is useful, consider the following example, which specifies reachability between nodes in a directed graph. A Node is declared to have any number of children:

class Node {
  var children: seq<Node>
}

There are several ways one could specify reachability between nodes. One way (which is used in Test/dafny1/SchorrWaite.dfy in the Dafny test suite) is to define a type Path, representing lists of Nodes, and to define a predicate that checks if a given list of Nodes is indeed a path between two given nodes:

datatype Path = Empty | Extend(Path, Node)

predicate ReachableVia(source: Node, p: Path, sink: Node, S: set<Node>)
  reads S
  decreases p
{
  match p
  case Empty =>
    source == sink
  case Extend(prefix, n) =>
    n in S && sink in n.children && ReachableVia(source, prefix, n, S)
}

In a nutshell, the definition of ReachableVia says

To be admissible by Dafny, the recursive predicate must be shown to terminate. Termination is assured by the specification decreases p, since every such datatype value has a finite structure and every recursive call passes in a path that is structurally included in the previous. Predicate ReachableVia must also declare (an upper bound on) which heap objects it depends on. For this purpose, the predicate takes an additional parameter S, which is used to limit the set of intermediate nodes in the path. More precisely, predicate ReachableVia(source, p, sink, S) returns true if and only if p is a list of nodes in S and source can reach sink via p.

Using predicate ReachableVia, we can now define reachability in S:

predicate Reachable(source: Node, sink: Node, S: set<Node>)
  reads S
{
  exists p :: ReachableVia(source, p, sink, S)
}

This looks like a good definition of reachability, but Dafny won’t admit it. The reason is twofold:

Often, it is easy to show that a quantifier is close-ended. In fact, if the type of a bound variable does not contain any object references, then the quantifier is trivially close-ended. For example,

forall x: int :: x <= Square(x)

is trivially close-ended.

Another innocent-looking quantifier occurs in the following example:

predicate IsCommutative<X>(r: (X, X) -> bool)
{
  forall x, y :: r(x, y) == r(y, x) // error: open-ended quantifier
}

Since nothing is known about type X, this quantifier might be open-ended. For example, if X were passed in as a class type, then the quantifier would be open-ended. One way to fix this predicate is to restrict it to non-heap based types, which is indicated with the (!new) type characteristic (see Section 5.3.1.4):

ghost predicate IsCommutative<X(!new)>(r: (X, X) -> bool) // X is restricted to non-heap types
{
  forall x, y :: r(x, y) == r(y, x) // allowed
}

Another way to make IsCommutative close-ended is to constrain the values of the bound variables x and y. This can be done by adding a parameter to the predicate and limiting the quantified values to ones in the given set:

predicate IsCommutativeInS<X>(r: (X, X) -> bool, S: set<X>)
{
  forall x, y :: x in S && y in S ==> r(x, y) == r(y, x) // close-ended
}

Through a simple syntactic analysis, Dafny detects the antecedents x in S and y in S, and since S is a parameter and thus can only be passed in as something that the caller has already allocated, the quantifier in IsCommutativeInS is determined to be close-ended.

Note, the x in S trick does not work for the motivating example, Reachable. If you try to write

predicate Reachable(source: Node, sink: Node, S: set<Node>)
  reads S
{
  exists p :: p in S && ReachableVia(source, p, sink, S) // type error: p
}

you will get a type error, because p in S does not make sense if p has type Path. We need some other way to justify that the quantification in Reachable is close-ended.

Dafny offers a way to extend the x in S trick to more situations. This is where the older modifier comes in. Before we apply older in the Reachable example, let’s first look at what older does in a less cluttered example.

Suppose we rewrite IsCommutativeInS using a programmer-defined predicate In:

predicate In<X>(x: X, S: set<X>) {
  x in S
}

predicate IsCommutativeInS<X>(r: (X, X) -> bool, S: set<X>)
{
  forall x, y :: In(x, S) && In(y, S) ==> r(x, y) == r(y, x) // error: open-ended?
}

The simple syntactic analysis that looks for x in S finds nothing here, because the in operator is relegated to the body of predicate In. To inform the analysis that In is a predicate that, in effect, is like in, you can mark parameter x with older:

predicate In<X>(older x: X, S: set<X>) {
  x in S
}

This causes the simple syntactic analysis to accept the quantifier in IsCommutativeInS. Adding older also imposes a semantic check on the body of predicate In, enforced by the verifier. The semantic check is that all the object references in the value x are older (or equally old as) the object references that are part of the other parameters, in the event that the predicate returns true. That is, older is designed to help the caller only if the predicate returns true, and the semantic check amounts to nothing if the predicate returns false.

Finally, let’s get back to the motivating example. To allow the quantifier in Reachable, mark parameter p of ReachableVia with older:

class Node {
  var children: seq<Node>
}

datatype Path = Empty | Extend(Path, Node)

ghost predicate Reachable(source: Node, sink: Node, S: set<Node>)
  reads S
{
  exists p :: ReachableVia(source, p, sink, S) // allowed because of 'older p' on ReachableVia
}

ghost predicate ReachableVia(source: Node, older p: Path, sink: Node, S: set<Node>)
  reads S
  decreases p
{
  match p
  case Empty =>
    source == sink
  case Extend(prefix, n) =>
    n in S && sink in n.children && ReachableVia(source, prefix, n, S)
}

This example is more involved than the simpler In example above. Because of the older modifier on the parameter, the quantifier in Reachable is allowed. For intuition, you can think of the effect of older p as adding an antecedent p in {source} + {sink} + S (but, as we have seen, this is not type correct). The semantic check imposed on the body of ReachableVia makes sure that, if the predicate returns true, then every object reference in p is as old as some object reference in another parameter to the predicate.

6.5. Nameonly Formal Parameters and Default-Value Expressions

A formal parameter of a method, constructor in a class, iterator, function, or datatype constructor can be declared with an expression denoting a default value. This makes the parameter optional, as opposed to required.

For example, 

function f(x: int, y: int := 10): int

may be called as either 

const i := f(1, 2)
const j := f(1)

where f(1) is equivalent to f(1, 10) in this case.

The above function may also be called as 

var k := f(y := 10, x := 2);

using names; actual arguments with names may be given in any order, though they must be after actual arguments without names.

Formal parameters may also be declared nameonly, in which case a call site must always explicitly name the formal when providing its actual argument.

For example, a function ff declared as 

function ff(x: int, nameonly y: int): int

must be called either by listing the value for x and then y with a name, as in ff(0, y := 4) or by giving both actuals by name (in any order). A nameonly formal may also have a default value and thus be optional.

Any formals after a nameonly formal must either be nameonly themselves or have default values.

The formals of datatype constructors are not required to have names. A nameless formal may not have a default value, nor may it follow a formal that has a default value.

The default-value expression for a parameter is allowed to mention the other parameters, including this (for instance methods and instance functions), but not the implicit _k parameter in least and greatest predicates and lemmas. The default value of a parameter may mention both preceding and subsequent parameters, but there may not be any dependent cycle between the parameters and their default-value expressions.

The well-formedness of default-value expressions is checked independent of the precondition of the enclosing declaration. For a function, the parameter default-value expressions may only read what the function’s reads clause allows. For a datatype constructor, parameter default-value expressions may not read anything. A default-value expression may not be involved in any recursive or mutually recursive calls with the enclosing declaration.

7. Specifications

Specifications describe logical properties of Dafny methods, functions, lambdas, iterators and loops. They specify preconditions, postconditions, invariants, what memory locations may be read or modified, and termination information by means of specification clauses. For each kind of specification, zero or more specification clauses (of the type accepted for that type of specification) may be given, in any order.

We document specifications at these levels:

This section documents the first two of these in a bottom-up manner. We first document the clauses and then the specifications that use them.

Specification clauses typically appear in a sequence. They all begin with a keyword and do not end with semicolons.

7.1. Specification Clauses

Within expressions in specification clauses, you can use specification expressions along with any other expressions you need.

7.1.1. Requires Clause (grammar)

Examples: 

method m(i: int)
  requires true
  requires i > 0
  requires L: 0 < i < 10

The requires clauses specify preconditions for methods, functions, lambda expressions and iterators. Dafny checks that the preconditions are met at all call sites. The callee may then assume the preconditions hold on entry.

If no requires clause is specified, then a default implicit clause requires true is used.

If more than one requires clause is given, then the precondition is the conjunction of all of the expressions from all of the requires clauses, with a collected list of all the given Attributes. The order of conjunctions (and hence the order of requires clauses with respect to each other) can be important: earlier conjuncts can set conditions that establish that later conjuncts are well-defined.

The attributes recognized for requires clauses are discussed in Section 11.4.

A requires clause can have custom error and success messages.

7.1.2. Ensures Clause (grammar)

Examples: 

method {:axiom} m(i: int) returns (r: int)
  ensures r > 0

An ensures clause specifies the post condition for a method, function or iterator.

If no ensures clause is specified, then a default implicit clause ensures true is used.

If more than one ensures clause is given, then the postcondition is the conjunction of all of the expressions from all of the ensures clauses, with a collected list of all the given Attributes. The order of conjunctions (and hence the order of ensures clauses with respect to each other) can be important: earlier conjuncts can set conditions that establish that later conjuncts are well-defined.

The attributes recognized for ensures clauses are discussed in Section 11.4.

An ensures clause can have custom error and success messages.

7.1.3. Decreases Clause (grammar)

Examples: 

method m(i: int, j: int) returns (r: int)
  decreases i, j
method n(i: int) returns (r: int)
  decreases *

Decreases clauses are used to prove termination in the presence of recursion. If more than one decreases clause is given it is as if a single decreases clause had been given with the collected list of arguments and a collected list of Attributes. That is,

decreases A, B
decreases C, D

is equivalent to

decreases A, B, C, D

Note that changing the order of multiple decreases clauses will change the order of the expressions within the equivalent single decreases clause, and will therefore have different semantics.

Loops and compiled methods (but not functions and not ghost methods, including lemmas) can be specified to be possibly non-terminating. This is done by declaring the method or loop with decreases *, which causes the proof of termination to be skipped. If a * is present in a decreases clause, no other expressions are allowed in the decreases clause. A method that contains a possibly non-terminating loop or a call to a possibly non-terminating method must itself be declared as possibly non-terminating.

Termination metrics in Dafny, which are declared by decreases clauses, are lexicographic tuples of expressions. At each recursive (or mutually recursive) call to a function or method, Dafny checks that the effective decreases clause of the callee is strictly smaller than the effective decreases clause of the caller.

What does “strictly smaller” mean? Dafny provides a built-in well-founded order for every type and, in some cases, between types. For example, the Boolean false is strictly smaller than true, the integer 78 is strictly smaller than 102, the set {2,5} is strictly smaller than (because it is a proper subset of) the set {2,3,5}, and for s of type seq<Color> where Color is some inductive datatype, the color s[0] is strictly less than s (provided s is nonempty).

What does “effective decreases clause” mean? Dafny always appends a “top” element to the lexicographic tuple given by the user. This top element cannot be syntactically denoted in a Dafny program and it never occurs as a run-time value either. Rather, it is a fictitious value, which here we will denote $\top$, such that each value that can ever occur in a Dafny program is strictly less than $\top$. Dafny sometimes also prepends expressions to the lexicographic tuple given by the user. The effective decreases clause is any such prefix, followed by the user-provided decreases clause, followed by $\top$. We said “user-provided decreases clause”, but if the user completely omits a decreases clause, then Dafny will usually make a guess at one, in which case the effective decreases clause is any prefix followed by the guess followed by $\top$.

Here is a simple but interesting example: the Fibonacci function.

function Fib(n: nat) : nat
{
  if n < 2 then n else Fib(n-2) + Fib(n-1)
}

In this example, Dafny supplies a decreases n clause.

Let’s take a look at the kind of example where a mysterious-looking decreases clause like “Rank, 0” is useful.

Consider two mutually recursive methods, A and B: 

method A(x: nat)
{
  B(x);
}

method B(x: nat)
{
  if x != 0 { A(x-1); }
}

To prove termination of A and B, Dafny needs to have effective decreases clauses for A and B such that:

Satisfying the second of these conditions is easy, but what about the first? Note, for example, that declaring both A and B with “decreases x” does not work, because that won’t prove a strict decrease for the call from A(x) to B(x).

Here’s one possibility: 

method A(x: nat)
  decreases x, 1
{
  B(x);
}

method B(x: nat)
  decreases x, 0
{
  if x != 0 { A(x-1); }
}

For the call from A(x) to B(x), the lexicographic tuple "x, 0" is strictly smaller than "x, 1", and for the call from B(x) to A(x-1), the lexicographic tuple "x-1, 1" is strictly smaller than "x, 0".

Two things to note: First, the choice of “0” and “1” as the second components of these lexicographic tuples is rather arbitrary. It could just as well have been “false” and “true”, respectively, or the sets {2,5} and {2,3,5}. Second, the keyword decreases often gives rise to an intuitive English reading of the declaration. For example, you might say that the recursive calls in the definition of the familiar Fibonacci function Fib(n) “decreases n”. But when the lexicographic tuple contains constants, the English reading of the declaration becomes mysterious and may give rise to questions like “how can you decrease the constant 0?”. The keyword is just that—a keyword. It says “here comes a list of expressions that make up the lexicographic tuple we want to use for the termination measure”. What is important is that one effective decreases clause is compared against another one, and it certainly makes sense to compare something to a constant (and to compare one constant to another).

We can simplify things a little bit by remembering that Dafny appends $\top$ to the user-supplied decreases clause. For the A-and-B example, this lets us drop the constant from the decreases clause of A:

method A(x: nat)
   decreases x
{
  B(x);
}

method B(x: nat)
  decreases x, 0
{
  if x != 0 { A(x-1); }
}

The effective decreases clause of A is $(x, \top)$ and the effective decreases clause of B is $(x, 0, \top)$. These tuples still satisfy the two conditions $(x, 0, \top) < (x, \top)$ and $(x-1, \top) < (x, 0, \top)$. And as before, the constant “0” is arbitrary; anything less than $\top$ (which is any Dafny expression) would work.

Let’s take a look at one more example that better illustrates the utility of $\top$. Consider again two mutually recursive methods, call them Outer and Inner, representing the recursive counterparts of what iteratively might be two nested loops: 

method Outer(x: nat)
{
  // set y to an arbitrary non-negative integer
  var y :| 0 <= y;
  Inner(x, y);
}

method Inner(x: nat, y: nat)
{
  if y != 0 {
    Inner(x, y-1);
  } else if x != 0 {
    Outer(x-1);
  }
}

The body of Outer uses an assign-such-that statement to represent some computation that takes place before Inner is called. It sets “y” to some arbitrary non-negative value. In a more concrete example, Inner would do some work for each “y” and then continue as Outer on the next smaller “x”.

Using a decreases clause $(x, y)$ for Inner seems natural, but if we don’t have any bound on the size of the $y$ computed by Outer, there is no expression we can write in the decreases clause of Outer that is sure to lead to a strictly smaller value for $y$ when Inner is called. $\top$ to the rescue. If we arrange for the effective decreases clause of Outer to be $(x, \top)$ and the effective decreases clause for Inner to be $(x, y, \top)$, then we can show the strict decreases as required. Since $\top$ is implicitly appended, the two decreases clauses declared in the program text can be: 

method Outer(x: nat)
  decreases x
{
  // set y to an arbitrary non-negative integer
  var y :| 0 <= y;
  Inner(x, y);
}

method Inner(x: nat, y: nat)
  decreases x,y
{
  if y != 0 {
    Inner(x, y-1);
  } else if x != 0 {
    Outer(x-1);
  }
}

Moreover, remember that if a function or method has no user-declared decreases clause, Dafny will make a guess. The guess is (usually) the list of arguments of the function/method, in the order given. This is exactly the decreases clauses needed here. Thus, Dafny successfully verifies the program without any explicit decreases clauses: 

method Outer(x: nat)
{
  var y :| 0 <= y;
  Inner(x, y);
}

method Inner(x: nat, y: nat)
{
  if y != 0 {
    Inner(x, y-1);
  } else if x != 0 {
    Outer(x-1);
  }
}

The ingredients are simple, but the end result may seem like magic. For many users, however, there may be no magic at all – the end result may be so natural that the user never even has to be bothered to think about that there was a need to prove termination in the first place.

Dafny also prepends two expressions to the user-specified (or guessed) tuple of expressions in the decreases clause. The first expression is the ordering of the module containing the decreases clause in the dependence-ordering of modules. That is, a module that neither imports or defines (as submodules) any other modules has the lowest value in the order and every other module has a value that is higher than that of any module it defines or imports. As a module cannot call a method in a module that it does not depend on, this is an effective first component to the overall decreases tuple.

The second prepended expression represents the position of the method in the call graph within a module. Dafny analyzes the call-graph of the module, grouping all methods into mutually-recursive groups. Any method that calls nothing else is at the lowest level (say level 0). Absent recursion, every method has a level value strictly greater than any method it calls. Methods that are mutually recursive are at the same level and they are above the level of anything else they call. With this level value prepended to the decreases clause, the decreases tuple automatically decreases on any calls in a non-recursive context.

Though Dafny fixes a well-founded order that it uses when checking termination, Dafny does not normally surface this ordering directly in expressions. However, it is possible to write such ordering constraints using decreases to expressions.

7.1.4. Framing (grammar)

Examples: 

*
o
o`a
`a
{ o, p, q }
{}

Frame expressions are used to denote the set of memory locations that a Dafny program element may read or write. They are used in reads and modifies clauses. A frame expression is a set expression. The form {} is the empty set. The type of the frame expression is set<object>.

Note that framing only applies to the heap, or memory accessed through references. Local variables are not stored on the heap, so they cannot be mentioned (well, they are not in scope in the declaration) in frame annotations. Note also that types like sets, sequences, and multisets are value types, and are treated like integers or local variables. Arrays and objects are reference types, and they are stored on the heap (though as always there is a subtle distinction between the reference itself and the value it points to.)

The FrameField construct is used to specify a field of a class object. The identifier following the back-quote is the name of the field being referenced. If the FrameField is preceded by an expression the expression must be a reference to an object having that field. If the FrameField is not preceded by an expression then the frame expression is referring to that field of the current object (this). This form is only used within a method of a class or trait.

A FrameField can be useful in the following case: When a method modifies only one field, rather than writing

class A {
  var i: int
  var x0: int
  var x1: int
  var x2: int
  var x3: int
  var x4: int
  method M()
    modifies this
    ensures unchanged(`x0) && unchanged(`x1) && unchanged(`x2) && unchanged(`x3) && unchanged(`x4)
  { i := i + 1; }
}

one can write the more concise:

class A {
  var i: int
  var x0: int
  var x1: int
  var x2: int
  var x3: int
  var x4: int
  method M()
    modifies `i
  { i := i + 1; }
}

There’s (unfortunately) no form of it for array elements – but to account for unchanged elements, you can always write forall i | 0 <= i < |a| :: unchanged(a[i]).

A FrameField is not taken into consideration for lambda expressions.

7.1.5. Reads Clause (grammar)

Examples: 

const o: object
const o, oo: object
function f()
  reads *
function g()
  reads o, oo
function h()
  reads { o }
method f()
  reads *
method g()
  reads o, oo
method h()
  reads { o }

Functions are not allowed to have side effects; they may also be restricted in what they can read. The reading frame of a function (or predicate) consists of all the heap memory locations that the function is allowed to read. The reason we might limit what a function can read is so that when we write to memory, we can be sure that functions that did not read that part of memory have the same value they did before. For example, we might have two arrays, one of which we know is sorted. If we did not put a reads annotation on the sorted predicate, then when we modify the unsorted array, we cannot determine whether the other array stopped being sorted. While we might be able to give invariants to preserve it in this case, it gets even more complex when manipulating data structures. In this case, framing is essential to making the verification process feasible.

By default, methods are not required to list the memory location they read. However, there are use cases for restricting what methods can read as well. In particular, if you want to verify that imperative code is safe to execute concurrently when compiled, you can specify that a method does not read or write any shared state, and therefore cannot encounter race conditions or runtime crashes related to unsafe communication between concurrent executions. See the {:concurrent} attribute for more details.

It is not just the body of a function or method that is subject to reads checks, but also its precondition and the reads clause itself.

A reads clause can list a wildcard *, which allows the enclosing function or method to read anything. This is the implicit default for methods with no reads clauses, allowing methods to read whatever they like. The default for functions, however, is to not allow reading any memory. Allowing functions to read arbitrary memory is more problematic: in many cases, and in particular in all cases where the function is defined recursively, this makes it next to impossible to make any use of the function. Nevertheless, as an experimental feature, the language allows it (and it is sound). If a reads clause uses *, then the reads clause is not allowed to mention anything else (since anything else would be irrelevant, anyhow).

A reads clause specifies the set of memory locations that a function, lambda, or method may read. The readable memory locations are all the fields of all of the references given in the set specified in the frame expression and the single fields given in FrameField elements of the frame expression. For example, in 

class C {
  var x: int
  var y: int

  predicate f(c: C) 
    reads this, c`x
  {
    this.x == c.x
  }
}

the reads clause allows reading this.x, this,y, and c.x (which may be the same memory location as this.x). }

If more than one reads clause is given in a specification the effective read set is the union of the sets specified. If there are no reads clauses the effective read set is empty. If * is given in a reads clause it means any memory may be read.

If a reads clause refers to a sequence or multiset, that collection (call it c) is converted to a set by adding an implicit set comprehension of the form set o: object | o in c before computing the union of object sets from other reads clauses.

An expression in a reads clause is also allowed to be a function call whose value is a collection of references. Such an expression is converted to a set by taking the union of the function’s image over all inputs. For example, if F is a function from int to set<object>, then reads F has the meaning

set x: int, o: object | o in F(x) :: o

For each function value f, Dafny defines the function f.reads, which takes the same arguments as f and returns that set of objects that f reads (according to its reads clause) with those arguments. f.reads has type T ~> set<object>, where T is the input type(s) of f.

This is particularly useful when wanting to specify the reads set of another function. For example, function Sum adds up the values of f(i) where i ranges from lo to hi:

function Sum(f: int ~> real, lo: int, hi: int): real
  requires lo <= hi
  requires forall i :: f.requires(i)
  reads f.reads
  decreases hi - lo
{
  if lo == hi then 0.0 else
    f(lo) + Sum(f, lo + 1, hi)
}

Its reads specification says that Sum(f, lo, hi) may read anything that f may read on any input. (The specification reads f.reads gives an overapproximation of what Sum will actually read. More precise would be to specify that Sum reads only what f reads on the values from lo to hi, but the larger set denoted by reads f.reads is easier to write down and is often good enough.)

Without such reads function, one could also write the more precise and more verbose: 

function Sum(f: int ~> real, lo: int, hi: int): real
  requires lo <= hi
  requires forall i :: lo <= i < hi ==> f.requires(i)
  reads set i, o | lo <= i < hi && o in f.reads(i) :: o
  decreases hi - lo
{
  if lo == hi then 0.0 else
    f(lo) + Sum(f, lo + 1, hi)
}

Note, only reads clauses, not modifies clauses, are allowed to include functions as just described.

Iterator specifications also allow reads clauses, with the same syntax and interpretation of arguments as above, but the meaning is quite different! See Section 5.11 for more details.

7.1.6. Modifies Clause (grammar)

Examples: 

class A { var f: int }
const o: object?
const p: A?
method M()
  modifies { o, p }
method N()
  modifies { }
method Q()
  modifies o, p`f

By default, methods are allowed to read whatever memory they like, but they are required to list which parts of memory they modify, with a modifies annotation. These are almost identical to their reads cousins, except they say what can be changed, rather than what the definition depends on. In combination with reads, modification restrictions allow Dafny to prove properties of code that would otherwise be very difficult or impossible. Reads and modifies are one of the tools that allow Dafny to work on one method at a time, because they restrict what would otherwise be arbitrary modifications of memory to something that Dafny can reason about.

Just as for a reads clause, the memory locations allowed to be modified in a method are all the fields of any object reference in the frame expression set and any specific field denoted by a FrameField in the modifies clause. For example, in 

class C {
  var next: C?
  var value: int

  method M() 
    modifies next
  { 
    ... 
  }
}

method M is permitted to modify this.next.next and this.next.value but not this.next. To be allowed to modify this.next, the modifies clause must include this, or some expression that evaluates to this, or this`next.

If an object is newly allocated within the body of a method or within the scope of a modifies statement or a loop’s modifies clause, then the fields of that object may always be modified.

A modifies clause specifies the set of memory locations that a method, iterator or loop body may modify. If more than one modifies clause is given in a specification, the effective modifies set is the union of the sets specified. If no modifies clause is given the effective modifies set is empty. There is no wildcard (*) allowed in a modifies clause. A loop can also have a modifies clause. If none is given, the loop may modify anything the enclosing context is allowed to modify.

Note that modifies here is used in the sense of writes. That is, a field that may not be modified may not be written to, even with the same value it already has or even if the value is restored later. The terminology and semantics varies among specification languages. Some define frame conditions in this sense (a) of writes and others in the sense (b) that allows writing a field with the same value or changing the value so long as the original value is restored by the end of the scope. For example, JML defines assignable and modifies as synonyms in the sense (a), though KeY interprets JML’s assigns/modifies in sense (b). ACSL and ACSL++ use the assigns keyword, but with modify (b) semantics. Ada/SPARK’s dataflow contracts encode write (a) semantics.

7.1.7. Invariant Clause (grammar)

Examples: 

method m()
{
  var i := 10;
  while 0 < i
    invariant 0 <= i < 10
}

An invariant clause is used to specify an invariant for a loop. If more than one invariant clause is given for a loop, the effective invariant is the conjunction of the conditions specified, in the order given in the source text.

The invariant must hold on entry to the loop. And assuming it is valid on entry to a particular iteration of the loop, Dafny must be able to prove that it then holds at the end of that iteration of the loop.

An invariant can have custom error and success messages.

7.2. Method Specification (grammar)

Examples: 

class C {
  var next: C?
  var value: int

  method M(i: int) returns (r: int)
    requires i >= 0
    modifies next
    decreases i
    ensures r >= 0
  { 
    ... 
  }
}

A method specification consists of zero or more reads, modifies, requires, ensures or decreases clauses, in any order. A method does not need reads clauses in most cases, because methods are allowed to read any memory by default, but reads clauses are supported for use cases such as verifying safe concurrent execution. See the {:concurrent} attribute for more details.

7.3. Function Specification (grammar)

Examples: 

class C {
  var next: C?
  var value: int

  function M(i: int): (r: int)
    requires i >= 0
    reads this
    decreases i
    ensures r >= 0
  { 
    0 
  }
}

A function specification is zero or more reads, requires, ensures or decreases clauses, in any order. A function specification does not have modifies clauses because functions are not allowed to modify any memory.

7.4. Lambda Specification (grammar)

A lambda specification provides a specification for a lambda function expression; it consists of zero or more reads or requires clauses. Any requires clauses may not have labels or attributes. Lambda specifications do not have ensures clauses because the body is never opaque. Lambda specifications do not have decreases clauses because lambda expressions do not have names and thus cannot be recursive. A lambda specification does not have modifies clauses because lambdas are not allowed to modify any memory.

7.5. Iterator Specification (grammar)

An iterator specification may contains reads, modifies, decreases, requires, yield requires, ensures and yield ensures` clauses.

An iterator specification applies both to the iterator’s constructor method and to its MoveNext method.

Examples of iterators, including iterator specifications, are given in Section 5.11. Briefly

7.6. Loop Specification (grammar)

A loop specification provides the information Dafny needs to prove properties of a loop. It contains invariant, decreases, and modifies clauses.

The invariant clause is effectively a precondition and it along with the negation of the loop test condition provides the postcondition. The decreases clause is used to prove termination.

7.7. Auto-generated boilerplate specifications

AutoContracts is an experimental feature that inserts much of the dynamic-frames boilerplate into a class. The user simply

AutoContracts then

In all the following cases, no modifies clause or reads clause is added if the user has given one.

7.8. Well-formedness of specifications

Dafny ensures that the requires clauses and ensures clauses, which are expressions, are well-formed independent of the body they belong to. Examples of conditions this rules out are null pointer dereferencing, out-of-bounds array access, and division by zero. Hence, when declaring the following method:

method Test(a: array<int>) returns (j: int)
  requires a.Length >= 1
  ensures a.Length % 2 == 0 ==> j >= 10 / a.Length
{
  j := 20;
  var divisor := a.Length;
  if divisor % 2 == 0 {
    j := j / divisor;
  }
}

Dafny will split the verification in two assertion batches that will roughly look like the following lemmas:

lemma Test_WellFormed(a: array?<int>)
{
  assume a != null;       // From the definition of a
  assert a != null;       // for the `requires a.Length >= 1`
  assume a.Length >= 1;   // After well-formedness, we assume the requires
  assert a != null;       // Again for the `a.Length % 2`
  if a.Length % 2 == 0 {
    assert a != null;     // Again for the final `a.Length`
    assert a.Length != 0; // Because of the 10 / a.Length
  }
}

method Test_Correctness(a: array?<int>)
{ // Here we assume the well-formedness of the condition
  assume a != null;       // for the `requires a.Length >= 1`
  assume a != null;       // Again for the `a.Length % 2`
  if a.Length % 2 == 0 {
    assume a != null;     // Again for the final `a.Length`
    assume a.Length != 0; // Because of the 10 / a.Length
  }

  // Now the body is translated
  var j := 20;
  assert a != null;          // For `var divisor := a.Length;`
  var divisor := a.Length;
  if * {
    assume divisor % 2 == 0;
    assert divisor != 0;
    j := j / divisor;
  }
  assume divisor % 2 == 0 ==> divisor != 0;
  assert a.Length % 2 == 0 ==> j >= 10 / a.Length;
}

For this reason the IDE typically reports at least two assertion batches when hovering a method.

8. Statements (grammar)

Many of Dafny’s statements are similar to those in traditional programming languages, but a number of them are significantly different. Dafny’s various kinds of statements are described in subsequent sections.

Statements have zero or more labels and end with either a semicolon (;) or a closing curly brace (‘}’).

8.1. Labeled Statement (grammar)

Examples: 

class A { var f: int }
method m(a: A) {
  label x:
  while true {
     if (*) { break x; }
  }
  a.f := 0;
  label y:
  a.f := 1;
  assert old@y(a.f) == 1;
}

A labeled statement is just

The label may be referenced in a break or continue statement within the labeled statement (see Section 8.14). That is, the break or continue that mentions the label must be enclosed in the labeled statement.

The label may also be used in an old expression (Section 9.22). In this case, the label must have been encountered during the control flow en route to the old expression. We say in this case that the (program point of the) label dominates the (program point of the) use of the label. Similarly, labels are used to indicate previous states in calls of two-state predicates, fresh expressions, unchanged expressions, and allocated expressions.

A statement can be given several labels. It makes no difference which of these labels is used to reference the statement—they are synonyms of each other. The labels must be distinct from each other, and are not allowed to be the same as any previous enclosing or dominating label.

8.2. Block Statement (grammar)

Examples: 

{
  print 0;
  var x := 0;
}

A block statement is a sequence of zero or more statements enclosed by curly braces. Local variables declared in the block end their scope at the end of the block.

8.3. Return Statement (grammar)

Examples: 

method m(i: int) returns (r: int) {
  return i+1;
}
method n(i: int) returns (r: int, q: int) {
  return i+1, i + 2;
}
method p() returns (i: int) {
  i := 1;
  return;
}
method q() {
  return;
}

A return statement can only be used in a method. It is used to terminate the execution of the method.

To return a value from a method, the value is assigned to one of the named out-parameters sometime before a return statement. In fact, the out-parameters act very much like local variables, and can be assigned to more than once. Return statements are used when one wants to return before reaching the end of the body block of the method.

Return statements can be just the return keyword (where the current values of the out-parameters are used), or they can take a list of expressions to return. If a list is given, the number of expressions given must be the same as the number of named out-parameters. These expressions are evaluated, then they are assigned to the out-parameters, and then the method terminates.

8.4. Yield Statement (grammar)

A yield statement may only be used in an iterator. See iterator types for more details about iterators.

The body of an iterator is a co-routine. It is used to yield control to its caller, signaling that a new set of values for the iterator’s yield (out-)parameters (if any) are available. Values are assigned to the yield parameters at or before a yield statement. In fact, the yield parameters act very much like local variables, and can be assigned to more than once. Yield statements are used when one wants to return new yield parameter values to the caller. Yield statements can be just the yield keyword (where the current values of the yield parameters are used), or they can take a list of expressions to yield. If a list is given, the number of expressions given must be the same as the number of named iterator out-parameters. These expressions are then evaluated, then they are assigned to the yield parameters, and then the iterator yields.

8.5. Update and Call Statements (grammar)

Examples: 

class C { var f: int }
class D {
  var i: int
  constructor(i: int) {
    this.i := i;
  }
}
method q(i: int, j: int) {}
method r() returns (s: int, t: int) { return 2,3; }
method m() {
  var ss: int, tt: int, c: C?, a: array<int>, d: D?;
  q(0,1);
  ss, c.f := r();
  c := new C;
  d := new D(2);
  a := new int[10];
  ss, tt := 212, 33;
  ss :| ss > 7;
  ss := *;
}

This statement corresponds to familiar assignment or method call statements, with variations. If more than one left-hand side is used, these must denote different l-values, unless the corresponding right-hand sides also denote the same value.

The update statement serves several logical purposes.

8.5.1. Method call with no out-parameters

1) Examples of method calls take this form 

m();
m(1,2,3) {:attr} ;
e.f().g.m(45);

As there are no left-hand-side locations to receive values, this form is allowed only for methods that have no out-parameters.

8.5.2. Method call with out-parameters

This form uses := to denote the assignment of the out-parameters of the method to the corresponding number of LHS values. 

a, b.e().f := m() {:attr};

In this case, the right-hand-side must be a method call and the number of left-hand sides must match the number of out-parameters of the method that is called. Note that the result of a method call is not allowed to be used as an argument of another method call, as if it were an expression.

8.5.3. Parallel assignment

A parallel-assignment has one-or-more right-hand-side expressions, which may be function calls but may not be method calls. 

    x, y := y, x;

The above example swaps the values of x and y. If more than one left-hand side is used, these must denote different l-values, unless the corresponding right-hand sides also denote the same value. There must be an equal number of left-hand sides and right-hand sides. The most common case has only one RHS and one LHS.

8.5.4. Havoc assignment

The form with a right-hand-side that is * is a havoc assignment. It assigns an arbitrary but type-correct value to the corresponding left-hand-side. It can be mixed with other assignments of computed values. 

a := *;
a, b, c := 4, *, 5;

8.5.5. Such-that assignment

This form has one or more left-hand-sides, a :| symbol and then a boolean expression on the right. The effect is to assign values to the left-hand-sides that satisfy the RHS condition.

x, y :| 0 < x+y < 10;

This is read as assign values to x and y such that 0 < x+y < 10 is true. The given boolean expression need not constrain the LHS values uniquely: the choice of satisfying values is non-deterministic. This can be used to make a choice as in the following example where we choose an element in a set.

method Sum(X: set<int>) returns (s: int)
{
  s := 0; var Y := X;
  while Y != {}
    decreases Y
  {
    var y: int;
    y :| y in Y;
    s, Y := s + y, Y - {y};
  }
}

Dafny will report an error if it cannot prove that values exist that satisfy the condition.

In this variation, with an assume keyword 

    y :| assume y in Y;

Dafny assumes without proof that an appropriate value exists.

Note that the syntax

    Lhs ":"

is interpreted as a label in which the user forgot the label keyword.

8.5.6. Method call with a by proof

The purpose of this form of a method call is to seperate the called method’s precondition and its proof from the rest of the correctness proof of the calling method.

opaque predicate P() { true }

lemma ProveP() ensures P() {
  reveal P();
}

method M(i: int) returns (r: int)
  requires P()
  ensures r == i
{ r := i; }

method C() {
  var v := M(1/3) by { // We prove 3 != 0 outside of the by proof
    ProveP();          // Prove precondtion  
  }
  assert v == 0;       // Use postcondition
  assert P();          // Fails
}

By placing the call to lemma ProveP inside of the by block, we can not use P after the method call. The well-formedness checks of the arguments to the method call are not subject to the separation.

8.6. Update with Failure Statement (:-) (grammar)

See the subsections below for examples.

A :-9 statement is an alternate form of the := statement that allows for abrupt return if a failure is detected. This is a language feature somewhat analogous to exceptions in other languages.

An update-with-failure statement uses failure-compatible types. A failure-compatible type is a type that has the following (non-static) members (each with no in-parameters and one out-parameter):

A failure-compatible type with an Extract member is called value-carrying.

To use this form of update,

The following subsections show various uses and alternatives.

8.6.1. Failure compatible types

A simple failure-compatible type is the following: 

datatype Status =
| Success
| Failure(error: string)
{
  predicate IsFailure() { this.Failure?  }
  function PropagateFailure(): Status
    requires IsFailure()
  {
    Failure(this.error)
  }
}

A commonly used alternative that carries some value information is something like this generic type: 

datatype Outcome<T> =
| Success(value: T)
| Failure(error: string)
{
  predicate IsFailure() {
    this.Failure?
  }
  function PropagateFailure<U>(): Outcome<U>
    requires IsFailure()
  {
    Failure(this.error) // this is Outcome<U>.Failure(...)
  }
  function Extract(): T
    requires !IsFailure()
  {
    this.value
  }
}

8.6.2. Simple status return with no other outputs

The simplest use of this failure-return style of programming is to have a method call that just returns a non-value-carrying Status value: 

method Callee(i: int) returns (r: Status)
{
  if i < 0 { return Failure("negative"); }
  return Success;
}

method Caller(i: int) returns (rr: Status)
{
  :- Callee(i);
  ...
}

Note that there is no LHS to the :- statement. If Callee returns Failure, then the caller immediately returns, not executing any statements following the call of Callee. The value returned by Caller (the value of rr in the code above) is the result of PropagateFailure applied to the value returned by Callee, which is often just the same value. If Callee does not return Failure (that is, returns a value for which IsFailure() is false) then that return value is forgotten and execution proceeds normally with the statements following the call of Callee in the body of Caller.

The desugaring of the :- Callee(i); statement is 

var tmp;
tmp := Callee(i);
if tmp.IsFailure() {
  rr := tmp.PropagateFailure();
  return;
}

In this and subsequent examples of desugaring, the tmp variable is a new, unique variable, unused elsewhere in the calling member.

8.6.3. Status return with additional outputs

The example in the previous subsection affects the program only through side effects or the status return itself. It may well be convenient to have additional out-parameters, as is allowed for := updates; these out-parameters behave just as for :=. Here is an example:

method Callee(i: int) returns (r: Status, v: int, w: int)
{
  if i < 0 { return Failure("negative"), 0, 0; }
  return Success, i+i, i*i;
}

method Caller(i: int) returns (rr: Status, k: int)
{
  var j: int;
  j, k :- Callee(i);
  k := k + k;
  ...
}

Here Callee has two outputs in addition to the Status output. The LHS of the :- statement accordingly has two l-values to receive those outputs. The recipients of those outputs may be any sort of l-values; here they are a local variable and an out-parameter of the caller. Those outputs are assigned in the :- call regardless of the Status value:

The desugaring of the j, k :- Callee(i); statement is 

var tmp;
tmp, j, k := Callee(i);
if tmp.IsFailure() {
  rr := tmp.PropagateFailure();
  return;
}

8.6.4. Failure-returns with additional data

The failure-compatible return value can carry additional data as shown in the Outcome<T> example above. In this case there is a (first) LHS l-value to receive this additional data. The type of that first LHS value is one that is assignable from the result of the Extract function, not the actual first out-parameter.

method Callee(i: int) returns (r: Outcome<nat>, v: int)
{
  if i < 0 { return Failure("negative"), i+i; }
  return Success(i), i+i;
}

method Caller(i: int) returns (rr: Outcome<int>, k: int)
{
  var j: int;
  j, k :- Callee(i);
  k := k + k;
  ...
}

Suppose Caller is called with an argument of 10. Then Callee is called with argument 10 and returns r and v of Outcome<nat>.Success(10) and 20. Here r.IsFailure() is false, so control proceeds normally. The j is assigned the result of r.Extract(), which will be 10, and k is assigned 20. Control flow proceeds to the next line, where k now gets the value 40.

Suppose instead that Caller is called with an argument of -1. Then Callee is called with the value -1 and returns r and v with values Outcome<nat>.Failure("negative") and -2. k is assigned the value of v (-2). But r.IsFailure() is true, so control proceeds directly to return from Caller. The first out-parameter of Caller (rr) gets the value of r.PropagateFailure(), which is Outcome<int>.Failure("negative"); k already has the value -2. The rest of the body of Caller is skipped. In this example, the first out-parameter of Caller has a failure-compatible type so the exceptional return will propagate up the call stack. It will keep propagating up the call stack as long as there are callers with this first special output type and calls that use :- and the return value keeps having IsFailure() true.

The desugaring of the j, k :- Callee(i); statement in this example is 

var tmp;
tmp, k := Callee(i);
if tmp.IsFailure() {
  rr := tmp.PropagateFailure();
  return;
}
j := tmp.Extract();

8.6.5. RHS with expression list

Instead of a failure-returning method call on the RHS of the statement, the RHS can instead be a list of expressions. As for a := statement, in this form, the expressions on the left and right sides of :- must correspond, just omitting a LHS l-value for the first RHS expression if its type is not value-carrying. The semantics is very similar to that in the previous subsection.

A RHS with a method call cannot be mixed with a RHS containing multiple expressions.

For example, the desugaring of 

method m(r: Status) returns (rr: Status) {
  var k;
  k :- r, 7;
  ...
}

is 

var k;
var tmp;
tmp, k := r, 7;
if tmp.IsFailure() {
  rr := tmp.PropagateFailure();
  return;
}

8.6.6. Failure with initialized declaration.

The :- syntax can also be used in initialization, as in 

var s, t :- M();

This is equivalent to 

var s, t;
s, t :- M();

with the semantics as described above.

8.6.7. Keyword alternative

In any of the above described uses of :-, the :- token may be followed immediately by the keyword expect, assert or assume.

In each of these cases, there is no abrupt return from the caller. Thus there is no evaluation of PropagateFailure. Consequently the first out-parameter of the caller need not match the return type of PropagateFailure; indeed, the failure-compatible type returned by the callee need not have a PropagateFailure member.

The equivalent desugaring replaces 

if tmp.IsFailure() {
  rr := tmp.PropagateFailure();
  return;
}

with 

expect !tmp.IsFailure(), tmp;

or 

assert !tmp.IsFailure();

or 

assume !tmp.IsFailure();

There is a grammatical nuance that the user should be aware of. The keywords assert, assume, and expect can start an expression. For example, assert P; E can be an expression. However, in e :- assert P; E; the assert is parsed as the keyword associated with :-. To have the assert considered part of the expression use parentheses: e :- (assert P; E);.

8.6.8. Key points

There are several points to note.

It is important to note the connection between the failure-compatible types used in the caller and callee, if they both use them. They do not have to be the same type, but they must be closely related, as it must be possible for the callee’s PropagateFailure to return a value of the caller’s failure-compatible type. In practice this means that one such failure-compatible type should be used for an entire program. If a Dafny program uses a library shared by multiple programs, the library should supply such a type and it should be used by all the client programs (and, effectively, all Dafny libraries). It is also the case that it is inconvenient to mix types such as Outcome and Status above within the same program. If there is a mix of failure-compatible types, then the program will need to use := statements and code for explicit handling of failure values.

8.6.9. Failure returns and exceptions

The :- mechanism is like the exceptions used in other programming languages, with some similarities and differences.

8.7. Variable Declaration Statement (grammar)

Examples: 

method m() {
  var x, y: int; // x's type is inferred, not necessarily 'int'
  var b: bool, k: int;
  x := 1; // settles x's type
}

A variable declaration statement is used to declare one or more local variables in a method or function. The type of each local variable must be given unless its type can be inferred, either from a given initial value, or from other uses of the variable. If initial values are given, the number of values must match the number of variables declared.

The scope of the declared variable extends to the end of the block in which it is declared. However, be aware that if a simple variable declaration is followed by an expression (rather than a subsequent statement) then the var begins a Let Expression and the scope of the introduced variables is only to the end of the expression. In this case, though, the var is in an expression context, not a statement context.

Note that the type of each variable must be given individually. The following code

var x, y : int;
var x, y := 5, 6;
var x, y :- m();
var x, y :| 0 < x + y < 10;
var (x, y) := makePair();
var Cons(x, y) = ConsMaker();

does not declare both x and y to be of type int. Rather it will give an error explaining that the type of x is underspecified if it cannot be inferred from uses of x.

The variables can be initialized with syntax similar to update statements (cf. Section 8.5).

If the RHS is a call, then any variable receiving the value of a formal ghost out-parameter will automatically be declared as ghost, even if the ghost keyword is not part of the variable declaration statement.

The left-hand side can also contain a tuple of patterns that will be matched against the right-hand-side. For example:

function returnsTuple() : (int, int)
{
    (5, 10)
}

function usesTuple() : int
{
    var (x, y) := returnsTuple();
    x + y
}

The initialization with failure operator :- returns from the enclosing method if the initializer evaluates to a failure value of a failure-compatible type (see Section 8.6).

8.8. Guards (grammar)

Examples (in if statements): 

method m(i: int) {
  if (*) { print i; }
  if i > 0 { print i; }
}

Guards are used in if and while statements as boolean expressions. Guards take two forms.

The first and most common form is just a boolean expression.

The second form is either * or (*). These have the same meaning. An unspecified boolean value is returned. The value returned may be different each time it is executed.

8.9. Binding Guards (grammar)

Examples (in if statements): 

method m(i: int) {
  ghost var k: int;
  if i, j :| 0 < i+j < 10 {
    k := 0;
  } else {
    k := 1;
  }
}

An if statement can also take a binding guard. Such a guard checks if there exist values for the given variables that satisfy the given expression. If so, it binds some satisfying values to the variables and proceeds into the “then” branch; otherwise it proceeds with the “else” branch, where the bound variables are not in scope.

In other words, the statement

if x :| P { S } else { T }

has the same meaning as

if exists x :: P { var x :| P; S } else { T }

The identifiers bound by the binding guard are ghost variables and cannot be assigned to non-ghost variables. They are only used in specification contexts.

Here is another example:

predicate P(n: int)
{
  n % 2 == 0
}

method M1() returns (ghost y: int)
    requires exists x :: P(x)
    ensures P(y)
{
  if x : int :| P(x) {
      y := x;
  }
}

8.10. If Statement (grammar)

Examples: 

method m(i: int) {
  var x: int;
  if i > 0 {
    x := i;
  } else {
    x := -i;
  }
  if * {
    x := i;
  } else {
    x := -i;
  }
  if i: nat, j: nat :| i+j<10 {
    assert i < 10;
  }
  if i == 0 {
    x := 0;
  } else if i > 0 {
    x := 1;
  } else {
    x := -1;
  }
  if 
    case i == 0 => x := 0;
    case i > 0 => x := 1;
    case i < 0 => x := -1;
}

The simplest form of an if statement uses a guard that is a boolean expression. For example,

  if x < 0 {
    x := -x;
  }

Unlike match statements, if statements do not have to be exhaustive: omitting the else block is the same as including an empty else block. To ensure that an if statement is exhaustive, use the if-case statement documented below.

If the guard is an asterisk then a non-deterministic choice is made:

  if * {
    print "True";
  } else {
    print "False";
  }

The then alternative of the if-statement must be a block statement; the else alternative may be either a block statement or another if statement. The condition of the if statement need not (but may) be enclosed in parentheses.

An if statement with a binding guard is non-deterministic; it will not be compiled if --enforce-determinism is enabled (even if it can be proved that there is a unique value). An if statement with * for a guard is non-deterministic and ghost.

The if-case statement using the AlternativeBlock form is similar to the if ... fi construct used in the book “A Discipline of Programming” by Edsger W. Dijkstra. It is used for a multi-branch if.

For example: 

method m(x: int, y: int) returns (max: int) 
{
  if {
    case x <= y => max := y;
    case y <= x => max := x;
  }
}

In this form, the expressions following the case keyword are called guards. The statement is evaluated by evaluating the guards in an undetermined order until one is found that is true and the statements to the right of => for that guard are executed. The statement requires at least one of the guards to evaluate to true (that is, if-case statements must be exhaustive: the guards must cover all cases).

In the if-with-cases, a sequence of statements may follow the =>; it may but need not be a block statement (a brace-enclosed sequence of statements).

The form that used ... (a refinement feature) as the guard is deprecated.

8.11. Match Statement (grammar)

Examples: 


match list {
  case Nil => {}
  case Cons(head,tail) => print head;
}
match x
case 1 =>
  print x;
case 2 =>
  var y := x*x;
  print y;
case _ =>
  print "Other";
  // Any statement after is captured in this case.

The match statement is used to do case analysis on a value of an expression. The expression may be a value of a basic type (e.g. int), a newtype, or an inductive or coinductive datatype (which includes the built-in tuple types). The expression after the match keyword is called the selector. The selector is evaluated and then matched against each clause in order until a matching clause is found.

The process of matching the selector expression against the case patterns is the same as for match expressions and is described in Section 9.31.2.

The selector need not be enclosed in parentheses; the sequence of cases may but need not be enclosed in braces. The cases need not be disjoint. The cases must be exhaustive, but you can use a wild variable (_) or a simple identifier to indicate “match anything”. Please refer to the section about case patterns to learn more about shadowing, constants, etc.

The code below shows an example of a match statement.

datatype Tree = Empty | Node(left: Tree, data: int, right: Tree)

// Return the sum of the data in a tree.
method Sum(x: Tree) returns (r: int)
{
  match x {
    case Empty => r := 0;
    case Node(t1, d, t2) =>
      var v1 := Sum(t1);
      var v2 := Sum(t2);
      r := v1 + d + v2;
  }
}

Note that the Sum method is recursive yet has no decreases annotation. In this case it is not needed because Dafny is able to deduce that t1 and t2 are smaller (structurally) than x. If Tree had been coinductive this would not have been possible since x might have been infinite.

8.12. While Statement (grammar)

Examples: 

method m() {
  var i := 10;
  while 0 < i
    invariant 0 <= i <= 10
    decreases i
  {
    i := i-1;
  }
  while * {}
  i := *;
  while 
     decreases if i < 0 then -i else i
  {
     case i < 0 => i := i + 1;
     case i > 0 => i := i - 1;
  }
}

Loops

Importantly, loops need loop specifications in order for Dafny to prove that they obey expected behavior. In some cases Dafny can infer the loop specifications by analyzing the code, so the loop specifications need not always be explicit. These specifications are described in Section 7.6 and Section 8.15.

The general loop statement in Dafny is the familiar while statement. It has two general forms.

The first form is similar to a while loop in a C-like language. For example:

method m(){
  var i := 0;
  while i < 5 {
    i := i + 1;
  }
}

In this form, the condition following the while is one of these:

The body of the loop is usually a block statement, but it can also be missing altogether. A loop with a missing body may still pass verification, but any attempt to compile the containing program will result in an error message. When verifying a loop with a missing body, the verifier will skip attempts to prove loop invariants and decreases assertions that would normally be asserted at the end of the loop body. There is more discussion about bodyless loops in Section 8.15.4.

The second form uses a case-based block. It is similar to the do ... od construct used in the book “A Discipline of Programming” by Edsger W. Dijkstra. For example:

method m(n: int){
  var r := n;
  while
    decreases if 0 <= r then r else -r
  {
    case r < 0 =>
      r := r + 1;
    case 0 < r =>
      r := r - 1;
  }
}

For this form, the guards are evaluated in some undetermined order until one is found that is true, in which case the corresponding statements are executed and the while statement is repeated. If none of the guards evaluates to true, then the loop execution is terminated.

The form that used ... (a refinement feature) as the guard is deprecated.

8.13. For Loops (grammar)

Examples: 

method m() decreases * {
  for i := 0 to 10 {}
  for _ := 0 to 10 {}
  for i := 0 to * invariant i >= 0 decreases * {}
  for i: int := 10 downto 0 {}
  for i: int := 10 downto 0 
}

The for statement provides a convenient way to write some common loops.

The statement introduces a local variable with optional type, which is called the loop index. The loop index is in scope in the specification and the body, but not after the for loop. Assignments to the loop index are not allowed. The type of the loop index can typically be inferred; if so, it need not be given explicitly. If the identifier is not used, it can be written as _, as illustrated in this repeat-20-times loop: 

for _ := 0 to 20 {
  Body
}

There are four basic variations of the for loop: 

for i: T := lo to hi
  LoopSpec
{ Body }

for i: T := hi downto lo
  LoopSpec
{ Body }

for i: T := lo to *
  LoopSpec
{ Body }

for i: T := hi downto *
  LoopSpec
{ Body }

Semantically, they are defined as the following respective while loops: 

{
  var _lo, _hi := lo, hi;
  assert _lo <= _hi && forall _i: int :: _lo <= _i <= _hi ==> _i is T;
  var i := _lo;
  while i != _hi
    invariant _lo <= i <= _hi
    LoopSpec
    decreases _hi - i
  {
    Body
    i := i + 1;
  }
}

{
  var _lo, _hi := lo, hi;
  assert _lo <= _hi && forall _i: int :: _lo <= _i <= _hi ==> _i is T;
  var i := _hi;
  while i != lo
    invariant _lo <= i <= _hi
    LoopSpec
    decreases i - _lo
  {
    i := i - 1;
    Body
  }
}

{
  var _lo := lo;
  assert forall _i: int :: _lo <= _i ==> _i is T;
  var i := _lo;
  while true
    invariant _lo <= i
    LoopSpec
  {
    Body
    i := i + 1;
  }
}

{
  var _hi := hi;
  assert forall _i: int :: _i <= _hi ==> _i is T;
  var i := _hi;
  while true
    invariant i <= _hi
    LoopSpec
  {
    i := i - 1;
    Body
  }
}

The expressions lo and hi are evaluated just once, before the loop iterations start.

Also, in all variations the values of i in the body are the values from lo to, but not including, hi. This makes it convenient to write common loops, including these:

for i := 0 to a.Length {
  Process(a[i]);
}
for i := a.Length downto 0 {
  Process(a[i]);
}

Nevertheless, hi must be a legal value for the type of the index variable, since that is how the index variable is used in the invariant.

If the end-expression is not *, then no explicit decreases is allowed, since such a loop is already known to terminate. If the end-expression is *, then the absence of an explicit decreases clause makes it default to decreases *. So, if the end-expression is * and no explicit decreases clause is given, the loop is allowed only in methods that are declared with decreases *.

The directions to or downto are contextual keywords. That is, these two words are part of the syntax of the for loop, but they are not reserved keywords elsewhere.

Just like for while loops, the body of a for-loop may be omitted during verification. This suppresses attempts to check assertions (like invariants) that would occur at the end of the loop. Eventually, however a body must be provided; the compiler will not compile a method containing a body-less for-loop. There is more discussion about bodyless loops in Section 8.15.4.

8.14. Break and Continue Statements (grammar)

Examples: 

class A { var f: int }
method m(a: A) {
  label x:
  while true {
    if (*) { break; }
  }
  label y: {
    var z := 1;
    if * { break y; }
    z := 2;
  }

}

Break and continue statements provide a means to transfer control in a way different than the usual nested control structures. There are two forms of each of these statements: with and without a label.

If a label is used, the break or continue statement must be enclosed in a statement with that label. The enclosing statement is called the target of the break or continue.

A break statement transfers control to the point immediately following the target statement. For example, such a break statement can be used to exit a sequence of statements in a block statement before reaching the end of the block.

For example, 

label L: {
  var n := ReadNext();
  if n < 0 {
    break L;
  }
  DoSomething(n);
}

is equivalent to 

{
  var n := ReadNext();
  if 0 <= n {
    DoSomething(n);
  }
}

If no label is specified and the statement lists n occurrences of break, then the statement must be enclosed in at least n levels of loop statements. Control continues after exiting n enclosing loops. For example,

method m() {
  for i := 0 to 10 {
    for j := 0 to 10 {
      label X: {
        for k := 0 to 10 {
          if j + k == 15 {
            break break;
          }
        }
      }
    }
    // control continues here after the "break break", exiting two loops
  }
}

Note that a non-labeled break pays attention only to loops, not to labeled statements. For example, the labeled block X in the previous example does not play a role in determining the target statement of the break break;.

For a continue statement, the target statement must be a loop statement. The continue statement transfers control to the point immediately before the closing curly-brace of the loop body.

For example, 

method m() {
  for i := 0 to 100 {
    if i == 17 {
      continue;
    }
    DoSomething(i);
  }
}
method DoSomething(i:int){}

is equivalent to 

method m() {
  for i := 0 to 100 {
    if i != 17 {
      DoSomething(i);
    }
  }
}
method DoSomething(i:int){}

The same effect can also be obtained by wrapping the loop body in a labeled block statement and then using break with a label, but that usually makes for a more cluttered program: 

method m() {
  for i := 0 to 100 {
    label LoopBody: {
      if i == 17 {
        break LoopBody;
      }
      DoSomething(i);
    }
  }
}
method DoSomething(i:int){}

Stated differently, continue has the effect of ending the current loop iteration, after which control continues with any remaining iterations. This is most natural for for loops. For a while loop, be careful to make progress toward termination before a continue statement. For example, the following program snippet shows an easy mistake to make (the verifier will complain that the loop may not terminate):

method m() {
  var i := 0;
  while i < 100 {
    if i == 17 {
      continue; // error: this would cause an infinite loop
    }
    DoSomething(i);
    i := i + 1;
  }
}
method DoSomething(i:int){}

The continue statement can give a label, provided the label is a label of a loop. For example,

method m() {
  label Outer:
  for i := 0 to 100 {
    for j := 0 to 100 {
      if i + j == 19 {
        continue Outer;
      }
      WorkIt(i, j);
    }
    PostProcess(i);
    // the "continue Outer" statement above transfers control to here
  }
}
method WorkIt(i:int, j:int){}
method PostProcess(i:int){}

If a non-labeled continue statement lists n occurrences of break before the continue keyword, then the statement must be enclosed in at least n + 1 levels of loop statements. The effect is to break out of the n most closely enclosing loops and then continue the iterations of the next loop. That is, n occurrences of break followed by one more break; will break out of n levels of loops and then do a break, whereas n occurrences of break followed by continue; will break out of n levels of loops and then do a continue.

For example, the WorkIt example above can equivalently be written without labels as 

method m() {
  for i := 0 to 100 {
    for j := 0 to 100 {
      if i + j == 19 {
        break continue;
      }
      WorkIt(i, j);
    }
    PostProcess(i);
    // the "break continue" statement above transfers control to here
  }
}
method WorkIt(i:int, j:int){}
method PostProcess(i:int){}

Note that a loop invariant is checked on entry to a loop and at the closing curly-brace of the loop body. It is not checked at break statements. For continue statements, the loop invariant is checked as usual at the closing curly-brace that the continue statement jumps to. This checking ensures that the loop invariant holds at the very top of every iteration. Commonly, the only exit out of a loop happens when the loop guard evaluates to false. Since no state is changed between the top of an iteration (where the loop invariant is known to hold) and the evaluation of the loop guard, one can also rely on the loop invariant to hold immediately following the loop. But the loop invariant may not hold immediately following a loop if a loop iteration changes the program state and then exits the loop with a break statement.

For example, the following program verifies: 

method m() {
  var i := 0;
  while i < 10
    invariant 0 <= i <= 10
  {
    if P(i) {
      i := i + 200;
      break;
    }
    i := i + 1;
  }
  assert i == 10 || 200 <= i < 210;
}
predicate P(i:int)

To explain the example, the loop invariant 0 <= i <= 10 is known to hold at the very top of each iteration, that is, just before the loop guard i < 10 is evaluated. If the loop guard evaluates to false, then the negated guard condition (10 <= i) and the invariant hold, so i == 10 will hold immediately after the loop. If the loop guard evaluates to true (that is, i < 10 holds), then the loop body is entered. If the test P(i) then evaluates to true, the loop adds 200 to i and breaks out of the loop, so on such a path, 200 <= i < 210 is known to hold immediately after the loop. This is summarized in the assert statement in the example. So, remember, a loop invariant holds at the very top of every iteration, not necessarily immediately after the loop.

8.15. Loop Specifications

For some simple loops, such as those mentioned previously, Dafny can figure out what the loop is doing without more help. However, in general the user must provide more information in order to help Dafny prove the effect of the loop. This information is provided by a loop specification. A loop specification provides information about invariants, termination, and what the loop modifies. For additional tutorial information see [@KoenigLeino:MOD2011] or the online Dafny tutorial.

8.15.1. Loop invariants

Loops present a problem for specification-based reasoning. There is no way to know in advance how many times the code will go around the loop and a tool cannot reason about every one of a possibly unbounded sequence of unrollings. In order to consider all paths through a program, specification-based program verification tools require loop invariants, which are another kind of annotation.

A loop invariant is an expression that holds just prior to the loop test, that is, upon entering a loop and after every execution of the loop body. It captures something that is invariant, i.e. does not change, about every step of the loop. Now, obviously we are going to want to change variables, etc. each time around the loop, or we wouldn’t need the loop. Like pre- and postconditions, an invariant is a property that is preserved for each execution of the loop, expressed using the same boolean expressions we have seen. For example,

var i := 0;
while i < n
  invariant 0 <= i
{
  i := i + 1;
}

When you specify an invariant, Dafny proves two things: the invariant holds upon entering the loop, and it is preserved by the loop. By preserved, we mean that assuming that the invariant holds at the beginning of the loop (just prior to the loop test), we must show that executing the loop body once makes the invariant hold again. Dafny can only know upon analyzing the loop body what the invariants say, in addition to the loop guard (the loop condition). Just as Dafny will not discover properties of a method on its own, it will not know that any but the most basic properties of a loop are preserved unless it is told via an invariant.

8.15.2. Loop termination

Dafny proves that code terminates, i.e. does not loop forever, by using decreases annotations. For many things, Dafny is able to guess the right annotations, but sometimes it needs to be made explicit. There are two places Dafny proves termination: loops and recursion.