Surprise in array concatenation

Surprise in array concatenation

[Gene]

Seldom am I surprised by Ada semantics, but today they got me.

type Int_List_Type is array(Integer range <>) of Integer;

procedure Main is

  function F(a : Int_List_Type) return Integer is
    i : Integer;
  begin
    if a'Length <= 1 then
      return a(1);
    else
      -- calculate i s.t. 1 <= i <= a'Last
      -- with some algorithm; details irrelevant
      ...
      return F(a(1..i - 1) & a(i + 1, a'Last));
    end if;
  end Calculate;

  a : Int_List(1..100);

begin
  -- yada yada; fill a with values
  Put(Calculate(F(a)));
end;

The gotcha is that when (and only when) i is determined to be zero, the
concatenation in the recursive call to F produces a starting index of 2
rather than 1.  Of course this causes the base case test to raise an
exception in the next recursive call.  This is in accordance with the
ALRM and GNAT implements it perfectly.

Yes I know how to recode this to use a'First instead of 1 as needed.

Nonetheless the rule seems silly:  When a leading zero-length array is
catenated to another array the result takes on the starting index of
the _second_ operand.  This doesn't make sense to me.  Why not use the
starting index of the zero-length array?

Gene

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On 31 Aug 2005 20:16:43 -0700, Gene wrote:

> Nonetheless the rule seems silly:  When a leading zero-length array is
> catenated to another array the result takes on the starting index of
> the _second_ operand.  This doesn't make sense to me.  Why not use the
> starting index of the zero-length array?

Because that might be ill-defined, I guess.

A more interesting question is why Empty'First does not raise any
exception. After all, there is no any lower bound of an empty index range.
Provided, that empty arrays are all same, of course. If not, then another
interesting question would appear: how to make an empty array with the
lower bound Integer'First?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Florian Weimer]

* Dmitry A. Kazakov:

> A more interesting question is why Empty'First does not raise any
> exception. After all, there is no any lower bound of an empty index range.
> Provided, that empty arrays are all same, of course. If not, then another
> interesting question would appear: how to make an empty array with the
> lower bound Integer'First?

You can't.  Even more problematic is the empty array whose index type
is an enumeration type with just one enumeration literal.

Re: Surprise in array concatenation

[Jean-Pierre Rosen]

Gene a �crit :
> Seldom am I surprised by Ada semantics, but today they got me.
> 
> type Int_List_Type is array(Integer range <>) of Integer;
> 
> procedure Main is
> 
>   function F(a : Int_List_Type) return Integer is
>     i : Integer;
>   begin
>     if a'Length <= 1 then
>       return a(1);
>     else
>       -- calculate i s.t. 1 <= i <= a'Last
>       -- with some algorithm; details irrelevant
>       ...
>       return F(a(1..i - 1) & a(i + 1, a'Last));
>     end if;
>   end Calculate;
> 
>   a : Int_List(1..100);
> 
> begin
>   -- yada yada; fill a with values
>   Put(Calculate(F(a)));
> end;
> 
> The gotcha is that when (and only when) i is determined to be zero, the
> concatenation in the recursive call to F produces a starting index of 2
> rather than 1.  Of course this causes the base case test to raise an
> exception in the next recursive call.  This is in accordance with the
> ALRM and GNAT implements it perfectly.
> 
> Yes I know how to recode this to use a'First instead of 1 as needed.
> 
> Nonetheless the rule seems silly:  When a leading zero-length array is
> catenated to another array the result takes on the starting index of
> the _second_ operand.  This doesn't make sense to me.  Why not use the
> starting index of the zero-length array?
> 
Because the lower bound of a null array needs not belong to the subtype 
used for indexing.

Note that you can force the lower bound by subtype conversion:
declare
    Result : constant string := F(a(1..i - 1) & a(i + 1, a'Last));
    subtype Force_Lower_To_1 is string (1 .. Result'length);
begin
    return Force_Lower_To_1 (Result);
end;

-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

> A more interesting question is why Empty'First does not raise any
> exception.

Because 'First does not denote an element?

> After all, there is no any lower bound of an empty index range.

? What's the bound of a range? (as opposed to a bounded array)

> Provided, that empty arrays are all same, of course. If not, then another
> interesting question would appear: how to make an empty array with the
> lower bound Integer'First?

Carrying the arguement further, how to reference an element
outside the machine's storage?

Re: Surprise in array concatenation

[Georg Bauhaus]

Florian Weimer wrote:

> Even more problematic is the empty array whose index type
> is an enumeration type with just one enumeration literal.

This looks like a formalist's problem to me. Use subtypes:

   type With_Off is (Off, Only);  -- two literals

   subtype The_King is With_Off range Only .. Only; -- one literal


   left_the_building:
     array (The_King'first .. The_King'base'first) of Boolean;

Re: Surprise in array concatenation

[Lutz Donnerhacke]

* Georg Bauhaus wrote:
> Florian Weimer wrote:
>> Even more problematic is the empty array whose index type
>> is an enumeration type with just one enumeration literal.
>
> This looks like a formalist's problem to me. Use subtypes:
>
>    type With_Off is (Off, Only);  -- two literals
>    subtype The_King is With_Off range Only .. Only; -- one literal

You formally introduces a base type. But even this subtype fails to
construct an empty array starting on Off.

Without the base type an empty array can't specified:

 1 with Ada.Text_IO;
 2 use Ada.Text_IO;
 3
 4 procedure t is
 5  type Offset is (Single);
 6  type Test_Array  is array (Offset range <>) of Integer;
 7  empty : Test_Array(Offset'First .. Offset'Base'Pred(Offset'First));
 8 begin
 9   Put_Line("empty'First = " & Offset'Image(empty'First));
10   Put_Line("empty'Last = " & Offset'Image(empty'Last));
11 end;

gcc -c t.adb
t.adb:7:49: Pred of "Offset'First"
t.adb:7:49: static expression raises "Constraint_Error"
gnatmake: "t.adb" compilation error

Re: Surprise in array concatenation

[Georg Bauhaus]

Lutz Donnerhacke wrote:
> * Georg Bauhaus wrote:
> 
>>Florian Weimer wrote:
>>
>>>Even more problematic is the empty array whose index type
>>>is an enumeration type with just one enumeration literal.
>>
>>This looks like a formalist's problem to me. Use subtypes:
>>
>>   type With_Off is (Off, Only);  -- two literals
>>   subtype The_King is With_Off range Only .. Only; -- one literal
> 
> 
> You formally introduces a base type. But even this subtype fails to
> construct an empty array starting on Off.

This looks like a formalist's problem to me.

Computer types have limited value sets, infinite types are an illusion,
useful but not real. If the value is outside the range of values that can
be realised inside a computer, you cannot make the value part of a
terminating computation that does reference the value.
 So why not explicitly identify limits, if you work near the limits?

 One use of 'base'first, where 'base'first < 'first, is in algorithms
that never reference the value at index 'base'first. Like in some
Ada.Containers algorithms. In Ada.Strings.*, index value 0 is off bounds,
but useful, and chosen explicitly.

  type String is array (Positive range <>) of Character;
  subtype Empty_String is String (1 .. 0);
  subtype Empty_String_Verbose is
     String (Positive'first .. Positive'pred(Positive'first));

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Thu, 01 Sep 2005 13:42:37 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
>> A more interesting question is why Empty'First does not raise any
>> exception.
> 
> Because 'First does not denote an element?

Because it does not exist. Consider a discrete type with one or even no
elements.

>> After all, there is no any lower bound of an empty index range.
> 
> ? What's the bound of a range? (as opposed to a bounded array)

The bound of the index range. Array itself has no any bounds, its index may
have them.

>> Provided, that empty arrays are all same, of course. If not, then another
>> interesting question would appear: how to make an empty array with the
>> lower bound Integer'First?
> 
> Carrying the arguement further, how to reference an element
> outside the machine's storage?

This way:

   raise Constraint_Error; -- (:-))

--------------
The problem with the current (Ada 83) design is that it tries to abstract
away trivial mathematical facts:

1. Not all sets have bounds
2. Even if a set is bounded it does not necessarily contain the bound.

Further trivial fact:

3. [a, a-1] is not an empty set. It might be an interval of negative
length, whatever meaning that may have.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

> --------------
> The problem with the current (Ada 83) design is that it tries to abstract
> away trivial mathematical facts:

As does a computer :-)

Re: Surprise in array concatenation

[Florian Weimer]

* Georg Bauhaus:

> Florian Weimer wrote:
>
>> Even more problematic is the empty array whose index type
>> is an enumeration type with just one enumeration literal.
>
> This looks like a formalist's problem to me.

To some extent, sure.  Furtunately, these arrays do not occur in
practice.  However, you have to think about this problem for a moment
when you write generic containers.

Re: Surprise in array concatenation

[Robert A Duff]

"Gene" <gene.ressler@gmail.com> writes:

> Seldom am I surprised by Ada semantics, but today they got me.
> 
> type Int_List_Type is array(Integer range <>) of Integer;

"Positive range <>" or "Natural range <>" is probably a better idea.
If you have an unconstrained array such that Index_Type'First =
Index_Type'Base'First, you will run into trouble with empty arrays.

>       return F(a(1..i - 1) & a(i + 1, a'Last));

> The gotcha is that when (and only when) i is determined to be zero, the
> concatenation in the recursive call to F produces a starting index of 2
> rather than 1.  Of course this causes the base case test to raise an
> exception in the next recursive call.  This is in accordance with the
> ALRM and GNAT implements it perfectly.

Consider:

    X: String(-99 .. -10_000); -- empty string
    Y: constant String := X & "Hello world."

Ada requires the bounds of a String to be in Positive, EXCEPT when it's
an empty String.  So X'First = -99, but Y'First can't be -99.

Your suggestion would make sense if Ada didn't allow weird things like
String(-99 .. -10_000).  It shouldn't -- allowing such things just
causes confusion and bugs.  The rule should be that 'First of every
String is exactly 1.  The 'Last should be in Positive, except in the
empty string case, where the bounds should be exactly 1..0.

The syntax for declaring String could be:

    type String(Length: Natural) is array (Positive range 1..Length)
                of Character;

No need for the "range <>" syntax in this language!

There's also an efficiency advantage: the dope can be just one word
instead of two, and the code to calculate 'Length could be branch free.

Note that Ada 200X has a Vectors generic container package, which
implements growable arrays.  If you pass in Integer as the index type,
you will get Constraint_Error at instantiation time, for this very
reason.  For the same reason, you can't pass an enumeration or modular
type as the index type -- empty vectors wouldn't work.

> Yes I know how to recode this to use a'First instead of 1 as needed.
> 
> Nonetheless the rule seems silly:  When a leading zero-length array is
> catenated to another array the result takes on the starting index of
> the _second_ operand.  This doesn't make sense to me.  Why not use the
> starting index of the zero-length array?

- Bob

Re: Surprise in array concatenation

[Robert A Duff]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On 31 Aug 2005 20:16:43 -0700, Gene wrote:
> 
> > Nonetheless the rule seems silly:  When a leading zero-length array is
> > catenated to another array the result takes on the starting index of
> > the _second_ operand.  This doesn't make sense to me.  Why not use the
> > starting index of the zero-length array?
> 
> Because that might be ill-defined, I guess.
> 
> A more interesting question is why Empty'First does not raise any
> exception.

Heh?  You want this:

    procedure Put(S: String) is
    begin
        for I in S'First..S'Last loop -- equivalent to S'Range
            Put_Char(S(I));

to crash when S = ""?

>... After all, there is no any lower bound of an empty index range.

In Ada, every range, and every array, has both a lower and an upper
bound.

> Provided, that empty arrays are all same, of course.

Depends on what you mean by "same".  ;-)  Different empty arrays can
have different bounds -- but "=" returns True!

>... If not, then another
> interesting question would appear: how to make an empty array with the
> lower bound Integer'First?

You can't.

You should always make sure Index'First > Index'Base'First when using
the "Index range <>" syntax.  (But you don't need to do that when you
have a constrained array -- "...array(Index) of ...".)

- Bob

Re: Surprise in array concatenation

[Robert A Duff]

Florian Weimer <fw@deneb.enyo.de> writes:

> * Dmitry A. Kazakov:
> 
> > A more interesting question is why Empty'First does not raise any
> > exception. After all, there is no any lower bound of an empty index range.
> > Provided, that empty arrays are all same, of course. If not, then another
> > interesting question would appear: how to make an empty array with the
> > lower bound Integer'First?
> 
> You can't.  Even more problematic is the empty array whose index type
> is an enumeration type with just one enumeration literal.

Why would you want an unconstrained array indexed by enumeration type?
And why would you want an empty array if the array type is constrained?

As for modular types -- well, they're an abomination all around.
It makes no sense whatsoever to have an index type for an unconstrained
array such that Index'Pred(Index'First) > Index'First!

- Bob

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On 01 Sep 2005 12:04:17 -0400, Robert A Duff wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On 31 Aug 2005 20:16:43 -0700, Gene wrote:
>> 
>>> Nonetheless the rule seems silly:  When a leading zero-length array is
>>> catenated to another array the result takes on the starting index of
>>> the _second_ operand.  This doesn't make sense to me.  Why not use the
>>> starting index of the zero-length array?
>> 
>> Because that might be ill-defined, I guess.
>> 
>> A more interesting question is why Empty'First does not raise any
>> exception.
> 
> Heh?  You want this:
> 
>     procedure Put(S: String) is
>     begin
>         for I in S'First..S'Last loop -- equivalent to S'Range
>             Put_Char(S(I));
> 
> to crash when S = ""?

Yes. It is in my view no different from

Y := X / X;

crashing when X=0. The former should be

for I in S'Range loop -- is not equivalent to S'First..S'Last when S is ""

The latter should be:

Y := 1; -- is not equivalent to X / X when X is 0

>>... After all, there is no any lower bound of an empty index range.
> 
> In Ada, every range, and every array, has both a lower and an upper
> bound.

That's exactly the problem! (:-))

>> Provided, that empty arrays are all same, of course.
> 
> Depends on what you mean by "same".  ;-)  Different empty arrays can
> have different bounds -- but "=" returns True!

Ditto. Empty sets are indistinguishable. They have no identity. Ada's empty
arrays are different with all nasty consequences of that.

>>... If not, then another
>> interesting question would appear: how to make an empty array with the
>> lower bound Integer'First?
> 
> You can't.

Which is bad.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Thu, 01 Sep 2005 17:36:26 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
>> --------------
>> The problem with the current (Ada 83) design is that it tries to abstract
>> away trivial mathematical facts:
> 
> As does a computer :-)

It does what you tell it. Computers do not have free will! (:-))

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Gene]

Ok.  Thanks.  And Jean-Pierre too.

I completely agree with the marginal utility of other-than-1 least
array indices.

Still it makes complete sense for your code

    X: String(-99 .. -10_000); -- empty string
    Y: constant String := X & "Hello world."

to generate an exception because the dest index range starts at -99.

I have a much bigger problem with

   A : Int_Array(1..i - 1);
   B:  Int_Array(i+1..10);
...
... := A & B;

producing an array indexed from 1 when i = 2 and from 2 when i = 1.
This still makes my head hurt.

The starting point of a range of length zero is a perfectly logical
concept.  It's easy to draw such a range on a number line, for example.
 The fact that A'First is always defined is a tacit verification!

So I'm still interested in an example that shows why the defined
behavior makes sense.

Gene

Re: Surprise in array concatenation

[tmoran]

>I completely agree with the marginal utility of other-than-1 least
>array indices.
   I strongly disagree.  While not dirt common, other 'firsts in
declarations do occur.  -n ..  +n comes to mind.  If you are going to
handle slices, you have to assume 'first /= 1 anyway, so you're not losing
much by allowing it in declarations.  Using 'first instead of 1 also makes
it simple to change between integer and enumeration value indexes.  The
way Ada.Text_IO.Get_Line (et al) returns Last, which works even if you
passed it a slice, has surely prevented many an error as compared to other
languages which would likely return a count (since "all arrays start at
x") and depend on the programmer to do any arithmetic needed to turn it
into an index.  And if you started all arrays at 1, you probably wouldn't
allow the idiom
  subtype cards is string(1 .. 80);
  subtype sequence is range 73 .. 80;
  ...
  if card(sequence) = (sequence=>' ') then

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:
> On 01 Sep 2005 12:04:17 -0400, Robert A Duff wrote:


>>Heh?  You want this:
>>
>>    procedure Put(S: String) is
>>    begin
>>        for I in S'First..S'Last loop -- equivalent to S'Range
>>            Put_Char(S(I));
>>
>>to crash when S = ""?
> 
> 
> Yes.

What is your approach to subranges then?

   function h(s: String) return Unsigned_32 is
      prefix: String renames
         s(s'first .. s'first + Integer'min(3, s'length - 1));
      result: Unsigned_32 := 0;
   begin
      for k in prefix'range loop
         result := result or Shift_Left(Character'pos(prefix(k)),
                                        (k - prefix'first) * 8);
      end loop;
      return result;
   end h;

(If you could assume for the moment that there is no
Unchecked_Conversion and not a different/better algorithm etc.)


Georg 

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

>>>The problem with the current (Ada 83) design is that it tries to abstract
>>>away trivial mathematical facts:
>>
>>As does a computer :-)
> 
> It does what you tell it. Computers do not have free will! (:-))

So why do you want to tell it about non-computer mathematics?

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Fri, 02 Sep 2005 12:43:24 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
>>>>The problem with the current (Ada 83) design is that it tries to abstract
>>>>away trivial mathematical facts:
>>>
>>>As does a computer :-)
>> 
>> It does what you tell it. Computers do not have free will! (:-))
> 
> So why do you want to tell it about non-computer mathematics?

Huh, there is only mathematics and non-mathematics!

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Fri, 02 Sep 2005 12:42:06 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
>> On 01 Sep 2005 12:04:17 -0400, Robert A Duff wrote:
> 
>>>Heh?  You want this:
>>>
>>>    procedure Put(S: String) is
>>>    begin
>>>        for I in S'First..S'Last loop -- equivalent to S'Range
>>>            Put_Char(S(I));
>>>
>>>to crash when S = ""?
>>  
>> Yes.
> 
> What is your approach to subranges then?
> 
>    function h(s: String) return Unsigned_32 is
>       prefix: String renames
>          s(s'first .. s'first + Integer'min(3, s'length - 1));
>       result: Unsigned_32 := 0;
>    begin
>       for k in prefix'range loop
>          result := result or Shift_Left(Character'pos(prefix(k)),
>                                         (k - prefix'first) * 8);
>       end loop;
>       return result;
>    end h;
> 
> (If you could assume for the moment that there is no
> Unchecked_Conversion and not a different/better algorithm etc.)

I don't see any problem, so far. Subrange of an empty range is empty. As
for the checksum of an empty string it is to be extra defined.

You cannot in general case reverse any possible sequence S1, S2, S3, ... to
deduce S0.

IF the sequence is a series bound by some operation *:
SN = x1 * x2 * ...* xN

AND * is a group operation

THEN you can take the unit element of the group for S0.

So if * is "+" then S0 could be 0. If * is "or" then S0 could be "false"
etc.

Now, take something else: let * be max, what would be the maximum of an
empty array? Real'First? What would be then with the array invariant Max >=
Min? What if Float is a subtype of a type which has lesser values than
Real'First?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:
> On Fri, 02 Sep 2005 12:42:06 +0200, Georg Bauhaus wrote:
> 
> 
>>Dmitry A. Kazakov wrote:
>>
>>>On 01 Sep 2005 12:04:17 -0400, Robert A Duff wrote:
>>
>>>>Heh?  You want this:
>>>>
>>>>   procedure Put(S: String) is
>>>>   begin
>>>>       for I in S'First..S'Last loop -- equivalent to S'Range
>>>>           Put_Char(S(I));
>>>>
>>>>to crash when S = ""?
>>>
>>> 
>>>Yes.
>>
>>What is your approach to subranges then?
>>
>>   function h(s: String) return Unsigned_32 is
>>      prefix: String renames
>>         s(s'first .. s'first + Integer'min(3, s'length - 1));
>>      result: Unsigned_32 := 0;
>>   begin
>>      for k in prefix'range loop
>>         result := result or Shift_Left(Character'pos(prefix(k)),
>>                                        (k - prefix'first) * 8);
>>      end loop;
>>      return result;
>>   end h;
>>
>>(If you could assume for the moment that there is no
>>Unchecked_Conversion and not a different/better algorithm etc.)
> 
> 
> I don't see any problem, so far. Subrange of an empty range is empty.

But earlier you said that s'first .. ... should crash when
s = "".

> As
> for the checksum of an empty string it is to be extra defined.
> 
> You cannot in general case reverse any possible sequence S1, S2, S3, ... to
> deduce S0.

This requirement being generated by arbitrarily applying
the mathematical habit of starting things, deducing thing,
extending things to become some general case (not well defined
for real computers), etc. Basic mathematical facts
are basic relative to some starting point from which you perform
mathematical reasoning.


> IF the sequence is a series bound by some operation *:
> SN = x1 * x2 * ...* xN
> 
> AND * is a group operation
> 
> THEN you can take the unit element of the group for S0.

And what does mathematical group theory offer when the computer
executes fine without it? Why don't you start your basic
mathematical theory from things that work, and explain them
first?

If a sphere of negative radius opens many interesting insights
into unforeseen extensions of geometry, will this have an
influence on a pot maker's occupation?

I'm not asking these questions because I believe that mathematics
is the wrong science for approaching real computers. It's not.

However, every once in a while I'm having to defend
that running computers and performing mathematics are two
sets of operations. They have a fair amount of overlap.
But they are not the same set. Yet many mathematicians
seem to view computer programming as if it were nothing but
a way of transforming their mathematical knowledge into programs,
largely ignoring a few issues:

1 - computers perform I/O, in time - no complete simple theory
    here, right?
2 - computers operate non-deterministically ("malfunction")
    ("Malfunctions are the technicians' job. I'm writing
    mathematically correct programs for flawless computers")
3 - computers are finite.
4 - computers cannot operate on no (0) bits.

Why don't they apply their mathematical capacity to problems
that are probably less fun and more dirty but more crucial?
That it, at least consider adapting mathematics to the world
instead of adapting the world to mathematics.


> Now, take something else: let * be max, what would be the maximum of an
> empty array?

A problem of math-think. Like this

... talking to son:

"See this little wood over there? I have counted the trees,
there are 139."

... a little later:

"Remember I told you about this wood having 139 trees, 14
years ago? Now there are only 23 left."

... talking to granddaughter visiting:

"See this little wood over there?" -- "No."
-- "It has 0 trees". -- "Ha, ha."

If there is nothing about which to say anything,
then mathematicians decide to say something about
it: truth. Useful, but in a material setting, you have
to consider whether it makes sense. Using your Max example,
I could ask those mathematicians about the maximum of a
subset of the natural numbers (possibly empty!). I'd venture
a guess that the answer will likely be, "It depends.".

For example, you have given "extra defined". ;-)

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:
> On Fri, 02 Sep 2005 12:43:24 +0200, Georg Bauhaus wrote:
> 
> 
>>Dmitry A. Kazakov wrote:
>>
>>
>>>>>The problem with the current (Ada 83) design is that it tries to abstract
>>>>>away trivial mathematical facts:
>>>>
>>>>As does a computer :-)
>>>
>>>It does what you tell it. Computers do not have free will! (:-))
>>
>>So why do you want to tell it about non-computer mathematics?
> 
> 
> Huh, there is only mathematics and non-mathematics!

Not at all. Mathematics is not even a well defined term in a formal
sense of the word "definition". (Notice the recursion :-)

Thus computer-mathematics (as in theory of real, operating hardware)
if used in a PL context has to start from some description
of the real computer to be used with a PL program.

Real computers executing (non-empty) programs translated from Ada text
cannot but transorm a finite number (> 0) of finite (non-empty) sets
of discrete "fantasies" of electro-magnetic values, somehow coping
with the effects of one or more "times".

That excludes infinity and no-bits from real-computer mathematics,
for a start. Likewise, forget about non-discrete numbers.

Re: Surprise in array concatenation

[Björn Persson]

Dmitry A. Kazakov wrote:
> On Thu, 01 Sep 2005 17:36:26 +0200, Georg Bauhaus wrote:
>>Dmitry A. Kazakov wrote:
>>>The problem with the current (Ada 83) design is that it tries to abstract
>>>away trivial mathematical facts:
>>
>>As does a computer :-)
> 
> It does what you tell it. Computers do not have free will! (:-))

You mean the Ada 83 design does have a free will? :-�

-- 
Bj�rn Persson                              PGP key A88682FD
                    omb jor ers @sv ge.
                    r o.b n.p son eri nu

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Fri, 02 Sep 2005 16:23:23 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
>> On Fri, 02 Sep 2005 12:43:24 +0200, Georg Bauhaus wrote:
>> 
>>>Dmitry A. Kazakov wrote:
>>>
>>>>>>The problem with the current (Ada 83) design is that it tries to abstract
>>>>>>away trivial mathematical facts:
>>>>>
>>>>>As does a computer :-)
>>>>
>>>>It does what you tell it. Computers do not have free will! (:-))
>>>
>>>So why do you want to tell it about non-computer mathematics?
>> 
>> Huh, there is only mathematics and non-mathematics!
> 
> Not at all. Mathematics is not even a well defined term in a formal
> sense of the word "definition". (Notice the recursion :-)
>
> Thus computer-mathematics (as in theory of real, operating hardware)
> if used in a PL context has to start from some description
> of the real computer to be used with a PL program.

So you add another adjective to get: "ill-defined computer mathematics."
(:-))
 
> Real computers executing (non-empty) programs translated from Ada text
> cannot but transorm a finite number (> 0) of finite (non-empty) sets
> of discrete "fantasies" of electro-magnetic values, somehow coping
> with the effects of one or more "times".
> 
> That excludes infinity and no-bits from real-computer mathematics,
> for a start. Likewise, forget about non-discrete numbers.

This is plain wrong. You can deal with all sorts of infinity in a finite
program. Because there is no limitation on how the set of computation
states (finite) have to be mapped onto the application domain set
(potentially infinite). There is no any problem to associate one state with
Pi, another with an empty set and third with aleph-twenty.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Fri, 02 Sep 2005 16:14:55 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
>> On Fri, 02 Sep 2005 12:42:06 +0200, Georg Bauhaus wrote:
>> 
>>>Dmitry A. Kazakov wrote:
>>>
>>>>On 01 Sep 2005 12:04:17 -0400, Robert A Duff wrote:
>>>
>>>>>Heh?  You want this:
>>>>>
>>>>>   procedure Put(S: String) is
>>>>>   begin
>>>>>       for I in S'First..S'Last loop -- equivalent to S'Range
>>>>>           Put_Char(S(I));
>>>>>
>>>>>to crash when S = ""?
>>>> 
>>>>Yes.
>>>
>>>What is your approach to subranges then?
>>>
>>>   function h(s: String) return Unsigned_32 is
>>>      prefix: String renames
>>>         s(s'first .. s'first + Integer'min(3, s'length - 1));
>>>      result: Unsigned_32 := 0;
>>>   begin
>>>      for k in prefix'range loop
>>>         result := result or Shift_Left(Character'pos(prefix(k)),
>>>                                        (k - prefix'first) * 8);
>>>      end loop;
>>>      return result;
>>>   end h;
>>>
>>>(If you could assume for the moment that there is no
>>>Unchecked_Conversion and not a different/better algorithm etc.)
>> 
>> I don't see any problem, so far. Subrange of an empty range is empty.
> 
> But earlier you said that s'first .. ... should crash when
> s = "".

Yes, because the code above is incorrect in my view. You should explicitly
test for s'length = 0.

>> As
>> for the checksum of an empty string it is to be extra defined.
>> 
>> You cannot in general case reverse any possible sequence S1, S2, S3, ... to
>> deduce S0.
> 
> This requirement being generated by arbitrarily applying
> the mathematical habit of starting things, deducing thing,
> extending things to become some general case (not well defined
> for real computers), etc.

Empty range is such a generalization!

> Basic mathematical facts
> are basic relative to some starting point from which you perform
> mathematical reasoning.

What about secondary school as a starting point? (:-))

>> IF the sequence is a series bound by some operation *:
>> SN = x1 * x2 * ...* xN
>> 
>> AND * is a group operation
>> 
>> THEN you can take the unit element of the group for S0.
> 
> And what does mathematical group theory offer when the computer
> executes fine without it? Why don't you start your basic
> mathematical theory from things that work, and explain them
> first?

It perfectly predicts where things like above work and where they fail.
Just try to rewrite your program to make it working for any array type.

Note there is nothing particularly difficult in writing some program in
C++. But *programming* in C++ is an immense problem. See any parallel?

> If a sphere of negative radius opens many interesting insights
> into unforeseen extensions of geometry, will this have an
> influence on a pot maker's occupation?

What about zero radius? If you want to play a Luddite, then start with
prohibiting empty strings. Do a writer need empty texts?

> I'm not asking these questions because I believe that mathematics
> is the wrong science for approaching real computers. It's not.
> 
> However, every once in a while I'm having to defend
> that running computers and performing mathematics are two
> sets of operations. They have a fair amount of overlap.
[..]

What is the point? Do computers something which cannot be described using
mathematics? That is not what you are saying. Then what?

A trivial analysis shows inconsistency of A'First..A'First-1. There is
nothing new in that. It is well known. A pragmatic school calmly admits it,
but points out that to fix would probably mean too much work, and that it's
much too late anyway, especially, because programs are infested with
constructs like A'First..A'Last, Index..A'Last etc.

But you seem to be seeking for rather philosophic arguments to keep it
inconsistent. (:-))

>> Now, take something else: let * be max, what would be the maximum of an
>> empty array?
> 
> A problem of math-think. Like this
> 
> ... talking to son:
> 
> "See this little wood over there? I have counted the trees,
> there are 139."
> 
> ... a little later:
> 
> "Remember I told you about this wood having 139 trees, 14
> years ago? Now there are only 23 left."
> 
> ... talking to granddaughter visiting:
> 
> "See this little wood over there?" -- "No."
> -- "It has 0 trees". -- "Ha, ha."
> 
> If there is nothing about which to say anything,
> then mathematicians decide to say something about
> it: truth. Useful, but in a material setting, you have
> to consider whether it makes sense.

Absolutely. Mathematics is applied to solve problems. To be able to do it
the mathematical models you use have to be adequate. But even before that
they have to be *consistent*. For good or bad, but no inconsistent thing
can be adequate.

> Using your Max example,
> I could ask those mathematicians about the maximum of a
> subset of the natural numbers (possibly empty!). I'd venture
> a guess that the answer will likely be, "It depends.".
> 
> For example, you have given "extra defined". ;-)

Exactly as with A'First. It depends! You choose A'First to exist for any
array. But I prefer a more usable in my view:

A(A'First) does exit

or

Index'Pos(A'First) <= Index'Pos(A'Last)

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Jeffrey R. Carter]

Gene wrote:

> I completely agree with the marginal utility of other-than-1 least
> array indices.

Then you need a lot more experience. There is great utility to arrays with lower 
bounds other than 1, and to arrays with non-numeric bounds.

30 years ago, when I became a coder, I worked in dendroclimatology, attempting 
to determine the climate of the past from tree-ring information. We had code 
with big arrays of tree-ring data, all indexed from 1, of course, since this was 
in FORTRAN 66, and other arrays of climate data. The tree-ring data started with 
values from some year in the past, such as 1600, and the climate data in 1895 or 
so. The code was liberally sprinkled with calculations to convert between the 
logical indices (years) and the actual indices (1 .. # of years). Different 
calculations had to be used for the 2 data sets, I didn't capture the algorithms 
in functions because I didn't know any better, and sometimes I managed to use 
the wrong calculation. Ah, those were the days!

How much easier it would have been if I could simply have indexed these things 
from 1600 .. 1965 and 1895 .. 1965. (Having record types would have helped, too.)

This helps explain the popularity of C and its descendants: It gives a real 
feeling of accomplishment to do this kind of thing successfully, even though it 
contributes nothing to the solution of the real problem being addressed.

The problem in the example is that the code defines an array type with "Integer 
range <>", allowing any lower bound in Integer, and proceeds to assume that all 
values of the type have lower bound of 1. That's a simple implementation error. 
Had the implementor recognized that values of the type may have any lower bound 
in Integer, and used 'First rather than an incorrect magic number, the problem 
would not have appeared.

If there is a requirement that the values have a lower bound of 1, there's an 
Ada mechanism for that:

type A is array (Positive range <>) of Whatever;

type Lower_Bound_Always_1 (Length : Natural) is record
    Value : A (1 .. Length);
end record;

Even then, one should still use 'First.

-- 
Jeff Carter
"I fart in your general direction."
Monty Python & the Holy Grail
05

Re: Surprise in array concatenation

[Dr. Adrian Wrigley]

On Thu, 01 Sep 2005 14:42:22 -0700, Gene wrote:

...
> I completely agree with the marginal utility of other-than-1 least
> array indices.

Like others, I'm surprised to find this is controvertial.

People have given some examples already.  My favourite
examples are:

Compatibility with languages that have 0-based arrays.
it would be really annoying if indices couldn't be shared
between C and Ada arrays, for example.
(most C/C++ users see litle utility in other-than-0 least indices!)

Ability for subprograms to receive slices of arrays as
parameters.  C code often has to pass start and stop
indices as separate function parameters, in addition to
the pointer to the first element.  Three parameters instead
of one adds clutter.  Particularly common in recursive calls.

Arrays indexed by modular types. (I know these have been criticised
elsewhere).  Modular indices are really handy for circular
buffers, as well as hash tables and things (pre Ada 200Y!).

Arrays indexed by characters (eg a letter frequency table,
'a' .. 'z').

I also use symmetric array indices (eg -10 .. 10) quite a
lot for tables indexed by differences.

Sometimes negative indices are useful too, (with 0 at the top, usually)
(eg -100 .. 0).  This is useful for analysing events through
relative time.  Negative indices are preconditions, positive
indices would be postconditions or responses. (
(If you only have positive indices, you find some arrays in
your program run forwards through time, and some run backwards.
Tracking which is which, and getting the '-' in the right
place is particularly error prone)

And of course, plenty of contrived examples can be made up,
some of which so actually occur in real problems.
It's just another area of coding where Ada matches the
problem domain, and other languages match the solution domain.
Like so many things in Ada, you may not use them every day
in some applications, but they're there when you need them!

By the way... why aren't fixed point types discrete?
The values are integral multiples of small, which can be
supplied by the user.  So I'd expect to be able to use
fixed point types as array indices etc.  You cant :(
Wouldn't fixed point be *much* more useful if it was discrete?
-- 
Adrian

Re: Surprise in array concatenation

[Jacob Sparre Andersen]

"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> writes:

> By the way... why aren't fixed point types discrete?

I don't know.  Is it be a leftover from some limitations in Ada83?

> The values are integral multiples of small, which can be supplied by
> the user.  So I'd expect to be able to use fixed point types as
> array indices etc.  You cant :( Wouldn't fixed point be *much* more
> useful if it was discrete?

Yes.

Jacob
-- 
�When in Rome; burn it�                        -- Diziet Sma

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

> Just try to rewrite your program to make it working for any array type.

A rewrite for any array (I presume: any index) will fail only where
mathematically subtracting 4 from 3 will fail in N.

> C++. But *programming* in C++ is an immense problem. See any parallel?

Are you saying that C++ is less mathematical than Ada?

> What about zero radius? If you want to play a Luddite, then start with
> prohibiting empty strings. Do a writer need empty texts?

Writers have used empty texts. Programmers frequently use empty
strings, for I/O.

> Do computers something which cannot be described using
> mathematics?

Yes, most real computers, if not all of them, cannot at all be shown to
be a Turing machine equivalent. We do not even know whether or not the
world's most often sold CPU works properly, at least not in a
mathematically satisfying sense ("yes" or "no").
Now think of the peripherals, etc. A real computer is a statistically
reliable device, but you cannot mathematically show that your desktop
computer does what we believe it does.

> That is not what you are saying. Then what?

Another problem with computer mathematics is that it largely neglects
continuous time, and bare I/O operations. Time is transformed into
ticks, I/O is reduced to 'Valid plus compiler magic built on top of
OS routines which mostly work - for whatever reason.
Who can show, in mathematically sufficient detail, the way of
some bits generated by a partition running on computer A sent
to a partition running on computer B? (Who *wants* to do this? :)

This requires statistics, rules of thumb, and experiments.

> A trivial analysis shows inconsistency of A'First..A'First-1.

The inconsistency of A'First..A'First - 1, if any, is relative
to a set of definitions.

It seem that off-bounds indices are a ubiquituous feature, found in
several programming languages' algorithms and data structures.
The indices avoid, for one thing, a proliferation of conditionals
like
  if x'length = 0 then ... else perform(...) end if;
Without the special test, you can unconditionally say

  forall things in x | P ...

or

  as-soon-as cursor is off things in x | P ...

Something that I think is frequently found in math literature ;-)

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Sat, 03 Sep 2005 22:01:03 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
>> C++. But *programming* in C++ is an immense problem. See any parallel?
> 
> Are you saying that C++ is less mathematical than Ada?

I'm saying that the source of C++'s problems is a less consistent,
careless, sometimes mindless design than Ada has.

>> What about zero radius? If you want to play a Luddite, then start with
>> prohibiting empty strings. Do a writer need empty texts?
> 
> Writers have used empty texts.

Does Amazon sell any empty books?

> Programmers frequently use empty strings, for I/O.

Then show me the "first character" printed! (:-))

>> Do computers something which cannot be described using
>> mathematics?
> 
> Yes, most real computers, if not all of them, cannot at all be shown to
> be a Turing machine equivalent.

Firstly, they can. You probably meant computer systems as whole
(+inputs/outputs.) It is not what usually called "computer".) Secondly,
mathematics does not end in Turing machines.

> We do not even know whether or not the
> world's most often sold CPU works properly, at least not in a
> mathematically satisfying sense ("yes" or "no").

It is a silly argument. Next time paying a fine, tell the officer that
because you cannot tell if traffic lights work properly, you can ignore
traffic regulations.

> Now think of the peripherals, etc.

See above.

> A real computer is a statistically
> reliable device, but you cannot mathematically show that your desktop
> computer does what we believe it does.

The probability theory is at your service.

But wait, should I understand the above as: Empty'First..Empty'First-1 is
correct, because Empty might be random? Come on! (:-))
 
>> That is not what you are saying. Then what?
> 
> Another problem with computer mathematics is that it largely neglects
> continuous time, and bare I/O operations.

You should address that to CS which is only a stepdaughter of mathematics.
Then the problem is not in which part of mathematics one would apply. The
problem is that you seem to reject mathematics (and logic) as a tool,
proposing nothing instead. The language should be consistent, there is no
doubt about it.

> Time is transformed into
> ticks, I/O is reduced to 'Valid plus compiler magic built on top of
> OS routines which mostly work - for whatever reason.
> Who can show, in mathematically sufficient detail, the way of
> some bits generated by a partition running on computer A sent
> to a partition running on computer B? (Who *wants* to do this? :)

Huh, who can solve Maxwell's equations for a TV set? Does it mean that you
can create one ignoring laws of physics?

> This requires statistics, rules of thumb, and experiments.

I.e. random empty strings...

>> A trivial analysis shows inconsistency of A'First..A'First-1.
> 
> The inconsistency of A'First..A'First - 1, if any, is relative
> to a set of definitions.

Yep, like:

1. "any unconstrained array type shall have empty instances"
2. "any array instance contain its lower and upper bound"

> It seem that off-bounds indices are a ubiquituous feature, found in
> several programming languages' algorithms and data structures.

Re-read what you wrote: an off-bound [array] index is an array bound! Is it
"off" or not? (:-))

> The indices avoid, for one thing, a proliferation of conditionals like
>   if x'length = 0 then ... else perform(...) end if;
> Without the special test, you can unconditionally say
> 
>   forall things in x | P ...

Absolutely! And Ada has this construct:

   for I in P'Range loop
      x := P (I);
      ... -- do something with x

It would be nice if Ada would support abstract iterations like:

   for x in P loop
      ... -- do something with x

Better ADT is what Ada needs.

> or
> 
>   as-soon-as cursor is off things in x | P ...

No! This is an extremely bad idea borrowed for C pointer arithmetic. It
presumes that cursor might be off. It is a very strong assumption, which
may have a great impact on the algorithm:

1. The cursor have to have "off" values. Consider the type Character,
you'll need to extend it with two values, left and right. Presently Ada
does not support this. And if it did, then it would require another
representation for extended Character with conversions forth and back all
the way. An alternative? Well, remember C's nul-terminated strings? Do you
enjoy them?

2. There should be a way to construct off-values. That might be very
non-trivial. Example: pointers. Try to find a pointer that does not point
to some object. You have to undertake some actions to ease it. For example
to reserve null with the *distributed* overhead of testing for "null"
throughout the program.

3. As I said before, you have a distributed overhead of distinguishing two
sorts of cursors. That would make optimization difficult. It is a halting
problem to determine if a cursor is off.

> Something that I think is frequently found in math literature ;-)

I'm not a mathematician, so I cannot tell. But I think that the set theory
explicitly forbids unbound quantifiers, which would otherwise refer to the
set of "all things" (an equivalent of "off-set" thing.) It is no-no.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Jean-Pierre Rosen]

Jacob Sparre Andersen a �crit :

>>The values are integral multiples of small, which can be supplied by
>>the user.  So I'd expect to be able to use fixed point types as
>>array indices etc.  You cant :( Wouldn't fixed point be *much* more
>>useful if it was discrete?
> 
That's the view of the solution space. The view of the problem space is 
that they are a different approximation of real numbers (floating point 
values being the other one). And you can't index an array with real 
values, whether float or fixed.

-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Surprise in array concatenation

[Jean-Pierre Rosen]

Robert A Duff a �crit :
> Why would you want an unconstrained array indexed by enumeration type?
> And why would you want an empty array if the array type is constrained?
> 
I do that all the time, especially in ASIS programming. You may have 
arrays indexed with subranges of declaration_kinds for example.

-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Arrays indexed by fixed point types (Was: Surprise in array concatenation)

[Jacob Sparre Andersen]

Jean-Pierre Rosen skrev:

> >>The values are integral multiples of small, which can be supplied
> >>by the user.  So I'd expect to be able to use fixed point types as
> >>array indices etc.  You cant :( Wouldn't fixed point be *much*
> >>more useful if it was discrete?
> 
> That's the view of the solution space. The view of the problem space
> is that they are a different approximation of real numbers (floating
> point values being the other one). And you can't index an array with
> real values, whether float or fixed.

I find that definition of arrays rather limited.

I have some cases, where my problem is to store data in an array
indexed by an approximation of real numbers.  The most obvious (and
recurring) example is a histogram of real valued samples.  As it is
now, I have to mess around with mapping my (approximated) real numbers
onto an integer scale and back again.

Greetings,

Jacob
-- 
ACRONYM: A Contrived Reduction Of Nomenclature Yielding Mnemonics

Re: Arrays indexed by fixed point types (Was: Surprise in array concatenation)

[Jean-Pierre Rosen]

Jacob Sparre Andersen a �crit :
> I find that definition of arrays rather limited.
> 
> I have some cases, where my problem is to store data in an array
> indexed by an approximation of real numbers.  The most obvious (and
> recurring) example is a histogram of real valued samples.  As it is
> now, I have to mess around with mapping my (approximated) real numbers
> onto an integer scale and back again.
> 
If you want to associate values to arbitrary elements, use a map.

Arrays are for discrete indices.

-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Surprise in array concatenation

[Dr. Adrian Wrigley]

On Mon, 05 Sep 2005 10:34:01 +0200, Jean-Pierre Rosen wrote:

> Jacob Sparre Andersen a �crit :
> 
>>>The values are integral multiples of small, which can be supplied by
>>>the user.  So I'd expect to be able to use fixed point types as
>>>array indices etc.  You cant :( Wouldn't fixed point be *much* more
>>>useful if it was discrete?
>> 
> That's the view of the solution space. The view of the problem space is 
> that they are a different approximation of real numbers (floating point 
> values being the other one). And you can't index an array with real 
> values, whether float or fixed.

Yes it is a solution space view.  The point that I was making was
that there were straightforward implementations available to
compilers.

The view of the problem space is that an array indexed by a real
value represents an arbitrary univariate function.  I use these
"all the time" in generating probability density estimates.
And also for lookup of complicated functions.  The example
of computing histograms from Jacob is closely related.

So I'm slightly surprised to hear you say you can't index an
array with real value (approximations).
-- 
Adrian

Re: Arrays indexed by fixed point types (Was: Surprise in array concatenation)

[Dmitry A. Kazakov]

On 05 Sep 2005 11:32:23 +0200, Jacob Sparre Andersen wrote:

> Jean-Pierre Rosen skrev:
> 
>>>>The values are integral multiples of small, which can be supplied
>>>>by the user.  So I'd expect to be able to use fixed point types as
>>>>array indices etc.  You cant :( Wouldn't fixed point be *much*
>>>>more useful if it was discrete?
>> 
>> That's the view of the solution space. The view of the problem space
>> is that they are a different approximation of real numbers (floating
>> point values being the other one). And you can't index an array with
>> real values, whether float or fixed.
> 
> I find that definition of arrays rather limited.

> I have some cases, where my problem is to store data in an array
> indexed by an approximation of real numbers.  The most obvious (and
> recurring) example is a histogram of real valued samples.

Well, but probably those samples aren't real numbers. I suppose they are
rather intervals. So the array index type should not be float (=uncountable
in the problem space), but from some finite set of intervals (=countable in
the problem space.)

[ However in my view array is just a syntax sugar, something with the
operation "()". ]

> As it is
> now, I have to mess around with mapping my (approximated) real numbers
> onto an integer scale and back again.

I think that instead of blowing up the language with countless types which
might be useful as array indices (actually maps), it would be much better
to provide user-defined index and array types with primitive operations
"()", 'First, 'Range, "in", "not in", aggregate etc.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Arrays indexed by fixed point types (Was: Surprise in array concatenation)

[Jacob Sparre Andersen]

Dmitry A. Kazakov wrote:
> Jacob Sparre Andersen wrote:

> > I have some cases, where my problem is to store data in an array
> > indexed by an approximation of real numbers.  The most obvious
> > (and recurring) example is a histogram of real valued samples.
> 
> Well, but probably those samples aren't real numbers. I suppose they
> are rather intervals.

Good point.  Yes.

> I think that instead of blowing up the language with countless types
> which might be useful as array indices (actually maps), it would be
> much better to provide user-defined index and array types with
> primitive operations "()", 'First, 'Range, "in", "not in", aggregate
> etc.

That would be nice, but wouldn't it be rather difficult to fit into
Ada?  We would still have the limitation as to which index types could
be used together with a for loop, so there would also be a need for
some kind of iterator for the user-defined array types.

Jacob
-- 
�In Ada you model the problem space, not the solution space.�
                                                     -- Robert I. Eachus

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

I think I can abbreviate, by answering this one:

> Huh, who can solve Maxwell's equations for a TV set? Does it mean that you
> can create one ignoring laws of physics?

You *are* ignoring the laws of physing in building a TV set
because no one *knows* whether Maxwell's equations describe
any particular TV set, and no one *can* perform a complete *test*.
We try to approximate, and we do believe, that's what we do.

If you claim *not* to ignore the laws of physics when building
TV sets, then you will have to show that all of what you build
is described by Maxwell's equations (etc.). It boils down to
"very likely", "I don't see otherwise", etc. But there is no
mathematical demonstration of Maxwell's law describing a TV set,
or is there?

The laws of physics provide helpful guidance, nothing more,
nothing less. No claims, please, that something is physically
lawful. Maxwell himself has asked us not to talk about electrons
as if we knew that they exist, or what they are.

A TV set might surprise us in suggesting that Maxwell's equations
aren't complete. Frankly, I won't speculate that my old TV set will
do this.


Likewise, a computer might surprise us in suggesting that our
fine mathematically thought-out program doesn't quite behave exactly
as we thought, because of the naughty computer thingy and its
quirks.


> Re-read what you wrote: an off-bound [array] index is an array bound! Is it
> "off" or not? (:-))

We have
 lo, hi: arrays -> I,
 item: arrays x I -> values

If hi is onto [1, 2, ... 5], then item(hi(Some_Array, X)) lies in values,
provided hi(Some_Array, X) is defined.

For example, hi(Some_Array, 17) is undefined, generating an exception in
Ada terms.

If Some_Array'first = 42, hi(some_array, Some_Array'First) is undefined.
Exception. Enough consistency here, for my taste.


> Better ADT is what Ada needs.

Is Ada a Must for you? These things are built into other programming
languages.

>>  as-soon-as cursor is off things in x | P ...
> 
> 
> No! This is an extremely bad idea borrowed for C pointer arithmetic. It
> presumes that cursor might be off. It is a very strong assumption, which
> may have a great impact on the algorithm:

Certainly off-container indices/cursors offer a practical approach.
 
> 1. The cursor have to have "off" values. Consider the type Character,
> you'll need to extend it with two values, left and right. Presently Ada
> does not support this.

Do you insist that every subtype must be associated with an index subtype,
such that every index value can be used to denote a value from the array?


> 2. There should be a way to construct off-values. That might be very
> non-trivial. Example: pointers. Try to find a pointer that does not point
> to some object.

The Eiffel solution is to (implicitly) have class NONE be an heir
of every class in the system. So NONE conforms to every type, or every
type is among the progenitors of NONE.
There is a single instance of NONE, called Void. A reference that isn't
attached to some object refers to Void.


>>Something that I think is frequently found in math literature ;-)
> 
> 
> I'm not a mathematician, so I cannot tell. But I think that the set theory
> explicitly forbids unbound quantifiers, which would otherwise refer to the
> set of "all things" (an equivalent of "off-set" thing.) It is no-no.

You mean that the set to be enumerated is given?
The set need not be finite in computing science, at least this is what
I remember from the pleasant days of working my way through books
on the subject.
Existential quantifiers can be bounded or not, if they are
bounded, you have bounded minimization (finding the smallest
number such that ...).

Re: Arrays indexed by fixed point types (Was: Surprise in array concatenation)

[Dmitry A. Kazakov]

On 05 Sep 2005 15:07:38 +0200, Jacob Sparre Andersen wrote:

>> I think that instead of blowing up the language with countless types
>> which might be useful as array indices (actually maps), it would be
>> much better to provide user-defined index and array types with
>> primitive operations "()", 'First, 'Range, "in", "not in", aggregate
>> etc.
> 
> That would be nice, but wouldn't it be rather difficult to fit into
> Ada?  We would still have the limitation as to which index types could
> be used together with a for loop, so there would also be a need for
> some kind of iterator for the user-defined array types.

Yes. That should be the user-defined "index" type, where "index" would be a
class of types like "array", "access", "range" are.

The main problem with making "array" and "access" fully user-defined is IMO
maintaining parallel type hierarchies:

abstract access <-- user access
abstract aliased type <-- concrete target type
---------
abstract array <-- user array
      [+ slices and other related subarray types]
abstract index <- user index
      [+ ranges and other subsets of]
abstract element type <-- concrete element type

To organize a for loop one should be able to obtain the index type of the
array. We already have T'Class, we could also introduce T'Index, T'Element
etc. It smells of types as first-class objects, matched by structure. Not
very Ada.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Arrays indexed by fixed point types (Was: Surprise in array concatenation)

[Dr. Adrian Wrigley]

On Mon, 05 Sep 2005 13:07:33 +0200, Jean-Pierre Rosen wrote:
...
> If you want to associate values to arbitrary elements, use a map.
> 
> Arrays are for discrete indices.

I agree.  But I'm still not satisfied.

I wrote:
> By the way... why aren't fixed point types discrete?

I think the answer is that it wasn't seen as sufficiently
important.

Dmitry wrote
> I think that instead of blowing up the language with countless types...

I don't think that is a risk.  I'm just looking for a bit
more orthogonality and to get more value from fixed point types.
When coding (DSP) in assembler on a FPU-less CPU (eg ARM), fixed
point types are extremely common. Indexing memory by them is
also common.  This compact efficient code is messy to write in Ada.

But then I'd also like records of discrete values to be discrete
also.  It'd make coding in dynamic dimensionalities massively easier.
I think convincing people that's a worthwhile addition would
be hard.
-- 
Adrian

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Mon, 05 Sep 2005 15:22:18 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
> I think I can abbreviate, by answering this one:
> 
>> Huh, who can solve Maxwell's equations for a TV set? Does it mean that you
>> can create one ignoring laws of physics?
> 
> You *are* ignoring the laws of physing in building a TV set
> because no one *knows* whether Maxwell's equations describe
> any particular TV set, and no one *can* perform a complete *test*.

That's a different thing. If you discovered that according to your design
the TV set would violate Ohm's law. What would you check first? The design
or the theory?

> Likewise, a computer might surprise us in suggesting that our
> fine mathematically thought-out program doesn't quite behave exactly
> as we thought, because of the naughty computer thingy and its
> quirks.

You are mixing inadequate and inconsistent models.

>> Re-read what you wrote: an off-bound [array] index is an array bound! Is it
>> "off" or not? (:-))
> 
> We have
>  lo, hi: arrays -> I,
>  item: arrays x I -> values
> 
> If hi is onto [1, 2, ... 5], then item(hi(Some_Array, X)) lies in values,
> provided hi(Some_Array, X) is defined.
> 
> For example, hi(Some_Array, 17) is undefined, generating an exception in
> Ada terms.
> 
> If Some_Array'first = 42, hi(some_array, Some_Array'First) is undefined.
> Exception. Enough consistency here, for my taste.

What about hi >= lo? What about handling Some_Array (Some_Array'First)
failure? Note that it fails not because there is no A'First, but because
the index is wrong? How so? It exists, but wrong! Then what would you do
with modular and enumeration types?

>> Better ADT is what Ada needs.
> 
> Is Ada a Must for you?

Sure. C++ shortens my life!

> These things are built into other programming
> languages.

Like C++? (:-))

>> 1. The cursor have to have "off" values. Consider the type Character,
>> you'll need to extend it with two values, left and right. Presently Ada
>> does not support this.
> 
> Do you insist that every subtype must be associated with an index subtype,
> such that every index value can be used to denote a value from the array?

   subtype I is Index range A'Range; -- This is legal Ada

What I want is freedom. I don't want the compiler to decide for me whether
there must be "off" values or not. The concept of array must be consistent
with index types having no "off" values, like ring buffers. It also should
consistently support arrays over empty index types.

>> 2. There should be a way to construct off-values. That might be very
>> non-trivial. Example: pointers. Try to find a pointer that does not point
>> to some object.
> 
> The Eiffel solution is to (implicitly) have class NONE be an heir
> of every class in the system. So NONE conforms to every type, or every
> type is among the progenitors of NONE.
> There is a single instance of NONE, called Void. A reference that isn't
> attached to some object refers to Void.

This is incompatible with modular and enumeration types. It also has a
distributed overhead. You either will have no by-copy types or will need to
store NONE where one bit would otherwise be enough. Then making a hash
function you'll need to explicitly test for NONE etc.
 
>>>Something that I think is frequently found in math literature ;-)
>> 
>> I'm not a mathematician, so I cannot tell. But I think that the set theory
>> explicitly forbids unbound quantifiers, which would otherwise refer to the
>> set of "all things" (an equivalent of "off-set" thing.) It is no-no.
> 
> You mean that the set to be enumerated is given?

Sure. And in mathematics there is no problem to write:

   forall x in X

The concept:

   for I in A'First..A'Last loop

is more specialized than

   for I in A'Range loop

and even more than

   for X in A loop -- Not Ada!

I in A'First..A'Last that A'Range is 1) ordered, 2) has the lower and upper
bounds, 3) these bounds belong to the array. These assumptions are not
always required. Moreover, for some arrays they are wrong. Consider making
a loop over a ring buffer starting in somewhere the middle. [We have
already debated unordered index types some time ago.] A very practical
principle is to design software with minimal assumptions.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Gene]

Thanks for a great discussion.

I didn't say general array indexing is not useful; it obviously is. I
said it's marginally useful in the literal (economist's) sense of "at
the margin."  A few illustrations...

1) If one had to give up a feature in order to get another, many would
put general array indexing early on the chopping block. Between fixed
and dynamic length arrays (and in particular bounded/unbounded
strings), for example, Ada forces one to change from native array
syntax to a procedural interface that hides re-sizing details.  Ada
programmers I know would happily give up general index ranges in order
to get dynamically resizing arrays with native syntax---at least those
who have worked in other languages where such are available.

2) General integer ranges for array indices are a half-hearted---at the
margins---compromise wrt fully general arrays allowing any type as an
index.  In other words, if you put
(A) 1-based arrays,
(B) general discrete type array indices, and
(C) fully general arrays
on a conceptual scale, (B) lies _much_ closer to (A) than to (C).

3) The wonder of Ada is the predicatable, orthogonal way that syntax
and semantics correspond.  But we have just been observing that general
integer array indexing leads to a not-very-predictable behavior in
combination with slicing and catenation. If all arrays were 1-based,
the problem could not have occurred.  Hence this unhappy confluence of
features, by conflicting with Ada's philosophy, is at the semantic
margins of the language.  It ought to be avoided if the goal is code
with obvious meaning. E.g. after I re-coded my original example
"properly" with 'First and 'Range to make its behavior correct, I
quickly added a comment, -- 'First is not always 1.  How marginally
Ada!

Again best regards to all and thanks for the discussion.

Re: Surprise in array concatenation

[jimmaureenrogers]

Gene wrote:
> Thanks for a great discussion.
>
> I didn't say general array indexing is not useful; it obviously is. I
> said it's marginally useful in the literal (economist's) sense of "at
> the margin."  A few illustrations...
>
> 1) If one had to give up a feature in order to get another, many would
> put general array indexing early on the chopping block. Between fixed
> and dynamic length arrays (and in particular bounded/unbounded
> strings), for example, Ada forces one to change from native array
> syntax to a procedural interface that hides re-sizing details.  Ada
> programmers I know would happily give up general index ranges in order
> to get dynamically resizing arrays with native syntax---at least those
> who have worked in other languages where such are available.

What kinds of projects do those Ada programmers work on? Is performance
a critical requirement? Resizable arrays always provide reduced
performance over fixed size arrays. Even worse, the performance
penalties are driven by the data. This makes successful critical timing
consistency impossible when using resizable arrays.

Ada provides three kinds of strings. Those three kinds are not present
merely for convenience. Each type of string represents a trade-off
between efficiency and flexibility. The default fixed string type is
the most efficient and least flexible.

>
> 2) General integer ranges for array indices are a half-hearted---at the
> margins---compromise wrt fully general arrays allowing any type as an
> index.  In other words, if you put
> (A) 1-based arrays,
> (B) general discrete type array indices, and
> (C) fully general arrays
> on a conceptual scale, (B) lies _much_ closer to (A) than to (C).

I disagree completely with what you say. General index types are
popular with scripting languages and a few other new languages.
None of those languages concern them selves with execution efficiency
to the extent that Ada does. None of those languages are useful in
hard real-time systems.

Ada language features have not been added merely for the convenience
of the programmer. The Ada language started with genuine design
requirements. Subsequent refinements of the language have not
abandoned the direction and philosophy expressed through those
requirements.

If you want to use a scripting language such as perl, then use perl.
Do not expect all languages to be scripting languages.

>
> 3) The wonder of Ada is the predicatable, orthogonal way that syntax
> and semantics correspond.  But we have just been observing that general
> integer array indexing leads to a not-very-predictable behavior in
> combination with slicing and catenation. If all arrays were 1-based,
> the problem could not have occurred.  Hence this unhappy confluence of
> features, by conflicting with Ada's philosophy, is at the semantic
> margins of the language.  It ought to be avoided if the goal is code
> with obvious meaning. E.g. after I re-coded my original example
> "properly" with 'First and 'Range to make its behavior correct, I
> quickly added a comment, -- 'First is not always 1.  How marginally
> Ada!

In fact the Ada approach is always predictable with regard to slicing
and concatenation. Your experience appears to be rooted in languages
with a different concept of type. For instance, C and C++ have no
array types. One can define an array in each of those languages, but
there is no type tag associated with such an array. One cannot look
up the name of an array type in a C or C++ symbol table.

Ada provides array types. Ada also provides subtypes. Every instance
of an unconstrained array type is constrained. Likewise, every
instance of an unconstrained array type represents a subtype of the
parent unconstrained array type.

All these bits of information are necessary for understanding Ada array
slicing and concatenation. Every Ada array and array slice has a set of
index values. Slicing an array does not "convert" the index values from
their original set to an equivalent size set beginning at 1, 0, or any
other value you might choose. The slice forms a view into the array
from which the slice is taken. It is quite logical, and not the least
marginal, that this view should maintain consistency in its
representation.  When concatenating two arrays, the language must
join the sets of indices in a continuous set of values. Your original
posting marveled that the joining of an empty array with a slice
not starting at 1 resulted in an array whose 'First value was the
same as the slice. Concatenating array A whose indices represent
the null set with array B whose indices represent some non-null set
should always result in an array whose indices are a non-null set.
Moreover, the most efficient and logical merging of the two sets
results in a set idenitcal to the indices of B.

Jim Rogers

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

>>Likewise, a computer might surprise us in suggesting that our
>>fine mathematically thought-out program doesn't quite behave exactly
>>as we thought, because of the naughty computer thingy and its
>>quirks.
> 
> 
> You are mixing inadequate and inconsistent models.

The world (our problem domain) *is* inconsistent,
otherwise, if it were consistent, how could we possibly
know what inconsistency is? We can agree on someting.
(As I said, HALT is the limit, I think we cannot even formally
decide, mathematically, whether consistency is consistent.)

A computer, being a real world item, has a good chance of
being whatever it is, there is no complete knowledge of a
computer's consistency. Mathematically consistent programs
can be helpful when the set of preferred consistency rules
is both specified and relates to the program.

>>We have
>> lo, hi: arrays -> I,
>> item: arrays x I -> values

> What about hi >= lo?

No problem, as hi, lo: arrays -> I are just functions.
(These are "minimal" assumptions, really.)

> What about handling Some_Array (Some_Array'First)
> failure?

Same as handling any indexing failure. But different from, and
possibly unrelated to, elaborating the range that is established by
a pair of index values.

> Note that it fails not because there is no A'First, but because
> the index is wrong? How so? It exists, but wrong!

A'First for an empty array isn't wrong at all, it is just a value
from the set of index values.
An array is associated with two particular values from the set
of index values. Then there is a function,
  item: arrays x I -> values,
defined for some (array, index) pairs, undefined for others.

> Then what would you do
> with modular and enumeration types?

Use subtypes. Computers are finite, so are types. So I say what
I want in Ada, another value to mark off the end. Not nice but
practical. (Real types exist inside computers, computed in finite
time. Mathematical types can exist as "infinite" type look-alikes
as in Haskell.)


>>>Better ADT is what Ada needs.
>>
>>Is Ada a Must for you?
> 
> 
> Sure. C++ shortens my life!

Then don't use C++. But there are practical alternatives to
C++ if you can give up some pieces of Ada.

> Like C++? (:-))

Like many.

> What I want is freedom.

Then choose not use empty arrays, or test for 'length = 0, or
build your own array abstraction, use use Ada.Containers.Vectors,
.... or do not use Ada.

> I don't want the compiler to decide for me whether
> there must be "off" values or not.

The compiler does not force you to use "off" index values,
it forces you to use Ada. When this limit is not o.K., ...


> The concept of array must be consistent
> with index types having no "off" values, like ring buffers.

I see that you like this view, and I see that many programmers and language
designers use indexing with off-bounds index values.

Some languages can do without index manipulation, and with empty sets.
Consider this SETL/2 example:

program automatic_indexes;

        Couples := { ["Frank", "Lisa"],
                     ["Joe", "Nancy"],
                     ["Jack", "John"],
                     ["Jack", "Lisa"] };

        selpuoC := {[x, y]: [y, x] in Couples};


        print("Just the Two of Us: ",
              {[x, y]: y = Couples(x) | #Couples{x} = 1 and #selpuoC{y} = 1});

        for person in { x: x in domain Couples | #Couples{x} = 1}
                   +  { y: y in range  Couples | #selpuoC{y} = 1}
        loop
                print(person, " says, 'One is enough for me!'");
        end loop;

end automatic_indexes;


 [Eiffel solution]

> This is incompatible with modular and enumeration types. It also has a
> distributed overhead. You either will have no by-copy types or will need to
> store NONE where one bit would otherwise be enough. Then making a hash
> function you'll need to explicitly test for NONE etc.

Are you sure you know these things about Eiffel, as opposed to something
that you think must must be the case with Eiffel?


> Sure. And in mathematics there is no problem to write:
> 
>    forall x in X

Like in many programming languages.

> I in A'First..A'Last that A'Range is 1) ordered, 2) has the lower and upper
> bounds, 3) these bounds belong to the array. These assumptions are not
> always required. Moreover, for some arrays they are wrong.

A range with A'Last > A'First is not wrong, I see that you don't
like it. It seems you want to restrict Ada by disallowing
programmers to freely use this widespread idiom for expressing
empty arrays, because it violates your preferences for some
consistency of ordered indexing, right?

Re: Surprise in array concatenation

[Georg Bauhaus]

Georg Bauhaus wrote:

> A range with A'Last > A'First is not wrong,
A'First > A'Last

Re: Surprise in array concatenation

[Jeffrey R. Carter]

Gene wrote:

> -- 'First is not always 1.  How marginally
> Ada!

'First is not always 1 (or 0, or X) is a basic concept in Ada. It's only if you 
don't know, or forget, this, and assume the behavior you learned in lesser 
languages, that you have problems.

I came to Ada from Pascal, so I was used to the lower bound not being fixed, and 
the discovery of attributes simply made life easier. Had I come directly from 
FORTRAN, for example, I might have had more difficulty, because it would have 
involved grasping both the idea of user-defined lower bounds and the idea of 
attributes.

-- 
Jeff Carter
"I'm particularly glad that these lovely children were
here today to hear that speech. Not only was it authentic
frontier gibberish, it expressed a courage little seen
in this day and age."
Blazing Saddles
88

Re: Surprise in array concatenation

[Robert A Duff]

tmoran@acm.org writes:

> >I completely agree with the marginal utility of other-than-1 least
> >array indices.
>    I strongly disagree.  While not dirt common, other 'firsts in
> declarations do occur.  -n ..  +n comes to mind.

Heh?  "Marginal utility" means the same as "not dirt common"!

My suggestion was that the language should _allow_ the programmer to fix
the lower bound for an array type.  And/or the upper bound.  In Ada, you
can fix both or neither -- but not one or the other.

Anyway, you'd still be allowed to do your -n..+n thing, in the rare
cases where that's useful.

>...  If you are going to
> handle slices, you have to assume 'first /= 1 anyway,...

No, I don't.  ;-)

Slices should slide to the lower bound.  The Ada rule breaks
abstraction:

    procedure P(X: String) is
    begin
        ...
    end P;

    Y: String := "Hello, world!";

    P(Y(3..4));

Inside the body of P, X is just a String -- we don't (or shouldn't) know
that it's a substring of Y.  So we can't possibly make any sense (inside
P) of the fact that X'First = 3.  Index 3 from what?

If I ran the circus, X'First would be 1.

>... so you're not losing
> much by allowing it in declarations.  Using 'first instead of 1 also makes
> it simple to change between integer and enumeration value indexes.  The
> way Ada.Text_IO.Get_Line (et al) returns Last, which works even if you
> passed it a slice, has surely prevented many an error as compared to other
> languages which would likely return a count (since "all arrays start at
> x") and depend on the programmer to do any arithmetic needed to turn it
> into an index.  And if you started all arrays at 1,

I wouldn't insist on starting _all_ arrays at 1, but I think it makes
sense for _many_ arrays, including String.

>... you probably wouldn't
> allow the idiom
>   subtype cards is string(1 .. 80);
>   subtype sequence is range 73 .. 80;
>   ...
>   if card(sequence) = (sequence=>' ') then

Why not?  In Ada, "=" doesn't care about the bounds -- just the length.

- Bob

Re: Surprise in array concatenation

[Robert A Duff]

"Jeffrey R. Carter" <spam@spam.com> writes:

> Gene wrote:
> 
> > -- 'First is not always 1.  How marginally
> > Ada!
> 
> 'First is not always 1 (or 0, or X) is a basic concept in Ada. It's only
> if you don't know, or forget, this, and assume the behavior you learned
> in lesser languages, that you have problems.
> 
> I came to Ada from Pascal, so I was used to the lower bound not being
> fixed,

Heh?  The lower (and upper!) bound of all array types in Pascal is
fixed.  And it has to be fixed at a static value.  Every array object of
a given type has the same fixed bounds.

(Well, some version of Pascal added conformant arrays, which relaxed
this requirement for formal parameters.)

It's true that the lower bound doesn't have to be 1, or any other
particular value, but it has to be static, and it is fixed for that
array type.

I don't think anybody would suggest that _all_ arrays in Ada must start
at 1.  That would preclude arrays indexed by enumeration types, which
don't have a concept of 1.

>... and the discovery of attributes simply made life easier. Had I
> come directly from FORTRAN, for example, I might have had more
> difficulty, because it would have involved grasping both the idea of
> user-defined lower bounds and the idea of attributes.

- Bob

Re: Surprise in array concatenation

[Robert A Duff]

"jimmaureenrogers@worldnet.att.net" <jimmaureenrogers@worldnet.att.net> writes:

>...Concatenating array A whose indices represent
> the null set with array B whose indices represent some non-null set
> should always result in an array whose indices are a non-null set.

Agreed.

> Moreover, the most efficient and logical merging of the two sets
> results in a set idenitcal to the indices of B.

I don't agree that's most logical, but I suppose that's somewhat a
matter of taste.

But the Ada rule is _certainly_ not the "most efficient"!

If all Strings start at 1, then we reduce the size of the array dope by
4 bytes.  If the average String length in your program is, say, 20
bytes, you're saving 4 bytes for every 24, or about 17% of the memory
use, which is substantial.  Saving memory generally speed up programs
due to cache effects.

It's really annoying to me that the compiler stores zillions of copies
of the number 1 in memory (one copy for each String object), just
because some oddball String _might_ start at other than 1.

Furthermore, bounds checking would be much faster, because there would
be no need to load the lower-bound from memory.  Memory loads are often
slow on modern machines.

Furthermore, consider the code generated for 'Length:  In Ada, it's
something like:

    if X'First <= X'Last then
        X'Last - X'First + 1
    else
        0
    end if;

If X'First were known to be always 1, it would be:

    X'Last

If X'First were known to be always 17, it would be:

    X'Last - 16

These latter are branch-free code sequences.  Branches are often slow on
modern machines.

- Bob

Re: Surprise in array concatenation

[Larry Kilgallen]

In article <wcck6hvnpsm.fsf@shell01.TheWorld.com>, Robert A Duff <bobduff@shell01.TheWorld.com> writes:
> "Jeffrey R. Carter" <spam@spam.com> writes:
> 
>> Gene wrote:
>> 
>> > -- 'First is not always 1.  How marginally
>> > Ada!
>> 
>> 'First is not always 1 (or 0, or X) is a basic concept in Ada. It's only
>> if you don't know, or forget, this, and assume the behavior you learned
>> in lesser languages, that you have problems.
>> 
>> I came to Ada from Pascal, so I was used to the lower bound not being
>> fixed,
> 
> Heh?  The lower (and upper!) bound of all array types in Pascal is
> fixed.  And it has to be fixed at a static value.  Every array object of
> a given type has the same fixed bounds.
> 
> (Well, some version of Pascal added conformant arrays, which relaxed
> this requirement for formal parameters.)

That is true, in the same sense that some versions of Ada added
modular types -- they were added to the standard.

Re: Surprise in array concatenation

[Robert A Duff]

Kilgallen@SpamCop.net (Larry Kilgallen) writes:

> In article <wcck6hvnpsm.fsf@shell01.TheWorld.com>, Robert A Duff <bobduff@shell01.TheWorld.com> writes:
> > "Jeffrey R. Carter" <spam@spam.com> writes:
> > 
> >> Gene wrote:
> >> 
> >> > -- 'First is not always 1.  How marginally
> >> > Ada!
> >> 
> >> 'First is not always 1 (or 0, or X) is a basic concept in Ada. It's only
> >> if you don't know, or forget, this, and assume the behavior you learned
> >> in lesser languages, that you have problems.
> >> 
> >> I came to Ada from Pascal, so I was used to the lower bound not being
> >> fixed,
> > 
> > Heh?  The lower (and upper!) bound of all array types in Pascal is
> > fixed.  And it has to be fixed at a static value.  Every array object of
> > a given type has the same fixed bounds.
> > 
> > (Well, some version of Pascal added conformant arrays, which relaxed
> > this requirement for formal parameters.)
> 
> That is true, in the same sense that some versions of Ada added
> modular types -- they were added to the standard.

Right.  I was being vague because I couldn't remember whether conformant
arrays were added in the first ISO Pascal standard, or the Extended
Pascal version.  I also can't remember the status of Extended Pascal
(was it ever officially blessed by ISO?).  Do you know?

Conformant arrays were certainly not part of the original Pascal as
documented in Jensen and Wirth's book, "Pascal User Manual and Report".
And conformant arrays are only for parameters -- not normal variables,
record components, heap objects, etc.  Correct?

- Bob

Re: Surprise in array concatenation

[Robert A Duff]

Jean-Pierre Rosen <rosen@adalog.fr> writes:

> Robert A Duff a �crit :
> > Why would you want an unconstrained array indexed by enumeration type?
> > And why would you want an empty array if the array type is constrained?
> >
> I do that all the time, especially in ASIS programming. You may have
> arrays indexed with subranges of declaration_kinds for example.

Really?  I can see why you might have:

    type Declaration_Kind is (This, That, Mumble, Dumble);
    subtype My_Kind is Declaration_Kind range This..That;
    subtype Your_Kind is Declaration_Kind range Mumble..Dumble;

    type A1 is array(My_Kind) of Blah;
    type A2 is array(Your_Kind) of Glorp;

But do you really do this:

    type A is array(Declaration_Kind range <>) of Something;
    subtype A1 is A(My_Kind);
    subtype A2 is A(Your_Kind);

"all the time"?  Nothing wrong with it; I just think the former case
would be by far more common.

And do you create *empty* arrays indexed by enums?  All the time?  ;-)

My empty arrays are usually indexed by signed integer types.

- Bob

Re: Surprise in array concatenation

[tmoran]

> Heh?  "Marginal utility" means the same as "not dirt common"!
Exceptional intelligence is not "dirt common", but I believe it is
of more than marginal utility.

Re: Surprise in array concatenation

[Pascal Obry]

Gene a �crit :
> quickly added a comment, -- 'First is not always 1.  How marginally
> Ada!

Maybe because Ada is good at modeling the problem-space and that arrays
there do not necessary have numerical index and when it is the case they
don't eventually start at 1. Others have pointed out lot of problems
that are better modeled with non numerical indexes or indexes not
starting at 1.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Mon, 05 Sep 2005 20:20:19 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
>>>Likewise, a computer might surprise us in suggesting that our
>>>fine mathematically thought-out program doesn't quite behave exactly
>>>as we thought, because of the naughty computer thingy and its
>>>quirks.
>> 
>> You are mixing inadequate and inconsistent models.
> 
> The world (our problem domain) *is* inconsistent,
> otherwise, if it were consistent, how could we possibly
> know what inconsistency is?

Inconsistency means that you can derive P and ~P. So far, there were no
evidences that the world doesn't obey logic.

> We can agree on someting.
> (As I said, HALT is the limit, I think we cannot even formally
> decide, mathematically, whether consistency is consistent.)

You cannot express the sentence above in a formal language. Which does not
imply its undecidability. Only proper propositions can be decidable or not.

> A computer, being a real world item, has a good chance of
> being whatever it is, there is no complete knowledge of a
> computer's consistency. Mathematically consistent programs
> can be helpful when the set of preferred consistency rules
> is both specified and relates to the program.

You better show a case where [mathematically] inconsistent program could be
usable. [Windows does not count! (:-))]

>>>We have
>>> lo, hi: arrays -> I,
>>> item: arrays x I -> values
> 
>> What about hi >= lo?
> 
> No problem, as hi, lo: arrays -> I are just functions.
> (These are "minimal" assumptions, really.)

If hi and lo are just arbitrary values then take 3.456 and 1. They are
easier to calculate.

hi and lo are bounds, as such they have definite contracts. They cannot be
"just" values. Once you formulate the contract, it will be pretty easy to
show whether it is consistent = no any properly constructed array object
violates the contract. It is not rocket science, really...

>> Then what would you do
>> with modular and enumeration types?
> 
> Use subtypes. Computers are finite, so are types.

I don't know what a finite type is. You might mean the domain set of a
type. Then you are wrong, the sets of values of Ada's universal types
aren't finite. You can have a type which values comprise an uncountable set
of any cardinality [I cannot tell for unreachable cardinals, though (:-))]
It is not the same as to be able enumerate all these values in one program!
There is no any limitation on how bit patterns are mapped to the type
values. I can have 0000->Pi, 0001->e, 0010-><whatsoever>.

>> What I want is freedom.
> 
> Then choose not use empty arrays, or test for 'length = 0, or
> build your own array abstraction, use use Ada.Containers.Vectors,
> .... or do not use Ada.

Ah, that's your definition of freedom... (:-))

>> I don't want the compiler to decide for me whether
>> there must be "off" values or not.
> 
> The compiler does not force you to use "off" index values,
> it forces you to use Ada. When this limit is not o.K., ...

It sounds as if the whole language design would collapse if empty arrays
were constructed otherwise [properly.] Do you really believe in that?

>> I in A'First..A'Last that A'Range is 1) ordered, 2) has the lower and upper
>> bounds, 3) these bounds belong to the array. These assumptions are not
>> always required. Moreover, for some arrays they are wrong.
> 
> A range with A'Last > A'First is not wrong, I see that you don't
> like it. It seems you want to restrict Ada by disallowing
> programmers to freely use this widespread idiom for expressing
> empty arrays, because it violates your preferences for some
> consistency of ordered indexing, right?

Did I say that?

The idiom you trying to push for has a clear application area. This area is
*narrower* than one of the array idiom.

Then with "off"-values or without them, A'Last shall *not* be less than
A'First. Presently the case A'Last < A'First is used to indicate that there
is no bounds. It is a quite silly way to handle errors. Instead of an
immediate response you return nonsensical values in hope that inconsistency
will be handled [or not] later. It is like to make Positive / 0 = -1, if
you will use it, you'll get Constraint_Error, if you won't, then, let's
call it a useful idiom of dividing to zero as opposed to impractical
mathematical definition...

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On 05 Sep 2005 18:13:16 -0400, Robert A Duff wrote:

> But the Ada rule is _certainly_ not the "most efficient"!
> 
> If all Strings start at 1, then we reduce the size of the array dope by
> 4 bytes.  If the average String length in your program is, say, 20
> bytes, you're saving 4 bytes for every 24, or about 17% of the memory
> use, which is substantial.  Saving memory generally speed up programs
> due to cache effects.
>
> It's really annoying to me that the compiler stores zillions of copies
> of the number 1 in memory (one copy for each String object), just
> because some oddball String _might_ start at other than 1.
> 
> Furthermore, bounds checking would be much faster, because there would
> be no need to load the lower-bound from memory.  Memory loads are often
> slow on modern machines.
> 
> Furthermore, consider the code generated for 'Length:  In Ada, it's
> something like:
> 
>     if X'First <= X'Last then
>         X'Last - X'First + 1
>     else
>         0
>     end if;
> 
> If X'First were known to be always 1, it would be:
> 
>     X'Last
> 
> If X'First were known to be always 17, it would be:
> 
>     X'Last - 16
> 
> These latter are branch-free code sequences.  Branches are often slow on
> modern machines.

Right. Here is another example to the list: almost any binary operation on
strings should do:

J := B'First;
for I in A'Range loop
   do something to A(I) with B(J);
   J := J + 1; -- Can this overflow at the end of loop? (:-))
end loop;

or its equivalent. It would be much less pain if either A'First = B'First
(for some arrays, as a part of the contract), or at least array renaming
worked properly (could shift the bounds.)

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Jean-Pierre Rosen]

Robert A Duff a �crit :
> Jean-Pierre Rosen <rosen@adalog.fr> writes:
> 
> 
>>Robert A Duff a �crit :
> Really?  I can see why you might have:
> 
>     type Declaration_Kind is (This, That, Mumble, Dumble);
>     subtype My_Kind is Declaration_Kind range This..That;
>     subtype Your_Kind is Declaration_Kind range Mumble..Dumble;
> 
>     type A1 is array(My_Kind) of Blah;
>     type A2 is array(Your_Kind) of Glorp;
> 
> But do you really do this:
> 
>     type A is array(Declaration_Kind range <>) of Something;
>     subtype A1 is A(My_Kind);
>     subtype A2 is A(Your_Kind);
Not that often, but it may happen. Especially if you  have services like:
    procedure do_something (On : A);
and want to be able to call it on A1 or A2.

> "all the time"?  Nothing wrong with it; I just think the former case
> would be by far more common.
More common, yes. But the other do happen.

> And do you create *empty* arrays indexed by enums?  All the time?  ;-)
Might happen as default values for the above do_something procedure.
Not common, but not impossible.

-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Surprise in array concatenation

[Georg Bauhaus]

Robert A Duff wrote:

> Slices should slide to the lower bound.  The Ada rule breaks
> abstraction:

I had thought that 'First and 'Last etc. are there just for
building an abstraction, not to break one. It might well be
that using 'First etc breaks people's habits or doesn't meet their
assumptions (rather concrete assumptions about string bounds?).
But how does it break the abstraction called String?

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

> Inconsistency means that you can derive P and ~P.

It's you who says this, stipulating the universal applicability
of binary logic. How can I justify that I can only derive
P from {}, and not ~P? Because it turns out to be useful.
Not because the derivation works.


> So far, there were no
> evidences that the world doesn't obey logic.

Tons. Starting at those things for which there is no explanation.
But we don't have a proof that the world is (binary) logical.
Wittgestein has made an attempt, but (of course) he had to give
up (shut up, in a sense, using an abbreviation of his own words).

BTW, people can say P now and ~P at another time, and this causes
very little mental stress.



>>We can agree on someting.
>>(As I said, HALT is the limit, I think we cannot even formally
>>decide, mathematically, whether consistency is consistent.)
> 
> 
> You cannot express the sentence above in a formal language. Which does not
> imply its undecidability. Only proper propositions can be decidable or not.

If the world is logical, as you claim, then our sentences
cannot be illogical, thus our sentences must be proper
propositions, thus decidable.


> You better show a case where [mathematically] inconsistent program could be
> usable. [Windows does not count! (:-))]

Inconsistent with what? Empty arrays having A'First > A'Last
are ubiquituous; I understand you find this inconsistent.

>>>>We have
>>>>lo, hi: arrays -> I,

> If hi and lo are just arbitrary values

I said, hi and lo are functions. I didn't say that they are
arbitrary.


> hi and lo are bounds, as such they have definite contracts. They cannot be
> "just" values. Once you formulate the contract, it will be pretty easy to
> show whether it is consistent = no any properly constructed array object
> violates the contract. It is not rocket science, really...

You have to know the contract of 'First etc. I see they can be surprising,
but I don't see a violation of Ada's well working contracts in
'First > 'Last.


>>Use subtypes. Computers are finite, so are types.
> 
> 
> I don't know what a finite type is. You might mean the domain set of a
> type. Then you are wrong, the sets of values of Ada's universal types
> aren't finite.

Ada's types in a real computer program are finite, no matter what.
Any value in an Ada program is finite due to de facto capacity
constraints.

> You can have a type which values comprise an uncountable set
> of any cardinality [I cannot tell for unreachable cardinals, though (:-))]

I very much doubt that any executable program has ever succeeded in
exstablishing a type representing an uncountable set, other than
symbolically, or by turning it into a countable finite thing, by way
of lazy evaluation.

> It is not the same as to be able enumerate all these values in one program!

For any infinite type,
there needs to be an algorithm or a declaration capable of constructing
the values in the type. For infinite types, the algorithms and declarations
don't exist.

> There is no any limitation on how bit patterns are mapped to the type
> values.

A limit on which items can be mapped to bit patterns is storage capacity.
Storage capacity is a worldly item << infinity.


> I can have 0000->Pi, 0001->e, 0010-><whatsoever>.

I did answer this.

>>>What I want is freedom.
>>
>>Then choose not use empty arrays, or test for 'length = 0, or
>>build your own array abstraction, use use Ada.Containers.Vectors,
>>.... or do not use Ada.
> 
> 
> Ah, that's your definition of freedom... (:-))

I won't ask language designers to rebuild their language
just because I prefer a certain, allegedly more consistent,
design of arrays, preferred by some in some algorithms,
not preferred by others.

 Is it so much better to introduce ubiquituous case distinctions
('Length = 0?) in every (sub)array algorithm just because there happens
to be a mathematical property that may be applied to indexes, forcing
A'First > A'Last to be a bad thing?


> It sounds as if the whole language design would collapse if empty arrays
> were constructed otherwise [properly.] Do you really believe in that?

Sure a lot of algorithms will collapse if they have to adopt your
consistency rules. If you dislike Ada's arrays, that's o.K..

If you claim to have found the only true rule stating what kind of arrays
are consistent with the rule and what kind isn't, then this sounds
like the RM has had inconsistent arrays for a number of years now.
Shouldn't there be an article somewhere that points out the erratic
definitions of array bounds in Ada 83, Ada 95, and the upcoming Ada 05?


> Did I say that?

If you insist on A'First <= A'Last, then it sounds like you want
to restrict Ada's attributes.


> The idiom you trying to push for has a clear application area. This area is
> *narrower* than one of the array idiom.

What is "_the_ array idiom"?

The few array types in some languages that I know don't seem to
have a problem with 

  "The Last Ones Shall be First"



> Then with "off"-values or without them, A'Last shall *not* be less than
> A'First.

Should this sentence start with "Thou shalst not do what everyone else
does"?


> Presently the case A'Last < A'First is used to indicate that there
> is no bounds.

That's wrong, in that it just indicates that A'Last < A'First yields
an empty range.

> It is a quite silly way to handle errors. Instead of an
> immediate response you return nonsensical values

What nonsensical values are returned in text like "3 .. 1"?

result := default_value;
for k in 3 .. 1 loop
 result := x(k);
end loop;

How could this be improved using

if x'length = 0 then
  result := default_value;
else
  for k in 3 .. 1 loop
   result := x(k);
  end loop;
end if;

Re: Surprise in array concatenation

[Bob Spooner]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wccoe77nq3l.fsf@shell01.TheWorld.com...
> tmoran@acm.org writes:
>
snip...
>
> Slices should slide to the lower bound.  The Ada rule breaks
> abstraction:

So if I pass a subprogram a slice of an array indexed by an enumeration type
then the mapping of the values to the enumeration type should change?

>
>     procedure P(X: String) is
>     begin
>         ...
>     end P;
>
>     Y: String := "Hello, world!";
>
>     P(Y(3..4));
>
> Inside the body of P, X is just a String -- we don't (or shouldn't) know
> that it's a substring of Y.  So we can't possibly make any sense (inside
> P) of the fact that X'First = 3.  Index 3 from what?
>
> If I ran the circus, X'First would be 1.
>

But that would make String a special case of an array if you allow other
arrays to start with a value other than the first value of the index type.
Yet another thing we would have to remember...

>
> I wouldn't insist on starting _all_ arrays at 1, but I think it makes
> sense for _many_ arrays, including String.
>

Many other special cases to remember as well?

snip...
>
> - Bob

In my view, the abstraction that is important here is that of the array
rather than that of the subprogram seeing a slice as always beginning with
Index'first. The characteristics of the abstraction of an array should be as
consistent in Ada as possible. While having the first value of a String and
whatever types of arrays you think are appropriate always be the first value
of the index type would save some memory and computation time, Ada is one of
the few languages where the array is a powerful and safe abstraction. It is
therefore much more useful than in other languages, making consistency of
behavior all the more important and, I think, worth the price in
computation. To make arrays robust and safe in C type languages, for
instance, involves adding a lot more baggage than an extra integer value and
a little bit of computation done transparently by the compiler.

Bob

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Tue, 06 Sep 2005 13:52:53 +0200, Georg Bauhaus wrote:

> If the world is logical, as you claim, then our sentences
> cannot be illogical, thus our sentences must be proper
> propositions, thus decidable.

OK, see mathematical type theory (starting for Russel & Whitehead)

>> hi and lo are bounds, as such they have definite contracts. They cannot be
>> "just" values. Once you formulate the contract, it will be pretty easy to
>> show whether it is consistent = no any properly constructed array object
>> violates the contract. It is not rocket science, really...
> 
> You have to know the contract of 'First etc. I see they can be surprising,
> but I don't see a violation of Ada's well working contracts in
> 'First > 'Last.

The violation is in inability to construct empty arrays and ranges for some
types.

>>>Use subtypes. Computers are finite, so are types.
>> 
>> I don't know what a finite type is. You might mean the domain set of a
>> type. Then you are wrong, the sets of values of Ada's universal types
>> aren't finite.
> 
> Ada's types in a real computer program are finite, no matter what.
> Any value in an Ada program is finite due to de facto capacity
> constraints.

That becomes funny. What is a "finite" value? Is 1/3 finite? What about
0.1? (:-))

>> You can have a type which values comprise an uncountable set
>> of any cardinality [I cannot tell for unreachable cardinals, though (:-))]
> 
> I very much doubt that any executable program has ever succeeded in
> exstablishing a type representing an uncountable set, other than
> symbolically, or by turning it into a countable finite thing, by way
> of lazy evaluation.

LOL! Any program represents anything symbolically. Do you really believe
that 1 is *the* 1? Did you see a label "made in Heaven" on it? (:-))

>> It is not the same as to be able enumerate all these values in one program!
> 
> For any infinite type,
> there needs to be an algorithm or a declaration capable of constructing
> the values in the type. For infinite types, the algorithms and declarations
> don't exist.

Surely they do:

type Infinite is (Infinity);

>  Is it so much better to introduce ubiquituous case distinctions
> ('Length = 0?) in every (sub)array algorithm just because there happens
> to be a mathematical property that may be applied to indexes, forcing
> A'First > A'Last to be a bad thing?

Yes. There is A'Range, which is legal, consistent and has no overhead of
testing if A'First > A'Last.

>> Presently the case A'Last < A'First is used to indicate that there
>> is no bounds.
> 
> That's wrong, in that it just indicates that A'Last < A'First yields
> an empty range.

The way how the operation ".." is defined on its operands has nothing to do
with existence of bounds of the result.

>> It is a quite silly way to handle errors. Instead of an
>> immediate response you return nonsensical values
> 
> What nonsensical values are returned in text like "3 .. 1"?

Nothing. 3 and 1 are literals. A'First and A'Last aren't. You are mixing
expressions and their results. You might claim that it is another
unnecessary limitation imposed by mathematics, but it is still so. Of
course you could consider the sequence of characters "A'First..A'Last" be
equivalent to the sequence "A'Range". But fortunately Ada does not have
preprocessor!

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Robert A Duff]

tmoran@acm.org writes:

> > Heh?  "Marginal utility" means the same as "not dirt common"!
> Exceptional intelligence is not "dirt common", but I believe it is
> of more than marginal utility.

Ya got me there!  ;-)

Now, do you claim that the vast majority of empty Strings in Ada have
bounds 1..0 because programmer lack the exceptional intelligence it
would take to use 10..-100 and the like?  ;-)

Maybe 10..-100 is "not dirt common" because it has "marginal utility"!

- Bob

Re: Surprise in array concatenation

[Robert A Duff]

Georg Bauhaus <bauhaus@futureapps.de> writes:

> Robert A Duff wrote:
> 
> > Slices should slide to the lower bound.  The Ada rule breaks
> > abstraction:
> 
> I had thought that 'First and 'Last etc. are there just for
> building an abstraction, not to break one. It might well be
> that using 'First etc breaks people's habits or doesn't meet their
> assumptions (rather concrete assumptions about string bounds?).
> But how does it break the abstraction called String?

It breaks the abstraction called "subprogram".  As I showed in my
example, a procedure is handed an integer value (X'First), which is an
offset from the beginning of some object it knows nothing about, and
should know nothing about.

- Bob

Re: Surprise in array concatenation

[Robert A Duff]

"Bob Spooner" <rls19@psu.edu> writes:

> "Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
> news:wccoe77nq3l.fsf@shell01.TheWorld.com...
> > tmoran@acm.org writes:
> >
> snip...
> >
> > Slices should slide to the lower bound.  The Ada rule breaks
> > abstraction:
> 
> So if I pass a subprogram a slice of an array indexed by an enumeration type
> then the mapping of the values to the enumeration type should change?

No.  Let me explain more clearly what I meant:

In Ada, for a given array type, you can choose to fix both bounds, or
neither.  You cannot choose to fix the lower bound (for all objects of
the type), but not the upper bound.  I think the programmer should have
all four choices of fixing the bounds for an array type.

Part of the problem here is that "array" is a fairly low-level
abstraction.  When the index is an enumeration type, you're usually
using the array to represent a higher-level concept -- a "mapping" from
enum values to whatever.  When you declare something like String, on the
other hand, you're using the array to represent a different higher-level
concept -- a "sequence of characters".

"Sequence" and "mapping" are different (though related) concepts.

For a sequence, the indices have no inherent meaning -- they just
represent the order in which the elements appear in the sequence.
So I don't have trouble with the idea that slices of strings should
slide the bounds to 1..Length, whereas slices of a "mapping" sort of
array should not.

> >
> >     procedure P(X: String) is
> >     begin
> >         ...
> >     end P;
> >
> >     Y: String := "Hello, world!";
> >
> >     P(Y(3..4));
> >
> > Inside the body of P, X is just a String -- we don't (or shouldn't) know
> > that it's a substring of Y.  So we can't possibly make any sense (inside
> > P) of the fact that X'First = 3.  Index 3 from what?
> >
> > If I ran the circus, X'First would be 1.
> >
> 
> But that would make String a special case of an array if you allow other
> arrays to start with a value other than the first value of the index type.
> Yet another thing we would have to remember...

Yes, you have to remember, for each array type, whether the programmer
who wrote it intended it as a sequence or a mapping.  If a sequence, you
have to remember whether they fixed the lower bound at zero or one (or
they did some other weird thing, presumably for good reason).

> >
> > I wouldn't insist on starting _all_ arrays at 1, but I think it makes
> > sense for _many_ arrays, including String.
> >
> 
> Many other special cases to remember as well?

Yes, String is just one example where it makes sense to fix the lower
bound at 1.  Just like for a linked list, you have to remember whether
it's circular or null-terminated or ....

> snip...
> >
> > - Bob
> 
> In my view, the abstraction that is important here is that of the array
> rather than that of the subprogram seeing a slice as always beginning with
> Index'first. The characteristics of the abstraction of an array should be as
> consistent in Ada as possible.

As consistent as possible, but no more so.  ;-)

Enumerations and integers have much in common (that's why they're both
part of the class of discrete types).  But there are some important
differences, and I don't think you can get away with pretending they're
the same thing.

We should avoid _gratuitous_ inconsistencies.

>... While having the first value of a String and
> whatever types of arrays you think are appropriate always be the first value
> of the index type would save some memory and computation time,...

It would also reduce the number of bugs, I think.  (In particular, it
would prevent the confusion shown by the original example at the start
of this thread.)

We know how to write code that correctly handles all Strings, including
those with bounds 100..101, but Ada should be designed to prevent
accidental errors, even in the presence of fallible programmers.

>... Ada is one of
> the few languages where the array is a powerful and safe abstraction. It is
> therefore much more useful than in other languages, making consistency of
> behavior all the more important and, I think, worth the price in
> computation. To make arrays robust and safe in C type languages,...

I'm comparing Ada to an Ada-like language that is slightly different
(and, I claim, slightly better).  I'm not comparing it to C.  Ada arrays
are obviously far superior to C arrays in many ways!

>... for
> instance, involves adding a lot more baggage than an extra integer value and
> a little bit of computation done transparently by the compiler.

It's not always transparent.  For example, Dmitry pointed out the
example of a procedure that takes two arrays, and wants to perform some
operation on pairs of elements from each.  If you can assume that the
two arrays have equal lower bounds, the source code becomes much simpler
(and therefore less error prone).

I'll grant you that you must then remember which array types allow that
assumption.  But that's already an issue, since you can fix _both_
bounds in Ada (and you have to remember you did that).  For example:

    type Char_Mapping is array(Character) of Character;

    procedure P(X, Y: Character_Mapping) is
    begin
        for I in Character loop -- or, equivalently, Char_Mapping'Range
            Do_Something(X(I), Y(I));

I claim that's perfectly reasonable code to write -- yet it would be
wrong if Char_Mapping had not fixed the bounds (that is, if it said
"range <>").

- Bob

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:
> On Tue, 06 Sep 2005 13:52:53 +0200, Georg Bauhaus wrote:
> 
> 
>>If the world is logical, as you claim, then our sentences
>>cannot be illogical, thus our sentences must be proper
>>propositions, thus decidable.
> 
> 
> OK, see mathematical type theory (starting for Russel & Whitehead)

(And hope to see what? There is no way out, we can only agree
on something. Mathematics declares the swamp away
into which it is built, and says so. But there are swamps in the
problem domain.)


> The violation is in inability to construct empty arrays and ranges for some
> types.

Many kinds of structured data cannot be constructed
from Ada's types because of Ada's rules. How does this violate Ada's
contracts? A contract is not necessarily simple, nor without deliberately
chosen limitations.


> That becomes funny. What is a "finite" value? Is 1/3 finite? What about
> 0.1? (:-))

Earlier I said, forget about real numbers (from mathematics) in real
computers. 1/3 is indeed an example in binary computers: An interval
representing two real numbers close to 1/3 is not 1/3, and you cannot
hope to be computing using real numbers using the facilities of a
real computing machine. That is because almost all reals cannot be
represented in a finite computer. The problem cannot in general be solved
by using intervals. For example, try to approximate 1/3,
using the analog of my fly-hits-windshield example. That is,
represent all numbers required for such a computation, and compare them.


> LOL! Any program represents anything symbolically.

No, an executing program has an interpretation.
This makes "representing" have a meaning.

An explosion (triggered by a signal coming through a cable plugged
into a computer outlet) is itself not a symbol that stands for something
else. Neither is The signal. You can have a bit pattern standing for the
explosing, thus a symbol. But a symbol is finite, and there can only
be finitely many in any computation in a real computer.


> Do you really believe
> that 1 is *the* 1? Did you see a label "made in Heaven" on it? (:-))

Type Positive starts at 1 and ends with Positive'Last.
Ignoring the literal 1 distraction for the moment, the phrase "counting
the value-elements in type Positive" has meaning. In real Ada programs,
the count is always finite. Here is a type of cardinality 1:

> type Infinite is (Infinity);

This is a finite type, obviously. For it's intended meaning as
fooling us into believing that a real computer could represent
infinite types, see my fly-windshield example.

Similarly, (the set of) universal integers can only be finite inside
the computer. If your program is to pick just any, not one particular
that happens to be small enough, the limit is the same.


>>>Presently the case A'Last < A'First is used to indicate that there
>>>is no bounds.
>>
>>That's wrong, in that it just indicates that A'Last < A'First yields
>>an empty range.
> 
> 
> The way how the operation ".." is defined on its operands has nothing to do
> with existence of bounds of the result.

The index values A'First etc. of an array always exist.
The elements might not exist.
This is consistent with how Ada is defined, AFAICT, and it is consistent
with the definitions in programming languages, and libraries.
It is also considered useful by many.


>>>It is a quite silly way to handle errors. Instead of an
>>>immediate response you return nonsensical values
>>
>>What nonsensical values are returned in text like "3 .. 1"?
> 
> 
> Nothing. 3 and 1 are literals. A'First and A'Last aren't.

What nonsensical values are returned in text like "A'First .. A'Last"
when A'First > A'Last? The fact that A'First doesn't always refer
to an element is not different from the fact that A'Length / 2
doesn't always refer to an element, even when the array isn't empty.
Of what use is the test A'Length = 0 in this case?

Re: Surprise in array concatenation

[Jeffrey Carter]

Robert A Duff wrote:
> Heh?  The lower (and upper!) bound of all array types in Pascal is
> fixed.  And it has to be fixed at a static value.  Every array object of
> a given type has the same fixed bounds.

Poor word choice, I guess. I meant fixed by the language, as arrays in 
FORTRAN 66 have a lower bound fixed at 1, or arrays in C have a lower 
bound fixed at 0.

> It's true that the lower bound doesn't have to be 1, or any other
> particular value, but it has to be static, and it is fixed for that
> array type.

This is what I meant. Even in Ada, the lower bound of an array object is 
fixed at some value. But the lower bound is defined by the user, not by 
the language.

-- 
Jeffrey Carter
"Now go away or I shall taunt you a second time."
Monty Python and the Holy Grail
E-mail: jeffrey_r_carter-nr [commercial-at]
         raytheon [period | full stop] com

Re: Surprise in array concatenation

[Jeffrey Carter]

Robert A Duff wrote:
> 
> I'm comparing Ada to an Ada-like language that is slightly different
> (and, I claim, slightly better).  I'm not comparing it to C.  Ada arrays
> are obviously far superior to C arrays in many ways!

We've seen lots of hints about this language. When can we expect an 
informal overview? Also, what's it called? Duff?

-- 
Jeffrey Carter
"Now go away or I shall taunt you a second time."
Monty Python and the Holy Grail
E-mail: jeffrey_r_carter-nr [commercial-at]
         raytheon [period | full stop] com

Re: Surprise in array concatenation

[Robert A Duff]

Jeffrey Carter <spam@spam.com> writes:

> Robert A Duff wrote:
> > Heh?  The lower (and upper!) bound of all array types in Pascal is
> > fixed.  And it has to be fixed at a static value.  Every array object of
> > a given type has the same fixed bounds.
> 
> Poor word choice, I guess. I meant fixed by the language, as arrays in
> FORTRAN 66 have a lower bound fixed at 1, or arrays in C have a lower
> bound fixed at 0.
> 
> > It's true that the lower bound doesn't have to be 1, or any other
> > particular value, but it has to be static, and it is fixed for that
> > array type.
> 
> This is what I meant. Even in Ada, the lower bound of an array object is
> fixed at some value. But the lower bound is defined by the user, not by
> the language.

Ah, yes, I see.  Sorry for being unclear.  We need to be careful to say
"fixed for an object" vs. "fixed for a type" vs. "fixed for the whole
language" vs. various other possibilities.  ;-)

- Bob

Re: Surprise in array concatenation

[Robert A Duff]

Jeffrey Carter <spam@spam.com> writes:

> Robert A Duff wrote:
> > I'm comparing Ada to an Ada-like language that is slightly different
> > (and, I claim, slightly better).  I'm not comparing it to C.  Ada arrays
> > are obviously far superior to C arrays in many ways!
> 
> We've seen lots of hints about this language. When can we expect an
> informal overview? 

;-)

Unfortunately, I have to make a living, so I spend most of my time
writing compilers, static analysis tools, and other stuff like that.
I don't have time to really dig into language design these days.
But that doesn't stop me from griping about existing languages...
And I seem to gripe most about the ones I like best.

>...Also, what's it called? Duff?

Heh.  No, not "Duff".  ;-)

- Bob

Re: Surprise in array concatenation

[Robert A Duff]

Georg Bauhaus <bauhaus@futureapps.de> writes:

> What nonsensical values are returned in text like "A'First .. A'Last"
> when A'First > A'Last? The fact that A'First doesn't always refer
> to an element is not different from the fact that A'Length / 2
> doesn't always refer to an element, even when the array isn't empty.
> Of what use is the test A'Length = 0 in this case?

I agree.  The idea that A'Range should mean anything other than
A'First..A'Last seems like a bad idea.  Making A'First raise an
exception in the empty case is just a tripping hazard.

- Bob

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Tue, 06 Sep 2005 17:51:11 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
>> On Tue, 06 Sep 2005 13:52:53 +0200, Georg Bauhaus wrote:
>> 
>> The violation is in inability to construct empty arrays and ranges for some
>> types.
> 
> Many kinds of structured data cannot be constructed
> from Ada's types because of Ada's rules. How does this violate Ada's
> contracts?

If those aren't abstract types, it does.

> A contract is not necessarily simple, nor without deliberately
> chosen limitations.

Arbitrary limitations you mean. If an unbounded array type is not allowed
to have empty instances, then I expect to see that explicitly specified in
the contract. Soon Ada will have never-null access types. It also could
have never-empty arrays, but only this way.

>> That becomes funny. What is a "finite" value? Is 1/3 finite? What about
>> 0.1? (:-))
> 
> Earlier I said, forget about real numbers (from mathematics) in real
> computers. 1/3 is indeed an example in binary computers: An interval
> representing two real numbers close to 1/3 is not 1/3, and you cannot
> hope to be computing using real numbers using the facilities of a
> real computing machine. That is because almost all reals cannot be
> represented in a finite computer.

Nope. You confuse sets and elements. Any infinite subset of R (and R
itself) cannot be represented by *specifying its members*, because they
aren't countable. But any real and any finite real subset can. Further any
set can be represented by other means.

The domain set of a type need not to be countable. Neither you need to
count all values of a type in a given program. Did you ever use all
possible values of Integer? Nevertheless, you can do all sorts of quite
useful things without that. Now imagine that there are more integers than
that. Would it change anything for you? Not in a well designed program!

Note an important point of Ada design, as opposed to may other languages.
In Ada you specify what kind of values you are going to use. You say:

My_Integer is range 0..100;
   -- I don't care about other integers
My_Float is digits 8 range 0.0..100.0;
   -- I don't care about reals outside and in between

This is the right way to handle uncountable things without inventing any
new "computer" mathematics, where an element is not element and greater is
less.

>> LOL! Any program represents anything symbolically.
> 
> No, an executing program has an interpretation.
> This makes "representing" have a meaning.

And meaning is represented by what? (:-))

>> Do you really believe
>> that 1 is *the* 1? Did you see a label "made in Heaven" on it? (:-))
> 
> Type Positive starts at 1 and ends with Positive'Last.

... and it does this not symbolically, but physically by attaching a tiny
rubber thread to the Platonic number 1. Right? (:-))

> The fact that A'First doesn't always refer
> to an element is not different from the fact that A'Length / 2
> doesn't always refer to an element, even when the array isn't empty.
> Of what use is the test A'Length = 0 in this case?

A'Length and A'First have different types. Ada is a typed language!

You are trying to formulate some generic algorithm which does not work for
all index types. This is why it is so important to have a consistent model
of indexing and arrays. For an unordered [index] type X it is wrong to
assume that:

1. If L in X and U in X then there is always M in X between L and U
2. That M can be computed as (L+U)/2

Examples: hash map, variable length string map etc.

The contracts like 1&2 have be stated, not implied ones, if the application
have to rely on them.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Thierry Pirot]

Robert A Duff  writes:

> It breaks the abstraction called "subprogram".  As I showed in my
> example, a procedure is handed an integer value (X'First), which is an
> offset from the beginning of some object it knows nothing about, and
> should know nothing about.
> 
Do you mean : 
the calling subprogram knows about that object (of which a slice is passed) and 
the called  subprogram doesn't and shouldn't ? 

I tend to agree, however, if I got it right, I wonder : 
what about a recursive subprogram ? 
It is both the called and calling program.  

(This may indeed be a bit sophistic, 
actually I have found Ada's passing of slice bounds quite elegant 
within recursive subprograms 
--- wherein a string is conveniently rendered a recursive object by
Ada's slices, i.e. strings include slices which are (sub)strings).  

-- 
   Take it Easy          Don't worry            Be Happy

                           Thierry

�������o�o��������o�o��������o�o��������o�o��������o�o�������

Re: Surprise in array concatenation

[adaworks]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2181 bytes --]


"Jean-Pierre Rosen" <rosen@adalog.fr> wrote in message
news:j50hfd.l2a.ln@hunter.axlog.fr...
> Robert A Duff a �crit :
> > Why would you want an unconstrained array indexed by enumeration type?
> > And why would you want an empty array if the array type is constrained?
> >
> I do that all the time, especially in ASIS programming. You may have
> arrays indexed with subranges of declaration_kinds for example.
>
I recall a project where an Ada newbie, having learned about enumerated
types, created one enumerated type that was three pages long.  That is,
the number of values in the type was so great that it took three pages
of 11 X 14 standard printer paper to contain it.

This was a situtation where a good idea was carried to an absurd extreme.

When choosing to design an enumerated type, whether for array indexing,
or otherwise, there are a few simple rules I have set for myself.

         1)  Keep the number of values to a minimum,
         2)  Don't invent an enumerated type that creates global
              dependencies,
         3)  An enumerated type should not require constant addition of
              new values throughout the maintenance cycle.

I have heard it expressed at some software-oriented conferences that
enumerated types represent an old-fashioned way of thinking about
software design.  Some in the OO community believe that, because
enumerated types are not extensible, they actually thwart good OO
design.

Perhaps if enumerated types were extensible, something I suggested
during the Ada 95 process, they would be more acceptable in OOP.
However, I was persuaded that the complexity of Ada, should that
be done, would be so much greater that the idea was a bad one.

As to using real numbers for array indexing, I think there are better
alternatives. An array, one-dimensional or multi-dimensional, can
be represented in other ways than an array.   That is, there are other
structures that can be topologically homeomorphic to the array
structure which can be indexed via keys that are based on real
numbers, but which resolve, computationally, to discrete values.

The solution is left as an exercised to the student.

Richard Riehle

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:
> On Tue, 06 Sep 2005 17:51:11 +0200, Georg Bauhaus wrote:

>> How does this violate Ada's
>>contracts? >>A contract is not necessarily simple, nor without deliberately
>>chosen limitations.
> 
> Arbitrary limitations you mean.

I won't accuse the designers of Ada to have placed arbitrary
limitations on things.

> Nope. You confuse sets and elements. Any infinite subset of R (and R
> itself) cannot be represented by *specifying its members*, because they
> aren't countable.

> But any real

Almost no real number can be represented in a computer.

> and any finite real subset can.

Only a small subset of the subset of finite subsets of R
can be represented in a computer.

> The domain set of a type need not to be countable.

A computer type needs to be countable, otherwise you will run
into computability trouble.

> Did you ever use all
> possible values of Integer?

Yes. And if this hadn't happened before there were no wrap-around
stories.

 [more integers]
> Would it change anything for you? Not in a well designed program!

That's true of well designed A'First-based algorithms, too.

 
> Note an important point of Ada design, as opposed to may other languages.
> In Ada you specify what kind of values you are going to use. You say:
> 
> My_Integer is range 0..100;
>    -- I don't care about other integers
> My_Float is digits 8 range 0.0..100.0;
>    -- I don't care about reals outside and in between
> 
> This is the right way to handle uncountable things without inventing any
> new "computer" mathematics,

This is *precisely* where newly invented computing mathematics
is at work! The theory of floating point computations covers finite
approximations. It doesn't matter whether computations are done on
paper, or inside a computing machine. Computer mathematics provides
the theoretical tools for reasoning about numbers that are not reals,
but are used in computations that people would like to be performed in R,
but that cannot be performed in R.

Once again, if you think you can get by with a finite subset
of R, I suggest that you try the fly-hits-windshield example.
One value of the computation will be very, very small. The other value
will be comparatively large. Still you have to use both in the same
"formula". There is a good chance that both together simply won't fit
inside our computing machines. (Whether or not this matters in practice
is a different issue; here a finite approximation suffices. But forget
about real numbers.)


>>>LOL! Any program represents anything symbolically.
>>
>>No, an executing program has an interpretation.
>>This makes "representing" have a meaning.
> 
> 
> And meaning is represented by what? (:-))

As I said, HALT is the limit, and we have to agree on something.
You can of course argue that operational semantics is useless.


>>>Do you really believe
>>>that 1 is *the* 1? Did you see a label "made in Heaven" on it? (:-))
>>
>>Type Positive starts at 1 and ends with Positive'Last.

> ... and it does this not symbolically, but physically

yes.

> by attaching a tiny
> rubber thread to the Platonic number 1. Right? (:-))

no.

> You are trying to formulate some generic algorithm which does not work for
> all index types.

My algorithm should work for arrays, using properties of arrays.
A'First .. A'Last, where A'First > A'Last works well in loops.

When are you interested in computing the value half-way between
the ends of a (non-numeric) enumeration type, attempting to use
A'Length / 2?

> This is why it is so important to have a consistent model
> of indexing and arrays.

It is important to be consistently using the proper type of arrays
in algorithms made for this type of arrays.

> For an unordered [index] type X it is wrong to
> assume that:

Can there be an index type in Ada that isn't ordered?

> 1. If L in X and U in X then there is always M in X between L and U
> 2. That M can be computed as (L+U)/2

You can't usually compute M when X is an enumeration type.
Otherwise, if A'Length <= 1, then (L+U)/2 = 0 = M.
Thus, M can be computed but is not necessarily between L and U.
Anyone who thinks like Ada suggest (and Eiffel, and C++, and ...),
and who isn't mislead by DK's incessant subservience to some field
of mathematics, is _not_ surprised. */2 can be found in just about
and textbook on algorithms.

I'll concede that your ideas might be interesting for use in
a data structure that is not an array as people know it around
the globe.

> Examples: hash map, variable length string map etc.

Aha!
 

Re: Surprise in array concatenation

[Georg Bauhaus]

Georg Bauhaus wrote:

> You can't usually compute M when X is an enumeration type.
if not referring to its position in the ordering, then
using 'val in indexing.

Re: Surprise in array concatenation

[Robert A Duff]

<adaworks@sbcglobal.net> writes:

> "Jean-Pierre Rosen" <rosen@adalog.fr> wrote in message
> news:j50hfd.l2a.ln@hunter.axlog.fr...
> > Robert A Duff a �crit :
> > > Why would you want an unconstrained array indexed by enumeration type?
> > > And why would you want an empty array if the array type is constrained?
> > >
> > I do that all the time, especially in ASIS programming. You may have
> > arrays indexed with subranges of declaration_kinds for example.
> >
> I recall a project where an Ada newbie, having learned about enumerated
> types, created one enumerated type that was three pages long.  That is,
> the number of values in the type was so great that it took three pages
> of 11 X 14 standard printer paper to contain it.
> 
> This was a situtation where a good idea was carried to an absurd extreme.

What do you think of Ada 200X's type Wide_Wide_Character, which is an
enumeration type with upwards of a billion literals?  ;-)

If you actually wrote down the declaration in full, and printed it out,
it would be a stack of paper about 500 feet tall!

> Perhaps if enumerated types were extensible, something I suggested
> during the Ada 95 process, they would be more acceptable in OOP.
> However, I was persuaded that the complexity of Ada, should that
> be done, would be so much greater that the idea was a bad one.

I think the idea of extensible enums is a good one.
But it's tricky to get the rules just right.
One would want to retain the huge benefit of Ada's full-coverage
rules for case statements and aggregates.

- Bob

Re: Surprise in array concatenation

[Robert A Duff]

Thierry Pirot <thierrypirot@skynet.be> writes:

> Robert A Duff  writes:
> 
> > It breaks the abstraction called "subprogram".  As I showed in my
> > example, a procedure is handed an integer value (X'First), which is an
> > offset from the beginning of some object it knows nothing about, and
> > should know nothing about.
> > 
> Do you mean : 
> the calling subprogram knows about that object (of which a slice is passed) and 
> the called  subprogram doesn't and shouldn't ? 

Yes, that's exactly what I mean.

> I tend to agree, however, if I got it right, I wonder : 
> what about a recursive subprogram ? 
> It is both the called and calling program.  

Good point.  And what about the case where there's no recursion,
but the callee _should_ know about that array which was sliced?
The answer must be some sort of a "subarray" abstraction, which
carries with it the original array (or a reference to it).
I haven't thought this through...

> (This may indeed be a bit sophistic, 
> actually I have found Ada's passing of slice bounds quite elegant 
> within recursive subprograms 
> --- wherein a string is conveniently rendered a recursive object by
> Ada's slices, i.e. strings include slices which are (sub)strings).  

Yes, in rare cases, including the recursive case you mention, I have
found some use for slices that remember their bounds within the original
array.  But in _most_ cases, I've found it an error-prone annoyance.

>    Take it Easy          Don't worry            Be Happy

Good advice.  :-)

- Bob

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Wed, 07 Sep 2005 20:20:56 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
>> On Tue, 06 Sep 2005 17:51:11 +0200, Georg Bauhaus wrote:
> 
> Almost no real number can be represented in a computer.

OK, it is beaten to death. See Richard's paradox. Its free interpretation,
I quote J. E. Littlewood from memory, is: let there be integer numbers
which cannot be defined by sentences shorter than 12 words. "This set is
bounded and thus contains the lowest number N." This sentence defines N and
amazingly contains only 11 words.

>>>>Do you really believe
>>>>that 1 is *the* 1? Did you see a label "made in Heaven" on it? (:-))
>>>
>>>Type Positive starts at 1 and ends with Positive'Last.
> 
>> ... and it does this not symbolically, but physically
> 
> yes.
> 
>> by attaching a tiny
>> rubber thread to the Platonic number 1. Right? (:-))
> 
> no.

How else you could check if 1 really refers to the physical 1! Maybe some
scoundrel has reconnected all 1s in your computer to the physical 946.23,
while you slept! (:-))

>> You are trying to formulate some generic algorithm which does not work for
>> all index types.
> 
> My algorithm should work for arrays, using properties of arrays.
> A'First .. A'Last, where A'First > A'Last works well in loops.
> 
> When are you interested in computing the value half-way between
> the ends of a (non-numeric) enumeration type, attempting to use
> A'Length / 2?

Iteration algorithms in numeric analysis. Of course Length/2 is nonsense,
but (Xn+Xm)/2 or Xn+(Xm-Xn)/2 or its generalization G*(Xn+Xm) is used quite
often. For example, Xi can be from a vector space. G can be a matrix which
norm is 0.5.

>> This is why it is so important to have a consistent model
>> of indexing and arrays.
> 
> It is important to be consistently using the proper type of arrays
> in algorithms made for this type of arrays.
> 
>> For an unordered [index] type X it is wrong to
>> assume that:
> 
> Can there be an index type in Ada that isn't ordered?

Sure:

   type Unordered_Index is (A, B, C, D);
   function "<" (Left, Right : Unordered_Index)
      return Boolean is abstract;
   type Unordered_Array is array (Unordered_Index) of Integer;

>> 1. If L in X and U in X then there is always M in X between L and U
>> 2. That M can be computed as (L+U)/2
> 
> You can't usually compute M when X is an enumeration type.
> Otherwise, if A'Length <= 1, then (L+U)/2 = 0 = M.
> Thus, M can be computed but is not necessarily between L and U.

1. This is plain wrong. If L=U then (L+U)/2=L. In general, it is always so
that min(L,U) <= (L+U)/2 <= max(L,U), when ordered numbers are considered.
(For generalizations on unordered cases see "convex hull")

2. M could not be computed just because "+", "/", 2 aren't defined. Then of
course there could be no order;

3. Note that (1) is wrong for modular types. Not surprisingly, they aren't
numbers, but classes of equivalence (sets of numbers, infinite sets, BTW,
yet representable in the computer, how strange (:-)). As such they don't
posses the order of numbers. See "rings of congruence classes." Alas but,
here (modular types) Ada is again not very inconsistent.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Jeffrey Carter]

adaworks@sbcglobal.net wrote:
> 
> I have heard it expressed at some software-oriented conferences that
> enumerated types represent an old-fashioned way of thinking about
> software design.  Some in the OO community believe that, because
> enumerated types are not extensible, they actually thwart good OO
> design.

How can an implementation technique thwart good design?

-- 
Jeffrey Carter
"Now go away or I shall taunt you a second time."
Monty Python and the Holy Grail
E-mail: jeffrey_r_carter-nr [commercial-at]
         raytheon [period | full stop] com

Re: Surprise in array concatenation

[Simon Wright]

Jeffrey Carter <spam@spam.com> writes:

> adaworks@sbcglobal.net wrote:
>> I have heard it expressed at some software-oriented conferences that
>> enumerated types represent an old-fashioned way of thinking about
>> software design.  Some in the OO community believe that, because
>> enumerated types are not extensible, they actually thwart good OO
>> design.
>
> How can an implementation technique thwart good design?

That was "good *OO* design".

We have been developing using UML-based OO techniques, but it is quite
hard using this sort of technology to cover the sort of important
questions you would answer in a system/subsystem design document (see
for example http://www.pogner.demon.co.uk/mil_498/ssdd-did.htm#scope),
and which don't depend so much -- if at all -- on the software
technology.

On UML features, by the way -- a picture may be worth a thousand
words, but a sizable sequence diagram is very hard to grasp, and don't
get me started on activity diagrams!

Re: Surprise in array concatenation

[adaworks]

"Jeffrey Carter" <spam@spam.com> wrote in message
news:75KTe.5$1r.0@dfw-service2.ext.ray.com...
> adaworks@sbcglobal.net wrote:
> >
> > I have heard it expressed at some software-oriented conferences that
> > enumerated types represent an old-fashioned way of thinking about
> > software design.  Some in the OO community believe that, because
> > enumerated types are not extensible, they actually thwart good OO
> > design.
>
> How can an implementation technique thwart good design?
>
Enumerated types, as presently designed, are not extensible.  They
do no encapsulate their operations, and new operations, though
they can be added, do not bind in a way that conforms to conventional
OO design principles.

It is difficult, though not impossible, to create designs where the
enumerated type is not exposed in the public part of a package
specification.   For many OOP practitioners, enumerated types
are at the wrong level of abstraction for appropriate support
of object-oriented programming.

Too often, these non-extensible types are designed to be globally
visible, thus creating a dependency nightmare.   When they are
publicly visible, any change will ripple through the entire design,
and the compilation of every dependent library unit will be
involved.

This is not to say that enumerated types are evil.  I don't expect
anyone to write a letter to Ada Letters titled, "Enumerated Types
Considered Harmful."   However, they are easy to use incorrectly,
and in the hands of Ada novices, they often create as many
problems as they solve.

It would be very nice if the Ada language had a capability to include
abstract data types or extensible objects as members of the ordered
set.   This would be even more powerful if the enumerated type
were, itself, abstract and extensible.   I say nice, but realizing that
such a feature would make it nearly impossible to design this so
the underlying design goals of Ada would be satisfied.  I myself would
find the implementation of this design to be extraodinarily difficult.

Richard Riehle

Re: Surprise in array concatenation

[Jacob Sparre Andersen]

Robert A Duff wrote:

> What do you think of Ada 200X's type Wide_Wide_Character, which is
> an enumeration type with upwards of a billion literals?  ;-)

Aren't quite a few of the positions undefined?  (not that I find ~100k
literals entertaining either)

Jacob
-- 
�A corollary of Murphy's law is that duplicate information
 eventually becomes different information.  Putting both in
 the same file may slow down the process, but it will not
 prevent it.�                                 -- Wes Groleau

Re: Surprise in array concatenation

[Jean-Pierre Rosen]

adaworks@sbcglobal.net a �crit :
> Enumerated types, as presently designed, are not extensible.  They
> do no encapsulate their operations, and new operations, though
> they can be added, do not bind in a way that conforms to conventional
> OO design principles.
> 
Can't resist...
Remember that a great strength of Ada is that you are not *forced* into 
OO design when it is not appropriate. Enumerated types are great for 
other methodologies.

This is not a troll for those who think that OO is everything...
(well, maybe :-) )

-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

>>Almost no real number can be represented in a computer.
 
> OK, it is beaten to death.

The fact is quite alive.


> How else you could check if 1 really refers to the physical 1!

Which physical 1? There is a written agreement on what represents
1 inside a computer, per computer. As I said, math declares the swamp
away into which it is built. Computer descriptions do soemthing similar.
I do not usually try to write programs using funny interpretations of
bits, and assume you don't either.


>>When are you interested in computing the value half-way between
>>the ends of a (non-numeric) enumeration type, attempting to use
>>A'Length / 2?
> 
> 
> Iteration algorithms in numeric analysis.

Sounds more like adding rectangles or points, when X runs along
the axis of discrete non-numeric enumeration values.
A plausible algorithm could be binary search when the indexed values
grow or shrink as the non-numeric index values grow in position.


>>Can there be an index type in Ada that isn't ordered?
> 
> 
> Sure:
> 
>    type Unordered_Index is (A, B, C, D);
>    function "<" (Left, Right : Unordered_Index)
>       return Boolean is abstract;

I was thinking of index types that are not ordered in Ada. See
below.

> 1. This is plain wrong. If L=U then (L+U)/2=L.

As you say, "+" isn't predefined for enumeration types.

As for M and (L+U)/2 I should have said, in Ada (and other PLs)
if 0 <= A'Length <= 1, then (L+U)/2 can be 0 = M, and A'Length/2 = 0, always.


> (For generalizations on unordered cases see "convex hull")
I'm trying to see arrays, and possible improvements. If a convex hull
offers something useful in arranging memory cells and copying
some of them to a CPU or I/O register, fine. (As this is what happens
in the end.)


> 2. M could not be computed just because "+", "/", 2 aren't defined. Then of
> course there could be no order;

But in fact, Ada's enumeration types are ordered. Try to make this
pass Ada compilation,

type Unordered_Index is (A, B, C, D);
for Unordered_Index use (A => 1, B => 3, C => 2, D => 4);

What does the compiler say?


> 3. Note that (1) is wrong for modular types.

And?

> Not surprisingly, they aren't
> numbers,

That's news. There are numbers congruent modulo some number.
But you think these numbers aren't numbers?

> but classes of equivalence (sets of numbers, infinite sets, BTW,
> yet representable in the computer, how strange (:-)).

One equivalence class is not the same as the set of numbers mapped
to members of the equivalence class. "type X is mod 10;" implies a
finite set of values. Try "a: X; a := 42;" In other words, 42 cannot
belong to the set of values expressed by X. Belonging and congruence
are not the same thing. For example, we cannot count an absolute
number of items when there are at least as many items as the modulus.

Here is a representation of DK's representation of the set of real
numbers inside a computer:

  2#1010010#

It remains to be shown how computations with real numbers are useful.


> here (modular types) Ada is again not very inconsistent.

I'm glad to hear this.

Re: Surprise in array concatenation

[Georg Bauhaus]

Simon Wright wrote:

> On UML features, by the way -- a picture may be worth a thousand
> words, but a sizable sequence diagram is very hard to grasp, and don't
> get me started on activity diagrams!

Could BON be more practical in this regard?
http://www.bon-method.com/

Re: Surprise in array concatenation

[Georg Bauhaus]

Georg Bauhaus wrote:

> One equivalence class is not the same as the set of numbers mapped
> to members of the equivalence class.

I was really thinking of the class representatives:

> "type X is mod 10;" implies a
> finite set of values. 

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Thu, 08 Sep 2005 12:27:50 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
>> How else you could check if 1 really refers to the physical 1!
> 
> Which physical 1? There is a written agreement on what represents
> 1 inside a computer, per computer.

Note that A=1 from the problem state is not a bit pattern. It is a set of
computational states for which A is considered be 1. So when you make a
memory dump and discover a bit pattern 000000001 at the address FF07712CA0
that tells absolutely nothing.

> As I said, math declares the swamp
> away into which it is built. Computer descriptions do soemthing similar.
> I do not usually try to write programs using funny interpretations of
> bits, and assume you don't either.

I don't care about representations as long as they aren't the part of the
problem space (like in communication protocols.)

>>>Can there be an index type in Ada that isn't ordered?
>> 
>> Sure:
>> 
>>    type Unordered_Index is (A, B, C, D);
>>    function "<" (Left, Right : Unordered_Index)
>>       return Boolean is abstract;
> 
> I was thinking of index types that are not ordered in Ada. See
> below.

if A < B then -- Compile error! What else you need?

>> 1. This is plain wrong. If L=U then (L+U)/2=L.
> 
> As you say, "+" isn't predefined for enumeration types.
> 
> As for M and (L+U)/2 I should have said, in Ada (and other PLs)
> if 0 <= A'Length <= 1, then (L+U)/2 can be 0 = M, and A'Length/2 = 0, always.

You cannot work with Length, it is another type! A'Length is universal
integer see ARM 3.6.2.

Mathematical equivalent of A'Length is distance between points
A'First/A'Last. If you want to work with A'Length, then you have to switch
from indices to the positions of, i.e. to I'Pos:

Array : Index -> Element
Index'Pos : Index -> Universal_Integer

Note that working with positions breaks the abstraction, because the order
of Index might be different from one of the position! If some day Ada will
have abstract arrays, then "for I in A loop" should iterate it in the order
of the Index, and not in the arbitrary one of Index'Pos.

>> (For generalizations on unordered cases see "convex hull")
> I'm trying to see arrays, and possible improvements. If a convex hull
> offers something useful

Believe me, convex sets (whether (1-t)a + tb belongs to the same set forall
0<=t<=1) are extremely important for countless numeric methods,
computational geometry etc.

>> 2. M could not be computed just because "+", "/", 2 aren't defined. Then of
>> course there could be no order;
> 
> But in fact, Ada's enumeration types are ordered.

See above.

> Try to make this pass Ada compilation,
> 
> type Unordered_Index is (A, B, C, D);
> for Unordered_Index use (A => 1, B => 3, C => 2, D => 4);

This has little to do with the order of Unordered_Index. The representation
clause defines representation. You should never mix:

1. The user-defined order and other operations (like +, -) and literals
from the problem space;
2. The positions of discrete values;
3. The representations of discrete values.

These all are different things. I hope it is clear that algorithms should
be written in terms of (1)?

>> 3. Note that (1) is wrong for modular types.
> 
> And?

and you could not write a generic array algorithm both relying on (1) and
usable for modular types.

>> Not surprisingly, they aren't
>> numbers,
> 
> That's news. There are numbers congruent modulo some number.
> But you think these numbers aren't numbers?

Yes. Modular 1 is an infinite set of numbers = { x | x = 1 (mod 16) }. You
can try to abstract this fact by choosing some definite element from each
of these sets. But you cannot do it completely. Because the structure is
different from one of Z. Some important results valid for Z will not hold.
What else would be the reason to have modular numbers?

>> but classes of equivalence (sets of numbers, infinite sets, BTW,
>> yet representable in the computer, how strange (:-)).
> 
> One equivalence class is not the same as the set of numbers mapped
> to members of the equivalence class. "type X is mod 10;" implies a
> finite set of values. Try "a: X; a := 42;" In other words, 42 cannot
> belong to the set of values expressed by X.

You again mixing sets and elements of. 42 is a literal. In the case of
equivalence classes it denotes not a number (Z) but a class of. There is no
class X'(42) for mod 10. Yet 42, now as an element of Z, is one of X'(2)
because 42=2(mod 10).

> Belonging and congruence are not the same thing.

They are exactly same. It is how the set is defined.

> For example, we cannot count an absolute
> number of items when there are at least as many items as the modulus.

This is the same logic error as above with A'Length. The type of the
cardinal numbers in Ada is defined as Universal_Integer. It is not the type
of the elements in a set!

(Taking too much C++ might be dangerous for your health! (:-))

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Ed Falis]

On Thu, 08 Sep 2005 06:36:04 -0400, Georg Bauhaus <bauhaus@futureapps.de>  
wrote:

> Could BON be more practical in this regard?
> http://www.bon-method.com/

I like BON myself - much more elegant than UML.  Another nice one is  
Trygve Reenskaug's "role modelling" approach in "Working with Objects".   
Problem is, neither of these has much software supporting them, and  
they're not considered de facto industry standards.

Did you ever read the tongue-in-cheek article Meyer did on UML?  It's  
hilarious.

- Ed

Re: Surprise in array concatenation

[Jeffrey Carter]

Simon Wright wrote:
> 
> That was "good *OO* design".


Fine. If enumeration types are not a suitable technique for implementing 
your good OO design, then don't use them during implementation. It 
shouldn't have any effect on the design.

> On UML features, by the way -- a picture may be worth a thousand
> words, but a sizable sequence diagram is very hard to grasp, and don't
> get me started on activity diagrams!

Most UML diagrams seem to have a small amount of information per 
diagram. Integrating large numbers of such diagrams in one's head seems 
less effective than using fewer diagrams with more information.

-- 
Jeffrey Carter
"Now go away or I shall taunt you a second time."
Monty Python and the Holy Grail
E-mail: jeffrey_r_carter-nr [commercial-at]
         raytheon [period | full stop] com

Re: Surprise in array concatenation

[Jeffrey Carter]

adaworks@sbcglobal.net wrote:
> 
> Enumerated types, as presently designed, are not extensible.  They
> do no encapsulate their operations, and new operations, though
> they can be added, do not bind in a way that conforms to conventional
> OO design principles.

So? Ada types should not be a consideration during design. Once your 
have your design, you decide how to implement it. If enumerated types 
are not suitable, don't use them.

Your compiler implements your design in machine code, which has no 
extension mechanisms. Should that affect your design?

-- 
Jeffrey Carter
"Now go away or I shall taunt you a second time."
Monty Python and the Holy Grail
E-mail: jeffrey_r_carter-nr [commercial-at]
         raytheon [period | full stop] com

Re: Surprise in array concatenation

[Pascal Obry]

Ed Falis a �crit :

> Did you ever read the tongue-in-cheek article Meyer did on UML?  It's 
> hilarious.

That's the problem with Meyer. I think that its strong positions against
Ada, UML... are making him hilarious sometimes :)

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|              http://www.obry.net
--| "The best way to travel is by means of imagination"
--|
--| gpg --keyserver wwwkeys.pgp.net --recv-key C1082595

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

> Note that A=1 from the problem state is not a bit pattern. It is a set of
> computational states for which A is considered be 1. So when you make a
> memory dump and discover a bit pattern 000000001 at the address FF07712CA0
> that tells absolutely nothing.

A dump might tell me a lot provided I know what kind of dump it is and when
it happened. Depending on the algorithm, for example, if FF07712CA0
addresses a cell that is 000000000 at the start of the program, and
the program sets it to 000000001 just once during the program's run,
then, assuming regular operation, I know what happened.


> I don't care about representations as long as they aren't the part of the
> problem space (like in communication protocols.)

Finiteness of computers happens to be one of the problems we
are discussing.


>>>   type Unordered_Index is (A, B, C, D);
>>>   function "<" (Left, Right : Unordered_Index)
>>>      return Boolean is abstract;
> 
> 
> if A < B then -- Compile error! What else you need?


"Ordered" as per Ada's requirements for enumerations.
For arrays (Ada arrays), I'd rather not have to think about *user*
*defined* order of the index type when it comes to element change.


> If some day Ada will
> have abstract arrays, then "for I in A loop" should iterate it in the order
> of the Index, and not in the arbitrary one of Index'Pos.

Please, could you stop naming this ADT an array? It has so many
more assumptions that it deserves a distinguishing name!

For example, you could have holes in your index type, IIUC.


>>>(For generalizations on unordered cases see "convex hull")
>>
>>I'm trying to see arrays, and possible improvements. If a convex hull
>>offers something useful
> 
> 
> Believe me, convex sets (whether (1-t)a + tb belongs to the same set forall
> 0<=t<=1) are extremely important for countless numeric methods,
> computational geometry etc.

I'm curious. How does this relate to array indexing?


>>Try to make this pass Ada compilation,
>>
>>type Unordered_Index is (A, B, C, D);
>>for Unordered_Index use (A => 1, B => 3, C => 2, D => 4);
> 
> 
> This has little to do with the order of Unordered_Index.

It has a lot to do with Ada's notion of the order of enumeration literals
(increasing).

> The representation
> clause defines representation. You should never mix:
> 
> 1. The user-defined order and other operations (like +, -) and literals
> from the problem space;
> 2. The positions of discrete values;
> 3. The representations of discrete values.
> 
> These all are different things. I hope it is clear that algorithms should
> be written in terms of (1)?

I can't imagine non-DK-array algorithms are usually written in terms
of (1) (*user-defined* sorting order of the index types).
These are Ada arrays, rock solid low level stuff, based on preexisting
contracts inherent in enumeration order or Positive's order, etc..

Why should I impose *any* order on (Red, Green) when this type lists
the colors of apples in my garden? I can very well construct my arrays
using the predifined order.
 Incidentally, Haskell permits user defined sorting order (<) for types that
are instances of type class Enum. Yet at the same time, you can request a
default order by stating "derives Enum".

Why should I redefine the order of Positive when using Ada.Strings.Fixed?


>>>3. Note that (1) is wrong for modular types.
>>
>>And?
> 
> 
> and you could not write a generic array algorithm both relying on (1) and
> usable for modular types.


My definition of "generic array algorithm" has limitations.
Some are imposed by Ada. I'm awaiting your abstract array data type,
same efficiency as Ada arrays, capable of making empty array
objects using a one-enumeral index type, permitting compile time
data layouts, safe indexing after index computations, perhaps
dynamically changing their length, ...


> You again mixing sets and elements of. 42 is a literal. In the case of
> equivalence classes it denotes not a number (Z) but a class of.

I'm not mixing sets and elements, I'm pointing out that symbol manipulation
and counting are sometimes different. I'm trying to point out the *you*
are talking evasively about special cases. Cases when there is a finite
subset of mathematical items that can be represented inside a computer,
element-wise or not. And this works in the special cases just because
the problem to solve is really about finite sets, inside a computer.
Whatever the finite sets represent in our interpretations, they are
finite.

If we need all umpteenth decimal digits in the expansion of Pi,
we might or might not get them, depending on what umpteenth is,
because any storage is finite.


> There is no
> class X'(42) for mod 10. Yet 42, now as an element of Z, is one of X'(2)
> because 42=2(mod 10).

Not "is", but "is represented" in an algorithm which is about equivalence
classes, not about counting.
 "Package number 245345=5(mod 10) is malformed. So please look at
package number 5." Huh?

>>Belonging and congruence are not the same thing.
> 
> 
> They are exactly same. It is how the set is defined.

It's time for me to study Lewis Carrol's stories, to that I can
legitimately refer to Humpty Dumpty. 

If there are 4 trees in a garden, there is really 1 tree in the
garden, because of modulo 3. BTW, was that modulo number the class
representative 3 or the number three or the symbol 3? Oh well...
Meanwhile the apples and plums below the 3 other trees start to rot.
Time for a depressing garbage collection... 


> The type of the
> cardinal numbers in Ada is defined as Universal_Integer.
> It is not the type of the elements in a set!

Universal_Integer is subject to capacity constraints, e.g. storage.
Therefore there exists a corresponding set, for each compiler + computer,
outside the domain of pure math-think and inside the domain of computer-
math-think.


> (Taking too much C++ might be dangerous for your health! (:-))

What has C++ got to do with this? (Except that C++ programmers might
be more aware of the limitations of the computer, because they have
to take care of limits themselves? Because template recursion is
usually limited to a certain depth, but OTOH template recursion
becomes highly visible in error messages?)

Re: Surprise in array concatenation

[Simon Wright]

Jeffrey Carter <spam@spam.com> writes:

> Most UML diagrams seem to have a small amount of information per
> diagram. Integrating large numbers of such diagrams in one's head
> seems less effective than using fewer diagrams with more
> information.

Class and state models (not quite the same as _diagrams_, of course)
are pretty dense if done right. But of course you have to use an
appropriate profile; and the reader has to grasp the profile too.

Re: Surprise in array concatenation

[Dmitry A. Kazakov]

On Thu, 08 Sep 2005 20:18:26 +0200, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
>> Note that A=1 from the problem state is not a bit pattern. It is a set of
>> computational states for which A is considered be 1. So when you make a
>> memory dump and discover a bit pattern 000000001 at the address FF07712CA0
>> that tells absolutely nothing.
> 
> A dump might tell me a lot provided I know what kind of dump it is and when
> it happened. Depending on the algorithm, for example, if FF07712CA0
                     ^^^^^^^^^^^^^^^^^!

>> If some day Ada will
>> have abstract arrays, then "for I in A loop" should iterate it in the order
>> of the Index, and not in the arbitrary one of Index'Pos.
> 
> Please, could you stop naming this ADT an array? It has so many
> more assumptions that it deserves a distinguishing name!

> For example, you could have holes in your index type, IIUC.

Try to define "hole" in terms of ADT, maybe then you'll understand the
problem better.

>>>>(For generalizations on unordered cases see "convex hull")
>>>
>>>I'm trying to see arrays, and possible improvements. If a convex hull
>>>offers something useful
>> 
>> Believe me, convex sets (whether (1-t)a + tb belongs to the same set forall
>> 0<=t<=1) are extremely important for countless numeric methods,
>> computational geometry etc.
> 
> I'm curious. How does this relate to array indexing?

The index ranges need to be convex if you want to have your "length / 2".
The above is the definition of a convex set.

>> The representation
>> clause defines representation. You should never mix:
>> 
>> 1. The user-defined order and other operations (like +, -) and literals
>> from the problem space;
>> 2. The positions of discrete values;
>> 3. The representations of discrete values.
>> 
>> These all are different things. I hope it is clear that algorithms should
>> be written in terms of (1)?
> 
> I can't imagine non-DK-array algorithms are usually written in terms
> of (1) (*user-defined* sorting order of the index types).
> These are Ada arrays, rock solid low level stuff, based on preexisting
> contracts inherent in enumeration order or Positive's order, etc..

Ada was designed as a higher level programming. If you want an assembly
language, there are plenty of them...

>> You again mixing sets and elements of. 42 is a literal. In the case of
>> equivalence classes it denotes not a number (Z) but a class of.
> 
> I'm not mixing sets and elements, I'm pointing out that symbol manipulation
> and counting are sometimes different.

Care to show a difference?

> It's time for me to study Lewis Carrol's stories, to that I can
> legitimately refer to Humpty Dumpty. 

It is always a good reading. Though any introductory book on modern algebra
could also help.

> If there are 4 trees in a garden, there is really 1 tree in the
> garden, because of modulo 3.

You still missing the point, and still mixing apples and oranges.

It is not 1 tree, it is a class of equivalence: { 1 tree, 4 trees, 7 trees,
...}. 4 trees (a set!) is in this class (a set of sets!) which you have
denoted as 1 (a number!)

> BTW, was that modulo number the class
> representative 3 or the number three or the symbol 3? Oh well...
> Meanwhile the apples and plums below the 3 other trees start to rot.
> Time for a depressing garbage collection... 

Those are philosophical questions. As a follower of Plato, you should
address them to his philosophy. In the philosophy I adhere they are just
meaningless.

>> The type of the
>> cardinal numbers in Ada is defined as Universal_Integer.
>> It is not the type of the elements in a set!
> 
> Universal_Integer is subject to capacity constraints,

And what's the point? This or that way, but Universal_Integer is a type
different from one of array index.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:


>>>Believe me, convex sets (whether (1-t)a + tb belongs to the same set forall
>>>0<=t<=1) 
 > The index ranges need to be convex if you want to have your "length / 2".
> The above is the definition of a convex set.

In other words, you want the index types to include floating point numbers?


> Ada was designed as a higher level programming. If you want an assembly
> language, there are plenty of them...

Higher, not high, in any current sense of the word. It didn't
even have high level data structures of the times (APL, SETL, ...)
It is only now going to have maps or sets, iterators, quantifier approximations,
...

Certainly Ada's array are not like "assembly language arrays", but
they share a lot. Even higher level data structures like STL or Ada.Containers,
are built around a machine model. When I can't map Ada's arrays
to computer storage, does Ada serve me in systems programming? No.


>>I'm not mixing sets and elements, I'm pointing out that symbol manipulation
>>and counting are sometimes different.
> 
> 
> Care to show a difference?

Yes.


>>It's time for me to study Lewis Carrol's stories, to that I can
>>legitimately refer to Humpty Dumpty. 
> 
> 
> It is always a good reading. Though any introductory book on modern algebra
> could also help.

Provided A'First > A'Last needs help. People seem to be o.K. using
this idiom. If you don't see a way of merging this ">" with algebra,
then perhaps you could present the well working idiom to mathematicians.
Maybe they can find a theory around it that satisfies your mathematical
needs.


>>If there are 4 trees in a garden, there is really 1 tree in the
>>garden, because of modulo 3.
> 
> 
> You still missing the point, and still mixing apples and oranges.

If there is one interpretation of bit pattern 01, and the interpretation
says, 01 represents an infinite set in my problem domain, *and* I need not
distinguish the elements of the set, then still this
set is not yet considered as part of a computation.
If it becomes part of a computation, there may be other bit patterns
needed in the computation. When the problem is about an unforseeable
number of bit patterns, then even though you can interpret single
finite bit patterns to stand for infinite imaginations (sets),
you cannot do this recursivly. That is, if the problem grows, and
includes many more bit patterns, you could try to make yet another
bit pattern stand for the many more bit patterns, provided you
find one that isn't used yet. For example, intermediate results
can be stored in a comprehensive bit pattern that reuses some
bit sequences no longer needed. This process consumes variables.
There is an end to the number of variables that can be used in
any finite program (the last two words being a tautology anyway).

Try to fill a hard disk with the average number of occurences
of the digits 5 and 6 that occur in sequence in the decimal expansion
of Pi. What is going to happen?

It is similar with mathematical reals. Just try to implement
the diagonalisation method.


Turing machines have infinite tapes, desktop computers don't.
And even with Turing machines there is infinity trouble. I guess you
won't deny this?


> As a follower of Plato, you should
> address them to his philosophy.

Plato has little to say about these issues, AFAICT.

 
>>>The type of the
>>>cardinal numbers in Ada is defined as Universal_Integer.
>>>It is not the type of the elements in a set!
>>
>>Universal_Integer is subject to capacity constraints,
> 
> 
> And what's the point? This or that way, but Universal_Integer is a type
> different from one of array index.

The point here is that you can't have the mathematical
integers inside computers, just as you can't have the mathematical
reals inside a computers. Some proofs wouldn't work because for example
you can't algorithmically find a sufficiently large m_0 such that
forall m > m_0, a property holds.
 This shows that a mathematical approach that ignores properties
of computers is possibly impossible.

(1) You need the mathematics of finite sets of discrete values, and R is
not one of them. 

(2) You will then need to show that because something is more simple and
easier seen as consistent with a smaller set of rules, it will also lead to
better programs. 

I see that some algorithms can be made general when A'First > A'Last
is permitted, and that some algorithms will need an additional
 if property(A'Length) then ... else ... end if;

I don't see that the set of mathematical structures applicable
to Ada array indexing must be restricted to those that you have
mentioned in this thread.

Re: Surprise in array concatenation

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

>>If there are 4 trees in a garden, there is really 1 tree in the
>>garden, because of modulo 3.
> 
> 
> You still missing the point, and still mixing apples and oranges.
> 
> It is not 1 tree, it is a class of equivalence: { 1 tree, 4 trees, 7 trees,
> ...}. 4 trees (a set!) is in this class (a set of sets!) which you have
> denoted as 1 (a number!)

You wanted an example of counting different from something else.
Why is the string "{{}}" different from "{}"?

Re: Surprise in array concatenation

[Bob Spooner]

"Jeffrey Carter" <spam@spam.com> wrote in message
news:B2_Te.5$oo1.2@dfw-service2.ext.ray.com...
> adaworks@sbcglobal.net wrote:
> >
> > Enumerated types, as presently designed, are not extensible.  They
> > do no encapsulate their operations, and new operations, though
> > they can be added, do not bind in a way that conforms to conventional
> > OO design principles.
>
> So? Ada types should not be a consideration during design. Once your
> have your design, you decide how to implement it. If enumerated types
> are not suitable, don't use them.
>
> Your compiler implements your design in machine code, which has no
> extension mechanisms. Should that affect your design?
>
> -- 

This type of discussion has come up before. The design is always influenced
by and constrained by what is available with which to implement it. And yes,
machine code characteristics such as word size do affect design. In the real
world, it is impossible to completely separate design from implementation.

Bob

Re: Surprise in array concatenation

[adaworks]

"Jeffrey Carter" <spam@spam.com> wrote in message
news:B2_Te.5$oo1.2@dfw-service2.ext.ray.com...
> adaworks@sbcglobal.net wrote:
> >
> > Enumerated types, as presently designed, are not extensible.  They
> > do no encapsulate their operations, and new operations, though
> > they can be added, do not bind in a way that conforms to conventional
> > OO design principles.
>
> So? Ada types should not be a consideration during design. Once your
> have your design, you decide how to implement it. If enumerated types
> are not suitable, don't use them.
>
It is not a matter of suitable or not.   Rather, it is a concern that enumerated
types can compromise a design unless one thinks carefully about their
long-term effects within that design.

> Your compiler implements your design in machine code, which has no
> extension mechanisms. Should that affect your design?
>
We typically do not extend instances.  Extensibility is at a different
level of abstraction.  Even if Ada were compiled to an intermediate
byte code, as is the case with Java, extensibility would stillbe at
the source code level on classes, not instances.

In reply to Dr. Rosen, you are correct in your observation that Ada
does not force a design paradigm on its users.   However, there is
a difference between being required to use a particular paradigm
and being able to use one's preferred paradigm.   When enumerated
types are extensible, one can choose OOP, or not.  Java, for
example, has a "final" option to make this choice feasible.

I certainly do not suggest using Java instead of Ada. Java falls short
of what we would want for reliable computing in large-scale
software systems, but we can learn from other languages, even
when those languages have inherent shortcomings.

Richard Riehle

Re: Surprise in array concatenation

[Dave Thompson]

On 05 Sep 2005 19:46:13 -0400, Robert A Duff
<bobduff@shell01.TheWorld.com> wrote:

> Kilgallen@SpamCop.net (Larry Kilgallen) writes:
> 
> > In article <wcck6hvnpsm.fsf@shell01.TheWorld.com>, Robert A Duff <bobduff@shell01.TheWorld.com> writes:
<snip>
> > > Heh?  The lower (and upper!) bound of all array types in Pascal is
> > > fixed.  And it has to be fixed at a static value.  Every array object of
> > > a given type has the same fixed bounds.
> > > 
> > > (Well, some version of Pascal added conformant arrays, which relaxed
> > > this requirement for formal parameters.)
> > 
> > That is true, in the same sense that some versions of Ada added
> > modular types -- they were added to the standard.
> 
> Right.  I was being vague because I couldn't remember whether conformant
> arrays were added in the first ISO Pascal standard, or the Extended
> Pascal version.  I also can't remember the status of Extended Pascal
> (was it ever officially blessed by ISO?).  Do you know?
> 
They were added as an option, "Level 1", in the first standard (7185),
and in fact are called out in the introductory section as one of only
two "major" changes made during standardization.  The Extended Pascal
standard (10206), which I've found lying about but not actually used,
and is on sale which I believe means approved at ANSI and ISO, adds
(purportedly?) more powerful "schemas" which I have not taken the time
to understand but apparently "subsume" conformant arrays.

> Conformant arrays were certainly not part of the original Pascal as
> documented in Jensen and Wirth's book, "Pascal User Manual and Report".
> And conformant arrays are only for parameters -- not normal variables,
> record components, heap objects, etc.  Correct?
> 
AIUI correct.

- David.Thompson1 at worldnet.att.net

Re: Surprise in array concatenation

[Ole-Hjalmar Kristensen]

I think this is actually wrong. Run-time polymorphism (virtual
functions) are fine if you what you need is to implement several
versions of a function with the same signature, for example providing
the same abstract interface to several different hardware devices.

However, if your main type of extension is adding new operations, like
handling a new message type or adding a new function to some device,
they are not that useful, and enumerated types and case statements is
actually cleaner and more maintainable.

>>>>>   <adaworks@sbcglobal.net> writes:


    > I have heard it expressed at some software-oriented conferences that
    > enumerated types represent an old-fashioned way of thinking about
    > software design.  Some in the OO community believe that, because
    > enumerated types are not extensible, they actually thwart good OO
    > design.


    > Richard Riehle

-- 
   C++: The power, elegance and simplicity of a hand grenade.

Re: Surprise in array concatenation

[Randy Brukardt]

<adaworks@sbcglobal.net> wrote in message
news:qWQTe.2510$6e1.231@newssvr14.news.prodigy.com...
> It would be very nice if the Ada language had a capability to include
> abstract data types or extensible objects as members of the ordered
> set.   This would be even more powerful if the enumerated type
> were, itself, abstract and extensible.   I say nice, but realizing that
> such a feature would make it nearly impossible to design this so
> the underlying design goals of Ada would be satisfied.  I myself would
> find the implementation of this design to be extraodinarily difficult.

It isn't *that* hard to define something that works (see AI-261). But it's
weird compared to the rest of the language. If we had gotten Integer'Class
in Ada 95, it would be more worthwhile...

                Randy.

Re: Surprise in array concatenation

[Randy Brukardt]

<adaworks@sbcglobal.net> wrote in message
news:zSFTe.4078$wk6.1150@newssvr11.news.prodigy.com...
> I recall a project where an Ada newbie, having learned about enumerated
> types, created one enumerated type that was three pages long.  That is,
> the number of values in the type was so great that it took three pages
> of 11 X 14 standard printer paper to contain it.

Hey, I resemble that remark!

The intermediate code definition for Janus/Ada includes an enumeration of
300 or so operations. The definition covers several pages (it has comments).
That's used as the discriminant on a giant variant record that covers more
than 6 pages. No newbies here. :-)

It's very useful for this to be an enumeration; when new operations are
added, the case statements in the optimizer and elsewhere fail to compile
until they've been updated with the new operations. That's a short term
pain, but it avoids a lot of problems in the long run (because the
operations were added considering impacts, rather than either forgotten or
defaulted to something that's likely to be wrong).

And, yes, Bob, it's not unusual to make arrays of (parts) of this type.

                    Randy.

Re: Surprise in array concatenation

[Larry Kilgallen]

In article <zcKdnQ0Er8bYF6neRVn-qQ@megapath.net>, "Randy Brukardt" <randy@rrsoftware.com> writes:
> <adaworks@sbcglobal.net> wrote in message
> news:zSFTe.4078$wk6.1150@newssvr11.news.prodigy.com...
>> I recall a project where an Ada newbie, having learned about enumerated
>> types, created one enumerated type that was three pages long.  That is,
>> the number of values in the type was so great that it took three pages
>> of 11 X 14 standard printer paper to contain it.
> 
> Hey, I resemble that remark!
> 
> The intermediate code definition for Janus/Ada includes an enumeration of
> 300 or so operations. The definition covers several pages (it has comments).
> That's used as the discriminant on a giant variant record that covers more
> than 6 pages.

I have something quite similar in software of a different purpose...

> It's very useful for this to be an enumeration; when new operations are
> added, the case statements in the optimizer and elsewhere fail to compile
> until they've been updated with the new operations. That's a short term
> pain, but it avoids a lot of problems in the long run (because the
> operations were added considering impacts, rather than either forgotten or
> defaulted to something that's likely to be wrong).

..for the same reason.

Re: Surprise in array concatenation

[Lurker]

"Randy Brukardt" <randy@rrsoftware.com> wrote in message
news:zcKdnQ0Er8bYF6neRVn-qQ@megapath.net...
> <adaworks@sbcglobal.net> wrote in message
> news:zSFTe.4078$wk6.1150@newssvr11.news.prodigy.com...
> > I recall a project where an Ada newbie, having learned about enumerated
> > types, created one enumerated type that was three pages long.  That is,
> > the number of values in the type was so great that it took three pages
> > of 11 X 14 standard printer paper to contain it.
>
> Hey, I resemble that remark!

Are you sure you "resemble" any remark at all?
Let alone the one up there :-)

Re: Surprise in array concatenation

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> <adaworks@sbcglobal.net> wrote in message
> news:zSFTe.4078$wk6.1150@newssvr11.news.prodigy.com...
> > I recall a project where an Ada newbie, having learned about enumerated
> > types, created one enumerated type that was three pages long.  That is,
> > the number of values in the type was so great that it took three pages
> > of 11 X 14 standard printer paper to contain it.
> 
> Hey, I resemble that remark!
> 
> The intermediate code definition for Janus/Ada includes an enumeration of
> 300 or so operations. The definition covers several pages (it has comments).
> That's used as the discriminant on a giant variant record that covers more
> than 6 pages. No newbies here. :-)
> 
> It's very useful for this to be an enumeration; when new operations are
> added, the case statements in the optimizer and elsewhere fail to compile
> until they've been updated with the new operations. That's a short term
> pain, but it avoids a lot of problems in the long run (because the
> operations were added considering impacts, rather than either forgotten or
> defaulted to something that's likely to be wrong).
> 
> And, yes, Bob, it's not unusual to make arrays of (parts) of this type.

You mean indexed by, not "of", I think.

I don't doubt it!  But I suspect you don't create very many
unconstrained arrays indexed by (parts of) this type.  And
not empty arrays thereof.  True?

I agree with you that there's nothing necessarily wrong with an
enumeration of hundreds.  And I agree that the full-coverage rule
for Ada case statements is very cool.

- Bob

Re: Surprise in array concatenation

[adaworks]

"Randy Brukardt" <randy@rrsoftware.com> wrote in message
news:zcKdnQ0Er8bYF6neRVn-qQ@megapath.net...
> <adaworks@sbcglobal.net> wrote in message
> news:zSFTe.4078$wk6.1150@newssvr11.news.prodigy.com...
> > I recall a project where an Ada newbie, having learned about enumerated
> > types, created one enumerated type that was three pages long.  That is,
> > the number of values in the type was so great that it took three pages
> > of 11 X 14 standard printer paper to contain it.
>
> Hey, I resemble that remark!
>
> The intermediate code definition for Janus/Ada includes an enumeration of
> 300 or so operations. The definition covers several pages (it has comments).
> That's used as the discriminant on a giant variant record that covers more
> than 6 pages. No newbies here. :-)
>
I did not mean to cast any aspersions on the knowledge and skill of those
who use enumerated types intelligently.   Rather, I meant to indicate that
enumerated types can be easily misused by those who are not thinking
about their life-cycle consequences.

In the project I was referencing, we had a large number of packages that
depended on the extra long enumeration type.  The enumeration type was
a list of weapon systems that could be engaged as necessary.   Every time
a new weapon was added, the entire system had to be recompiled.   I suggested,
and the project members agreed, that a table of weapons that could be
updated outside the software would give us greater flexibility.

One of the key problems in all of software practice is designing for
extensibility
and maintainability.    We want our software solutions to evolve gracefully,
over time, into more fully-featured systems, but we would like this to occur
without having to do the equivalent of "open-heart"  surgery every time a
new feature is required.    Enumerated types can have the effect of painting
one's self in to a corner.

Richard Riehle