Booch Components question

Booch Components question

[Simon Wright]

As you may know I've been maintaining the Ada 95 Booch Components[1] for
some years now.

I've just been reviewing the outstanding bugs; there are 7, and all but
one of them are to do with misbehaviours in Lists and date back to 2007.

The point of this query is, I'd like to close the bugs by saying "Won't
Fix" and to remove Lists from the BCs (I could put them in a
'deprecated' section, I suppose).

What!, you say, the BCs don't do lists, what sort of container facility
is that? ... and the answer is, that the BCs do support straightforward
sequences of items that you can copy, insert into, delete from, iterate
over, etc, it's just that they're called Collections.

The way Grady saw Lists, they were "polylithic" by which he meant they
implement structural sharing; what the user sees as a List is
effectively a pointer to an internal List structure maintained by the
library (an iList, let's say). Other Lists may point to the same or
different parts of the same iList; you can graft one List into another.

This is probably a hugely powerful facility, but I have to say that to
me it's also hugely dangerous, not least because it's far from obvious
how it's meant to be used (which might explain some of the bugs). For
example,

   --  It is possible, but not generally desirable, to produce
   --  multi-headed lists. In such cases, the predecessor of the item
   --  at the neck of a multi-headed list points to the most recently
   --  attached head.

I've tried to indicate this to users by including this warning:

   -------------------------------------------------------------------
   --  WARNING: If  you just want a standard  container to support  --
   --  iteration, filtering and sorting, use Collections. The List  --
   --  components  are   much  more  complex   than  you'll  need.  --
   -------------------------------------------------------------------

If anyone has objections/suggestions, now would be a good time to raise
them; thanks in advance.

[1] http://sourceforge.net/projects/booch95/index.html

Re: Booch Components question

[Randy Brukardt]

"Simon Wright" <simon@pushface.org> wrote in message 
news:m28vnlb9ry.fsf@pushface.org...
...
> If anyone has objections/suggestions, now would be a good time to raise
> them; thanks in advance.

[I don't use your components and haven't looked at them in many years, but I 
can't resist commenting. Feel free to give this comment the value you think 
it deserves... :-)]

I'm of two minds of this (maybe even more).

First, if someone needs *simple* components, they are best served by using 
the Standard ones added in Ada 2005. Even if they have to use Ada 95, they 
can use the Ada 2005 components with a few small modifications (change the 
name to Ada_Containers, and replace the anonyomous access types with named 
ones). [Ada 95 use of the containers will limit instantiations and 
call-backs to library-level, annoying sometimes but not a major hardship.] 
Using these containers means that they will be available on (most) future 
compilers and presumably will decrease the learning curve for future 
maintainers (most Ada programmers will be at least somewhat familar with 
them).

So, for alternative components to be valuable, they need facilities beyond 
the basic ones supported by Ada 2005 and even Ada 2012. This funny "list" 
container seems to be in that category. So it would seem to be a shame to 
lose it.

OTOH, the name "list" seems highly confusing. "List" seems to have gained a 
fairly standard meaning in the use of containers, and I'm not surprised that 
most people look there first. Having something that works rather differently 
with that name is asking for trouble.

So my suggestion would be to rename the container to something else to 
reduce the confusion. I realize that would add some confusion vis-a-vis your 
original source material (and a compatibility problem easily solved with 
package renames), but I expect the net effect would be much better.

OT3H :-), if people move to the Standard containers as we would hope, it 
doesn't really pay to maintain alternatives at all. So it might make sense 
to just deep-freeze the thing (don't waste time on enhancements or bugs 
unless awful), but keep it around for interested parties.

                                    Randy.

Re: Booch Components question

[Dmitry A. Kazakov]

On Mon, 14 Nov 2011 17:18:14 -0600, Randy Brukardt wrote:

> "Simon Wright" <simon@pushface.org> wrote in message 
> news:m28vnlb9ry.fsf@pushface.org...
> ...
>> If anyone has objections/suggestions, now would be a good time to raise
>> them; thanks in advance.
> 
> First, if someone needs *simple* components, they are best served by using 
> the Standard ones added in Ada 2005.

That presumes standard containers "simple." (:-))

> OTOH, the name "list" seems highly confusing. "List" seems to have gained a 
> fairly standard meaning in the use of containers, and I'm not surprised that 
> most people look there first. Having something that works rather differently 
> with that name is asking for trouble.

Hmm, what do you mean? The BC's list looks pretty much like list to me.

> OT3H :-), if people move to the Standard containers as we would hope, it 
> doesn't really pay to maintain alternatives at all.

It always does because there cannot be a universal container library, at
least in Ada in its present state:

1. The requirements are contradictory. Contradictions are preprogrammed by
language weaknesses, e.g. task safety of containers necessarily costs
performance and results in awful interfaces etc.

2. Many standard structures (falsely called containers) require
specialization in order to be used, e.g. trees, lists, graphs. The nature
of this specialization makes it easier to design such structures from
scratch.

3. There exist different attitudes towards container interfaces, I mean
usage of generics, access types, helper types, helper routines. People like
it different. I don't like list comprehension, others do like it, etc.

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

Re: Booch Components question

[Simon Wright]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> On Mon, 14 Nov 2011 17:18:14 -0600, Randy Brukardt wrote:

>> OTOH, the name "list" seems highly confusing. "List" seems to have
>> gained a fairly standard meaning in the use of containers, and I'm
>> not surprised that most people look there first. Having something
>> that works rather differently with that name is asking for trouble.
>
> Hmm, what do you mean? The BC's list looks pretty much like list to
> me.

On the surface, yes. But the 'structural sharing' is both hairy and
difficult to understand.

   --  These abstractions have been carefully constructed to eliminate
   --  all storage leaks, except in the case of intentional
   --  abuses. When a list is manipulated, all items that become
   --  unreachable are automatically reclaimed. Furthermore, this
   --  design protects against dangling references: an item is never
   --  reclaimed if there exists a reference to it.

What about unintentional abuses, I ask! or even just mistakes.

   --  Unreachable items are those that belong to a list or a sublist
   --  whose head is not designated by any alias. For example,
   --  consider the list (A B C), with the head of the list designated
   --  by L1. L1 initially points to the head of the list, at item
   --  A. Invoking the member function Tail on L1 now causes L1 to
   --  point to item B. Because A is now considered unreachable, the
   --  storage associated with item A is reclaimed; the predecessor of
   --  B is now null. Similarly, consider the list (D E F), with the
   --  head of the list designated by both L1 and L2. Both L1 and L2
   --  are aliases that initially point to the head of the list at
   --  item D. Invoking the member function Tail on L1 now causes L1
   --  to point to item E; L2 is unaffected. Suppose we now invoke the
   --  member function clear on L2. The semantics of this operation
   --  are such that only unreachable items are reclaimed. Thus, the
   --  storage associated with item D is reclaimed, because it is no
   --  longer reachable; L2 is now null, and the predecessor of E is
   --  now null. Items E and F are not reclaimed, because they are
   --  reachable through L1.

Ugh.

Re: Booch Components question

[Simon Wright]

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

> "Simon Wright" <simon@pushface.org> wrote in message 
> news:m28vnlb9ry.fsf@pushface.org...
> ...
>> If anyone has objections/suggestions, now would be a good time to raise
>> them; thanks in advance.
>
> [I don't use your components and haven't looked at them in many years,
> but I can't resist commenting. Feel free to give this comment the
> value you think it deserves... :-)]

Quite a lot, actually, Randy: thanks for the comments.

> I'm of two minds of this (maybe even more).

Me too.

> First, if someone needs *simple* components, they are best served by
> using the Standard ones added in Ada 2005. Even if they have to use
> Ada 95, they can use the Ada 2005 components with a few small
> modifications (change the name to Ada_Containers, and replace the
> anonyomous access types with named ones). [Ada 95 use of the
> containers will limit instantiations and call-backs to library-level,
> annoying sometimes but not a major hardship.]  Using these containers
> means that they will be available on (most) future compilers and
> presumably will decrease the learning curve for future maintainers
> (most Ada programmers will be at least somewhat familar with them).

Now that would be an interesting little project! Rather similar to
[1]. But I think there wouldn't be that many customers; surely anyone
starting a new project would just go for the standard Containers.

I think the only BC that I've used that doesn't have an equivalent in
the Standard is the Bag.

> So, for alternative components to be valuable, they need facilities
> beyond the basic ones supported by Ada 2005 and even Ada 2012. This
> funny "list" container seems to be in that category. So it would seem
> to be a shame to lose it.

I think I'll move it to a new 'deprecated' section. But the real trouble
with it is that it has quite serious bugs which I don't propose to fix.

> OTOH, the name "list" seems highly confusing. "List" seems to have
> gained a fairly standard meaning in the use of containers, and I'm not
> surprised that most people look there first. Having something that
> works rather differently with that name is asking for trouble.

Well, I think it's rather a sort of LISP-y list, where the List
variables in your program are rather like cursors, with the added
feature that if there are no more cursors pointing to a part of the
list, making it unreachable, it gets reclaimed.

> OT3H :-), if people move to the Standard containers as we would hope,
> it doesn't really pay to maintain alternatives at all. So it might
> make sense to just deep-freeze the thing (don't waste time on
> enhancements or bugs unless awful), but keep it around for interested
> parties.

That would be "the gripping hand" :-)

[1] https://sourceforge.net/apps/mediawiki/gnat-math-extn/

Re: Booch Components question

[Dmitry A. Kazakov]

On Tue, 15 Nov 2011 09:23:42 +0000, Simon Wright wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>> On Mon, 14 Nov 2011 17:18:14 -0600, Randy Brukardt wrote:
> 
>>> OTOH, the name "list" seems highly confusing. "List" seems to have
>>> gained a fairly standard meaning in the use of containers, and I'm
>>> not surprised that most people look there first. Having something
>>> that works rather differently with that name is asking for trouble.
>>
>> Hmm, what do you mean? The BC's list looks pretty much like list to
>> me.
> 
> On the surface, yes. But the 'structural sharing' is both hairy and
> difficult to understand.
> 
>    --  These abstractions have been carefully constructed to eliminate
>    --  all storage leaks, except in the case of intentional
>    --  abuses. When a list is manipulated, all items that become
>    --  unreachable are automatically reclaimed. Furthermore, this
>    --  design protects against dangling references: an item is never
>    --  reclaimed if there exists a reference to it.

Any list implementation must deploy some memory collection schema. BC uses
this one, so what?

I understand that the argument might be to provide unchecked lists instead
and leave memory collection to the user. But then the merits of including
such lists into the standard become questionable at least.

It is also clear that some users would need different schemas, e.g. arena.

Al this only means that there cannot be any "standard" list component,
because list, memory collection schema, task safety cannot be properly
decoupled.

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

Re: Booch Components question

[Simon Wright]

Simon Wright <simon@pushface.org> writes:

> I think the only BC that I've used that doesn't have an equivalent in
> the Standard is the Bag.

Actually, Queues and Ordered (Priority) Queues too (before Ada2012).

Re: Booch Components question

[Jeffrey Carter]

On 11/15/2011 04:19 AM, Simon Wright wrote:
> Simon Wright<simon@pushface.org>  writes:
>
>> I think the only BC that I've used that doesn't have an equivalent in
>> the Standard is the Bag.
>
> Actually, Queues and Ordered (Priority) Queues too (before Ada2012).

FWIW, we had a problem with GNAT Pro's Ada.Containers.Doubly_Linked_Lists that 
went away when we replaced it with equivalent use of 
PragmARC.List_Unbounded_Unprotected. AdaCore was unable to find a problem with 
our use of the pkg nor with the pkg itself, so it remains a mystery. I was 
unable to see a problem in the pkg either. The list size was about 50,000 items. 
We haven't had a problem with the set or map containers.

-- 
Jeff Carter
"I feel as though somebody stepped on my tongue
with muddy feet."
Never Give a Sucker an Even Break
112