src/HOL/ex/Predicate_Compile_ex.thy
changeset 33140 83951822bfd0
parent 33139 9c01ee6f8ee9
child 33141 89b23fad5e02
equal deleted inserted replaced
33139:9c01ee6f8ee9 33140:83951822bfd0
     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 
   468 where
   469 where
   469 "is_ord ET = True"
   470 "is_ord ET = True"
   470 | "is_ord (MKT n l r h) =
   471 | "is_ord (MKT n l r h) =
   471  ((\<forall>n' \<in> set_of l. n' < n) \<and> (\<forall>n' \<in> set_of r. n < n') \<and> is_ord l \<and> is_ord r)"
   472  ((\<forall>n' \<in> set_of l. n' < n) \<and> (\<forall>n' \<in> set_of r. n < n') \<and> is_ord l \<and> is_ord r)"
   472 
   473 
   473 code_pred [inductify] set_of .
   474 code_pred (mode: [1], [1, 2]) [inductify] set_of .
   474 thm set_of.equation
   475 thm set_of.equation
   475 
   476 
   476 text {* expected mode: [1], [1, 2] *}
       
   477 (* FIXME *)
   477 (* FIXME *)
   478 (*
   478 (*
   479 code_pred (inductify_all) is_ord .
   479 code_pred (inductify_all) is_ord .
   480 thm is_ord.equation
   480 thm is_ord.equation
   481 *)
   481 *)
   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 .