From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,229ea0001655d6a2 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Newsgroups: comp.lang.ada Subject: Re: Generic Package References: <1177539306.952515.222940@s33g2000prh.googlegroups.com> <1177601484.444701.171560@r35g2000prh.googlegroups.com> <9eejm6rqip.fsf@hod.lan.m-e-leypold.de> <19qllkvm6ut42$.1iqo74vjgmsrv$.dlg@40tude.net> <1177801611.10171.32.camel@localhost.localdomain> <1woad6hn9idy2$.6otnwphc1o0h$.dlg@40tude.net> <1177929029.6111.34.camel@localhost> <1177944533.13970.17.camel@localhost> <2aq08qbvw0ym$.1rquampzo7o53.dlg@40tude.net> <1ieq3io2d6nnq$.13818v3y35gnr.dlg@40tude.net> From: Markus E Leypold Organization: N/A Date: Tue, 01 May 2007 02:11:53 +0200 Message-ID: User-Agent: Some cool user agent (SCUG) Cancel-Lock: sha1:u7TtI7DAlVUtiawoDa1Tzu6hU4E= MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii NNTP-Posting-Host: 88.72.227.73 X-Trace: news.arcor-ip.de 1177977824 88.72.227.73 (1 May 2007 02:03:44 +0200) X-Complaints-To: abuse@arcor-ip.de Path: g2news1.google.com!news4.google.com!feeder3.cambrium.nl!feeder5.cambrium.nl!feeder1.cambrium.nl!feed.tweaknews.nl!news2.euro.net!newsfeed.freenet.de!news.unit0.net!newsfeed.arcor-ip.de!news.arcor-ip.de!not-for-mail Xref: g2news1.google.com comp.lang.ada:15446 Date: 2007-05-01T02:11:53+02:00 List-Id: "Dmitry A. Kazakov" writes: > On Mon, 30 Apr 2007 20:29:22 +0100, Simon Wright wrote: > >> "Dmitry A. Kazakov" 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