Back Home Up Next

VISITOR

1 Purpose

2 Problem Description

3 Domain Definitions

4 Elisa Components

1  Purpose

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.

2  Problem Description 

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 variables being assigned values before they're used, and so on. Moreover, we could use 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 AssignmentNodes 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 be better 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 encodes the 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 syntax tree. 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 syntax tree. NodeVisitor must declare an operation for each node class. An application that needs to compute program metrics will define new subclasses 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 class hierarchy. 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 add new functionality simply by defining new NodeVisitor subclasses.

3  Domain Definitions

We will transform the top-level relations into a set of corresponding domain definitions:

NodeVisitor  =  TypeCheckingVisitor | CodeGeneratingVisitor

Node  =  AssignmentNode  | VariableRefNode 

The next step is to translate the domain definitions into a number of Elisa components. In addition, we will use skeletons of definitions as shown in the preceding domain relationships

4  Elisa components 

Based on the domain definitions a set of related components are derived. The first component implements  a skeleton of the  NodeVisitor domain.

component NodeVisitors;
type NodeVisitor = category(
TypeCheckingVisitor,CodeGeneratingVisitor);

     VisitAssignment(NodeVisitor, AssignmentNode)   -> result;

     VisitVariableRef(NodeVisitor, VariableRefNode) -> result;

          . . .
begin

            <<implementations of >>

     VisitAssignment(TypeCheckingVisitor:typeVisitor, assignmentNode) = VisitAssignment(typeVisitor, assignmentNode);

     VisitAssignment(CodeGeneratingVisitor:codeVisitor, assignmentNode) = VisitAssignment(codeVisitor, assignmentNode);

          . . .

     VisitVariableRef(TypeCheckingVisitor:typeVisitor, variableRefNode) = VisitVariableRef(typeVisitor, variableRefNode);

     VisitVariableRef(CodeGeneratingVisitor:codeVisitor, variableRefNode) = VisitVariableRef(codeVisitor, variableRefNode);

          . . .

end component NodeVisitors;

 

 

The following component is a skeleton example of a TypeCheckingVisitor  component:

 

component TypeCheckingVisitors;
type TypeCheckingVisitor;

     CreateTypeCheckingVisitor( ) -> TypeCheckingVisitor;

     VisitAssignment(TypeCheckingVisitor, AssignmentNode) -> result;

     VisitVariableRef(TypeCheckingVisitor, VariableRefNode) -> result;

      . . .
begin

            <<implementations of >>

     CreateTypeCheckingVisitor( ) = TypeCheckingVisitor:[ ... ]; 

     VisitAssignment(typeCheckingVisitor, assignmentNode) = ...;

     VisitVariableRef(typeCheckingVisitor, variableRefNode) = ...;

          . . .

end component TypeCheckingVisitors;

 

 

The following component is a skeleton example of a CodeGeneratingVisitor component:

 

component CodeGeneratingVisitors;
type CodeGeneratingVisitor;

     CreateCodeGeneratingVisitor( ) -> CodeGeneratingVisitor;

     VisitAssignment(CodeGeneratingVisitor, AssignmentNode) -> result;

     VisitVariableRef(CodeGeneratingVisitor, VariableRefNode) -> result;

      . . .
begin

            <<implementations of >>

     CreateCodeGeneratingVisitor( ) = CodeGeneratingVisitor:[ ... ]; 

     VisitAssignment(codeGeneratingVisitor, assignmentNode) = ...;

     VisitVariableRef(codeGeneratingVisitor, variableRefNode) = ...;

          . . .

end component CodeGeneratingVisitors;

 

 

The following component is a skeleton example of a Node component:

 

component Nodes;
type Node = category(AssignmentNode, VariableRefNode);

     Accept(Node,NodeVisitor) -> result;

      . . .
begin

            <<implementations of >>

     Accept(AssignmentNode:assnode,nodeVisitor) = Accept(assnode, nodeVisitor);

     Accept(VariableRefNode:varnode,nodeVisitor) = Accept(varnode, nodeVisitor);

          . . .

end component Nodes;

 

 

The following component is a skeleton example of a AssignmentNode component:

 

 

component AssignmentNodes;
type AssignmentNode;

     CreateAssignmentNode(Node) -> AssignmentNode;

     Node(AssignmentNode) -> Node; 

     Accept(AssignmentNode, NodeVisitor) -> result;

      . . .
begin

            <<implementations of >>

     CreateAssignmentNode(node) = AssignmentNode:[ ..node... ];

     Node(assignmentNode) = assignmentNode.node; 

     Accept(assignmentNode, nodeVisitor) = [ ... VisitAssignment(nodeVisitor, assignmentNode)...];

          . . .

end component AssignmentNodes;

 

 

The following component is a skeleton example of a VariableRefNode component:

 

 

component VariableRefNodes;
type VariableRefNode;

     CreateVariableRefNode(Node) -> VariableRefNode;

     Node(VariableRefNode) -> Node; 

     Accept(VariableRefNode, NodeVisitor) -> result;

      . . .
begin

            <<implementations of >>

     CreateVariableRefNode(node) = VariableRefNode:[ ..node... ];

     Node(variableRefNode) = variableRefNode.node; 

     Accept(variableRefNode,nodeVisitor) = [...VisitVariableRef(nodeVisitor,variableRefNode)...];

          . . .

end component VariableRefNodes;

 

 

 

Back Home Up Next

  Part 5: Design Patterns   Visitor

            
Introduction

Home | Highlights of Elisa | Integrating Different Paradigms | Getting Started with Elisa | Demo's  | What is Domain Orientation | Bibliography | Copyright | News | Contact | Contents

Language Description:

Lexical Elements | Basic Data Types and Expressions | Definitions | Streams | Backtracking | Statements and Special Expressions | Arrays | Lists | Descriptors | Components | Collections | Generic Components | Terms | Categories | Types | Built-in Definitions | Higher-order Definitions | External Interfaces | Index 

Data Structures: Sequences | Examples involving Lists | Trees | Graphs | Searching State Spaces | Language Processing | Knowledge Representations
Domain Modeling:

Domain Modeling | Concepts | Domain Definitions | Domain Operations | Domain Implementations | Systems | Case study: an Order processing system | Case study: an Airport Support system | Domain Orientation versus Object Orientation

Design Patterns:

Introduction | Abstract Factory | Builder | Factory Method | Prototype | Singleton | Adapter | Bridge | Composite | Decorator | Facade | Flyweight | Proxy | Chain of Responsibility | Command | Interpreter | Iterator | Mediator | Memento | Observer | State | Strategy | Template Method | Visitor 

 

click tracking

 

Send me your comments

 

This page was last modified on 07-12-2012 15:50:31   

free hit counter