SCIP读书笔记（一）

    不得不说SCIP（Structure and Interpretation of Computer Programs）是我至今以来看过的让我最受益的一本教材了。它开启了我程序设计世界里的另一扇门，我有时会惊叹：原来程序可以这样写！这里我将自己的读书心得分享给大家，既然是读书心得，不到之处，还请大家指正。
    书中所有的例子都采用Scheme语言编写，因此我这里涉及到代码的地方也会使用Scheme。初次看Scheme语句的时候你可能会十分别扭，但是当你逐步深入学习时，你会发现Scheme语言的强大之处。我这里不会去评论各种编程语言的好坏，存在即是理由，不管是历史造就了一门语言，或是某个产品推动了一门语言的发展。每种语言都有自己的优点与缺点，在特定的场景下使用适当的语言，才能充分发挥程序的作用。就像生活中有各种各样的刀一样，有削铅笔的刀，有切菜的刀，有砍骨头的刀...每种刀只有在特定的场景下才能充分展示其作用，你不可能拿砍骨头的刀去削铅笔，反之，你也不会拿削铅笔的刀去砍骨头。语言就是一门工具，我们说学习一门语言，无外乎学习这门语言的语法规则，这是一件十分简单的事，我们可以在几个小时内就熟悉，但是我们其实更应该学习的是分析和解决问题的能力。写代码就是为了解决现实生活中的一些问题，遇到一个问题我们以什么方式能够高效优雅地解决，这才是一个程序员能力的体现。引用书中的一个比喻，我觉得十分恰当：学习一门语言就像学习下棋，语言的语法就像下棋的规则，就像象棋里的马走日，象飞田...每个人都能够快速的上手，但是要称为下棋的高手，光懂这些规则是远远不够的，还需要学习比如开局，战术，策略...因此作为程序员，我们更应该追求后者，提高自己分析和解决问题的能力，而不是炫耀学了多少种语言。好了，扯了很多不相关的东西，下面正式步入正题。
在这一篇中，我们主要熟悉Scheme的语法和一些基本概念。

1. 什么是程序设计语言？

书的开篇就提出了一个问题：什么是程序设计语言？程序设计语言需要具备什么特性？

程序设计语言就是一种指示机器去执行任务的方法，另外一方面，程序设计语言需要提供给其使用者一种表达其思想的方法。

上面是我翻译的，原文是这样的：

A powerful programming language is more than just a means for instructing a computer to perform tasks. The language also serves as a framework within which we organize our ideas about processes.

从这里我们可以看出，程序设计语言其实充当着翻译官的作用，它连接着程序员和机器，将程序员的思想翻译给机器执行。仔细想想，好像是这么一回事。强大的程序设计语言都具备以下三种机制：

• 元表达式：程序设计语言中的最简单的实体
• 组合方式：通过组合方式将简单的实体组合成更加复杂的元素
• 抽象能力：组合的元素能够被命名并作为一个整体来使用

所谓的元表达式就是程序中最简单的元素，主要包括两种：数字和元操作符+，-，*，/。元操作符和数字可以进行组合，例如在Scheme语言中你可以这样写：

(+ 1 2 3 4) -> 10
(* 2 3 5) -> 30

这样表示方法叫前缀表达式，语法规则是

(操作符 操作数 操作数 ...)

这样表示法相比于我们熟悉的中缀表达式的一个最大的好处是一个表达式可以有任意多个操作数而不会产生歧义，就像上面的例子。前缀表达式的另一个优势在于表达式的嵌套，例如：

(+ (* 2 3) (- 10 3)) -> 13

（注：要运行这些例子，需要下载一个Scheme解释器，例如MIT的scheme解释器)

    关于组合方式这一块，我们可以回顾下C语言和Java语言。在C语言中我们可以使用结构体struct和联合体union来简单的元素组合成复杂的元素；在Java语言中，我们使用类class来组合各种简单的元素，相比于结构体struct，class中还可以定义方法（当然，结构体中也可以定义函数指针变量来实现等价的效果），因此Java语言的组合方式更多一点。在Scheme语言里提供的组合方式叫做pair，我们可以使用box-and-pointer的表示方法来表示一个pair。在box-and-pointer中，每个实体都表示为一个box和指向该box的一个pointer，元表达式的box中就存放着与之对应的内容，而pair可以看做是两个连在一起的box和指向这两个box的pointer。一图胜千言：

box-and-pointer表示法

一个pair可以使用Scheme提供的cons函数来创建，如：

(cons 1 2) 就构建了上图中的pair

就像结构体struct中可以嵌套结构体，class中可以定义class一样，这里的cons中也可以嵌套cons，例如：

(cons 1 (cons 2 (cons 3 (cons 4 nil))))

用图形表示一下：

cons实现链表效果

是不是像某个数据结构：链表？（表达式中nil可以和我们熟悉的null做类比）这种嵌套（闭包特性：若某种操作的结果仍然可以用该操作处理，那么我们说这个操作有闭包特性，例如这里的cons）十分强大，能够表达各种各样的数据结构，这个后续还会详细介绍。
抽象能力这块其实是程序员需要重点关注的地方，看待一个问题的时候，我们应该尽可能地从更高层次上去抽象出问题的本质并找到合适的解决方案。在程序设计语言中的抽象能力主要体现在一个实体可以被命名，通过名字来引用某个实体。

    从元表达式、组合方式、抽象能力这三点我们可以总结一下：程序设计其实和搭积木很类似，我们有一个个简单的积木（元表达式），可以通过胶水或其他方式将一些简单的积木绑在一起（组合方式）得到组合的积木，最后我们用组合的积木（抽象能力）构建成最终的形状。反过来，我们要解决某个具体的问题，我们需要用抽象的能力将问题分解成一个个子问题，这些子问题能够更加简单的方式解决，当子问题解决后，我们将子问题的解组成原始问题的解。

2.Scheme基本语法

学习一门语言，当然最开始的就是学习其语法。这里主要简单的讲下基本语法，有兴趣的同学可以看书深入了解。

• 变量与函数的定义
  定义变量使用(define 变量名 变量值) 如 (define PI 3.14)
  定义函数使用(define (函数名 形式参数列表) 函数体) 如 (define (sum a b) (+ a b))
• 条件语句与预言

所谓的预言就是一个布尔表达式，有真和假两种情况，也就是我们常用的逻辑表达式：

逻辑与 (and <e1> <e2> ... <en>) 当<e1>, <e2> ... <en>都为真时为真，有短路规则.
逻辑或 (or <e1> <e2> ... <en>) 当<e1>, <e2> ... <en>任意一个为真时为真，有短路规则
逻辑非 (not <e>) <e>为真时表达式为假，<e>为假时表达式为真

条件语句的语法是：

(cond (<p1> <e1>)
       (<p2> <e2>)
        ...
        (<pn> <en>))

类似于我们熟悉预言里的switch语句，其执行顺序为若p1预言为真，那么就执行e1，同时e1表达式的结果将作为条件语句的结果返回。若p1为假，那么就判断p2预言，以此类推。条件语句还有一种，就是我们常用的if语句，其在Scheme里的语法为：

(if 预言 预言为真执行的语句 预言为假执行的语句) 例如 (if (> x 0) (+ x 1) (- x 1))

if语句是一种条件受限的cond语句，它只有两种情况。也就是说所有的if语句可以转换为cond语句，反之则不能。
    Scheme的基本语法就这么多，你或许会问，怎么没有循环表达式？这也是我当时的困惑，在Scheme中使用递归来代替了循环表达式，详细在后文中讲述。现在应该了解了Scheme的基本语法了，可以尝试用Scheme实现下书中的例子求某个数x的平方根。有疑问？请留言。