Concurrent Clean：从图重写中间语言到并发函数式编程

1984年，荷兰并行归约机项目开始了后来形成Clean的工作。阿姆斯特丹、乌得勒支与奈梅亨大学参与这一项目，奈梅亨团队关注图归约的理论以及它在顺序、并行机器上的实现。研究者希望有一种中间语言，把上层函数式程序与不同机器体系结构连接起来，也使实现之间的比较具有共同依据。

1987年，Tom Brus、Marko van Eekelen、Maarten van Leer和Rinus Plasmeijer在波特兰的函数式编程语言与计算机体系结构会议论文集中介绍Clean。当时的Clean主要是一种实验性函数图重写语言。它与奈梅亨、东英吉利大学合作研究的LEAN关系密切，可大致看作其中面向函数式计算的子集。随后，研究者通过Concurrent Clean继续发展并发设计和编译实现。

参考：[1] [2]

Clean把正在计算的对象表示为有向图，允许多个位置引用同一节点，也允许环。程序给出重写规则：当图的一部分符合左侧模式，系统构造或连接右侧结构，重定向有关引用。这样，图的共享是语言能直接表达的语义，程序员可以用它控制计算的复用。

早期论文举出“Plus X X，X: Fac 1000”的图。两个加数都指向表示一千阶乘的同一个X；按需求值时，共享结构使这一子计算的结果可供两处使用。另一个规则“Hd (Cons a b) → a”表示取得表头：匹配由Cons构成的表后，把结果指向a，而无须为了取表头先计算整条表。默认的惰性求值与图共享因此相互配合。

参考：[1]

早期Clean编译器在运行UNIX BSD 4.2的VAX/750上开发，既是语言实现，也是检验定义的试验台。运行系统在堆中存图，并使用栈辅助执行。频繁建立节点会增加时间和存储开销，团队因此研究严格性分析：如果确定某个参数总会被用到，就可以提前求值，并在适当情况下减少堆中的结构分配。

到1990年，编译流程采用ABC抽象机作为中间层：Clean先变成机器无关的ABC代码，再由不同后端解释执行或生成目标代码。John van Groningen在奈梅亨完成硕士研究，为Macintosh II的MC68020处理器及MC68881浮点协处理器实现代码生成器。他把指令分为基本块，分析共享子表达式、安排寄存器和执行次序，最后生成可连接的目标文件。这让同一前端可以服务不同机器，而优化工作仍需顾及具体处理器。

参考：[1] [3]

1991年，Eric Nöcker、Sjaak Smetsers、van Eekelen与Plasmeijer发表《Concurrent Clean》。其中既有多态类型系统，也有控制求值的标注；程序员可以局部把惰性求值改为严格求值，还能规定图的哪些部分由不同进程处理。进程之间按需要传递值或有待计算的表达式，避免一开始就复制所有内容。

论文的素数筛例子把进程接成流水线。生成器送出大于一的整数，第一个筛保留素数二，过滤其倍数；下一个筛保留三，再继续过滤。后续筛随着数据流建立，打印进程收集各筛的素数。这展示了语言如何表达相互连接的并发活动。当时的实现仍在推进：作者报告Macintosh II、Sun3代码生成器已经工作，但拟用于六十四个Transputer的并行实现当时只支持单个Transputer上的多进程，尚未给出真实多处理器加速数据。

参考：[2]

随后的工作把注意力扩展到真实应用的输入输出和状态更新。de Hoon、Rutten与van Eekelen开发的FunSheet电子表格，复用Clean编写的符号求值器、窗口输入输出库、编辑器及帮助工具。用户既可编辑单元格，也可请求化简表达式和判断某些符号等式。唯一性类型提供了一种约束：当函数拥有某个对象的唯一引用时，可以安全地原地修改它，减少复制。

存档稿记录，这个早期应用本身约一兆字节，需要约四兆字节空闲内存，在Macintosh System 7下运行。其已有编辑、符号求值与窗口操作功能，开发者也列出了待修缺陷。它、编辑器及Concurrent Clean系统可经FTP取得，用于非商业用途。Clean由此形成了一条具体发展路径：先公开计算模型和实验实现，再完善代码生成、并发控制及交互工具；后续版本的语言便利性和库设施，是这一过程逐步增加的成果。

参考：[4]