• Top
  • Documentation
  • Books
  • Boolean-reasoning
  • Projects
  • Debugging
  • Community
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
    • Kestrel-books
      • Crypto-hdwallet
      • Apt
      • Error-checking
      • Fty-extensions
      • Isar
      • Kestrel-utilities
      • Set
      • C
      • Soft
      • Bv
      • Imp-language
      • Ethereum
      • Event-macros
      • Java
      • Riscv
      • Bitcoin
      • Zcash
      • Yul
      • 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
      • Cryptography
      • Number-theory
      • Axe
      • Lists-light
      • Builtins
      • Solidity
      • Helpers
      • Htclient
      • Typed-lists-light
      • Arithmetic-light
    • X86isa
    • Axe
    • Execloader
  • Math
  • Testing-utilities

• Static-semantics

Supremum-type

Supremum (i.e. least upper bound) of two Syntheto types.

Signature

(supremum-type type1 type2 tops) → supremum?

Arguments

type1 — Guard (typep type1).

type2 — Guard (typep type2).

tops — Guard (toplevel-listp tops).

Returns

supremum? — Type (maybe-typep supremum?).

If one type is a subtype of the other, the latter is the supremum. Otherwise, we move up one step from either type if possible (i.e. if the chosen type has a direct one), and continue like that. It does not matter which type we choose. If the two types have a supremum, all paths converge to it. Here we always choose the first type, type1.

The discussion in subtypep about well-formedness and circularities applies here. We use the same approach to ensure termination. We return nil if we detect a circularity.

Definitions and Theorems

Function: supremum-type-aux

(defun supremum-type-aux (type1 type2 defined-names tops)
 (declare (xargs :guard (and (typep type1)
                             (typep type2)
                             (identifier-listp defined-names)
                             (toplevel-listp tops))))
 (let ((__function__ 'supremum-type-aux))
  (declare (ignorable __function__))
  (b* ((defined-names (identifier-list-fix defined-names))
       ((when (subtypep type1 type2 tops))
        (type-fix type2))
       ((when (subtypep type2 type1 tops))
        (type-fix type1))
       (direct (direct-supertype type1 tops)))
   (and
    direct
    (b* ((name (type-defined->name type1)))
     (and
         (member-equal name defined-names)
         (supremum-type-aux direct
                            type2 (remove1-equal name defined-names)
                            tops)))))))

Theorem: maybe-typep-of-supremum-type-aux

(defthm maybe-typep-of-supremum-type-aux
  (b*
    ((supremum? (supremum-type-aux type1 type2 defined-names tops)))
    (maybe-typep supremum?))
  :rule-classes :rewrite)

Theorem: supremum-type-aux-of-type-fix-type1

(defthm supremum-type-aux-of-type-fix-type1
  (equal (supremum-type-aux (type-fix type1)
                            type2 defined-names tops)
         (supremum-type-aux type1 type2 defined-names tops)))

Theorem: supremum-type-aux-type-equiv-congruence-on-type1

(defthm supremum-type-aux-type-equiv-congruence-on-type1
 (implies
   (type-equiv type1 type1-equiv)
   (equal (supremum-type-aux type1 type2 defined-names tops)
          (supremum-type-aux type1-equiv type2 defined-names tops)))
 :rule-classes :congruence)

Theorem: supremum-type-aux-of-type-fix-type2

(defthm supremum-type-aux-of-type-fix-type2
  (equal (supremum-type-aux type1 (type-fix type2)
                            defined-names tops)
         (supremum-type-aux type1 type2 defined-names tops)))

Theorem: supremum-type-aux-type-equiv-congruence-on-type2

(defthm supremum-type-aux-type-equiv-congruence-on-type2
 (implies
   (type-equiv type2 type2-equiv)
   (equal (supremum-type-aux type1 type2 defined-names tops)
          (supremum-type-aux type1 type2-equiv defined-names tops)))
 :rule-classes :congruence)

Theorem: supremum-type-aux-of-identifier-list-fix-defined-names

(defthm supremum-type-aux-of-identifier-list-fix-defined-names
  (equal (supremum-type-aux type1 type2
                            (identifier-list-fix defined-names)
                            tops)
         (supremum-type-aux type1 type2 defined-names tops)))

Theorem: supremum-type-aux-identifier-list-equiv-congruence-on-defined-names

(defthm
 supremum-type-aux-identifier-list-equiv-congruence-on-defined-names
 (implies
   (identifier-list-equiv defined-names defined-names-equiv)
   (equal (supremum-type-aux type1 type2 defined-names tops)
          (supremum-type-aux type1 type2 defined-names-equiv tops)))
 :rule-classes :congruence)

Theorem: supremum-type-aux-of-toplevel-list-fix-tops

(defthm supremum-type-aux-of-toplevel-list-fix-tops
  (equal (supremum-type-aux type1 type2
                            defined-names (toplevel-list-fix tops))
         (supremum-type-aux type1 type2 defined-names tops)))

Theorem: supremum-type-aux-toplevel-list-equiv-congruence-on-tops

(defthm supremum-type-aux-toplevel-list-equiv-congruence-on-tops
 (implies
   (toplevel-list-equiv tops tops-equiv)
   (equal (supremum-type-aux type1 type2 defined-names tops)
          (supremum-type-aux type1 type2 defined-names tops-equiv)))
 :rule-classes :congruence)

Function: supremum-type

(defun supremum-type (type1 type2 tops)
  (declare (xargs :guard (and (typep type1)
                              (typep type2)
                              (toplevel-listp tops))))
  (let ((__function__ 'supremum-type))
    (declare (ignorable __function__))
    (supremum-type-aux type1
                       type2 (get-defined-type-names tops)
                       tops)))

Theorem: maybe-typep-of-supremum-type

(defthm maybe-typep-of-supremum-type
  (b* ((supremum? (supremum-type type1 type2 tops)))
    (maybe-typep supremum?))
  :rule-classes :rewrite)

Theorem: supremum-type-of-type-fix-type1

(defthm supremum-type-of-type-fix-type1
  (equal (supremum-type (type-fix type1)
                        type2 tops)
         (supremum-type type1 type2 tops)))

Theorem: supremum-type-type-equiv-congruence-on-type1

(defthm supremum-type-type-equiv-congruence-on-type1
  (implies (type-equiv type1 type1-equiv)
           (equal (supremum-type type1 type2 tops)
                  (supremum-type type1-equiv type2 tops)))
  :rule-classes :congruence)

Theorem: supremum-type-of-type-fix-type2

(defthm supremum-type-of-type-fix-type2
  (equal (supremum-type type1 (type-fix type2)
                        tops)
         (supremum-type type1 type2 tops)))

Theorem: supremum-type-type-equiv-congruence-on-type2

(defthm supremum-type-type-equiv-congruence-on-type2
  (implies (type-equiv type2 type2-equiv)
           (equal (supremum-type type1 type2 tops)
                  (supremum-type type1 type2-equiv tops)))
  :rule-classes :congruence)

Theorem: supremum-type-of-toplevel-list-fix-tops

(defthm supremum-type-of-toplevel-list-fix-tops
  (equal (supremum-type type1 type2 (toplevel-list-fix tops))
         (supremum-type type1 type2 tops)))

Theorem: supremum-type-toplevel-list-equiv-congruence-on-tops

(defthm supremum-type-toplevel-list-equiv-congruence-on-tops
  (implies (toplevel-list-equiv tops tops-equiv)
           (equal (supremum-type type1 type2 tops)
                  (supremum-type type1 type2 tops-equiv)))
  :rule-classes :congruence)