关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷已经组成了程序设计理论和实践的惟一的珍贵源泉，无数读者都赞扬Knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到日常问题上，所有人都由于Knuth在他的书中表现出的博学、清晰、精确和高度幽默而对他无比敬仰。
　　为开始第4卷及后续各卷的写作并更新现有三卷中的部分内容，Knuth创立了称作册的一系列的小部头的书，定期出版。每一册将包含一部分或多个部分的全新的或修订的内容。最终，这些册子的内容将被归并成每卷综合的最后的版本，而在1962年开始的许多努力将得以完成。

　　第1卷　第1册
　　本册更新了《计算机程序设计艺术，第1卷，基本算法（第3版）》，并且最终将成为该书第4版的一部分。具体地说，它向程序员提供了盼望已久的MMIX——代替原来的MIX的一个以RISC为基础的计算机，并且描述了MMIX汇编语言。这一册也介绍了有关子程序、共行程序以及解释性程序的新内容。

　　（说明：http://www-cs-faculty.stanford.edu/~knuth/taocp.html包含了与本书及相关图书有关的当前信息。此外，http://www-cs-faculty.stanford.edu/~knuth/mmix.html上有可下载的软件，http://mmixmasters.sourceforge.net上有关于MMIX的信息。）

无

1. 一小捆……由比团伞花序的头状少的一个紧凑的聚伞花序组成的一个花簇。
　　2.分部出版的一本书的一部分。—P.B.戈夫（P. B. Gove），Webster誷

　　Third New International Dictionary（1961）本书是在我向着《计算机程序设计艺术》的最终版本的目标继续工作的过程中，我打算在较固定的期间里使之可以得到的一系列更新版本的头一本。
　　我这样出分册的做法是受到查尔斯·狄更斯（Charles Dickens）的启示，他就曾以序列形式出版他的小说。他在构思出比尔·希克斯（Bill Sikes）这一角色之前就出版了十几部分期连载的《奥里弗·特威斯特》（Oliver Twist）！还受到詹姆斯·默里（James Murray）的影响，他于1884年开始出版牛津英文词典的350页的部分，1888年完成字母B，而后又在1895年完成字母C。（默里于1915年在进行字母T的写作时去世；幸运的是，我的任务要比他的简单得多。）
和狄更斯与默里不同的是，我有计算机来帮助我编辑这些内容，使得我在把所有东西放在一起组成它的最后形式之前能很容易地作改动。尽管我已试图用最大努力来写出完备的内容因而不再需要作进一步的修改，但是我知道每一页都带给我几百个机会出错和遗漏重要的思想。我的文件充满了有关已被发现的优美算法的注记。但是计算机科学已经发展到这样一个水平上，我不可能指望在我希望涵盖的所有内容上我都是一个权威。因此在我能完成最后的版本之前，我需要来自读者的广泛的反馈。
　　换句话说，我想这些分册将包含大量的好材料，而我为有机会来把我已写出的每一个东西奉献给想要阅读它的任何人而感到激动不已。但我也期望，像你这样的b检测者能帮助我把它做得更好。和通常一样，我将支付2.56美元给向我报告无论是技术上的、历史上的、印刷上的或者政治上错误的头一个人。
　　查尔斯·狄更斯通常是一个月发表一次他的作品，有时一个星期一次；詹姆斯·默里倾向于大约每18个月完成350页的一个分期连载。上帝保佑，我的目标是每年写出两个128页的分册。大多数分册将作为第4卷和更高卷的新内容；但有时我也将给出对早先几卷的一个或多个的修改。例如，第4卷将需要参考属于第3卷的那些课题，但当第3卷出版时，这些内容还未被发现或发明出来。如果幸运的话，整个工作最终将兑现。
　　第1册是关于MMIX的，这是久已承诺的对于MIX的一个替代者。自从设计出MIX计算机迄今，37年已经过去，而在这些年间计算机的体系结构已经趋向于一个稍微不同风格的机器。因此，1990年时我就决定以一个新的计算机来替代MIX，它将比它的先驱者更加精简。
　　在第1卷的头三版中，习题1.3.1-25谈及所谓的MIXmaster(MIX能手)的扩充的MIX，它是同老版本向上兼容的。但是MIXmaster本身已经早就毫无希望地过时了。它允许有好几十亿个内存字节，但人们却不能以ASCII码来使用它打印出小写字母。而且，它调用子程序的标准约定也是不可改变地基于自修改指令！在1962年，十进制算术和自修改指令曾流行一时，但是随着机器变得越来越大和越来越快，它们很快就消失了。幸而，现代简化指令系统计算机(RISC)有一个非常吸引人的结构，因而我有机会来设计一种不仅时新而且有趣的计算机。
　　许多读者无疑会想：“为什么Knuth要以另一个机器来代替MIX而不是使用高级程序设计语言呢？现在几乎没有人使用汇编程序了。”这些人有权发表他们的意见，而且他们也无须劳烦地去读我的书的机器语言部分。但是我在20世纪60年代初期在第1卷前言里所写的使用机器语言的理由，到今天仍然是正确的：
　　* 我的书的主要目标之一是说明高级结构实际上是如何在机器上实现的，而不仅仅是说明如何来应用这些结构。我从基础往上，来说明共行程序链接、树结构随机数生成、高精度算术、数据包、组合查找、递归，等等。
　　* 在我的书中所需要的程序一般都很短，因而其要点可以容易地掌握。
　　* 对计算机不仅仅是心血来潮才感兴趣的读者至少应当了解一些奠基性硬件应当像什么样子，否则他们所写程序将是古怪离奇的。
　　* 如同我所描述的某些软件的输出那样，在任何情况下机器语言总是需要的。
　　* 以机器语言来表达像用于排序和查找算法的基本方法，使得在比较不同方案时有可能来对高速缓冲、RAM（随机存取内存）大小和其他硬件特征（内存速度、流水线、多个出口、朝一边看缓冲区、高速缓冲块区大小，等等）进行有意义的研究。
　　而且，如果我果真使用一种高级语言，那应该是哪一种语言呢？在20世纪60年代，我可能将选择Algol W；在70年代，我可能要使用Pascal语言来改写我的书，在80年代，我肯定把每个东西都要改成C；而到90年代，我又不得不转到C++以及大概还转到Java；而到21世纪，还有另外一种语言将肯定是生疏的。随着语言的流行和过时，重写我的书，我可没有那个时间；语言并非我的书的要点，重要之点倒是在你所喜欢的语言中你能够去做。我的书专注于不随时间流逝的真谛。
　　因此在《计算机程序设计艺术》中我将继续使用英语作为高级语言。而且我将继续使用一种低级语言来指出计算机实际上如何计算。对于只想要看看已经以一种插入方式使用一种时髦的语言做成软件包的算法的读者，应该买其他人的书。
　　一个好消息是，MMIX程序设计是令人愉快和简单的，这一册给出：
　　1) 向程序员提供的对于机器的介绍（替代第1卷第3版的1.3.1节）。
　　2) MMIX汇编语言（代替1.3.2节）。
　　3) 关于子程序、共行程序以及解释程序的新内容（代替1.4.1节、1.4.2节和1.4.3节）。
　　当然，在整个第1~3卷的现有版本中出现有MIX，因而在准备好这些卷的下一个版本之前，几十个程序要改写成MMIX的程序。我鼓励愿意来帮助做这个转换的读者参与到MMIXmasters中来，这是基于mmix masters. sourceforge. net的一个美妙的志愿者组织。
　　在第4卷和第5卷完成之前，将不会出第1卷的第4版。因此两个十分不同版本的1.3.1，1.3.2，1.4.1，1.4.2节和1.4.3节将同时共存数年，为避免可能的冲突，我暂时对新内容赋予带撇的编号1.3.1'，1.3.2'，1.4.1'，1.4.2'和1.4.3'。
　　我对于帮助我设计MMIX的所有人表示由衷的感谢。特别是，约翰·亨尼希(John Hennessy)和理查德 L. 塞特斯(Richard L.Sites)特别值得我感谢，因为他们积极的参与和实质性的贡献。还要感谢伏拉吉米尔·伊万诺维奇(Vladimir Ivanovic)，因为他自愿成为MMIX的大师/站点管理员。

D. E. K
斯坦福，加利福尼亚
1999年5月
如果你愿意，你永远能改写
—奈尔·西蒙(Neil Simon)，Rewrites: A Memoir（1996）

苏运霖：颇具盛名的计算机科学专家，出生于印度尼西亚，曾任教于吉林大学、暨南大学，现任广西大学梧州分校顾问、计算机科学系主任，学科带头人。他曾被评为全国电工学会优秀科技工作者和电机工程优秀科技工作者，获国务院特殊津贴。他还被美国纽约科学院邀请为该院院士，名字被录入《国际传记辞典》、《国际卓越领导者名单》以及《世界知识名人录》。1983年到1986年间，与新西兰的几所著名大学研究组合算法、计算机网络、Petri网络理论。1989年，他到美国访问、讲学近一年，参加分布式算法的设计并撰写了一批有创见的论文。之后，他陆续到挪威、瑞典、瑞士、丹麦、奥地利、德国、比利时、冰岛、荷兰、卢森堡、日本、新加坡、印度尼西亚和香港等国家和地区讲学与访问。曾翻译D. E. Knuth的巨著《计算机程序设计艺术》，并编写了多部教材。

炎炎酷热，淋淋汗珠，伏案疾书，机旁录字，夜以继日，乐此不疲，大功告成，释怀欣喜。当我把译稿从头至尾又校对了一遍，准备把它寄出之前，我突然感到有必要写一个序言来向读者谈一谈。
　　我是在今年6月份时才得知Donald E. Knuth以这种分册形式出版他的多卷集的新版本和新的卷的，当出版社提出让我来继续完成这些分册的翻译工作时，我欣然接受，并对出版社对我的信任深表感谢。
　　Donald E. Knuth在他的第1卷第1版的序中，就提到了他的喜忧交集的心情。一方面，他为自己的书的出版感到高兴（在那时，这还仅仅是他出的头一本书）；另一方面，又担心由于计算机科学技术的迅猛发展，而使他的书很快就过时了。他很清楚，任何一本书，特别是科学技术方面的书，再重要再经典，总有其寿命极限。
　　从那时开始，Donald E. Knuth就为使他的书保持时新而作出艰苦努力。在此后近30年间，他对第1卷到第3卷，已经进行了多次的修改充实和更新。第1卷，他已出了三版，目前的第1卷第1册，是为他最后一版即第4版做准备的。第2卷，他也已出了三版。第3卷，他已出了第2版。每一版，都不是简单地改正由读者向他提供发现的错误（为此对于每一个错误的第一个发现者，他提供2.56美元的报酬），以及他自己发现的错误，而是认真地进行新的润饰或者大的改动（他曾宣告说，他对90%的页面都作了几乎50%的修改）。因此可以说，他为使他的书保持时新，使之不至于很快过时，实在作了巨大的努力。
　　反观现在这第1卷的第1册，它有哪些新内容呢？作者在书名之下，加了“MMIX—新千年的RISC计算机”，题目本身就已告诉我们它的新颖之处了。
它有哪些值得提及的新内容呢？
　　其一，是MMIX本身。正如作者在第3版中提到的，MIX已经过时了，因此要使这套书成为时新的，就必须对贯穿于全书的MIX程序都进行全面的改造。光就1~3卷而言，这就涉及几百个大大小小的程序。要进行全部的改写，谈何容易。而且，首先的问题是新的机器应该有什么样的指令系统？作者目前提出的MMIX，真正是简化指令系统的计算机（RISC）。这些指令，既易学，易用，又完全可以同当今的计算机相媲美。甚至如作者所断言的，它还有“超前”的一些特征。作者所言，读者对于学习一种机器语言不应心存犹豫，任何一个对计算机不是心血来潮才感兴趣的人，掌握一种机器语言，是必不可少的，极为中肯。
　　其二，是MMIX汇编语言。这个汇编语言，有两个部分，一个是同MMIX的指令相对应的指令的汇编形式。另一个是MMIXAL本身，为便于使用这个汇编语言，在这方面，它确实也同原来的MIXAL有很大的不同。
　　其三，是关于子程序、共行程序以及解释性程序的新内容。这些新的内容，不仅仅是原来用MIX所写的程序，换成了用MMIX写成的程序。更重要的是，它增加了许多新的思想。仅以模拟程序为例，除了程序的修改之外，整个篇幅也发生了变化，由原来的10页增加到17页。足见，内容发生了多大变化。
　　我们从Donald E. Knuth对于他的这本专著的态度，应当向他学习什么呢？我想，至少我们应该学习这样一些方面。
　　首先是他的创新思想，Donald E. Knuth处处体现了作为一位杰出科学家的创新。他在近40年前就做出了以多卷书的形式来系统介绍计算机程序设计艺术这样的创举，是他首先建立或奠定了算法设计与分析这门学科，而后他又发明了TEX和METAFONT，使计算机用于排版和印刷上，引发了计算机排版的革命。现在以分册形式来出版专著，又是令世人为之拍案称奇的一个创举。他总是不断地开拓视野，不断地提出问题，而后又着力寻求问题的答案，在攀登科技的新高峰。
　　其次，是认真负责彻底探索的精神。我们阅读Donald E. Knuth的书，容易发现，他大量地引证国内外的文献，包括现在的和历史的，而且所涉及的也不仅仅是计算机方面的书。就以本书所引用的一些题记而言，好些来自于文学作品，老的有1945年的(图灵的语录)；新的有1998年的（布里安·克尔尼日等的语录）。而就技术本身而言，则所引用的不仅有经典的，还包括最新的成果在内。谈到这里，就不能不谈谈我们国内的一些教材。说是21世纪的教材，但是所引用的参考文献，都极为陈旧，或者连一本国外的同类书籍都没有参考，大都是把人家的东西，重新抄作一番，其内容之单薄，其创新点之贫乏，甚至是其错误之繁多，实在使人对这些书的作者们感到汗颜。如果这样也可以算是书，那可真是中国出版界的悲哀了。中国教育目前面临的大问题之一是教材内容的陈旧和粗制滥造，我们有责任呼吁我国的学界，来学一学国外这些科学家的精神，不要把写书当成为沽名钓誉的事而已。
　　第三，是他精益求精的精神。他对于自己的或别人的工作，总是希望把它们引向尽善尽美的程度，在别人看来已经是很好的结果，但他还是要去进行改进，使得它们达到更好的水平。然而，他在这样做时，又不钻牛角尖，正如他在本书的策略性考虑中所说，大概从没有一个复杂的计算机程序能做到再也不须改进了，所以不应无限次地去做所谓改进的工作。
　　由于译者水平所限，加上时间仓促，译文中有错误或不当之处，敬请读者不吝指正。

译　 者
于广西大学梧州分校
2005年12月

Chapter 1: Basic Concepts 1
1.3' MMIX 2
1.3.1' Description of MMIX 2
1.3.2' The MMIX Assembly Language 28
1.3.3' Applications to Permutations 51
1.4' Some Fundamental Programming Techniques 52
1.4.1' Subroutines 52
1.4.2' Coroutines 66
1.4.3' Interpretive Routines 73
Answers to Exercises 94
Index and Glossary 127