一般的,判断图灵机m(递归函数,程序)是否有性质P都可以规约到停机问题。
类型系统的做法是在全体有性质P的程序集合S里面划一个子集T,有算法(type checker)可以判断任意代码c是否属于T。若属于T(类型正确),则c必有性质P。若不属于T(类型不正确),则c可能有也可能没有性质P。
类型系统有三个矛盾的目标:
1 T的定义要简单(人能理解)
2 判断T成员的算法要高效(编译器类型检查快)
3 T覆盖尽可能多的S,至少是常用的部分(人不用跟类型系统搏斗)
以上对“判断程序没有内存泄漏”和“判断程序没有访问野指针”同样适用。
这里的区别,可能是能证明前者的类型系统,其T太小(太多没有内存泄漏的程序不能通过类型检查)。
Rust有趣的是它T的定义和判断算法都没有明确,允许编译器越来越“聪明”(允许当前版本不通过类型检查的代码在下个版本更复杂的类型检查算法(扩大了的T)下通过)。
【 在 F001 的大作中提到: 】
: 没什么奇怪的。这两类问题本质上是停机问题,不可能单靠静态检查解决。你读一下我以前写的这篇文章
:
https://zhuanlan.zhihu.com/p/22294916--
修改:ilovecpp FROM 123.147.250.*
FROM 123.147.250.*