diff --git a/thys/Word_Lib/Guide.thy b/thys/Word_Lib/Guide.thy --- a/thys/Word_Lib/Guide.thy +++ b/thys/Word_Lib/Guide.thy @@ -1,301 +1,312 @@ (*<*) theory Guide imports Main Word_Lemmas Word_Lemmas_32 Word_Lemmas_64 begin hide_const (open) Misc_set_bit.set_bit (*>*) section \A short overview over bit operations and word types\ subsection \Basic theories and key ideas\ text \ When formalizing bit operations, it is tempting to represent bit values as explicit lists over a binary type. This however is a bad idea, mainly due to the inherent ambiguities in representation concerning repeating leading bits. Hence this approach avoids such explicit lists altogether following an algebraic path: \<^item> Bit values are represented by numeric types: idealized unbounded bit values can be represented by type \<^typ>\int\, bounded bit values by quotient types over \<^typ>\int\, aka \<^typ>\'a word\. \<^item> (A special case are idealized unbounded bit values ending in @{term [source] 0} which can be represented by type \<^typ>\nat\ but only support a restricted set of operations). The most fundamental ideas are developed in theory \<^theory>\HOL.Parity\ (which is part of \<^theory>\Main\): \<^item> Multiplication by \<^term>\2 :: int\ is a bit shift to the left and \<^item> Division by \<^term>\2 :: int\ is a bit shift to the right. \<^item> Concerning bounded bit values, iterated shifts to the left may result in eliminating all bits by shifting them all beyond the boundary. The property \<^prop>\(2 :: int) ^ n \ 0\ represents that \<^term>\n\ is \<^emph>\not\ beyond that boundary. \<^item> The projection on a single bit is then @{thm [mode=iff] bit_iff_odd [where ?'a = int, no_vars]}. \<^item> This leads to the most fundamental properties of bit values: \<^item> Equality rule: @{thm [display, mode=iff] bit_eq_iff [where ?'a = int, no_vars]} \<^item> Induction rule: @{thm [display, mode=iff] bits_induct [where ?'a = int, no_vars]} On top of this, the following generic operations are provided after import of theory \<^theory>\HOL-Library.Bit_Operations\: \<^item> Singleton \<^term>\n\th bit: \<^term>\(2 :: int) ^ n\ \<^item> Bit mask upto bit \<^term>\n\: @{thm mask_eq_exp_minus_1 [where ?'a = int, no_vars]} \<^item> Left shift: @{thm push_bit_eq_mult [where ?'a = int, no_vars]} \<^item> Right shift: @{thm drop_bit_eq_div [where ?'a = int, no_vars]} \<^item> Truncation: @{thm take_bit_eq_mod [where ?'a = int, no_vars]} \<^item> Negation: @{thm [mode=iff] bit_not_iff [where ?'a = int, no_vars]} \<^item> And: @{thm [mode=iff] bit_and_iff [where ?'a = int, no_vars]} \<^item> Or: @{thm [mode=iff] bit_or_iff [where ?'a = int, no_vars]} \<^item> Xor: @{thm [mode=iff] bit_xor_iff [where ?'a = int, no_vars]} \<^item> Set a single bit: @{thm set_bit_def [where ?'a = int, no_vars]} \<^item> Unset a single bit: @{thm unset_bit_def [where ?'a = int, no_vars]} \<^item> Flip a single bit: @{thm flip_bit_def [where ?'a = int, no_vars]} \<^item> Signed truncation, or modulus centered around \<^term>\0::int\: @{thm [display] signed_take_bit_def [where ?'a = int, no_vars]} \<^item> (Bounded) conversion from and to a list of bits: @{thm [display] horner_sum_bit_eq_take_bit [where ?'a = int, no_vars]} Proper word types are introduced in theory \<^theory>\HOL-Word.Word\, with the following specific operations: \<^item> Standard arithmetic: @{term \(+) :: 'a::len word \ 'a word \ 'a word\}, @{term \uminus :: 'a::len word \ 'a word\}, @{term \(-) :: 'a::len word \ 'a word \ 'a word\}, @{term \(*) :: 'a::len word \ 'a word \ 'a word\}, @{term \0 :: 'a::len word\}, @{term \1 :: 'a::len word\}, numerals etc. \<^item> Standard bit operations: see above. \<^item> Conversion with unsigned interpretation of words: \<^item> @{term [source] \unsigned :: 'a::len word \ 'b::semiring_1\} \<^item> Important special cases as abbreviations: \<^item> @{term [source] \unat :: 'a::len word \ nat\} \<^item> @{term [source] \uint :: 'a::len word \ int\} \<^item> @{term [source] \ucast :: 'a::len word \ 'b::len word\} \<^item> Conversion with signed interpretation of words: \<^item> @{term [source] \signed :: 'a::len word \ 'b::ring_1\} \<^item> Important special cases as abbreviations: \<^item> @{term [source] \sint :: 'a::len word \ int\} \<^item> @{term [source] \scast :: 'a::len word \ 'b::len word\} \<^item> Operations with unsigned interpretation of words: \<^item> @{thm [mode=iff] word_le_nat_alt [no_vars]} \<^item> @{thm [mode=iff] word_less_nat_alt [no_vars]} \<^item> @{thm unat_div_distrib [no_vars]} \<^item> @{thm unat_drop_bit_eq [no_vars]} \<^item> @{thm unat_mod_distrib [no_vars]} \<^item> @{thm [mode=iff] udvd_iff_dvd [no_vars]} \<^item> Operations with signed interpretation of words: \<^item> @{thm [mode=iff] word_sle_eq [no_vars]} \<^item> @{thm [mode=iff] word_sless_alt [no_vars]} \<^item> @{thm sint_signed_drop_bit_eq [no_vars]} \<^item> Rotation and reversal: \<^item> @{term [source] \word_rotl :: nat \ 'a::len word \ 'a word\} \<^item> @{term [source] \word_rotr :: nat \ 'a::len word \ 'a word\} \<^item> @{term [source] \word_roti :: int \ 'a::len word \ 'a word\} \<^item> @{term [source] \word_reverse :: 'a::len word \ 'a word\} \<^item> Concatenation: @{term [source, display] \word_cat :: 'a::len word \ 'b::len word \ 'c::len word\} For proofs about words the following default strategies are applicable: \<^item> Using bit extensionality (facts \<^text>\bit_eq_iff\, \<^text>\bit_eqI\). \<^item> Using the @{method transfer} method. \ -subsection \More theories\ +subsection \More library theories\ text \ Note: currently, the theories listed here are hardly separate - entites since they import each other in various ways. + entities since they import each other in various ways. Always inspect them to understand what you pull in if you want to import one. \<^descr>[Syntax] \<^descr>[\<^theory>\Word_Lib.Hex_Words\] Printing word numerals as hexadecimal numerals. \<^descr>[\<^theory>\Word_Lib.Word_Type_Syntax\] Pretty type-sensitive syntax for cast operations. \<^descr>[\<^theory>\Word_Lib.Word_Syntax\] Specific ASCII syntax for prominent bit operations on word. \<^descr>[Proof tools] \<^descr>[\<^theory>\Word_Lib.Norm_Words\] Rewriting word numerals to normal forms. \<^descr>[\<^theory>\Word_Lib.Bitwise\] Method @{method word_bitwise} decomposes word equalities and inequalities into bit propositions. \<^descr>[\<^theory>\Word_Lib.Word_EqI\] Method @{method word_eqI_solve} decomposes word equalities and inequalities into bit propositions. \<^descr>[Operations] + \<^descr>[\<^theory>\HOL-Word.Misc_lsb\] + + The least significant bit as an alias: + @{thm [mode=iff] lsb_odd [where ?'a = int, no_vars]} + + \<^descr>[\<^theory>\HOL-Word.Misc_msb\] + + The most significant bit: + + \<^item> @{thm [mode=iff] msb_int_def [of k]} + + \<^item> @{thm [mode=iff] word_msb_sint [no_vars]} + + \<^item> @{thm [mode=iff] msb_word_iff_sless_0 [no_vars]} + + \<^item> @{thm [mode=iff] msb_word_iff_bit [no_vars]} + + \<^descr>[\<^theory>\HOL-Word.Traditional_Syntax\] + + Clones of existing operations decorated with + traditional syntax: + + \<^item> @{thm test_bit_eq_bit [no_vars]} + + \<^item> @{thm shiftl_eq_push_bit [no_vars]} + + \<^item> @{thm shiftr_eq_drop_bit [no_vars]} + + \<^item> @{thm sshiftr_eq [no_vars]} + \<^descr>[\<^theory>\Word_Lib.Word_Lib\] Various operations on word, particularly: \<^item> @{term [source] \(sdiv) :: 'a::len word \ 'a word \ 'a word\} \<^item> @{term [source] \(smod) :: 'a::len word \ 'a word \ 'a word\} \<^descr>[\<^theory>\Word_Lib.Aligned\] \ \<^item> @{thm [mode=iff] is_aligned_iff_udvd [no_vars]} \<^descr>[\<^theory>\Word_Lib.Word_Next\] \ \<^item> @{thm word_next_unfold [no_vars]} \<^item> @{thm word_prev_unfold [no_vars]} \<^descr>[Types] \<^descr>[\<^theory>\Word_Lib.Signed_Words\] - Formal tagging of word types with a \<^text>\signed\ marker; - currently it is not clear what practical relevance - this bears. + Formal tagging of word types with a \<^text>\signed\ marker. \<^descr>[Mechanisms] \<^descr>[\<^theory>\Word_Lib.Word_Enum\] More on explicit enumeration of word types. \<^descr>[Lemmas] Collections of lemmas: \<^descr>[\<^theory>\Word_Lib.Word_Lemmas\] generic. \<^descr>[\<^theory>\Word_Lib.Word_Lemmas_32\] for 32-bit words. \<^descr>[\<^theory>\Word_Lib.Word_Lemmas_64\] for 64-bit words. \ +subsection \More library sessions\ + +text \ + \<^descr>[\<^text>\Native_Word\] Makes machine words and machine arithmetic available for code generation. + It provides a common abstraction that hides the differences between the different target languages. + The code generator maps these operations to the APIs of the target languages. +\ + subsection \Legacy theories\ text \ The following theories contain material which has been factored out since it is not recommended to use it in new applications, mostly because matters can be expressed succinctly using already existing operations. This section gives some indication how to migrate away from those theories. However theorem coverage may still be terse in some cases. - \<^descr>[\<^theory>\HOL-Word.Misc_lsb\] - - A mere alias: @{thm [mode=iff] lsb_odd [where ?'a = int, no_vars]} - - \<^descr>[\<^theory>\HOL-Word.Misc_msb\] - - An alias for the most significant bit; suggested replacements: - - \<^item> @{thm [mode=iff] msb_int_def [of k]} - - \<^item> @{thm [mode=iff] word_msb_sint [no_vars]} - - \<^item> @{thm [mode=iff] msb_word_iff_sless_0 [no_vars]} - - \<^item> @{thm [mode=iff] msb_word_iff_bit [no_vars]} \<^descr>[\<^theory>\HOL-Word.Misc_set_bit\] - An alias: @{thm set_bit_eq [no_vars]} + Kind of an alias: @{thm set_bit_eq [no_vars]} \<^descr>[\<^theory>\HOL-Word.Misc_Typedef\] - An invasive low-level extension to HOL typedef to provide - conversions along type morphisms. - - \<^descr>[\<^theory>\HOL-Word.Traditional_Syntax\] - - Clones of existing operations decorated with - traditional syntax: - - \<^item> @{thm test_bit_eq_bit [no_vars]} - - \<^item> @{thm shiftl_eq_push_bit [no_vars]} - - \<^item> @{thm shiftr_eq_drop_bit [no_vars]} + A low-level extension to HOL typedef providing + conversions along type morphisms. The @{method transfer} method + seems to be sufficient for most applications though. \<^descr>[\<^theory>\HOL-Word.Bit_Comprehension\] Comprehension syntax for bit values over predicates \<^typ>\nat \ bool\. For \<^typ>\'a::len word\, straightforward alternatives exist; difficult to handle for \<^typ>\int\. \<^descr>[\<^theory>\HOL-Word.Reversed_Bit_Lists\] Representation of bit values as explicit list in \<^emph>\reversed\ order. This should rarely be necessary: the \<^const>\bit\ projection should be sufficient in most cases. In case explicit lists are needed, existing operations can be used: @{thm [display] horner_sum_bit_eq_take_bit [where ?'a = int, no_vars]} \ (*<*) end (*>*)