Re: Generic Package

[Markus E Leypold <development-2006-8ecbb5cc8aREMOVETHIS@ANDTHATm-e-leypold.de>]

"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