流水沉微

第一章 归纳的数据集

本章介绍了一些基本的编程工具,这些工具在后续编写解释器(interpreters)、检查器(checkers)和类似组成编程语言核心处理器(processor)之类的程序的时候需要用到

由于一门语言中的语法(syntax)通常都是嵌套(nested)或者树状结构(treelike structure),故递归在我们将使用的技术中将占据核心位置。第1.1节和第1.2节介绍了用归纳法来描述(specify)数据结构的方法,并揭示了这种描述方法将如何指导我们编写递归的程序。第1.3节阐述了如何将该方法扩展到更加复杂的问题中。最后,本章将以大量的练习作为结尾,这些练习才是本章的核心内容,他们将为你提供足够的经验,去掌握递归编程的思想(the technique of recursive programming),而这思想,正是本书其他部分的基石。

1.1 递归得描述(specified)数据

为一个过程(procedure)编写代码时,我们必须准确得知道该过程的参数的类型、以及该过程的返回值的类型。通常这些值都是复杂类型。在本节,我们将介绍描述这些值的一般方法。

1.1.1 归纳描述法(Inductive Specification)

归纳描述法 是一个描述数据的有力方法。为了展示这一点,我们将用它来描述自然数\(N={0,1,2,...}\)的一个真子集\(S\)

定义1.1.1
自然数\(n\)属于集合\(S\),当且仅当
  1. \(n=0\),或者
  2. \(n-3 \in S\)

让我们看看如何使用这个定义来决定哪些自然数属于集合\(S\),我们知道\(0 \in S\),那么\(3 \in S\),因为\((3-3)=0\)\(0 \in S\)。类似可知\(6 \in S\),因为\((6-3)=0\)\(3 \in S\)。将该推演过程继续下去,我们可以得到结论:所有的\(3\)的倍数都属于集合\(S\)

那么其他的自然数呢?\(1 \in S\)是否成立呢?我们知道\(1 \ne 0\),因此不满足条件1;此外\((1-3)=-2\),这不是一个自然数也就不属于集合\(S\),因此不满足条件2。故\(1\)不满足任何一个条件,\(1 \not \in S\),类似的,\(2 \not \in S\)。那么\(4\)呢?\(4 \in S\)只有在\(1 \in S\)成立的情况下成立,但是\(1 \not \in S\),所以\(4 \not \in S\)。类似地,我们可以得到这样的结论:如果\(n\)是一个自然数且它不是\(3\)的倍数,那么\(n \not \in S\)

以上讨论可以得到结论:\(S\)是这样的自然数的集合:\(3\)的倍数

我们可以用这个定义来写一个判断自然数\(n\)是否属于集合\(S\)的过程(procedure)

in-S? : N -> Bool
usage: (in-S? n) = #t if n is in S, #f otherwise

(define in-S?
    (lambda (n)
        (if (zero? n) #t
            (if (>= (- n 3) 0)
                (in-S? (- n 3))
                #f))))

这里我们根据定义用Scheme写了一个递归过程。其中in-S? : N -> Bool是一个批注(comment),称为该过程的契约(contract) ,它表示in-S?被设计为这样一个过程:以一个自然数作为入参并产生一个布尔值作为出参。这样的批注对读写代码都是很有帮助的

为了判断\(n \in S\)是否成立,我们首先判断\(n=0\)是否成立,如果后者成立,则前者也成立。否则我们需要看\(n-3 \in S\)是否成立,为了判断\(n-3 \in S\)是否成立,我们先要检查\((n-3) \ge 0\)是否成立。如果成立的话,我们就可以使用我们已有的过程逻辑来判断它是否属于集合\(S\),如果不成立,那么\(n\)不可能属于集合\(S\)

下面是另一种集合\(S\)的定义

定义1.1.2
定义集合\(S\)为包含于自然数\(N\)且满足下列两个性质的最小集合:
  1. \(n \in S\),且
  2. 如果\(n \in S\),那么\(n+3 \in S\)

一个“最小集合”是指满足条件1和条件2且是任何满足条件1和条件2的集合的子集。很容易看出这样的集合只有一个:假设存在\(S_1\)\(S_2\)都满足条件1和条件2且都是最小集合,那么\(S_1 \subseteq S_2 \)(因为\(S_1\)是最小集合)且\(S_2 \subseteq S_1 \)(因为\(S_2\)也是最小集合),因此\(S_1=S_2\)。我们需要这个额外条件,否则会有许多集合满足以上两个条件(参见练习1.3)

另外还有一种定义的写法:

\(\dfrac{}{0 \in S}\qquad\)
\(\dfrac{n \in S}{(n+3) \in S}\qquad\)

这只是前面写法的一种简写形式,每一个条目称为一个“推演规则”,或者简称为一个“规则”,横线读作“如果…那么…”,横线上半部分称为“假设/先行词”,横线下半部分称为“结论/推断”。当存在两个以上假设时,他们之间默认用“且”连接(例如定义1.1.5)。没有假设的规则称为“公理”,通常,公理的横线会省略不写,比如:

\(0 \in S\)

该公理的意思是:自然数\(n\)在集合\(S\)中,当且仅当语句\(n \in S\)可以在有限次数内使用推演规则从公理推导出。这个解释天然得保证了集合\(S\)是在规则范围内闭合的所有集合里的最小集合

这些定义全都描述了同样的事。第一个版本我们称为「自上而下」法,第二个版本称为「自下而上」法,而第三个版本称为「推演规则」法,现在我们来试试将这些规则应用到其他例子

定义1.1.3 (整数数列,自上而下)
一个Scheme list是一个List-of-Int,当且仅当:
  1. 它是一个空数列,或者
  2. 它是一个car是整数、cdr是一个整数数列的序对(pair)

在这里我们使用Int表示全体整数的集合,用List-of-Int表示全部整数数列的集合

译者注:
关于序对(pair)、car、cdr可以阅读Pairs and lists - Revised(5) Scheme。以下关于简单的Scheme语法不再提示

接下来再看另一个定义

定义1.1.4 (整数数列,自下而上)
集合List-of-Int在满足以下两个条件时,就是最小的Scheme List集合
  1. \(() \in List-of-Int\),且
  2. 如果\(n \in Int\)\(l \in List-of-Int\),那么\((n . l) \in List-of-Int\)

这里我们使用占位符.来表示Scheme语言中cons操作的结果。(n . l)表示一个Scheme语言中的一个序对,在这个序对中,carncdrl

定义1.1.5 (整数数列,推演规则)
\(() \in List-of-Int\)
\(\dfrac{n \in Int \hspace{2em} l \in List-of-Int}{(n \hspace{.5em} . \hspace{.5em} l) \in List-of-Int}\qquad\)

这3个定义是相等的。我们接下来演示一下如何用他们来生成List-of-Int中的一些元素

  1. ()是一个整数列,因为它满足定义1.1.4的属性1或者是满足定义1.1.5的第一个规则
  2. (14 . ())是一个整数列,根据定义1.1.4的属性2可知,因为14是一个整数,而()是一个整数列,我们可以将这个推论写作是List-of-Int的第二条规则的一个实例
    \(\dfrac{14 \in Int \hspace{2em} () \in List-of-Int}{(14 \hspace{.5em} . \hspace{.5em} ()) \in List-of-Int}\qquad\)
  3. (3 . (14 . ()))是一个整数列,根据属性2可知,因为3是一个整数,而(14 . ())是一个整数列,我们也可以将这个推演过程写作List-of-Int的第二条规则的一个实例
    \(\dfrac{3 \in Int \hspace{2em} (14 \hspace{.5em} . \hspace{.5em} ()) \in List-of-Int}{(3 \hspace{.5em} . \hspace{.5em} (14 \hspace{.5em} . \hspace{.5em} ())) \in List-of-Int}\qquad\)
  4. (-7 . (3 . (14 . ())))是一个整数列,根据属性2可知,因为-7是一个整数,而(3 . (14 . ()))是一个整数列,这次我们同样将这个推演过程写作List-of-Int的第二条规则的一个实例
    \(\dfrac{-7 \in Int \hspace{2em} (3 \hspace{.5em} . \hspace{.5em} (14 \hspace{.5em} . \hspace{.5em} ())) \in List-of-Int}{(-7 \hspace{.5em} . \hspace{.5em} (3 \hspace{.5em} . \hspace{.5em} (14 \hspace{.5em} . \hspace{.5em} ()))) \in List-of-Int}\qquad\)
  5. 如果一个数列也是这样构建的话,那就是一个整数列

将上面的点表示法转换成列表表示法,可以看到()(14)(3 14)(-7 3 14)都包含于List-of-Int。我们也可以将规则全部合起来,得到整个\((-7 \hspace{.5em} . \hspace{.5em} (3 \hspace{.5em} . \hspace{.5em} (14 \hspace{.5em} . \hspace{.5em} ()))) \in List-of-Int\)因果链的全景图。下面这个树状图被称为派生树或者演绎树

\(\begin{align} 14 \in N \hspace{2em} () &\in List-of-Int \\ \rule{3.5cm}{.6pt} & \rule{3.5cm}{.6pt} \\ 3 \hspace{.5em} . \hspace{.5em} (14 \hspace{.5em} . \hspace{.5em} ())) &\in List-of-Int \\ \rule{6cm}{.6pt} & \rule{3.5cm}{.6pt} \\ -7 \in N \hspace{2em} (3 \hspace{.5em} . \hspace{.5em} (14 \hspace{.5em} . \hspace{.5em} ())) &\in List-of-Int \\ \rule{6cm}{.6pt} & \rule{3.5cm}{.6pt} \\ (-7 \hspace{.5em} . \hspace{.5em} (3 \hspace{.5em} . \hspace{.5em} (14 \hspace{.5em} . \hspace{.5em} ()))) & \in List-of-Int \end{align}\)
练习1.1 [*]
写出下列集合的归纳法定义。每个定义都要写3种类型(自上而下,自下而上,推演规则),并使用你所写的规则,举出每个集合的示例数据
  1. \({3n+2 \hspace{.5em} | \hspace{.5em} n \in N}\)
  2. \({2n+3m+1 \hspace{.5em} | \hspace{.5em} n,m \in N}\)
  3. \({(n,2n+1) \hspace{.5em} | \hspace{.5em} n \in N}\)
  4. \({(n,n^2) \hspace{.5em} | \hspace{.5em} n \in N}\) 不要在定义的规则中使用平方,一点小提示,想想这个方程 \((n+1)^2 = n^2+2n+1 \)
练习1.2 [**]
根据以下规则分别可以得到什么样的集合?并阐述理由
  1. \((0,1) \in S \hspace{3em} \dfrac{(n, k) \in S}{(n+1,k+7) \in S}\qquad\)
  2. \((0,1) \in S \hspace{3em} \dfrac{(n, k) \in S}{(n+1,2k) \in S}\qquad\)
  3. \((0,0,1) \in S \hspace{3em} \dfrac{(n, i, j) \in S}{(n+1,j,i+j) \in S}\qquad\)
  4. [***] \((0,1,0) \in S \hspace{3em} \dfrac{(n, i, j) \in S}{(n+1,i+2,i+j) \in S}\qquad\)
练习1.3 [*]
找到满足以下条件的自然数集合T
  1. \(0 \in T\)
  2. 对任何\(n \in T\),都有\(n+3 \in T\)
  3. \(T \neq S\),其中\(S\)是定义1.1.2中的集合

1.1.2 用语法(Grammars)定义集合

之前的例子非常的直观,但是很容易想象到,在处理更复杂的数据类型的时候,描述过程会变得相当的笨重。为了作出改进,我们将展示如何用语法来描述集合。语法一般常用于描述字符串集合,但我们同样能用它来定义数值集合。比如我们可以用如下语法来定义\(List-of-Int\)

\(\begin{align} List-of-Int &::= () \\ List-of-Int &::= (Int \hspace{.5em} . \hspace{.5em} List-of-Int) \end{align}\)

由于定义1.1.4有两个属性,对应得这里有两条规则。第一条规则意味着空数组包含于List-ofInt,第二条规则说明了如果n在集合Int中、l在集合List-of-Int中,那么(n . l)在集合List-of-Int中,这两条规则的组合被称为一个语法

现在我们来仔细看看语法的定义,在定义中有如下元素:

  • 非终结性符号:非终结性符号是指那些被定义的集合的名字。在上面的例子中只有一个这样的集合,但通常来说,一般都会有好几个被定义的集合,这些集合有时候也被称为句法范畴。方便起见,我们约定对集合和非终结性符号的名字使用大写名字,在引用他们中的元素时使用小写名字。听起来很复杂但是一看例子就明白了,比如:\(Expression\)是 非终结的,所以我们写作\(e \in Expression\)或者e is an expression. 另一种惯用约定是巴科斯范式(Backus-Naur Form),或者简称BNF,写法是在单词两端写箭头,比如:\(<expression>\)

  • 终结性符合:比如以下符合:. ( ),一般会用等宽字体来写,比如lambda

  • Production:一条规则就是一个production(产品)。每个production分为左右两侧,左侧是一个非终结性符合,右侧是终结性符号和非终结性符号。左右两侧由符号::=分隔,读作。右侧内容阐明了根据其他句法范畴和终结性符号(比如左括号、右括号和句号)来构造句法范畴成员的方法

有时候,如果从上下文中已经可以得到足够清晰的意义,production中的部分句法范畴也会不进行定义,比如Int

语法经常会用使用符号缩写进行编写。如果一个production的左侧内容跟上一个production的左侧内容一致,推荐直接把左侧内容省略,比如:

\(\begin{align} List-of-Int &::= () \\ &::= (Int \hspace{.5em} . \hspace{.5em} List-of-Int) \end{align}\)

也可以只写一次::=,用一个特殊的|符号将右侧的两行内容分隔,比如:

\(\begin{align} List-of-Int ::= () \hspace{.5em} | \hspace{.5em} (Int \hspace{.5em} . \hspace{.5em} List-of-Int) \end{align}\)

还有一种缩写形式叫Kleene star(克林星),用\(\{...\}^*\)符号来表示