DP11 解譯器模式、訪問者模式
===
###### tags: `DesignPatterns`

參考
[Design Patterns Elements of Reusable Object-Oriented Software](http://www.uml.org.cn/c++/pdf/DesignPatterns.pdf)

[大話設計模式](https://www.tenlong.com.tw/products/9789866761799)

[UML工具](https://plantuml-editor.kkeisuke.com/#)

[DesignPatternsPHP](https://github.com/domnikl/DesignPatternsPHP/blob/master/Behavioral/State/OrderContext.php)

[Head First Design Patterns: A Brain-friendly Guide](https://www.books.com.tw/products/F010315469)

[汤姆大叔的博客: 深入理解JavaScript系列](https://www.cnblogs.com/TomXu/archive/2011/12/15/2288411.html)

[從實例學設計模式 by Jace Ju](http://slides.com/jaceju/design-patterns-by-examples/#/)

[设计模式之美](https://www.cnblogs.com/gaochundong/p/design_patterns.html)

[UNC-GOF](http://www.cs.unc.edu/~stotts/GOF/hires/chap1fso.htm)

http://fabien.potencier.org/what-is-dependency-injection.html

https://github.com/domnikl/DesignPatternsPHP

# 解譯器模式(Interpreter pattern)

## 大話:

### 定義:
解譯器模式 (Interpreter pattern)，給定一個語言，定義它的文法中的一種表示，並定義一個解譯器，這個解譯器使用該表示來解釋語言中的句子。

#### 使用時機:
如果一種特定類型的問題發生的頻率夠高，那麼可能就值得將該問題的各個實體表達為一個簡單語言中的句子，這樣就可以建立一個解譯器，該解譯器透過解釋這些句子來解決該問題。(p.407)

當有一個語言需要解譯執行，並且你可將該語言中的句子表示為一個抽象語法樹時，可以使用解譯器模式。

用了解譯器模式，就意味著可以很容易地改變和擴展文法，因為該模式使用類別來表示文法規則，你可以使用繼承來改變或擴展該文法也比較容易實現文法，因為定義抽象語法樹中個個節點的類別實現大體相似，這些類別都易於直接編寫。

### 討論:

- 哪邊有用到呢? 樂譜、簡譜

## GOF

## Command Pattern

### Intent

Given a language, define a represention for its grammar along with an interpreter that uses the representation to interpret sentences in the language.

### Motivation

If a particular kind of problem occurs often enough, then it might be worth while to express instances of the problem as sentences in a simple language. Then you can build an interpreter that solves the problem by interpreting these sentences.

For example, searching for strings that match a pattern is a common problem. Regular expressions are a standard language for specifying patterns of strings. Rather than building custom algorithms to match each pattern against strings, search algorithms could interpret a regular expression that specifies a set of strings to match.

例如處理判斷 Email、電話、地址等需求時，不需要個別寫對應的 method，可以將這些判斷字串的規則統一抽出來，利用正規表示式來處理字串搜尋匹配需求。

The Interpreter pattern describes how to define a grammar for simple languages, represent sentences in the language, and interpret these sentences. In this example, the pattern describes how to define a grammar for regular expressions, represent a particular regularexpression, and how to interpret that regular expression.

Suppose the following grammar defines the regular expressions:

expression ::= literal | alternation | sequence | repetition | '(' expression ')'

alternation ::= expression '|' expression

sequence ::= expression '&' expression

repetition ::= expression '*'

literal ::= 'a' | 'b' | 'c' | ... { 'a' | 'b' | 'c' | ... }*

The symbol expression is the start symbol, and literalis a terminal symbol defining simple words.

The Interpreter pattern uses a class to represent each grammar rule. Symbols on the right-hand side of the rule are instance variables of these classes. The grammar above is represented by five classes: an abstract class RegularExpression and its four subclasses LiteralExpression, AlternationExpression, SequenceExpression, and RepetitionExpression. The last three classes define variables that hold subexpressions.


Every regular expression defined by this grammar is represented by anabstract syntax tree made up of instances of these classes. Forexample, the abstract syntax tree


represents the regular expression

raining & (dogs | cats) *

We can create an interpreter for these regular expressions by definingthe Interpret operation on each subclass of RegularExpression.Interpret takes as an argument

the context in which to interpret theexpression. The context contains the input string and information onhow much of it has been matched so far. Each subclass ofRegularExpression implements Interpret to match the next part of theinput string based on the current context. For example,

- LiteralExpression will check if the input matches the literal it defines,

- AlternationExpression will check if the input matches any of its alternatives,

- RepetitionExpression will check if the input has multiple copies of expression it repeats,

and so on.

### Also Known As

### Applicability
Use the Interpreter pattern when there is a language to interpret, andyou can represent statements in the language as abstract syntax trees.The Interpreter pattern works best when

- the grammar is simple. For complex grammars, the class hierarchy forthe grammar becomes large and unmanageable. Tools such as parsergenerators are a better alternative in such cases. They can interpretexpressions without building abstract syntax trees, which can savespace and possibly time.

- efficiency is not a critical concern. The most efficient interpretersare usually not implemented by interpreting parse trees directlybut by first translating them into another form. For example, regularexpressions are often transformed into state machines. But even then,the translator can be implemented by the Interpreter pattern, sothe pattern is still applicable.
### Structure

### Participants

- AbstractExpression (RegularExpression)

- declares an abstract Interpret operation that is common to all nodes in the abstract syntax tree.
- TerminalExpression (LiteralExpression)
- implements an Interpret operation associated with terminal symbols in the grammar.
- an instance is required for every terminal symbol in a sentence.
- NonterminalExpression (AlternationExpression,RepetitionExpression, SequenceExpressions)

- one such class is required for every rule R ::= R1R2 ... Rn in the grammar.
- maintains instance variables of type AbstractExpression for each of the symbols R1 through Rn.
- implements an Interpret operation for nonterminal symbols in the grammar. Interpret typically calls itself recursively on the variables representing R1 through Rn.
- Context
- contains information that's global to the interpreter.
- Client
- builds (or is given) an abstract syntax tree representing a particular sentence in the language that the grammar defines. The abstract syntax tree is assembled from instances of the NonterminalExpression and TerminalExpression classes.
- invokes the Interpret operation.

### Collaborations

- The client builds (or is given) the sentence as an abstract syntaxtree of NonterminalExpression and TerminalExpression instances. Then the client initializes the context and invokes the Interpretoperation.
- Each NonterminalExpression node defines Interpret in terms ofInterpret on each subexpression. The Interpret operation of eachTerminalExpression defines the base case in the recursion.
- The Interpret operations at each node use the context to store and access the state of the interpreter.
-
### Consequences

The Interpreter pattern has the following benefits and liabilities:

1. It's easy to change and extend the grammar.Because the pattern uses classes to represent grammar rules, you canuse inheritance to change or extend the grammar. Existing expressionscan be modified incrementally, and new expressions can be defined asvariations on old ones.

2. Implementing the grammar is easy, too. Classes defining nodes in the abstract syntax tree have similar implementations. These classes are easy to write, and often their generation can be automated with a compiler or parser generator.

3. Complex grammars are hard to maintain.The Interpreter pattern defines at least one class for every rule in the grammar (grammar rules defined using BNF may require multiple classes). Hence grammars containing many rules can be hard tomanage and maintain. Other design patterns can be applied tomitigate the problem (see Implementation).But when the grammar is very complex, other techniques such as parser or compiler generators are more appropriate.

4. Adding new ways to interpret expressions. The Interpreter pattern makes it easier to evaluate an expression in anew way. For example, you can support pretty printing or type-checking an expression by defining a new operation on the expression classes. **If you keep creating new ways of interpreting an expression, then consider using the Visitor (366) pattern to avoid changing the grammar classes.**

### Implementation

The Interpreter and Composite (183) patterns share many implementation issues. The following issues are specific to Interpreter:

1. Creating the abstract syntax tree. The Interpreter pattern doesn't explain how to create an abstract syntax tree. In other words, it doesn't address parsing.The abstract syntax tree can be created by a table-driven parser, by a hand-crafted (usually recursive descent) parser, or directly by the client.

2. Defining the Interpret operation. You don't have to define the Interpret operation in the expression classes. If it's common to create a new interpreter, then it's betterto use the Visitor (366) pattern to put Interpret in a separate "visitor" object. For example, a grammar for a programming language will have many operations on abstract syntax trees, such asas type-checking, optimization, code generation, and so on. It will bemore likely to use a visitor to avoid defining these operations onevery grammar class.

3. **Sharing terminal symbols with the Flyweight pattern.** Grammars whose sentences contain many occurrences of a terminal symbolmight benefit from sharing a single copy of that symbol. Grammars forcomputer programs are good examples—each program variable will appear in many places throughout the code. In the Motivation example,a sentence can have the terminal symbol dog (modeled by the LiteralExpression class) appearing many times.

Terminal nodes generally don't store information about their positionin the abstract syntax tree. Parent nodes pass them whatever contextthey need during interpretation. Hence there is a distinction betweenshared (intrinsic) state and passed-in (extrinsic) state, and the Flyweight (218) pattern applies.

For example, each instance of LiteralExpression for dog receives a context containing the substring matched so far. And everysuch LiteralExpression does the same thing in its Interpret operation—it checks whether the next part of the input contains a dog—no matter where the instance appears in the tree.

### Known Uses

The Interpreter pattern is widely used in compilers implemented with object-oriented languages, as the Smalltalk compilers are. SPECTalkuses the pattern to interpret descriptions of input fileformats [Sza92]. The QOCA constraint-solving toolkituses it to evaluate constraints [HHMV92].

Considered in its most general form (i.e., an operation distributed over a class hierarchy based on the Composite pattern), nearly every use of the Composite pattern will also contain the Interpreter pattern. But the Interpreter pattern should be reserved for those cases in which you want to think of the class hierarchy as defining a language.

### Related Patterns

Composite (183) : The abstract syntax tree is an instance of the Composite pattern.

Flyweight (218) shows how to share terminal symbols within the abstract syntaxtree.

Iterator (289) : The interpreter can use an Iterator to traverse the structure.

Visitor (366) canbe used to maintain the behavior in each node in the abstract syntaxtree in one class.

---

# 訪問者模式(Visitor pattern)

## 大話:

### 定義: 訪問者模式(Visitor pattern)，表示一個作用於某物件結構中的各元素之操作。它使你可以在不改變個元素之類別的前提下，定義作用於這些元素的新操作。

#### 使用時機:

訪問者模式適用於資料結構相對穩定的系統。他把資料結構和作用於結構上的操作之間的耦合脫開，使得操作集合可以相對地自由演化。
(如果是不穩定的系統，可能經常異動 Element，那麼 Visitor 和 ConcreateVisitor 也必須新增對應 method，違反 OCP)

訪問者模式的目的是要把處理從資料結構分離出來。
很多系統可以按照演算法和資料結構分開，如果這樣的系統**有比較穩定的資料結構，又有易於變化的演算法的畫，使用訪問者模式就是比較合適的，因為訪問者模式使得演算法操作的增加變得容易**

訪問者模式的優點就是增加新的操作很容易，因為增加新的操作就意味著增加一個新的訪問者。訪問者模式將有關的行為集中的一個訪問者物件中。

通常 ConcreteVisitor 可以單獨開發，不必跟 ConcreteElementA 或 ConcreteElementB 寫在一起。 正因為這樣 ConcreteVisitor 能提高 ConcreteElement 之間的獨立性，如果把一個動作處理設計成 ConcreteElementA 和 ConcreteElementB
類別中的方法，每次想新增"處理"以擴充功能時，就得去修改 ConcreteElementA 和 ConcreteElementB 了。

訪問者的缺點就是使得增加新的資料結構變得困難了。

大多數時候你並不需要訪問者模式，但當一但你需要訪問者模式時，那就真的需要他了。

### 討論:

- 哪邊有用到呢?

- 哪邊可以用?

## GOF

## Command Pattern

### Intent

Represent an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.

### Motivation

Consider a compiler that represents programs as abstract syntax trees.It will need to perform operations on abstract syntax trees for "static semantic" analyses like checking that all variables are defined. It will also need to generate code. So it might define operations for type-checking, code optimization, flow analysis, checking for variablesbeing assigned values before they're used, and so on. Moreover, we coulduse the abstract syntax trees for pretty-printing, program restructuring, code instrumentation, and computing various metrics of a program.

Most of these operations will need to treat nodes that represent assignment statements differently from nodes that represent variables or arithmetic expressions. Hence there will be one class for assignment statements, another for variable accesses, another for arithmetic expressions, and so on. The set of node classes depends on the language being compiled, of course, but it doesn't change much for a given language.


This diagram shows part of the Node class hierarchy. The problem here is that distributing all these operations across the various node classes leads to a system that's hard to understand, maintain, and change. It will be confusing to have type-checking code mixed with pretty-printing code or flow analysis code. Moreover, adding a new operation usually requires recompiling all of these classes. It would bebetter if each new operation could be added separately, and the node classes were independent of the operations that apply to them.

We can have both by packaging related operations from each class in a separate object, called a visitor, and passing it to elements of the abstract syntax tree as it's traversed. When an element "accepts" the **visitor**, it sends a request to the visitor that encodesthe element's class. It also includes the element as an argument. The visitor will then execute the operation for that element—the operation that used to be in the class of the element.

For example, a compiler that didn't use visitors might type-check a procedure by calling the TypeCheck operation on its abstract syntaxtree. Each of the nodes would implement TypeCheck by calling TypeCheck on its components (see the preceding class diagram). If the compiler type-checked a procedure using visitors, then it would create a TypeCheckingVisitor object and call the Accept operation on the abstract syntax tree with that object as an argument. Each of the nodes would implement Accept by calling back on the visitor: an assignment node calls VisitAssignment operation on the visitor, while a variable reference calls VisitVariableReference. What used to be the TypeCheck operation in class AssignmentNode is now the VisitAssignment operation on TypeCheckingVisitor.

To make visitors work for more than just type-checking, we need an abstract parent class NodeVisitor for all visitors of an abstract syntaxtree. NodeVisitor must declare an operation for each node class. Anapplication that needs to compute program metrics will define newsubclasses of NodeVisitor and will no longer need to add application-specific code to the node classes. The Visitor pattern encapsulates the operations for each compilation phase in a Visitor associated with that phase.



**With the Visitor pattern, you define two class hierarchies: one for the elements being operated on (the Node hierarchy) and one for the visitors that define operations on the elements (the NodeVisitor hierarchy). You create a new operation by adding a new subclass to the visitor classhierarchy. As long as the grammar that the compiler accepts doesn't change (that is, we don't have to add new Node subclasses), we can addnew functionality simply by defining new NodeVisitor subclasses.**

### Applicability

Use the Visitor pattern when

- an object structure contains many classes of objects with differing interfaces, and you want to perform operations on these objects that depend on their concrete classes.

- many distinct and unrelated operations need to be performed on objects in an object structure, and you want to avoid "polluting" their classes with these operations. Visitor lets you keep related operations together by defining them in one class. When the object structure is shared by many applications, use Visitor to put operations in just those applications that need them.

- the classes defining the object structure rarely change, but you often want to define new operations over the structure. Changing the objectstructure classes requires redefining the interface to all visitors, which is potentially costly. If the object structure classes change often, then it's probably better to define the operations in those classes.

### Structure


### Participants

- Visitor (NodeVisitor)
- declares a Visit operation for each class of ConcreteElement in the object structure. The operation's name and signature identifies the class that sends the Visit request to the visitor. That lets the visitor determine the concrete class of the element being visited. Then the visitor can access the element directly through its particular interface.

- ConcreteVisitor (TypeCheckingVisitor)
- implements each operation declared by Visitor. Each operation implements a fragment of the algorithm defined for the corresponding class of object in the structure. ConcreteVisitor provides the context for the algorithm and stores its local state. This state often accumulates results during the traversal of the structure.

- Element (Node)
- defines an Accept operation that takes a visitor as an argument.

- ConcreteElement (AssignmentNode,VariableRefNode)
- implements an Accept operation that takes a visitor as an argument.

- ObjectStructure (Program)
- can enumerate its elements.
- may provide a high-level interface to allow the visitor to visit its elements.
- may either be a composite (see Composite (183)) or a collection such as a list or a set.

### Collaborations

- A client that uses the Visitor pattern must create a ConcreteVisitor object and then traverse the object structure, visiting each element with the visitor.

- When an element is visited, it calls the Visitor operation that corresponds to its class. The element supplies itself as an argument to this operation to let the visitor access its state, if necessary.

The following interaction diagram illustrates the collaborations between an object structure, a visitor, and two elements:


### Consequences

Some of the benefits and liabilities of the Visitor pattern are as follows:

1. **Visitor makes adding new operations easy.** Visitors make it easy to add operations that depend on the components ofcomplex objects. You can define a new operation over an object structuresimply by adding a new visitor. In contrast, if you spread functionality over many classes, then you must change each class to define a new operation.

2. **A visitor gathers related operations and separates unrelated ones.** Related behavior isn't spread over the classes defining the object structure; it's localized in a visitor. Unrelated sets of behavior are partitioned in their own visitor subclasses. That simplifies both theclasses defining the elements and the algorithms defined in the visitors. Any algorithm-specific data structures can be hidden in thevisitor.

3. **Adding new ConcreteElement classes is hard.** The Visitor pattern makes it hard to add new subclasses of Element. Each new ConcreteElement gives rise to a new abstract operation on Visitor anda corresponding implementation in every ConcreteVisitor class. Sometimes a default implementation can be provided in Visitor that can be inherited by most of the ConcreteVisitors, but this is the exception rather than the rule.

So the key consideration in applying the Visitor pattern is whether you are mostly likely to change the algorithm applied over an objects tructure or the classes of objects that make up the structure. **The Visitor class hierarchy can be difficult to maintain when new ConcreteElement classes are added frequently.** In such cases, it'sprobably easier just to define operations on the classes that make up the structure. If the Element class hierarchy is stable, but you are continually adding operations or changing algorithms, then the Visitor pattern will help you manage the changes.

在還不穩定或式不確定之前，建議先將 method 統一加在 element 裡面，等到需要時再考慮訪問者模式。

4. **Visiting across class hierarchies.** An **iterator** (see Iterator (289)) can visit the objects in a structure as it traverses them by calling their operations. But an iterator can't work across object structures with different types of elements. For example, the Iterator interface defined on page 295 can access only objects of type Item:

template <class Item> 
class Iterator { 
    // ...   
    Item CurrentItem() const; 
};

This implies that all elements the iterator can visit have a common parentclass Item.

Visitor does not have this restriction. It can visit objects that don't have a common parent class. You can add any type of object to a Visitor interface. For example, in

class Vistior {
public:
    // ...
    void VisitMyType(MyType*); 
    void VisitYourType(YourType*); 
};

MyType and YourType do not have to be related through inheritance at all.

5. **Accumulating state.** Visitors can accumulate state as they visit each element in the object structure. Without a visitor, this state would be passed as extra arguments to the operations that perform the traversal, or they might appear as global variables.

6. **Breaking encapsulation.** Visitor's approach assumes that the ConcreteElement interface is powerful enough to let visitors do their job. As a result, the pattern often forces you to provide public operations that access an element's internal state, which may compromise its encapsulation.

### Implementation

Each object structure will have an associated Visitor class. This abstract visitor class declares a VisitConcreteElement operation foreach class of ConcreteElement defining the object structure. EachVisit operation on the Visitor declares its argument to be a particular ConcreteElement, allowing the Visitor to access the interface of the ConcreteElement directly. ConcreteVisitor classes override each Visit operation to implement visitor-specific behavior for the corresponding ConcreteElement class.

The Visitor class would be declared like this in C++:

class Visitor { 
public:  
    virtual void VisitElementA(ElementA*);  
    virtual void VisitElementB(ElementB*);  

    // and so on for other concrete elements 
    
protected:  
    Visitor(); 
}; 

Each class of ConcreteElement implements an Accept operation that calls the matching Visit... operation on the visitorfor that ConcreteElement. Thus the operation that ends up getting called depends on both the class of the element and the class of the visitor.

The concrete elements are declared as

class Element {
public:
    virtual ~Element();
    virtual void Accept(Visitor&) = 0;

protected:
    Element();
};

class ElementA : public Elememt {
public:
    ElementA();
    virtual void Accept(Visitor& v) { v.VisitElementA(this); }
};

class ElementB : public Elememt {
public:
    ElementB();
    virtual void Accept(Visitor& v) { v.VisitElementB(this); }
};

A CompositeElement class might implement Accept like this:

class CompositeElement : public Element {
public :
    virtural void Accept(Visitor&);
private:
    List<Element*>* _children;
};

void CompositeElement::Accept (Visitor& v) {
    ListIterator<Element*> i(_children);
    
    for (i.First(); !i.IsDone(); i.Next()) {
        i.CurrentItem()->Accept(v);
    }
    
    v.VisitCompositeElement(this);
}

Here are two other implementation issues that arise when you apply theVisitor pattern:

1. **Double dispatch.** Effectively, the Visitor pattern lets you add operations to classes without changing them. Visitor achieves this by using a technique called **double-dispatch**. It's a well-known technique. In fact, some programming languages support it directly (CLOS, for example). Languages like C++ and Smalltalk support **single-dispatch**.

In single-dispatch languages, two criteria determine which operation will fulfill a request: the name of the request and the type of receiver. For example, the operation that a GenerateCode request will call depends on the type of node object you ask. In C++, calling GenerateCode on an instance of VariableRefNode will call VariableRefNode::GenerateCode (which generates code for a variable reference). Calling GenerateCode on an AssignmentNode will callAssignmentNode::GenerateCode (which will generate code for an assignment). **The operation that gets executed depends both on the kind of request and the type of the receiver.**

"Double-dispatch" simply means **the operation that gets executed depends on the kind of request and the types of two receivers.** **Accept is a double-dispatch operation. Its meaning depends on two types: the Visitor's and the Element's.** Double-dispatchinglets visitors request different operations on each class ofelement.

This is the key to the Visitor pattern: The operation that gets executed depends on both the type of Visitor and the type of Element it visits. Instead of binding operations statically into the Element interface, **you can consolidate the operations in a Visitor and use Accept to do the binding at run-time.** Extending the Element interface amounts to defining one new Visitor subclass rather than many new Element subclasses.

2. **Who is responsible for traversing the object structure?** A visitor must visit each element of the object structure. The questionis, how does it get there? We can put responsibility for traversal in any of three places: in the object structure, in the visitor, or in aseparate iterator object (see Iterator (289)).

**Often the object structure is responsible for iteration.** A collection will simply iterate over its elements, calling the Accept operation on each. A composite will commonly traverse itself by having each Accept operation traverse the element's children and call Accept on each ofthem recursively.

**Another solution is to use an iterator to visit the elements.** In C++,you could use either an internal or external iterator, depending on whatis available and what is most efficient. In Smalltalk, you usually use an internal iterator using do: and a block. Since internal iterators are implemented by the object structure, using an internal iterator is a lot like making the object structure responsible foriteration. The main difference is that an internal iterator will not cause double-dispatching—it will call an operation on the visitor with an element as an argument as opposed to calling anoperation on the element with the visitor as an argument. **But it's easy to use the Visitor pattern with an internal iterator if the operation on the visitor simply calls the operation on the element without recursing.**

You could even put the traversal algorithm in the visitor, although you'll end up duplicating the traversal code in each ConcreteVisitor for eachaggregate ConcreteElement. The main reason to put the traversal strategy in the visitor is to implement a particularly complex traversal, one that depends on the results of the operations on the object structure.We'll give an example of such a case in the Sample Code.

### Known Uses

The Smalltalk-80 compiler has a Visitor class called ProgramNodeEnumerator. It's used primarily for algorithms that analyze source code. It isn't used for code generation or pretty-printing, although it could be.

IRIS Inventor [Str93] is a toolkit for developing 3-D graphics applications. Inventorre presents a three-dimensional scene as a hierarchy of nodes, each representing either a geometric object or an attribute of one. Operations like rendering a scene or mapping an input event require traversing this hierarchy in different ways. Inventor does thisusing visitors called "actions." There are different visitors forrendering, event handling, searching, filing, and determiningbounding boxes.

To make adding new nodes easier, Inventor implements a double-dispatch scheme for C++. The scheme relies on run-time type information and a two-dimensional table in which rows represent visitors and columns represent node classes. The cells store apointer to the function bound to the visitor and node class.

Mark Linton coined the term "Visitor" in the X Consortium's Fresco Application Toolkit specification [LP93].

### Related Patterns
Composite (183) : Visitors can be used to apply an operation over an object structuredefined by the Composite pattern.

Interpreter (274) : Visitor may be applied to do the interpretation.