issue with implementing a visitor design pattern

issue with implementing a visitor design pattern

[cl1]

i'm trying to implement a visitor pattern for a parse tree(its a simple
calculator at this point). i have an abstract type:

type Visitor_Record is abstract tagged null record;

with primative operations Visit() for each node type like so:

Visit(V : in out Visitor_Record; Node : in Add_Op'Class) is abstract;
...
Visit(V : in out Visitor_Record; Node : in Assignment_Node'Class) is
abstract;

what i'm trying to do is implement a Preorder_Visitor_Record type that uses
the Visit() operation to
traverse the tree and calls an operation Visit_Operation() that is also a
primative operation on Preorder_Visitor_Record
like so:
with parse_tree_pkg; use parse_tree_pkg; -- has the parse tree nodes a
primative operation Accept_Visitor() for each node
                                                                 -- and the
abstract Visitor_Record with primative operations Visit() for each node
package Preorder_Visitor_Pkg is
    type Preorder_Visitor_Record is new Visitor_Record with null record;

    -- this is overidiing the abstract version in parse_tree_pkg;
    procedure Visit ( V : in out Preorder_Visitor_Record; Node : in
Add_Op'Class);
    .....

    procedure Visit_Operation (V : in preorder_Visitor_Record; node : in
add_op'class);
end preorder_visitor_Pkg;

package body Preorder_Visitor_Pkg is

procedure Visit_Operation ( V : in out Preorder_Visitor_Record; Node : in
Add_Op'Class)
is begin
    raise Not_Implemented; -- better handling in actual code with an error
message using ada.exceptions
end Visit_Operation
procedure Visit( V : in out Preorder_Visitor_Record; Node : in Add_Op'Class)
is begin
    Visit_Operation(V, Node);
end Visit;


the actual code errors saying ambiguos call of Visit_Operation() from within
the Visit() procedure. with possible interpretations at the definition of
Preorder_Visitor_Record and at the specification for Visit_Operation.

the code works when you take Visit_Operation out of the mix. the package
compiles and works with a test driver. but when i try to add in this
Visit_Operation it doesn't work. I don't know if there are some scoping
issues or if there is something else i need to know about primative
operations to make this work. any guidance would be appreciated.

Thanks,
Charles Lambert

Re: issue with implementing a visitor design pattern

[Robert I. Eachus]

cl1 wrote:
> i'm trying to implement a visitor pattern for a parse tree(its a simple
> calculator at this point). i have an abstract type:

I'll try to help...
> 
> type Visitor_Record is abstract tagged null record;
> 
> with primative operations Visit() for each node type like so:
> 
> Visit(V : in out Visitor_Record; Node : in Add_Op'Class) is abstract;
> ...
> Visit(V : in out Visitor_Record; Node : in Assignment_Node'Class) is
> abstract;

Do not make Visit classwide.  In other words get rid of the 'Class in 
the definition.  For dynamic dispatching where you may need 'Class is as 
the type of the formal parameter in the call.

> what i'm trying to do is implement a Preorder_Visitor_Record type that uses
> the Visit() operation to
> traverse the tree and calls an operation Visit_Operation() that is also a
> primative operation on Preorder_Visitor_Record
> like so:
> with parse_tree_pkg; use parse_tree_pkg; -- has the parse tree nodes a
> primative operation Accept_Visitor() for each node
>                                                                  -- and the
> abstract Visitor_Record with primative operations Visit() for each node
> package Preorder_Visitor_Pkg is
>     type Preorder_Visitor_Record is new Visitor_Record with null record;
> 
>     -- this is overidiing the abstract version in parse_tree_pkg;

But it doesn't in Ada and that is your problem.  It overloads not 
overrides in some scopes.  Ada 200Y will probably have an overrides 
keyword which will get you an error message at compile time here.

>     procedure Visit ( V : in out Preorder_Visitor_Record; Node : in
> Add_Op'Class);
>     .....
> 
>     procedure Visit_Operation (V : in preorder_Visitor_Record; node : in
> add_op'class);
> end preorder_visitor_Pkg;

Same problem here...
> 
> package body Preorder_Visitor_Pkg is
> 
> procedure Visit_Operation ( V : in out Preorder_Visitor_Record; Node : in
> Add_Op'Class)
> is begin
>     raise Not_Implemented; -- better handling in actual code with an error
> message using ada.exceptions
> end Visit_Operation
> procedure Visit( V : in out Preorder_Visitor_Record; Node : in Add_Op'Class)
> is begin
>     Visit_Operation(V, Node);
> end Visit;
> 
> 
> the actual code errors saying ambiguos call of Visit_Operation() from within
> the Visit() procedure. with possible interpretations at the definition of
> Preorder_Visitor_Record and at the specification for Visit_Operation.
> 
> the code works when you take Visit_Operation out of the mix. the package
> compiles and works with a test driver. but when i try to add in this
> Visit_Operation it doesn't work. I don't know if there are some scoping
> issues or if there is something else i need to know about primative
> operations to make this work. any guidance would be appreciated.
> 
> Thanks,
> Charles Lambert

The much deeper problem you have is that the Visitor pattern is a waste 
of effort in Ada.  Not wrong, or unimplementable, but the pattern as 
such is much heavier weight than it needs to be.  The normal approach to 
this problem in Ada is, in the package that declares the abstract data 
type, (the parse tree in this case) to have a generic procedure to do 
the work:

package Parse_Tree_Pkg is -- I'd call it Parse_Trees, but that is a 

                           -- style issue...

     type Node is ...;
     type Parse_Tree is ...;

     generic
       with procedure Visitor (N: in out Node);
     procedure In_Order (PT: in out Parse_Tree); -- visit all the nodes
                                                 -- of a parse tree in
                                                 -- order and Visitor
                                                 -- Visitor;

Now you can instantiate In_Order with whatever visitor you want.  Much 
easier to work with, and easier to change the In_Order instantiation to 
Pre_Order or Post_Order if the design changes.  Note that the generic 
formal procedure doesn't mention the ADT in its profile.  So you can 
pass the same concrete visitor implementation just as easily to a queue 
or stack, as long as the node type is the same.

-- 
                                           Robert I. Eachus

"The war on terror is a different kind of war, waged capture by capture, 
cell by cell, and victory by victory. Our security is assured by our 
perseverance and by our sure belief in the success of liberty." -- 
George W. Bush

Re: issue with implementing a visitor design pattern

[Robert A Duff]

"Robert I. Eachus" <rieachus@comcast.net> writes:

> The much deeper problem you have is that the Visitor pattern is a waste
> of effort in Ada.  Not wrong, or unimplementable, but the pattern as
> such is much heavier weight than it needs to be.

I agree.  In fact, I'd say "visitor" is my least favorite design pattern
of the ones in the Gamma et al book.  "Visitor" has all the
disadvantages of a case statement (over dispatching calls),
with none of the advantages!

- Bob

Re: issue with implementing a visitor design pattern

[Dale Stanbrough]

Robert A Duff wrote:

> "Robert I. Eachus" <rieachus@comcast.net> writes:
> 
> > The much deeper problem you have is that the Visitor pattern is a waste
> > of effort in Ada.  Not wrong, or unimplementable, but the pattern as
> > such is much heavier weight than it needs to be.
> 
> I agree.  In fact, I'd say "visitor" is my least favorite design pattern
> of the ones in the Gamma et al book.  "Visitor" has all the
> disadvantages of a case statement (over dispatching calls),
> with none of the advantages!

If you have two orthoganal classifications (object and function) and
you need to (effectively) double dispatch, the visitor pattern is 
quite useful. Not quite sure how else you would achieve it in Ada.

Dale

-- 
dstanbro@spam.o.matic.bigpond.net.au

Re: issue with implementing a visitor design pattern

[Robert A Duff]

Dale Stanbrough <MrNoSpam@bigpoop.net.au> writes:

> Robert A Duff wrote:
> > I agree.  In fact, I'd say "visitor" is my least favorite design pattern
> > of the ones in the Gamma et al book.  "Visitor" has all the
> > disadvantages of a case statement (over dispatching calls),
> > with none of the advantages!
> 
> If you have two orthoganal classifications (object and function) and
> you need to (effectively) double dispatch, the visitor pattern is 
> quite useful. Not quite sure how else you would achieve it in Ada.

You can have a variant record, with a discriminant of an enumeration
type, and use case statements on the discriminant.  You can even use
subtypes of the enumeration in the case statements.  The way things were
done in the olden days.  ;-)

You have to decide which of "adding new types" or "adding new operations"
is the more important issue.  If the former, the normal OOP style is
appropriate.  If the latter, case statements are appropriate.

My objection to the "visitor" pattern is that it simulates case
statements, but with a whole lot of verbose mechanistic code.
And it retains all the disadvantages of the case-statement style.

Now, OO advocates will tell us that case statements are evil -- one
ought to define dispatching operations, so adding a new type (or
"class") will not require editing all those case statements.
Well, that's quite true in the normal case where adding new types is the
main issue.  But when you use the "visitor" pattern, you've got
essentially the same issue of editing all the operations to handle the
new case.

I suspect much of OO advocates' hatred of case statements comes from
languages where case/switch statements automatically default to
something-or-other.  But Ada largely solves that problem via its
full-coverage rule (assuming you don't evilly use 'when others').  You
still have to edit all the case statements, which is particularly bad if
we're talking about a widely-used library, but at least in Ada, the
compiler tells you which case statements have missing cases.

If you want to mix the two styles, you're kind of stuck (in Ada, and in
pretty much every other OOP language).  You have to use the visitor
pattern.  If Ada allowed case statements on the 'Tag field of class-wide
objects, then things would be much easier.  OO advocates don't like
explicit tests on the 'Tag, and that's usually right, but when it's
necessary, I claim a simple case statement would be preferable to the
"visitor" pattern, which does essentially the same thing, but with a
whole lot of extra baggage.

Adding "case on 'Tag" to Ada would not be trivial.  One would have to
reconcile the open-ended type extension capability of tagged types with
the full-coverage rules of case statements.

- Bob

Re: issue with implementing a visitor design pattern

[Dmitry A. Kazakov]

On 24 Jan 2004 16:44:02 -0500, Robert A Duff
<bobduff@shell01.TheWorld.com> wrote:

>Dale Stanbrough <MrNoSpam@bigpoop.net.au> writes:
>
>> Robert A Duff wrote:

>Adding "case on 'Tag" to Ada would not be trivial.  One would have to
>reconcile the open-ended type extension capability of tagged types with
>the full-coverage rules of case statements.

Same as with integer types, an obligatory:

   when others =>
      ...

Then, of course, there could be subtypes of classes and thus finite
sets of tags:

type T is tagged ...;
type T1 is new T with ...;
type T2 is new T1 with ...;
...
type TN is new ...;

subtype Finite is T'Class (T1..TN);

Also useful would be dispatching on bare tags or an equivalent of
that.

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

Re: issue with implementing a visitor design pattern

[Robert A Duff]

Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> writes:

> On 24 Jan 2004 16:44:02 -0500, Robert A Duff
> <bobduff@shell01.TheWorld.com> wrote:
> 
> >Dale Stanbrough <MrNoSpam@bigpoop.net.au> writes:
> >
> >> Robert A Duff wrote:
> 
> >Adding "case on 'Tag" to Ada would not be trivial.  One would have to
> >reconcile the open-ended type extension capability of tagged types with
> >the full-coverage rules of case statements.
> 
> Same as with integer types, an obligatory:
> 
>    when others =>
>       ...

"when others" *defeats* the full-coverage rules.  It should be used only
if you know it covers *all* the other cases, including the ones that
haven't been invented yet!

> Then, of course, there could be subtypes of classes and thus finite
> sets of tags:

Maybe...

- Bob

Re: issue with implementing a visitor design pattern

[Dmitry A. Kazakov]

On 26 Jan 2004 15:18:41 -0500, Robert A Duff
<bobduff@shell01.TheWorld.com> wrote:

>Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> writes:
>
>> On 24 Jan 2004 16:44:02 -0500, Robert A Duff
>> <bobduff@shell01.TheWorld.com> wrote:
>> 
>> >Dale Stanbrough <MrNoSpam@bigpoop.net.au> writes:
>> >
>> >> Robert A Duff wrote:
>> 
>> >Adding "case on 'Tag" to Ada would not be trivial.  One would have to
>> >reconcile the open-ended type extension capability of tagged types with
>> >the full-coverage rules of case statements.
>> 
>> Same as with integer types, an obligatory:
>> 
>>    when others =>
>>       ...
>
>"when others" *defeats* the full-coverage rules.  It should be used only
>if you know it covers *all* the other cases, including the ones that
>haven't been invented yet!

It is a strange thing, "when others". Especially when others (:-)) is
empty, like in:

subtype Empty is String (0..-1);
X : Empty := (others => ' ');

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

Re: issue with implementing a visitor design pattern

[Georg Bauhaus]

Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
: 
: It is a strange thing, "when others". Especially when others (:-)) is
: empty,

Isn't that the vacuousity that you are asked to hammer into your
brain the moment you enter the study of mathematical subjects? :-)

Re: issue with implementing a visitor design pattern

[cl1]

after having read all the info given here in the newsgroup on this. I
definately open to implementing it with the generics, but
i would like to have it working with the set up i have now. I have written
lots of notes on what i have done so far and getting
it to work in the format i have now would better help me explain why i
changed when i post my writtings to the internet.

here is a link to some example source:
http://www.geocities.com/cwlambert76/preorder_visitor.adb.txt
it contains example code of both packages i have written so far.

what i have so far is a parse tree, along with an Accept_Visitor() operation
for each node. and an abstract
Visitor in my parse_tree_pkg with a Visit() operation for each node. i want
to implement the different types of tree traversal
only once(preorder, inorder, etc.) that is why i have created the
preorder_visitor_pkg. and any visitor that needs to "visit" the
parse tree can pick its traversal method by subclassing the appropriate
visitor package and overiding the Visit_Operation for
each node, and in turn not have to implement the actual traversal itself.
Now i know this may not be the best way to implement
this, at this point the only way to catch that a Visit_Operation() isn't
implemented is at runtime (not good). However this has
been a great learning process for me, and i would like to be able to share
my learning experiances with everyone. So once i
have this working then I will be more than happy to refactor my code to a
higher quality version, and i would greatly
appreciate all of your help in doing so.

Thanks,
Charles Lambert