* Generic Package @ 2007-04-25 22:15 andrew.carroll 2007-04-26 0:07 ` Jeffrey R. Carter ` (4 more replies) 0 siblings, 5 replies; 84+ messages in thread From: andrew.carroll @ 2007-04-25 22:15 UTC (permalink / raw) Is there a generic "collection" package in the libraries that come with Ada? For instance if in my design I have an "is a" relationship like table "is a" _collection_ of something then is there a generic "collection" package that I could use? ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-25 22:15 Generic Package andrew.carroll @ 2007-04-26 0:07 ` Jeffrey R. Carter 2007-04-26 7:46 ` Markus E Leypold 2007-04-26 6:02 ` Martin Krischik ` (3 subsequent siblings) 4 siblings, 1 reply; 84+ messages in thread From: Jeffrey R. Carter @ 2007-04-26 0:07 UTC (permalink / raw) andrew.carroll@okstate.edu wrote: > Is there a generic "collection" package in the libraries that come > with Ada? For instance if in my design I have an "is a" relationship > like table "is a" _collection_ of something then is there a generic > "collection" package that I could use? I'm not clear what you're after, but have you looked at the set of packages under Ada.Containers? If you're using Ada 95 rather than Ada, you have a number of libraries to choose from, but nothing that is defined by the language. -- Jeff Carter "There's no messiah here. There's a mess all right, but no messiah." Monty Python's Life of Brian 84 ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-26 0:07 ` Jeffrey R. Carter @ 2007-04-26 7:46 ` Markus E Leypold 0 siblings, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-04-26 7:46 UTC (permalink / raw) "Jeffrey R. Carter" <jrcarter@acm.org> writes: > andrew.carroll@okstate.edu wrote: >> Is there a generic "collection" package in the libraries that come >> with Ada? For instance if in my design I have an "is a" relationship >> like table "is a" _collection_ of something then is there a generic >> "collection" package that I could use? > > I'm not clear what you're after, but have you looked at the set of > packages under Ada.Containers? > > If you're using Ada 95 rather than Ada, you have a number of libraries > to choose from, but nothing that is defined by the language. There is a port of a version of Ada.Containers to Ada 05 though - not always bug free, but using it promises easy upgrade to Ada 2005. Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-25 22:15 Generic Package andrew.carroll 2007-04-26 0:07 ` Jeffrey R. Carter @ 2007-04-26 6:02 ` Martin Krischik 2007-04-26 7:57 ` Dmitry A. Kazakov ` (2 subsequent siblings) 4 siblings, 0 replies; 84+ messages in thread From: Martin Krischik @ 2007-04-26 6:02 UTC (permalink / raw) andrew.carroll@okstate.edu schrieb: > Is there a generic "collection" package in the libraries that come > with Ada? For instance if in my design I have an "is a" relationship > like table "is a" _collection_ of something then is there a generic > "collection" package that I could use? Try: http://en.wikibooks.org/wiki/Ada_Programming#Other_Language_Libraries Martin ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-25 22:15 Generic Package andrew.carroll 2007-04-26 0:07 ` Jeffrey R. Carter 2007-04-26 6:02 ` Martin Krischik @ 2007-04-26 7:57 ` Dmitry A. Kazakov 2007-04-26 15:31 ` andrew.carroll 2007-04-26 20:48 ` andrew.carroll 4 siblings, 0 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-26 7:57 UTC (permalink / raw) On 25 Apr 2007 15:15:07 -0700, andrew.carroll@okstate.edu wrote: > Is there a generic "collection" package in the libraries that come > with Ada? For instance if in my design I have an "is a" relationship > like table "is a" _collection_ of something then is there a generic > "collection" package that I could use? Is it sets you need? X "is a" S = X is in S -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-25 22:15 Generic Package andrew.carroll ` (2 preceding siblings ...) 2007-04-26 7:57 ` Dmitry A. Kazakov @ 2007-04-26 15:31 ` andrew.carroll 2007-04-26 16:07 ` Georg Bauhaus ` (3 more replies) 2007-04-26 20:48 ` andrew.carroll 4 siblings, 4 replies; 84+ messages in thread From: andrew.carroll @ 2007-04-26 15:31 UTC (permalink / raw) I discovered a possble design mistake in the program I wrote for my Master's course this semester. It's working and all that but I think I could have saved myself many hours of work had I recognized (and regurgitated from my undergraduate knowledge in 2002) the "is a" concept. With respect to databases a tuple "is a" collection of attributes and a table "is a" collection of tuples and a schema "is a" collection of tables. I could have used a generic "collection" to satisfy tuple, table and schema and I wouldn't have had to write code to iterate, add, delete, etcetera from them. Does that help explain it? I think the Booch components may have something I'm looking for. Even though this site http://www.adapower.net/booch/overview.html says it would be better to use a "collection" (there's the word again) than a linked list I think I could have used the generic linked list for my purposes. I wish the site had given more information as to what a "collection" is and where to find more information about it. Then again, I didn't read the whole thing. So what would be best to choose? ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-26 15:31 ` andrew.carroll @ 2007-04-26 16:07 ` Georg Bauhaus 2007-04-26 19:40 ` andrew.carroll 2007-04-26 18:54 ` Dmitry A. Kazakov ` (2 subsequent siblings) 3 siblings, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-04-26 16:07 UTC (permalink / raw) On Thu, 2007-04-26 at 08:31 -0700, andrew.carroll@okstate.edu wrote: > I discovered a possble design mistake in the program I wrote for my > Master's course this semester. It's working and all that but I think > I could have saved myself many hours of work had I recognized (and > regurgitated from my undergraduate knowledge in 2002) the "is a" > concept. With respect to databases a tuple "is a" collection of > attributes and a table "is a" collection of tuples and a schema "is a" > collection of tables. I could have used a generic "collection" to > satisfy tuple, table and schema and I wouldn't have had to write code > to iterate, add, delete, etcetera from them. > > Does that help explain it? Are you certain that these high level "is a" relations aren't entirely artificial? What is gained by finding a thin, common interface of tuples, tables, and schemata? In the case you describe, I'd prefer composition over inheritance. A table has many tuples, and a table is part of a schema. So that alone makes tables collections of tuples, for example. By analogy, every type of a program identifies a collection of values. But not every type in a program must be explicitly derived from some universal ancestor, even when we could find some remote property that it shares with all other types. There is value in differentiating objects. Universal unification of everything leads to answers as useful as 42. :) ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-26 16:07 ` Georg Bauhaus @ 2007-04-26 19:40 ` andrew.carroll 2007-04-26 20:01 ` Georg Bauhaus 0 siblings, 1 reply; 84+ messages in thread From: andrew.carroll @ 2007-04-26 19:40 UTC (permalink / raw) On Apr 26, 11:07 am, Georg Bauhaus <bauh...@futureapps.de> wrote: > On Thu, 2007-04-26 at 08:31 -0700, andrew.carr...@okstate.edu wrote: > > I discovered a possble design mistake in the program I wrote for my > > Master's course this semester. It's working and all that but I think > > I could have saved myself many hours of work had I recognized (and > > regurgitated from my undergraduate knowledge in 2002) the "is a" > > concept. With respect to databases a tuple "is a" collection of > > attributes and a table "is a" collection of tuples and a schema "is a" > > collection of tables. I could have used a generic "collection" to > > satisfy tuple, table and schema and I wouldn't have had to write code > > to iterate, add, delete, etcetera from them. > > > Does that help explain it? > > Are you certain that these high level "is a" relations aren't > entirely artificial? What is gained by finding a thin, common > interface of tuples, tables, and schemata? > > In the case you describe, I'd prefer composition over > inheritance. A table has many tuples, and a table is part > of a schema. So that alone makes tables collections of tuples, > for example. > > By analogy, every type of a program identifies a collection of > values. But not every type in a program must be explicitly derived > from some universal ancestor, even when we could find some remote > property that it shares with all other types. There is value in > differentiating objects. > > Universal unification of everything leads to answers > as useful as 42. :) Who said anything about derivation? Yeah, I used the word "is a" but that doesn't mean I want to build a whole class tree. As far as I am thinking I just do something like: package Tuple is new Generic_Collection(Item => attribute); Attribute can implement some kind of file_system interface and can iterate by positive count values which are sequential. Then I could do package Table is new Generic_Collection(Item => tuple.???); Then I could do package Schema is new Generic_Collection(Item => table.???); This is all in a dream world so please don't get to picky with the syntax. So, is there a "Generic_Collection" type of package in Ada? ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-26 19:40 ` andrew.carroll @ 2007-04-26 20:01 ` Georg Bauhaus 0 siblings, 0 replies; 84+ messages in thread From: Georg Bauhaus @ 2007-04-26 20:01 UTC (permalink / raw) On Thu, 2007-04-26 at 12:40 -0700, andrew.carroll@okstate.edu wrote: > Who said anything about derivation? Yeah, I used the word "is a" but > that doesn't mean I want to build a whole class tree. Ah, OK. > So, is there a "Generic_Collection" type of package in Ada? AFAIK, not in the sense that permits deciding the nature of the collection at runtime, or based on the type parameter (see also Dmitry's remarks). IIRC, Matt Heaney had originally intended to re-export the type T used as actual parameter for Element_Type of containers. In this case you might have written Tuples.Element_Subtype and instantiated other packages using this subtype without naming T. OTOH, the chaining is possible if I have understood correctly: package Tuple is new Vectors(Element_Type => attribute, ...); package Table is new Hashed_Sets(Element_Type => Tuple.Vector, ...); ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-26 15:31 ` andrew.carroll 2007-04-26 16:07 ` Georg Bauhaus @ 2007-04-26 18:54 ` Dmitry A. Kazakov 2007-04-26 21:52 ` Simon Wright 2007-04-26 21:50 ` Simon Wright 2007-04-27 4:45 ` Jeffrey R. Carter 3 siblings, 1 reply; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-26 18:54 UTC (permalink / raw) On 26 Apr 2007 08:31:24 -0700, andrew.carroll@okstate.edu wrote: > I discovered a possble design mistake in the program I wrote for my > Master's course this semester. It's working and all that but I think > I could have saved myself many hours of work had I recognized (and > regurgitated from my undergraduate knowledge in 2002) the "is a" > concept. With respect to databases a tuple "is a" collection of > attributes and a table "is a" collection of tuples and a schema "is a" > collection of tables. I could have used a generic "collection" to > satisfy tuple, table and schema and I wouldn't have had to write code > to iterate, add, delete, etcetera from them. Uhm, these containers are quite different in nature. You cannot iterate a relational table, because there is no order defined on it. Otherwise, yes you could implement everything on the basis of an unordered set [see the set theory (:-))]. Alas, unordered sets are close to useless in practice because they are O(N). This is where your crystal abstraction gets broken by the reality. You need some indexing to improve performance. An the way you index things heavily depends on what you index. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-26 18:54 ` Dmitry A. Kazakov @ 2007-04-26 21:52 ` Simon Wright 2007-04-27 9:00 ` Dmitry A. Kazakov 0 siblings, 1 reply; 84+ messages in thread From: Simon Wright @ 2007-04-26 21:52 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > You cannot iterate a relational table, because there is no order > defined on it. Why would that stop me iterating over all the rows? ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-26 21:52 ` Simon Wright @ 2007-04-27 9:00 ` Dmitry A. Kazakov 2007-04-27 11:11 ` Georg Bauhaus 2007-04-27 11:43 ` Markus E Leypold 0 siblings, 2 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-27 9:00 UTC (permalink / raw) On Thu, 26 Apr 2007 22:52:58 +0100, Simon Wright wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > >> You cannot iterate a relational table, because there is no order >> defined on it. > > Why would that stop me iterating over all the rows? Because iterating presumes following an order. If there is no *any* order, which one would you follow? It is clear that we could enumerate anything on a real computer, but that would be same as Unchecked_Conversion, it would break the abstraction. I guess, one should first create a "result set", then enumerate it according to some order relation. That thing could be iterated through. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 9:00 ` Dmitry A. Kazakov @ 2007-04-27 11:11 ` Georg Bauhaus 2007-04-27 12:06 ` Dmitry A. Kazakov 2007-04-27 11:43 ` Markus E Leypold 1 sibling, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-04-27 11:11 UTC (permalink / raw) On Fri, 2007-04-27 at 11:00 +0200, Dmitry A. Kazakov wrote: > On Thu, 26 Apr 2007 22:52:58 +0100, Simon Wright wrote: > > > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > > > >> You cannot iterate a relational table, because there is no order > >> defined on it. > > > > Why would that stop me iterating over all the rows? > > Because iterating presumes following an order. Any real table in an existing computer has a "natural" ordering suitable for iterating an operation for all elements: data in a real computer can be uniquely identified. The fact that the ordering is hidden behind the functional Iterate abstraction doesn't make it go away for any snapshot of rows. It's a don't care. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 11:11 ` Georg Bauhaus @ 2007-04-27 12:06 ` Dmitry A. Kazakov 2007-04-27 12:52 ` Markus E Leypold ` (2 more replies) 0 siblings, 3 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-27 12:06 UTC (permalink / raw) On Fri, 27 Apr 2007 13:11:30 +0200, Georg Bauhaus wrote: > On Fri, 2007-04-27 at 11:00 +0200, Dmitry A. Kazakov wrote: >> On Thu, 26 Apr 2007 22:52:58 +0100, Simon Wright wrote: >> >>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: >>> >>>> You cannot iterate a relational table, because there is no order >>>> defined on it. >>> >>> Why would that stop me iterating over all the rows? >> >> Because iterating presumes following an order. > > Any real table in an existing computer has a "natural" > ordering suitable for iterating an operation for all > elements: data in a real computer can be uniquely identified. No this is wrong even on a real computer. The DB engine could shuffle the rows asynchronously to your application. There could be other applications playing with the table. The table might spread over memories of several computers and different levels cashes. You have to bring transactions, replications and other synchronizing stuff to make any sense out of "natural order." > The fact that the ordering is hidden behind the functional > Iterate abstraction doesn't make it go away for any > snapshot of rows. It does. Semantically, table /= a snapshot of. That is. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 12:06 ` Dmitry A. Kazakov @ 2007-04-27 12:52 ` Markus E Leypold 2007-04-27 14:10 ` Georg Bauhaus 2007-04-27 19:44 ` Simon Wright 2 siblings, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-04-27 12:52 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Fri, 27 Apr 2007 13:11:30 +0200, Georg Bauhaus wrote: > >> On Fri, 2007-04-27 at 11:00 +0200, Dmitry A. Kazakov wrote: >>> On Thu, 26 Apr 2007 22:52:58 +0100, Simon Wright wrote: >>> >>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: >>>> >>>>> You cannot iterate a relational table, because there is no order >>>>> defined on it. >>>> >>>> Why would that stop me iterating over all the rows? >>> >>> Because iterating presumes following an order. >> >> Any real table in an existing computer has a "natural" >> ordering suitable for iterating an operation for all >> elements: data in a real computer can be uniquely identified. > > No this is wrong even on a real computer. The DB engine could shuffle the > rows asynchronously to your application. There could be other applications > playing with the table. The table might spread over memories of several > computers and different levels cashes. You have to bring transactions, > replications and other synchronizing stuff to make any sense out of > "natural order." > >> The fact that the ordering is hidden behind the functional >> Iterate abstraction doesn't make it go away for any >> snapshot of rows. > > It does. Semantically, table /= a snapshot of. That is. >>>>> You cannot iterate a relational table, because there is no order >>>>> defined on it. You know, I'm iterating over relational tables (or what I thought were relational tables) all the time. This basically is the way most of the interfaces to RDBSs I use work: Executing a query gives you a result cursor, which you can use to extract the result row by row. The actual sequence in which they come is unspecified and up to the database engine if I haven't specified sorting in my query (which I don't in many circumstances where I only want to get at a set of tuples but don't require any specific order). Are you telling me I've been hallucinating and that I have been NOT iterating over those tables (because one cannot)? Or do you intend to come up with a "smart" definition of "iterating" or "relational table" now, which -- contrary to everyones expectations and common understanding -- will somehow exclude my scenario from the definition? <Shaking my head> Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 12:06 ` Dmitry A. Kazakov 2007-04-27 12:52 ` Markus E Leypold @ 2007-04-27 14:10 ` Georg Bauhaus 2007-04-27 14:16 ` Dmitry A. Kazakov 2007-04-27 19:44 ` Simon Wright 2 siblings, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-04-27 14:10 UTC (permalink / raw) On Fri, 2007-04-27 at 14:06 +0200, Dmitry A. Kazakov wrote: > > Any real table in an existing computer has a "natural" > > ordering suitable for iterating an operation for all > > elements: data in a real computer can be uniquely identified. > > No this is wrong even on a real computer. The DB engine could shuffle the > rows asynchronously to your application. So what? Any delivery of DB rows to an application permits iteration as long as Iterate knows how to create a sequence from the inputs. I can't think of a DB system, in particular in the OP's context, that will deliver rows such that the recipients must be able to perform processing of more than one row at the same tick. > > The fact that the ordering is hidden behind the functional > > Iterate abstraction doesn't make it go away for any > > snapshot of rows. > > It does. Semantically, table /= a snapshot of. That is. For Iterate, a snapshot is a table, a collection of tuples. Semantically, every DB client program I have ever seen is based on the very fact that a snapshot is a table. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 14:10 ` Georg Bauhaus @ 2007-04-27 14:16 ` Dmitry A. Kazakov 2007-04-27 21:44 ` Georg Bauhaus 0 siblings, 1 reply; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-27 14:16 UTC (permalink / raw) On Fri, 27 Apr 2007 16:10:47 +0200, Georg Bauhaus wrote: > On Fri, 2007-04-27 at 14:06 +0200, Dmitry A. Kazakov wrote: > >> It does. Semantically, table /= a snapshot of. That is. > > For Iterate, a snapshot is a table, a collection of tuples. Well, for a hammer everything is a collection of nails. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 14:16 ` Dmitry A. Kazakov @ 2007-04-27 21:44 ` Georg Bauhaus 2007-04-28 7:38 ` Dmitry A. Kazakov 0 siblings, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-04-27 21:44 UTC (permalink / raw) On Fri, 2007-04-27 at 16:16 +0200, Dmitry A. Kazakov wrote: > On Fri, 27 Apr 2007 16:10:47 +0200, Georg Bauhaus wrote: > > > On Fri, 2007-04-27 at 14:06 +0200, Dmitry A. Kazakov wrote: > > > >> It does. Semantically, table /= a snapshot of. That is. > > > > For Iterate, a snapshot is a table, a collection of tuples. > > Well, for a hammer everything is a collection of nails. Please. From a user's perspective Iterate is the important interface. When I call Iterate to apply an operation to each tuple of a table, an order is established, even though it does not matter. I really don't understand why Iterate should not be able to produce a positional number for each tuple it produces. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 21:44 ` Georg Bauhaus @ 2007-04-28 7:38 ` Dmitry A. Kazakov 2007-04-28 17:50 ` Simon Wright 2007-04-28 21:04 ` Ray Blaak 0 siblings, 2 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-28 7:38 UTC (permalink / raw) On Fri, 27 Apr 2007 23:44:04 +0200, Georg Bauhaus wrote: > On Fri, 2007-04-27 at 16:16 +0200, Dmitry A. Kazakov wrote: >> On Fri, 27 Apr 2007 16:10:47 +0200, Georg Bauhaus wrote: >> >>> On Fri, 2007-04-27 at 14:06 +0200, Dmitry A. Kazakov wrote: >>> >>>> It does. Semantically, table /= a snapshot of. That is. >>> >>> For Iterate, a snapshot is a table, a collection of tuples. >> >> Well, for a hammer everything is a collection of nails. > > Please. From a user's perspective Iterate is the important > interface. Yes, but it is not the interface of a set of tuples. It is an interface of some ordered container. > When I call Iterate to apply an operation to > each tuple of a table, an order is established, even though > it does not matter. This is too swampy. There is a sufficient difference between foreach closures and interators. You can have foreach on an unordered set, but you cannot have iterators. The difference is in who has the control over the enumeration process. Iterators are more binding for the container and less for the user of. Consider a library. Say you wished to read all books there. You come to the librarian and order a book. Then you read that book and return. Now, you can ask him: give me another book. But you cannot require him to give you a book that you haven't yet read. That is your business, he would answer. The librarian interface is of an unordered set (no iterators). Yet you could give him a set of post-it notes with numbers on them and ask him to put one on each of the books. (Later you probably could ask him for a book with the specific number on it). He could still refuse but then you would come back with a flame thrower and burn the library and the damned books down. Both were examples of foreach. > I really don't understand why Iterate should not be able > to produce a positional number for each tuple it produces. Because it is not how relational algebra was specified. If you are objecting to its idea, well, I am with you, and the most of DB vendors are as well, as they all provide row IDs to ease our life. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-28 7:38 ` Dmitry A. Kazakov @ 2007-04-28 17:50 ` Simon Wright 2007-04-28 21:04 ` Ray Blaak 1 sibling, 0 replies; 84+ messages in thread From: Simon Wright @ 2007-04-28 17:50 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > This is too swampy. There is a sufficient difference between foreach > closures and interators. You can have foreach on an unordered set, > but you cannot have iterators. The difference is in who has the > control over the enumeration process. Iterators are more binding for > the container and less for the user of. Clearly "iterator" means something to you that it doesn't to me. This is probably not related to the discussions round Ada 05 which led to the use of the word Cursor instead of Iterator (the BCs use Iterator for historical reasons, but in a completely different sense from the STL, which is the basis for Ada.Containers). > Consider a library. Say you wished to read all books there. You come > to the librarian and order a book. Then you read that book and > return. Now, you can ask him: give me another book. But you cannot > require him to give you a book that you haven't yet read. That is > your business, he would answer. I think that's only because readers are a tiresome perturbation in the librarian's universe! ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-28 7:38 ` Dmitry A. Kazakov 2007-04-28 17:50 ` Simon Wright @ 2007-04-28 21:04 ` Ray Blaak 2007-04-29 16:33 ` Markus E Leypold 1 sibling, 1 reply; 84+ messages in thread From: Ray Blaak @ 2007-04-28 21:04 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > He could still refuse but then you would come back with a flame thrower and > burn the library and the damned books down. Both were examples of foreach. LOL! Where did that come from? -- Cheers, The Rhythm is around me, The Rhythm has control. Ray Blaak The Rhythm is inside me, rAYblaaK@STRIPCAPStelus.net The Rhythm has my soul. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-28 21:04 ` Ray Blaak @ 2007-04-29 16:33 ` Markus E Leypold 0 siblings, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-04-29 16:33 UTC (permalink / raw) Ray Blaak <rAYblaaK@STRIPCAPStelus.net> writes: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: >> He could still refuse but then you would come back with a flame thrower and >> burn the library and the damned books down. Both were examples of foreach. > > LOL! > > Where did that come from? From Dmitry Kazakov's surreal universe of not-quite computer science. I know, I'm beginning to sound bitter, but only because I realize that I have wasted so much time on somebody who in my judgement is rapidly approaching crank status. Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 12:06 ` Dmitry A. Kazakov 2007-04-27 12:52 ` Markus E Leypold 2007-04-27 14:10 ` Georg Bauhaus @ 2007-04-27 19:44 ` Simon Wright 2007-04-27 20:34 ` Dmitry A. Kazakov 2 siblings, 1 reply; 84+ messages in thread From: Simon Wright @ 2007-04-27 19:44 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Fri, 27 Apr 2007 13:11:30 +0200, Georg Bauhaus wrote: >> Any real table in an existing computer has a "natural" >> ordering suitable for iterating an operation for all >> elements: data in a real computer can be uniquely identified. > > No this is wrong even on a real computer. The DB engine could > shuffle the rows asynchronously to your application. There could be > other applications playing with the table. The table might spread > over memories of several computers and different levels cashes. You > have to bring transactions, replications and other synchronizing > stuff to make any sense out of "natural order." Just using ordered containers is hardly going to stop you needing to deal with locking! The BCs let you iterate over hashed containers. They're not thread-safe, but provided you lock properly you will visit all the elements once. I'm sure the same applies to Ada.Containers. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 19:44 ` Simon Wright @ 2007-04-27 20:34 ` Dmitry A. Kazakov 2007-04-27 21:16 ` Simon Wright 0 siblings, 1 reply; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-27 20:34 UTC (permalink / raw) On Fri, 27 Apr 2007 20:44:13 +0100, Simon Wright wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > >> On Fri, 27 Apr 2007 13:11:30 +0200, Georg Bauhaus wrote: > >>> Any real table in an existing computer has a "natural" >>> ordering suitable for iterating an operation for all >>> elements: data in a real computer can be uniquely identified. >> >> No this is wrong even on a real computer. The DB engine could >> shuffle the rows asynchronously to your application. There could be >> other applications playing with the table. The table might spread >> over memories of several computers and different levels cashes. You >> have to bring transactions, replications and other synchronizing >> stuff to make any sense out of "natural order." > > Just using ordered containers is hardly going to stop you needing to > deal with locking! In some sense it would. Provided it existed unconditionally, you would not need to lock anything. Because otherwise any relevant change would destroy the order in contradiction to the premise. Obviously you don't need to lock if possible changes wouldn't affect the order. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 20:34 ` Dmitry A. Kazakov @ 2007-04-27 21:16 ` Simon Wright 2007-04-28 7:36 ` Dmitry A. Kazakov 0 siblings, 1 reply; 84+ messages in thread From: Simon Wright @ 2007-04-27 21:16 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Fri, 27 Apr 2007 20:44:13 +0100, Simon Wright wrote: > >> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: >> >>> On Fri, 27 Apr 2007 13:11:30 +0200, Georg Bauhaus wrote: >> >>>> Any real table in an existing computer has a "natural" >>>> ordering suitable for iterating an operation for all >>>> elements: data in a real computer can be uniquely identified. >>> >>> No this is wrong even on a real computer. The DB engine could >>> shuffle the rows asynchronously to your application. There could be >>> other applications playing with the table. The table might spread >>> over memories of several computers and different levels cashes. You >>> have to bring transactions, replications and other synchronizing >>> stuff to make any sense out of "natural order." >> >> Just using ordered containers is hardly going to stop you needing to >> deal with locking! > > In some sense it would. Provided it existed unconditionally, you would not > need to lock anything. Because otherwise any relevant change would destroy > the order in contradiction to the premise. Obviously you don't need to lock > if possible changes wouldn't affect the order. I can't imagine any sense in which it could. Perhaps you're thinking of special hardware that could have these properties? But that's just devolving the concurrency problem to an engineer in another discipline. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 21:16 ` Simon Wright @ 2007-04-28 7:36 ` Dmitry A. Kazakov 0 siblings, 0 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-28 7:36 UTC (permalink / raw) On Fri, 27 Apr 2007 22:16:35 +0100, Simon Wright wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > >> On Fri, 27 Apr 2007 20:44:13 +0100, Simon Wright wrote: >> >>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: >>> >>>> On Fri, 27 Apr 2007 13:11:30 +0200, Georg Bauhaus wrote: >>> >>>>> Any real table in an existing computer has a "natural" >>>>> ordering suitable for iterating an operation for all >>>>> elements: data in a real computer can be uniquely identified. >>>> >>>> No this is wrong even on a real computer. The DB engine could >>>> shuffle the rows asynchronously to your application. There could be >>>> other applications playing with the table. The table might spread >>>> over memories of several computers and different levels cashes. You >>>> have to bring transactions, replications and other synchronizing >>>> stuff to make any sense out of "natural order." >>> >>> Just using ordered containers is hardly going to stop you needing to >>> deal with locking! >> >> In some sense it would. Provided it existed unconditionally, you would not >> need to lock anything. Because otherwise any relevant change would destroy >> the order in contradiction to the premise. Obviously you don't need to lock >> if possible changes wouldn't affect the order. > > I can't imagine any sense in which it could. Perhaps you're thinking > of special hardware that could have these properties? Or just "per magic," like priority ceiling locking. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 9:00 ` Dmitry A. Kazakov 2007-04-27 11:11 ` Georg Bauhaus @ 2007-04-27 11:43 ` Markus E Leypold 2007-04-28 17:35 ` Dmitry A. Kazakov 1 sibling, 1 reply; 84+ messages in thread From: Markus E Leypold @ 2007-04-27 11:43 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Thu, 26 Apr 2007 22:52:58 +0100, Simon Wright wrote: > >> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: >> >>> You cannot iterate a relational table, because there is no order >>> defined on it. >> >> Why would that stop me iterating over all the rows? > > Because iterating presumes following an order. If there is no *any* order, > which one would you follow? None. Iteration gives the values in a certain sequence, any time you iterate. But it doesn't follow an order in the case of unordered collections. Next time you iterate the elements might come in another sequence. > It is clear that we could enumerate anything on > a real computer, but that would be same as Unchecked_Conversion, it would > break the abstraction. So I'm having an unchecked operation if I enumerate elements of a set (sets are unordered). How embarrasing. Theat would mean, that there is no efficient way to get at the elements of a given subset of the natural numbers. I'd have to for I in 0 ... infinity: if (I in M) then ... else ... > I guess, one should first create a "result set", then enumerate it > according to some order relation. That thing could be iterated > through. What nonsense. Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 11:43 ` Markus E Leypold @ 2007-04-28 17:35 ` Dmitry A. Kazakov 2007-04-28 23:06 ` Georg Bauhaus 2007-04-29 16:26 ` Markus E Leypold 0 siblings, 2 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-28 17:35 UTC (permalink / raw) On Fri, 27 Apr 2007 13:43:58 +0200, Markus E Leypold wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > >> On Thu, 26 Apr 2007 22:52:58 +0100, Simon Wright wrote: >> >>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: >>> >>>> You cannot iterate a relational table, because there is no order >>>> defined on it. >>> >>> Why would that stop me iterating over all the rows? >> >> Because iterating presumes following an order. If there is no *any* order, >> which one would you follow? > > None. Iteration gives the values in a certain sequence, "Sequence" is defined as an ordered [and countable] set. >> It is clear that we could enumerate anything on >> a real computer, but that would be same as Unchecked_Conversion, it would >> break the abstraction. > > So I'm having an unchecked operation if I enumerate elements of a set > (sets are unordered). How embarrasing. Yes, because that set is a representation [model] of some other [domain space] set which could be fundamentally unordered and/or uncountable. As an example consider merits of the loop: for X in 0.0..1.0 loop Fortunately the above is illegal in Ada. Not because it were impossible: declare X : Float := 0.0; begin while X <= 1.0 loop ... X := Float'Succ (X); end loop; but because it is a mess. After interating reals we could proceed to complex numbers... -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-28 17:35 ` Dmitry A. Kazakov @ 2007-04-28 23:06 ` Georg Bauhaus 2007-04-29 8:19 ` Dmitry A. Kazakov 2007-04-29 16:26 ` Markus E Leypold 1 sibling, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-04-28 23:06 UTC (permalink / raw) On Sat, 2007-04-28 at 19:35 +0200, Dmitry A. Kazakov wrote: > Yes, because that set is a representation [model] of some other [domain > space] set which could be fundamentally unordered and/or uncountable. Should we therefore tie the notion of iterating something to procedures that a computer can't perform? ;-) > As an > example consider merits of the loop: > > for X in 0.0..1.0 loop > > Fortunately the above is illegal in Ada. Not because it were impossible: > > declare > X : Float := 0.0; > begin > while X <= 1.0 loop > ... > X := Float'Succ (X); > end loop; > > but because it is a mess. > > After interating reals we could proceed to complex numbers... And on to more not fully representable things such as collections of tuples made to correspond to the elements of a suitably defined Cauchy sequence. If only computers could produce the elements of more than zero uncountable sets ... Like Simon, I'm not sure I'm familiar with your iteration; my containers would be providing iteration if they can do one of - take a subprogram (e.g.) and call it for each of a collection of elements - provide access to an element and then the next if any where the meaning of "next" is specified in the collection's contract The amount of determinism need not be 100%. E.g., the post-condition if Iterate that each element is visited once, in no particular order, seems reasonable to me. http://www.icsi.berkeley.edu/~sather/Publications/toplas.html Is there iteration in the following SETL expression? Result := { x : x in {1, 3, 24, 17, 11} | P(x) }; ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-28 23:06 ` Georg Bauhaus @ 2007-04-29 8:19 ` Dmitry A. Kazakov 2007-04-29 15:10 ` (see below) 2007-04-30 10:30 ` Georg Bauhaus 0 siblings, 2 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-29 8:19 UTC (permalink / raw) On Sun, 29 Apr 2007 01:06:52 +0200, Georg Bauhaus wrote: > Like Simon, I'm not sure I'm familiar with your iteration; What about iterator = an object used to describe the iteration state? (I don't see much sense in calling loops iterators. To me the iterator is rather the variable of the loop. Loop performs/implements iteration.) > my containers would be providing iteration if they can do one of > > - take a subprogram (e.g.) and call it for each of a collection > of elements > > - provide access to an element and then the next if any where the > meaning of "next" is specified in the collection's contract > > The amount of determinism need not be 100%. E.g., the post-condition > if Iterate that each element is visited once, in no particular order, > seems reasonable to me. Consider the precondition of the code performed for each element. It is "here is an unvisited element" You can easily state it for the second case, because you have the iterator's value. For the former case you have a problem, because the precondition of the subprogram cannot be formulated and hence verified in any way. That is the difference. The thing might "iterate" or not, you cannot know it, you have to unconditionally trust it. (There is also very little what you could do in the subprogram without further assumptions, like that exactly one instance of it is called at a time.) > http://www.icsi.berkeley.edu/~sather/Publications/toplas.html > > Is there iteration in the following SETL expression? > > Result := { x : x in {1, 3, 24, 17, 11} | P(x) }; Iteration in what? In the language construct? In Result? Consider a possibility that Result were computed at compile time. Would it still be iteration? (In case you would call iteration anything that can be computed as a result of some iteration, then everything computable would obviously turn to be iteration. I doubt that would be any useful definition of.) -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-29 8:19 ` Dmitry A. Kazakov @ 2007-04-29 15:10 ` (see below) 2007-04-29 17:48 ` Dmitry A. Kazakov 2007-04-30 10:30 ` Georg Bauhaus 1 sibling, 1 reply; 84+ messages in thread From: (see below) @ 2007-04-29 15:10 UTC (permalink / raw) On 29/4/07 09:19, in article 1woad6hn9idy2$.6otnwphc1o0h$.dlg@40tude.net, "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote: > (I don't see much sense in calling loops iterators. To me the iterator is > rather the variable of the loop. Loop performs/implements iteration.) Your preference (unfortunately enshrined in OO jargon) does serious violence to English grammar! An <x>or is something that performs or implements <x>, not something that has <x> performed upon it! An actor is not a script. -- Bill Findlay <surname><forename> chez blueyonder.co.uk ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-29 15:10 ` (see below) @ 2007-04-29 17:48 ` Dmitry A. Kazakov 2007-04-29 22:36 ` (see below) 0 siblings, 1 reply; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-29 17:48 UTC (permalink / raw) On Sun, 29 Apr 2007 16:10:46 +0100, (see below) wrote: > On 29/4/07 09:19, in article 1woad6hn9idy2$.6otnwphc1o0h$.dlg@40tude.net, > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote: > >> (I don't see much sense in calling loops iterators. To me the iterator is >> rather the variable of the loop. Loop performs/implements iteration.) > > Your preference (unfortunately enshrined in OO jargon) > does serious violence to English grammar! > > An <x>or is something that performs or implements <x>, > not something that has <x> performed upon it! > > An actor is not a script. What about "polymorphism"? It means exactly the opposite to what its translation suggests (many-formed/shaped). -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-29 17:48 ` Dmitry A. Kazakov @ 2007-04-29 22:36 ` (see below) 2007-04-30 6:58 ` Dmitry A. Kazakov 0 siblings, 1 reply; 84+ messages in thread From: (see below) @ 2007-04-29 22:36 UTC (permalink / raw) On 29/4/07 18:48, in article 1n38bsd8xx0uc$.1eo1arncmwvkn.dlg@40tude.net, "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote: > What about "polymorphism"? It means exactly the opposite to what its > translation suggests (many-formed/shaped). You have lost me. It means exactly what it says. -- Bill Findlay <surname><forename> chez blueyonder.co.uk ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-29 22:36 ` (see below) @ 2007-04-30 6:58 ` Dmitry A. Kazakov 2007-04-30 9:59 ` Markus E Leypold ` (3 more replies) 0 siblings, 4 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-30 6:58 UTC (permalink / raw) On Sun, 29 Apr 2007 23:36:53 +0100, (see below) wrote: > On 29/4/07 18:48, in article 1n38bsd8xx0uc$.1eo1arncmwvkn.dlg@40tude.net, > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote: > >> What about "polymorphism"? It means exactly the opposite to what its >> translation suggests (many-formed/shaped). > > You have lost me. It means exactly what it says. But there is only one form (~interface) of a polymorphic thing. Substance (~implementation) is different. They should probably take "convergent" instead. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 6:58 ` Dmitry A. Kazakov @ 2007-04-30 9:59 ` Markus E Leypold 2007-04-30 10:01 ` Markus E Leypold ` (2 subsequent siblings) 3 siblings, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-04-30 9:59 UTC (permalink / raw) >>>> Your preference (unfortunately enshrined in OO jargon) >>>> does serious violence to English grammar! >>>> >>>> An <x>or is something that performs or implements <x>, >>>> not something that has <x> performed upon it! >>>> >>>> An actor is not a script. >>> What about "polymorphism"? It means exactly the opposite to what its >>> translation suggests (many-formed/shaped). >> >> You have lost me. It means exactly what it says. > > But there is only one form (~interface) of a polymorphic thing. Substance > (~implementation) is different. They should probably take "convergent" > instead. Wow, inbelievable. It actually works: If your original proposition is untenable, just open up another mostly unrelated but equally untenable line of argument. Repeat ad libitum. For more inspiration I suggest http://www.nizkor.org/features/fallacies/. Your own "But what about <some completely unrealted subject>" is probably not among them. You're indeed writing the book there. Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 6:58 ` Dmitry A. Kazakov 2007-04-30 9:59 ` Markus E Leypold @ 2007-04-30 10:01 ` Markus E Leypold 2007-04-30 10:36 ` Georg Bauhaus 2007-04-30 14:57 ` (see below) 3 siblings, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-04-30 10:01 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Sun, 29 Apr 2007 23:36:53 +0100, (see below) wrote: > >> On 29/4/07 18:48, in article 1n38bsd8xx0uc$.1eo1arncmwvkn.dlg@40tude.net, >> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote: >> >>> What about "polymorphism"? It means exactly the opposite to what its >>> translation suggests (many-formed/shaped). >> >> You have lost me. It means exactly what it says. > > But there is only one form (~interface) of a polymorphic thing. Substance ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Should be a strong indication that the 'poly' doesn't refer to the interface in the sense you're using the word. Are you ever assailed by doubt in situations like this? > (~implementation) is different. They should probably take "convergent" > instead. Converges to what? Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 6:58 ` Dmitry A. Kazakov 2007-04-30 9:59 ` Markus E Leypold 2007-04-30 10:01 ` Markus E Leypold @ 2007-04-30 10:36 ` Georg Bauhaus 2007-04-30 10:40 ` Georg Bauhaus 2007-04-30 12:14 ` Dmitry A. Kazakov 2007-04-30 14:57 ` (see below) 3 siblings, 2 replies; 84+ messages in thread From: Georg Bauhaus @ 2007-04-30 10:36 UTC (permalink / raw) On Mon, 2007-04-30 at 08:58 +0200, Dmitry A. Kazakov wrote: > On Sun, 29 Apr 2007 23:36:53 +0100, (see below) wrote: > > > On 29/4/07 18:48, in article 1n38bsd8xx0uc$.1eo1arncmwvkn.dlg@40tude.net, > > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote: > > > >> What about "polymorphism"? It means exactly the opposite to what its > >> translation suggests (many-formed/shaped). > > > > You have lost me. It means exactly what it says. > > But there is only one form (~interface) of a polymorphic thing. Substance > (~implementation) is different. They should probably take "convergent" > instead. Using the same interface, you can refer to many differently shapes objects. poly_ref: T'class := Factory.make(read_input); Who said that *objects* are polymorphic at any one time? ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 10:36 ` Georg Bauhaus @ 2007-04-30 10:40 ` Georg Bauhaus 2007-04-30 12:14 ` Dmitry A. Kazakov 1 sibling, 0 replies; 84+ messages in thread From: Georg Bauhaus @ 2007-04-30 10:40 UTC (permalink / raw) On Mon, 2007-04-30 at 12:36 +0200, Georg Bauhaus wrote: > On Mon, 2007-04-30 at 08:58 +0200, Dmitry A. Kazakov wrote: > > On Sun, 29 Apr 2007 23:36:53 +0100, (see below) wrote: > > > > > On 29/4/07 18:48, in article 1n38bsd8xx0uc$.1eo1arncmwvkn.dlg@40tude.net, > > > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote: > > > > > >> What about "polymorphism"? It means exactly the opposite to what its > > >> translation suggests (many-formed/shaped). > > > > > > You have lost me. It means exactly what it says. > > > > But there is only one form (~interface) of a polymorphic thing. Substance > > (~implementation) is different. They should probably take "convergent" > > instead. > > Using the same interface, you can refer to many differently > shapes objects. > > poly_ref: T'class := Factory.make(read_input); > > > Who said that *objects* are polymorphic at any one time? Or, if you insist on references that can be reassigned so they really exhibit some polymorphism, consider a pointer to T'class. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 10:36 ` Georg Bauhaus 2007-04-30 10:40 ` Georg Bauhaus @ 2007-04-30 12:14 ` Dmitry A. Kazakov 1 sibling, 0 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-30 12:14 UTC (permalink / raw) On Mon, 30 Apr 2007 12:36:33 +0200, Georg Bauhaus wrote: > Using the same interface, you can refer to many differently > shapes objects. The idea is that the implementation, internal structure, etc of the object is abstracted away. Shouldn't the term refer to what's left? Provided, that form/shape does not refer to outward appearance that users can see from outside. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 6:58 ` Dmitry A. Kazakov ` (2 preceding siblings ...) 2007-04-30 10:36 ` Georg Bauhaus @ 2007-04-30 14:57 ` (see below) 3 siblings, 0 replies; 84+ messages in thread From: (see below) @ 2007-04-30 14:57 UTC (permalink / raw) On 30/4/07 07:58, in article x83lepvaonj0$.8nqcwcdg7ykd.dlg@40tude.net, "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote: > On Sun, 29 Apr 2007 23:36:53 +0100, (see below) wrote: > >> On 29/4/07 18:48, in article 1n38bsd8xx0uc$.1eo1arncmwvkn.dlg@40tude.net, >> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote: >> >>> What about "polymorphism"? It means exactly the opposite to what its >>> translation suggests (many-formed/shaped). >> >> You have lost me. It means exactly what it says. > > But there is only one form (~interface) of a polymorphic thing. Substance > (~implementation) is different. They should probably take "convergent" > instead. Precisely: the "substance" (you are beginning to sound like a mediaeval scholastic theologian) is polymorphic. -- Bill Findlay <surname><forename> chez blueyonder.co.uk ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-29 8:19 ` Dmitry A. Kazakov 2007-04-29 15:10 ` (see below) @ 2007-04-30 10:30 ` Georg Bauhaus 2007-04-30 12:16 ` Dmitry A. Kazakov 1 sibling, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-04-30 10:30 UTC (permalink / raw) On Sun, 2007-04-29 at 10:19 +0200, Dmitry A. Kazakov wrote: > > my containers would be providing iteration if they can do one of > > > > - take a subprogram (e.g.) and call it for each of a collection > > of elements > > > > - provide access to an element and then the next if any where the > > meaning of "next" is specified in the collection's contract > > > > The amount of determinism need not be 100%. E.g., the post-condition > > if Iterate that each element is visited once, in no particular order, > > seems reasonable to me. > > Consider the precondition of the code performed for each element. It is > "here is an unvisited element" You can easily state it for the second case, > because you have the iterator's value. For the former case you have a > problem, because the precondition of the subprogram cannot be formulated > and hence verified in any way. Iteration in For_Each is controlled by the iterator For_Each, hence the iterator will make sure that the subprogram passed to For_Each will see each element once; that's a condition entirely outside the reach of my generic actual subprogram (or subprogram pointer). But so what? That's desirable. My subprogram can hardly be arranged to be called with an element more than once by For_Each, or not at all (instantiation not being recursive in Ada): "your subprogram is called with each element once" is part of the contract of For_Each. So it is not a question of trusting the iterator but rather a mere consequence of trust in the iterator being defined as required by the specification of iterator. > > Is there iteration in the following SETL expression? > > > > Result := { x : x in {1, 3, 24, 17, 11} | P(x) }; > > Iteration in what? In the language construct? In Result? Consider a > possibility that Result were computed at compile time. Would it still be > iteration? That's the point, there is iteration in this set former, but it happens behind the scene: on an AS-IF basis, it does not even matter when (or even if) iteration is happening; all that counts is that you can explain the meaning of the set former in terms of iteration. In fact, IIRC, SETL does say that the elements of {1, 3, 24, 17, 11} are picked in some order and checked against P. You build sets and you give estimates of O(f(n)) based on the little that is know about how iteration is performed in set formers. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 10:30 ` Georg Bauhaus @ 2007-04-30 12:16 ` Dmitry A. Kazakov 2007-04-30 14:48 ` Georg Bauhaus 0 siblings, 1 reply; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-30 12:16 UTC (permalink / raw) On Mon, 30 Apr 2007 12:30:29 +0200, Georg Bauhaus wrote: > On Sun, 2007-04-29 at 10:19 +0200, Dmitry A. Kazakov wrote: > > My subprogram can hardly be arranged to be called with an element > more than once by For_Each, or not at all (instantiation not > being recursive in Ada): > "your subprogram is called with each element once" is part of the > contract of For_Each. The point is that you cannot state this contract formally. It is equivalent to the well-ordering principle, I guess. > So it is not a question of trusting the iterator but rather > a mere consequence of trust in the iterator being defined > as required by the specification of iterator. But you could not present any formal specification of. Consider the program that counts elements of a set: C : Protected_Integer; procedure Count is begin C.Inc; end Count; begin C.Set (0); foreach S do Count; How could you prove that C.Get = S'Length? >>> Is there iteration in the following SETL expression? >>> >>> Result := { x : x in {1, 3, 24, 17, 11} | P(x) }; >> >> Iteration in what? In the language construct? In Result? Consider a >> possibility that Result were computed at compile time. Would it still be >> iteration? > > That's the point, there is iteration in this set former, but it > happens behind the scene: on an AS-IF basis, it does not even matter > when (or even if) iteration is happening; Right, that is _the_ point. What is the reason to call this "iteration," rather than an operation constructing a new set? -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 12:16 ` Dmitry A. Kazakov @ 2007-04-30 14:48 ` Georg Bauhaus 2007-04-30 16:29 ` Dmitry A. Kazakov 0 siblings, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-04-30 14:48 UTC (permalink / raw) On Mon, 2007-04-30 at 14:16 +0200, Dmitry A. Kazakov wrote: > > So it is not a question of trusting the iterator but rather > > a mere consequence of trust in the iterator being defined > > as required by the specification of iterator. > > But you could not present any formal specification of. > > Consider the program that counts elements of a set: > > C : Protected_Integer; > procedure Count is > begin > C.Inc; > end Count; > begin > C.Set (0); > foreach S do Count; "The following iterator is defined: generic with procedure P(C: Cursor); procedure foreach(S: Set); "The foreach procedure operates as if the following body were written procedure foreach(S: Set) is C: Cursor; begin C := first(S); while has_element(C) loop P(C); next(C); end loop; end; "The set S is locked while foreach is executing." > How could you prove that C.Get = S'Length? Given Sum: Integer := 0; procedure Count(C: Cursor) is begin Sum := Sum + 1; end; procedure how_many is new foreach(P => Count); Still impossible to show the above after the first run? > >>> Is there iteration in the following SETL expression? > >>> > >>> Result := { x : x in {1, 3, 24, 17, 11} | P(x) }; > >> > >> Iteration in what? In the language construct? In Result? Consider a > >> possibility that Result were computed at compile time. Would it still be > >> iteration? > > > > That's the point, there is iteration in this set former, but it > > happens behind the scene: on an AS-IF basis, it does not even matter > > when (or even if) iteration is happening; > > Right, that is _the_ point. What is the reason to call this "iteration," > rather than an operation constructing a new set? (It isn't called iteration, actually. The above is a set former. This was meant to be used for clarification, i.e. to learn what iteration might mean.) ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 14:48 ` Georg Bauhaus @ 2007-04-30 16:29 ` Dmitry A. Kazakov 2007-04-30 17:24 ` Georg Bauhaus 2007-04-30 19:29 ` Simon Wright 0 siblings, 2 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-30 16:29 UTC (permalink / raw) On Mon, 30 Apr 2007 16:48:53 +0200, Georg Bauhaus wrote: > On Mon, 2007-04-30 at 14:16 +0200, Dmitry A. Kazakov wrote: > >>> So it is not a question of trusting the iterator but rather >>> a mere consequence of trust in the iterator being defined >>> as required by the specification of iterator. >> >> But you could not present any formal specification of. >> >> Consider the program that counts elements of a set: >> >> C : Protected_Integer; >> procedure Count is >> begin >> C.Inc; >> end Count; >> begin >> C.Set (0); >> foreach S do Count; > > "The following iterator is defined: > > generic > with procedure P(C: Cursor); > procedure foreach(S: Set); > > "The foreach procedure operates as if the following body > were written > > procedure foreach(S: Set) is > C: Cursor; > begin > C := first(S); You forgot that first is not defined on Set, which is not well-ordered and thus does not have visible implementations of first, last, next, prev etc in its interface. It has Length, =, /=, :=, and, or, xor, /, Empty, in, not in. [*] > while has_element(C) loop > P(C); > next(C); > end loop; > end; > > "The set S is locked while foreach is executing." Concurrency is not the issue. Some ordered sets might become unordered in presence of concurrent access. But the reason is irrelevant here. The set is declared unordered. Locking it cannot not change that, unless you looked in the implementation. >> How could you prove that C.Get = S'Length? > > Given > Sum: Integer := 0; > procedure Count(C: Cursor) is > begin > Sum := Sum + 1; > end; > procedure how_many is new foreach(P => Count); > Still impossible to show the above after the first run? No, that would not be a proof, only a test. To make a proof out of it, you have to run this test on all possible programs with all possible sets. --------- * If Element of unordered Set is itself ordered and countable, then you could solve the problem by combining Element'Succ with "in" membership test. I.e. Element would give you an order. But in general case there could be no Element'Succ. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 16:29 ` Dmitry A. Kazakov @ 2007-04-30 17:24 ` Georg Bauhaus 2007-04-30 18:54 ` Dmitry A. Kazakov 2007-04-30 19:29 ` Simon Wright 1 sibling, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-04-30 17:24 UTC (permalink / raw) On Mon, 2007-04-30 at 18:29 +0200, Dmitry A. Kazakov wrote: > > "The foreach procedure operates as if the following body > > were written > > > > procedure foreach(S: Set) is > > C: Cursor; > > begin > > C := first(S); > > You forgot that first is not defined on Set, I was tempted to add C := first(S); -- where first picks any as defined for the -- `first` operation on sets; gimmeacursor(S); > which is not well-ordered and > thus does not have visible implementations of As I said, Iterate operates as if it were implemented the way shown. I had intended to base the argument on your prior remark that we can specify the preconditions on next etc. I claim that we can give a meaningful definition of First, too, which is not given by the usual meaning of First; we could call it Frumble if you like. > > while has_element(C) loop > > P(C); > > next(C); > > end loop; > > end; > > > > "The set S is locked while foreach is executing." > > Concurrency is not the issue. OK > The set > is declared unordered. Yes. An iterator will work without an externally visible order. > >> How could you prove that C.Get = S'Length? > > > > Given > > Sum: Integer := 0; > > procedure Count(C: Cursor) is > > begin > > Sum := Sum + 1; > > end; > > procedure how_many is new foreach(P => Count); > > Still impossible to show the above after the first run? > > No, that would not be a proof, only a test. To make a proof out of it, you > have to run this test on all possible programs with all possible sets. No, I only have to combine the semantics of foreach as specified previously, ":=", "+", etc. Then I can show that I get what I asked for. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 17:24 ` Georg Bauhaus @ 2007-04-30 18:54 ` Dmitry A. Kazakov 0 siblings, 0 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-30 18:54 UTC (permalink / raw) On Mon, 30 Apr 2007 19:24:52 +0200, Georg Bauhaus wrote: > On Mon, 2007-04-30 at 18:29 +0200, Dmitry A. Kazakov wrote: > >>> "The foreach procedure operates as if the following body >>> were written >>> >>> procedure foreach(S: Set) is >>> C: Cursor; >>> begin >>> C := first(S); >> >> You forgot that first is not defined on Set, > > I was tempted to add > > C := first(S); -- where first picks any as defined for the > -- `first` operation on sets; gimmeacursor(S); > >> which is not well-ordered and >> thus does not have visible implementations of > > As I said, Iterate operates as if it were implemented the way shown. > I had intended to base the argument on your prior remark that we > can specify the preconditions on next etc. I claim that we can > give a meaningful definition of First, too, which is not given by > the usual meaning of First; we could call it Frumble if you like. But you could not provide *any* implementation of Frumble in the terms of the operations defined on Set. To build a sequence of elements of S, you need the well-ordering principle: let s1 be the least in S (well-ordering of S) S1 = S / {s1} let s2 be the least in S1 (well-ordering of S1) S2 = S1 / {s2} ... until sN such that SN-1 = {sN} Now { s1, s2, ..., sN } is an ordering of S. Here it is not "/" which makes problems, but "least," which is as good/bad as "any" or "Frumble." So giving it any name changes nothing. >> The set >> is declared unordered. > > Yes. An iterator will work without an externally visible order. = per magic > No, I only have to combine the semantics of foreach as specified > previously, ":=", "+", etc. Then I can show that I get what I > asked for. But the semantics you have presented relies on a well-ordering of the set, which is claimed to be unordered. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 16:29 ` Dmitry A. Kazakov 2007-04-30 17:24 ` Georg Bauhaus @ 2007-04-30 19:29 ` Simon Wright 2007-04-30 20:04 ` Dmitry A. Kazakov 1 sibling, 1 reply; 84+ messages in thread From: Simon Wright @ 2007-04-30 19:29 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Mon, 30 Apr 2007 16:48:53 +0200, Georg Bauhaus wrote: >> "The foreach procedure operates as if the following body >> were written >> >> procedure foreach(S: Set) is >> C: Cursor; >> begin >> C := first(S); > > You forgot that first is not defined on Set, which is not > well-ordered and thus does not have visible implementations of > first, last, next, prev etc in its interface. It has Length, =, /=, > :=, and, or, xor, /, Empty, in, not in. [*] First is not *publicly* defined on Set but this is *implementation*, for Pete's sake! It's likely to be hard to implement iteration/foreach efficiently without private knowledge .. but you could, for example, copy the Set and then pick a random member, remove it from the copy, and process it, until the copy was empty. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 19:29 ` Simon Wright @ 2007-04-30 20:04 ` Dmitry A. Kazakov 2007-05-01 0:11 ` Markus E Leypold 2007-05-01 9:02 ` Georg Bauhaus 0 siblings, 2 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-04-30 20:04 UTC (permalink / raw) On Mon, 30 Apr 2007 20:29:22 +0100, Simon Wright wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > >> On Mon, 30 Apr 2007 16:48:53 +0200, Georg Bauhaus wrote: > >>> "The foreach procedure operates as if the following body >>> were written >>> >>> procedure foreach(S: Set) is >>> C: Cursor; >>> begin >>> C := first(S); >> >> You forgot that first is not defined on Set, which is not >> well-ordered and thus does not have visible implementations of >> first, last, next, prev etc in its interface. It has Length, =, /=, >>:=, and, or, xor, /, Empty, in, not in. [*] > > First is not *publicly* defined on Set but this is *implementation*, > for Pete's sake! It's likely to be hard to implement iteration/foreach > efficiently without private knowledge You missed the point. It was that if foreach were a primitive operation defined on an unordered set, then its contract could not be stated. The example I posed before Georg was to prove that counting members using foreach with an atomic integer would indeed have returned the number of members. (that is - without looking into the implementation, because there it is obviously ordered, iteratable, whatever) > .. but you could, for example, > copy the Set and then pick a random member, remove it from the copy, > and process it, until the copy was empty. I answered to this in a subthread. To be able to pick a random member <=> to have an order. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 20:04 ` Dmitry A. Kazakov @ 2007-05-01 0:11 ` Markus E Leypold 2007-05-01 9:02 ` Georg Bauhaus 1 sibling, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-05-01 0:11 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Mon, 30 Apr 2007 20:29:22 +0100, Simon Wright wrote: > >> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: >> >>> On Mon, 30 Apr 2007 16:48:53 +0200, Georg Bauhaus wrote: >> >>>> "The foreach procedure operates as if the following body >>>> were written >>>> >>>> procedure foreach(S: Set) is >>>> C: Cursor; >>>> begin >>>> C := first(S); >>> >>> You forgot that first is not defined on Set, which is not >>> well-ordered and thus does not have visible implementations of >>> first, last, next, prev etc in its interface. It has Length, =, /=, >>>:=, and, or, xor, /, Empty, in, not in. [*] >> >> First is not *publicly* defined on Set but this is *implementation*, >> for Pete's sake! It's likely to be hard to implement iteration/foreach >> efficiently without private knowledge > > You missed the point. It was that if foreach were a primitive operation No, you're missing the point. You've asserted that one "cannot iterate over relational tables because they are not ordered". Then you shifted the discussion to sets as an example -- in this case I'll permit it. So we're now talking about wether one can iterate over sets. Now, we are talking about _implementation_. And wether one can implement an iteration mechanism for sets (not necessarily in terms of the set primitive operations). I already could stop talking here, since iteration over set data structures has been implemented often enough. But just to complete the argument: We call a set/container implementation unordered, if the user is not required to provide an order function when the instantiating (either an object or a generic). That doesn't preclude an implementation from either using an internal, implementation dependent order to implement iteration or just use the following method: 1) for First() find some arbitrary element in the container/set. Mark it as already visited in the iterator state and return it. 2) for Next() find some other element in the container that hasn't ben visited yet. Mark it as already visited in the iterator state and return it. That requires that there is an internal way for the implementation to walk over all the the elements in the container. Nonetheless -- the thing implemented is still a set (in any useful interpretation), even if it has some ad-hoc ordering internally. What makes it a set is, that it exposes the operations - Empty -- construct an empty set - Add -- add an element - Remove -- remove an alement - Is_In -- Test wether element is in Set. It doesn't magically become a non-set if it also exposes iteration operations - Start -- Create an Iterator/Cursor. - Element -- Extract Element from Cursor - Next -- Set Cursor to next Element Note that there is no implementation exposed. Some example: A simple _implementation_ for a finite set would be a linked list. Interesting enough, there is a mechanism to walk through all elements in the set, but that doesn't impose an order in the sense the word is used in "ordered set". Because the data type "ordered set" is defined as a base set B and a relation f, so that f has certain properties and any value of the data type is a subset of B. The sequence in which a given set S \subset_of B is visited by walking the linked list: s1, s2, s3 ..., doesn't produce a relation on all of B. Got the difference? I'm a bit suprised you don't know this, since you said you have been studying mathematics. > defined on an unordered set, then its contract could not be stated. And that is nonsense too. Shall we? (A) We define cursors (abstractly) as thingies tha # The following operations/functions have to be implemented # Every function w/o a precondition has to be total. Element: c:Cursor => e:Element post: e \in Set(c) # see below # The following are only helper functions for the functional spec. # They describe the cursor state for purposes of the specification. Set : c:Cursor => s:Set Visited: c:Cursor => s:Set post: Element(c) \in s AND s \subset_of Set(c) # Note: The post condition of Visited just describes the limits # within which the state a Cursor which has been "attached" to a # given set Set(c) can change. (B) We define iteration as operations on cursors First: s:Set => c:Cursor post: Element(c) \in s AND Visited(c) = { Element(c) } AND Set(c) = s # Note: Any choice of Element(c) from s will satisfy the requirement. You might even # randomly select an element from s. Set(c) is necessary to memorize the set we're # iterating over (this is in the nature of a functional spec). Next: c:Cursor => c:'Cursor pre: Set(c) \without Visited(c) is not empty post: Set(c) = Set(c') # consistency, continues iteration over Set(c) AND Element(c') \in Set(c) AND Element(c') \not\in Visited(c) # pick an element not yet visited AND Visited(c') = Visited(c) \union { Element(c') # memorize "new" Element as visited # Note: Again the element picked is arbitrary, but must not have been seen before. So -- where did I use an order function (which would have to be valid for every s \in Set)? Do you deny that this functional specfication describes a contract for cursors to iterate over sets? > I answered to this in a subthread. To be able to pick a random member <=> > to have an order. No. Your definition of order (specifically an ordered data type) lacks precision. Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-30 20:04 ` Dmitry A. Kazakov 2007-05-01 0:11 ` Markus E Leypold @ 2007-05-01 9:02 ` Georg Bauhaus 2007-05-01 10:19 ` Dmitry A. Kazakov 1 sibling, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-05-01 9:02 UTC (permalink / raw) On Mon, 2007-04-30 at 22:04 +0200, Dmitry A. Kazakov wrote: > It was that if foreach were a primitive operation > defined on an unordered set, then its contract could not be stated. Every specific Set object (collection of elements) inside a computer has a memory layout. That is, for every specific set object there exists an index set, the collection of addresses that maps elements 1:1 onto a set of pairwise disjoint natural numbers. Since, I think, we are talking about computer representations of sets, the fact of representation (1) establishes some order (2) hence allows arguing about First, ..., Foreach in terms of the general (and specifically unknown) properties of every representation. For every finite set that doesn't fit into core memory, use garbage collection (a job for the librarian you mentioned). Define the element index number via a pair of numbers (time, address). These, again, can be enumerated. > To be able to pick a random member <=> > to have an order. Can you determine whether one of your sets is empty? ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-01 9:02 ` Georg Bauhaus @ 2007-05-01 10:19 ` Dmitry A. Kazakov 2007-05-01 13:42 ` Georg Bauhaus 0 siblings, 1 reply; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-05-01 10:19 UTC (permalink / raw) On Tue, 01 May 2007 11:02:22 +0200, Georg Bauhaus wrote: > On Mon, 2007-04-30 at 22:04 +0200, Dmitry A. Kazakov wrote: >> It was that if foreach were a primitive operation >> defined on an unordered set, then its contract could not be stated. > > Every specific Set object (collection of elements) inside a computer has > a memory layout. So the memory layout is a part of the contract? [... I skip stuff that computers are DFA's, which is not disputed ...] >> To be able to pick a random member <=> >> to have an order. > > Can you determine whether one of your sets is empty? Sure. I can compare an empty set with the given set. This does not require picking elements. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-01 10:19 ` Dmitry A. Kazakov @ 2007-05-01 13:42 ` Georg Bauhaus 2007-05-01 17:16 ` Dmitry A. Kazakov 0 siblings, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-05-01 13:42 UTC (permalink / raw) On Tue, 2007-05-01 at 12:19 +0200, Dmitry A. Kazakov wrote: > On Tue, 01 May 2007 11:02:22 +0200, Georg Bauhaus wrote: > > > On Mon, 2007-04-30 at 22:04 +0200, Dmitry A. Kazakov wrote: > >> It was that if foreach were a primitive operation > >> defined on an unordered set, then its contract could not be stated. > > > > Every specific Set object (collection of elements) inside a computer has > > a memory layout. > > So the memory layout is a part of the contract? Yes, in the sense that the specifics of memory layout and such are unknown and irrelevant to the client; in particular, no order needs to be specified. However, it is then known that the elements of sets in a computer have said properties. These properties will assign meaning to the phrase "Procedure Foreach calls procedure P once for each element of S" or, put differently but still with just logical references to implementation details, "For each node of the set S, the node will be used as the actual argument of P when P is invoked; this is done once for each node of S in an unspecified order." There isn't much a client (programmer) needs to know about nodes. He or she isn't concerned with implementation details. But the abstract notions of what is implemented provide enough formal information so that the operation of Foreach can be described formally. (Just not in terms of its own inner workings as a postcondition stating foreach in terms of foreach. So what?) As a consequence of this formal description, ("nodes", "called once", "each") I can call Foreach passing a procedure Add_One that increments a count variable when called. Provided there is a query function Length of Set (as is typically the case), then (remove quantifiers if more apt) function Unnamed(S: Set) return Count_Type; -- post: (∀s) s in Set [ s.Length = Result ] function Unnamed(S: Set) return Count_Type is count_var: Count_Type; procedure Add_One(C: Cursor) is begin count_var := count_var + 1; end; begin count_var := 0; Foreach(S, Add_One'access); -- Claim (∀s) s in Set [ s.Length = count_var ] -- Proof. Foreach calls Add_One exactly once for each node -- in s. Add_One unconditionally increments Count_Var by 1. -- No other operation changes the value of Count_Var. -- Hence, Count_Var (initially zero) is incremented by 1 for -- each node in s, so Foreach counts the elements of s. ∎ pragma assert(Length(S) = count_var); return count_var; end; If there is no Length defined for Set, the above is still enough, to me at least, to show that this computes the number of elements in a Set using a computer representation even when there is no known order of elements and without knowledge of the actual implementation. I think it is possible to add even more contract clauses almost like the ones you have mentioned: function First(S: Set) return Cursor; -- post: let (Result then t0) = (First(S) then Clock), -- (Result' then t) = (First(S) then Clock) in -- (∀t) t > t0 [ Result /= Result' ] As you can see, there is some order again but I don't have to know the order. (Finding a first book (and then the next book) is the job of the librarian, not mine.) > >> To be able to pick a random member <=> > >> to have an order. > > > > Can you determine whether one of your sets is empty? > > Sure. I can compare an empty set with the given set. This does not require > picking elements. Uhm, not require the client to pick or the implementation to pick? When two sets A and B are equal iff the same elements belong to both A and B, won't you need at least references to the elements for "=" to be called for the elements? ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-01 13:42 ` Georg Bauhaus @ 2007-05-01 17:16 ` Dmitry A. Kazakov 2007-05-01 19:14 ` Randy Brukardt 2007-05-01 21:41 ` Georg Bauhaus 0 siblings, 2 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-05-01 17:16 UTC (permalink / raw) On Tue, 01 May 2007 15:42:21 +0200, Georg Bauhaus wrote: > On Tue, 2007-05-01 at 12:19 +0200, Dmitry A. Kazakov wrote: >> On Tue, 01 May 2007 11:02:22 +0200, Georg Bauhaus wrote: >> >>> On Mon, 2007-04-30 at 22:04 +0200, Dmitry A. Kazakov wrote: >>>> It was that if foreach were a primitive operation >>>> defined on an unordered set, then its contract could not be stated. >>> >>> Every specific Set object (collection of elements) inside a computer has >>> a memory layout. >> >> So the memory layout is a part of the contract? > > Yes, in the sense that the specifics of memory layout and such are > unknown and irrelevant to the client; in particular, no order needs > to be specified. Apart from obvious uselessness of contracts referencing to the memory layout, the above is self-contradictory. Memory layout defines an order. It also is a part of the contract. Hence the interface is ordered. > -- Proof. Foreach calls Add_One exactly once for each node > -- in s. Add_One unconditionally increments Count_Var by 1. > -- No other operation changes the value of Count_Var. > -- Hence, Count_Var (initially zero) is incremented by 1 for > -- each node in s, so Foreach counts the elements of s. ∎ So the precondition of Add_One is true? Then your proof is wrong. Here is a counterexample: 1. let S'Length = N 2. because pred (Add_One) = true, that also includes Count_Val = N + 1. So let's take it. 3. observe that for whatever number of calls to Add_One might then happen, the result Count_Val is not N. i.e. Count_Val = N does not follow from S'Length = N /\ pred (Add_One) = true. q.e.d. (You cannot use true as the precondition. If you should to narrow it, for this you need the invariant of the implicit loop behind "foreach," and that would require ordering of S.) > As you can see, there is some order again but I don't have to know > the order. (Finding a first book (and then the next book) is the > job of the librarian, not mine.) Librarian is the interface. If it finds first book then that is a publicly ordered set = you _can_ know the order without breaking the abstraction. >>>> To be able to pick a random member <=> >>>> to have an order. >>> >>> Can you determine whether one of your sets is empty? >> >> Sure. I can compare an empty set with the given set. This does not require >> picking elements. > > Uhm, not require the client to pick or the implementation to pick? > When two sets A and B are equal iff the same elements > belong to both A and B, won't you need at least references to the > elements for "=" to be called for the elements? No. You have to show that whatever element you took (no matter how) it is either in both sets or else in neither: forall x in S, x in Q This does not force you to present any method of getting elements from any of the sets. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-01 17:16 ` Dmitry A. Kazakov @ 2007-05-01 19:14 ` Randy Brukardt 2007-05-01 20:14 ` Dmitry A. Kazakov 2007-05-02 8:06 ` Markus E Leypold 2007-05-01 21:41 ` Georg Bauhaus 1 sibling, 2 replies; 84+ messages in thread From: Randy Brukardt @ 2007-05-01 19:14 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message news:1ozvzzh59ebq8$.yeh9do8s3hig$.dlg@40tude.net... > On Tue, 01 May 2007 15:42:21 +0200, Georg Bauhaus wrote: ... > > Yes, in the sense that the specifics of memory layout and such are > > unknown and irrelevant to the client; in particular, no order needs > > to be specified. > > Apart from obvious uselessness of contracts referencing to the memory > layout, the above is self-contradictory. Memory layout defines an order. It > also is a part of the contract. Hence the interface is ordered. And now all is clear. It is impossible to implement a set with having some form of order. So, for us practitioners, an "unordered set" is simply a set with no defined order. I can see that you are arguing about a idealized set unordered set that cannot actually exist - an abstraction that is irrelevant in practice. No wonder people are confused. There is a reason that Ada.Containers has ordered and hashed sets, but not a mathematically unordered one. That because the latter is impossible to implement without a suboptimal mapping into one of the other forms. The net effect is that even if you could use such a form, you would take a massive performance hit to do so (all operations being O(N)). As such, there is no reason to consider such forms or worry about their properties. Randy. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-01 19:14 ` Randy Brukardt @ 2007-05-01 20:14 ` Dmitry A. Kazakov 2007-05-02 7:52 ` Markus E Leypold 2007-05-02 8:06 ` Markus E Leypold 1 sibling, 1 reply; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-05-01 20:14 UTC (permalink / raw) On Tue, 1 May 2007 14:14:46 -0500, Randy Brukardt wrote: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message > news:1ozvzzh59ebq8$.yeh9do8s3hig$.dlg@40tude.net... >> On Tue, 01 May 2007 15:42:21 +0200, Georg Bauhaus wrote: > ... >>> Yes, in the sense that the specifics of memory layout and such are >>> unknown and irrelevant to the client; in particular, no order needs >>> to be specified. >> >> Apart from obvious uselessness of contracts referencing to the memory >> layout, the above is self-contradictory. Memory layout defines an order. It >> also is a part of the contract. Hence the interface is ordered. > > And now all is clear. > > It is impossible to implement a set with having some form of order. So, for > us practitioners, an "unordered set" is simply a set with no defined order. > I can see that you are arguing about a idealized set unordered set that > cannot actually exist - an abstraction that is irrelevant in practice. No > wonder people are confused. > > There is a reason that Ada.Containers has ordered and hashed sets, but not a > mathematically unordered one. That because the latter is impossible to > implement without a suboptimal mapping into one of the other forms. The net > effect is that even if you could use such a form, you would take a massive > performance hit to do so (all operations being O(N)). As such, there is no > reason to consider such forms or worry about their properties. I definitely agree with this. And this is the answer to the OP question about "generic collections," they would be close to useless. Yet I think that this abstraction is not that irrelevant. One example is distributed systems, like DB engines. There is a reason why relational containers are defined unordered. It is not because no order could be invented. It is because this abstraction forces the programmer either to use snapshots (ordered mappings of an unordered set) or stored procedures (foreach-magic) to get at an order. Making the interface ordered would probably prevent efficient implementations of the DB engines. This boils down to the question of the underlying hardware. DB engine is a hardware from the application point view. It is a very strange hardware for which the logic of being able to enumerate everything at once, here and now, does not apply. It is likely so for any system with distributed containers and distributed programs dealing with them. In such hardware foreach-magic could be in order of magnitude more efficient than ordering in situ. Or let's take Get_Pixel / Set_Pixel on the image containers of the graphic accelerator. Further, if we looked into the future, on quantum computing stuff, then there is a possibility that such hardware could become rather normal. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-01 20:14 ` Dmitry A. Kazakov @ 2007-05-02 7:52 ` Markus E Leypold 0 siblings, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-05-02 7:52 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Tue, 1 May 2007 14:14:46 -0500, Randy Brukardt wrote: > >> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message >> news:1ozvzzh59ebq8$.yeh9do8s3hig$.dlg@40tude.net... >>> On Tue, 01 May 2007 15:42:21 +0200, Georg Bauhaus wrote: >> ... >>>> Yes, in the sense that the specifics of memory layout and such are >>>> unknown and irrelevant to the client; in particular, no order needs >>>> to be specified. >>> >>> Apart from obvious uselessness of contracts referencing to the memory >>> layout, the above is self-contradictory. Memory layout defines an order. It >>> also is a part of the contract. Hence the interface is ordered. >> >> And now all is clear. >> >> It is impossible to implement a set with having some form of order. So, for >> us practitioners, an "unordered set" is simply a set with no defined order. >> I can see that you are arguing about a idealized set unordered set that >> cannot actually exist - an abstraction that is irrelevant in practice. No >> wonder people are confused. >> >> There is a reason that Ada.Containers has ordered and hashed sets, but not a >> mathematically unordered one. That because the latter is impossible to >> implement without a suboptimal mapping into one of the other forms. The net >> effect is that even if you could use such a form, you would take a massive >> performance hit to do so (all operations being O(N)). As such, there is no >> reason to consider such forms or worry about their properties. > > I definitely agree with this. And this is the answer to the OP question > about "generic collections," they would be close to useless. > > Yet I think that this abstraction is not that irrelevant. One example is > distributed systems, like DB engines. There is a reason why relational > containers are defined unordered. It is not because no order could be > invented. It is because this abstraction forces the programmer either to > use snapshots (ordered mappings of an unordered set) or stored procedures > (foreach-magic) to get at an order. Making the interface ordered would > probably prevent efficient implementations of the DB engines. > > This boils down to the question of the underlying hardware. DB engine is a > hardware from the application point view. It is a very strange hardware for > which the logic of being able to enumerate everything at once, here and > now, does not apply. It is likely so for any system with distributed > containers and distributed programs dealing with them. In such hardware > foreach-magic could be in order of magnitude more efficient than ordering > in situ. Or let's take Get_Pixel / Set_Pixel on the image containers of the > graphic accelerator. Further, if we looked into the future, on quantum > computing stuff, then there is a possibility that such hardware could > become rather normal. But if we abstain for the moment from so many words and free wheeling associations and come back to your original statement: You asserted that one "cannot iterate over relational tables". I still do not get it. PostgresQL provides an interface to do exactly that: http://www.postgresql.org/docs/7.2/static/libpq-exec.html. In my book that interface provides means to "iterate over relational tables". Questioning wether this is really iteration or wether PostgresQL really provides "relational tables" is both, in my opinion, not a feasible option. So you have to admit that it is possible to iterate over realtional tables. Q.E.D. Thanks -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-01 19:14 ` Randy Brukardt 2007-05-01 20:14 ` Dmitry A. Kazakov @ 2007-05-02 8:06 ` Markus E Leypold 2007-05-03 0:37 ` Randy Brukardt 1 sibling, 1 reply; 84+ messages in thread From: Markus E Leypold @ 2007-05-02 8:06 UTC (permalink / raw) "Randy Brukardt" <randy@rrsoftware.com> writes: > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message > news:1ozvzzh59ebq8$.yeh9do8s3hig$.dlg@40tude.net... >> On Tue, 01 May 2007 15:42:21 +0200, Georg Bauhaus wrote: > ... >> > Yes, in the sense that the specifics of memory layout and such are >> > unknown and irrelevant to the client; in particular, no order needs >> > to be specified. >> >> Apart from obvious uselessness of contracts referencing to the memory >> layout, the above is self-contradictory. Memory layout defines an order. > It >> also is a part of the contract. Hence the interface is ordered. > > And now all is clear. No. The only thing that is clear to me, is, that DK is splitting hairs again, just to win the argument. > It is impossible to implement a set with having some form of order. So, for ^^^^^^^^^ Implement, yes. But it is possible to implement a set interface without forcing the user to provide an order function to instantiate the set. It is also possible to provide a mechanism for such an implementation that gives you all the elements in this set in some arbitary order/sequence which might change with every invocation. This is called iteration. DK originally stated, it is not possible to iterate over an unordered set: It is. It is possible to specify the contract for this iteration without referring to an order (I did it in one of my recent post). DK denied this. He is wrong. Implementing a set as a linked list might not be efficient enough for a large number of items -- still: It is a set in any sane sense and one can provide an interface to iterate over the items. And it has even been implemented without using an order defined on the elements of the set. So the even the statement "one cannot implement a set (with or without iteration) without providing an order over the elements" is plainly wrong. (And no: The linked list doesn't define an order on all possible elements of the set.) Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-02 8:06 ` Markus E Leypold @ 2007-05-03 0:37 ` Randy Brukardt 2007-05-03 8:36 ` Markus E Leypold 0 siblings, 1 reply; 84+ messages in thread From: Randy Brukardt @ 2007-05-03 0:37 UTC (permalink / raw) "Markus E Leypold" <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> wrote in message news:40irbbzm2t.fsf@hod.lan.m-e-leypold.de... > "Randy Brukardt" <randy@rrsoftware.com> writes: > > > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message > > news:1ozvzzh59ebq8$.yeh9do8s3hig$.dlg@40tude.net... > >> On Tue, 01 May 2007 15:42:21 +0200, Georg Bauhaus wrote: > > ... > >> > Yes, in the sense that the specifics of memory layout and such are > >> > unknown and irrelevant to the client; in particular, no order needs > >> > to be specified. > >> > >> Apart from obvious uselessness of contracts referencing to the memory > >> layout, the above is self-contradictory. Memory layout defines an order. > > It > >> also is a part of the contract. Hence the interface is ordered. > > > > And now all is clear. > > No. The only thing that is clear to me, is, that DK is splitting hairs > again, just to win the argument. Maybe, but that's just name calling and is never an appropriate way to conduct an argument. Besides, you're going to claim the same about me in your reply to this message... ;-) > > It is impossible to implement a set with having some form of order. So, for > ^^^^^^^^^ > > Implement, yes. But it is possible to implement a set interface > without forcing the user to provide an order function to instantiate > the set. It is also possible to provide a mechanism for such an > implementation that gives you all the elements in this set in some > arbitary order/sequence which might change with every invocation. This > is called iteration. You're repeating the obvious. But a set where you don't specify the order is still an ordered set: there exists an order between the elements, even if you don't know what it is and don't have to describe it. > DK originally stated, it is not possible to iterate over an unordered > set: It is. I actually agree with DK, using his definitions. The problem is that no such set could ever be constructed (even on a piece of paper, the elements have an order). So the fact is completely irrelevant: there is no such thing as an unordered set. > It is possible to specify the contract for this iteration without > referring to an order (I did it in one of my recent post). DK denied > this. He is wrong. Of course you can if you assume primitives that effectively give you an order. It's like specifying a contract for set inclusion: you certainly can do so, but it is unlikely to say anything interesting: it's mostly likely going to be a tautology. > Implementing a set as a linked list might not be efficient enough for > a large number of items -- still: It is a set in any sane sense and > one can provide an interface to iterate over the items. And it has > even been implemented without using an order defined on the elements > of the set. Yes, and so what? It still has an order between elements. That order doesn't have to be determined by the values of the elements, as you seem to be assuming. It could be determined by the address of the memory used or the ordering of some handle type, or by phase of the moon. But it isn't possible to have a set of elements without some order (at least on the sorts of machines that Ada was intended to program). > So the even the statement "one cannot implement a set (with or without > iteration) without providing an order over the elements" is plainly > wrong. A linked list sure;y provides an order for the elements. Why you insist on that order coming from the outside is beyond me. Even as hashed set doesn't meet your requirements for "order", which is completely ridiculous. > (And no: The linked list doesn't define an order on all possible > elements of the set.) An who cares about that? Any particular set of elements has an order. I don't much care if a different set object has a different order on the same elements. It's irrelevant. "An order" is not the same as "a defined order" or "the same order for any pair of elements with the same value". Indeed, any ordering between the values of the elements is completely unrelated to the abstract set properties. Any operations that depend on such an order are not set operations at all. In any case, this is an Ada forum, and abstractions that you cannot describe in Ada are simply not relevant (certainly not as the basis of containers). Any Ada implementation will have some implied ordering between the elements in the set. My contention always has been that "sets" are an irrelevant abstraction from a programming perspective. They're too inefficient to use for any purpose. What Ada.Containers calls a set is really a map where the keys are included as part of the elements. Yes, they have some set operations because some people thought if they were called sets they should have those operations. I would have preferred choosing a more sane name, but whatever. And I would hope that I was done reading this bulls***, but I'm sure I'm not... Randy. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-03 0:37 ` Randy Brukardt @ 2007-05-03 8:36 ` Markus E Leypold 2007-05-03 23:16 ` Randy Brukardt 0 siblings, 1 reply; 84+ messages in thread From: Markus E Leypold @ 2007-05-03 8:36 UTC (permalink / raw) "Randy Brukardt" <randy@rrsoftware.com> writes: > "Markus E Leypold" > <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> wrote in > message news:40irbbzm2t.fsf@hod.lan.m-e-leypold.de... >> "Randy Brukardt" <randy@rrsoftware.com> writes: >> >> > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message >> > news:1ozvzzh59ebq8$.yeh9do8s3hig$.dlg@40tude.net... >> >> On Tue, 01 May 2007 15:42:21 +0200, Georg Bauhaus wrote: >> > ... >> >> > Yes, in the sense that the specifics of memory layout and such are >> >> > unknown and irrelevant to the client; in particular, no order needs >> >> > to be specified. >> >> >> >> Apart from obvious uselessness of contracts referencing to the memory >> >> layout, the above is self-contradictory. Memory layout defines an > order. >> > It >> >> also is a part of the contract. Hence the interface is ordered. >> > >> > And now all is clear. >> >> No. The only thing that is clear to me, is, that DK is splitting hairs >> again, just to win the argument. > Maybe, but that's just name calling and is never an appropriate way to > conduct an argument. Well -- I admit being a tinsy bit annoyed here, since DK never proved/argued any of his assertions: Either he falls silent or changes the topic to just another "example" or some freely associated topic. > Besides, you're going to claim the same about me in > your reply to this message... ;-) We will see. I'm usually rather patient (as my posts in other threads have shown, I hope), when I want to make my point. >> > It is impossible to implement a set with having some form of order. So, > for >> ^^^^^^^^^ > >> Implement, yes. But it is possible to implement a set interface >> without forcing the user to provide an order function to instantiate >> the set. It is also possible to provide a mechanism for such an >> implementation that gives you all the elements in this set in some >> arbitary order/sequence which might change with every invocation. This >> is called iteration. > You're repeating the obvious. Sigh. Yes, it _is_ obvious. > But a set where you don't specify the order is > still an ordered set: Here I don't agree. I think we are not talking about abstract mathematical entities here, but about data types / containers. But first a short word on the abstract mathematical entitity (just in case we're straying mentally into that directions): I would find it inappropriate to call the set of colors an ordered set, just because there an order can be defined, which I haven't given. Mathematically an ordered set is (a) a set plus (b) a relation (with the approriate properties) on that set. If we have only a set it is only a set, not an ordered set (though it could be made to an ordered set). Now about the data type: The data type ordered set is defined as (a) a base set B (b) an order on that base set (c) the type of all subsets of B Note that the point of an ordered set data type is that you specify an order up front which is then _constant_ for all subsets of B. > there exists an order between the elements, even if ^^^^^^^ > you don't know what it is and don't have to describe it. In which sense does that order exist? In the linked list example a certain order of the elements in the subset (I prefer to call that sequence) comes into existence: But ad hoc and it doesn't constitute an order on the "set of all possible elements" (the set B). >> DK originally stated, it is not possible to iterate over an unordered >> set: It is. > > I actually agree with DK, using his definitions. The problem is that no such > set could ever be constructed (even on a piece of paper, the elements have > an order). So the fact is completely irrelevant: there is no such thing as > an unordered set. I repeat: There is a bit of confusion on 3 different things: (a) the way we write down sets (notation) (b) orders (binary relations with certain properties) (c) orderable sets, i.e. sets for which an order can be defined. You (in my opinion) are confusing ordered sets (sets for which b is given) with (c): Sets for which an order can be defined. I thing if you write down the definition "An ordered set is ..." you'll see the difference pretty fast: An ordered (in the mathematical sense) set is a pair (M,R) where M is a set and R a relation with certain properties. That is similar to the usual definition of a vector space: A vector space is a tuple (K,V,*,+) with ... -- where K is a field, V a set, * multiplication between vectors and scalars and + the vector addition. The vector space is the compound structure, not V or anything else. The _set_ V alone (i.e. the set R^3) is just a set, nothing else. The same applies to the concept of ordered set: An ordered set is a set plus an order relation. In mathematics AFAIK it's even not defined as an extra structure, since ist suffices to give R: M is just the domain of R, so in mathematics But essentially the same kind of argument -- as far as terminology goes -- has to be made for the abstract data type "ordered set" whose definition I already have sketched above. >> It is possible to specify the contract for this iteration without >> referring to an order (I did it in one of my recent post). DK denied >> this. He is wrong. > Of course you can if you assume primitives that effectively give you an > order. No. Have you read the functional spec I wrote? I just use set operations and a suitable cursor abstraction. Of course the choice of the next element is not deterministic in the specification but that is as it should be: It indicates that the implementation has a certain degree of freedom here. > It's like specifying a contract for set inclusion: you certainly can > do so, but it is unlikely to say anything interesting: it's mostly likely > going to be a tautology. ? >> Implementing a set as a linked list might not be efficient enough for >> a large number of items -- still: It is a set in any sane sense and >> one can provide an interface to iterate over the items. And it has >> even been implemented without using an order defined on the elements >> of the set. > Yes, and so what? It still has an order between elements. That order doesn't See above: The order needs to be constant for the data type "ordered set". > have to be determined by the values of the elements, as you seem to be > assuming. It could be determined by the address of the memory used or the > ordering of some handle type, or by phase of the moon. But it isn't possible > to have a set of elements without some order (at least on the sorts of > machines that Ada was intended to program). > >> So the even the statement "one cannot implement a set (with or without >> iteration) without providing an order over the elements" is plainly >> wrong. > > A linked list sure;y provides an order for the elements. Why you insist on > that order coming from the outside is beyond me. I hope my arguments from above make that clear. There is a lot of confusion going on here, what "ordered set" means: Not anything that occurs in a certain order at a given instance is ordered. Next time I put the same elements in the linked list, they are there in a different order: That is not what I understand would be an ordered container / set / data type. Esp. if you refer everything back to DKs original statement: "One cannot iterate over relational tables, because they are unordered". Since your interpretation says that implicitely an "order" (in your sense of the word) exists anyway, one can iterate over relational tables -- but that cannot have been what DK meant. > Even as hashed set doesn't > meet your requirements for "order", which is completely ridiculous. Completely ridiculous? Is that name calling now? I mean, I've been probably the only one even trying to achieve some amount of precision in this discussion. > >> (And no: The linked list doesn't define an order on all possible >> elements of the set.) > > An who cares about that? See the definition of the data type "ordered set". > Any particular set of elements has an order. I > don't much care if a different set object has a different order on the same > elements. It's irrelevant. "An order" is not the same as "a defined order" > or "the same order for any pair of elements with the same value". An order in your definition just means: I can iterate over the components or elements. In my opinion that is not what the discussion was about (and more proof how skillfull DK got everyone confused). > Indeed, any ordering between the values of the elements is completely > unrelated to the abstract set properties. Any operations that depend on such > an order are not set operations at all. > In any case, this is an Ada forum, and abstractions that you cannot describe > in Ada are simply not relevant (certainly not as the basis of containers). I beg to differ. Ada is not a specification language. DK has been bringing up the issue of "you cannot state the contract under this and that circumstances". There are abstractions (and iterating over sets is one of them) where you can indeed not state the contract in Ada (but in any functional specification notation like VDMSL or Z), but which you can implement in Ada. Without the help of the "outside agency" of a formal specification language one can spent eons discussing (a) wether the contract can be stated / makes sense and (b) can be implemented. > Any Ada implementation will have some implied ordering between the elements > in the set. Who cares about implementation? DKs arguments were about contracts and interfaces mostly. Exactly since we're in an Ada news group, shouldn't we separate them -- even in discussion? > My contention always has been that "sets" are an irrelevant abstraction from > a programming perspective. I disagree. If I just have a bag of thingies I need to process, I can use a list or a set. Sets are sometimes nearer to the original intention (no implied order, random access). > They're too inefficient to use for any purpose. The set operations might be. Personally I see a set data type as a container with an unspecified order of iteration and for which I don't have to provide a key. > What Ada.Containers calls a set is really a map where the keys are included > as part of the elements. That is implementation again. If it works as a set (interface) it is a set. > Yes, they have some set operations because some people thought if > they were called sets they should have those operations. I would > have preferred choosing a more sane name, but whatever. > And I would hope that I was done reading this bulls***, but I'm sure I'm > not... Sorry. I'll stop. No sense in annoying people. But I'm a bit pained that you characterize my "contribution" as BS, whereas you tolerate DKs prevarications pretty well. Never mind. Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-03 8:36 ` Markus E Leypold @ 2007-05-03 23:16 ` Randy Brukardt 2007-05-04 0:15 ` Markus E Leypold 0 siblings, 1 reply; 84+ messages in thread From: Randy Brukardt @ 2007-05-03 23:16 UTC (permalink / raw) "Markus E Leypold" <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> wrote in message news:ijwszq2tiq.fsf@hod.lan.m-e-leypold.de... ... > > I actually agree with DK, using his definitions. The problem is that no such > > set could ever be constructed (even on a piece of paper, the elements have > > an order). So the fact is completely irrelevant: there is no such thing as > > an unordered set. > > I repeat: There is a bit of confusion on 3 different things: > > (a) the way we write down sets (notation) > (b) orders (binary relations with certain properties) > (c) orderable sets, i.e. sets for which an order can be defined. Probably. But I was *very* clear, I was using DK's definitions. Whether they match some mathematical definition I don't know. You're arguing from some abstract mathematical definition and assuming everyone agrees with it. That doesn't wash. (Your definition is consistent, and fine, its just different than the one I was using. Thus it is hard to not talk past each other.) ... ... > > Of course you can if you assume primitives that effectively give you an > > order. > > No. Have you read the functional spec I wrote? I just use set > operations and a suitable cursor abstraction. Of course the choice of > the next element is not deterministic in the specification but that is > as it should be: It indicates that the implementation has a certain > degree of freedom here. I didn't recall it, but I think it actually proves my point. You've just moved the magic into a "cursor" abstraction and a "Next" abstraction - which shows far more implementation than the "foreach" iterator abstraction I was thinking of. (There's no good reason for a set to have a cursor abstraction, after all.) And "Next" gives you an order, even if that order is undefined. ... > > And I would hope that I was done reading this bulls***, but I'm sure I'm > > not... > > Sorry. I'll stop. No sense in annoying people. But I'm a bit pained > that you characterize my "contribution" as BS, whereas you tolerate > DKs prevarications pretty well. Never mind. Sorry, my comment was uncalled for. And it wasn't really directed at you but more at everyone who's kept this thread going for what seems like months. (And I'm guilty of that, too. I probably ought to get a newsreader with thread kill...) Randy. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-03 23:16 ` Randy Brukardt @ 2007-05-04 0:15 ` Markus E Leypold 0 siblings, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-05-04 0:15 UTC (permalink / raw) "Randy Brukardt" <randy@rrsoftware.com> writes: > "Markus E Leypold" > <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de> wrote in > message news:ijwszq2tiq.fsf@hod.lan.m-e-leypold.de... > ... >> > I actually agree with DK, using his definitions. The problem is that no > such >> > set could ever be constructed (even on a piece of paper, the elements > have >> > an order). So the fact is completely irrelevant: there is no such thing > as >> > an unordered set. >> >> I repeat: There is a bit of confusion on 3 different things: >> >> (a) the way we write down sets (notation) >> (b) orders (binary relations with certain properties) >> (c) orderable sets, i.e. sets for which an order can be defined. > > Probably. But I was *very* clear, I was using DK's definitions. Whether they > match some mathematical definition I don't know. You're arguing from some > abstract mathematical definition and assuming everyone agrees with it. No really. Calling something an ordered set because one can write down the elements in some order "doesn't wash" IMO. > That doesn't wash. (Your definition is consistent, and fine, its > just different than the one I was using. Thus it is hard to not talk > past each other.) Quite. Actually I proposed 2 definitions, one mathematical, the other, very similar, like what "usually" is used as an ordered container in programming (or in textbooks about abstract data types). I put "usually" in '"' because I see that people probably have different experiences. Every other definition (especially those that don't start with "A ... is a thingy with ..." I still see with distrust. > ... > ... >> > Of course you can if you assume primitives that effectively give you an >> > order. >> >> No. Have you read the functional spec I wrote? I just use set >> operations and a suitable cursor abstraction. Of course the choice of >> the next element is not deterministic in the specification but that is >> as it should be: It indicates that the implementation has a certain >> degree of freedom here. > I didn't recall it, but I think it actually proves my point. You've just > moved the magic into a "cursor" abstraction and a "Next" abstraction - which > shows far more implementation than the "foreach" iterator abstraction I was > thinking of. One can define a foreach operator which applies a given operation to each element in quite a similar way. I did it with a cursor, because (a) that would be the way iteration would be implemented in an imperative language and (b) the discussion started out with iteration. My cursor abstraction doesn't show much implementation (actually it cannot be implemented very efficiently in this form because it has to "freeze" the set state state into the cursor when it is created with first) -- what I wrote just describes what a cursor does, specifically, selecting the "next element", without recurring to some kind of order defined on the set or some kind of internal adresses. And that is the point I wanted to make: a specific order of the elements might emerge during iteration, but one doesn't need an order to define (the contract of) an iteration on a set without any structure (addresses, order) otherwise. > (There's no good reason for a set to have a cursor abstraction, > after all.) There is a good reason: if you want to iterate over the elements in a loop, the cursor takes the role of the loop variable, i.e. catches the state of the iteration (or call that iterator if you like). Foreach (as I understand you) would be more like a composition operator or a second order function: It would take a operation and a set and create an operation from them which is effectively the application of the operation to every element of the set. Since there are no second order functions in Ada, that would have to be implemented with a generic function and using a downward closure or some trick like this. Whatever -- therefore my preference to express the same thing with an iterator/cursor. It seemed more natural for a procedural language like Ada. > And "Next" gives you an order, even if that order is undefined. I get an undefined order? :-/ So I'll give you some money, even if it is not existent. :-) I think we would have to discuss about the meaning of order, to get to the ground of this, but better not here :-) and better not now: After all I never had problems with iterating over sets before, so why should I suddenly acquire the need to discuss them -- and I gather you have better things to do, too. > ... >> > And I would hope that I was done reading this bulls***, but I'm sure I'm >> > not... >> >> Sorry. I'll stop. No sense in annoying people. But I'm a bit pained >> that you characterize my "contribution" as BS, whereas you tolerate >> DKs prevarications pretty well. Never mind. > > Sorry, my comment was uncalled for. And it wasn't really directed at you but > more at everyone who's kept this thread going for what seems like months. > (And I'm guilty of that, too. I probably ought to get a newsreader with > thread kill...) I've now given, what I hope is the last contribution coming from me in this thread, only because I think that this is one of the rare opportunities to make my point understood and because I argue it is related to c.l.a. (i.e. I'm talking about specfying an abstract data structure formally). I admit, I'm guilty, too: My conflict is with DK, not with you -- and there is no sense in leading a proxy war. Thanks for the opportunity to get my arguments straight once before I stop and a good day to you :-). Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-01 17:16 ` Dmitry A. Kazakov 2007-05-01 19:14 ` Randy Brukardt @ 2007-05-01 21:41 ` Georg Bauhaus 2007-05-02 6:57 ` Ray Blaak ` (2 more replies) 1 sibling, 3 replies; 84+ messages in thread From: Georg Bauhaus @ 2007-05-01 21:41 UTC (permalink / raw) On Tue, 2007-05-01 at 19:16 +0200, Dmitry A. Kazakov wrote: > Apart from obvious uselessness of contracts referencing to the memory > layout, I didn't say that. > the above is self-contradictory. Memory layout defines an order. It > also is a part of the contract. Memory is not abstract, addresses aren't abstract, but what I have described as a formal model is abstract. > Hence the interface is ordered. The abstraction of the implementation implies the existence of a possible internal private ordering. The order can be completely controlled by an implementation and it won't be "reachable" through the public Set interface. Randy has explained much more about possible internal orderings. > > -- Proof. Foreach calls Add_One exactly once for each node > > -- in s. Add_One unconditionally increments Count_Var by 1. > > -- No other operation changes the value of Count_Var. > > -- Hence, Count_Var (initially zero) is incremented by 1 for > > -- each node in s, so Foreach counts the elements of s. ∎ > > So the precondition of Add_One is true? The proof mentions that Count_Var is initially zero and that it is only changed by Add_One. Together with the fact that these are (1) a local variable and (2) a local procedure closely tied this should imply that pre: Count_Var = 0. > 2. because pred (Add_One) = true, that also includes Count_Val = N + 1. This is not a possible interpretation of the program as given (because Count_Var := 0 immediately before Foreach is called), but you are right that the precondition is not explicitly stated. > > As you can see, there is some order again but I don't have to know > > the order. (Finding a first book (and then the next book) is the > > job of the librarian, not mine.) > > Librarian is the interface. If it finds first book then that is a publicly > ordered set = you _can_ know the order without breaking the abstraction. ? The first book might be determined by whatever order the librarian thinks he should choose this time. Nothing I could determine beforehand. The order(s), if any, isn't/aren't publicly known. > >>>> To be able to pick a random member <=> > >>>> to have an order. > >>> > >>> Can you determine whether one of your sets is empty? > >> > >> Sure. I can compare an empty set with the given set. This does not require > >> picking elements. > > > > Uhm, not require the client to pick or the implementation to pick? > > When two sets A and B are equal iff the same elements > > belong to both A and B, won't you need at least references to the > > elements for "=" to be called for the elements? > > No. You have to show that whatever element you took (no matter how) it is > either in both sets or else in neither: > > forall x in S, x in Q > > This does not force you to present any method of getting elements from any > of the sets. What's the contract of "in"? ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-01 21:41 ` Georg Bauhaus @ 2007-05-02 6:57 ` Ray Blaak 2007-05-02 8:22 ` Markus E Leypold 2007-05-02 8:07 ` Markus E Leypold 2007-05-02 10:29 ` Dmitry A. Kazakov 2 siblings, 1 reply; 84+ messages in thread From: Ray Blaak @ 2007-05-02 6:57 UTC (permalink / raw) Georg Bauhaus <bauhaus@futureapps.de> writes: > > > As you can see, there is some order again but I don't have to know > > > the order. (Finding a first book (and then the next book) is the > > > job of the librarian, not mine.) > > > > Librarian is the interface. If it finds first book then that is a publicly > > ordered set = you _can_ know the order without breaking the abstraction. > > ? > The first book might be determined by whatever order the librarian > thinks he should choose this time. Nothing I could determine beforehand. > The order(s), if any, isn't/aren't publicly known. Change it to: As you can see, there is some order again but I don't have to know the order. (Finding any book (and then another arbitrary book from the remainder) is the job of the librarian, not mine.) And that should be precise enough for everyone here. There is no first book as such in the set. There is only the first one that was given to you, which is not knowable in advance. -- Cheers, The Rhythm is around me, The Rhythm has control. Ray Blaak The Rhythm is inside me, rAYblaaK@STRIPCAPStelus.net The Rhythm has my soul. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-02 6:57 ` Ray Blaak @ 2007-05-02 8:22 ` Markus E Leypold 0 siblings, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-05-02 8:22 UTC (permalink / raw) Ray Blaak <rAYblaaK@STRIPCAPStelus.net> writes: > Georg Bauhaus <bauhaus@futureapps.de> writes: >> > > As you can see, there is some order again but I don't have to know >> > > the order. (Finding a first book (and then the next book) is the >> > > job of the librarian, not mine.) >> > >> > Librarian is the interface. If it finds first book then that is a publicly >> > ordered set = you _can_ know the order without breaking the abstraction. >> >> ? >> The first book might be determined by whatever order the librarian >> thinks he should choose this time. Nothing I could determine beforehand. >> The order(s), if any, isn't/aren't publicly known. > > Change it to: > > As you can see, there is some order again but I don't have to know the > order. (Finding any book (and then another arbitrary book from the remainder) > is the job of the librarian, not mine.) > > And that should be precise enough for everyone here. > > There is no first book as such in the set. There is only the first one that > was given to you, which is not knowable in advance. There is considerable confusion about what "order" means here. An order is a binary relation with certain properties defined on the set of all elements (the base set). The sets we're talking about are subsets of that set of all elements. Talking about the data type 'ordered set' means, I have to specify one constant order on the base set before instantiating or implementing the ordered set type. The fact that some ad-hoc ordering of a given subset occurs during iteration does not mean that the data type suddenly becomes ordered: This is just an artifact of sequential data processing in languages the specifiy operations as occuring sequentially in time. My impression is (from DKs axiom of choice argument and DKs uncoutable set example) that he seems to argue that there are unorderable sets in mathematics (sets for which no order could be provided), but this has no bearing on iteration (see the real numbers: can be ordered, but cannot be iterated over). Even worse: All that has no bearing on his original statement "one cannot iterate over relational tables" (those a finite) and his second implied statement that one cannot iterate over sets (one can, but obviously not over all kind of sets like algebraically expressed subsets of real numbers, but that has nothing to do with order, only with countability). I'm quite sure, DKs problem cannot be written down formally since it doesn't even exists, except in the twilight between free associations, hand waving arguments and exchanged all and existence quantors (see the misunderstandings about order). It is much more difficult to argue against arguments and misconceptions that have not been expressed exactly (because the battle ground tends to shift) than any other false statement. Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-01 21:41 ` Georg Bauhaus 2007-05-02 6:57 ` Ray Blaak @ 2007-05-02 8:07 ` Markus E Leypold 2007-05-02 10:29 ` Dmitry A. Kazakov 2 siblings, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-05-02 8:07 UTC (permalink / raw) Georg Bauhaus <bauhaus@futureapps.de> writes: > On Tue, 2007-05-01 at 19:16 +0200, Dmitry A. Kazakov wrote: > >> Apart from obvious uselessness of contracts referencing to the memory >> layout, > > I didn't say that. > >> the above is self-contradictory. Memory layout defines an order. It >> also is a part of the contract. > > Memory is not abstract, addresses aren't abstract, but what I > have described as a formal model is abstract. > >> Hence the interface is ordered. > > The abstraction of the implementation implies the existence > of a possible internal private ordering. Not even that. Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-01 21:41 ` Georg Bauhaus 2007-05-02 6:57 ` Ray Blaak 2007-05-02 8:07 ` Markus E Leypold @ 2007-05-02 10:29 ` Dmitry A. Kazakov 2007-05-02 11:48 ` Georg Bauhaus 2 siblings, 1 reply; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-05-02 10:29 UTC (permalink / raw) On Tue, 01 May 2007 23:41:31 +0200, Georg Bauhaus wrote: > On Tue, 2007-05-01 at 19:16 +0200, Dmitry A. Kazakov wrote: > >> Apart from obvious uselessness of contracts referencing to the memory >> layout, > > I didn't say that. But I did! (:-)) >> the above is self-contradictory. Memory layout defines an order. It >> also is a part of the contract. > > Memory is not abstract, addresses aren't abstract, In what sense? [ I doubt that you were able to bind objects of a higher level language to "non-abstract memory" in a more or less formal way. It is yet another discussion, we probably should not go into. The states of the memory are associated with some computational states and those with some objects "having" some values. It is a tick Napoleon pastry of abstractions layered over abstractions which you would not be able to flatten. As a practical example consider for I in ... loop -- what is I'Address here? can you specify the transistors I has? ] > The abstraction of the implementation implies the existence > of a possible internal private ordering. No, that is of course wrong. An abstraction of unordered set does not imply anything beyond itself. >>> -- Proof. Foreach calls Add_One exactly once for each node >>> -- in s. Add_One unconditionally increments Count_Var by 1. >>> -- No other operation changes the value of Count_Var. >>> -- Hence, Count_Var (initially zero) is incremented by 1 for >>> -- each node in s, so Foreach counts the elements of s. ∎ >> >> So the precondition of Add_One is true? > > The proof mentions that Count_Var is initially zero and that > it is only changed by Add_One. Together with the fact that these > are (1) a local variable and (2) a local procedure > closely tied this should imply that pre: Count_Var = 0. So, the precondition is not constant true, it is Count_Var = 0? Then either 1. N = 1 or 2. The program is incorrect, because for any N > 1 your precondition gets violated on the second call to Add_One. Here you are. You cannot specify the precondition of Add_One without referring to the iteration state. You are caught in a circle of tautologies. >>> As you can see, there is some order again but I don't have to know >>> the order. (Finding a first book (and then the next book) is the >>> job of the librarian, not mine.) >> >> Librarian is the interface. If it finds first book then that is a publicly >> ordered set = you _can_ know the order without breaking the abstraction. > > ? > The first book might be determined by whatever order the librarian > thinks he should choose this time. No, first = [whatever] order. It is same. > Nothing I could determine beforehand. "Beforehand" means what? I hope it does not that you present one set while dealing with another. Ordering is determined by sole existence of the librarian who can give you a [first] book and continue to do so. > The order(s), if any, isn't/aren't publicly known. It is, if you don't cheat. The procedure was described by me in other post. >>>>>> To be able to pick a random member <=> >>>>>> to have an order. >>>>> >>>>> Can you determine whether one of your sets is empty? >>>> >>>> Sure. I can compare an empty set with the given set. This does not require >>>> picking elements. >>> >>> Uhm, not require the client to pick or the implementation to pick? >>> When two sets A and B are equal iff the same elements >>> belong to both A and B, won't you need at least references to the >>> elements for "=" to be called for the elements? >> >> No. You have to show that whatever element you took (no matter how) it is >> either in both sets or else in neither: >> >> forall x in S, x in Q >> >> This does not force you to present any method of getting elements from any >> of the sets. > > What's the contract of "in"? One of the set theory. You choose the language and a set of axioms, and likely "in" will be somewhere there. So "in" is in a different position than ordering. In ZF ordered pairs are not fundamental, they are constructed. So we could talk about the contracts of on "ZF hardware." Of course it depends on the hardware. Nobody would construct, say, integers as they are constructed in ZF, because there is the ALU, which we could use instead. So "+" becomes per magic. Same is with foreach, you could have a hardware (axioms) for it. In that case it would have no contract. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-02 10:29 ` Dmitry A. Kazakov @ 2007-05-02 11:48 ` Georg Bauhaus 2007-05-02 11:50 ` Georg Bauhaus 2007-05-02 13:12 ` Dmitry A. Kazakov 0 siblings, 2 replies; 84+ messages in thread From: Georg Bauhaus @ 2007-05-02 11:48 UTC (permalink / raw) On Wed, 2007-05-02 at 12:29 +0200, Dmitry A. Kazakov wrote: > > Memory is not abstract, addresses aren't abstract, > > In what sense? When you write a Set implementation for a PC, you can specifying addresses and refer to addresses in a consistent way. > for I in ... loop > -- what is I'Address here? irrelevant without computational model. (I didn't say that the mentioned abstract addressable node is good for everything. But even so, it should not be too difficult to come up with an AS-IF model of how I "work"; otherwise, Ada would have an insurmountable teaching problem, besides other exegetic trouble.) > can you specify the transistors I has? ] no need. > > The abstraction of the implementation implies the existence > > of a possible internal private ordering. > > No, that is of course wrong. An abstraction of unordered set does not imply > anything beyond itself. I didn't say anything about unordered sets here. I have given a description of an implementation model. > > The proof mentions that Count_Var is initially zero and that > > it is only changed by Add_One. Together with the fact that these > > are (1) a local variable and (2) a local procedure > > closely tied this should imply that pre: Count_Var = 0. > > So, the precondition is not constant true, it is Count_Var = 0? Then either > > 1. N = 1 > > or > > 2. The program is incorrect, The program is correct; the assumption that Count_Var = 0 is false and not the precondition of Add_One at each time. My fault being sloppy. ("Count_Var is initially zero and ... is only changed by Add_One".) > Here you are. You cannot specify the precondition of Add_One without > referring to the iteration state. You are caught in a circle of > tautologies. Ok, Ok. There is a reason I didn't specify that as a precondition for Add_One. Add_One adds 1 to whatever initial value Count_Var has. It has the value 0 before the defined procedure Foreach starts operating using Add_One, as described. So there is a well defined operation going on and I can argue about this operation using the formally defined abstraction "Iterator". > No, first = [whatever] order. It is same. How is "whatever order" defined, exactly, and how can I say whatever first book will come given a library? > > Nothing I could determine beforehand. > > "Beforehand" means what? It means that it is impossible to predict an order because nothing is known about any order by any client. > Ordering is determined by sole existence of the > librarian who can give you a [first] book and continue to do so. That is, ordering is an outcome of the librarians operation, not of the books. > >> No. You have to show that whatever element you took (no matter how) it is > >> either in both sets or else in neither: > >> > >> forall x in S, x in Q > >> > >> This does not force you to present any method of getting elements from any > >> of the sets. > > > > What's the contract of "in"? > > One of the set theory. OK > Of course it depends on the hardware. OK. Glad to hear someone recognizes the inversion that mathematics brings in. Normative ontology at its best, though :-) ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-02 11:48 ` Georg Bauhaus @ 2007-05-02 11:50 ` Georg Bauhaus 2007-05-02 13:12 ` Dmitry A. Kazakov 1 sibling, 0 replies; 84+ messages in thread From: Georg Bauhaus @ 2007-05-02 11:50 UTC (permalink / raw) On Wed, 2007-05-02 at 13:48 +0200, Georg Bauhaus wrote: > But even so, it should not be too difficult to come up with an > AS-IF model of how I "work"; the loop variable I "works" > otherwise, Ada would have an > insurmountable teaching problem, besides other exegetic trouble.) ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-02 11:48 ` Georg Bauhaus 2007-05-02 11:50 ` Georg Bauhaus @ 2007-05-02 13:12 ` Dmitry A. Kazakov 2007-05-02 14:21 ` Markus E Leypold 2007-05-03 18:27 ` Georg Bauhaus 1 sibling, 2 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-05-02 13:12 UTC (permalink / raw) On Wed, 02 May 2007 13:48:26 +0200, Georg Bauhaus wrote: > On Wed, 2007-05-02 at 12:29 +0200, Dmitry A. Kazakov wrote: > >>> Memory is not abstract, addresses aren't abstract, >> >> In what sense? > > When you write a Set implementation for a PC, you can specifying > addresses and refer to addresses in a consistent way. But I am not required to do so. BTW 1, it is a quite common programming pattern to share some predefined states of the container, usually empty ones, but not only. An implementation of a container of integers could have a reserved representation for contiguous ranges of integers. For these it would keep only From and To. Now, let you have a container holding 1, 2, 3, can you point me the address of 2 there? Another typical pattern is some f applied to the actually kept values, so "()" actually is a composition f o "()". So what is in the container? BTW 2, it is sort of surprising to have such a discussion in c.l.a., for Ada was one of the first languages introducing a clear distinction between interface and implementation. >> for I in ... loop >> -- what is I'Address here? > > irrelevant without computational model. (I didn't say that the > mentioned abstract addressable node is good for everything. > But even so, it should not be too difficult to come up with an > AS-IF model of how I "work"; otherwise, Ada would have an > insurmountable teaching problem, besides other exegetic trouble.) Huh, argumentation to Turing-completeness is a subject of Godwin's Law... >>> The proof mentions that Count_Var is initially zero and that >>> it is only changed by Add_One. Together with the fact that these >>> are (1) a local variable and (2) a local procedure >>> closely tied this should imply that pre: Count_Var = 0. >> >> So, the precondition is not constant true, it is Count_Var = 0? Then either >> >> 1. N = 1 >> >> or >> >> 2. The program is incorrect, > > The program is correct; the assumption that Count_Var = 0 is > false and not the precondition of Add_One at each time. My fault > being sloppy. > ("Count_Var is initially zero and ... is only changed > by Add_One".) That still does not describe the precondition of. In particular, where it follows that counts S and not something else? S have to appear there. > So there is a well defined > operation going on It might be a well-defined operation, but its outcome is not. >> No, first = [whatever] order. It is same. > > How is "whatever order" defined, exactly, and how can I say whatever > first book will come given a library? Merely by saying/writing "first." That defines a book. >> Ordering is determined by sole existence of the >> librarian who can give you a [first] book and continue to do so. > > That is, ordering is an outcome of the librarians operation, > not of the books. Come on, all orderings are ordered but some orderings are more ordered than others? (:-)) _WHAT_ is the difference? Let you asked somebody to bring you books in their "proper" order. How can you determine if he does not cheat, or just mistakenly used the issue date rather than the birth day of the author written in Roman numerals and ordered according to Unicode positions? -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-02 13:12 ` Dmitry A. Kazakov @ 2007-05-02 14:21 ` Markus E Leypold 2007-05-03 18:27 ` Georg Bauhaus 1 sibling, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-05-02 14:21 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Wed, 02 May 2007 13:48:26 +0200, Georg Bauhaus wrote: > >> On Wed, 2007-05-02 at 12:29 +0200, Dmitry A. Kazakov wrote: >> >>>> Memory is not abstract, addresses aren't abstract, >>> >>> In what sense? >> >> When you write a Set implementation for a PC, you can specifying >> addresses and refer to addresses in a consistent way. > > But I am not required to do so. > > BTW 1, it is a quite common programming pattern to share some predefined > states of the container, usually empty ones, but not only. An > implementation of a container of integers could have a reserved > representation for contiguous ranges of integers. For these it would keep > only From and To. Now, let you have a container holding 1, 2, 3, can you > point me the address of 2 there? You're mixing up sufficient and necessary conditions. But never mind: your argument is so jumbled anyway -- why bother with logic :-(. > Another typical pattern is some f applied to the actually kept values, so > "()" actually is a composition f o "()". So what is in the container? > > BTW 2, it is sort of surprising to have such a discussion in c.l.a., for > Ada was one of the first languages introducing a clear distinction between > interface and implementation. Which you have been ignoring all along. The set implementation might use some natural order on the _representation_ of the items, but need not expose it. What one sees (interface) is a set. The order would only be used internally (but one doesn't need even that). >>> for I in ... loop >>> -- what is I'Address here? >> >> irrelevant without computational model. (I didn't say that the >> mentioned abstract addressable node is good for everything. >> But even so, it should not be too difficult to come up with an >> AS-IF model of how I "work"; otherwise, Ada would have an >> insurmountable teaching problem, besides other exegetic trouble.) > > Huh, argumentation to Turing-completeness is a subject of Godwin's Law... Look, who's speaking ... >>>> The proof mentions that Count_Var is initially zero and that >>>> it is only changed by Add_One. Together with the fact that these >>>> are (1) a local variable and (2) a local procedure >>>> closely tied this should imply that pre: Count_Var = 0. >>> >>> So, the precondition is not constant true, it is Count_Var = 0? Then either >>> >>> 1. N = 1 >>> >>> or >>> >>> 2. The program is incorrect, >> >> The program is correct; the assumption that Count_Var = 0 is >> false and not the precondition of Add_One at each time. My fault >> being sloppy. >> ("Count_Var is initially zero and ... is only changed >> by Add_One".) > > That still does not describe the precondition of. In particular, where it > follows that counts S and not something else? S have to appear there. I have not read GBs specification, but just try to understand mine. There you see explicitely which set you're iterating over. And I did not have to use any "order" to specify iteration over a set. > >> So there is a well defined >> operation going on > > It might be a well-defined operation, but its outcome is not. The outcome of a well defined operation (I take that as being well sepcified) does not have to be deterministic. > >>> No, first = [whatever] order. It is same. >> >> How is "whatever order" defined, exactly, and how can I say whatever >> first book will come given a library? > > Merely by saying/writing "first." That defines a book. > >>> Ordering is determined by sole existence of the >>> librarian who can give you a [first] book and continue to do so. >> >> That is, ordering is an outcome of the librarians operation, >> not of the books. > Come on, all orderings are ordered but some orderings are more ordered than > others? (:-)) _WHAT_ is the difference? More likely: What is the meaning of your sentence? > Let you asked somebody to bring > you books in their "proper" order. Other topic. What does "proper" mean here? > How can you determine if he does not > cheat, or just mistakenly used the issue date rather than the birth day of > the author written in Roman numerals and ordered according to Unicode > positions? So? I probably asked to get all those books -- on after the other. I get them. Wether "he" sorts them according to a predefined order or not -- who cares? Do I _have_ to determine wether he cheats? No: Every actual sequence of delivery suffices the requirement. And that is the point you refuse to see. And by the way: Ignoring what I say doesn't make you right. It makes it rather seem probable that you stop "discussing" the moment you're asked to put your cards upon the table and own up to your claims. Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-02 13:12 ` Dmitry A. Kazakov 2007-05-02 14:21 ` Markus E Leypold @ 2007-05-03 18:27 ` Georg Bauhaus 2007-05-03 19:07 ` Dmitry A. Kazakov 1 sibling, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-05-03 18:27 UTC (permalink / raw) On Wed, 2007-05-02 at 15:12 +0200, Dmitry A. Kazakov wrote: > On Wed, 02 May 2007 13:48:26 +0200, Georg Bauhaus wrote: > > > On Wed, 2007-05-02 at 12:29 +0200, Dmitry A. Kazakov wrote: > > > >>> Memory is not abstract, addresses aren't abstract, > >> > >> In what sense? > > > > When you write a Set implementation for a PC, you can specifying > > addresses and refer to addresses in a consistent way. > > But I am not required to do so. (I'll listen to Randy who said: "In any case, this is an Ada forum, and abstractions that you cannot describe in Ada are simply not relevant", and be brief, for one more time only.) > Now, let you have a container holding 1, 2, 3, can you > point me the address of 2 there? Yes. It is between 1 and 3, the docs say. Whether it actually is a computer address between 1'Address and 3'Address is a matter of implementation, but I can base arguments on 2 being between 1 and 3. But anyway, I don't have to at all because my Iterator is fine with any permutation of {1,2,3}. Let the implementation magic pick some first element. > BTW 2, it is sort of surprising to have such a discussion in c.l.a., for > Ada was one of the first languages introducing a clear distinction between > interface and implementation. Ada has interfaces, implementations, and a publicly available LRM which, in part, informs its readers about what to expect from behind some interfaces, in abstract terms I would say :-) > >> or > >> > >> 2. The program is incorrect, Precondition on local Count_Var together with Add_One before calling Foreach... I had given an argument about the correctness of the program WRT some model of how Foreach works. When a container doesn't provide an interface for expressing all preconditions, OK. Then the precondition refers to different things and it is up to the container to maintain invariants, no? > >> Ordering is determined by sole existence of the > >> librarian who can give you a [first] book and continue to do so. > > > > That is, ordering is an outcome of the librarians operation, > > not of the books. > > Come on, all orderings are ordered but some orderings are more ordered than > others? (:-)) _WHAT_ is the difference? Let you asked somebody to bring > you books in their "proper" order. How can you determine if he does not > cheat? I don't check an order that I don't know, can't know, and don't care about. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-03 18:27 ` Georg Bauhaus @ 2007-05-03 19:07 ` Dmitry A. Kazakov 2007-05-03 19:49 ` Markus E Leypold 0 siblings, 1 reply; 84+ messages in thread From: Dmitry A. Kazakov @ 2007-05-03 19:07 UTC (permalink / raw) On Thu, 03 May 2007 20:27:59 +0200, Georg Bauhaus wrote: > On Wed, 2007-05-02 at 15:12 +0200, Dmitry A. Kazakov wrote: >> On Wed, 02 May 2007 13:48:26 +0200, Georg Bauhaus wrote: >> >>> On Wed, 2007-05-02 at 12:29 +0200, Dmitry A. Kazakov wrote: >>> >>>>> Memory is not abstract, addresses aren't abstract, >>>> >>>> In what sense? >>> >>> When you write a Set implementation for a PC, you can specifying >>> addresses and refer to addresses in a consistent way. >> >> But I am not required to do so. > > (I'll listen to Randy who said: "In any case, this is an Ada forum, > and abstractions that you cannot describe in Ada are simply not > relevant", and be brief, for one more time only.) There exist legal Ada programs which don't refer to the type System.Address. (which statement is an exact equivalent to "I am not required to do so" [use addresses in Ada]) >> Now, let you have a container holding 1, 2, 3, can you >> point me the address of 2 there? > > Yes. It is between 1 and 3, the docs say. (Where RM says anything about 2'Address?) > Whether it actually is a > computer address between 1'Address and 3'Address is a matter of > implementation, Also it is not memory address. What is then, a postal address? > I had given an argument about the correctness of the program WRT > some model of how Foreach works. You didn't specified that "model." I am especially interested in the formal meaning of "once." -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-05-03 19:07 ` Dmitry A. Kazakov @ 2007-05-03 19:49 ` Markus E Leypold 0 siblings, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-05-03 19:49 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Thu, 03 May 2007 20:27:59 +0200, Georg Bauhaus wrote: > >> On Wed, 2007-05-02 at 15:12 +0200, Dmitry A. Kazakov wrote: >>> On Wed, 02 May 2007 13:48:26 +0200, Georg Bauhaus wrote: >>> >>>> On Wed, 2007-05-02 at 12:29 +0200, Dmitry A. Kazakov wrote: >>>> >>>>>> Memory is not abstract, addresses aren't abstract, >>>>> >>>>> In what sense? >>>> >>>> When you write a Set implementation for a PC, you can specifying >>>> addresses and refer to addresses in a consistent way. >>> >>> But I am not required to do so. >> >> (I'll listen to Randy who said: "In any case, this is an Ada forum, >> and abstractions that you cannot describe in Ada are simply not >> relevant", and be brief, for one more time only.) > > There exist legal Ada programs which don't refer to the type > System.Address. > > (which statement is an exact equivalent to "I am not required to do so" > [use addresses in Ada]) Considering you started with a "you can't ..." statement, "not required" won't do as an argument. - M ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-28 17:35 ` Dmitry A. Kazakov 2007-04-28 23:06 ` Georg Bauhaus @ 2007-04-29 16:26 ` Markus E Leypold 1 sibling, 0 replies; 84+ messages in thread From: Markus E Leypold @ 2007-04-29 16:26 UTC (permalink / raw) "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: > On Fri, 27 Apr 2007 13:43:58 +0200, Markus E Leypold wrote: > >> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: >> >>> On Thu, 26 Apr 2007 22:52:58 +0100, Simon Wright wrote: >>> >>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes: >>>> >>>>> You cannot iterate a relational table, because there is no order >>>>> defined on it. >>>> >>>> Why would that stop me iterating over all the rows? >>> >>> Because iterating presumes following an order. If there is no *any* order, >>> which one would you follow? >> >> None. Iteration gives the values in a certain sequence, > > "Sequence" is defined as an ordered [and countable] set. So what? Both, 1,2,3 aand 3,1,2 are possible sequences suitable for iterating over the set "all positive numbers below 4". One even needn't to get the same sequence on every iteration which somewhat disqualifies the idea that the set would have to be ordered so that I could iterate over it. Your implication was, that is impossible to "iterate" over the components/elements of structures/compounds which are not ordered. Admittedly the implementation is introducing an ad hoc order at the moment and for the moment the iteration takes place, but actually I don't care and a massively parallel machine might even choose to perform operations on single elements in parallel. But your point was that it is __impossible__ to iterate over such "unordered" structures, which is -- in my eyes -- patent nonsense. Every actual sequence of iteration would suffice and I think that the sentence "iterate over the set ..." could be well applied in this case under every useful meaning (and it can even be defined formally). But of course YMMV: People like me who do not think that every real programs are trivial, might not grasp your logic completely and not achieve your precision of definition. >>> It is clear that we could enumerate anything on >>> a real computer, but that would be same as Unchecked_Conversion, it would >>> break the abstraction. >> >> So I'm having an unchecked operation if I enumerate elements of a set >> (sets are unordered). How embarrasing. > > Yes, because that set is a representation [model] of some other [domain > space] set which could be fundamentally unordered and/or uncountable. As an Uncountable is another issue. You're ditching the original issue again (how familiar this has become to me ...). You said "one cannot iterate over realtional tables, because they are unordered". Realtional tables are not uncountable, so stick to the issue at hand, Dmitry. <snipped off topic "example"> > After interating reals we could proceed to complex numbers... Which has nothing at all to do with relational tables. I'd be really indebted to you, if you stuck to the topic you introduced (can one iterate over relational tables) and didn't give in to the brainstorm of completely unrelated fragments from mathematics and computer science that seems to afflict you every time one starts to discuss with you topics from computer science you yourself introduced. BTW: Your best way out of the corner into which you painted yourself again might be to define "relational tables" as tables with an uncountable number of tuples/rows -- in quite the style in which you defined "trivial program". Regards -- Markus ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-26 15:31 ` andrew.carroll 2007-04-26 16:07 ` Georg Bauhaus 2007-04-26 18:54 ` Dmitry A. Kazakov @ 2007-04-26 21:50 ` Simon Wright 2007-04-27 4:45 ` Jeffrey R. Carter 3 siblings, 0 replies; 84+ messages in thread From: Simon Wright @ 2007-04-26 21:50 UTC (permalink / raw) "andrew.carroll@okstate.edu" <andrew.carroll@okstate.edu> writes: > I think the Booch components may have something I'm looking for. > Even though this site http://www.adapower.net/booch/overview.html > says it would be better to use a "collection" (there's the word > again) than a linked list I think I could have used the generic > linked list for my purposes. I wish the site had given more > information as to what a "collection" is and where to find more > information about it. Then again, I didn't read the whole thing. That site's rather old (now http://booch95.sourceforge.net/) but those particular remarks are still valid. I say "Many people, faced with the BCs for the first time, choose Lists (Single or Double) as their standard Container. "This is probably not the best choice. Lists are complex entities which, I suppose, would be useful if you were implementing a list-processing engine like Lisp. "You'll be a lot better off using Collections!" and a few lines further up it says that the components available include Collections and Lists. I guess you were meant to read between the lines and infer that Collections => BC Collections. What I was trying to say was that many people think "I want to have lists of things, I'll use Lists" but that most of them would be better off using Collections ie BC.Containers.Collections because BC Lists are hairy. I have never personally found a need to use BC Lists. The choice of components and names was Grady Booch's, not mine! You could well have used the BCs (or one of the other libraries that people have pointed out), though your first choice as a student probably should be the Standard containers! (assuming Ada05). If nothing else, you'll find lots of documentation (RM & Rationale, to start with, and modern textbooks). ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-26 15:31 ` andrew.carroll ` (2 preceding siblings ...) 2007-04-26 21:50 ` Simon Wright @ 2007-04-27 4:45 ` Jeffrey R. Carter 2007-04-27 7:45 ` Martin Krischik 3 siblings, 1 reply; 84+ messages in thread From: Jeffrey R. Carter @ 2007-04-27 4:45 UTC (permalink / raw) andrew.carroll@okstate.edu wrote: > > I think the Booch components may have something I'm looking for. Even > though this site http://www.adapower.net/booch/overview.html says it > would be better to use a "collection" (there's the word again) than a > linked list I think I could have used the generic linked list for my > purposes. I wish the site had given more information as to what a > "collection" is and where to find more information about it. Then > again, I didn't read the whole thing. > > So what would be best to choose? It sounds as if you're using Ada 95, since otherwise I presume you would use Ada.Containers. In that case, there's information about a number of libraries at adapower.com. Personally, I like the PragmAda Reusable Components, but your tastes may differ. http://pragmada.home.mchsi.com/ -- Jeff Carter "I fart in your general direction." Monty Python & the Holy Grail 05 ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 4:45 ` Jeffrey R. Carter @ 2007-04-27 7:45 ` Martin Krischik 2007-04-27 22:54 ` Georg Bauhaus 0 siblings, 1 reply; 84+ messages in thread From: Martin Krischik @ 2007-04-27 7:45 UTC (permalink / raw) Jeffrey R. Carter schrieb: > It sounds as if you're using Ada 95, since otherwise I presume you would > use Ada.Containers. Ahmm - I actually prefer the interface of the booch components over Ada.Containers. I don't like the STL either. To low level for my taste. I foe once have no intention to move away from the booch components. Martin ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 7:45 ` Martin Krischik @ 2007-04-27 22:54 ` Georg Bauhaus 2007-04-30 20:13 ` Matthew Heaney 0 siblings, 1 reply; 84+ messages in thread From: Georg Bauhaus @ 2007-04-27 22:54 UTC (permalink / raw) On Fri, 2007-04-27 at 09:45 +0200, Martin Krischik wrote: > Jeffrey R. Carter schrieb: > > > It sounds as if you're using Ada 95, since otherwise I presume you would > > use Ada.Containers. > > Ahmm - I actually prefer the interface of the booch components over > Ada.Containers. I don't like the STL either. To low level for my taste. OTOH, Ada.Containers has been pushed from the STL towards the Booch Components, or so it could be said, I think. For example, a number of algorithms that are typically implemented using a generic function in C++ have been made a predefined part of the respective container packages. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-27 22:54 ` Georg Bauhaus @ 2007-04-30 20:13 ` Matthew Heaney 0 siblings, 0 replies; 84+ messages in thread From: Matthew Heaney @ 2007-04-30 20:13 UTC (permalink / raw) On Apr 27, 6:54 pm, Georg Bauhaus <bauh...@futureapps.de> wrote: > > OTOH, Ada.Containers has been pushed from the STL towards the Booch > Components, or so it could be said, I think. For example, a number > of algorithms that are typically implemented using a generic > function in C++ have been made a predefined part of the respective > container packages. Yes, some of the things that are included in the algorithms-part of the STL are included in the Ada05 container library, but that's mostly because the Ada05 container library doesn't have (except for the array sorting stuff) any dedicated algorithms. I included the algorithms that I thought were the most useful, based on my experience with the STL. It's not because Ada.Containers moved "towards the Booch Components." Martin K. claims that the Ada05 container library is too low level, but he didn't give any specific examples. I would be interested to know what difficulties he had. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2007-04-25 22:15 Generic Package andrew.carroll ` (3 preceding siblings ...) 2007-04-26 15:31 ` andrew.carroll @ 2007-04-26 20:48 ` andrew.carroll 4 siblings, 0 replies; 84+ messages in thread From: andrew.carroll @ 2007-04-26 20:48 UTC (permalink / raw) On Apr 25, 5:15 pm, "andrew.carr...@okstate.edu" <andrew.carr...@okstate.edu> wrote: > Is there a generic "collection" package in the libraries that come > with Ada? For instance if in my design I have an "is a" relationship > like table "is a" _collection_ of something then is there a generic > "collection" package that I could use? aparently my last message didn't get sent. I'll send this as a test and if it post before the other, then I'll send the other one again. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Generic Package @ 2003-12-02 23:15 Mr. J. 2003-12-03 9:31 ` Dmitry A. Kazakov 0 siblings, 1 reply; 84+ messages in thread From: Mr. J. @ 2003-12-02 23:15 UTC (permalink / raw) Hi, I have this code : ********************************************************************* generic type Language is array (Positive range<>) of Character; type States is array (Positive range <>) of Integer; package Automat_Producer is type StatesFunctions is array(Character,Integer) of Integer; procedure Init(Q0:Integer); procedure Change_State(C:Character); function Is_Final_State return Boolean; private Statesarr: Statesfunctions; Currentstate : Integer; FinalStates : States; end Automat_Producer; ********************************************************************* I have few Questions: How and when do I set the sizes of the generic types arrays? The compiler need to know the size of the FinalStates:States member, I will know it only during run-time, How do I do it ? I think I need somthing similiar to C++'s Constructor. 10x a lot, Janiv. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: Generic Package 2003-12-02 23:15 Mr. J. @ 2003-12-03 9:31 ` Dmitry A. Kazakov 0 siblings, 0 replies; 84+ messages in thread From: Dmitry A. Kazakov @ 2003-12-03 9:31 UTC (permalink / raw) On 2 Dec 2003 15:15:45 -0800, ratsonjaniv@hotmail.com (Mr. J.) wrote: >Hi, >I have this code : > >********************************************************************* >generic > type Language is array (Positive range<>) of Character; > type States is array (Positive range <>) of Integer; > > package Automat_Producer is > > type StatesFunctions is array(Character,Integer) of Integer; > > procedure Init(Q0:Integer); > procedure Change_State(C:Character); > function Is_Final_State return Boolean; > >private > > Statesarr: Statesfunctions; > Currentstate : Integer; > FinalStates : States; > >end Automat_Producer; >********************************************************************* > >I have few Questions: > >How and when do I set the sizes of the generic types arrays? Upon instantiation. >The compiler need to know the size of the FinalStates:States member, I >will know it only during run-time, How do I do it? >I think I need somthing similiar to C++'s Constructor. Not necessariliy. You have to constrain the variable States. There are many ways to do what you need. For example 1. you can pass the array bounds as the parameters: generic Number_Of_Final_States : Positive; type States is array (Positive range <>) of Integer; ... -- Other generic formal parameters package Automat_Producer is ... -- Public interface private FinalStates : States (1..Number_Of_Final_States); ... -- Other private things end Automat_Producer; So you could instantiate Automat_Producer with a desired number of states: package My_Producer is new Automat_Producer (Number_Of_Final_States => 10, ...); 2. you can pass the set of final states as a parameter: generic type States is array (Positive range <>) of Integer; FinalStates : States; ... -- Other generic formal parameters package Automat_Producer is ... -- Public interface private -- Do not need a list of final states it is a parameter now ... -- Other private things end Automat_Producer; 3. you could make the states an enumeration type with a domain set separated into final and non-final states: generic type State is (<>); First_Final_State : State; Last_Final_State : State; ... -- Other generic formal parameters package Automat_Producer is ... -- Public interface private -- Do not need a list of final states, a state is tested -- as if X in First_Final_State..Last_Final_State then -- ... -- Other private things end Automat_Producer; 4. you could provide a tester: generic type State is (<>); with function Is_Final (This : State) return Boolean; ... -- Other generic formal parameters package Automat_Producer is ... -- Public interface private -- Do not need a list of final states, a state is tested -- using Is_Final. ... -- Other private things end Automat_Producer; -- Regards, Dmitry Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 84+ messages in thread
* generic package @ 2003-12-02 23:13 Ratson Janiv 2003-12-03 17:39 ` Stephen Leake 0 siblings, 1 reply; 84+ messages in thread From: Ratson Janiv @ 2003-12-02 23:13 UTC (permalink / raw) Hi, I have this code : *************************************************************************** generic type Language is array (Positive range<>) of Character; type States is array (Positive range <>) of Integer; package Automat_Producer is type StatesFunctions is array(Character,Integer) of Integer; procedure Init(Q0:Integer); procedure Change_State(C:Character); function Is_Final_State return Boolean; private Statesarr: Statesfunctions; Currentstate : Integer; FinalStates : States; end Automat_Producer; **************************************************************************** **** I have few Questions: How and when do I set the sizes of the generic types arrays? The compiler need to know the size of the FinalStates:States member, I will know it only during run-time, How do I do it ? I think I need somthing similiar to C++'s Constructor. 10x a lot, Janiv. ^ permalink raw reply [flat|nested] 84+ messages in thread
* Re: generic package 2003-12-02 23:13 generic package Ratson Janiv @ 2003-12-03 17:39 ` Stephen Leake 0 siblings, 0 replies; 84+ messages in thread From: Stephen Leake @ 2003-12-03 17:39 UTC (permalink / raw) "Ratson Janiv" <janiv@013.net.il> writes: > generic > type Language is array (Positive range<>) of Character; > type States is array (Positive range <>) of Integer; > > package Automat_Producer is > > type StatesFunctions is array(Character,Integer) of Integer; > > procedure Init(Q0:Integer); > procedure Change_State(C:Character); > function Is_Final_State return Boolean; > > private > > Statesarr: Statesfunctions; > Currentstate : Integer; > FinalStates : States; > > end Automat_Producer; > > I have few Questions: > > How and when do I set the sizes of the generic types arrays? > The compiler need to know the size of the FinalStates:States member, I will > know it only during run-time, How do I do it ? The general answer to this question is to use a local declare block. Something like: procedure foo is size : Integer; begin get (Size); declare subtype Language_Range is Positive range 1 .. Size; type Language is array (language_range) of character; package Producer is new Automat_Producer (Language ...); begin ... end; end; -- -- Stephe ^ permalink raw reply [flat|nested] 84+ messages in thread
end of thread, other threads:[~2007-05-04 0:15 UTC | newest] Thread overview: 84+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2007-04-25 22:15 Generic Package andrew.carroll 2007-04-26 0:07 ` Jeffrey R. Carter 2007-04-26 7:46 ` Markus E Leypold 2007-04-26 6:02 ` Martin Krischik 2007-04-26 7:57 ` Dmitry A. Kazakov 2007-04-26 15:31 ` andrew.carroll 2007-04-26 16:07 ` Georg Bauhaus 2007-04-26 19:40 ` andrew.carroll 2007-04-26 20:01 ` Georg Bauhaus 2007-04-26 18:54 ` Dmitry A. Kazakov 2007-04-26 21:52 ` Simon Wright 2007-04-27 9:00 ` Dmitry A. Kazakov 2007-04-27 11:11 ` Georg Bauhaus 2007-04-27 12:06 ` Dmitry A. Kazakov 2007-04-27 12:52 ` Markus E Leypold 2007-04-27 14:10 ` Georg Bauhaus 2007-04-27 14:16 ` Dmitry A. Kazakov 2007-04-27 21:44 ` Georg Bauhaus 2007-04-28 7:38 ` Dmitry A. Kazakov 2007-04-28 17:50 ` Simon Wright 2007-04-28 21:04 ` Ray Blaak 2007-04-29 16:33 ` Markus E Leypold 2007-04-27 19:44 ` Simon Wright 2007-04-27 20:34 ` Dmitry A. Kazakov 2007-04-27 21:16 ` Simon Wright 2007-04-28 7:36 ` Dmitry A. Kazakov 2007-04-27 11:43 ` Markus E Leypold 2007-04-28 17:35 ` Dmitry A. Kazakov 2007-04-28 23:06 ` Georg Bauhaus 2007-04-29 8:19 ` Dmitry A. Kazakov 2007-04-29 15:10 ` (see below) 2007-04-29 17:48 ` Dmitry A. Kazakov 2007-04-29 22:36 ` (see below) 2007-04-30 6:58 ` Dmitry A. Kazakov 2007-04-30 9:59 ` Markus E Leypold 2007-04-30 10:01 ` Markus E Leypold 2007-04-30 10:36 ` Georg Bauhaus 2007-04-30 10:40 ` Georg Bauhaus 2007-04-30 12:14 ` Dmitry A. Kazakov 2007-04-30 14:57 ` (see below) 2007-04-30 10:30 ` Georg Bauhaus 2007-04-30 12:16 ` Dmitry A. Kazakov 2007-04-30 14:48 ` Georg Bauhaus 2007-04-30 16:29 ` Dmitry A. Kazakov 2007-04-30 17:24 ` Georg Bauhaus 2007-04-30 18:54 ` Dmitry A. Kazakov 2007-04-30 19:29 ` Simon Wright 2007-04-30 20:04 ` Dmitry A. Kazakov 2007-05-01 0:11 ` Markus E Leypold 2007-05-01 9:02 ` Georg Bauhaus 2007-05-01 10:19 ` Dmitry A. Kazakov 2007-05-01 13:42 ` Georg Bauhaus 2007-05-01 17:16 ` Dmitry A. Kazakov 2007-05-01 19:14 ` Randy Brukardt 2007-05-01 20:14 ` Dmitry A. Kazakov 2007-05-02 7:52 ` Markus E Leypold 2007-05-02 8:06 ` Markus E Leypold 2007-05-03 0:37 ` Randy Brukardt 2007-05-03 8:36 ` Markus E Leypold 2007-05-03 23:16 ` Randy Brukardt 2007-05-04 0:15 ` Markus E Leypold 2007-05-01 21:41 ` Georg Bauhaus 2007-05-02 6:57 ` Ray Blaak 2007-05-02 8:22 ` Markus E Leypold 2007-05-02 8:07 ` Markus E Leypold 2007-05-02 10:29 ` Dmitry A. Kazakov 2007-05-02 11:48 ` Georg Bauhaus 2007-05-02 11:50 ` Georg Bauhaus 2007-05-02 13:12 ` Dmitry A. Kazakov 2007-05-02 14:21 ` Markus E Leypold 2007-05-03 18:27 ` Georg Bauhaus 2007-05-03 19:07 ` Dmitry A. Kazakov 2007-05-03 19:49 ` Markus E Leypold 2007-04-29 16:26 ` Markus E Leypold 2007-04-26 21:50 ` Simon Wright 2007-04-27 4:45 ` Jeffrey R. Carter 2007-04-27 7:45 ` Martin Krischik 2007-04-27 22:54 ` Georg Bauhaus 2007-04-30 20:13 ` Matthew Heaney 2007-04-26 20:48 ` andrew.carroll -- strict thread matches above, loose matches on Subject: below -- 2003-12-02 23:15 Mr. J. 2003-12-03 9:31 ` Dmitry A. Kazakov 2003-12-02 23:13 generic package Ratson Janiv 2003-12-03 17:39 ` Stephen Leake
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox