Arrays in both C and Ada are a compound type with the
elements arranged sequentially in memory. All the elements in an array are of a
single type. For instance an array may contain integer elements or it may
contain floating point elements, or it may contain strings of characters, or it
may even contain other arrays.
One might therefore assume that arrays in C and Ada are
fundamentally the same. This article explores that assumption and finds some
clear differences between C arrays and Ada arrays.
|
Array Characteristic
|
C language
|
Ada Language
|
|
Array types
|
C only allows definition of the type of an array element. It does not
allow declaration of an array type.
|
Every Ada array is a member of a type, even if it is an anonymous
type.
|
|
Index range
|
Valid C array indices always start at 0. The C language provides no
implicit checking for referencing invalid array indices.
|
Ada array indices may begin at any programmer-chosen scalar value and
end at any programmer-chosen scalar value. Ada compilers validate static
array index references and by default the Ada runtime checks array index
values during program execution.
|
|
Array declaration
|
C arrays are declared by specifying the element type, the array name,
and the number of elements in the array.
|
Ada arrays are declared by specifying the array name, the array index
range and the array element type.
|
|
Array size
|
C array sizes can only be calculated using the sizeof operator within
the scope in which the array is first declared. Passing an array to a
function results in only the address of the first array element being passed
to the function. The programmer must pass another parameter to the function
indicating the size of the array. The compiler cannot ensure the size
parameter is correct.
|
Ada array attributes are available wherever the array is visible. Ada
array attributes include:
- ‘Size – The number of bits the array occupies
in memory.
- ‘Length – The number of elements in the array.
- ‘First – The first valid index value for the
array.
- ‘Last – The last valid index value for the
array
- ‘Range – The range specified by ‘First ..
‘Last
|
|
Array slicing
|
C does not provide a facility for array slicing.
|
Ada provides the ability to define a slice of an array.
|
|
Array assignment
|
C does not allow the programmer to copy one array to another using a
single assignment statement.
|
Ada allow arrays to be copied using a single assignment statement.
|
The impact of these differences is demonstrated by reviewing
the Merge-Sort algorithm implemented in both languages.
The first example is a C implementation of the Merge-Sort
algorithm.
1 /*
2 * C Program to
Perform Merge Sort using Recursion and Functions
3 */
4
5 #include
<stdio.h>
6 #include
<stdlib.h>
7
8 // merge
function
9 void Merge(int arr[], int left, int mid, int right)
10 {
11 int i, j, k;
12 int size1 = mid - left + 1;
13 int size2 = right - mid;
14
15 // created temporary array
16 int Left[size1], Right[size2];
17
18 // copying the data from arr to
temporary array
19 for (i = 0; i < size1; i++)
20 Left[i] = arr[left + i];
21
22 for (j = 0; j < size2; j++)
23 Right[j] = arr[mid + 1 + j];
24
25 // merging of the array
26 i = 0; // intital index of first subarray
27 j = 0; // inital index of second subarray
28 k = left; // initial index of parent array
29 while (i < size1 && j < size2)
30 {
31 if (Left[i] <= Right[j])
32 {
33 arr[k] = Left[i];
34 i++;
35 }
36 else
37 {
38 arr[k] = Right[j];
39 j++;
40 }
41 k++;
42 }
43
44 // copying the elements from Left[],
if any
45 while (i < size1)
46 {
47 arr[k] = Left[i];
48 i++;
49 k++;
50 }
51
52 // copying the elements from Right[],
if any
53 while (j < size2)
54 {
55 arr[k] = Right[j];
56 j++;
57 k++;
58 }
59 }
60
61 //merge sort
function
62 void Merge_Sort(int arr[], int left, int right)
63 {
64 if (left < right)
65 {
66
67 int mid = left + (right - left) / 2;
68
69 // recursive calling of merge_sort
70 Merge_Sort(arr, left, mid);
71 Merge_Sort(arr, mid + 1, right);
72
73 Merge(arr, left, mid, right);
74 }
75 }
76
77 // driver code
78 int main()
79 {
80 int size;
81 printf("Enter the size: ");
82 scanf("%d", &size);
83
84 int arr[size];
85 printf("Enter the elements of
array: ");
86 for (int i = 0; i < size; i++)
87 {
88 scanf("%d", &arr[i]);
89 }
90
91 Merge_Sort(arr, 0, size - 1);
92
93 printf("The sorted array is:
");
94 for (int i = 0; i < size; i++)
95 {
96 printf("%d ", arr[i]);
97 }
98 printf("\n");
99 return 0;
100 }
Both the Merge_Sort function and the Merge function take
several parameters.
62 void Merge_Sort(int arr[], int left, int right)
9 void Merge(int arr[], int left, int mid, int right)
The first parameter in each function specifies an array of
int elements. The remaining parameters specify various int values. These extra
parameters are needed in C because all array indices must begin at 0, the size
of the array parameter is not passed with the array, and C does not provide
array slicing.
The C programmer must provide all this information as
additional function parameters.
The C language does not provide assignment of one array to
another. The programmer must explicitly create a loop and assign each element
one at a time:
18 // copying the data from arr to
temporary array
19 for (i = 0; i < size1; i++)
20 Left[i] = arr[left + i];
21
22 for (j = 0; j < size2; j++)
23 Right[j] = arr[mid + 1 + j];
Each of these examples is a demonstration of the low-level
terseness of C. Each of these examples shows how much more writing must be done
in C to achieve what Ada does very simply.
The Ada version of the Merge-Sort algorithm is implemented
in a generic Ada package so that the sort procedure declared within the package
specification can be used to sort any mutable data type.
The Ada solution is done using three filles.
1 generic
2 type element_type is private;
3 type array_type is array (Integer range <>) of element_type;
4 with function "<"
(left, right : element_type) return Boolean is <>;
5 package generic_merge_sort
is
6 procedure sort (Item : in out array_type);
7 end generic_merge_sort;
The generic package specification requires three parameters
when an instance of the package is declared. The first parameter is the name of
the element type for the array which will be sorted. The second parameter is
the name of the array type to be sorted. This parameter is restricted to an
unconstrained array type indexed by Integer values. Each element of the array
type must be the type passed to the first parameter. The third parameter is a
possible overloading of the “<” function. This is an optional parameter. If
the element_type already has a “<” function defined that function will be
used by default.
The procedure sort is defined to take one parameter with
mode “in out”, meaning the parameter value(s) will be used and possibly modified
within the procedure. All modifications will be visible to the calling scope.
The package body contains the logic used to implement the
merge-sort algorithm.
1 package body generic_merge_sort
is
2 procedure merge (Item : in out array_type) is
3 mid
: Integer := Item'First + (Item'Last - Item'First) / 2;
4 Left : array_type := Item (Item'First .. mid);
5 Right : array_type := Item (mid + 1 .. Item'Last);
6 I : Integer := Left'First;
7 J : Integer := Right'First;
8 K : Integer
:= Item'First;
9 begin
10 while I <= Left'Last and then J <= Right'Last loop
11 if Left (I) < Right (J) then
12 Item (K) := Left (I);
13 I := I + 1;
14 else
15 Item (K) := Right (J);
16 J
:= J + 1;
17 end if;
18 K := K + 1;
19 end loop;
20 -- copying unused items from Left
21 while I <= Left'Last loop
22 Item (K) := Left (I);
23 I
:= I + 1;
24 K := K + 1;
25 end loop;
26 -- copying unused items from right
27 while J <= Right'Last loop
28 Item (K) := Right (J);
29 J := J + 1;
30 K
:= K + 1;
31 end loop;
32 end merge;
33
34 ----------
35 -- sort --
36 ----------
37
38 procedure sort (Item : in out array_type) is
39 mid : Integer;
40 begin
41 if Item'Length > 1 then
42 mid := Item'First + (Item'Last - Item'First)/2;
43 sort(Item(Item'First .. Mid));
44 sort(Item(Mid + 1 .. Item'Last));
45 merge(Item);
46 end if;
47 end sort;
48
49 end generic_merge_sort;
This example make extensive use of Ada array attributes. The
value of mid in both the merge procedure and the sort procedure is calculated
using the ‘First and ‘Last array attributes, simplifying the procedure
signature for both sort and merge. Both procedures only need an instance or
slice of an array passed to them.
In the merge procedure the Left and Right instances of
array_type are created and initialized with slices of the array Item passed to
the procedure. Ada’s ability to assign one array or slice to another array or
slice of the same type eliminates the need to explicitly calculate the sizes
needed for the Left and Right arrays. It also eliminates the need to explicitly
copy the values iteratively.
4 Left : array_type := Item (Item'First .. mid);
5 Right : array_type := Item (mid + 1 .. Item'Last);
For reference, here is the corresponding C code:
12 int size1 = mid - left + 1;
13 int size2 = right - mid;
14
15 // created temporary array
16 int Left[size1], Right[size2];
17
18 // copying the data from arr to
temporary array
19 for (i = 0; i < size1; i++)
20 Left[i] = arr[left + i];
21
22 for (j = 0; j < size2; j++)
23 Right[j] = arr[mid + 1 + j];
A comparison of the C merge_sort function and the Ada sort
procedure provides more insight to the differences between C arrays and Ada
arrays.
C merge_sort:
62 void Merge_Sort(int arr[], int left, int right)
63 {
64 if (left < right)
65 {
66
67 int mid = left + (right - left) / 2;
68
69 // recursive calling of merge_sort
70 Merge_Sort(arr, left, mid);
71 Merge_Sort(arr, mid + 1, right);
72
73 Merge(arr, left, mid, right);
74 }
75 }
Ada sort:
38 procedure sort (Item : in out array_type) is
39 mid : Integer;
40 begin
41 if Item'Length > 1 then
42 mid := Item'First + (Item'Last - Item'First)/2;
43 sort(Item(Item'First .. Mid));
44 sort(Item(Mid + 1 .. Item'Last));
45 merge(Item);
46 end if;
47 end sort;
The condition in the “if” statement, while achieving the
same result, is quite different. The C function relies upon the correctness of
the left and right parameters passed as the second and third arguments to the
function. The Ada procedure only relies upon the ‘Length attribute of the
array. The Ada syntax is much less error-prone and a more direct statement to a
human reader about the intention of the conditional statement. In order to get
a complete understanding of the purposes of the C left and right parameters one
must read the context of the main procedure, while the meaning of the Ada
conditional is completely clear in the local context. Since the sort parameter
type is an unconstrained array type every slice of the array is also an
instance of the unconstrained array type.
The C Merge_Sort function recursively calls itself passing
the beginning of the arr parameter each time but with different values for left
and right.
The Ada sort function recursively calls itself passing
slices of the parameter Item to each recursive call. In this manner each
recursion of Sort only sees the slice passed to it and all the other elements
of the array initially passed to the sort procedure from main are not available
to the recursive call.
The C Merge procedure passes the full array, but also passes
three parameters containing the left, mid and right index positions in the
array. The Ada merge procedure only array slice passed to it by the sort
procedure.
The main function in C is:
78 int main()
79 {
80 int size;
81 printf("Enter the size: ");
82 scanf("%d", &size);
83
84 int arr[size];
85 printf("Enter the elements of
array: ");
86 for (int i = 0; i < size; i++)
87 {
88 scanf("%d", &arr[i]);
89 }
90
91 Merge_Sort(arr, 0, size - 1);
92
93 printf("The sorted array is:
");
94 for (int i = 0; i < size; i++)
95 {
96 printf("%d ", arr[i]);
97 }
98 printf("\n");
99 return 0;
100 }
The main procedure in Ada is:
1 with Ada.Text_IO; use Ada.Text_IO;
2 with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
3 with generic_merge_sort;
4
5 procedure Main is
6 type int_arr is array (Integer range <>) of Integer;
7 package int_sort is new generic_merge_sort
8 (element_type => Integer, array_type => int_arr);
9 use int_sort;
10 Num_Elements : Positive;
11 begin
12 Put ("Enter the size of the array:
");
13 Get (Num_Elements);
14 declare
15 the_array : int_arr (1 .. Num_Elements);
16 begin
17 Put_Line ("Enter the array
values:");
18 for value of the_array loop
19 Get (value);
20 end loop;
21 sort (the_array);
22 Put_Line ("The sorted array
is:");
23 for value of the_array loop
24 Put (value'Image & " ");
25 end loop;
26 New_Line;
27 end;
28 end Main;
Lines 6 through 9 of the Ada program are needed to create an
instance of the generic_merge_sort package.
6 type int_arr is array (Integer range <>) of Integer;
7 package int_sort is new generic_merge_sort
8 (element_type => Integer, array_type => int_arr);
9 use int_sort;
An inner block is declared so that an array of the size
entered by the user can be created. The rest of the program is performed in
this inner block.
14 declare
15 the_array : int_arr (1 .. Num_Elements);
16 begin
17 Put_Line ("Enter the array
values:");
18 for value of the_array loop
19 Get (value);
20 end loop;
21 sort (the_array);
22 Put_Line ("The sorted array is:");
23 for value of the_array loop
24 Put (value'Image & " ");
25 end loop;
26 New_Line;
27 end;
The for loop used to read all the values into the array
starting at line 18 is an Ada iterator loop. The loop parameter “value” becomes
an alias for each array element starting at the first element and ending at the
last element. Thus, each value entered by the user is placed directly into the
array without explicit index notation.
The array is sorted.
21 sort (the_array);
Finally, the sorted array is output to standard output and
the program ends.
Conclusion:
The C and Ada examples implement the same merge-sort
algorithm to sort an array of integer values. C arrays are more primitive
abstractions than are Ada arrays. The more primitive abstractions require more
lines of C source code than does the Ada implementation. The C implementation
also requires a more complex parameter list for both its Merge function and its
Merge_Sort function. The Ada implementation concentrates on merely sorting an
array without additional parameters.
The built-in characteristics of Ada arrays really do
simplify the manipulation of arrays, even when those arrays are passed to an
Ada function or procedure.
I learned long ago that complexity is the enemy of
correctness. In these examples we see that lower complexity also provides fewer
opportunities for programmer error. We also see that a programming language
with a low level syntax is not necessarily simpler than a programming language
with a higher level syntax. Terse is not always simpler. Terse does not always
result in less typing for the programmer.
Login
