lang::typecheck::levels

lang/src/typecheck/levels.mo

Level variables: the substitution half of universe polymorphism.

W1.1 put SortLevel and the COMPARISON helpers (level_const, level_eq, level_le, level_lt, sort_level_of, sort_term_of_level, level_of_type) in lang/types.mo, beside the type they operate on. Those all answer a question about a level without walking a Term, so they have no dependency beyond types itself.

These do walk a Term, and that is why they live here instead: subst_levels_term and free_level_vars reuse term_map_children (lang/typecheck/traverse.mo), and traverse imports types -- so putting them in types.mo is an import CYCLE, not a style choice. Measured, not assumed: the first draft of this work had them there and every dependent file failed with unbound variable term_map_children.

Why levels are name-keyed rather than de Bruijn, which is what makes all of this short: a level variable can only be introduced at a DEF BOUNDARY, so it is free by construction. There is no second index space, and term_shift/term_subst/term_permute need no change -- they reach a sort through their existing catch-alls.

defsubst_levels_term#
pub def subst_levels_term (t : Term) (binds : List (Pair Identifier SortLevel)) : Term

Substitute level variables throughout a TERM.

Four lines of real work because term_map_children already walks all of Term's variants; only the sort arm needs saying, since a level is DATA on that node rather than a child (traverse.mo documents Term.sort as a leaf for exactly this reason, which is what makes the catch-all safe here).

defsolve_levels#
pub def solve_levels (param_ty : Term) (actual_ty : Term) (binds : List (Pair Identifier SortLevel)) : List (Pair Identifier SortLevel)

The level instantiation half (W1.4): bind a call site's level variable from one argument.

The rule is deliberately narrow. Only a parameter whose type is literally Sort (var u) contributes, and only when the argument's own inferred type is a sort; u then takes that sort's level, normalized to a concrete numeral when level_const folds it (Sort 1 arrives here as succ (concrete 0) from type_check_sort_full).

First binding wins, and everything else is left FREE rather than defaulted -- the same non-committal discipline solve_typevars documents, and for the same reason: level_le (lang/types.mo) answers false for a variable it cannot evaluate, so guessing a level the call site did not determine turns a missing constraint into a wrong one. Cumulativity is the unifier's job (unify_sort), which is why the MINIMAL binding is the right one here.

Sort (max u v) parameters and non-sort arguments contribute nothing (which of the two operands to bind is not determined); that is the documented completeness gap, not an oversight.

deffree_level_vars#
pub def free_level_vars (t : Term) : List Identifier

Every free level variable in a TERM, in first-seen order.

Spelled out per variant rather than routed through term_map_children, because that combinator REBUILDS a term and this one accumulates a list -- the shapes do not match. The arms that matter are the binders and the sort; everything else either holds no level or holds one only under a child listed here.