Peter Naur：从ALGOL 60到"编程即理论建构"，他定义了程序设计的认识论

图灵奖第四十届（2005）| Peter Naur：从ALGOL 60到”编程即理论建构”，他定义了程序设计的认识论

一句话概括：当别人关注代码怎么写时,他思考程序员如何理解——Naur不仅是ALGOL 60的主编，更是第一个深刻认识到”程序设计是建立心智模型”的哲学家程序员。

🏆 获奖简介

Peter Naur（彼得·诺尔，1928-2016）是编程语言理论家、软件工程先驱、计算机科学哲学家。

Peter Naur：

出生时间：1928年10月25日
出生地点：丹麦腓特烈堡
逝世时间：2016年1月3日（享年87岁）
主要成就：ALGOL 60报告主编、BNF（巴科斯-诺尔范式）共同发明者、软件工程理论奠基人
获奖年份：2005年
获奖原因：表彰他对定义ALGOL 60编程语言的根本贡献（for fundamental contributions to programming language design and the definition of ALGOL 60）

为什么他是第四十位？ 1950年代末，编程语言设计还是”凭感觉”的艺术——语法定义模糊，语义描述不清，不同实现各自为政。1960年，一群计算机科学家聚集在巴黎，试图设计一种通用的算法语言ALGOL 60。Naur作为主编，不仅协调了欧美两派的分歧，更重要的是，他与Backus一起创造了BNF范式——第一个严格、形式化的语言语法描述工具。这个看似技术性的贡献，实际上开创了编程语言可以被精确定义、数学化研究的新时代。但Naur的贡献远不止于此。1970-80年代，当软件危机肆虐时，他提出了深刻的哲学洞见：“程序设计不是写代码，而是在程序员大脑中建立关于问题域的理论”。这个今天看来显而易见的观点，在当时是颠覆性的——它挑战了”代码就是一切”的主流观念，强调了人的心智模型在软件开发中的核心地位。从ALGOL的技术精确性到”理论建构”的哲学深度，Naur一生都在追问：程序究竟是什么？程序员究竟在做什么？

🚀 Peter Naur的重大贡献

1. ALGOL 60报告：第一个现代编程语言的诞生

背景（1950年代末）：

编程语言混乱：每个计算机厂商都有自己的语言
FORTRAN（1957）：成功但不够严谨，缺乏形式化定义
需求：科学计算界需要一个通用、严格定义的算法语言
1958年：国际计算机学会成立委员会，设计ALGOL 58

Naur的角色（1959-1960）：

ALGOL 60报告主编：

挑战：

欧美分歧：美国派（Backus、Perlis）vs 欧洲派（Dijkstra、Bauer）
哲学差异：实用性vs数学优雅
技术难题：如何精确描述语言？

1960年1月：巴黎会议

13天的激烈讨论
Naur担任编辑，协调各方意见
最终达成共识：ALGOL 60规范

ALGOL 60的革命性特性：

块结构（Block Structure）：

begin
  integer x;
  x := 10;
  begin
    integer x;  # 内层x遮蔽外层x
    x := 20;
  end;
  # 外层x仍是10
end

作用域：变量的可见性由块定义
影响：所有现代语言（C、Java、Python）都继承了这个概念

递归（Recursion）：

integer procedure factorial(n);
  value n; integer n;
  factorial := if n = 0 then 1 else n * factorial(n - 1);

允许过程调用自身
FORTRAN当时不支持，ALGOL率先实现

词法作用域（Lexical Scoping）：

变量引用在编译时确定，而非运行时
使程序更容易理解和验证

过程参数（Procedure Parameters）：

procedure integrate(procedure f; real a, b);
  # f是函数参数，高阶函数！

函数作为一等公民
启发了函数式编程

call-by-name：

参数传递的灵活机制
虽然后来被call-by-value和call-by-reference替代，但展示了设计空间

历史地位：

“计算机科学家的语言”：虽然商业应用不广，但学术界广泛使用
教科书标准：《计算机程序设计艺术》用ALGOL伪代码
语言家族树：C、Pascal、Simula、Ada都继承了ALGOL

2. BNF范式：编程语言的”DNA图谱”

问题：如何精确描述编程语言的语法？

早期方法：

自然语言：模糊，易歧义
示例：不完整，无法覆盖所有情况

Backus-Naur Form（BNF）的诞生：

1960年：

John Backus：提出基本思想（受Chomsky形式文法启发）
Peter Naur：在ALGOL 60报告中改进和应用
命名：后人称为”Backus-Naur Form”（Naur本人谦虚地称为”Backus Normal Form”）

BNF的核心思想：

语法规则用产生式表示：

<expression> ::= <term> | <expression> + <term> | <expression> - <term>
<term> ::= <factor> | <term> * <factor> | <term> / <factor>
<factor> ::= <number> | ( <expression> )
<number> ::= <digit> | <number> <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

符号说明：

<> ：非终结符（可继续展开）
::= ：定义为
| ：或（多个选择）
无<>：终结符（具体字符）

例子：推导表达式 3 + 4 * 5：

<expression>
→ <expression> + <term>
→ <term> + <term>
→ <factor> + <term>
→ <number> + <term>
→ <digit> + <term>
→ 3 + <term>
→ 3 + <term> * <factor>
→ 3 + <factor> * <factor>
→ 3 + <number> * <number>
→ 3 + <digit> * <digit>
→ 3 + 4 * 5

BNF的革命性意义：

精确性：没有歧义，完全形式化
完备性：覆盖所有合法程序
可验证性：可以机械地检查语法正确性
自动化：可以生成编译器的语法分析器（Parser）

影响：

编译原理：yacc、bison、ANTLR等工具都基于BNF
协议定义：HTTP、JSON、XML等都用扩展BNF（EBNF）定义
理论基础：连接了Chomsky层次结构与编程语言
今天仍在使用：几乎所有新语言都用BNF或其变体定义

3. 软件工程早期实践

1960年代：Naur在丹麦计算技术中心工作

GIER ALGOL编译器：

背景：

GIER：丹麦制造的真空管计算机
挑战：资源极其有限（内存几KB）

Naur的贡献：

领导开发GIER ALGOL编译器（1961）
世界上第一个完整的ALGOL 60实现之一
创新：
- 在极小内存中实现复杂编译器
- 优化技术：多遍编译、符号表压缩
- 证明了ALGOL 60的可实现性

意义：

打破了”ALGOL太复杂无法实现”的怀疑
影响了后续编译器设计（如Pascal编译器）

软件文档与工程方法：

1960年代末-1970年代初：

参与NATO软件工程会议（1968、1969）
- “软件工程”术语的正式化
- 讨论软件危机的解决方案
强调文档的重要性
倡导系统化的开发方法

4. “编程即理论建构”：软件工程的哲学转向

1985年：Naur发表论文**“Programming as Theory Building”**

核心论点：

程序不等于代码：

传统观念：

程序 = 源代码
软件开发 = 写代码
维护 = 修改代码

Naur的颠覆：

程序 = 代码 + 程序员大脑中的理论
理论（Theory）：关于问题域的心智模型
- 为什么这样设计？
- 哪些假设？
- 如何应对变化？

类比：想象一座建筑：

代码：就像建筑的蓝图和材料
理论：建筑师关于”为什么这样设计”的理解
- 为什么选择这个结构？
- 如何平衡美观和实用？
- 如果需求变化怎么办？

失去理论的后果：

场景1：原作者离职

代码还在：但新人看不懂为什么这样写
修改困难：不敢动，怕破坏隐含假设
质量下降：新加的代码与原设计理念冲突

场景2：多年后维护

自己写的代码：过几年都看不懂
原因：理论丢失了
重新建构：需要重新理解问题域

Naur的解决方案：

理论不能脱离人：
- 不能完全用文档替代
- 文档只是辅助，理论在人脑中
团队的理论共享：
- Pair Programming：两人共同建构理论
- 代码审查：传播理论
- 导师制：老手传授理论给新手
理论的外化：
- 好的命名：反映概念模型
- 清晰架构：体现设计理念
- 文档：解释”为什么”，而非”是什么”

影响：

软件工程实践：

敏捷开发：强调团队沟通，而非文档
结对编程：共同建构理论
代码可读性：不仅能运行，还要能理解

理论连接：

心理学：程序员的认知过程
认识论：知识如何产生和传递
建构主义：学习是主动建构，而非被动接收

今天的共鸣： Naur的观点在今天看来几乎是常识，但在1985年是颠覆性的：

领域驱动设计（DDD）：强调领域模型
Clean Code运动：代码应该表达意图
知识管理：如何保留团队知识

5. 数据学与天文学背景

鲜为人知的事实：Naur最初不是学计算机的！

学术背景：

1949-1951：哥本哈根大学，学习天文学
1957年：获得天文学博士学位
研究：天体力学、观测数据处理

为什么转向计算机？

1950年代：天文学需要大量计算
接触计算机：用计算机处理观测数据
发现兴趣：计算比观星更吸引他

跨学科优势：

数学严谨性：天文学训练的精确性
数据处理：天文数据→程序数据
问题导向：科学问题需要计算工具

晚年回归：

1970-80年代：Naur重新对天文学感兴趣
数据学（Datalogy）：提出用”datalogy”替代”computer science”
- 强调数据处理，而非机器
- 计算机只是工具，数据才是本质

🌍 对世界的深远影响

编程语言设计：从艺术到科学

ALGOL的直接后代：

CPL → BCPL → B → C：Unix和C语言的祖先
Simula（1967）：第一个面向对象语言
- 继承了ALGOL的块结构
- 添加了类和对象
Pascal（1970）：Wirth设计，ALGOL的简化版
- 教学语言，影响了一代程序员
Ada（1980）：美国国防部语言，基于Pascal/ALGOL

间接影响：

JavaScript、Python、Java：虽然语法不同，但块结构、作用域、递归等概念都来自ALGOL

语言设计方法论：

形式化定义：BNF成为标准
分离语法和语义：语法用BNF，语义用自然语言或操作语义
正交性：语言特性相互独立，可自由组合

BNF的广泛应用

编译器生成：

Yacc（Yet Another Compiler Compiler）：Unix工具，输入BNF输出Parser
Bison：GNU版本的Yacc
ANTLR：现代语言工具，支持多种目标语言

协议和数据格式：

HTTP：RFC用扩展BNF定义
JSON：语法用类似BNF的符号描述
XML：DTD和Schema是BNF变体
SQL：数据库查询语言用BNF定义

理论基础：

形式语言理论：Chomsky层次结构（Type 0-3）
自动机理论：有限状态机、下推自动机与BNF的关系
编译原理课程：BNF是第一课

软件工程哲学：人的因素

“理论建构”的遗产：

敏捷宣言（2001）：

个体和交互 胜过过程和工具
工作的软件 胜过详尽的文档
与Naur的理念一致：理论在人，而非文档

极限编程（XP）：

结对编程：共同建构理论
代码集体所有权：团队共享理论
隐喻：用故事建立共同理解

领域驱动设计（DDD，Eric Evans 2003）：

通用语言（Ubiquitous Language）：团队和领域专家的共同词汇
领域模型：就是Naur所说的”理论”
上下文映射：不同子域有不同理论

现代实践：

代码审查：不仅查错误，更是传播理解
技术文档：强调”为什么”（ADR - Architecture Decision Records）
知识管理：Wiki、Confluence等工具

对计算机教育的影响

ALGOL作为教学语言：

1960-1980年代：欧洲大学普遍用ALGOL教学
《计算机程序设计艺术》（Knuth）：用ALGOL伪代码
算法书：很多用类ALGOL语言描述

编译原理：

BNF是编译原理课的核心内容
Dragon Book、Tiger Book等经典教材都用BNF

软件工程课程：

Naur的”理论建构”被纳入课程
强调沟通和理解，而非仅仅写代码

🏆 获奖理由（通俗版）

ACM官方表彰：“表彰他对定义ALGOL 60编程语言的根本贡献，这些贡献是许多后续编程语言的基础。”

更通俗的理解：

技术层面：

ALGOL 60：现代编程语言的”祖先”
- 块结构、递归、词法作用域…今天我们习以为常的特性，都源自ALGOL
BNF：编程语言的”宪法”
- 让语言可以精确定义，不再是”凭感觉”
- 编译器可以自动生成

哲学层面：

编程即理论建构：
- 程序不仅是代码，更是理解
- 程序员不仅是码农，更是思考者
- 软件维护不仅是改代码，更是重建理解

本质： Naur教会我们：

语言需要精确：BNF让语言可以被严格定义
但理解是人的：程序的真正含义在程序员心中
技术与人文的统一：计算机科学既是工程，也是认知科学

👤 个人生平与传奇

早年与教育（1928-1960）

童年：

1928年10月25日：出生于丹麦腓特烈堡
父亲是家具制造商
从小对数学和天文学感兴趣

大学时期（1947-1951）：

哥本哈根大学：学习天文学、数学、物理
成绩优异，尤其擅长数学

早期职业（1951-1957）：

1951-1953：英国剑桥大学天文台，研究助理
1953-1957：继续天文学研究，处理观测数据
接触计算机：用Cambridge EDSAC处理数据
- 发现计算比观测更吸引人

博士学位（1957）：

哥本哈根大学天文学博士
但此时已转向计算机

计算机生涯（1959-1990）

丹麦计算技术中心（1959-1969）：

助理主任
领导GIER ALGOL编译器项目
参与ALGOL 60委员会
这是他最高产的时期

哥本哈根大学（1969-1998）：

教授：计算机科学系
教授编程语言、软件工程
培养了大批丹麦计算机科学家

研究兴趣的演变：

1960年代：编程语言、编译器
1970年代：软件工程方法论
1980年代：软件工程哲学、认识论
1990年代：批判计算机科学教育

性格与风格

严谨：

天文学训练的精确性
对模糊定义零容忍
BNF就是这种严谨的体现

批判性思维：

不盲从权威
挑战主流观念
例如：批评”计算机科学”这个名称（他更喜欢”datalogy”）

跨学科视野：

天文学背景让他看问题角度不同
将哲学、心理学引入软件工程
强调人文因素

低调：

不喜欢媒体曝光
专注学术
在丹麦工作一生，很少去美国

特立独行：

晚年：对计算机科学现状批评严厉
认为计算机教育过于技术化，忽视思维训练
质疑形式化方法的过度承诺

晚年与逝世（1998-2016）

退休（1998）：

从哥本哈根大学退休，70岁
但仍活跃于学术讨论

兴趣转向：

重新对天文学感兴趣
批判计算机科学教育
写作哲学性质的文章

图灵奖（2005）：

77岁获奖
迟来的认可（比贡献晚了45年）
获奖演讲：强调人的理解重于形式系统

2016年1月3日：

在家中去世，享年87岁
身后留下的不仅是技术，更是思想

个人轶事

命名争议：

Backus-Naur Form：Naur自己更愿意称为”Backus Normal Form”
他认为Backus贡献更大，自己只是改进
但历史记住了两人的名字

与Dijkstra的友谊：

两人是ALGOL 60委员会同事
都强调程序的数学性质
Dijkstra：结构化编程
Naur：理论建构
互相尊重但风格不同

对形式化方法的批评：

1990年代：Naur批评形式化验证的过度承诺
认为：形式化只是工具，不能替代人的理解
引发争议，但坚持观点

💭 为什么他值得纪念？

1. 他让编程语言变得可定义

之前：

语言定义靠自然语言，模糊
不同编译器实现不一致
程序员互相看不懂对方的代码

之后：

BNF提供精确工具
语言可以数学化研究
编译器可以自动生成

影响：今天任何新语言都用BNF或其变体定义，这是Naur的遗产。

2. 他设计了现代语言的”基因”

ALGOL 60的特性：

块结构
词法作用域
递归
过程参数

这些特性：

C继承→影响Unix、Linux、操作系统
Simula继承→影响面向对象编程
Pascal继承→影响教学和Delphi
几乎所有现代语言都有这些特性

DNA效应：就像生物进化中的基因，ALGOL的”基因”遍布今天所有语言。

3. 他揭示了软件的”软”在哪里

传统观念：

软件=代码
硬件=机器

Naur的洞见：

软件的”软”不在于可以修改代码
而在于人的理解可以改变
代码只是理解的外化

深刻性：

解释了为什么软件难以维护
解释了为什么文档不够
解释了为什么团队协作困难

今天的共鸣：

敏捷：强调人的交流
DDD：强调领域模型（就是”理论”）
DevOps：强调文化，而非仅仅工具

4. 他是”哲学家程序员”

罕见的结合：

大多数程序员：关注技术细节
大多数哲学家：不懂技术
Naur：既是顶尖技术专家，又是深刻思想家

贡献：

将认识论引入软件工程
将心理学引入程序设计
让计算机科学不仅是工程，也是人文学科

遗产：提醒我们：

编程是思考，不仅是敲代码
程序员是知识工作者，不仅是技术工人
软件开发是创造性活动，不仅是机械流程

🔍 技术深度：BNF与形式语言理论

BNF的数学基础

Chomsky层次结构（1956）：语言学家Noam Chomsky提出四类文法：

类型	名称	识别机器	例子
Type-0	无限制文法	图灵机	自然语言
Type-1	上下文相关文法	线性有界自动机	{a^n b^n c^n}
Type-2	上下文无关文法	下推自动机	大多数编程语言
Type-3	正则文法	有限状态机	正则表达式

BNF表达的是Type-2（上下文无关文法）：

上下文无关：产生式左边只有一个非终结符
适合编程语言：大多数语法可以表达
可自动分析：可以构造Parser

从BNF到Parser

LL(k) Parser：

Left-to-right扫描，Leftmost推导，k个前看符号
递归下降：每个非终结符对应一个函数
手写容易：很多编译器手写递归下降Parser

LR(k) Parser：

Left-to-right扫描，Rightmost推导，k个前看符号
移入-规约：使用栈和状态机
自动生成：Yacc、Bison等工具

例子：算术表达式的递归下降Parser：

def expression():
    result = term()
    while current_token in ['+', '-']:
        op = current_token
        next_token()
        right = term()
        result = apply_op(result, op, right)
    return result

def term():
    result = factor()
    while current_token in ['*', '/']:
        op = current_token
        next_token()
        right = factor()
        result = apply_op(result, op, right)
    return result

def factor():
    if current_token.isdigit():
        result = int(current_token)
        next_token()
        return result
    elif current_token == '(':
        next_token()
        result = expression()
        expect(')')
        return result
    else:
        error("Unexpected token")

EBNF：扩展BNF

增强的表示能力：

可选：[...]

if_stmt ::= "if" condition "then" statement ["else" statement]

重复：{...}
```
digit_sequence ::= digit {digit}
```
分组：(...)
```
term ::= factor (("*" | "/") factor)*
```

优点：

更简洁
更接近自然思维

今天的应用：

ISO标准：很多用EBNF
W3C规范：XML、HTML用类似符号

🧪 实践意义：从理论到实践

对编译器开发者

BNF的实用性：

设计语言：先写BNF，再实现
沟通工具：团队对语法的共同理解
自动生成：用工具（Yacc、ANTLR）从BNF生成Parser
文档：语言规范必须包含BNF

例子：JSON的BNF：

value ::= object | array | string | number | "true" | "false" | "null"
object ::= "{" [member {"," member}] "}"
member ::= string ":" value
array ::= "[" [value {"," value}] "]"
string ::= '"' characters '"'
number ::= integer [fraction] [exponent]

对软件架构师

“理论建构”的实践：

领域建模：
- 不是直接写代码
- 先理解问题域
- 建立概念模型
- 代码是模型的实现
通用语言：
- 团队、客户、开发者用同一套词汇
- 代码中的类名、方法名反映领域概念
- 避免技术术语污染业务逻辑
知识传播：
- 结对：新人和老手一起工作
- 代码审查：不仅查错，更传递理解
- 文档：记录设计决策的”为什么”
演进式设计：
- 理论随着理解深入而演进
- 重构：不仅改代码，更是精化理论
- 持续学习：团队共同建构更好的理论

对软件工程师

日常实践：

命名：
- 好的命名体现理论
- calculate_total_price()比calc()好
- 揭示意图，而非仅仅实现
注释：
- 不要写”做什么”（代码已经说了）
- 写”为什么”（理论的外化）
- 例如：
```
# 使用两倍缓冲区大小，避免频繁扩容
buffer_size = initial_size * 2
```
代码组织：
- 模块划分反映概念边界
- 文件结构体现领域结构
- 不仅是技术分层，更是概念分层
维护他人代码：
- 先理解原作者的理论
- 阅读代码、文档、提交历史
- 问”为什么这样设计？”
- 不要轻易推翻，除非你的理论确实更好

📚 延伸阅读

书籍

Naur的著作：

“Programming as Theory Building” (1985)
- 短文但影响深远，必读
“Computing: A Human Activity” (1992)
- 论文集，涵盖编程哲学、教育、认识论

编程语言：

“Revised Report on the Algorithmic Language ALGOL 60” (1963)
- 历史文献，Naur主编
“Programming Languages: Design and Implementation” (Terrence Pratt)
- 系统介绍ALGOL及其影响

编译原理：

《编译原理》（龙书） (Aho, Lam, Sethi, Ullman)
- 编译器经典，BNF是基础
《程序设计语言：实践之路》 (Michael Scott)
- 从ALGOL到现代语言的演化

软件工程哲学：

《领域驱动设计》 (Eric Evans)
- 与Naur”理论建构”理念高度共鸣
《代码整洁之道》 (Robert Martin)
- 强调代码可读性，体现理解的重要性

论文

Naur的关键论文：

“The European Side of the Last Phase of the Development of ALGOL 60” (1978)
- 回忆ALGOL 60的设计过程
“Formalization in Program Development” (1982)
- 批评过度形式化
“Proof of Algorithms by General Snapshots” (1966)
- 程序验证的早期工作

相关论文：

John Backus: “The Syntax and Semantics of the Proposed International Algebraic Language” (1959)
- BNF的起源

在线资源

ACM图灵奖页面：Naur的获奖演讲视频
ALGOL 60 Report：可在线阅读的历史文献
“Programming as Theory Building”：很多网站提供免费PDF

🌟 精神遗产

精确与人文的统一

Naur的双重性：

技术精确：BNF体现了数学严谨性
人文关怀：“理论建构”强调人的理解

这不是矛盾：

语言需要精确定义（BNF）
但程序的意义在人心中（理论）
技术是手段，理解才是目的

”为什么”比”是什么”更重要

Naur的教导：

代码告诉你”是什么”
理论告诉你”为什么”
后者更难传递，但更重要

实践：

代码审查：不仅查语法，更查理解
文档：记录决策的理由
教育：不仅教语法，更教思维

跨学科的力量

Naur的背景：

天文学→计算机科学
技术→哲学

启示：

最深刻的洞见往往来自跨界
计算机科学不应孤立
与数学、哲学、心理学、语言学对话

总结语：Peter Naur是一位罕见的”双重贡献者”——既在技术上奠定了编程语言的形式化基础（ALGOL 60和BNF），又在哲学上揭示了软件开发的本质（理论建构）。

他教会我们：程序不仅是代码，更是理解；编程不仅是敲键盘，更是建构心智模型；软件工程不仅是技术学科，更是认知科学。从1960年的ALGOL 60到1985年的”理论建构”，Naur用25年时间完成了从技术到哲学的升华。

当你写BNF定义语言，你在使用Naur的工具；当你努力理解代码的”为什么”，你在实践Naur的哲学。这位丹麦学者留给我们的，不仅是技术遗产，更是思想启迪——提醒我们永远不要忘记：计算机是为人服务的，程序是人的创造，理解是一切的基础。

最后更新: 2024年12月 本文为图灵奖系列文章,旨在以通俗方式介绍计算机科学先驱的贡献