Dispatching

Contents

Overview

Data models often require processing that involves model-traversal. A traversal starts at a root element, performs some acrtions and then moves on to other elements in the model that are reachable from the root. Each newly reached element is then treated as a new root. The traversal continues in this way, being careful not to get into a loop, until all the elements in the model have been processed and all the links have been traversed. XMF provides two convenient ways of defining model traversal. They are similar, but differ slightly:
This section describes how to define a simple dispatcher.

To top.

Lifting

Suppose that we want to construct an extensible facility to transform data elements into abstract syntax The idea is that if element d is transformed into abstract syntax e, then the evaluation of expression e produces d. This process if called lifting. For example, the integer 10 is lifted to produce:
IntExp(10)
and the sequence:
Seq{1,true,"s"}
is lifted to produce:
SetExp("Seq",Seq{IntExp(1),BoolExp(true),StrExp("s")})
This can be done by traversing the data element, producing an abstract syntax element for each component and then composing the abstract syntax. For example, the sequence shown above is translated by turning each element of the sequence into syntax and then building the set-expression.

We want the lifting facility to be extensible so that we can add new types of data element with associated new abstract syntax forms that define them. For example, classes have their own abstract syntax @Class ... end that defines them, as to packages, constraints and attributes. We want the facility to allow users to add their own definitions as extensions.

These requirements make dispatching a good candidate technology for lifting.

To top.

Defining A Dispatching Class

A dispatcher is a type of class. To use a dispatcher, you create an instance of the class and invoke an operation, supplying it with the dispatching data. Each instance of the dispatching class propduces a new instance with state that can be used to control the processing performed during the traversal. A simple lifting dispatcher is stateless, so it does not define any attributes:
@Class Lift metaclass Walkers::Dispatcher
    
end
To use a dispatcher you need to create an instance of the class and then invoke its 'dispatch' operation:
let lifter = Lift()
in lifter.dispatch(e,null)
end
In the above example, the data element e is supplied as the value to dispatch on: e controls the handler that is used to perform the traversal. The dispatch operation takes two arguments: the second can be anything and will be supplied to the handler. It is usual to supply null if the argument is not used.

As it stands, the lifting dispatcher will report an error, because it has no handlers. The next section describes how to add handlers to a dispatcher.

To top.

Defining Handlers

Handlers are added to a dispatching class. Handlers are like operations except that they are associated with a specific type of element. When an element is supplied for dispatch, the handler with the most specific type matching that of the element is chosen to perform the processing. A handler is defined as follows:
@Handler Type in DispatchingClass(element:Type,arg,encountered:Boolean)
  body
end;
The handler describes the type that it handles, the dispatching clas that it is to be added to and the names of three arguments: the dispatching data element, an arbitrary argument and a boolean value determining whether or not the element has been encountered before by the dispatcher during the current processing.

The handler for lifting integers is defined as follows:
@Handler Integer in Lift(i,arg,encountered)
  IntExp(i)
end;
The handler required to lift sequences shows how a handler calls the dispatcher on the component elements:
@Handler Seq(Element) in Lift(s,arg,encountered)
  if s->isEmpty
  then [| Seq{} |]
  else
 
    // In the body of a handler, 'self' refers to the
    // dispatching object... 
 
    [| Seq{<self.dispatch(s->head,arg)> | 
           <self.dispatch(s->tail,arg)>}  
    |]
  end
end;
A vector requires further processing:
@Handler Vector in Lift(v,arg,encountered)
  [| let vector = Vector(<IntExp(v.size())>)
     in <0.to(v.size() - 1)->iterate(i exp = var |
          [| <exp>;
             vector.put(<IntExp(i)>,<self.dispatch(v.ref(i),arg)>) 
          |])>
     end  
  |]
end;
To top.

Dispatchers with State

The lifting dispatcher does not provide any state or any auxilliary operations to help the handlers. This section extends the lifting dispatcher defined in the previous sections with some state and some operations to provide a more realistic lifting facility.

The dispatcher defined above, handles tree-shaped data elements but does not behave correctly with respect to data elements where the same element may occur twice (sharing). Furthermore, the lifting dispatcher above will not return if the data contains loops. Data can easily contain shared elements and loops for example:

let v = Vector(3);
    s = Seq{1,2,3}
in v.put(0,s);
   v.put(1,s);
   v.put(2,v);
   v
end
is the data element:
#(1)=Vector[0 =
              #(2)=Seq{1,2,3},
            1 =
              #(2),
            2 =
              #(1)]
The lifter must take account of the shared occurrences of the sequence and the cycle that occurs in the vector. To do this, we maintain an indexed collection of elements as they are encountered at dispatch-time and an equivalent indexed collection as they are created at run-time. If an element is encountered twice at dispatch-time then the generated code simply refers to the index of the elemen at run-time. The lifted code for the vector is as follows:
// Create a stack that is used to build an
// indexed collection of element...
let table = Stack()
in // Create the vector and record it
   // on the stack...
   table.push(Vector(3));
   let var1 = table.top()
   in var1;
      var1.put(0,
        // Create the sequence and record
        // the components on the stack...
        let var2 = Seq{null | null}
        in table.push(var2);
           var2->head := 1;
           var2->tail := 
             let var3 = Seq{null | null}
             in table.push(var3);
                var3->head := 2;
                var3->tail := 
                  let var4 = Seq{null | null}
                  in table.push(var4);
                     var4->head := 3;
                     var4->tail := Seq{};
                     var4
                  end;
                var3
             end;
          var2
        end);
 
      // The second and third components of the
      // vector are now available via their indices
      // on the stack...
 
      var1.put(1,table.ref(1));
      var1.put(2,table.ref(0))
   end
end
We redefine the class Lift with some state and operations to help with the generation of the code shown above:
@Class Lift metaclass Dispatcher 
  
  // The stack is used to record the elements as they
  // are encountered during dispatching. An equivalent 
  // stack is used to record the elements as they
  // are constructed at run-time. The handlers must
  // arrange for the run-time elements to occur at the 
  // same indices as the dispatch-time elements...
    
  @Attribute stack    : Stack = Stack() end
    
  // Local variables are used at run-time to manipulate
  // the elements as they are constructed. The dispatcher
  // uses the following counter to allocate unique variable
  // names...
    
  @Attribute varCount : Integer         end
    
  @Operation newVar()
    
    // Allocate a new variable with a unique name...
      
    self.varCount := varCount + 1;
    "var" + varCount.toString()
  end
    
end
Handlers for elements without state are the same as before since they cannot be shared. Elements with state must have handlers that behave differently if the element has been encountered before. If the element has not been encountered before then it is pushed onto the dispatch-time stack and code is generated that will construct the element at run-time and add it to the run-time stack. If the element has been encountered before in at dispatch-time then it will exist at run-time and code is generated that references the run-time element using the dispatch-time stack index.

Here is an example of a handler that is used when lifting sequences (actually sequences are treated as pairs with head and tail locations):
@Handler SeqOfElement in Lift(s,arg,encountered)
  if encountered
  then 
 
    // The pair has already been created and lives
    // on the run-time stack at the same location
    // as the pair s on the dispatch-time stack...
 
    [| <arg>.ref(<stack.indexOf(s).lift()>) |]
 
  elseif s->isEmpty
  then [| Seq{} |]
  else  
 
    // Record the pair s on the dispatch-time
    // stack...
 
    stack.push(s);
 
    // Create a unique variable that will be used
    // to refer to the pair at run-time...
 
    let var = Var(self.newVar())
    in 
       // Create the pair at run-time. Note that the
       // head and tail are empty at thie point...
  
       [| let <var.name> = Seq{null|null}
          in 
             // Record the pair on the run-time stack.
             // Careful to make sure the pair lives at 
             // the same location on the two stacks...
 
             <arg>.push(<var>);
             
 
             // Set the head and tail ...
 
             <var> ->head := <self.dispatch(s->head,arg)>;
             <var> ->tail := <self.dispatch(s->tail,arg)>;
 
             // Make sure we return the newly created pair 
             // since the caller may need it...
 
             <var>
          end
       |]
    end
  end
end;
To top.