Published: 2016-01-04

读EOPL3第二章(Data Abstraction)

Table of Contents

1 概述

第二章讲述了数据抽象（data abstrction）的概念，通过将数据集分成interface（交互接口）和implementation（具体实现）来对数据进行抽象，这样的好处是可以是写的代码不依赖于数据集具体的实现。

2 通过交互接口(Interface)来表述数据

通过Data Abstraction的方式，将数据的表示分成Interface和Implementation，这样的好处是当需要更换数据的实现方式时，只要改写对应interface的实现方式，而不需要改写采用这些Interface的代码（client code），使得具体的client code不依赖于数据的表现形式 (representation-independent)。比如，当我们写程序来操作文件时采用的open,read,write,close等方法，这些方法可以看成是interface，我们具体写的代码通过操作这些interface来完成相应的操作，如果文件的实现形式更改了，我们只需改写这些相应的open,read,write,close而不用改写具体的client code

2.1 举个具体的例子，我们想要描述“自然数”这个数据集，interface可以是：=zero=,=is-zero?=,=successor=,=predecessor=，如果用$⌈ v ⌉$来指代数据v的表现形式的话，interface的实现需要满足下面条件：

\begin{align*} (zero) &= \lceil 0 \rceil \\ (is-zero? \lceil n \rceil) &= \begin{cases} \#t, & \text{n=0} \\ \#f, & \text{n $\neq$ 0} \end{cases} \\ (successor \lceil n \rceil) &= \lceil n+1 \rceil (n\geq 0) \\ (predecessor \lceil n+1 \rceil) &= \lceil n \rceil (n\geq 0) \end{align*}

这样当我们写程序的时候就可以使用这些interface来操作自然数集，比如定义加法： 

(define plus
  (lambda (x y)
    (if (is-zero? x)
        y
        (successor (plus (predecessor x) y)))))

不管interface的是怎么实现的，加法总是可以这样定义。其中用来构造数据类型的interface叫做constructors（上面例子中的｀zero｀，｀successor｀，｀predecessor｀），从数据值里提取信息的叫observers（上面例子中的｀is-zero?｀）。 而interface怎么实现取决于数据以怎样的方式表示：

  1. 一元表示的方法（Unary representation） 一元表示法可以这么定义：

    ⌈ 0 ⌉ = ()
    ⌈ n+1 ⌉ = (\#t \;.\; ⌈ n ⌉)

    在这种表示法下，上述自然数的interface可以这么定义： 

    (define zero (lambda () ’()))
(define is-zero? (lambda (n) (null? n)))
(define successor (lambda (n) (cons #t n)))
(define predecessor (lambda (n) (cdr n)))

  2. scheme　数字表示的方法（Scheme number representation） scheme　数字表示的方法　是用shceme中的整数n代表\(\lceil n \rceil\) 在这种表示法下，上述自然数的interface可以这么定义： 

    (define zero (lambda () 0))
(define is-zero? (lambda (n) (zero? n)))
(define successor (lambda (n) (+ n 1)))
(define predecessor (lambda (n) (- n 1)))

  3. 大数字表示法（Bignum representation） 大数字表示法可以这么定义：

    ⌈ n ⌉ =

    \begin{cases} (), &\text{n = 0}\\ (r \;.\; \lceil q \rceil), &\text{n = qN + r, 0 $\leq$ r $\leq$ N} \end{cases}

    按照这个定义，取N = 16， $⌈ 33 ⌉$　＝　(1 2), ⌈ 258 ⌉ = （2 0 1）， 因为\(258 = 2 \times 16^0 + 0 \times 16^1 + 1 \times 16^2\) 在这种表示法下，上述自然数的interface可以这么定义： 

(define N 10)

(define zero (lambda () '()))

(define is-zero? 
  (lambda (n) 
    (null? n)))

(define successor 
  (lambda (n) 
    (cond ((null? n) '(1)) 
    ((= (+ (car n) 1) N) (cons 0 (successor (cdr n)))) 
    (else (cons (+ (car n) 1) (cdr n))))))

(define predecessor 
  (lambda (n) 
    (cond ((null? n) (eopl:error'predecessor "zero.~%")) 
    ((zero? (car n)) (cons (- N 1) (predecessor(cdr n)))) 
    ((and (= (car n) 1) (null? (cdr n))) '()) 
    (else (cons (- (carn) 1) (cdr n))))))

3 两种表述数据类型的方法

通过数据类型：环境变量（environments）来说明，environments是是一个将变量和值绑定在一起的有限的数据集。环境变量可以以这样的形式表示\({(var_1,val_1),...,(var_n,val_n)}\).对应的interface需要满足以下条件：

\begin{align*} (empty-env) &= \lceil \theta \rceil \\ (apply-env \lceil f \rceil var) &= f(var) \\ (entend-env var v \lceil f \rceil) &= \lceil g \rceil ,\\ &where \; g(var1) = \begin{cases} v, & \text{if $\;var_1$ = var} \\ f(var_1), & \text{otherwise} \end{cases} \end{align*}

其中`empty-env`用来构造一个空的环境变量,`apply-env`用来获取环境变量中的值，`entend-env`用来扩充环境变量。 根据以上interface，一个环境变量可以如下构造： 

(define e (extend-env 'd 6 (extend-env 'y 8 (extend-env 'x 7
(extend-env 'y 14 (empty-env))))))

3.1 第一种表示：Data Structure Representation

根据environment的结构特征：每个environment可以从一个空的environment开始，用`extend-env`构造数次得到，所以每个环境变量可采用下面的语法表示：

#+ENDEXAMPLE lisp Env-exp :: = (empty-env) :: = (extend-env Identifier Scheme-value Env-exp)

#+ENDEXAMPLE

注意到这个表示和描述lists的语法是一样的，所以可以得到下面的实现（采用类似lists的实现）： 

Env = (empty-env) | (extend-env Var SchemeVal Env)
Var = Sym

empty-env : () → Env
(define empty-env
  (lambda () (list ’empty-env)))

extend-env : Var × SchemeVal × Env → Env
(define extend-env
  (lambda (var val env)
    (list ’extend-env var val env)))

apply-env : Env × Var → SchemeVal
(define apply-env
  (lambda (env search-var)
    (cond
      ((eqv? (car env) ’empty-env)
        (report-no-binding-found search-var))
      ((eqv? (car env) ’extend-env)
       (let ((saved-var (cadr env))
             (saved-val (caddr env))
            (saved-env (cadddr env)))
         (if (eqv? search-var saved-var)
             saved-val
             (apply-env saved-env search-var))))
      (else
         (report-invalid-env env)))))

(define report-no-binding-found
  (lambda (search-var)
    (eopl:error ’apply-env "No binding for ~s" search-var)))

(define report-invalid-env
  (lambda (env)
    (eopl:error ’apply-env "Bad environment: ~s" env)))

3.2 第二种表示：Procedural Representation

这种表示法将envrionment看成一个procedure, 给定一个var,得到一个val具体实现如下 

Env = Var → SchemeVal

empty-env : () → Env
(define empty-env
  (lambda ()
    (lambda (search-var)
      (report-no-binding-found search-var))))


extend-env : Var × SchemeVal × Env → Env
(define extend-env
  (lambda (saved-var saved-val saved-env)
    (lambda (search-var)
      (if (eqv? search-var saved-var)
          saved-val
          (apply-env saved-env search-var)))))

4 递归数据的interfaces

接下来看看如何得到interfaces，以lambda-calculus数据类型为例。 lambda-calculus可以采用如下定义： 

Lc-exp :: = Identifier
       :: = (lambda (Identifier) Lc-exp)
       :: = (Lc-exp Lc-exp)

Lc-exp :: = Identifier :: = (lambda (Identifier) Lc-exp) :: = (Lc-exp Lc-exp)

lambda-calculus的定义是采用递归的形式定义的，为了定义递归类型数据的interfaces，可以按照下面规则：

1.对每一个数据类型归纳一个constructor和predicate 2.对每一个传给constructor的参数归纳一个extractor

如此，可创建lambda-calculus的以下的interfaces: 

;The constructors are:
var-exp      : Var → Lc-exp
lambda-exp   : Var × Lc-exp → Lc-exp
app-exp      : Lc-exp × Lc-exp → Lc-exp

;The predicates are:
var-exp?     : Lc-exp → Bool
lambda-exp?  : Lc-exp → Bool
app-exp?     : Lc-exp → Bool

;The extractors are:
var-exp->var           :  Lc-exp → Var 
lambda-exp->bound-var  :  Lc-exp → Var
lambda-exp->body       :  Lc-exp → Lc-exp
app-exp->rator         :  Lc-exp → Lc-exp
app-exp->rand          :  Lc-exp → Lc-exp

然而，每次都这样创建interfaces会很枯燥，scheme里提供了一个自动构造和实现interfaces的工具，对于刚刚的interfaces可以如下创建： 

(define-datatype lc-exp lc-exp?
    (var-exp
        (var identifier?))
    (lambda-exp
        (bound-var identifier?)
        (body lc-exp?))
    (app-exp
        (rator lc-exp?)
        (rand lc-exp?)))

`define-datatype`依照如下格式：

(define-datatype type-name type-predicate-name
\;\;{ (variant-name { (field-name predicate) }*)}^+)

使用这个`define-datatype`定义的数据可以像下面这样使用： 

```
；判断lambda-calculus里是否存在某个symbol
occurs-free? : Sym × LcExp → Bool
(define occurs-free?
    (lambda (search-var exp)
        (cases lc-exp exp
            (var-exp (var) (eqv? var search-var))
            (lambda-exp (bound-var body)
                (and
                    (not (eqv? search-var bound-var))
                    (occurs-free? search-var body)))
            (app-exp (rator rand)
                (or
                    (occurs-free? search-var rator)
                    (occurs-free? search-var rand))))))
```

这里采用了 cases 来判断采用那种形式， cases 语法如下： 

(cases type-name expression
  { (variant-name ( { field-name }*) consequent) }*
  (else default))

define-datatype 提供了定义递归数据类型的一种选择，但不是唯一的方式。有时候根据特定情况可以定义一个更有效的形式，代价是需要手动实现这些interface的程序。

5 抽象语义和它的表现形式（Abstract Syntax and Its Representation）

语法一般规定了表达形式，通常是通过字符串和值来表示。这样的表现形式称为“具体的语义（concrete syntax）”或者“外部表现（external representation）”，比如lambda-calculus的定义： 

Lc-exp :: = Identifier
       :: = (lambda (Identifier) Lc-exp)
       :: = (Lc-exp Lc-exp)

lambda-calculus 也可以采用另外一种外部表现： 

Lc-exp :: = Identifier
       :: = proc Identifier => Lc-exp
       :: = Lc-exp(Lc-exp)

这些“外部表现”是便于人类识别的，但对于计算机来说，更具有意义的是“抽象语义（Abstract Syntax）”或者叫做“内部表现（interal representation）”，抽象语义去除了不包含实际信息的符号。像之前定义的=define-datatype=提供了一种方便的方法来定义这种内部表现。 对于表达式=(lambda (x) (f (f x)))=的abstract syntax可以用下图表示： ast-example.png

将具体语义和抽象语义互相转化是非常有意义的。如果具体语义是字符串，这个转化的过程称为解析（parsing），借助于解析器（parser）。通常写一个parser是很复杂的，我们可以借助一个parser generator来生成一个parser。如果具体语义是以一串列表给定的，解析过程会简单许多。

比如，对于lambda-calculus，在scheme中，像前面说的用 define-datatype 来定义那样,shceme read routine自动解析字符串成=lists=和=symbols=，然后转化为abstract syntax　会容易很多，像下面这个程序这样： 

parse-expression : SchemeVal → LcExp
(define parse-expression
    (lambda (datum)
        (cond
            ((symbol? datum) (var-exp datum))
            ((pair? datum)
                (if (eqv? (car datum) ’lambda)
                    (lambda-exp
                        (car (cadr datum))
                        (parse-expression (caddr datum)))
                    (app-exp
                        (parse-expression (car datum))
                        (parse-expression (cadr datum)))))
                (else (report-invalid-concrete-syntax datum)))))

而将抽象语义转化成具体语义会直观很多，比如将lambda-calculus的抽象语义转化成列表形式的具体语义，可以用下面的程序： 

unparse-lc-exp : LcExp → SchemeVal
(define unparse-lc-exp
    (lambda (exp)
        (cases lc-exp exp
            (var-exp (var) var)
            (lambda-exp (bound-var body)
                (list ’lambda (list bound-var)
                    (unparse-lc-exp body)))
            (app-exp (rator rand)
                (list
                    (unparse-lc-exp rator) (unparse-lc-exp rand))))))

Author: Nisen

Email: imnisen@163.com