Ayingotts's notes

Appearance

编程开发中，需要掌握的基本概念 ​

  1. 数据
    • 值和类型
    • 指针和引用
  2. 代码
    • 函数
    • 方法
    • 闭包
    • 接口
    • 虚表
  3. 运行方式
    • 并发运行
    • 同步异步
    • Promise / async / await
  4. 编程范式
    • 泛型编程

数据 ​

数据是程序操作的对象，不进行数据处理的程序是没有意义的。

值和类型 ​

严谨的说，类型是对值的区分，它包含了值在内存中的长度、对齐以及值可以进行的操作等信息。

一个值是符合一个特定类型的数据的某个实体。比如 64u8 ，它是 u8 类型，对应一个字节大小、取值范围在 0~255 的某个整数实体，这个实体是 64 。

值以类型规定的表达方式 ( representation ) 被存储成一组字节流进行访问。比如 64 ，存储在内存中的表现形式是 0x40 ，或者 0b 0100 0000 。

值无法脱离具体的类型进行讨论。同样是 0x40 ，如果是类型是 ASCII char ，它的含义就不是 64 ，而是 @ 符号。

不管是强类型的语言还是弱类型的语言，语言内部都有其类型的具体表述。一般而言，编程语言的类型可以分为原生类型和组合类型两大类。

原生类型 ( primitive type ) 是编程语言提供的最基础的数据类型。比如字符、整数、浮点数、布尔值、数组、元组、指针、引用、函数、闭包等。所有原生类型的大小都是固定的，因此它们可以被分配到栈上。

组合类型 ( composite type ) 或者说复合类型，是指由一组原生类型和其它类型组合而成的类型。组合类型可以细分为两类：

  1. 结构体 ( structure type ) ：多个类型组合在一起共同表达一个值的复杂函数结构。比如 Person 结构体，内部包含 name、age、email 等信息。用代数数据类型 ( algebraic data type ) 的说法，结构体是 product type 。
  2. 标签联合 ( tagged union ) ：也叫不相交并集 ( disjoint union ) ，可以存储一组不同但固定的类型中的某个类型的对象，具体是哪个类型由其标签决定。比如 Haskell 里的 Maybe 类型，或者 Swift 中的 Optional 就是标签联合。用代数数据类型的说法，标签联合是 sum type 。

不少语言不支持标签联合，只取其标签部分，提供了枚举类型 ( enumerate ) 。枚举是标签联合的子类型，但功能比较弱，无法表达复杂的结构。

指针和引用 ​

在内存中，一个值被存储到内存中的某个位置，这个位置对应一个内存地址。而指针是一个持有内存地址的值，可以通过解引用 ( dereference ) 来访问它指向的内存地址，理论上可以解引用到任意数据类型。

引用 ( reference ) 和指针非常类似，不同的是，引用的解引用访问是受限的，它只能解引用到它引用数据的类型，不能用作他用。比如，指向 42u8 这个值的一个引用，它解引用的时候只能使用 u8 数据类型。

指针的使用限制更少，但会带来更多的危害。如果没有用正确的类型解引用一个指针，那么会引发各种各样的内存问题，造成系统崩溃或者潜在的安全漏洞。

指针和引用是原生类型，它们可以分配在栈上。

比如，指向 hello world 字符串的指针，还包含字符串长度和字符串的容量，一共使用了 3 个 word ，在 64 位 CPU 下占用 24 个字节，这样比正常指针携带更多信息的指针，称之为胖指针 ( fat pointer ) 。很多数据结构的引用，内部都是由胖指针实现的。

代码 ​

数据是程序操作的对象，而代码是程序运行的主体，是开发者把物理世界中的需求转换成数字世界中逻辑的载体。

函数 ​

函数是编程语言的基本要素，它是对完成某个功能的一组相关语句和表达式的封装。

函数是对代码中重复行为的抽象。

在现代编程语言中，函数往往是一等公民，这意味着函数可以作为参数传递，或者作为返回值返回，也可以作为复合类型中的一个组成部分。

方法 ​

在面向对象的编程语言中，在类或者对象中定义的函数，被称为方法 ( method ) 。方法往往和对象的指针发生关系，比如 Python 对象的 self 引用，或 Java 对象的 this 引用。

闭包 ​

闭包是将函数，或者说代码何其环境一起存储的一种数据结构。闭包引用的上下文中的自由变量，会被捕获到闭包的结构中，成为闭包类型的一部分。

一般来说，如果一门编程语言，其函数是一等公民，那么它必然会支持闭包 ( closure ) ，因为函数作为返回值往往需要返回一个闭包。

closure

接口 ​

接口是一个软件系统开发的核心部分，它反应了系统的设计者对系统的抽象理解。

作为一个抽象层，接口将使用方和实现方隔离开来，使两者不直接有依赖关系，大大提高了复用性和扩展性。

很多编程语言都有接口的概念，允许开发者面向接口设计，比如 Java 的 interface、Elixir 的 behaviour、Swift 的 protocol 和 Rust 的 trait 。

在 HTTP 中，Request / Response 的服务处理模型其实就是一个典型的接口，我们只需要按照服务接口，定义出不同输入下，从 Request 到 Response 具体该如何映射，通过这个接口，系统就可以在合适的场景下，把符合要求的 Request 分派给服务。

面向接口的设计是软件开发中的重要能力，而 Rust 尤其重视接口的能力。

虚表 ​

当在运行期使用接口来引用具体类型的时候，代码就具备了运行时多态的能力。但是，在运行时，一旦使用了关于接口的引用，变量原本的类型被抹去，无法单纯从一个指针分析出这个引用具备什么样的能力。

因此，在生成这个引用的时候，需要构建胖指针，除了指向数据本身外，还需要指向一张涵盖了这个接口所支持方法的列表。这个列表，就是虚表 ( virtual table ) 。

下图展示了一个 Vec 数据在运行期被抹去类型，生成一个指向 Write 接口引用的过程

虚表记录了数据能够执行的接口，所以在运行期，想对一个接口有不同实现，可以根据上下文动态分派。

比如，想为一个编辑器的 Formatter 接口实现不同语言的格式化工具，可以在编辑器加载时，把所有支持的语言和其格式化工具放入一个哈希表中，哈希表的 key 为语言类型，value 为每种格式化工具 Formatter 接口的引用。这样，当用户在编辑器打开某个文件时，可以根据文件类型，找到对应 Formatter 的引用，来进行格式化操作。

运行方式 ​

程序在加载后，代码以何种方式运行，往往决定着程序的执行效率。

并发、并行 ​

并发 ( concurrency ) 与并行 ( parallel ) 是软件开发中经常遇到的概念。

并发是同时与多件事情打交道的能力，比如系统可以在任务 1 做到一定程度后，保存该任务的上下文，挂起并切换到任务 2 ，然后过段时间再切换回任务 1 。

并行是同时处理多件事情的手段。任务 1 和任务 2 可以在同一个时间片下工作，无需上下文切换。

并发是一种能力，而并行是一种手段。当系统拥有了并发能力后，代码如果跑在多个 CPU core 上，就可以并行运行。所以平时通常谈论高并发处理，而不说高并行处理。

很多拥有高并发处理能力的编程语言，会在用户程序中嵌入一个 M:N 的调度器，把 M 个并发任务，合理地分配在 N 个 CPU core 上并行运行，让程序的吞吐量达到最大。

同步、异步 ​

同步是指一个任务开始执行后，后续的操作会阻塞，直到这个任务结束。

在软件中，大部分的代码都是同步操作，比如 CPU ，只有流水线中的前一条指令执行完成，才会执行下一条指令。比如，一个函数 A 先后调用函数 B 和 C ，会先执行完 B 后才执行 C 。

同步执行保证了代码的因果关系 ( causality ) ，是程序正确性的保证。

然而，在遭遇 I / O 处理时，高效 CPU 指令和低效 I / O 之间的巨大鸿沟，成为了软件的性能杀手。

和内存访问相比，I / O 操作的访问速度低了两个数量级，一旦遇到 I / O 操作，CPU 只能闲置来等待 I / O 设备运行完毕。因此，操作系统为应用程序提供了异步 I / O ，让应用可以在当前 I / O 处理完毕之前，将 CPU 时间用作其它任务的处理。

所以，异步是指一个任务开始执行后，与它没有因果关系的其它任务可以正常执行，不必等待前一个任务结束。

在异步操作里，异步处理完成后的结果，一般用 Promise 保存，它是一个对象，用来描述在未来的某个时刻才能获得的结果的值，一般存在三个状态：

  1. 初始状态，Promise 未运行
  2. 等待 ( pending ) 状态，Promise 已运行，但未结束
  3. 结束状态，Promise 成功解析出值，或执行失败

在不同的支持异步的语言中，Promise 也叫 Future / Delay / Deferred 等，通常能看到 async / await 这对关键词。

async 定义了一个可以并发执行的任务，而 await 则触发这个任务并发执行。大多数语言中，async / await 是一个语法糖 ( syntactic sugar ) ，它使用状态机将 Promise 包装起来，让异步调用的使用感觉和同步调用非常类似，也让代码更容易阅读。

编程范式 ​

为了在不断迭代时，更好地维护代码，会引入各种各样的编程范式，提升代码质量。

泛型编程 ​

泛型编程包含两个层面，数据结构的泛型和使用泛型结构代码的泛型化。

数据结构的泛型 ​

数据结构的泛型往往被成为参数化类型或者参数多态。

rust
struct Connection<S> {
   io: S,
   state: State,
}
struct Connection<S> {
   io: S,
   state: State,
}

Connection 有一个参数 S ，其内部的域 io 的类型是 S ，S 具体的类型只有在使用 Connection 的上下文中才得到绑定。

参数化数据结构可以理解成一个产生类型的函数，在 "调用" 时，它接收若干个使用了具体类型的参数，返回携带这些类型的类型。比如，为 S 提供 TcpStream 这个类型，那么 Connection<TcpStream> 产生的类型，其中 io 的类型是 TcpStream 。

为了产生的类型能够正确使用泛型参数具有的变量和方法，需要用接口对泛型参数进行约束。支持泛型编程的语言，都会提供强大的接口编程能力。

数据结构的泛型是一种高级抽象，它带来的好处是可以延迟绑定，让数据结构的通用性更强，适用场景更广阔的；也大大减少了重复代码，提高了可维护性。

代码的泛型化 ​

使用泛型结构编写代码，相关的代码需要额外的抽象。

左边是用 C 写的二分查找，标记的几处操作和 int[] 强相关，如果对不同的数据类型做二分查找，实现也要随之改变。

右边 C++ 的实现，对这些操作做了抽象，可以用同一套代码二分查找迭代器 ( iterator ) 的数据类型。

这样的代码可以在更广阔的的场合使用，更简洁，更容易维护。

小结 ​

以上是四大类基础概念：数据、代码、运行方式和编程范式。

值无法离开类型单独讨论，类型一般分为原生类型和组合类型。指针和引用都指向值的内存地址，只不过二者在解引用时的行为不一样。引用只能解引用到原来的数据类型，而指针没有这个限制，然而，不受约束的指针解引用，会带来内存安全方面的问题。

函数是代码中重复行为的抽象，方法是对象内部定义的函数，而闭包是一种特殊的函数，它会捕获函数体内使用到的上下文中的自由变量，作为闭包成员的一部分。

接口将调用者和实现者隔离开，大大促进了代码的复用和扩展。面向接口可以让系统变得灵活，当使用接口去引用具体的类型时，需要虚表来辅助运行时代码的执行。有了虚表，可以很方便地进行动态分派，它是运行时多态的基础。

在代码的运行方式中，并发是并行的基础，是同时与多个任务打交道的能力；并行是并发的体现，是同时处理多个任务的手段。同步阻塞后续操作，异步允许后续操作。被广泛用于异步操作的 Promise 代表未来某个时刻会得到的结果，async / await 是 Promise 的封装，一般用状态机来实现。

泛型编程通过参数化让数据结构像函数一样延迟绑定，提升其通用性，类型的参数可以用接口约束，使类型满足一定的行为，同时，在使用泛型结构时，代码也需要更高的抽象度。

补充 ​

虚表相当于在运行时生成的一个涵盖了一系列函数指针的数据结构。有时候对于不同类型但是满足相同接口的数据，希望可以抹去它们的原始类型，让它们有相同的接口类型，以便于统一处理，这样更加灵活，但此时需要为每个数据构造它们各自对接口实现的虚表，这样可以依旧调用到属于该类型的实现。

虚表一般存储在堆上。Rust 下也有虚表的栈实现：https://github.com/archshift/dynstack