functional的pattern match vs. OO的visitor vs. if/switch

ajoo · #1 (**permalink**) 2002-12-14

考虑这样的一个简单的需求：
表示一个二叉树。
在C/C++里也许是这样：

代码:

struct Tree{
  Tree* left;
  Tree* right;
};

那么，对叶子节点，使用null 或0表示。

这是一种最常用的procedural的办法。它的好处是简单，清楚。坏处是处理0指针容易出错，你要时刻担心你手里的指针是不是0. 而且它也不够fancy. （当然，在这种方法在很多场合如嵌入式系统编程，还是必要的合理的）
典型的使用这样的结构的代码会是这样：

代码:

Tree* p = ......;
if(p->left==NULL)掉头！
else {左满舵； process(p->left);}
if(p->right==NULL)掉头！
else {右满舵; process(p->right);}

再看OO的方法，即visitor pattern:
先声明一个接口：

代码:

interface Tree{
   void accept(TreeVisitor v);
}
interface TreeVisitor{
    void visitNode(Tree left, Tree right);
    void visitLeaf();
}
class TreeCons implements Tree{
    public void accept(TreeVisitor v){v.visitNode(left, right);}
    private final Tree left;
    private final Tree right;
}
class TreeLeaf implements Tree{
    public void accept(TreeVisitor v){v.visitLeaf();}
}

典型的处理这样结构的代码会是这样：

代码:

Tree tree = ......;
tree.accept(new TreeVisitor(){
    public void visitNode(Tree left, Tree right){
       左满舵；
     left.accept(this);
        右满舵；
     right.accept(this);}
    public void visitLeaf(){掉头！}
});

这种方法的好处是：
1。类型安全。有编译器的保护，你想犯错误，把TreeLeaf当TreeCons用都不行。
2。fancy. 你可以跟人吹嘘你用了visitor pattern.

缺点是：
1。繁琐。你要写更多的代码。即使是Java的anonymous class的语法也要求你写好多的多余代码。这对重量级的处理程序还可以。但是要是我所要的只是对某一个case写一两句话，如，“判断这个Tree是否是空”这个visitor就太笨重了。本来在procedural里只要写两行的，你要我写十行？
此时，你会被引诱写这样的代码：

代码:

if(tree instanceof TreeCons){
   process(((TreeCons)tree).getLeft());
}
else{
    out.println("empty");
}

但是，这样的代码正是OO所不提倡的。它使用procedural的方式，并且rtti的使用也损害了程序的扩展性，灵活性，纯洁性和安全性。

2。visitor接口是否要返回值？是否要throws Exception?
写visitor接口时，你并不知道会有几十种实现，所以，你怎么决定返回值呢？在Java里，你可以用Object. 但，这样，你又牺牲了类型安全，比如：

代码:

interface Tree{
   Object accept(TreeVisitor v);
}
interface TreeVisitor{
    Object visitNode(Tree left, Tree right);
    Object visitLeaf();
}
String getName(Tree t){
   return (String)t.accept(new TreeVisitor(){
     public Object visitNode(Tree left, Tree right){return "cons";}
     public Object visitLeaf(){return "leaf";}
   });
}

看到了么？此处，你需要使用强制类型转换。而这正是visitor所力图避免的。

所以，人们一般都不给visitor指定返回类型。对以上的getName的逻辑，使用无返回类型的visitor的代码是这样：

代码:

class TreeNamer implements TreeVisitor{
    private String name;
   public String getName();
    public void visitNode(Tree left, Tree right){name="cons";}
    public void visitLeaf(){name="leaf";}
}
String getName(Tree t){
   final TreeNamer namer = new TreeNamer();
   t.accept(namer);
   return namer.getName();
}

没有牺牲类型安全，也同样达到了目的。

不过，此时，代码就更加繁琐了。你也不能再使用anonymous class. 明明是函数里面的逻辑，却要移到函数外实现。感觉绕啊绕啊的别扭极了。

其实，这里使用generics, 或者说模板，可以说最合适，代码可以是这样 (这里使用GJ的语法，感觉比C++的简洁)：

代码:

interface Tree{
   <T> T accept(TreeVisitor<T> v);
}
interface TreeVisitor<T>{
    T visitNode(Tree left, Tree right);
    T visitLeaf();
}
String getName(Tree t){
   return t.accept(new TreeVisitor<String>(){
     public String visitNode(Tree left, Tree right){return "cons";}
     public String visitLeaf(){return "leaf";}
   });
}

不过，即使用模板，我们也还是有一个麻烦：Exception.
因为定义visitor接口的时候，我们根本不知道各个实现会抛出什么异常。
幸好Java里所有的checked exception都是Exception. 可是我们真想让我们的每一个visitor接口都充斥着throws Exception这样的东西吗？那样，所有的visitor的使用者都得被迫try-catch或者throws Exception, 即使使用者知道不可能出现Exception.

代码:

interface Tree{
   <T> T accept(TreeVisitor<T> v)throws Exception;
}
interface TreeVisitor<T>{
    T visitNode(Tree left, Tree right)throws Exception;
    T visitLeaf()throws Exception;
}
String getName(Tree t){
    try{
   return t.accept(new TreeVisitor<String>(){
     public String visitNode(Tree left, Tree right){return "cons";}
     public String visitLeaf(){return "leaf";}
   });
    }catch(Exception e){
         return new RuntimeException("什么嘛！我根本没throw 任何Exception啊！");
    }
}

还有，如果我的visitor确实抛出了exception, 但那是SQLException, 又怎么办？

代码:

String getName(Tree t){
    try{
   return t.accept(new TreeVisitor<String>(){
     public String visitNode(Tree left, Tree right)throws Exception{读数据库；返回名字或抛出异常；}
     public String visitLeaf(){return "leaf";}
   });
    }catch(SQLException se){......}
    catch(Exception e){
         return new RuntimeException("什么嘛！我根本没throw 除了SQLException之外的任何Exception啊！");
    }
}

在上面的两个例子中，使用者都要根据自己写的visitor的实现，决定是否ignore一个exception. 这样做一来繁琐，二来，这也是一种逻辑的重复。如果后来使用者改变了visitor的实现，要多返回一种Exception, 他还必须自己记得修改try-catch, 类型系统此时无能为力。比如说，以下的代码就是逻辑错误的，它把IOException也给ignore掉了。谁说你除了SQLException就没抛出其他异常了？瞎说了吧？

代码:

String getName(Tree t){
    try{
   return t.accept(new TreeVisitor<String>(){
     public String visitNode(Tree left, Tree right)throws Exception{读数据库；返回名字或抛出异常；}
     public String visitLeaf()throws IOException{return configFile.getLeafName();//现在，有可能抛出IOException了}
   });
    }catch(SQLException se){......}
    catch(Exception e){
         return new RuntimeException("什么嘛！我根本没throw 除了SQLException之外的任何Exception啊！");
    }
}

基于这些麻烦，现实程序中的visitor往往也是不定义任何exception的。如果实现抛出了任何exception, 它必须被包装在一个RuntimeException (也就是一个不要求使用者try-catch-throws的exception).
但这种方法往往导致一个异常链，你得这样：

代码:

try{
   ......
}
catch(ChainException e){
    throw e.getException();
}

但是，也许e.getException()出来的还是一个ChainException!!!
(听说为了这个， jdk1.4不是1.5的还把异常链直接建入了Exception类里，也真够难为可怜的Sun的）

另外一个问题是，RuntimeException不要求使用者try-catch/throws, 所以，程序员的大意可能导致异常没有被及时处理。又是一个牺牲静态类型系统的地方。

好了，最后，让我们来看看functional是怎么处理这种需求的。它大致的语法如下（记不清了）

代码:

datatype Tree is Node of (Tree, Tree) | Leaf

简单吧？跟那一大堆visitor什么的怎么比？

接下来，我们的getName()函数可以这样：

代码:

case tree of Leaf => "leaf"
|
Node(left, right) => "cons"

简单吧？加上异常也一样简单：

代码:

case tree of Leaf => "leaf"
|
Node(left, right) => throw SQLException

没有类型安全的问题。没有代码繁琐的问题。

值得注意的是，这种方法虽然看上去和procedural的方法很象，但却有本质的不同。
类型系统会保证你不会把一个Leaf当成一个TreeCons, 你也不用做强制转换。

可以说，它既有传统procedural的简洁的优点（实际上，我觉得它比procedural的代码还要简洁的多），也具有OO visitor的类型安全的特点。（区别只是比visitor更安全罢了）

我最近就一直在想，能不能把pattern match这个特性并入到OO中去呢？各位有什么想法吗？欢迎讨论。

anrxhzh · #2 (**permalink**) 2002-12-14

从我的C++经验出发，曾得出这样的结论：错误处理在本质上是结构化的，不是面向对象的。OO的目标是模块间去耦，手段是接口和实现的分离，也就是说OO对接口的变化是无能为力的，而错误处理基本上隶属于接口，不属于实现。当一个函数的错误代码或者异常规格发生变化时，所有调用者都必须作相应的改动，这就是紧耦合。

ajoo · #3 (**permalink**) 2002-12-14

好像我在说语义和类型安全。你在说接口和耦合。两台戏嘛。

Elminster · #4 (**permalink**) 2002-12-17

恐怕很难。

代码:

case tree of Leaf => "leaf" 
| 
Node(left, right) => "cons"

这个写法的对应物，在 OO 里感觉恐怕就是 RTTI ：如果是叶子，那么怎样；如果不是，那么怎样。但是既然你否定了 RTTI ，那么要想把这东西放进一般的 OO 的框架恐怕很难。

倒是 GP 的思路似乎近些：

代码:

template<typename L, typename R> struct tree
{
    L lchild;
    R rchild;
};

struct leaf {}; // 嗯嗯，所有的外部节点当作叶子节点处理

那么一棵树可以是：

tree< tree< tree< leaf, leaf >, leaf >, tree< leaf, leaf > >;

可惜模板结构是类型系统一部分，是静态的，所以这个不能用。GJ 有没有戏？

ajoo · #5 (**permalink**) 2002-12-17

exception也很有可能是rtti实现的。但我并没有否定exception呀！底层实现是rtti, if-else还是visitor那是另一回事。我们关心的是代码是否类型安全。

这种case的写法和

代码:

if(tree instanceof TreeCons){
   TreeCons ct = (TreeCons) tree;
   ...
}
else if(tree instanceof TreeEmpty){
    TreeEmpty et = (TreeEmpty) tree;
    ....
}

或者

代码:

TreeCons* ct = dynamic_cast<TreeCons*> (tree);
if(ct !=0){......}

没区别吗？它们可不是静态类型安全的啊。

ajoo · #6 (**permalink**) 2002-12-17

在考虑一个pattern match的最简单情况：

代码:

datatype weekday=monday|tuesday|wednsday|thursday
|friday|saturday|sunday

case wd of monday=>1|
tuesday=>2|
wednsday=>3|
thursday=>4|
friday=>5|
saturday=>6|
sunday=>7

是不是和什么东西挺象啊？哈哈。enum嘛！

不过相比于C的enum, pattern match类型更安全。你不能把weekday当int使的。

Java就缺enum这么个东西。有些人说java不需要，甚至举出各种workaround来。

但是，这些workaround都有问题。
比如说，我前面的visitor的解决方法。繁琐的缺点我已经说了。另一个缺点是：
enum的逻辑等语义是和值类型一样的。也就是说，

代码:

Node(Leaf, Leaf)==Node(Leaf, Leaf)
Leaf == Leaf

但是，使用visitor object的话，逻辑等是对象引用的语义，

代码:

new TreeCons(new TreeLeaf(), new TreeLeaf()) != new TreeCons(new TreeLeaf(), new TreeLeaf())

new Leaf() != new Leaf()

你也许会说，使用singleton或者flyweight可以保证引用完整性。但是，即使你不怕劳苦地做出了这么个flyweight（一个高效通用的基于引用相等语义的
flyweight不是那么好做的。）
它在object persistence的时候还是会有问题。你怎么保证你的引用完整性不被persistence破坏呢？Java的serialization只保证在一次serialize的时候保持引用完整性。也就是说：你把一个对象serialize两次，它就会变成两个对象拉！

对简单的enum, 有的人还提出用这样的方法：
class Weekday{
public static final Weekday monday= new Weekday();
public static final Weekday tuesday= new Weekday();
public static final Weekday wednsday= new Weekday();
public static final Weekday thursday= new Weekday();
public static final Weekday friday= new Weekday();
public static final Weekday saturday= new Weekday();
public static final Weekday sunday= new Weekday();
}

但是，它也是有persistence语义的问题的。（实际上，我感觉，new在语义上就不应该承诺必然返回不同的地址。对这样的no-side-effect对象，语言实现完全可以考虑做适当的优化。不同于flyweight的是，这些优化可以是在编译时静态解析的，所以没有运行开销）相比之下，C的enum就没有这个问题。

哎，所以有时候当我看到一些板动不动的人自信地宣称：“Java不需要enum, Java不需要generics, java不需要这个，java不需要那个”时，真感觉#*￥）（—#￥

ajoo · #7 (**permalink**) 2002-12-17

甭管什么语言，当你这么一写：

代码:

tree< tree< tree< leaf, leaf >, leaf >, tree< leaf, leaf > >;

它就已经是静态决定了的。没法动态了。要想动态，只能是tree < tree, tree >
不过那样一来，也就没必要用 < > 了

Elminster · #8 (**permalink**) 2002-12-17

引用:

作者: ajoo

这种case的写法和

代码:

if(tree instanceof TreeCons){ 
   TreeCons ct = (TreeCons) tree; 
   ... 
} 
else if(tree instanceof TreeEmpty){ 
    TreeEmpty et = (TreeEmpty) tree; 
    .... 
}

或者

代码:

TreeCons* ct = dynamic_cast<TreeCons*> (tree); 
if(ct !=0){......}

没区别吗？它们可不是静态类型安全的啊。

两种做法当然有区别，可问题是我找不到更接近的对应物了。这里的关键在于，这种 case 的做法，当程序员拿到一个 tree 的时候，他可以知道这个 tree 是 cons 还是 leaf。相应的， OO 你怎么办？只要你用“interface & implementation”的方式，拿到 tree 你不作 downcast 就没法直接把把 tree 当作 leaf 或者 cons 来用。

ajoo · #9 (**permalink**) 2002-12-17

OO里直接的对应当然是visitor啦，怎么会是rtti呢？
不过，我可不是说让你在现有的C++/Java里找到一个等同的东西。因为OO里并没有同样的东西。
我是说考虑在OO语言里直接支持pattern match. 你觉得cons/pros在哪里呢？为什么现有的OO语言都不直接支持它呢？

smille · #10 (**permalink**) 2002-12-17

我觉得函数语言里的pattern match的语义就是对象的动态类型匹配。在C++这样的依赖静态类型检查的语言来说，动态类型检查肯定就绕过了编译时期的类型检查，所以，这是不太可能的，也许扩展union的定义能实现这一点。而其他的OO语言主要是靠类型rtti来实现这一点吧？如果使用virtual语义来实现有限动态类型检测，那实际上就是visitor模式。
函数型语言为什么能安全地进行对象的动态类型匹配呢？我觉得有几个原因：1. 无副作用; 2. 强大的类型推导系统; 3. 无类型转换。这三条加在一起，使得一个对象从生成的那一刻起，就不可能改头换面或者成为漏网之鱼。

ajoo · #11 (**permalink**) 2002-12-17

类型推导系统可以做的呀。都有现成的算法的。
关于1和3，为什么no-side-effect和no downcast是pattern match的充分必要条件呢？
downcast是程序员自己找麻烦，所以，类型系统对downcast不安全是可以理解的。不需要苛求啊。
no-side-effect又和pattern match有什么必然联系呢？

Elminster · #12 (**permalink**) 2002-12-17

引用:

作者: ajoo

OO里直接的对应当然是visitor啦，怎么会是rtti呢？

当然是 RTTI 啦，怎么会是 visitor 呢？这里面程序员的思考方式明明是“如果我拿到一个 a ，那么就做 A ；如果我拿到一个 b 那么就做 B”。而 visitor 的思考方式是“我只知道我拿到一个 * ，我让它做 & ”，然后在别处定义：“如果 * 接口背后的恰巧是个 a，那么 & 就等价于 A，如果 * 接口背后恰巧是个 b ，那么 & 就等价于 B”

引用:

作者: ajoo

我是说考虑在OO语言里直接支持pattern match. 你觉得cons/pros在哪里呢？为什么现有的OO语言都不直接支持它呢？

感觉上是这种东西很难无缝的融合到现有的 OO 语言的类型系统里去。比方说你的例子中的那个 tree ，就假设某个语言直接支持“datatype Tree is Node of (Tree, Tree) | Leaf”这种语法，那么 tree 类型和其他类型怎么交互呢？普通的 class 可以有 tree 类型的成员吗？如果我操作一个 tree ，导致其类型发生变化了怎么办？比方说删除其左右子树，使其由 cons 变为 leaf？fpl 禁止改变状态或许不会有这种事（我猜的），但现有的 OO 语言恐怕不是这样？leaf 又是什么类型？leaf 可以是个简单的 class 吗？问题实在太多了，权衡出一个好的方案只怕很难。

另一方面，我猜测，从设计思想上，这种 pattern match 的想法是不能简单的放进现有的 OO 的框架的，除非象 C++ 那样摆明车马当作一个新的 paradigm 来支持，否则只会破坏整个语言的一致性。

猜测而已，进一步的确证和讨论需要大量时间精力，这是我现在支付不起的。

smille · #13 (**permalink**) 2002-12-17

引用:

作者: ajoo

类型推导系统可以做的呀。都有现成的算法的。
关于1和3，为什么no-side-effect和no downcast是pattern match的充分必要条件呢？
downcast是程序员自己找麻烦，所以，类型系统对downcast不安全是可以理解的。不需要苛求啊。
no-side-effect又和pattern match有什么必然联系呢？

无副作用保证一个对象不会被改变，这就是类型和对象的一致性：对象在任何时刻的类型都是它定义时候的类型。再用类型推导系统保证类型的一致性，也就保证了对象的一致性。没有cast的意思就使得类型只能被安全地使用，比如haskell里type和class的关系。在这种情况下，整个系统的类型安全就得到了保证。

反之，有副作用和类型cast使得编译器无法断定一个对象的实际类型。比如一个函数，传入的参数定义是基本类，实际可能是个子类，具体是什么子类，编译器在编译时无法判定，除非做全局的数据流分析，但是做全局分析就要求分析所有涉及的子模块，这和静态语言的子模块各自独立，链接不做分析的传统是矛盾的。

所以，要想在OO语言安全地实现动态类型匹配，一个折中的办法就是利用virtual语义。

ajoo · #14 (**permalink**) 2002-12-18

在我的概念中，面向对象的特征是多态，而不是rtti. rtti只是一个附加的功能而已。你可以设计一个没有rtti的面向对象语言，但没有多态，那就不是面向对象了。实际上，如果你读了我翻的那篇对象概论，里面有个观点是：从purist的观点看，rtti是损害了OO的纯洁性的。所以选rtti来做OO的代表，就有点讽刺意味了。

所以，我说OO中pattern match的对应物是visitor. 而且，visitor和pattern match的一个共同点就是类型安全。而rtti的不安全类型正是pattern match所防止的。可以说rtti和pattern match只是形似罢了。
要说对应，用union+type flag好像和rtti对应。

下面逐句回答

引用:

就假设某个语言直接支持“datatype Tree is Node of (Tree, Tree) | Leaf”这种语法，那么 tree 类型和其他类型怎么交互呢？

当然可以交互啦。可以把它当作值类型嘛。和int, char, reference一样都是inline。当然，Node里面的两个Tree必须在堆中。它只带两个指针。
动态语义可以选择visitor或者union+type flag.反正对源程序透明啦。

引用:

普通的 class 可以有 tree 类型的成员吗？

普通的class可以有int类型成员吧？可以有struct成员吧？如果他们可以，自然这个也可以。

引用:

如果我操作一个 tree ，导致其类型发生变化了怎么办？

在C/C++里，你能动态改变一个对象的类型？

引用:

比方说删除其左右子树，使其由 cons 变为 leaf？

leaf在C中的直接对应是null或0, 你不可能把一个node对象变成0吧？
你概念中的叶子是这个：Node(leaf, leaf).
理解有误。

引用:

fpl 禁止改变状态或许不会有这种事（我猜的），但现有的 OO 语言恐怕不是这样？

OO也可以做immutable编程啊。只要有gc, 这不成问题。至少，让支持pattern match的datatype immutable是可行的阿。
实际上，我正在构思一个functional的OO语言。无副作用正是它要支持的。当然目标只是一个玩具。

引用:

leaf 又是什么类型？leaf 可以是个简单的 class 吗？

你在问静态类型还是动态语义？如果语言直接支持datatype, 那么它就是一个datatype, 不是class. 因为它是值语义。动态语义可以用type flag+union来实现。或者visitor也行。

当然，我不是说它肯定是可行的。我是正在试图看到它不可行的一面。

smille, 能举个例子证明side-effect或downcast会使pattern match不工作吗？
其实fpl里已有多态呀。你也可能拿到一个signature但不知道它的具体类型是什么。好像这并不构成问题。

ajoo · #15 (**permalink**) 2002-12-18

实际上，如果仅仅谈实现的可能性。
给定这样的代码：

代码:

datatype tree=Node of (Tree, Tree) | Leaf;
case tr of Node(left, right)=>x|
Leaf=>y

我完全可以写一个源码级的转换器，把它转换为union或visitor或rtti的代码（不同的是，这些不安全的代码是由程序生成的，datatype的静态类型系统可以保证程序员不犯错误。

代码:

struct tree{
   union{
     struct Node{
        tree* left;
        tree* right;
     }node;
     struct Leaf{} leaf;
  }
  int flag;
};
switch(tr->flag)
case NODE:
   return x;
case LEAF:
   return y;

类似于gj的解决方案。
当然，另一个问题是，如果我们支持rtti, 我们是否要让datatype代表运行时的一个单独类型。

Elminster · #16 (**permalink**) 2002-12-19

我当然知道 RTTI 的存在属于 OO 的“瑕疵”，我只是觉得你提出的这种 pattern match 的做法更类似于 RTTI 而不是 visitor 的解决方案。

引用:

作者: ajoo

引用:

比方说删除其左右子树，使其由 cons 变为 leaf？

leaf在C中的直接对应是null或0, 你不可能把一个node对象变成0吧？
你概念中的叶子是这个：Node(leaf, leaf).
理解有误。

就是这个，比方说原来一个节点的左右子树不是叶子，删除之后左右子树变成叶子了，那么这个节点的左右子树类型是不是变化了？leaf 是不是个类型？cons 是不是个类型？在程序别的地方，我可不可以用它们生成对象？我可不可以写接受它们作为参数的普通函数？象这样：

代码:

some_func(tree t);
some_func(leaf l);
some_func(cons c);

这里面的重载规则又怎么说？我又可不可以把指向 leaf 的引用赋给 tree 类型的引用？一大堆问题。

如果仅仅从实现角度，那是肯定没问题的，Effle 可以拿 C 当作“可移植的机器码”来用，构造出一个面向对象的语言，你当然也完全可以在 java 或者别的什么语言上构造出一个扩展来支持你的想法。

问题在于，你构造出来的扩展和原来的语法是不是可以很好的融合在一起，整个语言是不是仍有一致性。如果这个扩展加的很生硬，整个语言好象成了互不相干的两块，那即使你能实现，也没有太大的意义。

ajoo · #17 (**permalink**) 2002-12-20

引用:

就是这个，比方说原来一个节点的左右子树不是叶子，删除之后左右子树变成叶子了，那么这个节点的左右子树类型是不是变化了？

不好说，看leaf是否是一个类型了。而且，即使子树的动态类型变化了，它的静态类型没有变啊。也不表示节点自己的类型变化了。偷换概念了吧？

引用:

leaf 是不是个类型？cons 是不是个类型？

就算是吧。（其实，在fpl里，leaf只是一个type constructor, 不作为单独的类型存在，你只在构造或pattern match的时候用到他。所以，有点象是factory中的方法，从这个意义上说，pattern match就更象visitor了。
不过，即使把它当作一个独立的类型，我也看不出问题来）

引用:

在程序别的地方，我可不可以用它们生成对象？

当然啦，不然要它们还有什么用？不过它们生成的是否应该叫对象值得商榷。因为它们是值类型。（类似于原始类型）

引用:

我可不可以写接受它们作为参数的普通函数？象这样：
some_func(tree t);
some_func(leaf l);
some_func(cons c);

tree是肯定可以。至于leaf和cons, 看我们是否把它们当作独立的类型了。如果在ml里就不可以。
不过，就算可以，我觉得也没问题。至少，C++里同样的overloading规则可以用在这里。

我正在考虑的就是什么样的原因使它不适合加入OO. 你光跟我说：它不见得合适。等于什么也没说啊。
怎么个不合适呢？