Re: List Strawman JC01

[Jeffrey Carter <jeffrey.carter@boeing.com>]

Ted Dennison wrote:
> 
> In article <3C0DB9D0.7184868A@acm.org>, Jeffrey Carter says...
> >
> >some alternative naming conventions for consideration.
> >   type List_Handle is private; -- Initial value: Empty
> >   -- [Keep the name List for parameters]
> 
> I'm not a fan of the style where one adds a meaningless word like "Type" or
> "Handle" to the end of identifiers to save name space for other uses. Types
> should be named describing the general concept of what they represent, and
> objects and parameters should be given names describing their explicit role in
> the system.

I agree. And since List is a better parameter name than Target or
whatever for many operations, I choose to keep it available for a
parameter name. This means the type has to have a different name. In any
case, we're deliberately trying out different names to see which ones
cause the fewest people to barf.

> 
> >   -- Time: O(N)
> 
> I'd agree that this needs to be documented for the routines. However, it might
> be better to put this information in a matrix in the parent pacakge so that
> users can judge the various container package's performances against each other
> when deciding which one to use.

Except we're talking about one package for unbounded lists. In the case
of this strawman, there's no parent package.

> >   -- [Apparently unneeded List_Handle parameters are supplied
> >   -- to some operations in case they're needed for safety.]
> 
> If we don't go to completely "safe" iterators, perhaps. With completely safe
> iterators, its pretty pointless (all it does is give the user another way to
> screw up the call). The current version of the Strawman uses the safe approach,
> so the List type need not be supplied after the iterator is constructed.

The degree of safety is the undecided requirement. This notation allows
implementations with different degrees of safety; when we decide on
that, we can decide what notation to adopt. If we want a bounded list
package at some point with similar semantics, we probably will need list
parameters.

> 
> >   Storage_Exhausted : exception;
> 
> Why is this considered superior to STORAGE_ERROR? Do you have plans to do
> something here other than just handle STORAGE_ERROR and raise Storage_Exhausted?

As a general principle, a package should not be propagating predefined
exceptions to its clients. Also, this helps allow differing
implementations. If Storage_Error comes out of a list instead of
Storage_Exhausted, there's an error in the implementation, and the
difference helps you find it.

> 
> >   generic -- Sort
> >      with function "<" (Left : Element; Right : Element)
> 
> I really don't like this name, as it gets quite confusing what is going on when
> "<" is not used for the actual. (In fact, without the comment, I'd have little
> clue what is going on either way). I'd rather see the function named after
> either what it wants done or what condition exists relative to general sorting
> when TRUE is returned.
> 
> >   -- Sorts List into ascending order as defined by "<"
> 
> Perfect example here. What precisely does "ascending order as defined by "<""
> mean? I *still* don't know if supplying ">" will sort in ascending or decending
> order when iterated in the direction I like to iterate, based on the routine
> name and this comment.
> 
> For a code reader its even worse, because all they will see is:
> 
> Foo_Sort is new Sort ("<" => ">");
> 
> Their reaction is liable to be roughly "WTF?" On the other hand, if they see
> 
> Foo_Sort is new Sort (Swap_Items => ">");
> 
> ..then at least its clear to the reader that the sort will consider things out
> of order when the first item is greater than the second.

This is much less clear than "<". Everyone knows what "<" does.
"Swap_Items (L, R ...) return Boolean;" is meaningless.

> 
> We still have a bit of a problem here, as "First" and "Second" (or "Left" and
> "Right") aren't very well defined in this context. Is the "Front" of the list on
> the left or the right? Does "Sort" sort towards the front or the back?

Is the array

(1, 2, 3, 4)

in ascending order? The answer is obvious to most people, because an
array is a sequence.

Order in a list (or any other sequence) is very well defined. There's
the First element, the Next element, the Next element, ... , the Last
element. A list is sorted in ascending order according to "<" if no
element is less than ("<") a preceding element.

First and Second are perfectly well defined for a list. The first
element in List is designated by First (List); the second by Next (First
(List) ), and so on.

I note that I omitted an essential function from this specification:
"=". Please assume the following was part of the package:

generic -- "="
   with function "=" (Left : Element; Right : Element) return Boolean is
<>;
function "=" (Left : List_Handle; Right : List_Handle) return Boolean;
-- Two lists are equal if they have the same Length and have equal
Elements at
-- corresponding positions.

-- 
Jeffrey Carter