List Strawman JC01

List Strawman JC01

[Jeffrey Carter]

Here's an attempt at providing an unbounded list specification that
adheres to the current consensus as I understand it. It also provides
some alternative naming conventions for consideration.

-- 
Jeff Carter
"You empty-headed animal-food-trough wiper."
Monty Python & the Holy Grail

-- Proposed standard unbounded list ADT adhering to the
-- consensus reached so far

with Ada.Finalization;
generic -- List_Strawman_JC01
   type Element is private;
package List_Strawman_JC01 is -- Real name TBD
   pragma Preelaborate;

   type List_Handle is private; -- Initial value: Empty
   -- [Keep the name List for parameters]
   
   type Location is private; -- A position within a list;
                             -- Degree of safety TBD
                             -- Initial value: invalid
   -- [Keep the shorter name Position for parameters]
                             
   procedure Clear (List : in out List_Handle);
   -- Makes List Empty.
   --
   -- Time: O(N)
   --
   -- Postcondition: Is_Empty (List)
                             
   -- [Apparently unneeded List_Handle parameters are supplied
   -- to some operations in case they're needed for safety.]
   
   function Valid (Position : Location; List : List_Handle)
   return Boolean;
   -- Returns True if Position is a valid Location in List;
   -- returns False otherwise.
   --
   -- Time: O(1)
   
   -- Functions to obtain Locations from a List_Handle:
   
   function First (List : List_Handle) return Location;
   function Last  (List : List_Handle) return Location;
   -- These return the Location that designates the first or
   -- last Element stored in List, respectively.
   -- They return an invalid Location if List is empty.
   --
   -- Time: O(1)

   -- Functions to obtain Locations from other Locations:
   
   function Next     (Position : Location; List : List_Handle)
   return Location;
   function Previous (Position : Location; List : List_Handle)
   return Location;
   -- These return the following or preceding Location in List
   -- relative to Position.
   -- Next (Last (List) ) returns an invalid Location.
   -- Previous (First (List) ) returns an invalid Location.
   -- When applied to an invalid Location, these return an
   -- invalid location.
   
   Storage_Exhausted : exception;
   
   procedure Insert (Into    : in out List_Handle;
                     Item    : in     Element;
                     Before  : in     Location;
                     Position:    out Location);
   -- Inserts Item into Into before the Element at Before.
   -- Position becomes a valid Location in Into that
   -- designates the position at which Item is stored.
   -- If Before is invalid, Inserts Item as the first
   -- Element in Into.
   --
   -- Raises Storage_Exhausted if memory cannot be allocated
   -- to store Item in Into
   --
   -- Time: O(1)
   --
   -- Postcondition: not Is_Empty (Into)
   
   procedure Append (Into     : in out List_Handle;
                     Item     : in     Element;
                     After    : in     Location;
                     Position :    out Location);
   -- Similar to Insert, except Item is placed after the
   -- Element at After.
   -- If After is invalid, Item becomes the last Element
   -- in Into.
   --
   -- Raises Storage_Exhausted if memory cannot be allocated
   -- to store Item in Into
   --
   -- Time: O(1)
   --
   -- Postcondition: not Is_Empty (Into)
   
   Invalid_Location : exception;
   
   function Get (From : List_Handle; Position : Location)
   return Element;
   -- Returns the Element stored in From at Position.
   -- Raises Invalid_Position if Position is invalid.
   --
   -- Time: O(1)
   --
   -- Precondition: Valid (Position, From)     raises Invalid_Position
   
   procedure Delete (From     : in out List_Handle;
                     Position : in out Location);
   -- Deletes the Element stored at Position in From.
   -- Raises Invalid_Position if Position is invalid.
   --
   -- Time: O(1)
   --
   -- Precondition: Valid (Position, From)     raises Invalid_Position
   
   procedure Update (List     : in List_Handle;
                     Item     : in Element;
                     Position : in Location);
   -- Modifies the Element stored at Position in List
   -- to be Item.
   -- Raises Invalid_Position if Position is invalid.
   --
   -- Time: O(1)
   --
   -- Precondition: Valid (Position, From)     raises Invalid_Position
   --
   -- Postcondition: Get (List, Position) = Item
   
   function Is_Empty (List : List_Handle) return Boolean;
   -- Returns True if List is empty; False otherwise
   --
   -- Time: O(1)
   
   function Length (List : List_Handle) return Natural;
   -- Returns the number of Elements stored in List
   --
   -- Time: O(1) or O(N), depending on implementation
   
   generic -- Iterate
      with procedure Action (Item     : in out Element;
                             Position : in     Location;
                             Quit     :    out Boolean);
   procedure Iterate (Over : in List_Handle);
   -- Applies Action to each Element in Over, and its Location,
   -- in turn.
   -- Returns immediately if Quit is set to True (any remaining
   -- Elements in Over are not processed).
   --
   -- Time: O(N)
   
   generic -- Sort
      with function "<" (Left : Element; Right : Element)
      return Boolean;
   procedure Sort (List : in out List_Handle);
   -- Sorts List into ascending order as defined by "<"
   --
   -- Time : O(N log N)
   
   -- Any other operations considered necessary
private -- List_Strawman_JC01
   -- Dummy private part
   
   type List_Handle is new Ada.Finalization.Controlled
   with null record;
   
   procedure Adjust   (Object : in out List_Handle);
   procedure Finalize (Object : in out List_Handle);
   
   type Location is new Boolean;
end List_Strawman_JC01;

Re: List Strawman JC01

[Ted Dennison]

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.

>   type Location is private; -- A position within a list;
>                             -- Degree of safety TBD
>                             -- Initial value: invalid
>   -- [Keep the shorter name Position for parameters]

I have no concerns with this either way. If people prefer this scheme to the
newer "Iterator", I'd have no objections to using it.

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

>   -- Postcondition: Is_Empty (List)

This information should also be there, when there are important postconditions.
However, I prefer using English sentences to document this rather than some kind
of formal jargon. The difference in typing isn't even all that large between
"Postcondition:" and "Upon completion ". :-)

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

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

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

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?

Hmmm....perhaps the best way to solve that issue would be to provide a direction
type (non-generic) paramter to Sort as well.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Jeffrey Carter]

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

Re: List Strawman JC01

[Jeffrey Carter]

Jeffrey Carter wrote:
> 
> 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.

This, of course, is completely wrong. Now that my brain has rebooted,

with function "=" ...

should be in the generic formal part of the package, and "=" should not
be generic.

-- 
Jeff Carter
"Hello! Smelly English K...niggets."
Monty Python & the Holy Grail

Re: List Strawman JC01

[Ted Dennison]

In article <3C0EB851.77E7172A@boeing.com>, Jeffrey Carter says...
>
>Ted Dennison wrote:
>> be better to put this information in a matrix in the parent pacakge so that
>Except we're talking about one package for unbounded lists. In the case
>of this strawman, there's no parent package.

Not true. Since the name is "Containers.Lists.Unbounded", there are actually
*two* parent packages. I'm compiling the strawman before I post it, so those
packages do exist. Its just that there isn't anything in them to look at yet, so
I haven't bothered to post them. :-)

How about I add a 1-row "matrix" to the top of the package for now, with a note
that it will get moved to the parent when there are more rows?

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

That may be an issue, but it doesn't have to be done that way. We could decide
to still keep a pointer to the list in the iterator, which would allow the same
iterface as the current Unbounded strawman. But that's a discussion for another
time.

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

By "predefined" I take it you mean "declared in the standard Ada libarary
somewhere". Considering that the ultimate goal of this facility is to be part of
the standard Ada library, I don't think your principle applies here. :-)

Personally I don't really subscribe to that principle anyway. You should
certianly change the exception if the one raised isn't at the appropriate level
of abstraction for the user. This will, in practice, amount to the same
principle as yours. For instance, I wouldn't allow Ada.IO_Exceptions.Name_Error
to be propagated out of a log file facility. I'd change it to something like
Logfile.Unavailable or Logfile.Installation_Error, because those better describe
the condition causing the problem. Also, the fact that Ada's IO facilities are
used (rather than system calls or something) is an implementation detail that
the user doesn't care about. By this same principle you clearly wouldn't want to
allow Contraint_Error due to in internal calculation out of your routine either.
But this is quite different. Dynamic allocation is clearly going on here, and
Ada.Storage_Error perfectly describes the problem (as evidenced by the fact that
your name for it is hardly different at all).

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

In the context of a boolean expression, yes everyone knows. In the context of
the internals of a sort routine, its completely undefined. Is the "Left"
parameter the "Front" side or the "Back" side? Does a "True" result mean its out
of order or in order? You can supply answers to these questions I'm sure, but
the answers will be fairly arbitrary. They are certianly not self-evident.

>Is the array
>
>(1, 2, 3, 4)
>
>in ascending order? The answer is obvious to most people, because an
>array is a sequence.

No, its obvious to most people because the array is indexed by a discrete type,
upon which the "<" operator is defined. Thus the convention that ascending order
is the order in which items whose indexes return True for ">" will also have
values return true for ">" can be applied.

We have no such relationship for our doubly-linked list. "<" is not defined on
iterators. "Next" requires a direction parameter to disambiguate. The only
ordering a doubly-linked list has is the one the user puts upon it. I could look
at the list left to right, right to left, top to bottom, bottom to top, and no
one can say my view is wrong. I can iterate from front to back or back to front
and it won't make any real difference.

The only directional terminology we have at all is "Front" and "Back". For
anything directional to make sense at all, it *must* be cast in those terms. "<"
is not cast in those terms.

>the First element, the Next element, the Next element, ... , the Last
..
>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

You are probably thinking of a singly-linked list. That makes a bit of sense for
a singly-linked list because there is only one way you can iterate. Therefore we
know what ascending order is, because there's only one direction to traverse the
list. For a doubly-linked list, either end is equal. There may be an ordering,
but the direction of it is entirely imposed by the user. I'll ask you to go look
at the spec again. There is no "First" function, only a "Side" function, which
takes a directional parameter to disambiguate. "Next" also requires a
directional parameter to disambigute.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3C0EB851.77E7172A@boeing.com>, Jeffrey Carter says...
> >
> >Ted Dennison wrote:
> >> be better to put this information in a matrix in the parent pacakge so that
> >Except we're talking about one package for unbounded lists. In the case
> >of this strawman, there's no parent package.
> 
> Not true. Since the name is "Containers.Lists.Unbounded", there are actually
> *two* parent packages. I'm compiling the strawman before I post it, so those
> packages do exist. Its just that there isn't anything in them to look at yet, so
> I haven't bothered to post them. :-)

Since the time complexity comments were in my package, I thought we were
talking about it. Its name is "List_Strawman_JC01", it has no parent
package, and we have no other kind of list to compare it to.

> >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.
> 
> That may be an issue, but it doesn't have to be done that way. We could decide
> to still keep a pointer to the list in the iterator, which would allow the same
> iterface as the current Unbounded strawman. But that's a discussion for another
> time.

Yes, any other package should be decided later. The basic issue is that
I didn't want to constrain an implementation.

> >As a general principle, a package should not be propagating predefined
> >exceptions to its clients. Also, this helps allow differing
> 
> By "predefined" I take it you mean "declared in the standard Ada libarary
> somewhere". Considering that the ultimate goal of this facility is to be part of
> the standard Ada library, I don't think your principle applies here. :-)

This may end up being true in the final package. In the meantime, I
don't want to constrain an implementation.

> >This is much less clear than "<". Everyone knows what "<" does.
> >"Swap_Items (L, R ...) return Boolean;" is meaningless.
> 
> In the context of a boolean expression, yes everyone knows. In the context of
> the internals of a sort routine, its completely undefined. Is the "Left"
> parameter the "Front" side or the "Back" side? Does a "True" result mean its out
> of order or in order? You can supply answers to these questions I'm sure, but
> the answers will be fairly arbitrary. They are certianly not self-evident.

They don't matter. All that matters is that the generic needs to be able
to apply "<" to Elements. 
The client supplies "<", so he knows what "<" means.

Much of your discussion of "<" does not seem to be about package
List_Strawman_JC01, which is what we are discussing here. For example

> "Next" requires a direction parameter to disambiguate.
> The only directional terminology we have at all is "Front" and "Back".

These do not apply to this package.

> >the First element, the Next element, the Next element, ... , the Last
> ..
> >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
> 
> You are probably thinking of a singly-linked list. That makes a bit of sense for
> a singly-linked list because there is only one way you can iterate. Therefore we
> know what ascending order is, because there's only one direction to traverse the
> list. For a doubly-linked list, either end is equal. There may be an ordering,
> but the direction of it is entirely imposed by the user. I'll ask you to go look
> at the spec again. There is no "First" function, only a "Side" function, which
> takes a directional parameter to disambiguate. "Next" also requires a
> directional parameter to disambigute.

I'll ask you to go look at the spec (of List_Strawman_JC01) again. There
is a First function, since this is a basic property of a list. There is
no Side function. There are no directional parameters.

The ordering property applies for all lists, regardless of
implementation, just as it applies for arrays. An array is sorted in
ascending order if no element is less than a preceding element. The fact
that you can do

for I in reverse Some_Array'range loop

and traverse the elements in reverse order doesn't change this.

The fact that you can traverse an array backwards does not change the
fact that there is a specific, well defined, and well known ordering
that is "forward".

The fact that you can traverse a doubly linked list backwards does not
change the fact that there is a specific, well defined, and well known
ordering that is "forward". This is a basic property of a list known by
everyone who understands lists. Sequences, by definition, impose an
order on their elements from the first to the last. Both arrays and
lists are sequences.

Using the notation of List_Strawman_JC01 (since they use the same names
as these basic properties of lists), we can formally state that a list L
is sorted into ascending order according to "<" if

Length (L) < 2

OR

for all I, J : Location such that
  Valid (I, L) AND
  Valid (J, L) AND
  Next (I, L) = J
not (Get (L, J) < Get (L, I) )

-- 
Jeffrey Carter

Re: List Strawman JC01

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> In article <3C0EB851.77E7172A@boeing.com>, Jeffrey Carter says...
<snip>
> >This is much less clear than "<". Everyone knows what "<" does.
> >"Swap_Items (L, R ...) return Boolean;" is meaningless.
> 
> In the context of a boolean expression, yes everyone knows. In the context of
> the internals of a sort routine, its completely undefined. Is the "Left"
> parameter the "Front" side or the "Back" side? Does a "True" result mean its out
> of order or in order? You can supply answers to these questions I'm sure, but
> the answers will be fairly arbitrary. They are certianly not self-evident.

I agree with Ted; we need to be careful about making implicit
assumptions about direction. 

But this actually points to an inconsistency in Ted's current
strawman. It says:

-----------------------------------------------------------------------------
-- Sorting sub-package.
-- To sort in increasing order, use the ">" routine for the Reverse_Order
-- parameter. To sort in decreasing order, substitute your "<" routine for
-- the Reverse_Order parameter. :-)
-----------------------------------------------------------------------------
generic
   with function Reverse_Order (Left, Right : in Element) return Boolean;
package Sorting is


So it is currently using "Left" and "Right", rather than "Front" and
"Back".

Well, actually the Sort procedure doesn't say anything about
direction. It needs to say "Direction is implicitly Front to Back", or
it needs to take a Direction parameter.

Perhaps the documentation for Reverse_Order could say:

-- Function Reverse_Order is called with Left being the current
-- iteration position, and Right being the next one. Return True if
-- they should be swapped.

But that assumes Sort is done via some iteration scheme. Hmm. This is
not easy!

-- 
-- Stephe

Re: List Strawman JC01

[Mark Lundquist]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:smuP7.50028$xS6.82871@www.newsranger.com...
>
> 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.

I'm with ya on that... :-)

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

Yup!

It could be that the "save the name" notion comes from not knowing the name
resolution rules that provide the ability to qualify the type and object
names in constructs where they collide.  Or maybe someone knows how to do
it, but they just don't like to -- I guess it boils down to which way a
person thinks is uglier :-).  I prefer to name things naturally and then
qualify where necessary.

-- mark

Re: List Strawman JC01

[Mark Lundquist]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3C0EB851.77E7172A@boeing.com...
> > 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 often default to "This" or something like that, but usually I can find a
way to do better.  It seems that in your examples, you like to tailor your
parameter names to favor named association in calls, and I think that's good
practice (it's my preferred style, anyway).

> I choose to keep it available for a
> parameter name. This means the type has to have a different name.

Well it doesn't *have* to, e.g.:

    package Lists is
    .
    .
        procedure Make_Empty (List : Lists.List);

(although, that's a parameter that I would probably name "This")...

> In any
> case, we're deliberately trying out different names to see which ones
> cause the fewest people to barf.

The imagination recoils... :-)  ("Right then... next name please!")

Cheers,
Mark

Re: List Strawman JC01

[Jeffrey Carter]

Stephen Leake wrote:
> 
> I agree with Ted; we need to be careful about making implicit
> assumptions about direction.

Order is a basic property of sequences such as lists. I much prefer
making clients sort into descending order than allowing them to sort
into ascending order backwards, or however one says what such a
component would allow. It would allow 4 ways to obtain 2 results; the
added complexity does not seem to buy anything.

-- 
Jeffrey Carter

Re: List Strawman JC01

[Nick Roberts]

Again, I crave forgiveness, but I want to take to study this proposal, and
it may be a couple of days before I respond.

--
Best wishes,
Nick Roberts

Re: List Strawman JC01

[Ted Dennison]

In article <3C0FAF78.6F006DF7@boeing.com>, Jeffrey Carter says...
>
>Since the time complexity comments were in my package, I thought we were
>talking about it. Its name is "List_Strawman_JC01", it has no parent
>package, and we have no other kind of list to compare it to.

The whole goal here is to progressively modify the strawman to a point where
there can be enough of a consensus to move forward on it. To that end, I thought
you were presenting your ideas in package form, rather than just arguing them
verbally. If there a consensus around any of those ideas, I would then put them
in the strawman. Remember that the strawman is not *my* baby, its *ours*. There
is certianly stuff in there that I would do completely differently if I were
writing the package by myself.

I hope we are not involved in a process where everyone feels like they are going
to go out and make their own package and convince people to use that package
instead. That's not drawing people together, its splintering them apart. If that
starts happening, clearly this whole process is doomed.

Perhaps I am just overreacting, and you are only trying to say that you think
the strawman doesn't need to be in a package hierarchy?

>Much of your discussion of "<" does not seem to be about package
>List_Strawman_JC01, which is what we are discussing here. For example
>
>> "Next" requires a direction parameter to disambiguate.
>> The only directional terminology we have at all is "Front" and "Back".
>
>These do not apply to this package.

Ahhh. So what you are saying is that I need to take more of a holistic approach
on the naming issue. That's a good point. 

So really the lynchpin in your argument here is that we change our terminology
from talking about "Front" and "Back" to "First" and "Last". This way we
arbitrarily assign a direction to what is otherwise a directionless data
structure, and then terms that rely on the notion of progressing suddenly make
sense.

I don't think I'd be in favor of that, because that lack of direction is really
an integral part of a (doubly-linked) list, and I don't see directionality
gaining us a great deal of anything for the loss of flexability. But of course
if I turn out to be in the minority on this, I'll so change the strawman.

>I'll ask you to go look at the spec (of List_Strawman_JC01) again. There
>is a First function, since this is a basic property of a list. There is

No its not. Its a basic property of a *singly* linked list. For a doubly-linked
list, there is no logical "first" element, and working from either end is
equivalent.

>The ordering property applies for all lists, regardless of
>implementation, just as it applies for arrays. An array is sorted in
>ascending order if no element is less than a preceding element. The fact
>that you can do
(examples using other data structures deleted)
You can't use examples of *other* data structures to make your point, because
they aren't doubly-linked lists. This reflexive property is what makes a
doubly-linked list different from arrays and singly-linked lists.

OK. Lets try a thought experiment here. Picture in your mind's eye an array
rotating slowing in space. You don't have any markers on it; its just a string
of values. How do you know which is the "first" element? That's easy right? You
just find the side with the lowest index.

Now lets try the same thought experiment with a singly linked list. You've got a
string of cells linked with directional arrows rotating in space with
directional arrows going between them. How do you know which is the "first"
element? Again, this is easy. Its the element that only has an arrow going out
of it, and no arrow going into it.

Now lets do the same thing with a doubly-linked list. We have a string of cells
with bidirectional arrows between them rotating in space. Now how do you find
which element is the "first" one? 

The answer of course is that you *can't*. What we have here is a truly
direction-neutral structure. We could always go "eeny-meeny-miny-mo" and pick
one of course. But just because we did that doesn't suddenly make a directional
bias inherent in the data structure. Its something the user imposes, and its
there only in as much as the user believes in it and adheres to it.

I'd like to hear from one of the instructors in the audience about this. After
all, you are the ones who have to teach students data structures using this
thing.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Ted Dennison]

In article <3C0FF4F2.77B88A8F@boeing.com>, Jeffrey Carter says...
>
>Order is a basic property of sequences such as lists. I much prefer

Just stating this every post isn't going to make it so. You have to at least
attempt to say *why* you think this is true. I certainly don't see it.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Ted Dennison]

In article <nLPP7.4018$Yy.271026@rwcrnsc53>, Mark Lundquist says...
>        procedure Make_Empty (List : Lists.List);
>
>(although, that's a parameter that I would probably name "This")...

That's not *too* bad. After all, what you really want to say is that this is the
thing that is being made empty. Here I'd be apt to use something like "Target"
or "Subject" (or in a wierd mood, "Victim"). Those look better on the inside
than *this*. Yes, the outside code is more important, but someone has to
maintain the stuff on the inside of the routine too.

>> case, we're deliberately trying out different names to see which ones
>> cause the fewest people to barf.
>
>The imagination recoils... :-)  ("Right then... next name please!")

But it'd make a smashing Monty Python skit. :-)

Sort of a companion piece for the "Ministry of Silly Walks" skit...

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Darren New]

> >Order is a basic property of sequences such as lists. I much prefer
> 
> Just stating this every post isn't going to make it so. You have to at least
> attempt to say *why* you think this is true. I certainly don't see it.

It's what distinguishes a list from a bag. If you want a collection with
multiple copies of values but no order, it's called a "bag", in
generally-accepted computer-science-speak.  (As opposed to a "set",
which is a "bag" where every value appears at most once.)

Now, if what you mean is that some *specific* order (such as
"alphabetical") is not a basic property, then I'd agree. That seems to
be what you're saying, given that you're following up on sort routines.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List Strawman JC01

[Ted Dennison]

In article <un10ww4g1.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>But this actually points to an inconsistency in Ted's current
>strawman. It says:
>   with function Reverse_Order (Left, Right : in Element) return Boolean;
>So it is currently using "Left" and "Right", rather than "Front" and
>"Back".
>
>Well, actually the Sort procedure doesn't say anything about
>direction. It needs to say "Direction is implicitly Front to Back", or
>it needs to take a Direction parameter.

Right on both counts. I noticed the second issue a couple of days ago, but
missed the first.

For the Sort procedure, I was thinking along the lines of actually providing a
direction as a generic parameter. My initial thought was to make it a parameter
to the procedure. But then we'd probably have to make it a parameter to the
other two routines too. If we did that, there's always the possiblity someone
will muck themselves up by sorting in one order and inserting or merging in
another.

There is the stance that this is unneeded, since picking a direction and making
the user reverse the logic on their predicate is all that is required to allow
for sorting in either direction. But this does make things more explicit, and I
think I've already gone over why I don't think there's a Right direction to
pick. :-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> In article <3C0FAF78.6F006DF7@boeing.com>, Jeffrey Carter says...
> <snip>
> >> "Next" requires a direction parameter to disambiguate.
> >> The only directional terminology we have at all is "Front" and "Back".
> >
> >These do not apply to this package.
> 
> Ahhh. So what you are saying is that I need to take more of a holistic approach
> on the naming issue. That's a good point. 
> 
> So really the lynchpin in your argument here is that we change our terminology
> from talking about "Front" and "Back" to "First" and "Last". This way we
> arbitrarily assign a direction to what is otherwise a directionless data
> structure, and then terms that rely on the notion of progressing suddenly make
> sense.

I don't think "Front" and "Back" are significantly more
"directionless" than "First" and "Last". "A" and "B" would be more
directionless, although even those have an alphabetical order.

I'd go with "First" and "Last", to be consistent with general Ada
usage. An array is just as directionless as a list, and we are all
used to First, Last, and "reverse" for array iteration.

> I don't think I'd be in favor of that, because that lack of
> direction is really an integral part of a (doubly-linked) list, and
> I don't see directionality gaining us a great deal of anything for
> the loss of flexability. But of course if I turn out to be in the
> minority on this, I'll so change the strawman.
> 
> >I'll ask you to go look at the spec (of List_Strawman_JC01) again. There
> >is a First function, since this is a basic property of a list. There is
> 
> No its not. Its a basic property of a *singly* linked list. For a doubly-linked
> list, there is no logical "first" element, and working from either end is
> equivalent.

Again, I don't see "Front" as significantly different from "First"
here. Both return a well-defined item from one end of a list.
Both imply a cardinal order. And going thru a list from "Last" to
"First" _is_ equivalent to going thru it from "First" to "Last", just
as it is for Ada arrays.

> >The ordering property applies for all lists, regardless of
> >implementation, just as it applies for arrays. An array is sorted
> >in ascending order if no element is less than a preceding element.
> >The fact that you can do > (examples using other data structures
> >deleted) > You can't use examples of *other* data structures to
> >make your point, because > they aren't doubly-linked lists. This
> >reflexive property is what makes a > doubly-linked list different
> >from arrays and singly-linked lists.
> 
> OK. Lets try a thought experiment here. Picture in your mind's eye an array
> rotating slowing in space. You don't have any markers on it; its just a string
> of values. How do you know which is the "first" element? That's easy right? You
> just find the side with the lowest index.

Ok.

> Now lets try the same thought experiment with a singly linked list.
> You've got a string of cells linked with directional arrows rotating
> in space with directional arrows going between them. How do you know
> which is the "first" element? Again, this is easy. Its the element
> that only has an arrow going out of it, and no arrow going into it.

Ok.

> Now lets do the same thing with a doubly-linked list. We have a
> string of cells with bidirectional arrows between them rotating in
> space. Now how do you find which element is the "first" one?
> 
> The answer of course is that you *can't*. 

Ok, but neither can I find the "Front"!

> What we have here is a truly direction-neutral structure. We could
> always go "eeny-meeny-miny-mo" and pick one of course. But just
> because we did that doesn't suddenly make a directional bias
> inherent in the data structure. Its something the user imposes, and
> its there only in as much as the user believes in it and adheres to
> it.

Yes, the user imposes it. What's wrong with calling it "First"? 

I guess you are saying that using "First" implies that the analogy
with arrays is closer than it really is, and you want to make the
differences clearer. I can sympathize with that. But I think the fact
that the name of the package is "List" satisfies that criteria, and
the advantages of using "First" outweigh the harm.

If this were the last thing we had to argue about, we'd be in really
good shape :).

> I'd like to hear from one of the instructors in the audience about
> this. After all, you are the ones who have to teach students data
> structures using this thing.

That's a good idea.

-- 
-- Stephe

Doubly-linked list ordering(s) (was: List Strawman JC01)

[Ted Dennison]

In article <3C10F9CD.5476B14A@san.rr.com>, Darren New says...
>It's what distinguishes a list from a bag. If you want a collection with
>multiple copies of values but no order, it's called a "bag", in
>generally-accepted computer-science-speak.  (As opposed to a "set",
>which is a "bag" where every value appears at most once.)

Sort of. A "bag" is different in that it isn't linear. Its basicly a set w/o the
uniqueness requirement. I'm not saying that doubly-linked lists don't have any
order at all. I'm saying that they have exacly *two* of them, and they are both
equally valid.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Jeffrey Carter]

Ted Dennison wrote:
> 
> Perhaps I am just overreacting, and you are only trying to say that you think
> the strawman doesn't need to be in a package hierarchy?

Perhaps we were talking past each other here. I was discussing this
particular package as a vehicle to allow discussion of alternative names
and items that are still undecided while presenting everything we had
decided. Since the name of the package and the structure and contents of
any hierarchy containing it are still undecided, everything is/should be
presented in the package. I think the time complexity should be
associated with each operation, even if it is summarized elsewhere, in
the interests of locality.

> No its not. Its a basic property of a *singly* linked list. For a doubly-linked
> list, there is no logical "first" element, and working from either end is
> equivalent.

This quote seems to summarize the rest of the post (please correct me if
I'm oversimplifying).

Every data structures text I've seen describes the abstract concept of a
list as an ordered sequence of values with one value considered the
first value, another the next value, and so on to the last value. I
certainly haven't seen every data structures text, but I've seen a few,
and this was a general property of all lists in all of them, regardless
of implementation. Have you seen texts that say otherwise?

Generally, the concept of a list is presented something like:

A list X of length N can be considered an ordered sequence of values
x{i}:

x{1}, x{2}, x{3}, ..., x{N}

x{i} is the value at the ith position; x{1} is the value at the first
position, or first value, and x{N} is the last value.

[I use {i} to indicate what is typeset as a subscript; I chose {} to
emphasize that this is a notational inconvenience, not a programming
language.]

This is usually followed by some discussion of list operations from a
mathematical point of view:

X' = x{1}, ..., x{i-1}, y, x{i}, ..., x{N}

This is sufficiently common that we introduce an insertion function as
shorthand:

X' = ins(X,i,y), 1<=i<=N+1

i=N+1 means y is the last value of X'.

This is then followed by a discussion of using lists in programs;
programming issues, such as modifying one list rather than having lots
of lists that vary by one value; implementation issues
(bounded/unbounded; single/double); and one or more sample
implementations, often partial with the missing operations left as
exercises for the reader.

I have done this from memory because I don't have any texts available,
nor have I found any online. [However, see pp 70 and 72 of file
08Pointers.ppt available at

http://cs.calvin.edu/books/c++/ds/1e/NewPPSlides2/

(lecture slides for use with _C++: Introduction to Data Structures_ by
Larry Nyhoff)

for some evidence that such texts consider first and last elements basic
properties of lists.]

I hope this seems familiar, and would welcome comments from any
professors who teach data structures courses or authors who have written
texts. It's important that a standard list package implement basic list
concepts and properties.

Having learned that an implementation of a list is intended to be a
useful concrete version of this abstraction, and that this abstraction
includes the concepts of first, second, and last values, it seems to me
that it follows that every implementation includes these concepts.
Whether it's called First, Front, Head, or Horvald, every list has a
first element.

Imagine a sequence rotating in space, with one end labeled "First" and
the other end, "Last". How do you know which element is the first?

Of course, if what I learned about lists from multiple texts is wrong,
then so are my conclusions. In the meantime, that's my story and I'm
sticking to it.

-- 
Jeffrey Carter

Re: List Strawman JC01

[Ted Dennison]

In article <uk7vzudrz.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>I don't think "Front" and "Back" are significantly more
>"directionless" than "First" and "Last". "A" and "B" would be more
>directionless, although even those have an alphabetical order.

I thought a lot about this, and I couldn't really come up with anything more
neutral. "A" and "B" (or "A" and "Z") do imply an order (alphabetical). "First"
and "Last" obviously do too for the same reason. Even "Left" and "Right" imply
an order (reading order). That order is different for some people than it is for
others, but each individual reader will have a specific order it implies to
them.

"Front" and "Back" may have a certian implication of order, but its not very
strong. I go front to back in a book, but back to front in a line (queue for
non-americans). If my 6 year old were to ask me which comes first, "Front" or
"Back" (he often asks questions like that), I'd have to ask for context, or
declare it a nonsensical question. 

>> The answer of course is that you *can't*. 
>
>Ok, but neither can I find the "Front"!

Quite True. But you can find the ends, and we do have to arbitrarily label each
end *something*. We just have to find nice linear but direction-neutral
somethings to name them.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Ted Dennison]

In article <3C110606.A37E9D10@boeing.com>, Jeffrey Carter says...
>Perhaps we were talking past each other here. I was discussing this
>particular package as a vehicle to allow discussion of alternative names
>and items that are still undecided while presenting everything we had
>decided. Since the name of the package and the structure and contents of

Good. That's precisely what I was hoping we were doing. I guess my problem was
indeed that I was zoning in on individual things rather than considering the
naming scheme as a whole.

>Every data structures text I've seen describes the abstract concept of a
>list as an ordered sequence of values with one value considered the
>first value, another the next value, and so on to the last value. I

I'd agree with the first part, but not with the second, at least not for a
general bidirectional list like we have. 

I know some texts say "linked-list" when they mean "singly-linked-list". Also,
some authors may not be as careful about using confusing terminology like
"first" and "last" for ends like we are being. Also, sometimes people come into
reading with a preconcieved idea about things, and end up not comming away with
the precise concept that the author intended. And sometimes authors are just
plain wrong (it happens).

Anyway, I'm not sure where you got this impression. But I can assure you that I
have been "classicly trained" in Computer Science (BS and MS), have had to read
many such texts for no less than 5 different courses that covered this kind of
material, and did not come away with that impression. 

>nor have I found any online. [However, see pp 70 and 72 of file
>08Pointers.ppt available at
>
>http://cs.calvin.edu/books/c++/ds/1e/NewPPSlides2/

I did take a look at that. He does indeed use the unfortunate labels "First" and
"Last", which seem to be causing you so much trouble. This could be
carelessness, but I think he did it to show progression from his previous
singly-linked list example. Doing otherwise would have made it look too new. But
his heart is indeed in the right place, as he makes a point of referring to this
structure as "bidirectional" and "symmetricly-linked". I've never heard the
latter term before, and couldn't find anyone else using it, but it just about
sums things up perfectly.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Jeffrey Carter]

Ted Dennison wrote:
> 
> >> case, we're deliberately trying out different names to see which ones
> >> cause the fewest people to barf.
> >
> >The imagination recoils... :-)  ("Right then... next name please!")
> 
> But it'd make a smashing Monty Python skit. :-)
> 
> Sort of a companion piece for the "Ministry of Silly Walks" skit...

More like the chocolate assortment skit. Crunchy frog, ram's bladder
cup, ...

-- 
Jeffrey Carter

Re: Basic Properties of Lists

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3C110606.A37E9D10@boeing.com>, Jeffrey Carter says...
> 
> >Every data structures text I've seen describes the abstract concept of a
> >list as an ordered sequence of values with one value considered the
> >first value, another the next value, and so on to the last value. I
> 
> I'd agree with the first part, but not with the second, at least not for a
> general bidirectional list like we have.
> 
> I know some texts say "linked-list" when they mean "singly-linked-list". Also,
> some authors may not be as careful about using confusing terminology like
> "first" and "last" for ends like we are being. Also, sometimes people come into
> reading with a preconcieved idea about things, and end up not comming away with
> the precise concept that the author intended. And sometimes authors are just
> plain wrong (it happens).

This is not something that depends on an implementation; it is a
property of the abstraction.

> 
> Anyway, I'm not sure where you got this impression. But I can assure you that I
> have been "classicly trained" in Computer Science (BS and MS), have had to read
> many such texts for no less than 5 different courses that covered this kind of
> material, and did not come away with that impression.

Well, I just found a coworker's _Software Components with Ada_, and
Booch also has this as a property of the abstract concept of a list. I'm
not talking about his implementation, but his description of the
abstraction.

> 
> >nor have I found any online. [However, see pp 70 and 72 of file
> >08Pointers.ppt available at
> >
> >http://cs.calvin.edu/books/c++/ds/1e/NewPPSlides2/
> 
> I did take a look at that. He does indeed use the unfortunate labels "First" and
> "Last", which seem to be causing you so much trouble.

It appears from p 72 that the STL also uses this terminology.

They're not causing me any trouble. I thought they were causing you
trouble.

If we can't agree on the basic properties of lists we'll never get
anywhere. Perhaps we need an appeal to authority here. Who do you trust?
Feldman wrote a text on data structures in Ada, and is known to
sometimes comment on things here or in the Team-Ada list. Can we agree
to appeal to him and abide by his expert opinion?

-- 
Jeffrey Carter

Re: List Strawman JC01

[Mark Lundquist]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:KE6Q7.52969$xS6.87397@www.newsranger.com...
> In article <nLPP7.4018$Yy.271026@rwcrnsc53>, Mark Lundquist says...
> >        procedure Make_Empty (List : Lists.List);
> >
> >(although, that's a parameter that I would probably name "This")...
>
> That's not *too* bad. After all, what you really want to say is that this
is the
> thing that is being made empty.

Right.  "This" can take on a faint whiff of lameness (though not approaching
the pungency of "The_Foo"), and when it does that means I've lapsed into
defaulting to it without putting enough effort into coming up with names.  A
fair amount of the time, though, it really does work out that "This" is the
best name (following the "favor named association" approach).

> Here I'd be apt to use something like "Target"
> or "Subject" (or in a wierd mood, "Victim").

Hah, I use "Victim" too :-)... usually very locally, like in a declare
block, for something that is about to be deallocated.

> Those look better on the inside
> than *this*. Yes, the outside code is more important, but someone has to
> maintain the stuff on the inside of the routine too.
>

Good point.  If it helps, one can use a renaming declaration in the body to
give more reasonable "inside" names to the parameters.

> >The imagination recoils... :-)  ("Right then... next name please!")
>
> But it'd make a smashing Monty Python skit. :-)
>

My thought exactly :-).  Nudge nudge, wink wink, say no more, say no more...

-- mark

Re: List Strawman JC01

[Mark Lundquist]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:uV4Q7.52774$xS6.86977@www.newsranger.com...
>
> So really the lynchpin in your argument here is that we change our
terminology
> from talking about "Front" and "Back" to "First" and "Last". This way we
> arbitrarily assign a direction to what is otherwise a directionless data
> structure, and then terms that rely on the notion of progressing suddenly
make
> sense.
>
> I don't think I'd be in favor of that, because that lack of direction is
really
> an integral part of a (doubly-linked) list, and I don't see directionality
> gaining us a great deal of anything for the loss of flexability.

How does a choice of terminology result in more or less flexibility?

-- mark

Re: List Strawman JC01

[Mark Lundquist]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:rk8Q7.53164$xS6.87831@www.newsranger.com...
> In article <uk7vzudrz.fsf@gsfc.nasa.gov>, Stephen Leake says...
> >
> >I don't think "Front" and "Back" are significantly more
> >"directionless" than "First" and "Last". "A" and "B" would be more
> >directionless, although even those have an alphabetical order.
>
> I thought a lot about this, and I couldn't really come up with anything
more
> neutral. "A" and "B" (or "A" and "Z") do imply an order (alphabetical).
"First"
> and "Last" obviously do too for the same reason. Even "Left" and "Right"
imply
> an order (reading order). That order is different for some people than it
is for
> others, but each individual reader will have a specific order it implies
to
> them.
>
[snip]
> you can find the ends, and we do have to arbitrarily label each
> end *something*. We just have to find nice linear but direction-neutral
> somethings to name them.

Why don't you name it after the cartoon character CatDog, who has the heads
of a Cat and a Dog on either end?

    function Cat (List : Lists.List) return Iterator;
    function Dog (List : Lists.List) return Iterator;

    type Direction is (Catward, Dogward);

Picture a CatDog, rotating slowly in empty space.  How can you tell which
end is the Cat and which end is the Dog?  The point is, *you*can*.

:-) :-) :-)
-- mark

Re: Basic Properties of Lists

[Mark Lundquist]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1987 bytes --]


"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3C114702.98662A90@boeing.com...
>
> If we can't agree on the basic properties of lists we'll never get
> anywhere. Perhaps we need an appeal to authority here.

Look, you guys both know what a doubly-linked list is; you don't need some
double-dome to weigh in with a ruling on it!

You are having an argument about nomenclature, not about the basic
properties of anything.  You just think you are because you have befuddled
each other with bad arguments.

Jeffrey -- of course "sequence" (extrinsic ordering) is a fundamental
property of any kind of a linked list.  I don't think anyone is confusing
the data structure in question with a set, bag, heap, or any other kind of
intrinsically ordered thing.  Your point is irrelevant to the nomenclature
question.  Ted doesn't deny that a list has direction, he's saying that a
doubly-linked list has two directions, and for some reason he feels strongly
about any kind of preferential scheme that would seem to establish one end
or direction as secondary or relative (like "Normal" vs. "Bass_Ackwards"
:-).

But Ted, what's the big whoopie deal about this, anyway?  Who cares if the
names have a "directional bias", as long as the semantics are clear?  The
important thing is the relationship between the names you choose for the
extremities and the names you choose for "direction", right?  So if the
extremities are "Bow" and "Stern", then the directions had better be
"Forward" and "Aft".  That's why "Head/Tail" is kinda bad -- with a na�ve
choice for the direction names, like "Forward/Reverse", even the originator
of the naming scheme probably wouldn't be able to keep them straight :-).
But you have to start somewhere, and everybody knows it's arbitrary which
ends you call "First" and "Last".  I don't buy the argument that a
preferential naming scheme entails a loss of flexibility or that it obscures
the property of bidirectionality.

Cheers,
-- mark

Re: Basic Properties of Lists

[Chad R. Meiners]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2405 bytes --]

Why not create two different Iterator types: Standard_Iterator and
Reversed_Iterator (Or Cat_Iterator and Dog_Iterator)?
Each would have its own First, Last, Next, and Previous subroutines.
Perhaps a Flip function would be useful too.

-CRM

"Mark Lundquist" <mlundquist2@attbi.com> wrote in message
news:dcKQ7.23845$Yy.297532@rwcrnsc53...
>
> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
> news:3C114702.98662A90@boeing.com...
> >
> > If we can't agree on the basic properties of lists we'll never get
> > anywhere. Perhaps we need an appeal to authority here.
>
> Look, you guys both know what a doubly-linked list is; you don't need some
> double-dome to weigh in with a ruling on it!
>
> You are having an argument about nomenclature, not about the basic
> properties of anything.  You just think you are because you have befuddled
> each other with bad arguments.
>
> Jeffrey -- of course "sequence" (extrinsic ordering) is a fundamental
> property of any kind of a linked list.  I don't think anyone is confusing
> the data structure in question with a set, bag, heap, or any other kind of
> intrinsically ordered thing.  Your point is irrelevant to the nomenclature
> question.  Ted doesn't deny that a list has direction, he's saying that a
> doubly-linked list has two directions, and for some reason he feels
strongly
> about any kind of preferential scheme that would seem to establish one end
> or direction as secondary or relative (like "Normal" vs. "Bass_Ackwards"
> :-).
>
> But Ted, what's the big whoopie deal about this, anyway?  Who cares if the
> names have a "directional bias", as long as the semantics are clear?  The
> important thing is the relationship between the names you choose for the
> extremities and the names you choose for "direction", right?  So if the
> extremities are "Bow" and "Stern", then the directions had better be
> "Forward" and "Aft".  That's why "Head/Tail" is kinda bad -- with a na�ve
> choice for the direction names, like "Forward/Reverse", even the
originator
> of the naming scheme probably wouldn't be able to keep them straight :-).
> But you have to start somewhere, and everybody knows it's arbitrary which
> ends you call "First" and "Last".  I don't buy the argument that a
> preferential naming scheme entails a loss of flexibility or that it
obscures
> the property of bidirectionality.
>
> Cheers,
> -- mark
>
>
>
>

Re: Basic Properties of Lists

[Jeffrey Carter]

Mark Lundquist wrote:
> 
> Look, you guys both know what a doubly-linked list is; you don't need some
> double-dome to weigh in with a ruling on it!

I'm not talking about a doubly linked list; that's an implementation.
I'm talking about the abstract concept of a list. The abstraction is
completely random access and may be traversed in either direction, yet
still has a default ordering from first to last. The statement "This
list is sorted into ascending order" is meaningful for the abstraction,
without having to say in which direction.

A doubly linked implementation of a list allows reverse order traversal
with O(N) time complexity, but with the penalty of an additional O(N)
storage. A singly linked implementation of a list saves this additional
storage, but with the penalty that reverse traversal has O(N**2) time
complexity. They are both implementations of the same abstraction; they
both have a default ordering from first to last. The statement "This
list is sorted into ascending order" is meaningful for both of them,
without having to specify a direction. An implementation doesn't affect
the abstraction being implemented.

-- 
Jeff Carter
"Hello! Smelly English K...niggets."
Monty Python & the Holy Grail

Re: List Strawman JC01

[Ted Dennison]

In article <ccKQ7.23844$Yy.296947@rwcrnsc53>, Mark Lundquist says...
>
>Picture a CatDog, rotating slowly in empty space.  How can you tell which
>end is the Cat and which end is the Dog?  The point is, *you*can*.

Yup. The Dog end is the one chasing, the Cat end is the one complaining. :-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Marin David Condic]

I don't have an objection to arbitrarily tacking a name on both ends -
"Front" and "Back" are useful, but still kind of arbitrary. Why is one door
on your house a "Front" door and another the "Back" door? I use the "Back"
door of my house far more frequently than the "Front" door - so in a sense
it is more "Primary". Similarly, "First" and "Last" are kind of arbitrary,
yet still acceptable designations for ends of a doubly linked list. For that
matter, we could use "Left" and "Right" and rather arbitrarily decide that
those concepts will relate in some sense to the scanning of the list as if
it were text. The end you "Push" onto is the "Left" end and the end you
"Enqueue" onto is the "Right" end. Or arbitrarily, we could imagine the list
as vertical and use "Top" and "Bottom".

I think that the end-user of the list is going to be the one to impose some
meaning on the direction or ends of the list. If the application has some
sort of visual presentation then there may be some sense in which the ends
are going to be "Top" or "Bottom" or "Left" or "Right". Pick something and
don't worry too much that it isn't the perfect representation of the
abstract concept. I'd vote for being consistent with the nomenclature in
Ada.Strings.* just so that the end user doesn't have to keep switching
mental contexts when changing the data structures he's working with. There
might even be advantages to using the same enumeration types to avoid
needless proliferation of otherwise identical enumerals.

Or, for Cat In The Hat fans, we could name the ends "Thing 1" and "Thing 2".
:-)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:uV4Q7.52774$xS6.86977@www.newsranger.com...
>
> The answer of course is that you *can't*. What we have here is a truly
> direction-neutral structure. We could always go "eeny-meeny-miny-mo" and
pick
> one of course. But just because we did that doesn't suddenly make a
directional
> bias inherent in the data structure. Its something the user imposes, and
its
> there only in as much as the user believes in it and adheres to it.
>
> I'd like to hear from one of the instructors in the audience about this.
After
> all, you are the ones who have to teach students data structures using
this
> thing.
>

Re: Basic Properties of Lists

[Ted Dennison]

In article <dcKQ7.23845$Yy.297532@rwcrnsc53>, Mark Lundquist says...
>Look, you guys both know what a doubly-linked list is; you don't need some
>double-dome to weigh in with a ruling on it!

:-)

>But Ted, what's the big whoopie deal about this, anyway?  Who cares if the
>names have a "directional bias", as long as the semantics are clear?  The
>important thing is the relationship between the names you choose for the
>extremities and the names you choose for "direction", right?  So if the

I'm just explaining *why* I feel the way I do about the naming, that's all. You
are absolutely right that its not that big a deal.

>ends you call "First" and "Last".  I don't buy the argument that a
>preferential naming scheme entails a loss of flexibility or that it obscures
>the property of bidirectionality.

I'd agree with the first, but not the second. You might not buy the argument
that it obscures the issue fatally (I don't think I would either), but I don't
see how you can claim that it doesn't obscure it at all. 

How about we use "Head" and "Tail" for terminology? In the final analysis I
don't think they are any more biased than "Front" and "Back". Plus those terms
are traditionally associated with lists, so they might be more acceptable to
Jeff. As an added bonus, I don't think anyone is liable to complain that it
ought to be "Tailward" and "Headward" instead. :-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Marin David Condic]

O.K. How about the "Red" end of the list and the "Blue" end of the list? :-)

To stick with a more Ada flavor: use of 'First and 'Last consistency is
good - as would be imitating Ada.Strings and having "type Direction is
(Forward, Backward);" (implying a 'Front and 'Back - of sorts). I'd
personally vote for a Front and Back as this would be consistent with what I
have usually seen with double-ended lists & could be made consistent with
Ada.Strings.

Or we could see what kinds of names have been given to such things in other
libraries & be consistent with common usage if such exists. Or perhaps some
of the academics can let us know if there is a consistent usage in Data
Structures books?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:rk8Q7.53164$xS6.87831@www.newsranger.com...
>
> Quite True. But you can find the ends, and we do have to arbitrarily label
each
> end *something*. We just have to find nice linear but direction-neutral
> somethings to name them.
>

Re: List Strawman JC01

[Larry Hazel]

Marin David Condic wrote:
> 
> I don't have an objection to arbitrarily tacking a name on both ends -
> "Front" and "Back" are useful, but still kind of arbitrary. Why is one door
> on your house a "Front" door and another the "Back" door? I use the "Back"
> door of my house far more frequently than the "Front" door - so in a sense
> it is more "Primary". Similarly, "First" and "Last" are kind of arbitrary,
> yet still acceptable designations for ends of a doubly linked list. For that
> matter, we could use "Left" and "Right" and rather arbitrarily decide that
> those concepts will relate in some sense to the scanning of the list as if
> it were text. The end you "Push" onto is the "Left" end and the end you
> "Enqueue" onto is the "Right" end. Or arbitrarily, we could imagine the list
> as vertical and use "Top" and "Bottom".
> 
> I think that the end-user of the list is going to be the one to impose some
> meaning on the direction or ends of the list. If the application has some
> sort of visual presentation then there may be some sense in which the ends
> are going to be "Top" or "Bottom" or "Left" or "Right". Pick something and
> don't worry too much that it isn't the perfect representation of the
> abstract concept. I'd vote for being consistent with the nomenclature in
> Ada.Strings.* just so that the end user doesn't have to keep switching
> mental contexts when changing the data structures he's working with. There
> might even be advantages to using the same enumeration types to avoid
> needless proliferation of otherwise identical enumerals.
> 
> Or, for Cat In The Hat fans, we could name the ends "Thing 1" and "Thing 2".
> :-)
> 
> MDC
> --
> Marin David Condic
> Senior Software Engineer
> Pace Micro Technology Americas    www.pacemicro.com
> Enabling the digital revolution
> e-Mail:    marin.condic@pacemicro.com
> Web:      http://www.mcondic.com/
> 
> "Ted Dennison" <dennison@telepath.com> wrote in message
> news:uV4Q7.52774$xS6.86977@www.newsranger.com...
> >
> > The answer of course is that you *can't*. What we have here is a truly
> > direction-neutral structure. We could always go "eeny-meeny-miny-mo" and
> pick
> > one of course. But just because we did that doesn't suddenly make a
> directional
> > bias inherent in the data structure. Its something the user imposes, and
> its
> > there only in as much as the user believes in it and adheres to it.
> >
> > I'd like to hear from one of the instructors in the audience about this.
> After
> > all, you are the ones who have to teach students data structures using
> this
> > thing.
> >

Or we could use This_End and That_End :-)

If we use First, Last, Next, and Prior, we could provide a procedure to switch
the meanings.

Larry

Re: List Strawman JC01

[Ted Dennison]

In article <bcKQ7.23842$Yy.296757@rwcrnsc53>, Mark Lundquist says...
>How does a choice of terminology result in more or less flexibility?

Hmmmm. I suppose it doesn't *have* to. I'm just thinking back to all those
routines I added directional parameters to upon the realization that the list we
have is really symmetrical. But I guess the symetrical stuff could be kept in
with the asymetrical naming, if that's what people really want to have. 

I'm not really seeing a preference for JC01's terminology being expressed here
though, except by the JC01 author. Mostly what I'm seeing is along the lines of
"I don't care". The only other input I saw was roughly, "I like the neutral
terminology, but I'm not married to the current names". 

I'm sorry if you think this is time-wasting minutia. But it has already pointed
out a couple of inconsistencies in the current strawman which should be fixed.
So even if we don't adopt the JC01 terminology, the discussion has been quite
benificial. Plus the JC01 author went through all that effort writing up JC01
and posting it. We at least needed to air some kind of discussion on it.

Is there anyone else out there who would prefer to see the strawman changed to
use the JC01 terminology?

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Ted Dennison]

In article <9v2ldc$m67$1@nh.pace.co.uk>, Marin David Condic says...
>To stick with a more Ada flavor: use of 'First and 'Last consistency is
>good - as would be imitating Ada.Strings and having "type Direction is
>(Forward, Backward);" (implying a 'Front and 'Back - of sorts). I'd
>personally vote for a Front and Back as this would be consistent with what I
>have usually seen with double-ended lists & could be made consistent with
>Ada.Strings.

Well, again that would only be consistent with arrays, which have an ordering
defined. If there was a possibility of this becoming a built-in type, where
'First and 'Last might actually be made to apply, then I'd find this a
convincing argument for conveience sake. But as it is, I'd prefer to stick to a
a more neutral naming.

The current package uses "type Direction" for accessing the ends, so there is no
issue of using different names for that purpose unless you also want to quit
doing things this way.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: List Strawman JC01

[Ted Dennison]

In article <vU5R7.56192$xS6.90235@www.newsranger.com>, Ted Dennison says...
>though, except by the JC01 author. Mostly what I'm seeing is along the lines of
>"I don't care". The only other input I saw was roughly, "I like the neutral
>terminology, but I'm not married to the current names". 

OK. Add one "I'd prefer ""Last"" and ""First""" too. :-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Basic Properties of Lists

[Jeffrey Carter]

Ted Dennison wrote:
> 
> How about we use "Head" and "Tail" for terminology? In the final analysis I
> don't think they are any more biased than "Front" and "Back". Plus those terms
> are traditionally associated with lists, so they might be more acceptable to
> Jeff. As an added bonus, I don't think anyone is liable to complain that it
> ought to be "Tailward" and "Headward" instead. :-)

Or CAR and CDR, with associated CARward and CDRward directions :)

Head and Tail are OK. I'm primarily interested in being able to say
things like

the list is sorted in ascending order

without adding confusing terminology about the direction of traversal
needed to observe this property; Head -> Tail is implied. Saying the
list is sorted when traversed Forward or Frontward is unclear.

Similarly, I'd like to be able to say

the previous element from position P

without adding a direction; the previous element is closer to the Head.
Is the Forward neighbor of P closer to the Head or the Tail?

Maybe I'm just dense, but I find such terminology confusing.

-- 
Jeffrey Carter

Re: Basic Properties of Lists

[Ted Dennison]

In article <3C15337C.644622CC@boeing.com>, Jeffrey Carter says...
>
>Ted Dennison wrote:
>> 
>> How about we use "Head" and "Tail" for terminology? In the final analysis I
..
>Head and Tail are OK. I'm primarily interested in being able to say
>things like
>
>the list is sorted in ascending order
>
>without adding confusing terminology about the direction of traversal
>needed to observe this property; Head -> Tail is implied. Saying the

OK. To me, it would still be unclear. But if this terminology works for both of
us, then that's what we are shooting for. 

Does anyone have a big problem with "Head" and "Tail"?

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.