generic package

generic package

[Ratson Janiv]

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.

Generic Package

[Mr. J.]

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.

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: generic package

[Stephen Leake]

"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

Generic Package

[andrew.carroll]

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?

Re: Generic Package

[Jeffrey R. Carter]

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

Re: Generic Package

[Martin Krischik]

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

Re: Generic Package

[Markus E Leypold]

"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

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[andrew.carroll]

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?

Re: Generic Package

[Georg Bauhaus]

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. :)

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[andrew.carroll]

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?

Re: Generic Package

[Georg Bauhaus]

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, ...);

Re: Generic Package

[andrew.carroll]

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.

Re: Generic Package

[Simon Wright]

"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).

Re: Generic Package

[Simon Wright]

"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?

Re: Generic Package

[Jeffrey R. Carter]

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

Re: Generic Package

[Martin Krischik]

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

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Georg Bauhaus]

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.

Re: Generic Package

[Markus E Leypold]

"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

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Markus E Leypold]

"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

Re: Generic Package

[Georg Bauhaus]

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.

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Simon Wright]

"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.

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Simon Wright]

"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.

Re: Generic Package

[Georg Bauhaus]

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.

Re: Generic Package

[Georg Bauhaus]

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.

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Simon Wright]

"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!

Re: Generic Package

[Ray Blaak]

"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.

Re: Generic Package

[Georg Bauhaus]

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) };

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[(see below)]

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

Re: Generic Package

[Markus E Leypold]

"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

Re: Generic Package

[Markus E Leypold]

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

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[(see below)]

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

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Markus E Leypold]

>>>> 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

Re: Generic Package

[Markus E Leypold]

"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

Re: Generic Package

[Georg Bauhaus]

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.

Re: Generic Package

[Georg Bauhaus]

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?

Re: Generic Package

[Georg Bauhaus]

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.

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Georg Bauhaus]

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.)

Re: Generic Package

[(see below)]

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

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Georg Bauhaus]

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.

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Simon Wright]

"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.

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Matthew Heaney]

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.

Re: Generic Package

[Markus E Leypold]

"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

Re: Generic Package

[Georg Bauhaus]

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?

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Georg Bauhaus]

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?

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Randy Brukardt]

"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.

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Georg Bauhaus]

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"?

Re: Generic Package

[Ray Blaak]

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.

Re: Generic Package

[Markus E Leypold]

"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

Re: Generic Package

[Markus E Leypold]

"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

Re: Generic Package

[Markus E Leypold]

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

Re: Generic Package

[Markus E Leypold]

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

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Georg Bauhaus]

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 :-)

Re: Generic Package

[Georg Bauhaus]

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.)

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Markus E Leypold]

"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

Re: Generic Package

[Randy Brukardt]

"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.

Re: Generic Package

[Markus E Leypold]

"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

Re: Generic Package

[Georg Bauhaus]

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.

Re: Generic Package

[Dmitry A. Kazakov]

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

Re: Generic Package

[Markus E Leypold]

"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

Re: Generic Package

[Randy Brukardt]

"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.

Re: Generic Package

[Markus E Leypold]

"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