Re: A novel design of linked lists

["Adam Beneschan" <adam@irvine.com>]

Dmitry A. Kazakov wrote:

> > 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.

Apparently we are.  I don't see why it wouldn't be OK to declare
Item_Ptr as some sort of private type, and have users of the package
write Deref(P) instead of P.all when they want to get the pointed-to
value---or, if you want to be able to put it on the left side of an
assignment, include a function that returns a general-access to your
list type so that they could say something like The_Item(P).all :=
something.  You seem to think this is awful, and I don't see anything
wrong with it, so yes, 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.

OK, you're right about that---my mistake.

> > 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?

I'm not sure what you mean here.  When you declare an access to a
string, in Ada you can use that access to get at the string value---and
that includes not just the contents of each character, but the 'First
and 'Last attributes of the string, which are an important property of
the value.  I'm sure that's what you mean by "dope", but to me "dope"
is an implementation detail, not an Ada concept.  But if I define a
record type that doesn't have "next" or "previous" fields, then I don't
expect "next" and "previous" to be part of the value that is accessed
when I declare an access to that record type---or when you declare it
in your generic.  This is just how I think.  There's apparently a
philosophical chasm here, though.

                           -- Adam