Yaodan's Blog

Lisp中cons/car/cdr的几种实现方式

| Comments

基本概念

在Lisp中，cons、car、cdr是三个原始操作符，Lisp在它们（和另外几个原始操作符）的基础上，定义了一个干净、完整的编程语言。关于Lisp的基本概念，有一篇博客写的非常好，强烈推荐大家去读一读：《Lisp之根源》

Lisp中的一般表达式

Lisp中的表达式一般是长这样的：(op args)。

简单来说，他的构成方式就是用一对括号括起一些元素，形成一个表，用来表达一个过程。其中，在表里最左边的元素op叫做运算符，其他元素（0个或多个）都叫做运算对象。要得到一个表达式的值，就是将运算符描述的过程应用于实际参数，而所谓的实参就是那些运算对象的值。

给大家一些例子就好明白了：

lisp expressions
1
2
3
4
5

(+ 1 1)  --> 2
(- 2 1)  --> 1
(* 2 3)  --> 6
(/ 2 1)  --> 2
(+ 1 2 3 4)  --> 10

我们把运算符放在所有的运算对象左边，这种形式成为前缀表达式。乍看起来怪怪的，但好处多多，这里就不展开了。

cons

cons接收两个参数，组成了一个有序对（pair）。这是一个很简单的数据结构，但是由于cons的参数可以是任意类型，那么在这基础上就可以组成各种各样的数据结构了。

基本的有序对：

pair
1
2
3
4
5

(cons 17 29)

  *
 / \
17 29

链表：

list
1
2
3
4
5

(cons 3 (cons 5 (cons 7 (cons 9 nil))))

 *--*--*--*--nil
 |  |  |  |
 3  5  7  9

二叉树：

tree
1
2
3
4
5
6
7

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

   *
  / \
 *   *
/ \ / \
1 2 3 4

car/cdr

对于一个cons组成的有序对，我们可以用car取第一个元素，用cdr取第二个元素。

例子：

car & cdr
1
2

(car (cons 1 2)) --> 1
(cdr (cons 1 2)) --> 2

如何实现cons/car/cdr

在一般的Lisp方言里，由于这三个操作太重要，太原始了，为了效率，一般都是直接实现的。但是我们学习的时候还是可以想想如何自己来实现这三个操作的。

定义需求

这三个操作的描述已经在上面了，要实现他们，我们的需求就是：如果用cons把两个元素绑定在一起，那个可以用car和cdr把他们分别提取出来。

那么可以写一个很简单的测试来测我们的实现：

cons_test.clj
1
2
3
4

(deftest cons-test
  (testing "test my cons"
    (is (= (car (cons 17 29)) 17))
    (is (= (cdr (cons 17 29)) 29))))

普通实现

直接上代码了：

cons.clj
1
2
3
4
5
6
7
8
9
10
11

(defn cons
  [a, b]
  (fn [m] (if (= m 0) a b)))

(defn car
  [c]
  (c 0))

(defn cdr
  [c]
  (c 1))

我们说过了，cons实际上是用来定义一种数据，这个数据由两个元素组成。但是，我们的实现完全没有用到任何的数据结构，只是用过程就把他实现了。

这里面cons操作的结果不是数据，而是一个函数，这里直接返回了一个lambda表达式，当然也可以返回一个有名字的函数，像下面这样：

cons.clj
1
2
3
4
5
6

(defn cons
  [a, b]
  (defn dispatch
    [m]
    (if (= m 0) a b))
  dispath)

比如c的值是(cons 3 4)，那么c实际上是这样一个函数(λ [m] (if (= m 0) 3 4)，他的意思是给一个参数m，如果m的值是0，那么返回3（第一个元素），否则返回4（第二个元素）。再看看我们定义的car，他实际上是将0作为参数调用上面这个函数，结果返回3。cdr也是一样的道理。

这就是一个纯过程的实现，但是这里面m啊，0啊这些东西看起来还是很恶心，于是我们有了另外一个版本。

文艺实现

还是先上代码：

cons.clj
1
2
3
4
5
6
7
8
9
10
11

(defn cons
  [a, b]
  (fn [f] (f a b)))

(defn car
  [c]
  (c (fn [a, b] a)))

(defn cdr
  [c]
  (c (fn [a, b] b)))

我们先理解cons。如果c的值是(cons 3 4)，那么c实际上是这样一个函数(λ [f] (f 3 4))，这个函数接收一个函数f作为参数，返回值是以参数[3, 4]调用f的结果。接下来看car，car实际上也是调用c，而这个实参是一个函数(λ [a, b] a)，这个函数接收两个参数，并且返回第一个参数。接下来我们把这个函数代入c，得到的是这样的一个表达式：((λ [f] (f 3 4)) (λ [a, b] a))，由于前面的(λ [f] (f 3 4))是操作符，将后面的实参代入并替换f过后就会得到：((λ [a, b] a) 3 4)，这样再进行一次实参代入，大家就很容易的能看出结果应该是3了。cdr也是一样的道理。

二逼实现

如果限定一下，cons的参数只能是非负整数，那么还可以用这样的方式来定义：(cons a b) --> 2^a * 3^b，即用2的a次方和3的b次方的乘积表示。那么只需要将cons结果对2和3进行质因子分界，就能得到car和cdr。

代码在这里：

cons.clj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

(defn cons
  [a, b]

  (defn sqr
    [x, n]
    (cond (= n 0) 1
          (= n 1) x
          (> n 1) (* x (sqr x (- n 1)))
          :else (throw (.IllegalArgumentException "wrong param"))))

  (* (sqr 2 a) (sqr 3 b)))

(defn factor
  [x, a]

  (defn iter
    [x, n]
    (if (= 0 (mod x a)) (iter (/ x a) (+ n 1))
        n))

  (iter x 0))

(defn car
  [c]
  (factor c 2))

(defn cdr
  [c]
  (factor c 3))

总结

cons的这几种实现方式体现的其实就是在Lisp中对数据进行抽象的方式。我们用的是完全过程化的方式，过程的这种使用方法和我们关于数据应该是什么样的直观认识大相径庭。

把过程当作对象去操作，这为我们提供了一种表示复杂数据的能力。

Comments