Alternative to exceptions when attempting to pop an empty stack

 

A recent question on StackOverflow asked about whether or not a mutex is locked twice by the same thread without unlocking the mutex. See https://stackoverflow.com/questions/76890110/c-the-thread-repeatedly-locks-the-same-mutex-multiple-times?noredirect=1#comment135552146_76890110

The C++ source code presented in the question is:

1 #include <exception>
2 #include <memory>
3 #include <mutex>
4 #include <stack>
5
6 struct empty_stack : std::exception
7 {
8    const char* what() const throw();
9 };
10
11 template<typename T>
12 class threadsafe_stack
13 {
14 private:
15    std::stack<T> data;
16    mutable std::mutex m;
17 public:
18    threadsafe_stack(){}
19    threadsafe_stack(const threadsafe_stack& other) {
20       std::lock_guard<std::mutex> lock(other.m);
21       data = other.data;
22 }
23    threadsafe_stack& operator=(const threadsafe_stack& other) = delete;
24    void push(T new_value)
25    {
26       std::lock_guard<std::mutex> lk(m);
27       data.push(std::move(new_value));
28    }
29    std::shared_ptr<T> pop()
30    {
31       std::lock_guard<std::mutex> lock(m);
32       if (data.empty()) throw empty_stack();
33       std::shared_ptr<T> const res(std::make_shared<T>(data.top()));
34       data.pop();
35       return res;
36    }
37    void pop(T& value)
38    {
39       std::lock_guard<std::mutex> lock(m);
40       if (data.empty()) throw empty_stack();
41       *value = data.top();
42       data.pop();
43    }
44    bool empty() const
45    {
46       std::lock_guard<std::mutex> lock(m);
47       return data.empty();
48    }
49 };
 

One issue with this program design, which has nothing to do with the question asked, is throwing an exception when pop is called on an empty stack. An empty stack is not an exceptional situation. In fact the stack starts off as an empty stack when it is created.

Exception handling should not be used to deal with non-exceptional program state.

The following Ada stack implementation demonstrates how an empty stack should be handled in a thread-safe manner.

The Ada program defines a generic thread package with the same operations shown in the C++ example above.

The Ada program creates a generic stack package and a main procedure. Ada packages are separated into two parts, the package specification and the package body or implementation. The package specification defines the package API.

1 with Ada.Containers.Doubly_Linked_Lists;
2 generic
3    type element_type is private;
4 package generic_stack is
5    package List_Pack is new
6       Ada.Containers.Doubly_Linked_Lists (element_type);
7 use List_Pack;
8
9 protected type Stack is
10    procedure Push (Item : element_type);
11    entry Pop (Item : out element_type);
12    function Is_Empty return Boolean;
13 private
14    Buffer : List := Empty_List;
15 end Stack;
16
17 end generic_stack;
 

The package creates an Ada protected type. A protected type or protected object is a passive unit of concurrency which is implicitly protected from race conditions. There are three kinds of methods available to be defined within a protected type. Protected procedures implicitly acquire an unconditional exclusive read-write lock on the data in the protected type. Protected entries implicitly acquire a conditional exclusive read-write lock on the data in the protected type. A task suspends while the entry boundary condition evaluates to false. The suspended tasks are placed in an entry queue so that they can be activated when the boundary condition evaluates to true. The third kind of method available for a protected object is a function. Protected functions are limited to read-only access to the data in the protected type. Protected functions acquire a shared read lock on the data in the protected object.

The implementation of the package is in a separate file containing the package body.

1  package body generic_stack is
2
3     -----------
4     -- Stack --
5     -----------
6
7     protected body Stack is
8
9        ----------
10       -- Push --
11       ----------
12
13       procedure Push (Item : element_type) is
14       begin
15          Buffer.Append (Item);
16       end Push;
17
18       ---------
19       -- Pop --
20       ---------
21
22       entry Pop (Item : out element_type) when
23                  not Buffer.Is_Empty is
24       begin
25          Item := Buffer.Last_Element;
26          Buffer.Delete_Last;
27       end Pop;
28
29       --------------
30       -- Is_Empty --
31       --------------
32
33       function Is_Empty return Boolean is
34       begin
35          return Buffer.Is_Empty;
36       end Is_Empty;
37
38    end Stack;
39
40 end generic_stack;

 

The push procedure implicitly locks the Buffer when it begins executing and unlocks the Buffer as the procedure completes.

The pop entry only executes when Buffer.Is_Empty evaluates to false. When that condition is met any immediate call, or any task waiting in the entry queue is allowed to execute the entry. The default queuing policy of the entry queue is FIFO and all tasks suspended in the entry queue will be executed before any new call can be executed. The shared read-write lock is applied when execution of the entry starts and is release upon completion of the entry.

The Is_Empty function can only execute when no read-write lock is applied to the Buffer data element. Upon starting execution the function applies a shared read lock, allowing any number of tasks to read simultaneously and preventing any procedure or function to execute until the function completes and releases its shared read lock.

The main procedure, which is the program entry point for this example, follows.

1  with Ada.Text_IO; use Ada.Text_IO;
2  with generic_stack;
3
4  procedure Main is
5     package int_stack is new generic_stack (Integer);
6     use int_stack;
7
8     The_Stack : Stack;
9
10    task producer is
11       entry Start;
12    end producer;
13
14    task body producer is
15    begin
16       accept Start;
17       Put_Line ("Producer started.");
18       for I in 1 .. 20 loop
19          The_Stack.Push (I);
20          Put_Line ("Pushed" & I'Image);
21          delay 0.001;
22       end loop;
23    end producer;
24
25    task consumer is
26       entry Start;
27    end consumer;
28
29    task body consumer is
30       Num : Integer;
31    begin
32       accept Start;
33       Put_Line ("Consumer started.");
34       for I in 1 .. 20 loop
35          The_Stack.Pop (Num);
36          Put_Line ("Popped" & Num'Image);
37       end loop;
38    end consumer;
39
40 begin
41    consumer.Start;
42    delay 0.01;
43    producer.Start;
44 end Main;
 

Line 5 creates an instance of the generic_stack package passing the type Integer as the generic parameter. This results in a stack of integer values.

Line 8 declares an instance of the Stack type named The_Stack.

Line 10 declares the interface for the producer task. This task has one entry named Start.

Line 14 declares the implementation of the producer task.

Line 16 accepts the Start entry. The producer task will suspend until another task calls its Start entry. Task entries implement a Rendezvous logic allowing synchronous coordination of tasks. After accepting Start the producer executes a for loop 20 times, each time pushing the current value of the loop control variable onto the stack, displaying a message to standard output and then delaying (sleeping) for 0.001 seconds.

The consumer task declaration begins at line 25. The consumer also has a Start entry.

The consumer task accepts its start entry at line 32 and then pops 20 values off of the stack. The consumer task has no delay statement. The consumer tasks will then complete its iteration before the producer task pushes another value onto the stack. Each call to the pop entry will therefore encounter an empty stack until the producer pushes another value onto the stack.

Both the producer task and the consumer tasks begin execution immediately, but both tasks suspend until their Start entry is called.

Line 40 begins execution of the main procedure which is also the top-level task for the program. Line 41 calls consumer.Start. Line 42 causes the main procedure to delay for 0.01 seconds before line 43 calls producer.start.

This delay in starting the tasks ensures that the consumer must wait at least 0.01 seconds before the first data will be pushed onto the stack. In other words, the stack will be empty for at least 0.01 seconds.

The output of this program is:

 

Consumer started.
Producer started.
Pushed 1
Popped 1
Pushed 2
Popped 2
Pushed 3
Popped 3
Pushed 4
Popped 4
Pushed 5
Popped 5
Pushed 6
Popped 6
Pushed 7
Popped 7
Pushed 8
Popped 8
Pushed 9
Popped 9
Pushed 10
Popped 10
Pushed 11
Popped 11
Pushed 12
Popped 12
Pushed 13
Popped 13
Pushed 14
Popped 14
Pushed 15
Popped 15
Pushed 16
Popped 16
Pushed 17
Popped 17
Pushed 18
Popped 18
Pushed 19
Popped 19
Pushed 20
Popped 20
 

Clearly the program did not encounter any exceptions, yet the consumer could only pop values after they were pushed onto the stack.

Variant Records used as a return type from search functions

 When searching for a value in an array a programmer is faced with two possibilities.

1.       The value searched for is found and the index of the value in the array is returned.

2.       The value is not found and no array index is returned.

It is common practice to return a scalar value from functions using the C programming language. This tradition goes back to the earliest days of the C language when unspecified function return types were given the int type by default by the compiler.

The C language does not have a concept of exceptions or exception handlers. Instead, the value returned by a function either indicates success or failure.

It is common for positive return values to indicate success and negative or zero values to indicate failure. This pattern was established by the Unix operating system. C was invented to write the Unix operating system.

A search function is often designed to return the index of the array element containing the value corresponding to the target value for which one is searching. This programming pattern is also commonly found in the C++ language.

The following function prototype is written using C++;

int binary_search(string names[], int len, const string target);

The binary_search function returns an int. The first parameter is an array of string elements. The second parameter is the number of elements in the array of strings. The third element is the string value to search for in the array of strings.

The binary_search function returns the index value of the array element equal to the target string or it returns -1 if no array element corresponds to the target string. This behavior creates an abstraction with a strong vulnerability of confusion. The return value serves two purposes. It identifies whether or not the target value was found in the array and it identifies the index value of the array element equaling the target value.

The complete binary_search function is defined as:

int binary_search(string names[], int len, const string target) {   int low = 0;   int high = len - 1;   int mid = 0;\   string item;   while (low <= high) {     mid = (low + high) / 2;     item = names[mid];     if (item == target) {       return mid;     }     if (strcmp(target.c_str(), item.c_str()) < 0) {       high = mid - 1;     } else       low = mid + 1;   }   return -1; }

 

Logically whether or not the value was found is separate from the index value of the found element. There should be no index value for a found element when no element is found. The function allows the programmer to make the mistake of trying to reference an array element before the beginning of the array. In C and C++ doing this is undefined behavior, and is always wrong.

Avoiding undefined behavior

The C and C++ languages provide no assistance in the effort to avoid undefined behaviors. The compilers are not required to check for undefined behavior because the programmer is burdened with the responsibility of avoiding undefined behavior.

The Ada programming language provides a useful data structure known as a variant record, which C and C++ programmers may think is similar to a union. C and C++ unions provide different views of a common memory area so that, for instance, a number might be viewed as an int or a float. Ada variant records are different.

Every Ada variant record has a publicly visible discriminant field, even if the type is opaque. That discriminant field controls the contents, not just the view, of the record. The following example is used as a return type for a search function.

type Result_T (found : Boolean) is record       case found is          when True =>             Index : Natural;          when False =>             null;       end case;    end record;

The discriminant field in this example is named “found”. Found is a Boolean value. Every instance of Result_T contains a “found” field. The case statement within the record definition declares a second field named Index, which is of type Natural when and only when found is True. When found is False the record type contains no additional field. It only contains the found field.

This data structure separates the responsibility of identifying whether or not the target value was found from identifying the index value of the element equaling the target value.

The complete Ada version of the binary_search function is

function binary_search     (Names : in str_arr; Target : Unbounded_String) return            Result_T is       low  : Natural := Names'First;       High : Natural := Names'Last;       Mid  : Natural;       Item : Unbounded_String;    begin       while low <= High loop          Mid  := (High - low) / 2 + low;          Item := Names (Mid);          if Item = Target then             return (found => True, Index => Mid);          end if;          if Target < Item then             High := Mid - 1;          else             low := Mid + 1;          end if;       end loop;       return (found => False);    end binary_search;

If the item corresponding to Target is found the return value contains both a found and an Index field.

return (found => True, Index => Mid);

If no item corresponding to Target is found the return value only contains the found field.

return (found => False);

Since no Index value exists when found equals False, no undefined behavior can occur. The Ada runtime raises the pre-defined exception CONSTRAINT_ERROR along with the message “discriminant check failed” if the programmer attempts to reference the Index field when found equals False.

The proper way to deal with a variant record such as this returned by a function is:

Result : Result_T := binary_search (Names,                                                      To_Unbounded_String ("ali2")); begin  if Result.found then       Put_Line ("The given index is " & Result.Index'Image);       Put_Line ("The found name is " & To_String (Names                                                      (Result.Index)));  else     Put_Line ("String not found!");  end if;

This is similar to the proper way to respond to the return value from the C or C++ function. The difference is that when the return value is not evaluated the C or C++ program will not raise an exception. Instead it will simply exhibit an undefined behavior.

Array Handling

 

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.