程序设计能从冯.诺依曼风格中解放出来吗?程序的函数风格及其代数-----John Backus (IBM RESEARCH)

此文为1977年ACM演讲,以下为关键部分的摘抄及自己的解读:

1 传统程序设计语言:肥胖和脆弱

程序设计语言稳步地前进到它们今天肥硕的状况已经20年了,结果,程序设计语言的研究和发明已经失去了许多激动人心的东西.代替的是,它现在是那样一些人的领域:它们偏爱对细节厚厚的叙述进行工作,而不是用新的思想来进行奋斗.关于程序设计语言的讨论,经常类似于中世纪关于一个针尖上有几个能跳舞的天使的争论(tertio吐槽:翻译好次,原翻译是一个别针头上有几个能跳舞的安琪儿,靠!!!) ,而不是在基本不同的概念之间令人振奋的竞争.

2 计算系统的模型
模型的准则:

基础: 有没有一个对模型优雅而简洁的数学描述呢?
历史敏感性: 模型是否包括存储的思想,使得一个程序可能保存能影响后来程序特性的信息?
语义类型: 一个程序是否逐次地转换状态直到达到终止状态?
程序的清晰性和概念的有用性: 模型的程序是不是一个进程或计算的清晰表达式?

模型的分类:

1 简单的运算模型
例子: 图灵机各种自动机

2 应用模型
邱奇的lambda演算,柯里的组合子系统,纯粹的lisp,本文中描述的函数程序设计系统

3 冯诺依曼模型
冯诺依曼计算机,传统的程序设计语言吧

冯诺依曼语言:

赋值语句把程序设计分为两个世界.头一个世界由赋值语句的右边组成.这是有序表达式的世界,这是一个有用的代数性质的世界.它是大多数有用的计算发生于其中的世界.

传统程序设计语言的第二个世界是语句的世界.在这个世界中,主要的语句是赋值语句本身.语言中所有其他语句的存在是为了使实施计算成为可能,这个计算必须以这个原始构造为基础:赋值语句.

语句的这个世界是一个无序的世界,而且有很少有用的数学性质.结构程序设计可以看做向这个混沌的世界引入某些秩序的适度努力,但它在解决由一次一字的冯诺依曼程序设计风格所建立的基本问题方面成就很小,而且它主要使用循环,下标和控制的转移流动.

应用计算机系统: (tertio注: 指lambda演算,lisp)
应用计算机系统缺乏存储和历史敏感性是它们没有为计算机设计提供基础的基本原因.而且,大多数应用系统应用lambda演算的替换运算作为基本运算.这个运算有无限的威力,但它的完备和有效实现给机器设计者带来很大困难.

其次,在引进存储和改进对冯诺依曼计算机有效性的努力中,应用性系统已经趋向于淹没于大型的冯诺依曼系统中.例如纯粹的Lisp通常被淹没在具有许多冯诺依曼特征的大型系统中...

9 冯诺依曼语言缺乏有用的数学性质

公理语义精确地把冯诺依曼程序不优美的性质重新表述为谓词的转换.一次一字的重复游戏不因此而改变,只是游戏场地变了而已.
因此指称和公理语义时其基础体现优雅和强有力概念的描述机制,但是用它们来描述冯诺依曼语言不能产生一个优雅和强有力的语言.......

10 冯诺依曼语言的替代者是什么?

我们首先认识到一个系统不能是对历史敏感的(允许一个程序的执行影响随后的行为),除非这个系统有某种状态(头一个程序可以改变它而第二个程序可以访问它).因此至少在这个弱的意义下,计算系统对历史敏感的模型必须由一个状态转移的语义,但这并不意味着诶个计算都必须强烈地依赖一个复杂状态,而且对每一部分的计算都要求许多状态变化(如同在冯诺依曼语言中那样)
...
这些系统,我称之为应用状态转移(AST, Applicative State Transition)系统.这些简单系统避免冯诺依曼语言的许多复杂性和弱点,并且提供可变部分的一个强有力且广泛的集合.

(tertio注: 作为一个复杂系统,回避状态变化是鸵鸟的行为---这正是当前函数式的鼓吹者们错误的观点,为状态转移提供一个语义模型才是正途,而这一点巴科斯在1977年已经为我们指出了正确的方向)

在过去的三至四年中,我已经研究这个领域,但对于一个好的语言必须解决的许多冲突要求,还没有找到满意的解.但我相信这个寻找已经指出设计非冯诺依曼语言的一个有用方法.

这个方法涉及4个成分:

1 不带变量的函数风格的程序设计.

2 函数程序代数.描述了一个代数,其变量表示函数程序设计的函数性程序,而其"操作"是函数程序设计的函数形式,即函数程序设计的程序的组合形式.给出了代数的某些定律,给出一些定理和例子,来说明某些函数表达式如何转换为等价的无穷展开....

3 一个形式的函数程序设计系统.

4 应用的状态转移系统.

(以下是对上述4点的展开,由于有很多公式及推导,而且符号也没法打出来,略,实际上作为程序员来说,学习了lisp之后应该就不必再看前三个部分的公式及说明了)

(我认为这里最重要的是4,----应用状态转移系统)

14 应用状态转移(AST)系统

AST系统的结构:

1 一个应用子系统(例如FFP系统)
2 一个状态D,即应用子系统的定义集合
3 一组转换规则,它们描述输入如何被转换为输出,以及如何改变状态D

应用子系统不能改变状态D,而且在计算一个表达式期间,它不发生改变.新状态连同输出一起被计算,并在给出输出时,代替旧的状态.

以上是AST系统的概述

总之,巴科斯在这篇1977年的文章中,已经超越了命令式还是函数式的争论,在一个AST系统中,将函数式和状态转移模型结合在了一起.