Agda- A dependently typed functional programming language and proof assistant

Safe HaskellNone





findIdx :: Eq a => [a] -> a -> Maybe Int Source #

Find position of a value in a list. Used to change metavar argument indices during assignment.

reverse is necessary because we are directly abstracting over the list.

isBlockedTerm :: MetaId -> TCM Bool Source #

Check whether a meta variable is a place holder for a blocked term.

Performing the assignment

assignTerm :: MetaId -> [Arg ArgName] -> Term -> TCM () Source #

Performing the meta variable assignment.

The instantiation should not be an InstV or InstS and the MetaId should point to something Open or a BlockedConst. Further, the meta variable may not be Frozen.

assignTerm' :: MetaId -> [Arg ArgName] -> Term -> TCM () Source #

Skip frozen check. Used for eta expanding frozen metas.

Creating meta variables.

newIFSMeta :: MetaNameSuggestion -> Type -> TCM Term Source #

newIFSMeta s t cands creates a new "implicit from scope" metavariable of type the output type of t with name suggestion s. If t is a function type, then insert enough lambdas in front of it.

newNamedValueMeta :: RunMetaOccursCheck -> MetaNameSuggestion -> Type -> TCM Term Source #

Create a new value meta with specific dependencies.

newValueMeta :: RunMetaOccursCheck -> Type -> TCM Term Source #

Create a new metavariable, possibly η-expanding in the process.

newValueMeta' :: RunMetaOccursCheck -> Type -> TCM Term Source #

Create a new value meta without η-expanding.

newValueMetaCtx' :: RunMetaOccursCheck -> Type -> Telescope -> Permutation -> Args -> TCM Term Source #

Create a new value meta with specific dependencies.

newRecordMeta :: QName -> Args -> TCM Term Source #

Create a metavariable of record type. This is actually one metavariable for each field.

blockTerm :: Type -> TCM Term -> TCM Term Source #

Construct a blocked constant if there are constraints.

unblockedTester :: Type -> TCM Bool Source #

unblockedTester t returns False if t is a meta or a blocked term.

Auxiliary function to create a postponed type checking problem.

postponeTypeCheckingProblem_ :: TypeCheckingProblem -> TCM Term Source #

Create a postponed type checking problem e : t that waits for type t to unblock (become instantiated or its constraints resolved).

postponeTypeCheckingProblem :: TypeCheckingProblem -> TCM Bool -> TCM Term Source #

Create a postponed type checking problem e : t that waits for conditon unblock. A new meta is created in the current context that has as instantiation the postponed type checking problem. An UnBlock constraint is added for this meta, which links to this meta.

problemType :: TypeCheckingProblem -> TCM Type Source #

Type of the term that is produced by solving the TypeCheckingProblem.

etaExpandListeners :: MetaId -> TCM () Source #

Eta expand metavariables listening on the current meta.

wakeupListener :: Listener -> TCM () Source #

Wake up a meta listener and let it do its thing

etaExpandMetaSafe :: MetaId -> TCM () Source #

Do safe eta-expansions for meta (SingletonRecords,Levels).

data MetaKind Source #

Various kinds of metavariables.



Meta variables of record type.


Meta variables of "hereditarily singleton" record type.


Meta variables of level type, if type-in-type is activated.

allMetaKinds :: [MetaKind] Source #

All possible metavariable kinds.

etaExpandMeta :: [MetaKind] -> MetaId -> TCM () Source #

Eta expand a metavariable, if it is of the specified kind. Don't do anything if the metavariable is a blocked term.

etaExpandBlocked :: Reduce t => Blocked t -> TCM (Blocked t) Source #

Eta expand blocking metavariables of record type, and reduce the blocked thing.

Solve constraint x vs = v.

assignV :: CompareDirection -> MetaId -> Args -> Term -> TCM () Source #

Assign to an open metavar which may not be frozen. First check that metavar args are in pattern fragment. Then do extended occurs check on given thing.

Assignment is aborted by throwing a PatternErr via a call to patternViolation. This error is caught by catchConstraint during equality checking (compareAtom) and leads to restoration of the original constraints.

assign :: CompareDirection -> MetaId -> Args -> Term -> TCM () Source #

Miller pattern unification:

assign x vs v solves problem x vs = v for meta x if vs are distinct variables (linearity check) and v depends only on these variables and does not contain x itself (occurs check).

This is the basic story, but we have added some features:

  1. Pruning.
  2. Benign cases of non-linearity.
  3. vs may contain record patterns.

For a reference to some of these extensions, read Andreas Abel and Brigitte Pientka's TLCA 2011 paper.

assignMeta :: Int -> MetaId -> Type -> [Int] -> Term -> TCM () Source #

assignMeta m x t ids u solves x ids = u for meta x of type t, where term u lives in a context of length m. Precondition: ids is linear.

assignMeta' :: Int -> MetaId -> Type -> Int -> SubstCand -> Term -> TCM () Source #

assignMeta' m x t ids u solves x = [ids]u for meta x of type t, where term u lives in a context of length m, and ids is a partial substitution.

subtypingForSizeLt Source #


:: CompareDirection
-> MetaId

The meta variable x.

-> MetaVariable

Its associated information mvar <- lookupMeta x.

-> Type

Its type t = jMetaType $ mvJudgement mvar

-> Args

Its arguments.

-> Term

Its to-be-assigned value v, such that x args dir v.

-> (Term -> TCM ())

Continuation taking its possibly assigned value.

-> TCM () 

Turn the assignment problem _X args <= SizeLt u into _X args = SizeLt (_Y args) and constraint _Y args <= u.

expandProjectedVars :: (Normalise a, TermLike a, Show a, PrettyTCM a, NoProjectedVar a, Subst Term a, PrettyTCM b, Subst Term b) => a -> b -> (a -> b -> TCM c) -> TCM c Source #

Eta-expand bound variables like z in X (fst z).

etaExpandProjectedVar :: (PrettyTCM a, Subst Term a) => Int -> a -> TCM c -> (a -> TCM c) -> TCM c Source #

Eta-expand a de Bruijn index of record type in context and passed term(s).

class NoProjectedVar a where Source #

Check whether one of the meta args is a projected var.

Minimal complete definition


data ProjVarExc Source #


ProjVarExc Int [QName] 

type SubstCand Source #


 = [(Nat, Term)]

a possibly non-deterministic substitution

checkLinearity :: SubstCand -> ExceptT () TCM SubstCand Source #

Turn non-det substitution into proper substitution, if possible. Otherwise, raise the error.

type Res = [(Arg Nat, Term)] Source #

data InvertExcept Source #

Exceptions raised when substitution cannot be inverted.



Cannot recover.


A potentially neutral arg: can't invert, but can try pruning.

ProjectedVar Int [QName]

Try to eta-expand var to remove projs.

inverseSubst :: Args -> ExceptT InvertExcept TCM SubstCand Source #

Check that arguments args to a metavar are in pattern fragment. Assumes all arguments already in whnf and eta-reduced. Parameters are represented as Vars so checkArgs really checks that all args are Vars and returns the "substitution" to be applied to the rhs of the equation to solve. (If args is considered a substitution, its inverse is returned.)

The returned list might not be ordered. Linearity, i.e., whether the substitution is deterministic, has to be checked separately.

updateMeta :: MetaId -> Term -> TCM () Source #

Used in giveExpr.

allMetas :: TermLike a => a -> [MetaId] Source #

Returns every meta-variable occurrence in the given type, except for those in Sorts.