--- a/src/HOL/ROOT Thu Aug 06 17:51:37 2020 +0200
+++ b/src/HOL/ROOT Thu Aug 06 15:37:14 2020 +0000
@@ -612,6 +612,8 @@
description "
Miscellaneous examples for Higher-Order Logic.
"
+ sessions
+ "HOL-Word"
theories
Antiquote
Argo_Examples
@@ -693,7 +695,7 @@
Triangular_Numbers
Unification
While_Combinator_Example
- Word
+ Word_Conversions
veriT_Preprocessing
theories [skip_proofs = false]
SAT_Examples
--- a/src/HOL/Word/Word.thy Thu Aug 06 17:51:37 2020 +0200
+++ b/src/HOL/Word/Word.thy Thu Aug 06 15:37:14 2020 +0000
@@ -415,11 +415,11 @@
begin
lemma [transfer_rule]:
- "((=) ===> (pcr_word :: int \<Rightarrow> 'a::len word \<Rightarrow> bool)) of_bool of_bool"
+ "((=) ===> pcr_word) of_bool of_bool"
by transfer_prover
lemma [transfer_rule]:
- "((=) ===> (pcr_word :: int \<Rightarrow> 'a::len word \<Rightarrow> bool)) numeral numeral"
+ "((=) ===> pcr_word) numeral numeral"
by transfer_prover
lemma [transfer_rule]:
--- a/src/HOL/ex/Bit_Lists.thy Thu Aug 06 17:51:37 2020 +0200
+++ b/src/HOL/ex/Bit_Lists.thy Thu Aug 06 15:37:14 2020 +0000
@@ -5,7 +5,7 @@
theory Bit_Lists
imports
- Word "HOL-Library.More_List"
+ Word_Conversions "HOL-Library.More_List"
begin
subsection \<open>Fragments of algebraic bit representations\<close>
--- a/src/HOL/ex/Word.thy Thu Aug 06 17:51:37 2020 +0200
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,670 +0,0 @@
-(* Author: Florian Haftmann, TUM
-*)
-
-section \<open>Proof of concept for algebraically founded bit word types\<close>
-
-theory Word
- imports
- Main
- "HOL-Library.Type_Length"
- "HOL-Library.Bit_Operations"
-begin
-
-subsection \<open>Bit strings as quotient type\<close>
-
-subsubsection \<open>Basic properties\<close>
-
-quotient_type (overloaded) 'a word = int / "\<lambda>k l. take_bit LENGTH('a) k = take_bit LENGTH('a::len) l"
- by (auto intro!: equivpI reflpI sympI transpI)
-
-instantiation word :: (len) "{semiring_numeral, comm_semiring_0, comm_ring}"
-begin
-
-lift_definition zero_word :: "'a word"
- is 0
- .
-
-lift_definition one_word :: "'a word"
- is 1
- .
-
-lift_definition plus_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
- is plus
- by (subst take_bit_add [symmetric]) (simp add: take_bit_add)
-
-lift_definition uminus_word :: "'a word \<Rightarrow> 'a word"
- is uminus
- by (subst take_bit_minus [symmetric]) (simp add: take_bit_minus)
-
-lift_definition minus_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
- is minus
- by (subst take_bit_diff [symmetric]) (simp add: take_bit_diff)
-
-lift_definition times_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
- is times
- by (auto simp add: take_bit_eq_mod intro: mod_mult_cong)
-
-instance
- by standard (transfer; simp add: algebra_simps)+
-
-end
-
-instance word :: (len) comm_ring_1
- by standard (transfer; simp)+
-
-quickcheck_generator word
- constructors:
- "zero_class.zero :: ('a::len) word",
- "numeral :: num \<Rightarrow> ('a::len) word",
- "uminus :: ('a::len) word \<Rightarrow> ('a::len) word"
-
-context
- includes lifting_syntax
- notes power_transfer [transfer_rule]
-begin
-
-lemma power_transfer_word [transfer_rule]:
- \<open>(pcr_word ===> (=) ===> pcr_word) (^) (^)\<close>
- by transfer_prover
-
-end
-
-
-subsubsection \<open>Conversions\<close>
-
-context
- includes lifting_syntax
- notes
- transfer_rule_of_bool [transfer_rule]
- transfer_rule_numeral [transfer_rule]
- transfer_rule_of_nat [transfer_rule]
- transfer_rule_of_int [transfer_rule]
-begin
-
-lemma [transfer_rule]:
- "((=) ===> (pcr_word :: int \<Rightarrow> 'a::len word \<Rightarrow> bool)) of_bool of_bool"
- by transfer_prover
-
-lemma [transfer_rule]:
- "((=) ===> (pcr_word :: int \<Rightarrow> 'a::len word \<Rightarrow> bool)) numeral numeral"
- by transfer_prover
-
-lemma [transfer_rule]:
- "((=) ===> pcr_word) int of_nat"
- by transfer_prover
-
-lemma [transfer_rule]:
- "((=) ===> pcr_word) (\<lambda>k. k) of_int"
-proof -
- have "((=) ===> pcr_word) of_int of_int"
- by transfer_prover
- then show ?thesis by (simp add: id_def)
-qed
-
-end
-
-lemma abs_word_eq:
- "abs_word = of_int"
- by (rule ext) (transfer, rule)
-
-context semiring_1
-begin
-
-lift_definition unsigned :: "'b::len word \<Rightarrow> 'a"
- is "of_nat \<circ> nat \<circ> take_bit LENGTH('b)"
- by simp
-
-lemma unsigned_0 [simp]:
- "unsigned 0 = 0"
- by transfer simp
-
-end
-
-context semiring_char_0
-begin
-
-lemma word_eq_iff_unsigned:
- "a = b \<longleftrightarrow> unsigned a = unsigned b"
- by safe (transfer; simp add: eq_nat_nat_iff)
-
-end
-
-instantiation word :: (len) equal
-begin
-
-definition equal_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> bool"
- where "equal_word a b \<longleftrightarrow> (unsigned a :: int) = unsigned b"
-
-instance proof
- fix a b :: "'a word"
- show "HOL.equal a b \<longleftrightarrow> a = b"
- using word_eq_iff_unsigned [of a b] by (auto simp add: equal_word_def)
-qed
-
-end
-
-context ring_1
-begin
-
-lift_definition signed :: "'b::len word \<Rightarrow> 'a"
- is "of_int \<circ> signed_take_bit (LENGTH('b) - 1)"
- by (cases \<open>LENGTH('b)\<close>)
- (simp_all add: signed_take_bit_eq_iff_take_bit_eq [symmetric])
-
-lemma signed_0 [simp]:
- "signed 0 = 0"
- by transfer simp
-
-end
-
-lemma unsigned_of_nat [simp]:
- "unsigned (of_nat n :: 'a word) = take_bit LENGTH('a::len) n"
- by transfer (simp add: nat_eq_iff take_bit_eq_mod zmod_int)
-
-lemma of_nat_unsigned [simp]:
- "of_nat (unsigned a) = a"
- by transfer simp
-
-lemma of_int_unsigned [simp]:
- "of_int (unsigned a) = a"
- by transfer simp
-
-lemma unsigned_nat_less:
- \<open>unsigned a < (2 ^ LENGTH('a) :: nat)\<close> for a :: \<open>'a::len word\<close>
- by transfer (simp add: take_bit_eq_mod)
-
-lemma unsigned_int_less:
- \<open>unsigned a < (2 ^ LENGTH('a) :: int)\<close> for a :: \<open>'a::len word\<close>
- by transfer (simp add: take_bit_eq_mod)
-
-context ring_char_0
-begin
-
-lemma word_eq_iff_signed:
- "a = b \<longleftrightarrow> signed a = signed b"
- by safe (transfer; auto simp add: signed_take_bit_eq_iff_take_bit_eq)
-
-end
-
-lemma signed_of_int [simp]:
- "signed (of_int k :: 'a word) = signed_take_bit (LENGTH('a::len) - 1) k"
- by transfer simp
-
-lemma of_int_signed [simp]:
- "of_int (signed a) = a"
- by transfer (simp_all add: take_bit_signed_take_bit)
-
-
-subsubsection \<open>Properties\<close>
-
-lemma exp_eq_zero_iff:
- \<open>(2 :: 'a::len word) ^ n = 0 \<longleftrightarrow> LENGTH('a) \<le> n\<close>
- by transfer simp
-
-
-subsubsection \<open>Division\<close>
-
-instantiation word :: (len) modulo
-begin
-
-lift_definition divide_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
- is "\<lambda>a b. take_bit LENGTH('a) a div take_bit LENGTH('a) b"
- by simp
-
-lift_definition modulo_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
- is "\<lambda>a b. take_bit LENGTH('a) a mod take_bit LENGTH('a) b"
- by simp
-
-instance ..
-
-end
-
-lemma zero_word_div_eq [simp]:
- \<open>0 div a = 0\<close> for a :: \<open>'a::len word\<close>
- by transfer simp
-
-lemma div_zero_word_eq [simp]:
- \<open>a div 0 = 0\<close> for a :: \<open>'a::len word\<close>
- by transfer simp
-
-context
- includes lifting_syntax
-begin
-
-lemma [transfer_rule]:
- "(pcr_word ===> (\<longleftrightarrow>)) even ((dvd) 2 :: 'a::len word \<Rightarrow> bool)"
-proof -
- have even_word_unfold: "even k \<longleftrightarrow> (\<exists>l. take_bit LENGTH('a) k = take_bit LENGTH('a) (2 * l))" (is "?P \<longleftrightarrow> ?Q")
- for k :: int
- proof
- assume ?P
- then show ?Q
- by auto
- next
- assume ?Q
- then obtain l where "take_bit LENGTH('a) k = take_bit LENGTH('a) (2 * l)" ..
- then have "even (take_bit LENGTH('a) k)"
- by simp
- then show ?P
- by simp
- qed
- show ?thesis by (simp only: even_word_unfold [abs_def] dvd_def [where ?'a = "'a word", abs_def])
- transfer_prover
-qed
-
-end
-
-instance word :: (len) semiring_modulo
-proof
- show "a div b * b + a mod b = a" for a b :: "'a word"
- proof transfer
- fix k l :: int
- define r :: int where "r = 2 ^ LENGTH('a)"
- then have r: "take_bit LENGTH('a) k = k mod r" for k
- by (simp add: take_bit_eq_mod)
- have "k mod r = ((k mod r) div (l mod r) * (l mod r)
- + (k mod r) mod (l mod r)) mod r"
- by (simp add: div_mult_mod_eq)
- also have "... = (((k mod r) div (l mod r) * (l mod r)) mod r
- + (k mod r) mod (l mod r)) mod r"
- by (simp add: mod_add_left_eq)
- also have "... = (((k mod r) div (l mod r) * l) mod r
- + (k mod r) mod (l mod r)) mod r"
- by (simp add: mod_mult_right_eq)
- finally have "k mod r = ((k mod r) div (l mod r) * l
- + (k mod r) mod (l mod r)) mod r"
- by (simp add: mod_simps)
- with r show "take_bit LENGTH('a) (take_bit LENGTH('a) k div take_bit LENGTH('a) l * l
- + take_bit LENGTH('a) k mod take_bit LENGTH('a) l) = take_bit LENGTH('a) k"
- by simp
- qed
-qed
-
-instance word :: (len) semiring_parity
-proof
- show "\<not> 2 dvd (1::'a word)"
- by transfer simp
- show even_iff_mod_2_eq_0: "2 dvd a \<longleftrightarrow> a mod 2 = 0"
- for a :: "'a word"
- by transfer (simp_all add: mod_2_eq_odd take_bit_Suc)
- show "\<not> 2 dvd a \<longleftrightarrow> a mod 2 = 1"
- for a :: "'a word"
- by transfer (simp_all add: mod_2_eq_odd take_bit_Suc)
-qed
-
-
-subsubsection \<open>Orderings\<close>
-
-instantiation word :: (len) linorder
-begin
-
-lift_definition less_eq_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> bool"
- is "\<lambda>a b. take_bit LENGTH('a) a \<le> take_bit LENGTH('a) b"
- by simp
-
-lift_definition less_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> bool"
- is "\<lambda>a b. take_bit LENGTH('a) a < take_bit LENGTH('a) b"
- by simp
-
-instance
- by standard (transfer; auto)+
-
-end
-
-context linordered_semidom
-begin
-
-lemma word_less_eq_iff_unsigned:
- "a \<le> b \<longleftrightarrow> unsigned a \<le> unsigned b"
- by (transfer fixing: less_eq) (simp add: nat_le_eq_zle)
-
-lemma word_less_iff_unsigned:
- "a < b \<longleftrightarrow> unsigned a < unsigned b"
- by (transfer fixing: less) (auto dest: preorder_class.le_less_trans [OF take_bit_nonnegative])
-
-end
-
-lemma word_greater_zero_iff:
- \<open>a > 0 \<longleftrightarrow> a \<noteq> 0\<close> for a :: \<open>'a::len word\<close>
- by transfer (simp add: less_le)
-
-lemma of_nat_word_eq_iff:
- \<open>of_nat m = (of_nat n :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) m = take_bit LENGTH('a) n\<close>
- by transfer (simp add: take_bit_of_nat)
-
-lemma of_nat_word_less_eq_iff:
- \<open>of_nat m \<le> (of_nat n :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) m \<le> take_bit LENGTH('a) n\<close>
- by transfer (simp add: take_bit_of_nat)
-
-lemma of_nat_word_less_iff:
- \<open>of_nat m < (of_nat n :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) m < take_bit LENGTH('a) n\<close>
- by transfer (simp add: take_bit_of_nat)
-
-lemma of_nat_word_eq_0_iff:
- \<open>of_nat n = (0 :: 'a::len word) \<longleftrightarrow> 2 ^ LENGTH('a) dvd n\<close>
- using of_nat_word_eq_iff [where ?'a = 'a, of n 0] by (simp add: take_bit_eq_0_iff)
-
-lemma of_int_word_eq_iff:
- \<open>of_int k = (of_int l :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) k = take_bit LENGTH('a) l\<close>
- by transfer rule
-
-lemma of_int_word_less_eq_iff:
- \<open>of_int k \<le> (of_int l :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) k \<le> take_bit LENGTH('a) l\<close>
- by transfer rule
-
-lemma of_int_word_less_iff:
- \<open>of_int k < (of_int l :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) k < take_bit LENGTH('a) l\<close>
- by transfer rule
-
-lemma of_int_word_eq_0_iff:
- \<open>of_int k = (0 :: 'a::len word) \<longleftrightarrow> 2 ^ LENGTH('a) dvd k\<close>
- using of_int_word_eq_iff [where ?'a = 'a, of k 0] by (simp add: take_bit_eq_0_iff)
-
-
-subsection \<open>Bit structure on \<^typ>\<open>'a word\<close>\<close>
-
-lemma word_bit_induct [case_names zero even odd]:
- \<open>P a\<close> if word_zero: \<open>P 0\<close>
- and word_even: \<open>\<And>a. P a \<Longrightarrow> 0 < a \<Longrightarrow> a < 2 ^ (LENGTH('a) - 1) \<Longrightarrow> P (2 * a)\<close>
- and word_odd: \<open>\<And>a. P a \<Longrightarrow> a < 2 ^ (LENGTH('a) - 1) \<Longrightarrow> P (1 + 2 * a)\<close>
- for P and a :: \<open>'a::len word\<close>
-proof -
- define m :: nat where \<open>m = LENGTH('a) - 1\<close>
- then have l: \<open>LENGTH('a) = Suc m\<close>
- by simp
- define n :: nat where \<open>n = unsigned a\<close>
- then have \<open>n < 2 ^ LENGTH('a)\<close>
- by (simp add: unsigned_nat_less)
- then have \<open>n < 2 * 2 ^ m\<close>
- by (simp add: l)
- then have \<open>P (of_nat n)\<close>
- proof (induction n rule: nat_bit_induct)
- case zero
- show ?case
- by simp (rule word_zero)
- next
- case (even n)
- then have \<open>n < 2 ^ m\<close>
- by simp
- with even.IH have \<open>P (of_nat n)\<close>
- by simp
- moreover from \<open>n < 2 ^ m\<close> even.hyps have \<open>0 < (of_nat n :: 'a word)\<close>
- by (auto simp add: word_greater_zero_iff of_nat_word_eq_0_iff l)
- moreover from \<open>n < 2 ^ m\<close> have \<open>(of_nat n :: 'a word) < 2 ^ (LENGTH('a) - 1)\<close>
- using of_nat_word_less_iff [where ?'a = 'a, of n \<open>2 ^ m\<close>]
- by (cases \<open>m = 0\<close>) (simp_all add: not_less take_bit_eq_self ac_simps l)
- ultimately have \<open>P (2 * of_nat n)\<close>
- by (rule word_even)
- then show ?case
- by simp
- next
- case (odd n)
- then have \<open>Suc n \<le> 2 ^ m\<close>
- by simp
- with odd.IH have \<open>P (of_nat n)\<close>
- by simp
- moreover from \<open>Suc n \<le> 2 ^ m\<close> have \<open>(of_nat n :: 'a word) < 2 ^ (LENGTH('a) - 1)\<close>
- using of_nat_word_less_iff [where ?'a = 'a, of n \<open>2 ^ m\<close>]
- by (cases \<open>m = 0\<close>) (simp_all add: not_less take_bit_eq_self ac_simps l)
- ultimately have \<open>P (1 + 2 * of_nat n)\<close>
- by (rule word_odd)
- then show ?case
- by simp
- qed
- then show ?thesis
- by (simp add: n_def)
-qed
-
-lemma bit_word_half_eq:
- \<open>(of_bool b + a * 2) div 2 = a\<close>
- if \<open>a < 2 ^ (LENGTH('a) - Suc 0)\<close>
- for a :: \<open>'a::len word\<close>
-proof (cases \<open>2 \<le> LENGTH('a::len)\<close>)
- case False
- have \<open>of_bool (odd k) < (1 :: int) \<longleftrightarrow> even k\<close> for k :: int
- by auto
- with False that show ?thesis
- by transfer (simp add: eq_iff)
-next
- case True
- obtain n where length: \<open>LENGTH('a) = Suc n\<close>
- by (cases \<open>LENGTH('a)\<close>) simp_all
- show ?thesis proof (cases b)
- case False
- moreover have \<open>a * 2 div 2 = a\<close>
- using that proof transfer
- fix k :: int
- from length have \<open>k * 2 mod 2 ^ LENGTH('a) = (k mod 2 ^ n) * 2\<close>
- by simp
- moreover assume \<open>take_bit LENGTH('a) k < take_bit LENGTH('a) (2 ^ (LENGTH('a) - Suc 0))\<close>
- with \<open>LENGTH('a) = Suc n\<close>
- have \<open>k mod 2 ^ LENGTH('a) = k mod 2 ^ n\<close>
- by (simp add: take_bit_eq_mod divmod_digit_0)
- ultimately have \<open>take_bit LENGTH('a) (k * 2) = take_bit LENGTH('a) k * 2\<close>
- by (simp add: take_bit_eq_mod)
- with True show \<open>take_bit LENGTH('a) (take_bit LENGTH('a) (k * 2) div take_bit LENGTH('a) 2)
- = take_bit LENGTH('a) k\<close>
- by simp
- qed
- ultimately show ?thesis
- by simp
- next
- case True
- moreover have \<open>(1 + a * 2) div 2 = a\<close>
- using that proof transfer
- fix k :: int
- from length have \<open>(1 + k * 2) mod 2 ^ LENGTH('a) = 1 + (k mod 2 ^ n) * 2\<close>
- using pos_zmod_mult_2 [of \<open>2 ^ n\<close> k] by (simp add: ac_simps)
- moreover assume \<open>take_bit LENGTH('a) k < take_bit LENGTH('a) (2 ^ (LENGTH('a) - Suc 0))\<close>
- with \<open>LENGTH('a) = Suc n\<close>
- have \<open>k mod 2 ^ LENGTH('a) = k mod 2 ^ n\<close>
- by (simp add: take_bit_eq_mod divmod_digit_0)
- ultimately have \<open>take_bit LENGTH('a) (1 + k * 2) = 1 + take_bit LENGTH('a) k * 2\<close>
- by (simp add: take_bit_eq_mod)
- with True show \<open>take_bit LENGTH('a) (take_bit LENGTH('a) (1 + k * 2) div take_bit LENGTH('a) 2)
- = take_bit LENGTH('a) k\<close>
- by (auto simp add: take_bit_Suc)
- qed
- ultimately show ?thesis
- by simp
- qed
-qed
-
-lemma even_mult_exp_div_word_iff:
- \<open>even (a * 2 ^ m div 2 ^ n) \<longleftrightarrow> \<not> (
- m \<le> n \<and>
- n < LENGTH('a) \<and> odd (a div 2 ^ (n - m)))\<close> for a :: \<open>'a::len word\<close>
- by transfer
- (auto simp flip: drop_bit_eq_div simp add: even_drop_bit_iff_not_bit bit_take_bit_iff,
- simp_all flip: push_bit_eq_mult add: bit_push_bit_iff_int)
-
-instantiation word :: (len) semiring_bits
-begin
-
-lift_definition bit_word :: \<open>'a word \<Rightarrow> nat \<Rightarrow> bool\<close>
- is \<open>\<lambda>k n. n < LENGTH('a) \<and> bit k n\<close>
-proof
- fix k l :: int and n :: nat
- assume *: \<open>take_bit LENGTH('a) k = take_bit LENGTH('a) l\<close>
- show \<open>n < LENGTH('a) \<and> bit k n \<longleftrightarrow> n < LENGTH('a) \<and> bit l n\<close>
- proof (cases \<open>n < LENGTH('a)\<close>)
- case True
- from * have \<open>bit (take_bit LENGTH('a) k) n \<longleftrightarrow> bit (take_bit LENGTH('a) l) n\<close>
- by simp
- then show ?thesis
- by (simp add: bit_take_bit_iff)
- next
- case False
- then show ?thesis
- by simp
- qed
-qed
-
-instance proof
- show \<open>P a\<close> if stable: \<open>\<And>a. a div 2 = a \<Longrightarrow> P a\<close>
- and rec: \<open>\<And>a b. P a \<Longrightarrow> (of_bool b + 2 * a) div 2 = a \<Longrightarrow> P (of_bool b + 2 * a)\<close>
- for P and a :: \<open>'a word\<close>
- proof (induction a rule: word_bit_induct)
- case zero
- from stable [of 0] show ?case
- by simp
- next
- case (even a)
- with rec [of a False] show ?case
- using bit_word_half_eq [of a False] by (simp add: ac_simps)
- next
- case (odd a)
- with rec [of a True] show ?case
- using bit_word_half_eq [of a True] by (simp add: ac_simps)
- qed
- show \<open>bit a n \<longleftrightarrow> odd (a div 2 ^ n)\<close> for a :: \<open>'a word\<close> and n
- by transfer (simp flip: drop_bit_eq_div add: drop_bit_take_bit bit_iff_odd_drop_bit)
- show \<open>0 div a = 0\<close>
- for a :: \<open>'a word\<close>
- by transfer simp
- show \<open>a div 1 = a\<close>
- for a :: \<open>'a word\<close>
- by transfer simp
- show \<open>a mod b div b = 0\<close>
- for a b :: \<open>'a word\<close>
- apply transfer
- apply (simp add: take_bit_eq_mod)
- apply (subst (3) mod_pos_pos_trivial [of _ \<open>2 ^ LENGTH('a)\<close>])
- apply simp_all
- apply (metis le_less mod_by_0 pos_mod_conj zero_less_numeral zero_less_power)
- using pos_mod_bound [of \<open>2 ^ LENGTH('a)\<close>] apply simp
- proof -
- fix aa :: int and ba :: int
- have f1: "\<And>i n. (i::int) mod 2 ^ n = 0 \<or> 0 < i mod 2 ^ n"
- by (metis le_less take_bit_eq_mod take_bit_nonnegative)
- have "(0::int) < 2 ^ len_of (TYPE('a)::'a itself) \<and> ba mod 2 ^ len_of (TYPE('a)::'a itself) \<noteq> 0 \<or> aa mod 2 ^ len_of (TYPE('a)::'a itself) mod (ba mod 2 ^ len_of (TYPE('a)::'a itself)) < 2 ^ len_of (TYPE('a)::'a itself)"
- by (metis (no_types) mod_by_0 unique_euclidean_semiring_numeral_class.pos_mod_bound zero_less_numeral zero_less_power)
- then show "aa mod 2 ^ len_of (TYPE('a)::'a itself) mod (ba mod 2 ^ len_of (TYPE('a)::'a itself)) < 2 ^ len_of (TYPE('a)::'a itself)"
- using f1 by (meson le_less less_le_trans unique_euclidean_semiring_numeral_class.pos_mod_bound)
- qed
- show \<open>(1 + a) div 2 = a div 2\<close>
- if \<open>even a\<close>
- for a :: \<open>'a word\<close>
- using that by transfer
- (auto dest: le_Suc_ex simp add: mod_2_eq_odd take_bit_Suc elim!: evenE)
- show \<open>(2 :: 'a word) ^ m div 2 ^ n = of_bool ((2 :: 'a word) ^ m \<noteq> 0 \<and> n \<le> m) * 2 ^ (m - n)\<close>
- for m n :: nat
- by transfer (simp, simp add: exp_div_exp_eq)
- show "a div 2 ^ m div 2 ^ n = a div 2 ^ (m + n)"
- for a :: "'a word" and m n :: nat
- apply transfer
- apply (auto simp add: not_less take_bit_drop_bit ac_simps simp flip: drop_bit_eq_div)
- apply (simp add: drop_bit_take_bit)
- done
- show "a mod 2 ^ m mod 2 ^ n = a mod 2 ^ min m n"
- for a :: "'a word" and m n :: nat
- by transfer (auto simp flip: take_bit_eq_mod simp add: ac_simps)
- show \<open>a * 2 ^ m mod 2 ^ n = a mod 2 ^ (n - m) * 2 ^ m\<close>
- if \<open>m \<le> n\<close> for a :: "'a word" and m n :: nat
- using that apply transfer
- apply (auto simp flip: take_bit_eq_mod)
- apply (auto simp flip: push_bit_eq_mult simp add: push_bit_take_bit split: split_min_lin)
- done
- show \<open>a div 2 ^ n mod 2 ^ m = a mod (2 ^ (n + m)) div 2 ^ n\<close>
- for a :: "'a word" and m n :: nat
- by transfer (auto simp add: not_less take_bit_drop_bit ac_simps simp flip: take_bit_eq_mod drop_bit_eq_div split: split_min_lin)
- show \<open>even ((2 ^ m - 1) div (2::'a word) ^ n) \<longleftrightarrow> 2 ^ n = (0::'a word) \<or> m \<le> n\<close>
- for m n :: nat
- by transfer (auto simp add: take_bit_of_mask even_mask_div_iff)
- show \<open>even (a * 2 ^ m div 2 ^ n) \<longleftrightarrow> n < m \<or> (2::'a word) ^ n = 0 \<or> m \<le> n \<and> even (a div 2 ^ (n - m))\<close>
- for a :: \<open>'a word\<close> and m n :: nat
- proof transfer
- show \<open>even (take_bit LENGTH('a) (k * 2 ^ m) div take_bit LENGTH('a) (2 ^ n)) \<longleftrightarrow>
- n < m
- \<or> take_bit LENGTH('a) ((2::int) ^ n) = take_bit LENGTH('a) 0
- \<or> (m \<le> n \<and> even (take_bit LENGTH('a) k div take_bit LENGTH('a) (2 ^ (n - m))))\<close>
- for m n :: nat and k l :: int
- by (auto simp flip: take_bit_eq_mod drop_bit_eq_div push_bit_eq_mult
- simp add: div_push_bit_of_1_eq_drop_bit drop_bit_take_bit drop_bit_push_bit_int [of n m])
- qed
-qed
-
-end
-
-instantiation word :: (len) semiring_bit_shifts
-begin
-
-lift_definition push_bit_word :: \<open>nat \<Rightarrow> 'a word \<Rightarrow> 'a word\<close>
- is push_bit
-proof -
- show \<open>take_bit LENGTH('a) (push_bit n k) = take_bit LENGTH('a) (push_bit n l)\<close>
- if \<open>take_bit LENGTH('a) k = take_bit LENGTH('a) l\<close> for k l :: int and n :: nat
- proof -
- from that
- have \<open>take_bit (LENGTH('a) - n) (take_bit LENGTH('a) k)
- = take_bit (LENGTH('a) - n) (take_bit LENGTH('a) l)\<close>
- by simp
- moreover have \<open>min (LENGTH('a) - n) LENGTH('a) = LENGTH('a) - n\<close>
- by simp
- ultimately show ?thesis
- by (simp add: take_bit_push_bit)
- qed
-qed
-
-lift_definition drop_bit_word :: \<open>nat \<Rightarrow> 'a word \<Rightarrow> 'a word\<close>
- is \<open>\<lambda>n. drop_bit n \<circ> take_bit LENGTH('a)\<close>
- by (simp add: take_bit_eq_mod)
-
-lift_definition take_bit_word :: \<open>nat \<Rightarrow> 'a word \<Rightarrow> 'a word\<close>
- is \<open>\<lambda>n. take_bit (min LENGTH('a) n)\<close>
- by (simp add: ac_simps) (simp only: flip: take_bit_take_bit)
-
-instance proof
- show \<open>push_bit n a = a * 2 ^ n\<close> for n :: nat and a :: "'a word"
- by transfer (simp add: push_bit_eq_mult)
- show \<open>drop_bit n a = a div 2 ^ n\<close> for n :: nat and a :: "'a word"
- by transfer (simp flip: drop_bit_eq_div add: drop_bit_take_bit)
- show \<open>take_bit n a = a mod 2 ^ n\<close> for n :: nat and a :: \<open>'a word\<close>
- by transfer (auto simp flip: take_bit_eq_mod)
-qed
-
-end
-
-instantiation word :: (len) ring_bit_operations
-begin
-
-lift_definition not_word :: "'a word \<Rightarrow> 'a word"
- is not
- by (simp add: take_bit_not_iff)
-
-lift_definition and_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
- is \<open>and\<close>
- by simp
-
-lift_definition or_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
- is or
- by simp
-
-lift_definition xor_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
- is xor
- by simp
-
-lift_definition mask_word :: \<open>nat \<Rightarrow> 'a word\<close>
- is mask .
-
-instance by (standard; transfer)
- (auto simp add: minus_eq_not_minus_1 mask_eq_exp_minus_1
- bit_not_iff bit_and_iff bit_or_iff bit_xor_iff)
-
-end
-
-definition even_word :: \<open>'a::len word \<Rightarrow> bool\<close>
- where [code_abbrev]: \<open>even_word = even\<close>
-
-lemma even_word_iff [code]:
- \<open>even_word a \<longleftrightarrow> a AND 1 = 0\<close>
- by (simp add: even_word_def and_one_eq even_iff_mod_2_eq_zero)
-
-lemma bit_word_iff_drop_bit_and [code]:
- \<open>bit a n \<longleftrightarrow> drop_bit n a AND 1 = 1\<close> for a :: \<open>'a::len word\<close>
- by (simp add: bit_iff_odd_drop_bit odd_iff_mod_2_eq_one and_one_eq)
-
-lifting_update word.lifting
-lifting_forget word.lifting
-
-end
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/HOL/ex/Word_Conversions.thy Thu Aug 06 15:37:14 2020 +0000
@@ -0,0 +1,204 @@
+(* Author: Florian Haftmann, TUM
+*)
+
+section \<open>Proof of concept for conversions for algebraically founded bit word types\<close>
+
+theory Word_Conversions
+ imports
+ Main
+ "HOL-Library.Type_Length"
+ "HOL-Library.Bit_Operations"
+ "HOL-Word.Word"
+begin
+
+context semiring_1
+begin
+
+lift_definition unsigned :: \<open>'b::len word \<Rightarrow> 'a\<close>
+ is \<open>of_nat \<circ> nat \<circ> take_bit LENGTH('b)\<close>
+ by simp
+
+lemma unsigned_0 [simp]:
+ \<open>unsigned 0 = 0\<close>
+ by transfer simp
+
+lemma unsigned_1 [simp]:
+ \<open>unsigned 1 = 1\<close>
+ by transfer simp
+
+end
+
+lemma unat_unsigned:
+ \<open>unat = unsigned\<close>
+ by transfer simp
+
+lemma uint_unsigned:
+ \<open>uint = unsigned\<close>
+ by transfer (simp add: fun_eq_iff)
+
+context semiring_char_0
+begin
+
+lemma unsigned_word_eqI:
+ \<open>v = w\<close> if \<open>unsigned v = unsigned w\<close>
+ using that by transfer (simp add: eq_nat_nat_iff)
+
+lemma word_eq_iff_unsigned:
+ \<open>v = w \<longleftrightarrow> unsigned v = unsigned w\<close>
+ by (auto intro: unsigned_word_eqI)
+
+end
+
+context ring_1
+begin
+
+lift_definition signed :: \<open>'b::len word \<Rightarrow> 'a\<close>
+ is \<open>of_int \<circ> signed_take_bit (LENGTH('b) - 1)\<close>
+ by (simp flip: signed_take_bit_decr_length_iff)
+
+lemma signed_0 [simp]:
+ \<open>signed 0 = 0\<close>
+ by transfer simp
+
+lemma signed_1 [simp]:
+ \<open>signed (1 :: 'b::len word) = (if LENGTH('b) = 1 then - 1 else 1)\<close>
+ by (transfer fixing: uminus)
+ (simp_all add: signed_take_bit_eq not_le Suc_lessI)
+
+lemma signed_minus_1 [simp]:
+ \<open>signed (- 1 :: 'b::len word) = - 1\<close>
+ by (transfer fixing: uminus) simp
+
+end
+
+lemma sint_signed:
+ \<open>sint = signed\<close>
+ by transfer simp
+
+context ring_char_0
+begin
+
+lemma signed_word_eqI:
+ \<open>v = w\<close> if \<open>signed v = signed w\<close>
+ using that by transfer (simp flip: signed_take_bit_decr_length_iff)
+
+lemma word_eq_iff_signed:
+ \<open>v = w \<longleftrightarrow> signed v = signed w\<close>
+ by (auto intro: signed_word_eqI)
+
+end
+
+abbreviation nat_of_word :: \<open>'a::len word \<Rightarrow> nat\<close>
+ where \<open>nat_of_word \<equiv> unsigned\<close>
+
+abbreviation unsigned_int :: \<open>'a::len word \<Rightarrow> int\<close>
+ where \<open>unsigned_int \<equiv> unsigned\<close>
+
+abbreviation signed_int :: \<open>'a::len word \<Rightarrow> int\<close>
+ where \<open>signed_int \<equiv> signed\<close>
+
+abbreviation word_of_nat :: \<open>nat \<Rightarrow> 'a::len word\<close>
+ where \<open>word_of_nat \<equiv> of_nat\<close>
+
+abbreviation word_of_int :: \<open>int \<Rightarrow> 'a::len word\<close>
+ where \<open>word_of_int \<equiv> of_int\<close>
+
+text \<open>TODO rework names from here\<close>
+
+lemma unsigned_of_nat [simp]:
+ \<open>unsigned (of_nat n :: 'a::len word) = take_bit LENGTH('a) n\<close>
+ by transfer (simp add: nat_eq_iff take_bit_of_nat)
+
+lemma of_nat_unsigned [simp]:
+ \<open>of_nat (unsigned w) = w\<close>
+ by transfer simp
+
+lemma of_int_unsigned [simp]:
+ \<open>of_int (unsigned w) = w\<close>
+ by transfer simp
+
+lemma unsigned_int_greater_eq:
+ \<open>(0::int) \<le> unsigned w\<close> for w :: \<open>'a::len word\<close>
+ by transfer simp
+
+lemma unsigned_nat_less:
+ \<open>unsigned w < (2 ^ LENGTH('a) :: nat)\<close> for w :: \<open>'a::len word\<close>
+ by transfer (simp add: take_bit_eq_mod)
+
+lemma unsigned_int_less:
+ \<open>unsigned w < (2 ^ LENGTH('a) :: int)\<close> for w :: \<open>'a::len word\<close>
+ by transfer (simp add: take_bit_eq_mod)
+
+lemma signed_of_int [simp]:
+ \<open>signed (of_int k :: 'a::len word) = signed_take_bit (LENGTH('a) - 1) k\<close>
+ by transfer simp
+
+lemma of_int_signed [simp]:
+ \<open>of_int (signed a) = a\<close>
+ by transfer (simp_all add: take_bit_signed_take_bit)
+
+lemma signed_int_greater_eq:
+ \<open>- ((2::int) ^ (LENGTH('a) - 1)) \<le> signed w\<close> for w :: \<open>'a::len word\<close>
+proof (cases \<open>bit w (LENGTH('a) - 1)\<close>)
+ case True
+ then show ?thesis
+ by transfer (simp add: signed_take_bit_eq_or minus_exp_eq_not_mask or_greater_eq ac_simps)
+next
+ have *: \<open>- (2 ^ (LENGTH('a) - Suc 0)) \<le> (0::int)\<close>
+ by simp
+ case False
+ then show ?thesis
+ by transfer (auto simp add: signed_take_bit_eq intro: order_trans *)
+qed
+
+lemma signed_int_less:
+ \<open>signed w < (2 ^ (LENGTH('a) - 1) :: int)\<close> for w :: \<open>'a::len word\<close>
+ by (cases \<open>bit w (LENGTH('a) - 1)\<close>; transfer)
+ (simp_all add: signed_take_bit_eq signed_take_bit_eq_or take_bit_int_less_exp not_eq_complement mask_eq_exp_minus_1 OR_upper)
+
+context linordered_semidom
+begin
+
+lemma word_less_eq_iff_unsigned:
+ "a \<le> b \<longleftrightarrow> unsigned a \<le> unsigned b"
+ by (transfer fixing: less_eq) (simp add: nat_le_eq_zle)
+
+lemma word_less_iff_unsigned:
+ "a < b \<longleftrightarrow> unsigned a < unsigned b"
+ by (transfer fixing: less) (auto dest: preorder_class.le_less_trans [OF take_bit_nonnegative])
+
+end
+
+lemma of_nat_word_eq_iff:
+ \<open>of_nat m = (of_nat n :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) m = take_bit LENGTH('a) n\<close>
+ by transfer (simp add: take_bit_of_nat)
+
+lemma of_nat_word_less_eq_iff:
+ \<open>of_nat m \<le> (of_nat n :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) m \<le> take_bit LENGTH('a) n\<close>
+ by transfer (simp add: take_bit_of_nat)
+
+lemma of_nat_word_less_iff:
+ \<open>of_nat m < (of_nat n :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) m < take_bit LENGTH('a) n\<close>
+ by transfer (simp add: take_bit_of_nat)
+
+lemma of_nat_word_eq_0_iff:
+ \<open>of_nat n = (0 :: 'a::len word) \<longleftrightarrow> 2 ^ LENGTH('a) dvd n\<close>
+ using of_nat_word_eq_iff [where ?'a = 'a, of n 0] by (simp add: take_bit_eq_0_iff)
+
+lemma of_int_word_eq_iff:
+ \<open>of_int k = (of_int l :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) k = take_bit LENGTH('a) l\<close>
+ by transfer rule
+
+lemma of_int_word_less_eq_iff:
+ \<open>of_int k \<le> (of_int l :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) k \<le> take_bit LENGTH('a) l\<close>
+ by transfer rule
+
+lemma of_int_word_less_iff:
+ \<open>of_int k < (of_int l :: 'a::len word) \<longleftrightarrow> take_bit LENGTH('a) k < take_bit LENGTH('a) l\<close>
+ by transfer rule
+
+lemma of_int_word_eq_0_iff:
+ \<open>of_int k = (0 :: 'a::len word) \<longleftrightarrow> 2 ^ LENGTH('a) dvd k\<close>
+ using of_int_word_eq_iff [where ?'a = 'a, of k 0] by (simp add: take_bit_eq_0_iff)
+
+end