砖头一般厚的入门教材，不知所云的include或import，望而生畏的Hello World……大部分编程者都经历过一段折翼的入门历程。编程真的是一件如此复杂、如此晦涩的事情吗？我并不这么认为。这篇文章将用一种不那么主流的方式，来尝试说明，编程，其实是一件简单而有趣的事情。

前导阅读：谈编程

编程语言

如果你看过前导阅读，那你对编程应该有了一个大致的理解：编程的目的是操控数据，方法是使用通用数据操控机器的“小动作”组合出算法。现在的电脑，普遍能识别某种机器代码（可以认为是一个二进制串），但是这种机器代码对于人类来说太难理解，更别提编写了。所以，前辈们提出了编程语言的概念，即设计一种特定的语法与其对应的语义，使得我们可以通过这种语法来组合出合适的语义以描述我们的算法。为了更好的理解，请回忆前导阅读中提过的抽象的概念：我举过一个考试数据处理的例子，即可以在“小动作”层的基础上构建新的抽象层，为一些更高阶的任务提供接口（比如对一个数列求和）。不难发现，编程语言其实就是一类抽象层，为编程者完成任务提供了更高层次的“小部件”。

举个例子，如果“小动作”集合里提供了将两个数相加、相减、相乘、相除后存放到某个地方的操作，而我们的任务又有大量的四则运算，那么一款支持四则运算的编程语言就是很好的一个中间抽象层（通用机器与实际任务之间），你写好四则运算表达式，编程语言就会分析你的表达式，并将其翻译为一串“小动作”指令。所以编程的基本模式就是，你在编程语言提供的环境中写下四则运算表达式，写好后通过某个“按键”让编程语言完成表达式到“小动作”的翻译，最后在通用机器上执行这些“小动作”。

语法和语义

如果要你给四则运算设计一个语法，你会怎样设计呢？

一开始可能会设计成这样：

exp -> num + num
     | num - num
     | num * num
     | num / num
     | num

exp表示算术表达式，num表示数字，->表示推出，即左侧的exp可以由右边用|分隔的若干式子中的一个替代。比如要说明6 + 5是个合法的算术表达式，可以由下面的推出过程说明：

exp -> num + num -> 6 + num -> 6 + 5

然而生活中的四则运算是这样的：

6 * 2 - 10 / 5

这提示我们，一个运算符的两边也可以是一个算术表达式。由这个直觉我们可以自然地把语法修改为：

exp -> exp + exp
     | exp - exp
     | exp * exp
     | exp / exp
     | num

从而比较复杂的表达式也可以被推出：

exp -> exp - exp 
    -> exp * exp - exp 
    -> 6 * exp - exp 
    -> 6 * 2 - exp 
    -> 6 * 2 - exp / exp 
    -> 6 * 2 - 10 / exp 
    -> 6 * 2 - 10 / 5

注意到，这个推出的过程也蕴含了计算的方法，即语义。比如第一步中我们用-分隔，表示我们想分别对-两端的表达式计算，然后将结果作差。这样一来我们就能推出很多表达式了，看上去也能做计算了，不过这里有一个棘手的问题：如果上面的推导的第一步不是选择-分隔，而是选择/分隔，似乎也能推出啊？可是语义就不对了啊？

为了解决这个问题，人们引入了括号。6 * 2 - 10 / 5应当写成(6 * 2) - (10 / 5)，能去掉括号的原因在于人们约定俗成了一套运算的优先顺序。由此看来，我们对四则运算的语法定义还相当naive。

但是，如果我们换一种语法，用上述思路就已经可以清晰的描述算术表达式了。注意到一个正确的推出，其第一步一定是选择了正确的运算符，既然这个第一步的运算符这么重要，那我们不妨把它放在最前面。虽然这听上去很荒谬，但很快你就能认识到它的好处：

6 + 5 => + 6 5
6 * 2 - 10 / 5 => - * 6 2 / 10 5

+ 6 5应该很好理解，我们来重点看下第二个。因为我们考虑的算术运算都是二元的，所以从左往右看时，每次看到一个运算符，我们就知道了，“哦，要做一个运算，操作数是紧跟着这个运算符的两个表达式”。回到第二个例子，看到-后，我们认识到后面跟着两个表达式表示操作数，那么我们就去后面找，很容易找出* 6 2和/ 10 5。那么计算也很直接了，先算* 6 2和/ 10 5，然后结果相减。

再看一个例子：

(6 * 2 - 10) / 5 => / - * 6 2 10 5

可以发现，这种奇怪的表示方式比起我们习惯的表示法，一方面不需要括号，另一方面运算的顺序也很清晰。从而，其语法很好表示：

exp -> + exp exp
     | - exp exp
     | * exp exp
     | / exp exp
     | num

作为例子的结束，我们再来看看如果+可以接受若干个操作数，应该如何修正语法。比如+ 1值为1，+ 2 3 4值为9等。关键的问题在于，在从左往右处理时，碰到一个+，我们不知道它的运算数有几个，这使得我们计算可能产生歧义。借鉴我们熟知的加括号思想，我们将语法改写为：

exp -> (+ exp exp ... exp)
     | (- exp exp)
     | (* exp exp)
     | (/ exp exp)
     | num

那么/ + 2 3 4 3就会被写成(/ (+ 2 3 4) 3)，这样，每个运算符的操作数也一目了然了。

Racket

看到这里，你几乎已经入门了一种编程语言——Racket。Racket语言其实是Lisp的一个方言，不过安装和使用更为简单，所以就选择它来作为这篇入门使用的编程语言了。

启动DrRacket后，可以看到一个上下隔开的窗口，上部的面板是编写程序的地方，下部的面板是与编程语言交互的地方。你可以在交互区键入上一节的表达式，回车后就能得到表达式的值：

> (/ (+ 2 3 4) 3)
3

从现在开始，你就已经成为一位编程者了。你可以先自己写一些表达式，看一看效果（最起码，你已经可以把Racket当做一个计算器使了）。接下来，我将介绍Racket语言的一些基本构件，看它为我们完成编程任务提供了哪些抽象。

约束

我们以四则运算为基础来扩展各种构件。当一个表达式的值可能被重复使用时，在所有需要这个值的地方重复地写这个表达式是不明智的。我们可以将一个名字约束到一个值，那么之后需要这个值时，可以通过这个名字来得到。Racket中使用(define 名字 表达式)来声明约束：

> (define x (/ (+ 2 3 4) 3))
> x
3
> (+ x 1)
4
> (* x 10)
30

有时候我们希望一个约束只在局部有效，比如x只在(+ x 3)中有效，这时候可以使用let来建立约束，结构为(let ([名字1 表达式1] [名字2 表达式2] ...) 内表达式)，语义为计算表达式1、2等并约束到名字1、2等，然后对内表达式求值，求值中可以使用约束的名字1、2等。

> (let ([x 3]) (+ x 1))
4
> (let ([x 3] [y 4]) (+ x y))
7
> (let ([x 3]) 
    (let ([y (+ x 2)]) 
      (+ y 1)))
6

最后一个例子中，内表达式也是一个let，这启发我们，各种构件能以嵌套的方式组合在一起。也就是说，我们可以使用很少几种构件，构造出各种功能的程序。

数值

按照前导阅读中的定义，我们称基本数据类型为数值。上文中已经提及的数字，在Racket中，数字又可以分为整数、分数、实数、复数等。

> (/ 1 2)
1/2
> (/ 1.0 2)
0.5
> (sqrt -1)
0+1i

其中sqrt表示开根号，是一个单元运算。除了数字之外，另一种必不可少的数值是布尔。布尔是用来表达我们日常生活中真或假的概念。在Racket中，我们用#t表示真，#f表示假。

> #t
#t
> #f
#f

为了让布尔值有意义，除了各种算术运算符，Racket还提供了很多关系运算符，如=用来判断两个数字是否相等，>用来比较两个数字的大小等。还可以用number?来判断一个数值是否为一个数字。

> (= 1 2)
#f
> (= 1 1)
#t
> (> 3 2)
#t
> (number? 1)
#t
> (number? #t)
#f

Racket中还有一种符号类型。在一个字符串前面加上一个'就可以得到符号。

> 'a
'a
> 'value-of-exp-2!
'value-of-exp-2!

可以用eqv?算符来判断两个符号是否相等。

> (eqv? 'a 'a)
#t
> (define x 'value-of-exp-2!)
> (eqv? 'value-of-exp-2! x)
#t

控制

既然编程语言是我们用来操控数据的工具，那么它一定会提供多种控制策略。比如，生活中我们常常需要进行“如果看到卖西瓜的那么买一个包子”之类的决策，Racket中也有类似的构件，即if表达式，形如(if 布尔表达式 表达式1 表达式2)，布尔表达式即值为布尔值的表达式。if表达式的语义是，先对布尔表达式求值，若值为真，则取表达式1并求值，否则，取表达式2并求值。

> (if #t (+ 2 3) (- 2 3))
5
> (if #f (+ 2 3) (- 2 3))
-1
> (define x 5)
> (define y 4)
> (if (> x y) (+ 1 1) (- 1 1))
2

当然，生活中并不总是非黑即白的逻辑，有时可能会有“如果看到卖西瓜的，买一个包子；如果看到卖南瓜的，买两个包子；否则，买三个包子”这样的策略。诚然，我们可以用if来实现：

(买 (if 看到卖西瓜的
        一个包子
        (if 看到卖南瓜的
            两个包子
            三个包子)))

但是如果情况更多，这种嵌套的if就显得比较臃肿。所以，Racket提供了一个语法糖（即其语义可以由其他基础语法的语义表达出来的语法），名为cond，结构为(cond [布尔表达式1 表达式1] [布尔表达式2 表达式2] ...)。

(买 (cond
      [看到卖西瓜的 一个包子]
      [看到卖南瓜的 两个包子]
      [else 三个包子]))

else的语义即“否则”。给一个实际的表达式。

(cond
  [(> x 0) x]
  [(< x 0) (- 0 x)]
  [else 0])

对这个例子稍加分析，容易发现它的语义是对x求绝对值。另外，cond会从上到下选择第一个成真的分支并对其求值。

函数

如果我们的任务需要重复计算一个数字的绝对值，那么我们需要在每个地方都重复上面的代码吗？重复在大部分时候是我们在编程中需要避免的。Racket也提供了避免这种重复的方法，就是定义函数。例如，可以通过(define (函数名 参数名) 表达式)的方法定义函数。

> (define (abs x)
    (cond
      [(> x 0) x]
      [(< x 0) (- 0 x)]
      [else 0]))
> (abs 5)
5
> (abs (- 0 3))
3

Racket里的函数几乎与数学里的函数是相同的，如果你学过数学里的函数，那么这里的函数也就不难理解了。可以发现，之前的四则运算(+ 1 3)与这里我们自己定义abs后通过(abs 5)来使用，结构是非常相似的。实际上，+也是一个函数，只不过它是一个二元函数。Racket也支持多元函数，结构为(define (函数名 参数名1 参数名2 ...) 表达式)。

> (define (calc op a b)
    (if (eqv? op '+)
        (+ a b)
        (- a b)))
> (calc '+ 1 2)
3
> (calc '- 3 2)
1

在这个例子中，我们定义了三元函数calc，其三个参数的语义分别为操作符op、操作数1a、操作数2b，然后根据op对a和b进行相应的计算（还记得'+是一个符号吗？）。

最后让我用一个例子来展示函数的能力的强大。还记得阶乘是什么吗？考虑一个数列：

A_0 = 1
A_n = n * A_{n - 1}, \forall n > 0

即A_n为1到n的乘积，又称为n的阶乘。能写一个函数，其接受n作为参数，并求出n的阶乘吗？来尝试把上面的数学定义翻译成Racket程序，应该怎么处理呢？这个函数有一个参数n，那么先来看看n是否等于0，如果等于0，结果就是1，否则，就算出n-1的阶乘，然后与n相乘作为结果。

> (define (A n)
    (if (= n 0)
        1
        ...

等等，如何表达“算出n-1的阶乘”呢？回想函数A的语义，是接受一个n，算出n的阶乘。如果我们把n-1当做参数并计算A，不就可以得到n-1的阶乘了吗！

> (define (A n)
    (if (= n 0)
        1
        (A (- n 1))))

但是别忘了算了n-1的阶乘还要乘n才是答案。

> (define (A n)
    (if (= n 0)
        1
        (* (A (- n 1)) n)))
> (A 10)
3628800

这是个很值得玩味的例子。你应当感到困惑，怎么能在函数定义中使用自己呢？这个问题很重要，但是在这里按下不表。你可以结合前面用数列定义的阶乘来理解。前导阅读中也提到过自引用，这里也出现了自引用，而其实它有个很酷炫的名字——递归。

计算器

让我们来看看，用这些构件能做些什么东西出来。与一般的编程入门不同，这里没有Hello World。反之，我想展示的是大部分编程书里甚至都不会提到的东西——如何写一个程序完成四则运算。自然，我们的四则运算仍然是(+ 2 (* 3 2))的形式。

让我们再来回忆编程是什么：利用一系列“小构件”来操控数据。那么首先，我们要明确，任务中的数据是什么，以及我们如何在Racket中表示数据。数据就是一个四则运算表达式，那么我们如何在Racket中表示呢？

列表

事实上，用已有的知识并不足以表示这种数据。幸运的是，Racket中提供了一种非常强大的构件，叫做列表。列表是一种数据类型，它是有结构的，其语义是一串数据，语法为(list 表达式1 表达式2 ...)，它将计算每个表达式的值，然后串在一起，得到一个列表。

> (list 1 2 3)
'(1 2 3)
> (list 'a 'b 'c)
'(a b c)
> (list 1 'b 3)
'(1 b 3)
> (list (+ 2 3) 'a)
'(5 a)

列表中可以嵌套列表，这是很自然的，因为既然列表是一种数据，列表的语义又是一串数据。

> (list 1 2 (list 3 4) 5)
'(1 2 (3 4) 5)

有时我们也用'(...)的方式来构造列表，区别在于，内部的所有元素都会被当做符号对待。

> '(1 2 (list 3 4) 5)
'(1 2 (list 3 4) 5)
> (list 1 2 (list 'list 3 4) 5)
'(1 2 (list 3 4) 5)

这个结果里的list仅仅是作为一个符号。

列表作为一种有结构的数据，Racket自然提供了操作其结构的方法。比如car可以用来取出列表的首元素：

> (car '(1 2 3))
1
> (car '((1 2) 3))
'(1 2)

与之相对应，cdr用来求列表去除首元素后的剩余部分：

> (cdr '(1 2 3))
'(2 3)
> (cdr '((1 2) 3))
'(3)

注意到第2个例子的结果是'(3)而非3，即cdr的结果仍然是一个列表。作为练习，如果我们要取出列表的第2个元素，要如何做？方法：先去除首元素，得到剩余部分，然后取出剩余部分的首元素。

> (car (cdr '(1 2 3)))
2
> (car (cdr '((1 2) 3)))
3

四则运算表达式

回忆四则运算表达式的语法：

exp -> (+ exp exp)
     | (- exp exp)
     | (* exp exp)
     | (/ exp exp)
     | num

如何在Racket中表示四则运算表达式呢？一种最直接的方法就是把表达式当做Racket的列表。

> '(+ 1 2)
'(+ 1 2)
> '(+ (* 2 3) (- 5 1))
'(+ (* 2 3) (- 5 1))

如何取出一个表达式的运算符和两个操作数呢？方法：使用car和cdr。

> (car '(+ 1 2))
'+
> (car (cdr '(+ 1 2)))
1
> (car (cdr (cdr '(+ 1 2))))
2

为了在需要取出表达式的地方重复这些car和cdr，我们可以自己建立一层处理表达式成分的抽象。具体来说就是定义三个函数，参数是一个表达式，取出运算符、操作数1、操作数2。

(define (binary-exp->op exp)
  (car exp))
(define (binary-exp->exp1 exp)
  (car (cdr exp)))
(define (binary-exp->exp2 exp)
  (car (cdr (cdr exp))))

从现在开始，我们改为在Racket的上部面板中编写程序，编写完成后，可以点右上角的“Run”，这样你写的程序就会被执行，之后你就可以在下部面板中使用执行的结果。比如对上面这段程序，“Run”之后我们可以在下部的交互面板中使用我们定义的函数。

> (binary-exp->op '(+ 1 2))
'+

别忘了，四则表达式除了二元运算的形式，还有exp -> num的形式，所以一个良好的设计应该定义一些谓词（函数），判断一个表达式是哪种形式。

(define (number-exp? exp)
  (number? exp))
(define (binary-exp? exp)
  (list? exp))

list?函数判断参数是否是一个列表。最后，我们需要为exp -> num形式的表达式定义函数以取出其“成分”。这乍一看比较奇怪，其成分就是其本身，不过这样有一个好处，就是之后求值程序的编写中可以只使用我们在这里定义的谓词和成分提取函数来操控数据，换句话说，可以保证抽象的完整性。

(define (number-exp->number exp)
  exp)

求值

现在我们知道了数据如何表示、如何操作其成分，那么我们可以进入编程的下一步：操控数据以完成我们的任务。我们任务是，对一个四则运算表达式求值，具体来说，就是编写一个函数，其参数为一个表达式，结果是这个表达式的值。

(define (calc exp)
  ...

要怎么求值呢？首先，既然表达式有两种可能的形式，而这两种形式的求值方法是不一样的，所以我们的程序首先要区分这两种情况。

(define (calc exp)
  (cond
    [(number-exp? exp) 处理表达式是一个数字的情况]
    [(binary-exp? exp) 处理表达式是复杂表达式的情况])

先来考虑数字表达式的情况。这种情况比较简单，这种表达式的值就是表达式中的数字。

(define (calc exp)
  (cond
    [(number-exp? exp) (number-exp->number exp)]
    [(binary-exp? exp)
     ...

再来考虑复杂表达式。在上一节中我们定义了将复杂表达式不同的成分取出来的函数，所以我们先把运算符和操作数取出来：

(define (calc exp)
  (cond
    [(number-exp? exp) (number-exp->number exp)]
    [(binary-exp? exp)
     (let ([op (binary-exp->op exp)]
           [exp1 (binary-exp->exp1 exp)]
           [exp2 (binary-exp->exp2 exp)])
       ...

根据四则运算表达式的语义，我们需要对exp1和exp2分别求值，然后根据op算出结果。怎么“分别求值”呢？现在的任务是对表达式exp1和exp2求值，而我们的函数calc的语义是对参数（是一个表达式）求值，那么对exp1求值就是(calc exp1)，对exp2就是(calc exp2)。

(define (calc exp)
  (cond
    [(number-exp? exp) (number-exp->number exp)]
    [(binary-exp? exp)
     (let ([op (binary-exp->op exp)]
           [exp1 (binary-exp->exp1 exp)]
           [exp2 (binary-exp->exp2 exp)])
       (let ([number1 (calc exp1)]
             [number2 (calc exp2)])
         ...

这里再次出现了自引用！如果你觉得不好理解，可以暂时通过直觉来认识：既然calc是用来对表达式求值的，而exp1也是个表达式，我们也需要对它求值，那么自然就应该使用calc函数。接下来，我们需要根据op来算出结果。因为是四则运算，op有四种可能，所以可以使用cond构件来完成。

(define (calc exp)
  (cond
    [(number-exp? exp) (number-exp->number exp)]
    [(binary-exp? exp)
     (let ([op (binary-exp->op exp)]
           [exp1 (binary-exp->exp1 exp)]
           [exp2 (binary-exp->exp2 exp)])
       (let ([number1 (calc exp1)]
             [number2 (calc exp2)])
         (cond
           [(eqv? op '+) (+ number1 number2)]
           [(eqv? op '-) (- number1 number2)]
           [(eqv? op '*) (* number1 number2)]
           [(eqv? op '/) (/ number1 number2)])))]))

嗯，完成了？对，这样就完成了！点击“Run”，然后我们可以在交互面板测试我们的程序。

> (calc '(+ 1 2))
3
> (calc '(+ (* 2 3) (- 5 1)))
10
> (calc '(- (+ 5 (* 2 3)) (/ (+ 3 3) (/ 6 3))))
8

你可以自己造一些例子，然后再回过去阅读calc函数的代码。

继续学习

到这里，这篇入门就要结束了。如果你感到困惑，不要灰心，因为这篇入门里面的确有一些入门时不好理解的东西，比如——递归，编程里最重要的思想之一，或许我会在另一篇文章里探讨这种思想。如果你对这篇文章中提到的编程语言以及编程的思维方式感兴趣，你可以阅读SICP（中文版为《计算机程序的构造和解释》），相信这本书会让你获益匪浅。