Half Constrained Array Types and Slices

Half Constrained Array Types and Slices

[Jeffrey R. Carter]

Robert Duff present a concept from his idea for an Ada-like language (not called 
Duff) some time ago, that there was no need for "box" ("<>") in his language:

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

(IIRC)

In Ada we have constrained and unconstrained array types; I call this a "half 
constrained" array type so we have names for all of them. Since his language 
doesn't have box, I presume an unconstrained array type would be:

type Unconstrained (Lo : Positive; Hi : Natural) is array (Lo .. Hi) of Component;

while a constrained type would look like an Ada constrained type:

type Constrained is array (Lo .. Hi) of Component;

I was wondering how slices would work with this kind of syntax. I would expect a 
slice of a half-constrained array to have the fixed lower bound specified in its 
type declaration; that would differ from the others.

In Ada, we deal with slices of constrained array types by having the 1st named 
subtype be a constrained subtype of an unconstrained base type; that wouldn't 
seem to work here, since it would have a base type with 2 discriminants and a 
subtype with only 1.

-- 
Jeff Carter
"C's solution to this [variable-sized arrays] has real problems,
and people who are complaining about safety definitely have a point."
Dennis Ritchie
25

Re: Half Constrained Array Types and Slices

[Dmitry A. Kazakov]

On Thu, 02 Mar 2006 05:00:06 GMT, Jeffrey R. Carter wrote:

> Robert Duff present a concept from his idea for an Ada-like language (not called 
> Duff) some time ago, that there was no need for "box" ("<>") in his language:
> 
> type String (Length : Natural) is array (1 .. Length) of Character;

Not only this. Discriminants for arrays would also allow nice things like:

type Table (Element_Size : Natural) is
   array (...) of String (1..Element_Size);

or

type Container (Element_Type : Tag) is
   array (...) of Element'Class (Tag => Element_Type);

> (IIRC)
> 
> In Ada we have constrained and unconstrained array types; I call this a "half 
> constrained" array type so we have names for all of them. Since his language 
> doesn't have box, I presume an unconstrained array type would be:
> 
> type Unconstrained (Lo : Positive; Hi : Natural) is array (Lo .. Hi) of Component;

Rather:

type Unconstrained (Lo : Positive; Hi : Natural) is
    array (Integer range Lo .. Hi) of Component;

> while a constrained type would look like an Ada constrained type:
> 
> type Constrained is array (Lo .. Hi) of Component;
> 
> I was wondering how slices would work with this kind of syntax. I would expect a 
> slice of a half-constrained array to have the fixed lower bound specified in its 
> type declaration; that would differ from the others.
> 
> In Ada, we deal with slices of constrained array types by having the 1st named 
> subtype be a constrained subtype of an unconstrained base type; that wouldn't 
> seem to work here, since it would have a base type with 2 discriminants and a 
> subtype with only 1.

subtype Half_Constrained (Length : Natural) is Unconstrained (1, Length);

BTW, starting to modify Ada, one should introduce index types and allow
discriminants of any type. Then a range of indices could be just one
discriminant rather than two.

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

Re: Half Constrained Array Types and Slices

[Larry Kilgallen]

In article <qZuNf.2045$6I.1540@newsread3.news.pas.earthlink.net>, "Jeffrey R. Carter" <spam@spam.com> writes:

> In Ada we have constrained and unconstrained array types; I call this a "half 
> constrained" array type so we have names for all of them. Since his language 
> doesn't have box, I presume an unconstrained array type would be:
> 
> type Unconstrained (Lo : Positive; Hi : Natural) is array (Lo .. Hi) of Component;

That looks to me very much like Pascal.

Re: Half Constrained Array Types and Slices

[Georg Bauhaus]

On Thu, 2006-03-02 at 09:34 +0100, Dmitry A. Kazakov wrote:
> On Thu, 02 Mar 2006 05:00:06 GMT, Jeffrey R. Carter wrote:


> > type String (Length : Natural) is array (1 .. Length) of Character;
> 
> Not only this. Discriminants for arrays would also allow nice things like:
> 
> type Table (Element_Size : Natural) is
>    array (...) of String (1..Element_Size);

If you didn't dislike generics that much,

generic
   Element_Size: NATURAL;
package String_Tables is

   subtype SIZED_STRING is STRING(1.. Element_Size);

   type TABLE is array(POSITIVE range <>) of SIZED_STRING;

end String_Tables;

Re: Half Constrained Array Types and Slices

[Dmitry A. Kazakov]

On Thu, 02 Mar 2006 16:34:50 +0100, Georg Bauhaus wrote:

> On Thu, 2006-03-02 at 09:34 +0100, Dmitry A. Kazakov wrote:
>> On Thu, 02 Mar 2006 05:00:06 GMT, Jeffrey R. Carter wrote:
> 
>>> type String (Length : Natural) is array (1 .. Length) of Character;
>> 
>> Not only this. Discriminants for arrays would also allow nice things like:
>> 
>> type Table (Element_Size : Natural) is
>>    array (...) of String (1..Element_Size);
> 
> If you didn't dislike generics that much,
>
> generic
>    Element_Size: NATURAL;
> package String_Tables is
> 
>    subtype SIZED_STRING is STRING(1.. Element_Size);
> 
>    type TABLE is array(POSITIVE range <>) of SIZED_STRING;
> 
> end String_Tables;

Nope:

type Table (Element_Size : Natural) is
   array (...) of String (1..Element_Size);

function Read_From_File (File : File_Type) return Table;
function Write_To_File (File : File_Type; X : Table);
   -- Notice indefinite formal parameters and results are OK

subtype Punched_Cards is Table (80);
   -- Subtypes are OK

This is why I dislike generics. Each instance of String_Tables produces an
independent type. So there is no either named type or objects of the class
TABLE.

----
Note that this problem is known since Pascal. Strings in original Pascal
were of different types, when they had different lengths. Ada 83 introduced
the idea of unconstrained types to handle this nuisance. So different sizes
induced subtypes rather than types. Though the latter were also possible
using "type is new."

Generics is not Ada! (:-))

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

Re: Half Constrained Array Types and Slices

[Jeffrey R. Carter]

Dmitry A. Kazakov wrote:

> subtype Half_Constrained (Length : Natural) is Unconstrained (1, Length);

Again, you have a subtype with 1 discriminant of a type with 2. Are you saying 
that should be legal?

-- 
Jeff Carter
"You cheesy lot of second-hand electric donkey-bottom biters."
Monty Python & the Holy Grail
14

Re: Half Constrained Array Types and Slices

[Jeffrey R. Carter]

Larry Kilgallen wrote:

> In article <qZuNf.2045$6I.1540@newsread3.news.pas.earthlink.net>, "Jeffrey R. Carter" <spam@spam.com> writes:
>>
>>type Unconstrained (Lo : Positive; Hi : Natural) is array (Lo .. Hi) of Component;
> 
> That looks to me very much like Pascal.

I used Turbo Pascal quite a bit in the 1980s, and it had nothing that resembled 
this. Are the versions of Pascal that have constructs like this?

-- 
Jeff Carter
"You cheesy lot of second-hand electric donkey-bottom biters."
Monty Python & the Holy Grail
14

Re: Half Constrained Array Types and Slices

[Dmitry A. Kazakov]

On Thu, 02 Mar 2006 20:06:03 GMT, Jeffrey R. Carter wrote:

> Dmitry A. Kazakov wrote:
> 
>> subtype Half_Constrained (Length : Natural) is Unconstrained (1, Length);
> 
> Again, you have a subtype with 1 discriminant of a type with 2. Are you saying 
> that should be legal?

Why not?

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

Re: Half Constrained Array Types and Slices

[Robert A Duff]

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

> Robert Duff present a concept from his idea for an Ada-like language
> (not called Duff) some time ago, that there was no need for "box" ("<>")
> in his language:
> 
> type String (Length : Natural) is array (1 .. Length) of Character;
> 
> (IIRC)

Yeah.  But I did not invent this idea.  Something like this was proposed
as a language change during the Ada 9X design.  Probably invented by
Tucker before I joined the project.

(Except my hobby language can use this idea to _simplify_, whereas Ada
would have had to add this feature and still keep the "range <>"
notation for compatibility.)

> In Ada we have constrained and unconstrained array types; I call this a
> "half constrained" array type so we have names for all of them. Since
> his language doesn't have box, I presume an unconstrained array type
> would be:
> 
> type Unconstrained (Lo : Positive; Hi : Natural) is array (Lo .. Hi) of Component;
> 
> while a constrained type would look like an Ada constrained type:
> 
> type Constrained is array (Lo .. Hi) of Component;
> 
> I was wondering how slices would work with this kind of syntax. I would
> expect a slice of a half-constrained array to have the fixed lower bound
> specified in its type declaration;

Definitely.

>... that would differ from the others.

I'm not so sure about that.  I'm inclined to say slices always slide to
the lower bound.  The idea that X(3..5) should have lower bound 3 seems
to make sense at first, until you think about passing that slice as a
parameter.  The called procedure should not care that it's a slice at
all -- much less the particular bounds used to create it.  The Ada rule
violates abstraction.  Same issue for function returns.

It's also rather error prone.  It's easy to write code that assumes all
Strings start at 1 (and such code is more readable than the more-general
(correct) code using complicated expressions involving
'First/'Last/'Length).  And 99.9% of Strings _do_ have 'First=1,
so one doesn't notice the bug until it's too late.

> In Ada, we deal with slices of constrained array types by having the 1st
> named subtype be a constrained subtype of an unconstrained base type;
> that wouldn't seem to work here, since it would have a base type with 2
> discriminants and a subtype with only 1.

Yes, I agree that's a problem.  Various possible solutions come to
mind.  Probably the simplest is to outlaw slices of constrained arrays.
After all, what is the sense in saying "all arrays of type T go from
1 to 5", and then turn around and create values of type T with bounds
3..4?  Even in Ada as is, there is very little use for this feature.
You can do:

    type Bits is array(Int range 0..31) of Boolean;

    function Rotate(X: Bits) return Boolean Bits is
    begin
        return X(31) & X(0..30);
    end Rotate;

But that's not worth much language complexity.  If you want that,
declare an unconstrained (doubly unconstrained?) array, along with
constrained subtype(s).

I can talk about more and more exotic ideas, depending on how far away
from Ada you're willing to contemplate.  ;-)  For example, I'd like to
be able to do:

    type T(D1: ...; D2: ...) is ...
    subtype S is T(D1 => 17); -- Illegal in Ada to partially constrain!

Or maybe the syntax should be "T(D1 => 17, D2 => <>)".

Also:

    type Memory_Block(Length: Positive) is array(0..Length-1) of Byte;
                                                          ^^
                                        That ain't Ada!  ;-)
Not even close.  Ada forbids discriminants as part of an expression like
that.  I think pure (no side effects) expressions should be OK.  But
there's a whole lot of language mechanism needed to teach the compiler
to know which expressions are pure.

- Bob

Re: Half Constrained Array Types and Slices

[Robert A Duff]

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

> > type Unconstrained (Lo : Positive; Hi : Natural) is array (Lo .. Hi) of Component;
> 
> Rather:
> 
> type Unconstrained (Lo : Positive; Hi : Natural) is
>     array (Integer range Lo .. Hi) of Component;

Either one should work.  The existing rules for overload resolution
understand that Lo..Hi implies Integer.

- Bob

Re: Half Constrained Array Types and Slices

[Robert A Duff]

Kilgallen@SpamCop.net (Larry Kilgallen) writes:

> In article <qZuNf.2045$6I.1540@newsread3.news.pas.earthlink.net>, "Jeffrey R. Carter" <spam@spam.com> writes:
> 
> > In Ada we have constrained and unconstrained array types; I call this a "half 
> > constrained" array type so we have names for all of them. Since his language 
> > doesn't have box, I presume an unconstrained array type would be:
> > 
> > type Unconstrained (Lo : Positive; Hi : Natural) is array (Lo .. Hi) of Component;
> 
> That looks to me very much like Pascal.

Really?  I don't know any version of Pascal that allows anything like
that.

- Bob

Re: Half Constrained Array Types and Slices

[Robert A Duff]

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

> Dmitry A. Kazakov wrote:
> 
> > subtype Half_Constrained (Length : Natural) is Unconstrained (1, Length);
> 
> Again, you have a subtype with 1 discriminant of a type with 2. Are you
> saying that should be legal?

It is already legal for derived types:

    type U(Lo, Hi: Integer) is
        record
            A: String(Lo..Hi);
        end record;
    type Half(Hi: Integer) is new U(Lo => 1, Hi => Hi);

Not quite the same thing as a subtype...

- Bob

Re: Half Constrained Array Types and Slices

[Jeffrey R. Carter]

Robert A Duff wrote:
> 
> (Except my hobby language can use this idea to _simplify_, whereas Ada
> would have had to add this feature and still keep the "range <>"
> notation for compatibility.)

Right. I suppose you could introduce a notation like

Positive range 1 .. <>

to get a similar effect without having 2 ways to do an unconstrained array.

> I'm not so sure about that.  I'm inclined to say slices always slide to
> the lower bound.  The idea that X(3..5) should have lower bound 3 seems
> to make sense at first, until you think about passing that slice as a
> parameter.  The called procedure should not care that it's a slice at
> all -- much less the particular bounds used to create it.  The Ada rule
> violates abstraction.  Same issue for function returns.

OK. So you're saying a slice (Lo .. Hi) of an unconstrained array type would 
slide to Index'First .. Index'First + Hi - Lo?

> Yes, I agree that's a problem.  Various possible solutions come to
> mind.  Probably the simplest is to outlaw slices of constrained arrays.
> After all, what is the sense in saying "all arrays of type T go from
> 1 to 5", and then turn around and create values of type T with bounds
> 3..4?  Even in Ada as is, there is very little use for this feature.
> You can do:
> 
>     type Bits is array(Int range 0..31) of Boolean;
> 
>     function Rotate(X: Bits) return Boolean Bits is
>     begin
>         return X(31) & X(0..30);
>     end Rotate;
> 
> But that's not worth much language complexity.  If you want that,
> declare an unconstrained (doubly unconstrained?) array, along with
> constrained subtype(s).

That was the rule in Ada 83, IIRC. It apparently bit enough people that it was 
changed in Ada 95.

> I can talk about more and more exotic ideas, depending on how far away
> from Ada you're willing to contemplate.  ;-)  For example, I'd like to
> be able to do:
> 
>     type T(D1: ...; D2: ...) is ...
>     subtype S is T(D1 => 17); -- Illegal in Ada to partially constrain!
> 
> Or maybe the syntax should be "T(D1 => 17, D2 => <>)".

In that case, this would be how you'd deal with slices of half-constrained 
arrays if you wanted to keep the bounds; the base type would be unconstrained 
and the first-named subtype would be partially constrained.

-- 
Jeff Carter
"You cheesy lot of second-hand electric donkey-bottom biters."
Monty Python & the Holy Grail
14

Re: Half Constrained Array Types and Slices

[Dmitry A. Kazakov]

On Fri, 03 Mar 2006 05:15:00 GMT, Jeffrey R. Carter wrote:

> In that case, this would be how you'd deal with slices of half-constrained 
> arrays if you wanted to keep the bounds; the base type would be unconstrained 
> and the first-named subtype would be partially constrained.

But the anonymous type of a slice is not one of the original array. It 
could even be not a subtype. It becomes obvious if we consider (not allowed 
in Ada) slices of two-dimensional arrays (submatrix, column, row, element.) 
I cannot see how an index constraint of the original array subtype could 
propagate down to the slice. So I don't much trust the idea of sliding 
indices in slices. Sliding might be in the contract of ":=" or "&" when 
arguments are slices. And in any case that depends on the index type, which 
has to be (at least) ordered.

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

Re: Half Constrained Array Types and Slices

[Robert A Duff]

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

> Robert A Duff wrote:
> > I'm not so sure about that.  I'm inclined to say slices always slide to
> > the lower bound.  The idea that X(3..5) should have lower bound 3 seems
> > to make sense at first, until you think about passing that slice as a
> > parameter.  The called procedure should not care that it's a slice at
> > all -- much less the particular bounds used to create it.  The Ada rule
> > violates abstraction.  Same issue for function returns.
> 
> OK. So you're saying a slice (Lo .. Hi) of an unconstrained array type
> would slide to Index'First .. Index'First + Hi - Lo?

Yes.

> > Yes, I agree that's a problem.  Various possible solutions come to
> > mind.  Probably the simplest is to outlaw slices of constrained arrays.
> > After all, what is the sense in saying "all arrays of type T go from
> > 1 to 5", and then turn around and create values of type T with bounds
> > 3..4?  Even in Ada as is, there is very little use for this feature.
> > You can do:
> >     type Bits is array(Int range 0..31) of Boolean;
> >     function Rotate(X: Bits) return Boolean Bits is
> >     begin
> >         return X(31) & X(0..30);
> >     end Rotate;
> > But that's not worth much language complexity.  If you want that,
> > declare an unconstrained (doubly unconstrained?) array, along with
> > constrained subtype(s).
> 
> That was the rule in Ada 83, IIRC. It apparently bit enough people that
> it was changed in Ada 95.

I don't know of any change between 83 and 95, here.
But I could be forgetting something; please remind me.

Anyway, my suggestion was to forbid (at compile time) any slices that
might cause confusion in the mind of the programmer, or run-time
errors.  I think I'd be happy with a language that allows slices only
when the lower-bound is fixed.

I'd also be happy to eliminate slices as l-values.  They cause a lot of
implementation difficulty for not much benefit.  Or else go the whole
hog, and allow X(5..10) := "xx", which does not work in Ada, because
that would require changing the length of the whole thing.

> > I can talk about more and more exotic ideas, depending on how far away
> > from Ada you're willing to contemplate.  ;-)  For example, I'd like to
> > be able to do:
> >     type T(D1: ...; D2: ...) is ...
> >     subtype S is T(D1 => 17); -- Illegal in Ada to partially constrain!
> > Or maybe the syntax should be "T(D1 => 17, D2 => <>)".
> 
> In that case, this would be how you'd deal with slices of
> half-constrained arrays if you wanted to keep the bounds; the base type
> would be unconstrained and the first-named subtype would be partially
> constrained.

Yes, but this is all very not-Ada in several ways.
There are probably some semantic anomalies I have not considered.

- Bob

Re: Half Constrained Array Types and Slices

[Larry Kilgallen]

In article <wccek1ky3nj.fsf@shell01.TheWorld.com>, Robert A Duff <bobduff@shell01.TheWorld.com> writes:
> Kilgallen@SpamCop.net (Larry Kilgallen) writes:
> 
>> In article <qZuNf.2045$6I.1540@newsread3.news.pas.earthlink.net>, "Jeffrey R. Carter" <spam@spam.com> writes:
>> 
>> > In Ada we have constrained and unconstrained array types; I call this a "half 
>> > constrained" array type so we have names for all of them. Since his language 
>> > doesn't have box, I presume an unconstrained array type would be:
>> > 
>> > type Unconstrained (Lo : Positive; Hi : Natural) is array (Lo .. Hi) of Component;
>> 
>> That looks to me very much like Pascal.
> 
> Really?  I don't know any version of Pascal that allows anything like
> that.

VAX/DEC/HP Pascal uses something like that not in a type declaration
but in describing the type of a routine parameter.

Re: Half Constrained Array Types and Slices

[Jeff Carter]

Robert A Duff wrote:
>
> I don't know of any change between 83 and 95, here.
> But I could be forgetting something; please remind me.

I just checked my copy of the green book, and you're right. I seem to
recall some problem with slices of constrained types in Ada 83, but I
guess I'm mistaken.

> I'd also be happy to eliminate slices as l-values.  They cause a lot of
> implementation difficulty for not much benefit.  Or else go the whole
> hog, and allow X(5..10) := "xx", which does not work in Ada, because
> that would require changing the length of the whole thing.

What would that do?

> Yes, but this is all very not-Ada in several ways.
> There are probably some semantic anomalies I have not considered.

Of course, it's not-Ada by definition. But it's fun to talk about.

I've been thinking about a language that allows null arrays, even for
degenerate types like

type Single is (One);

type Degenerate is array (Single range <>) of Whatever;

Suppose we could say something like

V : Degenerate (null range); -- V'Length = 0

Now we can do things like

for I in V'range loop -- loop is not entered

if X in V'range -- always False

Y : Degenerate (V'range); -- Y'Length = 0

More importantly, we do these kinds of things in subprograms with
Degenerate parameters.

If Degenerate is a string type, "" is meaningful.

We seem to be fine as long as we don't do V'Last. I can't figure out
how such a language should handle 'First and 'Last for such a
value/object. Probably a failure of imagination on my part.

--
Jeff Carter

jrcarter commercial-at acm [period | full stop] org

Re: Half Constrained Array Types and Slices

[Dmitry A. Kazakov]

On 6 Mar 2006 09:50:16 -0800, Jeff Carter wrote:

> We seem to be fine as long as we don't do V'Last. I can't figure out
> how such a language should handle 'First and 'Last for such a
> value/object.

Compile error, if the index type isn't ordered (= does not have 'First,
'Last, "<", "=").

Otherwise, Constraint_Error.

BTW, in the second case there is an interesting possibility, I didn't think
much about. If the language had supertyping, then the compiler could create
an anonymous supertype of the index type with one or two more values. These
imaginary values could then be returned as 'First and 'Last. The idea is
same as in IEEE's positive and negative infinities. Of course these values
could have different representation than natural index. Yet the following
will be illegal:

I : Index := A'First; -- This may cause C_E while type conversion

I know no good way to name the type. Even Index'Class would be wrong.

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

Re: Half Constrained Array Types and Slices

[Martin Krischik]

Larry Kilgallen wrote:

> In article <wccek1ky3nj.fsf@shell01.TheWorld.com>, Robert A Duff
> <bobduff@shell01.TheWorld.com> writes:
>> Kilgallen@SpamCop.net (Larry Kilgallen) writes:
>> 
>>> In article <qZuNf.2045$6I.1540@newsread3.news.pas.earthlink.net>,
>>> "Jeffrey R. Carter" <spam@spam.com> writes:
>>> 
>>> > In Ada we have constrained and unconstrained array types; I call this
>>> > a "half constrained" array type so we have names for all of them.
>>> > Since his language doesn't have box, I presume an unconstrained array
>>> > type would be:
>>> > 
>>> > type Unconstrained (Lo : Positive; Hi : Natural) is array (Lo .. Hi)
>>> > of Component;
>>> 
>>> That looks to me very much like Pascal.
>> 
>> Really?  I don't know any version of Pascal that allows anything like
>> that.
> 
> VAX/DEC/HP Pascal uses something like that not in a type declaration
> but in describing the type of a routine parameter.

Yep. It's an optional feature of ISO pascal. Not many pascal compiler
actually implemented it.

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: Half Constrained Array Types and Slices

[Stefan Lucks]

On Mon, 6 Mar 2006, Jeff Carter wrote:

> Suppose we could say something like
>
> V : Degenerate (null range); -- V'Length = 0
>
> Now we can do things like
>
> for I in V'range loop -- loop is not entered
>
> if X in V'range -- always False
>
> Y : Degenerate (V'range); -- Y'Length = 0
>
> More importantly, we do these kinds of things in subprograms with
> Degenerate parameters.
>
> If Degenerate is a string type, "" is meaningful.
>
> We seem to be fine as long as we don't do V'Last. I can't figure out
> how such a language should handle 'First and 'Last for such a
> value/object. Probably a failure of imagination on my part.

Don't use V'Last at all ... but a new attribute V'Beyond instead.

Informally, V'Beyond should be the "next" value beyond V'last.

To avod unneccessary runtime errors, such a (non-Ada-)language should
rather not provide V'Last at all ...

-- 
Stefan Lucks      Th. Informatik, Univ. Mannheim, 68131 Mannheim, Germany
            e-mail: lucks@th.informatik.uni-mannheim.de
            home: http://th.informatik.uni-mannheim.de/people/lucks/
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------

Re: Half Constrained Array Types and Slices

[Jeff Carter]

Dmitry A. Kazakov wrote:
>
> BTW, in the second case there is an interesting possibility, I didn't think
> much about. If the language had supertyping, then the compiler could create
> an anonymous supertype of the index type with one or two more values. These
> imaginary values could then be returned as 'First and 'Last. The idea is
> same as in IEEE's positive and negative infinities. Of course these values
> could have different representation than natural index. Yet the following
> will be illegal:
>
> I : Index := A'First; -- This may cause C_E while type conversion

I suppose this could be handled much as we handle integer types, with a
base type that is different from the 1st-named subtype. So a
declaration such as

type Single is (One);

would be implemented as

type Single'Base is (First, One);

subtype Single is Single'Base range One .. One;

Then, given

type Degenerate is array (Single range <>) of Whatever;

V : Degenerate (null range);

we can say that V'Last is of type Single'Base. V'First = One, V'Last =
First.

Probably we'd do this for all enumeration types; that would allow ""
for all string types. Since we define Single'Pos (One) to be zero,
Single'Base'Pos (First) would have to be -1. Would that work? Or would
it be better for position numbers to start at 1?

--
Jeff Carter

jrcarter commercial-at acm [period | full stop] org

Re: Half Constrained Array Types and Slices

[Dmitry A. Kazakov]

On 7 Mar 2006 11:02:49 -0800, Jeff Carter wrote:

> Dmitry A. Kazakov wrote:
>>
>> BTW, in the second case there is an interesting possibility, I didn't think
>> much about. If the language had supertyping, then the compiler could create
>> an anonymous supertype of the index type with one or two more values. These
>> imaginary values could then be returned as 'First and 'Last. The idea is
>> same as in IEEE's positive and negative infinities. Of course these values
>> could have different representation than natural index. Yet the following
>> will be illegal:
>>
>> I : Index := A'First; -- This may cause C_E while type conversion
> 
> I suppose this could be handled much as we handle integer types, with a
> base type that is different from the 1st-named subtype. So a
> declaration such as
> 
> type Single is (One);
> 
> would be implemented as
> 
> type Single'Base is (First, One);
> 
> subtype Single is Single'Base range One .. One;
>
> Then, given
> 
> type Degenerate is array (Single range <>) of Whatever;
> 
> V : Degenerate (null range);
> 
> we can say that V'Last is of type Single'Base. V'First = One, V'Last =
> First.
>
> Probably we'd do this for all enumeration types; that would allow ""
> for all string types. Since we define Single'Pos (One) to be zero,
> Single'Base'Pos (First) would have to be -1. Would that work? Or would
> it be better for position numbers to start at 1?

Maybe it will work. At least it looks consistent.

An interesting related question is:

type Single is (One);
for Single'Size use 0; -- Can I have it really 0?

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

Re: Half Constrained Array Types and Slices

[brian.b.mcguinness]

Jeff Carter wrote:
> I've been thinking about a language that allows null arrays, even for
> degenerate types like
>
> type Single is (One);
>
> type Degenerate is array (Single range <>) of Whatever;
>
> Suppose we could say something like
>
> V : Degenerate (null range); -- V'Length = 0
>
> Now we can do things like
>
> for I in V'range loop -- loop is not entered
>
> if X in V'range -- always False
>
> Y : Degenerate (V'range); -- Y'Length = 0
>
> More importantly, we do these kinds of things in subprograms with
> Degenerate parameters.
>
> If Degenerate is a string type, "" is meaningful.
>
> We seem to be fine as long as we don't do V'Last. I can't figure out
> how such a language should handle 'First and 'Last for such a
> value/object. Probably a failure of imagination on my part.

Perhaps I misunderstand you, but hasn't this capability already been
provided in the 
Vector container?

--- Brian

Re: Half Constrained Array Types and Slices

[Jeff Carter]

brian.b.mcguinness@lmco.com wrote:
>
> Perhaps I misunderstand you, but hasn't this capability already been
> provided in the
> Vector container?
Not really. It requires a numeric index type, with Index'Base'First <
Index'First. It's also not part of the core language.

--
Jeff Carter

jrcarter commercial-at acm [period | full stop] org

Re: Half Constrained Array Types and Slices

[Robert A Duff]

"Jeff Carter" <jcgoogle@earthlink.net> writes:

> Robert A Duff wrote:
> > I'd also be happy to eliminate slices as l-values.  They cause a lot of
> > implementation difficulty for not much benefit.  Or else go the whole
> > hog, and allow X(5..10) := "xx", which does not work in Ada, because
> > that would require changing the length of the whole thing.
> 
> What would that do?

It would replace the slice X(5..10) with a shorter one,
thus shrinking the string.  That's what you might want
in a string-processing language...  As I said, very not-Ada.

> > Yes, but this is all very not-Ada in several ways.
> > There are probably some semantic anomalies I have not considered.
> 
> Of course, it's not-Ada by definition. But it's fun to talk about.

Yes.

> I've been thinking about a language that allows null arrays, even for
> degenerate types like
> 
> type Single is (One);
> 
> type Degenerate is array (Single range <>) of Whatever;

I don't quite see the point of this.  If 'Length = 0,
it seems to me, then the index type must be some sort of integer,
or something like that.  It depends on how far afield you want
to go.  For example, do you like "array(String range <>) of Integer"?
There's no _range_ there...

The idea that 'Range is equivalent to 'First..'Last seems reasonable to
me...

- Bob

Re: Half Constrained Array Types and Slices

[Robert A Duff]

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

> An interesting related question is:
> 
> type Single is (One);
> for Single'Size use 0; -- Can I have it really 0?

'Size should be 0 by default in this case.

- Bob

Re: Half Constrained Array Types and Slices

[Jeffrey R. Carter]

Robert A Duff wrote:
> 
> I don't quite see the point of this.  If 'Length = 0,
> it seems to me, then the index type must be some sort of integer,
> or something like that.  It depends on how far afield you want
> to go.  For example, do you like "array(String range <>) of Integer"?
> There's no _range_ there...

I think the index type should be discrete. But surely it doesn't need to be an 
integer:

with Ada.Text_IO;
procedure Null_Range is
    type A is (B, C);

    type D is array (A range <>) of Integer;

    E : D (C .. B);
begin -- Null_Range
    Ada.Text_IO.Put_Line (Item => A'Image (E'Last) );
end Null_Range;

This is valid Ada. With GNAT, it outputs B. However, if D were a string type, "" 
would not be valid for it.

> The idea that 'Range is equivalent to 'First..'Last seems reasonable to
> me...

I'm not saying it's a good idea. I'm just wondering what the consequences of it are.

-- 
Jeff Carter
"Crucifixion's a doddle."
Monty Python's Life of Brian
82

Re: Half Constrained Array Types and Slices

[Dmitry A. Kazakov]

On 09 Mar 2006 17:44:59 -0500, Robert A Duff wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> An interesting related question is:
>> 
>> type Single is (One);
>> for Single'Size use 0; -- Can I have it really 0?
> 
> 'Size should be 0 by default in this case.

But Single'Base'Size cannot be. I.e. subtypes should be allowed to have
different representation.

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

Re: Half Constrained Array Types and Slices

[Dmitry A. Kazakov]

On Fri, 10 Mar 2006 04:28:59 GMT, Jeffrey R. Carter wrote:

> Robert A Duff wrote:
>> 
>> I don't quite see the point of this.  If 'Length = 0,
>> it seems to me, then the index type must be some sort of integer,
>> or something like that.  It depends on how far afield you want
>> to go.  For example, do you like "array(String range <>) of Integer"?
> 
> I think the index type should be discrete.

No. It should have some interface, which we could call an "abstract index
type." If that type is ordered then ranges have meaning. Strings are
ordered, so ranges are theoretically OK.

[ Discreteness does not imply ranges. Modular types is an example of a
discrete type, which is very difficult for ranges. Order is more important.
]

>> There's no _range_ there...

There is, but for most of finite bounds a string range would contain an
uncountable number of items. For example "A".."B". This range includes
"AA", "AAA", etc. This might be is undesirable, however, it would be
interesting to think about how to deal with bounded infinite ranges, like
"A".."B". After all [universal] floating-point ranges are allowed in Ada,
and they aren't finite...

>> The idea that 'Range is equivalent to 'First..'Last seems reasonable to
>> me...
> 
> I'm not saying it's a good idea. I'm just wondering what the consequences of it are.

I don't think this idea is good. Mathematicians confront this issue as
well. So they introduced open and closed sets and carefully distinguish Min
from Inf and Max from Sup. What about range notations equivalent to ]a,b]
or (a,b]? First..Last is like [a,b].

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

Re: Half Constrained Array Types and Slices

[Robert A Duff]

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

> There is, but for most of finite bounds a string range would contain an
> uncountable number of items. For example "A".."B". This range includes
> "AA", "AAA", etc. This might be is undesirable, however, it would be
> interesting to think about how to deal with bounded infinite ranges, like
> "A".."B".

Note quite infinite, since X'Last <= Natural'Last for all Strings X.
And I suppose the highest value of String is:

    (Positive => Character'Last)

This leads nowhere useful!  ;-)

If you want "arrays" indexed by strings, you really want sparse arrays
implemented as hash tables or some such.  I call those "mappings", not
"arrays".  See the Containers library of Ada 2005.

>... After all [universal] floating-point ranges are allowed in Ada,
> and they aren't finite...

And they're not allowed in 'for' loops, nor as array indices.
Which is a good thing.

- Bob

Re: Half Constrained Array Types and Slices

[Robert A Duff]

"Jeffrey R. Carter" <spam.not.jrcarter@acm.not.spam.org> writes:

> I think the index type should be discrete. But surely it doesn't need to
> be an integer:
> 
> with Ada.Text_IO;
> procedure Null_Range is
>     type A is (B, C);
> 
>     type D is array (A range <>) of Integer;
> 
>     E : D (C .. B);
> begin -- Null_Range
>     Ada.Text_IO.Put_Line (Item => A'Image (E'Last) );
> end Null_Range;
> 
> This is valid Ada.

Indeed it is.  I don't think it's very useful, however.
My claim is that if you want empty arrays, you almost
certainly want to index them by (non-modular) integers.
Which is why I'm happy with the restriction in the Containers
library that Vector indices must be signed integers.

>... With GNAT, it outputs B. However, if D were a string
> type, "" would not be valid for it.
> 
> > The idea that 'Range is equivalent to 'First..'Last seems reasonable to
> > me...
> 
> I'm not saying it's a good idea. I'm just wondering what the
> consequences of it are.

I suppose the consequence is bugs -- rare cases where 'First and/or
'Last surprisingly raise Constraint_Error.

- Bob

Re: Half Constrained Array Types and Slices

[Dmitry A. Kazakov]

On 10 Mar 2006 12:33:46 -0500, Robert A Duff wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> There is, but for most of finite bounds a string range would contain an
>> uncountable number of items. For example "A".."B". This range includes
>> "AA", "AAA", etc. This might be is undesirable, however, it would be
>> interesting to think about how to deal with bounded infinite ranges, like
>> "A".."B".
> 
> Note quite infinite, since X'Last <= Natural'Last for all Strings X.
> And I suppose the highest value of String is:
> 
>     (Positive => Character'Last)
> 
> This leads nowhere useful!  ;-)

OK, but "universal string" indexed by universal integer are truly infinite.
(:-))

> If you want "arrays" indexed by strings, you really want sparse arrays
> implemented as hash tables or some such.  I call those "mappings", not
> "arrays".

Can't a map have indexing operation? Should indexing always imply ranges?

I think the visible interface of the corresponding index type should
determine whether ranges exist. If Map'Index'Succ isn't defined, then there
is no Map'Range and, so it is not an ordered container.

>>... After all [universal] floating-point ranges are allowed in Ada,
>> and they aren't finite...
> 
> And they're not allowed in 'for' loops, nor as array indices.
> Which is a good thing.

Nevertheless they exist. So there should be a rational answer why 0.0..1.0
is legal, but "A".."B" is not.

BTW, that the range bounds may be outside the range they specify, is not
unique for enumeration types. A similar thing shows itself for fixed point
types: delta ... range 0.0..1.0; It seems that the problem lies deeper...

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

Re: Half Constrained Array Types and Slices

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wccmzfyurm5.fsf@shell01.TheWorld.com...
> "Jeffrey R. Carter" <spam.not.jrcarter@acm.not.spam.org> writes:
> > I think the index type should be discrete. But surely it doesn't need to
> > be an integer:
> >
> > with Ada.Text_IO;
> > procedure Null_Range is
> >     type A is (B, C);
> >
> >     type D is array (A range <>) of Integer;
> >
> >     E : D (C .. B);
> > begin -- Null_Range
> >     Ada.Text_IO.Put_Line (Item => A'Image (E'Last) );
> > end Null_Range;
> >
> > This is valid Ada.
>
> Indeed it is.  I don't think it's very useful, however.
> My claim is that if you want empty arrays, you almost
> certainly want to index them by (non-modular) integers.
> Which is why I'm happy with the restriction in the Containers
> library that Vector indices must be signed integers.

I don't buy this, especially in the case of modular integers, but even in
the case of large enumeration sets (like Character). I don't see any reason
to think that integers are special; the whole reason for allowing
non-integer array indexes is for greater abstraction. Empty arrays are never
very useful, but I don't think there is much reason to say that they'll
useful in the one case but not the other. That's essentially that same as
saying that integers are more useful as array indexes; in that case, why
bother allowing anything else as array indexes? Of course, I was very
against the restriction in the Containers library, too...

                                     Randy.

Re: Half Constrained Array Types and Slices

[Jeffrey R. Carter]

Randy Brukardt wrote:

> I don't buy this, especially in the case of modular integers, but even in
> the case of large enumeration sets (like Character). I don't see any reason
> to think that integers are special; the whole reason for allowing
> non-integer array indexes is for greater abstraction. Empty arrays are never
> very useful, but I don't think there is much reason to say that they'll
> useful in the one case but not the other. That's essentially that same as
> saying that integers are more useful as array indexes; in that case, why
> bother allowing anything else as array indexes? Of course, I was very
> against the restriction in the Containers library, too...

FWIW, my opinions are closer to Brukardt's than to Duff's. However, null arrays 
are often useful; there are whole classes of recursive algorithms that look like

return G (X (X'First) ) & F (X (Index'Succ (X'First) .. X'Last) );

with a null array terminating the recursion.

-- 
Jeff Carter
"Apart from the sanitation, the medicine, education, wine,
public order, irrigation, roads, the fresh water system,
and public health, what have the Romans ever done for us?"
Monty Python's Life of Brian
80

Re: Half Constrained Array Types and Slices

[Niklas Holsti]

Jeffrey R. Carter wrote:
> Randy Brukardt wrote:
> 
>> ... Empty arrays are never very useful, ...
> 
> FWIW, my opinions are closer to Brukardt's than to Duff's. However, null 
> arrays are often useful; there are whole classes of recursive algorithms 
> that look like
> 
> return G (X (X'First) ) & F (X (Index'Succ (X'First) .. X'Last) );
> 
> with a null array terminating the recursion.

I second Jeffrey's opinion. I find that empty arrays are very
useful for my applications (program analysis). I could live
with a language where A'First and A'Last are available only when
A'Length > 0 and might raise Constraint_Error if A'Length = 0.
However, "for I in A'Range loop .. end loop" should work even
when A'Length = 0 (and do nothing in that case).

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .