• Top
    • Documentation
    • Books
    • Boolean-reasoning
    • Projects
    • Debugging
    • Std
    • Community
    • Proof-automation
    • Macro-libraries
    • ACL2
    • Interfacing-tools
    • Hardware-verification
    • Software-verification
      • Kestrel-books
        • Crypto-hdwallet
        • Apt
        • Error-checking
        • Fty-extensions
        • Isar
        • Kestrel-utilities
        • Set
        • Soft
        • C
          • Syntax-for-tools
            • Disambiguator
            • Abstract-syntax
            • Parser
            • Validator
              • Valid-exprs/decls/stmts
              • Valid-stmt
              • Valid-expr
              • Valid-dirdeclor
              • Valid-type-spec
              • Valid-transunit
              • Valid-stor-spec-list
              • Valid-binary
              • Valid-unary
              • Valid-initdeclor
              • Valid-fundef
              • Valid-type-spec-list-residual
              • Valid-cond
              • Valid-lookup-ord
                • Valid-transunit-ensemble
                • Valid-declor
                • Valid-iconst
                • Valid-initer
                • Valid-c-char
                • Valid-stringlit-list
                • Valid-funcall
                • Valid-add-ord
                • Valid-arrsub
                • Valid-univ-char-name
                • Valid-extdecl
                • Valid-extdecl-list
                • Valid-cast
                • Valid-add-ord-file-scope
                • Valid-spec/qual
                • Valid-sizeof/alignof
                • Valid-memberp
                • Valid-decl-spec
                • Valid-var
                • Valid-param-declon
                • Valid-oct-escape
                • Valid-structdeclor
                • Valid-structdecl
                • Valid-designor
                • Valid-escape
                • Valid-enum-const
                • Valid-cconst
                • Valid-s-char
                • Valid-dec/oct/hex-const
                • Valid-const
                • Valid-gensel
                • Valid-decl-spec-list
                • Valid-lookup-ord-file-scope
                • Valid-member
                • Valid-param-declor
                • Valid-spec/qual-list
                • Valid-fconst
                • Valid-stringlit
                • Valid-s-char-list
                • Valid-c-char-list
                • Valid-block-item
                • Valid-structdeclor-list
                • Valid-simple-escape
                • Valid-align-spec
                • Valid-enumer
                • Valid-dirabsdeclor
                • Valid-decl
                • Valid-pop-scope
                • Valid-enumspec
                • Valid-declor-option
                • Valid-push-scope
                • Valid-initer-option
                • Valid-block-item-list
                • Valid-absdeclor
                • Valid-label
                • Valid-genassoc
                • Valid-tyname
                • Valid-strunispec
                • Valid-structdecl-list
                • Valid-genassoc-list
                • Valid-dirabsdeclor-option
                • Valid-designor-list
                • Valid-const-expr
                • Valid-initdeclor-list
                • Valid-desiniter-list
                • Valid-absdeclor-option
                • Valid-table-num-scopes
                • Valid-expr-list
                • Valid-param-declon-list
                • Valid-desiniter
                • Valid-const-expr-option
                • Valid-expr-option
                • Valid-statassert
                • Valid-enumer-list
                • Valid-init-table
                • Valid-empty-scope
                • Valid-member-designor
                • Valid-decl-list
              • Printer
              • Formalized-subset
              • Mapping-to-language-definition
              • Input-files
              • Defpred
              • Output-files
              • Abstract-syntax-operations
              • Validation-information
              • Implementation-environments
              • Concrete-syntax
              • Ascii-identifiers
              • Unambiguity
              • Preprocessing
              • Abstraction-mapping
            • Atc
            • Language
            • Representation
            • Transformation-tools
            • Insertion-sort
            • Pack
          • Bv
          • Imp-language
          • Event-macros
          • Java
          • Bitcoin
          • Ethereum
          • Yul
          • Zcash
          • ACL2-programming-language
          • Prime-fields
          • Json
          • Syntheto
          • File-io-light
          • Cryptography
          • Number-theory
          • Lists-light
          • Axe
          • Builtins
          • Solidity
          • Helpers
          • Htclient
          • Typed-lists-light
          • Arithmetic-light
        • X86isa
        • Axe
        • Execloader
      • Math
      • Testing-utilities
    • Validator

    Valid-lookup-ord

    Look up an ordinary identifier in a validation table.

    Signature
    (valid-lookup-ord ident table) → (mv info? currentp)
    Arguments
    ident — Guard (identp ident).
    table — Guard (valid-tablep table).
    Returns
    info? — Type (valid-ord-info-optionp info?).
    currentp — Type (booleanp currentp).

    According to the visibility and hiding rules [C17:6.2.1/2], we look up the identifier starting from the innermost scope. We stop as soon as we find a match. We return nil if we reach the outermost scope without finding a match.

    We also return a flag saying whether the identifier was found in the current (i.e. innermost) scope or in some other scope. We initialize this flag to t, and we set to nil when we perform the recursive call. The flag is irrelevant if the first result is nil, but in this case the returned flag is nil too.

    Definitions and Theorems

    Function: valid-lookup-ord-loop

    (defun valid-lookup-ord-loop (ident scopes currentp)
      (declare (xargs :guard (and (identp ident)
                                  (valid-scope-listp scopes)
                                  (booleanp currentp))))
      (let ((__function__ 'valid-lookup-ord-loop))
        (declare (ignorable __function__))
        (b* (((when (endp scopes)) (mv nil nil))
             (scope (car scopes))
             (ord-scope (valid-scope->ord scope))
             (ident+info (assoc-equal (ident-fix ident)
                                      ord-scope))
             ((when ident+info)
              (mv (cdr ident+info)
                  (bool-fix currentp))))
          (valid-lookup-ord-loop ident (cdr scopes)
                                 nil))))

    Theorem: valid-ord-info-optionp-of-valid-lookup-ord-loop.info?

    (defthm valid-ord-info-optionp-of-valid-lookup-ord-loop.info?
      (b* (((mv ?info? ?updated-currentp)
            (valid-lookup-ord-loop ident scopes currentp)))
        (valid-ord-info-optionp info?))
      :rule-classes :rewrite)

    Theorem: booleanp-of-valid-lookup-ord-loop.updated-currentp

    (defthm booleanp-of-valid-lookup-ord-loop.updated-currentp
      (b* (((mv ?info? ?updated-currentp)
            (valid-lookup-ord-loop ident scopes currentp)))
        (booleanp updated-currentp))
      :rule-classes :rewrite)

    Theorem: valid-lookup-ord-loop-of-ident-fix-ident

    (defthm valid-lookup-ord-loop-of-ident-fix-ident
      (equal (valid-lookup-ord-loop (ident-fix ident)
                                    scopes currentp)
             (valid-lookup-ord-loop ident scopes currentp)))

    Theorem: valid-lookup-ord-loop-ident-equiv-congruence-on-ident

    (defthm valid-lookup-ord-loop-ident-equiv-congruence-on-ident
      (implies
           (ident-equiv ident ident-equiv)
           (equal (valid-lookup-ord-loop ident scopes currentp)
                  (valid-lookup-ord-loop ident-equiv scopes currentp)))
      :rule-classes :congruence)

    Theorem: valid-lookup-ord-loop-of-valid-scope-list-fix-scopes

    (defthm valid-lookup-ord-loop-of-valid-scope-list-fix-scopes
      (equal (valid-lookup-ord-loop ident (valid-scope-list-fix scopes)
                                    currentp)
             (valid-lookup-ord-loop ident scopes currentp)))

    Theorem: valid-lookup-ord-loop-valid-scope-list-equiv-congruence-on-scopes

    (defthm
      valid-lookup-ord-loop-valid-scope-list-equiv-congruence-on-scopes
      (implies
           (valid-scope-list-equiv scopes scopes-equiv)
           (equal (valid-lookup-ord-loop ident scopes currentp)
                  (valid-lookup-ord-loop ident scopes-equiv currentp)))
      :rule-classes :congruence)

    Theorem: valid-lookup-ord-loop-of-bool-fix-currentp

    (defthm valid-lookup-ord-loop-of-bool-fix-currentp
      (equal (valid-lookup-ord-loop ident scopes (bool-fix currentp))
             (valid-lookup-ord-loop ident scopes currentp)))

    Theorem: valid-lookup-ord-loop-iff-congruence-on-currentp

    (defthm valid-lookup-ord-loop-iff-congruence-on-currentp
      (implies
           (iff currentp currentp-equiv)
           (equal (valid-lookup-ord-loop ident scopes currentp)
                  (valid-lookup-ord-loop ident scopes currentp-equiv)))
      :rule-classes :congruence)

    Function: valid-lookup-ord

    (defun valid-lookup-ord (ident table)
      (declare (xargs :guard (and (identp ident)
                                  (valid-tablep table))))
      (let ((__function__ 'valid-lookup-ord))
        (declare (ignorable __function__))
        (valid-lookup-ord-loop ident (valid-table->scopes table)
                               t)))

    Theorem: valid-ord-info-optionp-of-valid-lookup-ord.info?

    (defthm valid-ord-info-optionp-of-valid-lookup-ord.info?
      (b* (((mv ?info? ?currentp)
            (valid-lookup-ord ident table)))
        (valid-ord-info-optionp info?))
      :rule-classes :rewrite)

    Theorem: booleanp-of-valid-lookup-ord.currentp

    (defthm booleanp-of-valid-lookup-ord.currentp
      (b* (((mv ?info? ?currentp)
            (valid-lookup-ord ident table)))
        (booleanp currentp))
      :rule-classes :rewrite)

    Theorem: valid-lookup-ord-of-ident-fix-ident

    (defthm valid-lookup-ord-of-ident-fix-ident
      (equal (valid-lookup-ord (ident-fix ident)
                               table)
             (valid-lookup-ord ident table)))

    Theorem: valid-lookup-ord-ident-equiv-congruence-on-ident

    (defthm valid-lookup-ord-ident-equiv-congruence-on-ident
      (implies (ident-equiv ident ident-equiv)
               (equal (valid-lookup-ord ident table)
                      (valid-lookup-ord ident-equiv table)))
      :rule-classes :congruence)

    Theorem: valid-lookup-ord-of-valid-table-fix-table

    (defthm valid-lookup-ord-of-valid-table-fix-table
      (equal (valid-lookup-ord ident (valid-table-fix table))
             (valid-lookup-ord ident table)))

    Theorem: valid-lookup-ord-valid-table-equiv-congruence-on-table

    (defthm valid-lookup-ord-valid-table-equiv-congruence-on-table
      (implies (valid-table-equiv table table-equiv)
               (equal (valid-lookup-ord ident table)
                      (valid-lookup-ord ident table-equiv)))
      :rule-classes :congruence)