Skip to content

依赖类型 elaboration

Dependent type elaboration · Elaboration of dependent types

把含隐式参数、洞与模式的表面程序约束求解为可由小型依赖核心检查的显式项。

条目类型
方法

形式陈述

Elaboration 区分便于书写的 surface language 与规则精小的 core theory。可把核心接口写成两种带输出的判断:

ΓeAt,ΓeAt,

前者从表面项 e 综合类型 A 并产生核心项 t,后者在期望类型 A 下检查并产生 t。这复用双向类型检查的信息流,但依赖情形还要插入隐式参数、求 universe level、解 metavariable,并反复调用定义相等核对依赖余类型。可靠性要求 elaboration 成功后确有 Γt:A;若声明 surface 与 core 的擦除关系 |t|=e,还应证明生成项保留约定的运行含义。

应用规则可先综合 f:Π(x:A).B,检查实参得到 u:A,再输出 fu:B[u/x]。遇到隐式 Π 参数时,elaborator 生成 metavariable ?m:A,把 B[?m/x] 与后续期望类型产生约束;约束求解若给出替换 θ,最终核心项必须施加 θ 且不残留未解决必需洞。依赖模式匹配还需经 coverage 与 index unification 生成 eliminator 或 case tree,而不直接成为内核信任的任意分支语法。

完备性只能相对于明确的 surface 设计陈述:某些声明式可定型项需要用户注解、显式 motive 或搜索提示;高阶 unification 与实例搜索一般没有同时终止且完备的算法。Elaboration 失败也不等于核心命题不可证,只说明当前信息流和搜索策略未找到项。

直觉

表面语言允许人省略显然信息,核心语言要求机器把每个依赖关系写清。Elaborator 就像排版前的技术编辑:根据上下文补上宇宙层、隐式类型参数和强制运输,把模式子句重排成核心消去;最后由独立内核检查成稿,而不是要求用户信任编辑过程没有猜错。

依赖类型让这种补全具有反馈回路。选择一个隐式实参会改变后续参数的类型,后续显式实参又可能反过来确定先前的 metavariable。双向方向标记限制信息流,约束队列保存尚未确定的部分;二者共同把全局猜测缩小成可管理的局部求解,却不能消灭固有歧义。

例子与边界

设核心恒等函数为

id:Π{A:U0}.AA.

表面项 id true 没写隐式 A。elaborator 先输出候选 id{?A}true,再由 true:Bool 产生约束 ?ABool,求解后得到核心项

id{Bool}true:Bool.

若期望类型已经是 Bool,checking 方向可更早传播该信息。对

append:Π{m,n}.Vec(A,m)Vec(A,n)Vec(A,m+n),

调用 append xs ys 会从两个向量的类型恢复 m,n,再把结果类型实例化;这不是运行时读取长度,而是解 typing constraints。

边界例子是 λx. x 处在 synthesis 位置且没有注解:x 的类型无来源,系统可拒绝或要求 annotation,不能凭“显然是恒等函数”选择某一个宇宙与类型。另一个边界是方程 ?Fxt 的高阶求解;若允许任意 metavariable 函数,可能有多个不可比较解或进入不可判定搜索。实现常采用 pattern unification、occurs check、冻结约束与用户交互,这些是有意限定的完备范围,不应包装成一般依赖类型推断。

推论与应用

Elaboration 把丰富语法与小可信内核分离。notation、type class、coercion、record projection 和 tactic 可以在不扩张核心证明规则的情况下加入,只要最终生成的项通过检查。这种架构还改善错误定位:约束记录了哪一个隐式选择导致类型冲突,编辑器可展示尚未解决洞的局部语境与目标。

分离也明确了信任边界。Elaborator 有 bug 时可能拒绝合法程序或生成错误项,但健全内核会拦下后者;若编译器绕过重检、让未解 metavariable 成为任意常量,可靠性便失效。性能优化如缓存规范形、增量约束求解和启发式实例搜索都必须保持最终 core judgment 不变。

参考资料
  • Ulf Norell, Towards a Practical Programming Language Based on Dependent Type Theory, PhD thesis, Chalmers University of Technology, 2007,metavariables、dependent pattern matching 与 Agda elaboration。
  • Jana Dunfield and Neel Krishnaswami, “Bidirectional Typing,” ACM Computing Surveys 54(5), 2021, Article 98,双向规则、注解与 elaboration 的可靠性/完备性框架。
  • The Agda Team, Agda User Manual, “Implicit Arguments,” “Metavariables,” and “Coverage Checking” sections,现代依赖语言的 surface-to-core 机制,accessed 2026。
关系图谱12 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系