• Top
  • Documentation
  • Books
  • Boolean-reasoning
  • Projects
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
    • Kestrel-books
    • X86isa
      • Program-execution
      • Tlb
      • Booting-linux
      • Introduction
      • X86isa-build-instructions
      • Publications
      • Contributors
      • Machine
        • X86isa-state
        • Syscalls
        • Cpuid
        • Linear-memory
          • Reasoning-about-memory-reads-and-writes
          • Rml256
          • Wml256
          • Rml128
          • Rml80
          • Program-location
          • Rml64
          • Wml128
          • Rml48
          • Rml32
          • Rml08
          • Rml16
          • Wml80
          • Byte-listp
          • Wml64
          • Wml08
          • Wml48
          • Parametric-memory-reads-and-writes
          • Combine-n-bytes
          • Wml32
          • Program-at
          • Wml16
          • Combine-bytes
          • Write-canonical-address-to-memory-user-exec
          • Write-canonical-address-to-memory
          • Wml-size
          • Rml-size
          • Riml64
          • Riml32
          • Riml16
          • Riml08
          • Wiml64
          • Wiml32
          • Wiml16
          • Wiml08
          • Wiml-size
          • Generate-xr-over-write-thms
          • Generate-write-fn-over-xw-thms
          • Generate-read-fn-over-xw-thms
          • Riml-size
        • Rflag-specifications
        • Characterizing-undefined-behavior
        • Top-level-memory
        • App-view
        • X86-decoder
        • Physical-memory
        • Decoding-and-spec-utils
        • Instructions
        • Register-readers-and-writers
        • X86-modes
        • Segmentation
        • Other-non-deterministic-computations
        • Environment
        • Paging
      • Implemented-opcodes
      • Proof-utilities
      • To-do
      • Peripherals
      • Model-validation
      • Modelcalls
      • Concrete-simulation-examples
      • Utils
      • Debugging-code-proofs
    • Axe
    • Execloader
  • Math
  • Testing-utilities

• Linear-memory

Byte-listp

Recognizer of a list of bytes

Signature

(byte-listp x) → *

Definitions and Theorems

Function: byte-listp

(defun byte-listp (x)
  (declare (xargs :guard t))
  (let ((__function__ 'byte-listp))
    (declare (ignorable __function__))
    (if (equal x nil)
        t
      (and (consp x)
           (n08p (car x))
           (byte-listp (cdr x))))))

Theorem: byte-listp-implies-true-listp

(defthm byte-listp-implies-true-listp
  (implies (byte-listp x) (true-listp x))
  :rule-classes :forward-chaining)

Theorem: n08p-element-of-byte-listp

(defthm n08p-element-of-byte-listp
 (implies (and (byte-listp acc)
               (natp m)
               (< m (len acc)))
          (unsigned-byte-p 8 (nth m acc)))
 :rule-classes
 (:rewrite
  (:type-prescription
      :corollary (implies (and (byte-listp acc)
                               (natp m)
                               (< m (len acc)))
                          (natp (nth m acc)))
      :hints
      (("Goal" :in-theory '(unsigned-byte-p integer-range-p natp))))
  (:linear
   :corollary (implies (and (byte-listp acc)
                            (natp m)
                            (< m (len acc)))
                       (and (<= 0 (nth m acc))
                            (< (nth m acc) 256)))
   :hints
   (("Goal"
        :in-theory '(unsigned-byte-p integer-range-p (:e expt)))))))

Theorem: repeat-byte-listp

(defthm repeat-byte-listp
  (implies (unsigned-byte-p 8 m)
           (byte-listp (acl2::repeat n m)))
  :rule-classes (:type-prescription :rewrite))

Theorem: len-of-nthcdr-byte-listp

(defthm len-of-nthcdr-byte-listp
  (implies (and (< m (len acc)) (natp m))
           (equal (len (nthcdr m acc))
                  (- (len acc) m))))

Theorem: byte-listp-revappend

(defthm byte-listp-revappend
  (implies (forced-and (byte-listp lst1)
                       (byte-listp lst2))
           (byte-listp (revappend lst1 lst2)))
  :rule-classes :type-prescription)

Theorem: true-listp-make-list-ac

(defthm true-listp-make-list-ac
  (implies (true-listp ac)
           (true-listp (make-list-ac n val ac)))
  :rule-classes :type-prescription)

Theorem: reverse-byte-listp

(defthm reverse-byte-listp
  (implies (byte-listp x)
           (byte-listp (reverse x)))
  :rule-classes (:type-prescription :rewrite))

Theorem: byte-listp-append

(defthm byte-listp-append
  (implies (forced-and (byte-listp lst1)
                       (byte-listp lst2))
           (byte-listp (append lst1 lst2)))
  :rule-classes (:rewrite :type-prescription))

Theorem: make-list-ac-byte-listp

(defthm make-list-ac-byte-listp
  (implies (and (byte-listp x) (n08p m))
           (byte-listp (make-list-ac n m x)))
  :rule-classes (:type-prescription :rewrite))