Array Help?

Robert A Duff writes on comp.lang.ada:
> Robert A Duff <bobduff@shell01.TheWorld.com> writes:
>
>> % ./array_test
>>
>> raised SYSTEM.ASSERTIONS.ASSERT_FAILURE : predicate failed at array_test.adb:14
>
> Actually, I just realized there's a workaround for the slice problem.
> The following does not raise any exception.
>
> procedure Array_Test is
>
> type Integer_Array is array (Positive range <>) of Integer
> with Dynamic_Predicate => Integer_Array'First = 1;
>
> procedure Foo (Param : in out Integer_Array) is
> begin
> null;
> end Foo;
>
> A : Integer_Array (1 .. 10) := (others => 0);
>
> subtype Slide is Integer_Array(1..6);
> begin
> Foo (Slide(A (3 .. 8)));

Doesn't that involve copy-in and copy-out between the slice and a
temporary object of type Slide? Grossly inefficient, methinks.

> end Array_Test;
>
> But that's kind of tricky; I wouldn't do that without copious
> comments. And some constants or something to avoid violating the DRY
> principle.

Yes. For Adam: DRY=Don't Repeat Yourself.

--
Ludovic Brenta.

On Wed, 29 Feb 2012 18:15:52 -0500, Robert A Duff wrote:

> Ada allows you to fix 'First and 'Last, and it allows you to let
> both vary. What's missing is a way to fix 'First, but allow
> 'Last to vary. I sort of implied that a predicate should do that,
> but that's wrong. There should be SOME way to do it. And for
> completeness, I'd allow fixing 'Last, but allowing 'First to vary,
> although that's much less useful.

That sort of thing has nothing to do with constraining, so the idea to get
it using a predicate is straight wrong.

> I'm certainly not saying "all arrays should start at 1". I'm saying
> "there should a way to declare an array type such that all objects of
> that type start at 1 (or any other value) while allowing 'Last to
> vary".

The array abstraction is that the given index denotes the *same* array
element. Sliding indices is another abstraction (ordinal, sequence) and it
does not require arrays having separate index types. Ordinals are same for
all sequences.

The point is that all cases where you wanted arrays to start from some
element are actually views on an array as a sequence of elements. Provide
that view and the problem would vanish. This would also eliminate the
problem of constructing empty arrays and simplify generics dealing with
arrays.

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

Ludovic Brenta <ludovic@ludovic-brenta.org> writes:

> Robert A Duff writes on comp.lang.ada:
>> Foo (Slide(A (3 .. 8)));
>
> Doesn't that involve copy-in and copy-out between the slice and a
> temporary object of type Slide? Grossly inefficient, methinks.

No, I don't see any need for the compiler to make a copy here.
It just needs to pass the 1..6 bounds, plus a pointer to
the array elements.

I'm too lazy to check the machine code to see whether GNAT
makes a copy, but I don't see why it would. Nor any other
Ada compiler.

- Bob

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

> That sort of thing has nothing to do with constraining, so the idea to get
> it using a predicate is straight wrong.

Yes, I agree. That's what I meant when I said, "I sort of implied that
a predicate should do that, but that's wrong."

- Bob

On Wed, 29 Feb 2012, Robert A Duff wrote:

> Sure, slices are useful, and I use them. But I wouldn't mind too
> much if they didn't exist. It's trivial to write a Slice function
> that does what "A(F..L)" does.

A predefined function Slice for all (at least for all one-dimensional)
array types would be OK. Having to instantiate a generic or to write a
slice function on ones own each time one needs a slice would clutter the
code ...

> You didn't address my point about l-values.

There is a simple reason why I didn't address that part of your posting: I
don't have a strong point in favor of slices as l-values.

> None of your slices above are l-values. L-value slices cause a lot of
> implementation trouble, and are nearly useless -- the language would be
> better off without them.

I haven't been aware that l-value slices are so difficult to implement,
and I wouldn't mind to put them away.

> > procedure Sort(Items: in out array(generic Positive range <>) of T) is
>
> Interesting idea.

Thank you!

Stefan

--
---- Stefan.Lucks (at) uni-weimar.de, University of Weimar, Germany ----
<http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
------ I love the taste of Cryptanalysis in the morning! ------

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wccy5rls0hl.fsf@shell01.TheWorld.com...
> stefan-lucks@see-the.signature writes:
....
> Sure, slices are useful, and I use them. But I wouldn't mind too
> much if they didn't exist. It's trivial to write a Slice function
> that does what "A(F..L)" does.

In Ada 2012, it's not that hard to write a Slice_LValue function that would
let you assign into A(F..L). It's in fact the key to my half-formed
Root_String'Class proposal (plus the indexing features already in Ada 2012 -
the only thing missing is string literals).

> You didn't address my point about l-values. None of your slices
> above are l-values. L-value slices cause a lot of implementation
> trouble, and are nearly useless -- the language would be better
> off without them.

I don't buy this at all. I've tried using loops instead of slices to do
string manipulation (early Janus/Ada didn't have slices), and the results
had horrific readability and performance. Even today, the optimization of
slices is much better than the optimization of the supposedly equivalent
loop (mainly because no optimization is needed to optimize the slice; the
code is already nearly optimal when created by the Janus/Ada front end).
Obviously, this could be different on a different Ada compiler, but I'm at
least a bit skeptical.

>> On the other hand, I agree that the fact that array slices carry their
>> original indices with them is a misfeature of Ada.
>>
>> I would appreciate way to convert ingoing parameters into some standard
>> indexing. For example (inventing a new syntax variant on the fly):
>>
>> procedure Sort(Items: in out array(generic Positive range <>) of T) is
>
> Interesting idea.

Can't you do this with a type conversion to an appropriate constrained array
subtype? (Such conversions slide.) I suppose it could be a pain to declare
such a subtype in front of every call, but it is a trick I've used a some
cases (usually in wrappers) to force sliding on arguments.

I suppose a more convinient way to force that would be helpful.

Randy.

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wccpqcxrzj2.fsf@shell01.TheWorld.com...
....
> Actually, I just realized there's a workaround for the slice problem.

Yes, as I just posted. I guess I should have read further before answering.

> The following does not raise any exception.
>
> procedure Array_Test is
>
> type Integer_Array is array (Positive range <>) of Integer
> with Dynamic_Predicate => Integer_Array'First = 1;
>
> procedure Foo (Param : in out Integer_Array) is
> begin
> null;
> end Foo;
>
> A : Integer_Array (1 .. 10) := (others => 0);
>
> subtype Slide is Integer_Array(1..6);
> begin
> Foo (Slide(A (3 .. 8)));
> end Array_Test;
>
> But that's kind of tricky; I wouldn't do that without copious
> comments. And some constants or something to avoid violating
> the DRY principle.

Maybe it's tricky, buit I've used it a lot, especially inside of things like
Ada.Strings.Fixed (and in my spam filter, which tends to do direct string
manipulations because it's usually easier to do that than to figure out what
Ada.Strings.Fixed function does 80% of the job [none of them ever seem to do
the whole job] and then figure out how to do the rest afterwards). But
typically, "Slide" uses bounds derived from whatever you're going to pass
(usually, "3" and "8" above are local variables anyway):

declare
L : Natural := 3;
R : Natural := 8; -- These are usually calculated from the other code
nearby.

subtype Slide is Integer_Array(1..R-L+1);
begin
Foo (Slide(A (L .. R)));
end;

Feel free to turn this into a "gem" if you're so inclined. :-)

Randy.

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wcclinkxvth.fsf@shell01.TheWorld.com...
> Ludovic Brenta <ludovic@ludovic-brenta.org> writes:
>
>> Robert A Duff writes on comp.lang.ada:
>>> Foo (Slide(A (3 .. 8)));
>>
>> Doesn't that involve copy-in and copy-out between the slice and a
>> temporary object of type Slide? Grossly inefficient, methinks.
>
> No, I don't see any need for the compiler to make a copy here.
> It just needs to pass the 1..6 bounds, plus a pointer to
> the array elements.
>
> I'm too lazy to check the machine code to see whether GNAT
> makes a copy, but I don't see why it would. Nor any other
> Ada compiler.

Surely Janus/Ada does not. It just makes a new array descriptor and passes
that -- exactly the same as it would do for the original slice. The only
interesting question is whether Janus/Ada would be smart enough to get rid
of the (unused) original slice's array descriptor. I didn't check, but I'm
sure there wouldn't be one in this case (static bounds). I have no idea what
would happen if the bounds were dynamic (as in my better example).

Randy.

On Wed, 7 Mar 2012, Randy Brukardt wrote:

> "Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
> news:wccy5rls0hl.fsf@shell01.TheWorld.com...
> > stefan-lucks@see-the.signature writes:
> >> procedure Sort(Items: in out array(generic Positive range <>) of T) is
> >
> > Interesting idea.
>
> Can't you do this with a type conversion to an appropriate constrained array
> subtype? (Such conversions slide.) I suppose it could be a pain to declare
> such a subtype in front of every call, but it is a trick I've used a some
> cases (usually in wrappers) to force sliding on arguments.

Can you explain a bit more?

> I suppose a more convinient way to force that would be helpful.

Beyond the inconvenience, there are two further issues:

1. Testing

When you declare

procedure Sort(Items: in out array(Positive range <>) of T)

in a package specification, and you try to write a proper black-box test,
you need *more* test cases then when you do the same with another popular
language. One of the additional test cases could look like

declare
X: array (Positive range Positive'last-2 .. Positive'Last) := ...;
Y: array (Positive range Positive'last-2 .. Positive'Last) := ...;
begin
Sort(X);
Assert(X=Y);
end;

Some time ago, I have actually been bitten by forgetting such a test case.

So the sad reality is that there is a property where Ada makes testing
harder than, say, C or C++.


2. Generality

Given the (Ada 2020?) specification

procedure Sort(Items: in out array(generic Positive range <>) of T);

Sort(X) should be callable if the index type of X is any discrete type,
except when the index type is too large (i.e., X has more than
Positive'Last elements).


--
---- Stefan.Lucks (at) uni-weimar.de, University of Weimar, Germany ----
<http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
------ I love the taste of Cryptanalysis in the morning! ------

<stefan-lucks@see-the.signature> wrote in message
news:Pine.LNX.4.64.1203081150460.6571@medsec1.medi en.uni-weimar.de...
> On Wed, 7 Mar 2012, Randy Brukardt wrote:
>
>> "Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
>> news:wccy5rls0hl.fsf@shell01.TheWorld.com...
>> > stefan-lucks@see-the.signature writes:
>> >> procedure Sort(Items: in out array(generic Positive range <>) of T)
>> >> is
>> >
>> > Interesting idea.
>>
>> Can't you do this with a type conversion to an appropriate constrained
>> array
>> subtype? (Such conversions slide.) I suppose it could be a pain to
>> declare
>> such a subtype in front of every call, but it is a trick I've used a some
>> cases (usually in wrappers) to force sliding on arguments.
>
> Can you explain a bit more?

Bob and I both gave examples of it in other messages.

>> I suppose a more convinient way to force that would be helpful.
>
> Beyond the inconvenience, there are two further issues:
>
> 1. Testing
>
> When you declare
>
> procedure Sort(Items: in out array(Positive range <>) of T)

Let's hope you never do that, because anonymous types are the bane of Ada.
And you surely can't do it today!

> in a package specification, and you try to write a proper black-box test,
> you need *more* test cases then when you do the same with another popular
> language.

Right. Bob's suggestion for some semi-constrained array subtype would fix
that. But note that it was killed in Ada 95 in part because the
implementation needed was essentially a record type with some sort of magic
indexing. Which was a mess.

Not sure if those issues can really go away, and I doubt there is much
interest in new first-class kinds of constraints.

....
> 2. Generality
>
> Given the (Ada 2020?) specification
>
> procedure Sort(Items: in out array(generic Positive range <>) of T);

Again, anonymous types are a disaster in Ada, and there is no way that we
should have more of them. I would strongly hope that this never appears even
in Ada 2525. ;-)

> Sort(X) should be callable if the index type of X is any discrete type,
> except when the index type is too large (i.e., X has more than
> Positive'Last elements).

If you want that, you need to declare that. Positive is a numeric type, and
thus has "+" and "-" available; it is never going to be allowed to match
"any discrete type" which includes enumeration types.

It's plenty easy to write a generic like this (see the predefined ones for
examples), so I fail to see what possible need you are addressing here.

Randy.

On Thu, 8 Mar 2012, Randy Brukardt wrote:
[...]
> <stefan-lucks@see-the.signature> wrote:

> > 1. Testing
> >
> > When you declare
> >
> > procedure Sort(Items: in out array(Positive range <>) of T)
>
> Let's hope you never do that, because anonymous types are the bane of Ada.
> And you surely can't do it today!

OK, the real thing would look about like that:

generic
type Element_Type is (<>);
type Index_Type is (Positive range <>);
type Collection_Type is array(Index_Type range <>) of Element_Type;
with function "<"(Left, Right : Element_Type) return Boolean is <>;

function Sort(Items : Collection_Type) return Collection_Type;

> > in a package specification, and you try to write a proper black-box test,
> > you need *more* test cases then when you do the same with another popular
> > language.
>
> Right. Bob's suggestion for some semi-constrained array subtype would fix
> that. But note that it was killed in Ada 95 in part because the
> implementation needed was essentially a record type with some sort of magic
> indexing. Which was a mess.

Would it ease the implementation if you constrain the start index to some
fixed value, such as Index_Type'First?

[...]

> > procedure Sort(Items: in out array(generic Positive range <>) of T);

> Again, anonymous types are a disaster in Ada, and there is no way that we
> should have more of them. I would strongly hope that this never appears even
> in Ada 2525. ;-)

Sorry for using anonymous arrays. I hardly ever do this in real
code. Please change the above code to

generic
type Element_Type is (<>);
type Collection_Type is array(generic Positive range <>) of Element_Type;
with function "<"(Left, Right : Element_Type) return Boolean is <>;
function Sort(Items : Collection_Type) return Collection_Type;

The issue is the same:

> > Sort(X) should be callable if the index type of X is any discrete type,
> > except when the index type is too large (i.e., X has more than
> > Positive'Last elements).
>
> If you want that, you need to declare that. Positive is a numeric type, and
> thus has "+" and "-" available; it is never going to be allowed to match
> "any discrete type" which includes enumeration types.
>
> It's plenty easy to write a generic like this (see the predefined ones for
> examples), so I fail to see what possible need you are addressing here.

It is a readability issue. I frequently use arrays with different index
types, that I need to sort, or to search for the same item being stored
more than once ... Having to instantiate, say, the same Sort procedure
several times makes the program less readable.

But I agree with you that that is a minor issue, and that Bob's suggestion
seems to solve the testing thing quite well.



--
---- Stefan.Lucks (at) uni-weimar.de, University of Weimar, Germany ----
<http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
------ I love the taste of Cryptanalysis in the morning! ------

<stefan-lucks@see-the.signature> wrote in message
news:Pine.LNX.4.64.1203090923440.19986@medsec1.med ien.uni-weimar.de...
> On Thu, 8 Mar 2012, Randy Brukardt wrote:
....
> Sorry for using anonymous arrays. I hardly ever do this in real
> code. Please change the above code to
>
> generic
> type Element_Type is (<>);
> type Collection_Type is array(generic Positive range <>) of
> Element_Type;
> with function "<"(Left, Right : Element_Type) return Boolean is <>;
> function Sort(Items : Collection_Type) return Collection_Type;
>
> The issue is the same:
>
>> > Sort(X) should be callable if the index type of X is any discrete type,
>> > except when the index type is too large (i.e., X has more than
>> > Positive'Last elements).

Which as I said doesn't make sense: Positive is numeric; if you want any
discrete type for the index you have to say so:

generic
type Element_Type is (<>); -- Really ought to be "is private".
type Index_Type is (<>);
type Collection_Type is array(Index_Type range <>) of Element_Type;
with function "<"(Left, Right : Element_Type) return Boolean is <>;
function Sort(Items : Collection_Type) return Collection_Type;

This works now (and has since Ada 83!), so I fail to see exactly what your
proposal gains (other than a bit less typing, and Ada have never been about
saving typing).

Randy.

On 03/09/2012 03:48 AM, stefan-lucks@see-the.signature wrote:
> On Thu, 8 Mar 2012, Randy Brukardt wrote:
> [...]
>> <stefan-lucks@see-the.signature> wrote:
>
>>> 1. Testing
>>>
>>> When you declare
>>>
>>> procedure Sort(Items: in out array(Positive range<>) of T)
>>
>> Let's hope you never do that, because anonymous types are the bane of Ada.
>> And you surely can't do it today!
>
> OK, the real thing would look about like that:
>
> generic
> type Element_Type is (<>);
> type Index_Type is (Positive range<>);
> type Collection_Type is array(Index_Type range<>) of Element_Type;
> with function "<"(Left, Right : Element_Type) return Boolean is<>;
>
> function Sort(Items : Collection_Type) return Collection_Type;
>
>>> in a package specification, and you try to write a proper black-box test,
>>> you need *more* test cases then when you do the same with another popular
>>> language.
>>
>> Right. Bob's suggestion for some semi-constrained array subtype would fix
>> that. But note that it was killed in Ada 95 in part because the
>> implementation needed was essentially a record type with some sort of magic
>> indexing. Which was a mess.
>
> Would it ease the implementation if you constrain the start index to some
> fixed value, such as Index_Type'First?

If that's what you want, why can't you (in this case) define that in
your generic parameters, rather than an index range (which already has a
defined type)?

--
---
BrianG
000
@[Google's email domain]
..com

On Wed, 14 Mar 2012, BrianG wrote:

> On 03/09/2012 03:48 AM, stefan-lucks@see-the.signature wrote:
> > On Thu, 8 Mar 2012, Randy Brukardt wrote:
> > [...]
> > > <stefan-lucks@see-the.signature> wrote:
> >
> > > > 1. Testing
> > > >
> > > > When you declare
> > > >
> > > > procedure Sort(Items: in out array(Positive range<>) of T)
> > >
> > > Let's hope you never do that, because anonymous types are the bane of Ada.
> > > And you surely can't do it today!
> >
> > OK, the real thing would look about like that:
> >
> > generic
> > type Element_Type is (<>);
> > type Index_Type is (Positive range<>);
> > type Collection_Type is array(Index_Type range<>) of Element_Type;
> > with function "<"(Left, Right : Element_Type) return Boolean is<>;
> >
> > function Sort(Items : Collection_Type) return Collection_Type;
> >
> > > > in a package specification, and you try to write a proper black-box
> > > > test,
> > > > you need *more* test cases then when you do the same with another
> > > > popular
> > > > language.
> > >
> > > Right. Bob's suggestion for some semi-constrained array subtype would fix
> > > that. But note that it was killed in Ada 95 in part because the
> > > implementation needed was essentially a record type with some sort of
> > > magic
> > > indexing. Which was a mess.
> >
> > Would it ease the implementation if you constrain the start index to some
> > fixed value, such as Index_Type'First?
>
> If that's what you want, why can't you (in this case) define that in your
> generic parameters, rather than an index range (which already has a defined
> type)?

Good catch! I actually meant Positive'First.

--
---- Stefan.Lucks (at) uni-weimar.de, University of Weimar, Germany ----
<http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
------ I love the taste of Cryptanalysis in the morning! ------