The Little Schemer

《The Little Schemer：递归与函数式的奥妙》是一本久负盛名的经典之作，两位作者Daniel P. Friedman、Matthias Felleisen在程序语言界名声显赫。《The Little Schemer：递归与函数式的奥妙》介绍了Scheme的基本结构及其应用、Scheme的五法十诫、Continuation-Passing-Style、Partial Function、Y-Combinator、Interpreter等内容，并通过这些内容阐述了计算的一般本质。《The Little Schemer：递归与函数式的奥妙》没有什么理论性描述，所有概念都蕴含在独特的引导式一问一答过程中，这种方式让读者对程序大师运用熟稔的程序方法来驾驭概念的能力叹为观止。
　　通过阅读《The Little Schemer：递归与函数式的奥妙》，可以让读者领略递归的奥妙、函数式编程风格的魅力。阅读完毕会有一种意犹未尽的感觉。
　　《The Little Schemer：递归与函数式的奥妙》适合所有程序员阅读，特别是函数式编程爱好者。好好享用！

Daniel P. Friedman，是美国印第安那大学计算机科学系的教授。Matthias Felleisen是美国莱斯大学计算机科学系的教授。同时，他们使用Scheme来教授计算及编程课程的经验超过了25年，发表了100多篇论文，出版了3部Scheme相关书籍。

　　卢俊祥，程序员；译者，爱读书；武当二十八式太极拳。

√ “计算能力是人类大脑让人兴奋的特性之一”——这个观念直接促生了与众不同的《The Little Schemer：递归与函数式的奥妙》。作者以极大的热情、幽默及易于理解的风格阐述抽象概念，为乐于探索计算本质的人们打开一扇崭新的思考之门。
　　√ 《The Little Schemer：递归与函数式的奥妙》将计算作为小学和高中算术与代数知识的扩展，并加以阐述。其以递归函数的方式介绍编程，简要讨论计算机所能发挥的作用。作者通过独特的编程语言、有趣的各式食物来描述这些抽象概念。
　　√ 多年来，《The Little Schemer：递归与函数式的奥妙》各个版本一直是广受欢迎的LISP教程。它还出版了法语版和日语版（现在终于有了中文版），已被广泛证明广受欢迎。

译者序
　　进入互联网、移动互联网时代，软件开发方面的好书层出不穷，绝大部分是技术新、方法新。然而，本书很独特，其出版于1995年，至今已有二十余年，而其前身The Little LISPer则出版于1987年，堪称“古董”！
　　为什么一本老书还有出版的必要？因为“经典”！因为其内容揭示了计算的一般本质，其价值历经时光的检验而含金量不减！其实本书已不用过多着墨加以介绍，其在广大程序员心中早已竖起了一座丰碑。
　　我酷爱编程，也接触过许多函数式编程语言，但没有任何一种编程语言能够像LISP那样擅于通过直接和简单的方式表达编程思维，不熟悉者迷惑于它的括号，而登堂入室者则能领略其精髓，最终游刃有余。本书只借助了Scheme编程语言的若干基础元件，就演绎出了各种问题的解决方式——这就是最佳诠释！
　　也许你在工作中不会用到Scheme，但是本书贵在作者深厚的编程积累，并能将丰富的经验充分发挥到本书内容中。全书的每一步都不显山露水，但最终蓦然回首时，轻舟已过万重山。探索计算本质的过程竟然如此巧妙，不禁让人拍案叫绝——手中用的是Scheme的招式，而心中洞察到的却是计算的内涵！
　　当其他编程书籍在讨论大量Hack技巧、各种设计模式的运用、形形色色的语法糖变化的时候，本书无疑就像一部另辟蹊径的武林秘籍，能大大增强习练者的内功。
　　作为一名有追求的程序员，这本书就是为你准备的。同时非常期待本书的姊妹篇The Seasoned Schemer。
　　参与本书翻译工作的还有林长瑞、吴桐、朱建宝、周荣华、吴胜华、叶铭辉、李禧强、姚建峰、郑秀玲。
　　感谢我的妻子和孩子，他们给了我很大的支持，小宝贝还给我带来了许许多多的乐趣。同时还要感谢本书编辑张春雨，在他的鼓励下，我的翻译过程充满愉悦。
　　卢俊祥
　　2017年6月
　　序
　　本序最初出现在The Little LISPer 一书的第二、三版中。经作者许可，特在此重现。
　　时光回到1967年，那时我报了一门摄影入门课程。包括我在内，大多数参加该课程的同学都憧憬着早日掌握创造性的摄影知识，希望自己有朝一日能成为又一个爱德华?韦斯顿 。第一天，老师详细地列出了一长串这学期要掌握的技能点。其中一个关键技能是安塞尔?亚当斯（Ansel Adams）的“区域曝光法”——用于预先视觉化冲印数据（最终冲印的灰度），及从景物光线强度中获取灰度。为了使用区域曝光法，还得学习曝光表用法以度量光线强度，以及通过曝光时间及显影时间来控制图像的灰度和对比度。反过来，这些技能又需要诸如胶片安装、显影、冲印和药水调制等更加底层的技能来支持。你必须学会将感光材料的显影过程程序化，以便在日后处理中获得一致的效果。第一次实验课是设法识别滑滑的显影剂和刺鼻的定影液。
　　而要让构图更具创造性，则必须首先具备驾驭工具的能力。甚至在能力具备之前都不要去构思如何组织一张好照片。在工程领域，如同其他创造性艺术，必须学会分析以支持我们在各方面的努力。那些有关钢材、扬尘以及大量数学方法等方面的知识，是计算构筑物属性时需要的，缺失了这些知识就无法构建美观而实用的桥梁。同样，未深入理解如何“预先视觉化”编程生成的工序，则无法构造出卓越的计算机系统。
　　一些摄影师选择8×10的黑白底片 ，而其他一些则选择35mm的底片 。不同片幅类型的底片各有其优缺点。跟摄影一样，编程也需要选择称心的语言。魔法编程语言Lisp属于崇尚自由和灵活风格的程序员！Lisp最初的设想是作为理论辅助工具，用于递归理论及符号代数。时至今日，Lisp已发展成为一个软件开发工具的大家族，魅力独特、功能强大且异常灵活，为软件系统的快速原型设计提供了全方位支持。与其他编程语言一样，技术社区开发出庞大的抽象功能库，Lisp则将这些功能连接起来。在Lisp的世界里，程序是一等数据，以参数方式传递，以值的方式返回，并存储在数据结构中。这种灵活性极具价值，而最重要的是，其为形式化、命名以及精简惯用法——工程设计中必不可少的常用使用模式，提供了机制保障。此外，Lisp程序能够轻松操纵Lisp程序的表述——一个开发庞大结构的程序综合 及分析工具（如交叉引用）的支持特性。
　　The Little LISPer一书以独特方式阐述了Lisp创造性编程哲学里的精髓技法。全书借助大量实际训练——掌握构建递归过程及操纵递归数据结构等技能所必要的实践，相当巧妙地将知识组织起来，让人丝毫感受不到学习的压力。The Little LISPer一书对Lisp学习者的意义，不亚于哈农 手指练习或车尔尼 钢琴研究对于钢琴学生的意义。
　　杰拉德?杰伊?萨斯曼
　　剑桥（美国，马萨诸塞州）
　　前言
　　为了给Scheme二十周年庆祝生日，我们第三次修订了The Little LISPer，这次我们把书名改为更贴切的The Little Schemer，并增写了姊妹篇：The Seasoned Schemer。
　　程序接受数据并产生数据。程序设计需要彻底理解数据；好的程序会反映出所处理数据的结构。大多数的数据集合，并由此延伸到大多数程序，都是可递归表示的。递归是依据自身定义对象或解决问题的方法。
　　本书的目标是引导读者学习递归思维模式。我们首先需要确定与递归概念搭档的语言。这里有三种相对明确的选择：自然语言，如英语；形式化的数学语言；或者是编程语言。自然语言易产生歧义、不严谨且有时候拖沓冗长。这可能在人们日常交流时没什么问题，但对于简明阐述递归这样的严谨概念，这些特征就容易出问题。数学语言则与自然语言相反：其仅通过一些符号就能表述强大的形式化概念。但很不幸，除非接受过数学专业训练，否则一般人理解不了数学语言。技术与数学的结合带给了我们第三种选择—几乎是最理想的选择：编程语言。我们相信编程语言是表达递归概念的最佳方式。编程语言像数学那样，具备将形式化含义赋予一系列符号的能力。但又不同于数学，可以直接体验编程语言—可以运行本书中的程序，观察其行为，然后修改它，再看看修改效果。
　　Scheme大概是用来讲解递归概念的最佳编程语言。符号化是Scheme的天然特质—程序员不必过多考虑所用语言符号与计算机表述形式之间的关联。递归是Scheme的天然计算机制；主要的Scheme编程任务是创建（可能的）递归定义。Scheme程序主要用于交互—程序员可以立即运行代码并观察结果。此外，至本书结束时，我们收获的最大感悟应该是：Scheme程序结构与程序所操纵数据之间是直接对应的 。
　　虽然Scheme程序可以以一种非常形式化的方式来描述，但理解Scheme并不需要特别的数学知识。实际上，本书基于一个Scheme两周“速成”介绍课程的讲义整理而成，该课程针对那些没有编程经验且不喜欢数学的学生。这些学生中有许多人正准备从事公共事务方面的工作。我们的信条是：用Scheme递归地编写程序本质上是简单的模式识别（Pattern Recognition）。由于我们唯一关心的是递归编程，因此我们仅在Scheme的几个招式上下功夫：car、cdr、cons、eq?、null?、zero?、add1、sub1、number?、and、or、quote、lambda、define以及cond。事实上，我们选择了完美的Scheme编程语言—我们的程序才能如此简洁。
　　The Little Schemer和The Seasoned Schemer并未涉足应用编程领域，但掌握书中的概念则为你打开了理解计算本质的大门。
　　阅读须知
　　你应该具备文字阅读能力，识得数字，还要会数数。
　　致谢
　　我们要感谢众多贡献者及他们为本书第二、三版提供的帮助。感谢Bruce Duba、Kent Dybvig、Chris Haynes、Eugene Kohibecker、Richard Salter、George Springer、Mitch Wand和David S. Wise的无数次讨论，为全书内容构思提供了思路。感谢Ghassan Abbas、Charles Baker、David Boyer、Mike Dunn、Terry Falkenberg、Rob Friedman、John Gateley、Mayer Goldberg、Iqbal Khan、Julia Lawall、Jon Mendelsohn、John Nienart、Jeffrey D. Perotti、Ed Robertson、Anne Shpuntoff、Erich Smythe、Guy Steele、Todd Stein和Larry Weisselberg在草稿阶段提供了许多重要意见。尤其感谢Bob Filman反复审核并提出深刻而尖锐的批评。最后，感谢Nancy Garrett、Peg Fletcher和Bob Filman为设计与TeX排版做出的贡献。
　　最新的第4版受惠于Dorai Sitaram的Scheme排版程序—无比智能的SLATEX。Kent Dybvig的Chez Scheme让Scheme编程变得非常愉快。真诚感谢Shelaswau Bushnell、Richard Cobbe、David Combs、Peter Drake、Kent Dybvig、Rob Friedman、Steve Ganz、Chris Haynes、Erik Hilsdale、Eugene Kohlbecker、Shriram Krishnamurthi、Julia Lawall、Suzanne Menzel Collin McCurdy、John Nienart、Jon Rossie、Jonathan Sobel、George Springer、Guy Steele、John David Stone、Vikram Subramaniam、Mitch Wand以及Melissa Wingard-Phillips的批评与建议。
　　读者指南
　　阅读本书切勿走马观花、一味图快。请仔细阅读，金玉珠玑分散在书中各个角落。本书很重要，重要的书至少读三遍。阅读时做到一步一个脚印。在未完全理解一章之前，不要尝试跳到下一章。问题按难度递增排序；解决不了早先的问题，后面的问题则将更难回答。
　　本书以对话方式组织内容，涉及Scheme程序的样例趣谈时，对话将在你（读者）和我们（作者）之间进行。请尽可能动手试验阅读到的样例代码。获取Scheme是一件很容易的事。尽管在不同Scheme实现之间存在微小语法差异（主要是特殊名称和特定函数方面的拼写），但Scheme语法基本上是一致的。接下来要玩转Scheme，还得定义本书引入的atom?、sub1和add1：
　　(define atom?
　　(lambda (x)
　　(and (not (pair? x)) (not (null? x)))))
　　试一试(atom? (quote ()))，看看其是否返回#f，以验证Scheme正确定义了atom?。实际上，该概念同样适用于诸如Common Lisp这样的现代Lisp方言。在Lisp中要以函数方式定义atom?：
　　(defun atom? (x)
　　(not (listp x)))
　　此外，你可能还需要对书中的程序进行稍加修改。典型的，只是做个别变化。框格注释 会给出程序试验的建议。“S：”打头的注释代表Scheme相关内容，“L：”打头的注释代表Common Lisp相关内容。
　　第4章我们会通过3个运算函数：add1、sub1和zero?来开发一个基本的算术程序。由于Scheme并未提供add1和sub1，因此需要借助内建的加减基本元件来定义它们。进一步的，为了避免冲突，程序的加减法必须以不同的符号：+和—来分别实现 。
　　本书不涉及任何形式化定义。我们相信你可以构建自己的定义，并因而记住及理解这些定义，这样的效果比我们一口口喂给你吃要好。但在你出山之前，需确保自己彻底理解了Scheme的五法十诫 。学习Scheme的钥匙是“模式识别”。Scheme十诫心法指出了具体模式。在本书的早期，一些概念出于简单起见讲解得比较浅显；但随着内容的深入，将适时展开描述。你应该也知道，虽然全书讲的是Scheme，但Scheme自身应用的广泛性，可不是我们用介绍性文字就能够清晰阐述的。在掌握了本书内容之后，就可以着手阅读与理解更加全面且高级的其他Scheme书籍了。
　　我们的大量示例都跟食物有关，这里有两个原因。首先，食物比抽象符号更形象（你如果正在节食，显然不适合读这本书，开玩笑）。我们希望各种食物能够帮助你理解示例及相关概念。其次，我们打算乱一下你的心智。我们知道学习之路总是充满各种沮丧，一点点障碍将有助你保持清醒。
　　你可以整装待发了。祝你好运！希望你好好享受荆棘旅程中的激情挑战。
　　祝你胃口大开！
　　丹尼尔?弗里德曼
　　马提亚?费雷森

第1章　玩具总动员 2
第2章　处理，处理，反复处理…… 14
第3章　用cons构筑恢宏 32
第4章　数字游戏 58
第5章　我的天！都是星星 80
第6章　如影随形 96
第7章　朋友及关系 110
第8章　Lambda终结者 124
第9章　……周而复始…… 148
第10章　值是什么 174
幕间休息 192
索引 194

Schemer,编程,计算机科学,工具书,好东西,程序,科普,游戏