Callback 和内部迭代器

最近用 C 做编译作业的时候用了 GLib 里面的 hash table，终于用到了 C 中 Callback。函数指针以前没有怎么用过，现在觉得是个不错的东西，还有就是 void 指针真是个让人即爱又恨的东西，而更恶心的东西莫过于 void 指针的指针了（能避免这样的东西还是避免吧，我的智力还是不够去处理那样“邪恶”的东西）。

因为看到 GSList 同时提供了外部迭代器和内部迭代器，所以想到了更其他语言作一下比较。同时也看看利用 callback 来实现内部迭代器的方法。

为什么要内部迭代器？通常在对容器作迭代时，对容器中的每个对象所做的操作都是一样的。迭代器隐藏了容器内部的实现，对外提供遍历容器内部的数据的方法。外部迭代器虽然做到了这一点，但是实际上迭代的过程还是要程序员自己来写。你得得到一个迭代器，然后在 for 循环里判断有没用到终点，没用的话执行循环体，然后让迭代器向后移动。实际上大多数的情况下迭代的不同只是在循环体而不是那个 for 循环，所以完全可以将这个 for 循环封装在对象内部，而将循环体通过某种方式传入，然后 for 循环通过某种方式去调用这个循环体就可以达到遍历的目的了。这样的迭代器就是内部迭代器了，一个明显的好处就是避免了容器使用者写错 for 循环的可能。现在问题的关键就在于循环体如何传入？一种比较自然的想法就是将函数作为参数传入，这样 for 循环只要调用这个函数就可以了，也就是 callback 了。下面就看看我所知道的各种语言使用 callback 来实现内部迭代器的方式。

先看 C。举个例子，GSList 的 g_slist_foreach 用来遍历一个链表。
1
void g_slist_foreach( GSList* list, GFunc func, gpointer user_data);
三个参数分别为：需要遍历的链表，callback 函数(也就是要作用在每一个链表中元素上的函数)，传给 callback 函数的数据（gpointer 实际就是一个 void 指针）。其中 callback 的函数的原型如下：
1
void callback(gpointer data, gpointer user_data);
在将函数指针传给 g_slist_foreach 的时候要将它转型为 GFunc。GFunc 应该是一个 typedef 吧。
1
typedef void (*GFunc) (gpointer data, gpointer user_data);
其中 data 是 list 中元素，而 user_data 是调用 g_slist_foreach 时传入的。其实 GSList 可以使用外部迭代器来遍历，方法如下：
1 2 3 4 5
GSList* iter; for (iter = some_gslist; iter; iter = iter->next) { gpointer data = iter->data; ...... }
所以 g_slist_foreach 可以像这样来实现（我没有看过它真正的实现，真正的实现可以接受只有一个参数的函数指针，只要在调用的时候把 NULL 传给 user_data。）
1 2 3 4 5
void g_slist_foreach(GSList* list, GFunc callback, gpointer user_data) { GSList* iter; for (iter = list; iter; iter = iter->next) callback(iter->data, user_data); }
这样 g_slist_foreach 相当于是一个内部迭代器了。对于复杂的遍历另外定义一个函数再通过 g_slist_foreach 来遍历代码会比较好看吧，另外也避免了写错 for 循环的可能性。对于简单的遍历要新定义一个函数感觉还是不太方便的。

再看 Java。Java 里面的 callback 的话可以通过 interface 或者 abstract class来实现。同样以链表为例吧，代码就随便一点了。

public interface ListIter {
    public void func(Object data, Object userData);
}

public class ListIterImpl implements ListIter {
    public void func(Object data, Object userData) {
        // do something on the data
    }
}

public class List {
    private class Node {
        public Node next;
        public Object data;
    }

    private Node head = new Node();

    public foreach(ListIter callback, Object userData) {
        Node iter = null;
        for (iter = head.next; iter != null; iter = iter.next)
            callback.func(iter.data, userData);
    }
}

// Use the list
List list = new List();
list.foreach(new ListIterImpl(), null);

这样，对于 List 的对象要遍历它只要创建一个类并实现 ListIter 接口，然后创建这个类的对象并将它传给 foreach 函数就可以。如果 ListIter 定义为 abstract class 的话那么可以让 ListIter 的对象来携带数据以避免传递用户数据了。这样其实就构造了 List 的一个内部迭代器了。但是 Java 的 Collection 中并没有采用这种方式，我想原因在于对于每一种遍历方式都要去创建一个类实在是不方便。不过注意 Java 5.0 中有个增强的 for 循环，利用它可以非常简单的来遍历一个链表，不需要接口，也不需要外部迭代器。

for (Object data : List) {
    // do something on the data
}

个人认为这也可以看作是一种内部迭代器，只不过迭代的过程由 Java 编译器完成了。自从知道这个增强的循环以后我就从来不使用 Java 的外部迭代器了。当然，List 的实现里面要提供一些东西以支持这样的遍历。不过遗憾的是我现在还不知道究竟要提供什么，Java 5.0 的文档里面似乎只提到了这个 for 循环用于 Collection 的对象上，而没用具体说类的实现是否有什么特别的要求。(有看到过文章说这是 continuation，不过这个我就不懂了) Callback 在 Java 中当然还是有用的，只不过不是用来作内部迭代器而已。以前用过 JavaSVN（现在名字叫 SVNKit），它里面就用了不少的 callback。

下面是 C++。我对 C++ 不是很熟悉。不过我想在 C++ 中实现 callback 的话即可以使用函数指针，也可以使用类似 Java 的方式。另外也可以使用函数对象，TCPPPL 中说一个定义的好的对象通常比一个函数工作的更好，而且函数对象执行起来也更快（用对象来保存对象的话避免了函数参数的传递吧，还有什么其他的原因呢？）。举个大概的例子吧，但愿不要有错误。假设在 List 的 C++ 实现里已经有了迭代器，提供了 begin(), end() 方法得到起始和末尾，那么可以使用 foreach 来遍历 List 的对象。大概的代码是这样的：

class Callback {
public:
    // Saves user supplied data
    Callback(Data user_data) {}

    void operator()(Data data) {
        // do some thing on the data
    }
}

foreach(list.begin(), list.end(), Callback(user_data));

for_each 实际上将 List 中每一个对象传给 Callback 类对象的重载过的 () 运算符，Callback 类本身又可以携带数据，所以就避免了在 callback 函数中另外再传用户数据的麻烦。

再看看 Scheme 就会觉得比较有趣了（Scheme 是 Lisp 的一种方言）。Lisp 淡化数据和过程的差别，传递数据和传递函数完全是一样的方式，过程不仅可以返回数据，也可以返回过程！所以这里的 callback 不是那么明显，而 Lisp 程序中传递过程这样的事情实在是太多了。我对 Scheme 的了解仅限于看 SICP 时学到的那些，请有经验的 Scheme 程序员不吝指教。这里就不以 List 为例子了，因为 Lisp 这样的语言中使用表作为通用的数据结构得到的威力远远大于专门构造一个链表（另外我承认我从来都没有自己尝试过在 Scheme 中创建一个链表，要写的话还要花一点时间呢）先解释一下表的概念吧。表实际上由有序对组成，可以使用 (cons x y) 来构造一个有序对，对这个有序对使用 (car (cons x y)) 的到的就是 x，而使用 (cdr (cons x y)) 得到的就是 y。一个表可以用下面的方式构造：

(cons x (cons y nil))

这样就构造了一个只有 2 个元素的表 (x y)。注意表一定是以 nil 结尾的。（nil 表示空）了解了表以后这里就以遍历一个表为例子吧。类似于使用外部迭代器，你可以自己使用 car, cdr 来遍历一个表。由于表的构造方式，使用递归是非常方便的。这里不使用赋值（我对 Scheme 中的赋值的理解还不够），在遍历完之后返回一个对每一个元素做过特定操作的新的表。（Scheme 的实现里对 tail-recursive 的计算的空间开销是常量，所以这里不用担心递归的开销，跟迭代没用差别）方便起见，分号之间的作为注释。

(define list (cons x (cons y (cons z nil))))

(define (iter items)
  (if (null? items)
    nil
    (cons (;; do something on (car items);;)
        (iter (cdr items)))))

;; iterate over list;;
(iter list)

这个遍历过程是很通用的，除了对表中元素的操作不同以外其他的代码在对其他表遍历的时候也可以使用。为了复用这些代码，也使得程序更简洁，可以将这个遍历过程抽象成一个过程。

;; From the famous and interesting book SICP;;
(define (map proc items)
  (if (null? items)
    nil
    (cons (proc (car items)
      (map proc (cdr items)))))

;; use map to iterate ove list
(map (lambda (x) (;; do some thing on x ;;)) list)

这里 map 过程的 proc 参数是一个过程，它接受一个参数。在调用 map 过程应用于表 list 的时候使用 lambda 定义了一个匿名过程，这样就可以避免另外单独定义一个函数了。（C++ 的 Boost 库中的 lambda 就是作这个事情的吧，不过没有尝试过）跟前面没有抽象成过程的例子比较一下，注意对表中每一个元素的操作位置的改变。可以将 map 过程看作一个内部迭代器。但是 Lisp 的威力在于这个 map 过程可以作用在任何的表上（注意表在 Lisp 中是通用的数据结构），而表可以用来存放任何类型的数据，所以 map 过程只需要一个！变化的东西只有表中存放的元素和如何对那些元素进行操作。而 C++/Java 这样的语言对每一个不同类型的类都需要提供这样的一个迭代器。你可以尝试定义一个通用的遍历过程作用于不同的容器，但是对不同类型的容器如何遍历？使用迭代器？那么这个迭代器当然得由容器类来提供了。（其实 C++ 中的 for_each 就可以看作是一个可以作用于不同容器的通用迭代器，但是如果容器不提供迭代器，for_each 又如何实现？）

最后是实现 callback 最爽的 Ruby 了。大概的代码样样子如下（Ruby 没有怎么正式使用过，写的不好请不要笑话）：

class List
  class Node
    attr_accessor :next, :data
  end

  @head = Node.new

  def foreach()
    iter = @head.next
    while (iter != nil)
      yield iter.data
      iter = iter.next
    end
  end
end

注意 yield 这个关键字，它会调用附加给函数 block （简单来说就是一段代码，Ruby 会将这段代码转为一个特殊的对象 Proc 传入），yield 把链表中的元素传给这个 block。在要遍历 List 对象的时候可以像这样：

list.foreach {|data| # do something on the element }

# or like this
list.foreach do |data|
  # do something on the element
end

不需要接口，不需要函数指针，要对元素做什么操作直接把代码写在 block 中。跟我在文章开头说的将一段代码传入 for 循环的想法最相近吧。实际上 Ruby 中只要 include 几个 module ，实现几个特定的函数就可以得到像 foreach 这样的内部迭代器，不过 Ruby 中习惯把这个函数的名字叫做 each 。 Ruby 中大量使用这样的内部迭代器，同时利用 block 可以非常方便的实现 callback 机制。

最后的一点想法。一个函数接受另一个函数（或者说一段代码）作为参数可以改变已经定义好的函数的行为。是不是可以把这个调用其他函数的函数看作是一个 template 呢？不管怎么说，将函数作为参数来传递真的是一种很有用的技术吧。

Random Tech Thoughts

The title above is not random

Comments