rzk-0.11.3: An experimental proof assistant for synthetic ∞-categories
Safe HaskellNone
LanguageHaskell2010

Rzk.TypeCheck.Context

Description

The typing context on free-foil.

The successor of Rzk.TypeCheck's Context var. Two things change, and they are the point of the migration.

A variable is a name, and so is a top-level entry.
A free-foil term refers to a variable by Name (an Int), and by nothing else: there is no way to put a VarIdent inside a term. So a top-level definition is a name too, bound in the outermost scope with no binder above it, and the hypotheses — global and local alike — are one NameMap, looked up in constant time. The old context was an association list keyed by a var whose equality walked an S-chain; lookupVarInfo alone was 11.5% of the checker's time. The surface name of an entry is resolved through ctxNamed.

This also gives sections their natural shape. A #assumed assumption is an ordinary binder, so the definitions of a section are checked in its scope, and closing the section abstracts the assumption by pairing its binder with the body — no rewrite of the elaborated terms (see Rzk.TypeCheck.Decl).

Entering a binder rebuilds nothing.
enterBinder extends the scope and sinks the rest of the context by coercion, so it costs O(1) rather than a walk of the context. The old enterScopeContext mapped S <$> over the whole context, rebuilding every elaborated term it held; the heap profile showed those forced copies retaining most of the live heap, and GlobalScopeInfo / globalEmbed (PR #277) exist only to keep that shift off the ~1500 top-level entries. All of that machinery is gone.
Synopsis

The pieces of a context

data Covariance Source #

Constructors

Covariant

Positive position.

Contravariant

Negative position.

Invariant

Unknown position.

data Verbosity Source #

Constructors

Debug 
Normal 
Silent 

Instances

Instances details
Eq Verbosity Source # 
Instance details

Defined in Rzk.TypeCheck.Context

Ord Verbosity Source # 
Instance details

Defined in Rzk.TypeCheck.Context

data LocationInfo Source #

Where a diagnostic points.

The line and column are the start of whatever the diagnostic is about: the declaration being checked, narrowed to the sub-term as the checker descends into it (see narrowLocation in Rzk.TypeCheck.Monad). The surface syntax records the start of a node and not its extent, so there is no end position to carry.

Instances

Instances details
Show LocationInfo Source # 
Instance details

Defined in Rzk.TypeCheck.Context

Eq LocationInfo Source # 
Instance details

Defined in Rzk.TypeCheck.Context

atPosition :: RzkPosition -> LocationInfo -> LocationInfo Source #

Point a location at a position in the same file.

data VarInfo (n :: S) Source #

What is known about a hypothesis, local or top-level.

Constructors

VarInfo 

Fields

Instances

Instances details
Sinkable VarInfo Source # 
Instance details

Defined in Rzk.TypeCheck.Context

Methods

sinkabilityProof :: forall (n :: S) (l :: S). (Name n -> Name l) -> VarInfo n -> VarInfo l #

data DataRole (n :: S) Source #

The role a top-level entry plays for a #data declaration. The ι-rule (in Eval) recognises an eliminator head and a constructor-headed scrutinee by these; both entries are otherwise opaque (they carry no value).

The argument counts speak of the entry's elaborated type: a constructor takes the datatype's parameters and then its own fields; an eliminator takes the parameters, the motive, one method per constructor (in declaration order), and the scrutinee. Closing a section prepends the section's assumptions uniformly to all entries of a declaration, so abstractOver bumps the parameter counts.

Constructors

DataRole 

Fields

data DataRoleKind Source #

Constructors

DataConKind ConSort Int Int [Int]

a constructor: its sort, its 0-based position among the constructors (= the method index), the number of its own fields after the parameters, and the 0-based positions of its recursive fields (each contributes an induction hypothesis right after the field in the method)

DataElimKind Int Int ElimKind

an eliminator: the number of methods (one per constructor, in declaration order) and the number of indices of the family; the spine is parameters, motive, methods, indices, scrutinee

data ConSort Source #

A point constructor inhabits the datatype and the ι-rule dispatches on it as a scrutinee head. A path constructor inhabits an identity type over the datatype, so it can never head a well-typed scrutinee, and the ι-rule must not fire on it: its computation rule is the propositional compute- lemma generated alongside the eliminators.

Constructors

PointCon 
PathCon 

Instances

Instances details
Eq ConSort Source # 
Instance details

Defined in Rzk.TypeCheck.Context

Methods

(==) :: ConSort -> ConSort -> Bool #

(/=) :: ConSort -> ConSort -> Bool #

data ElimKind Source #

Which eliminator; the ι-rule is the same for both.

Constructors

ElimInd 
ElimRec 

Instances

Instances details
Eq ElimKind Source # 
Instance details

Defined in Rzk.TypeCheck.Context

bumpDataRoleParams :: forall (n :: S). DataRole n -> DataRole n Source #

Add one leading parameter (a section assumption made explicit).

data ModalTope (n :: S) Source #

A tope, together with the modalities under which it is available.

Constructors

ModalTope 

Instances

Instances details
Sinkable ModalTope Source # 
Instance details

Defined in Rzk.TypeCheck.Context

Methods

sinkabilityProof :: forall (n :: S) (l :: S). (Name n -> Name l) -> ModalTope n -> ModalTope l #

data Action (n :: S) Source #

The judgement being performed, for tracing and for the error report.

data CachedSaturation (n :: S) Source #

The state of the tope-saturation cache in a Context (see ctxTopesSaturated).

Constructors

SaturationUncached

No cache was installed for this tope context (entailment falls back to the per-query pipeline).

SaturationCached (Maybe [[ModalTope n]])

A deferred pipeline run: forced by the first query under this context. Nothing records that the pipeline errored; queries then fall back, so the error surfaces exactly where it would have.

The context

data Context (n :: S) Source #

Constructors

Context 

Fields

  • ctxScope :: Scope n

    Every name in scope: the top-level entries, the section assumptions and the binders entered on the way here. Substitution and freshness need it.

  • ctxVars :: NameMap n (VarInfo n)

    What each name in scope stands for. Total on ctxScope, which is what lookupName assumes.

  • ctxNamed :: Map VarIdent (Name n)

    The surface name of each top-level entry (and of each named binder), for resolving an identifier the parser produced.

  • ctxBound :: [Name n]

    Every name in scope, most recently bound first.

    The order has to be recorded, not recovered: free-foil refreshes a binder only when its name clashes, so after a substitution an inner binder may well carry a smaller id than an outer one (\ x2 -> \ x1 -> …), and the ascending order of ctxVars is not the order things were bound in. Display depends on this: names claim their display name oldest-first, so that an inner binder is the one refreshed away from an outer name, and not the other way round.

  • ctxSections :: [SectionInfo n]

    The open sections, innermost first. Each records the entries declared in it, so closing it can turn them into declarations.

  • ctxDiscreteTopes :: [ModalTope n]

    Discreteness axioms for the flat cube variables in scope (a flat point of 2 or I is an endpoint). Maintained at binder entry, so entailment does not rescan the context on every query.

  • ctxTopes :: [ModalTope n]
     
  • ctxTopesNF :: [ModalTope n]
     
  • ctxTopesNFUnion :: [[ModalTope n]]
     
  • ctxTopesEntailBottom :: Maybe Bool
     
  • ctxTopesSaturated :: CachedSaturation n

    The saturated alternatives for this tope context, cached at the points where the tope context changes.

  • ctxShadow :: Map VarIdent [VarIdent]

    The identifiers in scope, keyed by their spelling (a VarIdent compares by spelling and carries the position of its defining occurrence, so the values are what a shadowing report names).

    The check runs at every binder entry, and scanning every name in scope each time was O(context) per binder — with every top-level definition of a project in scope, that is most of them.

  • ctxActionStack :: [Action n]
     
  • ctxActionStackDepth :: Int

    The length of ctxActionStack, maintained alongside it: measuring the list on every judgement made each action cost O(depth), and each path O(depth²).

  • ctxCurrentCommand :: Maybe Command
     
  • ctxLocation :: Maybe LocationInfo
     
  • ctxVerbosity :: Verbosity
     
  • ctxCovariance :: Covariance
     
  • ctxRenderBackend :: Maybe RenderBackend
     
  • ctxRenderHideTerm :: Bool

    When rendering a diagram, hide the proof term: drop the <title> (which carries the full term) from every cell and blank the visible label of proof-coloured (interior) cells, keeping the given boundary labels.

  • ctxHolesAreErrors :: Bool

    When True (the default), an unfilled hole is reported as a TypeErrorUnsolvedHole; finished work (and CI) must have no holes. The lenient mode (allowHoles) instead records each hole's goal and context.

  • ctxDeferHoleMismatches :: Bool

    How holes behave during unification, giving three modes overall. With ctxHolesAreErrors a hole is rejected outright (strict). Otherwise a hole always unifies as a leaf; this flag then chooses what happens when the surrounding structure disagrees: True (the default) defers — any term containing a hole is accepted, for an in-progress sketch — while False keeps such a mismatch an error (structuralHoleUnify).

  • ctxHintLemmas :: [VarIdent]

    Named top-level definitions a hole's candidate list may draw on, beyond the local hypotheses (see withHintLemmas).

  • ctxWarnOverhang :: Bool

    When True, a restriction face or recOR guard that overhangs the local tope context (is not entailed by it, while still overlapping it) is reported with a non-fatal hint. Off by default: deciding the overhang costs a solver entailment per face and guard, and the overhang is legitimate (see happy-restrict-face-not-contained). Enabled with #set-option "warn-overhang" "yes". The disjointness error next to it is unaffected: a vacuous face is always rejected.

  • ctxMetaPrefixSensitivity :: MetaPrefixSensitivity

    How sensitively the meta-parameter layer check classifies use positions (see Rzk.TypeCheck.MetaPrefix). Strict by default; set with #set-option "warn-meta-prefix" = "off" | "structural" | "strict".

data MetaPrefixSensitivity Source #

The sensitivity levels of the meta-parameter layer check.

Constructors

MetaPrefixOff

no meta-prefix warnings

MetaPrefixStructural

warn only at structurally object-level positions

MetaPrefixStrict

additionally require an unsaturated schema argument to sit within a top-level receiver's meta prefix (the default)

data SectionInfo (n :: S) Source #

An open section: the entries declared in it, newest first.

emptyTopeContext :: forall (n :: S). [ModalTope n] Source #

The tope context of an empty context: holds under every modality.

Entering a binder

Everything in a context that mentions the scope is a term, or a container of terms, and so is sinkable: a term whose free names lie in n has its free names in any l that extends n. free-foil sinks such a value by coercion (sink = unsafeCoerce, sound because DExt n l makes the renaming the identity on raw names; see §3.5 of the Foil paper), and the same argument applies to a whole record of them: renaming every field along the identity is the identity on the representation.

Two fields are not sinkable, and enterBinder restores both in the same breath, which is why the coercion below is not exported:

  • ctxScope is the set of names in n. It has to grow, not coerce — tellingly, free-foil gives Scope no Sinkable instance.
  • ctxVars must stay total on the names in scope (lookupName assumes it), so the new binder's entry has to be added.

sinkContextUnchecked :: forall (n :: S) (l :: S). DExt n l => Context n -> Context l Source #

Sink a context along a scope extension. Unsound on its own: leaves ctxScope and ctxVars describing the old scope, and the caller must fix both. See the note above; enterBinder is the only caller.

enterBinder Source #

Arguments

:: forall (n :: S) (l :: S). DExt n l 
=> NameBinder n l 
-> VarInfo n

its type, value and modality

-> [ModalTope l]

discreteness axioms the binder brings (a flat cube point, which are about the variable itself, hence at its scope)

-> Context n 
-> Context l 

Enter the scope of a binder: extend the scope with it, record what it is called and what it stands for, and carry the rest of the context in.

withFreshBinder :: forall (n :: S) r. Distinct n => Context n -> VarInfo n -> (forall (l :: S). DExt n l => NameBinder n l -> Context l -> r) -> r Source #

Enter a fresh binder: one the checker invents rather than one a term carries (to look under a Π when comparing two of them, say).

addBinderNames :: Binder -> Map VarIdent [VarIdent] -> Map VarIdent [VarIdent] Source #

Record the name a binder introduces (if any), for the shadowing check.

shadowedBy :: forall (n :: S). VarIdent -> Context n -> [VarIdent] Source #

The identifiers in scope spelled like this one.

Sinking the parts

sinkVars :: forall (n :: S) (l :: S). DExt n l => NameMap n (VarInfo n) -> NameMap n (VarInfo l) Source #

sinkTopes :: forall (n :: S) (l :: S). DExt n l => [ModalTope n] -> [ModalTope l] Source #

sinkNamed :: forall (n :: S) (l :: S). DExt n l => Map VarIdent (Name n) -> Map VarIdent (Name l) Source #

sinkNames :: forall (n :: S) (l :: S). DExt n l => [Name n] -> [Name l] Source #

Lookup

lookupVarInfo :: forall (n :: S). Name n -> Context n -> VarInfo n Source #

What a name stands for. Total: every name in scope has an entry.

varInfos :: forall (n :: S). Context n -> [VarInfo n] Source #

What every name in scope stands for, in no particular order.

varsInScope :: forall (n :: S). Context n -> [(Name n, VarInfo n)] Source #

Every hypothesis in scope, oldest binding first (see ctxBound: the ids themselves do not tell us this).

lookupNamed :: forall (n :: S). VarIdent -> Context n -> Maybe (Name n) Source #

The name a surface identifier resolves to, if any.

binderOfName :: forall (n :: S). Name n -> Context n -> Binder Source #

The display binder of a name (the whole pattern, for projection folding).

Modalities

class ModeTheory m where Source #

Methods

iden :: m Source #

comp :: m -> m -> m Source #

coe :: m -> m -> Bool Source #

isRA :: m -> Bool Source #

Instances

Instances details
ModeTheory TModality Source # 
Instance details

Defined in Rzk.TypeCheck.Context

applyModality :: forall (n :: S). TModality -> Context n -> Context n Source #

Accumulate a modality (a lock) over the hypotheses and the topes.

Note that top-level entries are not touched: a top-level variable is exempt from the accessibility check (see infer), so accumulating a modality over them was work with no observable effect. The old context did it to all ~1500 of them on every modal binder.

mapNameMap :: forall a b (n :: S). (a -> b) -> NameMap n a -> NameMap n b Source #

Map the values of a name map, keeping its keys.

insertVarInfo :: forall (n :: S). Name n -> VarInfo n -> Context n -> Context n Source #

Replace what a name stands for.

Closing a section rewrites the definitions made in it, so that each takes the section's assumptions as explicit parameters; this is how the rewritten entries go back into the context.

Topes

isAccessible :: forall (n :: S). ModalTope n -> Bool Source #

filterAccessible :: forall (n :: S). [ModalTope n] -> [ModalTope n] Source #

accessibleTopes :: forall (n :: S). [ModalTope n] -> [TermT n] Source #

plainTope :: forall (n :: S). TermT n -> ModalTope n Source #

availableTopes :: forall (n :: S). Context n -> [TermT n] Source #

availableTopesNF :: forall (n :: S). Context n -> [TermT n] Source #

Hole modes

allowHoles :: forall (n :: S). Context n -> Context n Source #

Switch to lenient hole mode: record each hole's goal and context instead of reporting it as an error.

withHintLemmas :: forall (n :: S). [VarIdent] -> Context n -> Context n Source #

Allow a hole's candidate list to draw on the given named top-level definitions, in addition to the local hypotheses.

structuralHoleUnify :: forall (n :: S). Context n -> Context n Source #

Within the given action, a hole unifies only as a leaf of an otherwise matching structure: a structural mismatch around a hole stays an error rather than being deferred (see ctxDeferHoleMismatches).