src/HOL/Predicate_Compile_Examples/Context_Free_Grammar_Example.thy
changeset 40924 a9be7f26b4e6
parent 40301 bf39a257b3d3
child 41956 c15ef1b85035
equal deleted inserted replaced
40923:be80c93ac0a2 40924:a9be7f26b4e6
    31 | "w \<in> S\<^isub>1 \<Longrightarrow> b # w \<in> S\<^isub>1"
    31 | "w \<in> S\<^isub>1 \<Longrightarrow> b # w \<in> S\<^isub>1"
    32 | "\<lbrakk>v \<in> B\<^isub>1; v \<in> B\<^isub>1\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>1"
    32 | "\<lbrakk>v \<in> B\<^isub>1; v \<in> B\<^isub>1\<rbrakk> \<Longrightarrow> a # v @ w \<in> B\<^isub>1"
    33 
    33 
    34 lemma
    34 lemma
    35   "w \<in> S\<^isub>1 \<Longrightarrow> w = []"
    35   "w \<in> S\<^isub>1 \<Longrightarrow> w = []"
    36 quickcheck[generator = prolog, iterations=1, expect = counterexample]
    36 quickcheck[tester = prolog, iterations=1, expect = counterexample]
    37 oops
    37 oops
    38 
    38 
    39 definition "filter_a = filter (\<lambda>x. x = a)"
    39 definition "filter_a = filter (\<lambda>x. x = a)"
    40 
    40 
    41 lemma [code_pred_def]: "filter_a [] = []"
    41 lemma [code_pred_def]: "filter_a [] = []"
    65   manual_reorder = [(("quickcheck", 1), [0,2,1,4,3,5])]}) *}
    65   manual_reorder = [(("quickcheck", 1), [0,2,1,4,3,5])]}) *}
    66 
    66 
    67 
    67 
    68 theorem S\<^isub>1_sound:
    68 theorem S\<^isub>1_sound:
    69 "w \<in> S\<^isub>1 \<Longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
    69 "w \<in> S\<^isub>1 \<Longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
    70 quickcheck[generator = prolog, iterations=1, expect = counterexample]
    70 quickcheck[tester = prolog, iterations=1, expect = counterexample]
    71 oops
    71 oops
    72 
    72 
    73 
    73 
    74 inductive_set S\<^isub>2 and A\<^isub>2 and B\<^isub>2 where
    74 inductive_set S\<^isub>2 and A\<^isub>2 and B\<^isub>2 where
    75   "[] \<in> S\<^isub>2"
    75   "[] \<in> S\<^isub>2"
    89   manual_reorder = [(("quickcheck", 1), [0,2,1,4,3,5])]}) *}
    89   manual_reorder = [(("quickcheck", 1), [0,2,1,4,3,5])]}) *}
    90 
    90 
    91 
    91 
    92 theorem S\<^isub>2_sound:
    92 theorem S\<^isub>2_sound:
    93 "w \<in> S\<^isub>2 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
    93 "w \<in> S\<^isub>2 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
    94 quickcheck[generator=prolog, iterations=1, expect = counterexample]
    94 quickcheck[tester = prolog, iterations=1, expect = counterexample]
    95 oops
    95 oops
    96 
    96 
    97 inductive_set S\<^isub>3 and A\<^isub>3 and B\<^isub>3 where
    97 inductive_set S\<^isub>3 and A\<^isub>3 and B\<^isub>3 where
    98   "[] \<in> S\<^isub>3"
    98   "[] \<in> S\<^isub>3"
    99 | "w \<in> A\<^isub>3 \<Longrightarrow> b # w \<in> S\<^isub>3"
    99 | "w \<in> A\<^isub>3 \<Longrightarrow> b # w \<in> S\<^isub>3"
   111   replacing = [(("s3", "limited_s3"), "quickcheck")],
   111   replacing = [(("s3", "limited_s3"), "quickcheck")],
   112   manual_reorder = [(("quickcheck", 1), [0,2,1,4,3,5])]}) *}
   112   manual_reorder = [(("quickcheck", 1), [0,2,1,4,3,5])]}) *}
   113 
   113 
   114 lemma S\<^isub>3_sound:
   114 lemma S\<^isub>3_sound:
   115 "w \<in> S\<^isub>3 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
   115 "w \<in> S\<^isub>3 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
   116 quickcheck[generator=prolog, iterations=1, size=1, expect = no_counterexample]
   116 quickcheck[tester = prolog, iterations=1, size=1, expect = no_counterexample]
   117 oops
   117 oops
   118 
   118 
   119 
   119 
   120 (*
   120 (*
   121 setup {* Code_Prolog.map_code_options (K
   121 setup {* Code_Prolog.map_code_options (K
   129   prolog_system = Code_Prolog.SWI_PROLOG}) *}
   129   prolog_system = Code_Prolog.SWI_PROLOG}) *}
   130 
   130 
   131 
   131 
   132 theorem S\<^isub>3_complete:
   132 theorem S\<^isub>3_complete:
   133 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>3"
   133 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>3"
   134 quickcheck[generator = prolog, size=1, iterations=1]
   134 quickcheck[tester = prolog, size=1, iterations=1]
   135 oops
   135 oops
   136 *)
   136 *)
   137 
   137 
   138 inductive_set S\<^isub>4 and A\<^isub>4 and B\<^isub>4 where
   138 inductive_set S\<^isub>4 and A\<^isub>4 and B\<^isub>4 where
   139   "[] \<in> S\<^isub>4"
   139   "[] \<in> S\<^isub>4"
   154   manual_reorder = [(("quickcheck", 1), [0,2,1,4,3,5])]}) *}
   154   manual_reorder = [(("quickcheck", 1), [0,2,1,4,3,5])]}) *}
   155 
   155 
   156 
   156 
   157 theorem S\<^isub>4_sound:
   157 theorem S\<^isub>4_sound:
   158 "w \<in> S\<^isub>4 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
   158 "w \<in> S\<^isub>4 \<longrightarrow> length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b]"
   159 quickcheck[generator = prolog, size=1, iterations=1, expect = no_counterexample]
   159 quickcheck[tester = prolog, size=1, iterations=1, expect = no_counterexample]
   160 oops
   160 oops
   161 
   161 
   162 (*
   162 (*
   163 theorem S\<^isub>4_complete:
   163 theorem S\<^isub>4_complete:
   164 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>4"
   164 "length [x \<leftarrow> w. x = a] = length [x \<leftarrow> w. x = b] \<longrightarrow> w \<in> S\<^isub>4"