SCHeng

It all returns to nothing.

python, scheme, sicp

SICP回顾:cons函数、使用过程定义数据结构(上)

scheng

最近在使用python完成SICP2.2部分的一些经典例题,因为在我看来使用不同的语言来完成一件相同的事情能够加深印象和理解。用python实现例题的部分也会再写成一篇文章,但是这里遇到了一些问题,需要先记录一下。

首先是我对2.2节的感悟:构造一个复杂的东西,是需要许多模块进行组合的。这些模块也可以进行拆分,但是拆分到最底层的某些部分,这些部分的构造一定是简单又正确的。(看上去是一句废话,但是要把一个东西构造成简单但是又正确的,还是比较困难的一件事情)

2.2节的最简单又正确的构造就是三个基本的函数conscarcdr,他们是那么简单,但是我又无法使用python将他们用一种优雅的方式构造出来。

到底是用python的元组来构造scheme的list,还是用python的列表来构造scheme的list,我没有进行深究,我认为这两种数据结构的效果是类似的。

第一次尝试

我打算用python现成的数据结构来表达scheme的list,那么conscarcdr也是要基于这种数据结构来进行编写的。

def car(tuple_parameter):
    try:
        return tuple_parameter[0]
    except (TypeError, IndexError):
        return None

def cdr(tuple_parameter):
    try:
        return tuple_parameter[1::]
    except(TypeError, IndexError):
        return None

def cons(tuple1, tuple2):
    if (type(tuple1) != tuple):
        tuple1 = (tuple1,)
    if (type(tuple2) != tuple):
        tuple2 = (tuple2,)
    return tuple1 + tuple2

这样的构造在不嵌套元组操作的时候看上去是对的,比如说c = cons(1,2)这样的操作会得到c=(1,2);但是如果进行嵌套元组操作,就会出错,比如说c=cons((1,2,3),(4,5,6)),我们期望得到的是类似c=((1,2,3),(4,5,6))这样的结构,但是输出结果是c=(1,2,3,4,5,6)。这样的构造是不行的。

第二次尝试

我改变了cons的构造,然后整体呈现是

def is_null(item):
    return item == ()

def car(tuple_parameter):
    try:
        return tuple_parameter[0]
    except (TypeError, IndexError):
        return ()

def cdr(tuple_parameter):
    try:
        return tuple_parameter[1::]
    except(TypeError, IndexError):
        return ()

def cons(tuple1, tuple2):
    return (tuple1,tuple2)

但是这样构造的输出比较丑,我得把元组写成a = (1,(2,(3,(4,()))))这种形式,等价于scheme里面(define a (list 1 2 3 4)),不过后续的部分操作都是对的。使用accumulate函数稍稍验证一下:

def accumulate(op, init, seqs):
    if is_null(seqs):
        return init
    return op(car(seqs), accumulate(op, init, cdr(seqs)))

accumulate(cons, (), a)
accumulate(add, 0, a)

def add(num1, num2):
    return num1 + num2

如果硬要把元组写成a=(1,2,3,4)这种格式,会出一点问题….使用accumulate(cons, (), a)看一下就明白了,会变成(1, (2, (3, (4, ()))))这样的格式。显然的,a=(1,2,3,4)这种形式要比(1, (2, (3, (4, ()))))看上去美观多了。

但是在scheme却不会出现这种情况,比如说对一个list进行操作:

(define a (list 1 2 3 4))
accumulate(cons, '(), a')

最终的输出仍然是(1 2 3 4),所以我推测应该是list与cons的实现存在问题。cons的实现并不是如同我上面那样构造的,或者说当cons应用在list上时呈现效果会有变化。不过更加具体的分析我还没有想好。还有一件更加奇怪的事情。

当我们去嵌套地调用cons函数时,出现的效果是这样的:

(define a (list 1 2 3))
(define b (list 4 5 6))
(cons a b ) = ((1 2 3 4) 4 5 6)

我将它描述为“b嵌套了a”或者”a被b嵌套了”。

但是当我去使用一个函数,情况就发生了变化:

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init (car-n seqs))
        (accumulate-n op init (cdr-n seqs)))))

(define (car-n seqs)
  (map car seqs))

(define (cdr-n seqs)
  (map cdr seqs))
(load "accumulate.scm")

(define sequence (list (list 1 2 3)
               (list 4 5 6)
               (list 7 8 9)
               (list 10 11 12)))

(accumulate-n cons '() sequence')

最后一行的效果是向list1进行一个矩阵翻转。

car-n的结果是生成一个list,然后通过accumulate-n将他们都链接起来,链接的方法是cons,但是最后输出的是((1 4 7 10) (2 5 8 11) (3 6 9 12)),并不是嵌套情况!前面举例的那个方法也是两个list通过cons方法链接起来,但是呈现结果是嵌套的。

我就开始猜想是不是因为scheme会根据数据结构的不同来选择不一样的链接方案?比如两个list链接就是类似链表的一种链接,而第二个例子因为已经指明了原本的数据结构是一个list,所以cons的链接方案仍然是list形式的。

我觉得在没有具体了解cons在scheme里面的实现,是无法得到正确的结论的。

所以对于python直接使用现成数据结构构造cons,我目前只能达到这个阶段了。更深层的内容需要更加了解函数式构造方法后再来补充。现在只能用这种丑陋的方法继续完成sicp例题了。

第三次尝试,使用过程构造数据结构

既然都在构造cons了,不如回顾一下p61提到的使用过程构造cons。

在我之前的尝试里面,cons理所当然地应该是一种数据结构,但是sicp个给了一种方法使他能够被函数构造出来。

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
      ((= m 1) y)
      (else (error "Argument not 0 or 1 -- CONS" m))))
  dispatch)

(define (car z) (z 0))

(define (cdr z) (z 1))

以及python

def cons(x, y):
    def dispatch(m):
        if m == 0:
            return x
        elif m == 1:
            return y
        else:
            print("Argument not 0 or 1 -- CONSS")
    return dispatch

def car(z):
    return z(0)

def cdr(z):
    return z(1)

这里定义的cons car cdr等都是过程,cons本质上是一个数据结构。

当使用cons对两个数据进行组合的时候,返回的是一个函数:

cons(1,2)

<function cons.<locals>.dispatch at 0x7feab94bb550>

cons((1,2,3),(4,5,6))

<function cons.<locals>.dispatch at 0x7feab94bb700>

当对被构造出来的这种结构使用car、cdr时,会根据情况来返回值。

a = cons((1,2,3,4), (5,6,7,8))
b = cons((11,12,13),a)
car(a)
car(b)
cdr(a)
cdr(b)

前面三种查询都是返回元组本身,也就是可以直接查看到值的结果,但是第四个返回的是<function cons.<locals>.dispatch at 0x7feab94bb700>,因为相当于直接查看a了,a的构造实际上是一个函数。

其实将被构造出来的这些数据带入car、cdr、cons函数并不难理解,这又让我想起来了经典的例题2.6,同样的2.6是使用过程“重新定义”了数字,这里是用过程重新定义cons的数据结构。

其实还有一些问题,不过我已经找到较为优雅的方法了,请看我的下一篇文章

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注