183 lines
14 KiB
Markdown
183 lines
14 KiB
Markdown
|
||
|
||
因收到Google相关通知，网站将会择期关闭。相关通知内容
|
||
|
||
|
||
030 编程范式游记（3） - 类型系统和泛型的本质
|
||
前面，我们讨论了从 C 到 C++ 的泛型编程方法，并且初探了一下更为抽象的函数式编程。正如在上一篇文章中所说的，泛型编程的方式并不只有 C++ 这样的方式，我们只是通过这个过程了解一下，底层静态类型语言泛型的原理。这样能够方便我们继续后面的历程。
|
||
|
||
是的，除了 C++ 那样的泛型，了解其它编程语言你一定会发现，在动态类型语言或是某些有语法糖支持的语言中，那个swap() 或 search() 函数的泛型其实可以很简单地就实现了。
|
||
|
||
比如，你甚至可以把swap()函数简单地写成下面这个样子（包括 Go 语言也有这样的语法）：
|
||
|
||
b, a = a, b;
|
||
|
||
|
||
|
||
在上一篇文章后面的 Reduce 函数中，可以看到，在编程世界中，我们需要处理好两件事。
|
||
|
||
|
||
第一件事是编程语言中的类型问题。
|
||
第二件事是对真实世界中业务代码的抽象、重用和拼装。
|
||
|
||
|
||
所以，在这篇文章中，我们还是继续深入地讨论上面这两个问题，着重讨论一下编程语言中的类型系统和泛型编程的本质。
|
||
|
||
类型系统
|
||
|
||
在计算机科学中，类型系统用于定义如何将编程语言中的数值和表达式归类为许多不同的类型，以及如何操作这些类型，还有这些类型如何互相作用。类型可以确认一个值或者一组值具有特定的意义和目的。
|
||
|
||
一般来说，编程语言者会有两种类型，一种是内建类型，如 int、float 和 char 等，一种是抽象类型，如 struct、class 和 function 等。抽象类型在程序运行中，可能不表示为值。类型系统在各种语言之间有非常大的不同，也许，最主要的差异存在于编译时期的语法，以及运行时期的操作实现方式。
|
||
|
||
编译器可能使用值的静态类型以最优化所需的存储区，并选取对数值运算时的较佳算法。例如，在许多 C 编译器中，“浮点数”数据类型是以 32 比特表示、与 IEEE 754 规格一致的单精度浮点数。因此，在数值运算上，C 应用了浮点数规范（浮点数加法、乘法等）。
|
||
|
||
类型的约束程度以及评估方法，影响了语言的类型。更进一步，编程语言可能就类型多态性部分，对每一个类型都对应了一个针对于这个类型的算法运算。类型理论研究类型系统，尽管实际的编程语言类型系统，起源于计算机架构的实际问题、编译器实现，以及语言设计。
|
||
|
||
程序语言的类型系统主要提供如下的功能。
|
||
|
||
|
||
程序语言的安全性。使用类型可以让编译器侦测一些代码的错误。例如：可以识别出一个错误无效的表达式。如：“Hello, World” + 3这样的不同数据类型间操作的问题。强类型语言提供更多的安全性，但是并不能保证绝对的安全。
|
||
利于编译器的优化。 静态类型语言的类型声明，可以让编译器明确地知道程序员的意图。因此，编译器就可以利用这一信息做很多代码优化工作。例如：如果我们指定一个类型是 int ，那么编译就知道，这个类型会以 4 个字节的倍数进行对齐，编译器就可以非常有效地利用更有效率的机器指令。
|
||
代码的可读性。有类型的编程语言，可以让代码更易读和更易维护。代码的语义也更清楚，代码模块的接口（如函数）也更丰富和更清楚。
|
||
抽象化。类型允许程序设计者对程序以较高层次的方式思考，而不是烦人的低层次实现。例如，我们使用整型或是浮点型来取代底层的字节实现，我们可以将字符串设计成一个值，而不是底层的字节的数组。从高层上来说，类型可以用来定义不同模块间的交互协议，比如函数的入参类型和返回类型，从而可以让接口更有语义，而且不同的模块数据交换更为直观和易懂。
|
||
|
||
|
||
但是，正如前面说的，类型带来的问题就是我们作用于不同类型的代码，虽然长得非常相似，但是由于类型的问题需要根据不同版本写出不同的算法，如果要做到泛型，就需要涉及比较底层的玩法。
|
||
|
||
对此，这个世界出现了两类语言，一类是静态类型语言，如 C、C++、Java，一种是动态类型语言，如 Python、PHP、JavaScript 等。
|
||
|
||
我们来看一下，一段动态类型语言的代码：
|
||
|
||
x = 5;
|
||
x = "hello";
|
||
|
||
|
||
在这个示例中，我们可以看到变量 x 一开始好像是整型，然后又成了字符串型。如果在静态类型的语言中写出这样的代码，那么就会在编译期出错。而在动态类型的语言中，会以类型标记维持程序所有数值的“标记”，并在运算任何数值之前检查标记。所以，一个变量的类型是由运行时的解释器来动态标记的，这样就可以动态地和底层的计算机指令或内存布局对应起来。
|
||
|
||
我们再来看一个示例，对于 JavaScript 这样的动态语言来说可以定义出下面这样的数据结构（一个数组的元素可以是各式各样的类型），这在静态类型的语言中是很难做到的。
|
||
|
||
var a = new Array()
|
||
a[0] = 2017;
|
||
a[1] = "Hello";
|
||
a[2] = {name: "Hao Chen"};
|
||
|
||
|
||
|
||
注：其实，这并不是一个数组，而是一个 key:value。因为动态语言的类型是动态的，所以，key 和 value 的类型都可以随意。比如，对于 a 这个数据结构，还可以写成：a["key"] = "value" 这样的方式。
|
||
|
||
|
||
在弱类型或是动态类型的语言中，下面代码的执行会有不确定的结果。
|
||
|
||
x = 5;
|
||
y = "37";
|
||
z = x + y;
|
||
|
||
|
||
|
||
有的像 Visual Basic 语言会给出的结果是 42：系统将字符串 “37” 转换成数字 37，以匹配运算上的直觉。
|
||
而有的像 JavaScript 将会产生的结果是 “537”：系统将数字 5 转换成字符串 “5” 并把两者串接起来。
|
||
|
||
|
||
|
||
注，像 Python 这样的语言则会产生一个运行时错误。
|
||
|
||
|
||
但是，我们需要清楚地知道，无论哪种程序语言，都逃避免不了一个特定的类型系统。哪怕是可随意改变变量类型的动态类型的语言，我们在读代码的过程中也需要脑补某个变量在运行时的类型。
|
||
|
||
所以，每个语言都需要一个类型检查系统。
|
||
|
||
|
||
静态类型检查是在编译器进行语义分析时进行的。如果一个语言强制实行类型规则（即通常只允许以不丢失信息为前提的自动类型转换），那么称此处理为强类型，反之称为弱类型。
|
||
动态类型检查系统更多的是在运行时期做动态类型标记和相关检查。所以，动态类型的语言必然要给出一堆诸如：is_array(), is_int(), is_string() 或是 typeof() 这样的运行时类型检查函数。
|
||
|
||
|
||
总之，“类型”有时候是一个有用的事，有时候又是一件很讨厌的事情。因为类型是对底层内存布局的一个抽象，会让我们的代码要关注于这些非业务逻辑上的东西。而且，我们的代码需要在不同类型的数据间做处理。但是如果程序语言类型检查得过于严格，那么，我们写出来的代码就不能那么随意。所以，对于静态类型的语言也开了些“小后门”：比如，类型转换，还有 C++、Java 运行时期的类型测试。
|
||
|
||
这些小后门也会带来相当讨厌的问题，比如下面这个 C 语言的示例。
|
||
|
||
int x = 5;
|
||
char y[] = "37";
|
||
char* z = x + y;
|
||
|
||
|
||
在上面这个例子中，结果可能和你想的完全不一样。由于 C 语言的底层特性，这个例子中的 z 会指向一个超过 y 地址 5 个字节的内存地址，相当于指向 y 字符串的指针之后的两个空字符处。
|
||
|
||
静态类型语言的支持者和动态类型自由形式的支持者，经常发生争执。前者主张，在编译的时候就可以较早发现错误，而且还可增进运行时期的性能。后者主张，使用更加动态的类型系统，分析代码更为简单，减少出错机会，才能更加轻松快速地编写程序。与此相关的是，后者还主张，考虑到在类型推断的编程语言中，通常不需要手动宣告类型，这部分的额外开销也就自动降低了。
|
||
|
||
在本系列内容的前两篇文章中，我们用 C/C++ 语言来做泛型编程的示例，似乎动态类型语言能够比较好地规避掉类型导致需要出现多个版本代码的问题。这样可以让我们更好地关注于业务。
|
||
|
||
但是，我们需要清楚地明白，任何语言都有类型系统，只是动态类型语言在运行时做类型检查。动态语言的代码复杂度比较低，并可以更容易地关注业务，在某些场景下是对的，但有些情况下却并不见得。
|
||
|
||
比如：在 JavaScript 中，我们需要做一个变量转型的函数，可能会是下面这个样子：
|
||
|
||
function ToNumber(x) {
|
||
switch(typeof x) {
|
||
case "number": return x;
|
||
case "undefined": return NaN;
|
||
case "boolean": return x ? 1 : 0;
|
||
case "string": return Number(x);
|
||
case "object": return NaN;
|
||
case "function": return NaN;
|
||
}
|
||
}
|
||
|
||
|
||
我相信，你在动态类型语言的代码中可以看到大量类似 typeof 这样的类型检查代码。是的，这是动态类型带来的另一个问题，就是运行时识别（这个是比较耗性能的）。
|
||
|
||
如果你用过一段时间的动态类型语言，一旦代码量比较大了，我们就会发现，代码中出现“类型问题”而引发整个程序出错的情况实在是太多太多了。而且，这样的出错会让整个程序崩溃掉，太恐怖了。这个时候，我们就很希望提前发现这些类型的问题。
|
||
|
||
静态语言的支持者会说编译器会帮我们找到这些问题，而动态语言的支持者则认为，静态语言的编译器也无法找到所有的问题，想真正提前找到问题只能通过测试来解决。其实他们都对。
|
||
|
||
泛型的本质
|
||
|
||
要了解泛型的本质，就需要了解类型的本质。
|
||
|
||
|
||
类型是对内存的一种抽象。不同的类型，会有不同的内存布局和内存分配的策略。
|
||
不同的类型，有不同的操作。所以，对于特定的类型，也有特定的一组操作。
|
||
|
||
|
||
所以，要做到泛型，我们需要做下面的事情。
|
||
|
||
|
||
标准化掉类型的内存分配、释放和访问。
|
||
标准化掉类型的操作。比如：比较操作，I/O 操作，复制操作……
|
||
标准化掉数据容器的操作。比如：查找算法、过滤算法、聚合算法……
|
||
标准化掉类型上特有的操作。需要有标准化的接口来回调不同类型的具体操作……
|
||
|
||
|
||
所以，C++ 动用了非常繁多和复杂的技术来达到泛型编程的目标。
|
||
|
||
|
||
通过类中的构造、析构、拷贝构造，重载赋值操作符，标准化（隐藏）了类型的内存分配、释放和复制的操作。
|
||
通过重载操作符，可以标准化类型的比较等操作。
|
||
通过 iostream，标准化了类型的输入输出控制。
|
||
通过模板技术（包括模板的特化），来为不同的类型生成类型专属的代码。
|
||
通过迭代器来标准化数据容器的遍历操作。
|
||
通过面向对象的接口依赖（虚函数技术），来标准化了特定类型在特定算法上的操作。
|
||
通过函数式（函数对象），来标准化对于不同类型的特定操作。
|
||
|
||
|
||
通过学习 C++，我们可以看到一个比较完整的泛型编程里所涉及的编程范式，这些编程泛式在其它语言中都会或多或少地体现着。比如，JDK 5 引入的泛型类型，就源自 C++ 的模板。
|
||
|
||
泛型编程于 1985 年在论文 Generic Programming 中被这样定义：
|
||
|
||
|
||
Generic programming centers around the idea of abstracting from concrete, efficient algorithms to obtain generic algorithms that can be combined with different data representations to produce a wide variety of useful software.
|
||
|
||
— Musser, David R.; Stepanov, Alexander A., Generic Programming
|
||
|
||
|
||
我理解其本质就是 —— 屏蔽掉数据和操作数据的细节，让算法更为通用，让编程者更多地关注算法的结构，而不是在算法中处理不同的数据类型。
|
||
|
||
小结
|
||
|
||
在编程语言中，类型系统的出现主要是对容许混乱的操作加上了严格的限制，以避免代码以无效的数据使用方式编译或运行。例如，整数运算不可用于字符串；指针的操作不可用于整数上，等等。但是，类型的产生和限制，虽然对底层代码来说是安全的，但是对于更高层次的抽象产生了些负面因素。比如在 C++ 语言里，为了同时满足静态类型和抽象，就导致了模板技术的出现，带来了语言的复杂性。
|
||
|
||
我们需要清楚地明白，编程语言本质上帮助程序员屏蔽底层机器代码的实现，而让我们可以更为关注于业务逻辑代码。但是因为，编程语言作为机器代码和业务逻辑的粘合层，是在让程序员可以控制更多底层的灵活性，还是屏蔽底层细节，让程序员可以更多地关注于业务逻辑，这是很难两全需要 trade-off 的事。
|
||
|
||
所以，不同的语言在设计上都会做相应的取舍。比如：C 语言偏向于让程序员可以控制更多的底层细节，而 Java 和 Python 则让程序员更多地关注业务功能的实现。而 C++ 则是两者都想要，导致语言在设计上非常复杂。
|
||
|
||
|
||
|
||
|