| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Unison.Typechecker.Context.Structure
Description
This module defines the ordered context type and related types used by the typechecking algorithm.
Synopsis
- data Element v loc
- variable :: Element v loc -> v
- declares :: Element v loc -> Maybe v
- data Context v loc
- context0 :: Context v loc
- elements :: Context v loc -> [Element v loc]
- type CtxSegment v loc = [Element v loc]
- data Scope
- scopeOf :: Ord v => v -> Context v loc -> Maybe Scope
- existentialIn :: Ord v => Scope -> v -> Context v loc -> Bool
- universalIn :: Ord v => Scope -> v -> Context v loc -> Bool
- ordered :: Ord v => Context v loc -> v -> v -> Bool
- lookupElement :: Ord v => v -> Context v loc -> Maybe (Element v loc)
- lookupSolved :: Ord v => Context v loc -> v -> Maybe (Monotype v loc)
- lookupAnn :: Ord v => Context v loc -> v -> Maybe (Type v loc)
- annotations :: Context v loc -> [(v, loc, Type v loc)]
- inconsistent :: Context v loc -> Bool
- apply :: Var v => Context v loc -> Type v loc -> Type v loc
- applySegment :: Var v => CtxSegment v loc -> Type v loc -> Type v loc
- unsolvedExistentials :: Ord v => CtxSegment v loc -> Set v
- existentialVars :: Ord v => CtxSegment v loc -> Set v
- recorded :: Ord v => CtxSegment v loc -> Map v (Recorded loc, Type v loc)
- data BadContext
- data Rejected v loc = Rejected (Context v loc) (Element v loc) BadContext
- extend :: Ord v => Element v loc -> Context v loc -> Either BadContext (Context v loc)
- extends :: Ord v => CtxSegment v loc -> Context v loc -> Either (Rejected v loc) (Context v loc)
- replace :: Ord v => v -> CtxSegment v loc -> Context v loc -> Either (Rejected v loc) (Context v loc)
- retract :: Ord v => v -> Context v loc -> Maybe (Context v loc, CtxSegment v loc)
- markRetained :: Ord v => Set v -> Context v loc -> Context v loc
Elements
Elements of an ordered algorithmic context. Every element but Refined
declares its variable; a context is valid when no variable is declared twice and
every type in it mentions only variables declared before it.
Constructors
| Var (TypeVar v loc) | A variable declaration |
| Solved (Blank loc) v (Monotype v loc) |
|
| Ann v loc (Type v loc) |
|
| Refined v (Type v loc) | The (already-declared) universal variable |
| Inconsistent v | Marks the context as inconsistent (the DK indexed-types paper's |
| Marker v | used for scoping |
declares :: Element v loc -> Maybe v Source #
The variable an element declares, if it declares one. A Refined element
constrains a universal declared earlier rather than declaring it.
Contexts
The ordered context of the typechecking algorithm.
The context is a sequence of Elements. The typechecking algorithm appends
to it, retracts a suffix of it (everything after a marker), replaces one
element with a few (e.g. an existential solved to an arrow, with the arrow's
fresh existentials inserted before it), and asks scoping questions: is this
variable declared, as an existential or a universal, and at what position?
Is it solved, and to what?
The sequence only orders the elements. What is known about each variable
is kept in indexes keyed by variable name, beside the sequence, and each of
those maps a variable to a position in the sequence (CtxPosition): every
element in the sequence has one, and vars maps each variable to
its element together with that position.
So for instance, a solution proposed for an existential β may only
mention variables declared before β in the context, existentials and
universals alike (the universals are the rigid type variables of enclosing
quantifiers). solve therefore looks up each free variable of the solution
in vars, checks that it is declared as the kind of variable it occurs
as, and compares its position with β's. Once β is solved, its solution
is read from the same entry. anns and refinements are the same idea for
term variable annotations and for the branch-local refinements of a
universal.
The sequence is a finger tree whose measure includes the greatest position in a
subtree (so that the element at a position can be found in logarithmic time),
and a count of Inconsistent elements (so that inconsistent can tell in
constant time whether the pattern-match branch being checked has been
marked unreachable by contradictory GADT refinements, in which case its
body is skipped).
Every change keeps the indexes describing exactly the elements in the sequence: an append or replacement records the new elements, and a retraction walks the elements it discards and forgets them. Each element is appended once and discarded at most once, so a retraction costs no more than the appends it undoes.
Segments of a context that have been retracted are plain lists
(CtxSegment); the typechecker reads them whole (to generalize over their
unsolved existentials, apply their solutions, or push some of them back).
type CtxSegment v loc = [Element v loc] Source #
A run of elements taken out of a context, in order.
Scope
A place in the context at which scoping questions are asked: at the end, or just before a given element.
scopeOf :: Ord v => v -> Context v loc -> Maybe Scope Source #
The scope just before the given variable's element.
existentialIn :: Ord v => Scope -> v -> Context v loc -> Bool Source #
Whether the variable is declared as an existential, solved or not, within the scope.
universalIn :: Ord v => Scope -> v -> Context v loc -> Bool Source #
Whether the variable is declared as a universal within the scope.
ordered :: Ord v => Context v loc -> v -> v -> Bool Source #
ordered ctx v v2 holds when v is an existential declared before v2's
element: Γ[v^][v2^] in the paper's notation.
Queries
lookupElement :: Ord v => v -> Context v loc -> Maybe (Element v loc) Source #
The element declaring the variable, if any.
annotations :: Context v loc -> [(v, loc, Type v loc)] Source #
Every term variable annotation in the context.
inconsistent :: Context v loc -> Bool Source #
Whether the context holds an Inconsistent element.
apply :: Var v => Context v loc -> Type v loc -> Type v loc Source #
Replace any existentials with their solution in the context, and any refined universals with their refinement.
applySegment :: Var v => CtxSegment v loc -> Type v loc -> Type v loc Source #
apply with the solutions and refinements found in a segment. The maps
are built once per segment, so a partial application to a segment can be
reused over many types.
unsolvedExistentials :: Ord v => CtxSegment v loc -> Set v Source #
The existentials a segment declares and does not solve.
existentialVars :: Ord v => CtxSegment v loc -> Set v Source #
The existentials a segment declares, solved or not.
recorded :: Ord v => CtxSegment v loc -> Map v (Recorded loc, Type v loc) Source #
The existentials of a segment that carry a Recorded blank, with the
type each stands for: its solution, or itself when unsolved.
Updates
data BadContext Source #
Why an element cannot go where it was put.
Constructors
| DuplicateVariable | Its variable is already declared by an element of the context. |
| UndeclaredExistential | Its type mentions an existential not declared before it. |
| UndeclaredUniversal | Its type mentions a universal not declared before it. |
| NotRedeclared | A replacement for a variable's element does not bind the variable again, which would make every later element that mentions it ill-formed. |
Instances
| Show BadContext Source # | |
Defined in Unison.Typechecker.Context.Structure Methods showsPrec :: Int -> BadContext -> ShowS # show :: BadContext -> String # showList :: [BadContext] -> ShowS # | |
| Eq BadContext Source # | |
Defined in Unison.Typechecker.Context.Structure | |
A refused update: the context as it stood (for replace, the elements
before the replaced one plus the replacements accepted so far), the element
refused, and why.
Constructors
| Rejected (Context v loc) (Element v loc) BadContext |
extend :: Ord v => Element v loc -> Context v loc -> Either BadContext (Context v loc) Source #
Adds an element to the end of the context.
extends :: Ord v => CtxSegment v loc -> Context v loc -> Either (Rejected v loc) (Context v loc) Source #
Adds elements to the end of the context, in order.
replace :: Ord v => v -> CtxSegment v loc -> Context v loc -> Either (Rejected v loc) (Context v loc) Source #
Replaces the element declaring a variable with a run of elements, which must bind the variable again (typically last, after fresh existentials its solution mentions). Each replacement is checked in the scope of the replaced element. A variable that is not declared leaves the context as it is.