Skip to content

Instantly share code, notes, and snippets.

@yuest
Created August 16, 2012 04:50
Show Gist options
  • Save yuest/3367033 to your computer and use it in GitHub Desktop.
Save yuest/3367033 to your computer and use it in GitHub Desktop.
Lisp 之根本 - blogist.yue.st

大名鼎鼎的 Paul Graham 写过一篇《The Roots of Lisp》,讲解他对 Lisp 根源的理解。这篇文章我在很多年前就试图阅读,但是都不大能读懂,直到去年年末时候我读了几十年前的 Lisp 1.5 手册的相关部分,终于算是理解了。再读一遍 pg 的文章,也就完全能懂了。现在结合自己的理解尝试把这些概念重述一遍。这篇文章就是想以自己的话语阐述一遍这些基本概念。这里会偏重于数学式的思维训练而不是实用性的程序编写,所以和实际情况会稍有出入。计划写两部分,第一部分是7个原始操作,第二部分讲实现 Lisp 解释器。

在 lisp manual 里面,我看到 John 使用了一种数学人很喜欢的表述方式,就是先定义符号和规则,然后在这套规则下让我们来看看我们可以怎么玩。有一点数学基础的人可能就会觉得这样理解会很容易。

##基本定义

首先定义符号,为了简化,我在这篇文章里就定义可用的符号26 个小写字母、10个数字、空格、左右圆括号和单引号

然后我们定义原子(atom),原子就是由字母和数字组成序列并且只能由字母开头,比如 abc123,比如 foo 或 bar 都是原子。

之后我们定义列表(list),列表的组成规则是,一个括号里面有若干个以空格分开的原子

接着我们就可以定义表达式(expression)了,表达式的定义如下:

  1. 一个原子是表达式
  2. 一个空括号是表达式
  3. 一个括号内有若干表达式,它们之间以空格分隔开,这整个括号及其内的表达式组成一个表达式

可以看到表达式是递归定义的(定义包含了被定义的术语)。

例如

atom
()
(atom)
(a b)
(() () ())

等等

#函数表示

之后我们就可以看一下 pg 所说的七个原始操作符。不过要先插一点内容说明一下 lisp 中函数的调用。

其实 John 在 Lisp Manual 里面定义的是有两种表达式的,S-表达式其实是用大写字母、括号和句点来表示,一个表达式只是一个括号包住它的左、右部分,用句点分隔,比如

(A.B)
(A.(B.C))
(((A.B).(A.C)).(D.(E.F)))

然后函数用小写字母和中括号、分号、等号来表示函数,如

car[(A.B)]=A
cdr[(A.B)]=B

这样的定义就比较一目了然,知道 car 函数取 S-表达式的左部分,cdr 函数取 S-表达式的右部分。

但是这个 S-表达式只存在于 MyCarthy 的手册里面,实际的 Lisp 实现都用的是手册里所称的 M-表达式,也就是不用大小写和中括号区分,一律用小写和圆括号,然后大家就说 lisp 是不区分程序和数据的语言。

什么意思呢?lisp 中的函数调用也是表达式的形式,只是表达式中第一个元素是函数名或操作符(或者直接就是一个匿名函数,这个之后会讲),后面是参数,比如最简单的 (+ 1 2 3) 就是计算 1 + 2 + 3 的结果,这是操作符;而 (a b c) 就相当于其他语言中的 a(b,c)。可以看成 Lisp 是把操作符也当成是函数等同起来看待的。

其实 Lisp 不是不区分数据和程序,而是形式上看起来他们会很像,都输出括号括起来的一个列表。那么问题来了,我怎么知道哪个是数据,哪个是程序呢。比如说我给出 (a b c) 的话,我可能是要表示别的编程语言中 a(b,c) 的意思,也可能是给出 (a b c) 这个列表。这就是 quote 操作符的意义所在:用来区分数据还是程序。

这就是很多新手(包括以前的我)读到“(quote x),简记成 'x,返回 x”就晕掉而打算放弃的原因,因为这样的句子没有道出其背后的意义。

##七个原始操作

quote:

现在理解了吧? 'x 返回的 x 表示就是 “x” 这个字母,而不是返回 x 变量所代表的值;'(a b c) 返回的 (a b c) 表示有三个 atom 元素的列表,而不是表示对 a 函数以 bc 为参数去调用。

atom:

atom 操作符用来判断某个变量是不是原子或空表,(atom x) 这个表达式,如果 x 是原子或空表,就返回t,否则返回空表。在 Lisp 里面用原子 't 和空表 () 表示其他语言中的布尔值真和假。

eq:

eq 用来判断两个变量是不是相同的原子或者都是空表。如果是相同原子或都是空表,返回 't,否则返回 ()

car 和 cdr:

前面说过一开始 John 定义的S-表达式是一个括号里面只有左右两边两个 S-表达式。car 取左边,cdr 取右边,这样很容易理解。紧接着 John 定义了 S-表达式的列表式写法和 S-表达式的等价关系。

就是用 (m1 m2 m3 m4 m5) 表示 (M1 . (M2 . (M3 . (M4. (M5 . ())))))

所以这样你就能明白为什么现在定义是 car 取列表的第一个元素,而 cdr 取列表去掉第一个元素后的其他元素组成的列表。因为对照 S-表达式过去,cdr 取到的是 (M2 . (M3 . (M4. (M5 . ())))),用列表形式表示就是 (m2 m3 m4 m5)。而不断取 cdr,因为 (m5) 用 S-表达式是 (M5 . ()),取到的就是 ()

这样就容易理解了吧。

cons:

如果有变量 y 是一个列表,那么 (cons x y) 返回一个列表,这个列表的第一个元素是 x,后续是 y 列表中的各个元素。简单说,就是返回的新列表相当于将 x 插入 y 的开头。例如 (cons 'a '(b c d)) 将返回 '(a b c d)

这在 S-表达式下很容易理解。cons[A,B]=(A.B) 的意思就是把 AB 两个 S-表达式合成 (A.B) 这样一个。如果 B 是一个列表,根据 S-表达式转 m-表达式的规则,不就相当于将 A 加到列表 B 前面嘛。

cond:

这个相当于其他语言的 if 或 switch 语句。

(cond (p1 e1) (p2 e2) (p3 e3))

相当于

if (p1) e1; else if (p2) e2; else if (p3) e3;

那么 else 怎么办呢?可以类似 if (p) e1; else if (true) e2,Lisp 里面就是 (cond (p e1) ('t e2))

这也可以解释为 S-表达式的形式:

cond[(P1.E1), (P2.E2)]

cond 接受的是以 S-表达式为元素的列表,从第一个元素开始判断,如果这个 S-表达式的左边为真,整个 cond 函数的结果就取这个 S-表达式的右边,不为真就继续看下一个 S-表达式的左边是否为真。

##下集预告

以上就是七个原始操作了,为什么定义这七个操作为原子操作符呢?因为有了以上这七个(quote、atom、eq、car、cdr、cons、cond)我们就可以用 Lisp 写一个解释器,去运行用 Lisp 写成的程序!虽然我不太清楚这意味着什么(当然,这意味着 Lisp 语言的解释器非常容易实现,意味着我们可以很容易地 hack Lisp 这门语言,但我不清楚这在学术意义上意味着什么),但是看起来是不是很厉害的样子,有木有?下一篇文章我们就来做这个事情。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment