Documentation

Cvc.Spec.Defs

Term-creation specification #

This module defines the data describing how to build the term constructors for a cvc5 term kind, and the environment extension storing that data.

A specification entry is written once, in the typed form, and describes everything both layers need:

The untyped signature is derived from the typed one by erasure: every shape becomes a plain Untyped.Term. See Cvc.Gen for the generators.

inductive Cvc.SizeExpr :

Natural-number expression describing a sort index, such as a bit-vector size.

Size variables are bound by the enclosing OpSpec, either as a size binder or as an operator index. Arithmetic is needed by operators whose result index is computed: BITVECTOR_CONCAT sums its arguments' sizes, BITVECTOR_EXTRACT yields hi - lo + 1, BITVECTOR_REPEAT yields n * k.

Subtraction is Nat subtraction, so it truncates at zero.

  • lit (n : Nat) : SizeExpr

    Literal size.

  • var (name : Lean.Name) : SizeExpr

    Size variable, bound by the enclosing OpSpec.

  • add (lft rgt : SizeExpr) : SizeExpr

    Sum of two sizes.

  • sub (lft rgt : SizeExpr) : SizeExpr

    Truncated difference of two sizes.

  • mul (lft rgt : SizeExpr) : SizeExpr

    Product of two sizes.

  • arity : SizeExpr

    The operator's own arity: how many term arguments it was applied to.

    For a result whose size is not a function of its arguments' sorts but of how many there are. In the fixed-arity constructor this is a literal; in the n-ary one it is the term array's size, which makes that signature depend on a runtime value. No entry currently uses it.

Instances For
    Equations
    Instances For
      @[instance_reducible]
      Equations
      @[instance_reducible]
      Equations

      Size variables occurring in a size expression.

      inductive Cvc.Shape :

      Sort shape: Typ extended with type variables and size arithmetic.

      A shape describes the sort of an argument or result as the typed layer sees it. Two operations are defined on shapes:

      • erasure, which forgets the shape entirely and yields the untyped signature, where every argument and the result are plain Untyped.Terms;
      • rendering, which turns the shape into the Lean type indexing a Typed.Term.
      • var (name : Lean.Name) : Shape

        Type variable, bound by the enclosing OpSpec.

      • bool : Shape

        SMT-LIB Bool, rendered as Bool.

      • int : Shape

        SMT-LIB Int, rendered as Int.

      • real : Shape

        SMT-LIB Real, rendered as Rat.

      • string : Shape

        SMT-LIB String, rendered as String.

      • regex : Shape

        SMT-LIB RegLan, rendered as Regex.

      • roundingMode : Shape

        SMT-LIB RoundingMode, rendered as Float.RoundingMode.

      • bitVec (size : SizeExpr) : Shape

        SMT-LIB bit-vector, rendered as BitVec size.

      • float (exp sig : SizeExpr) : Shape

        SMT-LIB floating point, rendered as Float exp sig.

      • finiteField (size : SizeExpr) : Shape

        SMT-LIB finite field, rendered as FiniteField size.

      • seq (elm : Shape) : Shape

        SMT-LIB sequence, rendered as Array elm.

      • set (elm : Shape) : Shape

        SMT-LIB set, rendered as Set elm; requires Ord on elm.

      • bag (elm : Shape) : Shape

        SMT-LIB bag, rendered as Bag elm; requires Ord on elm.

      • array (idx elm : Shape) : Shape

        SMT-LIB array, rendered as TotalMap idx elm; requires Ord on idx.

      • fn (dom cod : Shape) : Shape

        SMT-LIB function, rendered as the Lean arrow dom → cod.

        Curried: fn α (fn β γ) describes the SMT sort (-> α β γ).

      Instances For
        @[instance_reducible]
        Equations
        Equations
        Instances For
          @[instance_reducible]
          Equations
          Equations
          • One or more equations did not get rendered due to their size.
          Instances For

            Type variables occurring in a shape.

            Size variables occurring in a shape.

            Type variables that need an Ord instance, because they index a Set, Bag or TotalMap.

            Set, Bag and TotalMap are Std.TreeSet/Std.TreeMap wrappers, so their element (respectively index) type must be ordered.

            inductive Cvc.NaryUnit :

            Unit element used by an n-ary operator's N' variant on an empty term array.

            • bool (b : Bool) : NaryUnit

              Boolean literal, built with Term.mkBool.

            • int (i : Int) : NaryUnit

              Integer literal, built with Term.mkInt.

            Instances For
              @[instance_reducible]
              Equations
              Equations
              • One or more equations did not get rendered due to their size.
              Instances For
                @[instance_reducible]
                Equations
                inductive Cvc.Nary :

                Whether, and how, to generate n-ary variants of an operator.

                • never : Nary

                  Fixed arity only.

                • array : Nary

                  Also generate <id>N, taking a term array with at least two elements.

                • arrayWithUnit (unit : NaryUnit) : Nary

                  Also generate <id>N and <id>N', the latter defaulting on 0- and 1-element arrays.

                Instances For
                  @[instance_reducible]
                  Equations
                  Equations
                  Instances For
                    @[instance_reducible]
                    Equations
                    inductive Cvc.Assoc :

                    Associativity of an infix notation.

                    • left : Assoc

                      Left-associative: a - b - c is (a - b) - c.

                    • right : Assoc

                      Right-associative: a ∧ b ∧ c is a ∧ (b ∧ c).

                    Instances For
                      Equations
                      Instances For
                        @[instance_reducible]
                        Equations
                        @[instance_reducible]
                        Equations
                        Equations
                        Instances For
                          inductive Cvc.Notation :

                          Surface notation for an operator in the smt! DSL.

                          The generated grammar rule is named …smtOp.<shape>.<id>, and the expander in Cvc.Ext dispatches on the last three components of that node kind. That convention is what lets the grammar be generated per theory while the expansion logic stays written once.

                          • none : Notation

                            No surface notation; the operator is reachable as a function only.

                          • pref (sym : String) (prec argPrec : Nat) : Notation

                            Prefix notation such as ¬ t, with the rule's precedence and its argument's.

                          • inf (sym : String) (prec : Nat) (assoc : Assoc) : Notation

                            Infix notation such as a ∧ b.

                            When the operator also has an n-ary variant, the bracket form sym[a, b, …] is generated alongside and expands to the N function.

                          Instances For
                            Equations
                            Instances For
                              @[instance_reducible]
                              Equations
                              @[instance_reducible]
                              Equations

                              The symbol of a notation, if any.

                              Equations
                              Instances For
                                structure Cvc.ValArg :

                                A value parameter: a plain Lean argument, passed to the constructor as-is.

                                Constructors take data that is not a term — the Bool of a boolean literal, the String of a symbol's name, the numeral behind a bit-vector. Such a parameter is emitted unchanged in both layers, since there is no sort to erase.

                                • name : Lean.Name

                                  Name of the generated parameter.

                                • type : Lean.Name

                                  Lean type of the parameter, emitted verbatim.

                                Instances For
                                  @[instance_reducible]
                                  Equations
                                  Equations
                                  • One or more equations did not get rendered due to their size.
                                  Instances For
                                    Equations
                                    Instances For
                                      @[instance_reducible]
                                      Equations
                                      structure Cvc.Arg :

                                      One argument of an operator.

                                      • name : Lean.Name

                                        Name of the generated parameter.

                                      • shape : Shape

                                        Sort shape of the argument.

                                      Instances For
                                        @[instance_reducible]
                                        Equations
                                        Equations
                                        • One or more equations did not get rendered due to their size.
                                        Instances For
                                          Equations
                                          Instances For
                                            @[instance_reducible]
                                            Equations
                                            structure Cvc.TyVar :

                                            A type variable of an operator, together with the refinement classes it must satisfy.

                                            Refinement classes are emitted as instance binders by the typed generator and dropped by the untyped one, which has no index to constrain.

                                            Instances For
                                              Equations
                                              • One or more equations did not get rendered due to their size.
                                              Instances For
                                                @[instance_reducible]
                                                Equations
                                                @[instance_reducible]
                                                Equations
                                                Equations
                                                Instances For
                                                  structure Cvc.OpSpec :

                                                  Everything needed to generate the typed and untyped constructors for one term kind.

                                                  The entry is keyed by id, the name of the generated function; kind is the cvc5.Kind constructor the term is built with, and is checked to exist when the entry is declared.

                                                  • Name of the generated function, such as and.

                                                  • kind : Lean.Name

                                                    Constructor of cvc5.Kind, such as AND.

                                                    For an entry built by a TermManager method this is still the kind the resulting term has, even though the term is not built by applying it.

                                                  • TermManager method building the term, when it is not built by applying kind.

                                                    Nullary constants have no mkTerm form: SET_EMPTY is mkEmptySet, PI is mkPi, and so on. Where the sort cannot be inferred from the arguments, the generated function takes one Srt per type variable the arguments leave free and builds what the method wants from those.

                                                  • sortArg : Option Shape

                                                    Shape whose sort the tmFn method wants, when it is not the result's own.

                                                    This does not reach the generated signature. A constructor always takes the sorts of the type variables its arguments leave free — the element sorts — and the generator builds what cvc5 asks for out of them. Most methods want the sort of the term they build; mkEmptySequence wants the element sort instead, which is what this records.

                                                  • doc : String

                                                    Docstring of the generated fixed-arity function.

                                                  • tyVars : Array TyVar

                                                    Type variables, with their refinement classes.

                                                  • sizeVars : Array Lean.Name

                                                    Size variables, bound as implicit Nats and inferred from the arguments.

                                                  • indices : Array Lean.Name

                                                    Operator indices, bound as explicit Nats ahead of the term arguments.

                                                    An indexed operator is built by applying an Op carrying these values, rather than by applying the kind directly. They are what SMT-LIB writes as (_ extract hi lo).

                                                  • valArgs : Array ValArg

                                                    Value parameters, in order, ahead of the term arguments.

                                                  • args : Array Arg

                                                    Arguments, in order.

                                                  • ret : Shape

                                                    Sort shape of the result.

                                                  • nary : Nary

                                                    Which n-ary variants to generate.

                                                  • naryName : Option Lean.Name

                                                    Name of the n-ary variant, when <id>N is not the right one.

                                                    The N suffix suits an operator whose n-ary form is the same operation at greater arity. It does not suit one where the distinction is singular versus plural, a bit against several bits.

                                                  • smtNotation : Notation

                                                    Surface notation in the smt! DSL.

                                                  • declaredIn : Lean.Name

                                                    Module the entry was declared in, so that a generator can select a whole theory.

                                                  • order : Nat

                                                    Declaration order, so that generated constructors come out in specification order.

                                                  Instances For
                                                    @[instance_reducible]
                                                    Equations
                                                    Equations
                                                    • One or more equations did not get rendered due to their size.
                                                    Instances For

                                                      Type variables that need an Ord instance, across all arguments and the result.

                                                      Equations
                                                      • One or more equations did not get rendered due to their size.
                                                      Instances For

                                                        Type variables occurring in the result but in no argument.

                                                        Such a variable is lost by erasure: the untyped constructor takes the result sort explicitly while the typed one recovers it from its index. Applying a kind always infers the sort from the arguments, so this is empty for every kind-built entry, and op% rejects one where it is not. It is exactly the constructors — the tmFn entries — that need it.

                                                        Equations
                                                        Instances For

                                                          Whether the operator has a version lifted over nullables.

                                                          mkNullableLift takes a Kind and the terms to apply it to, and nothing else, which is what decides this:

                                                          • a constructor is out — it has no term argument to be null, and it builds through a TermManager method rather than a kind;
                                                          • an indexed operator is out — it is applied through an Op carrying its indices, and there is no way to hand one to mkNullableLift;
                                                          • value parameters are out for the same reason, having nowhere to go in the lifted lambda. They only ever occur on constructors, so this rules nothing else out.
                                                          Equations
                                                          Instances For

                                                            Environment extension holding every declared OpSpec, keyed by OpSpec.id.

                                                            Entries are added by the op% command and read by gen_untyped%/gen_typed%. Going through an extension is what lets the specification live in one module while generation happens in per-theory modules of both layers.

                                                            def Cvc.registerOpSpec {m : Type → Type} [Monad m] [Lean.MonadEnv m] (spec : OpSpec) :

                                                            Registers an operator specification.

                                                            Equations
                                                            Instances For

                                                              Looks an operator specification up by name.

                                                              Equations
                                                              Instances For
                                                                def Cvc.opSpecCount {m : Type → Type} [Monad m] [Lean.MonadEnv m] :
                                                                m Nat

                                                                Number of registered specifications, used to stamp declaration order.

                                                                Equations
                                                                Instances For
                                                                  def Cvc.opSpecsOf {m : Type → Type} [Monad m] [Lean.MonadEnv m] (mod : Lean.Name) :

                                                                  Every specification declared in a module, in declaration order.

                                                                  Equations
                                                                  • One or more equations did not get rendered due to their size.
                                                                  Instances For