# Documentation

Lean.Meta.SynthInstance

Equations
Instances For
Equations
Instances For
Equations
Equations

In tabled resolution, we creating a mapping from goals (e.g., Coe Nat ?x) to answers and waiters. Waiters are consumer nodes that are waiting for answers for a particular node.

We implement this mapping using a HashMap where the keys are normalized expressions. That is, we replace assignable metavariables with auxiliary free variables of the form _tc.. We do not declare these free variables in any local context, and we should view them as "normalized names" for metavariables. For example, the term f ?m ?m ?n is normalized as f _tc.0 _tc.0 _tc.1.

This approach is structural, and we may visit the same goal more than once if the different occurrences are just definitionally equal, but not structurally equal.

Remark: a metavariable is assignable only if its depth is equal to the metavar context depth.

Instances For
@[inline]
Equations
@[always_inline]
Equations
• One or more equations did not get rendered due to their size.
def Lean.Meta.SynthInstance.mkTableKey {m : } [inst : ] [inst : ] (e : Lean.Expr) :

Remark: mkTableKey assumes e does not contain assigned metavariables.

Equations
• One or more equations did not get rendered due to their size.
Instances For
Equations
• waiters :
Instances For
• maxResultSize : Nat
• maxHeartbeats : Nat
Instances For
• result? :
• generatorStack :
• resumeStack :
• tableEntries :

Remark: the SynthInstance.State is not really an extension of Meta.State. The field postponed is not needed, and the field mctx is misleading since synthInstance methods operate over different MetavarContexts simultaneously. That being said, we still use extends because it makes it simpler to move from M to MetaM.

Instances For
@[inline]
Equations
Equations
@[inline]
def Lean.Meta.SynthInstance.mapMetaM (f : {α : Type} → ) {α : Type} :
Equations
Equations
• Lean.Meta.SynthInstance.instInhabitedSynthM = { default := fun x x => default }

Return globals and locals instances that may unify with type

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

Create a new generator node for mvar and add waiter as its waiter. key must be mkTableKey mctx mvarType.

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

Create a key for the goal associated with the given metavariable. That is, we create a key for the type of the metavariable.

We must instantiate assigned metavariables before we invoke mkTableKey.

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

See getSubgoals and getSubgoalsAux

We use the parameter j to reduce the number of instantiate* invocations. It is the same approach we use at forallTelescope and lambdaTelescope. Given getSubgoalsAux args j subgoals instVal type, we have that type.instantiateRevRange j args.size args does not have loose bound variables.

Instances For

getSubgoals lctx localInsts xs inst creates the subgoals for the instance inst. The subgoals are in the context of the free variables xs, and (lctx, localInsts) is the local context and instances before we added the free variables to it.

This extra complication is required because 1- We want all metavariables created by synthInstance to share the same local context. 2- We want to ensure that applications such as mvar xs are higher order patterns.

The method getGoals create a new metavariable for each parameter of inst. For example, suppose the type of inst is forall (x_1 : A_1) ... (x_n : A_n), B x_1 ... x_n. Then, we create the metavariables ?m_i : forall xs, A_i, and return the subset of these metavariables that are instance implicit arguments, and the expressions:

• inst (?m_1 xs) ... (?m_n xs) (aka instVal)
• B (?m_1 xs) ... (?m_n xs)
Equations
• One or more equations did not get rendered due to their size.

Try to synthesize metavariable mvar using the instance inst. Remark: mctx is set using withMCtx. If it succeeds, the result is a new updated metavariable context and a new list of subgoals. A subgoal is created for each instance implicit parameter of inst.

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

Assign a precomputed answer to mvar. If it succeeds, the result is a new updated metavariable context and a new list of subgoals.

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

Move waiters that are waiting for the given answer to the resume stack.

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

Create a new answer after cNode resolved all subgoals. That is, cNode.subgoals == []. And then, store it in the tabled entries map, and wakeup waiters.

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

Process the next subgoal in the given consumer node.

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

Try the next instance in the node on the top of the generator stack.

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

Given (cNode, answer) on the top of the resume stack, continue execution by using answer to solve the next subgoal.

Equations
• One or more equations did not get rendered due to their size.
Equations
• One or more equations did not get rendered due to their size.
Equations
def Lean.Meta.SynthInstance.main (type : Lean.Expr) (maxResultSize : Nat) :
Equations
• One or more equations did not get rendered due to their size.

Type class parameters can be annotated with outParam annotations.

Given C a_1 ... a_n, we replace a_i with a fresh metavariable ?m_i IF a_i is an outParam. The result is type correct because we reject type class declarations IF it contains a regular parameter X that depends on an out parameter Y.

Then, we execute type class resolution as usual. If it succeeds, and metavariables ?m_i have been assigned, we try to unify the original type C a_1 ... a_n witht the normalized one.

Remark: when maxResultSize? == none, the configuration option synthInstance.maxResultSize is used. Remark: we use a different option for controlling the maximum result size for coercions.

def Lean.Meta.synthInstance? (type : Lean.Expr) (maxResultSize? : optParam () none) :
Equations
• One or more equations did not get rendered due to their size.
Equations
• One or more equations did not get rendered due to their size.
def Lean.Meta.trySynthInstance (type : Lean.Expr) (maxResultSize? : optParam () none) :

Return LOption.some r if succeeded, LOption.none if it failed, and LOption.undef if instance cannot be synthesized right now because type contains metavariables.

Equations
• One or more equations did not get rendered due to their size.
def Lean.Meta.synthInstance (type : Lean.Expr) (maxResultSize? : optParam () none) :
Equations
• One or more equations did not get rendered due to their size.