6 "even 0" |
6 "even 0" |
7 | "even n \<Longrightarrow> odd (Suc n)" |
7 | "even n \<Longrightarrow> odd (Suc n)" |
8 | "odd n \<Longrightarrow> even (Suc n)" |
8 | "odd n \<Longrightarrow> even (Suc n)" |
9 |
9 |
10 code_pred (mode: [], [1]) [show_steps] even . |
10 code_pred (mode: [], [1]) [show_steps] even . |
11 code_pred [depth_limited] even . |
11 code_pred [depth_limited, show_compilation] even . |
12 code_pred [rpred] even . |
12 (*code_pred [rpred] even .*) |
13 |
13 |
14 thm odd.equation |
14 thm odd.equation |
15 thm even.equation |
15 thm even.equation |
16 thm odd.depth_limited_equation |
16 thm odd.depth_limited_equation |
17 thm even.depth_limited_equation |
17 thm even.depth_limited_equation |
|
18 (* |
18 thm even.rpred_equation |
19 thm even.rpred_equation |
19 thm odd.rpred_equation |
20 thm odd.rpred_equation |
20 |
21 *) |
21 (* |
22 (* |
22 lemma unit: "unit_case f = (\<lambda>x. f)" |
23 lemma unit: "unit_case f = (\<lambda>x. f)" |
23 apply (rule ext) |
24 apply (rule ext) |
24 apply (case_tac x) |
25 apply (case_tac x) |
25 apply (simp only: unit.cases) |
26 apply (simp only: unit.cases) |
80 "append [] xs xs" |
81 "append [] xs xs" |
81 | "append xs ys zs \<Longrightarrow> append (x # xs) ys (x # zs)" |
82 | "append xs ys zs \<Longrightarrow> append (x # xs) ys (x # zs)" |
82 |
83 |
83 code_pred (mode: [1, 2], [3], [2, 3], [1, 3], [1, 2, 3]) [inductify] append . |
84 code_pred (mode: [1, 2], [3], [2, 3], [1, 3], [1, 2, 3]) [inductify] append . |
84 code_pred [depth_limited] append . |
85 code_pred [depth_limited] append . |
85 code_pred [rpred] append . |
86 (*code_pred [rpred] append .*) |
86 |
87 |
87 thm append.equation |
88 thm append.equation |
88 thm append.depth_limited_equation |
89 thm append.depth_limited_equation |
89 thm append.rpred_equation |
90 (*thm append.rpred_equation*) |
90 |
91 |
91 values "{(ys, xs). append xs ys [0, Suc 0, 2]}" |
92 values "{(ys, xs). append xs ys [0, Suc 0, 2]}" |
92 values "{zs. append [0, Suc 0, 2] [17, 8] zs}" |
93 values "{zs. append [0, Suc 0, 2] [17, 8] zs}" |
93 values "{ys. append [0, Suc 0, 2] ys [0, Suc 0, 2, 17, 0, 5]}" |
94 values "{ys. append [0, Suc 0, 2] ys [0, Suc 0, 2, 17, 0, 5]}" |
94 values [depth_limit = 3] "{(xs, ys). append xs ys [1, 2, 3, 4, (5::nat)]}" |
95 values [depth_limit = 3] "{(xs, ys). append xs ys [1, 2, 3, 4, (5::nat)]}" |
95 values [depth_limit = 10 random] 15 "{(ys, zs). append [1::nat, 2] ys zs}" |
96 (*values [depth_limit = 10 random] 15 "{(ys, zs). append [1::nat, 2] ys zs}"*) |
96 |
97 |
97 value [code] "Predicate.the (append_1_2 [0::int, 1, 2] [3, 4, 5])" |
98 value [code] "Predicate.the (append_1_2 [0::int, 1, 2] [3, 4, 5])" |
98 value [code] "Predicate.the (append_3 ([]::int list))" |
99 value [code] "Predicate.the (append_3 ([]::int list))" |
99 |
100 |
100 subsection {* Tricky case with alternative rules *} |
101 subsection {* Tricky case with alternative rules *} |
128 where |
129 where |
129 "tupled_append ([], xs, xs)" |
130 "tupled_append ([], xs, xs)" |
130 | "tupled_append (xs, ys, zs) \<Longrightarrow> tupled_append (x # xs, ys, x # zs)" |
131 | "tupled_append (xs, ys, zs) \<Longrightarrow> tupled_append (x # xs, ys, x # zs)" |
131 |
132 |
132 code_pred tupled_append . |
133 code_pred tupled_append . |
133 code_pred [rpred] tupled_append . |
134 (*code_pred [rpred] tupled_append .*) |
134 thm tupled_append.equation |
135 thm tupled_append.equation |
135 (* |
136 (* |
136 TODO: values with tupled modes |
137 TODO: values with tupled modes |
137 values "{xs. tupled_append ([1,2,3], [4,5], xs)}" |
138 values "{xs. tupled_append ([1,2,3], [4,5], xs)}" |
138 *) |
139 *) |
196 "partition f [] [] []" |
197 "partition f [] [] []" |
197 | "f x \<Longrightarrow> partition f xs ys zs \<Longrightarrow> partition f (x # xs) (x # ys) zs" |
198 | "f x \<Longrightarrow> partition f xs ys zs \<Longrightarrow> partition f (x # xs) (x # ys) zs" |
198 | "\<not> f x \<Longrightarrow> partition f xs ys zs \<Longrightarrow> partition f (x # xs) ys (x # zs)" |
199 | "\<not> f x \<Longrightarrow> partition f xs ys zs \<Longrightarrow> partition f (x # xs) ys (x # zs)" |
199 |
200 |
200 code_pred (mode: [1], [2, 3], [1, 2], [1, 3], [1, 2, 3]) partition . |
201 code_pred (mode: [1], [2, 3], [1, 2], [1, 3], [1, 2, 3]) partition . |
201 code_pred [depth_limited] partition . |
202 (*code_pred [depth_limited] partition .*) |
202 thm partition.depth_limited_equation |
203 (*thm partition.depth_limited_equation*) |
203 (*code_pred [rpred] partition .*) |
204 (*code_pred [rpred] partition .*) |
204 |
205 |
205 inductive tupled_partition :: "('a \<Rightarrow> bool) \<Rightarrow> ('a list \<times> 'a list \<times> 'a list) \<Rightarrow> bool" |
206 inductive tupled_partition :: "('a \<Rightarrow> bool) \<Rightarrow> ('a list \<times> 'a list \<times> 'a list) \<Rightarrow> bool" |
206 for f where |
207 for f where |
207 "tupled_partition f ([], [], [])" |
208 "tupled_partition f ([], [], [])" |
256 inductive succ :: "nat \<Rightarrow> nat \<Rightarrow> bool" where |
257 inductive succ :: "nat \<Rightarrow> nat \<Rightarrow> bool" where |
257 "succ 0 1" |
258 "succ 0 1" |
258 | "succ m n \<Longrightarrow> succ (Suc m) (Suc n)" |
259 | "succ m n \<Longrightarrow> succ (Suc m) (Suc n)" |
259 |
260 |
260 code_pred succ . |
261 code_pred succ . |
261 code_pred [rpred] succ . |
262 (*code_pred [rpred] succ .*) |
262 thm succ.equation |
263 thm succ.equation |
263 thm succ.rpred_equation |
264 (*thm succ.rpred_equation*) |
264 |
265 |
265 values 10 "{(m, n). succ n m}" |
266 values 10 "{(m, n). succ n m}" |
266 values "{m. succ 0 m}" |
267 values "{m. succ 0 m}" |
267 values "{m. succ m 0}" |
268 values "{m. succ m 0}" |
268 |
269 |
382 code_pred (inductify_all) (rpred) filterP . |
383 code_pred (inductify_all) (rpred) filterP . |
383 thm filterP.rpred_equation |
384 thm filterP.rpred_equation |
384 *) |
385 *) |
385 thm lexord_def |
386 thm lexord_def |
386 code_pred [inductify] lexord . |
387 code_pred [inductify] lexord . |
387 code_pred [inductify, rpred] lexord . |
388 (*code_pred [inductify, rpred] lexord .*) |
388 thm lexord.equation |
389 thm lexord.equation |
389 inductive less_than_nat :: "nat * nat => bool" |
390 inductive less_than_nat :: "nat * nat => bool" |
390 where |
391 where |
391 "less_than_nat (0, x)" |
392 "less_than_nat (0, x)" |
392 | "less_than_nat (x, y) ==> less_than_nat (Suc x, Suc y)" |
393 | "less_than_nat (x, y) ==> less_than_nat (Suc x, Suc y)" |
393 |
394 |
394 code_pred less_than_nat . |
395 code_pred less_than_nat . |
395 code_pred [depth_limited] less_than_nat . |
396 code_pred [depth_limited] less_than_nat . |
396 code_pred [rpred] less_than_nat . |
397 (*code_pred [rpred] less_than_nat .*) |
397 |
398 |
398 inductive test_lexord :: "nat list * nat list => bool" |
399 inductive test_lexord :: "nat list * nat list => bool" |
399 where |
400 where |
400 "lexord less_than_nat (xs, ys) ==> test_lexord (xs, ys)" |
401 "lexord less_than_nat (xs, ys) ==> test_lexord (xs, ys)" |
401 |
402 |
402 code_pred [rpred] test_lexord . |
403 (*code_pred [rpred] test_lexord .*) |
403 code_pred [depth_limited] test_lexord . |
404 code_pred [depth_limited] test_lexord . |
404 thm test_lexord.depth_limited_equation |
405 thm test_lexord.depth_limited_equation |
405 thm test_lexord.rpred_equation |
406 (*thm test_lexord.rpred_equation*) |
406 |
407 |
407 values [depth_limit = 5] "{x. test_lexord ([1, 2, 3], [1, 2, 5])}" |
408 (*values [depth_limit = 5] "{x. test_lexord ([1, 2, 3], [1, 2, 5])}"*) |
408 |
409 |
409 values [depth_limit = 25 random] "{xys. test_lexord xys}" |
410 (*values [depth_limit = 25 random] "{xys. test_lexord xys}"*) |
410 |
411 |
411 values [depth_limit = 5 random] "{xy. lexord less_than_nat xy}" |
412 (*values [depth_limit = 5 random] "{xy. lexord less_than_nat xy}"*) |
412 ML {* Predicate_Compile_Core.do_proofs := false *} |
413 |
413 lemma "(u, v) : lexord less_than_nat ==> (x @ u, y @ v) : lexord less_than_nat" |
414 lemma "(u, v) : lexord less_than_nat ==> (x @ u, y @ v) : lexord less_than_nat" |
414 quickcheck[generator=pred_compile] |
415 (*quickcheck[generator=pred_compile]*) |
415 oops |
416 oops |
416 |
417 |
417 lemmas [code_pred_def] = lexn_conv lex_conv lenlex_conv |
418 lemmas [code_pred_def] = lexn_conv lex_conv lenlex_conv |
418 (* |
419 (* |
419 code_pred [inductify] lexn . |
420 code_pred [inductify] lexn . |
420 thm lexn.equation |
421 thm lexn.equation |
421 *) |
422 *) |
422 code_pred [inductify, rpred] lexn . |
423 (*code_pred [inductify, rpred] lexn .*) |
423 |
424 |
424 thm lexn.rpred_equation |
425 (*thm lexn.rpred_equation*) |
425 |
426 |
426 code_pred [inductify] lenlex . |
427 code_pred [inductify] lenlex . |
427 thm lenlex.equation |
428 thm lenlex.equation |
428 (* |
429 (* |
429 code_pred [inductify, rpred] lenlex . |
430 code_pred [inductify, rpred] lenlex . |
448 h = max (height l) (height r) + 1 \<and> avl l \<and> avl r)" |
449 h = max (height l) (height r) + 1 \<and> avl l \<and> avl r)" |
449 (* |
450 (* |
450 code_pred [inductify] avl . |
451 code_pred [inductify] avl . |
451 thm avl.equation |
452 thm avl.equation |
452 *) |
453 *) |
453 code_pred [inductify, rpred] avl . |
454 (*code_pred [inductify, rpred] avl . |
454 thm avl.rpred_equation |
455 thm avl.rpred_equation |
455 values [depth_limit = 50 random] 10 "{t. avl (t::int tree)}" |
456 values [depth_limit = 50 random] 10 "{t. avl (t::int tree)}" |
456 |
457 *)(* |
457 lemma "avl t ==> t = ET" |
458 lemma "avl t ==> t = ET" |
458 quickcheck[generator=code] |
459 quickcheck[generator=code] |
459 quickcheck[generator = pred_compile] |
460 quickcheck[generator = pred_compile] |
460 oops |
461 oops |
461 |
462 *) |
462 fun set_of |
463 fun set_of |
463 where |
464 where |
464 "set_of ET = {}" |
465 "set_of ET = {}" |
465 | "set_of (MKT n l r h) = insert n (set_of l \<union> set_of r)" |
466 | "set_of (MKT n l r h) = insert n (set_of l \<union> set_of r)" |
466 |
467 |
489 |
489 |
490 section {* List functions *} |
490 section {* List functions *} |
491 |
491 |
492 code_pred [inductify] length . |
492 code_pred [inductify] length . |
493 thm size_listP.equation |
493 thm size_listP.equation |
494 |
494 (* |
495 code_pred [inductify, rpred] length . |
495 code_pred [inductify, rpred] length . |
496 thm size_listP.rpred_equation |
496 thm size_listP.rpred_equation |
497 values [depth_limit = 10 random] 20 "{xs. size_listP (xs::nat list) (5::nat)}" |
497 values [depth_limit = 10 random] 20 "{xs. size_listP (xs::nat list) (5::nat)}" |
498 |
498 *) |
499 code_pred [inductify] concat . |
499 code_pred [inductify] concat . |
500 thm concatP.equation |
500 thm concatP.equation |
501 |
501 |
502 code_pred [inductify] hd . |
502 code_pred [inductify] hd . |
503 code_pred [inductify] tl . |
503 code_pred [inductify] tl . |
546 | "w \<in> B\<^isub>1 \<Longrightarrow> a # w \<in> S\<^isub>1" |
546 | "w \<in> B\<^isub>1 \<Longrightarrow> a # w \<in> S\<^isub>1" |
547 | "w \<in> S\<^isub>1 \<Longrightarrow> a # w \<in> A\<^isub>1" |
547 | "w \<in> S\<^isub>1 \<Longrightarrow> a # w \<in> A\<^isub>1" |
548 | "w \<in> S\<^isub>1 \<Longrightarrow> b # w \<in> S\<^isub>1" |
548 | "w \<in> S\<^isub>1 \<Longrightarrow> b # w \<in> S\<^isub>1" |
549 | "\<lbrakk>v \<in> B\<^isub>1; v \<in> B\<^isub>1\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>1" |
549 | "\<lbrakk>v \<in> B\<^isub>1; v \<in> B\<^isub>1\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>1" |
550 |
550 |
551 code_pred [inductify, rpred] S\<^isub>1p . |
551 code_pred [inductify] S\<^isub>1p . |
552 |
552 |
553 thm S\<^isub>1p.equation |
553 thm S\<^isub>1p.equation |
554 thm S\<^isub>1p.rpred_equation |
554 (*thm S\<^isub>1p.rpred_equation*) |
555 |
555 |
556 values [depth_limit = 5 random] "{x. S\<^isub>1p x}" |
556 (*values [depth_limit = 5 random] "{x. S\<^isub>1p x}"*) |
557 |
557 |
558 inductive is_a where |
558 inductive is_a where |
559 "is_a a" |
559 "is_a a" |
560 |
560 |
561 inductive is_b where |
561 inductive is_b where |
566 code_pred [rpred] is_a . |
566 code_pred [rpred] is_a . |
567 |
567 |
568 values [depth_limit=5 random] "{x. is_a x}" |
568 values [depth_limit=5 random] "{x. is_a x}" |
569 code_pred [rpred] is_b . |
569 code_pred [rpred] is_b . |
570 |
570 |
571 code_pred [rpred] filterP . |
571 (*code_pred [rpred] filterP .*) |
572 values [depth_limit=5 random] "{x. filterP is_a [a, b] x}" |
572 (*values [depth_limit=5 random] "{x. filterP is_a [a, b] x}" |
573 values [depth_limit=3 random] "{x. filterP is_b [a, b] x}" |
573 values [depth_limit=3 random] "{x. filterP is_b [a, b] x}" |
574 |
574 *) |
|
575 (* |
575 lemma "w \<in> S\<^isub>1 \<Longrightarrow> length (filter (\<lambda>x. x = a) w) = 1" |
576 lemma "w \<in> S\<^isub>1 \<Longrightarrow> length (filter (\<lambda>x. x = a) w) = 1" |
576 quickcheck[generator=pred_compile, size=10] |
577 quickcheck[generator=pred_compile, size=10] |
577 oops |
578 oops |
578 |
579 *) |
579 inductive test_lemma where |
580 inductive test_lemma where |
580 "S\<^isub>1p w ==> filterP is_a w r1 ==> size_listP r1 r2 ==> filterP is_b w r3 ==> size_listP r3 r4 ==> r2 \<noteq> r4 ==> test_lemma w" |
581 "S\<^isub>1p w ==> filterP is_a w r1 ==> size_listP r1 r2 ==> filterP is_b w r3 ==> size_listP r3 r4 ==> r2 \<noteq> r4 ==> test_lemma w" |
581 |
582 (* |
582 code_pred [rpred] test_lemma . |
583 code_pred [rpred] test_lemma . |
583 |
584 *) |
|
585 (* |
584 definition test_lemma' where |
586 definition test_lemma' where |
585 "test_lemma' w == (w \<in> S\<^isub>1 \<and> (\<not> length [x <- w. x = a] = length [x <- w. x = b]))" |
587 "test_lemma' w == (w \<in> S\<^isub>1 \<and> (\<not> length [x <- w. x = a] = length [x <- w. x = b]))" |
586 |
588 |
587 code_pred [inductify, rpred] test_lemma' . |
589 code_pred [inductify, rpred] test_lemma' . |
588 thm test_lemma'.rpred_equation |
590 thm test_lemma'.rpred_equation |
|
591 *) |
589 (*thm test_lemma'.rpred_equation*) |
592 (*thm test_lemma'.rpred_equation*) |
590 (* |
593 (* |
591 values [depth_limit=3 random] "{x. S\<^isub>1 x}" |
594 values [depth_limit=3 random] "{x. S\<^isub>1 x}" |
592 *) |
595 *) |
593 code_pred [depth_limited] is_b . |
596 code_pred [depth_limited] is_b . |
|
597 |
594 code_pred [inductify, depth_limited] filter . |
598 code_pred [inductify, depth_limited] filter . |
595 thm filterP.intros |
599 |
|
600 thm filterP.intros |
596 thm filterP.equation |
601 thm filterP.equation |
597 |
602 |
598 values [depth_limit=3] "{x. filterP is_b [a, b] x}" |
603 values [depth_limit=3] "{x. filterP is_b [a, b] x}" |
599 find_theorems "test_lemma'_hoaux" |
604 find_theorems "test_lemma'_hoaux" |
600 code_pred [depth_limited] test_lemma'_hoaux . |
605 code_pred [depth_limited] test_lemma'_hoaux . |