From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,f2690a5e963b61b6 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news3.google.com!news.glorb.com!border1.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!feed4.newsreader.com!newsreader.com!feed7.newsreader.com!newsreader.com!hwmnpeer01.lga!hwmedia!hw-filter.lga!fe06.lga.POSTED!53ab2750!not-for-mail From: Mikhail Terekhov User-Agent: Mozilla Thunderbird 1.0.2 (Windows/20050317) X-Accept-Language: en-us, en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: GCC 4.0 Ada.Containers Cursor danger. References: <1120474891.635131.216700@g44g2000cwa.googlegroups.com> <42cb8d21$0$22761$9b4e6d93@newsread2.arcor-online.net> <42cd064c$0$10817$9b4e6d93@newsread4.arcor-online.net> <42cda8c4$0$22780$9b4e6d93@newsread2.arcor-online.net> <1u3hh2597i4ne$.1ryetugksbmus.dlg@40tude.net> <1120834341.499757.133770@g43g2000cwa.googlegroups.com> <1121093867.964444.232420@g14g2000cwa.googlegroups.com> <42d2bc2d$0$20148$9b4e6d93@newsread2.arcor-online.net> <1121134291.379399.79460@z14g2000cwz.googlegroups.com> <42d46b51$0$18005$9b4e6d93@newsread4.arcor-online.net> <42d6ef47$0$7644$9b4e6d93@newsread2.arcor-online.net> In-Reply-To: <42d6ef47$0$7644$9b4e6d93@newsread2.arcor-online.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Message-ID: X-Trace: dkoicekneficefklblgojnnjdcmamiclnichhedchlkkmadllkofpbhdcomdnfbnkocbaabgcpdeoapbkgngfglkbnbokccpdcolfpjjeflpngljdjbfanejebbbfpaobcfagklmibllijll NNTP-Posting-Date: Mon, 18 Jul 2005 20:11:08 MST Date: Mon, 18 Jul 2005 23:11:16 -0400 Xref: g2news1.google.com comp.lang.ada:3667 Date: 2005-07-18T23:11:16-04:00 List-Id: Georg Bauhaus wrote: > Mikhail Terekhov wrote: > >> - First is that all containers have an order. >> Again, sets and hashes in general are *not ordered*. >> To impose an order on them standard needs to put a >> restriction on implementarion algorithms. > > > Ada.Containers require that the elements of a set say can be > had one after the other through iteration using cursors. That is right. That is exactly what I'm trying to say. Except one thing. There is no need for cursors during iterations. > I can hardly think of this as a restriction in practice. This is not a restriction. This is clarity. Cursors are not needed for iteration. Cursors are a special case, they should be marked as such. > On the contrary, why should I be satisfied with just membership No you shouldn't. But membership test is a most basic operation which has exactly the same semantics for _any_ container type. This operation should be present for all container types and it doesn't depend on order or cursors. > test? Or with a fixed set of operations on sets? Or why should I > abandon sets in favor of some other containers, because they > fit better with someone's ideas of how a mathematical structure > is sometimes defined? ;-) No, you shouldn't be limited with a fixed set of operations on sets and you shouldn't abandon sets. I'm not really sure where did you get this idea from. This is almost in reverse of what I'm trying to say. You should be able to chose whatever abstraction fits your application best and this abstraction should be familiar to anyone who will read your source code. Sorted sets and hashes probably are very useful in some special cases, but they are just a special cases. It is not a very good idea to put some special cases as a _basis_ of the standard library. There is nothing wrong to put them into standard library, but only as an addition to or specialization of basic abstractions. > > Say I want a subset B of A, > > B := {x: x in A | x >= 0}; > > This could be done using a generic algorithm which is similar > to the Generic_Find algorithm that Matt has presented in that > there will be a generic formal procedure that acts > as the predicate ">= 0?". > > generic > with function Predicate(C: Cursor) return Boolean; > function Subset(S: Set) return Set; > > function Subset(S: Set) return Set is > C: Cursor := First(S); > result: Set; > begin > while Has_Element(C) loop > if Predicate(C) then > Include(result, Element(C)); > end if; > Next(C); > end loop; > return result; > end Subset; > > (The example doesn't really need iteration using cursors explicitly > because Iterate(S, Conditional_Include'access) or similar will do. > However, that's just an ad hoc example that I could think of and I wanted > to show cursors :-) That is wonderful! Almost any example of using cursor doesn't really need cursors. Why this burden then? > > >> You example >> is completely legal generic function in the current >> Ada.Containers framework. But if you decide at some >> point to add unordered containers, then you generic >> function became invalid because for unordered containers >> "first" and "last" have no sence at all. > > > For me, First and Last (or whatever you call them) *do* make sense > for any reasonable notion of a set in programming, sorted or not, > even when used in computer science. > Their purpose then is to start and end the enumeration of the elements Try to think a little bit farther. If there is no order or sorting, what is the meaning of First and Last? In your example First and Last denote a subset where to search and this is possible (to denote a subset using First and Last) only for ordered containers. > in the set. You can think of cursors as elements of a mathematical > index set (yes!) that is associated with the elements in some set. > Such as is used for example in proofs by induction, or when you want > to transform a set into a sorted set, etc. I couldn't get this part about proofs by induction, could you explain? There is nothing wrong if some program needs a sorted container. But in this case (I'm afraid to use this controversal term now, but couldn't came up with anything better :)) it is natural to use containers that explicitly support sort operation, because there are probably a number of sort orders and Sorted_Set can support just one that is implementation defined. Then your algorithm will be clear, implementation independent, easily understandable and probably more efficient. > > I find Cursors useful when I want to put an index set into operations > inside a computer. When I'm can use any container, > how could I implement index sets without Cursors? Index sets require indirection which is provided by the core language, i.e. access types; they require no cursors. > >> - Second is that find/search operation makes sence only >> for a mapping container i.e. vector or hash; > > > Find is a membership test, how could it not make sense for > a set? Find is not a membership test. Membership test is more generic, i.e it has _the same_ semantics for _any_ kind of container, namely "does this container contain this element or not?" Membership test is not a replacement for various kinds of search and vice versa. Find is more diverse and is not always make sense. For "mappings" i.e. vectors and hashes for example "Find" could return a key (index for vectors) of the element or a list/vector/set of keys whose elements satisfy some predicate. For ordered containers that are not mappings (lists, trees) "Find" could degenerate into membership test or could became "FindNext", "FindPrev" or "Count". For sets "Find" degenerates into membership test or could return a subset according to some predicate (as in your example). So, you see that "Find" differs for diffrent container types. It is "less generic" than membership test. > >> there is no sence to search for the element >> if you already have it. > > > (I had called my procedure "silly".) Programming is not equal > to logic ;-) Notice two uses: Exactly, but "silly" example can't prove anything. > > (1) > True generic operation for all container types can be membership > >> test not find/search. > > This is a membership test, but only accidentally. Think of an extended > algorithm that gives you a set of cursors of all occurences of > some item in a container, whatever kind of container it is. If you need just a set of references to some elements, then you are all set. Ada provides access types, why cursor? > >> Another problem with your example is that it is essentially a NOP. >> If you already have a cursor for your element why to search for it? > > > (2) The Cursor "item" designates an element in _some_ container. > This need not be the container that is searched. > Start and Stop can refer to a different container. > The algorithm will find the element in that container. Cursors could be an implementation detail, they are not needed for general API. Start and Stop can have no sense for some containers. Algorithm can use internally whatever it needs to deliver result. > >> Some times cursors replace >> collections completely! That kind of indirect interface is very >> dangerous in my view. > > > And Cursors enable programmers to do their work. Cursors add indirection. Programmers are perfecly able to do their work without Cursors, at least most of them (I'm not counting authors of Ada.Containers ;). I would say Cursors add "double indirection" :) - for elements and container itself. > Imagine programming without indirection, whatever the indirection > mechanism looks like. That would be a disaster :), let's say clear and loudly: "we love indirection", and let's use it explicitly via access types.:) > > >> Now to answer you question, just replace "My_Container" by >> "My_Vector_Container", then "item: My_Vector_Container.Cursor" by >> "item: My_Vector_Container.Element_Type" and then "Cursor" by "Index" >> in that order and you will get a "vectorized" version of you >> function ;) > > > Forcing every client program to use vectors... > Where did you get this idea from? Regards, Mikhail