Package parser-stream-thm: Properties of parse streams

Information

Files

• Package tarball parser-stream-thm-1.107.tgz
• Theory source file parser-stream-thm.thy (included in the package tarball)

Theorems

⊦ wellFounded isProperSuffix

⊦ ¬(error = eof)

⊦ fromList [] = eof

⊦ ∀xs. isSuffix xs xs

⊦ ∀xs. ¬isProperSuffix xs xs

⊦ ∀l. length (fromList l) = length l

⊦ ∀l. toList (fromList l) = (l, ⊥)

⊦ ∀xs. length xs = length (fst (toList xs))

⊦ ∀xs. isSuffix xs eof ⇔ xs = eof

⊦ ∀xs. isSuffix xs error ⇔ xs = error

⊦ ∀x xs. ¬(eof = cons x xs)

⊦ ∀x xs. ¬(error = cons x xs)

⊦ ∀xs ys. isProperSuffix xs ys ⇒ isSuffix xs ys

⊦ ∀h t. fromList (h :: t) = cons h (fromList t)

⊦ ∀l₁ l₂. fromList (l₁ @ l₂) = append l₁ (fromList l₂)

⊦ ∀xs ys. isProperSuffix xs ys ⇒ length xs < length ys

⊦ ∀xs ys. isSuffix xs ys ⇒ length xs ≤ length ys

⊦ ∀l xs. length (append l xs) = length l + length xs

⊦ ∀xs ys zs. append (xs @ ys) zs = append xs (append ys zs)

⊦ ∀xs ys zs.
    isProperSuffix xs ys ∧ isProperSuffix ys zs ⇒ isProperSuffix xs zs

⊦ ∀xs ys zs. isProperSuffix xs ys ∧ isSuffix ys zs ⇒ isProperSuffix xs zs

⊦ ∀xs ys zs. isSuffix xs ys ∧ isProperSuffix ys zs ⇒ isProperSuffix xs zs

⊦ ∀xs ys zs. isSuffix xs ys ∧ isSuffix ys zs ⇒ isSuffix xs zs

⊦ ∀xs ys e. toList xs = (ys, e) ⇒ length xs = length ys

⊦ surjective (λ(l, b). append l (if b then error else eof))

⊦ ∀xs. xs = error ∨ xs = eof ∨ ∃x xt. xs = cons x xt

⊦ ∀p. (∀xs. (∀ys. isProperSuffix ys xs ⇒ p ys) ⇒ p xs) ⇒ ∀xs. p xs

⊦ ∀x xs y ys. cons x xs = cons y ys ⇔ x = y ∧ xs = ys

⊦ ∀l xs ys e. toList (append l xs) = (l @ ys, e) ⇔ toList xs = (ys, e)

⊦ ∀f xs ys e. toList xs = (ys, e) ⇒ toList (map f xs) = (map f ys, e)

⊦ length error = 0 ∧ length eof = 0 ∧
  ∀x xs. length (cons x xs) = length xs + 1

⊦ (∀xs. append [] xs = xs) ∧
  ∀h t xs. append (h :: t) xs = cons h (append t xs)

⊦ (∀f. map f error = error) ∧ (∀f. map f eof = eof) ∧
  ∀f x xs. map f (cons x xs) = cons (f x) (map f xs)

⊦ ∀h.
    (∀f g xs.
       (∀ys. isProperSuffix ys xs ⇒ f ys = g ys) ⇒ h f xs = h g xs) ⇒
    ∃fn. ∀xs. fn xs = h fn xs

⊦ toList error = ([], ⊤) ∧ toList eof = ([], ⊥) ∧
  ∀x xs. toList (cons x xs) = let (l, e) ← toList xs in (x :: l, e)

⊦ (∀e b f. case e b f error = e) ∧ (∀e b f. case e b f eof = b) ∧
  ∀e b f x xs. case e b f (cons x xs) = f x xs

External Type Operators

• →
• bool
• Data
  • List
    • list
  • Pair
    • ×
• Number
  • Natural
    • natural
• Parser
  • Stream
    • stream

External Constants

• =
• select
• Data
  • Bool
    • ∀
    • ∧
    • ⇒
    • ∃
    • ∨
    • ¬
    • cond
    • ⊥
    • ⊤
  • List
    • ::
    • @
    • []
    • length
    • map
  • Pair
    • ,
    • fst
    • snd
• Function
  • surjective
• Number
  • Natural
    • +
    • <
    • ≤
    • bit0
    • bit1
    • suc
    • zero
• Parser
  • Stream
    • append
    • case
    • cons
    • eof
    • error
    • fromList
    • isProperSuffix
    • isSuffix
    • length
    • map
    • toList
• Relation
  • irreflexive
  • measure
  • subrelation
  • wellFounded

Assumptions

⊦ ⊤

⊦ ¬⊥ ⇔ ⊤

⊦ ¬⊤ ⇔ ⊥

⊦ length [] = 0

⊦ bit0 0 = 0

⊦ length eof = 0

⊦ length error = 0

⊦ ∀t. t ⇒ t

⊦ ∀n. n ≤ n

⊦ ∀m. wellFounded (measure m)

⊦ ⊥ ⇔ ∀p. p

⊦ ∀t. t ∨ ¬t

⊦ ∀xs. ¬isProperSuffix xs eof

⊦ ∀xs. ¬isProperSuffix xs error

⊦ (¬) = λp. p ⇒ ⊥

⊦ ∀t. (∀x. t) ⇔ t

⊦ ∀t. (λx. t x) = t

⊦ (∀) = λp. p = λx. ⊤

⊦ toList eof = ([], ⊥)

⊦ toList error = ([], ⊤)

⊦ ∀t. ¬¬t ⇔ t

⊦ ∀t. ⊥ ∧ t ⇔ ⊥

⊦ ∀t. ⊤ ∧ t ⇔ t

⊦ ∀t. t ∧ ⊥ ⇔ ⊥

⊦ ∀t. t ∧ ⊤ ⇔ t

⊦ ∀t. ⊥ ⇒ t ⇔ ⊤

⊦ ∀t. ⊤ ⇒ t ⇔ t

⊦ ∀t. t ⇒ ⊤ ⇔ ⊤

⊦ ∀t. ⊥ ∨ t ⇔ t

⊦ ∀t. ⊤ ∨ t ⇔ ⊤

⊦ ∀t. t ∨ ⊥ ⇔ t

⊦ ∀t. t ∨ ⊤ ⇔ ⊤

⊦ ∀n. 0 + n = n

⊦ ∀m. m + 0 = m

⊦ ∀l. [] @ l = l

⊦ ∀xs. append [] xs = xs

⊦ ∀f. map f [] = []

⊦ ∀f. map f eof = eof

⊦ ∀f. map f error = error

⊦ ∀r. wellFounded r ⇒ irreflexive r

⊦ ∀t. (⊥ ⇔ t) ⇔ ¬t

⊦ ∀t. (t ⇔ ⊥) ⇔ ¬t

⊦ ∀t. t ⇒ ⊥ ⇔ ¬t

⊦ ∀n. bit1 n = suc (bit0 n)

⊦ ∀l. fromList l = append l eof

⊦ (⇒) = λp q. p ∧ q ⇔ p

⊦ ∀t. (t ⇔ ⊤) ∨ (t ⇔ ⊥)

⊦ ∀m. suc m = m + 1

⊦ ∀x. (fst x, snd x) = x

⊦ ∀t₁ t₂. (if ⊥ then t₁ else t₂) = t₂

⊦ ∀t₁ t₂. (if ⊤ then t₁ else t₂) = t₁

⊦ ∀h t. ¬(h :: t = [])

⊦ ∀p x. p x ⇒ p ((select) p)

⊦ ∀n. bit0 (suc n) = suc (suc (bit0 n))

⊦ ∀x. ∃a b. x = (a, b)

⊦ ∀m n. m + n = n + m

⊦ ∀m n. m < n ⇒ m ≤ n

⊦ ∀r x. irreflexive r ⇒ ¬r x x

⊦ ∀h t. length (h :: t) = suc (length t)

⊦ ∀x xs. length (cons x xs) = suc (length xs)

⊦ ∀m n. ¬(m ≤ n) ⇔ n < m

⊦ ∀m n. m < suc n ⇔ m ≤ n

⊦ (∧) = λp q. (λf. f p q) = λf. f ⊤ ⊤

⊦ ∀e b f. case e b f eof = b

⊦ ∀e b f. case e b f error = e

⊦ ∀f. surjective f ⇔ ∀y. ∃x. y = f x

⊦ ∀p. ¬(∃x. p x) ⇔ ∀x. ¬p x

⊦ (∃) = λp. ∀q. (∀x. p x ⇒ q) ⇒ q

⊦ ∀m n. m + suc n = suc (m + n)

⊦ ∀m n. suc m + n = suc (m + n)

⊦ ∀r s. subrelation r s ∧ wellFounded s ⇒ wellFounded r

⊦ ∀t₁ t₂. ¬(t₁ ∧ t₂) ⇔ ¬t₁ ∨ ¬t₂

⊦ ∀p. (∃x. p x) ⇔ ∃a b. p (a, b)

⊦ ∀xs y ys. isProperSuffix xs (cons y ys) ⇔ isSuffix xs ys

⊦ (∨) = λp q. ∀r. (p ⇒ r) ⇒ (q ⇒ r) ⇒ r

⊦ ∀m n. m ≤ n ∧ n ≤ m ⇔ m = n

⊦ ∀xs ys. isSuffix xs ys ⇔ xs = ys ∨ isProperSuffix xs ys

⊦ ∀f. ∃fn. ∀a b. fn (a, b) = f a b

⊦ ∀m n. m < n ⇔ ∃d. n = m + suc d

⊦ ∀m x y. measure m x y ⇔ m x < m y

⊦ ∀h t xs. append (h :: t) xs = cons h (append t xs)

⊦ ∀l h t. (h :: t) @ l = h :: t @ l

⊦ ∀f h t. map f (h :: t) = f h :: map f t

⊦ ∀f x xs. map f (cons x xs) = cons (f x) (map f xs)

⊦ ∀p. p 0 ∧ (∀n. p n ⇒ p (suc n)) ⇒ ∀n. p n

⊦ ∀r s. subrelation r s ⇔ ∀x y. r x y ⇒ s x y

⊦ ∀e b f x xs. case e b f (cons x xs) = f x xs

⊦ ∀p. p [] ∧ (∀h t. p t ⇒ p (h :: t)) ⇒ ∀l. p l

⊦ ∀h₁ h₂ t₁ t₂. h₁ :: t₁ = h₂ :: t₂ ⇔ h₁ = h₂ ∧ t₁ = t₂

⊦ ∀a b a' b'. (a, b) = (a', b') ⇔ a = a' ∧ b = b'

⊦ ∀p. p error ∧ p eof ∧ (∀x xs. p xs ⇒ p (cons x xs)) ⇒ ∀xs. p xs

⊦ ∀r. wellFounded r ⇔ ∀p. (∀x. (∀y. r y x ⇒ p y) ⇒ p x) ⇒ ∀x. p x

⊦ ∀x xs. toList (cons x xs) = let (l, e) ← toList xs in (x :: l, e)

⊦ ∀e b f.
    ∃fn. fn error = e ∧ fn eof = b ∧ ∀x xs. fn (cons x xs) = f x xs (fn xs)

⊦ ∀r.
    wellFounded r ⇒
    ∀h.
      (∀f g x. (∀z. r z x ⇒ f z = g z) ⇒ h f x = h g x) ⇒
      ∃f. ∀x. f x = h f x

OpenTheory package document generated by opentheory 1.3 (release 20150511)