临时 #### 定义:: 范即模范之意，范式即模式、方法，是一类典型的编程风格，是指从事软件工程的一类典型的风格 编程语言发展到今天，本质是: 如何写出更为通用、更具可重用性的代码或模块 C 语言特性:: 1. C 语言是一个静态弱类型语言，在使用变量时需要声明变量类型，但是类型间可以有隐式转换 2. 不同的变量类型可以用结构体（struct）组合在一起，以此来声明新的数据类型 3. C 语言可以用 typedef 关键字来定义类型的别名，以此来达到变量类型的抽象 4. C 语言是一个有结构化程序设计、具有变量作用域以及递归功能的过程式语言 5. C 语言传递参数一般是以值传递，也可以传递指针 6. 通过指针，C 语言可以容易地对内存进行低级控制，然而这加大了编程复杂度 7. 编译预处理让 C 语言的编译更具有弹性，比如跨平台 泛型 ==== :: 抽象类型，这就是所谓的泛型编程 C语言-小实例:: void swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } C语言-泛型实现-void\*:: void swap(void* x, void* y, size_t size) { char tmp[size]; memcpy(tmp, y, size); memcpy(y, x, size); memcpy(x, tmp, size); } C语言-泛型实现-用宏定义来做泛型:: #define swap(x, y, size) {\ char temp[size]; \ memcpy(temp, &y, size); \ memcpy(&y, &x, size); \ memcpy(&x, temp, size); \ } 一个良好的泛型编程需要解决如下几个泛型编程的问题:: 1. 算法的泛型； 2. 类型的泛型； 3. 数据结构（数据容器）的泛型 C语言-泛型实现-search()函数:: int search(void* a, size_t size, void* target, size_t elem_size, int(*cmpFn)(void*, void*) ) { for(int i=0; i Iter search(Iter pStart, Iter pEnd, T target) { for(Iter p = pStart; p != pEnd; p++) { if ( *p == target ) return p; } return NULL; } 在编程世界中，我们需要处理好两件事:: 第一件事是编程语言中的类型问题 第二件事是对真实世界中业务代码的抽象、重用和拼装 程序语言的『类型』系统主要提供如下的功能:: 1. 程序语言的安全性 使用类型可以让编译器侦测一些代码的错误 例如: 可以识别出一个错误无效的表达式，如“Hello, World” + 3 强类型语言提供更多的安全性，但是并不能保证绝对的安全 2. 利于编译器的优化 静态类型语言的类型声明，可以让编译器明确地知道程序员的意图。 因此，编译器就可以利用这一信息做很多代码优化工作。 例如: 如果我们指定一个类型是 int ，那么编译就知道，这个类型会以 4 个字节的倍数进行对齐， 编译器就可以非常有效地利用更有效率的机器指令。 3. 代码的可读性 有类型的编程语言，可以让代码更易读和更易维护，代码的语义也更清楚， 代码模块的接口（如函数）也更丰富和清楚 4. 抽象化 类型允许程序设计者对程序以较高层次的方式思考，而不是烦人的低层次实现。 例如: 我们使用整型或是浮点型来取代底层的字节实现，我们可以将字符串设计成一个值，而不是底层字节的数组。 从高层上来说，类型可以用来定义不同模块间的交互协议，比如函数的入参类型和返回类型， 从而可以让接口更有语义，而且不同的模块数据交换更为直观和易懂。 动态&静态类型语言 ================= 两类语言:: 1. 一类是静态类型语言，如 C、C++、Java 2. 一种是动态类型语言，如 Python、PHP、JavaScript 等 泛型技术是静态系统所独有的特性 本质上我觉得还是为了兼顾执行效率和编程灵活性，实现零成本抽象这一刀尖上跳舞的巨大挑战。 在弱类型或是动态类型的语言中，下面代码的执行会有不确定的结果:: x = 5; y = "37"; z = x + y; 1. 像 Visual Basic 语言 给出的结果是 42：系统将字符串 "37" 转换成数字 37，以匹配运算上的直觉 2. 像 JavaScript 语言 给出的结果是 "537"：系统将数字 5 转换成字符串 "5" 并把两者串接起来 3. 像 Python 这样的语言 则会产生一个运行时错误 类型检查系统:: 1. 静态类型检查是在编译器进行语义分析时进行的 如果一个语言强制实行类型规则（即通常只允许以不丢失信息为前提的自动类型转换）， 那么称此处理为强类型，反之称为弱类型。 2. 动态类型检查系统更多的是在运行时期做动态类型标记和相关检查 所以，动态类型的语言必然要给出一堆诸如这样的运行时类型检查函数: is_array(), is_int(), is_string() 或是 typeof() 类型是对底层内存布局的一个抽象，会让我们的代码要关注于这些非业务逻辑上的东西 对于静态类型的语言也开了些“小后门”：比如，类型转换，还有 C++、Java 运行时期的类型测试 这些小后门也会带来相当讨厌的问题，比如下面这个 C 语言的示例: int x = 5; char y[] = "37"; char* z = x + y; 结果可能和你想的完全不一样 .. note:: 静态类型语言的支持者和动态类型自由形式的支持者，经常发生争执。前者主张，在编译的时候就可以较早发现错误，而且还可增进运行时期的性能。后者主张，使用更加动态的类型系统，分析代码更为简单，减少出错机会，才能更加轻松快速地编写程序。与此相关的是，后者还主张，考虑到在类型推断的编程语言中，通常不需要手动宣告类型，这部分的额外开销也就自动降低了。 .. note:: 任何语言都有类型系统，只是动态类型语言在运行时做类型检查。动态语言的代码复杂度比较低，并可以更容易地关注业务，在某些场景下是对的，但有些情况下却并不见得。 比如：在 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; } } .. note:: 用过一段时间的动态类型语言，一旦代码量比较大了，我们就会发现，代码中出现“类型问题”而引发整个程序出错的情况实在是太多太多了。而且，这样的出错会让整个程序崩溃掉，太恐怖了。这个时候，我们就很希望提前发现这些类型的问题。静态语言的支持者会说编译器能帮我们找到这些问题，而动态语言的支持者则认为，静态语言的编译器也无法找到所有的问题，想真正提前找到问题只能通过测试来解决。其实他们都对。 泛型的本质 ---------- 先了解下类型的本质:: 类型是对内存的一种抽象 不同的类型，会有不同的内存布局和内存分配的策略 不同的类型，有不同的操作 所以，对于特定的类型，也有特定的一组操作 要做到泛型，我们需要做下面的事情:: 1. 标准化掉类型的内存分配、释放和访问 2. 标准化掉类型的操作 比如：比较操作，I/O 操作，复制操作… 3. 标准化掉数据容器的操作 比如：查找算法、过滤算法、聚合算法… 4. 标准化掉类型上特有的操作 需要有标准化的接口来回调不同类型的具体操作… C++ 动用了非常繁多和复杂的技术来达到泛型编程的目标:: 1. 通过类中的构造、析构、拷贝构造，重载赋值操作符，标准化（隐藏）了类型的内存分配、释放和复制的操作 2. 通过重载操作符，可以标准化类型的比较等操作 3. 通过 iostream，标准化了类型的输入、输出控制 4. 通过模板技术（包括模板的特化），来为不同的类型生成类型专属的代码 5. 通过迭代器来标准化数据容器的遍历操作 6. 通过面向对象的接口依赖（虚函数技术），来标准化了特定类型在特定算法上的操作 7. 通过函数式（函数对象），来标准化对于不同类型的特定操作 .. note:: 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(1985 年). 本质就是 —— 屏蔽掉数据和操作数据的细节，让算法更为通用，让编程者更多地关注算法的结构，而不是在算法中处理不同的数据类型。 小结 ---- .. note:: 编程语言本质上帮助程序员屏蔽底层机器代码的实现，而让我们可以更为关注于业务逻辑代码。但是因为，编程语言作为机器代码和业务逻辑的粘合层，是在让程序员可以控制更多底层的灵活性，还是屏蔽底层细节，让程序员可以更多地关注于业务逻辑，这是很难两全需要 trade-off 的事。 不同的语言在设计上都会做相应的取舍，比如：C 语言偏向于让程序员可以控制更多的底层细节，而 Java 和 Python 则让程序员更多地关注业务功能的实现。而 C++ 则是两者都想要，导致语言在设计上非常复杂。 函数式编程 ========== 函数式编程的理念来自于数学中的代数。 .. note:: 对于函数式编程来说，它只关心定义输入数据和输出数据相关的关系，数学表达式里面其实是在做一种映射（mapping），输入的数据和输出的数据关系是什么样的，是用函数来定义的。 特征:: 1. stateless 函数不维护任何状态。 函数式编程的核心精神是 stateless， 简而言之就是它不能存在状态，打个比方，你给我数据我处理完扔出来。里面的数据是不变的。 2. immutable 输入数据是不能动的，动了输入数据就有危险，所以要返回新的数据集。 优势:: 1. 没有状态就没有伤害 2. 并行执行无伤害 3. Copy-Paste 重构代码无伤害 4. 函数的执行没有顺序上的问题 函数式编程还带来了以下一些好处:: 1. 惰性求值 这需要编译器的支持，表达式不在它被绑定到变量之后就立即求值，而是在该值被取用的时候求值。也就是说，语句如 x:=expression; (把一个表达式的结果赋值给一个变量) 显式地调用这个表达式被计算并把结果放置到 x 中，但是先不管实际在 x 中的是什么，直到通过后面的表达式中到 x 的引用而有了对它的值的需求的时候，而后面表达式自身的求值也可以被延迟，最终为了生成让外界看到的某个符号而计算这个快速增长的依赖树。 2. 确定性 所谓确定性，就是像在数学中那样，f(x) = y 这个函数无论在什么场景下，都会得到同样的结果，而不是像程序中的很多函数那样。同一个参数，在不同的场景下会计算出不同的结果，这个我们称之为函数的确定性。所谓不同的场景，就是我们的函数会根据运行中的状态信息的不同而发生变化。 劣势:: 数据复制比较严重。 注：有一些人可能会觉得这会对性能造成影响。其实，这个劣势不见得会导致性能不好。因为没有状态，所以代码在并行上根本不需要锁（不需要对状态修改的锁），所以可以拼命地并发，反而可以让性能很不错。比如：Erlang 就是其中的代表。 对于纯函数式（也就是完全没有状态的函数）的编程来说，各个语言支持的程度如下:: 1. 完全纯函数式 Haskell 2. 容易写纯函数 F#, Ocaml, Clojure, Scala 3. 纯函数需要花点精力 C#, Java, JavaScript 函数式编程用到的技术:: 1. first class function（头等函数） 这个技术可以让你的函数就像变量一样来使用。 也就是说，你的函数可以像变量一样被创建、修改，并当成变量一样传递、返回，或是在函数中嵌套函数。 2. tail recursion optimization（尾递归优化） 我们知道递归的害处，那就是如果递归很深的话，stack 受不了，并会导致性能大幅度下降。因此，我们使用尾递归优化技术——每次递归时都会重用 stack，这样能够提升性能。当然，这需要语言或编译器的支持。Python 就不支持。 3. map & reduce 这个技术不用多说了，函数式编程最常见的技术就是对一个集合做 Map 和 Reduce 操作。这比起过程式的语言来说，在代码上要更容易阅读。（传统过程式的语言需要使用 for/while 循环，然后在各种变量中把数据倒过来倒过去的）这个很像 C++ STL 中 foreach、find_if、count_if 等函数的玩法。 4. pipeline（管道） 这个技术的意思是，将函数实例成一个一个的 action，然后将一组 action 放到一个数组或是列表中，再把数据传给这个 action list，数据就像一个 pipeline 一样顺序地被各个函数所操作，最终得到我们想要的结果。 5. recursing（递归） 递归最大的好处就简化代码，它可以把一个复杂的问题用很简单的代码描述出来。注意：递归的精髓是描述问题，而这正是函数式编程的精髓。 6. currying（柯里化） 将一个函数的多个参数分解成多个函数， 然后将函数多层封装起来，每层函数都返回一个函数去接收下一个参数，这可以简化函数的多个参数。在 C++ 中，这很像 STL 中的 bind1st 或是 bind2nd。 7. higher order function（高阶函数） 所谓高阶函数就是函数当参数，把传入的函数做一个封装，然后返回这个封装函数。现象上就是函数传进传出，就像面向对象对象满天飞一样。这个技术用来做 Decorator 很不错。 函数式编程的理念:: 1. 把函数当成变量来用，关注描述问题而不是怎么实现，这样可以让代码更易读 2. 因为函数返回里面的这个函数，所以函数关注的是表达式，关注的是描述这个问题，而不是怎么实现这个事情 other ===== .. note:: 当我们说一门编程语言是图灵完备的语言时，说明这门语言所拥有的编程能力，是现代计算机语言所能拥有的最高能力。 * 冒号课堂 * 斯坦福编程范式公开课 * 【极客】左耳听风-分布式架构: https://time.geekbang.org/column/intro/48