时间戳

首页 > 解决方案 > C++ 被认为是冯诺依曼编程语言吗？

c++ - C++ 被认为是冯诺依曼编程语言吗？

问题描述

冯诺依曼语言一词适用于其计算模型基于冯诺依曼计算机体系结构的编程语言。

在此处输入图像描述

标签： c++computer-sciencecpu-architecturelanguage-designvon-neumann

解决方案

TL:DR: C++ 抽象机是一种PRAM（并行随机存取机）。

从您链接的冯诺依曼语言维基百科文章：

通过以线程的形式添加对并行处理的支持，许多广泛使用的编程语言（例如 C、C++ 和 Java）不再是严格的冯诺依曼语言。

停止描述了从存在到不存在的过渡。所以是的，根据维基百科，在 C++11 添加线程之前，C++严格来说是一种冯诺依曼语言。（在它基本上仍然是一种 VN 语言之后；让多个线程共享相同的地址空间并不会从根本上改变 C++ 的工作方式。）

在这种情况下成为冯诺依曼架构的有趣部分：

  • 完全拥有可寻址 RAM，允许随时高效访问（模缓存/分页）任何对象
  • 将程序存储在 RAM 中：函数指针是可能且高效的，无需解释器
  • 有一个程序计数器，可以逐步执行存储程序中的指令：自然模型是一种命令式编程语言，一次只做一件事。这是非常基本的，很容易忘记它不是唯一的模型！（与 FPGA 或 ASIC 或所有门可能在每个时钟周期并行执行某些操作的东西。或 MIMD GPU 中，您编写的计算“内核”可能并行运行在所有数据上，而没有隐含的顺序每个顺序元素被处理。或计算RAM：将ALU放在内存芯片中以绕过冯诺依曼瓶颈）

IDK 为什么 wiki 文章提到了自修改代码；与大多数语言一样，ISO C++ 没有对其进行标准化，并且与拆分总线/拆分地址空间哈佛架构的提前编译完全兼容。（没有eval或其他任何需要解释器或 JIT 的东西。）或者在普通 CPU（冯诺依曼）上，严格的 W^X 内存保护，并且从不使用mprotect将页面权限从可写更改为可执行。

当然，大多数真正的 C++ 实现确实提供了定义良好的方法来将机器代码写入缓冲区并转换为函数指针，作为扩展。（例如，GNU C/C++__builtin___clear_cache(start, end)以 I-cache 同步命名，但定义为可以安全地将数据调用为函数 wrt。死存储消除优化也是如此，因此即使在 x86 上，代码也可能在没有它的情况下中断它具有一致的 I-caches。）因此实现可以扩展 ISO C++ 以利用 Von Neumann 架构的这一特性；ISO C++ 有意限制范围，以允许操作系统和类似的东西之间存在差异。

请注意，成为冯诺依曼并不严格意味着支持间接寻址模式。一些早期的 CPU 没有，而自修改代码（重写指令中硬编码的地址）对于实现我们现在使用间接寻址的东西是必要的。

另请注意，约翰·冯·诺依曼（John Von Neumann）是一位非常有名的人，他的名字与许多基本事物有关。冯诺依曼架构（与哈佛相反）的一些内涵并非在所有情况下都真正相关。例如，“冯诺依曼语言”一词并不太关心冯诺依曼与哈佛的对比；它关心带有程序计数器的存储程序与像元胞自动机或图灵机（带有真实磁带）之类的东西。通过使用单独的总线（或只是拆分缓存）来获取指令（哈佛）来获得额外的带宽只是一种性能优化，而不是根本性的改变。

什么是抽象机器模型/计算模型？

首先，有一些计算模型比图灵机弱，比如有限状态机。还有非顺序计算模型，例如元胞自动机（康威的生命游戏），其中每个“步骤”并行发生多件事。

图灵机是最广为人知的（数学上最简单的）顺序抽象机，它和我们知道如何制造一样“强大”。没有任何绝对的内存寻址，只是磁带上的相对移动，它自然地提供了无限的存储空间。这很重要，并且使所有其他类型的抽象机器在某些方面与真正的 CPU 非常不同。请记住，这些计算模型用于理论计算机科学，而不是工程。诸如有限内存或性能之类的问题与理论上的可计算内容无关，仅在实践中。

如果您可以在图灵机上计算某些东西，则可以在任何其他图灵完备的计算模型上进行计算（根据定义），可能使用更简单的程序，也可能不使用。图灵机不是很好编程，或者至少与任何真实 CPU 的汇编语言有很大不同。最值得注意的是，内存不是随机访问的。而且他们不能轻易地为并行计算/算法建模。（如果你想在抽象中证明某个算法，那么为某种抽象机器实现它可能是一件好事。）

证明抽象机器需要具备哪些特性才能实现图灵完备也可能很有趣，因此这是开发更多抽象机器的另一个动机。

就可计算性而言，还有许多其他的等价物。RAM 机器模型最类似于具有内存阵列的现实世界 CPU 。但作为一个简单的抽象机器，它不会打扰寄存器。事实上，为了让事情更混乱，它把它的内存单元称为寄存器数组. RAM 机器支持间接寻址，因此与现实世界 CPU 的正确类比肯定是内存，而不是 CPU 寄存器。（并且有无限数量的寄存器，每个寄存器的大小都是无限的。地址永远存在，每个“寄存器”都需要能够保存一个指针。）RAM 机器可以是哈佛：程序存储在单独的有限状态部分机器。把它想象成一台具有内存间接寻址模式的机器，因此您可以将“变量”保存在已知位置，并将其中一些用作指向无限大小数据结构的指针。

抽象 RAM 机器的程序看起来像汇编语言，带有加载/添加/jnz 以及您希望它拥有的任何其他指令选择。操作数可以是立即数或寄存器数字（普通人称之为绝对地址）。或者如果模型有一个累加器，那么你有一个带有累加器的加载/存储机器，它更像一个真正的 CPU。

如果你想知道为什么像 MIPS 这样的“3 地址”机器被称为而不是 3 操作数，它可能是 1。因为指令编码需要空间/I-fetch 带宽，通过 Von Neumann 瓶颈来获取 3 个显式操作数位置（寄存器number) 和 2. 因为在 RAM 抽象机中，操作数是内存地址 = 寄存器号。

C++ 不可能是图灵完备的：指针的大小是有限的。

当然，C++ 与 CS 抽象机器模型有很大的不同：C++ 要求每种类型都有一个 compile-time-constant 有限的，所以如果你包括无限存储要求sizeof，C++就不可能是图灵完备的。中的所有内容实际上是图灵完备的吗？关于 cs.SE 也适用于 C++：类型具有固定宽度的要求是无限存储的阻碍。另请参阅https://en.wikipedia.org/wiki/Random-access_machine#Finite_vs_unbounded

所以计算机科学抽象机很傻，C++ 抽象机呢？

它们当然有它们的目的，但是关于 C++，我们可以说更多有趣的东西，如果我们不那么抽象的话，它会假设什么样的机器，还可以谈论机器可以高效地做什么。一旦我们谈论有限机器机器和性能，这些差异就变得相关了。

首先，完全运行 C++，其次，在没有巨大和/或不可接受的性能开销的情况下运行。（例如，硬件将需要相当直接地支持指针，可能不需要将指针值存储到使用它的每个加载/存储指令中的自修改代码。这在线程是其中一部分的 C++11 中不起作用语言：相同的代码可以同时在 2 个不同的指针上运行。）

我们可以更详细地了解 ISO C++ 标准所假设的计算模型，该标准描述了该语言如何根据抽象机上发生的情况来工作。真正的实现需要在真正的硬件上运行代码，这些代码“好像”抽象机器正在执行 C++ 源代码，重现任何/所有可观察的行为（无需调用 UB 即可被程序的其他部分观察到）。

C/C++ 有内存和指针，所以它绝对是一种 RAM 机器。

或者现在，一台并行随机存取机器，将共享内存添加到 RAM 模型中，并为每个线程提供自己的程序计数器。鉴于std::atomic<>释放序列使所有先前的操作对其他线程可见，同步的“建立之前发生的关系”模型是基于连贯的共享内存。在需要手动触发同步/刷新的东西之上模拟它对性能来说是可怕的。（非常聪明的优化可以证明什么时候可以延迟，所以不是每个发布存储都必须受到影响，但 seq-cst 可能会很糟糕。seq-cst 必须建立一个所有线程都同意的全局操作顺序；这很难，除非一个商店同时对所有其他线程可见。）

但请注意，在 C++ 中，实际同时访问是 UB，除非您使用atomic<T>. 这允许优化器自由地将 CPU 寄存器用于本地、临时甚至全局，而无需将寄存器作为语言特性公开。 UB通常允许优化；这就是为什么现代 C/C++ 实现不是可移植的汇编语言的原因。

C/C++ 中的历史register关键字意味着不能获取变量的地址，因此即使是非优化编译器也可以将其保存在 CPU 寄存器中，而不是内存中。 我们谈论的是 CPU 寄存器，而不是计算机科学 RAM 机器“寄存器 = 可寻址内存位置”。（例如rax..rsp/r8..r15在 x86 或r0..r31MIPS 上）。现代编译器会逃避分析并自然地将本地人正常保存在寄存器中，除非他们必须溢出它们。其他类型的 CPU 寄存器也是可能的，例如像 x87 FP 寄存器这样的寄存器堆栈。 无论如何，register关键字的存在是为了优化这种类型的机器。 但不排除在没有寄存器、只有内存-内存指令的机器上运行。

C++ 被设计为在具有 CPU 寄存器的冯诺依曼机器上运行良好，但 C++ 抽象机（标准用于定义语言）不允许将数据作为代码执行，或者说任何关于寄​​存器的内容。但是，每个 C++ 线程都有自己的执行上下文，并且对 PRAM 线程/内核进行建模，每个线程/内核都有自己的程序计数器和调用堆栈（或实现用于自动存储和确定返回位置的任何东西。）在真实机器中对于 CPU 寄存器，它们对每个线程都是私有的。

所有现实世界的 CPU 都是随机存取机，并且 CPU 寄存器与可寻址/可索引 RAM 分开。即使 CPU 只能使用单个累加器寄存器进行计算，通常也至少有一个指针或索引寄存器，至少允许一些有限的数组索引。至少所有可以作为 C 编译器目标工作的 CPU。

如果没有寄存器，每个机器指令编码都需要所有操作数的绝对内存地址。（可能像 6502 一样，其中的“零页”，即内存的低 256 字节是特殊的，并且存在使用零页中的字作为索引或指针的寻址模式，以允许 16 位指针没有任何 16位架构寄存器。或类似的东西。）请参阅为什么 C 到 Z80 编译器会产生糟糕的代码？在 RetroComputing.SE关于真实世界的 8 位 CPU 的一些有趣的东西，其中完全兼容的 C 实现（支持递归和重入）实现起来非常昂贵。很多缓慢是因为 6502 / Z80 系统太小而无法承载优化编译器。但即使是假设的现代优化交叉编译器（如 gcc 或 LLVM 后端）也会在某些事情上遇到困难。另请参阅关于什么是未使用的内存地址？对于 6502 的零页索引寻址模式的一个很好的解释：来自内存中绝对 8 位地址的 16 位指针 + 8 位寄存器。

完全没有间接寻址的机器不能轻易地支持数组索引、链表，而且绝对不能将指针变量作为一等对象。（反正效率不高）

什么在真机上有效 -> 什么习语是自然的

C 的大部分早期历史都在PDP-11上，这是一个普通的 mem + register 机器，任何寄存器都可以作为指针工作。当需要溢出时，自动存储映射到寄存器或调用堆栈上的空间。内存是一个扁平的字节数组（或块char），没有分段。

数组索引只是根据指针算法定义的，而不是它自己的东西，也许是因为 PDP-11 可以有效地做到这一点：任何寄存器都可以保存地址并被取消引用。（相对于一些机器只有几个指针宽度的特殊寄存器，其余的更窄。这在 8 位机器上很常见，但早期的 16 位机器（如 PDP-11）的 RAM 足够少，只有一个 16 位寄存器一个地址就够了）。

有关更多历史，请参阅 Dennis Ritchie 的文章C 语言的发展；C 从 PDP-7 Unix 上的 B 发展而来。（第一个 Unix 是用 PDP-7 asm 编写的）。我对 PDP-7 了解不多，但显然 BCPL 和 B 也使用只是整数的指针，而数组是基于指针算术的。

PDP-7 是一个 18 位字可寻址 ISA。这可能就是为什么 B 没有char类型。但是它的寄存器足够宽，可以容纳指针，所以它自然支持 B 和 C 的指针模型（指针并不特别，你可以复制它们并取消引用它们，你可以获取任何东西的地址）。如此平坦的内存模型，没有像您在分段机器或一些零页的 8 位微控制器上找到的“特殊”内存区域。

诸如 C99 VLA（和无限大小的局部变量）和无限重入和递归之类的东西意味着函数局部变量上下文（也就是使用堆栈指针的普通机器上的堆栈帧）的调用堆栈或其他分配机制。

推荐阅读