Re: MI ammunition : linked lists

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

Frank J. Lhota wrote:

> Even where MI is available, I would not implement linked lists this way.
> Do we really want the type of a node vary depending on its position on the
> list? Do we want to convert the type of end nodes when a new node is
> added, or when an end node is removed?

YES!

There are two opposite variants of list design. One of them, most people
seems keeping in mind, is to have a list element and then to add object
specific things:

type List_Element is ...;
type My_Object_In_A_List is new List_Element with private;

This sort of design faces many problems. What if My_Object_... has to be in
many lists simultaneously? No way. Then to the problem you and others
mention. It exists because an inheritance by extension from List_Element
fixes the representation of My_Object_... This is inherently bad. You can
argue that to have different representations for root, middle and end nodes
is wrong, and flatten them to be of same type, as all here propose. Let
accept it for a minute. How about another challenge. What if we have
different list representation? What if there is Double_Linked_List_Element,
Array_List_Element, Persistent_List_Element, Remote_List_Element and
My_Object could be put in either of them? By inheriting form a specific
element type, we produce different object types, depending on the element
representation. And if you move an object from one list to another it still
has to mutate! - This has nothing to do with MI! -

An alternative design could be objects independent from list elements. A
"list element" could act as a smart pointer to My_Object_...'Class. If you
do this, then mutating a list element would cause no problem, because it
would not affect the object itself. It is just like to get another pointer
to it. Because List_Elements are small (up to two fields), it would be very
efficient [assuming that List_Elements could be by-value]. In this case MI
would offer a type-safe representation for list elements. It is a clear
advantage. The problem with this approach is that:

1. user-defined access types are presently not supported, which makes
implementation of smart pointers (by controlled types) very difficult and
inefficient;

2. access types and user-defined by-value types cannot be tagged;

3. initialization / finalization is allowed for controlled types only;

4. there is no MI, after all.

I think that to fix 1-3 [and arguably 4] would drastically improve Ada, at
least much more than introdicing += or saturated arithmetics.

-- 
Regards,
Dmitry A. Kazakov
www.dmitry-kazakov.de