Re: A novel design of linked lists

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

On 19 Sep 2006 13:09:44 -0700, Adam Beneschan wrote:

> Dmitry A. Kazakov wrote:
>> [ It seems to me that some people have an impression that I am looking for
>> something extraordinary when asking for the object address, so I feel
>> necessary to provide an elaborated example where it were needed. ]
>>
>> Let's consider referential double-linked lists as an example. The drawbacks
>> of the Ada.Containers design are obvious. A typical design of such lists in
>> other languages would be adding Prev, Next pointers to the elements. Note
>> also, that we wished to have linked lists of elements which might
>> participate in many lists simultaneously. We also liked to statically check
>> the types of such lists, so that paths in different lists could never
>> converge.
>>
>> There are two ways to do add links Prevs and Nexts. One of them is to do it
>> upon inheritance. Another is by using new elements containing pointers to
>> the "true" elements.
>>
>> 1. The variant with inheritance is not an option in current Ada, because of
>> lack of MI. Even with MI it faces the problem that links has to be added to
>> the base type. That would require downcasting later, all over the program.
>> Adding links in the leaves of the type hierarchy would break it apart and
>> also freeze the types for future derivation. Ad-hoc supertypes could help,
>> but, firstly, they are not supported and, secondly, they barely could have
>> referential semantics. So the elements will require copying.
>>
>> 2. The variant with pointers is not a solution at all, because, honestly,
>> it would be a list of pointers rather than of the elements.
> 
> I'll have to admit that I don't see what "problem" you have that this
> isn't a solution to.  In fact, I'm not really clear on why it's
> important to you to adopt the approach you're adopting; your
> explanation is pretty sketchy.

That was an example illustrating the case - a need to get an intact object
address.

As for possible application areas of double-linked lists, honestly, I don't
know what sort of explanation you liked to hear from me...

> Part of my problem is that you seem to want to define a type, Item_Ptr,
> that gives you more than it's supposed to give you.  Your generic
> declares
> 
>    type Item_Ptr is access List_Type_Item;
> 
> where List_Type_Item is whatever type you're making a list out of.  I
> see a type like this, and I think it's just an access to the
> List_Type_Item, but there's actually additional baggage in this
> pointer, i.e. a "next" and a "previous" pointer.  So if I see code that
> calls Next on this Item_Ptr, my first thought is "Whooaa!  Item_Ptr is
> just an access to my Employee record, so where the heck is it going to
> get a pointer to another Employee?" It would be pretty confusing to me.

[ It would be nice to have user-defined fat access types, but,
unfortunately, Ada does not provide them. Ergo, you are not allowed to
think that way in Ada. You have to - "Aha, there must something in the
target object that allows this Next." ]

Item_Ptr is an ADT.

> Personally, if I'm going to have something that contains additional
> information, I'd prefer that it be a different type.

which is Item_Ptr. I hope that you'd agree that "contains additional
information" does not necessarily imply *physically* contains the
information.

> The need for
> downcasting, type conversion, or a Deref function in your generic that
> takes an Item_Ptr and returns the dereferenced item that I would use
> instead of .all, doesn't bother me at all.  So I don't see what problem
> there is that needs solving.

Hmm, if you consider a need in downcasting and explicit type conversions of
elements of a double-linked lists as OK, then we are on different pages.

> Plus, you introduce a problem.  Assuming the actual for List_Type_Item
> is T, you've defined Item_Ptr as an access to T; what happens if
> somewhere else in the program, there is another type that is also an
> access to T?  The language will let you convert between the two access
> types, but the result would be an absolute disaster.  But I just know
> that someone who doesn't really understand that Item_Ptr isn't just an
> access to T is going to try it.

No, it is illegal in Ada. You cannot freely convert between pool-specific
access types. Item_Ptr is pool-specific. You can convert it to a general
access type, but that would make no harm. A backward conversion is again
impossible. It does not leak, Ada is a safe language. [ I don't consider
Unchecked_Conversion issues, here. ]

> Put simply, you're trying to trick your Ada compiler into allowing
> programmers to use Ada syntax to write code in some other language than
> Ada, and someone who looks at the Ada code and assumes it's Ada is
> likely to be pretty darn confused.

Hmm, this definitely applies to the dopes of String objects. Is String Ada?

> Anyway, now that I've given you my tirade on why I think this is a bad
> approach, I'm going to give you an idea of how you might implement your
> bad approach.  The problem with your Next function is that if
> List_Item_Type is an unconstrained array, there will be extra data
> between the thing Item_Ptr points to and the Item_Header.  Since you've
> already admitted that this is going to be highly
> implementation-dependent, then you can probably assume that the size of
> this extra data is going to be the same always (for a given
> List_Item_Type), and then all you have to do is figure out what that
> size is the first time Next [or some other routine] is called.  Declare
> a variable in your package body:
> 
>     Dope_Offset : Storage_Offset := -1;
> 
> Fix your Allocate so that it saves the resulting Storage_Address in
> some global Global_Storage_Address in the package body before it
> returns.  Inside Next:
>
>    X : Item_Ptr;
>    ...
>    if Dope_Offset = -1 then
>      X := new List_Item_Type' (Item.all);
>      Dope_Offset := To_Address(X) - Global_Storage_Address;
>      Free(X);
>   end if;
> 
> where To_Address is from an instance of
> System.Address_To_Access_Conversions.  Now once Dope_Offset has been
> set up, you can use it as an offset and subtract it from your
> From_Item_Ptr calls.  

Unfortunately this will not work, because List_Item_Type is indefinite
limited. Then, construction - destruction of an item might be highly
undesirable, when Item is something like Device_Driver or DB_Connection.

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