Marvin's Blog【程式人生】

Ability will never catch up with the demand for it

19 Sep 2020

The Little Schemer读书笔记(一)

《The Little Schemer》读书笔记(第一章、第二章)。

本书特点,采用对话的形式来引导阅读,希望读者能够自行给出对于所涉及概念的定义。但是书中还是列举了许多Laws和Commandments,也就是条例和戒律,来帮助读者记住相关原理。

在Scheme中,变量的数据类型被区分为两大类:atom(单体)和list(连结)。而list又可以为空,比如'()就是一个空list。使用null?可以判断一个变量的数据类型:

  • (null? 123) 返回#f
  • (null? '()) 返回#t
  • (null? '(123)) 返回#f

上面的结果基于ChezScheme。不过在本书中,假定null?是不能作用在atom上的,也就是(null? 123)必须抛出异常。

The Law of Null?: The primitive null? is defined only for lists.

另外,pair?可以用来判断是否是非空list:

  • (pair? 123) 返回#f
  • (pair? '()) 返回#f
  • (pair? '(123)) 返回#t

下面是书中对atom?的定义:

(define atom?
  (lambda (x)
    (and (not (pair? x)) (not (null? x)))))

也就是说不是pair以及非null的情况下,类型才会被判定为atom,也就是(atom? '())返回#f。如果你使用ChezScheme的话,会发现其返回的是#t。

你可以注意到采用'atom的方式在代码中标注atom,另一种方式是采用(quote atom)。因为scheme的语法非常简单,所以atom可以是除了(和’)以外的任意字符串。比如*abc$`。

指定list可以使用'(abc)或者(quote abc)等方式。

Scheme的基本结构是S-Expression,包含atom,空list,以及非空list。

car是一个作用于非空list的操作,它给出list的第一个节点。list的节点是一个pair,空list没有节点,所以car会出错。

The Law of Car: The primitive car is defined only for non-empty lists

和car对应的操作叫做cdr,它给出的是list第一个节点之后的所有节点,所起它返回的还是一个list。同样的,cdr在空list上会出错。对于只有一个节点的list,cdr返回的是空list。

The Law of Cdr: The primitive cdr is defined only for non-empty lists. The cdr of any non-empty lists is awalys another list.

car和cdr这两个操作其实是一个操作的两面,这个操作都是把一个atom从一个list中分离出来,car返回的是这个atom,而cdr返回的是除去这个atom之后的list。有分离就有合并,下面要介绍的cons操作就是把一个atom合并到一个list中去。比如(const 'a '(b c))就是把a这个atom,合并到(b c)这个list中去,生成的结果是(a b c)这个list。

不过cons的第一个参数不但可以是atom,也可以是list。比如(cons '(a) '(b c))的返回结果是((a) b c)。简单地说,cons操作需要两个参数,第一个参数是任意S表达式,第二个参数是一个list。cons所做的其实是生成一个新的list节点,然后把cons的第一个参数作为新节点的顶部,然后第二个参数作为新节点的尾部。

The Law of Cons: The primitive cons take two arguments. The second argument to cons must be a list. The result is a list.

书中还提到了eq?操作,用来对比两个S表达式是否相等。不过书中好像把它的操作对象限定为非数字的atom。但实际在ChezScheme里面,其参数可以是任意类别。

The Law of Eq?: The primitive eq? takes two arguments, Each must be a non-numeric atom.

接下来的一个练习是实现lat?lat?是list of atom?的所写,输入参数是一个list,如果list的每个节点都是atom,则输出结果是#t,否则输出结果是#f。在边界条件,也就是list为空的情况下lat?也返回#t。

下面是lat?的定义:

 (define lat?
    (lambda (l)
      (cond
        ((null? l) #t)
        ((atom? (car l)) (lat? (cdr l)))
        (else #f))))

简单地说,lat?每次从输入的list上取下一个节点,如果节点元素是一个list,那么中止并返回#f,否则一直进行到list结束,然后返回#t。上面的代码中:

  • cond用来提问并根据答复来进行分支操作
  • lambda创建一个函数
  • define给函数赋予一个名字

书中对lat?的描述:

(lat? l) looks at each item in its argument to see if it is an atom. If it runs out of items before it finds a list, the value of (lat? t) is #t. If it finds a list, as it did in the example (bacon (and eggs)), the value of (lat? l) is #f.”

书中定义的第二个函数叫做member?,用来发现某个atom是否在一个lat中。member?的定义如下:

> (define member?
    (lambda (a lat)
      (cond
        ((null? lat) #f)
        (else (or (eq? (car lat) a) (member? a (cdr lat)))))))

接下来书中给出了第一个戒律:

The First Commandment: Always ask null? as the first question in expressing any function.

(本篇完)

comments powered by Disqus