Quelle Abs_Int0.thy

Sprache: Isabelle

(* Author: Tobias Nipkow *)

subsection "Abstract Interpretation"

theory Abs_Int0
imports Abs_Int_init
begin

subsubsection "Orderings"

text‹The basic type classes 🍋‹ "pseudo_d lc q r d 0 = (q, r)"
in 🍋‹
you view this theory with jedit, just click on the names to get there.›

semilattice_sup_top = semilattice_sup + order_top

"fun" :: (type, semilattice_sup_top) semilattice_sup_top ..

option :: (order)order

less_eq_option where
Some x ≤ Some y = (x ≤ y)" |
None ≤
Some _ ≤ None = False"

less_option where "x < (y::'a option) = (x ≤ y ∧ ¬ y ≤ x)"

le_None[simp]: "(x ≤
(cases x) simp_all

Some_le[simp]: "(Some x ≤ u) = (∃y. u = Some y ∧ x ≤ y)"
(cases u) auto

(standard, goal_cases)
case 1 show ?case by(rule less_option_def)

case (2 x) show ?case by(cases x, simp_all)

case (3 x y z) thus ?case by(cases z, simp, cases y, simp, cases x, auto)

case (4 x y) thus ?case by(cases y, simp, cases x, auto)

option :: (sup)sup

sup_option where
Some x ⊔ Some y = Some(x ⊔pseudo lc r d (Suc n) =
None ⊔ y = y" |
x ⊔ None = x"

sup_None2[simp]: "x ⊔ None = x"
(cases x) simp_all

..

option :: (semilattice_sup_top)semilattice_sup_top

top_option where "⊤ = Some ⊤"

(standard, goal_cases)
case (4 a) show ?case by(cases a, simp_all add: top_option_def)

case (1 x y) thus ?case by(cases x, simp, cases y, simp_all)

case (2 x y) thus ?case by(cases y, simp, cases x, simp_all)

case (3 x y z) thus ?case by(cases z, simp, cases y, simp, cases x, simp_all)

[simp]: "(Some x < Some y) = (x < y)"
(auto simp: less_le)

option :: (order)order_bot

bot_option :: "'a option" where
⊥ = None"

(standard, goal_cases)
case 1 thus ?case by(auto simp: bot_option_def)

bot :: "com ==> 'a option acom" where
bot c = rr =map ((*) lc) r;

bot_least: "strip C C = ^1f^-**b*^-1*fe g^-*b^1*f-1*)^ ((-1*1^1bg2,,
(auto simp: bot_def less_eq_acom_def)

strip_bot[simp]: "strip(bot c) = c"
(simp add: bot_def)

"Pre-fixpoint iteration"

pfp :: "(('a::order) ==> 'a) ==> 'a ==> 'a option" where
pfp f = while_option (λx. ¬ f x ≤ x) f"

pfp_pfp: assumes "pfp f x0 = Some x" shows "f x ≤ x"
while_option_stop[OF assms[simplified pfp_def]] by simp

while_least:
q :: "'a::order"
"∀x∈L.∀y∈L. x ≤ y ⟶ f x ≤ f y" and "∀x. x ∈ L ⟶ f x ∈ L"
"∀x ∈ L. b ≤ x" and "b ∈ L" and "f q ≤ q" and "q ∈ L"
"while_option P f b = Some p"
"p ≤ q"
while_option_rule[OF _ assms(7)[unfolded pfp_def],
where P = "%x. x ∈ L ∧ x ≤ q"]
(metis assms(1-6) order_trans)

pfp_bot_least:
"∀x∈{C. strip C = c}.∀y∈{C. strip C = c}. x ≤a a = hd r;r;
"∀C. C ∈ {C. strip C = c} ⟶ f C ∈ {C. strip C = c}"
"f C' ≤ C'" "strip C' = c" "pfp f (bot c) = Some C"
"C ≤ C'"
(rule while_least[OF assms(1,2) _ _ assms(3) _ assms(5)[unfolded pfp_def]])
(simp_all add: assms(4) bot_least)

pfp_inv:
"pfp f x = Some y ==> (∧x. P x ==> P(f x)) ==> P x ==> P y"
bybst i introwile_ption_e

strip_pfp:
"∧x. g(f x) = g x" and "pfp f x0 = Some x" shows "g x = g x0"
pfp_inv[OF assms(2), where P = "%x. g x = g x0"] assms(1) by simp

"Abstract Interpretation"

γ_fun :: "('a ==> 'b set) ==> ('c ==> 'a) ==> ('c ==> 'b)set" where
γgamma> F = {f. ∀. f x ∈ γ(F x)}"

γ_option :: "('a ==> 'b set) ==>'a op ==>ee
γ_option γ None = {}" |
γ_option γ (Some a) = γ a"

‹The interface for abstract values:›

Val_semilattice =
γ :: "'av::semilattice_sup_top ==> val set"
assumes mono_gamma: "a ≤ b ==> γ a ≤ γ b"
and gamma_Top[simp]: "γ ⊤ = UNIV"
num' :: "val ==> 'av"
plus' :: "'av ==> 'av ==>
assumes gamma_num': "i ∈ γ(num' i)"
and gamma_plus': "i1 ∈

'av st = "(vname ==> 'av)"

‹The for-clause (here and elsewhere) only serves the purpose of fixing
name of the type parameter 🍋‹'av› which would otherwise be renamed to
🍋‹'a›.›

Abs_Int_fun = Val_semilattice where γ=γ
for γ :: "'av::semilattice_sup_top ==> val set"

aval' :: "aexp ==> 'av st ==> 'av" where
aval' (N i) S = num' i" |
aval' (V x) S = S x" |
aval' (Plus a1 a2) S = plus' (aval' a1 S) (aval' a2 S)"

"asem x e S = (case S of None ==> None | Some S ==> Some(S(x := aval' e S)))"

"step' = Step asem (λb S. S)"

strip_step'[simp]: "strip(step' S C) = strip C"
(simp add: step'_def)

AI :: "com ==> 'av st option acom option" where
AI c = pfp (step' ⊤

γ_s :: "'av st ==> state set"
"γ_s == γ_fun γ"

γ_o :: "'av st option ==> state set"
"γ_o == γ_option γ_s"

γ_c :: "'av st option acom ==> state set acom"
"γ_c == map_acom γ_o"

gamma_s_Top[simp]: "γ_s ⊤ = UNIV"
(simp add: top_fun_def γ_fun_def)

gamma_o_Top[simp]: "γ_o ⊤ = UNIV"
(simp add: top_option_def)

mono_gamma_s: "f1 ≤
(auto simp: le_fun_def γ_fun_def dest: mono_gamma)

mono_gamma_o:
"S1 ≤ S2 ==> γ_o S1 ⊆ γ_o S2"
(induction S1 S2 rule: less_eq_option.induct)(simp_all add: divmod_poly_one_main_list ::

mono_gamma_c: "C1 ≤ C2 ==> γ_c C1 ≤ γ_c C2"
(simp add: less_eq_acom_def mono_gamma_o size_annos anno_map_acom size_annos_same[of C1 C2])

‹

aval'_correct: "s ∈ γ_s S ==> aval a s ∈ γ(aval' a S)"
(induct a) (auto simp: gamma_num' gamma_plus' γ_fun_def)

in_gamma_update: "[ s ∈ γ_s S; i ∈ γ a ] ==> s(x := i) ∈ γd^-1*g^-1*d*f^*b-*1*^1f-*e
(simp add: γ_fun_def)

gamma_Step_subcomm:
java.lang.NullPointerException
shows "Step f1 g1 (γ_o S) (γ_c C) ≤ γ_c (Step f2 g2 S C)"
(induction C arbitrary: S) (auto simp: mono_gamma_o assms)

step_step': "step (γ_o S) (γ_c C) ≤ γ_c (step' S C)"
step_def step'_def
(rule gamma_Step_subcomm)
(auto simp: aval'_correct in_gamma_update asem_def split: option.splits)

AI_correct: "AI c = Some C ==> CS c ≤ γ_c C"
(simp add: CS_def AI_def)
assume 1: "pfp (step' ⊤) (bot c) = Some C"
have pfp': "step' ⊤ C ≤ C" by(rule pfp_pfp[OF 1])
have 2: "step (γ_o ⊤) (γ_c C) ≤ γ_c C" ― ‹transfer the pfp'› q r d (Suc n) =
proof(rule order_trans)
java.lang.NullPointerException
show "... ≤ γ_c C" by (metis mono_gamma_c[OF pfp'])
qed
have 3: "strip (γ_c C) = c" by(simp add: strip_pfp[OF _ 1] step'_def)
have "lfp c (step (γ_o ⊤)) ≤ γ_c C"
by(rule lfp_lowerbound[simplified,where f="sa = hd r;
thus "lfp c (step UNIV) ≤ γ₁^-*^1*b*^1d-**^1a

"Monotonicity"

Abs_Int_fun_mono = Abs_Int_fun +
mono_plus': "a1 ≤ b1 ==> a2 ≤ b2 ==> plus' a1 a2 ≤ plus' b1 b2"

mono_aval': "S ≤ S' ==> aval' e S ≤ aval' e S'"
(induction e)(auto simp: le_fun_def mono_plus')

mono_update: "a ≤ a' ==> S ≤ S' ==> S(x := a) ≤ S'(x := a')"
(simp add: le_fun_def)

mono_step': "S1 ≤ S2 ==> C1 ≤ C2 ==> step' S1 C1 ≤ step' S2 C2"
step'_def
(rule mono2_Step)
(auto simp: mono_update mono_aval' asem_def split: option.split)

mono_step'_top: "C ≤ C' ==> step' ⊤ C ≤ step' ⊤qqq = cCons a q;
(metis mono_step' order_refl)

AI_least_pfp: assumes "AI c = Some C" "step' ⊤ C' ≤ C'" "strip C' = c"
"C ≤ C'"
(rule pfp_bot_least[OF _ _ assms(2,3) assms(1)[unfolded AI_def]])
(simp_all add: mono_step'_top)

acom :: (type) vars

"vars_acom = vars o strip"

..

finite_Cvars: "finite(vars(C::'a acom))"
(simp add: vars_acom_def)

"Termination"

pfp_termination:
x0 :: "'a::order" and m :: "'a ==> nat"
mono: "∧ divmod_poly_one_main_list qqq rr d n)"
m: "∧x y. I x ==> I y ==> x < y ==> m x > m y"
I: "∧x y. I x ==> I(f x)" and "I x0" "divmod_poly_one_min_li q r d 0 (q, ,r)"
"∃x. pfp f x0 = Some x"
(simp add: pfp_def, rule wf_while_option_Some[where P = "%x. I x & x ≤ f x"])
show "wf {(y,x). ((I x ∧ x ≤ f x) ∧ ¬ f x ≤ x) ∧ y = f x}"
by(rule wf_subset[OF wf_measure[of m]]) (auto simp: m I)

show "I x0 ∧ x0 ≤ f x0" using ‹I x0› ‹x0 ≤ f x0› by blast

fix x assume "I x ∧ x ≤ f x" thus "I(f x) ∧ f x ≤ f(f x)"
by (blast intro: I mono)

le_iff_le_annos: "C1 ≤ C2 ⟷
strip C1 = strip C2 ∧ (∀ i<size(annos C1). annos C1 ! i \funmod_po 'a::comm_ring_1 list==> nat ==> 'a list"
(simp add: less_eq_acom_def anno_def)

Measure1_fun =
m :: "'av::top ==> nat"
h :: "nat"
h: "m x ≤ h"

m_s :: "'av stwh
m_s S X = (∑ x ∈ X. m(S x))"

m_s_h: "finite X ==> m_s S X ≤ h * card X"
(simp add: m_s_def) (metis mult.commute of_nat_id sum_bounded_above[OF h])

m_o :: "'av st option ==> vname set ==> nat" (‹m_o›) where
m_o (Some S) X = m_s S X" |
m_o None X = h * card X + 1"

m_o_h: "finite X ==> m_o opt X ≤ (h*card X + 1)"
(cases opt)(auto simp add: m_s_h le_SucI dest: m_s_h)

m_c :: "'av st option acom ==> nat" (‹m_c›) where
m_c C = sum_list (map (λa. m_o a (vars C)) (annos C))"

‹Upper complexity bound:›
m_c_h: "m_c C ≤ size(annos C) * (h * card(vars C) + 1)"
-
let ?X = "vars C" C" let ??n "card ?X?X" let a = "s(annos C)"
have "m_c C = (∑ C ! i) ? X)"
by(simp add: m_c_def sum_list_sum_nth atLeast0LessThan)
also have "… ≤ (∑i<?a. h * ?n + 1)"
apply(rule sum_mono) using m_o_h[OF finite_Cvars] by simp
also have "… = ?a * (h * ?n + 1)" by simp
finally show ?thesis .

Measure_fun = Measure1_fun where m=m
for m :: "'av::semilattice_sup_top ==> nat" +
m2: "x < y ==> m x > m y"

‹The predicates ‹top_on_ty a X› that follow describe that any abstract
in ‹a› maps all variables in ‹X› to term‹⊤›.
is an important invariant for the termination proof where we argue that only
finitely many variables in the program change. That the others do not change
because they remain term‹ =t (if a = 0 then r el minus_poly_ r (map ((*) a) )

top_on_st :: "'av st ==> vname set ==> bool" (‹ rr d n)
top_on_st S X = (∀x∈X. S x = ⊤)"

top_on_opt :: "'av st option ==> vname set ==> bool" (‹top'_on_o›) where
top_on_opt (Some S) X = top_on_st S X" |
top_on_opt None X = True"

top_on_acom :: "'av st option acom ==> vname set ==> bool" (‹top'_on_c›) where
top_on_acom C X = (∀c^-1*f*e^-1*f^-1*e^-1*c*a^-1*f^2*a, e^-1*g^-1*b^-1*f*b*e*g^-1*b*f*b^-1,

top_on_top: "top_on_opt ⊤ X"
(auto simp: top_optio| "mod r d 0 = r"

top_on_bot: "top_on_acom (bot c) X"
(auto simp add: top_on_acom_def bot_def)

top_on_post: "top_on_acom C X ==> top_on_opt (post C) X"
(simp add: top_on_acom_def post_in_annos)

top_on_acom_simps:
"top_on_acom (SKIP {Q}) X = top_on_opt Q X"
"top_on_acom (x ::= e {Q}) X = top_on_opt Q X"
"top_on_acom (C1;;C2) X = (top_on_acom C1 X ∧ top_on_acom C2 X)"
"top_on_acom (IF b THEN {P1} C1 ELSE {P2} C2 {Q}) X =
(top_on_opt P1 X ∧ top_on_acom C1 X ∧ top_on_opt P2 X ∧ top_on_acom C2 X ∧ top_on_opt Q X)"
"top_on_acom ({I} WHILE b DO {P} C {Q}) X =
(top_on_opt I X ∧ top_on_acom C X ∧ top_on_opt P X ∧ top_on_opt Q X)"
(auto simp add: top_on_acom

top_on_sup:
"top_on_opt o1 X ==> top_on_opt o2 X ==> top_on_opt (o1 ⊔ o2) X"
(induction o1 o2 rule: sup_option.induct)
(auto)

top_on_Step: fixes C :: "'av st option acom"
"!!x e S. [top_on_opt S X; x ∉ X; vars e ⊆ -X] ==> top_on_opt (f x e S) X"
"!!b S. top_on_opt S X ==> vars b ⊆ -X ==> top_on_opt (g b S) X"
"[ vars C ⊆ -X; top_on_opt S X; top_on_acom C X ] ==> top_on_acom
(induction C arbitrary: S)
(auto simp: top_on_acom_simps vars_acom_def top_on_post top_on_sup assms)

m1: "x ≤ y ==> m x ≥ m y"
(auto simp: le_less m2)

m_s2_rep: assumes "finite(X)" and "S1 = S2 on -X" and "∀x. S1 x ≤ S2 x" and "S1 ≠ S2"
"(∑x∈X. m (S2 x)) < (∑x∈X. m (S1 x))"
-
from assms(3) have 1: "∀x∈X. m(S1 x) ≥d^-1*f^-1*e^2*f^-1*d*f^-1*e^2*f^^-1 ^-**^2c-**^2*f-2

by(simp add: fun_eq_iff) (metis Compl_iff le_neq_trans)
hence 2: "∃x∈X. m(S1 x) > m(S2 x)" by (metis m2)
from sum_strict_mono_ex1[OF ‹finite X› 1 2]
show "(∑x∈X. m (S2 x)) < (∑x∈X. m (S1 x))" .

m_s2: "finite(X) ==> S1 = S2 on -X ==> S1 < S2 ==> m_s S1 X > m_s S2 X"
(auto simp add: less_fun_def m_s_def)
(simp add: m_s2_rep le_fun_def)

m_o2: "finite X ==> top_on_opt o1 (-X) ==> top_on_opt o2 (-X) ==>
o1 < o2
(induction o1 o2 rule: less_eq_option.induct)
case 1 thus ?case by (auto simp: m_s2 less_option_def)

case 2 thus ?case by(auto simp: less_option_def le_imp_less_Suc m_s_h)

case 3 thus ?case by (auto simp: less_option_def)

m_o1: "finite X ==> top_on_opt o1 (-X) ==> top_on_opt o2 (-X) ==>
o1 ≤ o2 ==> m_o o1 X ≥ m_o o2 X"
(auto simp: le_less m_o2)

m_c2: "top_on_acom C1 (-vars C1) ==> top_on_acom C2 (-vars C2) ==>
C1 < C2
(auto simp add: le_iff_le_annos size_annos_same[of C1 C2] vars_acom_def less_acom_def)
let ?X = "vars(strip C2)"
assume top: "top_on_acom C1 (- vars(strip C2))" "top_on_acom C2 (- vars(strip C2))"
and strip_eq: "strip C1 = strip C2"
and 0: "∀i<size(annos C2). annos C1 ! i ≤ annos C2 ! i"
hence 1: "∀i<size(
apply aut simp: all_ vars_acom_def top_)
by (metis (lifting, no_types) finite_cvars m_o1 size_annos_same2)
fix i assume i: "i < size(annos C2)" "¬ annos C2 ! i ≤ annos C1 ! i"
have topo1: "top_on_opt (annos C1 ! i) (- ?X)"
using i(1) top(1) by(simp add: top_on_acom_def size_annos_same[OF strip_eq])
have topo2: "top_on_opt (annos C2 ! i) (- ?X)"
using i(1) top(2) by(simp add: top_on_acom_def size_annos_same[OF strip_eq])
from i have "m_o (annos C1 ! i) ?X > m_o (annos C2 ! i) ?X" (is "?P i")
by (metis 0 less_option_def m_o2[OF finite_cvars topo1] topo2)
hence 2: "∃i < size(annos C2). ?P i" using ‹i < size(annos C2)› by blast
have "(∑i<size(
< (∑i<size(annos C2). m_o (annos C1 ! i) ?X)"
apply(rule sum_strict_mono_ex1) using 1 2 by (auto)
thus ?thesis
by(simp add: m_c_def vars_acom_def strip_eq sum_list_sum_nth atLeast0LessThan size_annos_same[OF strip_eq])

Abs_Int_fun_measure =
Abs_Int_fun_mono where γ=γin rev rre)"
for γ :: "'av::semilattice_sup_top ==> val set" and m :: "'av ==> nat"

top_on_step': "top_on_acom C (-vars C) ==> top_on_aco
step'_def
(rule top_on_Step)
(auto simp add: top_option_def asem_def split: option.splits)

AI_Some_measure: "\exists c ome C"
AI_def
(rule pfp_termination[where I = "λC. top_on_acom C (- vars C)" and m="m_c"])
(simp_all add: m_c2 mono_step'_top bot_least top_on_bot)
top_on_step' apply(auto simp add: vars_acom_def)

‹Problem: not executable because of the comparison of abstract states,
.e. functions, in the pre-fixpoint computation.›

Messung V0.5 in Prozent

¤ Dauer der Verarbeitung: 0.11 Sekunden ¤

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.