1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
// --------------------------------------------------
module CoRecursion {
codatatype Stream<T> = More(head: T, rest: Stream);
function AscendingChain(n: int): Stream<int>
{
More(n, AscendingChain(n+1))
}
function AscendingChainAndRead(n: nat): Stream<int>
reads this; // with a reads clause, this function is not a co-recusvie function
{
More(n, AscendingChainAndRead(n+1)) // error: cannot prove termination
}
function AscendingChainAndPostcondition(n: nat): Stream<int>
ensures false; // with an ensures clause, this function is not a co-recusvie function
{
More(n, AscendingChainAndPostcondition(n+1)) // error: cannot prove termination
}
datatype List<T> = Nil | Cons(T, List);
function Prefix(n: nat, s: Stream): List
{
if n == 0 then Nil else
Cons(s.head, Prefix(n-1, s.rest))
}
}
// --------------------------------------------------
module CoRecursionNotUsed {
codatatype Stream<T> = More(T, Stream);
function F(s: Stream, n: nat): Stream
decreases n, true;
{
G(s, n)
}
function G(s: Stream, n: nat): Stream
decreases n, false;
{
if n == 0 then s else Tail(F(s, n-1))
}
function Tail(s: Stream): Stream
{
match s case More(hd, tl) => tl
}
function Diverge(n: nat): nat
{
Diverge(n) // error: cannot prove termination
}
}
// --------------------------------------------------
module EqualityIsSuperDestructive {
codatatype Stream<T> = Cons(head: T, tail: Stream)
function F(s: Stream<int>): Stream<int>
{
// Co-recursive calls are not allowed in arguments of equality, so the following call to
// F(s) is a recursive call.
if Cons(1, F(s)) == Cons(1, Cons(1, s)) // error: cannot prove termination
then Cons(2, s) else Cons(1, s)
}
lemma Lemma(s: Stream<int>)
{
// The following three assertions follow from the definition of F, so F had better
// generate some error (which it does -- the recursive call to F in F does not terminate).
assert F(s) == Cons(1, s);
assert F(s) == Cons(2, s);
assert false;
}
}
// --------------------------------------------------
module MixRecursiveAndCorecursive {
codatatype Stream<T> = Cons(head: T, tail: Stream)
function F(n: nat): Stream<int>
{
if n == 0 then
Cons(0, F(5)) // error: cannot prove termination -- by itself, this would look like a properly guarded co-recursive call...
else
F(n - 1).tail // but the fact that this recursive call is not tail recursive means that call in the 'then' branch is not
// allowed to be a co-recursive
}
// same thing but with some mutual recursion going on
function G(n: nat): Stream<int>
{
if n == 0 then
Cons(0, H(5)) // error: cannot prove termination
else
H(n)
}
function H(n: nat): Stream<int>
requires n != 0;
decreases n, 0;
{
G(n-1).tail
}
// but if all the recursive calls are tail recursive, then all is cool
function X(n: nat): Stream<int>
{
if n == 0 then
Cons(0, Y(5)) // error: cannot prove termination
else
Y(n)
}
function Y(n: nat): Stream<int>
requires n != 0;
decreases n, 0;
{
X(n-1)
}
}
|
