Theory Intervals_Tests

(* Author: Basil Fürer *)

theory Intervals_Tests
  imports TIGER_Lexer.TIGER_Tables
begin

section ‹Tests of character classes›

text ‹The class operations and minterms of theory‹TIGER_Lexer.TIGER_Intervals› on two
  instances: natural numbers below a bound and bytes.›

subsection ‹Natural numbers below a bound›

text ‹Natural numbers up to a bound are a discrete order:›

global_interpretation nat_cls: discrete_order ‹0::nat› ‹100› Suc ‹λn. n - 1›
  defines nat_clip = nat_cls.clip
    and nat_merge = nat_cls.merge
    and nat_norm = nat_cls.cls_norm
    and nat_compl_from = nat_cls.compl_from
    and nat_disj = nat_cls.cls_disj
    and nat_neg = nat_cls.cls_neg
    and nat_conj = nat_cls.cls_conj
  by unfold_locales (auto simp: le_diff_conv2)

value ‹nat_disj [(4, 6), (10, 12)] [(1, 3), (11, 20)]›
value ‹nat_neg [(0, 9), (20, 200), (15, 16)]›
value ‹nat_conj [(1, 10), (30, 40)] [(5, 35)]›
value ‹sat_cls (nat_conj [(1, 4)] [(5, 9)])›

subsection ‹Bytes›

value ‹char_disj [(CHR ''a'', CHR ''z'')] [(CHR ''A'', CHR ''Z''), (CHR ''_'', CHR ''_'')]›
value ‹char_neg [(CHR ''a'', CHR ''z'')]›
value ‹char_conj (char_neg [(CHR ''0'', CHR ''9'')]) [(CHR ''+'', CHR ''@'')]›
value ‹sat_cls (char_conj [(CHR ''a'', CHR ''z'')] (char_neg char_top))›

text ‹The minterms of ‹\w› and ‹\d› are ‹\d›, ‹\w ∧ ¬ \d› and ‹¬ \w›
  cite‹‹Ex.~1› in "dantoni2014-minimization-symbolic-automata"›. Each character
  lies in exactly one minterm, whose signature is its own:›

definition char_w where
  ‹char_w = [(CHR ''0'', CHR ''9''), (CHR ''A'', CHR ''Z''), (CHR ''_'', CHR ''_''),
    (CHR ''a'', CHR ''z'')]›

definition char_d where
  ‹char_d = [(CHR ''0'', CHR ''9'')]›

value ‹char_minterms [char_w, char_d]›

definition minterms_ok :: ‹char cls list ⇒ bool› where
  ‹minterms_ok P = list_all (λc.
    (case filter (λ(S, μ). in_cls μ c) (char_minterms P) of
      [(S, μ)] ⇒ S = Set.filter (λp. in_cls p c) (set P)
    | _ ⇒ False)) Enum.enum›

value ‹minterms_ok [char_w, char_d]›

text ‹The bit predicates of cite‹‹Ex.~2› in "dantoni2014-minimization-symbolic-automata"›
  on bytes give one minterm per byte value below ‹2k›:›

definition char_bit :: ‹nat ⇒ char cls› where
  ‹char_bit i = map (λn. (char_of (n * 2 ^ Suc i + 2 ^ i),
    char_of (n * 2 ^ Suc i + 2 ^ Suc i - 1))) [0 ..< 2 ^ (7 - i)]›

value ‹length (char_minterms (map char_bit [0 ..< 4]))›
value ‹minterms_ok (map char_bit [0 ..< 4])›

(* ~7s: 256 minterms. The check minterms_ok on 8 bits does not finish in 10 min. *)
value ‹length (char_minterms (map char_bit [0 ..< 8]))›

end