lang::typecheck::unify
lang/src/typecheck/unify.mo
pub def unify (a : Term) (b : Term) (scope : Scope) (locals : LocalScope) : Result TypeError TermStructural type unification. Returns the unified type.
Holes match anything. Pi matches Pi structurally.
App spines are congruent: heads and arguments compare separately.
Lambdas compare the binder's own type, then the bodies.
A lambda against a function-shaped non-lambda eta-expands the other side.
Sorts respect cumulativity (level ≤ expected_level).
A non-explicit binder -- a quantified type variable or a universe level,
which Term.forall used to spell -- is stripped before comparison, on
either side.
Peels both sides at entry rather than adding a Term.ctx arm to each
of the four matches below. Every one of them tests SHAPE with a _ =>
fallback, so a wrapper would not crash -- a wrapped Term.pi would just
fall through to Similar.similar and report a spurious mismatch, which
is the silent kind of wrong.
Placement rule R1 says a wrapper never reaches a type position and so
never reaches here at all. This peels anyway: the recursive calls below
go through unify, so one peel at the top covers every level.
CONVERSION CHECKING. scope/locals are here for definitional
equality: when the structural comparison fails, both sides are
reduced to weak-head normal form (lang/typecheck/whnf.mo) and
compared once more, so a type still written as an unreduced
application (identity_type foo) is compared against what it
computes to (Bool) instead of being rejected on its spelling.
Reduction happens ONLY on the failing path, never at entry. Three reasons, in order of how much they matter:
- Cost.
unifyis hot; this way the succeeding comparison -- the overwhelming majority -- does no extra work at all. - It can only ever ACCEPT more. Reduction is reached exactly where an error was about to be returned, so no program that type-checked before can start failing.
- It bounds the recursion. One retry, on already-reduced operands, cannot re-enter reduction.
#[terminating]: term_peel strictly removes wrappers, so the pair it
hands unify_go is smaller, but that is not a structural subterm the
checker can see.
pub for the drift pin (proofs/src/checker/cubical_props.mo), which
compares the kernel's inlined Equiv against the library's unfolding --
the same precedent as pub whnf and pub equiv_type.