Visitor pattern traversal using double/single dispatch software design pattern

[thnd23]

Hello again,

Recently I created an issue that Rascal language misses visitor pattern traversal. Your implementation with case and pattern with action by definition is not a Visitor pattern implementation. This software pattern relies on having double dispatch method one on the language nodes and the other one on the visit class itself. Python language handles this with a single dispatch. What Rascal does is that it matches something to a pattern, this is not the same as calling function/method on given language node.

Following image (taken from Wikipedia that you reference in your documentation) showcase simple UML class diagram of visitor pattern implementation.

Where is the visit and accept method? How do you by default visit specific language node? How do you access its properties?

My capacity might be insufficient to understand Rascal's Visitor pattern implementation. If that is the case, could you extend your documentation with an appropriate example to avoid any future confusion?

As a suggeted example here is Python's solution:

[jurgenvinju]

Hi there.

We called it the visit statement in Rascal, but it is not an implementation of the Object-oriented Visitor design pattern, or even related in any way. What visit does is a recursive "traversal" of a nested data-structure (tree, set, list, etc.) and apply the case to every level in the tree and to every sibling on that level, in a specific order. By default it's a bottom-up traversal and you can also choose other orders (like top-down).

Because Rascal has a dynamic dispatch mechanism which is not bound by a single receiver object, like in OO, there is no need for something like the "Visitor design pattern" in Rascal. You can dispatch on function parameter, or even two parameters at the same time! As a result, there is no need for "double dispatch" idioms at all in this language.

Consider this example:

data Exp = add(Exp l, Exp r) | zero();

Exp add(zero(), Exp r) = r;
Exp add(Exp l, zero()) = l;

The add function dispatches to one of the three alternatives (either the constructor or one of the two rewrite rules) based on the value of the left or the right argument (if its zero() or not). The Rascal language handles this kind of nested dispatch and you do not have to encode it using a Visitor design pattern like you would in an OO language which does not offer this kind of dispatch mechanism.

Similarly the cases of the visit statement dispatch dynamically using arbitrarily deep pattern matching which automates all of the dispatching you would have to encode using (generic) visitor design pattern code in other languages.

Here's an example where visit dispatches to all the add nodes and rewrites them if either their left or right child is zero(). It has the same effect as the above two definitions, but now it only happens when you run this code:

visit (add(add(zero(), add(zero(), zero()))) {
   case add(zero(), r) => r
  case  add(l, zero())  => l
}

Hope this helps!

[jurgenvinju]

It also helps to realize that Rascal does not have objects. It has modules as encapsulation of a set of functions. The functions do the dispatching and the modules are just collections of these functions. This is very much unlike object-oriented languages where the data and the functions are coupled together semantically.

[jurgenvinju]

About accessing properties:

• either we pattern match like so: add(l, r) matches any add node and binds the left-hand side and the right-hand side to l and r
• or we use field access notation like so: myExp.l accesses the l field of the add constructor or throws an exception if myExp is not an add (but a zero).
• or we use "keyword fields", which provide default values, like so: data Exp zero(int depth=0) and zero().depth == 0, or zero(depth=3).depth == 3

[thnd23]

Thank you very much for clarification. I am more than familiar with visitor pattern and I already built control flow generator using Python's Visitor pattern implementation. Every other definition on the internet mentions double dispatch that only makes sense for me when its applied to objects.

Edit: You should definitely remove reference to "Visitor pattern Wikipedia" because it will only confuse people since it seems like OO design pattern. This explanation is needed in documentation.

Edit2: Consider the following situation: I have an implementation written in object-oriented programming language C++. I decide to use Rascal to parse the C++ into an AST. How do I write visit "module" in such a way that I walk through all the function declarations (in my understanding objects with properties) and print out all their names and arguments.

[jurgenvinju]

• thanks for the advice @thnd23 ; removing the Visitor design pattern reference from the documentation should indeed help.
• the example code you asked for, given some kind of data definition for the C++ AST, I just made up (but you can check a real one for C++ here: https://github.com/cwi-swat/clair/blob/master/src/lang/cpp/AST.rsc)

import IO;

void printNamesAndArgumentsOfFunctions(Class myAST) {
   visit(myAST) {
      case functionDeclaration(_, name, formals): 
         println("found a function named <name> with parameters: <formals>");
   }
}

The _ in the pattern ignores the return type of the declaration.

Let's say each formal parameter is represented as parameter(Type t, str name) then you could print out only the names like so using a string template:

println("<for (parameter(_, n) <- formals) {>a parameter: <n>
        '<}>");

[thnd23]

Thank you very much for the explanation. It is really appreciated and it clarified what I did not understand.