author | wenzelm |
Thu, 14 Jun 2007 23:04:39 +0200 | |
changeset 23394 | 474ff28210c0 |
parent 23374 | a2f492c599e0 |
child 23416 | b73a6b72f706 |
permissions | -rw-r--r-- |
22371 | 1 |
(* Title: HOL/Library/SCT_Implementation.thy |
2 |
ID: $Id$ |
|
3 |
Author: Alexander Krauss, TU Muenchen |
|
4 |
*) |
|
5 |
||
23374 | 6 |
header "" (* FIXME proper header *) |
22665 | 7 |
|
22359
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
8 |
theory SCT_Implementation |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
9 |
imports ExecutableSet SCT_Definition |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
10 |
begin |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
11 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
12 |
fun edges_match :: "('n \<times> 'e \<times> 'n) \<times> ('n \<times> 'e \<times> 'n) \<Rightarrow> bool" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
13 |
where |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
14 |
"edges_match ((n, e, m), (n',e',m')) = (m = n')" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
15 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
16 |
fun connect_edges :: |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
17 |
"('n \<times> ('e::times) \<times> 'n) \<times> ('n \<times> 'e \<times> 'n) |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
18 |
\<Rightarrow> ('n \<times> 'e \<times> 'n)" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
19 |
where |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
20 |
"connect_edges ((n,e,m), (n', e', m')) = (n, e * e', m')" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
21 |
|
22744
5cbe966d67a2
Isar definitions are now added explicitly to code theorem table
haftmann
parents:
22665
diff
changeset
|
22 |
lemma grcomp_code [code]: |
22359
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
23 |
"grcomp (Graph G) (Graph H) = Graph (connect_edges ` { x \<in> G\<times>H. edges_match x })" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
24 |
by (rule graph_ext) (auto simp:graph_mult_def has_edge_def image_def) |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
25 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
26 |
definition test_SCT :: "acg \<Rightarrow> bool" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
27 |
where |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
28 |
"test_SCT \<A> = |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
29 |
(let \<T> = mk_tcl \<A> \<A> |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
30 |
in (\<T> \<noteq> 0 \<and> |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
31 |
(\<forall>(n,G,m)\<in>dest_graph \<T>. |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
32 |
n \<noteq> m \<or> G * G \<noteq> G \<or> |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
33 |
(\<exists>(p::nat,e,q)\<in>dest_graph G. p = q \<and> e = LESS))))" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
34 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
35 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
36 |
lemma SCT'_exec: |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
37 |
assumes a: "test_SCT \<A>" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
38 |
shows "SCT' \<A>" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
39 |
proof - |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
40 |
from mk_tcl_correctness2 a |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
41 |
have "mk_tcl \<A> \<A> = tcl \<A>" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
42 |
unfolding test_SCT_def Let_def by auto |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
43 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
44 |
with a |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
45 |
show ?thesis |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
46 |
unfolding SCT'_def no_bad_graphs_def test_SCT_def Let_def has_edge_def |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
47 |
by auto |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
48 |
qed |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
49 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
50 |
code_modulename SML |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
51 |
Implementation Graphs |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
52 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
53 |
lemma [code func]: |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
54 |
"(G\<Colon>('a\<Colon>eq, 'b\<Colon>eq) graph) \<le> H \<longleftrightarrow> dest_graph G \<subseteq> dest_graph H" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
55 |
"(G\<Colon>('a\<Colon>eq, 'b\<Colon>eq) graph) < H \<longleftrightarrow> dest_graph G \<subset> dest_graph H" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
56 |
unfolding graph_leq_def graph_less_def by rule+ |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
57 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
58 |
lemma [code func]: |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
59 |
"(G\<Colon>('a\<Colon>eq, 'b\<Colon>eq) graph) + H = Graph (dest_graph G \<union> dest_graph H)" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
60 |
unfolding graph_plus_def .. |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
61 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
62 |
lemma [code func]: |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
63 |
"(G\<Colon>('a\<Colon>eq, 'b\<Colon>{eq, times}) graph) * H = grcomp G H" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
64 |
unfolding graph_mult_def .. |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
65 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
66 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
67 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
68 |
lemma SCT'_empty: "SCT' (Graph {})" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
69 |
unfolding SCT'_def no_bad_graphs_def graph_zero_def[symmetric] |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
70 |
tcl_zero |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
71 |
by (simp add:in_grzero) |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
72 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
73 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
74 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
75 |
subsection {* Witness checking *} |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
76 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
77 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
78 |
definition test_SCT_witness :: "acg \<Rightarrow> acg \<Rightarrow> bool" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
79 |
where |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
80 |
"test_SCT_witness A T = |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
81 |
(A \<le> T \<and> A * T \<le> T \<and> |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
82 |
(\<forall>(n,G,m)\<in>dest_graph T. |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
83 |
n \<noteq> m \<or> G * G \<noteq> G \<or> |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
84 |
(\<exists>(p::nat,e,q)\<in>dest_graph G. p = q \<and> e = LESS)))" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
85 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
86 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
87 |
lemma no_bad_graphs_ucl: |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
88 |
assumes "A \<le> B" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
89 |
assumes "no_bad_graphs B" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
90 |
shows "no_bad_graphs A" |
23394 | 91 |
using assms |
92 |
unfolding no_bad_graphs_def has_edge_def graph_leq_def |
|
93 |
by blast |
|
22359
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
94 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
95 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
96 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
97 |
lemma SCT'_witness: |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
98 |
assumes a: "test_SCT_witness A T" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
99 |
shows "SCT' A" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
100 |
proof - |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
101 |
from a have "A \<le> T" "A * T \<le> T" by (auto simp:test_SCT_witness_def) |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
102 |
hence "A + A * T \<le> T" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
103 |
by (subst add_idem[of T, symmetric], rule add_mono) |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
104 |
with star3' have "tcl A \<le> T" unfolding tcl_def . |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
105 |
moreover |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
106 |
from a have "no_bad_graphs T" |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
107 |
unfolding no_bad_graphs_def test_SCT_witness_def has_edge_def |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
108 |
by auto |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
109 |
ultimately |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
110 |
show ?thesis |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
111 |
unfolding SCT'_def |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
112 |
by (rule no_bad_graphs_ucl) |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
113 |
qed |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
114 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
115 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
116 |
code_modulename SML |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
117 |
Graphs SCT |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
118 |
Kleene_Algebras SCT |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
119 |
SCT_Implementation SCT |
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
120 |
|
22845 | 121 |
code_gen test_SCT in SML |
22359
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
122 |
|
94a794672c8b
Added formalization of size-change principle (experimental).
krauss
parents:
diff
changeset
|
123 |
end |