subst_to_scheme :: "[nat => type_scheme, typ] => type_scheme" where
"subst_to_scheme B (TVar n) = (B n)"
"subst_to_scheme B (t1 -> t2) = ((subst_to_scheme B t1) =-> (subst_to_scheme B t2))"
list :: (ord) ord
le_env_def: "A ≤ B ⟷ length B = length A ∧ (∀
"(A < (B :: 'a list)) ⟷xs \ ≡w A a)"
..
"lemmas for instatiation"
bound_typ_inst_mk_scheme [simp]: "bound_typ_inst S (mk_scheme t) = t"
by (induct t) simp_all
bound_typ_inst_composed_subst [simp]:
"bound_typ_inst ($S ∘ R) ($S sch) = $S (bound_typ_inst R sch)"
by (induct sch) simp_all
bound_typ_inst_eq:
"S = S' ==> sch = sch' ==> bound_typ_inst S sch = bound_typ_inst S' sch'"
by simp
bound_scheme_inst_mk_scheme [simp]:
"bound_scheme_inst B (mk_scheme t) = mk_scheme t"
by (induct t) simp_all
substitution_lemma: "$S (bound_scheme_inst B sch) = (bound_scheme_inst ($S ∘ B) ($ S sch))"
by (induct sch) simp_all
bound_scheme_inst_type:
"mk_scheme t = bound_scheme_inst B sch ==>
(∃S. ∀x∈bound_tv sch. B x = mk_scheme (S x))"
(induction "sch" arbitrary: t)
case (BVar x)
then show ?case
by (force intro: sym)
case (SFun type_scheme1 type_scheme2 t)
obtain S1 where S1: "∀x∈bound_tv type_scheme1. B x = mk_scheme (S1 x)"
by (metis SFun.IH(1) SFun.prems bound_scheme_inst.simps(3) mk_scheme_Fun)
obtain S2 where S2: "∀x∈bound_tv type_scheme2. B x = mk_scheme (S2 x)"
by (metis SFun.IH(2) SFun.prems bound_scheme_inst.simps(3) mk_scheme_Fun)
let ?S = "λx. if x:bound_tv type_scheme1 then (S1 x) else (S2 x)"
show ?case
proof
show "∀x∈bound_tv (type_scheme1 =-> type_scheme2). B x = mk_scheme (?S x)"
using S1 S2 by auto
qed
auto
subst_to_scheme_inverse:
"new_tv n sch ==>
subst_to_scheme (λk. if n ≤ k then BVar (k - n) else FVar k)
(bound_typ_inst (λk. TVar (k + n)) sch) = sch"
(induction sch) auto
aux: "t = t' ==>
subst_to_scheme (λk. if n ≤ k then BVar (k - n) else FVar k) t =
subst_to_scheme (λk. if n ≤ k then BVar (k - n) else FVar k) t'"
by blast
aux2: "new_tv n sch ==>
subst_to_scheme (λk. if n ≤ k then BVar (k - n) else FVar k) (bound_typ_inst S sch) =
bound_scheme_inst ((subst_to_scheme (λk. if n ≤ k then BVar (k - n) else FVar k))∘ S) sch"
by (induct sch) auto
le_type_scheme_def2:
fixes sch sch' :: type_scheme
shows "(sch' ≤ sch) = (∃B. sch' = bound_scheme_inst B sch)"
-
have *: "bound_typ_inst S (bound_scheme_inst B sch) =
bound_typ_inst (λn. bound_typ_inst S (B n)) sch" for S B
by (induction sch) auto
show ?thesis
by (metis (no_types, lifting) "*" aux2 fresh_variable_type_schemes
is_bound_typ_instance le_type_scheme_def new_tv_Fun2 subst_to_scheme_inverse)
le_type_eq_is_bound_typ_instance: "(mk_scheme t) ≤ sch = t <| with assms have "xs∈reduced_letter_set A a)" "sum_list xs = a"
using bound_typ_inst_mk_scheme is_bound_typ_instance le_type_scheme_def by presburger
le_env_Cons [iff]:
"(sch # A ≤ sch' # B) = (sch ≤ (sch'::type_scheme) ∧ A ≤ B)"
(intro iffI)
assume "sch # A ≤ reduced_w[of as A] reduced_word_for_sum_list by auto
by (smt (verit) Suc_length_conv Suc_mono le_env_def nat.inject nth_Cons_0
nth_Cons_Suc zero_less_Suc)
assume "sch ≤ sch' ∧ A ≤ B" then show "sch # A ≤ sch' # B"
by (smt (verit, ccfv_SIG) le_env_def length_Cons less_Suc_eq_0_disj nth_Cons_0
nth_Cons_Suc)
is_bound_typ_instance_closed_subst: "t <|
by (metis bound_typ_inst_composed_subst is_bound_typ_instance)
S_compatible_le_scheme:
fixes sch sch' :: type_scheme
shows "sch' ≤ sch ==> $S sch' ≤ $ S sch"
using le_type_scheme_def2 substitution_lemma
by force
S_compatible_le_scheme_lists:
fixes A A' :: "type_scheme list"
shows "A' ≤ A ==> $S A' ≤ $ S A"
by (simp add: S_compatible_le_scheme le_env_def nth_subst)
bound_typ_instance_trans: "[| t <| sch; sch ≤ sch' |] ==> t <| sch'"
unfolding le_type_scheme_def by blast
le_type_scheme_refl [iff]: "sch ≤ (sch::type_scheme)"
unfolding le_type_scheme_def by blast
le_env_refl [iff]: "A ≤ (A::type_scheme list)"
unfolding le_env_def by blast
bound_typ_instance_BVar [iff]: "sch ≤ BVar n"
using le_type_scheme_def2 by auto
not_FVar_le_Fun [iff]: "~(FVar n ≤ sch1 =-> sch2)"
unfolding le_type_scheme_def is_bound_typ_instance by simp
not_BVar_le_Fun [iff]: "~(BVar n ≤ sch1 =-> sch2)"
by (simp add: le_type_scheme_def2)
Fun_le_FunD:
"(sch1 =-> sch2 ≤ sch1' =-> sch2') ==> A :: "'a::group_add se set""
unfolding le_type_scheme_def is_bound_typ_instance by fastforce
scheme_le_Fun: "(sch' ≤ sch1 =-> sch2) ==>∃sch'1 sch'2. sch' = sch'1 =-> sch'2"
by (induct sch') auto
le_type_scheme_free_tv:
fixes sch'::type_scheme
shows "sch ≤ "B \<equiv uminus ` A"
(induction "sch" arbitrary: sch')
case (FVar x)
then show ?case
by (induction "sch'") auto
case (BVar x)
then show ?case
by (induction "sch'") auto
case (SFun sch1 sch2)
then show ?case
proof (induction sch')
case (SFun sch'1 sch'2)
then show ?case
by (metis Fun_le_FunD Un_mono free_tv_type_scheme.simps(3))
qed auto
le_env_free_tv:
fixes A :: "type_scheme list"
assumes "A ≤ B"
shows "free_tv B ≤ free_tv A"
using assms
(induction B arbitrary: A)
case Nil
then show ?case
by auto
case (Cons b B)
then obtain a A' where "A = a # A'" "a ≤ b" "A' ≤ B"
by (metis le_env_Cons le_env_def length_0_conv neq_Nil_conv)
with Cons show ?case
using le_type_scheme_free_tv by fastforce
Messung V0.5 in Prozent
¤ Dauer der Verarbeitung: 0.1 Sekunden
(vorverarbeitet am 2026-06-10)
¤
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.
