List container strawman 1.1

List container strawman 1.1

[Ted Dennison]

I have a new version of the strawman up at my website at 
http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html 
. This version has the cascading style sheet too, so hopefully nearly 
everyone should be able to read it.

I tried to incorporate all of today's comments that don't require 
further discussion. If you made a comment that isn't incorporated, it 
either means that I think it need more discussion, or I forgot (sorry, 
it happens). If I missing something, please point it out.

I'm going to make one more attempt to attach it as text and not HTML. It 
may look a bit ugly due to some lines being longer than 60 characters.


with Ada.Finalization;
with Ada.Streams;

-------------------------------------------------------------------------------
-- This file contains a proposal for a standard Ada list package.
--
-- version - Strawman 1.1
-------------------------------------------------------------------------------
generic
    type Element is private;
package Containers.Lists.Unbounded is

 
-----------------------------------------------------------------------------
    -- The list type. I know the name's a bit redundant, but it doesn't 
look too
    -- bad, and any fully-named use will have to have a different name 
for the
    -- package anyway.
 
-----------------------------------------------------------------------------
    type List is private;

 
-----------------------------------------------------------------------------
    -- List construction operations. The returned list will contain 
*copies* of
    -- all the elements in the source lists, so these routines could get
    -- time-consuming. However, they should be useful for Lisp-like 
processing.
    --
    -- I'm trying out using unary plus ("+") for the "Construct" 
routine, but
    -- that's not a common idiom right now.
 
-----------------------------------------------------------------------------
    function "&" (Left, Right : Element) return List;
    function "&" (Left : Element; Right : List) return List;
    function "&" (Left : List; Right : Element) return List;
    function "&" (Left, Right : List) return List;
    function "+" (Initial_Element : Element) return List;

 
-----------------------------------------------------------------------------
    -- "push" and "pop" operations. Pops on empty lists raise No_Item.
 
-----------------------------------------------------------------------------
    No_Item : exception;

    procedure Push_Front (Target : in out List; New_Element : in 
Element);
    procedure Pop_Front  (Target : in out List; Old_Element :    out 
Element);
    procedure Push_Back  (Target : in out List; New_Element : in 
Element);
    procedure Pop_Back   (Target : in out List; Old_Element :    out 
Element);

 
-----------------------------------------------------------------------------
    -- Non-modifying query operations.
 
-----------------------------------------------------------------------------
    function Is_Empty (Subject : List) return Boolean;
    function Size     (Subject : List) return Natural;
    function Front    (Subject : List) return Element;
    function Back     (Subject : List) return Element;

 
-----------------------------------------------------------------------------
    -- Passive iterator. Operation will be applied on each element on 
the list
    -- Opertion can terminate this process early by setting Quit to True.
 
-----------------------------------------------------------------------------
    generic
       with procedure Operation (Target : in out Element; Quit : out 
Boolean);
    procedure Passive_Iterator (Target : in out List);

 
-----------------------------------------------------------------------------
    -- Iteration routines. For an empty list, First = Done_Iterating. 
Item and
    -- Remove raise No_Item if they are called with a value of 
Done_Iterating.
    -- As written, a typical iteration idiom would look like:
    --
    --    i := My_Lists.First (My_List);
    --    while i /= My_Lists.Done_Iterating loop
    --       do stuff with My_Lists.Item(i);
    --       i := My_Lists.Next (i);
    --    end loop;
    --
    -- Another alternative using "Size" would be:
    --
    --  i := My_Lists.First (My_List);
    --  for iteration_count in 1..My_Lists.Size (My_List) loop
    --    do stuff with My_Lists.Item (i);
    --    i := My_Lists.Next (i);
    --  end loop;
    --
 
-----------------------------------------------------------------------------
    type Iterator is private;
    Done_Iterating : constant Iterator;

    function First    (Subject : List)      return Iterator;
    function Last     (Subject : List)      return Iterator;
    function Next     (Location : Iterator) return Iterator;
    function Previous (Location : Iterator) return Iterator;
    function Item     (Location : Iterator) return Element;

    -- Ideally these routines would verify that Location was issued for 
the Subject
    -- list and is still valid, but that would be tough to enforce. 
Better to call
    -- such misuse a "bounded error", or somesuch.
 
-----------------------------------------------------------------------------
    -- Remove the element at the given location, and advance Location to 
the next
    -- element.
    -- If Location=Done_Iterating then No_Item will be raised.
    -- If Location=First, then Location will be set to the new First.
    -- If Location=Last, then Location will be set to Done_Iterating.
    -- otherwise, Location will be set to what Next was previously (the next
    -- element after the removal).
 
-----------------------------------------------------------------------------
    procedure Remove (Subject : in out List; Location : in out Iterator);

 
-----------------------------------------------------------------------------
    -- Insert the given element at the given location in the list (in 
front of
    -- the element that is already there). Location will continue to 
point to the
    -- same element.
    -- If Location=Done_Iterating, then the element will be put at the 
end of the
    -- list. Otherwise, the element will be placed immediately before 
the element
    -- at Location. Location will continue to reference that element.
 
-----------------------------------------------------------------------------
    procedure Insert (Subject : in out List; Location : in Iterator;
                                             New_Item : in Element);

 
-----------------------------------------------------------------------------
    -- Sorting routine.
    -- 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;
    procedure Sort (Subject : in out List);

 
-----------------------------------------------------------------------------
    -- Stream attributes.
 
-----------------------------------------------------------------------------
    procedure Stream_Read
      (Stream : access Ada.Streams.Root_Stream_Type'Class;
       Item   : out    List);

    procedure Stream_Write
      (Stream : access Ada.Streams.Root_Stream_Type'Class;
       Item   : in     List);

private
    -- Placebo entries to make the compiler happy (so I know the syntax 
above is correct)

 
-----------------------------------------------------------------------------
    -- Note that the list type is controlled. This makes this entire package
    -- unsusable anywhere but at the library level. The other option 
would be to remove
    -- the functions and make it limited.
    type List is new Ada.Finalization.Controlled with null record;

    for List'Read use Stream_Read;
    type Iterator is new Boolean;
    for List'Write use Stream_Write;

    Done_Iterating : constant Iterator := Iterator'First;

end Containers.Lists.Unbounded;

Re: List container strawman 1.1

[Larry Kilgallen]

In article <3BE301D1.4010106@telepath.com>, Ted Dennison <dennison@telepath.com> writes:
> I have a new version of the strawman up at my website at 
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html 

>     function Size     (Subject : List) return Natural;

Another possibility would be to allow declaration with a maximum
number of entries, in which case rather than returning Natural
the above would return the appropriate subtype.

Re: List container strawman 1.1

[Ted Dennison]

In article <EUahjJOdzNxZ@eisner.encompasserve.org>, Larry Kilgallen says...
>
>In article <3BE301D1.4010106@telepath.com>, Ted Dennison <dennison@telepath.com> writes:
>> I have a new version of the strawman up at my website at 
>> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html 
>
>>     function Size     (Subject : List) return Natural;
>
>Another possibility would be to allow declaration with a maximum
>number of entries, in which case rather than returning Natural
>the above would return the appropriate subtype.

Wouldn't that be more appropriate for Containers.Lists.Bounded?

---
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 container strawman 1.1

[Darren New]

Ted Dennison wrote:
>     -- Remove the element at the given location, and advance Location to
> the next
>     -- element.
>     -- If Location=Done_Iterating then No_Item will be raised.
>     -- If Location=First, then Location will be set to the new First.
>     -- If Location=Last, then Location will be set to Done_Iterating.

One problem with this is removing (say) the last three elements from a
list. Since you always assume you want to go forward, it is more
difficult to remove the last three than the first three, particularly
since "Next" and "Previous" aren't functions. 

One possibility: Removing the last element returns the new Last, unless
the list is now empty.

Another possibility: Have two iterator values, "off front" and "off
back", rather than just "done iterating". Actually, this would probably
be better as 
  Function No_Next(I : in Iterator) return Boolean;
  Function No_Previous(I : in Iterator) return Boolean;
  Function No_Item(I : in Iterator) return Boolean;

Then you could have things like "Insert_Before", "Insert_After", and
"Insert". "Insert" would take an iterator and insert the value at the
iterator, so now the iterator points to it. 

"Remove" would take an interator and return the new iterator. You could
still call "Previous" on an iterator that has "No_Next", and vica versa,
so deleting the end item isn't a problem.  You'd also have an iterator
that is No_Item(i)=True, so you would have to move it one way or the
other to find out where you are.

Adding an "Insert_Sorted" function that parallels the sort function
would allow the same structure to be used to maintain sorted lists.

Hmmm... Maybe I should write up a whole counterproposal kind of thing,
just to see how it flies?

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: List container strawman 1.1

[Larry Kilgallen]

In article <0XDE7.10576$xS6.14992@www.newsranger.com>, Ted Dennison<dennison@telepath.com> writes:
> In article <EUahjJOdzNxZ@eisner.encompasserve.org>, Larry Kilgallen says...
>>
>>In article <3BE301D1.4010106@telepath.com>, Ted Dennison <dennison@telepath.com> writes:
>>> I have a new version of the strawman up at my website at 
>>> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html 
>>
>>>     function Size     (Subject : List) return Natural;
>>
>>Another possibility would be to allow declaration with a maximum
>>number of entries, in which case rather than returning Natural
>>the above would return the appropriate subtype.
> 
> Wouldn't that be more appropriate for Containers.Lists.Bounded?

Yes.

Re: List container strawman 1.1

[Eric Merritt]

Not to rain on the discussion but I have to say that
the use of the "+" instead of Constructor is not very
intuitive. Someone suggested Make and Construct
wouldn't be bad, but I think "+" lacks readability and
could be confusing.
 
--- Ted Dennison <dennison@telepath.com> wrote:
> I have a new version of the strawman up at my
> website at 
>
http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> 
> . This version has the cascading style sheet too, so
> hopefully nearly 
> everyone should be able to read it.
> 
> I tried to incorporate all of today's comments that
> don't require 
> further discussion. If you made a comment that isn't
> incorporated, it 
> either means that I think it need more discussion,
> or I forgot (sorry, 
> it happens). If I missing something, please point it
> out.
> 
> I'm going to make one more attempt to attach it as
> text and not HTML. It 
> may look a bit ugly due to some lines being longer
> than 60 characters.
> 
> 
> with Ada.Finalization;
> with Ada.Streams;
> 
>
-------------------------------------------------------------------------------
> -- This file contains a proposal for a standard Ada
> list package.
> --
> -- version - Strawman 1.1
>
-------------------------------------------------------------------------------
> generic
>     type Element is private;
> package Containers.Lists.Unbounded is
> 
>  
>
-----------------------------------------------------------------------------
>     -- The list type. I know the name's a bit
> redundant, but it doesn't 
> look too
>     -- bad, and any fully-named use will have to
> have a different name 
> for the
>     -- package anyway.
>  
>
-----------------------------------------------------------------------------
>     type List is private;
> 
>  
>
-----------------------------------------------------------------------------
>     -- List construction operations. The returned
> list will contain 
> *copies* of
>     -- all the elements in the source lists, so
> these routines could get
>     -- time-consuming. However, they should be
> useful for Lisp-like 
> processing.
>     --
>     -- I'm trying out using unary plus ("+") for the
> "Construct" 
> routine, but
>     -- that's not a common idiom right now.
>  
>
-----------------------------------------------------------------------------
>     function "&" (Left, Right : Element) return
> List;
>     function "&" (Left : Element; Right : List)
> return List;
>     function "&" (Left : List; Right : Element)
> return List;
>     function "&" (Left, Right : List) return List;
>     function "+" (Initial_Element : Element) return
> List;
> 
>  
>
-----------------------------------------------------------------------------
>     -- "push" and "pop" operations. Pops on empty
> lists raise No_Item.
>  
>
-----------------------------------------------------------------------------
>     No_Item : exception;
> 
>     procedure Push_Front (Target : in out List;
> New_Element : in 
> Element);
>     procedure Pop_Front  (Target : in out List;
> Old_Element :    out 
> Element);
>     procedure Push_Back  (Target : in out List;
> New_Element : in 
> Element);
>     procedure Pop_Back   (Target : in out List;
> Old_Element :    out 
> Element);
> 
>  
>
-----------------------------------------------------------------------------
>     -- Non-modifying query operations.
>  
>
-----------------------------------------------------------------------------
>     function Is_Empty (Subject : List) return
> Boolean;
>     function Size     (Subject : List) return
> Natural;
>     function Front    (Subject : List) return
> Element;
>     function Back     (Subject : List) return
> Element;
> 
>  
>
-----------------------------------------------------------------------------
>     -- Passive iterator. Operation will be applied
> on each element on 
> the list
>     -- Opertion can terminate this process early by
> setting Quit to True.
>  
>
-----------------------------------------------------------------------------
>     generic
>        with procedure Operation (Target : in out
> Element; Quit : out 
> Boolean);
>     procedure Passive_Iterator (Target : in out
> List);
> 
>  
>
-----------------------------------------------------------------------------
>     -- Iteration routines. For an empty list, First
> = Done_Iterating. 
> Item and
>     -- Remove raise No_Item if they are called with
> a value of 
> Done_Iterating.
>     -- As written, a typical iteration idiom would
> look like:
>     --
>     --    i := My_Lists.First (My_List);
>     --    while i /= My_Lists.Done_Iterating loop
>     --       do stuff with My_Lists.Item(i);
>     --       i := My_Lists.Next (i);
>     --    end loop;
>     --
>     -- Another alternative using "Size" would be:
>     --
>     --  i := My_Lists.First (My_List);
>     --  for iteration_count in 1..My_Lists.Size
> (My_List) loop
>     --    do stuff with My_Lists.Item (i);
>     --    i := My_Lists.Next (i);
>     --  end loop;
>     --
>  
>
-----------------------------------------------------------------------------
>     type Iterator is private;
>     Done_Iterating : constant Iterator;
> 
>     function First    (Subject : List)      return
> Iterator;
>     function Last     (Subject : List)      return
> Iterator;
>     function Next     (Location : Iterator) return
> Iterator;
>     function Previous (Location : Iterator) return
> Iterator;
>     function Item     (Location : Iterator) return
> Element;
> 
>     -- Ideally these routines would verify that
> Location was issued for 
> the Subject
>     -- list and is still valid, but that would be
> tough to enforce. 
> Better to call
>     -- such misuse a "bounded error", or somesuch.
>  
>
-----------------------------------------------------------------------------
>     -- Remove the element at the given location, and
> advance Location to 
> the next
>     -- element.
>     -- If Location=Done_Iterating then No_Item will
> be raised.
>     -- If Location=First, then Location will be set
> to the new First.
>     -- If Location=Last, then Location will be set
> to Done_Iterating.
>     -- otherwise, Location will be set to what Next
> was previously (the next
>     -- element after the removal).
>  
>
-----------------------------------------------------------------------------
>     procedure Remove (Subject : in out List;
> Location : in out Iterator);
> 
>  
>
-----------------------------------------------------------------------------
>     -- Insert the given element at the given
> location in the list (in 
> front of
> 
=== message truncated ===


__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com

Re: List container strawman 1.1

[Larry Kilgallen]

In article <mailman.1004737572.17072.comp.lang.ada@ada.eu.org>, Eric Merritt <cyberlync@yahoo.com> writes:
> Not to rain on the discussion but I have to say that
> the use of the "+" instead of Constructor is not very
> intuitive. Someone suggested Make and Construct
> wouldn't be bad, but I think "+" lacks readability and
> could be confusing.

Yes, let's not emulate C.

Re: List container strawman 1.1

[Jeffrey Carter]

Darren New wrote:
> 
> Ted Dennison wrote:
> >     -- Remove the element at the given location, and advance Location to
> > the next
> >     -- element.
> >     -- If Location=Done_Iterating then No_Item will be raised.
> >     -- If Location=First, then Location will be set to the new First.
> >     -- If Location=Last, then Location will be set to Done_Iterating.
> 
> One problem with this is removing (say) the last three elements from a
> list. Since you always assume you want to go forward, it is more
> difficult to remove the last three than the first three, particularly
> since "Next" and "Previous" aren't functions.

While I agree with your sentiments, Next and Previous *are* functions.

-- 
Jeffrey Carter

Re: List container strawman 1.1

[Darren New]

Jeffrey Carter wrote:
> While I agree with your sentiments, Next and Previous *are* functions.

Sorry. My mistake.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: List container strawman 1.1

[Ted Dennison]

In article <3BE30DF7.3F2E6698@san.rr.com>, Darren New says...
>
>Ted Dennison wrote:
>One problem with this is removing (say) the last three elements from a
>list. Since you always assume you want to go forward, it is more
>difficult to remove the last three than the first three, particularly
>since "Next" and "Previous" aren't functions. 

The solution I would lean toward for this would be to provide another remove
(Perhaps the current one would be renamed "Delete", since it behaves like the
"Delete" key on a PC). Another possibility would be to provide a flag to
indicate where to move the iterator.

>Adding an "Insert_Sorted" function that parallels the sort function
>would allow the same structure to be used to maintain sorted lists.

Good point. 

>Hmmm... Maybe I should write up a whole counterproposal kind of thing,
>just to see how it flies?
Feel free.

---
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 container strawman 1.1

[Ted Dennison]

In article <3BE31DD5.FF96AFE0@san.rr.com>, Darren New says...
>
>I think there are some ideas that might be worthwhile there. For
>example, I don't see any good reason for procedures like Remove to
>require both the list and the iterator. I also think that it may be a

You're right. I'm used to implementing the iterator as a pointer for simplicity,
and I just put that idiom in without thinking about it. I don't see any good
reason why that can't be part of the iterator either.

---
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 container strawman 1.1

[Ted Dennison]

In article <mailman.1004737572.17072.comp.lang.ada@ada.eu.org>, Eric Merritt
says...
>
>Not to rain on the discussion but I have to say that
>the use of the "+" instead of Constructor is not very
>intuitive. Someone suggested Make and Construct
>wouldn't be bad, but I think "+" lacks readability and
>could be confusing.

That was my initial thought too. But the only response I got about it on 1.0 was
pro-unary operator. I figured if I switched to using it on this version, I'd
flush some anti folks out of the woodwork. :-)

---
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 container strawman 1.1

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3BE31DD5.FF96AFE0@san.rr.com>, Darren New says...
> >
> >I think there are some ideas that might be worthwhile there. For
> >example, I don't see any good reason for procedures like Remove to
> >require both the list and the iterator. I also think that it may be a
> 
> You're right. I'm used to implementing the iterator as a pointer for simplicity,
> and I just put that idiom in without thinking about it. I don't see any good
> reason why that can't be part of the iterator either.

A reason to include the list with the Position is so you can ensure that
the user is not by accident using a pointer to a different list than
desired, but it's more commonly done so you can adjust the list's first
or last pointer if the first or last node is deleted.

-- 
Jeff Carter
"I fart in your general direction."
Monty Python & the Holy Grail

Re: List container strawman 1.1

[Nick Roberts]

"Eric Merritt" <cyberlync@yahoo.com> wrote in message
news:mailman.1004737572.17072.comp.lang.ada@ada.eu.org...
> Not to rain on the discussion but I have to say that
> the use of the "+" instead of Constructor is not very
> intuitive. Someone suggested Make and Construct
> wouldn't be bad, but I think "+" lacks readability and
> could be confusing.

I would suggest:

   function Singleton (Item: in Element_Type) return List_Type;

since this would then make it clear that we are constructing a singleton
list.

--
Nick Roberts

Re: List container strawman 1.1

[Larry Hazel]

Eric Merritt wrote:
> 
> Not to rain on the discussion but I have to say that
> the use of the "+" instead of Constructor is not very
> intuitive. Someone suggested Make and Construct
> wouldn't be bad, but I think "+" lacks readability and
> could be confusing.
> 
To me, Create would be a better name.

   function Create return List;
   function Create (Initial_Element : Element) return List;
   function Create (Another List : List) return List;

Larry

Re: List container strawman 1.1

[Darren New]

Jeffrey Carter wrote:
> A reason to include the list with the Position is so you can ensure that
> the user is not by accident using a pointer to a different list than
> desired, but it's more commonly done so you can adjust the list's first
> or last pointer if the first or last node is deleted.

My thought was that it would be better to keep a pointer to the list in
the "iterator". That is, each iterator can only refer to one list
(except for the "off the end" iterator which I feel is a bad design
here), so why not?

You're not ensuring that the person isn't accidentally using the wrong
list. You're just making them say which list they think they're using,
and passing the right pointer but the wrong list isn't going to be
detected anyway. I.e., it's actually bad, because if you pass the right
pointer and the wrong list, and you try to delete the first record,
you'll get a different kind of failure than if you try to delete the
record in the middle. Better to always delete from the wrong list than
to sometimes delete from the wrong list, I think.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: List container strawman 1.1

[Jean-Marc Bourguet]

Ted Dennison wrote:
> 
> I have a new version of the strawman up at my website at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> . This version has the cascading style sheet too, so hopefully nearly
> everyone should be able to read it.

First, what's the semantic of assignation and of the equality test ?

[...]
>     type Iterator is private;
>     Done_Iterating : constant Iterator;
> 
>     function First    (Subject : List)      return Iterator;
>     function Last     (Subject : List)      return Iterator;
>     function Next     (Location : Iterator) return Iterator;
>     function Previous (Location : Iterator) return Iterator;
>     function Item     (Location : Iterator) return Element;
> 
>     -- Ideally these routines would verify that Location was issued for
> the Subject
>     -- list and is still valid, but that would be tough to enforce.
> Better to call
>     -- such misuse a "bounded error", or somesuch.
[...]

(I assume that the first test was meaningfull in the previous version).

It is not hard: the list can have a list of iterators and mark some invalid
when deleting an element or when going out of existance.  Then using an
invalid iterator would raise an exception (Next, Previous could be make to
work).  Having a Is_Valid function testing the validity of the iterator
could be nice.

A procedure to set the item as well as to get it could also be nice.
I wonder why you choose testing the equality with a special value to mark
the end of iteration instead of having a "done" function.  (If you
mimicked the C++ STL, there it is so so that "algorithms" works also with
normal pointers using pointer arithmetic, as in Ada we don't use pointer
arithmetic that's not an argument).  The one iteraror way has the following
advantages :
	- only one iterator to pass around,
	- easier to have "iterators" generating an infinite amount of data
	- easier to have filtering iterators.
While with the two iterators scheme, it is:
	- easier to describe ranges
Both schemas have the same expressing power but having worked with both,
I prefer the one iterator one.

-- 
Jean-Marc

Re: List container strawman 1.1

[Jeffrey Carter]

Darren New wrote:
> 
> My thought was that it would be better to keep a pointer to the list in
> the "iterator". That is, each iterator can only refer to one list
> (except for the "off the end" iterator which I feel is a bad design
> here), so why not?

Yes, the Position includes information that identifies the list, and
operations make sure it matches the list supplied. If they don't match,
the client has made an error and is notified via an exception. It is
never possible to supply the right list and the wrong position, or the
wrong list and the right position, and have an operation succeed.

Note that positions are not iterators. They do not iterate. Client code
may use them for iteration, but that does not make them iterators.

-- 
Jeff Carter
"You cheesy lot of second-hand electric donkey-bottom biters."
Monty Python & the Holy Grail

Re: List container strawman 1.1

[James Rogers]

Jeffrey Carter wrote:
> 
> Yes, the Position includes information that identifies the list, and
> operations make sure it matches the list supplied. If they don't match,
> the client has made an error and is notified via an exception. It is
> never possible to supply the right list and the wrong position, or the
> wrong list and the right position, and have an operation succeed.
> 
> Note that positions are not iterators. They do not iterate. Client code
> may use them for iteration, but that does not make them iterators.
> 

Think carefully about the implications of iterators with controlled
types. How many iterators will be allowed for each list instance?
When the list is finalized, how will you finalize all the iterators
accessing the list? Does this require the list accesses to be
implemented using a reference counting mechanism?

The rules you state above for iterators are good as they stand.
You do not state whether or not you can have multiple iterators
per list instance. If you can, then you have an interesting
complexity when dealing with insertions and deletions to/from the
list. For instance, what happens when you delete an element
through one iterator that is being accessed through another
iterator?

Is the iterator generated using a Singleton pattern? This will
allow multiple iterator "instances" to be created, but they would
always share exactly the same state. Accessing such iterators
in a tasking environment would require the iterator to be a
protected object.

Jim Rogers
Colorado Springs, Colorado USA

Re: List container strawman 1.1

[Mike Ovenden]

How about a Swap procedure, i.e. something like
	procedure Swap (List1, List2 : in out List);
as a means of allowing certain things to be written with
greater efficiency.

Ted Dennison wrote:
> 
...
> -------------------------------------------------------------------------------
> -- This file contains a proposal for a standard Ada list package.
> --
> -- version - Strawman 1.1
> -------------------------------------------------------------------------------
...

Re: List container strawman 1.1

[Eric Merritt]

> 
> I would suggest:
> 
>    function Singleton (Item: in Element_Type) return
> List_Type;
> 
> since this would then make it clear that we are
> constructing a singleton
> list.

Not to be too stupid, but this would imply that
throughout a running program there may only be one
instance of this list type. ie A list is instantiated
once and not again, any time the constructor is called
this already instantiated list is returned. Is this
the case? and if so how useful could this be?


__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com

Re: List container strawman 1.1

[Jean-Marc Bourguet]

Ted Dennison wrote:
> 
> I have a new version of the strawman up at my website at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> . This version has the cascading style sheet too, so hopefully nearly
> everyone should be able to read it.

I forgot something in my previous post, what about a way of inserting a 
list in constant time, destructing the inserted list?

-- 
Jean-Marc

Re: List container strawman 1.1

[Marin David Condic]

Just to toss in one more bit of feature-creep:

procedure Load (
    File    : in out Ada.Streams.Stream_IO.File_Type ;
    Subject : out List) ;

procedure Store (
    File    : in out Ada.Streams.Stream_IO.File_Type ;
    Subject : in List) ;


I'm presuming that the user can handle file management and keep track of
which list(s) they have put into the stream file and in what order.
(Dangerous, but so is life in general...) Under it lies some version of
'Input and 'Output to the stream file.

It might similarly have some advantage to have something like:

procedure Put (
    Subject  : in     List
    Bytes    :    out Ada.Streams.Stream_Element_Array) ;

procedure Get (
    Subject  :    out List
    Bytes    : in     Ada.Streams.Stream_Element_Array) ;

However, you can kind of roll-your-own from what you've already provided.
I'd see it as convenience and simplicity to have the above.

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:3BE301D1.4010106@telepath.com...
> I have a new version of the strawman up at my website at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> . This version has the cascading style sheet too, so hopefully nearly
> everyone should be able to read it.

Re: List container strawman 1.1

[Darren New]

Jeffrey Carter wrote:
> 
> Darren New wrote:
> >
> > My thought was that it would be better to keep a pointer to the list in
> > the "iterator". That is, each iterator can only refer to one list
> > (except for the "off the end" iterator which I feel is a bad design
> > here), so why not?
> 
> Yes, the Position includes information that identifies the list, and
> operations make sure it matches the list supplied. If they don't match,
> the client has made an error and is notified via an exception.

OK. Maybe it's because I'm not well-experienced in Ada, but passing the
same parameter twice just to make sure the programmer passes the same
parameter twice seems kind of odd to me.

> Note that positions are not iterators. They do not iterate. Client code
> may use them for iteration, but that does not make them iterators.

Yes, but they're *declared* as "Iterator". I know they're not iterators.
That's why my version calls em "Location". :-)

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: List container strawman 1.1

[Ted Dennison]

In article <3BE5AB8F.681577D0@free.fr>, Jean-Marc Bourguet says...
>First, what's the semantic of assignation and of the equality test ?

Since each element is copied into the list (rather than pointed to), then
assignment would make a new list that contains copies of all the elements in the
first list (in the same order). Equality probably should be the result of
"and"ing the equality test on all elements in both lists. However, that doesn't
seem too horribly useful to me, so perhaps "=" could get put in the private
section if people have a problem with that.

>It is not hard: the list can have a list of iterators and mark some invalid
>when deleting an element or when going out of existance.  Then using an
>invalid iterator would raise an exception (Next, Previous could be make to
>work).  Having a Is_Valid function testing the validity of the iterator
>could be nice.

That's pretty much what would have to be done. You missed the fact that the
iterators would have to be made controlled, with pointers back to the parent
List, so that they can remove themselves when they go out of scope or get
deallocated. Doing all that work for a such a minor safety gain doesn't seem to
be a big win for me. Additionally, implementing a list inside of our cannonical
list just rubs me the wrong way. Thus I'd vote against trying to make it "safe",
as long as the possible issues are clearly documented.

>A procedure to set the item as well as to get it could also be nice.

You can perform a Remove followed by an Insert, which would do roughly the same
thing. I suppose an "Assign" would save you a call, plus whatever dynamic
allocation would occur in deleting and creating an element. Since that would be
the only way to modify a list entry, perhaps it should be there.

>I wonder why you choose testing the equality with a special value to mark
>the end of iteration instead of having a "done" function.  (If you

Force of habit. I'm used to implementing these things as naked pointers. I think
the proper idiom probably should be "Done_Iterating" as a boolean function, as
you say (or perhaps "More_Elements", so the while condition is positive). Does
anyone disagree? Does anyone think they should *both* be there?

---
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 container strawman 1.1

[Ted Dennison]

In article <3BE6A43A.74812D8A@free.fr>, Jean-Marc Bourguet says...
>
>Ted Dennison wrote:
>> 
>> I have a new version of the strawman up at my website at
>> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
>> . This version has the cascading style sheet too, so hopefully nearly
>> everyone should be able to read it.
>
>I forgot something in my previous post, what about a way of inserting a 
>list in constant time, destructing the inserted list?

An entire list? It would be doable. Does it come up much?

I'm not sure what your second question is about. If you mean somehow keeping
track of which entires came from another list so that they can possibly in the
future be deleted in one operation, I don't see what use that would be.

---
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 container strawman 1.1

[Ted Dennison]

In article <9s6d45$bd2$1@nh.pace.co.uk>, Marin David Condic says...
>
>Just to toss in one more bit of feature-creep:
>
>procedure Load (
>    File    : in out Ada.Streams.Stream_IO.File_Type ;
>    Subject : out List) ;
>
>procedure Store (
>    File    : in out Ada.Streams.Stream_IO.File_Type ;
>    Subject : in List) ;

What's wrong with the Stream_Read and Stream_Write routines? You can get from
those to your version with one call to Ada.Streams.Stream_IO.Stream (File)

---
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 container strawman 1.1

[Darren New]

Ted Dennison wrote:
> the proper idiom probably should be "Done_Iterating" as a boolean function, as
> you say (or perhaps "More_Elements", so the while condition is positive). Does
> anyone disagree? Does anyone think they should *both* be there?

I don't think you should have two functions returning the same thing.
However, you have to ask whether "Done_Iterating" makes sense when the
previous thing you did wasn't an interation. I.e., it's the wrong name
because it's not talking about the state of the iterator, it's talking
about the state of the calling algorithm.

Something like "Off_End" or "Has_Item" or something like that would be
more appropriate, because it would make sense to say "Remove(...); if
Off_End(...) then ...." for example.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: List container strawman 1.1

[Marin David Condic]

Oh, just convenience and simplicity I guess. Not sure what the "correct"
idiom should be here. I regularly confuse myself in trying to re-remember
exactly how Streams are supposed to behave and hiding that under a
relatively straightforward procedure seems to free up those brain cells.
After all, the calls I outlined pretty much say what is supposed to happen:
"Get this list out of this file" or "Put this list into this file" in much
the same way one would view "Put_Line (Somefile, Somestring) ;"

I could see getting there via the Stream_Read and Stream_Write as you
outlined. It just seems to require more brain cells to get there. Probably
more flexible, so I wouldn't want to see them go away. I guess its more a
matter of taste than an engineering question.

I'm not married to the idea so if there are really strong objections, I
wouldn't be hurt if it found its way into the bit bucket. It would be
interesting to know if other folks would prefer the Load/Store I suggested
(in conjunction with the Stream_Read/Write) or just the Stream_Read/Write.

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:AjCF7.13578$xS6.18106@www.newsranger.com...
>
> What's wrong with the Stream_Read and Stream_Write routines? You can get
from
> those to your version with one call to Ada.Streams.Stream_IO.Stream (File)
>

Re: List container strawman 1.1

[Ted Dennison]

In article <3BE6F640.7488A048@san.rr.com>, Darren New says...
>
>Ted Dennison wrote:
>> the proper idiom probably should be "Done_Iterating" as a boolean function, as
>> you say (or perhaps "More_Elements", so the while condition is positive). Does
>> anyone disagree? Does anyone think they should *both* be there?
>
>I don't think you should have two functions returning the same thing.

I was talking about having both the object and the routine, not about two
routines. :-)

>Something like "Off_End" or "Has_Item" or something like that would be
>more appropriate, because it would make sense to say "Remove(...); if
>Off_End(...) then ...." for example.

I think I like "Has_Item", as it clearly states what's invalid (the "Item"
routine) and/or what exception you will get ("No_Item") if it is false. Plus it
is positive in an iterating while loop, which is no small consideration in my
book. 

---
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 container strawman 1.1

[Nick Roberts]

"Eric Merritt" <cyberlync@yahoo.com> wrote in message
news:mailman.1004964069.27693.comp.lang.ada@ada.eu.org...
> >
> > I would suggest:
> >
> >    function Singleton (Item: in Element_Type) return
> > List_Type;
> >
> > since this would then make it clear that we are
> > constructing a singleton
> > list.
>
> Not to be too stupid,

That's a risk I run all the time ;-) don't worry!

> but this would imply that
> throughout a running program there may only be one
> instance of this list type.

I don't quite understand what you're saying here ...

> ie A list is instantiated
> once and not again, any time the constructor is called
> this already instantiated list is returned. Is this
> the case? and if so how useful could this be?

... but I think the idea is that an object of type List_Type can be modified
after having been instantiated.

--
Nick Roberts

Re: List container strawman 1.1

[Darren New]

Ted Dennison wrote:
> I think I like "Has_Item", as it clearly states what's invalid (the "Item"
> routine) and/or what exception you will get ("No_Item") if it is false. Plus it
> is positive in an iterating while loop, which is no small consideration in my
> book.

Yep! I'm wondering if my proposed code made it out, since I've not seen
anyone actually comment about its features.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: List container strawman 1.1

[Nick Roberts]

But this can be done, and should be done, by declaring 'read' and 'write'
procedures for the List_Type, conforming to what RM95 13.13.2 requires, and
then using representation clauses to replace the default List_Type'Read and
List_Type'Write attributes. This way, the required behaviour becomes
implicit and automatic.

--
Nick Roberts


"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9s6d45$bd2$1@nh.pace.co.uk...
> Just to toss in one more bit of feature-creep:
>
> procedure Load (
>     File    : in out Ada.Streams.Stream_IO.File_Type ;
>     Subject : out List) ;
>
> procedure Store (
>     File    : in out Ada.Streams.Stream_IO.File_Type ;
>     Subject : in List) ;
>
>
> I'm presuming that the user can handle file management and keep track of
> which list(s) they have put into the stream file and in what order.
> (Dangerous, but so is life in general...) Under it lies some version of
> 'Input and 'Output to the stream file.
>
> It might similarly have some advantage to have something like:
>
> procedure Put (
>     Subject  : in     List
>     Bytes    :    out Ada.Streams.Stream_Element_Array) ;
>
> procedure Get (
>     Subject  :    out List
>     Bytes    : in     Ada.Streams.Stream_Element_Array) ;

Re: List container strawman 1.1

[Jeffrey Carter]

Darren New wrote:
> 
> Jeffrey Carter wrote:
> > Note that positions are not iterators. They do not iterate. Client code
> > may use them for iteration, but that does not make them iterators.
> 
> Yes, but they're *declared* as "Iterator". I know they're not iterators.
> That's why my version calls em "Location". :-)

They're declared incorrectly in a strawman version as Iterator. We don't
have to refer to them by that name; that's why I used "position". We
need to get a meaningful name accepted before this makes it past the
strawman stage.

-- 
Jeffrey Carter

Re: List container strawman 1.1

[Eric Merritt]

> 
> I don't quite understand what you're saying here ...

A singleton is a generally an object of which there is
only one instance throughout the entire application.
That means that accessed from anywhere in the program
it will return the same list, in effect it is only
instantiated once. That instance is then returned any
time a new list is called for. So any elements added
to the list are available thought the application.
Basically a Singleton is a single instance of an
object, ie there can never be more then one instance
singleton object in an application. 

> List_Type can be modified
> after having been instantiated.

Yes but that is not what i was saying ;)


__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com

Re: List container strawman 1.1

[Jean-Marc Bourguet]

Ted Dennison wrote:
> 
> In article <3BE6A43A.74812D8A@free.fr>, Jean-Marc Bourguet says...
> >
> >Ted Dennison wrote:
> >>
> >> I have a new version of the strawman up at my website at
> >> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> >> . This version has the cascading style sheet too, so hopefully nearly
> >> everyone should be able to read it.
> >
> >I forgot something in my previous post, what about a way of inserting a
> >list in constant time, destructing the inserted list?
> 
> An entire list? It would be doable. Does it come up much?
> 
> I'm not sure what your second question is about. If you mean somehow keeping
> track of which entires came from another list so that they can possibly in the
> future be deleted in one operation, I don't see what use that would be.

There is only one suggestion.  My suggestion correspond to one of the
splice
method of the C++ std::list<>.

    procedure Insert (Location : in Iterator; Inserted_List : in out
List);

with post condition: Is_Empty(Inserted_List) = True;

-- 
Jean-Marc

Re: List container strawman 1.1

[Roy Bell]

> 
> 
> with Ada.Finalization;
> with Ada.Streams;
> 

Can we defer the routines that require Ada.Streams to a child unit?

Re: List container strawman 1.1

[Darren New]

Eric Merritt wrote:
> Not to be too stupid, but this would imply that
> throughout a running program there may only be one
> instance of this list type. 

I think you're confusing a Singleton list (defined as a list having only
one element) with the Singleton design pattern (defined as a class
having only one instance).

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
     Sore feet from standing in line at airport
                 security checkpoints: Jet Leg.

Re: List container strawman 1.1

[Nick Roberts]

"Eric Merritt" <cyberlync@yahoo.com> wrote in message
news:mailman.1005002950.9554.comp.lang.ada@ada.eu.org...
> A singleton is a generally an object of which there is
> only one instance throughout the entire application.
> That means that accessed from anywhere in the program
> it will return the same list, in effect it is only
> instantiated once. That instance is then returned any
> time a new list is called for. So any elements added
> to the list are available thought the application.
> Basically a Singleton is a single instance of an
> object, ie there can never be more then one instance
> singleton object in an application.

That may be the meaning other languages, but not Ada! I intended the word
('singleton') in the mathematical sense of a set with only one element. Okay
so we're not talking about a set, but a list, but I think the meaning is
fairly obvious. In a program, code such as:

   Team(England,Jumping,Ladies) := Singleton(HRH_Princess_Anne);

would help to emphasise that a list was being constructed that comprised
only one element. It would contrast usefully, I think, with a multiple
constructor:

   Team(USA,TF_Relay_4x400m,Men) :=
      To_List((Alvin_Harrison, Antonio_Pettigrew, Calvin_Harrison,
Michael_Johnson));

Of course, one alternative is not to have a 'singleton' constructor. It's
only a convenience:

   Team(England,Jumping,Ladies) := To_List((1 => HRH_Princess_Anne));

I think I'd prefer having it, though.

--
Nick Roberts

Re: List container strawman 1.1

[Stephen Leake]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes:

> "Eric Merritt" <cyberlync@yahoo.com> wrote in message
> news:mailman.1005002950.9554.comp.lang.ada@ada.eu.org...
> > A singleton is a generally an object of which there is
> > only one instance throughout the entire application.
> > That means that accessed from anywhere in the program
> > it will return the same list, in effect it is only
> > instantiated once. That instance is then returned any
> > time a new list is called for. So any elements added
> > to the list are available thought the application.
> > Basically a Singleton is a single instance of an
> > object, ie there can never be more then one instance
> > singleton object in an application.
> 
> That may be the meaning other languages, but not Ada! 

This may be beating a dead horse, but I think there is an important
point here.

"Ada", the language, does _not_ define the term "singleton". Neither
does any other programming language that I am aware of.

So you are talking about a programming paradigm. It is hard not to
assume everyone shares your paradigm, but it is a good skill to develop.

> I intended the word ('singleton') in the mathematical sense of a set
> with only one element. Okay so we're not talking about a set, but a
> list, but I think the meaning is fairly obvious. 

Nope. Not to some of us.

Many of us have heard of the Singleton design pattern; that is what I
thought of when you used the word. After puzzling about it for a
while, I realized you must mean something else.

-- 
-- Stephe

Re: List container strawman 1.1

[Eric Merritt]

> I think you're confusing a Singleton list (defined
> as a list having only
> one element) with the Singleton design pattern
> (defined as a class
> having only one instance).

That would be it, thanks for the clarification. I
almost thought I was going a bit insane. lol


__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com

Re: List container strawman 1.1

[Eric Merritt]

news:mailman.1005002950.9554.comp.lang.ada@ada.eu.org...
> > A singleton is a generally an object of which
> there is
> > only one instance throughout the entire
> application.
> > That means that accessed from anywhere in the
> program
> > it will return the same list, in effect it is only
> > instantiated once. That instance is then returned
> any
> > time a new list is called for. So any elements
> added
> > to the list are available thought the application.
> > Basically a Singleton is a single instance of an
> > object, ie there can never be more then one
> instance
> > singleton object in an application.
> 
> That may be the meaning other languages, but not
> Ada! I intended the word
> ('singleton') in the mathematical sense of a set
> with only one element. Okay
> so we're not talking about a set, but a list, but I
> think the meaning is
> fairly obvious. In a program, code such as:
> 
>    Team(England,Jumping,Ladies) :=
> Singleton(HRH_Princess_Anne);
> 
> would help to emphasise that a list was being
> constructed that comprised
> only one element. It would contrast usefully, I
> think, with a multiple
> constructor:
> 
>    Team(USA,TF_Relay_4x400m,Men) :=
>       To_List((Alvin_Harrison, Antonio_Pettigrew,
> Calvin_Harrison,
> Michael_Johnson));
> 
> Of course, one alternative is not to have a
> 'singleton' constructor. It's
> only a convenience:
> 
>    Team(England,Jumping,Ladies) := To_List((1 =>
> HRH_Princess_Anne));

I was under the impression that we were talking about
the singleton design pattern not a Singleton list.
Actually I have never heard a single element list
refered to as a Singleton. I guess you learn something
every day. thank you.

__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com

Re: List container strawman 1.1

[Eric Merritt]

> 
> This may be beating a dead horse, but I think there
> is an important
> point here.
> 
> "Ada", the language, does _not_ define the term
> "singleton". Neither
> does any other programming language that I am aware
> of.
> 
> So you are talking about a programming paradigm. It
> is hard not to
> assume everyone shares your paradigm, but it is a
> good skill to develop.
> 


I am not talking about a programming paradigm, I am
talking about a method of design. A programming
paradigm is Object Oriented Programming, Procedural
Programming, Functional Programming etc. The design
patterns put forth by the GoF (and others) can apply
in most Object Oriented languages, especially Ada. So
these are, in fact, just design aids. 

In any case, this came about as I was confused when
someone suggested singleton as the name for a list
constructor. I thought that implied a singleton list
(in the design pattern sense) and they ment a list
with a single entry. In any case, it dosn't really
matter and seems to be cleared up.




__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com

Re: List container strawman 1.1

[Nick Roberts]

"Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
news:u1yjbers0.fsf@gsfc.nasa.gov...
> ...
> > I intended the word ('singleton') in the mathematical sense of a set
> > with only one element. Okay so we're not talking about a set, but a
> > list, but I think the meaning is fairly obvious.
>
> Nope. Not to some of us.

Hmm, well, okay. But is it a meaning you and the Ada community could add (to
that of the singleton instance), or do we seek another word?

I quite like 'Create', but doesn't it clash with the rather different
meaning in Ada.*_IO?

Maybe 'Solo'?

   Team(England,Equestrian_Jumping,Female) := Solo(HRH_Princess_Anne);

Or 'Unitary'? 'Unitary_List'? 'Singular'?

   Team(England,Equestrian_Jumping,Female) := Singular(HRH_Princess_Anne);

Hmm, I quite like that ;-)

Felicitations,

--
Nick Roberts

Re: List container strawman 1.1

[Stephen Leake]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes:

> "Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
> news:u1yjbers0.fsf@gsfc.nasa.gov...
> > ...
> > > I intended the word ('singleton') in the mathematical sense of a set
> > > with only one element. Okay so we're not talking about a set, but a
> > > list, but I think the meaning is fairly obvious.
> >
> > Nope. Not to some of us.
> 
> Hmm, well, okay. But is it a meaning you and the Ada community could add (to
> that of the singleton instance), or do we seek another word?

Part of the problem with this whole notion is that we are only
_initializing_ the list to contain one element. Nothing prevents us
from adding other elements. So it is _not_ a singleton list, even
using your definition!

> I quite like 'Create', but doesn't it clash with the rather
> different meaning in Ada.*_IO?

Hmm. Ada.Text_IO.Create (file: file_Type) _does_ initialize an
object of type File_Type, and List.Create (the_list : list)
initializes an object of type List, so they are similar in meaning.

I really wish that last function call was List.Create (List : in out
List_Type). But that's another issue :)

-- 
-- Stephe

Re: List container strawman 1.1

[Nick Roberts]

"Stephen Leake" <stephen.a.leake.1@gsfc.nasa.gov> wrote in message
news:u668mcr80.fsf@gsfc.nasa.gov...
> ...
> Part of the problem with this whole notion is that we are only
> _initializing_ the list to contain one element. Nothing prevents us
> from adding other elements. So it is _not_ a singleton list, even
> using your definition!

Oh yes it is. It's a function that returns a constant singleton (list)
object. Whether you then assign it to a list object (which can then be
extended) or do anything else to it is immaterial. (We _are_ talking about a
function aren't we?)

> > I quite like 'Create', but doesn't it clash with the rather
> > different meaning in Ada.*_IO?
>
> Hmm. Ada.Text_IO.Create (file: file_Type) _does_ initialize an
> object of type File_Type, and List.Create (the_list : list)
> initializes an object of type List, so they are similar in meaning.

True, but it might be confusing that Ada.Text_IO.Create is a procedure,
whereas the list constructor we're discussing is a function (isn't it?).

--
Best wishes,
Nick Roberts

Re: List container strawman 1.1

[Ehud Lamm]

Ted Dennison <dennison@telepath.com> wrote in message
news:PdCF7.13570$xS6.18096@www.newsranger.com...

> Force of habit. I'm used to implementing these things as naked pointers. I
think
> the proper idiom probably should be "Done_Iterating" as a boolean
function, as
> you say (or perhaps "More_Elements", so the while condition is positive).
Does
> anyone disagree? Does anyone think they should *both* be there?
>

I prefer the routine, and not the object.
I usually choose between two names More_Elements, or End_Of_List/Structure,
to mimic End_Of_File.

Ehud

Re: List container strawman 1.1

[Ehud Lamm]

Personally, I don't see why the user should care about streams. The
abstraction here is to provide a way to store and retrieve lists. Let the
package care about the implementation details.

Ehud

Re: List container strawman 1.1

[Ehud Lamm]

Roy Bell <rmbell@acm.org> wrote in message news:3BE7DA00.8020807@acm.org...
> >
> >
> > with Ada.Finalization;
> > with Ada.Streams;
> >
>
> Can we defer the routines that require Ada.Streams to a child unit?
>

I agree.
But maybe the added complexity isn't worth it?
I wouldn't see this as a show stopper.

Ehud

Re: List container strawman 1.1

[Simon Wright]

Eric Merritt <cyberlync@yahoo.com> writes:

> I was under the impression that we were talking about
> the singleton design pattern not a Singleton list.
> Actually I have never heard a single element list
> refered to as a Singleton. I guess you learn something
> every day. thank you.

I don't think anyone else has heard this either, it would be as well
to forget it straight away!

Re: List container strawman 1.1

[Roy Bell]

Ehud Lamm wrote:

> Roy Bell <rmbell@acm.org> wrote in message news:3BE7DA00.8020807@acm.org...
> 
>>>
>>>with Ada.Finalization;
>>>with Ada.Streams;
>>>
>>>
>>Can we defer the routines that require Ada.Streams to a child unit?
>>
>>
> 
> I agree.
> But maybe the added complexity isn't worth it?
> I wouldn't see this as a show stopper.
> 
> Ehud
> 
> 
> 


All of the other proposed additions/deletions are insignificant by 
comparison. I have seen 100s of Kbytes added to the size of the 
executable when IO is used.

Re: List container strawman 1.1

[Marin David Condic]

Well, there's some food value in being able to say "Lists work naturally
with streams because..." If there is some ability to get it into/out-of a
Stream_Element_Array, then the lists play nicely in the same sandbox as
streams.

But for storage and retrieval from a file, I'd prefer the mechanism to be
invisible. Somehow this list goes into the file and somehow when I ask for
it back, I get it back. In the middle and unexplained miracle occurs. If I
want to put ten lists into the same file - great. They come back properly if
I ask for them back in the right order and all is right with the world.

Provided there is some storage/retrieval mechanism and there is some ability
to have a list work nicely with streams (never know what sort of streams
someone may want to build, right?) the way any other language supplied data
type would work with streams, then I don't really care what the mechanism
is - as long as it doesn't have too many instantiations to get there. :-)

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/


"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9sdog7$e5q$1@news.huji.ac.il...
> Personally, I don't see why the user should care about streams. The
> abstraction here is to provide a way to store and retrieve lists. Let the
> package care about the implementation details.
>

Re: List container strawman 1.1

[Nick Roberts]

Hear hear.

--
Nick Roberts


"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9semhc$i1k$1@nh.pace.co.uk...
> Well, there's some food value in being able to say "Lists work naturally
> with streams because..."
> ...

Re: List container strawman 1.1

[Ted Dennison]

In article <9s74eg$12b2bq$5@ID-25716.news.dfncis.de>, Nick Roberts says...
(Talking about adding Text I/O routines for lists to the package)
>But this can be done, and should be done, by declaring 'read' and 'write'
>procedures for the List_Type, conforming to what RM95 13.13.2 requires, and
>then using representation clauses to replace the default List_Type'Read and
>List_Type'Write attributes. This way, the required behaviour becomes
>implicit and automatic.

The problem with doing that is that it must be done in the same package where
the type is declared. In this case, that's the generic list package. If this is
something compiler vendors provide, or something that gets put under "Ada.*" one
day, modifying the body may not be possible.

---
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 container strawman 1.1

[Ted Dennison]

In article <3BEACA5A.9030100@acm.org>, Roy Bell says...
>> Roy Bell <rmbell@acm.org> wrote in message news:3BE7DA00.8020807@acm.org...
>> 
>>>>
>>>>with Ada.Finalization;
>>>>with Ada.Streams;
>>>>
>>>>
>>>Can we defer the routines that require Ada.Streams to a child unit?
>
>All of the other proposed additions/deletions are insignificant by 
>comparison. I have seen 100s of Kbytes added to the size of the 
>executable when IO is used.

I don't believe there is any I/O in Ada.Streams. Perhaps you are thinking of
Ada.Streams.Stream_IO?

The problem with putting stuff in a child is that Ada rules would require it to
be a generic as well. That would lead to the situation where proper use requires
instantiating the first package, then using *it* (not the generic but the
instantiation of it) to instantiate the second package. Its not too horrible one
you figure it out. But this is exactly what Booch does that everyone is saying
is unacceptable. So I feel that we really need to avoid using child packages
unless there is a compelling reason.

---
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 container strawman 1.1

[Ehud Lamm]

Ted Dennison <dennison@telepath.com> wrote in message
news:20TG7.18929$xS6.30469@www.newsranger.com...
> The problem with putting stuff in a child is that Ada rules would require
it to
> be a generic as well. That would lead to the situation where proper use
requires
> instantiating the first package, then using *it* (not the generic but the
> instantiation of it) to instantiate the second package. Its not too
horrible one
> you figure it out. But this is exactly what Booch does that everyone is
saying
> is unacceptable. So I feel that we really need to avoid using child
packages
> unless there is a compelling reason.
>

Seems like a reasonable design decision. Like all tradeoffs, it sucks...

Ehud

Re: List container strawman 1.1

[Marin David Condic]

I'm wondering if everyone is declaring it "Unacceptable" or perhaps a little
less strongly, it is merely being viewed as "Undesirable". (That would
describe my gut feeling on it.) I'd still think that the BC's might be
usable if some conditions were met. 1) See if you can hide some of the
complexity by making a simple-case binding for the most common usages. 2)
Create a "Booch Components for Idiots" text that shows cookie-cutter
recepies for how to do the simple cases (covers up for #1 if that's not
feasable.) 3) Get some reasonable level of concensus that the BC's are an
acceptable, if not perfect, solution. (I'd agree to this - how about the
rest of the crowd?)

Or it might be possible to declare as part of the BC's++ that there will be
a couple of new packages that handle the simple cases while keeping the rest
of the BC's around for the more advanced user?

I think the biggest problem here is that we all have our own particular
desires, programming styles, knowledge-base, etc., that keeps us hoping we
can get something more to our liking. Nothing wrong with that, but the
likely outcome of insisting on it is going to be that everyone goes their
own way and we're right back here at the beginning with no common component
library.

Is it possible we might work in this direction:

1) Accept the BC's as a working hypothesis.

2) Extend the BC's to include some List and Map components that handle the
simple cases without too much pain. (Basically, something like what Ted put
out as a strawman. It either stands alone or is implemented with the BC's as
a wrapper around them.)

3) Add on to the BC's the capability of loading and storing the components
to files via some version of working nicely with Streams.

4) Come up with a document that does a little bit of basic "How To"
explaining and have this go along for the ride in some way.

5) Get some acceptance from the vendors to have this endorsed and hopefully
shipped with some compilers.

What I'm outlining above doesn't sound like it is impossible to accept nor
does it constitute some astronomical level of work. A small group of us
might be able to accomplish this before the next ice age. Would this be
acceptable to anyone?

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:20TG7.18929$xS6.30469@www.newsranger.com...
> instantiation of it) to instantiate the second package. Its not too
horrible one
> you figure it out. But this is exactly what Booch does that everyone is
saying
> is unacceptable. So I feel that we really need to avoid using child
packages
> unless there is a compelling reason.
>

Re: List container strawman 1.1

[Ehud Lamm]

Marin David Condic <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9sh49o$ohc$1@nh.pace.co.uk...
> I'm wondering if everyone is declaring it "Unacceptable" or perhaps a
little
> less strongly, it is merely being viewed as "Undesirable".

Of course. It is all a matter of striking the right balance between all the
conflicting goals.

> 1) Accept the BC's as a working hypothesis.
>

[etc. For rest of plan see original message].

But one must ask, WHY the BC? Other have their own favorites, which may be
better.
The problem is that analyzing large libraries trying to find the "best" one
to start with, and trying to remove dependencies with code  that may be best
left out, seems even less appealing than designing from scratch...

Basically, none of this is rocket science - so both these approaches can
lead to a reasonable outcome.

Ehud

Re: List container strawman 1.1

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:EXSG7.18921$xS6.30449@www.newsranger.com...
> In article <9s74eg$12b2bq$5@ID-25716.news.dfncis.de>, Nick Roberts says...
> (Talking about adding Text I/O routines for lists to the package)
> >But this can be done, and should be done, by declaring 'read' and 'write'
> >procedures for the List_Type, conforming to what RM95 13.13.2 requires,
and
> >then using representation clauses to replace the default List_Type'Read
and
> >List_Type'Write attributes. This way, the required behaviour becomes
> >implicit and automatic.
>
> The problem with doing that is that it must be done in the same package
where
> the type is declared. In this case, that's the generic list package. If
this is
> something compiler vendors provide, or something that gets put under
"Ada.*" one
> day, modifying the body may not be possible.

But why is that a problem? Provided the compiler vendor gets the
implementation (of 'Read and 'Write) right, why should anyone need to modify
it?

--
Nick Roberts

Re: List container strawman 1.1

[Ted Dennison]

Marin David Condic wrote:

> I'm wondering if everyone is declaring it "Unacceptable" or perhaps a little
> less strongly, it is merely being viewed as "Undesirable". (That would

Generally, I'd agree with you. However, at least one person did use the 
word "unaceptable" when I described the multi-level instantiation 
process a Booch user has to go through.

Re: List container strawman 1.1

[Ted Dennison]

Stephen Leake wrote:

> "Ada", the language, does _not_ define the term "singleton". Neither
> does any other programming language that I am aware of.

Common Lisp does (or at least its spec does). See 
http://www.xanalys.com/software_tools/reference/HyperSpec/Body/glo_s.html#singleton 
.

For the HTML-impaired, it reads:

singleton adj. (of a sequence) having only one element. ``(list 'hello) 
returns a singleton list.''


Since Lisp was built around List processing, I think its reasonable to 
accept their terminology in these matters. In fact, my initial name for 
this routine was simply the full spelling (de-abbreviating?) of Lisp's 
"CONS", which in the Lisp world is both the name of the list 
construction routine, and the general term people use to describe the 
creation of a list. I'm not willing to go so far as to use CONS, CAR, 
and CDR though. :-)

Perhaps in this vein, we should just do the Lisp-like thing, and create 
a null list which folks would have to "&" to their element to create a 
singleton list. :-)

Re: List container strawman 1.1

[Ted Dennison]

Stephen Leake wrote:

> Hmm. Ada.Text_IO.Create (file: file_Type) _does_ initialize an
> object of type File_Type, and List.Create (the_list : list)
> initializes an object of type List, so they are similar in meaning.

..except that Ada.Text_IO.Create creates an *empty* file, while this 
routine creates a non-empty list. It also works on a limited-private 
object which is invalid for any use until Create (or Open) is called. 
List objects would be valid (if empty) from inception.

I'm still leaning toward "Construct" or "Singleton". The hits against 
"Construct" were that it is a bit long, and that it has other meanings 
in CS outside of its older list-processing meaning. But it seems to be 
that "Singleton" has these exact problems as well. However, singleton 
does have the advantage that it is a better name for a function since it 
describes what you are getting. "Construct" would be a better name for a 
procedure, since it describes what is being done.

Re: List container strawman 1.1

[Darren New]

Ted Dennison wrote:
> in CS outside of its older list-processing meaning. But it seems to be
> that "Singleton" has these exact problems as well. However, singleton
> does have the advantage that it is a better name for a function since it
> describes what you are getting.

I'd go with "singleton". The only reason it "already has a meaning in
CS" is that the meaning is the same.  A singleton set is a set with only
one element, a singleton list is a list with only one element, and a
singleton class is a class with only one instance.

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

Re: List container strawman 1.1

[Jeffrey Carter]

Ted Dennison wrote:
> 
> Generally, I'd agree with you. However, at least one person did use the
> word "unaceptable" when I described the multi-level instantiation
> process a Booch user has to go through.

I think I used "unacceptable" to refer to the several hours of study you
said was necessary to learn to instantiate a simple data structure.
Multiple instantiations are undesirable, but multiple instantiations
that take hours to learn to use unacceptable.

-- 
Jeff Carter
"Son of a window-dresser."
Monty Python & the Holy Grail

Re: List container strawman 1.1

[Florian Weimer]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

> "Ada", the language, does _not_ define the term "singleton". Neither
> does any other programming language that I am aware of.

It's used by the Python folks for a tuple with one element.

Re: List container strawman 1.1

[Simon Wright]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:

> Personally, I don't see why the user should care about streams. The
> abstraction here is to provide a way to store and retrieve
> lists. Let the package care about the implementation details.

Wouldn't it be nice to be able to send lists over a network
connection? supporting streams allows this at extremely low cost
(well, when you get GNAT.Sockets generally available, I don't know
about AdaAockets)

Re: List container strawman 1.1

[Marin David Condic]

If for no other reason, I offer these: The BC's seem to have a certain
amount of following already and hence a possible constituency to lobby for
it and a willingness to go along with it - hence some likelyhood that we
will actually get an agreement and something will result from this. Also,
the fact that it already exists is a plus - an advantage shared by some
other component libraries as well.

I have no problem adopting something that already exists and has some
consensus that this is one of many possible "Right Answers." I also don't
have a problem if everybody agrees to build a component library from
bottom-dead-center. What I'd prefer to avoid is a never-ending discussion
about what constitutes the "Right Answer" such that we never see an end
product out of it. If supporting an existing component library (with some
modification/extension?) gets us moving along, I'd accept a less than
optimal answer.

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/


"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9shlbg$nu1$1@news.huji.ac.il...
>
> But one must ask, WHY the BC? Other have their own favorites, which may be
> better.
> The problem is that analyzing large libraries trying to find the "best"
one
> to start with, and trying to remove dependencies with code  that may be
best
> left out, seems even less appealing than designing from scratch...
>

Re: List container strawman 1.1

[Marin David Condic]

Well is it possible to either create some kind of binding or stand-alone
equivalent that hides/eliminates the need for a multi-level instantiation
for the simple cases? Or could we put together something that is a kind of
"Monkey See-Monkey Do" example set that overcomes a steep learning curve for
the simple cases?

I'd just like to see us get something adopted and an existing library has
some advantages. So far, I don't think we've got one that provides a nice,
simple answer for the nice, simple cases nor is there apparently one that
will support Streams, so I imagine we'd be looking at doing some kind of
enhancements anyway. But it would be nice to leverage something already in
existence and already having some level of following.

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:3BEC9207.5070309@telepath.com...
>
> Generally, I'd agree with you. However, at least one person did use the
> word "unaceptable" when I described the multi-level instantiation
> process a Booch user has to go through.
>

Re: List container strawman 1.1

[Simon Wright]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:

> I'm wondering if everyone is declaring it "Unacceptable" or perhaps
> a little less strongly, it is merely being viewed as
> "Undesirable". (That would describe my gut feeling on it.) I'd still
> think that the BC's might be usable if some conditions were met. 1)
> See if you can hide some of the complexity by making a simple-case
> binding for the most common usages.

It does rather go against the grain of the BCs, IMO, but I could add
this (which does everything bar closed iteration). "Collection" is
what everyone has been calling "List", BTW.  Almost all the operations
could in fact be omitted in this package, because they are inherited,
though one would have to "use" it to get at them easily and I suspect
pedagogically one would prefer to see the operations. Just treat it as
implementation inheritance.

================================================================================
--  Copyright (C) 2001 Simon Wright.
--  All Rights Reserved.
--
--      This program is free software; you can redistribute it
--      and/or modify it under the terms of the Ada Community
--      License which comes with this Library.
--
--      This program is distributed in the hope that it will be
--      useful, but WITHOUT ANY WARRANTY; without even the implied
--      warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
--      PURPOSE. See the Ada Community License for more details.
--      You should have received a copy of the Ada Community
--      License with this library, in the file named "Ada Community
--      License" or "ACL". If not, contact the author of this library
--      for a copy.
--

--  $RCSfile: bc-simple_collections.ads,v $
--  $Revision: 1.1 $
--  $Date: 2001/11/11 20:48:36 $
--  $Author: simon $

with BC.Containers.Collections.Unbounded;
with BC.Support.Standard_Storage;

generic
   type Item is private;
   with function "=" (L, R : Item) return Boolean is <>;
package BC.Simple_Collections is

   pragma Elaborate_Body;

   package Abstract_Containers is new BC.Containers (Item);
   package Abstract_Collections is new Abstract_Containers.Collections;
   package Collections is new Abstract_Collections.Unbounded
     (Storage => BC.Support.Standard_Storage.Pool);


   type Collection is new Collections.Collection with private;
   --  A collection denotes an indexed collection of items, drawn from
   --  some well-defined universe. A collection may contain duplicate
   --  items; a collection owns a copy of each item.


   -----------------------------
   --  Collection operations  --
   -----------------------------

   function Null_Collection return Collection;
   --  Return an empty Collection.

   function "=" (Left, Right : in Collection) return Boolean;

   procedure Clear (C : in out Collection);
   --  Empty the collection of all items.

   procedure Insert (C : in out Collection; Elem : Item);
   --  Add the item to the front of the collection.

   procedure Insert (C : in out Collection;
                     Elem : Item; Before : Positive);
   --  Add the item before the given index item in the collection; if
   --  before is 1, the item is added to the front of the collection.

   procedure Append (C : in out Collection; Elem : Item);
   --  Add the item at the end of the collection.

   procedure Append (C : in out Collection;
                     Elem : Item;
                     After : Positive);
   --  Add the item after the given index item in the collection.

   procedure Remove (C : in out Collection;
                     At_Index : Positive);
   --  Remove the item at the given index in the collection.

   procedure Replace (C : in out Collection;
                      At_Index : Positive; Elem : Item);
   --  Replace the item at the given index with the given item.

   function Length (C : Collection) return Natural;
   --  Return the number of items in the collection.

   function Is_Empty (C : Collection) return Boolean;
   --  Return True if and only if there are no items in the
   --  collection.

   function First (C : Collection) return Item;
   --  Return a copy of the item at the front of the collection.

   function Last (C : Collection) return Item;
   --  Return a copy of the item at the end of the collection.

   function Item_At (C : Collection;
                     At_Index : Positive) return Item;
   --  Return a copy of the item at the indicated position in the
   --  collection.

   function Location (C : Collection;
                      Elem : Item) return Natural;
   --  Return the first index at which the item is found (0 if the
   --  item desn't exist in the collection).


   -----------------
   --  Iteration  --
   -----------------

   subtype Iterator is Abstract_Containers.Iterator'Class;

   function New_Iterator
     (For_The_Collection : Collection) return Iterator;
   --  Return a reset Iterator bound to the specific Collection.

   procedure Reset (It : in out Iterator);
   --  Reset the Iterator to the beginning.

   procedure Next (It : in out Iterator);
   --  Advance the Iterator to the next Item in the Container.

   function Is_Done (It : Iterator) return Boolean;
   --  Return True if there are no more Items in the Container.

   function Current_Item (It : Iterator) return Item;
   --  Return a copy of the current Item.


private

   type Collection is new Collections.Collection with null record;

   function Null_Container return Collection;

end BC.Simple_Collections;
================================================================================

>                                     2) Create a "Booch Components
> for Idiots" text that shows cookie-cutter recepies for how to do the
> simple cases (covers up for #1 if that's not feasable.)

Has anyone had a chance to look at
http://www.pushface.org/components/bc/case-study.html yet to see if
I'm on anything like the right lines?

> Or it might be possible to declare as part of the BC's++ that there
> will be a couple of new packages that handle the simple cases while
> keeping the rest of the BC's around for the more advanced user?

My first reaction was that if anyone can get their heads round Maps
they should be able to do a couple of measly instantiations :-)

Re: List container strawman 1.1

[Simon Wright]

Jeffrey Carter <jrcarter@acm.org> writes:

> Ted Dennison wrote:
> > 
> > Generally, I'd agree with you. However, at least one person did use the
> > word "unaceptable" when I described the multi-level instantiation
> > process a Booch user has to go through.
> 
> I think I used "unacceptable" to refer to the several hours of study
> you said was necessary to learn to instantiate a simple data
> structure.  Multiple instantiations are undesirable, but multiple
> instantiations that take hours to learn to use unacceptable.

I think it only takes hours the first time (and without any help).


From the documentation:

In the example, a Car has three attributes, the Plate (the Index Mark;
my first car's was 8493KC), the Model name (it was a Vauxhall Cresta)
and the date it was Registered (some time in the mists of antiquity).

   with Ada.Calendar;
   with Ada.Strings.Bounded;
   package Cars is

      package Plate_Strings
      is new Ada.Strings.Bounded.Generic_Bounded_Length (10);
      subtype Plate_String
      is Plate_Strings.Bounded_String;

      package Model_Strings
      is new Ada.Strings.Bounded.Generic_Bounded_Length (32);
      subtype Model_String
      is Model_Strings.Bounded_String;

      type Car is record
         Plate : Plate_String;
         Model : Model_String;
         Registered : Ada.Calendar.Time;
      end record;

   end Cars;

A company's Fleet holds a number of Cars. 

The first thing to do is to instantiate the top-level abstract
Containers for Car. Note, we have to supply an equality operator ("=")
for Car; we could also just use Cars.

   with BC.Containers;
   with Cars;
   package Abstract_Car_Containers
   is new BC.Containers (Cars.Car, "=" => Cars."=");

Next, using the new Abstract_Car_Containers, instantiate the abstract
Collections:

   with Abstract_Car_Containers;
   with BC.Containers.Collections;
   package Abstract_Car_Collections
   is new Abstract_Car_Containers.Collections;

You now have to choose the representation to be used for the concrete
Collection. To start with, assume that you'll never have more than 30
Cars to deal with. This means that you can use the Bounded form.

   with Abstract_Car_Collections;
   with BC.Containers.Collections.Bounded;
   package Fleets
   is new Abstract_Car_Collections.Bounded (Maximum_Size => 30);

You now need to create your Fleet: 

   with Fleets;
   package My_Fleet is

      The_Fleet : Fleets.Collection;

   end My_Fleet;




There, not so bad eh :-)

Re: List container strawman 1.1

[Pascal Obry]

Simon Wright <simon@pushface.org> writes:

> "Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:
> 
> > Personally, I don't see why the user should care about streams. The
> > abstraction here is to provide a way to store and retrieve
> > lists. Let the package care about the implementation details.
> 
> Wouldn't it be nice to be able to send lists over a network
> connection? supporting streams allows this at extremely low cost
> (well, when you get GNAT.Sockets generally available, I don't know
> about AdaAockets)

Or across partitions when building distributed programs.

Pascal.


-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|         http://perso.wanadoo.fr/pascal.obry
--|
--| "The best way to travel is by means of imagination"

Re: List container strawman 1.1

[Ehud Lamm]

I agree. I retract my previous position.

Ehud

Re: List container strawman 1.1

[Ehud Lamm]

Simon Wright <simon@pushface.org> wrote in message
news:x7v668hrpdz.fsf@smaug.pushface.org...

> My first reaction was that if anyone can get their heads round Maps
> they should be able to do a couple of measly instantiations :-)

Someone can be an experienced programmer, or at least know about data
strcutres, and still be new to Ada.

Ehud

Re: List container strawman 1.1

[Ted Dennison]

In article <x7v3d3lrp5b.fsf@smaug.pushface.org>, Simon Wright says...
>
>Jeffrey Carter <jrcarter@acm.org> writes:
>> I think I used "unacceptable" to refer to the several hours of study
>> you said was necessary to learn to instantiate a simple data
>> structure.  Multiple instantiations are undesirable, but multiple
>> instantiations that take hours to learn to use unacceptable.
>
>I think it only takes hours the first time (and without any help).

Right. Back when I had to figure it out, there weren't really any docs. So that
really describes the process if you are just looking at the sources to try to
figure it out. I haven't looked at what docs there are now. I'm not "newbie"
enough with it any more to judge how tough it would be to figure out that way
anyway.

Since I ended up using similiar mechanisms in OpenToken, I made sure that every
version came with a rather extensive user guide with examples for using just
about every package. That approach seems to have worked fairly well, but I
haven't really got many reports from folks using the more complicated parsing
features, so I don't know.

---
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 container strawman 1.1

[Marin David Condic]

"Simon Wright" <simon@pushface.org> wrote in message
news:x7v668hrpdz.fsf@smaug.pushface.org...
>
> It does rather go against the grain of the BCs, IMO, but I could add
> this (which does everything bar closed iteration). "Collection" is
> what everyone has been calling "List", BTW.  Almost all the operations
> could in fact be omitted in this package, because they are inherited,
> though one would have to "use" it to get at them easily and I suspect
> pedagogically one would prefer to see the operations. Just treat it as
> implementation inheritance.
>
It looks like it simplifies things quite a bit. I think that the more it
looks like what Ted was proposing, the more likely it is going to be an easy
alternative for the beginner and/or simple cases. Having glanced (see below)
at the BC instantiation thing, I can see where there is an objection to it
concerning simplicity and if this can be totally hidden for a plain-vanilla
case beneath some other package spec, I think newbies to it would be helped
considerably.

My impression from what I can see is that the BC's are a kind of
"Theoretically Pure" thing - an academic distilation of all the fundamental
behaviors and functionalities needed by a variety of data structures of
different shapes. This may provide some additional power and ability to
create new abstractions, but the poor bastard who just needs to pile up a
few employee records and step through them really doesn't care about the
intellectual niceties. He just wants a list he can get to quickly and
easily. That's why I'm suggesting an add-on that creates a shield from the
abstractions in the BC's while leaving the rest of it there in case someone
wants the more complex stuff.

>
> Has anyone had a chance to look at
> http://www.pushface.org/components/bc/case-study.html yet to see if
> I'm on anything like the right lines?
>
I gave it a cursory glance. Yes, I think that is on the right track - pick a
simple case and illustrate everything you need to do to get the job done.


>
> My first reaction was that if anyone can get their heads round Maps
> they should be able to do a couple of measly instantiations :-)

What do you mean "get their heads round Maps"? If we mean the same thing by
"Maps" I don't understand what is so complex?

generic
    type Index_Type is private ;
    type Item is private ;
    with function "<" (L, R: in Index_Type) is <> ;
package Maps is
    --
    --  Various types/procedures, etc. here that let you insert, delete,
retrieve
    --  and scan over things of type Item based on Index_Type. Your garden
    --  variety ISAM file in memory...
    --
end Maps ;


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/

Re: List container strawman 1.1

[Jeffrey Carter]

Simon Wright wrote:
> 
> I think it only takes hours the first time (and without any help).

Hours the first time (and after a few months of non-use) is still
unacceptable.

-- 
Jeffrey Carter

Re: List container strawman 1.1

[Simon Wright]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:

> My impression from what I can see is that the BC's are a kind of
> "Theoretically Pure" thing - an academic distilation of all the
> fundamental behaviors and functionalities needed by a variety of
> data structures of different shapes.

Hmm, I wouldn't go as far as that :-)

There's a lot of stuff that a purist wouldn't have put in there: would
you normally expect to be able to sort a Deque? access its 5th member?
etc

Re: List container strawman 1.1

[Simon Wright]

Jeffrey Carter <jeffrey.carter@boeing.com> writes:

> Simon Wright wrote:
> > 
> > I think it only takes hours the first time (and without any help).
> 
> Hours the first time (and after a few months of non-use) is still
> unacceptable.

Good grief! I accept that! the remainder of my posting was part of my
attempt to document the process (ie, provide help) so that people
_wouldn't_ need to spend hours!

Re: List container strawman 1.1

[Stephen Leake]

Darren New <dnew@san.rr.com> writes:

> Ted Dennison wrote:
> > in CS outside of its older list-processing meaning. But it seems to be
> > that "Singleton" has these exact problems as well. However, singleton
> > does have the advantage that it is a better name for a function since it
> > describes what you are getting.
> 
> I'd go with "singleton". The only reason it "already has a meaning in
> CS" is that the meaning is the same.  A singleton set is a set with only
> one element, a singleton list is a list with only one element, and a
> singleton class is a class with only one instance.

That last one is more commonly heard these days, and is significantly
different. A true singleton class _cannot_ be expanded to have more
than one instance _by design_. The "singleton" list discussed here is
just the initial value; it can easily be expanded. 

That difference is enough to rule out "Singleton" for me.

-- 
-- Stephe

Re: List container strawman 1.1

[Stephen Leake]

Florian Weimer <fw@deneb.enyo.de> writes:

> Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:
> 
> > "Ada", the language, does _not_ define the term "singleton". Neither
> > does any other programming language that I am aware of.
> 
> It's used by the Python folks for a tuple with one element.

My goodness, there are certainly a lot of programming languages I'm
not aware of! I'll have to be more careful with this kind of statement
in the future :).

-- 
-- Stephe

Re: List container strawman 1.1

[Stephen Leake]

Simon Wright <simon@pushface.org> writes:

> It does rather go against the grain of the BCs, IMO, but I could add
> this (which does everything bar closed iteration). "Collection" is
> what everyone has been calling "List", BTW.  Almost all the operations
> could in fact be omitted in this package, because they are inherited,
> though one would have to "use" it to get at them easily and I suspect
> pedagogically one would prefer to see the operations. Just treat it as
> implementation inheritance.

Excellent. I think this puts the matter to rest!

Now I _really_ have to see if I can do this for SAL :), and we can get
back to arguing about what the correct complex container structure is,
instead of what the correct simple container structure is :).

> <code snipped>

-- 
-- Stephe

Re: List container strawman 1.1

[Darren New]

Stephen Leake wrote:
> > I'd go with "singleton". The only reason it "already has a meaning in
> > CS" is that the meaning is the same.  A singleton set is a set with only
> > one element, a singleton list is a list with only one element, and a
> > singleton class is a class with only one instance.
> 

Not that it makes much difference, but this *is* usenet afterall... ;-)

> That last one is more commonly heard these days, and is significantly
> different. 

I suspect it's more commonly heard by folks who have been programming
much longer than they've been out of high-school. :-)

> A true singleton class _cannot_ be expanded to have more
> than one instance _by design_. The "singleton" list discussed here is
> just the initial value; it can easily be expanded.

A "singleton list" can never be expanded in math, since math is
"functional" so to speak. That Ada isn't functional rules this out.

Is it possible to do the Singleton pattern in Ada? I guess a limited
type that always refered to a global, or even just a global variable
would do it. Since Ada supports procedural programming, you don't really
do "singleton" in Ada, I expect.

> That difference is enough to rule out "Singleton" for me.

But certainly, if it causes confusion, a better name should be chosen.

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

Re: List container strawman 1.1

[Ted Dennison]

In article <3BF1567C.89167E12@san.rr.com>, Darren New says...
(talking about "Singleton")
>I suspect it's more commonly heard by folks who have been programming
>much longer than they've been out of high-school. :-)

Mmmm....(takes off shoes to facilitate the counting)...

I think I'd qualify, but I had never heard "Singleton" used that way until this
thread.

>A "singleton list" can never be expanded in math, since math is
>"functional" so to speak. That Ada isn't functional rules this out.

Ada *can* be used functionally, and the current strawman certianly provides for
that. I believe someone even tried to make that point earlier. It just isn't
exclusively functional.

>Is it possible to do the Singleton pattern in Ada? I guess a limited

If I created a package with only routines ("methods"), and a single global
object declared in the body that they all operate on, wouldn't that qualify?

>But certainly, if it causes confusion, a better name should be chosen.

I'd be more apt to blame the confusion on poor choice of naming by the OO
people, and move on. But then I'm not the one confused, either. :-)

I suppose we could just create a null list and make everyone "&" to that, just
to stop the bickering. :-)

---
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 container strawman 1.1

[Marin David Condic]

I might - but that isn't saying much what with my being the sort of
anti-intellectual in the crowd. :-)

I think I was just talking about how it seems to want to distill more
generalizations and specializations than I might ever want or use. Certainly
it goes farther at abstracting things than I would if I were just slamming
together a linked list package for my own quick-and-dirty use. (I'd never
bother with iterators, for example - just create some Next/Prev/EOList
subprograms and get to work. :-)

I still don't think that would rule out the BCs from being the "Standard"
data structure package - but I'd want to see some extensions to it first.

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/


"Simon Wright" <simon@pushface.org> wrote in message
news:x7vvggfxi8i.fsf@smaug.pushface.org...
>
> Hmm, I wouldn't go as far as that :-)
>
> There's a lot of stuff that a purist wouldn't have put in there: would
> you normally expect to be able to sort a Deque? access its 5th member?
> etc

Re: List container strawman 1.1

[Ben Place]

Ted Dennison at dennison@telepath.com wrote on 11/13/01 3:36 PM:

> I suppose we could just create a null list and make everyone "&" to that, just
> to stop the bickering. :-)

Why not overload a "Create" function so that it takes either no arguments, a
single element, or a list.

This would return a null list, a list with a single element in it, or a copy
of the list passed in, respectively.

And can I vote for calling it "Create" while I'm here not lurking?

Thanks,
Ben Place

Re: List container strawman 1.1

[Nick Roberts]

There is another possibility that some people may like. My proposal includes
overloadings of the "*" function to provide replication. So instead of:

   Cuddly_Marsupials := Singleton("Koala");

one could write:

   Cuddly_Marsupials := 1*"Koala";

The problem with this replication form is that, in the case of string
elements, it could lead to ambiguities if a type from Ada.Strings.* is
visible, and in the case of integer elements it would certainly lead to
ambiguities.

I have suggested other names. How about:

   Cuddly_Marsupials := Only("Koala");

?

--
Best wishes,
Nick Roberts



"Ben Place" <benjaminplace@NOSPAM.sprintmail.com> wrote in message
news:B8171B48.5D00%benjaminplace@NOSPAM.sprintmail.com...
> Ted Dennison at dennison@telepath.com wrote on 11/13/01 3:36 PM:
>
> > I suppose we could just create a null list and make everyone "&" to
that, just
> > to stop the bickering. :-)
>
> Why not overload a "Create" function so that it takes either no arguments,
a
> single element, or a list.
>
> This would return a null list, a list with a single element in it, or a
copy
> of the list passed in, respectively.
>
> And can I vote for calling it "Create" while I'm here not lurking?
>
> Thanks,
> Ben Place
>

Re: List container strawman 1.1

[Jeffrey Carter]

Nick Roberts wrote:
> 
> I have suggested other names. How about:
> 
>    Cuddly_Marsupials := Only("Koala");

I don't see that a special operation is required or desirable. What's
wrong with

Insert (Item => "Koala", Into => Cuddly_Marsupials, Position => First
(Cuddly_Marsupials) );

as the first operation on Cuddly_Marsupials?

Besides, Tasmanian Devils are pretty cuddly, too :)

-- 
Jeffrey Carter

Re: List container strawman 1.1

[Ted Dennison]

In article <3BF2976C.8C545E25@boeing.com>, Jeffrey Carter says...
>
>I don't see that a special operation is required or desirable. What's
>wrong with
>
>Insert (Item => "Koala", Into => Cuddly_Marsupials, Position => First
>(Cuddly_Marsupials) );

The problem with that is that it won't work in an initialization.

>Besides, Tasmanian Devils are pretty cuddly, too :)
The little ones on my 2-year-old's bedslippers certianly are. :-)

---
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 container strawman 1.1

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3BF2976C.8C545E25@boeing.com>, Jeffrey Carter says...
> >
> >I don't see that a special operation is required or desirable. What's
> >wrong with
> >
> >Insert (Item => "Koala", Into => Cuddly_Marsupials, Position => First
> >(Cuddly_Marsupials) );
> 
> The problem with that is that it won't work in an initialization.

Since a list will initialize itself to empty, I don't see that as a
problem. We may be willing to allow people to use lists in a functional
manner, with all the implicit deallocation and allocation for deep
copies that implies for a dynamic structure, but we certainly don't want
to encourage it.

-- 
Jeffrey Carter

Re: List container strawman 1.1

[Nick Roberts]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BF2F0E7.5DD40B4B@boeing.com...
> Ted Dennison wrote:
> > The problem with that is that it won't work in an initialization.
>
> Since a list will initialize itself to empty, I don't see that as a
> problem. We may be willing to allow people to use lists in a functional
> manner, with all the implicit deallocation and allocation for deep
> copies that implies for a dynamic structure, but we certainly don't want
> to encourage it.

I think there will sometimes be situations where it would be pretty
inconvenient not to be able to build a singleton list value 'on the fly'.
Suppose we wanted to use someone's wonderful utility procedure Send_Mail to
send an e-mail Father Christmas. We might want to make a call such as:

   procedure Send_Mail (Recipient   => Single("santa@north.pole"),
                        CC          => To_List(("taxman@inland.rev",

"thewishfairy@nevernever.land"));
                        Text        => "Dear Santa, please could I have
...",
                        Attachments => Single(List_of_Presents));

This call has three lists made up inline. Imagine havine to declare two or
three list variables instead, and then call a procedure for each to give it
the right value. Not really a problem, but a lot less convenient.

--
Best wishes,
Nick Roberts