# HG changeset patch # User wenzelm # Date 1214424094 -7200 # Node ID a6dc1769fdda19ae693f4ac5a20401644e74e4c3 # Parent 24ec32bee347f14680d5a9b59958f3a2b5dccab6 modernized specifications; diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMP/Com.thy --- a/src/HOL/IMP/Com.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMP/Com.thy Wed Jun 25 22:01:34 2008 +0200 @@ -28,9 +28,9 @@ | Cond bexp com com ("IF _ THEN _ ELSE _" 60) | While bexp com ("WHILE _ DO _" 60) -syntax (latex) - SKIP :: com ("\") - Cond :: "bexp \ com \ com \ com" ("\ _ \ _ \ _" 60) - While :: "bexp \ com \ com" ("\ _ \ _" 60) +notation (latex) + SKIP ("\") and + Cond ("\ _ \ _ \ _" 60) and + While ("\ _ \ _" 60) end diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMP/Compiler.thy --- a/src/HOL/IMP/Compiler.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMP/Compiler.thy Wed Jun 25 22:01:34 2008 +0200 @@ -8,16 +8,16 @@ subsection "The compiler" -consts compile :: "com \ instr list" -primrec -"compile \ = []" -"compile (x:==a) = [SET x a]" -"compile (c1;c2) = compile c1 @ compile c2" -"compile (\ b \ c1 \ c2) = - [JMPF b (length(compile c1) + 1)] @ compile c1 @ - [JMPF (\x. False) (length(compile c2))] @ compile c2" -"compile (\ b \ c) = [JMPF b (length(compile c) + 1)] @ compile c @ - [JMPB (length(compile c)+1)]" +primrec compile :: "com \ instr list" +where + "compile \ = []" +| "compile (x:==a) = [SET x a]" +| "compile (c1;c2) = compile c1 @ compile c2" +| "compile (\ b \ c1 \ c2) = + [JMPF b (length(compile c1) + 1)] @ compile c1 @ + [JMPF (\x. False) (length(compile c2))] @ compile c2" +| "compile (\ b \ c) = [JMPF b (length(compile c) + 1)] @ compile c @ + [JMPB (length(compile c)+1)]" subsection "Compiler correctness" @@ -65,31 +65,33 @@ lemma [simp]: "(\[],q,s\ -*\ \p',q',t\) = (p' = [] \ q' = q \ t = s)" by(simp add: rtrancl_is_UN_rel_pow) -constdefs - forws :: "instr \ nat set" -"forws instr == case instr of - SET x a \ {0} | - JMPF b n \ {0,n} | - JMPB n \ {}" - backws :: "instr \ nat set" -"backws instr == case instr of - SET x a \ {} | - JMPF b n \ {} | - JMPB n \ {n}" +definition + forws :: "instr \ nat set" where + "forws instr = (case instr of + SET x a \ {0} | + JMPF b n \ {0,n} | + JMPB n \ {})" -consts closed :: "nat \ nat \ instr list \ bool" -primrec -"closed m n [] = True" -"closed m n (instr#is) = ((\j \ forws instr. j \ size is+n) \ - (\j \ backws instr. j \ m) \ closed (Suc m) n is)" +definition + backws :: "instr \ nat set" where + "backws instr = (case instr of + SET x a \ {} | + JMPF b n \ {} | + JMPB n \ {n})" + +primrec closed :: "nat \ nat \ instr list \ bool" +where + "closed m n [] = True" +| "closed m n (instr#is) = ((\j \ forws instr. j \ size is+n) \ + (\j \ backws instr. j \ m) \ closed (Suc m) n is)" lemma [simp]: "\m n. closed m n (C1@C2) = (closed m (n+size C2) C1 \ closed (m+size C1) n C2)" -by(induct C1, simp, simp add:add_ac) +by(induct C1) (simp, simp add:add_ac) theorem [simp]: "\m n. closed m n (compile c)" -by(induct c, simp_all add:backws_def forws_def) +by(induct c) (simp_all add:backws_def forws_def) lemma drop_lem: "n \ size(p1@p2) \ (p1' @ p2 = drop n p1 @ drop (n - size p1) p2) = diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMP/Denotation.thy --- a/src/HOL/IMP/Denotation.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMP/Denotation.thy Wed Jun 25 22:01:34 2008 +0200 @@ -10,21 +10,19 @@ types com_den = "(state\state)set" -constdefs - Gamma :: "[bexp,com_den] => (com_den => com_den)" - "Gamma b cd == (\phi. {(s,t). (s,t) \ (phi O cd) \ b s} \ +definition + Gamma :: "[bexp,com_den] => (com_den => com_den)" where + "Gamma b cd = (\phi. {(s,t). (s,t) \ (phi O cd) \ b s} \ {(s,t). s=t \ \b s})" -consts - C :: "com => com_den" - -primrec +primrec C :: "com => com_den" +where C_skip: "C \ = Id" - C_assign: "C (x :== a) = {(s,t). t = s[x\a(s)]}" - C_comp: "C (c0;c1) = C(c1) O C(c0)" - C_if: "C (\ b \ c1 \ c2) = {(s,t). (s,t) \ C c1 \ b s} \ +| C_assign: "C (x :== a) = {(s,t). t = s[x\a(s)]}" +| C_comp: "C (c0;c1) = C(c1) O C(c0)" +| C_if: "C (\ b \ c1 \ c2) = {(s,t). (s,t) \ C c1 \ b s} \ {(s,t). (s,t) \ C c2 \ \b s}" - C_while: "C(\ b \ c) = lfp (Gamma b (C c))" +| C_while: "C(\ b \ c) = lfp (Gamma b (C c))" (**** mono (Gamma(b,c)) ****) diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMP/Examples.thy --- a/src/HOL/IMP/Examples.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMP/Examples.thy Wed Jun 25 22:01:34 2008 +0200 @@ -8,11 +8,11 @@ theory Examples imports Natural begin -constdefs - factorial :: "loc => loc => com" - "factorial a b == b :== (%s. 1); +definition + factorial :: "loc => loc => com" where + "factorial a b = (b :== (%s. 1); \ (%s. s a ~= 0) \ - (b :== (%s. s b * s a); a :== (%s. s a - 1))" + (b :== (%s. s b * s a); a :== (%s. s a - 1)))" declare update_def [simp] diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMP/Expr.thy --- a/src/HOL/IMP/Expr.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMP/Expr.thy Wed Jun 25 22:01:34 2008 +0200 @@ -68,23 +68,22 @@ lemmas [intro] = tru fls ROp noti andi ori subsection "Denotational semantics of arithmetic and boolean expressions" -consts - A :: "aexp => state => nat" - B :: "bexp => state => bool" -primrec +primrec A :: "aexp => state => nat" +where "A(N(n)) = (%s. n)" - "A(X(x)) = (%s. s(x))" - "A(Op1 f a) = (%s. f(A a s))" - "A(Op2 f a0 a1) = (%s. f (A a0 s) (A a1 s))" +| "A(X(x)) = (%s. s(x))" +| "A(Op1 f a) = (%s. f(A a s))" +| "A(Op2 f a0 a1) = (%s. f (A a0 s) (A a1 s))" -primrec +primrec B :: "bexp => state => bool" +where "B(true) = (%s. True)" - "B(false) = (%s. False)" - "B(ROp f a0 a1) = (%s. f (A a0 s) (A a1 s))" - "B(noti(b)) = (%s. ~(B b s))" - "B(b0 andi b1) = (%s. (B b0 s) & (B b1 s))" - "B(b0 ori b1) = (%s. (B b0 s) | (B b1 s))" +| "B(false) = (%s. False)" +| "B(ROp f a0 a1) = (%s. f (A a0 s) (A a1 s))" +| "B(noti(b)) = (%s. ~(B b s))" +| "B(b0 andi b1) = (%s. (B b0 s) & (B b1 s))" +| "B(b0 ori b1) = (%s. (B b0 s) | (B b1 s))" lemma [simp]: "(N(n),s) -a-> n' = (n = n')" by (rule,cases set: evala) auto diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMP/Hoare.thy --- a/src/HOL/IMP/Hoare.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMP/Hoare.thy Wed Jun 25 22:01:34 2008 +0200 @@ -10,8 +10,9 @@ types assn = "state => bool" -constdefs hoare_valid :: "[assn,com,assn] => bool" ("|= {(1_)}/ (_)/ {(1_)}" 50) - "|= {P}c{Q} == !s t. (s,t) : C(c) --> P s --> Q t" +definition + hoare_valid :: "[assn,com,assn] => bool" ("|= {(1_)}/ (_)/ {(1_)}" 50) where + "|= {P}c{Q} = (!s t. (s,t) : C(c) --> P s --> Q t)" inductive hoare :: "assn => com => assn => bool" ("|- ({(1_)}/ (_)/ {(1_)})" 50) @@ -26,8 +27,9 @@ | conseq: "[| !s. P' s --> P s; |- {P}c{Q}; !s. Q s --> Q' s |] ==> |- {P'}c{Q'}" -constdefs wp :: "com => assn => assn" - "wp c Q == (%s. !t. (s,t) : C(c) --> Q t)" +definition + wp :: "com => assn => assn" where + "wp c Q = (%s. !t. (s,t) : C(c) --> Q t)" (* Soundness (and part of) relative completeness of Hoare rules diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMP/Natural.thy --- a/src/HOL/IMP/Natural.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMP/Natural.thy Wed Jun 25 22:01:34 2008 +0200 @@ -18,12 +18,12 @@ @{text "(c,s,s')"} is part of the relation @{text evalc}}: *} -constdefs - update :: "('a \ 'b) \ 'a \ 'b \ ('a \ 'b)" ("_/[_ ::= /_]" [900,0,0] 900) - "update == fun_upd" +definition + update :: "('a \ 'b) \ 'a \ 'b \ ('a \ 'b)" ("_/[_ ::= /_]" [900,0,0] 900) where + "update = fun_upd" -syntax (xsymbols) - update :: "('a \ 'b) \ 'a \ 'b \ ('a \ 'b)" ("_/[_ \ /_]" [900,0,0] 900) +notation (xsymbols) + update ("_/[_ \ /_]" [900,0,0] 900) text {* The big-step execution relation @{text evalc} is defined inductively: @@ -104,9 +104,9 @@ in @{text s'} iff @{text c'} started in the same @{text s} also terminates in the same @{text s'}}. Formally: *} -constdefs - equiv_c :: "com \ com \ bool" ("_ \ _") - "c \ c' \ \s s'. \c, s\ \\<^sub>c s' = \c', s\ \\<^sub>c s'" +definition + equiv_c :: "com \ com \ bool" ("_ \ _") where + "c \ c' = (\s s'. \c, s\ \\<^sub>c s' = \c', s\ \\<^sub>c s')" text {* Proof rules telling Isabelle to unfold the definition diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMP/Transition.thy --- a/src/HOL/IMP/Transition.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMP/Transition.thy Wed Jun 25 22:01:34 2008 +0200 @@ -25,21 +25,20 @@ Some syntactic sugar that we will use to hide the @{text option} part in configurations: *} -syntax - "_angle" :: "[com, state] \ com option \ state" ("<_,_>") - "_angle2" :: "state \ com option \ state" ("<_>") - -syntax (xsymbols) - "_angle" :: "[com, state] \ com option \ state" ("\_,_\") - "_angle2" :: "state \ com option \ state" ("\_\") +abbreviation + angle :: "[com, state] \ com option \ state" ("<_,_>") where + " == (Some c, s)" +abbreviation + angle2 :: "state \ com option \ state" ("<_>") where + " == (None, s)" -syntax (HTML output) - "_angle" :: "[com, state] \ com option \ state" ("\_,_\") - "_angle2" :: "state \ com option \ state" ("\_\") +notation (xsymbols) + angle ("\_,_\") and + angle2 ("\_\") -translations - "\c,s\" == "(Some c, s)" - "\s\" == "(None, s)" +notation (HTML output) + angle ("\_,_\") and + angle2 ("\_\") text {* Now, finally, we are set to write down the rules for our small step semantics: diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMP/VC.thy --- a/src/HOL/IMP/VC.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMP/VC.thy Wed Jun 25 22:01:34 2008 +0200 @@ -18,46 +18,44 @@ | Aif bexp acom acom | Awhile bexp assn acom -consts - vc :: "acom => assn => assn" - awp :: "acom => assn => assn" - vcawp :: "acom => assn => assn \ assn" - astrip :: "acom => com" - -primrec +primrec awp :: "acom => assn => assn" +where "awp Askip Q = Q" - "awp (Aass x a) Q = (\s. Q(s[x\a s]))" - "awp (Asemi c d) Q = awp c (awp d Q)" - "awp (Aif b c d) Q = (\s. (b s-->awp c Q s) & (~b s-->awp d Q s))" - "awp (Awhile b I c) Q = I" +| "awp (Aass x a) Q = (\s. Q(s[x\a s]))" +| "awp (Asemi c d) Q = awp c (awp d Q)" +| "awp (Aif b c d) Q = (\s. (b s-->awp c Q s) & (~b s-->awp d Q s))" +| "awp (Awhile b I c) Q = I" -primrec +primrec vc :: "acom => assn => assn" +where "vc Askip Q = (\s. True)" - "vc (Aass x a) Q = (\s. True)" - "vc (Asemi c d) Q = (\s. vc c (awp d Q) s & vc d Q s)" - "vc (Aif b c d) Q = (\s. vc c Q s & vc d Q s)" - "vc (Awhile b I c) Q = (\s. (I s & ~b s --> Q s) & +| "vc (Aass x a) Q = (\s. True)" +| "vc (Asemi c d) Q = (\s. vc c (awp d Q) s & vc d Q s)" +| "vc (Aif b c d) Q = (\s. vc c Q s & vc d Q s)" +| "vc (Awhile b I c) Q = (\s. (I s & ~b s --> Q s) & (I s & b s --> awp c I s) & vc c I s)" -primrec +primrec astrip :: "acom => com" +where "astrip Askip = SKIP" - "astrip (Aass x a) = (x:==a)" - "astrip (Asemi c d) = (astrip c;astrip d)" - "astrip (Aif b c d) = (\ b \ astrip c \ astrip d)" - "astrip (Awhile b I c) = (\ b \ astrip c)" +| "astrip (Aass x a) = (x:==a)" +| "astrip (Asemi c d) = (astrip c;astrip d)" +| "astrip (Aif b c d) = (\ b \ astrip c \ astrip d)" +| "astrip (Awhile b I c) = (\ b \ astrip c)" (* simultaneous computation of vc and awp: *) -primrec +primrec vcawp :: "acom => assn => assn \ assn" +where "vcawp Askip Q = (\s. True, Q)" - "vcawp (Aass x a) Q = (\s. True, \s. Q(s[x\a s]))" - "vcawp (Asemi c d) Q = (let (vcd,wpd) = vcawp d Q; +| "vcawp (Aass x a) Q = (\s. True, \s. Q(s[x\a s]))" +| "vcawp (Asemi c d) Q = (let (vcd,wpd) = vcawp d Q; (vcc,wpc) = vcawp c wpd in (\s. vcc s & vcd s, wpc))" - "vcawp (Aif b c d) Q = (let (vcd,wpd) = vcawp d Q; +| "vcawp (Aif b c d) Q = (let (vcd,wpd) = vcawp d Q; (vcc,wpc) = vcawp c Q in (\s. vcc s & vcd s, \s.(b s --> wpc s) & (~b s --> wpd s)))" - "vcawp (Awhile b I c) Q = (let (vcc,wpc) = vcawp c I +| "vcawp (Awhile b I c) Q = (let (vcc,wpc) = vcawp c I in (\s. (I s & ~b s --> Q s) & (I s & b s --> wpc s) & vcc s, I))" diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMPP/Com.thy --- a/src/HOL/IMPP/Com.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMPP/Com.thy Wed Jun 25 22:01:34 2008 +0200 @@ -15,8 +15,8 @@ typedecl glb typedecl loc -consts - Arg :: loc +axiomatization + Arg :: loc and Res :: loc datatype vname = Glb glb | Loc loc @@ -43,8 +43,9 @@ | Call vname pname aexp ("_:=CALL _'(_')" [65, 65, 0] 60) consts bodies :: "(pname * com) list"(* finitely many procedure definitions *) - body :: " pname ~=> com" -defs body_def: "body == map_of bodies" +definition + body :: " pname ~=> com" where + "body = map_of bodies" (* Well-typedness: all procedures called must exist *) @@ -78,9 +79,9 @@ "WT (c1;;c2)" "WT (IF b THEN c1 ELSE c2)" "WT (WHILE b DO c)" "WT (BODY P)" "WT (X:=CALL P(a))" -constdefs - WT_bodies :: bool - "WT_bodies == !(pn,b):set bodies. WT b" +definition + WT_bodies :: bool where + "WT_bodies = (!(pn,b):set bodies. WT b)" ML {* val make_imp_tac = EVERY'[rtac mp, fn i => atac (i+1), etac thin_rl] *} diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMPP/EvenOdd.thy --- a/src/HOL/IMPP/EvenOdd.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMPP/EvenOdd.thy Wed Jun 25 22:01:34 2008 +0200 @@ -10,38 +10,41 @@ imports Misc begin -constdefs - even :: "nat => bool" - "even n == 2 dvd n" +definition + even :: "nat => bool" where + "even n = (2 dvd n)" -consts - Even :: pname +axiomatization + Even :: pname and Odd :: pname -axioms - Even_neq_Odd: "Even ~= Odd" +where + Even_neq_Odd: "Even ~= Odd" and Arg_neq_Res: "Arg ~= Res" -constdefs - evn :: com - "evn == IF (%s. s = 0) +definition + evn :: com where + "evn = (IF (%s. s = 0) THEN Loc Res:==(%s. 0) ELSE(Loc Res:=CALL Odd(%s. s - 1);; Loc Arg:=CALL Odd(%s. s - 1);; - Loc Res:==(%s. s * s))" - odd :: com - "odd == IF (%s. s = 0) + Loc Res:==(%s. s * s)))" + +definition + odd :: com where + "odd = (IF (%s. s = 0) THEN Loc Res:==(%s. 1) - ELSE(Loc Res:=CALL Even (%s. s - 1))" + ELSE(Loc Res:=CALL Even (%s. s - 1)))" defs bodies_def: "bodies == [(Even,evn),(Odd,odd)]" -consts - Z_eq_Arg_plus :: "nat => nat assn" ("Z=Arg+_" [50]50) - "even_Z=(Res=0)" :: "nat assn" ("Res'_ok") -defs - Z_eq_Arg_plus_def: "Z=Arg+n == %Z s. Z = s+n" - Res_ok_def: "Res_ok == %Z s. even Z = (s = 0)" +definition + Z_eq_Arg_plus :: "nat => nat assn" ("Z=Arg+_" [50]50) where + "Z=Arg+n = (%Z s. Z = s+n)" + +definition + Res_ok :: "nat assn" where + "Res_ok = (%Z s. even Z = (s = 0))" subsection "even" diff -r 24ec32bee347 -r a6dc1769fdda src/HOL/IMPP/Natural.thy --- a/src/HOL/IMPP/Natural.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOL/IMPP/Natural.thy Wed Jun 25 22:01:34 2008 +0200 @@ -17,10 +17,10 @@ setlocs :: "state => locals => state" getlocs :: "state => locals" update :: "state => vname => val => state" ("_/[_/::=/_]" [900,0,0] 900) -syntax (* IN Natural.thy *) - loc :: "state => locals" ("_<_>" [75,0] 75) -translations - "s" == "getlocs s X" + +abbreviation + loc :: "state => locals" ("_<_>" [75,0] 75) where + "s == getlocs s X" inductive evalc :: "[com,state, state] => bool" ("<_,_>/ -c-> _" [0,0, 51] 51) diff -r 24ec32bee347 -r a6dc1769fdda src/HOLCF/IMP/Denotational.thy --- a/src/HOLCF/IMP/Denotational.thy Wed Jun 25 21:25:51 2008 +0200 +++ b/src/HOLCF/IMP/Denotational.thy Wed Jun 25 22:01:34 2008 +0200 @@ -14,15 +14,14 @@ dlift :: "(('a::type) discr -> 'b::pcpo) => ('a lift -> 'b)" where "dlift f = (LAM x. case x of UU => UU | Def y => f\(Discr y))" -consts D :: "com => state discr -> state lift" - -primrec +primrec D :: "com => state discr -> state lift" +where "D(\) = (LAM s. Def(undiscr s))" - "D(X :== a) = (LAM s. Def((undiscr s)[X \ a(undiscr s)]))" - "D(c0 ; c1) = (dlift(D c1) oo (D c0))" - "D(\ b \ c1 \ c2) = +| "D(X :== a) = (LAM s. Def((undiscr s)[X \ a(undiscr s)]))" +| "D(c0 ; c1) = (dlift(D c1) oo (D c0))" +| "D(\ b \ c1 \ c2) = (LAM s. if b (undiscr s) then (D c1)\s else (D c2)\s)" - "D(\ b \ c) = +| "D(\ b \ c) = fix\(LAM w s. if b (undiscr s) then (dlift w)\((D c)\s) else Def(undiscr s))"