• Top
  • Documentation
  • Books
  • Boolean-reasoning
  • Projects
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
    • Kestrel-books
      • Crypto-hdwallet
      • Apt
      • Error-checking
      • Fty-extensions
      • Isar
      • Kestrel-utilities
      • Soft
      • Bv
      • Imp-language
      • C
      • Event-macros
      • Java
      • Bitcoin
      • Ethereum
      • Yul
      • Zcash
      • ACL2-programming-language
      • Prime-fields
      • Json
      • Syntheto
        • Process-syntheto-toplevel-fn
        • Translation
        • Language
          • Static-semantics
            • Check-expression-fns
            • Subtypep
            • Match-type
            • Check-product-update-expression
            • Get-builtin-function-in/out/pre-post
            • Check-sum-update-expression
            • Check-sum-field-expression
            • Check-strict-binary-expression
            • Check-lt/le/gt/ge-expression
            • Check-eq/ne-expression
            • Check-div/rem-expression
            • Check-add/sub/mul-expression
            • Align-let-vars-values
            • Check-iff-expression
            • Check-function-definition-top/nontop
            • Check-sum-construct-expression
            • Check-rem-expression
            • Check-mul-expression
            • Check-sub-expression
            • Check-div-expression
            • Check-add-expression
            • Check-ne-expression
            • Check-lt-expression
            • Check-le-expression
            • Check-gt-expression
            • Check-ge-expression
            • Check-eq-expression
            • Check-function-specifier
            • Type-result
            • Check-product-construct-expression
            • Supremum-type
            • Check-call-expression
            • Check-product-field-expression
            • Check-function-definer
            • Make-subproof-obligations
            • Get-function-in/out/pre/post
            • Check-sum-test-expression
            • Match-field
            • Decompose-expression
            • Match-to-target
            • Check-unary-expression
            • Max-supertype
            • Match-type-list
            • Check-minus-expression
            • Check-type-definition
            • Check-not-expression
            • Check-type-product
            • Match-field-list
            • Check-type-subset
            • Check-type-definition-in-recursion
            • Align-let-vars-values-aux
            • Non-trivial-proof-obligation
            • Check-type-recursion
            • Check-function-specification
            • Check-toplevel
            • Supremum-type-list
            • Check-component-expression
            • Check-branch-list
            • Check-function-recursion
            • Check-function-definition
            • Binding
            • Check-function-header
            • Check-function-definition-list
            • Check-type-definition-list-in-recursion
            • Check-theorem
            • Check-nonstrict-binary-expression
            • Context-add-variables
            • Decompose-expression-aux
            • Check-alternative
            • Check-multi-expression
            • Check-type-sum
            • Check-type
            • Check-alternative-list
            • Context-add-condition
            • Check-type-definer
            • Check-transform
            • Check-variable
            • Check-transform-args
            • Check-toplevel-list
            • Context-add-condition-list
            • Check-if/when/unless-expression
            • Initializers-to-variable-substitution
            • Context-add-binding
            • Check-function-header-list
            • Context-add-toplevel
            • Ensure-single-type
            • Max-supertypes
            • Check-bind-expression
            • Check-type-list
            • Check-literal
            • Literal-type
            • Check-expression-list
            • Variable-context
            • Check-cond-expression
            • Check-branch
            • Args-without-defaults
            • Check-expression
            • *builtin-function-names*
            • Function-called-in
          • Abstract-syntax
          • Outcome
          • Abstract-syntax-operations
          • Outcome-list
          • Outcomes
        • Process-syntheto-toplevel
        • Shallow-embedding
      • File-io-light
      • Number-theory
      • Cryptography
      • Lists-light
      • Builtins
      • Axe
      • Solidity
      • Helpers
      • Htclient
      • Typed-lists-light
      • Arithmetic-light
    • X86isa
    • Axe
    • Execloader
  • Math
  • Testing-utilities

• Static-semantics

Check-sum-update-expression

Check if a sum update expression is statically well-formed.

Signature

(check-sum-update-expression tname target target-result alternative 
                             inits inits-result expr ctxt) 
 
  → 
result

Arguments

tname — Guard (identifierp tname).

target — Guard (expressionp target).

target-result — Guard (type-resultp target-result).

alternative — Guard (identifierp alternative).

inits — Guard (initializer-listp inits).

inits-result — Guard (type-resultp inits-result).

expr — Guard (expressionp expr).

ctxt — Guard (contextp ctxt).

Returns

result — Type (type-resultp result).

This is similar to check-product-update-expression, but the target expression must be (a subtype of) a sum type, and the product type is the one associated to the alternative. We also generate a proof obligation saying that the sum type value is of the specified alternative.

Definitions and Theorems

Function: check-sum-update-expression

(defun check-sum-update-expression
       (tname target target-result alternative
              inits inits-result expr ctxt)
 (declare (xargs :guard (and (identifierp tname)
                             (expressionp target)
                             (type-resultp target-result)
                             (identifierp alternative)
                             (initializer-listp inits)
                             (type-resultp inits-result)
                             (expressionp expr)
                             (contextp ctxt))))
 (declare
     (xargs :guard (type-result-case inits-result
                                     :err t
                                     :ok (= (len inits-result.types)
                                            (len inits)))))
 (let ((__function__ 'check-sum-update-expression))
  (declare (ignorable __function__))
  (type-result-case
   target-result
   :err (type-result-err target-result.info)
   :ok
   (type-result-case
    inits-result
    :err (type-result-err inits-result.info)
    :ok
    (b*
     ((type (ensure-single-type target-result.types))
      ((when (not type))
       (type-result-err (list :multi-valued-field-target
                              (expression-fix target)
                              target-result.types)))
      (type (max-supertype type (context->tops ctxt)))
      ((when (not type))
       (type-result-err (list :no-max-supertype type)))
      (tsum (get-type-sum type (context->tops ctxt)))
      ((when (not tsum))
       (type-result-err (list :sum-update-type-mismatch type)))
      (oblig?
           (non-trivial-proof-obligation
                (context->obligation-vars ctxt)
                (context->obligation-hyps ctxt)
                (make-expression-sum-test :type tname
                                          :target target
                                          :alternative alternative)
                expr))
      (product
           (get-alternative-product alternative
                                    (type-sum->alternatives tsum)))
      ((when (not product))
       (type-result-err (list :sum-update-no-alternative
                              tsum (identifier-fix alternative))))
      (fields (type-product->fields product))
      ((mv okp obligs unmatched-fields)
       (match-field-list inits inits-result.types fields ctxt))
      ((when (not okp))
       (type-result-err (list :field-type-mismatch
                              type (initializer-list-fix inits)
                              unmatched-fields)))
      (inv (type-product->invariant product))
      (inv-oblig?
       (if inv
        (b*
         ((subst-new (initializers-to-variable-substitution inits))
          (names (field-list->name-list unmatched-fields))
          (subst-old
            (omap::from-lists names
                              (expression-sum-field-list
                                   tname target alternative names)))
          (subst (omap::update* subst-new subst-old)))
         (non-trivial-proof-obligation
              (context->obligation-vars ctxt)
              (context->obligation-hyps ctxt)
              (subst-expression subst inv)
              expr))
        nil)))
     (make-type-result-ok
          :types (list type)
          :obligations (append inits-result.obligations
                               oblig? obligs inv-oblig?)))))))

Theorem: type-resultp-of-check-sum-update-expression

(defthm type-resultp-of-check-sum-update-expression
  (b* ((result (check-sum-update-expression
                    tname target target-result alternative
                    inits inits-result expr ctxt)))
    (type-resultp result))
  :rule-classes :rewrite)

Theorem: check-sum-update-expression-of-identifier-fix-tname

(defthm check-sum-update-expression-of-identifier-fix-tname
  (equal
       (check-sum-update-expression (identifier-fix tname)
                                    target target-result alternative
                                    inits inits-result expr ctxt)
       (check-sum-update-expression
            tname target target-result alternative
            inits inits-result expr ctxt)))

Theorem: check-sum-update-expression-identifier-equiv-congruence-on-tname

(defthm
   check-sum-update-expression-identifier-equiv-congruence-on-tname
 (implies
  (identifier-equiv tname tname-equiv)
  (equal
       (check-sum-update-expression
            tname target target-result alternative
            inits inits-result expr ctxt)
       (check-sum-update-expression tname-equiv
                                    target target-result alternative
                                    inits inits-result expr ctxt)))
 :rule-classes :congruence)

Theorem: check-sum-update-expression-of-expression-fix-target

(defthm check-sum-update-expression-of-expression-fix-target
  (equal (check-sum-update-expression tname (expression-fix target)
                                      target-result alternative
                                      inits inits-result expr ctxt)
         (check-sum-update-expression
              tname target target-result alternative
              inits inits-result expr ctxt)))

Theorem: check-sum-update-expression-expression-equiv-congruence-on-target

(defthm
  check-sum-update-expression-expression-equiv-congruence-on-target
  (implies (expression-equiv target target-equiv)
           (equal (check-sum-update-expression
                       tname target target-result alternative
                       inits inits-result expr ctxt)
                  (check-sum-update-expression
                       tname
                       target-equiv target-result alternative
                       inits inits-result expr ctxt)))
  :rule-classes :congruence)

Theorem: check-sum-update-expression-of-type-result-fix-target-result

(defthm check-sum-update-expression-of-type-result-fix-target-result
  (equal (check-sum-update-expression
              tname
              target (type-result-fix target-result)
              alternative
              inits inits-result expr ctxt)
         (check-sum-update-expression
              tname target target-result alternative
              inits inits-result expr ctxt)))

Theorem: check-sum-update-expression-type-result-equiv-congruence-on-target-result

(defthm
 check-sum-update-expression-type-result-equiv-congruence-on-target-result
 (implies (type-result-equiv target-result target-result-equiv)
          (equal (check-sum-update-expression
                      tname target target-result alternative
                      inits inits-result expr ctxt)
                 (check-sum-update-expression
                      tname
                      target target-result-equiv alternative
                      inits inits-result expr ctxt)))
 :rule-classes :congruence)

Theorem: check-sum-update-expression-of-identifier-fix-alternative

(defthm check-sum-update-expression-of-identifier-fix-alternative
  (equal (check-sum-update-expression tname target target-result
                                      (identifier-fix alternative)
                                      inits inits-result expr ctxt)
         (check-sum-update-expression
              tname target target-result alternative
              inits inits-result expr ctxt)))

Theorem: check-sum-update-expression-identifier-equiv-congruence-on-alternative

(defthm
 check-sum-update-expression-identifier-equiv-congruence-on-alternative
 (implies (identifier-equiv alternative alternative-equiv)
          (equal (check-sum-update-expression
                      tname target target-result alternative
                      inits inits-result expr ctxt)
                 (check-sum-update-expression
                      tname
                      target target-result alternative-equiv
                      inits inits-result expr ctxt)))
 :rule-classes :congruence)

Theorem: check-sum-update-expression-of-initializer-list-fix-inits

(defthm check-sum-update-expression-of-initializer-list-fix-inits
  (equal (check-sum-update-expression
              tname target target-result
              alternative (initializer-list-fix inits)
              inits-result expr ctxt)
         (check-sum-update-expression
              tname target target-result alternative
              inits inits-result expr ctxt)))

Theorem: check-sum-update-expression-initializer-list-equiv-congruence-on-inits

(defthm
 check-sum-update-expression-initializer-list-equiv-congruence-on-inits
 (implies (initializer-list-equiv inits inits-equiv)
          (equal (check-sum-update-expression
                      tname target target-result alternative
                      inits inits-result expr ctxt)
                 (check-sum-update-expression
                      tname target target-result alternative
                      inits-equiv inits-result expr ctxt)))
 :rule-classes :congruence)

Theorem: check-sum-update-expression-of-type-result-fix-inits-result

(defthm check-sum-update-expression-of-type-result-fix-inits-result
  (equal (check-sum-update-expression
              tname target target-result alternative
              inits (type-result-fix inits-result)
              expr ctxt)
         (check-sum-update-expression
              tname target target-result alternative
              inits inits-result expr ctxt)))

Theorem: check-sum-update-expression-type-result-equiv-congruence-on-inits-result

(defthm
 check-sum-update-expression-type-result-equiv-congruence-on-inits-result
 (implies (type-result-equiv inits-result inits-result-equiv)
          (equal (check-sum-update-expression
                      tname target target-result alternative
                      inits inits-result expr ctxt)
                 (check-sum-update-expression
                      tname target target-result alternative
                      inits inits-result-equiv expr ctxt)))
 :rule-classes :congruence)

Theorem: check-sum-update-expression-of-expression-fix-expr

(defthm check-sum-update-expression-of-expression-fix-expr
  (equal (check-sum-update-expression
              tname target target-result alternative
              inits inits-result (expression-fix expr)
              ctxt)
         (check-sum-update-expression
              tname target target-result alternative
              inits inits-result expr ctxt)))

Theorem: check-sum-update-expression-expression-equiv-congruence-on-expr

(defthm
    check-sum-update-expression-expression-equiv-congruence-on-expr
  (implies (expression-equiv expr expr-equiv)
           (equal (check-sum-update-expression
                       tname target target-result alternative
                       inits inits-result expr ctxt)
                  (check-sum-update-expression
                       tname target target-result alternative
                       inits inits-result expr-equiv ctxt)))
  :rule-classes :congruence)

Theorem: check-sum-update-expression-of-context-fix-ctxt

(defthm check-sum-update-expression-of-context-fix-ctxt
  (equal (check-sum-update-expression
              tname
              target target-result alternative inits
              inits-result expr (context-fix ctxt))
         (check-sum-update-expression
              tname target target-result alternative
              inits inits-result expr ctxt)))

Theorem: check-sum-update-expression-context-equiv-congruence-on-ctxt

(defthm check-sum-update-expression-context-equiv-congruence-on-ctxt
  (implies (context-equiv ctxt ctxt-equiv)
           (equal (check-sum-update-expression
                       tname target target-result alternative
                       inits inits-result expr ctxt)
                  (check-sum-update-expression
                       tname target target-result alternative
                       inits inits-result expr ctxt-equiv)))
  :rule-classes :congruence)