I am writing some numerical library functions wherein the unconstrained arrays (vectors) that functions receive must be zero-index based. Passing a non-zero-based vector would sadly give a run-time error. However, there is an obvious solution:
Say an input vector has the name “V”, one could simply re-write the functions to make adjustmust using V’First.
However, that comes with additional run-time costs due to the addition operation required on every vector element read/write.
If it were possible to create an unconstrained array type WHEREIN the index of the first element would be guaranteed to be zero, then any issues would be caught at compile time. (Since the function would only receive such a type.)
However, I do not think it this is possible, is it?
Also, I’d be happy to receive any thoughts and suggestions regarding this.
I should explain, a run-time error would be obtained because the algorithm is written using arithmetic operations on the indices that are only valid for zero-based index arrays.
So, giving the function a non-zero based array would likely result in an access error.
The code itself is not broken.
As mentioned, it would indeed be trivial to use A’First, etc. But would like to avoid the runtime arithmetic operations for all of these adjustment.
with Ada.Text_IO; use Ada.Text_IO;
procedure Test is
procedure F (S : String) is
subtype Slide is String (1..S'Length);
X : Slide renames S;
begin
Put_Line (Integer'Image (X'First) & " .." & Integer'Image (X'Last));
end F;
begin
F ((3..5 => 'X'));
end Test;
Premature optimization is the root of all evil
– Donald Knuth
Depending on the compiler and the machine differences might be marginal. E.g. on my machine this:
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Calendar; use Ada.Calendar;
procedure Test is
type A is array (Natural range <>) of Integer;
procedure Broken_Add (X : in out A; Y : A) is
begin
for I in X'Range loop
X (I) := X (I) + Y (I);
end loop;
end Broken_Add;
procedure Correct_Add (X : in out A; Y : A) is
J : Natural := Y'First;
begin
for I in X'Range loop
X (I) := X (I) + Y (J);
J := J + 1;
end loop;
end Correct_Add;
X : A (0..100_000) := (others => 1);
Y : A (0..100_000) := (others => 2);
Tries : constant := 10_000;
S : Time;
T1, T2 : Duration;
begin
S := Clock;
for I in 1..Tries loop
Broken_Add (X, Y);
end loop;
T1 := Clock - S;
S := Clock;
for I in 1..Tries loop
Correct_Add (X, Y);
end loop;
T2 := Clock - S;
Put_Line ("Broken :" & T1'Image);
Put_Line ("Correct:" & T2'Image);
end Test;
It becomes an off-topic but to remove loop overhead from test I usually measure:
for I in 1..N loop
<testee>
end loop;
and then
for I in 1..N loop
<testee>
<testee>
end loop;
Then I subtract the first from the second, convert to Long_Float and dive by N. That should allow to measure quite small code. Well, unless the compiler does not optimize it away…
Why?
This sounds a lot like you are confusing Index with Offset — this is a very common thing from the languages with 0-based indexing: they just pun off the confluence of these two very different things being the same numerically — and utterly breaks when you shift things:
Package Example_Array is
Type Index is ( Frog, Dog, Cat, Bird );
Type Population is Array (Index range <>) of Natural;
End Example_Array;
Given the above you can’t mix the offset and index because (2*Dog) is nonsense.
Also note that Ada uses unconstrained arrays in String, and to good effect: because you can return unconstrained arrays Function Get_User_Input return String; is perfectly fine. Moreover, the ability to slice an array fits into the discussion: consider Text : String := "David"; and Format : String := Text(2..4), the latter being "avi".
Don’t go this route; conflating index and offset will only lead you to trouble.
Use the 'Range, 'First, and 'Last attributes.
In fact, consider the whole Maybe from functional programming: a lot of newbies from functional programming instantly reach for variant records, even when unconstrained arrays show us how to do it simply:
Generic
Type Element is limited private; -- Any non-discriminated type.
Package Example is
-- A range of one value.
Subtype Index Boolean is True..True;
-- An unconstrained array on that one-element index.
Type Option is Array (Index range <>) of Element;
-- Make an Optional from a value.
Function "+"(Right : Element) return Option is
( Option'(True => Right) );
-- An example to make an empty Option.
Nothing : Constant Option:= ( True..False => <> );
End Example;
With the above you can operate on all Option arrays with a for-loop (For E of A loop or For X of A'Range loop) and write the processing therein. The nice feature of doing this is that this makes the program logic much more easy to simply apply to all vector sizes, rather than the possible-0/possible-1.
TL;DR — Zero-based indexing is a premature optimization and leads to less robust programming.
BTW, returning to the original problem, you can slide indices in Ada. Here is how you do it:
with Ada.Text_IO; use Ada.Text_IO;
procedure Test is
type A is array (Natural range <>) of Integer;
procedure F (X : A) is
subtype AZ is A (0..X'Length - 1);
XZ : AZ with Import => True, Address => X'Address;
begin
Put_Line (Integer'Image (XZ (0)));
end F;
begin
F ((7 => 7, 8 => 8, 9 => 9)); -- Outputs 7
end Test;
Note that X’Address when applied to an array means address of the first element.
I appreciate this input. The issue is exactly this “Offset” and “Index” issue, there is agreement on this. When dealing with equally spaced time series data, many existing algorithms are based on “position from the first sample” (precisely the OFFSET). So, it is indeed the offset that we need to use.
This is easily done using A’Range and A’First when accepting arrays with arbitrary indexing. But I had been concerned with potential costs of the arithmetic operations on doing so with every vector element access (hence the origin question).
Based on your input here, and Dmitry’s input I see that in terms of robustness of code (and only micro-speed-improvements) that I should probably drop my original strategy of “zero-based only” types.
I learn quite much from responses here, thanks again for helping my understanding.
This is quite an intriguing suggestion! I have not seen this “Import” and “Address” before. As this is new to me, I cannot foresee if there are run-time costs of this approach particularly if the input array of “F” is of type “in out”. (But as pointed out earlier - “premature optimization” - I probably should not worry so much about that.)
But anyhow, this will be fun to play with and learn more. Now, I have some experimenting to do. This is much appreciated help for my learning today.
There should not be any. It is purely a view change. One array is mapped onto another.
This is frequently used in C bindings. C has no arrays. So you have a combination of a pointer to the first element and the length. On the Ada side you declare an array of the length and place it in the memory where the pointer points to. Address specifies the address, Import instructs to drop any initialization and finalization that would apply otherwise. That is.
Similarity index sliding is done. Other important cases are decoding/encoding protocols, implementation of ring buffers, blackboards and other containers of unconstrained elements.
This explanation makes sense, it helps quite much my understanding. Funny that you should mention ring buffers because that is one of my next steps in a project.
I was wanting to use the old “bit mask on the counter of a ring buffer of size 2**n” to avoid any conditionals in the looping (I hope those words are clear enough). This “Import/Address” might be helpful to do this.
type Thing_Impl is array (Natural range <>) of Whatever;
type Thing (Last : Integer) is record
Value : Thing_Impl (0 .. Last);
end record;
Starting with Ada 12, you can use a type invariant or predicate
type Thing is array (Natural range <>) of Whatever with
Dynamic_Predicate => Thing'First = 0;
These are used similarly
X : Thing (Last => 23);
X.Value (0)
or
X : Thing (0 .. 23);
X (0)
There are pros and cons for both. The record approach has sliding, which the predicate approach lacks. The record approach requires appending .Value to everything, while the predicate approach uses normal array syntax.
