Should weak counted reference be able to be strengthened?

Should weak counted reference be able to be strengthened?

[Natasha Kerensikova]

Hello,

I hope I'm not too off-topic, but I have a question about designing weak
and strong references in a reference-counting system, implemented in
Ada.

In most of the general discussion about weak references, the title
question is a no-brainer: since the object referred by a weak reference
can disappear at any time, a strong reference must be obtained from the
weak reference before actually accessing the object.

However, in my (strong-only) current reference counting system, and in
most of those written in Ada, the referred object is not accessed
directly from the reference, instead they use an access discriminant in
a Mutator object (or an access constant discriminant in an Accessor),
and the object contains privately a strong reference, because in some
weird situations the reference might disappear before the mutator.

So my question is, now that I am considering extending my
reference-counting system to include weak reference, do I really needed
a public interface to build a strong reference from a weak one?
Or is it enough to have weak reference primitives that return Accessor
and Mutator objects, thereby allowing safe access without allowing a
weak reference to be promoted into a strong one?

In all the use cases I can imagine, the weak reference is only used to
access the referred object. I can't make up an example where a strong
reference would be needed from only a weak one. Am I missing something?

The interesting point I see in forbidding such a "reference
strengthening" is to prevent some cases circular strong references,
which is the problem weak references are supposed to solve.
Indeed, when an object has only a weak reference, it means it's
dangerous for it to hold a strong one, so it might also be dangerous for
it to hand one over to anything it can access.
The holder can still do bad things by storing an Accessor or a Mutator
object, but it is much more obviously a bad thing.

What are your thoughts on this?


As a side note, I'm a bit surprised by how easy weak/strong reference
seem to be: I think I would only need to store two counters instead of
one, one for the strong references and one for all references,
deallocating the object when the strong reference counter reaches
zero, and freeing the counters when the total counter reaches zero -- as
if each weak reference was a strong reference to the counters. Then it's
only a matter of adding an atomic increase-if-not-zero to the strong
reference counter to build accessors from weak references.
Is there a subtle trap I'm missing?


Thanks in advance for your help,
Natasha

Re: Should weak counted reference be able to be strengthened?

[Dmitry A. Kazakov]

On Fri, 21 Nov 2014 11:07:07 +0000 (UTC), Natasha Kerensikova wrote:

> So my question is, now that I am considering extending my
> reference-counting system to include weak reference, do I really needed
> a public interface to build a strong reference from a weak one?

Yes.

> Or is it enough to have weak reference primitives that return Accessor
> and Mutator objects, thereby allowing safe access without allowing a
> weak reference to be promoted into a strong one?

How this is supposed to work? The only safe referential object is a strong
reference.

> In all the use cases I can imagine, the weak reference is only used to
> access the referred object. I can't make up an example where a strong
> reference would be needed from only a weak one. Am I missing something?

Yes. There are many cases when weak references are components of containers
or when weak references are used in composite objects which change their
content upon disappearance of the referenced object.

> The interesting point I see in forbidding such a "reference
> strengthening" is to prevent some cases circular strong references,
> which is the problem weak references are supposed to solve.

When a weak reference is promoted to a strong one that occurs on a nested
context. Such strong references are allocated on the stack. Therefore there
is no any danger of getting circular dependencies unless the structure of
references in objects is already circular. In short, there is nothing to
worry about.

> As a side note, I'm a bit surprised by how easy weak/strong reference
> seem to be: I think I would only need to store two counters instead of
> one, one for the strong references and one for all references,
> deallocating the object when the strong reference counter reaches
> zero, and freeing the counters when the total counter reaches zero -- as
> if each weak reference was a strong reference to the counters. Then it's
> only a matter of adding an atomic increase-if-not-zero to the strong
> reference counter to build accessors from weak references.
> Is there a subtle trap I'm missing?

Weak references usually require a notification mechanism when the object
disappears. Thus you need a count and the head of the doubly-linked list of
the weak references pointing to the object.

In some complicated design you may need an identification of the holder of
a read-write strong reference. That is when referenced objects are mutated
while accessed in an immutable way in parallel. This is usually the case
when manipulating structures like graphs and trees. A read-write reference
clones the object if this is the first reference and works with already
existing copy if this is the second reference from the same context.

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

Re: Should weak counted reference be able to be strengthened?

[Natasha Kerensikova]

On 2014-11-21, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> On Fri, 21 Nov 2014 11:07:07 +0000 (UTC), Natasha Kerensikova wrote:
>
>> So my question is, now that I am considering extending my
>> reference-counting system to include weak reference, do I really needed
>> a public interface to build a strong reference from a weak one?
>
> Yes.

Thanks.

>> Or is it enough to have weak reference primitives that return Accessor
>> and Mutator objects, thereby allowing safe access without allowing a
>> weak reference to be promoted into a strong one?
>
> How this is supposed to work? The only safe referential object is a strong
> reference.

The strong reference is hidden in the accessor object. Consider for
example the following specification fragments, where T is the formal
type of the referred objects:

   type Accessor (Data : not null access constant T) is limited private;

   type Strong_Reference is tagged private;

   function Query (Ref : Strong_Reference) return Accessor;

   type Weak_Reference is tagged private;

   function Weaken (Parent : Strong_Reference'Class) return Weak_Reference;
      --  'Class only because we are still in the same package

   function Query (Ref : Weak_Reference) return Accessor;

private

   type Accessor (Data : not null access constant T) is limited record
      Parent : Strong_Reference;
   end record;

The only way to actually reach a referred object is by dereferencing the
access discriminant of an Accessor value. The strong reference inside
Accessor objects ensure that the referred object will outlive the
Accessor object.

However in that example, there is no way for the client to obtain a
strong reference from a weak one, since the one inside Accessor (that
ensures safe access) is private.

>> In all the use cases I can imagine, the weak reference is only used to
>> access the referred object. I can't make up an example where a strong
>> reference would be needed from only a weak one. Am I missing something?
>
> Yes. There are many cases when weak references are components of containers
> or when weak references are used in composite objects which change their
> content upon disappearance of the referenced object.

I wasn't aware of such a possibility, that's probably the big thing I
missed.

In all the examples with which I came up, the owner of a weak reference
doesn't need to distinguish between an empty reference that never held
an object and an empty reference because the object has been released.

>> The interesting point I see in forbidding such a "reference
>> strengthening" is to prevent some cases circular strong references,
>> which is the problem weak references are supposed to solve.
>
> When a weak reference is promoted to a strong one that occurs on a nested
> context. Such strong references are allocated on the stack. Therefore there
> is no any danger of getting circular dependencies unless the structure of
> references in objects is already circular. In short, there is nothing to
> worry about.

Such strong references are not limited, and could be very well be copied
to a permanent object. Or at least, strong references like the one in my
spec example above. However I agree that the strong reference inside
Accessor is indeed always on the stack, and guaranteed to never escape
from the Accessor object. So to make it live longer, one would need to
allocate an Accessor on the heap, which would be conspicuous.

>> As a side note, I'm a bit surprised by how easy weak/strong reference
>> seem to be: I think I would only need to store two counters instead of
>> one, one for the strong references and one for all references,
>> deallocating the object when the strong reference counter reaches
>> zero, and freeing the counters when the total counter reaches zero -- as
>> if each weak reference was a strong reference to the counters. Then it's
>> only a matter of adding an atomic increase-if-not-zero to the strong
>> reference counter to build accessors from weak references.
>> Is there a subtle trap I'm missing?
>
> Weak references usually require a notification mechanism when the object
> disappears. Thus you need a count and the head of the doubly-linked list of
> the weak references pointing to the object.

I'm still not completely figuring out how much usefulness is lost when
the notification mechanism is not implemented.

Honestly, weak references with notifications feel like too large a
project for me. Even more complicated systems, like those you described
in the following snipped paragraph, are also out of the question. There
is only so much I feel comfortable to re-invent.

So basically now, I'm wondering whether my poor limited weak references
still have some use or whether I should be giving up entirely.

As far as I can see, they are still useful as "backlinks", e.g. a
parent object that has containers whose elements need a reference to the
parent, though that's a bit limited...



Thanks for your comments,
Natasha

Re: Should weak counted reference be able to be strengthened?

[Dmitry A. Kazakov]

On Fri, 21 Nov 2014 15:00:12 +0000 (UTC), Natasha Kerensikova wrote:

> The strong reference is hidden in the accessor object. Consider for
> example the following specification fragments, where T is the formal
> type of the referred objects:
> 
>    type Accessor (Data : not null access constant T) is limited private;
> 
>    type Strong_Reference is tagged private;
> 
>    function Query (Ref : Strong_Reference) return Accessor;
> 
>    type Weak_Reference is tagged private;
> 
>    function Weaken (Parent : Strong_Reference'Class) return Weak_Reference;
>       --  'Class only because we are still in the same package
> 
>    function Query (Ref : Weak_Reference) return Accessor;
> 
> private
> 
>    type Accessor (Data : not null access constant T) is limited record
>       Parent : Strong_Reference;
>    end record;

Why do you need accessors? For Ada's crazy implicit dereference?

> The only way to actually reach a referred object is by dereferencing the
> access discriminant of an Accessor value. The strong reference inside
> Accessor objects ensure that the referred object will outlive the
> Accessor object.

It is much simpler to return a plain access type:

   function Ptr (Ref : Strong_Reference) return not null access T['Class];

> However in that example, there is no way for the client to obtain a
> strong reference from a weak one, since the one inside Accessor (that
> ensures safe access) is private.

I don't understand the design anyway. Strong references should be obtained
from the access type the object (straight after object allocation).

>>> In all the use cases I can imagine, the weak reference is only used to
>>> access the referred object. I can't make up an example where a strong
>>> reference would be needed from only a weak one. Am I missing something?
>>
>> Yes. There are many cases when weak references are components of containers
>> or when weak references are used in composite objects which change their
>> content upon disappearance of the referenced object.
> 
> I wasn't aware of such a possibility, that's probably the big thing I
> missed.
> 
> In all the examples with which I came up, the owner of a weak reference
> doesn't need to distinguish between an empty reference that never held
> an object and an empty reference because the object has been released.

A classic example is GUI. Let you have a button widget. If you put the
button into a box widget, that is a strong reference held by the box
widget.

But if you can connect to the button's signal On_Click, this is a weak
reference. If the button is deleted, the signal handler is silently
disconnected. Having any signals connected does not prevent the signal
emitters from being deleted.

>>> The interesting point I see in forbidding such a "reference
>>> strengthening" is to prevent some cases circular strong references,
>>> which is the problem weak references are supposed to solve.
>>
>> When a weak reference is promoted to a strong one that occurs on a nested
>> context. Such strong references are allocated on the stack. Therefore there
>> is no any danger of getting circular dependencies unless the structure of
>> references in objects is already circular. In short, there is nothing to
>> worry about.
> 
> Such strong references are not limited, and could be very well be copied
> to a permanent object.

That is all the point. In this case circular dependency is already in the
design of the container object's types. It is irrelevant if circular
components are initialized from weak or strong references.

> However I agree that the strong reference inside
> Accessor is indeed always on the stack, and guaranteed to never escape
> from the Accessor object.

Helper types is bad design.

>>> As a side note, I'm a bit surprised by how easy weak/strong reference
>>> seem to be: I think I would only need to store two counters instead of
>>> one, one for the strong references and one for all references,
>>> deallocating the object when the strong reference counter reaches
>>> zero, and freeing the counters when the total counter reaches zero -- as
>>> if each weak reference was a strong reference to the counters. Then it's
>>> only a matter of adding an atomic increase-if-not-zero to the strong
>>> reference counter to build accessors from weak references.
>>> Is there a subtle trap I'm missing?
>>
>> Weak references usually require a notification mechanism when the object
>> disappears. Thus you need a count and the head of the doubly-linked list of
>> the weak references pointing to the object.
> 
> I'm still not completely figuring out how much usefulness is lost when
> the notification mechanism is not implemented.

You cannot implement them without that. A weak reference must be
invalidated when the object disappear. Thus some kind of notification must
be there anyway.

> Honestly, weak references with notifications feel like too large a
> project for me. Even more complicated systems, like those you described
> in the following snipped paragraph, are also out of the question. There
> is only so much I feel comfortable to re-invent.

Here is an implementation of:

http://www.dmitry-kazakov.de/ada/components.htm#Backward_Link

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

Re: Should weak counted reference be able to be strengthened?

[Natasha Kerensikova]

On 2014-11-21, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> On Fri, 21 Nov 2014 15:00:12 +0000 (UTC), Natasha Kerensikova wrote:
>
>>    type Accessor (Data : not null access constant T) is limited record
>>       Parent : Strong_Reference;
>>    end record;
>
> Why do you need accessors? For Ada's crazy implicit dereference?

Not for implicit dereference, last time I checked my GNAT FSF didn't
handle it well.

Rather for the reasons explained in
http://www.adacore.com/adaanswers/gems/gem-107-preventing-deallocation-for-reference-counted-types/

>> However I agree that the strong reference inside
>> Accessor is indeed always on the stack, and guaranteed to never escape
>> from the Accessor object.
>
> Helper types is bad design.

I wasn't aware of that.

But then what about:

   type Counter is range 0 .. 640_000;  --  that ought to be enough for anybody

isn't that also a bad-design helper type?

>>>> As a side note, I'm a bit surprised by how easy weak/strong reference
>>>> seem to be: I think I would only need to store two counters instead of
>>>> one, one for the strong references and one for all references,
>>>> deallocating the object when the strong reference counter reaches
>>>> zero, and freeing the counters when the total counter reaches zero -- as
>>>> if each weak reference was a strong reference to the counters. Then it's
>>>> only a matter of adding an atomic increase-if-not-zero to the strong
>>>> reference counter to build accessors from weak references.
>>>> Is there a subtle trap I'm missing?
>>>
>>> Weak references usually require a notification mechanism when the object
>>> disappears. Thus you need a count and the head of the doubly-linked list of
>>> the weak references pointing to the object.
>> 
>> I'm still not completely figuring out how much usefulness is lost when
>> the notification mechanism is not implemented.
>
> You cannot implement them without that. A weak reference must be
> invalidated when the object disappear. Thus some kind of notification must
> be there anyway.

In the example in the innermost quote, there is no direct notification,
in that there is no way to run arbitrary code when the referred object
disappear. However the information about object disappearance is
accessible to the weak reference: whenever the strong reference count is
zero, the referred object cannot be accessed. You could consider it at
as asynchronous notification, but that's still useless e.g. to clean-up
a cache entry or a signal handler (unless some periodic task goes
through the list of weak references to explicitly check whether they are
still valid).


Natasha

Re: Should weak counted reference be able to be strengthened?

[Dmitry A. Kazakov]

On Fri, 21 Nov 2014 18:24:13 +0000 (UTC), Natasha Kerensikova wrote:

> On 2014-11-21, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>> On Fri, 21 Nov 2014 15:00:12 +0000 (UTC), Natasha Kerensikova wrote:
>>
>>>    type Accessor (Data : not null access constant T) is limited record
>>>       Parent : Strong_Reference;
>>>    end record;
>>
>> Why do you need accessors? For Ada's crazy implicit dereference?
> 
> Not for implicit dereference, last time I checked my GNAT FSF didn't
> handle it well.
> 
> Rather for the reasons explained in
> http://www.adacore.com/adaanswers/gems/gem-107-preventing-deallocation-for-reference-counted-types/

Which is misleading. The result should have been an anonymous access. Then
it could not be copied without a conversion.

And there is a safe pattern (in Ada 2005) for handling references without
any access types and without implicit dereference.

>>> However I agree that the strong reference inside
>>> Accessor is indeed always on the stack, and guaranteed to never escape
>>> from the Accessor object.
>>
>> Helper types is bad design.
> 
> I wasn't aware of that.
> 
> But then what about:
> 
>    type Counter is range 0 .. 640_000;  --  that ought to be enough for anybody
> 
> isn't that also a bad-design helper type?

No, because Counter is not a helper type. A type is helper when needed due
to language reasons (deficiencies usually). When a type describes a problem
space entity like Counter does, it is not a helper.

>>>>> As a side note, I'm a bit surprised by how easy weak/strong reference
>>>>> seem to be: I think I would only need to store two counters instead of
>>>>> one, one for the strong references and one for all references,
>>>>> deallocating the object when the strong reference counter reaches
>>>>> zero, and freeing the counters when the total counter reaches zero -- as
>>>>> if each weak reference was a strong reference to the counters. Then it's
>>>>> only a matter of adding an atomic increase-if-not-zero to the strong
>>>>> reference counter to build accessors from weak references.
>>>>> Is there a subtle trap I'm missing?
>>>>
>>>> Weak references usually require a notification mechanism when the object
>>>> disappears. Thus you need a count and the head of the doubly-linked list of
>>>> the weak references pointing to the object.
>>> 
>>> I'm still not completely figuring out how much usefulness is lost when
>>> the notification mechanism is not implemented.
>>
>> You cannot implement them without that. A weak reference must be
>> invalidated when the object disappear. Thus some kind of notification must
>> be there anyway.
> 
> In the example in the innermost quote, there is no direct notification,
> in that there is no way to run arbitrary code when the referred object
> disappear. However the information about object disappearance is
> accessible to the weak reference: whenever the strong reference count is
> zero,

The reference count is a part of the object. When the object is gone, there
is no reference count.

Of course, you could add some levels of indirection to keep counters off
the objects, but then you would have serious problems, e.g. like Ada tasks
have when allocated and deallocated dynamically.

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

Re: Should weak counted reference be able to be strengthened?

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:1h5a33dishpky.8m2rngmy7e7x$.dlg@40tude.net...
> On Fri, 21 Nov 2014 18:24:13 +0000 (UTC), Natasha Kerensikova wrote:
>
>> On 2014-11-21, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>>> On Fri, 21 Nov 2014 15:00:12 +0000 (UTC), Natasha Kerensikova wrote:
>>>
>>>>    type Accessor (Data : not null access constant T) is limited record
>>>>       Parent : Strong_Reference;
>>>>    end record;
>>>
>>> Why do you need accessors? For Ada's crazy implicit dereference?
>>
>> Not for implicit dereference, last time I checked my GNAT FSF didn't
>> handle it well.
>>
>> Rather for the reasons explained in
>> http://www.adacore.com/adaanswers/gems/gem-107-preventing-deallocation-for-reference-counted-types/
>
> Which is misleading. The result should have been an anonymous access. Then
> it could not be copied without a conversion.

So? You still could convert it to any type and cause it to become dangling.

> And there is a safe pattern (in Ada 2005) for handling references without
> any access types and without implicit dereference.

Sure, but it's practically unusable (as occurred in the containers).

>>>> However I agree that the strong reference inside
>>>> Accessor is indeed always on the stack, and guaranteed to never escape
>>>> from the Accessor object.
>>>
>>> Helper types is bad design.
>>
>> I wasn't aware of that.

Me either. ;-) Remember that Dmitry often has unique opinions about software 
design. :-)

                                  Randy.

Re: Should weak counted reference be able to be strengthened?

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:kywrzxvibzmw$.1h82z2coiciqh$.dlg@40tude.net...
> On Fri, 21 Nov 2014 15:00:12 +0000 (UTC), Natasha Kerensikova wrote:
>
>> The strong reference is hidden in the accessor object. Consider for
>> example the following specification fragments, where T is the formal
>> type of the referred objects:
>>
>>    type Accessor (Data : not null access constant T) is limited private;
>>
>>    type Strong_Reference is tagged private;
>>
>>    function Query (Ref : Strong_Reference) return Accessor;
>>
>>    type Weak_Reference is tagged private;
>>
>>    function Weaken (Parent : Strong_Reference'Class) return 
>> Weak_Reference;
>>       --  'Class only because we are still in the same package
>>
>>    function Query (Ref : Weak_Reference) return Accessor;
>>
>> private
>>
>>    type Accessor (Data : not null access constant T) is limited record
>>       Parent : Strong_Reference;
>>    end record;
>
> Why do you need accessors? For Ada's crazy implicit dereference?

It's not crazy, it's brilliant. ;-) There's really no other way to make 
things both easy-to-use and safe.

Anyway, I think Natasha was right initially. The only strong references that 
ought to exist are those associated with the accessor type, and those 
clearly will be short-lived and not going to end up circular. That's 
essentially the model used the the Ada.Containers (where a Cursor is a weak 
reference, and the tampering check is used to ensure it is a strong 
reference while an accessor or iterator exists).

Indeed, the easiest thing to do is to rename Accessor to Strong_Reference, 
and all is solved. :-)

The real question is whether there is a real need to have a long-lived 
Strong_Reference. I would argue against such a thing, but I don't think it 
is clearly an open-and-shut case.

>> The only way to actually reach a referred object is by dereferencing the
>> access discriminant of an Accessor value. The strong reference inside
>> Accessor objects ensure that the referred object will outlive the
>> Accessor object.
>
> It is much simpler to return a plain access type:
>
>   function Ptr (Ref : Strong_Reference) return not null access T['Class];

Sure, but now you have an extra function with no real purpose. If you use 
the accessor form, you don't need any way at all to get the pointer, you 
always have access to it. As I said, the most sensible thing is to rename 
type Accessor to Strong_Reference and all is well (especially as you usually 
won't explicitly create one of these, so the name is irrelevant).

And anytime you have a bare pointer, you have the possibility of it becoming 
dangling because they're easy to copy. My preference would be to never 
expose it at all, but of course that causes problems for ease-of-use.

                                          Randy.

Re: Should weak counted reference be able to be strengthened?

[Shark8]

On 21-Nov-14 15:39, Randy Brukardt wrote:
> And anytime you have a bare pointer, you have the possibility of it becoming
> dangling because they're easy to copy.

...Isn't that what Limited is for? To prevent copying?

Re: Should weak counted reference be able to be strengthened?

[Dmitry A. Kazakov]

On Fri, 21 Nov 2014 15:49:42 -0700, Shark8 wrote:

> On 21-Nov-14 15:39, Randy Brukardt wrote:
>> And anytime you have a bare pointer, you have the possibility of it becoming
>> dangling because they're easy to copy.
> 
> ...Isn't that what Limited is for? To prevent copying?

But access type are only half-types in Ada. You cannot do

   type P is limited access T;

In a better designed type system, the pointer type interface ("is access")
would not be copyable.

In order to get a copyable pointer you would have to derive it from the
interface of copyable objects ("is private").

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

Re: Should weak counted reference be able to be strengthened?

[Dmitry A. Kazakov]

On Fri, 21 Nov 2014 16:39:25 -0600, Randy Brukardt wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
> news:kywrzxvibzmw$.1h82z2coiciqh$.dlg@40tude.net...

>> Why do you need accessors? For Ada's crazy implicit dereference?
> 
> It's not crazy, it's brilliant. ;-) There's really no other way to make 
> things both easy-to-use and safe.

Of course there is a way and without either accessor types or implicit
dereference.

[...] 
> The real question is whether there is a real need to have a long-lived 
> Strong_Reference. I would argue against such a thing, but I don't think it 
> is clearly an open-and-shut case.

Sure, the only purpose of strong references is to be long-lived.

>>> The only way to actually reach a referred object is by dereferencing the
>>> access discriminant of an Accessor value. The strong reference inside
>>> Accessor objects ensure that the referred object will outlive the
>>> Accessor object.
>>
>> It is much simpler to return a plain access type:
>>
>>   function Ptr (Ref : Strong_Reference) return not null access T['Class];
> 
> Sure, but now you have an extra function with no real purpose. If you use 
> the accessor form, you don't need any way at all to get the pointer, you 
> always have access to it.

Accessor is a whole type without purpose and all functions it has are
without purpose as well.

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

Re: Should weak counted reference be able to be strengthened?

[Natasha Kerensikova]

On 2014-11-21, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>>>>>> As a side note, I'm a bit surprised by how easy weak/strong reference
>>>>>> seem to be: I think I would only need to store two counters instead of
>>>>>> one, one for the strong references and one for all references,
>>>>>> deallocating the object when the strong reference counter reaches
>>>>>> zero, and freeing the counters when the total counter reaches zero -- as
>>>>>> if each weak reference was a strong reference to the counters. Then it's
>>>>>> only a matter of adding an atomic increase-if-not-zero to the strong
>>>>>> reference counter to build accessors from weak references.
>>>>>> Is there a subtle trap I'm missing?
>>>> 
>>>> [...]
>> 
>> In the example in the innermost quote, there is no direct notification,
>> in that there is no way to run arbitrary code when the referred object
>> disappear. However the information about object disappearance is
>> accessible to the weak reference: whenever the strong reference count is
>> zero,
>
> The reference count is a part of the object. When the object is gone, there
> is no reference count.
>
> Of course, you could add some levels of indirection to keep counters off
> the objects, but then you would have serious problems, e.g. like Ada tasks
> have when allocated and deallocated dynamically.

Having the counters separate from the object is actually the defining
point of implementation, and the only reason it exists in the first
place:

generic
   type Held_Data (<>) is limited priavte;
package Natools.References is
   [...]
private
   type Data_Access is access Held_Data;
   type Counter_Access is access Counter;

   type Reference is new Ada.Finalization.Controlled with record
      Count : Counter_Access := null;
      Data : Data_Acess := null;
   end record;
end Natools.References;

As far as I understand, this makes it possible to instantiate with
literally any Ada type, except incomplete ones. This makes it useful in
a niche not covered by any other implementation (that I know of).

However, what are the serious problems I'm supposed to have?
I have used this implementation with task types, but I have yet to
encounter any.


Natasha

Re: Should weak counted reference be able to be strengthened?

[Dmitry A. Kazakov]

On Sat, 22 Nov 2014 09:57:05 +0000 (UTC), Natasha Kerensikova wrote:

> On 2014-11-21, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>>>>>>> As a side note, I'm a bit surprised by how easy weak/strong reference
>>>>>>> seem to be: I think I would only need to store two counters instead of
>>>>>>> one, one for the strong references and one for all references,
>>>>>>> deallocating the object when the strong reference counter reaches
>>>>>>> zero, and freeing the counters when the total counter reaches zero -- as
>>>>>>> if each weak reference was a strong reference to the counters. Then it's
>>>>>>> only a matter of adding an atomic increase-if-not-zero to the strong
>>>>>>> reference counter to build accessors from weak references.
>>>>>>> Is there a subtle trap I'm missing?
>>>>> 
>>>>> [...]
>>> 
>>> In the example in the innermost quote, there is no direct notification,
>>> in that there is no way to run arbitrary code when the referred object
>>> disappear. However the information about object disappearance is
>>> accessible to the weak reference: whenever the strong reference count is
>>> zero,
>>
>> The reference count is a part of the object. When the object is gone, there
>> is no reference count.
>>
>> Of course, you could add some levels of indirection to keep counters off
>> the objects, but then you would have serious problems, e.g. like Ada tasks
>> have when allocated and deallocated dynamically.
> 
> Having the counters separate from the object is actually the defining
> point of implementation, and the only reason it exists in the first
> place:
> 
> generic
>    type Held_Data (<>) is limited priavte;
> package Natools.References is
>    [...]
> private
>    type Data_Access is access Held_Data;

This won't work. A pool-specific pointer should be the package's parameter,
since the objects are allocated outside the package, aren't they?

>    type Counter_Access is access Counter;
> 
>    type Reference is new Ada.Finalization.Controlled with record
>       Count : Counter_Access := null;
>       Data : Data_Acess := null;
>    end record;
> end Natools.References;
>
> As far as I understand, this makes it possible to instantiate with
> literally any Ada type, except incomplete ones.

If you want this, use a custom storage pool to allocate the objects and put
the reference count before the object upon allocation. At least, it will
guarantee that both will vanish together.

[ There is some minor issue with Ada's design bug of X'Address when X is an
unconstrained array, but nothing one could not work around ]

> This makes it useful in
> a niche not covered by any other implementation (that I know of).

I don't think it is useful because reference-counted objects share some
common interface. So there must be a base type anyway.
 
> However, what are the serious problems I'm supposed to have?
> I have used this implementation with task types, but I have yet to
> encounter any.

The problem is that when you deallocate a task that is not yet terminated.
A typical code deallocating tasks looks like:

   T.Shut_Down; -- Go away!
   while not T'Terminated loop -- Still here?
      delay 0.01;
   end loop;
   Free (T); -- We are ready now

This is basically the same issue as with your Reference type which may
outlive the object. So are some internal things associated with the task,
which may outlive the object deallocated when the access-to-task is freed.

This is a complicated design with no reason (in case of tasks, there is a
reason). Why should reference outlive the object?

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

Re: Should weak counted reference be able to be strengthened?

[Natasha Kerensikova]

On 2014-11-22, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
> On Sat, 22 Nov 2014 09:57:05 +0000 (UTC), Natasha Kerensikova wrote:
>> generic
>>    type Held_Data (<>) is limited priavte;
>> package Natools.References is
>>    [...]
>> private
>>    type Data_Access is access Held_Data;
>
> This won't work. A pool-specific pointer should be the package's parameter,
> since the objects are allocated outside the package, aren't they?

They aren't. I find it much easier to deal with memory in the private
parts of a single package.

References are normally created using:

   function Create
     (Constructor : not null access function return Held_Data)
      return Reference;


(To be perfectly honest, I later added an access based constructor where
the client performs the allocation, but only to prevent an internal copy
from the function return to the allocated memory in a non-limited large
object instance (large enough to have the program OOM-killed when using
an internal copy, while an external build-in-place fits in the target
system memory).
You can inspect the whole code at
https://github.com/faelys/natools/blob/trunk/src/natools-references__protected.ads
)

>> However, what are the serious problems I'm supposed to have?
>> I have used this implementation with task types, but I have yet to
>> encounter any.
>
> The problem is that when you deallocate a task that is not yet terminated.
> A typical code deallocating tasks looks like:
>
>    T.Shut_Down; -- Go away!
>    while not T'Terminated loop -- Still here?
>       delay 0.01;
>    end loop;
>    Free (T); -- We are ready now
>
> This is basically the same issue as with your Reference type which may
> outlive the object. So are some internal things associated with the task,
> which may outlive the object deallocated when the access-to-task is freed.
>
> This is a complicated design with no reason (in case of tasks, there is a
> reason). Why should reference outlive the object?

How could a reference outlive the object?
The object is deallocated only in the Finalize of the last reference.


Natasha

Re: Should weak counted reference be able to be strengthened?

[Dmitry A. Kazakov]

On Sat, 22 Nov 2014 10:36:15 +0000 (UTC), Natasha Kerensikova wrote:

> On 2014-11-22, Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>> On Sat, 22 Nov 2014 09:57:05 +0000 (UTC), Natasha Kerensikova wrote:
>>> generic
>>>    type Held_Data (<>) is limited priavte;
>>> package Natools.References is
>>>    [...]
>>> private
>>>    type Data_Access is access Held_Data;
>>
>> This won't work. A pool-specific pointer should be the package's parameter,
>> since the objects are allocated outside the package, aren't they?
> 
> They aren't. I find it much easier to deal with memory in the private
> parts of a single package.
> 
> References are normally created using:
> 
>    function Create
>      (Constructor : not null access function return Held_Data)
>       return Reference;

You expect all clients having a function (parameterless!) to create
objects? This would be barely usable.

And this will not work with truly limited types. Constructing functions do
not work and never will.

A pragmatic design is that the client creates the object by whatever means
it finds appropriate and then passes the control over to the first strong
reference. Which is quite safe because no explicit pointers involved. For
example:

   declare
      P : Handle := Ref (new Object (...));
   begin

OK, in practical cases due to Ada's limitations (lacking constructors and
other messes), the code looks rather like:

   declare
      P : Handle := Ref (new Derived_Object (...));
      This : Derived_Object renames Derived_Object (P.Ptr.all);
   begin
      This.Component := ...;
          -- Doing things Initialize failed to accomplish.

>>> However, what are the serious problems I'm supposed to have?
>>> I have used this implementation with task types, but I have yet to
>>> encounter any.
>>
>> The problem is that when you deallocate a task that is not yet terminated.
>> A typical code deallocating tasks looks like:
>>
>>    T.Shut_Down; -- Go away!
>>    while not T'Terminated loop -- Still here?
>>       delay 0.01;
>>    end loop;
>>    Free (T); -- We are ready now
>>
>> This is basically the same issue as with your Reference type which may
>> outlive the object. So are some internal things associated with the task,
>> which may outlive the object deallocated when the access-to-task is freed.
>>
>> This is a complicated design with no reason (in case of tasks, there is a
>> reason). Why should reference outlive the object?
> 
> How could a reference outlive the object?
> The object is deallocated only in the Finalize of the last reference.

Then how a weak reference could access it otherwise? The point is that you
need to invalidate weak references at once or else you have keep some
object's data no matter where allocated after the object's official death.

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

Re: Should weak counted reference be able to be strengthened?

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:1tlppwq452jbq$.d1y3trfego8b$.dlg@40tude.net...
> On Fri, 21 Nov 2014 16:39:25 -0600, Randy Brukardt wrote:
>
...
> [...]
>> The real question is whether there is a real need to have a long-lived
>> Strong_Reference. I would argue against such a thing, but I don't think 
>> it
>> is clearly an open-and-shut case.
>
> Sure, the only purpose of strong references is to be long-lived.

But you (almost?) never need such a thing, at least not without access to 
underlying object as well. Thus I suggested unifying the Accessor and the 
Strong_Reference.

>>>> The only way to actually reach a referred object is by dereferencing 
>>>> the
>>>> access discriminant of an Accessor value. The strong reference inside
>>>> Accessor objects ensure that the referred object will outlive the
>>>> Accessor object.
>>>
>>> It is much simpler to return a plain access type:
>>>
>>>   function Ptr (Ref : Strong_Reference) return not null access 
>>> T['Class];
>>
>> Sure, but now you have an extra function with no real purpose. If you use
>> the accessor form, you don't need any way at all to get the pointer, you
>> always have access to it.
>
> Accessor is a whole type without purpose and all functions it has are
> without purpose as well.

I was suggesting that "Accessor" actually be named "Strong_Reference"; I can 
see no need for a separate Strong_Reference type. As such, there's no extra 
type here. Instead, you have an extra function "Ptr" which serves no purpose 
except an extra complication. :-)

                               Randy.

Re: Should weak counted reference be able to be strengthened?

[Dmitry A. Kazakov]

On Mon, 24 Nov 2014 16:15:10 -0600, Randy Brukardt wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
> news:1tlppwq452jbq$.d1y3trfego8b$.dlg@40tude.net...
>> On Fri, 21 Nov 2014 16:39:25 -0600, Randy Brukardt wrote:
>>
> ...
>> [...]
>>> The real question is whether there is a real need to have a long-lived
>>> Strong_Reference. I would argue against such a thing, but I don't think 
>>> it is clearly an open-and-shut case.
>>
>> Sure, the only purpose of strong references is to be long-lived.
> 
> But you (almost?) never need such a thing, at least not without access to 
> underlying object as well. Thus I suggested unifying the Accessor and the 
> Strong_Reference.

Right. But I go one step further and hide target type altogether making
only the reference visible.

Actually, reference like an access type must inherit the target object's
interface. The original Ada 83 design was right with regard to indexing and
record member operations inherited by access types. It should have
inherited everything including assignment.

Access type assignment should have a different notation unless ":=" were
specifically overridden. Especially because copying pointers is always
dangerous.

>>> Sure, but now you have an extra function with no real purpose. If you use
>>> the accessor form, you don't need any way at all to get the pointer, you
>>> always have access to it.
>>
>> Accessor is a whole type without purpose and all functions it has are
>> without purpose as well.
> 
> I was suggesting that "Accessor" actually be named "Strong_Reference"; I can 
> see no need for a separate Strong_Reference type. As such, there's no extra 
> type here. Instead, you have an extra function "Ptr" which serves no purpose 
> except an extra complication. :-)

Ptr was needed to keep it Ada 95 compatible.

An Ada 2005 design would hide the target object type altogether.

   type T_Interface is interface ...
   procedure Foo (X : T_Interface) is abstract;

privately:

   type T is ... and T_Interface ...  -- Object implementation
   overriding procedure Foo (X : T);

publicly

  type T_Reference is ... and T_Interface with private;
   overriding procedure Foo (X : T_Reference);
private
  type T_Ptr is access T;
  type T_Reference is ... and T_Interface with record
      Ptr : T_Ptr;
  end record;

  procedure Foo (X : T_Reference) is
  begin
     X.Ptr.Foo; -- Delegation
  end Foo;

Instead of introducing "crazy beautiful" implicit dereference, Ada 2012
should have delegation support for the patterns like this.

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

Re: Should weak counted reference be able to be strengthened?

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:1xbl1kdcf9at5.1dfv4py4kvx0o.dlg@40tude.net...
...
> Instead of introducing "crazy beautiful" implicit dereference, Ada 2012
> should have delegation support for the patterns like this.

Depending heavily on interfaces is a sure way to madness. :-)

But the real problem here is I don't see any way to add "delegation support" 
that actually saves much over the explicit version that you showed. We 
certainly don't want *everything* to delegate (it has to be declared somehow 
for the particular operations in question), and because of overloading we 
have to at least have the complete profile. That means an awful lot of 
typing (and source text to read), and lots of chance for errors.

In a sense, Ada 2012 has delegation support as one can use expression 
functions that way. (If I had gotten the full design in place, they could 
have been used with an interface type to provide a default implementation as 
well, which could have been designed to delegate. But we left out the two 
options for expression functions [staticness, and the interface cases].)

                                   Randy.

Re: Should weak counted reference be able to be strengthened?

[Dmitry A. Kazakov]

On Tue, 25 Nov 2014 15:49:49 -0600, Randy Brukardt wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
> news:1xbl1kdcf9at5.1dfv4py4kvx0o.dlg@40tude.net...
> ...
>> Instead of introducing "crazy beautiful" implicit dereference, Ada 2012
>> should have delegation support for the patterns like this.
> 
> Depending heavily on interfaces is a sure way to madness. :-)
> 
> But the real problem here is I don't see any way to add "delegation support" 
> that actually saves much over the explicit version that you showed. We 
> certainly don't want *everything* to delegate (it has to be declared somehow 
> for the particular operations in question),

Everything of course, unless explicitly overridden.

> and because of overloading we 
> have to at least have the complete profile. That means an awful lot of 
> typing (and source text to read), and lots of chance for errors.

Yes, which is why delegation and other means to compose overridden
operations are needed.

The programmer should be able to define things which happen implicitly when
for example:

   type X is new Integer;

This implicitly defines a lot of operations composed like:

   function "abs" (Value : X) return X
      = X (abs (Integer (Value));

It is not much different from how "sane" implicit dereference would work

   type Y is access Integer;

   function "abs" (Value : Y) return Integer
      = abs (Value.all);

I don't know how to describe such things syntactically. That is a
challenge.

> In a sense, Ada 2012 has delegation support as one can use expression 
> functions that way.

Yes, they could be viewed this way, but in my view they are too powerful.
What I want is a more limited mechanism of composition which could be
easily checked. The limitation is that the old body is used with an
epilogue and/or a prologue and conversions are applied to the arguments
and/or the result. If the body has to be changed, it must be overridden.

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

Re: Should weak counted reference be able to be strengthened?

[brbarkstrom]

On Wednesday, November 26, 2014 4:28:07 AM UTC-5, Dmitry A. Kazakov wrote:
> On Tue, 25 Nov 2014 15:49:49 -0600, Randy Brukardt wrote:
> 
> > "Dmitry A. Kazakov" wrote in message 
> 
> > ...
> >> Instead of introducing "crazy beautiful" implicit dereference, Ada 2012
> >> should have delegation support for the patterns like this.
> > 
> > Depending heavily on interfaces is a sure way to madness. :-)
> > 
> > But the real problem here is I don't see any way to add "delegation support" 
> > that actually saves much over the explicit version that you showed. We 
> > certainly don't want *everything* to delegate (it has to be declared somehow 
> > for the particular operations in question),
> 
> Everything of course, unless explicitly overridden.
> 
> > and because of overloading we 
> > have to at least have the complete profile. That means an awful lot of 
> > typing (and source text to read), and lots of chance for errors.
> 
> Yes, which is why delegation and other means to compose overridden
> operations are needed.
> 
> The programmer should be able to define things which happen implicitly when
> for example:
> 
>    type X is new Integer;
> 
> This implicitly defines a lot of operations composed like:
> 
>    function "abs" (Value : X) return X
>       = X (abs (Integer (Value));
> 
> It is not much different from how "sane" implicit dereference would work
> 
>    type Y is access Integer;
> 
>    function "abs" (Value : Y) return Integer
>       = abs (Value.all);
> 
> I don't know how to describe such things syntactically. That is a
> challenge.
> 
> > In a sense, Ada 2012 has delegation support as one can use expression 
> > functions that way.
> 
> Yes, they could be viewed this way, but in my view they are too powerful.
> What I want is a more limited mechanism of composition which could be
> easily checked. The limitation is that the old body is used with an
> epilogue and/or a prologue and conversions are applied to the arguments
> and/or the result. If the body has to be changed, it must be overridden.
> 
> -- 
> Regards,
> Dmitry A. Kazakov

This dialogue reminds me of a substantial conversation currently going on
in the library community with respect to long-term (200 years) information
preservation with transformational migration.  The problem gets even more
interesting in federated archives (think DSA across the Internet).

The life of digital files (or databases) is more or less limited by the
lifecycle of hardware or software obsolescence.  So, if your favorite
documentation formatting vendor decides to deprecate the previous format,
what's an archive to do - transform the original or throw it out?  If the
archive throws the document out, it might still want a reference to it to
maintain a provenance track that can aid in proving authenticity of the
transformed original.  

Furthermore, that community has tendencies to want some centralized authority 
to provide references to the "unique" "authentic original."  [Never mind the
fact that such an authority - raking in money even - is a single point of
failue.]  So, if the archive throws out that original file (or it becomes 
unreadable) and the community seems to think that a backup copy is "not 
authentic" because only the one "original" copy was the "authentic" one
there may need to be some mechanism to notify users of the history of the
changes.

The weak references in the previous posts appear to be like the 
"centralized" site's reference to the archive copy that they think is
the "authentic original" (but now unreadable or deleted).  The latter
is presumably the strong reference.

I'm still inclined to think Ada has a significant potential market in
the long-term information preservation business.  The requirements for
loss per year are into the number of nines we think about for life-critical
software systems.  After looking at the posts here, I am pretty sure that
the arguments about weak and strong references in Ada are similar (and
perhaps mathematically identical) to the issues the library community
is arguing about.  There may even be some light their discussion 
could shed on the one in the Ada community.  [Besides, if this small
discussion could help solve a "big" problem, that would be even more fun.]

Bruce B.

Re: Should weak counted reference be able to be strengthened?

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:1kqnn4e05fbl2$.1wv2gk39uwsha.dlg@40tude.net...
> On Tue, 25 Nov 2014 15:49:49 -0600, Randy Brukardt wrote:
...
> It is not much different from how "sane" implicit dereference would work
>
>   type Y is access Integer;
>
>   function "abs" (Value : Y) return Integer
>      = abs (Value.all);
>
> I don't know how to describe such things syntactically. That is a
> challenge.

Exactly; without a syntax solution there's really not much point in the 
idea. I've tried to do that even in the limited case of finalization 
routines, and was unable to come up with anything that really worked. (The 
semantics is reasonably straightforward, but it has to be be written in a 
readable and hopefully natural way.)

And I really can hardly imagine something that would work "always", given 
the differences between functions and procedures, and the need to handle out 
parameters, and so on.

>> In a sense, Ada 2012 has delegation support as one can use expression
>> functions that way.
>
> Yes, they could be viewed this way, but in my view they are too powerful.
> What I want is a more limited mechanism of composition which could be
> easily checked. The limitation is that the old body is used with an
> epilogue and/or a prologue and conversions are applied to the arguments
> and/or the result. If the body has to be changed, it must be overridden.

It strikes me that renames-as-body can also be used in that way (for a more 
limited case). But you really would prefer something much more automatic, 
and that seems hard to do usefully.

                                               Randy.