Re: how do i implement double-dispatching?

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

cl1motorsports wrote:

> I'm trying to implement double dispatching with a visitor pattern in (of
> course) Ada. I have a parse tree package that has all the node types of
> the tree, and i have a visitor package with an abstract visitor type that
> has a Visit operation for all the types in the parse tree. It doesn't want
> to compile the way i have it written. I have provided a shortened version
> of the parse tree and abstract visitor code with gnatmake errors below. If
> anyone has a solution to this please point me in the correct direction. My
> purpose here is to implement a framework for pretty-printers, html-izers,
> language translators (e.g c2ada) all from the same parse tree without
> having to recompile the parse tree. basically the framework user will
> create a new type that inherits from the abstract visitor type to insure
> that operations for each type of node in the parse tree are implemented.
> Just thought i would give some background info on the code so you would
> know why i tried to implement it like this and so you could give a
> solution within the domain. well enough ranting, On to the Code!!!
> 
> -- parse_tree_pkg.ads
> 
> with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
> package Parse_Tree_Pkg is
> 
>    -- abstract parse tree node
>    type Parse_Tree_Node_Record is abstract tagged
>       record
>          Start_Line   : Integer;
>          Start_Column : Integer;
>          End_Line     : Integer;
>          End_Column   : Integer;
>       end record;
>    type Parse_Tree_Node is access Parse_Tree_Node_Record'Class;
> 
>    -- actual(concrete) parse tree nodes
>    type Equal_Op is new Parse_Tree_Node_Record with null record;
> 
>    type Number_Node is new Parse_Tree_Node_Record with
>       record
>          Value : Float;
>       end record;
> 
>    type Name_Node is new Parse_Tree_Node_Record with
>       record
>          Value : Unbounded_String;
>       end record;
> 
>    type Assignment_Node is new Parse_Tree_Node_Record with
>       record
>          Name       : Parse_Tree_Node;
>          Equal      : Parse_Tree_Node;
>          Expression : Parse_Tree_Node;
>       end record;
> 
> end Parse_Tree_Pkg;
> 
> -- abstract_visitor.ads
> 
> with Parse_Tree_Pkg; use Parse_Tree_Pkg;
> package Abstract_Visitor is
>    -- This package provides a visitor interface
>    -- so that operations can be created independant
>    -- of the parse tree.
>    -- If you want to implement a visitor to run
>    -- operations on the parse tree you must "with" this
>    -- package and create all the visit operations in
>    -- it.
> 
>    type Visitor_Record is abstract tagged null record;
>    type Visitor_Access is access Visitor_Record'Class;
> 
>    procedure Visit(V : in out Visitor_Record; Node : in Equal_Op) is
>    abstract;

procedure Visit
          (  V    : in out Visitor_Record;
             Node : Parse_Tree_Node_Record'Class
          )  is abstract;

Ada has a restricted form of multiple dispatch, which cannot be applied in
your case. So Visit has to be dispatching in only one parameter. An
implementation of Visit in a derived visitor type has to emulate dispatch
on the second parameter:

type My_Fashioned_Visitor is new Visitor_Record with private;
procedure Visit
          (  V    : in out My_Fashioned_Visitor;
             Node : Parse_Tree_Node_Record'Class
          )  is
begin
   if Node in Equal_Op'Class then
      -- Visiting Equal_Op or its derivate
      ...
   elsif Node in Number_Node'Class then
      ...
   elsif Node in Name_Node'Class then
      ...
   elsif Node in Assignment_Node'Class then
      ...
   else
      raise Constraint_Error; -- Who knows this Node?
   end if;
end Visit;

When the number of different nodes is known it is OK.

Note that there is a choice, you can make Visit dispatching in the Node
parameter:

with Abstract_Visitor;
...
type Parse_Tree_Node_Record is abstract ...;
procedure Visit
          (  V    : in out Visitor_Record'Class;
             Node : Parse_Tree_Node_Record
          )  is abstract;

Each node will override Visit to define what should be done with it when
visited. Which way is better depends on which type is expected to be
extended at most.

In general case there is no solution for this problem, because dispatching
operation is fundamentally different from a class-wide (generic) one. So
any solution that substitutes one for another (i.e. when one of the
arguments becomes class-wide) is inherently insufficient. Fortunaltely in
many cases one can foresee the number of types involved or break a
dispatching operation down into a set of other operations so that it could
be replaced with a class-wide one.

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de