前言
Foreword
教育家、将军、营养师、心理学家和家长“编程”，军队，学生以及一些组织“被编程”。向大问题发起进攻需要引入一系列程序，而它们中的大部分是在半路上冒出来的。这些程序里充斥着似乎只为当前难题所特有的问题。要想把编程本身作为一种智力劳动去欣赏，你就必须开始编程；你必须阅读和编写很多计算机程序。程序关于什么以及它们服务于哪些应用程序并不很重要，重要的是它们运行得有多好，以及在创造更伟大程序的过程中它们和其他程序结合得有多平滑。因此，程序员必须同时追求部件的完美性和收集的充分性。本书中所用的“程序”注重对于那些以Lisp的一种方言写成、用于在数字计算机上执行的程序的创造、执行和研究。通过使用Lisp语言，我们所局限的并非是我们可以编的程，而只是用于描述程序的记号。
Educators, generals, dieticians, psychologists, and parents program. Armies, students, and some societies are programmed. An assault on large problems employs a succession of programs, most of which spring into existence en route. These programs are rife with issues that appear to be particular to the problem at hand. To appreciate programming as an intellectual activity in its own right you must turn to computer programming; you must read and write computer programs -- many of them. It doesn't matter much what the programs are about or what applications they serve. What does matter is how well they perform and how smoothly they fit with other programs in the creation of still greater programs. The programmer must seek both perfection of part and adequacy of collection. In this book the use of ''program'' is focused on the creation, execution, and study of programs written in a dialect of Lisp for execution on a digital computer. Using Lisp we restrict or limit not what we may program, but only the notation for our program descriptions.
通过传达本书的主题，我们把重点放在三件事物上：人的思维、计算机程序的集合和计算机。每段计算机程序都是一个在人脑中酝酿出的、属于真实思维流程的模型。这些从人的经验和思想中产生的流程数量庞大、细节错综复杂、且永远只有一部分能被领会。我们的计算机程序对它们建立的模型很难使我们始终保持满意。因此，即使我们的程序是精心打造的分立符号的集合、互锁函数的嵌合体，它们也会不断演变：随着我们深化、扩展、推广对模型的认识，我们对它们进行修改，直到模型最终达到亚稳态，但它仍处在另一个我们所纠结的模型内。编程的快乐源于不断在脑中和在计算机上揭示以程序表示的机理，以及它们产生时爆发出的认识。如果说艺术能解释我们的梦，计算机就能化为程序执行它们！
Our traffic with the subject matter of this book involves us with three foci of phenomena: the human mind, collections of computer programs, and the computer. Every computer program is a model, hatched in the mind, of a real or mental process. These processes, arising from human experience and thought, are huge in number, intricate in detail, and at any time only partially understood. They are modeled to our permanent satisfaction rarely by our computer programs. Thus even though our programs are carefully handcrafted discrete collections of symbols, mosaics of interlocking functions, they continually evolve: we change them as our perception of the model deepens, enlarges, generalizes until the model ultimately attains a metastable place within still another model with which we struggle. The source of the exhilaration associated with computer programming is the continual unfolding within the mind and on the computer of mechanisms expressed as programs and the explosion of perception they generate. If art interprets our dreams, the computer executes them in the guise of programs!
尽管它的能力十分强大，计算机还是一位严苛任务布置者。交给它的程序必须完全正确，而且我们想要告诉它的事情必须被事无巨细地交代准确。和其他一切符号化的活动一样，我们通过论证确信程序中的真理。Lisp语言本身可以被赋予语义（顺便提一句，这又是一个模型），而如果可以明确说明一段程序的功能，比如在谓词演算中，逻辑的证法就可以被用于提出一段令人满意的正确性论证。然而不幸的是，随着程序变大、变复杂——它们几乎总是会发生这样的变化——说明本身的充分性、一致性和正确性就会变得值得质疑。因此，大型程序很少伴有完整、正规的正确性论证。既然大程序都是由小程序发展而成的，开发一个我们已经确定其正确性的标准程序结构的装备库，也就是所谓的习语，并学会使用具有确证价值的组织技巧将它们合并到更大的结构中，就是至关重要的。本书详细阐释了这些技巧。掌握这些技巧对于参与到编程这样一项普罗米修斯式的伟大事业中是必不可少的。揭示和精通强大组织技巧比其他任何东西都更能促进我们创造大型的、具有重大意义的程序的能力。反过来，由于编写大型程序的任务十分繁重，我们被激励着去发明减少功能和细节的混乱度，以便使它们能更好地和大型程序相适应的新手段。
For all its power, the computer is a harsh taskmaster. Its programs must be correct, and what we wish to say must be said accurately in every detail. As in every other symbolic activity, we become convinced of program truth through argument. Lisp itself can be assigned a semantics (another model, by the way), and if a program's function can be specified, say, in the predicate calculus, the proof methods of logic can be used to make an acceptable correctness argument. Unfortunately, as programs get large and complicated, as they almost always do, the adequacy, consistency, and correctness of the specifications themselves become open to doubt, so that complete formal arguments of correctness seldom accompany large programs. Since large programs grow from small ones, it is crucial that we develop an arsenal of standard program structures of whose correctness we have become sure -- we call them idioms -- and learn to combine them into larger structures using organizational techniques of proven value. These techniques are treated at length in this book, and understanding them is essential to participation in the Promethean enterprise called programming. More than anything else, the uncovering and mastery of powerful organizational techniques accelerates our ability to create large, significant programs. Conversely, since writing large programs is very taxing, we are stimulated to invent new methods of reducing the mass of function and detail to be fitted into large programs.
和程序不同，计算机必须服从物理规律。如果它们想运行得更迅速，例如每次状态改变只花几纳秒，它们就必须在很短的距离（最多$$1\frac{1}{2}$$英尺）内传递电子。由大量装置释放出的热量聚集在空间内，必须被消除。有一种精巧的工程艺术可以平衡功能的多样性和装置的密度。在任何情况下，硬件总是比那些我们愿意去编程的东西更原始。将我们的Lisp程序转化成“机器”程序的流程本身就是我们对其编程的抽象模型。研究和创造它们能提供很多对于有关为任意模型编程的组织性程序的认识。当然，计算机本身也可以被建模。想想看：最小物理开关元件的行为利用量子物理建模，量子物理学由微分方程式描述，微分方程式的详细行为藉由数值近似获得，数值近似在计算机程序中被表示，计算机程序在计算机上运行，而计算机又是由……！
Unlike programs, computers must obey the laws of physics. If they wish to perform rapidly -- a few nanoseconds per state change -- they must transmit electrons only small distances (at most 1 1/2 feet). The heat generated by the huge number of devices so concentrated in space has to be removed. An exquisite engineering art has been developed balancing between multiplicity of function and density of devices. In any event, hardware always operates at a level more primitive than that at which we care to program. The processes that transform our Lisp programs to ''machine'' programs are themselves abstract models which we program. Their study and creation give a great deal of insight into the organizational programs associated with programming arbitrary models. Of course the computer itself can be so modeled. Think of it: the behavior of the smallest physical switching element is modeled by quantum mechanics described by differential equations whose detailed behavior is captured by numerical approximations represented in computer programs executing on computers composed of ...!
区分看待三个重点并不仅仅是为了战术上的便利。即便如他们所说，一切都在头脑中，这样的逻辑分隔能增进这三个重点间的符号化交流，而根据人的经验，这三个重点的丰富性、生命力和潜能只有生命的进化本身能超越。这些重点之间的关系最多只是亚稳态的。计算机永远不够大、不够快。硬件技术的每个突破都会产生更多的大规模编程项目和新型组织原则，同时丰富抽象模型。每位读者都应该定期问自己“向着哪儿，向着哪儿？”——但也不要问得太频繁，以免你因为想不明白这令人喜忧参半的哲学问题而失去编程的乐趣。
It is not merely a matter of tactical convenience to separately identify the three foci. Even though, as they say, it's all in the head, this logical separation induces an acceleration of symbolic traffic between these foci whose richness, vitality, and potential is exceeded in human experience only by the evolution of life itself. At best, relationships between the foci are metastable. The computers are never large enough or fast enough. Each breakthrough in hardware technology leads to more massive programming enterprises, new organizational principles, and an enrichment of abstract models. Every reader should ask himself periodically ''Toward what end, toward what end?'' -- but do not ask it too often lest you pass up the fun of programming for the constipation of bittersweet philosophy.
我们写的程序中里，有一些（但它们的数量永远不够）发挥精确的数学上的作用，比如排序、找数列最大项、判断素性、开根号。我们把这些程序成称为算法。很多算法以它们的最优行为而闻名，尤其是考虑运行时间和存储需求这两个重要参数时。程序员应该具有优质的算法和习语。即使有些程序很难被精确描述，但程序员依然有义务评估，并一直试图优化，它们的性能。
Among the programs we write, some (but never enough) perform a precise mathematical function such as sorting or finding the maximum of a sequence of numbers, determining primality, or finding the square root. We call such programs algorithms, and a great deal is known of their optimal behavior, particularly with respect to the two important parameters of execution time and data storage requirements. A programmer should acquire good algorithms and idioms. Even though some programs resist precise specifications, it is the responsibility of the programmer to estimate, and always to attempt to improve, their performance.
Lisp语言在被使用了大约四分之一个世纪之后幸存了下来。活跃的编程语言中只有Fortran语言比它存在得更久一些。两种语言都为重要应用领域中的编程需求提供了支持：Fortran支持科学和工程计算，而Lisp支持人工智能。这两个领域一如既往得重要，从事它们的程序员也是如此执着于这两种语言，以至于Lisp和Fortran在另四分之一个世纪中也许还会被处于使用中。
Lisp is a survivor, having been in use for about a quarter of a century. Among the active programming languages only Fortran has had a longer life. Both languages have supported the programming needs of important areas of application, Fortran for scientific and engineering computation and Lisp for artificial intelligence. These two areas continue to be important, and their programmers are so devoted to these two languages that Lisp and Fortran may well continue in active use for at least another quarter-century.
Lisp是变化的。文中使用的Scheme方言由最初的Lisp演变而来，并在几个重要的方面不同于后者，包括变量绑定的静态作用域以及允许函数将函数作为值产生。就语义结构而言，Scheme和Algol 60的相似程度和早期Lisp一样。虽然Algol 60再也没有成为活跃编程语言，但它仍继续活在Scheme和Pascal的基因中。两种语言所沟通的文化比聚集在这两种语言周围的东西差异更大，这是很难得的。Pascal是用来建金字塔的，那是由大军把大石块推到位而建成的壮观而令人惊叹的静态结构；Lisp是用来搭有机体的，那是由小队把无数脉动的简单有机物安放好而搭成的壮观而令人惊叹的动态结构。这两种语言的组织原则是相通的，除了一个极重要的不同：交到一个Lisp程序员手上的可自主决定、导出的功能比在Pascal项目中能找到的多出不止一个数量级。Lisp程序往库里塞满了工具程序数量超过了产生它们的应用程序的函数。工具程序的增长在很大程度上是由链表这一Lisp的原生数据结构导致的。链表的简单结构和自然适用性体现在那些非特异程度令人惊奇的函数中。在Pascal中，过量的可声明数据结构会在禁止或惩罚随意合作的函数中引起特化。因此，金字塔必须千年不变，而有机体则要么演化，要么灭亡。
Lisp changes. The Scheme dialect used in this text has evolved from the original Lisp and differs from the latter in several important ways, including static scoping for variable binding and permitting functions to yield functions as values. In its semantic structure Scheme is as closely akin to Algol 60 as to early Lisps. Algol 60, never to be an active language again, lives on in the genes of Scheme and Pascal. It would be difficult to find two languages that are the communicating coin of two more different cultures than those gathered around these two languages. Pascal is for building pyramids -- imposing, breathtaking, static structures built by armies pushing heavy blocks into place. Lisp is for building organisms -- imposing, breathtaking, dynamic structures built by squads fitting fluctuating myriads of simpler organisms into place. The organizing principles used are the same in both cases, except for one extraordinarily important difference: The discretionary exportable functionality entrusted to the individual Lisp programmer is more than an order of magnitude greater than that to be found within Pascal enterprises. Lisp programs inflate libraries with functions whose utility transcends the application that produced them. The list, Lisp's native data structure, is largely responsible for such growth of utility. The simple structure and natural applicability of lists are reflected in functions that are amazingly nonidiosyncratic. In Pascal the plethora of declarable data structures induces a specialization within functions that inhibits and penalizes casual cooperation. It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures. As a result the pyramid must stand unchanged for a millennium; the organism must evolve or perish.
为了说明这一区别，我们可以把本书对待内容和练习的方式和任何使用Pascal的基础课本做比较。不要产生这是一本只有在MIT、在那里独特的教学方式下才能被理解消化的课本的错觉。这正是一本严肃的关于Lisp编程的书该有的样子，无论它的学生是谁，以及在哪里被教授。
To illustrate this difference, compare the treatment of material and exercises within this book with that in any first-course text using Pascal. Do not labor under the illusion that this is a text digestible at MIT only, peculiar to the breed found there. It is precisely what a serious book on programming Lisp must be, no matter who the student is or where it is used.
请注意，和其他大部分用于为人工智能领域的工作做准备的Lisp书籍不同，这是一本关于编程的课本。总之，随着我们放宽视野，软件工程和人工智能对编程的核心关注点开始趋于一致。这就解释了为什么在人工智能领域外对于Lisp的兴趣增长得那么快。
Note that this is a text about programming, unlike most Lisp books, which are used as a preparation for work in artificial intelligence. After all, the critical programming concerns of software engineering and artificial intelligence tend to coalesce as the systems under investigation become larger. This explains why there is such growing interest in Lisp outside of artificial intelligence.
正如人们从其目标中所期望的那样，人工智能领域的研究产生了很多具有重大意义的编程问题。在其他的编程文化中，这种一连串的问题会产生出新的语言。事实上，通过发明新语言对任务模块间的交流进行控制和分隔就是一种适用于任何庞杂的编程任务的有用组织原则。随着这些语言离人们日常交互得最多的系统的边界越来越近，它们具有变得更不原始的倾向。于是，这样的系统就包含了复制了许多次的复杂的语言处理函数。Lisp的语法和语义简单到语法分析可以被视为一项基本的任务。因此，语法分析技术在Lisp编程的地位无足轻重，语言处理器的构造也很少成为大型Lisp系统发展和变化的障碍。最后，正是这语法和语义的简单性给了所有Lisp程序员以负担和自由。如果不让程序充满任意函数，没有一个大小超过几行的Lisp程序可以被写出来。发明，然后适应；适应了以后再重新发明！我们向那些把思想放进嵌套括号中Lisp程序员致敬。
As one would expect from its goals, artificial intelligence research generates many significant programming problems. In other programming cultures this spate of problems spawns new languages. Indeed, in any very large programming task a useful organizing principle is to control and isolate traffic within the task modules via the invention of language. These languages tend to become less primitive as one approaches the boundaries of the system where we humans interact most often. As a result, such systems contain complex language-processing functions replicated many times. Lisp has such a simple syntax and semantics that parsing can be treated as an elementary task. Thus parsing technology plays almost no role in Lisp programs, and the construction of language processors is rarely an impediment to the rate of growth and change of large Lisp systems. Finally, it is this very simplicity of syntax and semantics that is responsible for the burden and freedom borne by all Lisp programmers. No Lisp program of any size beyond a few lines can be written without being saturated with discretionary functions. Invent and fit; have fits and reinvent! We toast the Lisp programmer who pens his thoughts within nests of parentheses.
——艾伦·佩利
于康涅狄格州，纽黑文市
Alan J. Perlis
New Haven, Connecticut