From 5623306213e01e8d667a7893cb0c3275ecfbf065 Mon Sep 17 00:00:00 2001 From: Clément Pit--Claudel Date: Sat, 22 Aug 2015 13:44:42 -0700 Subject: Add a 'tutorial' folder to the distribution, with an initial example. It would be nice to gather neat Dafny examples there; each new feature could have its own small file that demoes it, and we could also have examples that showcase stuff that we think is impressive. I'm adding this as a test folder, because it's important to check that these cool examples don't break, but the focus probably shouldn't be on exhaustively testing the features being demoed. --- Test/tutorial/maximum.dfy | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100644 Test/tutorial/maximum.dfy (limited to 'Test/tutorial/maximum.dfy') diff --git a/Test/tutorial/maximum.dfy b/Test/tutorial/maximum.dfy new file mode 100644 index 00000000..81faa219 --- /dev/null +++ b/Test/tutorial/maximum.dfy @@ -0,0 +1,32 @@ +// RUN: %dafny /compile:0 /print:"%t.print" /dprint:"%t.dprint" /autoTriggers:1 /printTooltips "%s" > "%t" +// RUN: %diff "%s.expect" "%t" + +// This file shows how to specify and implement a function to compute the +// largest element of a list. The function is fully specified by two +// preconditions, as proved by the MaximumIsUnique lemma below. + +method Maximum(values: seq) returns (max: int) + requires values != [] + ensures max in values + ensures forall i | 0 <= i < |values| :: values[i] <= max +{ + max := values[0]; + var idx := 0; + while (idx < |values|) + invariant max in values + invariant idx <= |values| + invariant forall j | 0 <= j < idx :: values[j] <= max + { + if (values[idx] > max) { + max := values[idx]; + } + idx := idx + 1; + } +} + +lemma MaximumIsUnique(values: seq, m1: int, m2: int) + requires m1 in values && forall i | 0 <= i < |values| :: values[i] <= m1 + requires m2 in values && forall i | 0 <= i < |values| :: values[i] <= m2 + ensures m1 == m2 { + // This lemma does not need a body: Dafny is able to prove it correct entirely automatically. +} -- cgit v1.2.3