读EOPL3第一章(可归纳的数据集)

最近在看《Essentials of Programming Language》第三版，做些总结。看的是英文版，翻译如有不足还请指出。 正如在前言里提到：第一章重点阐述了可归纳的数据和递归的程序之间的关系，还介绍了一些变量作用域的概念。

第一章先介绍了一些方法来定义“可递归的数据集”，比如，如果想定义自然数N={0,1,2,…}的一个特定子集S,可以用下面的三种形式：

;自上而下的方式(top-down)
自然数n属于S当且仅当：
1. n = 0, or
2. n − 3 ∈ S.

;自下而上的方式(bottom-up)
定义集合S是包含于N的最小的集合，并且满足如下两个条件：
1. 0 ∈ S, and
2. if n ∈ S, then n + 3 ∈ S.


;推理的方式(rules of inference)
------
0 ∈ S


n ∈ S
---------
(n + 3) ∈ 

同理，如果要定义scheme里的一个整数集列表List-of-Int，可以这样定义：

;top-down
一个列表是一个整数列表当且仅当：
1. 它是一个空列表, 或者
2. 它由两部分组成，第一部分是整数，第二部分是一个整数列表

；bottom-up
这个整数列表是最小的scheme列表，满足如下两个条件
1. () ∈ List-of-Int, and
2. if n ∈ Int and l ∈ List-of-Int, then (n . l) ∈ List-of-Int.

;rules of inference

() ∈ List-of-Int


n ∈ Int  l ∈ List-of-Int
--------------------------
(n . l) ∈ List-of-Int


(注：当我学会如何正确输入数学符号再来改写这边的格式吧;))

上面的这种定义的方式很直接，为了简化书写，引入了定义数据集的语法，比如定义Scheme里的一个整数集的列表list-of-Int，可以用如下的语法：

List-of-Int ::= ()
List-of-Int ::= (Int . List-of-Int)

;或者简化成
List-of-Int ::= ()
            ::= (Int . List-of-Int)


;或者再简化成
List-of-Int ::= () | (Int . List-of-Int)


;另一种写法
List-of-Int ::= ({Int}∗ )

定义的其它类型的数据集：

;(s-list, s-exp)
S-list ::= ({S-exp}∗ )
S-exp  ::= Symbol | S-list
;或者也可以这么定义
S-list ::= ()
       ::= (S-exp . S-list)
S-exp ::= Symbol | S-list



;(binary tree)
Bintree ::= Int | (Symbol Bintree Bintree)


;(lambda expression)
LcExp ::= Identifier
      ::= (lambda (Identifier) LcExp)
      ::= (LcExp LcExp)

看这部分的时候让我想起了高中时候学递归证明的思想：当要证明一个定理或推论时，可以分成两步，先证明在一些简单的或者极端的或者说边缘的条件下成立（比如当n=0时成立），再证明，如果n=x时成立的话n=x+1也成立。

写递归的程序思路和递归证明命题的思路相似：将问题缩小成更小的相同的问题，然后可以调用程序来递归处理。 比如要求一个列表的长度，可以转化为“求列表除去第一个元素的长度＋1”：

list-length : List → Int
usage: (list-length l) = the length of l
(define list-length
  (lambda (lst)
    (if (null? lst)
        0
    (+ 1 (list-length (cdr lst))))))

比如要求一个列表第n个元素是什么，可以转化为“求除去第一个元素后余下的列表第n-1个元素是什么”

nth-element : List × Int → SchemeVal
usage: (nth-element lst n) = the n-th element of lst
(define nth-element
  (lambda (lst n)
    (if (null? lst)
        (report-list-too-short n)
    (if (zero? n)
        (car lst)
        (nth-element (cdr lst) (- n 1))))))

(define report-list-too-short
  (lambda (n)
    (eopl:error ’nth-element
      "List too short by ~s elements.~%" (+ n 1))))

有时候对于互相依赖的递归的数据结构，比如s-list，可能要写两个对应的递归的程序来处理会比较容易理解（一个可以） 比如要替换一个s-list中的b为a，

;采用这个定义：
S-list ::= ()
       ::= (S-exp . S-list)
S-exp ::= Symbol | S-list


subst : Sym × Sym × S-list → S-list
(define subst
  (lambda (new old slist)
    (if (null? slist)
        ’()
    (cons
      (subst-in-s-exp new old (car slist))
      (subst new old (cdr slist))))))



subst-in-s-exp : Sym × Sym × S-exp → S-exp
(define subst-in-s-exp
  (lambda (new old sexp)
    (if (symbol? sexp)
        (if (eqv? sexp old) new sexp)
    (subst new old sexp))))

你可能已经注意到了，递归的程序结构是依赖定义的语法的机构的。

有时候，想将问题简化为小些的问题时，会发现不是那么容易，可能需要用到所谓的“环境参数”，比如将list: (a b c d …) 转化为((0 a) (1 b) (2 c) …)，需要借助环境参数比如“0"会更方便。这时候可以写一个辅助程序接受一个list和n生成((n a) (n+1 b) (n+2 c) …)，然后写我们需要的程序时调用这个辅助程序并给上环境参数n=0就可以了：

;辅助程序
number-elements-from : Listof(SchemeVal) × Int → Listof(List(Int, SchemeVal))
usage: (number-elements-from ’(v0 v1 v2 ...) n) = ((n v0 ) (n + 1 v1 ) (n + 2 v2 ) ...)
(define number-elements-from
  (lambda (lst n)
    (if (null? lst) ’()
        (cons
      (list n (car lst))
      (number-elements-from (cdr lst) (+ n 1))))))

;我们想写的程序
number-elements : List → Listof(List(Int, SchemeVal))
(define number-elements
  (lambda (lst)
    (number-elements-from lst 0)))

从第一章中可以看到递归处理问题能力的强大，以及数据结构的描述和写出来的程序间的联系。然而第一章比较核心的还是它的习题部分，无奈等我学一下科学的输入符号再附上有意思的习题吧:) EOF