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 sort shape of each argument and of the result,
- the type and size variables the operator is polymorphic in, with their refinement classes,
- which n-ary variants to generate.
The untyped signature is derived from the typed one by erasure: every shape becomes a plain
Untyped.Term. See Cvc.Gen for the generators.
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
Equations
- One or more equations did not get rendered due to their size.
- Cvc.instReprSizeExpr.repr Cvc.SizeExpr.arity prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.SizeExpr.arity")).group prec✝
Instances For
Equations
- Cvc.instReprSizeExpr = { reprPrec := Cvc.instReprSizeExpr.repr }
Equations
Equations
- Cvc.instBEqSizeExpr.beq (Cvc.SizeExpr.lit a) (Cvc.SizeExpr.lit b) = (a == b)
- Cvc.instBEqSizeExpr.beq (Cvc.SizeExpr.var a) (Cvc.SizeExpr.var b) = (a == b)
- Cvc.instBEqSizeExpr.beq (a.add a_1) (b.add b_1) = (Cvc.instBEqSizeExpr.beq a b && Cvc.instBEqSizeExpr.beq a_1 b_1)
- Cvc.instBEqSizeExpr.beq (a.sub a_1) (b.sub b_1) = (Cvc.instBEqSizeExpr.beq a b && Cvc.instBEqSizeExpr.beq a_1 b_1)
- Cvc.instBEqSizeExpr.beq (a.mul a_1) (b.mul b_1) = (Cvc.instBEqSizeExpr.beq a b && Cvc.instBEqSizeExpr.beq a_1 b_1)
- Cvc.instBEqSizeExpr.beq Cvc.SizeExpr.arity Cvc.SizeExpr.arity = true
- Cvc.instBEqSizeExpr.beq x✝¹ x✝ = false
Instances For
Size variables occurring in a size expression.
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
- int : Shape
- real : Shape
SMT-LIB
Real, rendered asRat. - string : Shape
- regex : Shape
SMT-LIB
RegLan, rendered asRegex. - roundingMode : Shape
SMT-LIB
RoundingMode, rendered asFloat.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; requiresOrdonelm. - bag
(elm : Shape)
: Shape
SMT-LIB bag, rendered as
Bag elm; requiresOrdonelm. - array
(idx elm : Shape)
: Shape
SMT-LIB array, rendered as
TotalMap idx elm; requiresOrdonidx. - fn
(dom cod : Shape)
: Shape
SMT-LIB function, rendered as the Lean arrow
dom → cod.Curried:
fn α (fn β γ)describes the SMT sort(-> α β γ).
Instances For
Equations
- Cvc.instInhabitedShape = { default := Cvc.instInhabitedShape.default }
Equations
- Cvc.instReprShape = { reprPrec := Cvc.instReprShape.repr }
Equations
- One or more equations did not get rendered due to their size.
- Cvc.instReprShape.repr Cvc.Shape.bool prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.Shape.bool")).group prec✝
- Cvc.instReprShape.repr Cvc.Shape.int prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.Shape.int")).group prec✝
- Cvc.instReprShape.repr Cvc.Shape.real prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.Shape.real")).group prec✝
- Cvc.instReprShape.repr Cvc.Shape.string prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.Shape.string")).group prec✝
- Cvc.instReprShape.repr Cvc.Shape.regex prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.Shape.regex")).group prec✝
- Cvc.instReprShape.repr Cvc.Shape.roundingMode prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.Shape.roundingMode")).group prec✝
Instances For
Equations
- Cvc.instBEqShape = { beq := Cvc.instBEqShape.beq }
Equations
- One or more equations did not get rendered due to their size.
Instances For
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.
Equations
Equations
- Cvc.instReprNaryUnit = { reprPrec := Cvc.instReprNaryUnit.repr }
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
Equations
- Cvc.instBEqNaryUnit.beq (Cvc.NaryUnit.bool a) (Cvc.NaryUnit.bool b) = (a == b)
- Cvc.instBEqNaryUnit.beq (Cvc.NaryUnit.int a) (Cvc.NaryUnit.int b) = (a == b)
- Cvc.instBEqNaryUnit.beq x✝¹ x✝ = false
Instances For
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>Nand<id>N', the latter defaulting on 0- and 1-element arrays.
Instances For
Equations
- Cvc.instInhabitedNary = { default := Cvc.instInhabitedNary.default }
Equations
- Cvc.instReprNary = { reprPrec := Cvc.instReprNary.repr }
Equations
- One or more equations did not get rendered due to their size.
- Cvc.instReprNary.repr Cvc.Nary.never prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.Nary.never")).group prec✝
- Cvc.instReprNary.repr Cvc.Nary.array prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.Nary.array")).group prec✝
Instances For
Equations
Instances For
Equations
- Cvc.instBEqNary = { beq := Cvc.instBEqNary.beq }
Equations
- Cvc.instInhabitedAssoc = { default := Cvc.instInhabitedAssoc.default }
Equations
- Cvc.instReprAssoc.repr Cvc.Assoc.left prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.Assoc.left")).group prec✝
- Cvc.instReprAssoc.repr Cvc.Assoc.right prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.Assoc.right")).group prec✝
Instances For
Equations
- Cvc.instReprAssoc = { reprPrec := Cvc.instReprAssoc.repr }
Equations
- Cvc.instBEqAssoc = { beq := Cvc.instBEqAssoc.beq }
Equations
- Cvc.instBEqAssoc.beq x✝ y✝ = (x✝.ctorIdx == y✝.ctorIdx)
Instances For
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 theNfunction.
Instances For
Equations
Equations
- One or more equations did not get rendered due to their size.
- Cvc.instReprNotation.repr Cvc.Notation.none prec✝ = Repr.addAppParen (Std.Format.nest (if prec✝ ≥ 1024 then 1 else 2) (Std.Format.text "Cvc.Notation.none")).group prec✝
Instances For
Equations
- Cvc.instReprNotation = { reprPrec := Cvc.instReprNotation.repr }
Equations
Equations
- Cvc.instBEqNotation.beq Cvc.Notation.none Cvc.Notation.none = true
- Cvc.instBEqNotation.beq (Cvc.Notation.pref a a_1 a_2) (Cvc.Notation.pref b b_1 b_2) = (a == b && (a_1 == b_1 && a_2 == b_2))
- Cvc.instBEqNotation.beq (Cvc.Notation.inf a a_1 a_2) (Cvc.Notation.inf b b_1 b_2) = (a == b && (a_1 == b_1 && a_2 == b_2))
- Cvc.instBEqNotation.beq x✝¹ x✝ = false
Instances For
The symbol of a notation, if any.
Equations
- Cvc.Notation.none.sym? = none
- (Cvc.Notation.pref a a_1 a_2).sym? = some a
- (Cvc.Notation.inf a a_1 a_2).sym? = some a
Instances For
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
Equations
- Cvc.instInhabitedValArg = { default := Cvc.instInhabitedValArg.default }
Equations
- Cvc.instReprValArg = { reprPrec := Cvc.instReprValArg.repr }
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- Cvc.instBEqValArg = { beq := Cvc.instBEqValArg.beq }
Equations
- Cvc.instInhabitedArg = { default := Cvc.instInhabitedArg.default }
Equations
- Cvc.instReprArg = { reprPrec := Cvc.instReprArg.repr }
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- Cvc.instBEqArg = { beq := Cvc.instBEqArg.beq }
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.
- name : Lean.Name
Name of the type variable.
Refinement classes, such as
IsArith.
Instances For
Equations
- Cvc.instInhabitedTyVar = { default := Cvc.instInhabitedTyVar.default }
Equations
- One or more equations did not get rendered due to their size.
Instances For
Equations
- Cvc.instReprTyVar = { reprPrec := Cvc.instReprTyVar.repr }
Equations
- Cvc.instBEqTyVar = { beq := Cvc.instBEqTyVar.beq }
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.
- id : Lean.Name
Name of the generated function, such as
and. - kind : Lean.Name
Constructor of
cvc5.Kind, such asAND.For an entry built by a
TermManagermethod this is still the kind the resulting term has, even though the term is not built by applying it. TermManagermethod building the term, when it is not built by applyingkind.Nullary constants have no
mkTermform:SET_EMPTYismkEmptySet,PIismkPi, and so on. Where the sort cannot be inferred from the arguments, the generated function takes oneSrtper type variable the arguments leave free and builds what the method wants from those.Shape whose sort the
tmFnmethod 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;
mkEmptySequencewants the element sort instead, which is what this records.- doc : String
Docstring of the generated fixed-arity function.
Type variables, with their refinement classes.
Size variables, bound as implicit
Nats and inferred from the arguments.Operator indices, bound as explicit
Nats ahead of the term arguments.An indexed operator is built by applying an
Opcarrying these values, rather than by applying the kind directly. They are what SMT-LIB writes as(_ extract hi lo).Value parameters, in order, ahead of the term arguments.
Arguments, in order.
- ret : Shape
Sort shape of the result.
- nary : Nary
Which n-ary variants to generate.
Name of the n-ary variant, when
<id>Nis not the right one.The
Nsuffix 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
Equations
- Cvc.instInhabitedOpSpec = { default := Cvc.instInhabitedOpSpec.default }
Equations
- Cvc.instReprOpSpec = { reprPrec := Cvc.instReprOpSpec.repr }
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
- spec.unboundRetVars = Array.filter (fun (x : Lean.Name) => !(Array.flatMap (fun (x : Cvc.Arg) => x.shape.typeVars) spec.args).contains x) spec.ret.typeVars
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
TermManagermethod rather than a kind; - an indexed operator is out — it is applied through an
Opcarrying its indices, and there is no way to hand one tomkNullableLift; - 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.
Registers an operator specification.
Equations
- Cvc.registerOpSpec spec = Lean.modifyEnv fun (x : Lean.Environment) => Lean.PersistentEnvExtension.addEntry Cvc.opSpecExt x (spec.id, spec)
Instances For
Looks an operator specification up by name.
Equations
- Cvc.findOpSpec? id = do let __do_lift ← Lean.getEnv pure ((Cvc.opSpecExt.getState __do_lift).get? id)
Instances For
Number of registered specifications, used to stamp declaration order.
Equations
- Cvc.opSpecCount = do let __do_lift ← Lean.getEnv pure (Cvc.opSpecExt.getState __do_lift).size
Instances For
Every specification declared in a module, in declaration order.
Equations
- One or more equations did not get rendered due to their size.