Visitor Pattern

來自專欄 Cofree

前文怎麼都發布不了，直到我拉到最底下，才看到那幾個小紅字。。。其實上篇的內容不多，就是Java代碼太長了而已。。。

偶爾詐屍一下，想寫點實用性的東西，故想到了一些以前挖的坑，想慢慢填回來，上文寫不下了，故這些話寫在這裡。。。

---------------------------------------------------------------------------------------------

《A Little Java A Few Patterns》是一本Java必讀經典，全書以問答的形式，循序漸進的講解Visitor模式，（唯一障礙可能是你對披薩餅的知識）。我想以Visitor模式為切入點來聊聊OO和FP。（本文其實是對前文的發散）

Visitor模式

關於Visitor模式的介紹網上有大量的介紹性文章，但是用一本書去描述一個模式，必然會告訴我們更多的細節；書里描述了Visitor模式的完整抽象過程，我們先像網上文章一樣，總結一下這個模式：

Datatype & Data Variants

Datatype顧名思義就是數據類型（代表數據的類型）：

abstract class Nat {}

Nat就是個datatype，我們發現它是abstract的，無法被實例化，data variants則是可以被實例化（構造）的具體子類：

class Zero extends Nat {}class OneMoreThan extends Nat { Nat predecessor; OneMoreThan(Nat p) { predecessor = p; }}

Zero和OneMoreThan都是Nat的variants，他們可以被構造如：new Zero()，new OneMoreThan(new Zero)，他們的datatype都是Nat

這和FP中的algebraic data type是對應的（就是從ADT這邊來的吧）。

Actions & Operations

看一個傳統OO的例子：

public class Exp { public int literal(int v) { return v; } public int add(int a, int b) { return a + b;} public int subtract(int a, int b) { return a - b;} public int multiply(int a, int b) { return a * b;}}Exp exp = new Exp();

當想加個divide方法時，會非常輕鬆，我們只需繼承Exp類型，添加方法就行，不用改動原來的class：

public class DExp extends Exp { public int divide(int a, int b) { return a / b;}}Exp exp = new DExp(); //修改實現

我們將添加的新方法稱之為：operations （Exp類型目前有5種operations，並且還可以添加更多）

我們的Exp類，現在是能做計算，如果我要列印一個表達式，而不是對它求值呢？sorry，只能新寫個class，並且所有方法返回String

public class ExpShow { public String literal(int v) { return v + ""; } public String add(String a, String b) { return "(" + a + "+" + b + ")";} public String subtract(String a, String b) { return "(" + a + "-" + b + ")";} public String multiply(String a, String b) { return "(" + a + "*" + b + ")";}}

我們將這種新的result types的實現稱為Actions，（Exp類型只有一種Action，並且不支持添加新的action）

註：引入類型參數，即將Exp 改成 Exp<T> 介面 就可以支持添加不同的Actions了（Exp<T> 的具體實現類），這裡談論的是傳統OO

OK，對Actions和Operations的定義了解後，就方便理解Visitor了。

Visitor & Visitee

Datatype是幹嘛用的？表示具體數據用的，比如new Zero()表示0，new OneMoreThan(new Zero)表示1，它是Visitor模式的組成部分（被訪問者，Visitee）。Visitor將如上的Exp分成了兩部分：datatype + actions，我們的datatype以及其variants：

//datatypestatic abstract class Exp {} //variantsfinal class Literal extends Exp { public final int val; public Literal(int val) { this.val = val; }}final class Add extends Exp { public final Exp a; public final Exp b; public Add(Exp a, Exp b) { this.a = a; this.b = b; }}final class Subtract extends Exp { public final Exp a; public final Exp b; public Subtract(Exp a, Exp b) { this.a = a; this.b = b; }}final class Multiply extends Exp { public final Exp a; public final Exp b; public Multiply(Exp a, Exp b) { this.a = a; this.b = b; }}

datatype只表示數據，那麼我們就可以隨意的去解釋它，即添加不同的Actions，怎麼個添加法呢？就是為其添加一個Visitor：

class ExpVisitor { public int forLiteral(int v) { return v; } public int forAdd(Exp a, Exp b) { return a.accept(this) + b.accept(this); } public int forSubtract(Exp a, Exp b) { return a.accept(this) - b.accept(this); } public int forMultiply(Exp a, Exp b) { return a.accept(this) * b.accept(this); }}abstract class Exp { public abstract int accept(ExpVisitor visitor);}final class Literal extends Exp { public final int val; public Literal(int val) { this.val = val; } public int accept(ExpVisitor visitor) { return visitor.forLiteral(val); }}final class Add extends Exp { public final Exp a; public final Exp b; public Add(Exp a, Exp b) { this.a = a; this.b = b; } public int accept(ExpVisitor visitor) { return visitor.forAdd(a, b); }}...Exp exp1 = new Add(new Literal(1), new Literal(2));int res = exp1.accept(new ExpVisitor());

在datatype Exp上開了協議（accept），所有variants都實現了該方法，具體的Action實現委託給了ExpVisitor，針對支持不同的Action，現在還做不到，因為要支持不同的Actions，需要添加不同的accept方法，和不同return type的ExpVisitor，但是這個完全可以通過抽象來解決：

public interface ExpVisitor<T> { public T forLiteral(int v); public T forAdd(Exp a, Exp b); public T forSubtract(Exp a, Exp b); public T forMultiply(Exp a, Exp b);}...abstract class Exp { public abstract <T> T accept(ExpVisitor<T> visitor);}class ExpEvalVisitor implements ExpVisitor<Integer> { @Override public Integer forLiteral(int v) { return v; } @Override public Integer forAdd(Exp a, Exp b) { return a.accept(this) + b.accept(this); } @Override public Integer forSubtract(Exp a, Exp b) { return a.accept(this) - b.accept(this); } @Override public Integer forMultiply(Exp a, Exp b) { return a.accept(this) * b.accept(this); }}static class ExpShowVisitor implements ExpVisitor<String> { @Override public String forLiteral(int v) { return v + ""; } @Override public String forAdd(Exp a, Exp b) { return "(" + a.accept(this) + "+" + b.accept(this) + ")"; } @Override public String forSubtract(Exp a, Exp b) { return "(" + a.accept(this) + "-" + b.accept(this) + ")"; } @Override public String forMultiply(Exp a, Exp b) { return "(" + a.accept(this) + "*" + b.accept(this) + ")"; }}int res2 = exp1.accept(new ExpEvalVisitor());String res3 = exp1.accept(new ExpShowVisitor());

（書里用的是Object，因為書比較老，我們直接用類型參數去表示Actions了），ExpEvalVisitor和ExpShowVisitor就是不同的actions

Extensibility

什麼是可擴展性？它有兩個正交的概念，就是前面所說的Actions & Operations，（兩邊都要兼顧叫：Expression Problem）

前面不同的Visitor的實現類，可以實現actions的擴展，那麼Operation呢？還是加個divide方法，需要添加新的Variant和Visitor：

final class Divide extends Exp { public final Exp a; public final Exp b; public Divide(Exp a, Exp b) { this.a = a; this.b = b; } public <T> T accept(ExpVisitor<T> visitor) { return ((ExpVisitor2<T>) visitor).forDivide(a, b); } }//原諒我的命名public interface ExpVisitor2<T> extends ExpVisitor<T> { public T forDivide(Exp a, Exp b);}

其次擴展actions：

class ExpEvalVisitor2 extends ExpEvalVisitor implements ExpVisitor2<Integer> { @Override public Integer forDivide(Exp a, Exp b) {return a.accept(this) / b.accept(this);}}

就可以了：

Exp exp2 = new Divide(exp1, exp1);int res4 = exp2.accept(new ExpEvalVisitor2());

我們沒有修改任何已有代碼，完全是新加代碼，並且實現了Actions & Operations的擴展，Visitor模式的優勢在於分離的兩端，Visitor和Visitee都是可以擴展的，一邊代表Actions，一邊代表Operations。

可見OOP是很牛逼的一種編程範式。

如果你看過書，那麼書中的Visitor，其最終形式是這樣的：

public interface ExpVisitor<T> { public T forLiteral(Literal e); public T forAdd(Add e); public T forSubtract(Subtract e); public T forMultiply(Multiply e);}

注意變化在參數列表上，我們不在暴露具體實現，而是直接傳入variant，誠然，這樣更OO，封裝數據，對Visitor暴露的是數據的訪問方法，而不是數據本身，舉個簡單的例子：比如Point類，如果是傳數據的話，就只能是x,y兩個坐標信息，但如果傳入的是class對象本身，那麼我們就可以獲取很多東西，這樣就多了所有Actions都共享的中間邏輯層。

看到這裡，難免會有個疑問，這個和前篇文章里的模擬的Classic FP，是不是太像了？

Visitor Pattern & Classic FP

我在上面的代碼里故意將Visitor的實現，寫緊湊了，來看看下面的代碼是不是和Pattern Macthing去做destruction很像：

class ExpEvalVisitor implements ExpVisitor<Integer> { @Override public Integer forLiteral(int v) { return v; } @Override public Integer forAdd(Exp a, Exp b) { return a.accept(this) + b.accept(this); } @Override public Integer forSubtract(Exp a, Exp b) { return a.accept(this) - b.accept(this); } @Override public Integer forMultiply(Exp a, Exp b) { return a.accept(this) * b.accept(this); }}//vsint eval(Exp e) { return let(e).match( literal(v -> v), subtract((a, b) -> eval(a) - eval(b)), add((a, b) -> eval(a) + eval(b)), multiply((a, b) -> eval(a) * eval(b)) ).var;}

forLiteral(...) 你可以直接看成 case Literal(...)

關於datatype和data variants 與 FP 的 algebraic data type，基本上就是前者在模擬後者，不過需要注意的是：algebraic data type，是不支持隨意添加variants的（除了當前文件，不允許在別處添加variants）：

data Exp = Literal Int | Subtract Exp Exp | Add Exp Exp | ...

datatype及其variants就是AST，而visitors就是interpreter

雖然很像，但是Classic FP 並不支持Operations的擴展，原因在於上面的algebraic data type不支持隨意添加variants，以及pattern matching的alternative限制。

不過這只是Classic FP 不是 FP，在FP中完全可以通過引入Free Structure + Inject typeclass去補上丟失的擴展性，這叫「data types à la carte style」（我不知道怎樣念）。

Final tagless style

前面我們看到，我們最終將Visitor的參數改為了variants，如果繼續走下去，依然暴露的是數據，而不是訪問數據的方法會怎樣？

嗯，我們將可以丟棄datatype，是的，只留下Visitor：

public interface Exp<T> { public T literal(int v); public T add(T a, T b); public T subtract(T a, T b); public T multiply(T a, T b);}

我們將ExpVisitor改一下名字和方法名，並丟棄Exp datatype，都用類型參數T取代，沒錯著就變成了Final tagless style：

class Eval implements Exp<Integer> { @Override public Integer literal(int v) { return v; } @Override public Integer add(Integer a, Integer b) { return a + b; } @Override public Integer subtract(Integer a, Integer b) { return a - b; } @Override public Integer multiply(Integer a, Integer b) { return a * b; }}Eval e = new Eval();int res = e.add(e.literal(1), e.literal(2));

既然沒有了Visitee，那麼Visitor自然也不再是Visitor了，而是被稱之為algebraic（或其它名字比如：denotational semantic），而其實現Eval 則叫algebraic的interpreter（或semantic domian），我們將原來承裝數據的AST，全部轉為了函數（指稱），也就是用函數去表示AST的term的意義（函數體具體實現）； Actions 和 Operations都在一起了，有意思的是其擴展性卻不會有問題，和擴展前面Visitor一樣：

public interface DExp<T> extends Exp<T> { public T divide(T a, T b);}class DEval extends Eval implements DExp<Integer> { @Override public Integer divide(Integer a, Integer b) { return a / b; }}DEval de = new DEval();int res2 = de.divide(de.add(de.literal(1), de.literal(2)), de.literal(3));

這在OO里叫 Object Algebras [From Object Algebras to Finally Tagless Interpreters]

而這個轉變的過程稱之為「Boehm-Berarducci encoding」[http://okmij.org/ftp/tagless-?nal/course/Boehm-Berarducci.html] （類似Church encoding）

總結

1. Visitor模式是一種很牛的模式，如果對擴展性要求較高，優先考慮，甚至可以作為OO的基本編程方式

2. OO和FP之前果然還是同一mental model的不同representation

3. 如果你使用的OO語言支持FP，請不要太刻意去最求FP（畢竟部分支持，畢竟FP水太深），因為它能做到的，很有可能OO也能做到（甚至可能更好）

推薦閱讀：