实现 TeX 的算法:回首编程技术的过去三十年

  • Sergio De Simone
  • 侯伯薇

2015 年 1 月 19 日

话题:函数式编程语言 & 开发架构文化 & 方法

Glenn Vanderburg是 LivingSocial 的工程主管,在最近的ClojureConj会议上,对他使用 Clojure 实现 TeX 算法的工作做了很有趣的叙述。在那个过程中,他发现在过去三十年间,编程技术已经发生了非常大的变化。

TeX 简史

首先,一些历史可能有助于说明 TeX 的重要性。Donald Knuth 在 1982 年发布了 TeX 1.0,32 年后,它仍然代表了计算机排版的先进状态,Glenn 说。此外,TeX 一直是少数几个提供了源代码的大型项目,人们可以从中学习。

TeX 是一部鸿篇巨制:它运行快速、可移植、产出优秀的结果,并且在三十年后它还在广泛使用中,只发现了很少缺陷。

Glenn 特别提到,很有趣的是,当 Knuth 收到他的巨著《计算机编程艺术》的第一页样张,就决定开始编写 TeX,因为他发现排版“丑陋得让人失望”。这样,Knuth 开始编写程序,使得他的书看起来自己能够接受。当 TeX 可用之后,因为快速排序而为人所知的Tony Hoare建议 Knuth 发布源代码,那样从此可以为学生所用,那时是 1982 年,互联网还没有出现,也没有太多源代码示例。这个目标让 Knuth 开始有了文学编程Literate Programming)的冲动,最终 TeX 的源代码在 1986 年公诸于众。直到 Linux 内核出现之前,它一直是世界上被最广泛阅读的代码,Glenn 说。

TeX 内部

TeX 架构是一个处理文本的管道,它会把文本切分成多种类型的对象,如页、段落、行、词等等,最终生成一个 DVI 文件。从 TeX 出现到现在已经有超过三十年,回顾过去,我们会惊奇的发现它仍然是非常“早期”的东西,Glenn 说。

TeX 源代码中有很多现在并不被认为是好的编程风格的例子,像:

  • 全局变量;
  • 一个字母的变量;
  • goto 语句;
  • 数百行长的过程;
  • 大量宏;
  • 重复代码;
  • 局部变量重用;
  • 到处都是单线程假设;
  • 可变性代码普遍存在

阅读这样的代码就像是在访问另一个时代 […] 在那本书出版的 1986 年,它代表了非常不错的编程方式,但很多方面现在已经过时了。

当时很多方式都是因为受到了当时可用硬件的限制,只有有限的计算能力和可用内存,据 Glenn 所说,Knuth 为了减少函数调用到最小程度做了非常大的努力,而那实在是太昂贵了。这使得 TeX 的代码库高度整合,从而“抽取出任何一个部分都无法独立使用”。

TeX 积极地使用技术来改善手动的操作,我们今天可能会真的看不起那些技术,但我们更应该仰视那些技术,因为要考虑到摩尔定律,不仅仅是那个定律,还有当时的语言实现技术。

使用 Clojure 重新实现 TeX:Cló

因此,Tex 可能并非是今天指导新手程序员的最佳示例,然而,Glenn 之所以要重新实现它,是因为它能够展示出编程技术已经发生了多大改变,并且能够提供真实的示例,说明从过程化转换到函数式语言的时候,算法会发生多大改变。

据 Glenn 所说,想要理解 TeX 代码的功能很困难,大多是因为它的简洁和极度优化,正如上面所概述的。最初,他试图让自己的设计尽可能和 TeX 保持一致。正如上面所说,Tex 严格地单线程执行,而在当今计算机领域,非常重要的一个目标就是利用已经可用的多核硬件。Clojure 非常有用的一种特性是,让他可以把 TeX 的基本管道实现为一系列函数,然后他可以替换线程宏,从而从串行执行模式转换到并行执行模式。“那让我开始做一些像比较两个苹果的工作。” Cló的实现当然要比 TeX 慢很多,但转换到并行执行带来了“巨大的收益”。

Glenn 发现另一个有趣的点是,他在某些时候不得不实现和 TeX 一样的优化。然而,不久他就意识到,那会让他无法使用在函数式语言中天然存在的非常好的抽象,从而让事情比应该的情况更加复杂。这也让他觉得不知道 TeX 的 API 受到了语言模式多么大的影响,特别是普遍的不可变性和单线程的假设。

对于 Glenn 最重要的反映来自于意识到编程技术有了多大的发展。如果我们回顾 1982 年的编程技术,就会看到:

  • 计算机运行缓慢,内存非常小;
  • 大多数程序员从未见过多核处理器,CPU 的字节和比特的大小都不一样;
  • 对于浮点算法没有 IEEE 标准;
  • 可移植性意味着要支持差不多 40 个不同的操作系统,每个都拥有不同的文件系统结构、不同的目录语法、不同的 I/O 和分配 API、字符集;
  • 不可能动态载入代码;
  • 优化编译器还是研究性项目;
  • 没有开源和免费的软件,你需要从头开始实现不可想象的基本内容、常用数据结构和流程。
  • 当版本控制可用的时候,功能还非常初级;
  • 人们还从未听说过自动化测试;
  • 今天的工具非常豪华,但也是多年来小步的改进逐渐得来的。

因此,对于我们还要继续改进编程技术的工作,Glenn 邀请大家首先享受已经存在的良好基础。

查看英文原文:Implementing TeX's Algorithms: Looking Back at Thirty Years of Programming

函数式编程语言 & 开发架构文化 & 方法