* Re: Ada.Containers.Vectors - querying multiple elements [not found] ` <426E5A0B.3010109@on2.com> @ 2005-04-26 16:00 ` Duncan Sands 2005-04-28 0:54 ` Randy Brukardt 0 siblings, 1 reply; 52+ messages in thread From: Duncan Sands @ 2005-04-26 16:00 UTC (permalink / raw) To: users; +Cc: comp.lang.ada Hi Matthew, to summarize your reply: "that's the price you pay for abstraction". What I would really like to know is why there is a significant advantage to allowing implementations that are far from the pointer-to-an-array method. > > I've been playing around with Ada.Containers.Vectors (part of > > Ada 2005, see http://charles.tigris.org/; look for AI-302) and > > noticed that there's no way to view or operate on a "slice" of > > a vector. > > There's nothing special about a vector, that it alone should provide > array-based operations. A vector is a container just like any other, > but with constant time (O(1)) random access. That is presumably how you like to think of it, but you could also say: "A vector is a container just like any other, from which you can take slices with O(length) time". > The logical model for a vector is an array, but physically a vector can > have any representation consistent with logical specifications. Sure, but that's not a restriction on the specification, that's a restriction on the implementation. You could add a procedure like I mentioned to the spec - the implementations would have to implement it, that's all. The question is: what do you lose by adding such a routine? I fully appreciate that finding the "right" abstraction is a delicate balancing act requiring a lot of time and experience. So: why is the current specification the right choice, and not one with "slices" in it. For example, Ada.Strings.Unbounded has slices - was that a mistake? > The reference implementation uses an array, but I know of a vendor who > plans to use a skip list, and another who plans to use a two-level > structure (not unlike an STL deque). To my mind, this is the real argument. It implicitly shows that there can be real advantages to implementing Vector in a non-obvious way. However I don't see why either of these is incompatible with taking read-only slices. It may not be as efficient as with a simple pointer-to-array implementation, but it's not bad: the deque is no problem, and the skip list should be pretty efficient too. That's fairly inevitable: if you can access elements in constant time, you can access N of them in time O(N). However it looks to me like in both cases the "slice" operation can be done more efficiently than by repeatedly calling "Element" to copy into a buffer. > So there are no array-based operations for vector, just as there are no > array-based operations for any other container. What's wrong with having operations that only apply to a vector and not to other containers? I guess you have a philosophy that tells you it is a bad idea - care to explain? > > I'd like something like this: > > > > procedure Query_Elements > > (Container : in Vector; > > First_Index : in Index_Type; > > Last_Index : in Extended_Index; > > Process : not null > > access procedure (Elements : in Element_Array)); > > > > where Element_Array would be: > > > > type Element_Array is > > array (Index_Type range <>) of Element_Type; > > > > Is there any reason no such routine exists? > > This wouldn't work, because a vector container doesn't guarantee that > the underlying data structure is a contiguous array. As you mention below, it can be implemented by copying into a buffer (read-only access), or copying to and from a buffer (read-write access). So there is no logical objection, though limited stack space might be a practical problem. > > It would be good to have for both > > efficiency reasons > > No, there would be no efficiency benefit (in fact, there would be an > efficiency penalty, in order synthesize an array object) if the > underlying data structure were something other than an array. Surely the question is whether it can be significantly more efficient to implement it in the body, as compared to having the user do an element by element copy. For the pointer-to-an-array implementation, the body can do a much more efficient job; I don't know how much you gain for deques and skip lists. > > and simple implementation of certain classes of algorithms. > > In my case I have a "divide and conquer" recursive algorithm which while it > > can be written using the current package, would be simpler to write if something > > like Query_Elements existed. > > The thing I wish the API provided for vectors are operators such as: > > function "+" (C : Cursor; Off : Integer) return Cursor; > function "-" (L, R : Cursor) return Integer; > etc. > > I lobbied for this, but there was little enthusiasm among the ARG. OK. All the best, Duncan. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 16:00 ` Ada.Containers.Vectors - querying multiple elements Duncan Sands @ 2005-04-28 0:54 ` Randy Brukardt 0 siblings, 0 replies; 52+ messages in thread From: Randy Brukardt @ 2005-04-28 0:54 UTC (permalink / raw) "Duncan Sands" <baldrick@free.fr> wrote in message news:mailman.79.1114531228.24457.comp.lang.ada@ada-france.org... > Hi Matthew, to summarize your reply: "that's the price you pay for > abstraction". What I would really like to know is why there is a > significant advantage to allowing implementations that are far from > the pointer-to-an-array method. Probably because it wouldn't have gotten enough support from the ARG without an appropriate level of abstraction. There is a political aspect to designing for an existing standard, after all, you don't always end up with what someone might think is the best possible solution. In our case, the way our generics are implemented (always shared bodies), the "canonical" implementation would require thousands of tiny allocations. That would work, of course, but it would hardly be high speed. By allocating smaller chunks (and avoiding copying to/from those chunks), we can keep those allocations down to something that is done only for the elements that make up an expansion. ... > > The logical model for a vector is an array, but physically a vector can > > have any representation consistent with logical specifications. > > Sure, but that's not a restriction on the specification, that's a > restriction on the implementation. You could add a procedure like > I mentioned to the spec - the implementations would have to implement > it, that's all. The question is: what do you lose by adding such a > routine? I fully appreciate that finding the "right" abstraction is > a delicate balancing act requiring a lot of time and experience. So: > why is the current specification the right choice, and not one with > "slices" in it. For example, Ada.Strings.Unbounded has slices - was > that a mistake? The slices of Ada.Strings.Unbounded are copies, always. I don't think there would be any problem with having a slice function -- it just would be rather inefficient. > > The reference implementation uses an array, but I know of a vendor who > > plans to use a skip list, and another who plans to use a two-level > > structure (not unlike an STL deque). > > To my mind, this is the real argument. It implicitly shows that there > can be real advantages to implementing Vector in a non-obvious way. > However I don't see why either of these is incompatible with taking > read-only slices. It may not be as efficient as with a simple > pointer-to-array implementation, but it's not bad: the deque is no > problem, and the skip list should be pretty efficient too. That's > fairly inevitable: if you can access elements in constant time, you can > access N of them in time O(N). However it looks to me like in both > cases the "slice" operation can be done more efficiently than by > repeatedly calling "Element" to copy into a buffer. A slice is a *contiguous* list of elements in every compiler that I'm familiar with. If you have a non-contiguous representation (certainly the case with a skip list or deque), the only way to provide that would be a full-scale copy. (One could optimize it if it happened to be all within a single chunk, but that seems unlikely to be of much benefit.) > > So there are no array-based operations for vector, just as there are no > > array-based operations for any other container. > > What's wrong with having operations that only apply to a vector and not > to other containers? I guess you have a philosophy that tells you it is > a bad idea - care to explain? We really wanted the Vector and List to be interoperable as much as possible, and similarly for the Map and Set. We've tended to add operations to the "other" container to make that possible. (In theory, you could have an interface that would allow algorithms to work on both a Vector and a List. That probably would be more valuable if there were more types of sequence containers.) There are of course operations on one that isn't allowed on the other. But I have little enthusiasm for making Vectors even larger; it already has 240 paragraphs. (Useless aside: When I first started formatting the containers library for the draft AARM, I just dumped the entire text into the source file, with no section breaks. It generated about 1200 paragraphs. I was impressed that the tools didn't expire when given that many paragraphs at once. I'm rather glad to not have to refer to A.18.2(1188/2). :-) Randy Brukardt. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Ada.Containers.Vectors - querying multiple elements @ 2005-04-26 11:43 Duncan Sands 2005-04-26 14:12 ` Georg Bauhaus 0 siblings, 1 reply; 52+ messages in thread From: Duncan Sands @ 2005-04-26 11:43 UTC (permalink / raw) To: comp.lang.ada; +Cc: users I've been playing around with Ada.Containers.Vectors (part of Ada 2005, see http://charles.tigris.org/; look for AI-302) and noticed that there's no way to view or operate on a "slice" of a vector. There's a routine procedure Query_Element (Container : in Vector; Index : in Index_Type; Process : not null access procedure (Element : in Element_Type)); for looking at one element; I'd like something like this: procedure Query_Elements (Container : in Vector; First_Index : in Index_Type; Last_Index : in Extended_Index; Process : not null access procedure (Elements : in Element_Array)); where Element_Array would be: type Element_Array is array (Index_Type range <>) of Element_Type; Is there any reason no such routine exists? It would be good to have for both efficiency reasons and simple implementation of certain classes of algorithms. In my case I have a "divide and conquer" recursive algorithm which while it can be written using the current package, would be simpler to write if something like Query_Elements existed. All the best, Duncan. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 11:43 Duncan Sands @ 2005-04-26 14:12 ` Georg Bauhaus 2005-04-26 14:39 ` Duncan Sands 2005-04-27 4:59 ` Jeffrey Carter 0 siblings, 2 replies; 52+ messages in thread From: Georg Bauhaus @ 2005-04-26 14:12 UTC (permalink / raw) Duncan Sands wrote: > procedure Query_Elements > (Container : in Vector; > First_Index : in Index_Type; > Last_Index : in Extended_Index; > Process : not null access procedure (Elements : in Element_Array)); > It would be good to have for both > efficiency reasons and simple implementation of certain classes of algorithms. > In my case I have a "divide and conquer" recursive algorithm which while it > can be written using the current package, would be simpler to write if something > like Query_Elements existed. Couldn't you use Cursors, here: Cursor := find_or_something(container, ...); there: constant Cursor := find_or_something(container, ...); while here /= there loop ... next(here); end loop; -- Georg ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 14:12 ` Georg Bauhaus @ 2005-04-26 14:39 ` Duncan Sands 2005-04-26 15:44 ` Matthew Heaney 2005-04-27 4:59 ` Jeffrey Carter 1 sibling, 1 reply; 52+ messages in thread From: Duncan Sands @ 2005-04-26 14:39 UTC (permalink / raw) To: Georg Bauhaus; +Cc: comp.lang.ada Hi Georg, thanks for replying. > > procedure Query_Elements > > (Container : in Vector; > > First_Index : in Index_Type; > > Last_Index : in Extended_Index; > > Process : not null access procedure (Elements : in Element_Array)); > > > > It would be good to have for both > > efficiency reasons and simple implementation of certain classes of algorithms. > > In my case I have a "divide and conquer" recursive algorithm which while it > > can be written using the current package, would be simpler to write if something > > like Query_Elements existed. > > Couldn't you use Cursors, > > here: Cursor := find_or_something(container, ...); > there: constant Cursor := find_or_something(container, ...); > > while here /= there loop > ... > next(here); > end loop; I'm particularly concerned about: (1) efficiency - suppose (for example) I want to transmit the contents of my vector down a socket. Then I would have to do an element-by- element copy into a buffer (using code like you suggest), and then send the buffer. The element-by-element copy is inefficient, and with a procedure like Query_Elements above simply wouldn't (necessarily) be needed. An element-by-element copy can't compete with memcpy (what you'd probably get if you copied a slice directly, which would be possible using Query_Elements), and certainly can't compete with no copy at all. By the way, this is not a real example, it's just the first thing that came to mind. In any case, it is a special case of point (2): (2) reuse of legacy code - I don't know about you, but I've a lot of legacy code around that takes an array as a parameter. I mean code that doesn't change the length of the array (or anything like that) - code that just operates on the array in-place. Suppose I am using a Vector, and want to have some legacy code operate on it, or on part of it. Right now I would have to copy the appropriate part of the Vector into a buffer, and pass that to the legacy code, and then copy it back. Not very efficient - and not necessary if the Vectors api was extended slightly. Ciao, D. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 14:39 ` Duncan Sands @ 2005-04-26 15:44 ` Matthew Heaney 2005-04-26 16:05 ` Duncan Sands ` (2 more replies) 0 siblings, 3 replies; 52+ messages in thread From: Matthew Heaney @ 2005-04-26 15:44 UTC (permalink / raw) Duncan Sands wrote: > > (1) efficiency - suppose (for example) I want to transmit the contents > of my vector down a socket. You're not grokking the Ada95 way of doing things. Use the stream operations for that. All containers (indeed, all non-limited types in the predefined language environment) support streaming. Your socket abstraction should have a selector function to return a reference to a stream, so you can say: declare S : Socket; V : Vector; begin ... Vector'Write (Stream (S), V); end; > (2) reuse of legacy code - I don't know about you, but I've a lot of > legacy code around that takes an array as a parameter... A vector container isn't necessarily implemented as an array, so there are no benefits to having array-based operations. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 15:44 ` Matthew Heaney @ 2005-04-26 16:05 ` Duncan Sands [not found] ` <1114531544.32583.142.camel@localhost.localdomain> 2005-04-28 14:17 ` Duncan Sands 2 siblings, 0 replies; 52+ messages in thread From: Duncan Sands @ 2005-04-26 16:05 UTC (permalink / raw) To: Matthew Heaney; +Cc: comp.lang.ada Hi Matthew, > > (1) efficiency - suppose (for example) I want to transmit the > contents > > of my vector down a socket. > > You're not grokking the Ada95 way of doing things. Use the stream > operations for that. All containers (indeed, all non-limited types in > the predefined language environment) support streaming. I agree it wasn't a good example. > > (2) reuse of legacy code - I don't know about you, but I've a lot of > > legacy code around that takes an array as a parameter... > > A vector container isn't necessarily implemented as an array, so there > are no benefits to having array-based operations. Not so. There is a benefit if array-based operations can be implemented much more efficiently in the body of Ada.Containers.Vectors (where properties of the data structure can be fully exploited), as compared to implementing them outside the body (via copying to a buffer using multiple calls to Element). The pointer-to-an-array implementation is an example where you get a big benefit from implementing in the body; that's not to say there is no benefit for other implementations. All the best, Duncan. ^ permalink raw reply [flat|nested] 52+ messages in thread
[parent not found: <1114531544.32583.142.camel@localhost.localdomain>]
[parent not found: <426E72C3.9070108@on2.com>]
* Re: Ada.Containers.Vectors - querying multiple elements [not found] ` <426E72C3.9070108@on2.com> @ 2005-04-26 16:59 ` Duncan Sands [not found] ` <1114534751.32583.144.camel@localhost.localdomain> 2005-04-26 18:59 ` Duncan Sands 2 siblings, 0 replies; 52+ messages in thread From: Duncan Sands @ 2005-04-26 16:59 UTC (permalink / raw) To: Matthew Heaney; +Cc: comp.lang.ada > >>A vector container isn't necessarily implemented as an array, so there > >>are no benefits to having array-based operations. > > > > > > Not so. There is a benefit if array-based operations can be implemented > > much more efficiently in the body of Ada.Containers.Vectors (where > > properties of the data structure can be fully exploited), as compared to > > implementing them outside the body (via copying to a buffer using multiple > > calls to Element). The pointer-to-an-array implementation is an example > > where you get a big benefit from implementing in the body; that's not to > > say there is no benefit for other implementations. > > > What you really want is to take advantage of the container > representation to implement an algorithm more efficiently. That's fine. > Ada95 has a specific technique for that: make the algorithm a child > subprogram. > > Instead of trying to bring the mountain to Mohammed, bring Mohammed to > the mountain... But isn't it illegal to create a child of package Ada? Ciao, D. ^ permalink raw reply [flat|nested] 52+ messages in thread
[parent not found: <1114534751.32583.144.camel@localhost.localdomain>]
[parent not found: <426E73DE.2070505@on2.com>]
* Re: Ada.Containers.Vectors - querying multiple elements [not found] ` <426E73DE.2070505@on2.com> @ 2005-04-26 17:08 ` Duncan Sands 2005-04-26 18:17 ` Martin Dowie 0 siblings, 1 reply; 52+ messages in thread From: Duncan Sands @ 2005-04-26 17:08 UTC (permalink / raw) To: Matthew Heaney; +Cc: comp.lang.ada > > But isn't it illegal to create a child of package Ada? > > But you're not creating a child of Ada. You're creating a child of > ada.containers.vectors. That is also illegal. By "child" I was referring to any descendant. Ciao, D. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 17:08 ` Duncan Sands @ 2005-04-26 18:17 ` Martin Dowie 2005-04-26 18:48 ` Duncan Sands 0 siblings, 1 reply; 52+ messages in thread From: Martin Dowie @ 2005-04-26 18:17 UTC (permalink / raw) Duncan Sands wrote: >>>But isn't it illegal to create a child of package Ada? >> >>But you're not creating a child of Ada. You're creating a child of >>ada.containers.vectors. > > > That is also illegal. By "child" I was referring to any descendant. No it is _not_ 'illegal' to add a {grand}child to the "Ada" package hierarchy. It is the namespace under "Ada" that the ARG seem particularly keen on reserving. Cheers -- Martin ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 18:17 ` Martin Dowie @ 2005-04-26 18:48 ` Duncan Sands 0 siblings, 0 replies; 52+ messages in thread From: Duncan Sands @ 2005-04-26 18:48 UTC (permalink / raw) To: Martin Dowie; +Cc: comp.lang.ada > No it is _not_ 'illegal' to add a {grand}child to the "Ada" package > hierarchy. > > It is the namespace under "Ada" that the ARG seem particularly keen > on reserving. Yes, you and Matthew are quite right. I was misled by the fact that by default GNAT will not allow grandchildren. All the best, Duncan. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements [not found] ` <426E72C3.9070108@on2.com> 2005-04-26 16:59 ` Duncan Sands [not found] ` <1114534751.32583.144.camel@localhost.localdomain> @ 2005-04-26 18:59 ` Duncan Sands 2005-04-26 19:05 ` Georg Bauhaus 2 siblings, 1 reply; 52+ messages in thread From: Duncan Sands @ 2005-04-26 18:59 UTC (permalink / raw) To: Matthew Heaney; +Cc: comp.lang.ada > >>A vector container isn't necessarily implemented as an array, so there > >>are no benefits to having array-based operations. > > > > > > Not so. There is a benefit if array-based operations can be implemented > > much more efficiently in the body of Ada.Containers.Vectors (where > > properties of the data structure can be fully exploited), as compared to > > implementing them outside the body (via copying to a buffer using multiple > > calls to Element). The pointer-to-an-array implementation is an example > > where you get a big benefit from implementing in the body; that's not to > > say there is no benefit for other implementations. > > > What you really want is to take advantage of the container > representation to implement an algorithm more efficiently. That's fine. > Ada95 has a specific technique for that: make the algorithm a child > subprogram. > > Instead of trying to bring the mountain to Mohammed, bring Mohammed to > the mountain... Well, Mohammed is still waiting for the mountain... I can't say I like the child unit suggestion: a different child would be needed for each compiler, which is unpleasant. If I was trying to do something weird, then that would be fair enough. But (IMHO) grabbing a "slice" of a vector is a very normal thing to want to do. Why not support it as efficiently as possible? Ciao, D. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 18:59 ` Duncan Sands @ 2005-04-26 19:05 ` Georg Bauhaus 2005-04-26 20:34 ` Duncan Sands 2005-04-26 21:47 ` Dr. Adrian Wrigley 0 siblings, 2 replies; 52+ messages in thread From: Georg Bauhaus @ 2005-04-26 19:05 UTC (permalink / raw) Duncan Sands wrote: > But (IMHO) grabbing a "slice" of a > vector is a very normal thing to want to do. Why not support it as > efficiently as possible? I'm curious. Where is slicing a dynamically sized vector done frequently? -- Georg ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 19:05 ` Georg Bauhaus @ 2005-04-26 20:34 ` Duncan Sands 2005-04-26 21:47 ` Dr. Adrian Wrigley 1 sibling, 0 replies; 52+ messages in thread From: Duncan Sands @ 2005-04-26 20:34 UTC (permalink / raw) To: Georg Bauhaus; +Cc: comp.lang.ada > > But (IMHO) grabbing a "slice" of a > > vector is a very normal thing to want to do. Why not support it as > > efficiently as possible? > > I'm curious. Where is slicing a dynamically sized vector > done frequently? Whenever you want to use legacy code that works on arrays? It's true I have no statistics - I would like to hear some. By the way, I would be perfectly satisfied if Matthew said: "based on our code survey, hardly anybody needs this, so we didn't include it". However his arguments don't seem to be of this kind. Anyway, here's the example that started this whole thing: I have a package that used GNAT.Dynamic_Tables (GDT). These tables are quite efficient and easy to manipulate, but they do have some problems. For example, if your table element type has some kind of automatic initialization (eg: it is a pointer => initialized to null) then that initialization won't happen. This can cause strange bugs if forgotten. I ran into just such a bug this morning, which made me do what I had long intended to do: ditch GDT. Rather than writing my own abstraction to replace it, I decided to look into the AI302 containers. For the case in hand, Ada.Containers.Vectors seemed perfect - and it was perfect (thanks Matthew!). The only place where I had any problem at all was in using one of our existing debugging routines which turns an array into a formatted output string. For this it would have been nice to be able to access the vector as an array. Since you can't do that directly, I wrote a new debugging routine which takes a vector as parameter - so there was no real problem there either. However it did strike me that the ability to view parts of the vector as arrays would be generally useful, and thus my original email. All the best, Duncan. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 19:05 ` Georg Bauhaus 2005-04-26 20:34 ` Duncan Sands @ 2005-04-26 21:47 ` Dr. Adrian Wrigley 2005-04-26 23:21 ` Marius Amado Alves ` (2 more replies) 1 sibling, 3 replies; 52+ messages in thread From: Dr. Adrian Wrigley @ 2005-04-26 21:47 UTC (permalink / raw) On Tue, 26 Apr 2005 21:05:28 +0200, Georg Bauhaus wrote: > Duncan Sands wrote: > >> But (IMHO) grabbing a "slice" of a >> vector is a very normal thing to want to do. Why not support it as >> efficiently as possible? > > I'm curious. Where is slicing a dynamically sized vector > done frequently? recursive algorithms! (and plenty of other places too.) (this was discussed in the endless C++/Ada rant a few weeks ago. Slicing arrays, and using array attributes 'First, 'Last obviate the need for extra parameters. Of course, the C++ enthusiasts didn't seem to be impressed. To work properly, arrays need to be able to start from any index, of course.) I agree with Duncan's point. It would be good to have in the Vectors containers. I rather hoped Vectors could do everything that Arrays could. I'm disappointed. Adrian -- Dr. Adrian Wrigley, Cambridge, UK ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 21:47 ` Dr. Adrian Wrigley @ 2005-04-26 23:21 ` Marius Amado Alves [not found] ` <9decddc0038674b3c85aeceefb4d3b83@netcabo.pt> 2005-04-27 11:10 ` Georg Bauhaus 2 siblings, 0 replies; 52+ messages in thread From: Marius Amado Alves @ 2005-04-26 23:21 UTC (permalink / raw) To: comp.lang.ada On 26 Apr 2005, at 22:47, Dr. Adrian Wrigley wrote: > On Tue, 26 Apr 2005 21:05:28 +0200, Georg Bauhaus wrote: > >> Duncan Sands wrote: >> >>> But (IMHO) grabbing a "slice" of a >>> vector is a very normal thing to want to do. Why not support it as >>> efficiently as possible? >> >> I'm curious. Where is slicing a dynamically sized vector >> done frequently? > > recursive algorithms! > (and plenty of other places too.) Yes. I fought for slices in the ARG forum many months ago [1]. I was practically alone. Where were you guys? :-) You could have made the difference. It happened with indefinite elements. Here I pushed harder. It took three waves of discussion, at separate times. The final wave was started by a simple statement of need by someone else. Ada.Containers now have indefinite elements, but not slices. For slices there was only one wave. Now it's too late for Ada 2005. [1] Discussion archived at http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-30302.TXT?rev=1.16 ^ permalink raw reply [flat|nested] 52+ messages in thread
[parent not found: <9decddc0038674b3c85aeceefb4d3b83@netcabo.pt>]
* Re: Ada.Containers.Vectors - querying multiple elements [not found] ` <9decddc0038674b3c85aeceefb4d3b83@netcabo.pt> @ 2005-04-27 8:15 ` Duncan Sands [not found] ` <1114589729.10418.13.camel@localhost.localdomain> 1 sibling, 0 replies; 52+ messages in thread From: Duncan Sands @ 2005-04-27 8:15 UTC (permalink / raw) To: Marius Amado Alves; +Cc: comp.lang.ada Hi Marius, > Yes. I fought for slices in the ARG forum many months ago [1]. I was > practically alone. Where were you guys? :-) You could have made the > difference. It happened with indefinite elements. Here I pushed harder. > It took three waves of discussion, at separate times. The final wave > was started by a simple statement of need by someone else. > Ada.Containers now have indefinite elements, but not slices. For slices > there was only one wave. Now it's too late for Ada 2005. > > [1] Discussion archived at > http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-30302.TXT?rev=1.16 I'm reading that (long) discussion now. How does one get onto this mailing list? You know, if vectors were called sequences, probably I wouldn't be asking for slices - it's true that the name "vector" carries a lot of mental baggage :) Ciao, D. ^ permalink raw reply [flat|nested] 52+ messages in thread
[parent not found: <1114589729.10418.13.camel@localhost.localdomain>]
* Re: Ada.Containers.Vectors - querying multiple elements [not found] ` <1114589729.10418.13.camel@localhost.localdomain> @ 2005-04-27 11:49 ` Marius Amado Alves 2005-04-28 0:36 ` Randy Brukardt 0 siblings, 1 reply; 52+ messages in thread From: Marius Amado Alves @ 2005-04-27 11:49 UTC (permalink / raw) To: Duncan Sands; +Cc: comp.lang.ada On 27 Apr 2005, at 09:15, Duncan Sands wrote: >> Yes. I fought for slices in the ARG forum many months ago [1]... >> >> [1] Discussion archived at >> http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-30302.TXT?rev=1.16 > > I'm reading that (long) discussion now. How does one get onto this > mailing list? I don't remember exactly how I subscribed. Try sending an email with "help Ada-Comment" in the body to "listserv@ada-auth.org" ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-27 11:49 ` Marius Amado Alves @ 2005-04-28 0:36 ` Randy Brukardt 2005-04-28 7:09 ` Duncan Sands 0 siblings, 1 reply; 52+ messages in thread From: Randy Brukardt @ 2005-04-28 0:36 UTC (permalink / raw) "Marius Amado Alves" <amado.alves@netcabo.pt> wrote in message news:mailman.90.1114605018.24457.comp.lang.ada@ada-france.org... > > On 27 Apr 2005, at 09:15, Duncan Sands wrote: > > > I'm reading that (long) discussion now. How does one get onto this > > mailing list? > > I don't remember exactly how I subscribed. Try sending an email with > "help Ada-Comment" in the body to "listserv@ada-auth.org" There is a page outlining the process at http://www.adaic.com/standards/articles/comment.html. You can find it on the Ada 95 documents page: http://www.adaic.com/standards/ada95.html. Randy. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-28 0:36 ` Randy Brukardt @ 2005-04-28 7:09 ` Duncan Sands 0 siblings, 0 replies; 52+ messages in thread From: Duncan Sands @ 2005-04-28 7:09 UTC (permalink / raw) To: Randy Brukardt; +Cc: comp.lang.ada > > I don't remember exactly how I subscribed. Try sending an email with > > "help Ada-Comment" in the body to "listserv@ada-auth.org" > > There is a page outlining the process at > http://www.adaic.com/standards/articles/comment.html. You can find it on the > Ada 95 documents page: http://www.adaic.com/standards/ada95.html. Thanks Randy. By the way, if you send the "help Ada-Comment" command it tells you how to unsubscribe, but doesn't tell you how to subscribe (or at least I didn't spot it)! Ciao, D. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 21:47 ` Dr. Adrian Wrigley 2005-04-26 23:21 ` Marius Amado Alves [not found] ` <9decddc0038674b3c85aeceefb4d3b83@netcabo.pt> @ 2005-04-27 11:10 ` Georg Bauhaus 2005-04-27 11:57 ` Duncan Sands 2 siblings, 1 reply; 52+ messages in thread From: Georg Bauhaus @ 2005-04-27 11:10 UTC (permalink / raw) Dr. Adrian Wrigley wrote: > On Tue, 26 Apr 2005 21:05:28 +0200, Georg Bauhaus wrote: > > >>Duncan Sands wrote: >> >> >>>But (IMHO) grabbing a "slice" of a >>>vector is a very normal thing to want to do. Why not support it as >>>efficiently as possible? >> >>I'm curious. Where is slicing a dynamically sized vector >>done frequently? > > > recursive algorithms! > (and plenty of other places too.) Recursive algorithms on arrays that change their 'Length during recursion by removing or inserting slices? Or are array parameters used for the side effect of passing bounds which are really central to the algorithm? (This can be expressed using nested subprograms of two index values, like in quicksort, such that the array is visible to the subprogram.) Hmm. Is there really a big difference? When I pass an array slice to a subprogram that takes an in mode array parameter, then inside the subprogram I can look at the array properties and at elements within the array parameter's range. OTOH, When I pass two vector cursors to an STL-like subprogram, then inside the subprogram I can look at the vector properties and at elements within the range specified by the two cursors. > (this was discussed in the endless C++/Ada rant a few weeks > ago. IIRC, we had arrays of fixed size in these discussions, or else array subprogram parameters. (Part of the comparison was with std::valarray rather than std::vector, and valarray which offers slicing is special among STL containers, as are Ada arrays among Ada.Containers ;-) -- Georg ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-27 11:10 ` Georg Bauhaus @ 2005-04-27 11:57 ` Duncan Sands 0 siblings, 0 replies; 52+ messages in thread From: Duncan Sands @ 2005-04-27 11:57 UTC (permalink / raw) To: Georg Bauhaus; +Cc: comp.lang.ada Hi Georg, > Recursive algorithms on arrays that change their > 'Length during recursion by removing or inserting slices? > Or are array parameters used for the side effect of passing > bounds which are really central to the algorithm? (This can > be expressed using nested subprograms of two index values, > like in quicksort, such that the array is visible to the > subprogram.) that's how I reimplemented the recursive algorithm that started this thread: just pass the bounds around instead of an actual array. However this required rewriting the code. That's why I've been mentioning legacy code: what about legacy code that I can't reasonably rewrite? And it seems wrong that if I want to use "vector" in some high level abstraction built on low level building blocks, I have to push the use of "vector" down into those building blocks too. Ciao, Duncan. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 15:44 ` Matthew Heaney 2005-04-26 16:05 ` Duncan Sands [not found] ` <1114531544.32583.142.camel@localhost.localdomain> @ 2005-04-28 14:17 ` Duncan Sands 2 siblings, 0 replies; 52+ messages in thread From: Duncan Sands @ 2005-04-28 14:17 UTC (permalink / raw) To: Matthew Heaney; +Cc: comp.lang.ada > > (1) efficiency - suppose (for example) I want to transmit the > contents > > of my vector down a socket. > > You're not grokking the Ada95 way of doing things. Use the stream > operations for that. All containers (indeed, all non-limited types in > the predefined language environment) support streaming. By the way, I let this one drop, but in fact I wasn't thinking of sending/ receiving the whole vector down the socket, just parts of it: using the vector as an extensible buffer for building up and processing packets according to some communications protocol. The Element_Type would be Stream_Element in this case. Sending the vector object itself makes no sense in such a setting. Anyway, it's my fault for forgetting to say I only wanted to transmit slices. The other kind of thing I had in mind was linear algebra operations done by eg a Fortran library. For similar efficiency reasons you really have to be dealing with contiguous memory - copying things all over the place costs too much. No need to reply to this email by the way - you've already explained that Vector was not intended to necessarily be implemented as a contiguous array. Ciao, D. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-26 14:12 ` Georg Bauhaus 2005-04-26 14:39 ` Duncan Sands @ 2005-04-27 4:59 ` Jeffrey Carter 2005-04-27 7:21 ` Duncan Sands 2005-04-28 0:33 ` Randy Brukardt 1 sibling, 2 replies; 52+ messages in thread From: Jeffrey Carter @ 2005-04-27 4:59 UTC (permalink / raw) Georg Bauhaus wrote: > Duncan Sands wrote: > >> procedure Query_Elements >> (Container : in Vector; >> First_Index : in Index_Type; >> Last_Index : in Extended_Index; >> Process : not null access procedure (Elements : in >> Element_Array)); > > > Couldn't you use Cursors, IMNSHO, a unbounded-array abstraction doesn't need such operations, nor cursors. One should use it in a manner very similar to an array: for I in Index'First .. Last (Container) loop -- operate on Get (Container, I) end loop; During early discussions on AI-302 I implemented an unbounded-array package based on Ada.Strings.Unbounded, from the point of view that the basic operations in Unbounded are an instantiation of the unbounded-array with Character, Positive, and String. Here's the spec, if anyone's interested (lines may wrap): with Ada.Finalization; with System; generic -- Unbounded_Arrays type Index is (<>); type Element is private; type Fixed is array (Index range <>) of Element; with function "=" (Left : Element; Right : Element) return Boolean is <>; package Unbounded_Arrays is pragma Preelaborate; type Unbounded_Array is private; -- Initial value: null, equal to Null_Unbounded_Array, Length = 0. -- -- An Unbounded_Array is similar to a Fixed. It has a lower bound of Index'First, -- and an upper bound that can vary dynamically up to Index'Last. Null_Unbounded_Array : constant Unbounded_Array; -- Conversions function To_Unbounded (Source : Fixed) return Unbounded_Array; function "+" (Source : Fixed) return Unbounded_Array renames To_Unbounded; -- Converts Source to an Unbounded_Array. function To_Fixed (Source : Unbounded_Array) return Fixed; function "+" (Source : Unbounded_Array) return Fixed renames To_Fixed; -- Converts Source to a Fixed. If Source is null and there is no representation -- for a null Fixed, raises Constraint_Error. -- Size and index information Invalid_Index : exception; -- Raised by operations dealing with Index when the Index is invalid. function Last (Source : Unbounded_Array) return Index; -- Returns the Index of the last position occupied in Source. -- If Source is null, returns Index'First. -- Similar to the array operation Source'Last. type Count is mod System.Max_Binary_Modulus; function Length (Source : Unbounded_Array) return Count; -- Returns the number of occupied positions in Source. -- Similar to the array operation Source'Length. -- If the result is > Count'Last, raises Constraint_Error. -- Access to Elements function Get (From : Unbounded_Array; Location : Index) return Element; -- Returns the Element stored in From at position Location. -- Similar to the array operation From (Location). -- -- Precondition: -- Length (From) > 0 and -- Location in Index'First .. Last (From) raises Invalid_Index if violated procedure Put (Into : in out Unbounded_Array; Location : in Index; Item : in Element); -- Changes the Element stored in Into at position Location to be Item. -- Similar to the array operation Into (Location) := Item. -- -- Precondition: -- Length (Into) > 0 and -- Location in Index'First .. Last (Into) raises Invalid_Index if violated -- -- Postcondition: -- Get (Into, Location) = Item function Slice (From : Unbounded_Array; Low : Index; High : Index) return Fixed; function Slice (From : Unbounded_Array; Low : Index; High : Index) return Unbounded_Array; -- Return the slice of From with bounds Low .. High. Similar to the array operation -- From (Low .. High). -- The version that returns a Fixed returns a value with bounds of Low .. High. -- The version that returns an Unbounded_Array follows the specification of the type: -- the lower bound is always Index'First. -- -- Precondition: -- Low > High or -- (Length (From) > 0 and -- Low in Index'First .. Last (From) and -- High in Index'First .. Last (From) ) raises Invalid_Index if violated procedure Replace_Slice (Into : in out Unbounded_Array; Low : Index; High : Index; Replacement : Fixed); procedure Replace_Slice (Into : in out Unbounded_Array; Low : Index; High : Index; Replacement : Unbounded_Array); -- Replaces the slice of Into with bounds Low .. High with Replacement. -- Similar to the array operation Into (Low .. High) := Replacement. -- -- Preconditions: -- (Low > High and [Replacement'Length or Length (Replacement)] = 0) or -- (Length (Into) > 0 and -- Low in Index'First .. Last (Into) and -- High in Index'First .. Last (Into) ) raises Invalid_Index if violated -- -- [Replacement'Length or Length (Replacement)] = -- Length (Slice (Into, Low, High) ) raises Constraint_Error if violated -- -- Postcondition: -- Slice (Into, Low, High) = Replacement -- Concatenation procedure Append (Onto : in out Unbounded_Array; Item : in Element); procedure Append (Onto : in out Unbounded_Array; Item : in Fixed); procedure Append (Onto : in out Unbounded_Array; Item : in Unbounded_Array); -- Equivalent to Onto := Onto & Item. function "&" (Left : Unbounded_Array; Right : Unbounded_Array) return Unbounded_Array; function "&" (Left : Unbounded_Array; Right : Fixed) return Unbounded_Array; function "&" (Left : Fixed; Right : Unbounded_Array) return Unbounded_Array; function "&" (Left : Unbounded_Array; Right : Element) return Unbounded_Array; function "&" (Left : Element; Right : Unbounded_Array) return Unbounded_Array; -- Similar to the equivalent array operations. -- Equality function "=" (Left : Unbounded_Array; Right : Unbounded_Array) return Boolean; function "=" (Left : Unbounded_Array; Right : Fixed) return Boolean; function "=" (Left : Fixed; Right : Unbounded_Array) return Boolean; -- Returns True if Left and Right represent the same array value; False otherwise private -- Unbounded_Arrays -- Not specified by the language ... end Unbounded_Arrays; Unlike the Vector container that will be part of Ada 0X, this has no restrictions on the Index subtype. Any discrete type is acceptable. -- Jeff Carter "What I wouldn't give for a large sock with horse manure in it." Annie Hall 42 ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-27 4:59 ` Jeffrey Carter @ 2005-04-27 7:21 ` Duncan Sands 2005-04-28 2:54 ` Jeffrey Carter 2005-04-28 0:33 ` Randy Brukardt 1 sibling, 1 reply; 52+ messages in thread From: Duncan Sands @ 2005-04-27 7:21 UTC (permalink / raw) To: Jeffrey Carter; +Cc: comp.lang.ada Hi Jeffrey, > IMNSHO, a unbounded-array abstraction doesn't need such operations, nor > cursors. One should use it in a manner very similar to an array: > > for I in Index'First .. Last (Container) loop > -- operate on Get (Container, I) > end loop; that isn't the only way of using an array. The example of recursive algorithms taking subarrays was already mentioned. With the spec you included, it looks like you would have to use the Slice function to get a subarray - this means returning a copy on the stack, which is unacceptable if the array is long, and also problematic (=maybe very costly) if it contains controlled elements. Also, if you want to use a low-level or legacy routine that operates on an array, then you have a similar need to copy. Ciao, D. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-27 7:21 ` Duncan Sands @ 2005-04-28 2:54 ` Jeffrey Carter 2005-04-28 7:15 ` Duncan Sands 2005-04-28 7:18 ` Duncan Sands 0 siblings, 2 replies; 52+ messages in thread From: Jeffrey Carter @ 2005-04-28 2:54 UTC (permalink / raw) Duncan Sands wrote: > that isn't the only way of using an array. The example of recursive > algorithms taking subarrays was already mentioned. With the spec you > included, it looks like you would have to use the Slice function to > get a subarray - this means returning a copy on the stack, which is > unacceptable if the array is long, and also problematic (=maybe very > costly) if it contains controlled elements. The standard components are not intended to be suitable for situations with exceptional requirements, as Randy B has made clear on many occasions. But if you can't accept the cost of Slice, you can always write your recursive algorithm to take the object and the 2 bounds. > Also, if you want to use a low-level or legacy routine that operates > on an array, then you have a similar need to copy. I'm not clear how you'd expect to use a subprogram that operates on an array with a container, except by converting the contents to an array, or rewriting it to use the container. -- Jeff Carter "Son of a window-dresser." Monty Python & the Holy Grail 12 ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-28 2:54 ` Jeffrey Carter @ 2005-04-28 7:15 ` Duncan Sands 2005-04-28 12:27 ` Matthew Heaney ` (2 more replies) 2005-04-28 7:18 ` Duncan Sands 1 sibling, 3 replies; 52+ messages in thread From: Duncan Sands @ 2005-04-28 7:15 UTC (permalink / raw) To: Jeffrey Carter; +Cc: comp.lang.ada > > Also, if you want to use a low-level or legacy routine that operates > > on an array, then you have a similar need to copy. > > I'm not clear how you'd expect to use a subprogram that operates on an > array with a container, except by converting the contents to an array, > or rewriting it to use the container. When you have a container that is an extensible array, wanting to be able to directly access slices of it as an array seems normal (and useful) to me. I guess the point is that Vector is not an extensible array - the designers chose a more abstract design. Calling it "Vector" is just asking for confusion about what it is intended to be IMHO. Ciao, Duncan. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-28 7:15 ` Duncan Sands @ 2005-04-28 12:27 ` Matthew Heaney 2005-04-28 13:18 ` Matthew Heaney 2005-04-29 2:46 ` Jeffrey Carter 2 siblings, 0 replies; 52+ messages in thread From: Matthew Heaney @ 2005-04-28 12:27 UTC (permalink / raw) Duncan Sands <baldrick@free.fr> writes: > Calling it "Vector" is just asking for confusion about what it is > intended to be IMHO. Well, the C++ ISO standard (1998) didn't require that type std::vector be a contiguous array either. That intepretation was added later. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-28 7:15 ` Duncan Sands 2005-04-28 12:27 ` Matthew Heaney @ 2005-04-28 13:18 ` Matthew Heaney 2005-04-28 13:53 ` Duncan Sands 2005-04-29 2:46 ` Jeffrey Carter 2 siblings, 1 reply; 52+ messages in thread From: Matthew Heaney @ 2005-04-28 13:18 UTC (permalink / raw) Duncan Sands <baldrick@free.fr> writes: > When you have a container that is an extensible array, wanting to be > able to directly access slices of it as an array seems normal (and > useful) to me. In the STL way of doing things, you don't write algorithms in terms of a specific container. You write algorithms in terms of an "abstract container." Iterators allow you to view a container in a container-neutral way, as merely a "sequence of items," described using an iterator pair to bound the sequence, and with iterator operations for navigating among the elements of the sequence. What people sometims forget is that the STL is really an algorithms library. The containers are designed to allow you to apply an algorithm over the elements. The nice thing about the STL is that it treats all containers, including built-in arrays, the same. Actually, I said that kinda backwards. The STL treats all containers just like built-in arrays. This is because the STL follows the C machine model, in which items exist at addresses, and to view an item you deference a pointer with that address as its value. The problem you're having is that you have an algorithm written in terms of a specific container: an array. And now you want to apply that algorithm to a different kind of container: a vector. This is precisely the kind of problem the STL algorithm model was designed to solve. You can do this in Ada too, by writing algorithms in a way that is container neutral. See for example generic_anonymous_array_sort, which is declared like this: generic type Index_Type is (<>); with function Less (Left, Right : Index_Type) return Boolean is <>; with procedure Swap (Left, Right : Index_Type) is <>; procedure Generic_Anonymous_Array_Sort (First, Last : in Index_Type'Base); Now this is named "anonymous array sort," but in fact it works over any container (hint: vector) that supports indexing with a discrete index type. The generic formal subprogram Less compares two items in the "array", and Swap exchanges them. <http://charles.tigris.org/source/browse/charles/src/ai302/a-cgaaso.ads> Had you written your algorithm as above, then you wouldn't be having the difficulties you're having now. It would work for an array: procedure Op (A : in out Array_Type) is function Less (L, R : IT) return Boolean is begin return A (L) < A (R); end; procedure Swap (L, R : IT) is LE : constant ET := A (L); begin A (L) := A (R); A (R) := LE; end; procedure Sort is new Generic_Anonymous_Array_Sort (IT); begin Sort (A'First, A'Last); end; You'll note carefully that we don't pass the array type to the instantiation. That's why the algorithm is "container neutral." The algorithm above would work equally well for a vector: procedure Op (V : in out Vector) is function Less (L, R : IT) return Boolean is begin return V.Element (L) < V.Element (R); end; procedure Swap (L, R : IT) is LE : constant ET := V.Element (L); begin V.Replace_Element (L, V.Element (R)); V.Replace_Element (R, LE); end; procedure Sort is new Generic_Anonymous_Array_Sort (IT); begin Sort (First_Index (V), Last_Index (V)); end; You could even write an array-specific, or vector-specific algorithm, in terms of the non-specific algorithm, so you'd only have to write those little binder operations once: generic type IT is (<>); type ET is private; type Array_Type is array (IT range <>) of ET; procedure Generic_Array_Sort (A : in out Array_Type); procedure Generic_Array_Sort (A : in out Array_Type) is function Less (L, R : IT) return Boolean is begin return A (L) < A (R); end; procedure Swap (L, R : IT) is LE : constant ET := A (L); begin A (L) := A (R); A (R) := LE; end; procedure Sort is new Generic_Anonymous_Array_Sort (IT); begin Sort (A'First, A'Last); end Generic_Array_Sort; For the vector, you could say: generic with package Vector_Types is new Ada.Containers.Vectors (<>); procedure Generic_Vector_Sort (V : in out Vector); Or you could say: generic type IT is (<>); type ET (<>) is private; type VT (<>) is limited private; with function Element (V : VT; I : IT) return ET is <>; with proc Repl_Elem (V : VT; I : IT; E : ET) is <>; procedure Generic_Vector_Sort (V : in out VT); Now, don't you think that's better than what you did? > I guess the point is that Vector is not an extensible array - the > designers chose a more abstract design. An extensible array is the model for a vector, but of course a vector doesn't have to be implemented that way. You want to view the elements in a vector as a contiguous array, but that wouldn't confere any benefits unless if the underlying implementation is a contiguous array. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-28 13:18 ` Matthew Heaney @ 2005-04-28 13:53 ` Duncan Sands 0 siblings, 0 replies; 52+ messages in thread From: Duncan Sands @ 2005-04-28 13:53 UTC (permalink / raw) To: Matthew Heaney; +Cc: comp.lang.ada Hi Matthew, thanks for your detailed explanation. > > When you have a container that is an extensible array, wanting to be > > able to directly access slices of it as an array seems normal (and > > useful) to me. > > In the STL way of doing things, you don't write algorithms in terms of a > specific container. You write algorithms in terms of an "abstract > container." Iterators allow you to view a container in a > container-neutral way, as merely a "sequence of items," described using > an iterator pair to bound the sequence, and with iterator operations for > navigating among the elements of the sequence. ... > The problem you're having is that you have an algorithm written in terms > of a specific container: an array. And now you want to apply that > algorithm to a different kind of container: a vector. This is precisely > the kind of problem the STL algorithm model was designed to solve. > > You can do this in Ada too, by writing algorithms in a way that is > container neutral. See for example generic_anonymous_array_sort, which > is declared like this: ... > Had you written your algorithm as above, then you wouldn't be having the > difficulties you're having now. It would work for an array: ... > Now, don't you think that's better than what you did? You are certainly correct that when I quickly reworked the routine in question to take a vector rather than an array, I should have done it in a more abstract way, as in your example. As for the other code I have in mind, at some point things really have to be contiguous arrays for efficiency reasons. As pointed out in the AI discussion, efficiency was not the main goal of the container libraries - people who need something super efficient should write their own custom object. That's fine by me. > > I guess the point is that Vector is not an extensible array - the > > designers chose a more abstract design. > > An extensible array is the model for a vector, but of course a vector > doesn't have to be implemented that way. Extensible arrays are useful - it would have been nice to have them. > You want to view the elements in a vector as a contiguous array, but > that wouldn't confer any benefits unless if the underlying > implementation is a contiguous array. That's not entirely true, but in any case it would seem to go against the philosophy you outlined above. All the best, Duncan. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-28 7:15 ` Duncan Sands 2005-04-28 12:27 ` Matthew Heaney 2005-04-28 13:18 ` Matthew Heaney @ 2005-04-29 2:46 ` Jeffrey Carter 2005-04-29 18:22 ` Robert A Duff 2 siblings, 1 reply; 52+ messages in thread From: Jeffrey Carter @ 2005-04-29 2:46 UTC (permalink / raw) Duncan Sands wrote: > When you have a container that is an extensible array, wanting to be > able to directly access slices of it as an array seems normal (and > useful) to me. I guess the point is that Vector is not an extensible > array - the designers chose a more abstract design. Calling it "Vector" > is just asking for confusion about what it is intended to be IMHO. I agree about the name. To further complicate matters, there's a type Vector in the matrix-math packages, violating a long-standing convention that the standard packages are use-friendly, even in combination. -- Jeff Carter "Beyond 100,000 lines of code you should probably be coding in Ada." P. J. Plauger 26 ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-29 2:46 ` Jeffrey Carter @ 2005-04-29 18:22 ` Robert A Duff 0 siblings, 0 replies; 52+ messages in thread From: Robert A Duff @ 2005-04-29 18:22 UTC (permalink / raw) Jeffrey Carter <spam@spam.com> writes: > I agree about the name. To further complicate matters, there's a type > Vector in the matrix-math packages, violating a long-standing convention > that the standard packages are use-friendly, even in combination. That hardly seems like a big deal. Anyway, there's precedent. There are several types called File_Type. If you say 'use' on more than one I/O package, the exception names also clash. - Bob ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-28 2:54 ` Jeffrey Carter 2005-04-28 7:15 ` Duncan Sands @ 2005-04-28 7:18 ` Duncan Sands 1 sibling, 0 replies; 52+ messages in thread From: Duncan Sands @ 2005-04-28 7:18 UTC (permalink / raw) To: Jeffrey Carter; +Cc: comp.lang.ada > The standard components are not intended to be suitable for situations > with exceptional requirements, as Randy B has made clear on many > occasions... http://www.ada-auth.org/cgi-bin/cvsweb.cgi/AIs/AI-30302.TXT?rev=1.16 for those who are interested. Ciao, D. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-27 4:59 ` Jeffrey Carter 2005-04-27 7:21 ` Duncan Sands @ 2005-04-28 0:33 ` Randy Brukardt 2005-04-28 3:09 ` Jeffrey Carter 1 sibling, 1 reply; 52+ messages in thread From: Randy Brukardt @ 2005-04-28 0:33 UTC (permalink / raw) "Jeffrey Carter" <spam@spam.com> wrote in message news:R_Ebe.13911$lP1.2554@newsread1.news.pas.earthlink.net... ... > Unlike the Vector container that will be part of Ada 0X, this has no > restrictions on the Index subtype. Any discrete type is acceptable. Of course, you did that by having a goofy definition for Last: if Length(S0) = 0, Last(S0) = Index'First. if Length(S1) = 1, Last(S1) = Index'First. I would have preferred to allow any discrete type in Ada.Containers.Vectors, but I lost that battle because the natural instantiation would usually raise Constraint_Error for enumerations and modular types. Other solutions involving lots of special cases are possible, but ultimately, it wasn't thought to be worth it. Enumerations as a Vector index is pretty strange, but modular types seem useful to me. Randy. Randy. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-28 0:33 ` Randy Brukardt @ 2005-04-28 3:09 ` Jeffrey Carter 2005-04-28 20:55 ` Randy Brukardt 0 siblings, 1 reply; 52+ messages in thread From: Jeffrey Carter @ 2005-04-28 3:09 UTC (permalink / raw) Randy Brukardt wrote: > "Jeffrey Carter" <spam@spam.com> wrote in message > news:R_Ebe.13911$lP1.2554@newsread1.news.pas.earthlink.net... > ... > >>Unlike the Vector container that will be part of Ada 0X, this has no >>restrictions on the Index subtype. Any discrete type is acceptable. > > Of course, you did that by having a goofy definition for Last: > > if Length(S0) = 0, Last(S0) = Index'First. > if Length(S1) = 1, Last(S1) = Index'First. It doesn't seem so goofy to me. The test for a null unbounded array is "S = Null_Unbounded_Array" or Length (S) = 0. Last is pretty meaningless if the array is null, so having it return something meaningless seemed better than having it raise an exception. If Length (S) = 1, then Last = First, by definition, so Last (S) = Index'First. There didn't seem to be any way to return an appropriate result from To_Fixed if the unbounded array was null, so it raises an exception. The definition of Last was driven by the decision to allow null unbounded arrays regardless of the base range of Index. Currently, unconstrained Ada array types can exist that don't have null arrays. IIRC, this will be corrected in Ada 0X; if you allow them for arrays, you ought to allow them for the unbounded-array abstraction. -- Jeff Carter "Son of a window-dresser." Monty Python & the Holy Grail 12 ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-28 3:09 ` Jeffrey Carter @ 2005-04-28 20:55 ` Randy Brukardt 2005-04-29 2:54 ` Jeffrey Carter 2005-04-29 7:52 ` Dmitry A. Kazakov 0 siblings, 2 replies; 52+ messages in thread From: Randy Brukardt @ 2005-04-28 20:55 UTC (permalink / raw) "Jeffrey Carter" <spam@spam.com> wrote in message news:0uYbe.542$BE3.229@newsread2.news.pas.earthlink.net... ... > The definition of Last was driven by the decision to allow null > unbounded arrays regardless of the base range of Index. Currently, > unconstrained Ada array types can exist that don't have null arrays. > IIRC, this will be corrected in Ada 0X; if you allow them for arrays, > you ought to allow them for the unbounded-array abstraction. It's not really corrected in Ada 2006; it has additional aggregates that help, but the basic problem of having to mess with the bounds still exists: Obj : Some_Array (Enum'First .. Enum'Val(Enum'Pos(Enum'First)+Some_Length-1); doesn't work if Some_Length = 0 and there is no general way to fix that. You just have to special case Some_Length = 0 and that is unpleasant. The solution that Ada.Containers.Vector took to this problem is essentially to ban instantiating it with subtypes where 'First = 'Base'First. (OK, you can do the instantiation, but it will raise Constraint_Error.) One can argue whether that is the best solution, but it seems clear that all of the possible solutions are ugly. Randy. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-28 20:55 ` Randy Brukardt @ 2005-04-29 2:54 ` Jeffrey Carter 2005-04-29 18:34 ` Robert A Duff 2005-04-29 20:00 ` Randy Brukardt 2005-04-29 7:52 ` Dmitry A. Kazakov 1 sibling, 2 replies; 52+ messages in thread From: Jeffrey Carter @ 2005-04-29 2:54 UTC (permalink / raw) Randy Brukardt wrote: > It's not really corrected in Ada 2006; it has additional aggregates that > help, but the basic problem of having to mess with the bounds still exists: > > Obj : Some_Array (Enum'First .. > Enum'Val(Enum'Pos(Enum'First)+Some_Length-1); > > doesn't work if Some_Length = 0 and there is no general way to fix that. You > just have to special case Some_Length = 0 and that is unpleasant. Right, but you can say Obj : Some_Array := Some_Array'(<>); (I hope I've remembered the syntax correctly) and Obj'Length = 0; there was no way to do this before if Enum'First = Enum'Last. And you should be able to convert Obj into a corresponding unbounded array. > The solution that Ada.Containers.Vector took to this problem is essentially > to ban instantiating it with subtypes where 'First = 'Base'First. (OK, you > can do the instantiation, but it will raise Constraint_Error.) One can argue > whether that is the best solution, but it seems clear that all of the > possible solutions are ugly. Yes. I think this solution is uglier than having Last = First if Length = 0. -- Jeff Carter "Beyond 100,000 lines of code you should probably be coding in Ada." P. J. Plauger 26 ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-29 2:54 ` Jeffrey Carter @ 2005-04-29 18:34 ` Robert A Duff 2005-04-29 20:18 ` Randy Brukardt 2005-04-29 20:00 ` Randy Brukardt 1 sibling, 1 reply; 52+ messages in thread From: Robert A Duff @ 2005-04-29 18:34 UTC (permalink / raw) Jeffrey Carter <spam@spam.com> writes: > Randy Brukardt wrote: > > > It's not really corrected in Ada 2006; it has additional aggregates that > > help, but the basic problem of having to mess with the bounds still exists: > > Obj : Some_Array (Enum'First .. > > Enum'Val(Enum'Pos(Enum'First)+Some_Length-1); > > doesn't work if Some_Length = 0 and there is no general way to fix > > that. You > > just have to special case Some_Length = 0 and that is unpleasant. > > Right, but you can say > > Obj : Some_Array := Some_Array'(<>); > > (I hope I've remembered the syntax correctly) I don't see any such syntax in the draft RM, and I'm not sure which syntax you're referring to. >... and Obj'Length = 0; there > was no way to do this before if Enum'First = Enum'Last. And you should > be able to convert Obj into a corresponding unbounded array. Every array object has a 'Last in Ada. It's simply impossible to create an array with a 'Last that does not exist. So a zero-length array whose 'First is the lower bound of the base range is simply impossible. I don't think this has changed in Ada 2006. I don't think it's a problem, either. If you want zero-length arrays, then you're counting things, and signed integers are the appropriate index type. Arrays indexed by enums are usually things like tables, and therefore not empty. Can you think of an example where you want an empty array, and a enum or modular type is appropriate for the index? I can't think of any at the moment. > > The solution that Ada.Containers.Vector took to this problem is essentially > > to ban instantiating it with subtypes where 'First = 'Base'First. (OK, you > > can do the instantiation, but it will raise Constraint_Error.) One can argue > > whether that is the best solution, but it seems clear that all of the > > possible solutions are ugly. > > Yes. I think this solution is uglier than having Last = First if Length = 0. Last = First seems just plain wrong, to me. You want to loop from First up to Last -- if Length = 0, that loop had better not do anything. - Bob ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-29 18:34 ` Robert A Duff @ 2005-04-29 20:18 ` Randy Brukardt 0 siblings, 0 replies; 52+ messages in thread From: Randy Brukardt @ 2005-04-29 20:18 UTC (permalink / raw) "Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message news:wccfyx94el8.fsf@shell01.TheWorld.com... ... > I don't think it's a problem, either. If you want zero-length arrays, > then you're counting things, and signed integers are the appropriate > index type. Arrays indexed by enums are usually things like tables, > and therefore not empty. Can you think of an example where you want > an empty array, and a enum or modular type is appropriate for the index? > I can't think of any at the moment. I can't think of any for enum, but for modular, it makes perfect sense. Remember, a modular type is the only way to get an unsigned type in Ada, and thus it's not unusual to declare such a value and give it a range, use it in arrays, etc. Yes, it would be worlds better if there was a real, checked, unsigned integer type in Ada (and I'd use that instead), but that was screwed up by the Ada 9X team, and it isn't going to get fixed. Most of my modern programs have a useful unsigned type somewhere near the start: type Counter_Type is mod 2**32; with various subtypes of that around. It's also not unusual to use a 16-bit modular type when space is tight. Now, I suppose if you're willing to assume that every Ada compiler supports 64-bit integers, supports unsigned storage representations, and doesn't do 64-bit operations when unsigned 32-bit operations will do, then you could avoid using modular types in this way. But the above doesn't describe any Ada compilers that I have used. Once those types are in wide use, it isn't usual for them to be used to index some data structure. And thus you get null array slices of modular types and the like. Randy. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-29 2:54 ` Jeffrey Carter 2005-04-29 18:34 ` Robert A Duff @ 2005-04-29 20:00 ` Randy Brukardt 2005-04-30 4:06 ` Jeffrey Carter 1 sibling, 1 reply; 52+ messages in thread From: Randy Brukardt @ 2005-04-29 20:00 UTC (permalink / raw) "Jeffrey Carter" <spam@spam.com> wrote in message news:hlhce.936$HL2.780@newsread3.news.pas.earthlink.net... > Randy Brukardt wrote: ... > Right, but you can say > > Obj : Some_Array := Some_Array'(<>); > > (I hope I've remembered the syntax correctly) and Obj'Length = 0; there > was no way to do this before if Enum'First = Enum'Last. And you should > be able to convert Obj into a corresponding unbounded array. I have no idea what you are talking about. That would represent an array with exactly one default initialized element -- if it was allowed, which it is not. That's because "<>" is only allowed with named notation, meaning you have to give the bounds in the aggregate (or use "others"). Randy. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-29 20:00 ` Randy Brukardt @ 2005-04-30 4:06 ` Jeffrey Carter 0 siblings, 0 replies; 52+ messages in thread From: Jeffrey Carter @ 2005-04-30 4:06 UTC (permalink / raw) Randy Brukardt wrote: > I have no idea what you are talking about. That would represent an array > with exactly one default initialized element -- if it was allowed, which it > is not. That's because "<>" is only allowed with named notation, meaning you > have to give the bounds in the aggregate (or use "others"). Apparently, neither do I. That's what I get for relying on my memory. I seem to recall something to allow declaration of a null aggregate for any array type, but I've now spent some time searching the AIs and can't find it. Sorry. -- Jeff Carter "Spam! Spam! Spam! Spam! Spam! Spam! Spam! Spam!" Monty Python's Flying Circus 53 ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-28 20:55 ` Randy Brukardt 2005-04-29 2:54 ` Jeffrey Carter @ 2005-04-29 7:52 ` Dmitry A. Kazakov 2005-04-29 20:26 ` Randy Brukardt 1 sibling, 1 reply; 52+ messages in thread From: Dmitry A. Kazakov @ 2005-04-29 7:52 UTC (permalink / raw) On Thu, 28 Apr 2005 15:55:25 -0500, Randy Brukardt wrote: > "Jeffrey Carter" <spam@spam.com> wrote in message > news:0uYbe.542$BE3.229@newsread2.news.pas.earthlink.net... > ... >> The definition of Last was driven by the decision to allow null >> unbounded arrays regardless of the base range of Index. Currently, >> unconstrained Ada array types can exist that don't have null arrays. >> IIRC, this will be corrected in Ada 0X; if you allow them for arrays, >> you ought to allow them for the unbounded-array abstraction. > > It's not really corrected in Ada 2006; it has additional aggregates that > help, but the basic problem of having to mess with the bounds still exists: > > Obj : Some_Array (Enum'First .. > Enum'Val(Enum'Pos(Enum'First)+Some_Length-1); > > doesn't work if Some_Length = 0 and there is no general way to fix that. You > just have to special case Some_Length = 0 and that is unpleasant. > > The solution that Ada.Containers.Vector took to this problem is essentially > to ban instantiating it with subtypes where 'First = 'Base'First. (OK, you > can do the instantiation, but it will raise Constraint_Error.) One can argue > whether that is the best solution, but it seems clear that all of the > possible solutions are ugly. I wonder if introducing ranges as a type class could mend this. Provided a fictitious attribute Enum'Range (0) would return a null-length range, one could then create empty arrays without referencing to any concrete index bounds. But then Obj'First and Obj'Last could potentially raise Constraint_Error, which might appear unpleasant but perfectly consistent. Could there be a distributed overhead in the implementations of 'First and 'Last then? -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-29 7:52 ` Dmitry A. Kazakov @ 2005-04-29 20:26 ` Randy Brukardt 2005-04-30 9:24 ` Dmitry A. Kazakov 0 siblings, 1 reply; 52+ messages in thread From: Randy Brukardt @ 2005-04-29 20:26 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message news:1wjh6qsazg3rg$.lupowyuqu0tw$.dlg@40tude.net... ... > I wonder if introducing ranges as a type class could mend this. Provided a > fictitious attribute Enum'Range (0) would return a null-length range, one > could then create empty arrays without referencing to any concrete index > bounds. But then Obj'First and Obj'Last could potentially raise > Constraint_Error, which might appear unpleasant but perfectly consistent. > Could there be a distributed overhead in the implementations of 'First and > 'Last then? Yes, there would be a distributed overhead. For Janus/Ada (the only compiler for which I can speak definitively), in the general case array bounds are stored in a descriptor record, along with a dimension length and a pointer to the data. The dimension length is really redundant; I don't think most compilers store it separately. In order to be able to represent an array as you say, all compilers would have to store the dimension length and presumably a bit mask to specify which bounds are invalid and raise C_E if explicitly touched. And of course all references to 'First and 'Last would have to check the bit mask. Not too expensive, but certainly a significant change to compilers and some additional overhead. Array indexing in the general case subtracts 'First from the calculated value, so I don't think it would make sense to allow 'First to be an invalid value - at least not unless the length of the array was 0 (in which case it doesn't matter). But adding overhead to array indexing operations is not going to win anyone friends. :-) More seriously, I think it would be a non-starter. You also have the problem of making the range check for any value when one or the other bound could be invalid. More overhead in a particularly bad spot. So I don't think this idea is going to fly. Randy. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-29 20:26 ` Randy Brukardt @ 2005-04-30 9:24 ` Dmitry A. Kazakov 2005-05-02 3:21 ` Randy Brukardt 0 siblings, 1 reply; 52+ messages in thread From: Dmitry A. Kazakov @ 2005-04-30 9:24 UTC (permalink / raw) On Fri, 29 Apr 2005 15:26:31 -0500, Randy Brukardt wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message > news:1wjh6qsazg3rg$.lupowyuqu0tw$.dlg@40tude.net... > ... >> I wonder if introducing ranges as a type class could mend this. Provided a >> fictitious attribute Enum'Range (0) would return a null-length range, one >> could then create empty arrays without referencing to any concrete index >> bounds. But then Obj'First and Obj'Last could potentially raise >> Constraint_Error, which might appear unpleasant but perfectly consistent. >> Could there be a distributed overhead in the implementations of 'First and >> 'Last then? > > Yes, there would be a distributed overhead. For Janus/Ada (the only compiler > for which I can speak definitively), in the general case array bounds are > stored in a descriptor record, along with a dimension length and a pointer > to the data. The dimension length is really redundant; I don't think most > compilers store it separately. In order to be able to represent an array as > you say, all compilers would have to store the dimension length and > presumably a bit mask to specify which bounds are invalid and raise C_E if > explicitly touched. And of course all references to 'First and 'Last would > have to check the bit mask. Not too expensive, but certainly a significant > change to compilers and some additional overhead. > > Array indexing in the general case subtracts 'First from the calculated > value, so I don't think it would make sense to allow 'First to be an invalid > value - at least not unless the length of the array was 0 (in which case it > doesn't matter). But adding overhead to array indexing operations is not > going to win anyone friends. :-) More seriously, I think it would be a > non-starter. I presume the compilers keep A'First and A'Last in T'Base, so all internal index evaluations need not to check if 'First or 'Last is in T. BTW, it seems that A'First is in T'Base anyway! I failed to find any clear reference in ARM, but the following: X : String := ""; begin Ada.Text_IO.Put_Line (Integer'Image (X'First)); happily prints 0 with GNAT, no Constraint_Error! As long as no empty enumeration *types* and no "mod 0" *types* allowed, there is always a way to have A'First in T'Base (or better to say "T'Implementation"). So the problem as I see it is with A'Last. Considering T is mod 1 implemented by some unsigned type, then A'First = 0, and 'Last is what? It would be problematic to force all modular types to be internally implemented as signed. Yet one could have A'Last=T'Implementation'First and A'First=T'Implementation'First+1 for empty arrays. Who cares? Now consider the following test: type T is mod 1; type T_Array is array (T range <>); X : T_Array := <somehow-obtained-empty-array>; begin for I in X'Range loop -- This is OK null; end loop; for I in X'First..X'Last loop -- This cannot be OK null; end loop; Which is in a perfect contradiction with 3.6.2(7). It could probably be mended too if we had universal index types. But this is yet another story. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-04-30 9:24 ` Dmitry A. Kazakov @ 2005-05-02 3:21 ` Randy Brukardt 2005-05-02 17:04 ` Dmitry A. Kazakov 0 siblings, 1 reply; 52+ messages in thread From: Randy Brukardt @ 2005-05-02 3:21 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message news:txah28f4zlnp$.1pqea609lovyn.dlg@40tude.net... ... > Now consider the following test: > > type T is mod 1; > type T_Array is array (T range <>); > X : T_Array := <somehow-obtained-empty-array>; > begin > for I in X'Range loop -- This is OK > null; > end loop; > for I in X'First..X'Last loop -- This cannot be OK > null; > end loop; > > Which is in a perfect contradiction with 3.6.2(7). It could probably be > mended too if we had universal index types. But this is yet another story. In Ada as currently defined, you would get Constraint_Error from the attempt to define the bounds. That happens with string types: type T is mod 1; type T_Array is array (T range <>) of Character; X : T_Array := ""; -- Raises Constraint_Error There is actually an ACATS test to check this. (I remember it because one vendor disputed the test; it was upheld.) You'd get the same result if there was a way to describe a null array aggregate: X : T_Array := (null array); -- Not Ada, and if it was, it would raise Constraint_Error here. It turns out that Interfaces.C.To_C has a similar problem, and it too raises Constraint_Error for a null string (if not null terminated). Of course, you could conceivably use other rules, but they'd be incompatible with the current ones, which wouldn't be a problem in cases like these, but they might be in other cases. Randy. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-05-02 3:21 ` Randy Brukardt @ 2005-05-02 17:04 ` Dmitry A. Kazakov 2005-05-02 18:57 ` Robert A Duff 0 siblings, 1 reply; 52+ messages in thread From: Dmitry A. Kazakov @ 2005-05-02 17:04 UTC (permalink / raw) On Sun, 1 May 2005 22:21:42 -0500, Randy Brukardt wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message > news:txah28f4zlnp$.1pqea609lovyn.dlg@40tude.net... > ... >> Now consider the following test: >> >> type T is mod 1; >> type T_Array is array (T range <>); >> X : T_Array := <somehow-obtained-empty-array>; >> begin >> for I in X'Range loop -- This is OK >> null; >> end loop; >> for I in X'First..X'Last loop -- This cannot be OK >> null; >> end loop; >> >> Which is in a perfect contradiction with 3.6.2(7). It could probably be >> mended too if we had universal index types. But this is yet another story. > > In Ada as currently defined, you would get Constraint_Error from the attempt > to define the bounds. That happens with string types: > > type T is mod 1; > type T_Array is array (T range <>) of Character; > X : T_Array := ""; -- Raises Constraint_Error > > There is actually an ACATS test to check this. (I remember it because one > vendor disputed the test; it was upheld.) So "" is not allowed for any string type which index is not a subtype/derived type S of some base type T, such that S'First>T'First. With a nice consequence that: type T1 is range -2147483647..0; type T1_Array is array (T range <>) of Character; type T2 is range -2147483648..0; type T2_Array is array (T range <>) of Character; type T3 is range -2147483649..0; type T3_Array is array (T range <>) of Character; X : T1_Array := ""; -- Legal Y : T2_Array := ""; -- Illegal Z : T3_Array := ""; -- Again legal!!!!! That's really funny. What is so special in the number -2147483648? Should it mean that potentially no program that uses negative indices and empty strings is portable, you never know where *a* built-in integer type may start? -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-05-02 17:04 ` Dmitry A. Kazakov @ 2005-05-02 18:57 ` Robert A Duff 2005-05-03 8:14 ` Dmitry A. Kazakov 0 siblings, 1 reply; 52+ messages in thread From: Robert A Duff @ 2005-05-02 18:57 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > So "" is not allowed for any string type which index is not a > subtype/derived type S of some base type T, such that S'First>T'First. With > a nice consequence that: > > type T1 is range -2147483647..0; ^^^^^^^^^^ You misspelled "-2**31". ;-) > type T1_Array is array (T range <>) of Character; > > type T2 is range -2147483648..0; > type T2_Array is array (T range <>) of Character; > > type T3 is range -2147483649..0; > type T3_Array is array (T range <>) of Character; > > X : T1_Array := ""; -- Legal > Y : T2_Array := ""; -- Illegal > Z : T3_Array := ""; -- Again legal!!!!! Well, Ada's integer types are intended to be hardware-oriented, for better or worse. This empty-array issue is an extremely rare case. Consider: X1: T1 := T1'First; X2: T2 := T2'First; X3: T3 := T3'First; X1 := (X1-1)/2; X2 := (X2-1)/2; X3 := (X3-1)/2; Which of the above will raise Constraint_Error (due to overflow on the subtraction)? Well it's entirely implementation defined, but given typical hardware and compiler, you'll get the same behavior as with the empty strings. Seems to me that arithmetic is a more common case. I mean, nobody makes arrays starting near -2**31. > That's really funny. What is so special in the number -2147483648? Should > it mean that potentially no program that uses negative indices and empty > strings is portable, you never know where *a* built-in integer type may > start? Well, you know *something*. The base range has to be symmetric about zero (or have one extra negative value). And you have control: type T2_Base is range (-2**31)-1..0; subtype T2 is T2_Base range -2**31..0; type T2_Array is array (T2 range <>) of Character; Now you can have empty string literals (presuming your compiler supports signed integers as big as T2_Base). I admit this stuff is a little bit error prone. That's what you get when the language is hardware oriented (for efficiency, of course). - Bob ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-05-02 18:57 ` Robert A Duff @ 2005-05-03 8:14 ` Dmitry A. Kazakov 2005-05-03 23:30 ` Robert A Duff 0 siblings, 1 reply; 52+ messages in thread From: Dmitry A. Kazakov @ 2005-05-03 8:14 UTC (permalink / raw) On 02 May 2005 14:57:15 -0400, Robert A Duff wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > >> So "" is not allowed for any string type which index is not a >> subtype/derived type S of some base type T, such that S'First>T'First. With >> a nice consequence that: >> >> type T1 is range -2147483647..0; > ^^^^^^^^^^ > You misspelled "-2**31". ;-) Actually it is 1 - 2**31 (:-)), but the point is that it can be any number! The standard is silent about powers of 2. Can I write a compiler with a built-in integer type Short_Int which range is -5..5? Is this illegal? >> type T1_Array is array (T range <>) of Character; >> >> type T2 is range -2147483648..0; >> type T2_Array is array (T range <>) of Character; >> >> type T3 is range -2147483649..0; >> type T3_Array is array (T range <>) of Character; >> >> X : T1_Array := ""; -- Legal >> Y : T2_Array := ""; -- Illegal >> Z : T3_Array := ""; -- Again legal!!!!! > > Well, Ada's integer types are intended to be hardware-oriented, for > better or worse. This empty-array issue is an extremely rare case. > Consider: > > X1: T1 := T1'First; > X2: T2 := T2'First; > X3: T3 := T3'First; > > X1 := (X1-1)/2; > X2 := (X2-1)/2; > X3 := (X3-1)/2; > > Which of the above will raise Constraint_Error (due to overflow on the > subtraction)? Well it's entirely implementation defined, but given > typical hardware and compiler, you'll get the same behavior as with the > empty strings. How would you formally, in the sense ARM 1.1.5, classify the error above and one of using empty strings? It seems to me that to rely on Constraint_Error above would be a bounded error. But programs using empty strings would be illegal Ada programs. > Seems to me that arithmetic is a more common case. I mean, nobody makes > arrays starting near -2**31. I don't think that statistical approach is appropriate here. Anyway it makes an implementation of many generic algorithms and container libraries very difficult if possible. > I admit this stuff is a little bit error prone. That's what you get > when the language is hardware oriented (for efficiency, of course). Is this the only way to achieve efficiency? -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-05-03 8:14 ` Dmitry A. Kazakov @ 2005-05-03 23:30 ` Robert A Duff 2005-05-05 10:51 ` Dmitry A. Kazakov 0 siblings, 1 reply; 52+ messages in thread From: Robert A Duff @ 2005-05-03 23:30 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On 02 May 2005 14:57:15 -0400, Robert A Duff wrote: > > > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > > > >> So "" is not allowed for any string type which index is not a > >> subtype/derived type S of some base type T, such that S'First>T'First. With > >> a nice consequence that: > >> > >> type T1 is range -2147483647..0; > > ^^^^^^^^^^ > > You misspelled "-2**31". ;-) > > Actually it is 1 - 2**31 (:-)), Right. Which proves my point, which is that your point would be clearer if you used "2**31" or whatever instead of putting in a literal. Without underscores, even! >... but the point is that it can be any number! Right. > The standard is silent about powers of 2. As well it should be, IMHO. >... Can I write a compiler with a > built-in integer type Short_Int which range is -5..5? Is this illegal? Yes. But the built-in types are irrelevant. What's relevant is the "base range" of a type. The RM says it has to be (almost) symmetric about zero. So, yes, if you say "type T is range 2..3" the base range could be -5..5 (according to the RM). > >> type T1_Array is array (T range <>) of Character; > >> > >> type T2 is range -2147483648..0; > >> type T2_Array is array (T range <>) of Character; > >> > >> type T3 is range -2147483649..0; > >> type T3_Array is array (T range <>) of Character; > >> > >> X : T1_Array := ""; -- Legal > >> Y : T2_Array := ""; -- Illegal > >> Z : T3_Array := ""; -- Again legal!!!!! > > > > Well, Ada's integer types are intended to be hardware-oriented, for > > better or worse. This empty-array issue is an extremely rare case. > > Consider: > > > > X1: T1 := T1'First; > > X2: T2 := T2'First; > > X3: T3 := T3'First; > > > > X1 := (X1-1)/2; > > X2 := (X2-1)/2; > > X3 := (X3-1)/2; > > > > Which of the above will raise Constraint_Error (due to overflow on the > > subtraction)? Well it's entirely implementation defined, but given > > typical hardware and compiler, you'll get the same behavior as with the > > empty strings. > > How would you formally, in the sense ARM 1.1.5, classify the error above > and one of using empty strings? It seems to me that to rely on > Constraint_Error above would be a bounded error. But programs using empty > strings would be illegal Ada programs. There's no "bounded error" here. These things raise C_E, or return the correct result. If every intermediate result is in the base range, the RM requires correct results; otherwise, it allows C_E or correct results. RM-4.9(34..35) might make some such things illegal -- I'm not sure. (Illegal = compile-time error.) > > Seems to me that arithmetic is a more common case. I mean, nobody makes > > arrays starting near -2**31. > > I don't think that statistical approach is appropriate here. Anyway it > makes an implementation of many generic algorithms and container libraries > very difficult if possible. I don't see a big problem here. If you're counting things, use signed integers, and start counting at zero or one. If you're using enums or modulars, you're not "counting", and zero-length arrays/vectors/whatever make no sense. > > I admit this stuff is a little bit error prone. That's what you get > > when the language is hardware oriented (for efficiency, of course). > > Is this the only way to achieve efficiency? No. I think I can design an efficent language that doesn't have these problems. But it ain't Ada. - Bob ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-05-03 23:30 ` Robert A Duff @ 2005-05-05 10:51 ` Dmitry A. Kazakov 2005-05-07 1:20 ` Matthew Heaney 0 siblings, 1 reply; 52+ messages in thread From: Dmitry A. Kazakov @ 2005-05-05 10:51 UTC (permalink / raw) On 03 May 2005 19:30:29 -0400, Robert A Duff wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > >> I don't think that statistical approach is appropriate here. Anyway it >> makes an implementation of many generic algorithms and container libraries >> very difficult if possible. > > I don't see a big problem here. If you're counting things, use signed > integers, and start counting at zero or one. If you're using enums or > modulars, you're not "counting", and zero-length arrays/vectors/whatever > make no sense. Come on, empty set appear *before* number and arithmetic. Further, to be countable is much weaker than to be ordered. In an imaginary, better Ada there should be unordered, uncountable types which would still allow containers. There would be no way to enumerate elements in such container, but for any given X it would be possible to Is_In (X, C). Even for such weak types there should be empty containers such that Is_In returns false for any X. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-05-05 10:51 ` Dmitry A. Kazakov @ 2005-05-07 1:20 ` Matthew Heaney 2005-05-07 7:17 ` Dmitry A. Kazakov 0 siblings, 1 reply; 52+ messages in thread From: Matthew Heaney @ 2005-05-07 1:20 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > In an imaginary, better Ada there should be unordered, uncountable > types which would still allow containers. There would be no way to > enumerate elements in such container, but for any given X it would be > possible to Is_In (X, C). Even for such weak types there should be > empty containers such that Is_In returns false for any X. Tell me, Dmitry, how do you intend for predicate Is_In to be implemented, if the objects in the container are neither ordered nor enumerable? ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Ada.Containers.Vectors - querying multiple elements 2005-05-07 1:20 ` Matthew Heaney @ 2005-05-07 7:17 ` Dmitry A. Kazakov 0 siblings, 0 replies; 52+ messages in thread From: Dmitry A. Kazakov @ 2005-05-07 7:17 UTC (permalink / raw) On Sat, 07 May 2005 01:20:21 GMT, Matthew Heaney wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > >> In an imaginary, better Ada there should be unordered, uncountable >> types which would still allow containers. There would be no way to >> enumerate elements in such container, but for any given X it would be >> possible to Is_In (X, C). Even for such weak types there should be >> empty containers such that Is_In returns false for any X. > > Tell me, Dmitry, how do you intend for predicate Is_In to be > implemented, if the objects in the container are neither ordered nor > enumerable? That's an implementation detail! (:-)) But OK, here are many ways depending on the concrete case. For example: an unordered, uncountable index is just a public view. The container is free keep an array indexed by plain numbers. Objects might be uncountable, but we can count containers instead. So we attach the list of containers in which an object participates to the object. Or else we could maintain a global incidence matrix ... and so on and so far. My point actually was: empty containers and index ranges (sets) must be! -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
end of thread, other threads:[~2005-05-07 7:17 UTC | newest] Thread overview: 52+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <1114515832.32583.41.camel@localhost.localdomain> [not found] ` <426E5A0B.3010109@on2.com> 2005-04-26 16:00 ` Ada.Containers.Vectors - querying multiple elements Duncan Sands 2005-04-28 0:54 ` Randy Brukardt 2005-04-26 11:43 Duncan Sands 2005-04-26 14:12 ` Georg Bauhaus 2005-04-26 14:39 ` Duncan Sands 2005-04-26 15:44 ` Matthew Heaney 2005-04-26 16:05 ` Duncan Sands [not found] ` <1114531544.32583.142.camel@localhost.localdomain> [not found] ` <426E72C3.9070108@on2.com> 2005-04-26 16:59 ` Duncan Sands [not found] ` <1114534751.32583.144.camel@localhost.localdomain> [not found] ` <426E73DE.2070505@on2.com> 2005-04-26 17:08 ` Duncan Sands 2005-04-26 18:17 ` Martin Dowie 2005-04-26 18:48 ` Duncan Sands 2005-04-26 18:59 ` Duncan Sands 2005-04-26 19:05 ` Georg Bauhaus 2005-04-26 20:34 ` Duncan Sands 2005-04-26 21:47 ` Dr. Adrian Wrigley 2005-04-26 23:21 ` Marius Amado Alves [not found] ` <9decddc0038674b3c85aeceefb4d3b83@netcabo.pt> 2005-04-27 8:15 ` Duncan Sands [not found] ` <1114589729.10418.13.camel@localhost.localdomain> 2005-04-27 11:49 ` Marius Amado Alves 2005-04-28 0:36 ` Randy Brukardt 2005-04-28 7:09 ` Duncan Sands 2005-04-27 11:10 ` Georg Bauhaus 2005-04-27 11:57 ` Duncan Sands 2005-04-28 14:17 ` Duncan Sands 2005-04-27 4:59 ` Jeffrey Carter 2005-04-27 7:21 ` Duncan Sands 2005-04-28 2:54 ` Jeffrey Carter 2005-04-28 7:15 ` Duncan Sands 2005-04-28 12:27 ` Matthew Heaney 2005-04-28 13:18 ` Matthew Heaney 2005-04-28 13:53 ` Duncan Sands 2005-04-29 2:46 ` Jeffrey Carter 2005-04-29 18:22 ` Robert A Duff 2005-04-28 7:18 ` Duncan Sands 2005-04-28 0:33 ` Randy Brukardt 2005-04-28 3:09 ` Jeffrey Carter 2005-04-28 20:55 ` Randy Brukardt 2005-04-29 2:54 ` Jeffrey Carter 2005-04-29 18:34 ` Robert A Duff 2005-04-29 20:18 ` Randy Brukardt 2005-04-29 20:00 ` Randy Brukardt 2005-04-30 4:06 ` Jeffrey Carter 2005-04-29 7:52 ` Dmitry A. Kazakov 2005-04-29 20:26 ` Randy Brukardt 2005-04-30 9:24 ` Dmitry A. Kazakov 2005-05-02 3:21 ` Randy Brukardt 2005-05-02 17:04 ` Dmitry A. Kazakov 2005-05-02 18:57 ` Robert A Duff 2005-05-03 8:14 ` Dmitry A. Kazakov 2005-05-03 23:30 ` Robert A Duff 2005-05-05 10:51 ` Dmitry A. Kazakov 2005-05-07 1:20 ` Matthew Heaney 2005-05-07 7:17 ` Dmitry A. Kazakov
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox