首先谢谢灰咕姐姐帮我画的可爱封面！
写在前面
我很偶然地想要写这篇文章，其实我本来想把这些内容写在我另一篇正在写的文章（关于函数式编程的）的一部分，但是我发现这实在是太棒了，于是欣然决定专门开一篇文章来写，或许它可以为那个不知道是否能完成的函数式编程文章做铺垫。
我原本打算在十二月初就能看完它并且完成这篇文章，但是我感染了新冠，就这么昏睡了一个周末，又有另外一个项目正在做，而期末考就快来了...就少了很多时间折腾这些，总之，就这样吧。
文章内容只是我个人对论文内容的一个小小的总结和一些理解，若你对此产生了兴趣，我强烈建议你阅读这个经典论文（这可是函数式编程的开山之作！）。
https://www.cs.cmu.edu/~crary/819-f09/Backus78.pdf
论文及作者简介
《Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs》（编程能否从冯·诺依曼风格中解放出来？程序的函数式风格及其代数）是John Backus在1977年获得了图灵奖的一篇演讲论文。
论文作者John Backus在获得图灵奖之前也有一些对计算机界有很大贡献并影响至今的东西，例如这个极具代表性的：
他带领他的团队做出了Fortran，它是第一个高级编程语言（第一个版本于1957发布），比我们耳熟能详的Lisp还要早。即便至今已有几十年历史，它仍然不过时，并且仍然在更新。他设计Fortran的初衷是为IBM704系统设计一个更加接近自然语言的编程语言以提高开发效率，事实也是如此，它比汇编语言可以少20倍的代码量，而且更加易懂。可以说是现代计算机产业以及其他高级编程语言的开端。
冯·诺依曼风格
计算系统模型分类
我们根据一些标准可以对计算系统分类模型，该模型是否有一个精致且紧凑的数学描述？陈述是简单还是复杂？每种编程语言的基础都是一个模型，作者将现有的模型分成三类：
简单操作模型：图灵机，各种自动机，简明有用，有历史敏感性（有储存），语义上，状态转换非常简单。 应用模型：Lambda演算，combinators 系统，纯Lisp，后面会描述到的函数式语言。精确且有用，历史不敏感，规约语义（无状态的）程序清晰。 冯·诺依曼模型：冯·诺依曼计算机，传统编程语言。复杂庞大，历史敏感，带有复杂的状态转换。
注：历史敏感性指允许一个程序执行会影响后续的某个行为。
不过这个分类确实多少有些粗暴，也会有一些无法分类进去的东西，这篇论文我们需要关注的是应用模型和冯·诺依曼模型
冯·诺依曼语言
首先将目光移向标题，“编程能否从冯·诺依曼风格中解放出来？”。
冯·诺依曼在20世纪40年代，为了解决当时的ENIAC计算机低效而提出的一种计算机的结构设计（相关论文：First Draft of a Report on the EDVAC），这种结构被沿用至今，仍然是计算机的主流结构。在那之前的计算机，程序和数据是两个概念，程序是控制器的一部分，这样即低效又不灵活，而冯·诺依曼提出了将程序编码作为数据一同存在储存器中，执行程序只是从储存器中依次取出指令并执行，也就导致了现在硬件设计和程序设计可以分开进行，无论是程序还是数据的最终都是二进制编码。并且他确定了计算机的组成部分：运算器，控制器，存储器，输入设备，输出设备。
这个做法在当年可以说是前所未有的突破，做到了优雅又实用，简化了工程和编程问题的复杂性。而标题的“von Neumann Style”其实就是指受冯·诺依曼结构影响的编程风格。冯·诺依曼结构催生了“冯·诺依曼编程语言”，而限制了开发者。John Backus认为编程语言为了适应冯·诺依曼结构而变得笨重且低效。而所谓“传统编程语言”基本上都只是更复杂的冯·诺依曼语言，Fortran 和 Algol 68看起来相差很大，但都是冯·诺依曼语言。体现在使用变量模仿计算机的储存单元，使用流程控制语句来详细说明它该做的事，逐字逐句的解释。而我们依赖这种语言，几乎所有语言都是建立于冯·诺依曼语言的原则之上，也就延续了冯·诺依曼语言的地位，限制了非冯·诺依曼语言的发展。在论文中John Backus提到，【赋值语句是编程语言的冯诺依曼瓶颈，令我们不断思考，用着几乎相同的方式逐字逐句地解释。】
冯·诺伊曼瓶颈
你可能已经听说过了冯·诺伊曼瓶颈(von Neumann Bottleneck)。首先看看这是冯·诺依曼结构的图（来自Wiki：Von Neumann architecture）
在冯·诺伊曼结构中，数据与指令并不会被分开，而是存放在同一内存中。来对比一下另外一个，哈佛结构（Harvard architecture）则会分为Instruction Memory和Data Memory，则就算在没有缓存的情况下，读取指令和数据访问也可以同时进行，因为他们不在同一个内存通道。（图来自Wiki：哈佛架构）
再看回冯·诺依曼结构，若处理器要从内存读数据，处理完成再送回去，而指令和数据还放在一起，这导致取指令的同时就不能取数据，这个问题在冯·诺依曼结构出来的时代并不会显得多严重，但是几十年后的CPU运算速度远远大于当时，而CPU运算再快也得浪费时间来等这些数据，这就会浪费很多CPU利用率。而这个“传输”就被称为冯·诺依曼瓶颈。
传统编程语言的问题
John Backus认为传统编程语言大而笨重，而且还复杂，表达能力和可变性非常有限。
首先，这是我对6.Language Frameworks versus Changeable Parts的第1，2段做的一个简单的翻译。
让我们区分编程的两个部分，首先，它的框架给了系统的总体规则，其次，它的可变部分，其框架预期存在，但没有指定特定行为。例如，for语句和几乎所有其他语句都是Algol框架的一部分，一种语言的框架描述了它的固定特征，为其多变的特征提供了一个通用的环境。假设一种语言与一个小框架，它可以容纳各种各样的强大功能完全作为多变的部分，那么，这样的框架可以支持很多不同的特性和风格，冯诺依曼语言似乎总是有一个巨大的框架和非常有限的可变性，是什么原因导致这种情况发生？答案关注冯·诺依曼语言的两个问题。
顺便提一下，【Algol】是在20世纪50年代中期发展起来的一种命令式编程语言，被设计用来避免FORTRAN中一些已知的问题。
扯回这个问题，John Backus所认为的冯·诺依曼语言的两个问题。第一个问题就是前面有提到的逐字解释（word-at-a-time）的编程风格，每个字在状态中来回流动，就像流过冯·诺依曼瓶颈一样。句法和状态转移的强耦合，也就是在传统编程语言里面进行状态管理，要做语法层面手动操作。
这篇论文发表于1977年，当时并没有那么多新的编程范式，例如我们现在比较流行的面向对象编程。在当时传统编程语言不提供有效的组合形式，这体现在你无法基于现有程序去构建新的程序。光是扯理论好像没那么好理解，我们来看看作者在论文中提出的一个简单的例子————一个内积程序。
首先，这是向量内积运算的计算公式：
用我们的“传统编程语言”的思维来实现，就用For循环罢！这是Algol语言对此的实现：
c := 0
for i := 1 step 1 until n do
c := c + a[i] x b[i]
John Backus是如此评价这种方式的：
它的语句根据复杂的规则对不可见的“状态”进行操作 它并不是分层的 这是一个重复且动态的指令，你必须在脑子里执行一遍才能看懂 重复分配和修改变量【i】，逐字解释 一部分数据，n在程序中，因此它缺乏通用性 给变量命名，只能用于向量A和B。
最后一点在论文中是这样的，作者貌似没有在这里就讲完：
It names its arguments; it can only be used for vectors a and b. To become general, it requires a procedure declaration. These involve complex issues (e.g., callby-name versus call-by-value).
这是作者提出的一个 “函数式的，内积的程序”做法
Def Innerproduct
≡ (Insert +) ° (ApplyToAll x) ° Transpose
以缩写形式就是
Def IP ≡ (/+) ° (α ×) ° Trans.
Composition (°)、Insert (/) 和 ApplyToAll (α)是结合现有的函数形成的新的东西，因此， f ° g 是由首先应用 g 然后是 f 而得到的函数，αf 是由 f 应用到参数的所有成员而得到的函数，如果对将 f 应用到对象 x之后的结果，我们写下了 f :x ，那么我们就可以解释“在评估内积到向量对<<1, 2, 3>, <6, 5, 4>> 的应用”的每一步了。
与前面那个传统编程语言比较一下
它仅仅在它的参数上运行，没有隐含的状态和复杂的转换条件。 有层级的，可组合的，它由三种更简单的函数构建而成(+, x, Trans)，和三种函数形式，分别是f°g，αf，/f 它静态且不重复，有助于人类理解它（而不像上面那个，你要脑补一遍才能理解） 其操作是在整个概念单元上的，而不是单词，它的三个步骤是独立且不重复的 完全通用，适用于任何一对一致的向量 没有给变量命名，可以被应用到任何一对向量而没有任何过程声明和复杂的替换条件 程序指令通用而可组合，可以组合成更高阶的操作符。
像“不给变量命名”这类论点不做探讨了，因为这想法在几十年后的今天也几乎没有被实现。
前面提到的，句法和状态转移的强耦合，指冯·诺依曼语言的语义和状态必须密切耦合，其中计算的每个细节都会改变状态，导致你要把细节构建到状态和转换规则中去。你在研究那个“框架”的细节必须明确它的每个特性。
所谓【一门编程语言有力的可变部分】最重要的无非就是可以从旧的构建出新的过程，而冯·诺依曼语言只提供了原始的组合形式。冯·诺依曼语言中表达式和陈述句分裂成了两个世界，函数式属于表达式世界，一个有用的代数性质的世界。而在陈述句世界，主要语句就是赋值语句，它缺乏有用的数学性质。冯·诺伊曼语言缺少有用的数学性质，对程序推理造成障碍，许多证明是通过代数推导出来的，而使用这种方法需要这个语言具有一定的代数性质。那么就可以机械地来把问题转换成解决方案，这是论文中作者提出的一个简单的例子。
ax + bx = a + b
(a+b)x = a + b
(a+b)x = (a + b)1
x = 1
我们就能解出这个简单的方程，而没有脱离代数的语言，在冯·诺依曼语言几乎没有以这种方式解决问题的可能性。
冯·诺伊曼语言的替代者？
在论文的开头作者有提到这篇论文的目的有两个，一是提出常规框架的缺陷所导致编程语言表现力的弱点，其次，建议一些新的语言种类，探索替代途径。
对冯·诺伊曼语言替代方案的探索
在一门历史敏感的语言中，一段程序允许改变一些由系统保存的存储，影响后面程序来的行为，任何这样的语言都需要某种状态转换语义。但并不是指每个计算都必须非常密切的与这个状态耦合，John Backus将这样的系统称为应用状态转移（Applicative State Transition）系统（AST）。
John Backus早在1977年就为我们指出了这个正确的方向，我们需要一个为状态转移提供的一个语义模型，在这个复杂的系统下，尝试避免状态变化貌似是一个十分愚蠢的做法。
past three or four years and have not yet found a satisfying solution to the many conflicting requirements that a good language must resolve. But I believe this search has indicated a useful approach to designing nonvon Neumann languages.
John Backus将这种【方法】总结为四个要素
一种没有变量的函数式编程风格 函数式程序的代数。描述一个代数，其变量表示函数式程序设计的函数性程序，其操作则是函数式程序设计的程序的组合形式。给出了代数的一些定律，一些定理和例子，以说明某些函数表达式如何转换为等价的无穷展开。 正式的函数式编程系统 一个上面所提及的应用状态转换系统（即AST）。
函数式编程系统（FP Systems）
这是John Backus提出的一个非正式的类函数式编程（Functional Programming）系统。FP系统基于使用一组固定的组合形式，被称为函数形式（functional form）。这些加上简单的定义就是从现有函数构建新函数的唯一的方法。在FP系统中不使用变量，所有功能都属于一种类型：函数将对象映射到对象并始终采用单个参数。
A functional form refers to the algebraic form of a relationship between a dependent variable and regressors or explanatory variables.
其实，我们所见到的，现代的函数式编程语言与当时John Backus曾希望的函数式编程范式还是有不少区别，但是大体上的思想还是那样。在I. Functional Programming Systems (FP Systems)中他有对FP系统做出比较详细的描述，篇幅有限就介绍一部分（更多是翻译和理解，还有一些小小的补充）。
一个FP系统应该包括
一组O对象 将对象映射到对象的函数f的集合F 一个操作，应用 一组F函数形式（Functional forms好像）用于组合现有的功能或对象，以形成新的功能F 定义F中的一些函数的一组定义D，并为它们每个分配名称
对象（Objects）
一个对象x也是一个原子（Atom），一个序列<x~ .... , Xn>，其元素Xi是对象或⊥。所以集合A原子数量的选择决定了对象的集合。
⊥是未定义的（undefined）值，又叫底（bottom）。
将A视为由大写字母、数字、特殊符号的非空字符串的集合。这些字符串未被FP系统的符号使用，其中一些字符串属于被称为数字的原子类别。Φ用于表示空序列并且是唯一既是原子又是序列的对象。原子T（True）和F（False）表示“真”和“假”。在构造对象时，一个很重要的约束条件是，如果x是以J_为元素的序列，则x = ⊥，也就是"sequence constructor" is "⊥preserving." 因此，没有适当的序列是以i作为元素的。
应用（Application）
FP系统只有一种操作，即应用（Application）。假设f是函数且x是对象，则f:x是一个应用并表示将f应用于x的结果的对象。这是一个例子：
+:<1,2> = 3 tI:<.A,B,C> = <B,C>
I:<A,B,C> = A 2:<A,B,C> = B
函数（Functions）
所有函数fin F都将对象映射到对象，并且是底保持（bottom-preserving）的：f:⊥ = ⊥, F中所有的f。函数要么是原始（primitive）的，要么是Functional form。 原始函数是由FP系统所提供的，或已定义的。Functional form是程序形成的运算操作（建造自原始函数的）。
将两者区分开在某些情况很有用，例如f:x=⊥的情况下，如果f:x的计算终止并产生了对象_1_，即f在x处未定义，f终止但在x处没有有意义的值，否则就是f在x处不终止。 他们的目的是为FP系统提供广泛的，有用且强大的原始函数。在原文的11.2.3 Functions段落，作者有举出很多原始函数的例子，例如Selector，Tail，都有对它们较细的解释（所列出的函数在原文后面的例子会经常用到，但是篇幅有限我不挨个例子写了）。
（剩余关于FP系统的详细内容参见原文11-13节）
John Backus认为FP系统比传统语言或者给予Lambda演算的语言要简单得多，它们只是用基本点固定命名系统和一个简单的固定规则，用一个函数代替它的名字，因此它避免了传统命名系统和Lambda演算的替换规则的复杂性。
FP的局限性
FP有一些限制，例如给定的FP系统是一种固定的语言；它对历史不敏感；没有程序可以改变程序库；FP系统无法计算程序，因为函数表达式不是对象；也不能在FP系统定义新的功能形式。
应用状态转换系统
本段对应原文的14节Applicative State Transition Systems (AST Systems)
对AST系统与ALGOL的结构做一个比较。Algol程序是一系列语句，每个语句代表Algol状态转换。这个“状态”指堆栈、指针、标识符到值的变量映射等状态的复杂信息储存。Algol语句它不是“状态到状态”函数的表达式，它们是具有上下文相关部分的复杂消息，每个部分通过自己的协议将信息传输到状态，或从状态传输信息。
而AST系统提供了一种方法实现一种语义不受影响的计算系统，其语义不依赖于与状态通信的大量复杂的协议，而是有两个协议来从状态获取信息：1，从中获取要应用的函数的定义。2，获取整个状态本身。然后有一个用于更改状态的协议：通过函数应用计算新状态。并且，AST语义不依赖于状态改变，是因为状态本身没有改变。计算结果是输出和一个新的状态。它的结构上一个序列，比Algol状态的结构要简单许多，AST系统的结构避免了那种传统状态的复杂性和限制，以完全不同和更简单的方式实现了更自由的框架。
一个AST系统的结构：
一个应用子系统 一个状态D，即应用子系统的定义集合 一组转换规则,它们描述输入如何被转换为输出,以及如何改变状态D
应用子系统不能改变状态D，它在计算一个表达式期间不发生改变，新状态联通输出一起被计算，并在给出输出时，新状态代替掉旧状态。
14节包含对AST系统结构、转换规则的详细解释和一些应用例子。
最后
我无法将论文中的每个细节都给写完，在原文内有很多实例讲解能很好的助于你理解。关于一些词如何翻译的问题我考虑了很久，有些翻译可能多少不准确，所以，我的建议是，在能力允许下去阅读原文。如果你有接触过函数式编程，你可能会觉得这篇论文关于函数式编程的观念和实际很不一样，事实也确实如此。FP算是一个开山之作，它是学术界开始活跃探索函数式编程的开端，导致了现代函数式编程语言，但很多地方并不是当时John Backus所期望的那样。FP系统自身未被在学术界之外大量使用过，1980年代John Backus又建立了FL作为FP的后继语言。
虽然如此，感觉冯·诺依曼架构被替代仍然很遥远，哪怕是几十年后的今天。但在语言层面上人们已经有了更多突破传统编程语言限制的尝试，总之，让我们拭目以待吧。
