Theory Multitape_Binary_Codec

theory Multitape_Binary_Codec
  imports Main
begin

section ‹Fixed-width binary blocks›

text ‹Several constructions over the substrate write a natural number onto a
  tape as a block of a fixed number of cells, one binary digit per cell: a
  symbol of a large alphabet as its index, or a field of a record a machine
  keeps on a work tape.  This theory is that codec, once.  It mentions no
  machine.

  The two digit symbols are parameters, ‹d0› for the bit ‹0› and ‹d1› for the
  bit ‹1›, over an arbitrary symbol type.  A construction whose tape alphabet
  has no spare symbols can then extend it by two fresh ones and use those, and
  one with a fixed alphabet instantiates the parameters once and names the
  instance.

  A block is most-significant digit first.  For ‹n ≥ 2 ^ k› the high bits
  of ‹n› are dropped.›

fun nat_to_syms :: "'x ⇒ 'x ⇒ nat ⇒ nat ⇒ 'x list" where
  "nat_to_syms d0 d1 0 _ = []"
| "nat_to_syms d0 d1 (Suc k) n =
     nat_to_syms d0 d1 k (n div 2) @ [if n mod 2 = 0 then d0 else d1]"

text ‹The bit a symbol denotes: ‹1› for ‹d1›, ‹0› for anything else.  The
  decoder is total, so it reads a malformed block as some number; checking
  that every cell is a digit is the caller's business.›

definition bit_of :: "'x ⇒ 'x ⇒ nat" where
  "bit_of d1 x = (if x = d1 then 1 else 0)"

lemma bit_of_same [simp]: "bit_of d1 d1 = 1"
  by (simp add: bit_of_def)

lemma bit_of_other [simp]: "x ≠ d1 ⟹ bit_of d1 x = 0"
  by (simp add: bit_of_def)

fun syms_to_nat :: "'x ⇒ 'x list ⇒ nat" where
  "syms_to_nat d1 [] = 0"
| "syms_to_nat d1 (b # bs) = bit_of d1 b * 2 ^ length bs + syms_to_nat d1 bs"

text ‹A block has the requested width, and every cell is one of the two
  digit symbols.›

lemma length_nat_to_syms [simp]:
  "length (nat_to_syms d0 d1 k n) = k"
  by (induct k arbitrary: n) auto

lemma set_nat_to_syms:
  "set (nat_to_syms d0 d1 k n) ⊆ {d0, d1}"
  by (induct k arbitrary: n) auto

text ‹Appending a low digit shifts the value left and adds the new bit.  This
  matches the shape of @{const nat_to_syms}, which appends its low digit, and
  is the step of the round trip below.›

lemma syms_to_nat_snoc:
  "syms_to_nat d1 (xs @ [b]) = 2 * syms_to_nat d1 xs + bit_of d1 b"
  by (induct xs) auto

lemma bit_of_low_bit:
  assumes "d0 ≠ d1"
  shows "bit_of d1 (if n mod 2 = 0 then d0 else d1) = n mod 2"
  using assms mod_less_divisor[of 2 n] by (auto simp: bit_of_def)

text ‹The round trip: writing ‹n < 2 ^ k› as a block of ‹k› cells and reading
  it back gives ‹n›, provided the two digits differ.›

lemma syms_to_nat_nat_to_syms:
  assumes d: "d0 ≠ d1" and "n < 2 ^ k"
  shows "syms_to_nat d1 (nat_to_syms d0 d1 k n) = n"
  using ‹n < 2 ^ k›
proof (induct k arbitrary: n)
  case 0
  thus ?case by simp
next
  case (Suc k)
  have lt: "n div 2 < 2 ^ k" using ‹n < 2 ^ Suc k› by simp
  have "syms_to_nat d1 (nat_to_syms d0 d1 (Suc k) n)
          = syms_to_nat d1
              (nat_to_syms d0 d1 k (n div 2)
                 @ [if n mod 2 = 0 then d0 else d1])"
    by simp
  also have "…
          = 2 * syms_to_nat d1 (nat_to_syms d0 d1 k (n div 2))
              + bit_of d1 (if n mod 2 = 0 then d0 else d1)"
    by (rule syms_to_nat_snoc)
  also have "… = 2 * (n div 2) + n mod 2"
    using Suc.hyps[OF lt] bit_of_low_bit[OF d, of n] by simp
  also have "… = n" by presburger
  finally show ?case .
qed

text ‹Injectivity on the bounded range follows: decoding is a left inverse
  there, so equal blocks have equal values.›

lemma nat_to_syms_inj:
  assumes d: "d0 ≠ d1"
      and n1: "n1 < 2 ^ k" and n2: "n2 < 2 ^ k"
      and eq: "nat_to_syms d0 d1 k n1 = nat_to_syms d0 d1 k n2"
  shows "n1 = n2"
proof -
  have "n1 = syms_to_nat d1 (nat_to_syms d0 d1 k n1)"
    by (simp add: syms_to_nat_nat_to_syms[OF d n1])
  also have "… = syms_to_nat d1 (nat_to_syms d0 d1 k n2)" using eq by simp
  also have "… = n2" by (simp add: syms_to_nat_nat_to_syms[OF d n2])
  finally show ?thesis .
qed

subsection ‹The width of a block›

text ‹The width that indexes a finite set ‹S›: the fewest binary digits that
  number all of its elements, ‹⌈log2 (card S)⌉›, and at least one, so that no
  block is empty.  It is defined by ‹LEAST›, and such an ‹n› exists because
  ‹card S < 2 ^ card S›.›

definition block_width :: "'z set ⇒ nat" where
  "block_width S = max 1 (LEAST n. card S ≤ 2 ^ n)"

lemma block_width_pos: "1 ≤ block_width S"
  unfolding block_width_def by simp

text ‹Coverage: ‹card S ≤ 2 ^ block_width S›, so every index below ‹card S›
  is in the range where @{const nat_to_syms} is injective.›

lemma card_le_two_pow_block_width: "card S ≤ 2 ^ block_width S"
proof -
  have ex: "∃n. card S ≤ 2 ^ n"
    using less_exp[of "card S"] by (intro exI[of _ "card S"]) simp
  let ?m = "LEAST n. card S ≤ 2 ^ n"
  have m_bound: "card S ≤ 2 ^ ?m" using LeastI_ex[OF ex] .
  have "?m ≤ block_width S" unfolding block_width_def by simp
  hence "(2::nat) ^ ?m ≤ 2 ^ block_width S" by (rule power_increasing) simp
  with m_bound show ?thesis by linarith
qed

text ‹Minimality: once ‹S› has two elements, one digit fewer does not
  suffice.  With coverage this pins the width to ‹⌈log2 (card S)⌉›: it is
  constant on each band ‹2 ^ (b - 1) < card S ≤ 2 ^ b› and rises by one as
  ‹card S› passes a power of two.›

lemma two_pow_block_width_pred_less_card:
  assumes card2: "2 ≤ card S"
  shows "2 ^ (block_width S - 1) < card S"
proof -
  have ex: "∃n. card S ≤ 2 ^ n"
    using less_exp[of "card S"] by (intro exI[of _ "card S"]) simp
  let ?m = "LEAST n. card S ≤ 2 ^ n"
  have notP0: "¬ card S ≤ 2 ^ (0::nat)" using card2 by simp
  have m_pos: "0 < ?m"
  proof (rule ccontr)
    assume "¬ 0 < ?m"
    then have "?m = 0" by simp
    then have "card S ≤ 2 ^ (0::nat)" using LeastI_ex[OF ex] by simp
    with notP0 show False by simp
  qed
  hence bw: "block_width S = ?m" unfolding block_width_def by simp
  have "block_width S - 1 < ?m" using bw m_pos by simp
  hence "¬ card S ≤ 2 ^ (block_width S - 1)" by (rule not_less_Least)
  thus ?thesis by simp
qed

text ‹The exact value, for a caller that knows the band ‹card S› lies in:
  bracketing the cardinality between two consecutive powers pins the
  ⬚‹LEAST›, and the lower bound makes the const‹max› inert.›

lemma block_width_eqI:
  assumes lo: "2 ^ n < card S" and hi: "card S ≤ 2 ^ Suc n"
  shows "block_width S = Suc n"
proof -
  have "(LEAST m. card S ≤ 2 ^ m) = Suc n"
  proof (rule Least_equality)
    show "card S ≤ 2 ^ Suc n" by (rule hi)
  next
    fix m assume m: "card S ≤ 2 ^ m"
    show "Suc n ≤ m"
    proof (rule ccontr)
      assume "¬ Suc n ≤ m"
      then have "m ≤ n" by simp
      then have "(2::nat) ^ m ≤ 2 ^ n"
        using power_increasing [of m n "2::nat"] by simp
      with lo m show False by simp
    qed
  qed
  then show ?thesis by (simp add: block_width_def)
qed

end