Access idiom

Access idiom

[Gene]

First, thanks for past help from this group.

I'm at an impasse developing a graph data structure.  There are many
node types derived from a "most general" one.  Most of the node types
contain fields that are classwide access to child nodes.  Various
primitive procedures operate on nodes, dispatching on unnamed node
access types.  In many cases, the operations return such an access
child value.  Other "identity" ops just return the dispatching
parameter as classwide access.

Here is the idea:

----- hoo.ads ----
package Hoo is

   type Node_Type is tagged record
      I : Integer := 0;
   end record;
   function Op(P : access Node_Type) return access Node_Type'Class;

   type Threat_Type is new Node_Type with record
      Target : access Node_Type'Class;
   end record;
   overriding
   function Op(P : access Threat_Type) return access Node_Type'Class;

end Hoo;

---- hoo.adb ----
package body Hoo is

   function Op(P : access Node_Type) return access Node_Type'Class is
   begin
      return P; -- identity operation
   end Op;

   overriding
   function Op(P : access Threat_Type) return access Node_Type'Class
is
   begin
      return P.Target; -- just return a child
   end Op;

end Hoo;

---- foo.adb (main procedure) ----
with Hoo; use Hoo;

procedure Foo is
   Threat : access Threat_Type;
begin
   -- Nonsense just to verify type compatibility.
   Threat := new Threat_Type;
   Threat.Target := Op(Threat);
end Foo;
-----

This is all fine.  The trouble is that some of the primitive ops need
to return multiple values, some of which will be classwide access to
node.  The "natural" implementation seems to be a procedure with
several "out" parameters; but, "seem" is the operative word.  To use
out parameters, the classwide access node type must be named.  The
problem here is I can't see a way to dispatch on this named access
type, which will be necessary to recursively operate on child nodes.

One idea is to return a record type that holds the needed multiple
values, but this seems ugly.  It will require defining a bunch of
ephemeral record types that don't have clear meaning as objects.

I tentatively have given up on access dispatching entirely,
dispatching instead on node types (not access) and copying to form
fresh values of a named classwide access type for the return
value(s).  This same named type is used for node child pointers.
While this okay, there is a lot of useless copying.

Feels like I'm playing whack-a-mole with the Ada type system.  What's
the idomatic way to get this job done without the copying?

Thanks,
Gene

Re: Access idiom

[Ludovic Brenta]

Gene writes:
> I tentatively have given up on access dispatching entirely,
> dispatching instead on node types (not access) and copying to form
> fresh values of a named classwide access type for the return
> value(s).  This same named type is used for node child pointers.
> While this okay, there is a lot of useless copying.
>
> Feels like I'm playing whack-a-mole with the Ada type system.  What's
> the idomatic way to get this job done without the copying?

Parameters of tagged types being always passed by reference (see ARM
6.3.2(5)), there is no copying involved in "dispatching on node types"
as opposed to access, so I think your solution is fine.  Then again, I
may have misunderstood your problem.

-- 
Ludovic Brenta.

Re: Access idiom

[Gene]

On Jan 20, 8:01 pm, Ludovic Brenta <ludo...@ludovic-brenta.org> wrote:
> Gene writes:
> > I tentatively have given up on access dispatching entirely,
> > dispatching instead on node types (not access) and copying to form
> > fresh values of a named classwide access type for the return
> > value(s).  This same named type is used for node child pointers.
> > While this okay, there is a lot of useless copying.
>
> > Feels like I'm playing whack-a-mole with the Ada type system.  What's
> > the idomatic way to get this job done without the copying?
>
> Parameters of tagged types being always passed by reference (see ARM
> 6.3.2(5)), there is no copying involved in "dispatching on node types"
> as opposed to access, so I think your solution is fine.  Then again, I
> may have misunderstood your problem.
>

I haven't been clear.  When I dispatch on the tagged record types
rather than access to tagged record, then I have no way of returning a
pointer to the dispatching object or a child pointer.

In concept, what I'd need to do is something like this:

type Node_Ptr_Type is access Node_Type'Class;

procedure Op(P : in Threat_Type; Result : out Node_Ptr_Type) is
begin
   Result := P'Access; -- identity operation
end Op;

... or the other way:

procedure Op(P : access Threat_Type; Result : out Node_Ptr_Type) is
begin
   Result := Node_Ptr_Type(P); -- identity operation
end Op;

Of course neither of these is correct Ada.  Instead I'm doing this:

procedure Op(P : in Threat_Type; Result : out Node_Ptr_Type) is
begin
   Result := Node_Ptr_Type'(new Threat_Type'(P)); -- identity
operation
end Op;

This works, but the copy is unnecessary.

Access idiom

[Grein, Christoph (Fa. ESG)]

You need *all* on the access type:

  type Node_Ptr_Type is access all Node_Type'Class;

  procedure Op (P: access Threat_Type; Result: out Node_Ptr_Type) is 
  begin 
    Result := Node_Ptr_Type (P);  --  OK now
  end Op;


Eurocopter Deutschland GmbH
Sitz der Gesellschaft/Registered Office: Donauwoerth
Registergericht/Registration Court: Amtsgericht Augsburg HRB 16508
Vorsitzender des Aufsichtsrates/Chairman of the Supervisory Board: Dr. Lutz Bertling
Geschaeftsfuehrung/Board of Management:
Dr. Wolfgang Schoder, Vorsitzender/CEO; Friedrich-Wilhelm Hormel; Ralf Barnscheidt

CONFIDENTIALITY NOTICE 

This communication and the information it contains is intended for the addressee(s) named above and for no other persons or organizations. It is confidential and may be legally privileged and protected by law. The unauthorized use, copying or disclosure of this communication or any part of it is prohibited and may be unlawful. 
If you have received this communication in error, kindly notify us by return e-mail and discard and/or delete the communication. Thank you very much. 
It is possible for e-mails to be intercepted or affected by viruses. Whilst we maintain virus checks on our e-mails, we accept no liability for viruses or other material which might be introduced with this message. 

Re: Access idiom

[Dmitry A. Kazakov]

On Sun, 20 Jan 2008 11:57:09 -0800 (PST), Gene wrote:

> To use
> out parameters, the classwide access node type must be named.  The
> problem here is I can't see a way to dispatch on this named access
> type, which will be necessary to recursively operate on child nodes.

As it was already suggested it will dispatch after dereferncing. In Ada
2005 which seems you are using, you will not need P.all with prefix
notation: Node.Next.Next, Next(Node).Next, both Next in both variants
dispatch.

Alternatively you can use tagged handles to nodes wrapping an access type.
The operations on nodes become private. The operations on handles are
public.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Access idiom

[Robert A Duff]

Gene <gene.ressler@gmail.com> writes:

> In concept, what I'd need to do is something like this:
>
> type Node_Ptr_Type is access Node_Type'Class;
>
> procedure Op(P : in Threat_Type; Result : out Node_Ptr_Type) is
> begin
>    Result := P'Access; -- identity operation
> end Op;

I'm not sure exactly what you're trying to do,
but the following might be what you want:

  type Node_Ptr_Type is access constant Node_Type'Class;
                               ^^^^^^^^

  procedure Op(P : in Threat_Type; Result : out Node_Ptr_Type) is
  begin
     Result := P'Unchecked_Access; -- identity operation
                 ^^^^^^^^^^
  end Op;

or:

  type Node_Ptr_Type is access all Node_Type'Class;
                               ^^^

  procedure Op(P : in out Threat_Type; Result : out Node_Ptr_Type) is
                      ^^^
  begin
     Result := P'Unchecked_Access; -- identity operation
                 ^^^^^^^^^^
  end Op;

'Unchecked_Access can lead to dangling pointers -- you need to make sure
you don't pass nested objects to Op.

- Bob

Re: Access idiom

[Jeffrey R. Carter]

Gene wrote:
> 
> I'm at an impasse developing a graph data structure.  There are many
> node types derived from a "most general" one.  Most of the node types
> contain fields that are classwide access to child nodes.  Various
> primitive procedures operate on nodes, dispatching on unnamed node
> access types.  In many cases, the operations return such an access
> child value.  Other "identity" ops just return the dispatching
> parameter as classwide access.

There should be no need for public access types or values in such a data 
structure. Hiding them should make the package easier to use, easier to 
implement, and safer.

-- 
Jeff Carter
"Apart from the sanitation, the medicine, education, wine,
public order, irrigation, roads, the fresh water system,
and public health, what have the Romans ever done for us?"
Monty Python's Life of Brian
80

Re: Access idiom

[Gene]

On Jan 21, 1:15 pm, "Jeffrey R. Carter"
<spam.jrcarter....@acm.nospam.org> wrote:
> Gene wrote:
>
> > I'm at an impasse developing a graph data structure.  There are many
> > node types derived from a "most general" one.  Most of the node types
> > contain fields that are classwide access to child nodes.  Various
> > primitive procedures operate on nodes, dispatching on unnamed node
> > access types.  In many cases, the operations return such an access
> > child value.  Other "identity" ops just return the dispatching
> > parameter as classwide access.
>
> There should be no need for public access types or values in such a data
> structure. Hiding them should make the package easier to use, easier to
> implement, and safer.

First, I think the collective wisdom has put me straight. Thanks.

Another, more succinct explanation...  The graph has many node types,
all with common ancestor.  Edges are pointers--named or anonymous
access Node_Type'Class; don't care which.  Required is a primitive
"transform" procedure that dispatches on node type and must return a
pointer to an _arbitrary node type_ (i.e. again of type access
Node_Type'Class).  Frequently the transform should just return its
parameter without modification.  Using primitive functions (which
would enable return of anonymous access Node_Type'Class) is not good
due to need for multiple return values.

Jeff, in view of all the above, a named "access all Node_Type'Class"
type seems necessary for the return values.

I failed earlier because the out parameter wouldn't convert
automatically from named to unnamed access, and I didn't realize type
conversion would work on L-values.

Further comments very welcome if there is a better way.  Again,
thanks.

This compiles and dispatches as expected:

---- hoo.ads
package Hoo is

   type Node_Type is abstract tagged null record;
   type Node_Ptr_Type is access all Node_Type'Class;
   procedure XForm(P : access Node_Type;
                   Rtn : out Node_Ptr_Type) is abstract;

   type Binary_Type is new Node_Type with record
      Left, Right : access Node_Type'Class;
   end record;

   overriding
   procedure XForm(P : access Binary_Type;
                   Rtn : out Node_Ptr_Type);
end Hoo;

---- hoo.adb
package body Hoo is

   overriding
   procedure XForm
     (P : access Binary_Type;
      Rtn : out Node_Ptr_Type)
   is
   begin
      Rtn := Node_Ptr_Type(P);
   end XForm;

end Hoo;

---- foo.adb
procedure Foo is
   P : access Binary_Type;
begin
   P := new Binary_Type;
   Xform(P.Left, Node_Ptr_Type(P.Left));
end Foo;

Re: Access idiom

[Randy Brukardt]

"Gene" <gene.ressler@gmail.com> wrote in message
news:adad44a1-0519-4333-add6-86936adc7ab1@l1g2000hsa.googlegroups.com...
...
>In concept, what I'd need to do is something like this:

>type Node_Ptr_Type is access Node_Type'Class;

>procedure Op(P : in Threat_Type; Result : out Node_Ptr_Type) is
>begin
>   Result := P'Access; -- identity operation
>end Op;

This is how Claw works, so it obviously is OK.

You do need to use "'Unchecked_Access" instead of "'Access", and you need to
declare the type "access all".]

>... or the other way:
>
>procedure Op(P : access Threat_Type; Result : out Node_Ptr_Type) is
>begin
>   Result := Node_Ptr_Type(P); -- identity operation
>end Op;

This works, but I think it is nasty to the client, because they have to
convert objects into access values at the call interface. Since "P : in
Threat_Type" is passed by reference, but doesn't carry runtime
accessibility, it's actually cheaper than "P : access Threat_Type".

                               Randy.

Re: Access idiom

[Randy Brukardt]

"Gene" <gene.ressler@gmail.com> wrote in message
news:adad44a1-0519-4333-add6-86936adc7ab1@l1g2000hsa.googlegroups.com...
...
>In concept, what I'd need to do is something like this:

>type Node_Ptr_Type is access Node_Type'Class;

>procedure Op(P : in Threat_Type; Result : out Node_Ptr_Type) is
>begin
>   Result := P'Access; -- identity operation
>end Op;

This is how Claw works, so it obviously is OK.

You do need to use "'Unchecked_Access" instead of "'Access", and you need to
declare the type "access all".]

>... or the other way:
>
>procedure Op(P : access Threat_Type; Result : out Node_Ptr_Type) is
>begin
>   Result := Node_Ptr_Type(P); -- identity operation
>end Op;

This works, but I think it is nasty to the client, because they have to
convert objects into access values at the call interface. Since "P : in
Threat_Type" is passed by reference, but doesn't carry runtime
accessibility, it's actually cheaper than "P : access Threat_Type".

                               Randy.

Re: Access idiom

[Randy Brukardt]

"Jeffrey R. Carter" <spam.jrcarter.not@acm.nospam.org> wrote in message
news:6j5lj.309998$Fc.80333@attbi_s21...
> Gene wrote:
> >
> > I'm at an impasse developing a graph data structure.  There are many
> > node types derived from a "most general" one.  Most of the node types
> > contain fields that are classwide access to child nodes.  Various
> > primitive procedures operate on nodes, dispatching on unnamed node
> > access types.  In many cases, the operations return such an access
> > child value.  Other "identity" ops just return the dispatching
> > parameter as classwide access.
>
> There should be no need for public access types or values in such a data
> structure. Hiding them should make the package easier to use, easier to
> implement, and safer.

Humm, I wouldn't go quite that far. If you need to return a reference to an
object (in the graph in this case) where the specific type of the object
isn't known, you have to use access types unless you can afford to copy them
all the time. We tried to do that with Claw, and it didn't work very well
(especially with user-defined extensions). We ended up adding returning of
access values in a few critical cases (like Get_Parent) in order to avoid
the bad effects of copying.

Summary: I wouldn't use "access" for any "in" parameters, but return values
and out parameters may need to be different.

                           Randy.

Re: Access idiom

[Randy Brukardt]

"Jeffrey R. Carter" <spam.jrcarter.not@acm.nospam.org> wrote in message
news:6j5lj.309998$Fc.80333@attbi_s21...
> Gene wrote:
> >
> > I'm at an impasse developing a graph data structure.  There are many
> > node types derived from a "most general" one.  Most of the node types
> > contain fields that are classwide access to child nodes.  Various
> > primitive procedures operate on nodes, dispatching on unnamed node
> > access types.  In many cases, the operations return such an access
> > child value.  Other "identity" ops just return the dispatching
> > parameter as classwide access.
>
> There should be no need for public access types or values in such a data
> structure. Hiding them should make the package easier to use, easier to
> implement, and safer.

Humm, I wouldn't go quite that far. If you need to return a reference to an
object (in the graph in this case) where the specific type of the object
isn't known, you have to use access types unless you can afford to copy them
all the time. We tried to do that with Claw, and it didn't work very well
(especially with user-defined extensions). We ended up adding returning of
access values in a few critical cases (like Get_Parent) in order to avoid
the bad effects of copying.

Summary: I wouldn't use "access" for any "in" parameters, but return values
and out parameters may need to be different.

                           Randy.

Re: Access idiom

[Gene]

On Jan 21, 10:56 pm, Gene <gene.ress...@gmail.com> wrote:
> On Jan 21, 1:15 pm, "Jeffrey R. Carter"
>
> <spam.jrcarter....@acm.nospam.org> wrote:
> > Gene wrote:
>
> > > I'm at an impasse developing a graph data structure.  There are many
> > > node types derived from a "most general" one.  Most of the node types
> > > contain fields that are classwide access to child nodes.  Various
> > > primitive procedures operate on nodes, dispatching on unnamed node
> > > access types.  In many cases, the operations return such an access
> > > child value.  Other "identity" ops just return the dispatching
> > > parameter as classwide access.
>
> > There should be no need for public access types or values in such a data
> > structure. Hiding them should make the package easier to use, easier to
> > implement, and safer.
>
> First, I think the collective wisdom has put me straight. Thanks.
>
> Another, more succinct explanation...  The graph has many node types,
> all with common ancestor.  Edges are pointers--named or anonymous
> access Node_Type'Class; don't care which.  Required is a primitive
> "transform" procedure that dispatches on node type and must return a
> pointer to an _arbitrary node type_ (i.e. again of type access
> Node_Type'Class).  Frequently the transform should just return its
> parameter without modification.  Using primitive functions (which
> would enable return of anonymous access Node_Type'Class) is not good
> due to need for multiple return values.
>
> Jeff, in view of all the above, a named "access all Node_Type'Class"
> type seems necessary for the return values.
>
> I failed earlier because the out parameter wouldn't convert
> automatically from named to unnamed access, and I didn't realize type
> conversion would work on L-values.
>
> Further comments very welcome if there is a better way.  Again,
> thanks.
>
> This compiles and dispatches as expected:
>
> ---- hoo.ads
> package Hoo is
>
>    type Node_Type is abstract tagged null record;
>    type Node_Ptr_Type is access all Node_Type'Class;
>    procedure XForm(P : access Node_Type;
>                    Rtn : out Node_Ptr_Type) is abstract;
>
>    type Binary_Type is new Node_Type with record
>       Left, Right : access Node_Type'Class;
>    end record;
>
>    overriding
>    procedure XForm(P : access Binary_Type;
>                    Rtn : out Node_Ptr_Type);
> end Hoo;
>
> ---- hoo.adb
> package body Hoo is
>
>    overriding
>    procedure XForm
>      (P : access Binary_Type;
>       Rtn : out Node_Ptr_Type)
>    is
>    begin
>       Rtn := Node_Ptr_Type(P);
>    end XForm;
>
> end Hoo;
>
> ---- foo.adb
> procedure Foo is
>    P : access Binary_Type;
> begin
>    P := new Binary_Type;
>    Xform(P.Left, Node_Ptr_Type(P.Left));
> end Foo;

I guess this classifies as a "duh..."  Declaring graph edges as
Node_Ptr_Type instead of access Node_Type'Class eliminates need for
type conversion at call site...  So now the 2nd last line above is
just

Xform(P.Left, P.Left);

Entlich ist es ganz sauber!  Fascinating that changing all the
declaration _and_ implementation code from

Xform(P : in Node_type; Rtn : out Node_Ptr_type);

to

Xform(P : access Node_Type; Rtn : out Node_Ptr_type);

was possible with only find-and-replace edits (including deletions of
many .all's) ... good evidence of the orthogonality and consistency of
Ada syntax.

Thanks for remarks that access params incur a performance hit.  In
this app, clean, simple syntax is far more important than performance.

All the best,
Gene

Re: Access idiom

[Dmitry A. Kazakov]

On Mon, 21 Jan 2008 19:56:54 -0800 (PST), Gene wrote:

> Further comments very welcome if there is a better way.  Again,
> thanks.
> 
> This compiles and dispatches as expected:
> 
> ---- hoo.ads
> package Hoo is
> 
>    type Node_Type is abstract tagged null record;

    type Node_Type (<>) is abstract limited tagged private;

1. I would add limited to indicate that are nodes never copied.

2. Maybe Ada.Finalization.Limited_Controlled should be used as the base.

3. "null record" looks much like an interface. You are in Ada 2005, so
Node_Type could become an interface.

>    type Node_Ptr_Type is access all Node_Type'Class;

   type Node_Ptr_Type is access Node_Type'Class;

I don't like general access types. What if somebody allocated a node on the
stack linked it with another in the pool and then left the scope? Also,
trees can often profit from arena and mark-and-sweep allocators, so you
could do:

   for Node_Ptr_Type'Storage_Pool use My_Nice_Arena_Pool;

>    procedure XForm(P : access Node_Type;
>                    Rtn : out Node_Ptr_Type) is abstract;
> 
>    type Binary_Type is new Node_Type with record
>       Left, Right : access Node_Type'Class;

   Left, Right : Node_Ptr_Type;

We have an access type for that, and we don't want nodes having children
allocated on the stack. (Not-null constraint can be added in Ada2005 if
required.)

>    end record;
> 
>    overriding
>    procedure XForm(P : access Binary_Type;
>                    Rtn : out Node_Ptr_Type);
> end Hoo;
> 
> ---- hoo.adb
> package body Hoo is
> 
>    overriding
>    procedure XForm
>      (P : access Binary_Type;
>       Rtn : out Node_Ptr_Type)
>    is
>    begin
>       Rtn := Node_Ptr_Type(P);

OK, that will be an unchecked conversion with pool-specific access types.
This is a weaknesses of my approach, but I usually buy that. When
conversions become too frequent I use the Rosen trick.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Access idiom

[Jeffrey R. Carter]

Gene wrote:
> 
> Another, more succinct explanation...  The graph has many node types,
> all with common ancestor.  Edges are pointers--named or anonymous
> access Node_Type'Class; don't care which.  Required is a primitive
> "transform" procedure that dispatches on node type and must return a
> pointer to an _arbitrary node type_ (i.e. again of type access
> Node_Type'Class).  Frequently the transform should just return its
> parameter without modification.  Using primitive functions (which
> would enable return of anonymous access Node_Type'Class) is not good
> due to need for multiple return values.

In general, I would disagree. The visible part of the package specification 
presents the abstraction to the package client. The rest of the package is the 
implementation of that abstraction. The client should not need to know how you 
choose to implement the abstraction "Edge", and shouldn't have to take special 
action in his application code because you chose a specific implementation.

-- 
Jeff Carter
"Your mother was a hamster and your father smelt of elderberries."
Monty Python & the Holy Grail
06