// RUN: %dafny /compile:0 /dprint:"%t.dprint" "%s" > "%t" // RUN: %diff "%s.expect" "%t" // Dafny versions of examples from "Practical Coinduction" by Kozen and Silva. // The comments in this file explain some things about Dafny and its support for // co-induction; for a full description, see "Co-induction Simply" by Leino and // Moskal. // In Dafny, a co-inductive datatype is declared like an inductive datatype, but // using the keyword "codatatype" instead of "datatype". The definition lists the // constructors of the co-datatype (here, Cons) and has the option of naming // destructors (here, hd and tl). Here and in some other signatures, the type // argument to Stream can be omitted, because Dafny fills it in automatically. codatatype Stream = Cons(hd: A, tl: Stream) // -------------------------------------------------------------------------- // A co-predicate is defined as a largest fix-point. copredicate LexLess(s: Stream, t: Stream) { s.hd <= t.hd && (s.hd == t.hd ==> LexLess(s.tl, t.tl)) } // A co-lemma is used to establish the truth of a co-predicate. colemma Theorem1_LexLess_Is_Transitive(s: Stream, t: Stream, u: Stream) requires LexLess(s, t) && LexLess(t, u) ensures LexLess(s, u) { // Here is the proof, which is actually a body of code. It lends itself to a // simple, intuitive co-inductive reading. For a theorem this simple, this simple // reading is all you need. To understand more complicated examples, or to see // what's actually going on under the hood, it's best to read the "Co-induction // Simply" paper. if s.hd == u.hd { Theorem1_LexLess_Is_Transitive(s.tl, t.tl, u.tl); } } // Actually, Dafny can do the proof of the previous lemma completely automatically. Here it is: colemma Theorem1_LexLess_Is_Transitive_Automatic(s: Stream, t: Stream, u: Stream) requires LexLess(s, t) && LexLess(t, u) ensures LexLess(s, u) { // no manual proof needed, so the body of the co-lemma is empty } // The following predicate captures the (inductively defined) negation of (the // co-inductively defined) LexLess above. predicate NotLexLess(s: Stream, t: Stream) { exists k: nat :: NotLexLess'(k, s, t) } predicate NotLexLess'(k: nat, s: Stream, t: Stream) { if k == 0 then false else !(s.hd <= t.hd) || (s.hd == t.hd && NotLexLess'(k-1, s.tl, t.tl)) } lemma EquivalenceTheorem(s: Stream, t: Stream) ensures LexLess(s, t) <==> !NotLexLess(s, t) { if !NotLexLess(s, t) { EquivalenceTheorem0(s, t); } if LexLess(s, t) { EquivalenceTheorem1(s, t); } } colemma EquivalenceTheorem0(s: Stream, t: Stream) requires !NotLexLess(s, t) ensures LexLess(s, t) { // Here, more needs to be said about the way Dafny handles co-lemmas. // The way a co-lemma establishes a co-predicate is to prove, by induction, // that all finite unrollings of the co-predicate holds. The unrolling // depth is specified using an implicit parameter _k to the co-lemma. EquivalenceTheorem0_Lemma(_k, s, t); } // The following lemma is an ordinary inductive lemma. The syntax ...#[...] // indicates a finite unrolling of a co-inductive predicate. In particular, // LexLess#[k] refers to k unrollings of LexLess. lemma EquivalenceTheorem0_Lemma(k: nat, s: Stream, t: Stream) requires !NotLexLess'(k, s, t) ensures LexLess#[k](s, t) { // This simple inductive proof is done completely automatically by Dafny. } lemma EquivalenceTheorem1(s: Stream, t: Stream) requires LexLess(s, t) ensures !NotLexLess(s, t) { // The forall statement in Dafny is used, here, as universal introduction: // what EquivalenceTheorem1_Lemma establishes for one k, the forall // statement establishes for all k. forall k: nat { EquivalenceTheorem1_Lemma(k, s, t); } } lemma EquivalenceTheorem1_Lemma(k: nat, s: Stream, t: Stream) requires LexLess(s, t) ensures !NotLexLess'(k, s, t) { } lemma Theorem1_Alt(s: Stream, t: Stream, u: Stream) requires NotLexLess(s, u) ensures NotLexLess(s, t) || NotLexLess(t, u) { forall k: nat | NotLexLess'(k, s, u) { Theorem1_Alt_Lemma(k, s, t, u); } } lemma Theorem1_Alt_Lemma(k: nat, s: Stream, t: Stream, u: Stream) requires NotLexLess'(k, s, u) ensures NotLexLess'(k, s, t) || NotLexLess'(k, t, u) { } function PointwiseAdd(s: Stream, t: Stream): Stream { Cons(s.hd + t.hd, PointwiseAdd(s.tl, t.tl)) } colemma Theorem2_Pointwise_Addition_Is_Monotone(s: Stream, t: Stream, u: Stream, v: Stream) requires LexLess(s, t) && LexLess(u, v) ensures LexLess(PointwiseAdd(s, u), PointwiseAdd(t, v)) { // The co-lemma will establish the co-inductive predicate by establishing // all finite unrollings thereof. Each finite unrolling is proved by // induction, and this induction is performed automatically by Dafny. Thus, // the proof of this co-lemma is trivial (that is, the body of the co-lemma // is empty). } // -------------------------------------------------------------------------- // The declaration of an (inductive or co-inductive) datatype in Dafny automatically // gives rise to the declaration of a discriminator for each constructor. The name // of such a discriminator is the name of the constructor plus a question mark (that // is, the question mark is part of the identifier that names the discriminator). // For example, the boolean expression r.Arrow? returns whether or not a RecType r // has been constructed by the Arrow constructor. One can of course also use a // match expression or match statement for this purpose, but for whatever reason, I // didn't do so in this file. Note that the precondition of the access r.dom is // r.Arrow?. Also, for a parameter-less constructor like Bottom, a use of the // discriminator like r.Bottom? is equivalent to r == Bottom. codatatype RecType = Bottom | Top | Arrow(dom: RecType, ran: RecType) copredicate Subtype(a: RecType, b: RecType) { a == Bottom || b == Top || (a.Arrow? && b.Arrow? && Subtype(b.dom, a.dom) && Subtype(a.ran, b.ran)) } colemma Theorem3_Subtype_Is_Transitive(a: RecType, b: RecType, c: RecType) requires Subtype(a, b) && Subtype(b, c) ensures Subtype(a, c) { } // -------------------------------------------------------------------------- // Closure Conversion type Const // uninterpreted type (the details are not important here) type Var(==) // uninterpreted type that supports equality datatype Term = TermConst(Const) | TermVar(Var) | TermAbs(abs: LambdaAbs) datatype LambdaAbs = Fun(v: Var, body: Term) codatatype Val = ValConst(Const) | ValCl(cl: Cl) codatatype Cl = Closure(abs: LambdaAbs, env: ClEnv) codatatype ClEnv = ClEnvironment(m: map) // The built-in Dafny "map" type denotes finite maps copredicate ClEnvBelow(c: ClEnv, d: ClEnv) { // The expression "y in c.m" says that y is in the domain of the finite map // c.m. forall y :: y in c.m ==> y in d.m && ValBelow(c.m[y], d.m[y]) } copredicate ValBelow(u: Val, v: Val) { (u.ValConst? && v.ValConst? && u == v) || (u.ValCl? && v.ValCl? && u.cl.abs == v.cl.abs && ClEnvBelow(u.cl.env, v.cl.env)) } colemma Theorem4a_ClEnvBelow_Is_Transitive(c: ClEnv, d: ClEnv, e: ClEnv) requires ClEnvBelow(c, d) && ClEnvBelow(d, e) ensures ClEnvBelow(c, e) { forall y | y in c.m { Theorem4b_ValBelow_Is_Transitive#[_k-1](c.m[y], d.m[y], e.m[y]); } } colemma Theorem4b_ValBelow_Is_Transitive(u: Val, v: Val, w: Val) requires ValBelow(u, v) && ValBelow(v, w) ensures ValBelow(u, w) { if u.ValCl? { Theorem4a_ClEnvBelow_Is_Transitive(u.cl.env, v.cl.env, w.cl.env); } } datatype Capsule = Cap(e: Term, s: map) datatype ConstOrAbs = CC(c: Const) | AA(abs: LambdaAbs) predicate IsCapsule(cap: Capsule) { cap.e.TermAbs? } function ClosureConversion(cap: Capsule): Cl requires IsCapsule(cap) { Closure(cap.e.abs, ClosureConvertedMap(cap.s)) // In the Kozen and Silva paper, there are more conditions, having to do with free variables, // but, apparently, they don't matter for the theorems being proved here. } function ClosureConvertedMap(s: map): ClEnv { // The following line uses a map comprehension. In the notation "map y | D :: E", // D constrains the domain of the map to be all values of y satisfying D, and // E says what a y in the domain maps to. ClEnvironment(map y: Var | y in s :: if s[y].AA? then ValCl(Closure(s[y].abs, ClosureConvertedMap(s))) else ValConst(s[y].c)) } predicate CapsuleEnvironmentBelow(s: map, t: map) { forall y :: y in s ==> y in t && s[y] == t[y] } colemma Theorem5_ClosureConversion_Is_Monotone(s: map, t: map) requires CapsuleEnvironmentBelow(s, t) ensures ClEnvBelow(ClosureConvertedMap(s), ClosureConvertedMap(t)) { } // -------------------------------------------------------------------------- // The following defines, co-inductively, a relation on streams. The syntactic // shorthand in Dafny lets us omit the type parameter to Bisim and the (same) // type arguments in the types of s and t. If we want to write this explicitly, // we would write: // copredicate Bisim(s: Stream, t: Stream) // which is equivalent. (Being able to omit the arguments reduces clutter. Note, // in a similar way, if one tells a colleague about Theorem 6, one can either // say the explicit "Bisim on A-streams is a symmetric relation" or, since the // A in that sentence is not used, "Bisim on streams is a symmetric relation".) copredicate Bisim(s: Stream, t: Stream) { s.hd == t.hd && Bisim(s.tl, t.tl) } colemma Theorem6_Bisim_Is_Symmetric(s: Stream, t: Stream) requires Bisim(s, t) ensures Bisim(t, s) { // proof is automatic } function merge(s: Stream, t: Stream): Stream { Cons(s.hd, merge(t, s.tl)) } // SplitLeft and SplitRight are defined in terms of each other. Because the // call to SplitRight in the body of SplitLeft is an argument to a co-constructor, // Dafny treats the call as a co-recurvie call. A consequence of this is that // there is no proof obligation to show termination for that call. However, the // call from SplitRight back to SplitLeft is an ordinary (mutually) recursive // call, and hence Dafny checks termination for it. // In general, the termination argument needs to be supplied explicitly in terms // of a metric, rank, variant function, or whatever you want to call it--a // "decreases" clause in Dafny. Dafny provides some help in making up "decreases" // clauses, and in this case it automatically adds "decreases 0" to SplitLeft // and "decreases 1" to SplitRight. With these "decreases" clauses, the // termination check of SplitRight's call to SplitLeft will simply be "0 < 1", // which is trivial to check. function SplitLeft(s: Stream): Stream { Cons(s.hd, SplitRight(s.tl)) } function SplitRight(s: Stream): Stream { SplitLeft(s.tl) } colemma Theorem7_Merge_Is_Left_Inverse_Of_Split_Bisim(s: Stream) ensures Bisim(merge(SplitLeft(s), SplitRight(s)), s) { var LHS := merge(SplitLeft(s), SplitRight(s)); // The construct that follows is a "calc" statement. It gives a way to write an // equational proof. Each line in the calculation is an expression that, on // behalf of the given hint, is equal to the next line of the calculation. In // the first such step below, the hint is omitted (there's just an English // comment, but Dafny ignores it, of course). In the next two steps, the hint // is itself a calculation. In the last step, the hint is an invocation of // the co-inductive hypothesis--that is, it is a call of the co-lemma itself. calc { Bisim#[_k](LHS, s); // when all comes around, this is our proof goal: Bisim unrolled _k times (where _k > 0) == // def. Bisim (more precisely, def. Bisim#[_k] in terms of Bisim#[_k-1]) LHS.hd == s.hd && Bisim#[_k-1](LHS.tl, s.tl); == calc { // the left conjunct is easy to establish, so let's do that now LHS.hd; == merge(SplitLeft(s), SplitRight(s)).hd; == SplitLeft(s).hd; == s.hd; } Bisim#[_k-1](LHS.tl, s.tl); == calc { // let us massage the formula LHS.tl LHS.tl; == merge(SplitLeft(s), SplitRight(s)).tl; == merge(SplitRight(s), SplitLeft(s).tl); == merge(SplitLeft(s.tl), SplitRight(s.tl)); } Bisim#[_k-1](merge(SplitLeft(s.tl), SplitRight(s.tl)), s.tl); // this is the hypothesis on s.tl == { Theorem7_Merge_Is_Left_Inverse_Of_Split_Bisim(s.tl); } true; } } colemma Theorem7_Merge_Is_Left_Inverse_Of_Split_Equal(s: Stream) ensures merge(SplitLeft(s), SplitRight(s)) == s { // The proof of this co-lemma is actually done completely automatically (so the // body of this co-lemma can be empty). However, just to show what the calculations // would look like in a hand proof, here they are: calc { merge(SplitLeft(s), SplitRight(s)).hd; == SplitLeft(s).hd; == s.hd; } calc { merge(SplitLeft(s), SplitRight(s)).tl; == merge(SplitRight(s), SplitLeft(s).tl); == merge(SplitLeft(s.tl), SplitRight(s.tl)); ==#[_k-1] { Theorem7_Merge_Is_Left_Inverse_Of_Split_Equal(s.tl); } s.tl; } }