转载 https://arthurchiao.art/blog/memory-models-underlie-programming-languages-zh/

编程语言中的 6 种内存模型（2016）

译者序

本文翻译自一篇英文博客 The memory models that underlie programming languages，截至本文翻译时，原文最 后一次更新是在 2016 年。

作者似乎是计算机和编程领域的老兵，除了高屋建瓴地分析这 6 种横跨半个多 世纪的内存模型之外，还举重若轻地点评了如下几十种语言、库或系统（大部 分都是编程语言）：Forth、morden Lisps、Haskell、ML、Python、Ruby、PHP5、Lua、 JavaScript、Erlang、Smalltalk、Java、C#、Assembly、Awk、Perl4、Tcl、Octave、 Matlab、APL、J、K、PV-WAVE IDL、Lush、S、S-Plus、R、Numpy、Pandas、OpenGL、Linda 、C++、D、MUMPS、Wheat、Prolog、miniKANREN 等等。

由于译者水平有限，本文不免存在遗漏或错误之处。如有疑问，请查阅原文。

以下是译文。

目录

1. 引言
2. 序曲：只有原子变量的程序
3. COBOL 内存模型：嵌套结构 —— 内存就像一张税单
4. LISP 内存模型：对象图 —— 内存是一张带标签的有向图
5. FORTRAN 内存模型：并行数组 —— 内存是一系列数组
6. 茶歇：为什么没有 Lua、Erlang 和 Forth 内存模型？
7. 磁带内存模型：管道 —— 写入、等待数据、继续写入
8. MULTICS 内存模型：目录 —— 内存是一棵树
9. SQL 内存模型：关系 —— 内存是一个可变、多值有限函数集
10. 注释

编程语言发展至今，大约产生了 6 种主要的内存概念化（conceptualizations of memory ）模型，我将其称为 “内存模型”（memory models）[2]。从历史渊源上看，这 6 种 模型中有 3 种来自于 20 世纪 50 年代（1950s）最重要的 3 种编程语言：

• COBOL
• LISP
• FORTRAN

另外 3 种来自于在历史上有重要地位的数据存储系统：

• 磁带（magnetic tap）
• Unix-style 层级文件系统（Unix-style hierarchical filesystems）
• 关系数据库（relational databases）

相比于语法（syntax）乃至类型系统（type systems），内存模型在更深层次 上决定了一门编程语言能够做什么或不能做什么。但奇怪的是，我还从未看到过介绍这 些模型的好文章，因此我决定自己来写一篇。在本文中，我会介绍一些主流模型之外的其他 选项（possible alternatives to the mainstream options），以及为什么它们很有趣。

Forth 能提供的基础设施。 但是，大部分编程语言不会止步于此，事实上很多语言并不会提供 peek() 和 poke() 函数。相反，它们会在朴素的、单一维度的字节数组（austere uniform array of bytes） 之上提供某种形式的结构。

例如，即使只能对有限状态机进行编程，但只要有了嵌套记录（nested-record）、数组 （array）和 union 等数据结构，就能使语言的能力得到很大加强。

Adam N. Rosenberg 提倡永远用并行数组风格来编程 ，并且用一本书的厚度来解释为什 么应该这样做。我并不认为这一个好主义，但他是我见过的这种思想的最佳现代捍卫者。

5.4 优缺点

优点

简单来说，

1. 并行数组是缓存友好的
2. 支持不同属性有不同的可见度
3. 支持设置 watchpoints
4. 提供的序列是有意义的（provide a sequence that can be meaningful）
5. 支持多维索引（属性可以是 entity tuple，而并不仅仅是单个 entity）

另外，并行数组还支持编写子过程来在属性之上进行抽象，因为它们在运行时才对每 个属性进行具体化：你可以写一个能够应用到任何属性的 sum 或 covariance 函数 — — 这一点尤其有趣：虽然并行数组不支持让某个特定实体对某段特定程序可见（private） ，但它支持让实体（变量）的某个 属性（attribute）是私有的（private）。

缺点

我不喜欢并行数组，因为它们非常容易导致错误。

• 编译器无法分辨数组的某个给定的索引是否合法，调试器和垃圾回收器也不能。
• 并行数组本质上容易导致类型错误（type error）—— 将某种类型的实体的某个标识 符存储在一个另一种类型的数组中 —— 相比于编译时错误消息或运行时错误消息，这种方 式会更容易导致错误（尤其是在没有打开数组范围检查的情况下）。
• 另外，由于并行数组在运行时具体化的是属性（attributes）而不是实体（entities）， 因此创建和删除实体很容易出错，子过程倾向于有很多的参数（增加了抽象的 成本，导致子过程的实现变长）
• 与嵌套记录模型中类似的 arbitrary limits 问题（即对内存中数组的大小没有施加限制 ，可以为任意大小，见上文。译者注）。

并行数组的序列化非常容易和高效，尤其是如果你不考虑 CPU 架构间的可移植性；但是它 们一般是以属性为维度的，需要同时对涉及到的所有实体的某个属性进行序列化或反序 列化。

5.5 对其他编程语言的影响

Fortran 并不是唯一一种推荐用并行数组组织内存的语言。

• Octave、Matlab、APL、J、K、PV-WAVE IDL、Lush、S、S-Plus 和 R 很大程度上都是面 向并行数组（parallel-array-oriented）的编程语言
• Numpy、Pandas、和 OpenGL 是面向并行数组的库（parallel-array-oriented libraries）
• 我前面还提到，Perl4、awk、和 Tcl 在一定程度上也是面向并行数组的

以上提到的某些语言为了减少并行数组不一致（getting out of sync）的风险，将数 组设计为一旦创建就不可变的（immutable once populated），或者至少鼓励创建新数 组；Pandas、K 和 那些并行字典衍生语言（parallel-dictionary variant）减少类型错误 风险的方式是鼓励用非数值方式访问数组（index your arrays by things that aren’ t integers）。

在并行数组模型中，我们可以很方便地将对某个实体集合进行循环的操作封装到一个叶子函 数（leaf functions，即不会再调用其他自定义函数的函数），这可以降低解释开销（ interpretation overhead），因此即使是在 1960s 年代的某个解释器上 APL 都可以做高 性能数值计算任务（high-performance numerical work）。

现代硬件的某些特性限制了并行数组取得更高的性能的可能性：CPU 和内存速度之间越来越 大的 gap、GPU 的 SIMT 架构、CPU（为了增加 ALU 硅片面积相比于控制硅片面积的比例而 增加的）SIMD 指令。最终，游戏程序员开始以“面向数据的设计”（data-oriented design）和（某种程度的）“实体系统”（entity systems）的名义回归到并行数组。 数值（科学）计算从未抛弃过并行数组。

Wheat 的现代面向对象编程环境，作为 PHP 之外的 web app 编程环境；我个人对此是有点喜欢的。

In Wheat, each function’s activation record is a “directory”, with its variables as (dynamically typed, rather than blob) “files” in it. Some subtrees of the “filesystem” are persistent, but not others; access to remotely hosted data is transparent. Essentially, Wheat sought to eliminate the impedance mismatch between the persistent, hierarchically-named, globally-accessible resources of the Web, and the program’s own conception of memory.

最近无意间变成了图灵完备（Turing-complete）的 ，因此原理上 SQL 是可 以接管整个世界的。

与真正意义上的编程语言，例如 Lisp、FORTRAN 和 C 相比，这种模型看上去并不属于同一个 范畴，这是因为 SQL 作为一个编程语言更多的是出于好奇而不是实用目的。但是，再考虑 一下文章开头给出的示例编程语言。如果对这个示例语言进行扩展，支持 SQL 声明、 将原生类型的结果存储到变量、对结果集合进行迭代，那它就会成为一个可用的编程系统 — — 虽然会是一个不够灵活的系统。（实际上，我描述的这门示例语言或多或少就是 PL/SQL。）

这不是说要改变这门语言中的类型（denoted or expressed types）。即使这门语言仍然只 能将数值当做变量或表达式值处理，只要它能够将这些数值存储到关系中，并且能通过查询 再将它们取出来，那这门语言的处理能力也会得到巨大提升。

9.4 SQL 优缺点

SQL 也有一些限制：

• 表名（table names）在一个全局 namespace 中，行和列都是全局可访问的（你无法创建 私有列或行，虽然在某种意义上说，每次查询得到的结果都是一张私有表，可以作为私有 行和列使用）
• 每列通常情况下只能 hold primitive 数据类型，例如数值和字符串（至少现代数据库已 经不再像 COBOL 一样只支持固定宽度的字符串了）
• 经常运行非常慢（painfully slow）

从某个角度看，SQL 操作，以及它的优缺点，和并行数组非常相似：

for (int i = 0; i < moz_hosts_len; i++) {
    if (0 == strcmp(moz_hosts_host[i], "news.ycombinator.com")) {
        results[results_len++] = moz_hosts_id[i];
    }
}

或者，下面的例子更清晰地展示了 SQL 如何节省了你写算法的 effort，用并行数组实现一 个 sort-merge join 非常难于维护，而用 SQL：

select accountholder.middlename
from accountholder, account
where accountholder.id = account.accountholderid

如果用 C 语言和并行数组来实现同样的功能：

int *fksort = iota(account_len);
sort_by_int_column(account_accountholderid, fksort, account_len);
int *pksort = iota(accountholder_len);
sort_by_int_column(accountholder_id, pksort, accountholder_len);
int i = 0, j = 0, k = 0;
while (i < account_len &amp;&amp; j < accountholder_len) {
    int fk = account_accountholderid[fksort[i]];
    int pk = accountholder_id[pksort[j]];
    if (fk == pk) {
        result_id[k] = fk;
        result_middle_name[k] = accountholder_middlename[pksort[j]];
        k++;
        i++;                // Supposing accountholder_id is unique.
    } else if (fk < pk) {
        i++;
    } else {
        j++;
    }
}
free(fksort);
free(pksort);

这里 iota 的实现是：

int *iota(int size) {
    int *results = calloc(size, sizeof(*results));
    if (!results) abort();
    for (int i = 0; i < size; i++) results[i] = i;
    return results;
}

sort_by_int_column 或多或少可以实现如下：

void sort_by_int_column(int *values, int *indices, int indices_len) {
    qsort_r(indices, indices_len, sizeof(*indices),
            indirect_int_comparator, values);
}

int indirect_int_comparator(const void *a, const void *b, void *arg) {
    int *values = arg;
    return values[*(int*)a] - values[*(int*)b];
}

SQL 背后的实现使用了很多技巧，牺牲了简单查询的效率，但提高了复杂查询的效率， 而用户程序看到的抽象是一样的。

9.5 评论：抽象层次

人们经常说 SQL 是一门声明式语言（declarative language）：不需要说明应该如何计算 结果（how a result is computed），只需要说明你希望的结果是什么（what result is desired）。 我认为这种观点只是部分正确，而且语言并不是只能分为声明式（declarativeness）或非 声明式两种，这涉及的是描述的抽象层次（level of abstraction of the description） ，而这是一个无限连续体（infinite continuum）问题，如果只是出于性能原因，那些低于 这个抽象层次但很实用的考虑一定会不可避免的侵入进来。

也许更有趣的是，Prolog 和 miniKANREN 实现了关系型模型（虽然二者的实现并不纯粹 ），它们将关系型编程和对象图（object-graph）递归数据结构结合起来，取得了真正令 人惊叹的能力。例如，一个非常简单的 miniKANREN 程序可以在一个合理的计算时间内， 生成无限多个输出自身源代码的程序（quines）。

广义的有约束编程（constraint programming）领域中，只需指定期望的结果的一些特性（结 果必须满足的“约束”），然后系统会承担寻找答案的任务，由于 SAT 和 SMT solvers 近些 年取得的巨大进步，这个领域正在取得长足的发展。

? HOST DISCONNECT CAUSED BY ISTIO SIDECAR INJECTION[译] C 不是一门低层（LOW-LEVEL）语言（ACMQUEUE, 2018） ?

? 2016-2022 Arthur Chiao, Powered by Jekyll , Theme originated from Long Haul. Site visits: , powered by busuanzi