News Hacker|极客洞察

27 184 天前 chadnauseam.com
🤔依赖类型之争:概念澄清、可判定性与编译器代价
把类型检查委托给网络服务就安全可靠了吗?

🎯 讨论背景

原帖“Dependent types and how to get rid of them”引发的讨论集中在依赖类型的定义、学习资源与工程取舍上。评论引用了 lambda cube(用于分类类型系统)、CoC(Calculus of Constructions,依赖类型演算)和 ATAPL(与类型理论相关的教材/讲义)等资源,帮助把依赖类型放到更广的类型系统谱系中理解。讨论触及单例类型、类型与值的“宇宙”分层、可判定性问题,以及依赖类型如何模糊编译期与运行期的界限(并提到 const generics、Typeof 等实例)。另有分支把“通过网络请求获取类型”的设想与 LSP 做对比,探讨可重复性与编译器是否应依赖外部服务的风险。

📌 讨论焦点

学习资源与理论框架

评论第一波推荐了 lambda cube 作为理解不同类型系统(从简单类型到依赖类型)之间关系的直观框架,并给出具体链接以便入门。有人贴出自己的博客对 lambda cube 的讲解并分享了实现经验,提到已经实现过 CoC(Calculus of Constructions)的实现。另有评论建议回顾 ATAPL(与类型理论相关的教材/讲义)中相关章节来巩固概念,整体倾向先把依赖类型放在类型系统谱系里学习再深入细节。

[来源1] [来源2] [来源3] [来源4]

依赖类型的本质:类型/值宇宙与单例类型

一位读者对“函数返回类型”如何工作表达了困惑,认为值和值的类型应位于不同的宇宙(universe),并把值看作一种原始元素(ur-element)。回复指出可以把值视为单例类型(singleton types),并把“值参数”当作受约束为单例的类型参数来理解,这是一种 level constraint 的观点;举例如 type Nine int = {9} 作为对 int 的 refinement。讨论还涉及可判定性问题:一旦允许可计算的类型参与类型检查,就可能引入不可判定性,因此编译器需要决定在哪些位置求值或延后求值。关于运行时与编译时的界限,评论提到 const generics 与 typeof(Typeof: (T : type) -> (x:T) -> Type)等例子,说明依赖类型往往模糊了编译期/运行期的边界。

[来源1] [来源2]

对语言与编译器的工程权衡

有评论提出工程角度的权衡:依赖类型在某些情况下反而能简化语言与编译器实现,因为它把类型层和值层统一为一门语言,避免像 Haskell 的 class/instance 层或 C++ 的 template 那样额外实现“元语言”。具体论据包括:Haskell 的 class/instance 本质上是一种建立在 lambda calculus 之上的逻辑编程子语言(可图灵完备),C++ 的模板也是一门复杂的元编程语言,二者都增加了编译器复杂度。相反,对于显式的依赖类型语言,类型检验常化为项等价(term equality),实现编译器变得更直接。然而代价是类型推断(type inference)难以完美,开发者往往需依赖启发式或更多显式注释,不能期望 HM 风格的完全自动推断。

[来源1]

网络取类型的争议(LSP 与编译器的边界)

一条幽默的评论把“pickType 向服务器发网络请求返回类型”的设想比作 LSP(Language Server Protocol),引发关于把类型解析交由网络服务的争论。反对者认为编译过程不应依赖非确定性的网络请求,因为这会破坏可重复性和确定性;支持者或澄清者则指出 LSP 更多是编辑器与语言服务之间的 IPC/网络通信,旨在为编辑器提供类型信息,并不必然改变编译器的核心行为。讨论还触及人们对编辑器容错与编译器稳定性期望的差异——对编辑器的随机崩溃容忍度更高,但对编译器的随机失败更敏感。

[来源1] [来源2] [来源3]

📚 术语解释

lambda cube: 一个将各种带有不同表达力的 λ 演算(如简单类型、泛型、依赖类型等)按维度分类的理论框架,用于比较类型系统的扩展方式。

CoC (Calculus of Constructions): 一种高表达力的依赖类型演算,是多数学术型依赖类型系统(例如 Coq)的理论基础,把类型与项统一在同一形式系统中。

singleton type(单例类型): 把具体值封装为仅包含该值的类型(例如 type Nine = {9}),用于在类型层表达值级约束或作为依赖类型参数。

const generics: 在泛型参数中允许使用常量值(如整数)作为类型参数的机制,常作为依赖类型的有限替代方案以表达基于常量的约束。

Hindley–Milner (HM): 一种经典的类型推断算法(常见于 ML/Haskell 语系),以高度自动化的类型推断著称,但对依赖类型的表达能力有限。

LSP (Language Server Protocol): 编辑器与语言后端通信的协议,用于提供补全、类型信息和诊断等服务,通常通过 IPC 或网络与语言服务进程交互。