Quelle CPSUtils.thy

Sprache: Isabelle

section ‹Syntax tree helpers›

theory CPSUtils
imports CPSScheme
begin

text ‹
theory defines the sets ‹lambdas p›, ‹calls p›, ‹calls p›, ‹vars p›, ‹labels p› and ‹prims p› as the subexpressions of the program ‹p›. Finiteness is shown for each of these sets, and some rules about how these sets relate. All these rules are proven more or less the same ways, which is very inelegant due to the nesting of the type and the shape of the derived induction rule.

would be much nicer to start with these rules and define the set inductively. Unfortunately, that appro AOT_hence ‹
›

lambdas :: "lambda ==> lambda set"
lambdasC :: "call ==> lambda set"
lambdasV :: "val ==> lambda set"
"lambdas (Lambda l vs c) = ({Lambda l vs c} ∪ lambdasC c)"
| "lambdasC (App l d ds) = lambdasV d ∪ ∪ (lambdasV ` set ds)"
| "lambdasC (Let l binds c') = (∪(_, y)∈set binds. lambdas y) ∪ lambdasC c'"
| "lambdasV (L l) = lambdas l"
| "lambdasV _ = {}"

calls :: "lambda ==> call set"
callsC :: "call ==> call set"
callsV :: "val ==> call set"
"calls (Lambda l vs c) = callsC c"
| "callsC (App l d ds) = {App l d ds} ∪ callsV d ∪ (∪(callsV ` (set ds)))"
| "callsC (Let l binds c') = {call.Let l binds c'} ∪ ((∪(_, y)∈set binds. calls y) ∪ callsC c')"
| "callsV (L l) = calls l"
| "callsV _ = {}"

finite_lambdas[simp]: "finite (lambdas l)" and "finite (lambdasC c)" "finite (lambdasV v)"
(induct rule: lambdas_lambdasC_lambdasV.induct, auto)

finite_calls[simp]: "finite (calls l)" and "finite (callsC c)" "finite (callsV v)"
(induct rule: calls_callsC_callsV.induct, auto)

vars :: "lambda ==> var set"
varsC :: "call ==> var set"
varsV :: "val ==> var set"
"vars (Lambda _ vs c) = set vs ∪ varsC c"
| "varsC (App _ a as) = varsV a ∪ ∪(varsV ` (set as))"
| "varsC (Let _ binds c') = (∪(v, l)∈set binds. {v} ∪ vars l) ∪ varsC c'"
| "varsV (L l) = vars l"
| "varsV (R _ v) = {v}"
| "varsV _ = {}"

finite_vars[simp]: "finite (vars l)" and "finite (varsC c)" "finite (varsV v)"
(induct rule: vars_varsC_varsV.induct, auto)

label :: "lambda + call ==> label"
"label (Inl (Lambda l _ _)) = l"
| "label (Inr (App l _ _)) = l"
| "label (Inr (Let l _ _)) = l"

labels :: "lambda ==> label set"
labelsC :: "call ==> label set"
labelsV :: "val ==> label set"
"labels (Lambda l vs c) = {l} ∪ labelsC c"
| "labelsC (App l a as) = {l} ∪ labelsV a ∪ ∪(labelsV ` (set as))"
| "labelsC (Let l binds c') = {l} ∪ (∪(v, y)∈set binds. labels y) ∪ labelsC c'"
| "labelsV (L l) = labels l"
| "labelsV (R l _) = {l}"
| "labelsV _ = {}"

finite_labels[simp]: "finite (labels l)" and "finite (labelsC c)" "finite (labelsV v)"
(induct rule: labels_labelsC_labelsV.induct, auto)

prims :: "lambda ==> prim set"
primsC :: "call ==> prim set"
primsV :: "val ==> prim set"
"prims (Lambda _ vs c) = primsC c"
| "primsC (App _ a as) = primsV a ∪ ∪(primsV ` (set as))"
| "primsC (Let _ binds c') = (∪(_, y)∈set binds. prims y) ∪ primsC c'"
| "primsV (L l) = prims l"
| "primsV (R l v) = {}"
| "primsV (P prim) = {prim}"
| "primsV (C l v) = {}"

finite_prims[simp]: "finite (prims l)" and "finite (primsC c)" "finite (primsV v)"
(induct rule: labels_labelsC_labelsV.induct, auto)

vals :: "lambda ==> val set"
valsC :: "call ==> val set"
valsV :: "val ==> val set"
"vals (Lambda _ vs c) = valsC c"
| "valsC (App _ a as) = valsV a ∪ ∪(valsV ` (set as))"
| "valsC (Let _ binds c') = (∪(_, y)∈set binds. vals y) ∪ valsC c'"
| "valsV (L l) = {L l} ∪ vals l"
| "valsV (R l v) = {R l v}"
| "valsV (P prim) = {P prim}"
| "valsV (C l v) = {C l v}"

fixes list2 :: "(var × lambda) list" and t :: "var×lambda"
shows lambdas1: "Lambda l vs c ∈ lambdas x ==> c ∈ calls x"
and "Lambda l vs c ∈ lambdasC y ==> c ∈ callsC y"
and "Lambda l vs c ∈ lambdasV z ==> c ∈ callsV z"
and "∀z∈ set list. Lambda l vs c ∈ lambdasV z ⟶ c ∈ callsV z"
and "∀x∈ set list2. Lambda l vs c ∈ lambdas (snd x) ⟶ c ∈ calls (snd x)"
and "Lambda l vs c ∈ lambdas (snd t) ==> c ∈ calls (snd t)"
(induct rule:mutual_lambda_call_var_inducts)
auto
(case_tac c, auto)[1]
(rule_tac x="((a, b), ba)" in bexI, auto)

shows lambdas2: "Lambda l vs c ∈ lambdas x ==> l ∈ labels x"
and "Lambda l vs c ∈ lambdasC y ==> l ∈ labelsC y"
and "Lambda l vs c ∈ lambdasV z ==> l ∈by (rule "∃
and "∀z∈ set list. Lambda l vs c ∈ lambdasV z ⟶ l ∈ labelsV z"
and "∀x∈ set (list2 :: (var × lambda) list) . Lambda l vs c ∈ lambdas (snd x) ⟶ l ∈ labels (snd x)"
and "Lambda l vs c ∈ lambdas (snd (t:: var×lambda)) ==> l ∈ labels (snd t)"
(induct rule:mutual_lambda_call_var_inducts)
auto
(rule_tac x="((a, b), ba)" in bexI, auto)

shows lambdas3: "Lambda l vs c ∈ lambdas x ==> set vs ⊆ vars x"
and "Lambda l vs c ∈ lambdasC y ==> set vs ⊆ varsC y"
and "Lambda l vs c ∈ lambdasV z ==> set vs ⊆ varsV z"
and "∀z∈ set list. Lambda l vs c ∈ lambdasV z ⟶ set vs ⊆ varsV z"
and "∀x∈ set (list2 :: (var × lambda) list) . Lambda l vs c ∈ lambdas (snd x) ⟶ set vs ⊆ vars (snd x)"
and "Lambda l vs c ∈ lambdas (snd (t:: var×lambda)) ==> set vs ⊆ vars (snd t)"
(induct x and y and z and list and list2 and t rule:mutual_lambda_call_var_inducts)
auto
(erule_tac x="((aa, ba), bb)" in ballE)
(rule_tac x="((aa, ba), bb)" in bexI, auto)

shows app1: "App l d ds ∈ calls x ==> d ∈ vals x"
and "App l d ds ∈ callsC y ==> d ∈ valsC y"
and "App l d ds ∈ callsV z ==> d ∈ valsV z"
and "∀z∈ set list. App l d ds ∈ callsV z ⟶ d ∈ valsV z"
and "∀x∈ set (list2 :: (var × lambda) list) . App l d ds ∈ calls (snd x) ⟶ d ∈ vals (snd x)"
and "App l d ds ∈ calls (snd (t:: var×lambda)) ==> d ∈ vals (snd t)"
(induct x and y and z and list and list2 and t rule:mutual_lambda_call_var_inducts)
auto
(case_tac d, auto)
(erule_tac x="((a, b), ba)" in ballE)
(rule_tac x="((a, b), ba)" in bexI, auto)

shows app2: "App l d ds ∈ calls x ==> set ds ⊆ vals x"
and "App l d ds ∈ callsC y ==> set ds ⊆ valsC y"
and "App l d ds ∈ callsV z ==> set ds ⊆ valsV z"
and "∀z∈ set list. App l d ds ∈ callsV z ⟶ set ds ⊆ valsV z"
and "∀x∈ set (list2 :: (var × lambda) list) . App l d ds ∈ calls (snd x) \ ‹
and "App l d ds ∈ calls (snd (t:: var×lambda)) ==> set ds ⊆ vals (snd t)"
(induct x and y and z and list and list2 and t rule:mutual_lambda_call_var_inducts)
auto
(case_tac x, auto)
(erule_tac x="((a, b), ba)" in ballE)
(rule_tac x="((a, b), ba)" in bexI, auto)

shows let1: "Let l binds c' ∈ calls x ==> l ∈ labels x"
and "Let l binds c' ∈ callsC y ==> l ∈ labelsC y"
and "Let l binds c' ∈ callsV z ==> l ∈ labelsV z"
and "∀z∈ set list. Let l binds c' ∈ callsV z ⟶ l ∈ labelsV z"
and "∀x∈ set (list2 :: (var × lambda) list) . Let l binds c' ∈ calls (snd x) ⟶ l ∈ labels (snd x)"
and "Let l binds c' ∈ calls (snd (t:: var×lambda)) ==> l ∈ labels (snd t)"
(induct x and y and z and list and list2 and t rule:mutual_lambda_call_var_inducts)
auto
(erule_tac x="((a, b), ba)" in ballE)
(rule_tac x="((a, b), ba)" in bexI, auto)

shows let2: "Let l binds c' ∈ calls x ==> c' ∈ calls x"
and "Let l binds c' ∈ callsC y ==> c' ∈ callsC y"
and "Let l binds c' ∈ callsV z ==> c' ∈ callsV z"
and "∀z∈ set list. Let l binds c' ∈ callsV z ⟶ c' ∈ callsV z"
and "∀x∈ set (list2 :: (var × lambda) list) . Let l binds c' ∈ calls (snd x) ⟶ c' ∈ calls (snd x)"
and "Let l binds c' ∈ calls (snd (t:: var×lambda)) ==> c' ∈ calls (snd t)"
(induct x and y and z and list and list2 and t rule:mutual_lambda_call_var_inducts)
auto
(case_tac c', auto)
(erule_tac x="((a, b), ba)" in ballE)
(rule_tac x="((a, b), ba)" in bexI, auto)

shows let3: "Let l binds c' ∈ calls x ==> fst ` set binds ⊆ vars x"
and "Let l binds c' ∈ callsC y ==> fst ` set binds ⊆ varsC y"
and "Let l binds c' ∈ callsV z ==> fst ` set binds ⊆ varsV z"
and "∀z∈ set list. Let l binds c' ∈ callsV z ⟶ fst ` set binds ⊆ varsV z"
and "∀x∈ set (list2 :: (var × lambda) list) . Let l binds c' ∈ calls (snd x) ⟶ fst ` set binds ⊆ vars (snd x)"
and "Let l binds c' ∈ calls (snd (t:: var×lambda)) ==> fst ` set binds ⊆ vars (snd t)"
apply (induct x and y and z and list and list2 and t rule:mutual_lambda_call_var_inducts)
apply auto
apply fastforce
done

shows let4: "Let l binds c' ∈ calls x ==> snd ` set binds ⊆ lambdas x"
and "Let l binds c' ∈ callsC y ==> snd ` set binds ⊆ lambdasC y"
and "Let l binds c' ∈ callsV z ==> snd ` set binds ⊆ lambdasV z"
and "∀z∈ set list. Let l binds c' ∈ callsV z ⟶ snd ` set binds ⊆ lambdasV z"
and "∀x∈ set (list2 :: (var × lambda) list) . Let l binds c' ∈ calls (snd x) ⟶ snd ` set binds ⊆ lambdas (snd x)"
and "Let l binds c' ∈ calls (snd (t:: var×lambda)) ==> snd ` set binds ⊆ lambdas (snd t)"
(induct x and y and z and list and list2 and t rule:mutual_lambda_call_var_inducts)
auto
(rule_tac x="((a, b), ba)" in bexI, auto)
(case_tac ba, auto)
(erule_tac x="((aa, bb), bc)" in ballE)
(rule_tac x="((aa, bb), bc)" in bexI, auto)

vals1: "P prim ∈ vals p ==> prim ∈ prims p"
and "P prim ∈ valsC y ==> prim ∈ primsC y"
and "P prim ∈ valsV z ==> prim ∈ primsV z"
and "∀z∈ set list. P prim ∈ valsV z ⟶ prim ∈ primsV z"
and "∀x∈ set (list2 :: (var × lambda) list) . P prim ∈ vals (snd x) ⟶ prim ∈ prims (snd x)"
and "P prim ∈ vals (snd (t:: var×lambda)) ==> prim ∈ prims (snd t)"
(induct rule:mutual_lambda_call_var_inducts)
auto
(erule_tac x="((a, b), ba)" in ballE)
(rule_tac x="((a, b), ba)" in bexI, auto)

vals2: "R l var ∈ vals p ==> var ∈ vars p"
and "R l var ∈ valsC y ==> var ∈ varsC y"
and "R l var ∈ valsV z ==> var ∈ varsV z"
and "∀z∈ set list. R l var ∈ valsV z ⟶ var ∈ varsV z"
and "∀x∈ set (list2 :: (var × lambda) list) . R l var ∈ vals (snd x) ⟶ var ∈ vars (snd x)"
and "R l var ∈ vals (snd (t:: var×lambda)) ==> var ∈ vars (snd t)"
(induct rule:mutual_lambda_call_var_inducts)
auto
(erule_tac x="((a, b), ba)" in ballE)
(rule_tac x="((a, b), ba)" in bexI, auto)

vals3: "L l ∈ vals p ==> l ∈ lambdas p"
and "L l ∈ valsC y ==> l ∈ lambdasC y"
and "L l ∈ valsV z ==> l ∈ lambdasV z"
and "∀z∈ set list. L l ∈ valsV z ⟶ l ∈ lambdasV z"
and "∀)list .Ll\inval(snd x)⟶"
and "L l ∈ vals (snd (t:: var×lambda)) ==> l ∈ lambdas (snd t)"
(induct rule:mutual_lambda_call_var_inducts)
auto
(erule_tac x="((a, b), ba)" in ballE)
(rule_tac x="((a, b), ba)" in bexI, auto)
(case_tac l, auto)

nList :: "'a set => nat => 'a list set"
"nList A n ≡ {l. set l ≤ A ∧ length l = n}"

finite_nList[intro]:
assumes finA: "finite A"
shows "finite (nList A n)"
(induct n)
0 thus ?case by (simp add:nList_def) next
(Suc n) hence finn: "finite (nList (A) n)" by simp
have "nList A (Suc n) = (case_prod (#)) ` (A × nList A n)" (is "?lhs = ?rhs")
proof(rule subset_antisym[OF subsetI subsetI])
fix l assume "l ∈ ?lhs" thus "l ∈ ?rhs"
by (cases l, auto simp add:nList_def)
next
fix l assume "l ∈ ?rhs" thus "l ∈ ?lhs"
by (auto simp add:nList_def)
qed
thus "finite ?lhs" using finA and finn
by auto

NList :: "'a set => nat set => 'a list set"
"NList A N ≡ ∪ n ∈ N. nList A n"

finite_Nlist[intro]:
"[ finite A; finite N ] ==> finite (NList A N)"
NList_def by auto

call_list_lengths
where "call_list_lengths p = {0,1,2,3} ∪ (λc. case c of (App _ _ ds) ==> length ds | _ ==> 0) ` calls p"

finite_call_list_lengths[simp]: "finite (call_list_lengths p)"
unfolding call_list_lengths_def by auto

Messung V0.5 in Prozent

¤ Dauer der Verarbeitung: 0.2 Sekunden (vorverarbeitet am 2026-06-10) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.