数据抽象引导

数据抽象的基本思想，就是设法构造出一些使用复合数据对象的程序，使它们就像是在“抽象数据”上操作一样。 也就是说，我们的程序中使用数据的方式应该是这样的，除了完成当前工作所必要的东西之外，它们不对所使用的数据做任何多余的假设。 与此同时，一种“具体”数据表示的定义，也应该与程序中使用数据的方式无关。

这里，这样的两个部分之间界面将是一组过程，称之为选择函数和构造函数，它们在具体表示之上实现抽象的数据。

为了展示这一技术，下面考虑怎样通过已给定线段得到中点的过程。

实例：线段中点的计算

作为开始，假定已经有了一种根据两个点构造一个线段的方法。并进一步假定，如果有了一个线段，有一种方法取得它的两个起点和终点。再者，假定如果有了一个点，有一种方法取得它的坐标。现在再假设有关的构造函数和选择函数都可以作为过程使用：

(make-segment b e) 返回一个线段，起点是b，终点是e
(start-segment seg) 返回线段seg的起点
(end-segment seg) 返回线段seg的终点
(x-point point) 返回点point的$x$坐标
(y-point point) 返回点point的$y$坐标

现在还没有说明一个线段如何表示，也没有说过程start-segment、end-segment以及make-segment如何实现。然而，如果我们有了这几个过程，那么就可以根据如下的关系去计算给定线段的中点了

$$ x_m = \frac{x_2 + x_1}{2} \\ y_m = \frac{y_2 + y_1}{2} $$

可以将这个规则表述为一下过程

(define (midpoint-segment seg)
  (cons
   (/ (+ (x-point (start-segment seg)) (x-point (end-segment seg))) 2)
   (/ (+ (y-point (start-segment seg)) (y-point (end-segment seg))) 2)))

这样，在有了选择和构造过程start-segment、end-segment等的基础之上，写出了计算重点之的过程，虽然这些基础还没有定义。。。

序对

为了在具体成面上实现线段这一数据抽象，这里使用语言提供的*序对*复合结构，这种结构可以通过cons构造出来。同时，如果给了一个序对，可以用基本过程car和cdr按如下方式提取出其中的各个部分:

(define x (cons 1 2))
(car x)
1
(cdr x)
2

注意，序对也是一个数据对象，可以像基本数据对象一样给它一个名称且操作它。

(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))
(car (car z))
1
(cdr (cdr z))
4

线段的表示

序对为完成这里的线段提供了一种自然的方式，可以通过将线段表示为两个点的序对。这样就很容易作出上面的基础过程的实现：

;; constructor
(define (make-point x y)
  (cons x y))

;; selectorl
(define (x-point p)
  (car p))

(define (y-point p)
  (cdr p))

;; constructor
(define (make-segment p1 p2)
  (cons p1 p2))

;; selector
(define (start-segment seg)
  (car seg))

(define (end-segment seg)
  (cdr seg))

现在可以试验求中点的过程了:

;; display
(define (print point)
  (newline)
  (display "(")
  (display (x-point point))
  (display ", ")
  (display (y-point point))
  (display ")"))

(print (midpoint-segment (make-segment (make-point 1 3) (make-point 6 2))))

(7/2, 5/2)

抽象屏障

一般而言，数据抽象的基本思想就是为每一类数据对象标识出一组操作，使得对这类数据对象的所有操作都可以基于它们表述，而且在操作这些数据对象时也只使用它们。

下图形象化的表示了线段系统的结构。其中的水平线表示*抽象屏障*，它们隔离了系统中不同的层次。在每一层上，这种屏障都把使用数据的程序（上面）与实现数据抽象的程序（下面）分开来。拿序对来说明，就是：只要序对可以通过cons、car和cdr操作，有关序对如何实现的细节与点和线段部分都是完全没有关系的。从作用上来看，每一层次中的过程构成了所定义的抽象屏障的界面，联系起系统中的不同层次。

abstract_barrier

这一简单的思想有许多优点。最明显的优点是这种方法使程序很容易维护和修改。

数据意味着什么

那么，*数据*究竟以为着什么？说它就是“由给定的构造函数和选择函数所实现的东西”还是不够的。同样，拿序对来说。前面从来没有提到过序对究竟是什么，只说是语言为序对提供了三个过程cons、car和cdr。有关这三个操作，需要知道的全部东西就是，如果cons将两个对象粘接到一起，那么就可以通过car和cdr取出这两个对象。前面确实说过这三个过程是所用语言里的基本过程（实际为list结构）。然而，任何能满足上述条件的三个过程都可以成为实现序对的基础。甚至，可以完全不用数据结构，只使用过程就就可以实现序对：

(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))

过程的这一使用方式与我们有关数据应该是什么的直观认识大相径庭。但不管怎么说，序对的这一过程实现确实是一个合法的实现，如果只通过cons、car和cdr访问序对，我们将无法把这一实现与“真正的”数据结构去分开。这一实例也说明可以将过程作为对象去操作，因此就自动地为我们提供了一种表示复合数据的能力。这些东西现在看起来好像只是很好玩，但实际上，数据的过程性表示将在我们的程序设计宝库里扮演一种核心角色。有关的程序设计风格通常称为消息传递。

如果觉得将序对表示为过程还不足以令人如雷灌顶，那么请考虑，在一个可以对过程做任何操作的语言里，我们可以完全没有数（至少在只考虑非负整数的情况下）。比如，在支持半残函数式的C++中，可以将Alonzo Church发明的Chruch计数表示为

/*********************************************************
          File Name:functional.cpp
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: Fri 23 Sep 2016 12:53:54 PM CST
**********************************************************/

#include <iostream>
#include <functional>

int main()
{
  auto one = [](auto f) {
    return f;
  };

  auto add = [](auto lhs, auto rhs) {
    return [=](auto f) {
      return [=] {
        lhs(f)();
        rhs(f)();
      };
    };
  };

  auto mul = [](auto lhs, auto rhs) {
    return [=](auto f) {
      return [=] {
        return lhs(rhs(f))();
      };
    };
  };

  auto two = add(one, one);
  auto four = mul(two, two);
  auto five = add(one, four);
  five([]{ std::cout << "5\n"; })();

编译运行，发现确实five打印了5次。

如你所见，当我们实现add和mul的时候，我们并不关心它要操作的是数还是个过程。下面使用Racket实现，并做解释

首先，定义0

(define zero
  (λ (f)
    (λ (x) x)))

这里zero有两部分f表示将被调用n次的过程，x表示用于这个过程的操作数，并且这两部分可以结合起来。但这里过程f并为对数据x进行操作。

接下来定义1

(define one
  (λ (f)
    (λ (x)
      (f x))))

同样，one也有两部分，和zero不同的是，这里过程f以x作为操作数调用了一次。

接下来定义2

(define two
  (λ (f)
    (λ (x)
      (f (f x)))))

这里过程f两次作用于x，将(f x)替换为x。

在实现加法前，先看看书中给出的add-的定义

(define (add-1 n)
  (λ (f)
    (λ (x)
      (f ((n f) x)))))

同样，将((n f) x)替换为x，再和zero和one的实现对比可以发现，这其实就是one的定义！

所以，这意味着什么呢？这就是怎样求Church数的啊！你给它一个函数，它返回一个对给定操作数调用n次的函数。这里add-1只是返回一个对操作数调用1次的函数而已。

所以，要实现加法，如(+ a b)，假设a对过程f调用若干次的返回值接着调用b对过程f调用若干次的返回值即可：

(define (add a b)
  (λ (f)
    (λ (x)
      ((a f) ((b f) x)))))

下面来验证一下： church_numerals

参考阅读： - lambda calculus - 丘奇和图灵 - [lambda calculus and turing machine]()自行Google

数据抽象引导

实例： 线段中点的计算

序对

线段的表示

抽象屏障

数据意味着什么

实例：线段中点的计算