计算机程序设计艺术：第1卷 第1册（双语版）MMIX：新千年的RISC计算机

　　这第1分册更新了《计算机程序设计艺术，第1卷，第3版：基本算法》，并且最终将成为该书第4版的一部分。具体地说，它向程序员提供了盼望已久的mmix——代替原来的mix的一个以risc为基础的计算机，并且描述了mmix汇编语言。这一分册也介绍了有关子程序、共行程序以及解释性程序的新内容。.
　　 关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷已经组成了程序设计理论和实践的惟一的和珍贵的源泉，无数读者都赞扬knuth的著作对个人的深远影响。科学家们为他的分析的美丽和优雅所惊叹，而从事实践的程序员们已经成功地应用他的“菜谱式”的解到他们每天的问题上，所有人都由于knuth在他的书中表现的博学、清晰、精确和高度幽默而对他无比敬仰。...
　　 为开始这三卷的第四也是最后一版，更新现有三卷中的部分内容，knuth已经创立了称作分册的一序列的小部头的书，定期出版。每个分册将包含整个新的或修改内容的一部分或多个部分。最终，这些分册的内容将被归并成每卷最后的版本，而在1962年开始的许多努力终将完成。 ...

chapterlbasicconcepts
1．3 mmix.
1．3．1 descriptionofmmix
1．3. 2 themmixassembly
language
1．3．3 applicationsto
permutations
1．4 somefundamentalprogramming
techniques
1．4．1subroutines
1．4．2 coroutines
1．4．3 interpretiveroutines
answerstoexercises
第重章基本概念
1．3 mmix
1．3．1 mmix概述
1．3．2 mmix汇编语言
1．3．3 在排列中的应用
1．4，某些基本的程序设计技术
1．4．1 子程序

　　炎炎酷热，淋淋汗珠，伏案疾书，机旁录字，夜以继日，乐此不疲，大功告成，释怀欣喜。当我把译稿从头至尾又校对了一遍，准备把它寄出之前，我突然感到有必要写一点东西来向读者谈一谈。.
　　 我于2005年6月份时才得知，Donald E. Knuth以这种分册形式出版他的多卷集的新版本和新的卷，当出版社提出让我来继续完成这些分册的翻译工作时，我欣然接受，并对出版社的信任深表感谢。 Donald E. Knuth在他的第1卷第1版的序中，就提到了他的喜忧交集的心理。一方面，他为自己的书的出版感到高兴（在那时，这还仅仅是他出的头一本书）；另一方面，又担心由于计算机科学技术的迅猛发展，而使他的书很快就过时了。他很清楚，任何一本书，特别是科学技术方面的书，再重要再经典，总有其寿命极限。 从那时开始，Donald E. Knuth就为使他的书保持时新而做出艰苦努力。在此后近30年间，他对第1卷到第3卷，已经做了多次的修改和更新。第1卷，他已出了3版，目前的第1卷第1册，是为他最后一版即第4版做准备的。第3卷，他已出了第2版。每一版都不是简单地改正由读者向他提供发现的错误（为此对于每一个错误的第一个发现者，他提供2.56美元的报酬），以及他自己发现的错误，而是认真地进行新的润饰或者大的改动（他曾宣告说，他对90%的页面都做了几乎50%的修改）。因此可以说，Knuth为使他的书保持时新，使之不至于很快过时，实在做了巨大的努力。.. 反观现在这第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世纪的教材，但是所引用的参考文献都极为陈旧，或者连一本国外的同类书籍都没有参考。再就是把人家的东西重新抄作一番，其内容的单薄，其创新点之贫乏，甚至是其错误之繁多，实在令人汗颜。如果这样也可以算是书，那可真是中国出版界的悲哀了。中国教育目前面临的大问题之一是教材内容的陈旧和粗制滥造，我们有责任呼吁我国的学界，来学一学国外这些科学家的精神，不要把写书当成为沽名钓誉的事。 第三，是他精益求精的精神。他对于自己的或别人的工作，总是希望把它们引向尽善尽美的程度，在别人看来已经是很好的结果，但他还是要去进行改进，使得它们达到更好的水平。然而，他在这样做时，又不钻牛角尖，正如他在本书的策略性考虑中所说，大概从没有一个复杂的计算机程序能做到再也不须改进了，所以不应无限次地去做所谓改进的工作。 因此，我想，我们出版高德纳的书，其深远意义也应包括这些。而不仅仅在于计算机的那些算法本身上。我们等待着祖国科学辉煌的明天。 相关信息： 《计算机程序设计艺术》新版：关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷（第三版）已经组成了程序设计理论和实践的惟一的珍贵源泉，无数读者都赞扬Knuth的著作深远影响。 您现在读到的是Donald E.Knuth以分册形式出版的《计算机程序设计艺术》的全新第4版。包括对前3卷的更新按分册出版以及全新按分册推出的第4卷。 第1卷的第1分册更新了第1卷的第一部分内容。第4卷的2、3、4分册都是全新的。其他的分册作者也将陆续写完。 双语版:华章此次推出的双语版是英文版和中文翻译版的合集。双语版的前半部分是原著的英文影印版，后半部分是国内计算机专家苏云霖老师的译著。我们力图通过这种形式为读者提供权威的、完整的、便于参考查阅的、性价比更高的经典图书。 Donald E. Knuth：算法和程序设计技术的先驱者，计算机排版系统TEX和METAFONT的发明者，他因这些成就和大量富于创造力和影响深远的论著而誉满全球。作为斯坦福大学计算机程序设计艺术的荣誉退休教授，他当前正全神贯注于完成其关于计算机科学的史诗性的七卷集。（http://www-cs-faculty.stanford.edu/~knuth/taocp.html包含了与本书及相关图书有关的当前信息。） 苏运霖：国内外颇具盛名的计算机科学家，现为广西大学梧州分校计算机科学系主任、博士生导师。他曾获广东省科协优秀科技工作者称号，享受国务院特殊津贴，还曾被选为全国电工学会优秀科技工作者和电机工程优秀科技工作者。他还被美国纽约科学院邀请为该院院士，并入选美国国际传记中心出版的《国际传记辞典》以及英国国际传记中心出版的《世界知识名人录》。...

　　fascile 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，（默里在进行字母T的写作时于1915年去世；幸运的是，我的任务要比他的简单得多）。
　　和狄更斯与默里不同的是，我有计算机来帮助我编辑这些内容，使得我在把所有东西放在一起组成它的最后形式之前能很容易地作改动。尽管我已试图作最大努力来写出完备的内容因而不再需要作进一步的修改，但是我知道每一页都带给我几百个机会出错和遗漏重要的思想。我的文件充满了有关已被发现的优美算法的注记。但是计算机科学已经发展到这样一个水平上，我不可能指望在我希望涵盖的所有内容上我都是一个权威。因此在我能完成最后的版本之前，我需要来自读者的广泛的反馈。
　　换句话说，我想这些分册将包含大量的好材料，而我为有机会来把我已写出的每一个东西奉献给想要阅读它的任何人而感到激动不已。但我也期望，像你这样的β检测者能帮助我把它做得更好。和通常一样，我将支付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而不执著于一个高级程序设计语言？现在几乎没有人使用汇编程序了。”这些人有权发表他们的意见，而且他们也无须劳烦地去读我的书的机器语言部分。但是我在1960年代初期在我第1卷前言里所写的使用机器语言的理由，到今天仍然是正确的。
　　· 我的书的主要目标之一是说明高级结构实际上是如何在机器上实现的，而不仅仅是说明如何来应用这些结构。我从基础往上，来说明共行程序链接，树结构，数据包，组合查找，递归。等等。
　　· 在我的书中所需要的程序一般地都很短，因而其要点可以容易地掌握。
　　· 对计算机不仅仅是偶而地感兴趣的读者至少应当有奠基性硬件应当像什么样子的一些想法。否则他们所写程序将是古怪离奇的。
　　· 如同我所描述的某些软件的输出那样，在任何情况下机器语言总是需要的。
　　· 以机器语言来表达像对于排序和查找算法的基本方法，使得在比较不同方案时有可能来进行对于高速缓冲，RAM（随机存取内存）大小和其它硬件特征（内存速度、流水线、多个出口、朝一边看缓冲区、高速缓冲块区大小，等等）进行有意义的研究。
　　而且，如果我果真使用一种高级语言，那它应该是哪一个语言呢？在1960年，我可能将选择Algol W；在70年代，我可能要使用Pascal语言来改写我的书，在80年代，我肯定把每个东西都要改成C；而到90年代，我又不得不转到C++以及大概还转到Java；而到2000年，还有另外一种语言将肯定是生疏。随着语言的流行和过时，重写我的书，我可没有那个时间；语言并非我的书的要点，重要之点倒是在你所喜欢的语言中你能够去做。我的书专注于不随时间流逝的真谛。
　　因此在计算机程序设计艺术中我将继续使用英语作为高级语言。而且我将继续使用一种低级语言来指出计算机实际上如何计算。对于只想要看看已经以一种插入或方式使用一种时髦的语言做成软件包的算法，应该买其他人的书。
　　关于MMIX程序设计的好消息是令人愉快和简单的，这一分册给出：