这是我接触Java的第二个星期（雾），大概是自己上手最快的语言了吧。
作为一个菜Haskeller，总想人肉将Haskell代码编译到Java上。
看了A little Java这本书，相比于Thinking in Java这些“传统”一点的书，觉得挺耳目一新的。
今天就把学到的东西记录一下——「利用Visitor Pattern模拟ML系语言的Pattern Matching」
当然，在OOP里面模拟Pattern Matching也是一件特别有成就感的事情，毕竟Pattern Matching这是一个特别好用的东西。
先看最简单的Maybe（写成Option）模式匹配的例子：
data Option a
= Some a
| None
getOrElse :: Option a -> a -> a
getOrElse opt other =
case opt of
Some v -> v
None -> other
然后再看看在Java里面如何表达。首先要定义等价的数据结构：
abstract class Option<T> {}
final class Some<T> extends Option<T> {
private final T value;
Some(T v) {
value = v;
}
}
final class None<T> extends Option<T> {}
可以将Java中抽象类表示一个Datatype，然后将继承这个抽象类的类作为这个Datatype的变体(variant)。然后如何模拟模式匹配呢？有请今天的主角：Visitor Pattern。用一个visitor来访问每个变体里的字段。
interface OptionVisitors<T, R> {
R forSome(T v);
R forNone();
}
abstract class Option<T> {
public abstract <R> R accept(OptionVisitors<? super T, ? extends R> v);
public static <T> Option<T> Some(T v) {
if (v==null){
throw new NullPointerException();
} else {
return new Some<T>(v);
}
}
public static <T> Option<T> None() {
return new None<T>();
}
}
final class Some<T> extends Option<T> {
private final T value;
Some(T v) {
value = v;
}
public <R> R accept(OptionVisitors<? super T, ? extends R> v) {
return v.forSome(value); //用Visitor访问私有字段value，并进行变换
}
}
final class None<T> extends Option<T> {
public <R> R accept(OptionVisitors<? super T, ? extends R> v) {
return v.forNone();
}
}
我们为每个类里加入了accept方法，接受一个visitor作为一个参数，返回作用将访问到的数据经visitor变换后的结果。于是我们来写一个getOrElse方法吧（在Option里）：
public T getOrElse(T other) {
return this.accept(new OptionVisitors<>() {
public T forSome(T v) { return v; }
public T forNone() { return other; }
});
}
如果我们改一改约定俗成的名字，将accept改成match，Visitor改成Pattern，就很Haskell了（虽然这样就不Java了）
public T getOrElse(T other) {
return this.match(new OptionPattern<>() {
public T Some(T v) { return v; }
public T None() { return other; }
});
}
我们还可以使用visitor pattern来解决expression problem——刚刚看到了，添加一个新方法是一个很稀松平常的事情；而每添加Datatype的新的一个变体，也只需要多写一个visitor继承旧visitor添加处理新变体的方法即可。
听说visitor pattern和Scott encoding有些许关系，于是我去粗略看了一下——这不就是CPS变换嘛！
我们来看一下在Haskell里怎么用CPS模拟模式匹配的：
type OptionCPS r a =
r -> -- forNone
(a -> r) -> -- forSome
-> r -- return type
none :: OptionCPS r a -- data constructor
none forNone forSome = forNone
some :: a -> OptionCPS r a -- data constructor
some a forNone forSome = forSome a
getOrElse :: OptionCPS a a -> a -> a
getOrElse opt other =
opt
other -- while none
(\v -> v) -- while some
这就是Option的Scott encoding。
这里还可以用newtype封装一下。
newtype OptionCPS r a = OptionCPS { dispatch ::
r -> -- forNone
(a -> r) -> -- forSome
-> r -- return type
}
none :: OptionCPS r a -- data constructor
none = OptionCPS $ \forNone forSome -> forNone
some :: a -> OptionCPS r a -- data constructor
some a = OptionCPS $ \forNone forSome -> forSome a
getOrElse :: OptionCPS a a -> a -> a
getOrElse opt other = dispatch opt
other -- forNone = other
(\v -> v) -- forSome = \v -> v
这里的形式跟visitor pattern已经十分相像了。
我尝试解释一下这玩意儿，我们来看一下最原始的模式匹配的一个形式：
case d of
C1 x11 x12 ... x1n1 -> f1 x11 x12 ... x1n1
C2 x21 x22 ... x2n2 -> f2 x21 x22 ... x2n2
...
Cm xm1 xm2 ... xmnm -> fm xm1 xm2 ... xmnm
其实，一个模式匹配表达式，本质就是传入m个函数（一个Datatype有m个变体），替换掉对应data constructor的位置，进行进一步的计算。
根据这个形式，我们可以用写出一个Datatype的data constructor的形式：
C1 x11 x12 ... x1n1 = \c1 c2 ... cm -> c1 x11 x12 ... x1n1
C2 x21 x22 ... x2n2 = \c1 c2 ... cm -> c2 x21 x22 ... x2n2
...
Cm xm1 xm2 ... xmnm = \c1 c2 ... cm -> cm xm1 xm2 ... xmnm
那么当传入了m个函数之后，比如作用在C1上：
((C1 x11 x12 ... x1n1) f1 f2 ... fm) = f1 x11 x12 ... x1n1 :: r
就只会计算其中一个分支，这样就达到了模式匹配的效果。
我们顺便观察一下里面的类型：
Ck xk1 xk2 ... xknk :: D = (X11 -> X12 -> ... -> X1n1 -> r) -- forC1
-> (X21 -> X22 -> ... -> X2n2 -> r) -- forC2
...
-> (Xm1 -> Xm2 -> ... -> Xmnm -> r) -- forCm
-> r
这个本质上就是CPS形式的代码：一个变体（Ck xk1 xk2 … xknk）需要“取出”里面的数据，就要传入m个回调函数（延续）才能“得到”最终的结果（进行模式匹配）。（当然这也就是所谓的Scott encoding。）
这m个回调函数在Java的具体实现中就是Visitor中的m个方法，accept方法就是这个匹配的过程。
我们将上面的一段代码再改写一下：
newtype Option r a = Option { accept :: OptionVisitor r a -> r }
data OptionVisitor r a = OptionVisitor {
forNone :: r
, forSome :: a -> r
}
none :: Option r a -- data constructor
none = Option $ \(OptionVisitor forNone forSome) -> forNone
some :: a -> Option r a -- data constructor
some a = Option $ \(OptionVisitor forNone forSome) -> forSome a
getOrElse :: Option a a -> a -> a
getOrElse opt other = opt `accept` OptionVisitor {
forNone = other
, forSome = \v -> v
}
这样就十分Java了，基本能做到跟上面的Java代码一一对应起来。但是注意的是，这里仅仅只是将上面CPS形式的代码封装了起来而已。
不过这样模拟出来的模式匹配的能力也是十分有限的，仅仅只能匹配一层的的结构。如果需要加强，就得在visitor中多加几个方法，但这样就十分的不灵活了
于是在这里下个结论：visitor pattern在形式上就是一种运用了CPS变换的代码。但是知道的注意的是，它并不能具有与CPS变换具有相同的显式控制 控制流 的能力，因为它并没有将visitor当做参数传递到接下来的计算中，尽管你写出来了这样一段代码：
static ABC<Integer> fact(Integer n) {
if (n == 0) {
return new ABC<>(1);
} else {
return fact(n-1).accept(n1 -> new ABC<>(n1 * n));
}
}
除非写成（我瞎写的，还没验证）：
static ABC<Integer> fact(Integer n, ABCVisitor<Integer, ABC<Integer>> v) {
if (n == 0) {
return new ABC<>(1).accept(v);
} else {
return fact(n-1, n1 -> new ABC<>(n1 * n).accept(v));
}
}
只不过visitor pattern提出来并不是为了解决控制流这个问题的，这样弄简直是瞎搞= =，仅仅只是满足了我一时的探索心（强行把CPS变换和visitor pattern联系在了一起）
visitor pattern用来做什么我就不多赘述了。
CPS变换究竟是什么也不多说了。
因为这两个东西太多文章说过了，你甚至不需要谷歌就能查询到很多关于它们的资料。
还有，文章采用了极为不严谨的表达，纯属自high，也懒得找出处了，
如有“带坏”，我也没办法，，
如有错误，感谢指出。。。
晚安