Theory TIGER_Lexer.TIGER_Intervals
theory TIGER_Intervals
imports TIGER_Pred_Algebra
begin
section ‹Character classes as interval lists›
text ‹A character class is a list of closed intervals ‹(lo, hi)› and denotes the
characters in one of them. A well-formed class is sorted, and its intervals are
nonempty, disjoint and nonadjacent. Owens et al. label transitions with character sets
because iterating over a large alphabet such as Unicode is impractical
\<^cite>‹‹Sect.~4.2› in "owens2009-regex-derivatives-reexamined"›. Lists of intervals
are closed under the Boolean operations and so form an effective Boolean algebra
\<^cite>‹‹Sect.~2› in "dantoni2014-minimization-symbolic-automata"›; single ranges
are not \<^cite>‹‹Sect.~6.2› in "dantoni2014-minimization-symbolic-automata"›.
The alphabet is a bounded discrete linear order (bytes, codepoints). Its bottom, top,
successor and predecessor are parameters of the locale ‹discrete_order›,
not a type class. Its axioms speak only about the range from bottom to top (\<^typ>‹nat›
with a bound is an instance). The locale ‹bounded_discrete_order› adds that
the range is the whole type.
The operations accept any list and return well-formed classes. We prove their
denotations relative to the range and interpret \<^locale>‹eba› in
‹bounded_discrete_order›. Negation is the gaps of the normal form, and
conjunction follows from De Morgan's law. The instance on \<^typ>‹char› is in
‹TIGER_Tables› (an interpretation carries only the locale constants defined before it, so
it follows the generator).›
type_synonym 'ch cls = ‹('ch × 'ch) list›
fun in_cls :: ‹'ch::ord cls ⇒ 'ch ⇒ bool› where
‹in_cls [] c ⟷ False›
| ‹in_cls ((l, h) # p) c ⟷ l ≤ c ∧ c ≤ h ∨ in_cls p c›
text ‹The denotation of a class depends only on its set of intervals:›
lemma in_cls_append[simp]: ‹in_cls (p @ q) c ⟷ in_cls p c ∨ in_cls q c›
by (induct p c rule: in_cls.induct) auto
lemma in_cls_iff: ‹in_cls p c ⟷ (∃x ∈ set p. fst x ≤ c ∧ c ≤ snd x)›
by (induct p c rule: in_cls.induct) auto
lemma in_cls_sort_key[simp]: ‹in_cls (sort_key f p) c ⟷ in_cls p c›
by (simp add: in_cls_iff)
lemma not_in_cls_if_less: ‹∀x ∈ set p. c < fst x ⟹ ¬ in_cls p (c::'ch::linorder)›
by (auto simp: in_cls_iff not_le)
fun sat_cls :: ‹'ch::ord cls ⇒ bool› where
‹sat_cls [] ⟷ False›
| ‹sat_cls ((l, h) # p) ⟷ l ≤ h ∨ sat_cls p›
text ‹A class is satisfiable when one of its intervals is nonempty:›
lemma sat_cls_iff: ‹sat_cls p ⟷ (∃c. in_cls p (c::'ch::order))›
by (induct p rule: sat_cls.induct) (auto intro: order_trans)
subsection ‹The alphabet›
text ‹Within the range from ‹bot› to ‹top›, ‹succ c› is the least character above
‹c› and ‹pred c› the greatest below it:›
locale discrete_order =
fixes bot :: ‹'ch::linorder›
and top :: 'ch
and succ :: ‹'ch ⇒ 'ch›
and pred :: ‹'ch ⇒ 'ch›
assumes bot_le_top: ‹bot ≤ top›
and succ_le_iff: ‹c < top ⟹ succ c ≤ d ⟷ c < d›
and le_pred_iff: ‹bot < c ⟹ d ≤ pred c ⟷ d < c›
begin
lemma less_succ: ‹c < top ⟹ c < succ c›
using succ_le_iff[of c ‹succ c›] by simp
lemma succ_le_top: ‹c < top ⟹ succ c ≤ top›
using succ_le_iff[of c top] by simp
lemma pred_less: ‹bot < c ⟹ pred c < c›
using le_pred_iff[of c ‹pred c›] by simp
lemma succ_pred: ‹⟦ bot < c; c ≤ top ⟧ ⟹ succ (pred c) = c›
proof -
assume ‹bot < c› ‹c ≤ top›
then have ‹pred c < c› ‹pred c < top›
using pred_less[of c] by auto
then have ‹succ (pred c) ≤ c› ‹pred c < succ (pred c)›
using succ_le_iff[of ‹pred c› c] less_succ[of ‹pred c›] by auto
with ‹bot < c› show ?thesis
using le_pred_iff[of c ‹succ (pred c)›] by auto
qed
subsection ‹Well-formed classes›
fun in_range :: ‹'ch cls ⇒ bool› where
‹in_range [] ⟷ True›
| ‹in_range ((l, h) # p) ⟷ bot ≤ l ∧ l ≤ h ∧ h ≤ top ∧ in_range p›
definition separated :: ‹'ch cls ⇒ bool› where
‹separated = sorted_wrt (λx y. snd x < top ∧ succ (snd x) < fst y)›
definition wf_cls :: ‹'ch cls ⇒ bool› where
‹wf_cls p ⟷ in_range p ∧ separated p›
text ‹A class is in range when its intervals are nonempty and lie between ‹bot› and
‹top›. It is separated when each interval ends before the successor of the end of
every earlier one (so the intervals are sorted, disjoint and nonadjacent):›
lemma in_range_iff: ‹in_range p ⟷ (∀x ∈ set p. bot ≤ fst x ∧ fst x ≤ snd x ∧ snd x ≤ top)›
by (induct p rule: in_range.induct) auto
lemma in_range_append[simp]: ‹in_range (p @ q) ⟷ in_range p ∧ in_range q›
by (auto simp: in_range_iff)
lemma in_range_sort_key[simp]: ‹in_range (sort_key f p) ⟷ in_range p›
by (simp add: in_range_iff)
subsection ‹Normal form›
definition clip :: ‹'ch cls ⇒ 'ch cls› where
‹clip p = filter (λ(l, h). l ≤ h) (map (λ(l, h). (max bot l, min h top)) p)›
text ‹Clipping cuts the intervals to the range and drops the empty ones:›
lemma in_range_clip: ‹in_range (clip p)›
by (induct p rule: in_range.induct) (auto simp: clip_def)
lemma in_cls_clip: ‹in_cls (clip p) c ⟷ bot ≤ c ∧ c ≤ top ∧ in_cls p c›
by (induct p rule: in_range.induct) (auto simp: clip_def)
fun merge :: ‹'ch cls ⇒ 'ch cls› where
‹merge ((l, h) # (l', h') # p) =
(if l' ≤ h ∨ l' = succ h then merge ((l, max h h') # p)
else (l, h) # merge ((l', h') # p))›
| ‹merge p = p›
lemmas merge_induct = merge.induct[case_names Cons_Cons Nil Single]
text ‹Merging joins overlapping and adjacent neighbours of a list sorted by lower
bounds. It keeps the first lower bound and takes the others from its input:›
lemma merge_hd: ‹p ≠ [] ⟹ merge p ≠ [] ∧ fst (hd (merge p)) = fst (hd p)›
by (induct p rule: merge_induct) auto
lemma merge_ConsE:
obtains h' p' where ‹merge ((l, h) # p) = (l, h') # p'›
using merge_hd[of ‹(l, h) # p›] by (cases ‹merge ((l, h) # p)›) auto
lemma fst_merge_subset: ‹fst ` set (merge p) ⊆ fst ` set p›
by (induct p rule: merge_induct) auto
lemma in_range_merge: ‹in_range p ⟹ in_range (merge p)›
by (induct p rule: merge_induct) (auto simp: max_def)
lemma in_join_iff:
assumes ‹l ≤ l'› ‹l' ≤ h ∨ l' = succ h› ‹h' ≤ top›
shows ‹l ≤ c ∧ c ≤ max h h' ⟷ l ≤ c ∧ c ≤ h ∨ l' ≤ c ∧ c ≤ h'›
proof -
have ‹l' ≤ c› if ‹h < c› ‹c ≤ h'›
using assms that succ_le_iff[of h c] by auto
with assms show ?thesis
by (cases ‹c ≤ h›) (auto simp: max_def)
qed
lemma in_cls_merge:
‹⟦ sorted (map fst p); in_range p ⟧ ⟹ in_cls (merge p) c ⟷ in_cls p c›
proof (induct p rule: merge_induct)
case (Cons_Cons l h l' h' p)
show ?case
proof (cases ‹l' ≤ h ∨ l' = succ h›)
case True
moreover from Cons_Cons.prems
have ‹sorted (map fst ((l, max h h') # p))› ‹in_range ((l, max h h') # p)›
by (auto simp: max_def)
ultimately show ?thesis
using Cons_Cons in_join_iff[of l l' h h' c] by auto
next
case False
with Cons_Cons show ?thesis
by auto
qed
qed simp_all
lemma separated_merge: ‹⟦ sorted (map fst p); in_range p ⟧ ⟹ separated (merge p)›
proof (induct p rule: merge_induct)
case (Cons_Cons l h l' h' p)
show ?case
proof (cases ‹l' ≤ h ∨ l' = succ h›)
case True
moreover from Cons_Cons.prems
have ‹sorted (map fst ((l, max h h') # p))› ‹in_range ((l, max h h') # p)›
by (auto simp: max_def)
ultimately show ?thesis
using Cons_Cons by auto
next
case False
with Cons_Cons.prems have ‹h < top›
by auto
with False have ‹succ h < l'›
using succ_le_iff[of h l'] by auto
moreover have ‹l' ≤ fst x› if ‹x ∈ set (merge ((l', h') # p))› for x
using that fst_merge_subset[of ‹(l', h') # p›] Cons_Cons.prems by fastforce
ultimately show ?thesis
using False Cons_Cons by (auto simp: separated_def intro: less_le_trans)
qed
qed (simp_all add: separated_def)
definition cls_norm :: ‹'ch cls ⇒ 'ch cls› where
‹cls_norm p = merge (sort_key fst (clip p))›
text ‹The normal form of a class is well-formed and denotes its characters in range:›
lemma wf_cls_norm: ‹wf_cls (cls_norm p)›
by (simp add: wf_cls_def cls_norm_def in_range_merge separated_merge in_range_clip)
lemma in_cls_norm: ‹in_cls (cls_norm p) c ⟷ bot ≤ c ∧ c ≤ top ∧ in_cls p c›
by (simp add: cls_norm_def in_cls_merge in_range_clip in_cls_clip)
subsection ‹Complement›
fun compl_from :: ‹'ch ⇒ 'ch cls ⇒ 'ch cls› where
‹compl_from c [] = [(c, top)]›
| ‹compl_from c ((l, h) # p) =
(if c < l then [(c, pred l)] else []) @ (if h < top then compl_from (succ h) p else [])›
lemmas compl_from_induct = compl_from.induct[case_names Nil Cons]
text ‹The gaps of a well-formed class from ‹c› on are its complement from ‹c› to ‹top›:›
lemma in_cls_compl_from:
assumes ‹wf_cls p› ‹∀x ∈ set p. c ≤ fst x› ‹bot ≤ c› ‹c ≤ top›
shows ‹in_cls (compl_from c p) d ⟷ c ≤ d ∧ d ≤ top ∧ ¬ in_cls p d›
using assms
proof (induct c p rule: compl_from_induct)
case (Cons c l h p)
from Cons.prems have ‹bot ≤ l› ‹l ≤ h› ‹h ≤ top› ‹c ≤ l› ‹wf_cls p›
and above: ‹∀x ∈ set p. h < top ∧ succ h < fst x›
by (simp_all add: wf_cls_def separated_def)
have ih: ‹in_cls (compl_from (succ h) p) d ⟷ succ h ≤ d ∧ d ≤ top ∧ ¬ in_cls p d›
if ‹h < top›
proof -
have ‹h < succ h› ‹succ h ≤ top›
using that less_succ succ_le_top by auto
with that ‹wf_cls p› above ‹bot ≤ l› ‹l ≤ h› show ?thesis
by (intro Cons.hyps) auto
qed
have ‹¬ in_cls p d› if ‹d ≤ h›
using above that less_succ[of h] by (intro not_in_cls_if_less) auto
then show ?case
using ‹c ≤ l› ‹l ≤ h› ‹h ≤ top› ‹bot ≤ c› ih le_pred_iff[of l d] succ_le_iff[of h d]
by (cases ‹d < l›) auto
qed simp
lemma wf_compl_from:
assumes ‹wf_cls p› ‹∀x ∈ set p. c ≤ fst x› ‹bot ≤ c› ‹c ≤ top›
shows ‹wf_cls (compl_from c p) ∧ (∀x ∈ set (compl_from c p). c ≤ fst x)›
using assms
proof (induct c p rule: compl_from_induct)
case (Nil c)
then show ?case
by (simp add: wf_cls_def separated_def)
next
case (Cons c l h p)
from Cons.prems have ‹bot ≤ l› ‹l ≤ h› ‹h ≤ top› ‹c ≤ l› ‹wf_cls p›
and above: ‹∀x ∈ set p. h < top ∧ succ h < fst x›
by (simp_all add: wf_cls_def separated_def)
define r where ‹r = (if h < top then compl_from (succ h) p else [])›
have ‹wf_cls r ∧ (∀x ∈ set r. succ h ≤ fst x ∧ h < top)›
proof (cases ‹h < top›)
case True
then have ‹h < succ h› ‹succ h ≤ top›
using less_succ succ_le_top by auto
with True ‹wf_cls p› above ‹bot ≤ l› ‹l ≤ h›
have ‹wf_cls (compl_from (succ h) p) ∧ (∀x ∈ set (compl_from (succ h) p). succ h ≤ fst x)›
by (intro Cons.hyps) auto
with True show ?thesis
by (simp add: r_def)
qed (simp add: r_def wf_cls_def separated_def)
then have ‹wf_cls r› ‹∀x ∈ set r. l < fst x›
using ‹l ≤ h› less_succ[of h] by auto
moreover have ‹compl_from c ((l, h) # p) = (if c < l then [(c, pred l)] else []) @ r›
by (simp add: r_def)
moreover have ‹pred l < top› ‹succ (pred l) = l› ‹c ≤ pred l› if ‹c < l›
proof -
from that ‹bot ≤ c› have ‹bot < l›
by simp
with that ‹l ≤ h› ‹h ≤ top› show ‹pred l < top› ‹succ (pred l) = l› ‹c ≤ pred l›
using pred_less[of l] succ_pred[of l] le_pred_iff[of l c] by auto
qed
ultimately show ?case
using ‹bot ≤ c› ‹c ≤ l›
by (cases ‹c < l›) (auto simp: wf_cls_def separated_def sorted_wrt_append)
qed
subsection ‹The operations›
definition cls_top :: ‹'ch cls› where
‹cls_top = [(bot, top)]›
definition cls_bot :: ‹'ch cls› where
‹cls_bot = []›
definition cls_disj :: ‹'ch cls ⇒ 'ch cls ⇒ 'ch cls› where
‹cls_disj p q = cls_norm (p @ q)›
definition cls_neg :: ‹'ch cls ⇒ 'ch cls› where
‹cls_neg p = compl_from bot (cls_norm p)›
definition cls_conj :: ‹'ch cls ⇒ 'ch cls ⇒ 'ch cls› where
‹cls_conj p q = cls_neg (cls_disj (cls_neg p) (cls_neg q))›
text ‹The operations denote the Boolean operations on the range:›
lemma in_cls_top: ‹in_cls cls_top c ⟷ bot ≤ c ∧ c ≤ top›
by (simp add: cls_top_def)
lemma in_cls_bot: ‹¬ in_cls cls_bot c›
by (simp add: cls_bot_def)
lemma in_cls_disj: ‹in_cls (cls_disj p q) c ⟷ bot ≤ c ∧ c ≤ top ∧ (in_cls p c ∨ in_cls q c)›
by (simp add: cls_disj_def in_cls_norm)
lemma in_cls_neg: ‹in_cls (cls_neg p) c ⟷ bot ≤ c ∧ c ≤ top ∧ ¬ in_cls p c›
proof -
have ‹∀x ∈ set (cls_norm p). bot ≤ fst x›
using wf_cls_norm by (simp add: wf_cls_def in_range_iff)
then show ?thesis
using wf_cls_norm bot_le_top by (auto simp: cls_neg_def in_cls_compl_from in_cls_norm)
qed
lemma in_cls_conj: ‹in_cls (cls_conj p q) c ⟷ bot ≤ c ∧ c ≤ top ∧ in_cls p c ∧ in_cls q c›
by (auto simp: cls_conj_def in_cls_neg in_cls_disj)
text ‹All of them return well-formed classes:›
lemma wf_top: ‹wf_cls cls_top›
by (simp add: cls_top_def wf_cls_def separated_def bot_le_top)
lemma wf_bot: ‹wf_cls cls_bot›
by (simp add: cls_bot_def wf_cls_def separated_def)
lemma wf_disj: ‹wf_cls (cls_disj p q)›
by (simp add: cls_disj_def wf_cls_norm)
lemma wf_neg: ‹wf_cls (cls_neg p)›
proof -
have ‹∀x ∈ set (cls_norm p). bot ≤ fst x›
using wf_cls_norm by (simp add: wf_cls_def in_range_iff)
then show ?thesis
using wf_compl_from wf_cls_norm bot_le_top by (simp add: cls_neg_def)
qed
lemma wf_conj: ‹wf_cls (cls_conj p q)›
by (simp add: cls_conj_def wf_neg)
end
subsection ‹The effective Boolean algebra›
text ‹When the range is the whole type, character classes form an effective Boolean
algebra:›
locale bounded_discrete_order = discrete_order +
assumes bot_le: ‹bot ≤ c›
and le_top: ‹c ≤ top›
begin
sublocale eba in_cls cls_top cls_bot cls_conj cls_disj cls_neg sat_cls
by unfold_locales
(simp_all add: bot_le le_top in_cls_top in_cls_bot in_cls_conj in_cls_disj in_cls_neg
sat_cls_iff)
end
end