Comparing Access Types

Comparing Access Types

[Jere]

I have a package which uses a type to wrap an access type.  I thought it
might be nice to provide the basic comparison functions, "=", "<", ">", etc.
but access types can only be compared using "=" and "/=".  I figured that
way, my types could be used in some sort of sorted container, like a map.

I want to keep the incomplete type for other reasons, so that seems to limit
my options.

1.  Address_To_Access_Conversions is out (cannot use an incomplete type)
2.  I cannot simply do var.all'Address (Again, incomplete type)

Is there some way to do this within the Ada standard or am I hamstrung
due to the incomplete type specification?

Also, why weren't <, >, <=, >= provided for access types.  Even if the
representation of an Access type is implementation defined, surely
those operators could have been defined.

A toned down example:

generic
   type Item_Type(<>);
   type Item_Access is access Item_Type;
package My_Package is

   type Some_Type is record
      Reference : Item_Access := null;
   end record;

   function "<" (Left,Right : Some_Type) return Boolean;

end My_Package;

package body My_Package is

function "<" (Left,Right : Some_Type) return Boolean is
begin
   return Left.Reference < Right.Reference;  --fails to compile
end "<";

end My_Package

Re: Comparing Access Types

[Simon Wright]

Jere <jhb.chat@gmail.com> writes:

> I have a package which uses a type to wrap an access type.  I thought
> it might be nice to provide the basic comparison functions, "=", "<",
> ">", etc.  but access types can only be compared using "=" and "/=".
> I figured that way, my types could be used in some sort of sorted
> container, like a map.

I've used a hashed container.

Re: Comparing Access Types

[Dmitry A. Kazakov]

On 09/11/2017 06:37, Jere wrote:
> I have a package which uses a type to wrap an access type.  I thought it
> might be nice to provide the basic comparison functions, "=", "<", ">", etc.
> but access types can only be compared using "=" and "/=".  I figured that
> way, my types could be used in some sort of sorted container, like a map.
> 
> I want to keep the incomplete type for other reasons, so that seems to limit
> my options.
> 
> 1.  Address_To_Access_Conversions is out (cannot use an incomplete type)
> 2.  I cannot simply do var.all'Address (Again, incomplete type)

Of course you can.

> Is there some way to do this within the Ada standard or am I hamstrung
> due to the incomplete type specification?
> 
> Also, why weren't <, >, <=, >= provided for access types.  Even if the
> representation of an Access type is implementation defined, surely
> those operators could have been defined.

No, in general case it cannot, in the spirit of the semantics that A < B 
if the physical machine address of A < B. Actually even equality cannot 
be for segmented memory but it felt good enough.

> A toned down example:
> 
> generic
>     type Item_Type(<>);
>     type Item_Access is access Item_Type;
> package My_Package is
> 
>     type Some_Type is record
>        Reference : Item_Access := null;
>     end record;
> 
>     function "<" (Left,Right : Some_Type) return Boolean;
> 
> end My_Package;
> 
> package body My_Package is
> 
> function "<" (Left,Right : Some_Type) return Boolean is
> begin
>     return Left.Reference < Right.Reference;  --fails to compile
> end "<";

You have two options:

1. Compare addresses, e.g.

with System; use System;

function "<" (Left,Right : Some_Type) return Boolean is
begin
    return (  Right.Reference /= null
           and then
              (  Left.Reference = null
              or else
                 Left.Reference.all'Address < Right.Reference.all'Address
           )  );
end "<";

2. A better way is to use the native object's order:

generic
    type Item_Type(<>);
    type Item_Access is access Item_Type;
    with function "=" (Left, Right : Item_Type) return Boolean is <>;
    with function "<" (Left, Right : Item_Type) return Boolean is <>;
package My_Package is

function "<" (Left,Right : Some_Type) return Boolean is
begin
    return (  Right.Reference /= null
           and then
              (  Left.Reference = null
              or else
                 Left.Reference.all < Right.Reference.all
           )  );
end "<";

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

Re: Comparing Access Types

[Robert A Duff]

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

> No, in general case it cannot, in the spirit of the semantics that A < B
> if the physical machine address of A < B.

I agree with you that "<" makes little sense for access types.
Even in C, "<" on pointers is undefined unless they point
into the same array.

>...Actually even equality cannot
> be for segmented memory but it felt good enough.

?

"=" returns True if two access values designate the same object,
which is a well defined concept, and has nothing to do with
segmented memory.  And it's easy to implement, whether memory
is segmented or not.

- Bob

Re: Comparing Access Types

[Dmitry A. Kazakov]

On 09/11/2017 23:38, Robert A Duff wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> ...Actually even equality cannot
>> be for segmented memory but it felt good enough.
> 
> ?
> 
> "=" returns True if two access values designate the same object,
> which is a well defined concept, and has nothing to do with
> segmented memory.  And it's easy to implement, whether memory
> is segmented or not.

You could have two segments mapped to the same physical memory. Then you 
may have two unequal segmented addresses pointing to the same physical 
memory unit and so "=" will lie.

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

Re: Comparing Access Types

[Jere]

On Friday, November 10, 2017 at 3:35:10 AM UTC-5, Dmitry A. Kazakov wrote:
> On 09/11/2017 23:38, Robert A Duff wrote:
> > "Dmitry A. Kazakov" writes:
> > 
> >> ...Actually even equality cannot
> >> be for segmented memory but it felt good enough.
> > 
> > ?
> > 
> > "=" returns True if two access values designate the same object,
> > which is a well defined concept, and has nothing to do with
> > segmented memory.  And it's easy to implement, whether memory
> > is segmented or not.
> 
> You could have two segments mapped to the same physical memory. Then you 
> may have two unequal segmented addresses pointing to the same physical 
> memory unit and so "=" will lie.
> 
> -- 
> Regards,
> Dmitry A. Kazakov
> http://www.dmitry-kazakov.de

I know that a lot of the embedded C compilers that we use overcome
this issue by encoding unique segment information into their pointers.
So a pointer isn't just a physical address, but something more that
expresses a unique location based on physical memory location + whatever
other information is available.  I don't know enough about Ada compilers,
but my expectation is that they could also solve that problem (maybe
the same way or maybe in a better way).

Re: Comparing Access Types

[Robert A Duff]

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

> You could have two segments mapped to the same physical memory.

No, the implementation would not allow that to happen.

The fact that the hardware allows it is irrelevant.
In fact, nonsegmented machines can do the same thing
-- you can map two virtual pages to the same physical
address.  If you want "=" on pointers to work, then
simply don't do that.

>... Then you
> may have two unequal segmented addresses pointing to the same physical
> memory unit and so "=" will lie.

If "=" lies, then the Ada implementation is simply wrong.

- Bob

Re: Comparing Access Types

[Robert A Duff]

I wrote:

> If "=" lies, then the Ada implementation is simply wrong.

There were more than one Ada compiler for the 8086,
and I'm pretty sure "=" on access values worked
properly.  It's really not hard to get it right -- in
fact I think the compiler would have to go out of
it's way to get it wrong.

- Bob

Re: Comparing Access Types

[Randy Brukardt]

"Robert A Duff" <bobduff@TheWorld.com> wrote in message 
news:wccinei14g6.fsf@TheWorld.com...
>I wrote:
>
>> If "=" lies, then the Ada implementation is simply wrong.
>
> There were more than one Ada compiler for the 8086,
> and I'm pretty sure "=" on access values worked
> properly.  It's really not hard to get it right -- in
> fact I think the compiler would have to go out of
> it's way to get it wrong.

I doubt that. It wouldn't have worked "right" in Janus/Ada, for instance, we 
just did a binary comparison. So

   C000:DEAD /= CDEA:000D even though they pointed at the same physical 
memory.

But you could only run into that if you converted a System.Address into an 
access value; it would never happen within a correctly running Ada program 
so we didn't want to pay the extra cost of doing it perfectly right. (Same 
reason that I'd never waste time [mine or a programs] making zero-size 
objects work *right* in this sense.)

                                         Randy.

Re: Comparing Access Types

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "Robert A Duff" <bobduff@TheWorld.com> wrote in message 
> news:wccinei14g6.fsf@TheWorld.com...
>>I wrote:
>>
>>> If "=" lies, then the Ada implementation is simply wrong.
>>
>> There were more than one Ada compiler for the 8086,
>> and I'm pretty sure "=" on access values worked
>> properly.  It's really not hard to get it right -- in
>> fact I think the compiler would have to go out of
>> it's way to get it wrong.
>
> I doubt that. It wouldn't have worked "right" in Janus/Ada, ...

I don't believe you.  ;-)

>...for instance, we 
> just did a binary comparison. 

Of course.  That's the only sensible way to do it.

>...So
>
>    C000:DEAD /= CDEA:000D even though they pointed at the same physical 
> memory.

There's no requirement that C000:DEAD = CDEA:000D, so long as "new"
and '[Unchecked_]Access are not producing such weird values.
Just make sure that all access values pointing to the
same object are bit-wise identical.

I stand by me statement: "... the compiler would have to go out of
it's way to get it wrong."

> But you could only run into that if you converted a System.Address into an 
> access value; it would never happen within a correctly running Ada program 

Exactly.  There's no reason for the Ada implementer to worry about
doing weird things with 'Address and Unchecked_Conversion and
the like.  The programmer is required to obey the implementation's
run-time model when using such features.

As you pointed out, access values need not be represented as addresses,
so how could you expect converting addresses to access values
to make any sense at all (unless of course, the implementation
makes promises that go beyond the Ada RM)?

> so we didn't want to pay the extra cost of doing it perfectly right.

I think you did it perfectly right.

- Bob

Re: Comparing Access Types

[Randy Brukardt]

"Robert A Duff" <bobduff@TheWorld.com> wrote in message 
news:wcclgj3z1of.fsf@TheWorld.com...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
...
> As you pointed out, access values need not be represented as addresses,
> so how could you expect converting addresses to access values
> to make any sense at all (unless of course, the implementation
> makes promises that go beyond the Ada RM)?

We never wanted to, but it seems that about 90% of Ada 83 programmers 
expected that to work (and a large % still do). In Ada 95, of course, we 
have Access_to_Address_Conversions (or is that 
Address_to_Access_Conversions - never remember which... :-) Still, getting 
people to use that is like pulling their teeth.

                       Randy.

Re: Comparing Access Types

[Shark8]

On Monday, November 20, 2017 at 3:25:48 PM UTC-7, Randy Brukardt wrote:
> 
> In Ada 95, of course, we 
> have Access_to_Address_Conversions (or is that 
> Address_to_Access_Conversions - never remember which... :-) Still, getting 
> people to use that is like pulling their teeth.

Huh.
Why do you think that is? I use it when I need it, although very infrequently, it's pretty much purpose-built to do that (it's in the name, after all).

Re: Comparing Access Types

[Dmitry A. Kazakov]

On 21/11/2017 01:30, Shark8 wrote:
> On Monday, November 20, 2017 at 3:25:48 PM UTC-7, Randy Brukardt wrote:
>>
>> In Ada 95, of course, we
>> have Access_to_Address_Conversions (or is that
>> Address_to_Access_Conversions - never remember which... :-) Still, getting
>> people to use that is like pulling their teeth.
> 
> Why do you think that is? I use it when I need it, although very 
> infrequently,

It is quite unavoidable when using C bindings. Or else, for X'Address 
use, which is less welcome I guess.

> it's pretty much purpose-built to do that (it's in the 
> name, after all).

It has a nasty issue that you cannot pass your own access type. It is 
clear that not any access type could be acceptable. The implementation 
should be free to reject some upon instantiation.

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

Re: Comparing Access Types

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:ov0pp1$1rlu$1@gioia.aioe.org...
...
>> it's pretty much purpose-built to do that (it's in the name, after all).
>
> It has a nasty issue that you cannot pass your own access type. It is 
> clear that not any access type could be acceptable. The implementation 
> should be free to reject some upon instantiation.

Bob apologies for that nearly every time the subject comes up. (Not sure if 
he will do it here...) It is generally acknowledged to be a mistake; any 
general access type with convention Ada ought to work, and that is easily 
modeled with a generic formal access type. Having the type declared in the 
instance is a pain. It's not quite the pain than many think it is, since one 
can use a type conversion from the type declared in the instance to any 
other general access type with the right convention and designated type. But 
all of those extra conversions are just noise, and add nothing to program 
readability or understandability.

                                              Randy.

Re: Comparing Access Types

[Jere]

On Thursday, November 9, 2017 at 5:38:41 PM UTC-5, Robert A Duff wrote:
> "Dmitry A. Kazakov" writes:
> 
> > No, in general case it cannot, in the spirit of the semantics that A < B
> > if the physical machine address of A < B.
> 
> I agree with you that "<" makes little sense for access types.
> Even in C, "<" on pointers is undefined unless they point
> into the same array.

I'm not hugely in disagreement here, but I am curious as to why it doesn't
make sense.  My impression of access types is that they hold some sort of
information used to locate/manage an object and that they must be unique
for unique objects (that is two access types pointing to two separate
objects cannot have identical implementation values under the hood). If they
must be unique, there is generally a way to order them.  I'm not suggesting
treating them like integers or even exposing how the ordering is done.

Again, I am not trying to outright disagree, just understand.  In either
case, I think I have given up on ordering them and will let the client
do as Dmitry suggests (comparing the objects they reference for ordering
instead).

For debugging purposes, I do wish there was a way for me to get a printable
unique value for access types.  When I work with incomplete types, 'Address
no longer works (with GNAT at least) and there is no 'Image for access types.
Any thoughts on that? I'm trying to trace the inner workings of a type
that holds access types internally but since the access types are for
incomplete types, I'm having trouble doing that within the generic package.

Re: Comparing Access Types

[Robert A Duff]

Jere <jhb.chat@gmail.com> writes:

> I'm not hugely in disagreement here, but I am curious as to why it doesn't
> make sense.

What would it mean?  If X /= Y, then X < Y returns either True
or False arbitrarily?  That could work, but it doesn't seem all
that useful.

If a garbage collector is moving things around in memory,
then it would be hard to implement efficiently.

> For debugging purposes, I do wish there was a way for me to get a printable
> unique value for access types.

Unchecked convert to type Integer_Address, then use 'Image.

- Bob

Re: Comparing Access Types

[Jere]

On Friday, November 10, 2017 at 11:00:17 AM UTC-5, Robert A Duff wrote:
> Jere writes:
> 
> > I'm not hugely in disagreement here, but I am curious as to why it doesn't
> > make sense.
> 
> What would it mean?  If X /= Y, then X < Y returns either True
> or False arbitrarily?  That could work, but it doesn't seem all
> that useful.
> 
> If a garbage collector is moving things around in memory,
> then it would be hard to implement efficiently.

Ok, that makes sense.  The use case I had was more for keys in a map.  I
didn't really care about the actual order, but wanted a way to store a
collection of objects using the access types as the key.  That
would allow for quick searching in large groups.  With the incomplete
type formal parameter, I was having trouble coming up with options.

However, I don't have to implement it that way.  Dmitry comments 
gave me some ideas.  I can either push that off to the client in 
a different way or add more formal parameters to my generic to 
support it if I want.

> 
> > For debugging purposes, I do wish there was a way for me to get a printable
> > unique value for access types.
> 
> Unchecked convert to type Integer_Address, then use 'Image.
> 
> - Bob

Thanks!  This worked. I can use that in my debug package.

Re: Comparing Access Types

[Jere]

On Thursday, November 9, 2017 at 3:33:51 AM UTC-5, Dmitry A. Kazakov wrote:
> On 09/11/2017 06:37, Jere wrote:
> > 
> > 1.  Address_To_Access_Conversions is out (cannot use an incomplete type)
> > 2.  I cannot simply do var.all'Address (Again, incomplete type)
> 
> Of course you can.

When I use GNAT GPL 2016 I get the following error:
10:33 prefix of "Address" attribute cannot be an incomplete type

It works fine for other types of generic formals, but for incomplete 
types, it fails with an error like this.

> 
> > Is there some way to do this within the Ada standard or am I hamstrung
> > due to the incomplete type specification?
> > 
> > Also, why weren't <, >, <=, >= provided for access types.  Even if the
> > representation of an Access type is implementation defined, surely
> > those operators could have been defined.
> 
> No, in general case it cannot, in the spirit of the semantics that A < B 
> if the physical machine address of A < B. Actually even equality cannot 
> be for segmented memory but it felt good enough.
> 

I may not understand, but I don't see this as any issue.  Even when physical
memory is split into pages, banks, segments, etc., it can be organized into
unique locations.  I'm not suggesting that access values need to map directly
to memory addresses but it seems odd that an access type, which holds some
unique information about an object, cannot be ordered in some fashion.

> > A toned down example:
> > 
> > generic
> >     type Item_Type(<>);
> >     type Item_Access is access Item_Type;
> > package My_Package is
> >  <SNIPPED>
> 
> You have two options:
> 
> 1. Compare addresses, e.g.
> 
> with System; use System;
> 
> function "<" (Left,Right : Some_Type) return Boolean is
> begin
>     return (  Right.Reference /= null
>            and then
>               (  Left.Reference = null
>               or else
>                  Left.Reference.all'Address < Right.Reference.all'Address
>            )  );
> end "<";
> 
> 2. A better way is to use the native object's order:
> 
> generic
>     type Item_Type(<>);
>     type Item_Access is access Item_Type;
>     with function "=" (Left, Right : Item_Type) return Boolean is <>;
>     with function "<" (Left, Right : Item_Type) return Boolean is <>;
> package My_Package is
> 
> function "<" (Left,Right : Some_Type) return Boolean is
> begin
>     return (  Right.Reference /= null
>            and then
>               (  Left.Reference = null
>               or else
>                  Left.Reference.all < Right.Reference.all
>            )  );
> end "<";
> 
> -- 
> Regards,
> Dmitry A. Kazakov
> http://www.dmitry-kazakov.de

Ok, that makes sense.  If I have to do it that way, then I'll have
to push it off to the client in some fashion.  Though again, GNAT
won't currently let me do the first option yet.

Thanks

Re: Comparing Access Types

[Randy Brukardt]

"Jere" <jhb.chat@gmail.com> wrote in message 
news:0e68d62f-6e81-4f48-998f-cccdb4c650a1@googlegroups.com...
...
> I may not understand, but I don't see this as any issue.  Even when 
> physical
> memory is split into pages, banks, segments, etc., it can be organized 
> into
> unique locations.  I'm not suggesting that access values need to map 
> directly
> to memory addresses but it seems odd that an access type, which holds some
> unique information about an object, cannot be ordered in some fashion.

Flattening segmented memory would be expensive to implement (in general 
requiring expensive protected system calls) and it doesn't seem useful (as 
Bob noted), especially if something is moving objects around.

                            Randy.

Re: Comparing Access Types

[Randy Brukardt]

"Jere" <jhb.chat@gmail.com> wrote in message 
news:b3976d73-296f-4958-bfb2-26bf49901a48@googlegroups.com...
...
> Also, why weren't <, >, <=, >= provided for access types.  Even if the
> representation of an Access type is implementation defined, surely
> those operators could have been defined.

They could have been, but they don't mean anything. One needs "=" and "/=" 
for null checks and direct pointer comparisons.

As Dmitry notes, "<" doesn't have a clear meaning for a segmented machine 
(comparing a code pointer and a data pointer is meaningless). Moreover, 
nothing in Ada says that an access value has to have any obvious 
relationship to a physical machine address. The Ada 83 design considered the 
idea that an access value might be a handle or some other sort of indirect 
value. (That's a bit different for a general access type, but even there the 
values are effectively unordered.)

If you need ordering, use System.Address. Better yet, don't use access types 
or addresses in your public interfaces at all -- your clients will be a lot 
happier for it. (YMMV.)

                                       Randy.