Skip to content

Latest commit

 

History

History
318 lines (201 loc) · 17.6 KB

第2章 创建你的第一个 LISP 程序 Creating Your First Lisp Program.md

File metadata and controls

318 lines (201 loc) · 17.6 KB

第2章 创建你的第一个 LISP 程序 Creating Your First Lisp Program

翻译者：FreeBlues

github版本：https://github.com/FreeBlues/Land-of-lisp-CN

开源中国版本：http://my.oschina.net/freeblues/blog?catalog=516771

目录

既然我们已经讨论过 Lisp 的一些哲学并且拥有了一个正常运行的 CLISP 环境，我们就准备以一个简单游戏的形式来写一些实际的 Lisp 代码。

猜数字游戏

我们将要编写的第一个游戏是能想到的最简单的游戏。 它是一个经典的猜数游戏。

在这个游戏中，你选择一个从1到100的数字，接着计算机要把它猜出来。

接下来展示了当你选取数字23时游戏玩起来是什么样子。计算机以50开始猜，并且随着每次不停的猜测，你要输入 (smaller) 或 (bigger) 直到计算机猜中你的数字。

>(guess-my-number)
50
>(smaller) 
25
>(smaller) 
12
>(bigger) 
18
>(bigger) 
21
>(bigger) 
23

为了创建这个游戏，我们需要编写3个函数：guess-my-number，bigger 和 smaller。玩家简单地从 REPL 调用这3个函数就可以了。正如你在前面章节所看到的，当你启动 CLISP (或者其他 Lisp)，REPL 将会呈现在你面前，通过它你输入的命令可以被读取(read)，然后被求值(evaluated)，最后被打印出来(printed)。在这个例子里，我们要运行命令 guess-my-number，bigger 和 smaller。

在 Lisp 中调用函数，你要把这个函数和打算传给这个函数的所有参数一起用括号括起来。既然一部分函数不需要任何参数，我们只要用括号把它们的名字括起来就可以了。

让我们考虑一下这个简单游戏背后的策略。简单思考一下，我们通过以下步骤来逐步实现：

1.确定玩家数字的上限和下限(大和小)。因为范围在1到100之间，最小的数字应该是1，最大的数字应该是100。 2.在这两个数字之间猜一个数。 3.如果玩家说真实数字更小一些，降低上限(最大数字)。 4.如果玩家说真实数字更大一些，增加下限(最小数字)。

C2-1图

通过上述简单步骤，每次猜测都把可能的数字范围缩小一半，计算机能很快找出玩家的数字。

这种搜索算法被称为二分法(binary search)，正如你所知，像这样的二分法一直被用于计算机编程中。你能沿用相同的步骤，例如，高效地找到一个特定的数字，从被给定的数值的排序表中。在这个例子里，你可以简单地追踪表里的最小行和最大行，并且很快找到正确的行，以一种类似的方式。

定义全局变量

当玩家调用那些构成我们游戏的函数时，程序需要追踪下限和上限。为了做到这一点，我们需要创建两个被称为 *small* 和 *big* 的全局变量。

定义“小”和“大”变量

在 Lisp 中一个被定义为全局的变量被称为一个顶层定义(top-level definition)。我们可以使用函数 defparameter 来创建新的顶层定义：

>(defparameter *small* 1)
*small*
>(defparameter *big* 1)
*big*

函数名 defparameter 会带来一点困惑，因为它实际上没有对参数(parameter)做任何操作。它所做的就是让你定义一个全局变量(global variable)。

我们发送给 defparameter 第一个参数是心变量的名字。环绕名字 *small* 和 *big* 前后的星号(*)--被昵称为耳套(earmuffs)--完全是随意和可选的。Lisp 把星号当做变量名的一部分并且忽略掉它们。Lisper 喜欢以这种方式作为一个约定俗成的惯例为他们的全局变量标上星号，以便它们可以更容易和局部变量区分开来，在本章的后面将会讨论这一点。

注意

尽管耳套在严格技术意义上来说是可选的，我还是建议使用它们。我无法保证你的安全，如果你把代码贴到一个 Common Lisp 新闻组并且你的全局变量没有带耳套。

全局变量定义函数的替代

当你使用 defparameter 设置一个全局变量的值时，任何之前存储在这个变量中的值都会被重写覆盖掉：

>(defparameter *foo* 5)
FOO
>*foo*
5
>(defparameter *foo* 6)
FOO
>*foo*
6

正如你所见，当我们重新定义了变量 *foo* 之后，它的值变了。

另一个可以用来声明全局变量的命令被称为 defvar ，它不会覆盖掉一个全局变量之前的值：

> (defvar *foo* 5) FOO
> *foo*
5
> (defvar *foo* 6) FOO
> *foo*
5

注意

当你在其他地方阅读关于 Lisp 的知识时，你可能也会看到程序员们在 Common Lisp 中使用术语动态变量(dynamic variable)或特殊变量(special variable)来指一个全局变量。这是因为 Common Lisp 中的全局变量有一些特殊的能力，我们将会在后面的章节讨论这些。

Lisp的基本规矩

跟其他语言比起来，Lisp 中命令被调用的方式和代码被格式化的方式有些奇怪。首先，我们需要用括号把命令(以及命令的参数)括起来，就像 defparameter 函数一样：

>(defparameter *small* 1)
*small*

缺少括号的话，命令不会被调用。

此外，空格和换行被完全忽略，当 Lisp 读入你的代码时。这意味着你能用任何疯狂的方式来调用这个命令，而结果不会变：

> (          defparameter 
      *small* 1)
*SMALL*

因为 Lisp 代码能以这种灵活的方式格式化，Lisper 对于格式化命令有很多约定俗成的惯例，包括什么时候使用多行和缩进。在本书的代码实例上，我们将会大致遵循一些常见的缩排惯例。不过，相对于讨论源代码缩排规则我们更感兴趣的是编写一些游戏，因此本书中我们将不会在代码布局上花费过多时间。

定义全局函数

我们的猜数游戏通过计算机对玩家请求的响应来开始游戏，然后请求更小或更大的猜测。为了实现这些，我们需要定义3个全局函数：guess-my-number，bigger 和 smaller。我们还要定义一个名为 start-over 的函数，用来重新开始游戏以一个不同的数字。在 Common Lisp 中，用 defun 来定义函数，如下所示：

(defun function_name (参数)
	...)

首先，我们为一个函数指明名字和参数。然后我们接着写组成函数处理逻辑的代码。

定义猜数函数

我们定义的第一个函数是 guess-my-number。这个函数使用变量 *small* 和 *big* 的值来生成一个针对玩家数字的猜测。定义如下所示：

> (defun guess-my-number ()
	(ash (+ *small* *big*) -1))
GUESS-MY-NUMBER

在函数名字 guess-my-number 之后的空括号 () 指明这个函数不需要参数。

尽管在把片段代码输入到 REPL 时不需要担心缩排和断行，你必须确保把括号的位置放置正确。如果你忘掉一个后括号或者把一个括号放到了错误的位置上，你很可能会得到一个错误。

当我们任何时候像这样在 REPL 里运行一段代码时，输入表达式的结果值将会被打印出来。Common Lisp 中的每一个命令都会产生一个返回值。例如 defun 命令简单地返回新建函数的函数名。这就是为什么我们看到在我们调用 defun 之后在 REPL 中函数名被鹦鹉学舌般返回给我们。

这个函数做了什么？正如之前讨论过的，这个游戏中计算机最好的猜测将是一个介于两个限制之间的数字。为了完成这一点，我们选择两个限制的平均值。然而，如果平均值以一个分数结尾的话，我们想要使用近似(near-average)数，因为我们猜测的是完整的数字。

我们在函数 guess-my-number 中实现这些功能通过以下处理：首先把上限值和下限值加在一起，，然后使用算数移位函数 ash ，来使上限值、下限值之和减半并且截短结果。代码 (+ *small* *big*) 把这两个变量加起来。因为加法用另一个函数调用， <1> ，加的结果被接着传递给函数 ash。

包围函数 ash 和函数 (+) 的括号在 Lisp 中是必须要有的。这些括号告诉 Lisp “我想让你马上调用这个函数”。

内置的(build-in) Lisp 函数 ash 以二进制的方式看待一个数字，然后把它所有的二进制位(bits)同时移向左边或右边，丢掉在这个过程中失去的任何位（译者注：）。例如，十进制数字 11 用二进制表达就是 00001011。我们可以向左移动这个数字里所有的位，通过 ash 把 1 作为第二个参数：

>(ash 11 1)
22

这样就产生了 22，二进制是 00010110。我们也可以把所有位向右移动(去掉了最后的一位 1)通过用 -1 作为第二个参数：

>(ash 11 -1)
5

这样会产生5，二进制是 00000101。

通过在 guess-my-number 中使用函数 ash，我们可以连续减半可能数字的搜索空间来快速缩小最终正确数字的范围。正如之前提到的，这种减半处理被称为二分搜索，一种在计算机编程中很有用的技术。函数 ash 经常被用于 Lisp 中这些二分搜索。

让我们看看当我们的新函数被调用时将会发生什么：

>(guess-my-number)
50

因为这是第一次猜测，我们看到调用这个函数的输出告诉我们一切都按计划进行：程序选择了数字 50，正好位于 1 和 100 的中间。

在用 Lisp 编程时，你将会写很多函数，它们不会明确打印值到屏幕上。作为替代，它们将会简单地把函数体的计算值返回。例如，我们说我们想要一个函数仅仅返回数字 5 ，我们可以这样写：

> (defun return-five ()
	(+ 2 3))

因为函数体里计算的值被求值为 5，调用 (return-five) 只会返回 5。

这就是 guess-my-number 的设计思路。我们看到这个被计算后的结果出现在屏幕上(数字 50)不是因为函数使这个数字显示，而是因为这是 REPL 的一个特性。

注意

如果你之前使用过其他编程语言，你可能记得为了让一个值被返回不得不写一些类似 return… 的东西。在 Lisp 中，这是不必要的。函数体中被计算的最终值会被自动返回

定义更小更大函数

现在要写我们的 smaller 和 bigger 函数了。像 guess-my-number 一样，这些都是用 defun 定义的全局函数：

> (defun smaller ()
	(setf *big* (1- (guess-my-number)))
	(guess-my-number))
SMALLER
> (defun bigger ()
	(setf *small* (1+ (guess-my-number)))
	(guess-my-number))
BIGGER

首先，我们使用 defun 来开始一个新全局函数 smaller 的定义。因为这个函数不带任何参数，所以函数名后面的括号是空的 <1>。

接着，我们使用 setf 函数来改变我们全局变量 *big* 的值 <2>。因为我们知道那个数字必须要比上次猜的值更小一些，最大的它现在是比猜测值要小的那个。代码 (1- (guess-my-number)) 这么计算：首先调用函数 guess-my-number 来获得最近的猜测值，然后对这个猜测值使用函数 1-，会从猜测值里减去 1。

最后，我们想要函数 smaller 给我们显示一个新的猜测值。我们通过把函数 guess-my-number 放在函数体的最后一行来实现 <3>。这一次，guess-my-number 将会使用更新过的 *big* 值，用这个值来计算下一个猜测值。我们的函数的最终的值将会自动返回，使得我们新的猜测值(由 guess-my-number 产生)通过函数 smaller 产生。

函数 bigger 以相同的方式工作，除了它是把 *small* 的值增加之外。终究，如果你调用函数 bigger，你就是在说你的数字要比上一次猜测值更大，因此最小的它现在要比(就是变量 small 所对应的值)前一次猜测值更大。函数 1+ 简单地在由 guess-my-number 返回的猜测值上加 1 <4>。

可以在这里看到当程序猜了 56 时我们函数的运行情况：

> (bigger) 
75
> (smaller) 
62
> (smaller)
56

定义重新开始函数

为了完成我们的游戏，我们将会增加函数 start-over 来重新设置我们的全局变量：

(defun start-over ()
	(defparameter *small* 1)
	(defparameter *big* 100)
	(guess-my-number))

正如你所见，函数 start-over 重置了变量 *small* 和 *big*，接着再次调用函数 guess-my-number 来返回一个重新开始的游戏。不论何时只要你想启动一个使用不同数字的崭新游戏时，你都可以调用这个函数来重置游戏。

定义局部变量

为了我们简单的游戏，我们已经定义了全局变量和全局函数。然而，大多数情况下你可能想把定义限制在一个单独的函数中或者是一块代码内。这些就是被称为局部变量和局部函数。

定义一个局部变量。要使用命令 let。一个 let 命令有着如下结构：

(let (variable declarations)
	...body...)

在 let 命令中的第一部分是一个变量声明的列表。在这里我们可以声明一个或多个局部变量 <1>。接着，在命令体里(并且仅仅在这个体内)，我们能使用这些变量 <2>。这里是关于 let 命令的一个例子：

> (let ((a 5)
	    (b 6))
	(+ab))
11

在这个例子中，我们分别为变量 a <1> 和 b <2> 声明了值 5 和 6。这些就是我们的变量声明。然后，在命令 let 的体内，我们把它们加在一起 <3>，显示出结果值 11。

在使用一个 let 表达式时，你必须用括号把被声明的变量全部括到一起。另外，你必须把每一对变量名字和初始化变量值用另一对括号括起来。

注意

尽管缩排和断行是完全随意的，因为在一个 let 表达式里的变量名和它们的值形成了一种简单的表格，提倡的经验是把被声明的变量垂直对齐。这就是为什么在上一个例子中 b 被直接置于 a 的下方。

定义局部函数

我们用 flet 命令来定义局部函数。命令 flet 有着如下结构：

(flet ((function_name (arguments)
		...function body...))
	...body...)

在 flet 的顶部，我们声明了一个函数(在起始两行)。这个函数接着在这个主体内将对我们可用 <3>。一个函数声明包括一个函数名字，函数的参数 <1>，以及函数主体 <2>，在那里我们将放置函数的代码。

这里是一个例子：

> (flet ((f (n)
			(+ n 10)))
	(f5))
15

在这个例子中，我们定义了一个独立的函数 f ，它带着一个单独的参数，n <1>。函数 f 把 10 加到变量 n 上 <2>，被传给它的。=== 接下来我们使用数字 5 作为参数来调用这个函数，值 15 会被返回 <3>。

跟 let 一样，你能在 flet 的范围内(译者注：也就是在 flet 的顶部)定义一个或多个函数。

一个单独的 flet 命令能被用来一次定义多个本地函数。简单地在命令的第一部分增加多个函数声明就可以了：

> (flet ((f (n)
			(+ n 10))
		(g (n)
			(- n 3)))
	(g (f 5)))
12

在这里，我们声明了两个函数：一个名为 f <1>，一个名为 g <2>。在 flet 的主体部分，我们可以立即使用这两个函数。在这个例子里，主体先使用参数 5 调用 f 得到 15，接着调用 g 来减去 3，最终得到的结果是 12。

为了使得函数名在被定义的函数中也可用(译者注：此处是指同时定义函数可以相互调用)，我们可以使用命令 labels 。它的基本结构跟命令 flet 相同。这里是一个例子：

> (labels ((a (n)
			  (+ n 5))
		   (b (n)
			  (+ (a n) 6)))
	(b 10))
21

在这个例子里，局部函数 a 把 5 加到一个数字上 <1>。接着，函数 b 被声明 <2>。函数 b 调用了函数 a，然后在结果上加 6 <3>。最终，函数 b 使用参数值 10 被调用 <4>。因为 10 加 6 加 5 等于 21，数字 21 成为整个表达式的最终值。当我们想要用函数 b 调用函数 a 时 <3>，就需要我们选择 labels 而不是 flet。如果我们用了 flet，函数 b 是不会"知道"函数 a的。

命令 labels 允许我们使用一个局部函数调用另一个，同时它也允许我们用一个函数调用它自己。这种做法在 Lisp 代码中很常见，被称为递归(你将会在未来的章节中看到很多关于递归的例子)。

你学到什么

本章中，我们讨论了用于定义变量和函数的基本 Common Lisp 命令。一路走来，你学到了如下内容：

  • 定义一个全局变量，使用 defparameter 命令。

  • 定义一个全局函数，使用 defun 命令。

  • 分别使用 let 和 flet 命令来定义局部变量和局部函数。

  • 函数 labels 跟 flet 很相似，不过它允许函数自我调用。

  • 调用自己的函数被称为递归函数。