# HG changeset patch # User wenzelm # Date 1608758722 -3600 # Node ID db8f94656024ebc496d839e6506acba8285339eb # Parent 5906162c8dd45c14da9ebca01cd5c8266856f192 tuned document, notably authors and sections; diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/Arith2.thy --- a/src/HOL/Hoare/Arith2.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/Arith2.thy Wed Dec 23 22:25:22 2020 +0100 @@ -1,12 +1,12 @@ (* Title: HOL/Hoare/Arith2.thy Author: Norbert Galm Copyright 1995 TUM - -More arithmetic. Much of this duplicates ex/Primes. *) +section \More arithmetic\ + theory Arith2 -imports Main + imports Main begin definition cd :: "[nat, nat, nat] \ bool" @@ -21,7 +21,7 @@ | "fac (Suc n) = Suc n * fac n" -subsubsection \cd\ +subsection \cd\ lemma cd_nnn: "0 cd n n n" apply (simp add: cd_def) @@ -48,7 +48,7 @@ done -subsubsection \gcd\ +subsection \gcd\ lemma gcd_nnn: "0 n = gcd n n" apply (unfold gcd_def) @@ -79,7 +79,7 @@ done -subsubsection \pow\ +subsection \pow\ lemma sq_pow_div2 [simp]: "m mod 2 = 0 \ ((n::nat)*n)^(m div 2) = n^m" diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/Examples.thy --- a/src/HOL/Hoare/Examples.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/Examples.thy Wed Dec 23 22:25:22 2020 +0100 @@ -3,13 +3,15 @@ Copyright 1998 TUM *) -chapter \Various examples\ - -theory Examples imports Hoare_Logic Arith2 begin +section \Various examples\ -section \ARITHMETIC\ +theory Examples + imports Hoare_Logic Arith2 +begin -subsection \multiplication by successive addition\ +subsection \Arithmetic\ + +subsubsection \Multiplication by successive addition\ lemma multiply_by_add: "VARS m s a b {a=A \ b=B} @@ -54,7 +56,7 @@ done -subsection \Euclid's algorithm for GCD\ +subsubsection \Euclid's algorithm for GCD\ lemma Euclid_GCD: "VARS a b {0Dijkstra's extension of Euclid's algorithm for simultaneous GCD and SCM\ +subsubsection \Dijkstra's extension of Euclid's algorithm for simultaneous GCD and SCM\ text \ From E.W. Disjkstra. Selected Writings on Computing, p 98 (EWD474), @@ -112,7 +114,7 @@ done -subsection \Power by iterated squaring and multiplication\ +subsubsection \Power by iterated squaring and multiplication\ lemma power_by_mult: "VARS a b c {a=A & b=B} @@ -132,7 +134,7 @@ done -subsection \Factorial\ +subsubsection \Factorial\ lemma factorial: "VARS a b {a=A} @@ -185,7 +187,7 @@ done -subsection \Square root\ +subsubsection \Square root\ \ \the easy way:\ @@ -221,7 +223,7 @@ done -section \LISTS\ +subsection \Lists\ lemma imperative_reverse: "VARS y x {x=X} @@ -276,9 +278,9 @@ done -section \ARRAYS\ +subsection \Arrays\ -subsection \Search for a key\ +subsubsection \Search for a key\ lemma zero_search: "VARS A i {True} diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/ExamplesAbort.thy --- a/src/HOL/Hoare/ExamplesAbort.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/ExamplesAbort.thy Wed Dec 23 22:25:22 2020 +0100 @@ -1,11 +1,13 @@ (* Title: HOL/Hoare/ExamplesAbort.thy Author: Tobias Nipkow Copyright 1998 TUM - -Some small examples for programs that may abort. *) -theory ExamplesAbort imports Hoare_Logic_Abort begin +section \Some small examples for programs that may abort\ + +theory ExamplesAbort + imports Hoare_Logic_Abort +begin lemma "VARS x y z::nat {y = z & z \ 0} z \ 0 \ x := y div z {x = 1}" diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/ExamplesTC.thy --- a/src/HOL/Hoare/ExamplesTC.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/ExamplesTC.thy Wed Dec 23 22:25:22 2020 +0100 @@ -5,9 +5,7 @@ section \Examples using Hoare Logic for Total Correctness\ theory ExamplesTC - -imports Hoare_Logic - + imports Hoare_Logic begin text \ diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/Heap.thy --- a/src/HOL/Hoare/Heap.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/Heap.thy Wed Dec 23 22:25:22 2020 +0100 @@ -1,12 +1,15 @@ (* Title: HOL/Hoare/Heap.thy Author: Tobias Nipkow Copyright 2002 TUM - -Pointers, heaps and heap abstractions. -See the paper by Mehta and Nipkow. *) -theory Heap imports Main begin +section \Pointers, heaps and heap abstractions\ + +text \See the paper by Mehta and Nipkow.\ + +theory Heap + imports Main +begin subsection "References" @@ -22,9 +25,9 @@ "addr (Ref a) = a" -section "The heap" +subsection "The heap" -subsection "Paths in the heap" +subsubsection "Paths in the heap" primrec Path :: "('a \ 'a ref) \ 'a ref \ 'a list \ 'a ref \ bool" where "Path h x [] y \ x = y" @@ -55,7 +58,7 @@ by simp -subsection "Non-repeating paths" +subsubsection "Non-repeating paths" definition distPath :: "('a \ 'a ref) \ 'a ref \ 'a list \ 'a ref \ bool" where "distPath h x as y \ Path h x as y \ distinct as" @@ -78,9 +81,9 @@ by (case_tac Ps, auto) -subsection "Lists on the heap" +subsubsection "Lists on the heap" -subsubsection "Relational abstraction" +paragraph "Relational abstraction" definition List :: "('a \ 'a ref) \ 'a ref \ 'a list \ bool" where "List h x as = Path h x as Null" @@ -131,7 +134,7 @@ done -subsection "Functional abstraction" +subsubsection "Functional abstraction" definition islist :: "('a \ 'a ref) \ 'a ref \ bool" where "islist h p \ (\as. List h p as)" diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/HeapSyntax.thy --- a/src/HOL/Hoare/HeapSyntax.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/HeapSyntax.thy Wed Dec 23 22:25:22 2020 +0100 @@ -3,7 +3,11 @@ Copyright 2002 TUM *) -theory HeapSyntax imports Hoare_Logic Heap begin +section \Heap syntax\ + +theory HeapSyntax + imports Hoare_Logic Heap +begin subsection "Field access and update" diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/HeapSyntaxAbort.thy --- a/src/HOL/Hoare/HeapSyntaxAbort.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/HeapSyntaxAbort.thy Wed Dec 23 22:25:22 2020 +0100 @@ -3,7 +3,11 @@ Copyright 2002 TUM *) -theory HeapSyntaxAbort imports Hoare_Logic_Abort Heap begin +section \Heap syntax (abort)\ + +theory HeapSyntaxAbort + imports Hoare_Logic_Abort Heap +begin subsection "Field access and update" diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/Hoare_Logic.thy --- a/src/HOL/Hoare/Hoare_Logic.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/Hoare_Logic.thy Wed Dec 23 22:25:22 2020 +0100 @@ -4,7 +4,13 @@ Author: Walter Guttmann (extension to total-correctness proofs) *) -section \Sugared semantic embedding of Hoare logic\ +section \Hoare logic\ + +theory Hoare_Logic + imports Hoare_Syntax Hoare_Tac +begin + +subsection \Sugared semantic embedding of Hoare logic\ text \ Strictly speaking a shallow embedding (as implemented by Norbert Galm @@ -12,10 +18,6 @@ later. \ -theory Hoare_Logic -imports Hoare_Syntax Hoare_Tac -begin - type_synonym 'a bexp = "'a set" type_synonym 'a assn = "'a set" type_synonym 'a var = "'a \ nat" @@ -167,7 +169,7 @@ qed -subsection \Concrete syntax\ +subsubsection \Concrete syntax\ setup \ Hoare_Syntax.setup @@ -181,7 +183,7 @@ \ -subsection \Proof methods: VCG\ +subsubsection \Proof methods: VCG\ declare BasicRule [Hoare_Tac.BasicRule] and SkipRule [Hoare_Tac.SkipRule] diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/Hoare_Logic_Abort.thy --- a/src/HOL/Hoare/Hoare_Logic_Abort.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/Hoare_Logic_Abort.thy Wed Dec 23 22:25:22 2020 +0100 @@ -7,7 +7,7 @@ section \Hoare Logic with an Abort statement for modelling run time errors\ theory Hoare_Logic_Abort -imports Hoare_Syntax Hoare_Tac + imports Hoare_Syntax Hoare_Tac begin type_synonym 'a bexp = "'a set" diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/Hoare_Syntax.thy --- a/src/HOL/Hoare/Hoare_Syntax.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/Hoare_Syntax.thy Wed Dec 23 22:25:22 2020 +0100 @@ -1,9 +1,9 @@ (* Title: HOL/Hoare/Hoare_Syntax.thy Author: Leonor Prensa Nieto & Tobias Nipkow Author: Walter Guttmann (extension to total-correctness proofs) +*) -Concrete syntax for Hoare logic, with translations for variables. -*) +section \Concrete syntax for Hoare logic, with translations for variables\ theory Hoare_Syntax imports Main diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/Hoare_Tac.thy --- a/src/HOL/Hoare/Hoare_Tac.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/Hoare_Tac.thy Wed Dec 23 22:25:22 2020 +0100 @@ -1,9 +1,9 @@ (* Title: HOL/Hoare/Hoare_Tac.thy Author: Leonor Prensa Nieto & Tobias Nipkow Author: Walter Guttmann (extension to total-correctness proofs) +*) -Derivation of the proof rules and, most importantly, the VCG tactic. -*) +section \Hoare logic VCG tactic\ theory Hoare_Tac imports Main diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/Pointer_Examples.thy --- a/src/HOL/Hoare/Pointer_Examples.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/Pointer_Examples.thy Wed Dec 23 22:25:22 2020 +0100 @@ -1,17 +1,20 @@ (* Title: HOL/Hoare/Pointer_Examples.thy Author: Tobias Nipkow Copyright 2002 TUM - -Examples of verifications of pointer programs. *) -theory Pointer_Examples imports HeapSyntax begin +section \Examples of verifications of pointer programs\ + +theory Pointer_Examples + imports HeapSyntax +begin axiomatization where unproven: "PROP A" -section "Verifications" -subsection "List reversal" +subsection "Verifications" + +subsubsection "List reversal" text "A short but unreadable proof:" @@ -105,7 +108,7 @@ done -subsection "Searching in a list" +subsubsection "Searching in a list" text\What follows is a sequence of successively more intelligent proofs that a simple loop finds an element in a linked list. @@ -174,7 +177,8 @@ apply clarsimp done -subsection "Splicing two lists" + +subsubsection "Splicing two lists" lemma "VARS tl p q pp qq {List tl p Ps \ List tl q Qs \ set Ps \ set Qs = {} \ size Qs \ size Ps} @@ -204,7 +208,7 @@ done -subsection "Merging two lists" +subsubsection "Merging two lists" text"This is still a bit rough, especially the proof." @@ -392,7 +396,7 @@ text"The proof is automatic, but requires a numbet of special lemmas." -subsection "Cyclic list reversal" +subsubsection "Cyclic list reversal" text\We consider two algorithms for the reversal of circular lists. @@ -468,7 +472,7 @@ done -subsection "Storage allocation" +subsubsection "Storage allocation" definition new :: "'a set \ 'a" where "new A = (SOME a. a \ A)" diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/Pointer_ExamplesAbort.thy --- a/src/HOL/Hoare/Pointer_ExamplesAbort.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/Pointer_ExamplesAbort.thy Wed Dec 23 22:25:22 2020 +0100 @@ -1,15 +1,17 @@ (* Title: HOL/Hoare/Pointer_ExamplesAbort.thy Author: Tobias Nipkow Copyright 2002 TUM - -Examples of verifications of pointer programs *) -theory Pointer_ExamplesAbort imports HeapSyntaxAbort begin +section \Examples of verifications of pointer programs\ -section "Verifications" +theory Pointer_ExamplesAbort + imports HeapSyntaxAbort +begin -subsection "List reversal" +subsection "Verifications" + +subsubsection "List reversal" text "Interestingly, this proof is the same as for the unguarded program:" diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/Pointers0.thy --- a/src/HOL/Hoare/Pointers0.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/Pointers0.thy Wed Dec 23 22:25:22 2020 +0100 @@ -9,7 +9,11 @@ - in fact in some case they appear to get (a bit) more complicated. *) -theory Pointers0 imports Hoare_Logic begin +section \Alternative pointers\ + +theory Pointers0 + imports Hoare_Logic +begin subsection "References" @@ -40,9 +44,9 @@ by vcg_simp -section "The heap" +subsection "The heap" -subsection "Paths in the heap" +subsubsection "Paths in the heap" primrec Path :: "('a::ref \ 'a) \ 'a \ 'a list \ 'a \ bool" where @@ -68,9 +72,9 @@ lemma [simp]: "\x. u \ set as \ Path (f(u := v)) x as y = Path f x as y" by(induct as, simp, simp add:eq_sym_conv) -subsection "Lists on the heap" +subsubsection "Lists on the heap" -subsubsection "Relational abstraction" +paragraph "Relational abstraction" definition List :: "('a::ref \ 'a) \ 'a \ 'a list \ bool" where "List h x as = Path h x as Null" @@ -118,7 +122,7 @@ apply(fastforce dest:List_hd_not_in_tl) done -subsection "Functional abstraction" +subsubsection "Functional abstraction" definition islist :: "('a::ref \ 'a) \ 'a \ bool" where "islist h p \ (\as. List h p as)" @@ -173,9 +177,9 @@ done -section "Verifications" +subsection "Verifications" -subsection "List reversal" +subsubsection "List reversal" text "A short but unreadable proof:" @@ -256,7 +260,7 @@ done -subsection "Searching in a list" +subsubsection "Searching in a list" text\What follows is a sequence of successively more intelligent proofs that a simple loop finds an element in a linked list. @@ -312,7 +316,7 @@ done -subsection "Merging two lists" +subsubsection "Merging two lists" text"This is still a bit rough, especially the proof." @@ -398,7 +402,7 @@ (* TODO: merging with islist/list instead of List: an improvement? needs (is)path, which is not so easy to prove either. *) -subsection "Storage allocation" +subsubsection "Storage allocation" definition new :: "'a set \ 'a::ref" where "new A = (SOME a. a \ A & a \ Null)" @@ -427,5 +431,4 @@ apply (clarsimp simp: subset_insert_iff neq_Nil_conv fun_upd_apply new_notin) done - end diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/SchorrWaite.thy --- a/src/HOL/Hoare/SchorrWaite.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/SchorrWaite.thy Wed Dec 23 22:25:22 2020 +0100 @@ -1,14 +1,15 @@ (* Title: HOL/Hoare/SchorrWaite.thy Author: Farhad Mehta Copyright 2003 TUM - -Proof of the Schorr-Waite graph marking algorithm. *) +section \Proof of the Schorr-Waite graph marking algorithm\ -theory SchorrWaite imports HeapSyntax begin +theory SchorrWaite + imports HeapSyntax +begin -section \Machinery for the Schorr-Waite proof\ +subsection \Machinery for the Schorr-Waite proof\ definition \ \Relations induced by a mapping\ @@ -194,8 +195,7 @@ done -section\The Schorr-Waite algorithm\ - +subsection \The Schorr-Waite algorithm\ theorem SchorrWaiteAlgorithm: "VARS c m l r t p q root @@ -573,4 +573,3 @@ qed end - diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/SepLogHeap.thy --- a/src/HOL/Hoare/SepLogHeap.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/SepLogHeap.thy Wed Dec 23 22:25:22 2020 +0100 @@ -1,13 +1,14 @@ (* Title: HOL/Hoare/SepLogHeap.thy Author: Tobias Nipkow Copyright 2002 TUM - -Heap abstractions (at the moment only Path and List) -for Separation Logic. *) +section \Heap abstractions for Separation Logic\ + +text \(at the moment only Path and List)\ + theory SepLogHeap -imports Main + imports Main begin type_synonym heap = "(nat \ nat option)" @@ -15,6 +16,7 @@ text\\Some\ means allocated, \None\ means free. Address \0\ serves as the null reference.\ + subsection "Paths in the heap" primrec Path :: "heap \ nat \ nat list \ nat \ bool" diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/Separation.thy --- a/src/HOL/Hoare/Separation.thy Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/Separation.thy Wed Dec 23 22:25:22 2020 +0100 @@ -9,10 +9,13 @@ into parser and pretty printer, which is not very modular. Alternative: some syntax like

which stands for P H. No more compact, but avoids the funny H. - *) -theory Separation imports Hoare_Logic_Abort SepLogHeap begin +section \Separation logic\ + +theory Separation + imports Hoare_Logic_Abort SepLogHeap +begin text\The semantic definition of a few connectives:\ diff -r 5906162c8dd4 -r db8f94656024 src/HOL/Hoare/document/root.tex --- a/src/HOL/Hoare/document/root.tex Wed Dec 23 21:32:24 2020 +0100 +++ b/src/HOL/Hoare/document/root.tex Wed Dec 23 22:25:22 2020 +0100 @@ -1,4 +1,4 @@ -\documentclass[11pt,a4paper]{report} +\documentclass[11pt,a4paper]{article} \usepackage{graphicx} \usepackage[english]{babel} \usepackage{isabelle,isabellesym} @@ -10,7 +10,12 @@ \begin{document} \title{Hoare Logic} -\author{Various} +\author{ + Norbert Galm \\ + Walter Guttmann \\ + Farhad Mehta \\ + Tobias Nipkow \\ + Leonor Prensa Nieto} \maketitle \begin{abstract} @@ -27,7 +32,11 @@ \thispagestyle{empty} \tableofcontents -\newpage +\begin{center} + \includegraphics[scale=0.5]{session_graph} +\end{center} + +\clearpage \input{session}