List container strawman

List container strawman

[Ted Dennison]

Since we do seem to be reaching a small amount of agreement on details, I went
ahead a put together a strawman package spec (sans private part) for the
unbounded list container, for the purposes of keeping the dicussions rolling in
a postitive direction. It is attached here, and available on my website at
http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html . If it
is close enough to be worth persuing, we may be able to use it as a starting
point.

(Note: The htmlization there was done by a tool I'm developing as part of the
next release of OpenToken. If you have comments on the job it did, I'd like them
too, but email would probably be the best venue for it).

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

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

Re: List container strawman

[James Rogers]

My attempts to access your website result in the following message:

The page that you have requested /dennison/Ted/htmlify.css was not
found.

Jim Rogers
Colorado Springs, Colorado USA

Ted Dennison wrote:
> 
> Since we do seem to be reaching a small amount of agreement on details, I went
> ahead a put together a strawman package spec (sans private part) for the
> unbounded list container, for the purposes of keeping the dicussions rolling in
> a postitive direction. It is attached here, and available on my website at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html . If it
> is close enough to be worth persuing, we may be able to use it as a starting
> point.
> 
> (Note: The htmlization there was done by a tool I'm developing as part of the
> next release of OpenToken. If you have comments on the job it did, I'd like them
> too, but email would probably be the best venue for it).
> 
> ---
> T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
> 
> No trees were killed in the sending of this message.
> However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Eric Merritt]

Just out of curiosity, for the iteration functions
would it be more efficient/readable to provide a
Has_Next and Has_Previous routines that return a
boolean? I realize that you have already provided
mechenisims in teh Size function and the raiseing the
No_More exception.


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

Re: List container strawman

[Ehud Lamm]

Thanks fro the effort. Sorry I didn't have time these past week to
contribute anything.

A few questions/comments. I am not sure about many of these.

1. In my scheme "Element" is a generic parameter of the top package
(Containers), and not of the specific implementations.
(Remember, my attemp for having interface inheritance)

2. Why is List private? Shouldn't it be limited private, so we avoid
possible erros caused by aliasing?
We may need a private implementation, but I'd prefer this not to be the
default, since it can come and bite you when you don't know what you are
doing. The private version is for library builders and more advanced users,
best used as part of a layered design that hides the list itself.
(If the majority wants private, at least the spec should mention the
possbile problems)


3. "Construct" is indeed a long name. We can, as part of the library, decide
on some standard name for this like - or +

4. I've seen many implemenations that paremtrize Insert and Remove with a
direction parameter, instead of having seperate routines (_Back/_Front). I
am not sure I know which approach I prefer...

5. Front() and Back() raise execption on Empty List?


6. I like having a "No_More_Elements()" operation as part of the Iterator
interface. It saves time compared to Size (for containers that don't keep
count of size), and I don't like programming with exceptions ("exceptions
for control flow").

7. Sort should be in a child unit.

Finally, a more general question:
Is this a DeQueue or a Doubly-linked list? Should these be two different
abstractions? (IMO: Yes, they should).

Ehud

Re: List container strawman

[Ted Dennison]

[-- Attachment #1: Type: text/plain, Size: 337 bytes --]

Ted Dennison wrote:

> Ted Dennison wrote:
> 
>> a postitive direction. It is attached here, and available on my 
>> website at
> 
> Whoops. No, it wasn't. That was probably for the best, as Newsranger 
> likes to hose formatting. It is attached here (posted w/ Mozilla).


(sigh)

My aplogies for posting HTML. Here's the text file.




[-- Attachment #2: containers-lists-unbounded.ads --]
[-- Type: text/plain, Size: 5343 bytes --]

-------------------------------------------------------------------------------
-- This file contains a proposal for a standard Ada list package.
--
-- version - Strawman 1.0
-------------------------------------------------------------------------------
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 considered using unary minus ("-") 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 Construct (Initial_Element : Element) return List;

   -----------------------------------------------------------------------------
   -- "push" and "pop" operations.
   -----------------------------------------------------------------------------
   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;

   -----------------------------------------------------------------------------
   -- I'm not too sure how useful these are, since they have to work on global
   -- data.
   -----------------------------------------------------------------------------
   generic
      with procedure Operation (Target : in out Element);
   procedure Closure_Operation (Target : in out List);

   -----------------------------------------------------------------------------
   -- Iteration routines. Next and Previous raise No_More if there is no item in
   -- the given direction. For an empty list, First = Last. As written, a
   -- typical iteration idiom would look like:
   --
   --    i := My_Lists.First (My_List);
   --    loop
   --       do stuff with My_Lists.Item(i);
   --       exit when i = My_Lists.Last (My_List);
   --       i := My_Lists.Next (i);
   --    end loop;
   --
   -- Another alternative using exception handling would be:
   --
   --    declare
   --       i := My_Lists.First (My_List);
   --    begin
   --       loop
   --          do stuff with My_Lists.Item(i);
   --          i := My_Lists.Next (i);
   --       end loop;
   --    exception
   --       when My_Lists.No_More =>
   --          null;
   --    end;
   --
   -- A third 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;
   No_More : exception;

   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 this routine 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.
   procedure Remove   (Subject : in out List; Location : Iterator);

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

private
   -- Placebo entries to make the compiler happy (so I know the syntax above is correct)
   type List is new Boolean;
   type Iterator is new Boolean;

end Containers.Lists.Unbounded;

Re: List container strawman

[Larry Kilgallen]

In article <3BE29BD4.10401@telepath.com>, Ted Dennison <dennison@telepath.com> writes:
> This is a multi-part message in MIME format.
> --------------060706040909060005070802
> Content-Type: text/plain; charset=us-ascii; format=flowed
> Content-Transfer-Encoding: 7bit
> 
> Ted Dennison wrote:
> 
>> Ted Dennison wrote:
>> 
>>> a postitive direction. It is attached here, and available on my 
>>> website at
>> 
>> Whoops. No, it wasn't. That was probably for the best, as Newsranger 
>> likes to hose formatting. It is attached here (posted w/ Mozilla).
> 
> 
> (sigh)
> 
> My aplogies for posting HTML. Here's the text file.
> 
> 
> 
> 
> --------------060706040909060005070802
> Content-Type: text/plain;
>  name="containers-lists-unbounded.ads"
> Content-Transfer-Encoding: 7bit
> Content-Disposition: inline;
>  filename="containers-lists-unbounded.ads"

So why _do_ you continue to post HTML if you know it is undesired ?

But thanks for _finally_ changing to a reasonable title.

Re: List container strawman

[Ted Dennison]

In article <3BE21F0E.49967416@worldnet.att.net>, James Rogers says...
>
>My attempts to access your website result in the following message:
>
>The page that you have requested /dennison/Ted/htmlify.css was not
>found.

Out of curiosity, what browser were you using? It works fine for me with IE 5
and Mozilla 0.95. However, I have had someone else report trouble with an older
version of Netscape.

However, I just ran the page through the CSS validator, and it reports the same
error you are reporting. Basicly, I forgot to put up the style sheet that goes
with it. Ooops! I'll get that up there when I get back home.

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

[Preben Randhol]

On Fri, 02 Nov 2001 14:23:32 GMT, Ted Dennison wrote:
> In article <3BE21F0E.49967416@worldnet.att.net>, James Rogers says...
>>
>>My attempts to access your website result in the following message:
>>
>>The page that you have requested /dennison/Ted/htmlify.css was not
>>found.
> 

> Out of curiosity, what browser were you using? It works fine for me
> with IE 5 and Mozilla 0.95. However, I have had someone else report
> trouble with an older version of Netscape.

It works with: w3m, links, lynx, opera, dillo, galeon, skipstone,
konqueror :-)

Preben
-- 
"Violence is the last refuge of the incompetent", Isaac Asimov

Re: List container strawman

[Marin David Condic]

I just took a quick look at it & I think it would be workable. It has
simplicity on its side. Without having thought about it for any real length
of time I don't see anything major missing, but perhaps there might be some
desirable operations to be added. For example, I think it ought to have a
"Load/Store" operation to get/put the contents to a file using Streams.
("You give me a file name string and a list & I handle the I/O") It would be
handy to have 'Input and 'Output working on it as well so you could get it
in and out of a Stream_Element_Array.

Also, I think it would be wise to have this (and any other packages) rooted
at some common package with a name like "ASCL" just to make the whole thing
identifiable as a conglomerate. (But that would be arguing about names and I
promised I would not do that! :-)

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:kPoE7.9567$xS6.13287@www.newsranger.com...
> Since we do seem to be reaching a small amount of agreement on details, I
went
> ahead a put together a strawman package spec (sans private part) for the
> unbounded list container, for the purposes of keeping the dicussions
rolling in
> a postitive direction. It is attached here, and available on my website at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html .
If it
> is close enough to be worth persuing, we may be able to use it as a
starting
> point.
>
> (Note: The htmlization there was done by a tool I'm developing as part of
the
> next release of OpenToken. If you have comments on the job it did, I'd
like them
> too, but email would probably be the best venue for it).
>
> ---
> T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
>
> No trees were killed in the sending of this message.
> However a large number of electrons were terribly inconvenienced.

Re: List container strawman

[Marin David Condic]

Limited private sounds like a good idea to me - with operations to assign
one list to another via duplication.

One other thing: Allow me publically to display my ignorance. If Element is
private, how does this play with tagged records? I know there is a "tagged
private" formal type - but I've never played with it so I don't know what
the implications are for that. If the Element type is "private" only and
this precludes some things, that's probably O.K. for a first cut - it would
let you pile up most of the basic data types and so would be useful. Just
wondering how the tagged private thing works.

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:9rti6v$hcu$1@news.huji.ac.il...
>
> 2. Why is List private? Shouldn't it be limited private, so we avoid
> possible erros caused by aliasing?
> We may need a private implementation, but I'd prefer this not to be the
> default, since it can come and bite you when you don't know what you are
> doing. The private version is for library builders and more advanced
users,
> best used as part of a layered design that hides the list itself.
> (If the majority wants private, at least the spec should mention the
> possbile problems)
>

Re: List container strawman

[Ted Dennison]

In article <9rti6v$hcu$1@news.huji.ac.il>, Ehud Lamm says...
>1. In my scheme "Element" is a generic parameter of the top package
>(Containers), and not of the specific implementations.
>(Remember, my attemp for having interface inheritance)

I didn't do that because that is precisely what Booch does that makes it so
complicated to use. If one does that, then proper use of the package would
require 3 cascading generic package instantiations. If that is OK, then in my
opinion we should just bag this whole thing and use Booch.

>2. Why is List private? Shouldn't it be limited private, so we avoid
>possible erros caused by aliasing?

First off, I'd like to note for anyone who may have missed it, that any Element
passed in to be put on a list or taken off of one will be *copied*. Pointers to
elements will not be used.

If List were limited private, then we'd have to get rid of all those "&"
routines. My thinking was that Lisp-like functional list processing would be
desirable. You could indeed have aliasing problems, but only if your Element
type uses pointers. Having "&" avaliable also makes list operations somewhat
consistent with arrays, which also have "&".

However, any use of those "&" routines will involve creating a copy of every
element (much like using "&" with arrays does). That would probably be too
expensive in most cases, so perhaps it really isn't all that valuable. I'm
curious how others feel about this.

>(If the majority wants private, at least the spec should mention the
>possbile problems)

I can agree with this. At the least there should be some sort of warning in
there about using pointers in Element with those routines.

>3. "Construct" is indeed a long name. We can, as part of the library, decide
>on some standard name for this like - or +

As the comment said, I seriously considered that. However, it is not (yet) a
common idiom to use those for constructors. So I'm not sure if it would help or
hurt readability. Again, I'm curious what people think about this.

>4. I've seen many implemenations that paremtrize Insert and Remove with a
>direction parameter, instead of having seperate routines (_Back/_Front). I
>am not sure I know which approach I prefer...

>5. Front() and Back() raise execption on Empty List?

Assuming you are talking about the iterator routines "First" and "Last", that's
a good point. I seem to have totally neglected that case, and thus left serious
problems in there. For instance, the comment that says "For an empty list, First
= Last." is clearly wrong. That would indicate a list with one element, not an
empty one. I'll have to redo the iterators somehow...


>6. I like having a "No_More_Elements()" operation as part of the Iterator
>interface. It saves time compared to Size (for containers that don't keep
>count of size), and I don't like programming with exceptions ("exceptions
>for control flow").

That seems sensible. And I agree about using exceptions, which is why it is only
one example of 3. That stuff is all wrong anyway though...

>7. Sort should be in a child unit.

Why do you feel that way? What does putting it off in a separate unit gain you?

>
>Finally, a more general question:
>Is this a DeQueue or a Doubly-linked list? Should these be two different
>abstractions? (IMO: Yes, they should).

What specificly would the difference be?

Clearly it would have to be doubly-linked to support all those push and pop
operations, and both Next and Previous as iterators. You could implement those
on a singly-linked list, but it wouldn't be very efficient.

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

[Ted Dennison]

In article <TOPqAssaO5$l@eisner.encompasserve.org>, Larry Kilgallen says...
>
>So why _do_ you continue to post HTML if you know it is undesired ?

Damn. I'm sorry about that. I'm not used to posting w/ Mozilla. I thought
posting it as a text attachment would make it text. I guess I should have posted
it to alt.text first.

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

[Preben Randhol]

On Fri, 02 Nov 2001 15:09:39 GMT, Ted Dennison wrote:
> Damn. I'm sorry about that. I'm not used to posting w/ Mozilla. I thought
> posting it as a text attachment would make it text. I guess I should have posted
> it to alt.text first.
        ^^^^^^^^
        alt.test I hope? ;-)

Preben
-- 
"Violence is the last refuge of the incompetent", Isaac Asimov

Re: List container strawman

[Larry Kilgallen]

In article <E%xE7.9986$xS6.13571@www.newsranger.com>, Ted Dennison<dennison@telepath.com> writes:

> However, I just ran the page through the CSS validator, and it reports the same
> error you are reporting. Basicly, I forgot to put up the style sheet that goes
> with it. Ooops! I'll get that up there when I get back home.

CSS is a relatively new feature for browsers (and _working_ CSS is
even newer).

Unlike an Ada project where you pick a version (Ada95) and force
everyone to use that version, World Wide Web communications must
often work to people who have made different tool choices.

Dreamweaver 4 has the capability to take a CSS-designed web page
and create backward compatible source for actual deployment.

Re: List container strawman

[Ted Dennison]

In article <9rubqc$i1u$1@nh.pace.co.uk>, Marin David Condic says...
>desirable operations to be added. For example, I think it ought to have a
>"Load/Store" operation to get/put the contents to a file using Streams.
>("You give me a file name string and a list & I handle the I/O") It would be
>handy to have 'Input and 'Output working on it as well so you could get it
>in and out of a Stream_Element_Array.

Definitely.

>Also, I think it would be wise to have this (and any other packages) rooted
>at some common package with a name like "ASCL" just to make the whole thing
>identifiable as a conglomerate. (But that would be arguing about names and I
>promised I would not do that! :-)

:-)
Actually, that's a perfectly reasonable discussion to be having. I picked the
root name of "Containers" just to have something. If it were part of the Ada
standard, I'd like to see "Ada.Containers.*". Otherwise, we'd need a good root
name either on top of, or instead of, "Containers".

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

[Marin David Condic]

O.K. I hereby revoke my agreement with Limited Private. If the List type
works kind of like the Ada.Strings.Unbounded.Unbounded_String type, then I
guess we're O.K. (Lists do look an awful lot like Ada.Strings.Unbounded,
don't they? You could view an unbounded string kind of as a list of
characters, eh? Maybe look at A.S.U for ideas about how it should look and
what sort of operations it should have?)

How is assignment handled here? If you don't inherit from Ada.Finalization
how do you make sure you copy the list rather than duplicate pointers to the
list? (Assuming the underlying implementation relies on pointers to list
elements.)

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:1EyE7.10050$xS6.13527@www.newsranger.com...
>
> First off, I'd like to note for anyone who may have missed it, that any
Element
> passed in to be put on a list or taken off of one will be *copied*.
Pointers to
> elements will not be used.
>
> If List were limited private, then we'd have to get rid of all those "&"
> routines. My thinking was that Lisp-like functional list processing would
be
> desirable. You could indeed have aliasing problems, but only if your
Element
> type uses pointers. Having "&" avaliable also makes list operations
somewhat
> consistent with arrays, which also have "&".
>
> However, any use of those "&" routines will involve creating a copy of
every
> element (much like using "&" with arrays does). That would probably be too
> expensive in most cases, so perhaps it really isn't all that valuable. I'm
> curious how others feel about this.
>

Re: List container strawman

[Marin David Condic]

The problem with Ada.Containers is that a) it presumes we're going to get it
into the standard and b) it makes it difficult for someone to modify the
source since compilers are free to restrict you from manipulating things
under Ada... (Try declaring Ada.Containers and see if it will compile.)

Probably it is better to have it rooted as its own thing so it can be as
flexible as possible until such time as The Powers That Be decide to
immortalize you by including The Dennison Components into the standard. :-)
It could probably be accommodated at a later date through a bunch of
"renames" things...

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:JMyE7.10064$xS6.13823@www.newsranger.com...
> Actually, that's a perfectly reasonable discussion to be having. I picked
the
> root name of "Containers" just to have something. If it were part of the
Ada
> standard, I'd like to see "Ada.Containers.*". Otherwise, we'd need a good
root
> name either on top of, or instead of, "Containers".

Re: List container strawman

[Ted Dennison]

In article <mailman.1004675765.27706.comp.lang.ada@ada.eu.org>, Eric Merritt
says...
>
>Just out of curiosity, for the iteration functions
>would it be more efficient/readable to provide a
>Has_Next and Has_Previous routines that return a
>boolean? I realize that you have already provided
>mechenisims in teh Size function and the raiseing the
>No_More exception.

It certinaly shouldn't be tough to do, so I don't see a good reason for not
doing it. However, the iterators as presented have serious problems. I have to
redo them anyway, so it may be best to reserve discussion about them (other than
how to redo them of course) until that is done.

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

[Francisco Javier Loma Daza]

On 2 Nov 2001, Marin David Condic wrote:
> Date: 2 Nov 2001 14:57:16 GMT
> To: comp.lang.ada@ada.eu.org
> From: "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>]
> Reply-To: comp.lang.ada@ada.eu.org
> Sender: comp.lang.ada-admin@ada.eu.org
> Subject: Re: List container strawman
> 
> Limited private sounds like a good idea to me - with operations to assign
> one list to another via duplication.
> 
> One other thing: Allow me publically to display my ignorance. If Element
> is
> private, how does this play with tagged records? I know there is a
> "tagged
> private" formal type - but I've never played with it so I don't know what
> the implications are for that.


    If the formal is tagged private then you can derive a tagged type from
it.

generic
    type T is tagged private;
package DD

    type Object is new T with null record;

end DD;

Re: List container strawman

[Ted Dennison]

In article <9rti6v$hcu$1@news.huji.ac.il>, Ehud Lamm says...
>2. Why is List private? Shouldn't it be limited private, so we avoid
>possible erros caused by aliasing?

Ahh. It finally dawned on me what your objection to private was. (I'm a little
slow today again.) We are talking about what happens when you do a 
"List1 := List2;", aren't we?

Yeah, it is either going to have to be limited, or be derived from
Ada.Finalization.Controlled. Limited gets rid of the ability to perform
funtional operations on it; Controlled get rid of the ability to instantiate it
from within a subprogram.

Have I mentioned lately how much I dislike the implementation of controlled
types? :-{

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

[Marin David Condic]

O.K. Thanks. Now I get it.

My guess is that you could still instantiate with a tagged type, so piling
up tagged records should not be a problem, right? Could you instantiate with
a 'Class wide type so anything of a class could be put on the list?

Of course you could not do an abstract type (to a plain old private formal)
since they don't exist yet, but I don't see that as a drawback.

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/


"Francisco Javier Loma Daza" <Francisco.Loma@isotrol.com> wrote in message
news:mailman.1004716745.9697.comp.lang.ada@ada.eu.org...
>
>     If the formal is tagged private then you can derive a tagged type from
> it.
>
> generic
>     type T is tagged private;
> package DD
>
>     type Object is new T with null record;
>
> end DD;
>
>

Re: List container strawman

[Ted Dennison]

In article <9rue9f$j4t$1@nh.pace.co.uk>, Marin David Condic says...
>How is assignment handled here? If you don't inherit from Ada.Finalization
>how do you make sure you copy the list rather than duplicate pointers to the
>list? (Assuming the underlying implementation relies on pointers to list
>elements.)

Well, the honest answer is that I hadn't thought of that. :-(

I guess if the funcional stuff is going to remain in there, then it will have to
be a controlled type. That means that users won't be able to instantiate it from
within a subprogram (yuk!). If we *do* make it limited, then another issue I
just thought of is that we wouldn't be able to make lists of lists (we had
already decided that we won't allow limited list components). However, I can't
think of a good common use for lists of lists of the top of my head.

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

[Marin David Condic]

I'd think that in *most* instances you aren't going to need to instantiate
from within a subprogram. Hence, Controlled is probably not that much of a
burden. (We don't live in a perfect world do we?)

How does Ada.Strings.Unbounded handle not being limited? I didn't see an
indication of it being derived from Controlled and it is doing something
fairly similar to lists. Or does it rely on behind-the-scenes magic to cope
with their dynamic nature?

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:WOzE7.10186$xS6.14012@www.newsranger.com...
>
> Ahh. It finally dawned on me what your objection to private was. (I'm a
little
> slow today again.) We are talking about what happens when you do a
> "List1 := List2;", aren't we?
>
> Yeah, it is either going to have to be limited, or be derived from
> Ada.Finalization.Controlled. Limited gets rid of the ability to perform
> funtional operations on it; Controlled get rid of the ability to
instantiate it
> from within a subprogram.
>
> Have I mentioned lately how much I dislike the implementation of
controlled
> types? :-{
>

Re: List container strawman

[Marin David Condic]

If the List type is simply private, can it contain an element that is
Controlled? In other words, is this a problem that can be covered up with
just one more layer of indirection?

I'm guessing that Ada.Strings.Unbounded has to do *something* fairly dynamic
in its underlying implementation and it has to solve the problem of
assignment along the way. That either means a) the problem can be solved
from within the language or b) its done with smoke and mirrors behind the
scenes. I'm guessing that A is likely to be the case, so perhaps a solution
does exist?

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:wVzE7.10194$xS6.14029@www.newsranger.com...
>
> I guess if the funcional stuff is going to remain in there, then it will
have to
> be a controlled type. That means that users won't be able to instantiate
it from
> within a subprogram (yuk!). If we *do* make it limited, then another issue
I
> just thought of is that we wouldn't be able to make lists of lists (we had
> already decided that we won't allow limited list components). However, I
can't
> think of a good common use for lists of lists of the top of my head.
>

Re: List container strawman

[Ted Dennison]

In article <9rueje$j69$1@nh.pace.co.uk>, Marin David Condic says...
>
>The problem with Ada.Containers is that a) it presumes we're going to get it
>into the standard and b) it makes it difficult for someone to modify the
>source since compilers are free to restrict you from manipulating things
>under Ada... (Try declaring Ada.Containers and see if it will compile.)

All of which is why it isn't currently named that. :-)

>Probably it is better to have it rooted as its own thing so it can be as
>flexible as possible until such time as The Powers That Be decide to
>immortalize you by including The Dennison Components into the standard. :-)

Fine by me. It might be a good idea if it were something reasonably
interchangable with "Ada." when/if the time comes. But then again, perhaps it
would be best to have somthing that we would be comfortable with on its own for
perpetuity.

I know the "Dennison Components" bit was just a joke, but I'd like to make one
thing perfectly clear: I don't want or need my name prominently attached to
this. This has been and should contiune to be a community effort. We have just
reached a point in the discussion where we really need something tangible to
talk around. I'm trying to see if it is possible to synthesize our agreements
into source code form. If it is possible, great. If not, it was worth a shot. If
I wanted to make my *own* component library, I'd just do it rather than come up
here asking for input on everything. More likely, I'd *not* do it and use Booch.
:-)

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

[David Botton]

Why not start with the Original (as in Ada 83) Booch
http://www.adapower.com/original_booch components and just modify them (they
are under the GMGPL)? They are a very close fit already.

"Ted Dennison" <dennison@telepath.com> wrote
> Since we do seem to be reaching a small amount of agreement on details

Re: List container strawman

[Ted Dennison]

In article <9ruhig$kef$1@nh.pace.co.uk>, Marin David Condic says...
>up tagged records should not be a problem, right? Could you instantiate with
>a 'Class wide type so anything of a class could be put on the list?

I don't believe so. However, you can't do that with an array either. In both
cases you'd have to use a pointer to your tagged type. That would mean you'd
have to avoid the funtional stuff ("&" routines), or at least be careful using
it.

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

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

Re: List container strawman

[Marin David Condic]

I think we're clear that this is a group-consensus effort to at least see
what sort of requirements people have for such a library. So far, we're at
least kicking around some concrete ideas, which IMHO is a good thing.

I know we've got a couple of BC fans here & if there was a consensus to
accept that, I'd get on board, so maybe its still an idea worth kicking
around. But I can understand and agree with the objection that it is not as
simple and straightforward as one might like. Is there any way we might
identify interested parties and get a straw-poll on it? Any chance the
vendors would likely get on board?

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:j8AE7.10206$xS6.13935@www.newsranger.com...
>
> I know the "Dennison Components" bit was just a joke, but I'd like to make
one
> thing perfectly clear: I don't want or need my name prominently attached
to
> this. This has been and should contiune to be a community effort. We have
just
> reached a point in the discussion where we really need something tangible
to
> talk around. I'm trying to see if it is possible to synthesize our
agreements
> into source code form. If it is possible, great. If not, it was worth a
shot. If
> I wanted to make my *own* component library, I'd just do it rather than
come up
> here asking for input on everything. More likely, I'd *not* do it and use
Booch.
> :-)

Re: List container strawman

[Jeffrey Carter]

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

This is NOT a list. A list allows insertions at any point in the
sequence. This is a dequeue.

> --
> -- version - Strawman 1.0
> -------------------------------------------------------------------------------
> generic
>    type Element is private;

This specifies that the package requires "=" for Element. I see no need
for "=" in implementing a dequeue. The generic formal part is improperly
specified.

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

This either needs to be limited private or a controlled type. Since this
is an unbounded dequeue, assignment of one dequeue to another will
result in sharing the internal structure implementing the source
dequeue.

What are the time/space implications for the operations. For example, is
Size O(1) or O(N)?

> 
>    -----------------------------------------------------------------------------
>    -- 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 considered using unary minus ("-") 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 Construct (Initial_Element : Element) return List;

I suggest Make rather than Construct.

> 
>    -----------------------------------------------------------------------------
>    -- "push" and "pop" operations.
>    -----------------------------------------------------------------------------
>    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);

What happens if you Pop from an empty list?

> 
>    -----------------------------------------------------------------------------
>    -- 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;
> 
>    -----------------------------------------------------------------------------
>    -- I'm not too sure how useful these are, since they have to work on global
>    -- data.

They are global to Operation, but they are no more global to the client
code than are any variables used in the "do stuff" part of your examples
below.

>    -----------------------------------------------------------------------------
>    generic
>       with procedure Operation (Target : in out Element);
>    procedure Closure_Operation (Target : in out List);

This is an iterator and should be so named ("Iterate"). I recommend
adding a Quit or Continue out Boolean parameter to Operation to allow
the client to terminate the iteration early.

> 
>    -----------------------------------------------------------------------------
>    -- Iteration routines. Next and Previous raise No_More if there is no item in
>    -- the given direction. For an empty list, First = Last. As written, a
>    -- typical iteration idiom would look like:
>    --
>    --    i := My_Lists.First (My_List);
>    --    loop
>    --       do stuff with My_Lists.Item(i);
>    --       exit when i = My_Lists.Last (My_List);
>    --       i := My_Lists.Next (i);
>    --    end loop;
>    --
>    -- Another alternative using exception handling would be:
>    --
>    --    declare
>    --       i := My_Lists.First (My_List);
>    --    begin
>    --       loop
>    --          do stuff with My_Lists.Item(i);
>    --          i := My_Lists.Next (i);
>    --       end loop;
>    --    exception
>    --       when My_Lists.No_More =>
>    --          null;
>    --    end;
>    --
>    -- A third 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;
>    --
>    -----------------------------------------------------------------------------

This is really ugly. Why should the client have to include all this
framing code every time he uses an iterator? The passive iterator
(generic) given above does the same thing without all this extra client
code, and allows the value stored in the dequeue to be changed as well.

>    type Iterator is private;
>    No_More : exception;
> 
>    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 this routine 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.

This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for
an example.

>    procedure Remove   (Subject : in out List; Location : Iterator);

Using a given Iterator value, what is the value of Next or Previous
after Remove? How about Item? What about when you remove the first or
last Elements in the dequeue?

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

This seems ugly and easy to get wrong. Why not import "<" and specify
that after calling Sort, the Elements in Subject will be in order
according to "<"? Then the meaning of the imported function is clear
without such a comment.

>    generic
>       with function Reverse_Order (Left, Right : in Element) return Boolean;
>    procedure Sort (Subject : in out List);
> 
> private
>    -- Placebo entries to make the compiler happy (so I know the syntax above is correct)
>    type List is new Boolean;
>    type Iterator is new Boolean;
> 
> end Containers.Lists.Unbounded;

-- 
Jeffrey Carter

Re: List container strawman

[Jeffrey Carter]

Ted Dennison wrote:
> 
> Yeah, it is either going to have to be limited, or be derived from
> Ada.Finalization.Controlled. Limited gets rid of the ability to perform
> funtional operations on it; Controlled get rid of the ability to instantiate it
> from within a subprogram.

Functions may return limited values; the function call may be used as
the actual for a parameter or renamed as a (constant) object of the
type.

Controlled requires instantiating at the library level, which is a pain,
but I think it's required anyway for an unbounded structure, since
otherwise you will have memory leaks when objects of the type go out of
scope.

-- 
Jeffrey Carter

Re: List container strawman

[David Botton]

Just to clarify, I am not referring to the BC components.

"David Botton" <David@Botton.com> wrote in message
news:tu5kdq7ej2j3e6@corp.supernews.com...
> Why not start with the Original (as in Ada 83) Booch
> http://www.adapower.com/original_booch components and just modify them
(they
> are under the GMGPL)? They are a very close fit already.
>
> "Ted Dennison" <dennison@telepath.com> wrote
> > Since we do seem to be reaching a small amount of agreement on details
>
>

Re: List container strawman

[Mark Johnson]

Ted Dennison wrote:

> [snip]  If we *do* make it limited, then another issue I
> just thought of is that we wouldn't be able to make lists of lists (we had
> already decided that we won't allow limited list components). However, I can't
> think of a good common use for lists of lists of the top of my head.

Examples of a list (or nested) of lists...
 - represent the nested scope of names (e.g., A.X.3) or other items
 - a sparse array implementation (2d or 3d...)
 - associative lookups of data
are a few that come off the top of my head. I kept thinking of LISP when I thought
of other applications as well. Not to say there are not better algorithms to
implement such capabilities, but you will likely be surprised at what people come up
with.
  --Mark

Re: List container strawman

[Marin David Condic]

Or a Unix/WinNT directory - that could be modeled as a list of lists of
lists of... (Sounds like recursion to me...)

Its something that would be nice to be able to do, but its not necessarily
something that won't have its own drawbacks. We can't expect everything out
of one little list package, so maybe we take a cut at what is possible and
think about alternate designs as possible additions. Maybe thats an
indication of a need for alternate list packages - or possibly other data
structures like trees?

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/


"Mark Johnson" <Mark_H_Johnson@Raytheon.com> wrote in message
news:3BE2E1DD.EE0078C7@Raytheon.com...
>
> Examples of a list (or nested) of lists...
>  - represent the nested scope of names (e.g., A.X.3) or other items
>  - a sparse array implementation (2d or 3d...)
>  - associative lookups of data
> are a few that come off the top of my head. I kept thinking of LISP when I
thought
> of other applications as well. Not to say there are not better algorithms
to
> implement such capabilities, but you will likely be surprised at what
people come up
> with.

Re: List container strawman

[Larry Kilgallen]

In article <3BE2E1DD.EE0078C7@Raytheon.com>, Mark Johnson <Mark_H_Johnson@Raytheon.com> writes:

> Examples of a list (or nested) of lists...
>  - represent the nested scope of names (e.g., A.X.3) or other items

It seems to me that would be a list inside a record, since if the
list contained elements for X, Y and Z, something associated with
the list would have to indicate A.

Re: List container strawman

[Ted Dennison]

In article <9rui2b$kku$1@nh.pace.co.uk>, Marin David Condic says...
>How does Ada.Strings.Unbounded handle not being limited? I didn't see an
>indication of it being derived from Controlled and it is doing something
>fairly similar to lists. Or does it rely on behind-the-scenes magic to cope
>with their dynamic nature?

The one implementation I know about (and I haven't looked at Gnat's so I could
easily make it two) does indeed use a controlled type. Since it isn't a generic,
and is indeed declared at the library level, this is no problem. We have the
problem here because its a generic. 

Remember, declaring objects of type List isn't the issue. The issue is declaring
the list type itself.

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

[Mike Brenner]

Ted Dennison <dennison@telepath.com> posted a Strawman for a List package asked for comments.

Comment 1. Possibly add a new retrieval function. The ability to PEEK, that is, to read the n-th element from either side of the list without popping. To implement this, the ITEM function could possibly be split into PEEK_FRONT and PEEK_BACK.

Comment 2. The lists are indexed by type natural. It might be beneficial to generically put in an indexing type to use instead?

Comment 3. There is no method of putting in a garbage collector.

Comment 4. The ability to delete, insert, move, swap, and copy things around might be useful. These would be fast in a double linked list and slow in a single linked list.

Comment 5. I like Marin David Condic's idea of adding a load/store to put the list to streams and 'read and 'write. Adding to that, I prefer all types to have a string representation, for example:

	function image(list: lists) return string;

Comment 6. I agree with Ehud Lamm that there is a significant difference between limited private and private. In differing circumstances, one would want both. The limited private is safer but has syntactic problems (e.g. one has to use functions instead of the assignment operator).

Comment 7. I also agree that SORT should be a child package so we can substitute a faster sort for whatever is provided. Also all higher functionality should be substitutable through child packages, generic parameters, or some other method.

Comment 8. On copying the list, there is a convention in Python that there is a copy that just copies the top level of pointers and a deep_copy that copies all levels of pointers. Perhaps something like that could be invented here.

Re: List container strawman

[Ted Dennison]

In article <3BE2DB99.B707D409@boeing.com>, Jeffrey Carter says...
>
>Ted Dennison wrote:
>> 
>> -- This file contains a proposal for a standard Ada list package.
>
>This is NOT a list. A list allows insertions at any point in the
>sequence. This is a dequeue.

Ahhh. I *knew* I forgot a routine. :-) I'll add Insert next to Remove.


>This either needs to be limited private or a controlled type. Since this
>is an unbounded dequeue, assignment of one dequeue to another will
>result in sharing the internal structure implementing the source
>dequeue.

Right again.

>What are the time/space implications for the operations. For example, is
>Size O(1) or O(N)?

That's something we should most certianly discuss (for all these ops). I'd be
for specifying that Size *should* be O(1), which implies that it will be kept
with the main list structure rather than calculated at every Size call.

>I suggest Make rather than Construct.

Fair enough. I'm used to seeing "make" in terms of GNU make, but the term
"Construct" has a fair bit of baggage too. Do we have a second on this motion?

>What happens if you Pop from an empty list?

Good catch. I'll add an exception for that.

(talking about the Closure_Operation generic's Operation procedure parameter)
>They are global to Operation, but they are no more global to the client
>code than are any variables used in the "do stuff" part of your examples
>below.

True. I'm so used to avioding using globals in routines that its tough to
retrain my thinking in this case. But I guess its OK, since you can instantiate
this generic at any level you choose. Thus it could still be data local to the
calling subroutine, but "global" to Operation.

>>    generic
>>       with procedure Operation (Target : in out Element);
>>    procedure Closure_Operation (Target : in out List);
>
>This is an iterator and should be so named ("Iterate"). I recommend
>adding a Quit or Continue out Boolean parameter to Operation to allow
>the client to terminate the iteration early.

Both seem like good suggestions. I'll work on it.

>>    -- Iteration routines. Next and Previous raise No_More if there is no 
>This is really ugly. Why should the client have to include all this
>framing code every time he uses an iterator? The passive iterator
>(generic) given above does the same thing without all this extra client
>code, and allows the value stored in the dequeue to be changed as well.

I messed that interface up a bit, so I'd appreciate it if you would look over
the next version and reconsider your comment. It does clean it up a bit. Also
note that to use the passive iterator, you need a generic instantiation and a
custom Operation routine, both of which this solution does not require. I think
most folks would at least find it a wash.

Even if it isn't as nice as the passive iterator, I think it is still needed, as
that is how Insert and Remove (your middle of the list operations) are
performed.

>This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for
>an example.

Hmmm. Yeah, I guess one could keep a copy of the address of the list around,
assuming that it is implemented in a way in which that makes sense. That still
doesn't prevent further operations from invalidating your iterator. To detect
that, you'd need to somehow keep track of every iterator issued along with the
list (in a little mini-list inside it) %-( .

>
>>    procedure Remove   (Subject : in out List; Location : Iterator);
>
>Using a given Iterator value, what is the value of Next or Previous
>after Remove? How about Item? What about when you remove the first or
>last Elements in the dequeue?

Yet another good catch (one would think you've done this before ;-) ). I'd say
that:

o  The mode for "Location" should be "in out" so it won't be invalid afterwards.
o  If Location=First, then Location will be set to the new First.
o  If Location=Last, then Location will be set to Done_Iterating.
o  If Location=Done_Iterating, then No_Item will be raised.
o  otherwise, Location will be set to what Next was previously (the next element
after the removal).



>
>> 
>>    -----------------------------------------------------------------------------
>>    -- 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. :-)
>>    -----------------------------------------------------------------------------
>
>This seems ugly and easy to get wrong. Why not import "<" and specify
>that after calling Sort, the Elements in Subject will be in order
>according to "<"? Then the meaning of the imported function is clear
>without such a comment.

I started with that, but it wasn't clear to *me* when I read it back to myself.
(Hint: which end of the list is on the "left"?) Admittedly, I'm not always the
perfect judge of such things though. Does anyone else think that would be
clearer?

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

[David Starner]

On 2 Nov 2001 07:31:02 -0600, Larry Kilgallen <Kilgallen@SpamCop.net> wrote:
> In article <3BE29BD4.10401@telepath.com>, Ted Dennison <dennison@telepath.com> writes:
>> --------------060706040909060005070802
>> Content-Type: text/plain;
>>  name="containers-lists-unbounded.ads"
>> Content-Transfer-Encoding: 7bit
>> Content-Disposition: inline;
>>  filename="containers-lists-unbounded.ads"
> 
> So why _do_ you continue to post HTML if you know it is undesired ?

That's not HTML; that's MIME.   

-- 
David Starner - dstarner98@aasaa.ofe.org
Pointless website: http://dvdeug.dhis.org
"I saw a daemon stare into my face, and an angel touch my breast; each 
one softly calls my name . . . the daemon scares me less."
- "Disciple", Stuart Davis

Re: List container strawman

[Ted Dennison]

In article <mailman.1004730907.14961.comp.lang.ada@ada.eu.org>, Mike Brenner
says...
>
>Comment 3. There is no method of putting in a garbage collector.

*That's* the other thing I forgot! I was thinking of having a storage pool be an
optional parameter (the default being the default storage pool). Any problems
with that?

>Comment 4. The ability to delete, insert, move, swap, and copy things around might be useful. These would be fast in a double linked list and slow in a single linked list.

Delete and insert are now in there. The others aren't but could be accomplished
with delete and insert. Does anyone think they need their own routines anyway?

>
>Comment 5. I like Marin David Condic's idea of adding a load/store to put the 
>list to streams and 'read and 'write. Adding to that, I prefer all types to 

Done.

>have a string representation, for example:
>
>	function image(list: lists) return string;

In my own code, I'd agree. For something meant to fit nicely into the existing
Ada library, I'm not so sure. Remember that it wouldn't be too tough to do this
yourself using one of the iterators.

>Comment 7. I also agree that SORT should be a child package so we can 
>substitute a faster sort for whatever is provided. Also all higher 
>functionality should be substitutable through child packages, generic >parameters, or some other method.

You can *still* do that (or some important information in the declaration may be
deferred to the body, in which case you can't do either). All this does is
provide a default algorithm which is easy to use. However, it really doesn't
matter much at all syntacticly. This way just saves a "with".

>Comment 8. On copying the list, there is a convention in Python that there is a copy that just copies the top level of pointers and a deep_copy that copies all levels of pointers. Perhaps something like that could be invented here.

I don't think that would be feasible, since that would require client help for
any pointers that are in the Element type (its opaque to the List package). I'm
guessing Python doesn't have that issue?

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

[Larry Kilgallen]

In article <9rv0qq$8i41@news.cis.okstate.edu>, David Starner <dvdeug@x8b4e53cd.dhcp.okstate.edu> writes:
> On 2 Nov 2001 07:31:02 -0600, Larry Kilgallen <Kilgallen@SpamCop.net> wrote:
>> In article <3BE29BD4.10401@telepath.com>, Ted Dennison <dennison@telepath.com> writes:
>>> --------------060706040909060005070802
>>> Content-Type: text/plain;
>>>  name="containers-lists-unbounded.ads"
>>> Content-Transfer-Encoding: 7bit
>>> Content-Disposition: inline;
>>>  filename="containers-lists-unbounded.ads"
>> 
>> So why _do_ you continue to post HTML if you know it is undesired ?
> 
> That's not HTML; that's MIME.   

Correct.

Re: List container strawman

[Jeffrey Carter]

Marin David Condic wrote:
> 
> If the List type is simply private, can it contain an element that is
> Controlled? In other words, is this a problem that can be covered up with
> just one more layer of indirection?

There's no problem with the actual type being Controlled if the formal
type is [limited] private. If there's anything about the actual type
that requires finalization we would hope the client would implement it
as a controlled type, since objects of this type are going to come and
go as items are added and removed from the structure.

> 
> I'm guessing that Ada.Strings.Unbounded has to do *something* fairly dynamic
> in its underlying implementation and it has to solve the problem of
> assignment along the way. That either means a) the problem can be solved
> from within the language or b) its done with smoke and mirrors behind the
> scenes. I'm guessing that A is likely to be the case, so perhaps a solution
> does exist?

Unbounded_String may be implemented as a controlled type. It's
implementation is not defined, so compiler writers may use any tricks
they think necessary, but you could write the implementation in plain
Ada.

Another place where some compiler writers use tricks is the interaction
between a random number Generator value and the Random function. The
generator holds the state data for the algorithm, which are supposed to
be updated when a number is generated. You can implement Generator as a
controlled type with a pointer to the state data, but again other tricks
are possible from within the compiler.

-- 
Jeffrey Carter

Re: List container strawman

[Jeffrey Carter]

Ted Dennison wrote:
> 
> Even if it isn't as nice as the passive iterator, I think it is still needed, as
> that is how Insert and Remove (your middle of the list operations) are
> performed.

OK. Then this isn't really an iterator type; it's the "Position" type
that indicates where in the list you're operating. Now this is starting
to look like a list, except I expect to see the general operations
(obtain a Position for a list and operate on a specific Position within
a list) first, with the bells and whistles later.

> 
> >This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for
> >an example.
> 
> Hmmm. Yeah, I guess one could keep a copy of the address of the list around,
> assuming that it is implemented in a way in which that makes sense. That still
> doesn't prevent further operations from invalidating your iterator. To detect
> that, you'd need to somehow keep track of every iterator issued along with the
> list (in a little mini-list inside it) %-( .

The technique used by PragmARC.List_Unbounded_Unprotected is that the
list object contains a pointer to a "mini-node" (a node with no data
stored in it). This makes insertions and deletions at the beginning and
end of the list look exactly the same as insertions and deletions in the
middle, but it also follows that the value of this pointer is unique to
the list object. Call this value the list ID. Every node in the list
contains a copy of this ID, as does every Position value generated for
the list. An operation is not permitted unless the IDs for the list,
position, and node match. When a node is deleted, its ID is invalidated
(set to null), and the position used to delete the node is similarly
invalidated (both its ID and pointer are set to null). If a client makes
a copy of a Position and uses one to delete a node, he cannot then
manipulate the deallocated node through the other since it has an
invalid ID. Easy to implement and fairly foolproof.

> 
> >
> >>    procedure Remove   (Subject : in out List; Location : Iterator);
> >
> >Using a given Iterator value, what is the value of Next or Previous
> >after Remove? How about Item? What about when you remove the first or
> >last Elements in the dequeue?
> 
> Yet another good catch (one would think you've done this before ;-) ). I'd say
> that:
> 
> o  The mode for "Location" should be "in out" so it won't be invalid afterwards.
> o  If Location=First, then Location will be set to the new First.
> o  If Location=Last, then Location will be set to Done_Iterating.
> o  If Location=Done_Iterating, then No_Item will be raised.
> o  otherwise, Location will be set to what Next was previously (the next element
> after the removal).

Now that I know that this is standard list manipulation, not iteration,
I'd recommend calling it Delete. It's also a lot simpler to make
Location in out and invalidate it.

There should probably be an Update procedure that changes the Element
stored at a location.

> >>    -----------------------------------------------------------------------------
> >>    -- 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. :-)
> >>    -----------------------------------------------------------------------------
> >
> >This seems ugly and easy to get wrong. Why not import "<" and specify
> >that after calling Sort, the Elements in Subject will be in order
> >according to "<"? Then the meaning of the imported function is clear
> >without such a comment.
> 
> I started with that, but it wasn't clear to *me* when I read it back to myself.
> (Hint: which end of the list is on the "left"?) Admittedly, I'm not always the
> perfect judge of such things though. Does anyone else think that would be
> clearer?

A list is a sequence; it has a first Element, a second Element, and so
on. The postcondition here is that for any 2 valid locations L1 and L2
such that L1 /= L2 and L2 = Next (L1),

not (Item (L2) < Item (L1) ).

-- 
Jeffrey Carter

Re: List container strawman

[Matthew Heaney]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BE3235D.E292B890@boeing.com...
> Another place where some compiler writers use tricks is the interaction
> between a random number Generator value and the Random function. The
> generator holds the state data for the algorithm, which are supposed to
> be updated when a number is generated. You can implement Generator as a
> controlled type with a pointer to the state data, but again other tricks
> are possible from within the compiler.

Why would you need to implement type Generator as a Controlled type?
Generator state is allocated on the stack, so Finalization is not required.
Allocating state on the heap and using Controlled Finalization would be a
horribly inefficient way to implement that type.

No heap allocation or compiler magic is needed to implement Generator; just
use the Rosen Trick:

package P is
   type Generator is limited private;
   function Random (G : Generator) return Integer;
private
   type Handle_Type (G : access Generator) is null record;
   type Generator is limited record
      Handle : Handle_Type (G'Access);
      State : State_Type;  --whatever
   end record;
end P;

package body P is
   function Random (G : Generator) return Integer is
      State : State_Type renames G.Handle.G.all;
   begin
      -- modify State as necessary
      return X;
    end;
end P;

This is all perfectly legal.

Re: List container strawman

[Jeffrey Carter]

Matthew Heaney wrote:
> 
> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
> news:3BE3235D.E292B890@boeing.com...
> > Another place where some compiler writers use tricks is the interaction
> > between a random number Generator value and the Random function. The
> > generator holds the state data for the algorithm, which are supposed to
> > be updated when a number is generated. You can implement Generator as a
> > controlled type with a pointer to the state data, but again other tricks
> > are possible from within the compiler.
> 
> Why would you need to implement type Generator as a Controlled type?
> Generator state is allocated on the stack, so Finalization is not required.
> Allocating state on the heap and using Controlled Finalization would be a
> horribly inefficient way to implement that type.

The obvious way to modify an in parameter is to have it be an access
value and change what it points to. You would want this to be Controlled
so you could deallocate the storage when an object of the type goes out
of scope.

The GNAT implementation says

   --  The design of this spec is very awkward, as a result of Ada 95
not
   --  permitting in-out parameters for function formals (most naturally
   --  Generator values would be passed this way). In pure Ada 95, the
only
   --  solution is to use the heap and pointers, and, to avoid memory
leaks,
   --  controlled types.

> 
> No heap allocation or compiler magic is needed to implement Generator; just
> use the Rosen Trick:

Yes, that is a trick that can be used (although your example has a
couple of errors). Was it known before standardization? I somehow
suspect it would have been outlawed if it were.

GNAT uses

   type State is ...

   type Generator is limited record
      Gen_State : State;
   end record;

Following the above quote, they add

   --  This is awfully heavy, so what we do is to use
Unrestricted_Access to
   --  get a pointer to the state in the passed Generator. This works
because
   --  Generator is a limited type and will thus always be passed by
reference.

   type Pointer is access all State;

   function Random  (Gen : Generator) return Uniformly_Distributed is
      Genp : constant Pointer := Gen.Gen_State'Unrestricted_Access;

and then modify Genp.all. Since 'Unrestricted_Access is an
implementation-dependent attribute, I think this qualifies as a trick,
too. I wonder if there is some advantage to this trick over the Rosen
trick.

-- 
Jeff Carter
"Now go away or I shall taunt you a second time."
Monty Python & the Holy Grail

Re: List container strawman

[Ted Dennison]

In article <3BE32A18.18404AD1@boeing.com>, Jeffrey Carter says...
>The technique used by PragmARC.List_Unbounded_Unprotected is that the
>list object contains a pointer to a "mini-node" (a node with no data
>stored in it). This makes insertions and deletions at the beginning and
>end of the list look exactly the same as insertions and deletions in the
>middle, but it also follows that the value of this pointer is unique to
>the list object. Call this value the list ID. Every node in the list
>contains a copy of this ID, as does every Position value generated for
>the list. An operation is not permitted unless the IDs for the list,
>position, and node match. When a node is deleted, its ID is invalidated
>(set to null), and the position used to delete the node is similarly
>invalidated (both its ID and pointer are set to null). If a client makes
>a copy of a Position and uses one to delete a node, he cannot then
>manipulate the deallocated node through the other since it has an
>invalid ID. Easy to implement and fairly foolproof.

So you are saying that you are placing values into the memory before it is
deallocated, in the hopes that any code trying to access it through a stale
pointer will still find that value there (telling it not to use this)?

What if:
a) The memory at that location gets reallocated to something else in the
meantime, which then puts what looks like a valid value in there.

b) The OS marks that location as not allocated, and issues a segfault (or
whatever) when you try to access it.

>Now that I know that this is standard list manipulation, not iteration,
>I'd recommend calling it Delete. It's also a lot simpler to make
>Location in out and invalidate it.

That could be done. "Delete" would also be a natural name for toasting a list,
but then I guess in the current scheme "-" would make more sense for that.

>There should probably be an Update procedure that changes the Element
>stored at a location.

That sounds right.


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

[Simon Wright]

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

> This is an iterator and should be so named ("Iterate"). I recommend
> adding a Quit or Continue out Boolean parameter to Operation to
> allow the client to terminate the iteration early.

One of my users suggests making this an in out parameter, initialized
to "carry on", so that he doesn't have to (remember to) assign it
before exit.

Re: List container strawman

[Simon Wright]

Ted Dennison<dennison@telepath.com> writes:

> In article <mailman.1004730907.14961.comp.lang.ada@ada.eu.org>, Mike Brenner
> says...
> >
> >Comment 3. There is no method of putting in a garbage collector.
> 
> *That's* the other thing I forgot! I was thinking of having a
> storage pool be an optional parameter (the default being the default
> storage pool). Any problems with that?

I couldn't find a way of giving the parameter a default; the problem
being that there's no standard way of getting at the standard storage
pool. GNAT makes it visible, but warns you about using features that
aren't "officially" supported.

I guess one could go in for indirections using accesses or functions
.. I have

  generic
     Storage : in out System.Storage_Pools.Root_Storage_Pool'Class;
  package BC.Containers.Collections.Unbounded is

and you can get at the default pool using

  with System.Storage_Pools;

  package BC.Support.Standard_Storage is

     type T is access Integer; -- arbitrary subtype

     Pool : System.Storage_Pools.Root_Storage_Pool'Class
       renames T'Storage_Pool;

  end BC.Support.Standard_Storage;


Aha! this compiles (GNAT 3.14a1), whether it is legal and works on
other compilers is a different matter of course ..

  with System.Storage_Pools;
  package Default_Pool is

     type Pool_Access
     is access all System.Storage_Pools.Root_Storage_Pool'Class;

     type T is access Integer;
     Pool : System.Storage_Pools.Root_Storage_Pool'Class
       renames T'Storage_Pool;

     generic
	Storage : Pool_Access := Pool'Access;
     package G is
     end G;

  end Default_Pool;

Re: List container strawman

[Simon Wright]

Simon Wright <simon@pushface.org> writes:

> Aha! this compiles (GNAT 3.14a1), whether it is legal and works on
> other compilers is a different matter of course ..
> 
>   with System.Storage_Pools;
>   package Default_Pool is
> 
>      type Pool_Access
>      is access all System.Storage_Pools.Root_Storage_Pool'Class;
> 
>      type T is access Integer;
>      Pool : System.Storage_Pools.Root_Storage_Pool'Class
>        renames T'Storage_Pool;
> 
>      generic
> 	Storage : Pool_Access := Pool'Access;
>      package G is
>      end G;
> 
>   end Default_Pool;

Drat, I fear it's not legal; well, ObjectAda thinks not. Pool needs to
be aliased so that Pool'Access at line 12 is permitted. Bug report
sent to ACT ..

Re: List container strawman

[Nick Roberts]

May I make a suggestion, which, though I say it myself, I feel is rather
important!

Please make the type List derived from an abstract 'iterator' type. List
would then inherit the iteration operations of this type. An alternative is
for List to provide a function that generates or gives access to an object
derived from this iterator type.

For example:


generic
   type Element_Type is private;

package Containers is

   ...

   type Terminating_Producer is abstract tagged limited private;

   procedure Read (Producer: in out Terminating_Producer; Item: out
Element_Type) is abstract;

   function End_of_Data (Producer: in Terminating_Producer) return Boolean
is abstract;

   ...

   type Sequence_Reproducer is abstract new Terminating_Producer with
private;

   procedure Restart (Reproducer: in out Sequence_Reproducer) is abstract;

   type Sequence_Recorder is abstract new Sequence_Reproducer with private;

   procedure Rewrite (Reproducer: in out Sequence_Reproducer) is abstract;

   procedure Write (Recorder: in out Sequence_Recorder; Item: in
Element_Type) is abstract;

   function Count (Recorder: in Sequence_Recorder) return Natural is
abstract;

   function Is_Recording (Recorder: in Sequence_Recorder) return Boolean is
abstract;

   ...

end Containers;


The Restart procedure tells a sequence reproducer to start producing its
data over again. The Rewrite procedure tells a sequence recorder to start
recording data (at which point Write can be used and Read cannot;
Is_Recording returns True). Restart than tells it to start reading again (at
which point Write cannot be used; Is_Recording returns False). Count returns
the number of items currently recorded.


package Containers.Lists.Unbounded is

   type Linked_List is new Sequence_Recorder with private;

   -- Representing a singly-linked (forward) list type, with typical
operations.

   function "&" (Left, Right: in Linked_List) return Linked_List is
abstract;
   ...

   procedure Push (List: in out Linked_List; Item: in  Element_Type);
   procedure Pop  (List: in out Linked_List; Item: out Element_Type);

   ... -- etc

   type Doubly_Linked_List is new Sequence_Recorder with private;

   function "&" (Left, Right: in Linked_List) return Abstract_List is
abstract;
   ...

   procedure Push (List: in out Linked_List; Item: in  Element_Type);
   procedure Pop  (List: in out Linked_List; Item: out Element_Type);

   procedure Reverse_Push (List: in out Linked_List; Item: in
Element_Type);
   procedure Reverse_Pop  (List: in out Linked_List; Item: out
Element_Type);

   ... -- etc

end Containers.Utility.Lists;


In this way, a piece of software which only needs to iterate over a
container can be passed any of the list types, or other container types.
E.g.:


generic
   with package Specific_Containers is new Containers(<>);

procedure Print_a_List (List: in out
Specific_Containers.Sequence_Producer'Class);

...

   package Thingy_Containers is new Containers(Thingy_Type);

   Thingies_1: Thingy_Containers.Lists.Unbounded.Linked_List;
   Thingies_2: Thingy_Containers.Lists.Unbounded.Doubly_Linked_List;

   ...

   package Print_Thingies is new Print_a_List(Thingy_Containers);

   ...

   Print_Thingies(Thingies_1);
   Print_Thingies(Thingies_2);


We can call instantiations of Print_a_List with objects of type Linked_List,
or Doubly_Linked_List, or anything else (i.e. other containers) derived from
Sequence_Producer.

My choice of identifiers, and the details of my design may not be ideal, but
the basic idea is right.

Please don't get this elementary aspect of the design wrong!

--
Nick Roberts



"Ted Dennison" <dennison@telepath.com> wrote in message
news:kPoE7.9567$xS6.13287@www.newsranger.com...
> Since we do seem to be reaching a small amount of agreement on details, I
went
> ahead a put together a strawman package spec (sans private part) for the
> unbounded list container, for the purposes of keeping the dicussions
rolling in
> a postitive direction. It is attached here, and available on my website at
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html .
If it
> is close enough to be worth persuing, we may be able to use it as a
starting
> point.

Re: List container strawman

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3BE32A18.18404AD1@boeing.com>, Jeffrey Carter says...
> >The technique used by PragmARC.List_Unbounded_Unprotected is that the
> >list object contains a pointer to a "mini-node" (a node with no data
> >stored in it). This makes insertions and deletions at the beginning and
> >end of the list look exactly the same as insertions and deletions in the
> >middle, but it also follows that the value of this pointer is unique to
> >the list object. Call this value the list ID. Every node in the list
> >contains a copy of this ID, as does every Position value generated for
> >the list. An operation is not permitted unless the IDs for the list,
> >position, and node match. When a node is deleted, its ID is invalidated
> >(set to null), and the position used to delete the node is similarly
> >invalidated (both its ID and pointer are set to null). If a client makes
> >a copy of a Position and uses one to delete a node, he cannot then
> >manipulate the deallocated node through the other since it has an
> >invalid ID. Easy to implement and fairly foolproof.
> 
> So you are saying that you are placing values into the memory before it is
> deallocated, in the hopes that any code trying to access it through a stale
> pointer will still find that value there (telling it not to use this)?

That's right. You don't get 100% confidence, but it's better than the
nothing that most lists provide.

> 
> What if:
> a) The memory at that location gets reallocated to something else in the
> meantime, which then puts what looks like a valid value in there.

It's certainly possible that the memory could be reallocated to the same
list, so the dangling reference becomes valid again. I did say *fairly*
foolproof. :)

> 
> b) The OS marks that location as not allocated, and issues a segfault (or
> whatever) when you try to access it.

Then you're no worse off than without the check.

> That could be done. "Delete" would also be a natural name for toasting a list,
> but then I guess in the current scheme "-" would make more sense for that.

Let me record my vote against unary operators as primary names. I
probably won't object if they're renames of other subprograms. I suggest
Clear for deleting all Elements in a List; Make_Empty might also be
acceptable.

Finally, what you're calling an iterator is what is usually called a
"position within a list" in discussing lists as an abstraction, and the
manipulation of a list is usually defined in terms of positions. I think
it would make the package easier to understand if it adheres to this
convention: call the type Position and present the operations for
obtaining positions and using them to manipulate a list before the
dequeue- and string-like operations.

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

Re: List container strawman

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:wVzE7.10194$xS6.14029@www.newsranger.com...

> I guess if the funcional stuff is going to remain in there, then it will
have to
> be a controlled type. That means that users won't be able to instantiate
it from
> within a subprogram (yuk!). If we *do* make it limited, then another issue
I
> just thought of is that we wouldn't be able to make lists of lists (we had
> already decided that we won't allow limited list components). However, I
can't
> think of a good common use for lists of lists of the top of my head.

Lists of lists are frequently useful, but the problem you suggest is easily
(and efficiently) solved by having lists of access values to lists. E.g.:


   package Item_Collections is new Collections(Game_Item);

   subtype Item_List is Item_Collections.Utility.Linked_List;

   type Game_Room is limited
      record
         ...
         Contents: Item_List;
      end record;

   type Room_Reference is access all Game_Room;

   package Room_Collections is new Collections(Room_Reference);


and so on.

--
Nick Roberts

Re: List container strawman

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:j8AE7.10206$xS6.13935@www.newsranger.com...
> ...
> I know the "Dennison Components" bit was just a joke, but I'd like to make
one
> thing perfectly clear: I don't want or need my name prominently attached
to
> this. This has been and should contiune to be a community effort. We have
just
> reached a point in the discussion where we really need something tangible
to
> talk around. I'm trying to see if it is possible to synthesize our
agreements
> into source code form. If it is possible, great. If not, it was worth a
shot. If
> I wanted to make my *own* component library, I'd just do it rather than
come up
> here asking for input on everything. More likely, I'd *not* do it and use
Booch.

I'm afraid I feel it ought to be named 'Iteration'. It's terribly insipid,
but it seems to fit the bill, to me:


   generic
      type Element_Type is private;

   package Iteration is

      ...

   end Iteration;


This would then be instantiated in a very clear way:



   package Thingy_Iteration is new Iteration(Thingy_Type);

   Thingy_List_1: Thingy_Iteration.Lists.Unbounded.Doubly_Linked_List;


I think perhaps there should be a child package Lists, which declares an
abstract List_Type with attendant common list operations. This should then
have children such as Unbounded which declares concrete utility types based
on List_Type. We could then have other hierarchies implementing queues,
content-addressed containers, and so on.

See also my other posting.

--
Nick Roberts

Re: List container strawman

[Nick Roberts]

I tried to kick start the Ada Structured Component Library (ASCL) group more
than a year ago, on eGroups, but weirdly I seemed to get a pile of interest
which fizzled out as fast as it arrived. Very odd.

Anyway, I am interested!

--
Nick Roberts


"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9ruk02$lft$1@nh.pace.co.uk...
> I think we're clear that this is a group-consensus effort to at least see
> what sort of requirements people have for such a library. So far, we're at
> least kicking around some concrete ideas, which IMHO is a good thing.
>
> I know we've got a couple of BC fans here & if there was a consensus to
> accept that, I'd get on board, so maybe its still an idea worth kicking
> around. But I can understand and agree with the objection that it is not
as
> simple and straightforward as one might like. Is there any way we might
> identify interested parties and get a straw-poll on it? Any chance the
> vendors would likely get on board?

Re: List container strawman

[Darren New]

Jeffrey Carter wrote:
> > a) The memory at that location gets reallocated to something else in the
> > meantime, which then puts what looks like a valid value in there.
> 
> It's certainly possible that the memory could be reallocated to the same
> list, so the dangling reference becomes valid again. I did say *fairly*
> foolproof. :)

If you really want it to be foolproof, then for each "Location" pointer,
you keep a pointer to the list, a pointer to the element being indexed,
and a list number counter. In each list head, you keep a list number
counter, a counter of the number of Location pointers outstanding, and
the head and tail of the list.

Creating a Location copies the list number counter into the Location
record and otherwise initializes it. It also increments the reference
count in the List head. Deleting a Location decrements the ref count in
the list head. Deleting the list is defered (via finalization) until the
reference count goes to zero.

Each access to the pointer in the Location can run thru the linked list
that the Location claims it points to, to make sure the node it points
to is still on the list. This makes indirection become O(N) instead of
O(1), but it's also the kind of check that would be easy to turn on and
off at runtime, let alone compile time.

Did this for a Pascal compiler, so students using dangling pointers
would be told that instead of just dumping core.

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

[Larry Kilgallen]

In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com> writes:

> If you really want it to be foolproof,

Yes please.

Re: List container strawman

[Darren New]

> > If you really want it to be foolproof,
> Yes please.

Well, yes. However, the performance overhead can be significant. There
are ways of reducing it (see, for example, some of the fields in the
private structures in my offering) but to be 100% bullet-proof, you'd at
least need to have O(N) access times. Given user-programmable and
multiple storage pools, this would be harder than in Pascal. The trick
is to make it so you can turn it on and off at runtime, or for only a
particular type of list (i.e., particular instantiations) so you can
narrow down the problem.

Actually, I never really thought of it with user-definable storage
pools. There may be a much more efficient way of working it.

A couple other points:
1) Does Ada even ensure there's only one default storage pool? I would
think that perhaps the storage pool for Integers might be different than
the storage pool for big records.... perhaps a different storage pool
for each size item being stored or some such? Hence, I'm not surprised
that it's difficult to find out what the "default" storage pool is. Or
am I wrong in this?

2) Perhaps using terms from Unbounded_String might be wise? I.e., stuff
that treats an unbounded string as an array of elements that happen to
be characters rather than relying on the fact that they're characters.
Ie., calling the routines Element(), Replace_Element(), Slice(),
Overwrite(), Delete(), "*", etc?  This isn't what I think of as the best
naming convention, but it's at least going to be familiar to other Ada
programmers.

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

[Stephen Leake]

Do you have an example implimentation? I don't see how you can
implement "Sort" without a "Compare" operation on Element. Typically,
a user will want more than one "Compare" operation (ie Sort on first
name, sort on date). Moving Sort into a child package, that takes a
generic parameter of "Compare", would provide this.

Also, the semantics of the operations need to be clearly defined. Does
calling "Remove" invalidate other Iterators? What, exactly, does
"Closure_Operation" do?

There should be a "Insert (Iterator)" to add an element at the current
iterator position.

"List" should be limited, to prevent non-deep copies when Element is
an access type. Or it should be derived from Controlled, to allow the
user to override Adjust to provide a deep copy. Or a "Copy_Element"
generic procedure should be provided.

-- 
-- Stephe

Re: List container strawman

[Marin David Condic]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BE3235D.E292B890@boeing.com...
>
> There's no problem with the actual type being Controlled if the formal
> type is [limited] private. If there's anything about the actual type
> that requires finalization we would hope the client would implement it
> as a controlled type, since objects of this type are going to come and
> go as items are added and removed from the structure.
>
I think you missed it. Its the other way around. I was asking if the list
type you might be exporting from the generic package can be private and
contain something that is controlled.

generic
    type Something is private ;
package A_Package is
    type Something_Else is private ;
private
    type Something_Else is record
        X : Some_Type_Derived_From_Controlled_Along_Some_With_Chain ;
    end record ;
end A_Package ;

Without having passed anything like this past a compiler, I just don't know
if it is legal and gets Ted the ability to instantiate the generic from
within a non-library-level scope.


>
> Unbounded_String may be implemented as a controlled type. It's
> implementation is not defined, so compiler writers may use any tricks
> they think necessary, but you could write the implementation in plain
> Ada.
>
The spec in the appendix does not indicate a "with Ada.Finalization;"
anywhere I can see, so it isn't clear how they intended for it to be done.
That's why I was wondering how they dealt with assignment if, for example,
one were to want Unbounded_String to be implemented with some version of
dynamic allocation.

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

[Ted Dennison]

In article <9s6a60$a49$1@nh.pace.co.uk>, Marin David Condic says...
>generic
>    type Something is private ;
>package A_Package is
>    type Something_Else is private ;
>private
>    type Something_Else is record
>        X : Some_Type_Derived_From_Controlled_Along_Some_With_Chain ;
>    end record ;
>end A_Package ;
>
>Without having passed anything like this past a compiler, I just don't know
>if it is legal and gets Ted the ability to instantiate the generic from
>within a non-library-level scope.

The problem with this approach is that the X field in Something_Else can have no
knowledge of any of other the fields in Something_Else, and thus is unable to
control it. It can control itself, but not its parent Something_Else. 

I think you can sometimes use tricks like this if the thing being controlled has
nothing to do with any of the generic parameters (or anything dependant upon
them). But in all other cases you are hosed, as near as I can tell.

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

[Marin David Condic]

Hmmmmmmm..........


So basically, you're saying that a library level generic that contained as
part of it a Controlled element, you'd be able to instantiate it in a
procedure (non-library level)? But if a data item in it is itself derived
from Controlled, you can't? (Seems kind of strange, but I'm sure there's
going to be some corner-case of the rules to explain it.)

The Controlled thing clearly can't have anything to do with the generic
parameters since it needs to be itself declared in some other package. You
could pass the generic parameter making an instance of the Controlled thing,
but this is just pushing the problem off by one package - not really a
solution. So it would probably have to use something either convoluted
enough to fool the compiler into doing what you want, or it would need to do
something kind of "dirty" like using System.Address in the Controlled part
and doing some kind of access type to the generic parameter with a
conversion to address. (Kinky, but since it all remains hidden down in the
bowels of the implementation, probably not a hopelessly bad idea.)

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:yWAF7.13454$xS6.17694@www.newsranger.com...
>
> The problem with this approach is that the X field in Something_Else can
have no
> knowledge of any of other the fields in Something_Else, and thus is unable
to
> control it. It can control itself, but not its parent Something_Else.
>
> I think you can sometimes use tricks like this if the thing being
controlled has
> nothing to do with any of the generic parameters (or anything dependant
upon
> them). But in all other cases you are hosed, as near as I can tell.
>

Re: List container strawman

[Ted Dennison]

In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New says...
>
>If you really want it to be foolproof, then for each "Location" pointer,
>you keep a pointer to the list, a pointer to the element being indexed,
>and a list number counter. In each list head, you keep a list number
>counter, a counter of the number of Location pointers outstanding, and
>the head and tail of the list.

That's not good enough either, since the List could change to make the location
itself invalid. The List itself could even go out of scope while the location
doesn't. I've implemented a lot of these types of iterators in my time, so I
have thought through the issue quite a bit already.

The best I could come up with for a Right Thing would be to keep a list of
extant Location pointers in each List object. That way the list itself can go
and invalidate the Location whenever it needs to (probably by flipping some
"valid" boolean in the Location type). Locations would have to be limited for
this to work, so the functions that return locations would have to be changed to
procedures.

To my mind, that's a rediculous amount of work and overhead to support a mild
"safeing up" of one small facility (iterators). I'm of the inlincation that if
you aren't going to do the Right Thing here, then bag it. Half-measures are
liable to cause as much harm as good by giving folks a false sense of security.
You might as well just aviod the whole issue, save all the work and overhead,
and just put it on the user to use this one feature correctly. As long as the
issues are well documented (eg: Its a "Bounded Error" to use an iterator after
any modification of its list not involving that iterator), then I don't see a
big problem.

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

[Jean-Marc Bourguet]

Ted Dennison wrote:
[...]
> The best I could come up with for a Right Thing would be to keep a list of
> extant Location pointers in each List object. That way the list itself can go
> and invalidate the Location whenever it needs to (probably by flipping some
> "valid" boolean in the Location type). Locations would have to be limited for
> this to work, so the functions that return locations would have to be changed to
> procedures.

Why should they be limited?  If they are controlled, that should be enough or
do I miss something?

[...]

-- 
Jean-Marc

Re: List container strawman

[Darren New]

Ted Dennison wrote:
> 
> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New says...
> >
> >If you really want it to be foolproof, then for each "Location" pointer,
> >you keep a pointer to the list, a pointer to the element being indexed,
> >and a list number counter. In each list head, you keep a list number
> >counter, a counter of the number of Location pointers outstanding, and
> >the head and tail of the list.
> 
> That's not good enough either, since the List could change to make the location
> itself invalid.

I'm not sure how that could happen. The "location" record itself would
be separate from the list.

> The List itself could even go out of scope while the location
> doesn't.

Yes. That's why I suggested that it have a reference count, and
finalization would need to either be defered until all the locations are
also finalized or all locations would have to be invalidated when the
list goes out of scope.  Of course, in Ada this is probably a little
more complex, and you'd wind up with the public "List" type probably
just being a pointer to a controlled record.

> I've implemented a lot of these types of iterators in my time, so I
> have thought through the issue quite a bit already.

Yep.
 
> The best I could come up with for a Right Thing would be to keep a list of
> extant Location pointers in each List object. That way the list itself can go
> and invalidate the Location whenever it needs to (probably by flipping some
> "valid" boolean in the Location type). Locations would have to be limited for
> this to work, so the functions that return locations would have to be changed to
> procedures.

That could work too. You could have a linked list of Locations pointed
to by the List object.
 
> To my mind, that's a rediculous amount of work and overhead to support a mild
> "safeing up" of one small facility (iterators).

Agreed. On the other hand, you could include different bodies depending
on whether you were having trouble or not. :-) I.e., the interface
shouldn't *preclude* adding all kinds of safety checks, I think.

> I'm of the inlincation that if
> you aren't going to do the Right Thing here, then bag it. Half-measures are
> liable to cause as much harm as good by giving folks a false sense of security.
> You might as well just aviod the whole issue, save all the work and overhead,
> and just put it on the user to use this one feature correctly. As long as the
> issues are well documented (eg: Its a "Bounded Error" to use an iterator after
> any modification of its list not involving that iterator), then I don't see a
> big problem.

Agreed. But it *is* doable. Probably not worth doing, tho. My
expectation is that it would be a debugging aid you turned on if you
need it, kind of like "Purify" for your C code.

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

[Ted Dennison]

In article <3BE6EBB1.EF463656@free.fr>, Jean-Marc Bourguet says...
>
>Ted Dennison wrote:
>[...]
>> The best I could come up with for a Right Thing would be to keep a list of
>> extant Location pointers in each List object. That way the list itself can go
>> and invalidate the Location whenever it needs to (probably by flipping some
>> "valid" boolean in the Location type). Locations would have to be limited for
>> this to work, so the functions that return locations would have to be changed to
>> procedures.
>
>Why should they be limited?  If they are controlled, that should be enough or
>do I miss something?

That would be a lot tougher, as they'd have to somehow go add themselves and
remove themselves from the List's list dynamcily. I guess its doable, its just
even more work. :-)

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

[Ted Dennison]

In article <3BE6F58C.7C88F6CD@san.rr.com>, Darren New says...
>
>Ted Dennison wrote:
>> That's not good enough either, since the List could change to make the 
>> location itself invalid.
>
>I'm not sure how that could happen. The "location" record itself would
>be separate from the list.

Lots of ways. For instance, the element pointed to could be deleted using
another iterator. It could get removed with a Pop. It could get removed with
that global list empty that someone suggested I add.

>> I'm of the inlincation that if
>> you aren't going to do the Right Thing here, then bag it. Half-measures are
>
>Agreed. But it *is* doable. Probably not worth doing, tho. My

Exactly.

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

[Ted Dennison]

In article <9s6o5m$fsi$1@nh.pace.co.uk>, Marin David Condic says...

>So basically, you're saying that a library level generic that contained as
>part of it a Controlled element, you'd be able to instantiate it in a
>procedure (non-library level)? But if a data item in it is itself derived
>from Controlled, you can't? (Seems kind of strange, but I'm sure there's
>going to be some corner-case of the rules to explain it.)

Yes. It isn't controlled per se. Its just that you can't declare a derived
tagged type at a lower level than its parent, and Controlled is a tagged type.
The rule goes for all tagged types. Its just that controlled was unfortunately
implemented as a tagged type declared at the library level.

>solution. So it would probably have to use something either convoluted
>enough to fool the compiler into doing what you want, or it would need to do
>something kind of "dirty" like using System.Address in the Controlled part
>and doing some kind of access type to the generic parameter with a
>conversion to address. (Kinky, but since it all remains hidden down in the
>bowels of the implementation, probably not a hopelessly bad idea.)

Any solution would have to have the library-level controlled type somehow know
how to control the non-library-level type. If the controlled stuff isn't a
generic parameter or dependent on one, there are (nasty) ways to do that. If it
is, then you are just plain hosed (unless someone knows a neat trick I don't).

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

[ramatthews]

In article <bgR13FMw5mIK@eisner.encompasserve.org>, Kilgallen@SpamCop.net (Larry Kilgallen) wrote:
> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com> writes:
> 
>> If you really want it to be foolproof,
> 
> Yes please.


While I see a foolproof list does not have universal appeal I have
been successfully using one for some time so I thought its 
specification would help discussions.

Robert Matthews

-----------------------------------------------------
with Ada.Finalization;
with Ada.IO_Exceptions;
with Ada.Streams;
with Ada.Tags;

generic
   type Data_Type (<>) is private;
package Containers.Lists.Unbounded is

   --  This package provides facilities for manipulating simple list structures.
   --
   --  A list is an ordered sequence of data elements. It can also be empty,
   --  containing no data elements.
   --
   --  Client software creates an empty list by declaring a variable of type
   --  List_Type. Data elements can then be added to the list via the subprograms
   --  Prepend and Append. Note that data is copied into the list - pointers are not
   --  retained to the original data.
   --
   --  All data elements can be removed from a list via subprogram Delete_All.
   --  Applying this subprogram to an already empty list will have no effect.
   --
   --  When applied to an empty list, Is_Empty will return True, otherwise it will
   --  return False.
   --
   --  A list can be assigned to another. The target list will be emptied then loaded with
   --  a copy of each data element in the source list. The copying will be done such that
   --  the ordering of the data elements in each list will be the same.
   --  Note that if the source list is empty, then the target will be set empty.
   --
   --  Two lists can be compared for equality. To be equal they must have equal data elements
   --  at corresponding positions. Two empty lists are considered equal.
   --
   --  The elements in a list can be accessed via an enumerator: the client software
   --  declares a variable of type Enumerator_Type which it then attaches to a list via
   --  the function New_Enumerator.
   --
   --  At any one time an enumerator denotes a single element in its associated list. This
   --  element is termed the "current" element. Initially current will be set to the first
   --  element in the list; the following subprograms allow current to move to a different
   --  element: Goto_Next, Goto_Previous, Goto_First, Goto_Last.
   --
   --  The following subprograms allow an enumerator's current element to be retrieved,
   --  changed, or deleted: Current, Update, Delete. Note that after Delete, current
   --  still denotes the same point in the list, even though the associated data
   --  element no longer exists.
   --
   --  The subprogram Insert allows a new data element to be added to the list either
   --  before or after the current element. Note that if the list is empty then this
   --  subprogram will still insert the data even though current does not exist.
   --  Alternatively if current has been deleted then Insert will insert the data at
   --  the point in the list from which current was deleted.
   --  After the insertion, current will be set to the new data element.
   --
   --  When current is at the start of a list, Is_First will return True,
   --  otherwise it will return False.
   --  When current is at the end of a list,   Is_Last  will return True,
   --  otherwise it will return False.
   --
   --  If current exists Current_Exists will return True, otherwise it will return False
   --  (current will not exist if the element denoted by current has been deleted, or if
   --  the associated list is empty).
   --
   --  If the list associated with an enumerator exists List_Exists will return True, otherwise
   --  it will return False (a list can cease to exist if the list's variable goes out of scope).
   --
   --  An enumerator can be assigned to another enumerator. The target enumerator will then
   --  be associated with the same list and denote the same current element. Note that
   --  if the source enumerator's list and/or current do not exist then these characteristics
   --  will be transferred to the target enumerator.
   --
   --  Two enumerators can be compared for equality. They must be associated with the same
   --  list and their current elements must be the same element. Note that two enumerators whose
   --  lists do not exist are deemed equal. Also two enumerators whose lists exist but whose current
   --  elements do not, are deemed equal if:
   --   1) the lists are the same and empty; or
   --   2) the lists are the same and non-empty, and each current denotes the same point in the list.
   --
   --  Note that two or more enumerators can change the same list; changes made via one enumerator
   --  will be visible to the other enumerators. Similarly changes made directly to a list will be
   --  visible to its enumerators. However, concurrent access from more than one task is not supported;
   --  concurrent access may well lead to list and enumerator corruption.
   --
   --  Note also that the storage associated with lists and enumerators is automatically deallocated
   --  when their variables go out of scope.
   --
   --  Stream input/output can be used with lists via the stream oriented attributes List_Type'Write
   --  and List_Type'Read.
   --  For the Write attribute, each data element in the list is sent to the stream via
   --  Data_Type'Output.
   --  For the Read attribute, data elements are extracted from the stream (via Data_Type'Input)
   --  and inserted into the list. Note that any data elements previously in the list will be deleted.
   --  Note also that an empty list will be suitably flagged in the stream data, and so will be
   --  correctly handled when read back in.
   --
   --
   --  When applied to an empty list, the following will raise No_Data:
   --   Goto_First, Goto_Last, Goto_Next, Goto_Previous, Is_First, Is_Last.
   --
   --  When current is the last  data element in a list, Goto_Next     will raise No_Data.
   --  When current is the first data element in a list, Goto_Previous will raise No_Data.
   --
   --  When current does not exist, the following will raise No_Data:
   --   Delete, Current, Update.
   --
   --  When an enumerator's list does not exist, the following will raise No_List:
   --   Insert, Delete, Current, Update, Goto_First, Goto_Last, Goto_Next, Goto_Previous,
   --   Is_First, Is_Last, Current_Exists, Is_Empty[Enumerator_Type].
   --
   --  When the stream I/O attributes are used, the following exceptions may be raised:
   --    Device_Error, Data_Error, Constraint_Error, Tag_Error, End_Error and Mode_Error.
   --  See the Ada Reference Manual for details.
   --
   ------------------------------------------------------------------------------------------------

   type List_Type       is tagged private;
   type Enumerator_Type is        private;

   --  Subprograms for directly dealing with lists...

   procedure Prepend       (List  : in out List_Type; Data : in Data_Type);   -- Insert data at start of list.
   procedure Append        (List  : in out List_Type; Data : in Data_Type);   -- Insert data at end of list.
   procedure Delete_All    (List  : in out List_Type);                        -- Delete all data from list.

   function  Is_Empty      (List  : in     List_Type) return Boolean;
   function  "="           (Left  : in     List_Type;                   -- Check lists have equal.
                            Right : in     List_Type) return Boolean;   -- elements at matching positions.

   function New_Enumerator (List  : in     List_Type'Class) return Enumerator_Type;
   --  Enumerator will denote the list and its current will be the first in the list.

   --  Note: can also assign list to list: target list will contain a copy of all the elements in the source
   --  list, with each element and its copy having the same position in their respective lists.
   ----------------------------------------------------------------------

   --  Subprograms for dealing with the current element of an enumerator...

   type Position_Type is (Before_Current, After_Current);

   procedure Insert         (Enumerator : in out Enumerator_Type;
                                   Data : in Data_Type;
                                   Position : in Position_Type);
   procedure Delete         (Enumerator : in     Enumerator_Type);
   function  Current        (Enumerator : in     Enumerator_Type) return Data_Type; 

   procedure Update         (Enumerator : in out Enumerator_Type; Data : in Data_Type);
   --  Update current element.
   --  Note that if new data is larger, then new data will be loaded into a new element that replaces
   --  the old in the list. The location in the list will not have changed but current will now denote
   --  that new data element - hence the in out mode.

   procedure Goto_First     (Enumerator : in out Enumerator_Type); 
   procedure Goto_Last      (Enumerator : in out Enumerator_Type);
   procedure Goto_Next      (Enumerator : in out Enumerator_Type);
   procedure Goto_Previous  (Enumerator : in out Enumerator_Type);

   function  Is_First       (Enumerator : in     Enumerator_Type) return Boolean;
   function  Is_Last        (Enumerator : in     Enumerator_Type) return Boolean;

   function  Current_Exists (Enumerator : in     Enumerator_Type) return Boolean;
   function  List_Exists    (Enumerator : in     Enumerator_Type) return Boolean;

   function  Is_Empty       (Enumerator : in     Enumerator_Type) return Boolean;
   -- Is the associated list empty.


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

   --  Note: can also assign enumerator to enumerator: target will denote same list
   --  and have same current as source.
   --------------------------------------------------------

   --  The subprograms can raise the following exceptions:

   No_Data      : exception;
   No_List      : exception;
   
   --  And for stream I/O...
   
   Device_Error : exception renames Ada.IO_Exceptions.Device_Error;
   Data_Error   : exception renames Ada.IO_Exceptions.Data_Error;
   End_Error    : exception renames Ada.IO_Exceptions.End_Error;
   Mode_Error   : exception renames Ada.IO_Exceptions.Mode_Error;
   Tag_Error    : exception renames Ada.Tags.Tag_Error;
   --  Also Constraint_Error may be raised.

   ---------------------------------------------------

private
   type Data_Access_Type is access Data_Type;

   type Data_Envelope_Type;
   type Data_Envelope_Access_Type is access Data_Envelope_Type;

   type Enumerator_Envelope_Type;
   type Enumerator_Envelope_Access_Type is access Enumerator_Envelope_Type;

   type List_Header_Type;
   type List_Header_Access_Type is access List_Header_Type;

   type Data_Envelope_Type is record
      Data     : Data_Access_Type;
      Next     : Data_Envelope_Access_Type;
      Previous : Data_Envelope_Access_Type;
   end record;

   type List_Header_Type is
   record
      First       : Data_Envelope_Access_Type;
      Last        : Data_Envelope_Access_Type;
      Enumerators : Enumerator_Envelope_Access_Type;   -- Sub-list of enumerators attached to this List.
   end record;

   type List_Type is new Ada.Finalization.Controlled with
   record
      Header : List_Header_Access_Type;
   end record;

   procedure Initialize (List : in out List_Type);
   procedure Adjust     (List : in out List_Type);
   procedure Finalize   (List : in out List_Type);

   procedure List_Write (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : in  List_Type);
   for List_Type'Write use List_Write;
   
   procedure List_Read  (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : out List_Type);
   for List_Type'Read use List_Read;


   type Enumerator_Envelope_Type is
   record
      List_Header         : List_Header_Access_Type;           -- List that Enumerator applies to.
      Current             : Data_Envelope_Access_Type;         -- List element that Enumerator denotes.
      Next_Enumerator     : Enumerator_Envelope_Access_Type;   -- Enumerators are linked in their own sub-list,
      Previous_Enumerator : Enumerator_Envelope_Access_Type;   --  within the relevant List.
      Next_Data           : Data_Envelope_Access_Type;         -- List element that follows current.
      Previous_Data       : Data_Envelope_Access_Type;         -- List element that precedes current.
   end record;
   --  Note that in the above record, components Next_Data and Previous_Data duplicate the Next and Previous
   --  components of the record referenced by Current. This duplication is necessary for the case when Current
   --  is Null (ie. the corresponding data element has been deleted), Next_Data and Previous_Data then indicate
   --  where in the list the enumerator is.

   type Enumerator_Type is new Ada.Finalization.Controlled with
   record
      Header : Enumerator_Envelope_Access_Type;
   end record;

   procedure Initialize (Enumerator : in out Enumerator_Type);
   procedure Adjust     (Enumerator : in out Enumerator_Type);
   procedure Finalize   (Enumerator : in out Enumerator_Type);

end Containers.Lists.Unbounded;
-------------------------------------------------------------

Re: List container strawman

[Stephen Leake]

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

> Hmmmmmmm..........
> 
> 
> So basically, you're saying that a library level generic that contained as
> part of it a Controlled element, you'd be able to instantiate it in a
> procedure (non-library level)? But if a data item in it is itself derived
> from Controlled, you can't? (Seems kind of strange, but I'm sure there's
> going to be some corner-case of the rules to explain it.)

The issue is where the Controlled _type_ is declared, not where the
_object_ of that type is declared. The _type_ must be declared at
library level, so pointers to it's base class are at the same level as
Controlled itself.

In this case, the Controlled type is still declared at library level;
the generic instantiation declares another type, which happens to
contain a component object of the Controlled type.

> The Controlled thing clearly can't have anything to do with the

You need to distinguish between declaring the type and declaring the
object. "Thing" is not specific enough.


-- 
-- Stephe

Re: List container strawman

[Darren New]

ramatthews@tinuviel.com wrote:
> While I see a foolproof list does not have universal appeal I have
> been successfully using one for some time so I thought its
> specification would help discussions.

Heh. This looks almost exactly like what I came up with and posted
earlier. :-) Except you've actually written it. ;-)

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

[Jeffrey Carter]

ramatthews@tinuviel.com wrote:
> 
> While I see a foolproof list does not have universal appeal I have
> been successfully using one for some time so I thought its
> specification would help discussions.

How does this extra complexity ensure that the list is foolproof? It is
not clear, for example, how this prevents updating a node through one
Position (which you call Enumerator_Type) that has been deleted through
another.

The initial block of comments is rather a lot to digest all at once, and
might be better distributed among the type and subprogram declarations
it refers to. The use of "current" by itself is a bit confusing; it
sounds as if it is a global property of a list, when actually it is a
property of a position within a list.

Overall, the package looks quite usable. I might suggest a default of
Before_Current in the Insert procedure.

-- 
Jeff Carter
"Sons of a silly person."
Monty Python & the Holy Grail

Re: List container strawman

[Ehud Lamm]

Ted Dennison <dennison@telepath.com> wrote in message
news:WOzE7.10186$xS6.14012@www.newsranger.com...
> In article <9rti6v$hcu$1@news.huji.ac.il>, Ehud Lamm says...
> >2. Why is List private? Shouldn't it be limited private, so we avoid
> >possible erros caused by aliasing?
>
> Ahh. It finally dawned on me what your objection to private was. (I'm a
little
> slow today again.) We are talking about what happens when you do a
> "List1 := List2;", aren't we?


Yep.

And to make things worse the scoping issues with Controlled are really
confusing for beginners.
Now I don't see any reason why newcomers shouldn't be able to reuse standard
containers, but I really don't want to start explaining "controled type must
be declared at library level".
Amusingly, a student just asked about this problem, in my course newsgroup,
trying to reuse a linked list package. They are now just learning about the
basics of ADTs, and Ada packages...

Are we coming to the conclusion that Ada95 approaches to memory management
(Controlled and storage pools), simply aren't enough for creating reliable
components, without imposing inessential restrictions?
We want user created abstractions to be as much like language supplied types
as possible, remember.

Ehud

Re: List container strawman

[Simon Wright]

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

> "List" should be limited, to prevent non-deep copies when Element is
> an access type.

I don't see why you would want to do this specifically? (perhaps I've
misunderstood).

If I make a List of Bank_Account_Access whose 5th element is a pointer
to my bank account, and then make a copy of it, what would you expect
the 5th element of the new List to point to? Better not be a *copy* of
my bank account!

Re: List container strawman

[M. A. Alves]

On Fri, 2 Nov 2001, Ted Dennison wrote:
> Since we do seem to be reaching a small amount of agreement on
> details, . . . I went ahead a put together a strawman package spec
> (sans private part) for the unbounded list container . . .
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> . . .

For some time ago now package Unbounded_Array has been serving me well.  A
public version is at

  http://lexis.di.fct.unl.pt/ADaLIB/misc.htm

and may be worth perusing.  A more recent version exists, if someone is
interest (the indicated version has a little bug, that site is no longer
under my control, I am also looking for web hosting for Adlib, Adlib
itself is changing status).

I would expect PragmArc, a very nice effort for an Ada standard components
library, to have a list containers package also--and very OO as you like
it.

Just my 2 cents for the List Container thread.

Cheers,

-- 
   ,
 M A R I O   data miner, LIACC, room 221   tel 351+226078830, ext 121
 A M A D O   Rua Campo Alegre, 823         fax 351+226003654
 A L V E S   P-4150 PORTO, Portugal        mob 351+939354002

Re: List container strawman

[ramatthews]

In article <3BEA0F08.AD9AB7C1@acm.org>, Jeffrey Carter <jrcarter@acm.org> wrote:

> 
> How does this extra complexity ensure that the list is foolproof? It is
> not clear, for example, how this prevents updating a node through one
> Position (which you call Enumerator_Type) that has been deleted through
> another.
> 

> 


If two Positions (of Enumerator_Type) are denoting the same
element in a list and one is used to delete the element then
BOTH will return False to 'Current_Exists' and BOTH will raise
'No_Data' on using 'Update'.

This is ensured by the (behind the scenes) two-way linkage
between the list and all of its Positions.

As an aside, if I were re-implementing this I would use the
term 'Cursor' in place of 'Enumerator' - but then arguments
over names can go on for ever!

Robert Matthews.

Re: List container strawman

[Jeffrey Carter]

"M. A. Alves" wrote:
> 
> I would expect PragmArc, a very nice effort for an Ada standard components
> library, to have a list containers package also--and very OO as you like
> it.

Yes, I have already mentioned PragmARC.List_Unbounded_Unprotected in
this discussion, and there is also PragmARC.List_Unbounded which is task
safe. There are also unbounded stack and queue components built on the
list component, and bounded queue components.

-- 
Jeffrey R. Carter
PragmAda Software Engineering

Re: List container strawman

[Ted Dennison]

In article <9sdnb2$dd4$1@news.huji.ac.il>, Ehud Lamm says...
>
>Now I don't see any reason why newcomers shouldn't be able to reuse standard
>containers, but I really don't want to start explaining "controled type must
>be declared at library level".

To make matters worse, that isn't even where you'd have to start. You'd have to
start by talking about tagged types and declaration levels, then move to the
fact that controlled is a tagged type declared at the library level. :-)

>Are we coming to the conclusion that Ada95 approaches to memory management
>(Controlled and storage pools), simply aren't enough for creating reliable
>components, without imposing inessential restrictions?

I don't think there's anything horribly wrong with the rest of the language, but
we can certianly come to the conclusion that the way Controlled is currently
implemented blows. I've said as much to any who would listen for about the last
year or so. However, I would like to agree with Nick's point that my contempt is
aimed solely at the feature in its current state, not the folks who worked on
the language design. I could easily see where this consequence was either not
forseen, or it wasn't realised how big of a problem the restriction 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

[Ehud Lamm]

Ted Dennison <dennison@telepath.com> wrote in message
news:72SG7.18851$xS6.30225@www.newsranger.com...
> However, I would like to agree with Nick's point that my contempt is
> aimed solely at the feature in its current state, not the folks who worked
on
> the language design. I could easily see where this consequence was either
not
> forseen, or it wasn't realised how big of a problem the restriction would
be.
>

I am sure we can all agree that no one here feels contempt for the Ada95
designers.

Ehud

Re: List container strawman

[Marin David Condic]

Aside from the restrictions, I've found it to be just plain buggy. By
combining Controlled with other features, either Controlled breaks, or the
other features break. Granted, the experience I have, has only been with a
handful of versions of a single compiler, but because it seems to kill
things in new and interesting ways in a variety of settings, I begin to
wonder if the feature is just simply not reliable in its current design.

We need something very much like Controlled, but perhaps it is possible to
design something that is a little less restrictive and/or a little easier to
make reliable?

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:72SG7.18851$xS6.30225@www.newsranger.com...
>
> I don't think there's anything horribly wrong with the rest of the
language, but
> we can certianly come to the conclusion that the way Controlled is
currently
> implemented blows. I've said as much to any who would listen for about the
last
> year or so. However, I would like to agree with Nick's point that my
contempt is
> aimed solely at the feature in its current state, not the folks who worked
on
> the language design. I could easily see where this consequence was either
not
> forseen, or it wasn't realised how big of a problem the restriction would
be.
>

Re: List container strawman

[Ted Dennison]

In article <po0cs9.dt.ln@127.0.0.1>, ramatthews@tinuviel.com says...
>
>In article <bgR13FMw5mIK@eisner.encompasserve.org>, Kilgallen@SpamCop.net (Larry Kilgallen) wrote:
>> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com> writes:
>> 
>>> If you really want it to be foolproof,
>> 
>> Yes please.
>
>
>While I see a foolproof list does not have universal appeal I have
>been successfully using one for some time so I thought its 
>specification would help discussions.

Yup. That does exactly what is needed to make it safe. I never said it was
impossible, just that its a lot of work, inculding some extra runtime work that
might not endear the facility to real-time users. One problem is that creating
an iterator with this facility involves dynamic allocation and linked-list
traversal. That violates our general principle of avoiding runtime vs. setup
overhead, but that could probably(?) be fixed or at least avoided by the user if
noted. Another issue is that it puts a controlled type in the generic package,
which I was trying to avoid so that it was instantiateable at lower levels.
However, it turned out that List has to be controlled anyway, so perahps this
isn't so bad.

I'm interested in what the general consensus is here. Should we do the extra
work to make iterators safe, given that this will have at least the following
effects:

o  Add extra dynamic memory operations to any list modification (there were some
there already).
o  Add a (usually small) internal list traversal to any element deletion.
o  Add a small validity check (or possibly two) to every iterator operation.
o  Possibly make iterator creation non-determistic (time-wise).
o  Possibly make iterator assignment non-deterministic. Note that functions are
currently used for iterating, so that would make just about any use of iterators
non-determinstic, unless procedure variants are introduced.

If there's a way to get rid of the last two "possibly"s (which there probably
is, but I don't know), I think I'd vote in favor of it. Otherwise I'd lean
against it just on the basis that I don't generaly go for one small
"nice-to-have" feature accounting for large amounts of the implmentation's code
and complexity, which is what would happen here.

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

[Ted Dennison]

In article <9sh2qq$nu6$1@nh.pace.co.uk>, Marin David Condic says...
>
>Aside from the restrictions, I've found it to be just plain buggy. By
>combining Controlled with other features, either Controlled breaks, or the
>other features break. Granted, the experience I have, has only been with a
>handful of versions of a single compiler, but because it seems to kill
>things in new and interesting ways in a variety of settings, I begin to
>wonder if the feature is just simply not reliable in its current design.

I've often found trouble when doing complicated or unusual things with the
language with any compiler. Perhaps what you are seeing is just a combination of
the fact that, as Robert pointed out, Controlled is tricky to implement
properly, and the fact that as designed it isn't as useful (and therefore as
exercised in compilers) as it could 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

[Jean-Marc Bourguet]

Ted Dennison<dennison@telepath.com> writes:

> In article <po0cs9.dt.ln@127.0.0.1>, ramatthews@tinuviel.com says...
> > In article <bgR13FMw5mIK@eisner.encompasserve.org>, Kilgallen@SpamCop.net
> >(Larry Kilgallen) wrote:
> >> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com>
> >>writes:
> >> 
> >>> If you really want it to be foolproof,
> >>  Yes please.
> >
> >
> >While I see a foolproof list does not have universal appeal I have been
> >successfully using one for some time so I thought its specification would
> >help discussions.
> 
> Yup. That does exactly what is needed to make it safe. I never said it was
> impossible, just that its a lot of work, inculding some extra runtime work
> that might not endear the facility to real-time users. One problem is that
> creating an iterator with this facility involves dynamic allocation and
> linked-list traversal. 

Why do you need dynamic allocation.  The pointer can be in the
iterator and put at the start of the list.  As most lists have few
iterators and when they have more than one, a majority of the uses are
nested the list traversal will be done only on list modifications.

> That violates our general principle of avoiding
> runtime vs. setup overhead, but that could probably(?) be fixed or at least
> avoided by the user if noted. Another issue is that it puts a controlled
> type in the generic package, which I was trying to avoid so that it was
> instantiateable at lower levels.  However, it turned out that List has to
> be controlled anyway, so perahps this isn't so bad.
> 
> I'm interested in what the general consensus is here. Should we do the
> extra work to make iterators safe, given that this will have at least the
> following effects:

I'm for.
 
> o Add extra dynamic memory operations to any list modification (there were
> some there already).  

I don't think so.

> o Add a (usually small) internal list traversal to any element
> deletion.

Agree.

> o Add a small validity check (or possibly two) to every iterator
> operation.

Agree.

> o Possibly make iterator creation non-determistic (time-wise).  

I don't think so. (Iterator deletion would be made non deterministic
if they are assigned in a non nested way and the iterator list is a
singly linked one).

> o Possibly make iterator assignment non-deterministic. 

Not if the iterator list is doubly linked.

-- 
Jean-Marc

Re: List container strawman

[Ted Dennison]

In article <mailman.1005231504.1899.comp.lang.ada@ada.eu.org>, M. A. Alves
says...
>For some time ago now package Unbounded_Array has been serving me well.  A
>public version is at
>
>  http://lexis.di.fct.unl.pt/ADaLIB/misc.htm

I wouldn't be adverse to us doing something like that in a separate package (eg:
Containers.Vector if I use STL lingo). The implementation for using direct
indexing in Lists would probably be too inneficient to bother with though. But I
could see another package implementing a big chunk of contiguous storage, where
things like extending the size can be arbitrarily expensive but direct indexing
is O(1).

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

[Matthew Heaney]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9sh2qq$nu6$1@nh.pace.co.uk...
> Aside from the restrictions, I've found it to be just plain buggy. By
> combining Controlled with other features, either Controlled breaks, or the
> other features break. Granted, the experience I have, has only been with a
> handful of versions of a single compiler, but because it seems to kill
> things in new and interesting ways in a variety of settings, I begin to
> wonder if the feature is just simply not reliable in its current design.

Well, I can only speak from my experience (several versions of GNAT), but I
have never had a problem with Controlled types.

Which features "break" when you use Controlled?

Re: List container strawman

[Ted Dennison]

In article <3bec1cbe$0$15824$626a54ce@news.free.fr>, Jean-Marc Bourguet says...
>
>Ted Dennison<dennison@telepath.com> writes:
>
>Why do you need dynamic allocation.  The pointer can be in the

The implementation he presented (a working one, I believe) had it. Since I've
only thought about it before, and he's actually implemented it, I'm assuming
there's some implementation reason he needed to do it that way that isn't
apparent just looking at a spec. Perhaps there isn't. That's what I'd like to
hear.

>> o Add extra dynamic memory operations to any list modification (there were
>> some there already).  
>
>I don't think so.

Hmmm. Yeah, your'e right. Its actually another one of those "ususally small"
internal list traversals. What will happen is that you have to check all other
iterators. But that's probably only nessecary when an item is deleted, which I
covered below.

>> o Add a (usually small) internal list traversal to any element
>> deletion.
>
>Agree.
>
>> o Add a small validity check (or possibly two) to every iterator
>> operation.
>
>Agree.
>
>> o Possibly make iterator creation non-determistic (time-wise).  
>
>I don't think so. (Iterator deletion would be made non deterministic
>if they are assigned in a non nested way and the iterator list is a
>singly linked one).

I said "probably" this for both the last bulletts because he implemented
iterators using accesses to controlled types. If it can be done on the stack,
then both these "possibly"s go away (and I would thus vote for it).

Perhaps it would be best if I could play with an implementation and see if its
doable. That would mean I'd have to tear myself away from Civ3 for a few hours
though...

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

[Larry Kilgallen]

In article <DQUG7.19137$xS6.31310@www.newsranger.com>, Ted Dennison<dennison@telepath.com> writes:

> I'm interested in what the general consensus is here. Should we do the extra
> work to make iterators safe, given that this will have at least the following
> effects:

For my world, I favor safety over efficiency.

I have already decided not to use assembly language, and despite a lack
of demand from me, "they" keep making the computers faster.

I understand that some might have use for a more efficient package,
but I believe the one promulgated to the masses should be the one
with maximum error detection.

Re: List container strawman

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

I vote for having a truly safe list implementation, like this one, if
only for reference. I vote for also having an Unchecked_List package,
so we can use it in higher-level abstractions that add safety in
different ways.

That way, when someone says "why isn't this list package _safe_? I
thought Ada was a _safe_ language!", we can say "look at the safe list
package; it has too much overhead for _this_ use, but it's available
if you want it".

It might also inspire some grad student to make a version with less
overhead, or a compiler optimization that removes the overhead, or
something.

-- 
-- Stephe

Re: List container strawman

[Ted Dennison]

In article <u7kszpv8k.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>Ted Dennison<dennison@telepath.com> writes:
>
>I vote for having a truly safe list implementation, like this one, if
..

Just to make things perfectly clear, these are Stephen's words, not mine. I'm
sure he wasn't confused about this, but someone else might 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

[Larry Kilgallen]

In article <u7kszpv8k.fsf@gsfc.nasa.gov>, Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:
> Ted Dennison<dennison@telepath.com> writes:
> 
> I vote for having a truly safe list implementation, like this one, if
> only for reference. I vote for also having an Unchecked_List package,
> so we can use it in higher-level abstractions that add safety in
> different ways.
> 
> That way, when someone says "why isn't this list package _safe_? I
> thought Ada was a _safe_ language!", we can say "look at the safe list
> package; it has too much overhead for _this_ use, but it's available
> if you want it".

Then how about naming the packages Safe_List and Unchecked_List ?

Is it possible for them to have the same profile, allowing people
to switch easily if they change their mind or need to debug ?

Re: List container strawman

[Nick Roberts]

I'm sorry, I'm throw one of classic spanners in the works here, but I'm
afraid I think you've got your approach horribly horribly wrong!

For a start, all this mularchy about insertion and deletion is just plain
silly! It really is. You don't need them, and shouldn't implement them. Yes,
really. Let me show you why.

Suppose you want to have a list of names (strings), and you want to
normalise them as follows:

(a) convert them all to uppercase;
(b) all beginning with "MACxy", where x is a letter, to have "MCxy" inserted
afterwards;
(c) all beginning with "?" to be deleted.

I'm going to frame the answer in terms of my own proposal, please forgive me
for that. The essential answer is that you don't keep a list of the strings,
but you keep a list of access values to them. You then simply build a new
list (of access values), and then delete the old one:

   with Ada.Characters.Handling; use Ada.Characters.Handling;
   ...
   type Name_Ref is access [all] String;
   package Name_Ref_Iteration is new Iteration(Name_Ref);

   procedure Normalize_Names (
      From: in out Name_Ref_Iteration.Sequence_Recorder'Class;
      Into: Name_Ref_Iteration.Sequence_Recorder'Class) is
      Ref: Name_Ref; N: Natural;
   begin
      Rewrite(Into); -- possibly redundant (possibly poor design, actually)
      Restart(From); -- ditto
      while not End_of_Data(From) loop
         Read(From,Ref);
         if Ref /= null and then Ref.all'Length > 0 and then
Ref(Ref.all'First) /= '?' then
            To_Upper(Ref.all);
            Write(Into,Ref);
            N := Ref.all.First-1; -- in case string doesn't start at 1
            if Ref.all'Length >= 5 and then Ref(N+1..N+3) = "MAC" and then
Is_Letter(Ref(N+4)) then
               Write(Into, new String'("MC"&Ref(N+4..Ref.all'Last)));
            end if;
         else
            Ref := null; -- or maybe use Unchecked_Deallocation
         end if;
      end loop;
      Rewrite(From); -- erases it (again, possibly wrong here)
      Restart(Into); -- again possibly redundant
   end Normalize_Names;

Note how this procedure can be passed parameters of ANY 'sequence recorder'
container type (instantiated on Name_Ref), not just lists. Supposing we
wanted to use a list container type:

   package Name_Ref_Lists is new xyz.Lists(Name_Ref_Iteration);
   subtype Name_List is Name_Ref_Lists.List_Type;
   L1, L2: Name_List;
   ... set up L1 with names
   Normalize_Names(L1,L2);

A note about the Restarts and Rewrites: they are probably better left
outside procedures such as this, in fact. I have quietly deleted oddities
like null pointers: a real program should probably raise exceptions.

Trust me, guys, this approach is majorly better in every way (easier to use,
easier to read & understand, easier to implement, more memory efficient,
more speed efficient) than messing around with inserts and deletes, for the
vast majority of situations.

I know I can seem pompous, overbearing, etc., etc., especially about this
subject, but it pains me to see you going so far astray, and spending so
much time arguing about features that you don't need anyway!

It also gives me another opportunity to demonstrate the idea of having a set
of abstract container types, upon which operations (such as Normalize_Names)
can be hung, thus freeing you of: (1) having to worry about which container
type to use when writing the procedure; (2) the procedure shackling you to
one particular container type. Do you turn away from this Utopia? ;-)

--
Best wishes,
Nick Roberts

Re: List container strawman

[Nick Roberts]

"Larry Kilgallen" <Kilgallen@SpamCop.net> wrote in message
news:RyJAqQJQiv6e@eisner.encompasserve.org...
> ...
> Is it possible for them to have the same profile, allowing people
> to switch easily if they change their mind or need to debug ?

The answer to this is yes: by basing them both on an abstract type.

(On the other hand, I've demonstrated in another post in this thread that
you don't need insert or delete anyway.)

--
Nick Roberts

Re: List container strawman

[Ted Dennison]

In article <9sib27$13aeg3$5@ID-25716.news.dfncis.de>, Nick Roberts says...
>For a start, all this mularchy about insertion and deletion is just plain
>silly! It really is. You don't need them, and shouldn't implement them. Yes,
>really. Let me show you why.

I'm not sure I understand this. It looks like you are talking about having the
users manage the internal details of all their own data structures, to which my
first reaction would be "ewwwww.". I'll admit there may be some interesting
possiblities I don't see in this though.

>It also gives me another opportunity to demonstrate the idea of having a set
>of abstract container types, upon which operations (such as Normalize_Names)
>can be hung, thus freeing you of: (1) having to worry about which container
>type to use when writing the procedure; (2) the procedure shackling you to
>one particular container type. Do you turn away from this Utopia? ;-)

But remember that one of our stipulations is essentially "no multilevel generic
instantiations required". Does this work that way? Without that restriction you
could do all sorts of cool things, as has been done in Booch and others. In that
enviroment I'd say that we already have plenty of players, and one of them is
liable to be perfectly suitable (although I suppose more are always welcome). I
don't want to discourage you from making the ultimate container library. But for
the purposes of what we are doing here it has to be very easy to use, and
frankly I couldn't figure out quite what was going on in the code you presented.

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

[Simon Wright]

"Matthew Heaney" <mheaney@on2.com> writes:

> Well, I can only speak from my experience (several versions of
> GNAT), but I have never had a problem with Controlled types.
> 
> Which features "break" when you use Controlled?

I don't remember the exact details, but I see a remark in the BC's
release notes:
  Iterators are visibly Controlled. The Controlled bit is because of
  work on synchronized forms, and the visible bit is because of a GNAT
  3.13 problem with finalization when using a function return value to
  initialize a classwide value.

.. GNAT's WITH TYPE sometimes fails when you have a record which
contains a field of a WITH TYPE IS ACCESS type and a field of a
controlled type and you create an access type for the record and you
try to use a non-standard storage pool ..

.. like Ted said, it can take some poking at extreme cases to get this
stuff to show!

Re: List container strawman

[Ehud Lamm]

Nick Roberts <nickroberts@adaos.worldonline.co.uk> wrote in message
news:9sib27$13aeg3$5@ID-25716.news.dfncis.de...
>
> It also gives me another opportunity to demonstrate the idea of having a
set
> of abstract container types, upon which operations (such as
Normalize_Names)
> can be hung, thus freeing you of: (1) having to worry about which
container
> type to use when writing the procedure; (2) the procedure shackling you to
> one particular container type. Do you turn away from this Utopia? ;-)


These goal are vrey worthy. In fact they are one of the reasons people want
inheritance.
Problem is that we are looking for a way of achieving these goal, without
making newcomers struggle with nested instatiations, and complexities of the
Ada tagged type approach (freezing, scope of access types etc. etc.)
Perhaps I missed the point - but does your approach solve the dillema?

Ehud

Re: List container strawman

[Ehud Lamm]

This is indeed a useful abstraction.

Ehud

Re: List container strawman

[Nick Roberts]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9sjvrl$2pd$1@news.huji.ac.il...
> ...
> These goal are vrey worthy. In fact they are one of the reasons people
want
> inheritance.
> Problem is that we are looking for a way of achieving these goal, without
> making newcomers struggle with nested instatiations, and complexities of
the
> Ada tagged type approach (freezing, scope of access types etc. etc.)
> Perhaps I missed the point - but does your approach solve the dillema?

I thought we were agreed that there was no way to achieve the goals (of
decoupling) without the multiple instantiations. In any case, I believe that
is so, and I suppose I am trying to convince people that it's (very much!)
the lesser of two evils to have the multiple instantiations and the
decoupling. I really think this is a case where the apparently easier way is
in fact the harder one.

--
Best wishes,
Nick Roberts

Re: List container strawman

[ramatthews]

In article <DQUG7.19137$xS6.31310@www.newsranger.com>, Ted Dennison<dennison@telepath.com> wrote:

> 
> I'm interested in what the general consensus is here. Should we do the extra
> work to make iterators safe, given that this will have at least the following
> effects:
> 
> o  Add extra dynamic memory operations to any list modification (there were some
> there already).
> o  Add a (usually small) internal list traversal to any element deletion.
> o  Add a small validity check (or possibly two) to every iterator operation.
> o  Possibly make iterator creation non-determistic (time-wise).
> o  Possibly make iterator assignment non-deterministic. Note that functions are
> currently used for iterating, so that would make just about any use of iterators
> non-determinstic, unless procedure variants are introduced.
> 

You express some implementation concerns that, for the implementation
I have to hand, I hope I can clarify.

The list contains two doubly-linked lists: one for the data, the
other for the enumerators (also called Iterators and Positions in
this discussion on cla). The enumerators list is traversed when the following
subprograms are called: Prepend, Append, Delete_All, Insert, Delete and
Finalize (for a list). In addition Update will cause a traversal of the
enumerators list when the new value cannot be assigned to the existing
data element (eg when the new value has a different tag); in this case
the new value is assigned to a new data element and the old data element
deleted - hence the need to update the enumerators. (Note that the
package specification gives an incorrect comment on this).

When a list is declared in client code, two data items are created:
(1) the list that the client code directly sees (List_Type), and
(2) the list header (List_Header_Type) that is created on the heap.
A similar situation exists for an enumerator (Enumerator_Type and
the heap held Enumerator_Envelope_Type). This split was made, on stylistic
grounds, to avoid use of the attribute Unchecked_Access in the body.

Having 'safe' enumerators does introduce some extra checking. For example
when retrieving the data denoted by an enumerator the subprogram 'Current'
checks:
(1) that the enumerator's list exists: "Enumerator.Header.List_Header /= null",
(2) that the data exists: "Enumerator.Header.Current /= null".

Enumerator creation, assignment and finalization involves manipulation of
the affected enumerator lists - but does not require list traversal.

Robert Matthews.

Re: List container strawman

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:L6dH7.20105$xS6.32596@www.newsranger.com...
> In article <9sib27$13aeg3$5@ID-25716.news.dfncis.de>, Nick Roberts says...
> >For a start, all this mularchy about insertion and deletion is just plain
> >silly! It really is. You don't need them, and shouldn't implement them.
Yes,
> >really. Let me show you why.
>
> I'm not sure I understand this. It looks like you are talking about having
the
> users manage the internal details of all their own data structures, to
which my
> first reaction would be "ewwwww.". I'll admit there may be some
interesting
> possiblities I don't see in this though.

In general, of course, you want to hide details such as pointers. But don't
get carried away! Sometimes the application programmer has got to deal with
things like pointers.

In the example I gave, the fact that the list container was used to
(explicitly) contain pointers is likely to actually have many advantages for
the application programmer: other manipulations of the data - not involving
containers - can also be carried out more efficiently (and sometimes more
conveniently) using those same pointers.

> >It also gives me another opportunity to demonstrate the idea of having a
set
> >of abstract container types, upon which operations (such as
Normalize_Names)
> >can be hung, thus freeing you of: (1) having to worry about which
container
> >type to use when writing the procedure; (2) the procedure shackling you
to
> >one particular container type. Do you turn away from this Utopia? ;-)
>
> But remember that one of our stipulations is essentially "no multilevel
generic
> instantiations required". Does this work that way? Without that
restriction you
> could do all sorts of cool things, as has been done in Booch and others.
In that
> enviroment I'd say that we already have plenty of players, and one of them
is
> liable to be perfectly suitable (although I suppose more are always
welcome). I
> don't want to discourage you from making the ultimate container library.
But for
> the purposes of what we are doing here it has to be very easy to use, and
> frankly I couldn't figure out quite what was going on in the code you
presented.

I'm not quite trying to make 'the ultimate library' ;-) but I suppose I am
aiming at something that would be useful for 'real' programming, rather than
just for students and demos. Ada is not a toy language, it's not a Pascal or
BASIC, it's an industrial language intended for building real, big software.
Honestly, I think it's a mistake to try to defend students (or anyone else)
from this fact.

When we make a wooden box for the first time in kindergarten we use one nail
per joint. As grown ups, when we make a box for some real purpose, we use
two nails per joint. When making toy programs at university we may have used
one instantiation per data type; but when as professionals we start writing
real software, we use two instantiations per data type! (It's all a part of
the maturing process ;-)

At the end of the day, a box that falls to pieces (because you only used one
nail) doesn't make life easier for anyone. As I say in my reply to Ehud, I
really believe this is a situation where trying to make things easier for
the user will end up making things much harder for them.

To me, you really seem to be saying something like "Oh, there shouldn't be
any safety catches on guns: it makes them too complicated for the user! Our
guns have just the trigger and nothing else." It may sound nice, but you are
inevitably going to cause of lot of users to end up shooting themselves (in
the foot, or worse :-)

I hope you'll forgive me if I re-post the code I gave, corrected and cleaned
up a little, and with a blow-by-blow commentary on what's going on.

   with Ada.Characters.Handling; use Ada.Characters.Handling;

This is to conveniently obtain some character-handling functions provided by
Ada.

   type Name_Ref is access [all] String;

Here we declare the access type that is going to be the 'data type' stored
by containers.

   package Name_Ref_Iteration is new Iteration(Name_Ref);

This instantiates the package of abstract container types (including
Sequence_Recorder), so that they are specialised for Name_Refs (but they are
still abstract).

   procedure Normalize_Names (
      Source: in out Name_Ref_Iteration.Sequence_Recorder'Class;
      Target: in out Name_Ref_Iteration.Sequence_Recorder'Class) is

Source and Target are both in the class of the abstract container type
Sequence_Recorder. This means that the corresponding actuals, when the
procedure is called, must be (concrete types) derived from
Sequence_Recorder, and therefore that they must, at the very least,
implement the procedures Read, Restart, Rewrite, and Write, and the function
End_of_Data.

      Ref: Name_Ref;
      N: Natural;

Just a couple of temporary variables.

   begin
      while not End_of_Data(Source) loop

We will iterate over the elements (name pointers, of type Name_Ref) in the
Source container.

         Read(Source,Ref);

We read one reference in from the Source container. This is a dispatching
call: the correct Read for the actual container will be called.

         if Ref /= null and then Ref.all'Length > 0 and then
Ref(Ref.all'First) /= '?' then

This just checks various conditions to ensure the name pointer (in Ref) is
usable, and not to be deleted (indicated by the leading '?').

            To_Upper(Ref.all);

Convert the string (pointed to by the pointer in Ref) to uppercase.

            Write(Target,Ref);

Write the pointer into the Target container. Again, this is a dispatching
call.

            N := Ref.all.First-1; -- in case string doesn't start at 1
            if Ref.all'Length >= 5 and then Ref(N+1..N+3) = "MAC" and then
Is_Letter(Ref(N+4)) then
               Write(Target, new String'("MC"&Ref(N+4..Ref.all'Last)));
            end if;

This is just a bit of messing about with the Macs. The important thing to
note is that another Write may be performed, thus achieving the effect of
insertion.

         else
            Ref := null; -- or maybe use Unchecked_Deallocation

The effect of deletion is achieved by simply not writing the pointer into
Target.

         end if;
      end loop;
   end Normalize_Names;

The usage of this procedure, in conjunction with a (concrete) list container
type (which we assume is derived from Sequence_Recorder), might be:

   package Name_Ref_Lists is new SCL.Lists.Unbounded(Name_Ref_Iteration);

Now we instantiate the package that will export a list type for use
(List_Type) wich is specialised for name pointers (type Name_Ref).

   subtype Name_List is Name_Ref_Lists.List_Type;

This just conveniently renames the exported list type.

   L1, L2: Name_List;

Here we declare two list variables.

   ... set up L1 with names

We will do something (not shown, but e.g. read a file) to read the names,
and put the pointers to them into L1.

   Rewrite(L2);

This prepares (and erases, if necessary) L2 for being written into.

   Restart(L1);

This prepares (and rewinds to the start, if necessary) L1 for being read
from.

   Normalize_Names(L1,L2);

We call the procedure. The actuals, L1 and L2, could have been of any
container type (provided they were both derived from Sequence_Recorder). In
this case, they happen to both be lists.

   Rewrite(L1);

This is just a simple way to erase L1.

   Restart(L2);

Get L2 ready to be read, for the next step in the overall processing
(whatever that might be).

I really hope this helps clarify things. The vital point is that the
procedure Normalize_Names can be used with any container type (derived from
Sequence_Recorder), rather than being permanently tied down to one container
type.

--
Best wishes,
Nick Roberts

Re: List container strawman

[Larry Hazel]

Nick Roberts wrote:
> 
> I hope you'll forgive me if I re-post the code I gave, corrected and cleaned
> up a little, and with a blow-by-blow commentary on what's going on.
> 
This mostly looks very good to me except it seems terribly inefficient to have
to copy the whole list into a new list then delete the old list if all I need to
do is modify a few entries, delete a few others and insert a few.  Seems as if
we still need methods to delete, update, and insert elements.

Larry

Re: List container strawman

[Nick Roberts]

"Larry Hazel" <lhhazel@otelco.net> wrote in message
news:3BEDB57E.1203D638@otelco.net...
> Nick Roberts wrote:
> >
> > I hope you'll forgive me if I re-post the code I gave, corrected and
cleaned
> > up a little, and with a blow-by-blow commentary on what's going on.
> >
> This mostly looks very good to me except it seems terribly inefficient to
have
> to copy the whole list into a new list then delete the old list if all I
need to
> do is modify a few entries, delete a few others and insert a few.  Seems
as if
> we still need methods to delete, update, and insert elements.

In fact, I completely agree with you. It was extremely clumsy of me to
simply say "you don't need inserts or delete". You do. What you don't need
is insert or delete in association with an iterator (or a separate iterator
type at all). All you need are straightforward insert and delete functions
and procedures that identify the position of insertion or deletion with a
number (type Positive), starting at 1 for the first item in the list.

Detail: A container object would have three modes: seq read; seq write;
normal. Calling Read or End_of_Data other than in seq read mode, or calling
Write or Terminate_Data other than in seq write mode, would raise an
exception (SCL.Exceptions.Mode_Error). Restart causes a switch to seq read
mode. Rewrite causes a switch to seq write mode. Any other operation when
not in normal mode causes a switch to normal mode. This way, non-sequential
modification cannot interfere with iteration. Simple.

Doing the equivalent of what my example procedure Normalize_Names did using
inserts and deletes with an iterator would have ended up with code that was
more difficult to program, more difficult to read, slower in execution, and
(I think) more wasteful of memory. Showing this was the true purpose of my
example. Admittedly, I really need to add more detail, but it's finding the
time :-(

--
Best wishes,
Nick Roberts

Re: List container strawman

[Darren New]

Nick Roberts wrote:
> Doing the equivalent of what my example procedure Normalize_Names did using
> inserts and deletes with an iterator would have ended up with code that was
> more difficult to program, more difficult to read, slower in execution, and
> (I think) more wasteful of memory. Showing this was the true purpose of my
> example. Admittedly, I really need to add more detail, but it's finding the
> time :-(

Using sequences like this when the problem is expressed in terms of a
loop over all elements makes sense. Using sequences when the problem is
expressed in other forms may not. If your list is a list of characters
that you're trying to parse, for example, matching up parens or doing
reg-exp sorts of stuff (yes, I know you'd use strings) then only doing
reads *or* writes, only going in one direction doesn't make good sense.
If you have an ordered list and you want to insert an element in the
right place, copying the entire list to do so isn't very efficient.

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

Re: List container strawman

[Nick Roberts]

"Darren New" <dnew@san.rr.com> wrote in message
news:3BF01760.A21F56B3@san.rr.com...
> Nick Roberts wrote:
> > Doing the equivalent of what my example procedure Normalize_Names did
using
> > inserts and deletes with an iterator would have ended up with code that
was
> > more difficult to program, more difficult to read, slower in execution,
and
> > (I think) more wasteful of memory. Showing this was the true purpose of
my
> > example. Admittedly, I really need to add more detail, but it's finding
the
> > time :-(
>
> Using sequences like this when the problem is expressed in terms of a
> loop over all elements makes sense. Using sequences when the problem is
> expressed in other forms may not. If your list is a list of characters
> that you're trying to parse, for example, matching up parens or doing
> reg-exp sorts of stuff (yes, I know you'd use strings) then only doing
> reads *or* writes, only going in one direction doesn't make good sense.
> If you have an ordered list and you want to insert an element in the
> right place, copying the entire list to do so isn't very efficient.

In essence, I agree, and I've devised a new proposal with bi-directional
cursor operations. Hopefully I'll have this ready to send to Ted Dennison in
a couple of days time, for him to kindly put on his web site.

--
Best wishes,
Nick Roberts

Re: List container strawman

[Stephen Leake]

Simon Wright <simon@pushface.org> writes:

> Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:
> 
> > "List" should be limited, to prevent non-deep copies when Element is
> > an access type.
> 
> I don't see why you would want to do this specifically? (perhaps I've
> misunderstood).
> 
> If I make a List of Bank_Account_Access whose 5th element is a pointer
> to my bank account, and then make a copy of it, what would you expect
> the 5th element of the new List to point to? Better not be a *copy* of
> my bank account!

Good example. But there are many other examples where copying a list
does _not_ make sense. For example, if I have a list of controls in a
GUI dialog box, and I pop up another dialog box, I want a list of
_new_ controls, not the same ones.

So the base list container must allow the user to control the copying
process. That means either making it Limited and providing a Copy
operation, or making it Controlled and providing Adjust. In either
case, the user of the package must provide a Copy_Element operation
that does the Right Thing.

-- 
-- Stephe

Re: List container strawman

[Jeffrey Carter]

Stephen Leake wrote:
> 
> Good example. But there are many other examples where copying a list
> does _not_ make sense. For example, if I have a list of controls in a
> GUI dialog box, and I pop up another dialog box, I want a list of
> _new_ controls, not the same ones.

Since an unbounded list creates values of the Element type, assigns to
them, and deallocates them, we must rely on the client to provide an
actual type that handles this properly. If an Element contains a pointer
and the client wants a deep copy, assignment must perform a deep copy.
If the client wants multiple pointers to the same object, assignment
need only copy the pointer. This is not a concern of the list.

-- 
Jeffrey Carter

Re: List container strawman

[Jeffrey Carter]

Stephen Leake wrote:
> 
> So the base list container must allow the user to control the copying
> process. That means either making it Limited and providing a Copy
> operation, or making it Controlled and providing Adjust. In either
> case, the user of the package must provide a Copy_Element operation
> that does the Right Thing.

If the client has to provide an Assign procedure for the Element type,
then the Element type should be limited private. While I have no problem
with this, I think most of the participants in this discussion have
already decided that's too complicated for them.

-- 
Jeffrey Carter

Re: List container strawman

[Nick Roberts]

To my mind (and you need to understand that I live in my own little closeted
world :-) there might be some mileage in providing some generic functions
that provide a deep copy operation:


   generic
      type Element_Type(<>) is private;
      type Access_Type is access Element_Type;

   function SCL.Deep_Copy_by_Access
      (Ref: in Access_Type)
      return Access_Type;


   function SCL.Deep_Copy_by_Access
      (Ref: in Access_Type)
      return Access_Type is
   begin
      return new Element_Type'(Ref.all);
   end;


This just provides a convenient way to get a Deep_Copy function for a
(pool-specific) access type of a (non-access) data type. Then we could
provide a deep copy for unbounded lists:


   generic
      with function Deep_Copy
         (Item: in Element_Type)
         return Element_Type is <>;

   function SCL.Lists.Unbounded.List_Deep_Copy
      (Source: in Unbounded_List)
      return Unbounded_List;


There would be the same for unbounded lists and other container types.


--
Best wishes,
Nick Roberts

Re: List container strawman

[Marin David Condic]

I don't think I'd characterize it as "complicated" - more like "awkward". In
the past, I've built data structures that would have a "private" flavor and
a "limited private" flavor so that when I had the simple case (assignment
and equality inherently available) I didn't have to go to the effort of
inventing small subprograms or otherwise jockying around the fact that the
limited case was going to insist I provide something that was already there.

I think the reason for "private" being preferable over "limited private" is
that now we can build things that inherit from Controlled, so if you need to
do something to control behavior on assignment, you can, but you don't have
to for the simple case. Hence, you can save yourself some generic parameters
and make instantiation a simpler matter. (Do you really want to have to
define an "Assign" procedure every time you want to stack up some integers?
Its not complicated - just a pain in the posterior.)

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/


"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BF1A33D.73DE084F@boeing.com...
>
> If the client has to provide an Assign procedure for the Element type,
> then the Element type should be limited private. While I have no problem
> with this, I think most of the participants in this discussion have
> already decided that's too complicated for them.
>

Re: List container strawman

[Jeffrey Carter]

Marin David Condic wrote:
> 
> I don't think I'd characterize it as "complicated" - more like "awkward". In
> the past, I've built data structures that would have a "private" flavor and
> a "limited private" flavor so that when I had the simple case (assignment
> and equality inherently available) I didn't have to go to the effort of
> inventing small subprograms or otherwise jockying around the fact that the
> limited case was going to insist I provide something that was already there.
> 
> I think the reason for "private" being preferable over "limited private" is
> that now we can build things that inherit from Controlled, so if you need to
> do something to control behavior on assignment, you can, but you don't have
> to for the simple case. Hence, you can save yourself some generic parameters
> and make instantiation a simpler matter. (Do you really want to have to
> define an "Assign" procedure every time you want to stack up some integers?
> Its not complicated - just a pain in the posterior.)
> 
> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
> news:3BF1A33D.73DE084F@boeing.com...
> >
> > If the client has to provide an Assign procedure for the Element type,
> > then the Element type should be limited private. While I have no problem
> > with this, I think most of the participants in this discussion have
> > already decided that's too complicated for them.
> >

Yes, but I was referring to a comment that suggested an Assign procedure
needs to be provided even though Element is private. In that case you
might as well make Element limited private since it buys you additional
applicability without changing how the component is instantiated.

Of course, the real reason not to import Element as private is that it
is an incorrect specification, and precise specification is essential to
design by contract. A generic package has 2 specifications: the generic
formal part, which should specify precisely what the client must provide
to use the package, and the package specification, which should specify
precisely what services the package provides to its clients.

A formal private type specifies that the package requires "=" for type,
when in fact a list does not use "=" for its Element type.

-- 
Jeffrey Carter

Re: List container strawman

[Marin David Condic]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BF2A186.F1911068@boeing.com...
>
> Yes, but I was referring to a comment that suggested an Assign procedure
> needs to be provided even though Element is private. In that case you
> might as well make Element limited private since it buys you additional
> applicability without changing how the component is instantiated.
>
I would agree that once you've gone to the effort of insisting there be an
Assign and an "=" in the generic formal part, then you might just as well
have made it limited private and enabled the creation of lists of just about
anything.

But I don't want to have to specify an Assign and an "=" every time I want
to stack up some integers or something similarly simple. I just want to get
the job done with as little effort or excess baggage as is possible.


> Of course, the real reason not to import Element as private is that it
> is an incorrect specification, and precise specification is essential to
> design by contract. A generic package has 2 specifications: the generic
> formal part, which should specify precisely what the client must provide
> to use the package, and the package specification, which should specify
> precisely what services the package provides to its clients.
>
Interesting, but IMHO, not compelling. Some folks may want a list package to
satisfy all sorts of requirements that are of some kind of academic
interest. They may even want a formal mathematical proof of correctness. I
don't think any of this Moves The Mission Forward. My big questions are
"Does it work reliably?" and "Is it easy to use?". Design by contract,
Ravenscar profiles, Mathematical proofs, etc. may all contribute something
to question #1, but if they start getting in the way of question #2, I'd
find that a hindrance to producing something large numbers of people will
want to use.

If we insist on Design By Contract or some other approaches as requirements,
I'd ask "Do all the other packages provided by the Ada standard meet these
requirements?" I'd suggest that they probably don't - in which case, why
should a data-structures-add-on to the language need to do so?


> A formal private type specifies that the package requires "=" for type,
> when in fact a list does not use "=" for its Element type.
>

I'd suggest that no matter how hard you try, you aren't going to get me to
shed a single tear over the fact that an "=" operation came along for the
ride even though a List package (according to what definition? mine is
pretty loose!) doesn't need it. Every time I write a math function for a
type Float, I bring in a whole slew of operations I may not need. Every time
I "with" a package, the same thing happens. Every time you have a generic
formal of "digits <>" or similar, you bring in operations that may not be
needed. I respectfully submit the question: "So What?" :-)

No matter what we do, we will *never* arrive at a "Perfect" List package.
The best we can hope for is a "Good Enough" List package that covers some
sufficient bulk of the possible uses and does so as easily and with as much
functionality as can reasonably be had.

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

[Nick Roberts]

Have I missed something in this discussion? If it is, as I get the
impression, over whether the data type (the type of each element of a list)
generic parameter should be private or limited private, I think I can give
you the definitive answer.

Unless I'm really missing something, it's got to be private (non-limited),
because otherwise how do you copy values of that type into or out of the
list? End of argument (isn't it?).

--
Best wishes,
Nick Roberts

Re: List container strawman

[Ehud Lamm]

Indeed one advantage of having a standard design for the different packages
in the library is to encourage this sort of general utilities.

Ehud

Re: List container strawman

[Marin David Condic]

Nope. Sorry. You can (and I have) make a list package using limited private
that insists on having a procedure called "Assign" and a function called "="
as generic formals. The advantage of that is that now you could do something
like make a List of Lists (assuming your list type is limited). The
disadvantage is that when you just need a list of integers, you've still got
to go define the "Assign" at least - assuming the "=" has the "is <>", so it
gloms onto the existing "=" function. O.K. It's not the end of civilization
as we know it, but its a pain in the backside - especially where you might
have library level instantiations, etc. Who wants to keep writing trivial
"Assign" subprograms (and maintaining them in separate files, etc., if you
have to do library level instantiations.) for every usage of a list - which
most of the time won't need anything tricky in the "Assign" procedure
anyway.

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/


"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message
news:9svf7q$161cka$1@ID-25716.news.dfncis.de...
>
> Unless I'm really missing something, it's got to be private (non-limited),
> because otherwise how do you copy values of that type into or out of the
> list? End of argument (isn't it?).
>

Re: List container strawman

[Matthew Heaney]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message
news:9svf7q$161cka$1@ID-25716.news.dfncis.de...
> Have I missed something in this discussion? If it is, as I get the
> impression, over whether the data type (the type of each element of a
list)
> generic parameter should be private or limited private, I think I can give
> you the definitive answer.

The problem is worse, because most of the participants in this discussion
have assumed that "list" means a polylithic structure (elements are shared),
a la LISP.  This is an incorrect model.  The container abstraction is
monolithlic, and refering to it as a "list" only means that it has constant
time insertion and removal.  So you don't need "construct" or "cons" or
"singleton" or "head" or "tail" or whatever.

Furthermore, you can add an item to the list at the front, back, or
somewhere in the middle.  You can remove any iteim of the list.

with Ada.Finalization;
generic
   type Item_Type is private;
   with function "=" (L, R : Item_Type) return Boolean is <>;
package Lists is
   type List_Type is private;  --implies Controlled
   procedure Push_Front (List : in out List_Type; Item : in Item_Type);
   procedure Push_Back (List : in out List_Type; Item : in Item_Type);
   procedure Pop_Front (List : in out List_Type);
   procedure Pop_Back (List : in out List_Type);
   function Front (List : List_Type) return Item_Type;
   function Back (List : List_Type) return Item_Type;
   function Length (List : List_Type) return Natural;

   type Iterator_Type (List : access List_Type) is limited private;
   procedure Insert (Iterator : in Iterator_Type; Item : in Item_Type);
   procedure Remove (Iterator : in out Iterator_Type);
   procedure Advance (Iterator : in out Iterator_Type);
   procedure Backup (Iterator : in out Iterator_Type);
   function Item (Iterator : in Iterator_Type) return Item_Type;
--or maybe
--type Iterator_Type is private;
--function Front (List : List_Type) return Iterator_Type;
--function Back (List : List_Type) return Iterator_Type;
--bounded form would probably require:
--function Front (List : access List_Type) return Iterator_Type;
--procedure Insert (List : in out List_Type; Iterator : Iterator_Type; Item
: Item_Type);
--procedure Remove (List : in out List_Type; Iterator : in out
Iterator_Type);
--etc
...
end;

That's the general idea.  I'm undecided about how to declare the iterator
type, because the limited form may have a false sense of security, e.g.

declare
   List : aliased Integer_Lists.List_Type;
begin
   Push_Front (List, 42);
   declare
      Iter : Iterator_Type (List'Access);
   begin
      Pop_Front (List);
      X := Item (Iter); --uh oh
   end;
end;

it may be simpler to just

declare
   List : List_Type;
   Iter : Iterator_Type;
begin
   Push_Front (List, 42);
   Iter := Front (List);
...
end;

It may also be necessary to use "First" and "Last" to refer to the first and
last elements in the sequence, and "Front" and "Back" to refer to the nonce
values that immediately preceed First and immediately follow Last, eg

declare
   List : List_Type;
   Iter : Iterator_Type := First (List);
begin
   while Iter /= List.Back loop
      ...
      Remove (List, Iter);
   end loop;
end;

You could then use First and Back to specify a half-open range, a la the STL
in C++.

Some food for thought...

Re: List container strawman

[Vincent Marciante]

Jeffrey Carter wrote:
> 
> Matthew Heaney wrote:
> >
> > "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
> > news:3BE3235D.E292B890@boeing.com...
> > > Another place where some compiler writers use tricks is the interaction
> > > between a random number Generator value and the Random function.

<snip>

> > No heap allocation or compiler magic is needed to implement Generator; just
> > use the Rosen Trick:
> 
> Yes, that is a trick that can be used (although your example has a
> couple of errors). Was it known before standardization? I somehow
> suspect it would have been outlawed if it were.
> 
> GNAT uses

<snip> 

> I wonder if there is some advantage to this trick over the Rosen
> trick.

IIRC

The GNAT code was written before the Rosen Trick was first described.
The GNAT code worked and there was no important reason to change it.
If the Rosen Trick was known at the time, it would have been used. 

Vincent Marciante

Re: List container strawman

[Nick Roberts]

Hah, it's pretty funny, Marin. You've made me spot an error in my just
released proposal for the list package! I've declared the Abstract_List type
limited, and it shouldn't be.

Sorry, but my point (now ;-) would be that, whilst you can indeed do what
you say, you wouldn't want to. Because lists are non-limited (hah :-) you
can have a list of lists (etc.) without any problem. If you have a limited
type, you don't want a list of objects of that type, you want a list of
access values referencing them (e.g. consider a list of tasks).

So, to sum up, I'm certain the data type (generic parameter) should be
non-limited, so it can be copied without any sillyness.

--
Best wishes,
Nick Roberts

Re: List container strawman

[Marin David Condic]

Back in the days of Ada83, this was more of a problem. Now that you have
Finalization, making a List type non-limited is less of a problem.

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/


"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message
news:9t1q26$16frj1$1@ID-25716.news.dfncis.de...
>
> Sorry, but my point (now ;-) would be that, whilst you can indeed do what
> you say, you wouldn't want to. Because lists are non-limited (hah :-) you
> can have a list of lists (etc.) without any problem. If you have a limited
> type, you don't want a list of objects of that type, you want a list of
> access values referencing them (e.g. consider a list of tasks).
>

Re: List container strawman

[Nick Roberts]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9t3ddg$c9c$1@nh.pace.co.uk...
> Back in the days of Ada83, this was more of a problem. Now that you have
> Finalization, making a List type non-limited is less of a problem.

Acknowledged.

--
Best wishes,
Nick Roberts