❌ About FreshRSS

Normal view

There are new articles available, click to refresh the page.
Before yesterdaySoftware Orthodoxy

Parallel Comparison of C++ and Ada Producer-Consumer Implementations

 

Producer Consumer Comparison 

The C++ source code for this example is taken from the blog post here by Andrew Wei. A detailed description of the C++ software is given in the blog post.

This solution is shown in parallel with a corresponding Ada solution.

Both C++ and Ada separate interface specifications from implementation. C++ uses the header file, in this case the file named Buffer.hpp, to provide the interface specification for the buffer used in this example. C++ is not very strict about what goes into a header file and what goes into a .cpp file. The Ada version creates an Ada package. The Ada package specification defines the task types named producer_Int and consumer_Int. The buffer shared by all instances of producer_int and consumer_int is defined within the Ada package body file.

Interface Specification Files

Ada C++
package pc_tasks is
   task type produce_Int (Id : Natural);
   task type consume_Int (Id : Natural);
end pc_tasks;
//
//  Buffer.hpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/31/21.
//

#ifndef Buffer_hpp
#define Buffer_hpp

#include <mutex>
#include <condition_variable>
#include <stdio.h>
 
#define BUFFER_CAPACITY 10

class Buffer {
    // Buffer fields
    int buffer [BUFFER_CAPACITY];
    int buffer_size;
    int left; // index where variables are put inside of buffer (produced)
    int right; // index where variables are removed from buffer (consumed)
    
    // Fields for concurrency
    std::mutex mtx;
    std::condition_variable not_empty;
    std::condition_variable not_full;
    
public:
    // Place integer inside of buffer
    void produce(int thread_id, int num);
    
    // Remove integer from buffer
    int consume(int thread_id);
    
    Buffer();
};

#endif /* Buffer_hpp */

This comparison shows the interface for Ada task types while the C++ interface (.hpp) file shows the interface for the Buffer class. The C++ interface definition defines the interfaces, both public and private, to the Buffer class.

Shared Buffer Implementations

The Ada package body contains both the definition and implementation of the shared buffer object and the implementation of the task types.

Ada C++
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Numerics.Discrete_Random;

package body pc_tasks is
   type Index_T is mod 10; -- Modular type for 10 values
   type Circular_Array is array (Index_T) of Integer;

   protected buffer is
      entry produce (Item : in Integer);
      entry consume (Item : out Integer);
   private
      Buf      : Circular_Array;
      P_Index  : Index_T := Index_T'First;
      C_Index  : Index_T := Index_T'First;
      Buf_Size : Natural := 0;
   end buffer;

   protected body buffer is
      entry produce (Item : in Integer) when Buf_Size < Index_T'Modulus is
      begin
         Buf (P_Index) := Item;
         P_Index       := P_Index + 1;
         Buf_Size      := Buf_Size + 1;
      end produce;

      entry consume (Item : out Integer) when Buf_Size > 0 is
      begin
         Item     := Buf (C_Index);
         C_Index  := C_Index + 1;
         Buf_Size := Buf_Size - 1;
      end consume;
   end buffer;

   task body produce_Int is
      subtype decimal is Integer range 1 .. 10;
      package rand_int is new Ada.Numerics.Discrete_Random (decimal);
      use rand_int;
      value : decimal;
      seed  : Generator;
   begin
      Reset (seed);
      for I in 1 .. 4 loop
         value := Random (seed);
         buffer.produce (value);
         Put_Line ("Task" & Id'Image & " produced" & value'Image);
         delay 0.1;
      end loop;
   end produce_Int;

   task body consume_Int is
      Num : Integer;
   begin
      for I in 1 .. 6 loop
         buffer.consume (Num);
         Put_Line ("Task" & Id'Image & " consumed" & Num'Image);
         delay 0.1;
      end loop;
   end consume_Int;

end pc_tasks;
//
//  Buffer.cpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/31/21.
//

#include <iostream>
#include "Buffer.hpp"

Buffer::Buffer() {
    buffer_size = 0;
    left = 0;
    right = 0;
}

void Buffer::produce(int thread_id, int num) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    std::cout << "thread " << thread_id << " produced " << num << "\n";
    
    // Wait if the buffer is full
    not_full.wait(unique_lock, [this]() {
        return buffer_size != BUFFER_CAPACITY;
    });
    
    // Add input to buffer
    buffer[right] = num;
    
    // Update appropriate fields
    right = (right + 1) % BUFFER_CAPACITY;
    buffer_size++;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that buffer isn't empty
    not_empty.notify_one();
}

int Buffer::consume(int thread_id) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    // Wait if buffer is empty
    not_empty.wait(unique_lock, [this]() {
        return buffer_size != 0;
    });
    
    // Getvalue from position to remove in buffer
    int result = buffer[left];
    
    std::cout << "thread " << thread_id << " consumed " << result << "\n";
    
    // Update appropriate fields
    left = (left + 1) % BUFFER_CAPACITY;
    buffer_size--;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that the buffer isn't full
    not_full.notify_one();
    
    // Return result
    return result;
}

The Ada part of the package implementing the shared buffer is isolated below, along with a repeat of the C++ Buffer class implementation.

Ada C++
   type Index_T is mod 10; -- Modular type for 10 values
   type Circular_Array is array (Index_T) of Integer;

   protected buffer is
      entry produce (Item : in Integer);
      entry consume (Item : out Integer);
   private
      Buf      : Circular_Array;
      P_Index  : Index_T := Index_T'First;
      C_Index  : Index_T := Index_T'First;
      Buf_Size : Natural := 0;
   end buffer;

   protected body buffer is
      entry produce (Item : in Integer) when Buf_Size < Index_T'Modulus is
      begin
         Buf (P_Index) := Item;
         P_Index       := P_Index + 1;
         Buf_Size      := Buf_Size + 1;
      end produce;

      entry consume (Item : out Integer) when Buf_Size > 0 is
      begin
         Item     := Buf (C_Index);
         C_Index  := C_Index + 1;
         Buf_Size := Buf_Size - 1;
      end consume;
   end buffer;
//
//  Buffer.cpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/31/21.
//

#include <iostream>
#include "Buffer.hpp"

Buffer::Buffer() {
    buffer_size = 0;
    left = 0;
    right = 0;
}

void Buffer::produce(int thread_id, int num) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    std::cout << "thread " << thread_id << " produced " << num << "\n";
    
    // Wait if the buffer is full
    not_full.wait(unique_lock, [this]() {
        return buffer_size != BUFFER_CAPACITY;
    });
    
    // Add input to buffer
    buffer[right] = num;
    
    // Update appropriate fields
    right = (right + 1) % BUFFER_CAPACITY;
    buffer_size++;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that buffer isn't empty
    not_empty.notify_one();
}

int Buffer::consume(int thread_id) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    // Wait if buffer is empty
    not_empty.wait(unique_lock, [this]() {
        return buffer_size != 0;
    });
    
    // Getvalue from position to remove in buffer
    int result = buffer[left];
    
    std::cout << "thread " << thread_id << " consumed " << result << "\n";
    
    // Update appropriate fields
    left = (left + 1) % BUFFER_CAPACITY;
    buffer_size--;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that the buffer isn't full
    not_full.notify_one();
    
    // Return result
    return result;
}

 The Ada buffer definition begins by defining the array type to be used in the shared buffer. Ada allows arrays to be indexed by any discrete type. In this example an Ada modular type is declared and named Index_T. Type Index_T is declared to be "mod 10", which specifies that all its values are in the range of 0 through 9 and all the arithmetic operators return a value within this range. The only arithmetic operator used in this example is "+". Addition on a modular type is modular. Thus, in this example, 9 + 1 yields 0, which is exactly as needed for a circular buffer.

Type Circular_Array is an array indexed by Index_T. Every element of Circular_Array is an Integer.

Ada protected objects are protected against race conditions. They are specifically used for data shared by Ada tasks. Ada tasks are commonly implemented as operating system threads, but may also be used on a bare-bones system using only a compiler-generated Ada runtime.

The protected object is named buffer. It is separated into a specification and an implementation, but both parts in this example are contained in the package body. The protected specification declares the name of the protected object. There are three kinds of methods that may be used inside a protected object: procedures, entries and functions. Procedures have exclusive unconditional read-write access to the data in the protected object. Entries have conditional read-write access to the data in a shared object. Functions have shared read-only access to the data in the protected object. This example only uses two entries. The private portion of the protected object contains the definition of the data members in the protected object. Buf is an instance of Circular_Array. P_Index is an instance of the Index_T type and is used by the producer to add new data to the protected object. C_Index is an instance of Index_T type and is used by the consumer to index data read from the protected object. Buf_Size is an instance of the Natural subtype of Integer. Natural is a pre-defined subtype of Integer with a minimum value of 0. Buf_Size is initialized with the value 0.

The protected body implements the two entries. Each entry has an associated condition which must evaluate to True for the entry to execute. All tasks calling an entry while its controlling condition evaluates to False are implicitly placed in an entry queue for the called entry using a queuing policy of First-In-First-Out (FIFO). The next entry call in the queue is serviced as soon as the condition evaluates to TRUE. Tasks suspended in the entry queue are given access to the protected entry before any new tasks, thus maintaining the temporal condition of the calls.

The produce entry can only write to the protected object when Buf_Size is less than Index_T'Modulus, which in this case evaluates to 10. The consumer entry can only read from the protected object when Buf_Size is greater than 0.

Each entry implicitly handles all locking and unlocking of the protected object. The protected object is locked just before the "begin" reserved word in each entry and is unlocked just before the "end" reserved word in each entry. The modular nature of the index manipulations as well as the implicit lock manipulations explain the relatively simple Ada code compared with the more verbose corresponding C++ code.

Thread Implementations

The Ada task implementations are also contained in the package body while the C++ thread implementations are contained in the main.cpp file. Those corresponding source code sections are compared below.

Ada C++
   task body produce_Int is
      subtype decimal is Integer range 1 .. 10;
      package rand_int is new Ada.Numerics.Discrete_Random (decimal);
      use rand_int;
      value : decimal;
      seed  : Generator;
   begin
      Reset (seed);
      for I in 1 .. 4 loop
         value := Random (seed);
         buffer.produce (value);
         Put_Line ("Task" & Id'Image & " produced" & value'Image);
         delay 0.1;
      end loop;
   end produce_Int;

   task body consume_Int is
      Num : Integer;
   begin
      for I in 1 .. 6 loop
         buffer.consume (Num);
         Put_Line ("Task" & Id'Image & " consumed" & Num'Image);
         delay 0.1;
      end loop;
   end consume_Int;
// Takes in reference to a buffer and adds a random integer
void produceInt(Buffer &buffer) {
    for (int i = 0; i < 4; i++) {
        // Generate random number between 1 and 10
        int new_int = rand() % 10 + 1;
        buffer.produce(i, new_int);
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

// Takes in reference to a buffer and returns the latest int added
// in the buffer
void consumeInt(Buffer &buffer) {
    for (int i = 0; i < 6; i++) {
        buffer.consume(i);
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

The Ada tasks have visibility to the buffer protected object because the task bodies and the protected object are both defined within the same package body scope.

The produce_Int task defines an Integer subtype named decimal with valid values in the range of 1 through 10. That type is passed to the generic package Ada.Numerics.Discrete_Random so that random numbers in the range of 1 through 10 will be generated for this program. The random number seed is reset based upon the system clock using the Reset(seed) command. The for loop iterates through the values 1 through 4. Each iteration generates a new random value, writes the value to buffer.produce, outputs the value to standard output and then delays 0.1 seconds (100 milliseconds).

The consumer_int task defines a local integer variable named Num. The for loop iterates through the numbers 1 through 6. Each iteration calls buffer.consume, assigning the entry out parameter to Num, outputs the consumed value and delays 0.1 seconds.

Program Entry Points

While the program entry point for a C++ program is named "main", the program entry point for an Ada program may have any name chosen by the programmer. Note that the Ada entry point is a procedure, meaning it does not return any value and that procedure has no parameters.

Ada C++
with pc_tasks;    use pc_tasks;
with Ada.Text_IO; use Ada.Text_IO;

procedure Main is
begin
   Put_Line("Executing code in main...");
   declare
      Produce_Task0 : produce_Int (0);
      Consume_Task0 : consume_Int (1);
      Produce_Task1 : produce_Int (2);
      Consume_Task1 : consume_Int (3);
      Produce_Task2 : produce_Int (4);
   begin
      null;
   end;
   Put_Line ("Done!");
end Main;
int main(int argc, const char * argv[]) {
    std::cout << "Executing code in main...\n";
    
    // Initialize random seed
    srand (time(NULL));
    
    // Create Buffer
    Buffer buffer;
    
    // Create a thread to produce
    std::thread produceThread0(produceInt, std::ref(buffer));
    
    std::thread consumeThread0(consumeInt, std::ref(buffer));
    
    std::thread produceThread1(produceInt, std::ref(buffer));
    
    std::thread consumeThread1(consumeInt, std::ref(buffer));
    
    std::thread produceThread2(produceInt, std::ref(buffer));
    
    produceThread0.join();
    produceThread1.join();
    produceThread2.join();
    consumeThread0.join();
    consumeThread1.join();
    
    std::cout << "Done!\n";
    return 0;
}

Ada does not provide a "join()" method. Instead, the code block in which a task or set of task is declared cannot complete until all the tasks within that code block complete. The idiom shown above declared the 5 task type instances within an inner code block, which does not complete until all five of the tasks have terminated. Upon completion of that inner block the message "Done!" is output to standard output.

Complete code listings for both languages

Ada C++
package pc_tasks is
   task type produce_Int (Id : Natural);
   task type consume_Int (Id : Natural);
end pc_tasks;
//
//  Buffer.hpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/31/21.
//

#ifndef Buffer_hpp
#define Buffer_hpp

#include <mutex>
#include <condition_variable>
#include <stdio.h>
 
#define BUFFER_CAPACITY 10

class Buffer {
    // Buffer fields
    int buffer [BUFFER_CAPACITY];
    int buffer_size;
    int left; // index where variables are put inside of buffer (produced)
    int right; // index where variables are removed from buffer (consumed)
    
    // Fields for concurrency
    std::mutex mtx;
    std::condition_variable not_empty;
    std::condition_variable not_full;
    
public:
    // Place integer inside of buffer
    void produce(int thread_id, int num);
    
    // Remove integer from buffer
    int consume(int thread_id);
    
    Buffer();
};

#endif /* Buffer_hpp */
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Numerics.Discrete_Random;

package body pc_tasks is
   type Index_T is mod 10; -- Modular type for 10 values
   type Circular_Array is array (Index_T) of Integer;

   protected buffer is
      entry produce (Item : in Integer);
      entry consume (Item : out Integer);
   private
      Buf      : Circular_Array;
      P_Index  : Index_T := Index_T'First;
      C_Index  : Index_T := Index_T'First;
      Buf_Size : Natural := 0;
   end buffer;

   protected body buffer is
      entry produce (Item : in Integer) when Buf_Size < Index_T'Modulus is
      begin
         Buf (P_Index) := Item;
         P_Index       := P_Index + 1;
         Buf_Size      := Buf_Size + 1;
      end produce;

      entry consume (Item : out Integer) when Buf_Size > 0 is
      begin
         Item     := Buf (C_Index);
         C_Index  := C_Index + 1;
         Buf_Size := Buf_Size - 1;
      end consume;
   end buffer;

   task body produce_Int is
      subtype decimal is Integer range 1 .. 10;
      package rand_int is new Ada.Numerics.Discrete_Random (decimal);
      use rand_int;
      value : decimal;
      seed  : Generator;
   begin
      Reset (seed);
      for I in 1 .. 4 loop
         value := Random (seed);
         buffer.produce (value);
         Put_Line ("Task" & Id'Image & " produced" & value'Image);
         delay 0.1;
      end loop;
   end produce_Int;

   task body consume_Int is
      Num : Integer;
   begin
      for I in 1 .. 6 loop
         buffer.consume (Num);
         Put_Line ("Task" & Id'Image & " consumed" & Num'Image);
         delay 0.1;
      end loop;
   end consume_Int;

end pc_tasks;
//
//  Buffer.cpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/31/21.
//

#include <iostream>
#include "Buffer.hpp"

Buffer::Buffer() {
    buffer_size = 0;
    left = 0;
    right = 0;
}

void Buffer::produce(int thread_id, int num) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    std::cout << "thread " << thread_id << " produced " << num << "\n";
    
    // Wait if the buffer is full
    not_full.wait(unique_lock, [this]() {
        return buffer_size != BUFFER_CAPACITY;
    });
    
    // Add input to buffer
    buffer[right] = num;
    
    // Update appropriate fields
    right = (right + 1) % BUFFER_CAPACITY;
    buffer_size++;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that buffer isn't empty
    not_empty.notify_one();
}

int Buffer::consume(int thread_id) {
    // Acquire a unique lock on the mutex
    std::unique_lock<std::mutex> unique_lock(mtx);
    
    // Wait if buffer is empty
    not_empty.wait(unique_lock, [this]() {
        return buffer_size != 0;
    });
    
    // Getvalue from position to remove in buffer
    int result = buffer[left];
    
    std::cout << "thread " << thread_id << " consumed " << result << "\n";
    
    // Update appropriate fields
    left = (left + 1) % BUFFER_CAPACITY;
    buffer_size--;
    
    // Unlock unique lock
    unique_lock.unlock();
    
    // Notify a single thread that the buffer isn't full
    not_full.notify_one();
    
    // Return result
    return result;
}
with pc_tasks;    use pc_tasks;
with Ada.Text_IO; use Ada.Text_IO;

procedure Main is
begin
   Put_Line("Executing code in main...");
   declare
      Produce_Task0 : produce_Int (0);
      Consume_Task0 : consume_Int (1);
      Produce_Task1 : produce_Int (2);
      Consume_Task1 : consume_Int (3);
      Produce_Task2 : produce_Int (4);
   begin
      null;
   end;
   Put_Line ("Done!");
end Main;
//
//  main.cpp
//  ProducerConsumer
//
//  Created by Andrew Wei on 5/30/21.
//

#include <thread>
#include <iostream>
#include "Buffer.hpp"
#include <stdlib.h>

// Takes in reference to a buffer and adds a random integer
void produceInt(Buffer &buffer) {
    for (int i = 0; i < 4; i++) {
        // Generate random number between 1 and 10
        int new_int = rand() % 10 + 1;
        buffer.produce(i, new_int);
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

// Takes in reference to a buffer and returns the latest int added
// in the buffer
void consumeInt(Buffer &buffer) {
    for (int i = 0; i < 6; i++) {
        buffer.consume(i);
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

int main(int argc, const char * argv[]) {
    std::cout << "Executing code in main...\n";
    
    // Initialize random seed
    srand (time(NULL));
    
    // Create Buffer
    Buffer buffer;
    
    // Create a thread to produce
    std::thread produceThread0(produceInt, std::ref(buffer));
    
    std::thread consumeThread0(consumeInt, std::ref(buffer));
    
    std::thread produceThread1(produceInt, std::ref(buffer));
    
    std::thread consumeThread1(consumeInt, std::ref(buffer));
    
    std::thread produceThread2(produceInt, std::ref(buffer));
    
    produceThread0.join();
    produceThread1.join();
    produceThread2.join();
    consumeThread0.join();
    consumeThread1.join();
    
    std::cout << "Done!\n";
    return 0;
}

 Summary

The same producer-consumer problem can be solved using both Ada and C++. The C++ approach to the producer-consumer pattern requires far more attention to low level details than does the Ada approach to the producer-consumer pattern. The greatest difference in the two approaches is the requirement for the C++ programmer to explicitly manipulate mutex locking/unlocking and suspended thread wait and notification commanding.

  • 15 October 2023 at 22:53

Parallel Comparison of Java Producer-Consumer with Ada Producer-Consumer

 

Comparison of Java producer-consumer source code with Ada producer-consumer source code. While the Java program defines several classes the Ada program defines one Ada package and a main procedure. The Ada package encapsulates the definitions of the shared buffer type and the task types. The main procedure creates instances of the shared buffer type and the task types.

Ada packages separate interface definitions from implementation. In this example the interface definition and the definition are split into two files, which Ada calls the package specification and the package body.

The Shared buffer

Both programs implement a producer-consumer model using a single-element buffer shared by the producer and the consumer.

Both programs implement a shared buffer object with two data elements. A count is stored in a variable named materials and a  Boolean variable named available is used to control access to the shared buffer by the producer and consumer thread (or task in Ada).

The Java program implements the shared buffer as a class while the Ada program implements the shared buffer as a protected object.

Ada Java
   protected type buffer is
      entry Put (Item : in Integer);
      entry Get (Item : out Integer);
   private
      Materials : Integer;
      Available : Boolean := False;
   end buffer;

   type Buffer_Access is access buffer;
   protected body buffer is

      ---------
      -- Put --
      ---------

      entry Put (Item : in Integer) when not Available is
      begin
         Materials := Item;
         Available := True;
      end Put;

      ---------
      -- Get --
      ---------

      entry Get (Item : out Integer) when Available is
      begin
         Item      := Materials;
         Available := False;
      end Get;

   end buffer;
class Shop
{
      private int materials;
      private boolean available = false;
      public synchronized int get()
      {
            while (available == false)
            {
                  try
                  {
                        wait();
                  }
                  catch (InterruptedException ie)
                  {
                  }
            }
            available = false;
            notifyAll();
            return materials;
      }
      public synchronized void put(int value)
      {
            while (available == true)
            {
                  try
                  {
                        wait();
                  }
                  catch (InterruptedException ie)
                  {
                        ie.printStackTrace();
                  }
            }
            materials = value;
            available = true;
            notifyAll();
      }
}

Ada separates interface definition from implementation while Java does not separate the two. The implementation is the interface definition.

The Ada protected object named buffer is defined to have two entries named Put and Get. Put writes an Integer value to Buffer.  Get reads the current Integer value in Buffer and passes that value out to the calling task. The buffer protected object has two private  data members. Materials is an Integer. Available is a Boolean instance initialized to False.

The Java Shop class has two private data members. They are materials, which is an int and available, which is a boolean initialized to false.

The Ada implementation provides the implementation of the two entries named Put and Get. Ada protected entries always have an associated condition which must evaluate to True for the entry to be executed. The Put entry condition is defined as "when not Available" while the Get entry condition is defined as "when Available". Thus, the Put entry will only execute when Available is True and the GET entry will only execute when Available is False.

When the entry condition is false the task calling the entry is suspended in an entry queue implicitly maintained by the protected object. The entry queue defaults to a First-In, First-Out (FIFO) queuing policy so that the entry queue is emptied in the order the tasks called the entry.

The Java Shop class achieves the same effect by explicitly writing a polling loop which only exits when the available private data member evaluates to the proper condition. The while loop condition is the inverse of the Ada condition because the loop continues while the available  data member does not satisfy the condition for the method to execute. Each time through the loop the method calls the wait()  method because the method will only be executed when the thread calling the method awakes due to the notifyAll() method call. The notifyAll() method awakens all waiting threads and the one that can proceed does so.



The Producer

The Ada program creates a producer task. The Java program creates a Producer task which extends the Thread class.

Ada Java
  task type Producer (Buf : Buffer_Access; Id : Positive);
  task body Producer is
  begin
   for I in 0 .. 9 loop
     Buf.Put (I);
     Put_Line ("Producer" & Id'Image & " produced" & I'Image);
     delay 0.000_1;
   end loop;
  end Producer;
class Producer extends Thread
{
      private Shop Shop;
      private int number;

      public Producer(Shop c, int number)
      {
            Shop = c;
            this.number = number;
      }
      public void run()
      {
            for (int i = 0; i < 10; i++)
            {
                  Shop.put(i);
                  System.out.println("Produced value " + this.number+ " put: " + i);
                  try
                  {
                        sleep((int)(Math.random() * 100));
                  }
                  catch (InterruptedException ie)
                  {
                        ie.printStackTrace();
                  }
            }
      }
}

Ada tasks separate the task interface from the task implementation. A task type named producer is declared with a discriminant value. In this case the discriminant value is used to identify each instance of the task type. The task implementation simply iterates through the values 0 through 9, each time calling buffer.put with the loop iteration value, and then outputting the value to standard output. The buffer protected object is visible to the task because they are all created within the same scope. In this case that scope is the program main procedure.

The Java program creates a Producer class which extends Thread. An variable of the Shop class named Shop is created. The Producer constructor is used to set the value of the Shop variable and also to set the value of the number private data member. The run() method iterates through the values 0 through 9, each time calling Shop.put with the iteration value. Each iteration the method sleeps a random number between 0 and 100 milliseconds.

The Consumer

The Ada consumer task type is very similar to the Ada producer task type and the Java Consumer class is very similar to the Java Producer class.

Ada Java
   task type Consumer (Buf : Buffer_Access; Id : Positive);
   task body Consumer is
      Value : Integer;
   begin
      for I in 1 .. 10 loop
         Buf.Get (Value);
         Put_Line ("Consumer" & Id'Image & " consumed" & Value'Image);
      end loop;
   end Consumer;
class Consumer extends Thread
{
      private Shop Shop;
      private int number;
      public Consumer(Shop c, int number)
      {
            Shop = c;
            this.number = number;
      }
      public void run()
      {
            int value = 0;
            for (int i = 0; i < 10; i++)
            {
                  value = Shop.get();
                  System.out.println("Consumed value " + this.number+ " got: " + value);
            }
      }
}

The Ada consumer task declares a local variable named Value. The task iterates 10 times, each time calling buffer.Get and then printing the value passed out to the Value variable.

The Java Consumer class run() method iterates 10 times, each time calling Shop.get() and printing out the value returned.

The Program Entry Point

The program entry point for Java is always a method named public static void main(String[] args) while the Ada program entry point can have any name. The Ada program entry point is always a parameter-less procedure. In this example that procedure is also named main for similarity with the Java example. The Java entry point method resides in a class named ProducerConsumer

while the Ada main procedure encapsulates all the other parts of this program.

Ada Java
with simple_buffer_pc; use simple_buffer_pc;

procedure Main is
   shop : Buffer_Access := new buffer;
   P1 : Producer (Buf => shop, Id => 1);
   C1 : Consumer (Buf => shop, Id => 1);
begin
   null;
end Main;
public class ProducerConsumer
{
      public static void main(String[] args)
      {
            Shop c = new Shop();
            Producer p1 = new Producer(c, 1);
            Consumer c1 = new Consumer(c, 1);
            p1.start();
            c1.start();
      }
}

The Java main method creates a new instance of the Shop class then creates one instance each of the Producer class and the Consumer class, passing the Shop class instance to both so both threads reference the same shop instance. The threads are started by calling the start() method inherited from the Thread class.

The Ada main procedure contains the definitions of the protected object Buffer and the two task types producer and consumer. After the end of the consumer task definition one instance of the producer task type is created and one instance of the consumer task type is created. The tasks automatically start when the program reached the begin reserved word for the main procedure. The main procedure then does nothing, which is signified by the null reserved word. The main procedure will not terminate until all the tasks created within the main task terminate. In Java terms, the main task implicitly joins the producer and consumer tasks.

Both entire programs

The full source code of programs are presented below to provide full context for the reader.

Ada Java
package simple_buffer_pc is
   protected type buffer is
      entry Put (Item : in Integer);
      entry Get (Item : out Integer);
   private
      Materials : Integer;
      Available : Boolean := False;
   end buffer;

   type Buffer_Access is access buffer;
   task type Producer (Buf : Buffer_Access; Id : Positive);
   task type Consumer (Buf : Buffer_Access; Id : Positive);
end simple_buffer_pc;
with Ada.Text_IO; use Ada.Text_IO;

package body simple_buffer_pc is

   protected body buffer is

      entry Put (Item : in Integer) when not Available is
      begin
         Materials := Item;
         Available := True;
      end Put;

      entry Get (Item : out Integer) when Available is
      begin
         Item      := Materials;
         Available := False;
      end Get;
   end buffer;

   task body Producer is
   begin
      for I in 0 .. 9 loop
         Buf.Put (I);
         Put_Line ("Producer" & Id'Image & " produced" & I'Image);
         delay 0.000_1;
      end loop;
   end Producer;

   task body Consumer is
      Value : Integer;
   begin
      for I in 1 .. 10 loop
         Buf.Get (Value);
         Put_Line ("Consumer" & Id'Image & " consumed" & Value'Image);
      end loop;
   end Consumer;

end simple_buffer_pc;
with simple_buffer_pc; use simple_buffer_pc;

procedure Main is
   shop : Buffer_Access := new buffer;
   P1 : Producer (Buf => shop, Id => 1);
   C1 : Consumer (Buf => shop, Id => 1);
begin
   null;
end Main;
public class ProducerConsumer
{
      public static void main(String[] args)
      {
            Shop c = new Shop();
            Producer p1 = new Producer(c, 1);
            Consumer c1 = new Consumer(c, 1);
            p1.start();
            c1.start();
      }
}
class Shop
{
      private int materials;
      private boolean available = false;
      public synchronized int get()
      {
            while (available == false)
            {
                  try
                  {
                        wait();
                  }
                  catch (InterruptedException ie)
                  {
                  }
            }
            available = false;
            notifyAll();
            return materials;
      }
      public synchronized void put(int value)
      {
            while (available == true)
            {
                  try
                  {
                        wait();
                  }
                  catch (InterruptedException ie)
                  {
                        ie.printStackTrace();
                  }
            }
            materials = value;
            available = true;
            notifyAll();
      }
}
class Consumer extends Thread
{
      private Shop Shop;
      private int number;
      public Consumer(Shop c, int number)
      {
            Shop = c;
            this.number = number;
      }
      public void run()
      {
            int value = 0;
            for (int i = 0; i < 10; i++)
            {
                  value = Shop.get();
                  System.out.println("Consumed value " + this.number+ " got: " + value);
            }
      }
}
class Producer extends Thread
{
      private Shop Shop;
      private int number;

      public Producer(Shop c, int number)
      {
            Shop = c;
            this.number = number;
      }
      public void run()
      {
            for (int i = 0; i < 10; i++)
            {
                  Shop.put(i);
                  System.out.println("Produced value " + this.number+ " put: " + i);
                  try
                  {
                        sleep((int)(Math.random() * 100));
                  }
                  catch (InterruptedException ie)
                  {
                        ie.printStackTrace();
                  }
            }
      }
}
  • Both programs produce very similar results although the Java example needs to deal with possible exceptions while the Ada example does not need to deal with exceptions. 
  • The logic used to ensure the Java Shop put method uses a form of a spin lock implementing a subtle form of negative logic to ensure the materials data member is only updated when available is false while the Ada buffer put entry uses positive logic.
  • The logic used to ensure the Java Shop get method uses a form of a spin lock implementing a subtle form of negative logic to ensure the materials data member is only read when available is true while the Ada buffer get entry uses positive logic.
  • Even with the need to separate interface from implementation the Ada program requires less typing than the Java program.



  • 14 October 2023 at 16:42

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.

  • 13 August 2023 at 05:16

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.
  • 8 August 2023 at 02:00

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.

  • 5 August 2023 at 20:36

Threads of Confusion

Many programming languages support concurrent behavior through the creation of threads and the explicit manipulation of semaphores, locks or mutexes. The C language seems to have initiated this approach to handling concurrency.

C example

The following example of using a mutex with thread comes from C Program to Show Thread Interface and Memory Consistency Errors – GeeksforGeeks

1       // C program to use a mutex to avoid memory consistency

2       // errors

3       #include <pthread.h>

4       #include <stdio.h>

5       #include <stdlib.h>

6

7       // Global variable that will be shared among threads

8       int shared_counter = 0;

9

10       // Mutex to protect the shared counter

11       pthread_mutex_t shared_counter_mutex

12       = PTHREAD_MUTEX_INITIALIZER;

13

14       // Function that will be executed by each thread

15       void* thread_function(void* thread_id)

16       {

17               // Get the thread ID

18               long tid = (long)thread_id;

19

20               // Lock the mutex to protect the shared counter

21               pthread_mutex_lock(&shared_counter_mutex);

22

23               // Increment the shared counter

24               shared_counter++;

25

26               // Print the thread ID and the updated value of the

27               // shared counter

28               printf("Thread %ld: shared_counter = %d\n", tid,

29                             shared_counter);

30

31               // Unlock the mutex

32               pthread_mutex_unlock(&shared_counter_mutex);

33

34               // Return NULL to indicate successful execution of the

35               // thread

36               return NULL;

37   }

38

39       int main(int argc, char* argv[])

40       {

41               // Check if the number of arguments is correct

42               if (argc != 2) {

43                       printf("Usage: %s <number_of_threads>\n", argv[0]);

44                       exit(EXIT_FAILURE);

45       }

46

47               // Get the number of threads to create from the command

48               // line arguments

49               int num_threads = atoi(argv[1]);

50

51               // Create an array of pthread_t structures to store the

52               // thread IDs

53               pthread_t* threads = (pthread_t*)malloc(

54                       num_threads * sizeof(pthread_t));

55

56               // Create the specified number of threads

57               for (int i = 0; i < num_threads; i++) {

58                       int status = pthread_create(

59                               &threads[i], NULL, thread_function, (void*)i);

60                       if (status != 0) {

61                               printf("Error: pthread_create() returned error "

62                                             "code %d\n",

63                                             status);

64                               exit(EXIT_FAILURE);

65           }

66       }

67

68               // Wait for all threads to finish execution

69               for (int i = 0; i < num_threads; i++) {

70                       int status = pthread_join(threads[i], NULL);

71                       if (status != 0) {

72                               printf("Error: pthread_join() returned error "

73                                             "code %d\n",

74                                             status);

75                               exit(EXIT_FAILURE);

76           }

77       }

78

79               // Free the memory allocated for the thread IDs

80               free(threads);

81

82               // Print the final value of the shared counter

83               printf("Final value of shared_counter: %d\n",

84                             shared_counter);

85

86               // Return success

87               return 0;

88   }

The C threading model uses the pthread library to create threads. The behavior of each created thread is controlled by the function passed to the thread as part of the pthread_create function parameter list. First an array of pthread_t structures is created:

53               pthread_t* threads = (pthread_t*)malloc(

54                       num_threads * sizeof(pthread_t));

Next, the Id number of each thread is created as the function named thread_function is passed to each element of the thread as a parameter to the pthread_create function:

57               for (int i = 0; i < num_threads; i++) {

58                       int status = pthread_create(

59                               &threads[i], NULL, thread_function, (void*)i);

60                       if (status != 0) {

61                               printf("Error: pthread_create() returned error "

62                                             "code %d\n",

63                                             status);

64                               exit(EXIT_FAILURE);

65           }

66       }

The third parameter to the pthread_create command is the function passed to the newly created thread. The fourth argument is the parameter passed to the function passed to the thread. Not only is the thread function parameter passed as the fourth argument to the pthread_create function, it is also cast to a pointer to void. This bit of syntax can be confusing because the value being passed is not a pointer, but rather an int.

Let's now look inside the function named thread_function, but before that, let's look at the creation of the pthread_mutex used to control access to the shared counter.

10       // Mutex to protect the shared counter

11       pthread_mutex_t shared_counter_mutex

12       = PTHREAD_MUTEX_INITIALIZER;

Yes, the pthread_mutex_t instance used to control access to the shared counter is itself a shared instance of a type. You might also see that the shared_counter_mutex is only loosely connected to the shared_counter integer variable. That loose connection is a voluntary connection not enforced by any syntax in the C pthreads library.

The thread_function is defined as:

14       // Function that will be executed by each thread

15       void* thread_function(void* thread_id)

16       {

17               // Get the thread ID

18               long tid = (long)thread_id;

19

20               // Lock the mutex to protect the shared counter

21               pthread_mutex_lock(&shared_counter_mutex);

22

23               // Increment the shared counter

24               shared_counter++;

25

26               // Print the thread ID and the updated value of the

27               // shared counter

28               printf("Thread %ld: shared_counter = %d\n", tid,

29                             shared_counter);

30

31               // Unlock the mutex

32               pthread_mutex_unlock(&shared_counter_mutex);

33

34               // Return NULL to indicate successful execution of the

35               // thread

36               return NULL;

37   }

The thread function must explicitly lock the shared_counter mutex, then increment the shared_counter, then output the current value of the shared_counter and finally unlock the shared_counter_mutex.

A major source of confusion

The order of the locking modifying and unlocking the mutex is critical. The shared_counter knows nothing of these locks. The pthread_mutex_t has no syntactical connection to the shared_counter. On the other hand, failing to lock, perform operations and then unlock the mutex will result in semantic failures which prevent the mutex from properly locking the shared_counter and then unlocking the shared counter after the operations are completed. Even worse, there is no syntax in the C pthread library prohibiting a thread from simply accessing the shared_counter while completely ignoring the mutex lock and unlock behaviors.

Further program issues

The remainder of the program calls pthread_join, forcing the main thread to wait until all the pthreads have completed before continuing to execute its sequence of instructions.

68               // Wait for all threads to finish execution

69               for (int i = 0; i < num_threads; i++) {

70                       int status = pthread_join(threads[i], NULL);

71                       if (status != 0) {

72                               printf("Error: pthread_join() returned error "

73                                             "code %d\n",

74                                             status);

75                               exit(EXIT_FAILURE);

76           }

77       }

It is important to understand that the pthread_join function called for each thread can fail and return failure status.

Once the pthreads have completed the program frees all the pointers in the array of pointers to pthread_t that were created to create the array of threads. This is done because it is always correct to free dynamically allocated memory when that memory is no longer needed in the program.

While this action is not particularly confusing, it is yet another detail that should be explicitly implemented.

Ada Example

The Ada programming language has tasking, which is roughly equivalent to threads, built into the core language since the first Ada language standard in 1983. In the 1995 standard protected types were added to the core language, which allow asynchronous communication between tasks. There are no special Ada libraries to implement tasking or protected types.

A protected type or protected object is protected against inappropriate simultaneous access to a shared data structure. A protected type or object is built very much in the philosophy of Object Oriented Programming inasmuch as the protected object has programmer-defined behaviors, however the locking and unlocking of the protected object is performed implicitly by the object itself and not through explicit lock and unlock methods called by the task accessing the protected object.

There are three kinds of protected methods.

  • Protected procedures – Protected procedures control an unconditional exclusive read-write lock on the protected object. The task calling the protected procedure can access the protected object whenever the object is unlocked.

  • Protected entries – Protected entries control a conditional exclusive read-write lock on the protected object. The calling task can only execute the entry when its boundary condition evaluates to True and only then can the task implicitly acquire the exclusive read-write lock.

  • Protected functions – Protected functions control an unconditional shared read lock on the protected object. This allows multiple tasks to simultaneously read from the protected object at the same time, but prevents any task to execute any procedure or entry while tasks are calling protected functions.

The following Ada example creates a protected object implementing the shared counter. The protected object in this example implements one procedure and one function. The source code for this program is:

1       with Ada.Text_IO;         use Ada.Text_IO;

2       with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

3

4       procedure Main is

5             Num_Tasks : Positive;

6

7             -- protected object shared by all the tasks

8             protected counter is

9                   procedure update (The_Count : out Natural);

10                   function get_value return Natural;

11             private

12                   count : Natural := 0;

13             end counter;

14

15             protected body counter is

16                   procedure update (The_Count : out Natural) is

17                   begin

18                         count     := count + 1;

19                         The_Count := count;

20                   end update;

21                   function get_value return Natural is

22                   begin

23                         return count;

24                   end get_value;

25             end counter;

26

27             -- Define the task type

28             task type thread is

29                   entry set_id (Id : in Positive);

30             end thread;

31

32             task body thread is

33                   Me       : Positive;

34                   My_Count : Natural;

35             begin

36                   -- accept the set_id entry call from the main task

37                   accept set_id (Id : in Positive) do

38                         Me := Id;

39                   end set_id;

40

41                   counter.update (My_Count);

42                   Put_Line ("Task" & Me'Image & ": counter =" & My_Count'Image);

43             end thread;

44

45       begin

46             Put ("Enter the number of tasks to create: ");

47             Get (Num_Tasks);

48

49             -- declare an inner block in which all the tasks will execute

50             -- the inner block will only complete after all tasks have completed

51             declare

52                   -- create an array of thread objects

53                   pool : array (1 .. Num_Tasks) of thread;

54             begin

55                   for I in pool'Range loop

56                         -- set the id number of each thread object

57                         pool (I).set_id (I);

58                   end loop;

59             end;

60

61      -- output the total after all threads have completed

62      Put_Line

63        ("The final value of the shared counter:" &

64         Natural'Image (counter.get_value));

65

66   end Main;

Ada allows functions, procedures, protected objects and task types to be declared within any function, procedure or task type. This means all items declared in this program are completely local to this program and not “static” as are multiple functions created in the same file in C.

Ada variables are declared by stating the name of the variable, followed by a colon, followed by the type of the variable. This is opposite the order of declaring variables in C where the type is listed first followed by the variable name.

5             Num_Tasks : Positive;

The variable name is Num_Tasks. The type is Positive, which is a pre-defined subtype of the Ada Integer type. Integer is equivalent to the C int type. Positive is an Integer with a minimum possible value of 1 and a maximum possible value of Integer'Last, which is the same as MAX_INT in C. This variable is used to contain the number of tasks the user specifies during the execution of the program.

The protected object named counter is declared in two parts. Protected objects are always declared in two parts. The protected specification defines the public view of the protected methods along with a private view of the data elements in the protected object. The protected body contains the definition of the protected methods, and is not visible to any task calling the protected object.

The protected specification for the counter protected object is:

8             protected counter is

9                   procedure update (The_Count : out Natural);

10                   function get_value return Natural;

11             private

12                   count : Natural := 0;

13             end counter;

There are two methods for this protected object. The procedure named update has one parameter which passes a value of type Natural out to the calling task. Natural is a predefined subtype of Integer with a minimum value of 0. The function named get_value returns a value of the subtype Natural.

In the private section of the protected specification one data element is declared. It is a variable named count. The type of the variable is Natural and it is initialized to 0.

The protected body for the counter protected object is:

15             protected body counter is

16                   procedure update (The_Count : out Natural) is

17                   begin

18                         count     := count + 1;

19                         The_Count := count;

20                   end update;

21                   function get_value return Natural is

22                   begin

23                         return count;

24                   end get_value;

25             end counter;

The update procedure increments count and passes its current value out through the parameter named The_Count.

The function get_value simply returns the value of count. The Ada compiler will issue an error message if the programmer attempts to modify the count data member of the protected object within the execution of the get_value function. Functions are read-only methods in a protected object.

The procedure update implicitly implements a read-write lock and the function get_value implicitly implements a read lock.

The task type named thread is defined in two parts. The first part, the task specification, defines that name of the task type and the direct interfaces to the task type. In this case one task entry is defined. That entry is used to set the task ID.

28             task type thread is

29                   entry set_id (Id : in Positive);

30             end thread;

The task entry implements a direct synchronous communication channel to each instance of the thread type. The entry synchronization scheme is called a Rendezvous. The word "rendezvous" is a French word meaning "a meeting at an agreed time and place". A task calling another task's entry is will suspend until the task declaring the entry accepts the entry call. Similarly, a task accepting an entry will suspend until another task calls that entry. Once both the task calling the entry and the task accepting the entry are in this state for an overlapping time period any data specified in the entry specification is passed between the calling task and the called task. Once the entry has completed both tasks continue to execute concurrently.

The behavior of the task type is defined in the task body.

32             task body thread is

33                   Me       : Positive;

34                   My_Count : Natural;

35             begin

36                   -- accept the set_id entry call from the main task

37                   accept set_id (Id : in Positive) do

38                         Me := Id;

39                   end set_id;

40

41                   counter.update (My_Count);

42                   Put_Line ("Task" & Me'Image & ": counter =" & My_Count'Image);

43             end thread;

The task body declared two local variables. Each instance of the task type has unique instances of these two variables.

The first action taken by the thread task is to accept the set_id entry, passing the Id value from a calling task to this task. The accept statement assigns the value of Id to the task's local variable named Me. Task entries implement a Rendezvous behavior. The thread task will wait at the accept statement until its entry is called by another task. Once the value is passed to the thread task both tasks will the resume concurrent behavior.

The thread task calls the protected object's update procedure, using its local variable My_Count to receive the current value of the counter protected object. Finally, the thread task simply outputs the value it received from the counter.update procedure.

The next “begin” begins the execution of the Main task.

45       begin

46             Put ("Enter the number of tasks to create: ");

47             Get (Num_Tasks);

48

49             -- declare an inner block in which all the tasks will execute

50             -- the inner block will only complete after all tasks have completed

51             declare

52                   -- create an array of thread objects

53                   pool : array (1 .. Num_Tasks) of thread;

54             begin

55                   for I in pool'Range loop

56                         -- set the id number of each thread object

57                         pool (I).set_id (I);

58                   end loop;

59             end;

60

61      -- output the total after all threads have completed

62      Put_Line

63        ("The final value of the shared counter:" &

64         Natural'Image (counter.get_value));

65

66   end Main;

The Main task prompts the user for the number of tasks to create and reads the number entered by the user.

An inner block is created starting at the “declare” reserved word. That inner block has a declarative section in which an array of thread tasks, equal in number to the value entered by the user, is created. The tasks in the array named pool begin executing immediately. Their first responsibility is to accept the set_id entry, so each task waits until its set_id entry is called.

The “for” loop iterates through each element in the pool array assigning the element's index value as the ID for the task.

Immediately after accepting its ID number each task executes counter.update and then outputs the value of the counter passed back through the counter.update procedure.

The inner block will only complete when all the tasks created within the block complete. This produces the same effect as the “join” command in the C example.

After the inner block completes the Main task calls the counter.get_value function and displays the final value of the shared counter. Completion of the inner block automatically frees the array of task objects which were created on the stack at the start of the inner block. No explicit loop to free the task elements is needed or even possible.

Conclusion

While the two programs above achieve the same behavior dealing with allowing multiple threads or tasks to update a shared counter, the C solution contains more opportunities for programmer confusion and error. It also requires a lot more coding by the programmer than the Ada solution.

  • 22 July 2023 at 01:49

Bit Arrays

 

A bit array is an array that compactly stores bits. A bit may represent the values 0 or 1, or it can be viewed as representing the values False or True.

The C language has a somewhat loose interpretation of Boolean values, treating 0 as false and non-zero as true. The Ada programming language defines the Boolean type as the enumeration (False, True). Since that enumeration has only two values the Boolean type has only two position values. False is at position 0 and True is at position 1.

C array indexing is connected to memory addresses. The typical smallest memory addressable value is a byte, which is typically 8 bits. Indexing a bit array, where each bit within a string of bytes has its own index value requires some bit gymnastics.

The following C example is taken from https://www.sanfoundry.com/c-program-implement-bit-array/


Two functions are created.

The function toggle_bit toggles the bit at the index value specified by the function’s second parameter.

The function get_bit returns the numeric value of the bit at the index value specified by the function’s second value.

The output of the program is:

0: 1

1: 0

2: 1

3: 0

4: 1

5: 0

6: 1

7: 0

8: 1

9: 0

10: 1

11: 0

12: 1

13: 0

14: 1

15: 0

16: 1

17: 0

18: 1

19: 0

20: 1

21: 0

22: 1

23: 0

24: 1

25: 0

26: 1

27: 0

28: 1

29: 0

30: 1

31: 0

32: 1

33: 0

34: 1

35: 0

36: 1

37: 0

38: 1

39: 0

40: 1

41: 0

42: 1

43: 0

44: 1

45: 0

46: 1

47: 0

48: 1

49: 0

50: 1

51: 0

52: 1

53: 0

54: 1

55: 0

56: 0

57: 0

 

The Ada language allows the declaration of packed arrays of Boolean to represent each Boolean as a single bit.

Ada allows the programmer to use normal array index notation to access each element of a bit array.

The following Ada implementation of a bit array produces the same behavior as the C program except that the Ada program also displays the number of elements in the array and the number of bits occupied by an instance of the array.

An unconstrained array type named Bit_Array is declared. Each element of Bit_Array is a Boolean. Every instance of Bit_Array is packed, which causes the Boolean values to be represented by single bits.

Similar to the C program, the variable X is declared to be an instance of Bit_Array containing 58 elements. Whereas the C program uses a macro to create the array of bits, the Ada program uses normal Ada array declaration syntax. In C all the elements of the array are initialized to 0. In Ada all elements of the array are initialized to False.

The “while” loop in the Ada program toggles every other element in the array. The element indexed by the value 56 is then toggled again.

The “for” loop prints the Boolean position of each element of the array.

The output of the Ada program is

X contains 58 elements.

X occupies 64 bits

 

 0: 1

 1: 0

 2: 1

 3: 0

 4: 1

 5: 0

 6: 1

 7: 0

 8: 1

 9: 0

 10: 1

 11: 0

 12: 1

 13: 0

 14: 1

 15: 0

 16: 1

 17: 0

 18: 1

 19: 0

 20: 1

 21: 0

 22: 1

 23: 0

 24: 1

 25: 0

 26: 1

 27: 0

 28: 1

 29: 0

 30: 1

 31: 0

 32: 1

 33: 0

 34: 1

 35: 0

 36: 1

 37: 0

 38: 1

 39: 0

 40: 1

 41: 0

 42: 1

 43: 0

 44: 1

 45: 0

 46: 1

 47: 0

 48: 1

 49: 0

 50: 1

 51: 0

 52: 1

 53: 0

 54: 1

 55: 0

 56: 0

 57: 0

Conclusion:

Both C and Ada can implement bit arrays. The Ada implementation is simpler and easier to understand than is the C implementation.


  • 4 July 2023 at 01:33

Comparing Programming Languages Part 1 Scalar Ranges

 Overview

It is often asserted that all general purpose programming languages can solve the same set of problems. This means that no one programming language has functional advantages over any other programming language.

That assertion is only mostly true, which means it is false.

For example, weakly typed languages can perform and make use of implicit type conversions while strongly typed languages cannot. Strongly typed languages must employ explicit conversions to achieve a similar effect.

The purpose of this article is to begin discussing some of the things that are difficult in one commonly used language and relatively easy in another.

Scalar Ranges

Programming languages derived from Pascal syntax allow scalar types and subtypes to be defined by the programmer, while programming languages derived from C syntax do not allow the programmer to define scalar types or subtypes.

In C++, for example, a class must be declared encapsulating the behavior of a scalar type with a programmer specified range of values. Making a subtype of that class then requires the creation of an inherited class expressing the restrictions distinguishing the subtype.

In C++ enums are encapsulated in a class as illustrated by the following Stack Overflow issue:

How can I implicitly convert an enum to its subset and vice versa in C++?

More precisely, the feature I want is like implicitly convert an enum to its subset enum and vice versa.

The code I wish it working:

enum class Human {

    A = 1,

    B = 2,

};

 

enum class Male {    // subset of Human

    A = Human::A,

};

 

enum class Female {    // subset of Human

    B = Human::B,

};

 

 

// some functions can handle all humans

void human_func(Human h) {

    // ...

}

 

// some only take a subset of humans

void male_func(Male m) {

    // ...

}

 

void female_func(Female m) {

    // ...

}

 

 

// and user only uses values of Human as token

constexpr auto SOMEONE = Human::A;

 

int main() {

    human_func(SOMEONE);  // ok

    male_func(SOMEONE);   // also ok, Human::A implicitly converted to Male

    female_func(SOMEONE); // failed, can't convert Human::A to Female.

}

 

But enum cannot do the conversion. Now I have two options:

// 1. static_assert with template parameter

 

template <Human H>

void female_func() {

    static_assert(H == Human::B);

    // ...

}

 

// 2. manually convert it

 

#define _ENUM_TO_ENUM(e1, e2) \

    static_cast<e2>(static_cast<std::underlying_type_t<decltype(e1)>>(e1))

 

void female_func(_ENUM_TO_ENUM(SOMEONE, Female)) {

    // But this way the compiler does not check if the value is valid.

    // I can put anything in.

    // ...

}

 

 

As is shown above, the concept of a scalar range and subrange is complicated by the need in C++ to express such a type as a class.

One answer provided to this question is

enum class Gender {MALE, FEMALE};

 

struct Human

{

    Gender m_gender;

    Human(Gender g) : m_gender{g}

    {}

    virtual ~Human() = default;

};

 

struct Man : public Human

{

    Man() : Human{Gender::MALE}

    {}

};

struct Woman : public Human

{

    Woman() : Human(Gender::FEMALE)

    {}

};

 

void human_func(const Human & h)

{

    //...

}

void man_func(const Man & m)

{

    //...

}

void woman_func(const Woman & w)

{

    //...

}

 

It is clear that this approach may work for an enum with 2 values, but becomes unusable with an enum containing tens or hundreds of values.

The Ada programming language, on the other hand, uses the concept of scalar ranges and subtypes extensively.

The Character type in Ada is an enumeration type with the range of values expressed as nul .. 'ÿ'. The ASCII characters are a subset of the Character type with value in the range of nul .. del. Within the ASCII characters the upper case characters are the range ‘A’ .. ‘Z’ and the lower characters are the range ‘a’ .. ‘z’.

If the programmer wants to pass only upper case characters as a parameter to a procedure the procedure can be defined as

subtype Upper is range (‘A’ .. ‘Z’);

procedure Upper_Action(U : Upper);

This procedure will only accept characters in the range specified by the subtype Upper.

A function that counts all the upper case characters in a string can be defined as

function Count_Uppers (S : in String) return Natural is

   Count : Natural := 0;

begin

   for value of S loop

      if S in Upper then

         Count := Count + 1;

      end if;

    return Count;

end Count_Uppers;

The Ada samples above exhibit the behavior and usage requested by the person using C++ in the Stack Overflow question above.

The Ada program is not encumbered with the heavy syntax and rules associated with C++ classes.

  • 2 June 2023 at 23:23

Comparison of Bit Array Implementations using C and Ada

 

I found the following programming example in Bit Array in C - Sanfoundry

#include <stdio.h>

#define SIZE (58) /* amount of bits */

#define ARRAY_SIZE(x) (x/8+(!!(x%8)))

char get_bit(char *array, int index);

void toggle_bit(char *array, int index);


void toggle_bit(char *array, int index) {

    array[index / 8] ^= 1 << (index % 8);

}

char get_bit(char *array, int index) {

    return 1 & (array[index / 8] >> (index % 8));

}

int main(void) {

    /* initialize empty array with the right size */

    char x[ARRAY_SIZE(SIZE)] = { 0 };

    int i;

    for (i = 0; i < SIZE; i += 2)

        toggle_bit(x, i);

    toggle_bit(x, 56);

    for (i = 0; i < SIZE; i++)

        printf("%d: %d\n", i, get_bit(x, i));

    return 0;

}

 

The program creates a bit array containing 58 elements. The program works as expected and manages to illustrate very arcane features of the C programming language.

I challenge anybody not familiar with C bit shifting to completely understand how the two void functions named get_bit and toggle_bit actually work.

void toggle_bit(char *array, int index) {

    array[index / 8] ^= 1 << (index % 8);

}

char get_bit(char *array, int index) {

    return 1 & (array[index / 8] >> (index % 8));

}

These functions are examples of the “simplicity” of C programming. While the syntax is compact the semantics of these functions are not. Describing what these two functions do would take several paragraphs of text.

 

As an avid Ada programmer I decided to implement a bit array in Ada and perform the same behaviors on the bit array.

The Ada program is slightly longer, sacrificing compactness for clarity.

-- Ada program to implement a bit array

with Ada.Text_IO; use Ada.Text_IO;

procedure Main is

   type bit is range 0 .. 1;

   type index is range 0 .. 57;

   type bit_array is array (index) of bit with

      Component_Size => 1;

   x   : bit_array := (others => 0);

   Idx : index     := 0;

begin

   for I in x'Range loop

      if I mod 2 = 0 then

         toggle_bit (x, I);

      end if;

   end loop;

   toggle_bit (x, 56);


   for I in x'Range loop

      Put_Line (I'Image & ":" & bit'Image (x (I)));

   end loop;

   Put_Line("Size of bit array is" & Integer'Image(X'Size) & " bits.");

   Put_Line("Length of array is" & Integer'Image(X'Length));

end Main;

 

The Ada programming language measures the size of data types in units of bits while the C program must convert bytes to bits in determining its size.

Compare the corresponding Ada and C code sections:

C:

#define SIZE (58) /* amount of bits */

#define ARRAY_SIZE(x) (x/8+(!!(x%8)))

. . .

char x[ARRAY_SIZE(SIZE)] = { 0 };

 

Ada:

   type bit is range 0 .. 1;

   type index is range 0 .. 57;

   type bit_array is array (index) of bit with

      Component_Size => 1;

. . .

x   : bit_array := (others => 0);

 

The Ada code defines an integral type named bit with 0 and 1 as the only valid values. The Ada code then defines an index range to be used in the array type. Knowing the index range prevents buffer overflows in other parts of the program.

The array type bit_array is declared. C provides no means to define array types, only array instances.

In the C example the array named x is defined as an array of type char, but we are not interested in values of type char. We are interested in the bit values within each char element. The size of the char array must be declared to be the number of char elements needed to store 58 bits. Each char element is 8 bits, therefore 8 char elements are needed to store 58 bits.

The corresponding Ada source code is somewhat more readable. A bit_array is an array of 58 elements indexed by the values 0 through 57. The size of each array component is 1, which in Ada terms is 1 bit.

The variable x in the C example is declared to be an array of 8 char data elements. All elements (and all 64 bits) are initialized to 0.

The variable x in the Ada example is declared to be an instance of bit_array, which is declared to be an array of 58 bits. Each element is initialized to 0. Only the 58 bits are initialized to 0.

The C function named toggle_bit is difficult to understand.

void toggle_bit(char *array, int index) {

    array[index / 8] ^= 1 << (index % 8);

}

 

The purpose of this function is to identify the bit specified by the index parameter and toggle the bit. If the bit is 1 then set it to zero. If the bit is 0 then set it to 1.

The Ada procedure named toggle_bit performs the same behavior with a somewhat more verbose, but also clearer syntax.

   procedure toggle_bit (arr : in out bit_array; Idx : index) is

   begin

      if arr (Idx) = 1 then

         arr (Idx) := 0;

      else

         arr (Idx) := 1;

      end if;

   end toggle_bit;

 

Note that the bits in the bit array are indexed with the same syntax used to index any other Ada array. No special syntax is needed. The compiler writes all the low level bit shifting for the programmer, eliminating the need for an explicit get_bit procedure as found in the C example. The Ada version clearly states toggle logic. If the current value of the bit indexed by Idx is 1 then assign 0 to that bit, otherwise assign 1 to that bit.

Also note the obscurity of the C syntax for passing an array to a function. The array is not actually passed to the function. The name of the array is passed as a pointer to the first element of the array, thus the parameter used to “pass” the array is a pointer to char rather than an array. A pointer to char may be a pointer to the first element of an array of char or it may be a pointer to a char which is not a member of an array of char. C requires the programmer to know whether or not the parameter points to an array. The C syntax also does not specify whether or not the actual parameter passed to this function may be modified by the function.

The Ada procedure specifies the parameter arr is an instance of bit_array. Furthermore, the passing mode “in out” specifies that the value of the array is used and modified by the procedure, specifying that the actual parameter passed to this procedure may be modified by the procedure.

Outputs:

The output of the C program is:

0: 1

1: 0

2: 1

3: 0

4: 1

5: 0

6: 1

7: 0

8: 1

9: 0

10: 1

11: 0

12: 1

13: 0

14: 1

15: 0

16: 1

17: 0

18: 1

19: 0

20: 1

21: 0

22: 1

23: 0

24: 1

25: 0

26: 1

27: 0

28: 1

29: 0

30: 1

31: 0

32: 1

33: 0

34: 1

35: 0

36: 1

37: 0

38: 1

39: 0

40: 1

41: 0

42: 1

43: 0

44: 1

45: 0

46: 1

47: 0

48: 1

49: 0

50: 1

51: 0

52: 1

53: 0

54: 1

55: 0

56: 0

57: 0

 

The output of the Ada program is:

 0: 1

 1: 0

 2: 1

 3: 0

 4: 1

 5: 0

 6: 1

 7: 0

 8: 1

 9: 0

 10: 1

 11: 0

 12: 1

 13: 0

 14: 1

 15: 0

 16: 1

 17: 0

 18: 1

 19: 0

 20: 1

 21: 0

 22: 1

 23: 0

 24: 1

 25: 0

 26: 1

 27: 0

 28: 1

 29: 0

 30: 1

 31: 0

 32: 1

 33: 0

 34: 1

 35: 0

 36: 1

 37: 0

 38: 1

 39: 0

 40: 1

 41: 0

 42: 1

 43: 0

 44: 1

 45: 0

 46: 1

 47: 0

 48: 1

 49: 0

 50: 1

 51: 0

 52: 1

 53: 0

 54: 1

 55: 0

 56: 0

 57: 0

Size of bit array is 64 bits.

Length of array is 58

 

  • 22 April 2023 at 19:27

Poor Quality C Programming Examples

 

C is hard enough without low quality programming examples

I recently read through some of the C programming examples from Sanfoundry. Some of the examples are well constructed while others are very poorly constructed.

One of the bad examples I read is found under the heading of Simple C Programs. The example purports to show how to count the number of vowels and consonants in an input sentence.

The source code for the example follows.

/*

 * C program to read a sentence and count the total number of vowels

 * and consonants in the sentence.

 */

#include <stdio.h>

 

void main()

{

    char sentence[80];

    int i, vowels = 0, consonants = 0, special = 0;

 

    printf("Enter a sentence \n");

    gets(sentence);

    for (i = 0; sentence[i] != '\0'; i++)

    {

        if ((sentence[i] == 'a' || sentence[i] == 'e' || sentence[i] ==

        'i' || sentence[i] == 'o' || sentence[i] == 'u') ||

        (sentence[i] == 'A' || sentence[i] == 'E' || sentence[i] ==

        'I' || sentence[i] == 'O' || sentence[i] == 'U'))

        {

            vowels = vowels + 1;

        }

        else

        {

            consonants = consonants + 1;

        }

        if (sentence[i] =='\t' ||sentence[i] =='\0' || sentence[i] ==' ')

        {

            special = special + 1;

        }

    }

    consonants = consonants - special;

    printf("No. of vowels in %s = %d\n", sentence, vowels);

    printf("No. of consonants in %s = %d\n", sentence, consonants);

}

 

This program does not actually identify a sentence. Instead it merely reads a single input line from stdin. The first conditional carefully identifies the values of the vowels and then assumes anything not a vowel is a consonant. A second conditional makes a weak attempt to find “special” characters that are not letters, but this conditional only looks for tabs, spaces and end of string null characters. It completely ignores punctuation and numeric digits. Sentences often contain punctuation and numeric digits, which are neither vowels nor consonants. The error shows in an inflated count of consonants when an input string contains punctuation and/or numeric digits.

The example program is poorly designed and does not fulfill the requirements expressed on the page C Program to Count the Number of Vowels and Consonants in a Sentence - Sanfoundry.

I wrote an Ada program to achieve the same stated goals. This program uses approximately the same number of lines of source code as the C program while avoiding the problem of miscounting consonants.

-- Ada program to read a line of text and count the number of vowels

-- and consonants in the text

 

with Ada.Text_IO; use Ada.Text_IO;

 

procedure Main is

   subtype Letter is Character with

        Static_Predicate => Letter in 'a' .. 'z' | 'A' .. 'Z';

   subtype Vowel is Character with

     Static_Predicate => Vowel in 'a' | 'e' | 'i' | 'o' | 'u' |

       'A' | 'E' | 'I' | 'O' | 'U';

 

   Line       : String (1 .. 80);

   vowels     : Natural := 0;

   consonants : Natural := 0;

   Length     : Natural;

begin

   Put_Line ("Enter a sentence:");

   Get_Line (Item => Line, Last => Length);

   for I in 1 .. Length loop

      if Line (I) in Letter then

         if Line (I) in Vowel then

            vowels := vowels + 1;

         else

            consonants := consonants + 1;

         end if;

      end if;

   end loop;

   Put_Line

     ("Number of vowels in " & Line (1 .. Length) & " is" & vowels'Image);

   Put_Line

     ("Number of consonants in " & Line (1 .. Length) & " is" &

      consonants'Image);

end Main;

 

The Ada program explicitly defines a subtype of Character containing only English letters. It also defines a subtype of Character defining only the vowels defined in the C program.

The first conditional in the Ada program filters out all characters that are not letters. Within that conditional block the current character is tested for being a vowel. If it is not a vowel then it can only be a consonant. Both the vowel count and the consonant count are correct because the program selected only letters and filtered out all non-letter characters.

C language philosophy

The C language expects the programmer to perform all error checking while only providing very primitive means of specifying the correct data conditions. Historically C has concentrated its design on execution speed at the expense of programmer effort.

Ada language philosophy

The Ada language provides syntax tools to define subtypes of a data type based upon either a range of values or set of values. The Ada example above defines two subtypes of the predefined type Character. One subtype defines the set of all lower case and upper case letters. The other subtype defines the set of lower case and upper case letters identified as vowels.

Each of these subtypes is expressed in a very compact manner in a single expression.

These subtypes express exactly what is a letter and what is a vowel.

Conclusion

The C program never specifies what is a letter. The result is a latent error in program logic which most beginning C students would be unlikely to identify. Eliminating this error would require either a laborious list of letters in C or a list of the numeric ranges representing lower case letters and upper case letters. The first option greatly obscures the meaning of the filtering by its complexity. The second option greatly obscures the meaning of the filtering by using the numeric representation of the letters in a compound conditional expression such as

If ((sentence[i] >= 65 && sentence[i] <= 90) || (sentence[i] >= 97 && sentence[i] <= 122))

The Ada equivalent is accomplished by defining the set of values constituting a letter

subtype Letter is Character with

        Static_Predicate => Letter in 'a' .. 'z' | 'A' .. 'Z';

 

Followed by a simple conditional

if Line (I) in Letter then

The Ada “in” operator returns True if Line (I) is a member of the set of values defined for Letter and False if Line (I) is not a member of the set of values define for Letter.

The set of letters is defined as all the characters in the range starting at ‘a’ and ending at ‘z’ and all the characters in the range starting at ‘A’ and ending at ‘Z’. While this set defines the same values as the C conditional example above, it does so in a very clear manner understandable by programmers of all levels of experience, without resorting to a table of values mapping characters to numeric representations.

The Ada program clearly specifies all the values needed to count vowels and consonants, thereby eliminating the latent defect present in the C program.

  • 5 April 2023 at 05:08

Comparing a simple Java Producer-Consumer example to an Ada producer-consumer example

Both Java and Ada provide built-in concurrency features.

The Java example below is taken from TutorialRide.com

Java Example

public class ProducerConsumer

{

      public static void main(String[] args)

      {

            Shop c = new Shop();

            Producer p1 = new Producer(c, 1);

            Consumer c1 = new Consumer(c, 1);

            p1.start();

            c1.start();

      }

}

class Shop

{

      private int materials;

      private boolean available = false;

      public synchronized int get()

      {

            while (available == false)

            {

                  try

                  {

                        wait();

                  }

                  catch (InterruptedException ie)

                  {

                  }

            }

            available = false;

            notifyAll();

            return materials;

      }

      public synchronized void put(int value)

      {

            while (available == true)

            {

                  try

                  {

                        wait();

                  }

                  catch (InterruptedException ie)

                  {

                        ie.printStackTrace();

                  }

            }

            materials = value;

            available = true;

            notifyAll();

      }

}

class Consumer extends Thread

{

      private Shop Shop;

      private int number;

      public Consumer(Shop c, int number)

      {

            Shop = c;

            this.number = number;

      }

      public void run()

      {

            int value = 0;

            for (int i = 0; i < 10; i++)

            {

                  value = Shop.get();

                  System.out.println("Consumed value " + this.number+ " got: " + value);

            }

      }

}

class Producer extends Thread

{

      private Shop Shop;

      private int number;

 

      public Producer(Shop c, int number)

      {

            Shop = c;

            this.number = number;

      }

      public void run()

      {

            for (int i = 0; i < 10; i++)

            {

                  Shop.put(i);

                  System.out.println("Produced value " + this.number+ " put: " + i);

                  try

                  {

                        sleep((int)(Math.random() * 100));

                  }

                  catch (InterruptedException ie)

                  {

                        ie.printStackTrace();

                  }

            }

      }

}

 

The Java example uses a single element buffer shared between the producer and the consumer. The shared buffer is implemented in the Shop class. The Shop class contains two private variables. The int variable materials will contain the data shared by the producer and the consumer. The boolean variable available is used to control the access to the variable materials so that the consumer can only read data when available is TRUE and the producer can only produce data when available is FALSE.

In the class Shop put method a while loop polls the available variable while the value of available is TRUE. Similarly the get method uses a while loop to poll the available variable while the value of available is FALSE. In both cases the wait() method causes the thread calling the synchronized method to suspend until the notifyAll() method awakens the suspended thread.

class Shop

{

      private int materials;

      private boolean available = false;

      public synchronized int get()

      {

            while (available == false)

            {

                  try

                  {

                        wait();

                  }

                  catch (InterruptedException ie)

                  {

                  }

            }

            available = false;

            notifyAll();

            return materials;

      }

      public synchronized void put(int value)

      {

            while (available == true)

            {

                  try

                  {

                        wait();

                  }

                  catch (InterruptedException ie)

                  {

                        ie.printStackTrace();

                  }

            }

            materials = value;

            available = true;

            notifyAll();

      }

}

 

The Java notifyAll() method awakens all waiting threads, both producers and consumers. The awakened thread checks the value of available. If the value of the variable available matches the loop’s terminating condition the method is completed, otherwise the method again suspends upon executing wait().

Java does not provide any policy concerning which thread awakened by the call to notifyAll() will run, thus the use of multiple producers and multiple consumers will produce non-deterministic execution of the multiple threads.

The output of the Java example above is:


Ada Example

The following Ada code closely resembles the Java code in its external behavior with the exception that the Ada code implements two producers and two consumers.

with Ada.Text_IO; use Ada.Text_IO;

 

procedure Main is

   protected buffer is

      entry Put (Item : in Integer);

      entry Get (Item : out Integer);

   private

      Num   : Integer;

      Empty : Boolean := True;

   end buffer;

 

   protected body buffer is

      entry Put (Item : in Integer) when Empty is

      begin

         Num   := Item;

         Empty := False;

      end Put;

 

      entry Get (Item : out Integer) when not Empty is

      begin

         Item  := Num;

         Empty := True;

      end Get;

   end buffer;

 

   task type producer (Id : Positive);

 

   task type consumer (Id : Positive);

 

   task body producer is

   begin

      for I in 0 .. 4 loop

         buffer.Put (I);

         Put_Line ("Producer" & Id'Image & " produced" & I'Image);

         delay 0.0001;

      end loop;

   end producer;

 

   task body consumer is

      Value : Integer;

   begin

      for I in 1 .. 5 loop

         buffer.Get (Value);

         Put_Line ("Consumer" & Id'Image & " consumed" & Value'Image);

         delay 0.0001;

      end loop;

   end consumer;

   P1 : producer (1);

   P2 : producer (2);

   C1 : consumer (1);

   C2 : consumer (2);

begin

   null;

end Main;

 

Ada allows subprograms, equivalent to Java methods, to be defined within the scope of other subprograms. Similarly, Ada protected objects and tasks may be defined within a subprogram. Ada provides two kinds of subprograms; functions which always return a value and procedures which never return a value, however parameter values can be passed out of a procedure to the scope in which the procedure is called.

The entry point to an Ada program is always a procedure with no parameters. The procedure may be named whatever the programmer wants to name it. It need not be called “main”. In this case I did name it “main” for ease of understanding by Java programmers.

Ada provides protected objects and protected types as passive units of concurrency. In this case the protected object is named “buffer”.

protected buffer is

      entry Put (Item : in Integer);

      entry Get (Item : out Integer);

   private

      Num   : Integer;

      Empty : Boolean := True;

   end buffer;

 

   protected body buffer is

      entry Put (Item : in Integer) when Empty is

      begin

         Num   := Item;

         Empty := False;

      end Put;

 

      entry Get (Item : out Integer) when not Empty is

      begin

         Item  := Num;

         Empty := True;

      end Get;

   end buffer;

 

Unlike Java, Ada clearly separates the interface specification of a protected object from its implementation. In this case the lines highlighted in blue are the protected object interface. Protected objects are allowed to have three kinds of methods used to interface with the object. The three kinds of methods are entries, procedure and functions. Entries provide read/write access to the protected object with an associated boundary condition. Procedures provide unconditional read/write access to the protected object. Function provide read-only access to the protected object. Entries and procedures implicitly implement an exclusive read/write lock on the protected object. Tasks waiting for the entry boundary condition to open are placed in a suspension queue and are allowed access to the protected object in accordance with the specified queuing policy. The default queuing policy is First-In-First-Out. Functions implicitly enforce a shared read lock on the protected object allowing multiple tasks to simultaneously call functions without encountering any race conditions.

The private part of the protected object interface specification contains the data items within the protected object. Those data items are only accessible through the entries, procedures or functions defined for the protected object. In this case the variable Num is an Integer. It will hold the value assigned by the producer and read by the consumer. The variable Empty is a Boolean initialized to True. The Empty variable is used to control whether a producer or a consumer is allowed to execute the put or get entries.

The implementation of the protected object entries is found in the protected body, highlighted above in red.

The Put entry takes an IN parameter of type Integer and executes only when Empty is True. The Put entry assigns the value in the parameter Item to the protected object’s Num variable. It then assigns false to the protected object’s Empty variable.

The Get entry takes an OUT parameter of type Integer and executes only when Empty is False. The Get entry assigns the value in Num to the parameter Item, which is passed out to the calling task. The Empty variable is then assigned True.

All the locking and queuing activities of the entries are written by the compiler and are not left as an exercise for the programmer.

The implementation of the two task types also separates the interface specification from the implementation.

   task type producer (Id : Positive);

 

   task type consumer (Id : Positive);

 

   task body producer is

   begin

      for I in 0 .. 4 loop

         buffer.Put (I);

         Put_Line ("Producer" & Id'Image & " produced" & I'Image);

         delay 0.0001;

      end loop;

   end producer;

 

   task body consumer is

      Value : Integer;

   begin

      for I in 1 .. 5 loop

         buffer.Get (Value);

         Put_Line ("Consumer" & Id'Image & " consumed" & Value'Image);

         delay 0.0001;

      end loop;

   end consumer;

 

Again, the task type interface specifications are highlighted in blue and the implementations are highlighted in red.

In this example each task type has a discriminant value named Id, of the subtype Positive. Ada does not have constructors like Java does. In this case the discriminant serves the purpose of a constructor, allowing a parameter within the task to be set when an instance of the task type is created.

The task body for the producer task type simply executes a “for” loop iterating through the range of values specified as 0 .. 4. Each iteration the producer calls buffer.Put(I), writing its current value of “I” to the protected object named buffer. The producer task then outputs a statement saying The producer with the Id value assigned to it through the discriminant, produced whatever value I is at this iteration. The task then delays (similar to sleep in Java) for 0.0001 seconds. Similarly, the task body for the consumer task type declares a local variable named Value of type Integer and then iterates through a “for” loop five times. Each time through the “for” loop the task calls buffer.Get(Value). Value is assigned the value read from the buffer. The task then outputs its consumer Id and the value it read, followed by delaying for 0.0001 seconds.

   P1 : producer (1);

   P2 : producer (2);

   C1 : consumer (1);

   C2 : consumer (2);

begin

   null;

end Main;

 

The rest of procedure “main” declares two producer objects and two consumer objects. The four tasks start running as soon as the program reaches the “begin” in the “main” procedure. The executable part of the “main” procedure does nothing except wait for the four tasks to complete. The “null;” statement notifies the compiler that the main procedure does nothing intentionally. In fact the main procedure simply creates and starts the tasks and then does nothing.

The output of the Ada example is:

Producer 1 produced 0

Consumer 1 consumed 0

Producer 2 produced 0

Consumer 2 consumed 0

Producer 1 produced 1

Consumer 1 consumed 1

Producer 2 produced 1

Consumer 2 consumed 1

Producer 1 produced 2

Consumer 1 consumed 2

Producer 2 produced 2

Consumer 2 consumed 2

Producer 1 produced 3

Consumer 1 consumed 3

Producer 2 produced 3

Consumer 2 consumed 3

Producer 1 produced 4

Consumer 1 consumed 4

Producer 2 produced 4

Consumer 2 consumed 4

 

Conclusion

While the Java example produces similar output to the Ada example, when one accounts for only one producer and one consumer, the outputs would look more chaotic in the Java example if two or more producers and two or more consumers were used. The difference is cause by the fact that tasks suspended on an Ada entry are queued in FIFO order while thread suspended due to the Java wait() method then activated through the Java notifyAll() method are activated in no particular order.

The Ada example is far less complex to write than is the Java example. A simple source line count shows the Java example to use 95 lines without using any blank lines while the Ada example uses 54 lines including many blank lines. The Java example adds extra lines as part of the class definitions for multiple classes, including the definition of constructors which Ada does not have. Furthermore the while loops needed to poll the wait() and notifyAll() activities in both the Put and Get methods of class Shop have no corresponding source lines in the Ada example because all the suspension, queuing and activation activities of the Ada program are written by the compiler and not by the programmer.

While the outputs of the two examples are superficially similar, they are not the same. The ordered output of the Ada program cannot be reliably reproduced using Java.

  • 30 January 2022 at 03:48

Create a Reversed Copy of a String

 A recent question on Stack Overflow concerned creation of a C program to create and print a reverse copy of a string. Thus, for example, the string “hello” would be copied to another string and would contain “olleh”.

C versions

While this is clearly a beginner level problem, the difficulties encountered by the person submitting the question illustrate how learning C can be a struggle.

The source code posted by the author of the question is:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define ARR_SIZE 50

int main()
{
 char string[ARR_SIZE];
 printf("Enter char array!\n");
 fgets(string, ARR_SIZE, stdin);

 string[strlen(string) - 1] = '\0';
 int length = (strlen(string) - 1);
 int length2 = (strlen(string) - 1);

 printf("%s\t%d\n", string, length);

 for (int i = 0; i <= length; i++)
 {
 printf("INDEX = %d CHAR = %c\n", i, string[i]);
 }
 
 printf("%d", length2);
 char copy[ARR_SIZE];
 
 for (int i = 0; i <= length2; i++)
 {
 copy[i] = string[length];
 length--;
 }

 


 printf("\n%s", copy);
}

 

There are a number of beginner mistakes in this code example. One answer attempted to correct the most obvious errors with the following result:

#include <stdio.h>
#include <string.h>
// remove unneeded headers

#define ARR_SIZE 50

int main(void)
{
  char string[ARR_SIZE];
  printf("Enter char array!\n");
  fgets(string, ARR_SIZE, stdin);

  string[strlen(string) - 1] = '\0';
  // remove the -1 on the string length calculation, the NUL terminator is not
  // included in strlen's return value
  int length = strlen(string);
  // no sense in calling strlen twice
  int length2 = length;

  // fixed `length` now prints the correct length
  printf("%s\t%d\n", string, length);

  // change from <= to <. The array indices where the characters live are
  // [0, length-1].
  for (int i = 0; i < length; i++)
  {
    printf("INDEX = %d CHAR = %c\n", i, string[i]);
  }
 
  // fixed `length2` now prints the correct length
  printf("%d", length2);
  char copy[ARR_SIZE];
 
  for (int i = 0; i < length2; i++)
  {
    // last character in `string` lives at the `length`-1 index
    copy[i] = string[length-1];
    length--;
  }

  // `length2` is the index after the last char in `copy`, this needs
  // to be NUL terminated.
  copy[length2] = '\0';

  // prints the reversed string
  printf("\n%s", copy);
}

 

These suggestions do produce a working program, but it has some weaknesses inherent in the C language handling of strings. The biggest weakness is the effort needed to deal with determining how long the string is. C strings are terminated with a null character. The example above uses the strlen function to find the position of the null character.

A second answer tried to offer a more compact solution, although it does omit the necessary header files. The author of this example suggested that a proper solution should define and use a function. Note that this function is highly compact, uncommented, and extremely terse. In other words it contains all the elements commonly associated with C programming.

char *copyreverse(char *dest, const char *src)
{
  size_t len = strlen(src);
  const char *end = src + len - !!len;
  char *wrk = dest;
  while(len--)
    *wrk++ = *end--;
  *wrk = 0;
  return dest;
}
int main()
{
  char dest[10];
  char *src = "hello";
  printf("`%s` reversed `%s`\n", src, copyreverse(dest, src));
}

 

In this case we see a function named copyreverse and a function named main in the same file. In C this places the two functions in the same file scope, allowing copyreverse to be visible to the implementation of main. C does not allow a function to be implemented within the scope of another function.

This terse solution has typical C problems. The copyreverse function takes two parameters, a pointer to character named dest and a pointer to character named src. Only the programmer know that these pointers should point to the start of an array of characters and not a simple character. There is no check in the program to ensure that the dest parameter points to an array large enough to hold all the characters contained in the array pointed to by the parameter src. This failure to check sizes opens the opportunity for a buffer overflow.

Another part of the simplification of this program is its lack of ability to read the string from standard input, thus making the program unnecessarily compact.

Ada versions

Next I offer a couple of solutions created in the Ada programming language.

The first Ada example creates a function using the Ada.Strings.Unbounded package which provides an append procedure for unbounded strings. Use of unbounded strings prevents any buffer overflow problems.

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;

procedure Main is
  Result : Unbounded_String := Null_Unbounded_String;
  Input : String (1 .. 80);
  Length : Natural;
begin
  Put ("Enter a string: ");
  Get_Line (Item => Input, Last => Length);
  Put_Line (Input (1 .. Length));
  for C of reverse Input (1 .. Length) loop
    Append (Result, C);
  end loop;
  Put_Line (To_String (Result));
end Main;

 

The Get_Line procedure reads the string from standard input and places it into a string named Input. The Get_Line function passes out the modified string as well as a parameter indicating the index of the last character of the useful information in the string. The Put_Line procedure simply writes the input data to standard output. The data to be output is in the slice of the Input variable which was filled by Put_Line.  The for loop scans through the slice of Input in reverse order, appending each value to the Unbounded_String named Result. When the loop finishes Result will contain the data in Input (1 .. Length), but in reverse order.

The final Put_Line procedure call simply converts the Unbounded_String Result to a corresponding String value and outputs that String value.

A second Ada example avoids the use of the package Ada.Strings.Unbounded and does the string copy directly to another Ada string.

with Ada.Text_IO; use Ada.Text_IO;

procedure main_2 is
   function reverse_str (src : in String) return String is
     Result : String (src'Range);
     r_idx : Positive := Result'First;
   begin
     for value of reverse src loop
       Result (r_idx) := value;
       r_idx := r_idx + 1;
     end loop;
   return Result;
  end reverse_str;

  Input : String (1 .. 80);
  Length : Natural;
begin
  Put ("enter a string: ");
  Get_Line (Input, Length);
  Put_Line (Input (1 .. Length));
  Put_Line (reverse_str (Input (1 .. Length)));
end main_2;

 

The function named reverse_str is defined within the procedure main_2. Reverse_str takes one String parameter named src and returns a String. Reverse_str creates a String variable named Result. Result is created to have the same index range as src, and therefore has exactly the same size as src, eliminating any possibility of overflow. The variable r_idx is an instance of the subtype Positive and is initialized to the first index value of Result. The for loop iterates through src in reverse assigning each value of src to the element in Result indexed by the variable r_idx. The variable r_idx is then incremented and the loop continues until all elements of src have been processed. Result is then returned by the function reverse_str.

The body of main_2 prompts for a string to be input from standard input, reads up to 80 characters from standard input and places the data in the variable Input. The value of the string Input (1 .. Length) is output and on the next output line the value of the reverse of Input (1 .. Length) is output.

While not as terse as the second C solution the second Ada version is highly readable and does not require the programmer to provide a destination string parameter of possibly dubious size as is required in the C program. The Ada version also does not require the src string to be scanned to determine its size followed by an obscure expression seen in the C example to deal with a possible empty string. Instead the Ada range syntax defines a range where the first index is greater than the last index to be an empty range. For instance, if the users passes an empty string to the Ada program the notation Input (1 .. Length) resolves to Input ( 1 .. 0), which is an empty string. The for loop then does not iterate through the values because the first index exceeds the last index and Result, which is created with the expression Result : String := (src’Range) is defined as an empty string. Result is returned without being modified in the for loop and no buffer overflow occurs.

The Ada versions are both simpler because of the differences between Ada strings and C strings and also because Ada arrays, of which strings are an example, can easily be sliced.

The Ada versions both avoid the possibility of array overflows while the second C version does not.

The Ada versions avoid any pointer manipulation syntax while the second C example performs all array element processing using explicit pointer manipulations.

 

  • 4 November 2021 at 04:24

Tasking and Ada Rendezvous

 

Tasking and the Ada Rendezvous

Multiprocessing has been a part of the Ada programming language since the language was first standardized in 1983. The original version of Ada provided active concurrency objects called tasks. Today tasks are commonly implement by Ada compilers as operating system threads, but the Ada language does not depend on operating system threading to implement tasks.

The execution of an Ada program consists of the execution of one or more tasksEach task represents a separate thread of control that proceeds independently and concurrently between the points where it interacts with other tasks. The various forms of task interaction are described in this clause, and include:

·         the activation and termination of a task;

·         a call on a protected subprogram of a protected object, providing exclusive read-write access, or concurrent read-only access to shared data;

·         a call on an entry, either of another task, allowing for synchronous communication with that task, or of a protected object, allowing for asynchronous communication with one or more other tasks using that same protected object;

·         a timed operation, including a simple delay statement, a timed entry call or accept, or a timed asynchronous select statement (see next item);

·         an asynchronous transfer of control as part of an asynchronous select statement, where a task stops what it is doing and begins execution at a different point in response to the completion of an entry call or the expiration of a delay;

·         an abort statement, allowing one task to cause the termination of another task.

Tasks can be implemented as a task type, allowing multiple identical instances of a task to be created, or as single task entities defined as members of an anonymous task type.

Definition of a task type includes declaration of all interfaces to the task type. Task interfaces, or calling points, are called task entries. Each task entry allow another task to call an instance of the task type, possibly passing data to or from the task type instance.

Rendezvous

When one task calls an entry of another task the two task synchronize to allow data to be passed from one task to the other. If task A calls an entry named set_id declared in task B with the purpose of passing an id value from task A to task B the two tasks synchronize to allow direct communication between the tasks. Task A calls the Task B entry. Task B accepts the entry call. Synchronization happens when both task are ready to process the entry. If task A calls the entry before task B accepts the entry call then task A suspends until task B is ready. Similarly, if task B accepts the entry before any task calls the entry then task B suspends until the entry is called. An entry is allowed to transfer data to or from the task calling the entry.

Table 1 Task Type Example

task type Counter is
   entry Set_Num (Val : in Integer);
end Counter;

 

The task type in the example above is named Counter. Task type Counter has one entry. A task type may have multiple entries or it may have no entries.

The single entry in this example is named Set_Num. Set_Num requires a single parameter of type Integer. The “in” mode designation causes the value to be passed from the calling task to the called instance of Counter.

Each task or task type declaration must be completed with a task body. The task or task type declaration contains the declaration of the name of the task or task type as well as the declaration of all entries associated with the task or task type. The task body contains the logic implemented by the task. The task body must have the same name as its corresponding task or task type declaration.

Table 2 Task Body Example

task body Counter is
   Seed : Generator;
   Num  : Integer;
begin
   Reset (Seed);

   accept Set_Num (Val : in Integer) do
      Num := Val;
   end Set_Num;
 

   delay Duration (Random (Seed) * 0.01);

   Put_Line (Num'Image);

end Counter;

 

The structure of a task body is very similar to the structure of an Ada procedure. Local variables are declared between the “is” reserved word and the “begin” reserved word. The “accept” statement performs the task’s interaction with the entry call. In this case the parameter “Val” contains the value passed from the task calling the entry. That value is copied into the local variable “Num”. The accept operation ends when the code reaches “end Set_Num”. Upon completion of the accept operation the synchronization of this task with its calling task completes and both tasks resume asynchronous execution.

Calling a Task Entry

The following example demonstrates how one task calls the entry of another task.

Table 3 Calling a Task Entry

with Ada.Text_IO;               use Ada.Text_IO;

with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random;

procedure Main is

   task type Counter is
      entry Set_Num (Val : in Integer);
   end Counter; 

   task body Counter is
      Seed : Generator;
      Num  : Integer;

   begin

      Reset (Seed);

      accept Set_Num (Val : in Integer) do
         Num := Val;
      end Set_Num; 

      delay Duration (Random (Seed) * 0.01);

      Put_Line (Num'Image);

   end Counter;

   subtype Index is Integer range 0 .. 9;

   Counters : array (Index) of Counter;

begin

   for I in Counters'Range loop
        Counters (I).Set_Num (I);
   end loop;

end Main;

 

The purpose of this simple program is to use tasks to print the digits 0 through 9 in random order. The task type counter is designed to receive a single integer value through its Set_Num entry, delay execution for a random time (in this case the time is a random fraction of milliseconds between 9 milliseconds and 1 millisecond) and then output the value of its local variable named Num. Upon completing the output operation the instance of Counter completes.

An array of Counter objects is created. The name of that array is Counters. The array is indexed by the values 0 through 9, which causes the array to have 10 instances of task type Counter. Those tasks start automatically when program execution reaches the “begin” statement of the Main procedure.

Looking back at the task body for Counter we see that the first action of the task is to call the Reset procedure for random generator, setting the random number seed to a unique value based upon the current computer clock. After resetting the random number seed the task calls the accept operator for the Set_Num entry. The task then suspends until its Set_Num entry is called.

The “for” loop in the Main procedure iterates through the array of Counter tasks, calling each one in order and passing its array index value as the number it will output. Keep in mind that the Main procedure executes in a task separate from the ten Counter tasks.

Another example of the Ada Rendezvous is shown below. This example defines an Ada package implementing parallel addition of an array of integer values. The example is implemented in three files.

Table 4 Parallel_Addition.ads

package Parallel_Addition is

   type Data_Array is array(Integer range <>) of Integer;

   type Data_Access is access all Data_Array;

   function Sum(Item : in not null Data_Access) return Integer;

end Parallel_Addition;

 

This package specification declares an unconstrained array type named Data_Array. Data_Array arrays are indexed by some set of values within the valid set of Integer values. Each element contains an Integer. An unconstrained array allows the user to pass an array of any size permitted by the computer hardware.

The type Data_Access is a reference to Data_Array.

The function Sum takes a parameter of type Data_Access so that very large arrays created on the heap may be passed to the function. The function returns a single Integer which is the sum of all the elements in the array passed to the function.

Table 5 Parallel_Addition.adb

package body Parallel_Addition is

   ---------
   -- Sum --
   --------- 

   function Sum (Item : in not null Data_Access) return Integer is

      task type Adder is

         entry Set (Min : Integer; Max : Integer);

         entry Report (Value : out Integer);

      end Adder;

 

      task body Adder is

         Total : Integer := 0;
         First : Integer;
         Last  : Integer;

      begin

         accept Set (Min : Integer; Max : Integer) do
            First := Min;
            Last  := Max;
         end Set;

         for I in First .. Last loop
            Total := Total + Item (I);
         end loop;

         accept Report (Value : out Integer) do
            Value := Total;
         end Report;

      end Adder;

      A1  : Adder;
      A2  : Adder;
      R1  : Integer;
      R2  : Integer;
      Mid : constant Integer := (Item'Length / 2) + Item'First;

   begin

      A1.Set (Min => Item'First, Max => Mid);
      A2.Set (Min => Mid + 1, Max => Item'Last);

      A1.Report (R1);
      A2.Report (R2);

      return R1 + R2;

   end Sum;

end Parallel_Addition;

 

The package body for Parallel_Addition contains the implementation of the Sum function declared in the Parallel_Addition package specification.

Within the Sum function we find the declaration of a task type name Adder. Instances of Adder will perform the parallel addition. The task type declaration for Adder includes two entries named Set and Report. The Set entry sets the minimum and maximum index values to be used by the task. The Report entry passes the total calculate by the task back to the entry’s calling task.

Two instances of Adder are created. One is named A1 and the other is named A2. Similarly two integer variables intended to hold the results of the additions are created. Those variables are named R1 and R2.

The Sum function calculated a middle value for the index values in the array passed to it as Item.

The Adder tasks begin execution when program execution reaches the “begin” of the Sum function.

The Sum function calls the Set entry for Adder A1 passing it the index values for the first index of Item and the Mid value. Similarly, the set entry for Adder A2 is passed the index value of Mid + 1 and the last index value of Item.

The Sum function immediately calls the Adder A1 Report entry to receive the value for R1, followed by calling the Adder A2 report entry to receive the value for R2. The Sum function will suspend until A1 accepts its Report entry. It will then suspend again if necessary until A2 accepts its Repot entry.

Sum returns the sum of R1 and R2.

Table 6 Parallel_Addition_Test.adb

with Parallel_Addition; use Parallel_Addition;
with Ada.Text_IO;       use Ada.Text_IO;
with Ada.Calendar;      use Ada.Calendar; 

procedure Parallel_Addition_Test is

   The_Data : Data_Access := new Data_Array (1 .. Integer'Last);

   Start    : Time;
   Stop     : Time;

   The_Sum  : Integer; 

begin

   The_Data.all := (others => 1);
   Start        := Clock;
   The_Sum      := Sum (The_Data);
   Stop         := Clock;
   Put_Line ("The sum is: " & Integer'Image (The_Sum));
   Put_Line
     ("Addition elapsed time is " &
      Duration'Image (Stop - Start) &
        " seconds.");
   Put_Line
     ("Time per addition operation is " &
          Float'Image(Float(Stop - Start) / Float(The_Data'Length)) &
        " seconds.");

end Parallel_Addition_Test;

 

The program Parallel Addition Test creates an array containing 2,147,483,647 elements. The object of this test is to calculate an average time for each addition operation using the Parallel_Addition package. A large array provides a statistically solid number for the average time.

In this case all the elements of the array are initialized to 1 so that the addition will not result in an integer overflow. This also gives a good check of the addition, since the correct result is 2,147,483,647.

The program captures the clock time in the variable Start, calls the Sum function, then captures the time in the variable Stop. The difference between the two times is the approximate time used to sum the array.

The addition result along with the elapsed time and the average time per addition operation are reported.

The result of an example run is:

Table 7 Example Parallel_Addition_Test Output

The sum is:  2147483647
Addition elapsed time is  4.918378900 seconds.
Time per addition operation is  2.29030E-09 seconds.

 

  • 24 October 2020 at 03:37

Is Ada truly verbose?

 

People who prefer programming language syntax derived from the C language have often argued that the Ada language is verbose because it uses entire words rather than punctuation.

Meaning

C Syntax

Ada Syntax

Begin a block

{

begin, loop

End a block

}

end, end if, end loop, end subprogram name, end task name, end protected object name, end record

Declare a function taking a single integer parameter and returning an integer value

int foo (int x);

function foo (x : integer) return integer;

Declare a 10 element integer array indexed with the values 0 through 9

int a [10];

a : array (0..9) of integer;

Write a “for” loop to sum all the elements in array a declared above.

for (int I = 0; I < 10; i++)

{

   sum += a [i];

}

for I in a’range loop

   sum := sum + a (i);

end loop;

 

Of course, not everything in Ada takes more lines of code or more typing than the equivalent program in C or C++. For instance, the following C++ program is taken from the CodesCracker website. Its purpose is to convert a user input of a hexadecimal value into the corresponding decimal value.

/* C++ Program - Hexadecimal to Decimal Conversion */            

#include<iostream.h>

#include<stdlib.h>

#include<conio.h>

#include<math.h>

unsigned long convtodecnum(char hex[]);

void main()

{

    clrscr();

    unsigned long decnum;

    char hex[9];     // 8 characters for 32-bit Hexadecimal Number and one for ' '   

    cout<<" Enter 32-bit Hexadecimal Number : ";

    cin>>hex;

    decnum = convtodecnum(hex);

    cout<<"Value in Decimal Number is "<<decnum<<"\n";

    getch();

}

unsigned long convtodecnum(char hex[])

{

    char *hexstr;

    int length = 0;

    const int base = 16;     // Base of Hexadecimal Number

    unsigned long decnum = 0;

    int i;

    // Now Find the length of Hexadecimal Number

    for (hexstr = hex; *hexstr != '\0'; hexstr++)

    {

       length++;

    }

    // Now Find Hexadecimal Number

    hexstr = hex;

    for (i = 0; *hexstr != '\0' && i < length; i++, hexstr++)

    {

       // Compare *hexstr with ASCII values

       if (*hexstr >= 48 && *hexstr <= 57)   // is *hexstr Between 0-9

       {

           decnum += (((int)(*hexstr)) - 48) * pow(base, length - i - 1);

       }

       else if ((*hexstr >= 65 && *hexstr <= 70))   // is *hexstr Between A-F

       {

           decnum += (((int)(*hexstr)) - 55) * pow(base, length - i - 1);

       }

       else if (*hexstr >= 97 && *hexstr <= 102)   // is *hexstr Between a-f

       {

           decnum += (((int)(*hexstr)) - 87) * pow(base, length - i - 1);

       }

       else

       {

           cout<<"Invalid Hexadecimal Number \n";

       }

    }

    return decnum;

}

 

An Ada program handling the same input and results in the same output is:

-- Convert Hexadecimal string to decimal value

with Ada.Text_IO; use Ada.Text_IO;

procedure Main is

   type Unsigned_Long is mod 2**32;

   Decimal : Unsigned_Long;

begin

   Put ("Enter a 32 bit hexadecimal number: ");

   Decimal := Unsigned_Long'Value ("16#" & Get_Line & "#");

   Put_Line (Decimal'Image);

exception

   when Constraint_Error =>

      Put_Line ("Input value is not a valid 32 bit hexadecimal number.");

end Main;

 

Ada has the built-in capability to handle literal numbers represented by base 2 through base 16. The base 16 value FF is represented as 16#FF#. Ada accepts either upper or lower case representation of the hexadecimal values A through F. The program simply appends the 16# to the entered hexadecimal digits and then appends # to the end of the string. The integer’value built in attribute converts a string representation of an integer to its corresponding integer value.

The message created in response to the exception Constraint_Error is raised if the user enters a value more than 2^32 or if one of the digits is not in the range of 0 through 9 or A through F.

In this case the Ada program appears to be far less verbose than the C++ program.

  • 22 October 2020 at 04:16

Barber Shop Problem Implemented using Ada

In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are customers, resting when there are none, and doing so in an orderly manner.
The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in computer science.

Problem Description:

Simulate a barber shop with one barber, one barber chair and a waiting room with N chairs for waiting customers. When the barber finishes cutting the hair of one customer he dismisses the customer and goes to the waiting room to see if another customer is waiting. If the customer is waiting the barber cuts the customer's hair. If no customers are waiting the barber goes to sleep on the barber chair. The next customer to arrive must awaken the barber.
If all waiting room chairs are full when a new customer arrives that arriving customer will leave the barbershop. If the barbershop is closed all arriving customers will leave the barbershop. The barber will cut the hair of all customers already in a chair when the barbershop closes.

An Ada solution

The design approach taken below began with identifying the active and passive elements in the simulation. The active elements include the barber and the customers. The barbershop is a passive element. It contains chairs in a waiting room, a single barber chair, a count of waiting customers, and a state of Open or Closed.

The Ada language provides tasks as active elements of concurrency and protected objects as passive elements of concurrency. Operations on a passive object are always called by one or more tasks, and execute within the execution schedule of the task making the call.

The actions of the barber are to sleep when there are no customers, serve a customer in one of the chairs, and close the shop when directed.

The actions of the customers are to take an available seat or leave if no seat is available. Customers also leave if the barbershop is closed.

This solution provides a task for the barber, a task for all the customers, and a protected object named Barber_Shop.


The Barber_Shop package specification declares two tasks.
package Barber_Shop is
   task Barber is
      entry Close_Shop;
   end Barber;

   task Customers;
end Barber_Shop;

The Barber task simulates the behaviors of the barber. The barber task closes the barbershop when the entry Close_Shop is called by the main procedure.
The package body for the Barber_Shop package defines a protected object named Shop, which handles whether or not the shop is open along with whether or not customers have arrived.
with Ada.Text_IO;               use Ada.Text_IO;
with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random;

package body Barber_Shop is
   Seed : Generator;

   type Num_Seats is range 0 .. 3;
   protected Shop is
      function Is_Open return Boolean;
      function Shop_Empty return Boolean;
      entry Take_Seat;
      entry Serve_Customer;
      procedure Close_Shop;
   private
      Shop_Open      : Boolean   := True;
      Occupied_Seats : Num_Seats := 0;
   end Shop;

   protected body Shop is
      function Is_Open return Boolean is
      begin
         return Shop_Open;
      end Is_Open;

      function Shop_Empty return Boolean is
      begin
         return Occupied_Seats = 0;
      end Shop_Empty;

      entry Take_Seat when Shop_Open and then Occupied_Seats < Num_Seats'Last
      is
      begin
         Occupied_Seats := Occupied_Seats + 1;
      end Take_Seat;

      entry Serve_Customer when Occupied_Seats > 0 is
      begin
         Occupied_Seats := Occupied_Seats - 1;
      end Serve_Customer;

      procedure Close_Shop is
      begin
         Shop_Open := False;
      end Close_Shop;

   end Shop;

   ------------
   -- Barber --
   ------------

   task body Barber is
      procedure Cut_Hair is
      begin
         Put_Line ("Luigi is serving a customer.");
         delay Duration (Random (Seed) * 3.0);
      end Cut_Hair;

   begin
      loop
         select
            accept Close_Shop;
            Put_Line ("Luigi is closing the shop");
            Shop.Close_Shop;
         else
            if Shop.Is_Open then
               if Shop.Shop_Empty then
                  Put_Line ("Luigi is sleeping.");
               end if;
               Shop.Serve_Customer;
               Cut_Hair;
            else
               while not Shop.Shop_Empty loop
                  Shop.Serve_Customer;
                  Cut_Hair;
               end loop;
               exit;
            end if;
         end select;
      end loop;
   end Barber;

   ---------------
   -- Customers --
   ---------------

   task body Customers is
   begin
      loop
         delay Duration (Random (Seed) * 6.0);
         select
            Shop.Take_Seat;
            Put_Line ("A customer took a seat");
         else
            if Shop.Is_Open then
               Put_Line ("A customer left because all the seats were taken.");
            else
               Put_Line ("A customer left because the shop is closed.");
               exit;
            end if;
         end select;
      end loop;
   end Customers;
begin
   Reset (Seed);
end Barber_Shop;

The main procedure is very simple. It starts the simulation by withing the Barber_Shop package, delays for 60 seconds, and then calls Barber.Close_Shop;

with Barber_Shop; use Barber_Shop;
procedure Main is
begin
   delay 60.0;
   Barber.Close_Shop;
end Main;
  • 28 May 2020 at 20:48

Producer-Consumer Patterns


Producer-Consumer Patterns
The Producer-Consumer pattern is classically defined as two threads or tasks coordinating their behavior through a shared fixed length buffer. The producer writes data to the buffer. The consumer reads data from the buffer. The producer must stop writing to the buffer while the buffer is full. The consumer must stop reading from the buffer while the buffer is empty.

The size of the buffer is fixed and does not grow during the life of the program. The minimum size of the buffer must be one element. The maximum size of the buffer is limited only by memory constraints on the program.

The classic Producer-Consumer design uses one producer and one consumer.

Classic Producer-Consumer Pattern


In this pattern the producer and consumer have no direct interaction. Each interacts with the fixed length buffer, allowing the two tasks to execute asynchronously until the buffer is full or empty. It is important that the producer cannot write to the buffer while the consumer is reading from the buffer to avoid race conditions. Similarly, the consumer cannot read from the buffer while the producer is writing to the buffer. Coordination of writing and reading can be implemented through a simple binary semaphore when there is one producer and one consumer.

Coordination becomes more difficult when other configurations are used. Additional configurations include
  • Single Producer with Multiple Consumers
  • Multiple Producers with Single Consumer
  • Multiple Producers with Multiple Consumers




Single Producer Multiple Consumer Pattern


Multiple Consumer Single Producer Pattern





Multiple Producer Multiple Consumer Pattern



The coordination problem becomes most complex when dealing with multiple producers writing to a single buffer and multiple consumers reading from the same single buffer.

Producer-Consumer Implemented Using Ada

Ada tasks are similar to threads in many other languages. Tasks are active objects. Ada protected objects are passive elements of concurrency. Protected objects are executed by tasks when a task calls one of the protected object's methods.



Ada Tasks

Tasks work independently unless they are suspended while waiting for a lock or in an entry queue. Tasks communicate synchronously with each other through task entries. They communicate asynchronously with each other through protected objects.

Task Entries

Task entries implement the Rendezvous model of communication. A task may declare an entry, which is a synchronization point during which data may be passed directly between tasks. A task may call another task's entry. The task declaring the entry can accept the entry call at the point in its logic best suited for handling the entry call.

A task calling the entry of another task will suspend until the called task reaches the accept statement for that entry. At this point the two tasks are synchronized to allow data to be passed from one task to the other. If the called task reaches its accept statement before another task calls the corresponding entry the called task will suspend, waiting for a calling task. Following completion of the task entry both tasks will continue executing independently of each other.

Select statements

Ada provides a method for conditionally accepting entry calls. The select clause provides the ability to handle one of many entries, or to poll an entry so that a rendezvous can be handled without incurring a protracted suspension of the task. An example from the Ada Language Reference Manual is



task body Server is
   Current_Work_Item : Work_Item;
begin
   loop
      select
         accept Next_Work_Item(WI : in Work_Item) do
            Current_Work_Item := WI;
         end;
         Process_Work_Item(Current_Work_Item);
      or
         accept Shut_Down;
         exit; -- Premature shut down requested
      or
         terminate; -- Normal shutdown at end of scope
      end select;
   end loop;
end Server;

Ada Protected Objects
Ada protected objects are protected against race conditions and deadlock. Protected objects are designed to be shared by multiple tasks. Protected objects implement sophisticated versions of Hoare monitors. Protected objects handle their own locking mechanisms, making their design highly Object Oriented. The calling tasks never directly manipulate locks.

Protected Methods

There are three kinds of protected methods:
  • Procedures
  • Entries
  • Functions

Protected Procedures

Protected Procedures are allowed to read from or write to the protected object. Protected Procedures acquire exclusive unconditional access to the Protected Object through a read-write lock.

Protected Entries

Protected Entries are also allowed to read from or write to the protected object. Like Protected Procedures, Protected Entries acquire an exclusive read-write lock. The difference between a protected Procedure and a Protected Entry is the conditional nature of a Protected Entry call. Each Protected Entry is defined with a guard condition which must evaluate to True or False. When the guard condition is False execution of the Protected Entry is blocked and the calling task suspends until the guard condition evaluates to True. Each suspended task is placed in an Entry Queue so that calls to a Protected Entry are executed in the proper order. There are two common queuing policies; First In First Out (FIFO) and Priority. The default queuing policy is FIFO, so that the queued tasks execute the Protected Entry in the temporal order in which the Protected Entry was called.

Protected Functions

Protected functions are only allowed to read data from the Protected Object. They are not allowed to modify the Protected Object in any way. Protected functions acquire a shared read-only lock on the Protected Object. This lock prevents Protected Procedures and Protected Entries from executing while the lock is asserted, but permit any number of simultaneous function calls to execute on the Protected Object. Protected objects cannot execute while a Protected Entry or Protected Procedure read-write lock is asserted.

All these locking and queuing operations are performed implicitly. The programmer does not create any explicit lock or queue manipulation calls.

Ada Producer-Consumer Example

The following example uses Ada tasks, task entries, Ada Protected Objects and Protected Object entries.



with Ada.Strings.Bounded;
generic
   Buf_Size : Positive;
package Universal_PC is
   package Label_Strings is new Ada.Strings.Bounded.Generic_Bounded_Length(30);
   use Label_Strings;

   task type Producer is
      entry Set_Id(Label : Label_Strings.Bounded_String);
      entry Done;
   end Producer;


   task type Consumer is
      entry Set_Id(Label : Label_Strings.Bounded_String);
      entry Stop;
   end Consumer;


end Universal_PC;


The package specification defines a bounded string type named Label_Strings with a maximum length of 30 characters. It also defines two task types; Producer and Consumer. The Producer task type has two task entries; Set_Id, which passes in an instance of Bounded_String and Done which passes no information. Done only acts to synchronize the Producer and a calling task upon an event. In this case the event is when the Producer is done. The Consumer task type has two task entries; Set_Id, which passes an instance of Bounded_String to Consumer, and Stop, which commands the Consumer task instance to terminate.



with Ada.Text_IO.Bounded_IO;

package body Universal_PC is
   package Label_IO is new Ada.Text_IO.Bounded_IO (Label_Strings);
   use Label_IO;

   ------------
   -- Buffer --
   ------------

   type Internal_Buf is array (Natural range 0 .. Buf_Size - 1) of
       Label_Strings.Bounded_String;

   protected Buffer is
      entry Read (Item : out Label_Strings.Bounded_String);
      entry Write (Item : in Label_Strings.Bounded_String);
   private
      Count       : Natural := 0;
      Buf         : Internal_Buf;
      Write_Index : Natural := 0;
      Read_Index  : Natural := 0;
   end Buffer;

   protected body Buffer is
      entry Read (Item : out Label_Strings.Bounded_String)
         when Count > 0 is
      begin
         Item       := Buf (Read_Index);
         Count      := Count - 1;
         Read_Index := (Read_Index + 1) mod Buf_Size;
      end Read;

      entry Write (Item : in Label_Strings.Bounded_String)
         when Count < Buf_Size is
      begin
         Buf (Write_Index) := Item;
         Count             := Count + 1;
         Write_Index       := (Write_Index + 1) mod Buf_Size;
      end Write;

   end Buffer;

   --------------
   -- Producer --
   --------------

   task body Producer is
      Id : Label_Strings.Bounded_String;
   begin
      accept Set_Id (Label : Label_Strings.Bounded_String) do
         Id := Label;
      end Set_Id;
      for I in 1 .. 10 loop
         Buffer.Write (Id & ' ' & To_Bounded_String (I'Image));
         delay 0.01;
      end loop;
      accept Done;
   end Producer;

   --------------
   -- Consumer --
   --------------

   task body Consumer is
      Id : Label_Strings.Bounded_String;
      Value : Label_Strings.Bounded_String;
   begin
      accept Set_Id (Label : Label_Strings.Bounded_String) do
         Id := Label;
      end Set_Id;
      loop
         select
            accept Stop;
            exit;
         else
            select
               Buffer.Read (Value);
               Put_Line (Id & ':' & ' ' & Value);
            or
               delay 0.01;
            end select;
         end select;
      end loop;
   end Consumer;

end Universal_PC;


The package body provides the implementation of the tasks declared in the package specification. It also provides the implementation for the Protected Object named Buffer.
The Protected Object specification declares two Protected Entries for Buffer. The Write entry passes Bounded_String into Buffer and the Read entry passes a Bounded_String out of Buffer. The private part of the Protected Object specification defines the data contained in Buffer. Four data items are defined. Count maintains a count of the number of data elements currently in use in Buf array of Buffer. Buf is an array of Bounded_Strings. Write_Index contains the index for the next Write entry call. Read_Index contains the index for the next Read entry call.

The Protected Body contains the implementation of the two entry calls. The Read entry call has a condition stating that the call can only execute when Count > 0. This condition enforces the requirement that one cannot read from an empty Producer-Consumer queue. The Write entry call has a condition stating that the call can only execute when Count < Buf_Size. This condition enforces the requirement that one cannot write to a full Producer-Consumer queue. All the Protected Entry locking and queuing is written automatically by the compiler. The programmer is only concerned with writing the entry behaviors not associated with locking and queuing.

The package body also contains the implementation of the task bodies for Producer and Consumer.
Each Producer starts by accepting the Set_Id task entry, allowing the programmer to assign an ID label unique to each Producer task. The Producer task then iterates through the numbers in the range 1 through 10. Each iteration calls Buffer.Write, passing a bounded string containing the task ID concatenated with the iteration value. After writing all 10 values to Buffer the task accepts the Done entry then terminates.

Each Consumer task starts by accepting the Set_Id entry, just like the Producer tasks. The Consumer then enters a simple loop that iterates through a set of select calls polling the Stop task entry then polling the Buffer.Read protected entry. The loop exits when the Stop task entry is handled.



with universal_pc;

procedure Universal_pc_test is
   package Pc is new Universal_Pc(10);
   use PC;

   P1 : Producer;
   P2 : Producer;
   C1 : Consumer;
   C2 : Consumer;
begin
   P1.Set_Id(Label_Strings.to_Bounded_String("Producer 1"));
   P2.Set_Id(Label_Strings.To_Bounded_String("Producer 2"));
   C1.Set_Id(Label_Strings.To_Bounded_String("Consumer 1"));
   C2.Set_Id(Label_Strings.To_Bounded_String("Consumer 2"));
   P1.Done;
   P2.Done;
   C1.Stop;
   C2.Stop;
end Universal_pc_test;


This procedure is the “main” procedure or program entry point for the program. Every program entry point is also implicitly a task.

The generic package Universal_PC is instantiated with a Buf_Size of 10. Two producers, P1 and P2, are declared. Two Consumers, C1 and C2, are declared. The four tasks start as soon as execution of the program reaches the “begin” in the procedure Universal_pc_test. Initially all four tasks are suspended at their Set_Id task accept calls. The four task entries are called, passing appropriate labels to the four tasks.

P1.Done and P2.Done are called immediately. The calling task (Universal_pc_test) is suspended untils P1 and then P2 accept their Done entries. At that point both producers have completed. C1.Stop and C2.Stop are then called to terminate the two Consumer tasks.

The output of this program is

Consumer 1: Producer 1 1
Consumer 1: Producer 2 1
Consumer 1: Producer 2 2
Consumer 2: Producer 1 2
Consumer 1: Producer 1 3
Consumer 2: Producer 2 3
Consumer 1: Producer 2 4
Consumer 2: Producer 1 4
Consumer 1: Producer 2 5
Consumer 2: Producer 1 5
Consumer 1: Producer 2 6
Consumer 2: Producer 1 6
Consumer 2: Producer 2 7
Consumer 1: Producer 1 7
Consumer 2: Producer 1 8
Consumer 1: Producer 2 8
Consumer 2: Producer 2 9
Consumer 1: Producer 1 9
Consumer 2: Producer 1 10
Consumer 1: Producer 2 10



This solution will work with any Buf_Size greater than 0 and any number of producers and consumers.

  • 1 May 2020 at 14:29

Producer-Consumer Determinism


The Producer-Consumer pattern is a common pattern used in concurrent programming. In this model one task writes values to a fixed length buffer and another task reads values from the fixed length buffer.
There are many variations on the Producer-Consumer pattern, mostly dealing with various numbers of producers and various numbers of consumers.
This article will use a simple Producer-Consumer pattern with a single producer and a single consumer. 

Determinism

The Producer-Consumer pattern has some simple limitations. The Consumer task cannot read data from an empty buffer and the Producer task cannot write data to a full buffer. These limitations might lead the programmer to assume that the Producer and Consumer will spend their time alternately reading and writing the buffer. First the Producer will write a value then the Consumer will read a value. While the general idea is correct, the actual viewed results may be a bit confusing.

Non-Deterministic Example

with Ada.Text_IO; use Ada.Text_IO;


procedure Main is

   Max_Iter : constant Positive := 40;

   Buf_Size : constant          := 6;

   subtype Index is Integer range 0 .. Buf_Size - 1;

   type Buf_Array is array (Index) of Integer;


   protected Buffer is

      entry Write (Item : in Integer);

      entry Read (Item : out Integer);

   private

      Buf       : Buf_Array;

      Read_Idx  : Index   := 0;

      Write_Idx : Index   := 0;

      Count     : Natural := 0;

   end Buffer;


   protected body Buffer is

      entry Write (Item : in Integer) when Count < Buf_Size is

      begin

         Buf (Write_Idx) := Item;

         Write_Idx       := (Write_Idx + 1) mod Buf_Size;

         Count           := Count + 1;

         Put_Line ("Producer wrote" & Item'Image);

      end Write;


      entry Read (Item : out Integer) when Count > 0 is

      begin

         Item     := Buf (Read_Idx);

         Read_Idx := (Read_Idx + 1) mod Buf_Size;

         Count    := Count - 1;

         Put_Line ("Consumer read" & Item'Image);

      end Read;

   end Buffer;


   task Producer;

   task Consumer;


   task body Producer is

   begin

      for I in 1 .. Max_Iter loop

         Buffer.Write (I);

      end loop;

      Put_Line ("       Producer finished");

   end Producer;


   task body Consumer is

      Num : Integer;

   begin

      for I in 1 .. Max_Iter loop

         Buffer.Read (Num);

      end loop;

      Put_Line ("       Consumer finished");

   end Consumer;

begin

   null;

end Main;

This example provides a shared buffer of 6 data elements. The Producer writes to the buffer when it is not full and the Consumer reads from the buffer when it is not empty. A typical execution of this program results in the following output:

Producer wrote 1

Consumer read 1

Producer wrote 2

Consumer read 2

Producer wrote 3

Consumer read 3

Producer wrote 4

Producer wrote 5

Producer wrote 6

Producer wrote 7

Producer wrote 8

Producer wrote 9

Consumer read 4

Producer wrote 10

Consumer read 5

Consumer read 6

Consumer read 7

Consumer read 8

Consumer read 9

Consumer read 10

Producer wrote 11

Consumer read 11

Producer wrote 12

Producer wrote 13

Producer wrote 14

Producer wrote 15

Producer wrote 16

Producer wrote 17

Consumer read 12

Producer wrote 18

Consumer read 13

Consumer read 14

Consumer read 15

Consumer read 16

Consumer read 17

Consumer read 18

Producer wrote 19

Consumer read 19

Producer wrote 20

Consumer read 20

Producer wrote 21

Consumer read 21

Producer wrote 22

Consumer read 22

Producer wrote 23

Producer wrote 24

Producer wrote 25

Producer wrote 26

Producer wrote 27

Producer wrote 28

Consumer read 23

Producer wrote 29

Consumer read 24

Consumer read 25

Consumer read 26

Consumer read 27

Consumer read 28

Consumer read 29

Producer wrote 30

Consumer read 30

Producer wrote 31

Producer wrote 32

Producer wrote 33

Producer wrote 34

Producer wrote 35

Producer wrote 36

Consumer read 31

Producer wrote 37

Consumer read 32

Consumer read 33

Consumer read 34

Consumer read 35

Consumer read 36

Consumer read 37

Producer wrote 38

Consumer read 38

Producer wrote 39

Producer wrote 40

       Producer finished

Consumer read 39

Consumer read 40

       Consumer finished

As you can see, while the Producer and Consumer sometimes alternate in their execution, there are also periods during which either the Producer or the Consumer dominates, creating a series of actions from one task or the other. In other words, the execution of the two tasks is not deterministic. The non-deterministic nature shown is due to the operating system choosing when to schedule each task.

Deterministic Examples

How can the programmer create deterministic behavior given the whims of the operating system?
One way is to reduce the buffer size to 1 element.

with Ada.Text_IO; use Ada.Text_IO;


procedure Main is

   Max_Iter : constant Positive := 40;

   Buf_Size : constant          := 1;

   subtype Index is Integer range 0 .. Buf_Size - 1;

   type Buf_Array is array (Index) of Integer;


   protected Buffer is

      entry Write (Item : in Integer);

      entry Read (Item : out Integer);

   private

      Buf       : Buf_Array;

      Read_Idx  : Index   := 0;

      Write_Idx : Index   := 0;

      Count     : Natural := 0;

   end Buffer;


   protected body Buffer is

      entry Write (Item : in Integer) when Count < Buf_Size is

      begin

         Buf (Write_Idx) := Item;

         Write_Idx       := (Write_Idx + 1) mod Buf_Size;

         Count           := Count + 1;

         Put_Line ("Producer wrote" & Item'Image);

      end Write;


      entry Read (Item : out Integer) when Count > 0 is

      begin

         Item     := Buf (Read_Idx);

         Read_Idx := (Read_Idx + 1) mod Buf_Size;

         Count    := Count - 1;

         Put_Line ("Consumer read" & Item'Image);

      end Read;

   end Buffer;


   task Producer;

   task Consumer;


   task body Producer is

   begin

      for I in 1 .. Max_Iter loop

         Buffer.Write (I);

      end loop;

      Put_Line ("       Producer finished");

   end Producer;


   task body Consumer is

      Num : Integer;

   begin

      for I in 1 .. Max_Iter loop

         Buffer.Read (Num);

      end loop;

      Put_Line ("       Consumer finished");

   end Consumer;

begin

   null;

end Main;

Now the entry guard conditions on the Protected Object named Buffer force the Producer and Consumer tasks to take turns in a deterministic manner.

Producer wrote 1
Consumer read 1
Producer wrote 2
Consumer read 2
Producer wrote 3
Consumer read 3
Producer wrote 4
Consumer read 4
Producer wrote 5
Consumer read 5
Producer wrote 6
Consumer read 6
Producer wrote 7
Consumer read 7
Producer wrote 8
Consumer read 8
Producer wrote 9
Consumer read 9
Producer wrote 10
Consumer read 10
Producer wrote 11
Consumer read 11
Producer wrote 12
Consumer read 12
Producer wrote 13
Consumer read 13
Producer wrote 14
Consumer read 14
Producer wrote 15
Consumer read 15
Producer wrote 16
Consumer read 16
Producer wrote 17
Consumer read 17
Producer wrote 18
Consumer read 18
Producer wrote 19
Consumer read 19
Producer wrote 20
Consumer read 20
Producer wrote 21
Consumer read 21
Producer wrote 22
Consumer read 22
Producer wrote 23
Consumer read 23
Producer wrote 24
Consumer read 24
Producer wrote 25
Consumer read 25
Producer wrote 26
Consumer read 26
Producer wrote 27
Consumer read 27
Producer wrote 28
Consumer read 28
Producer wrote 29
Consumer read 29
Producer wrote 30
Consumer read 30
Producer wrote 31
Consumer read 31
Producer wrote 32
Consumer read 32
Producer wrote 33
Consumer read 33
Producer wrote 34
Consumer read 34
Producer wrote 35
Consumer read 35
Producer wrote 36
Consumer read 36
Producer wrote 37
Consumer read 37
Producer wrote 38
Consumer read 38
Producer wrote 39
Consumer read 39
Producer wrote 40
       Producer finished
Consumer read 40
       Consumer finished

Using the Ada programming language this seems to be task coordination done the hard way. The easy way to achieve this same behavior is to use the Ada Rendezvous facility to communicate between the Producer and the Consumer.
The Rendezvous facility provides very direct synchronization between tasks. The task calling a task entry must suspend until the called task handles the task entry. The called task must suspend at the point of handling an entry until another task calls the entry.
The same Producer-Consumer problem implemented using a task entry is shown below.

with Ada.Text_IO; use Ada.Text_IO;


procedure PC_Rendezvous is

   Max_Iter : constant := 40;


   task Producer;

   task Consumer is

      entry Write (Item : in Integer);

   end Consumer;


   task body Producer is

   begin

      for I in 1 .. Max_Iter loop

         Put_Line ("Producer writing" & I'Image);

         Consumer.Write (I);

      end loop;

      Put_Line("      Producer finished");

   end Producer;


   task body Consumer is

      Num : Integer;

   begin

      for I in 1 .. Max_Iter loop

         accept Write (Item : in Integer) do

            Num := Item;

         end Write;

         Put_Line ("Consumer read" & Num'Image);

      end loop;

      Put_Line("      Consumer finished");

   end Consumer;

begin

   null;

end PC_Rendezvous;

The output of this program is:

Producer writing 1

Consumer read 1

Producer writing 2

Consumer read 2

Producer writing 3

Consumer read 3

Producer writing 4

Consumer read 4

Producer writing 5

Consumer read 5

Producer writing 6

Consumer read 6

Producer writing 7

Consumer read 7

Producer writing 8

Consumer read 8

Producer writing 9

Consumer read 9

Producer writing 10

Consumer read 10

Producer writing 11

Consumer read 11

Producer writing 12

Consumer read 12

Producer writing 13

Consumer read 13

Producer writing 14

Consumer read 14

Producer writing 15

Consumer read 15

Producer writing 16

Consumer read 16

Producer writing 17

Consumer read 17

Producer writing 18

Consumer read 18

Producer writing 19

Consumer read 19

Producer writing 20

Consumer read 20

Producer writing 21

Consumer read 21

Producer writing 22

Consumer read 22

Producer writing 23

Consumer read 23

Producer writing 24

Consumer read 24

Producer writing 25

Consumer read 25

Producer writing 26

Consumer read 26

Producer writing 27

Consumer read 27

Producer writing 28

Consumer read 28

Producer writing 29

Consumer read 29

Producer writing 30

Consumer read 30

Producer writing 31

Consumer read 31

Producer writing 32

Consumer read 32

Producer writing 33

Consumer read 33

Producer writing 34

Consumer read 34

Producer writing 35

Consumer read 35

Producer writing 36

Consumer read 36

Producer writing 37

Consumer read 37

Producer writing 38

Consumer read 38

Producer writing 39

Consumer read 39

Producer writing 40

Consumer read 40

      Consumer finished

      Producer finished

Task deterministic behavior is achieve by forcing synchronization between the two tasks.

  • 17 April 2020 at 17:09

Ada Concurrency - Avoiding Race Conditions


Race conditions

Concurrent tasks are commonly scheduled by the operating system. The result is that the programmer cannot predict the order of execution of tasks. For example, if two tasks increment a shared variable the result may not be what was expected.

Num : Integer := 100; -- shared variable
Procedure Increment is
Begin
   Num := Num + 1;
End Increment;

If two tasks simultaneously call the Increment procedure the following interaction is possible

Num := 100 + 1;

Each task reads the initial value of Num as 100, then adds one to the value and stores 101 into the variable Num. The trouble we see is the Increment function has been executed twice but the value stored in Num is only increased by 1 from the original value.
The race condition happens when two or more tasks perform overlapping writes to the same variable.
The following program illustrates this problem.

with Ada.Text_IO; use Ada.Text_IO;

procedure non_deterministic is
   Num : Integer := 0;
  
   procedure Increment is
   begin
      Num := Num + 1;
   end Increment;
  
   task type Adder;
  
   task body Adder is
   begin
      for I in 1..100_000 loop
         Increment;
      end loop;
   end Adder;
  
begin
   declare
      A1, A2 : Adder;
   begin
      null;
   end;
   Put_Line(Num'Image);
end non_deterministic;

The shared variable Num is initialized to 0. Two tasks are created. Each task calls Increment 100,000 times. If there are no race conditions the value of Num after both tasks complete should be 200,000. Instead successive executions of the program produce unexpected results:

196996
112584
124100
94783

Avoiding race conditions

The 1995 version of the Ada language added Protected Objects to the language. Ada protected objects are protected against race conditions and deadlocks.
A protected object is a passive element of concurrency while a task is an active element of concurrency. Protected objects are allowed to have three kinds of operations; procedures, entries, and functions. Protected procedures are allowed to read and write data in the protected object. Each protected object is granted an exclusive read/write lock on the protected object so that no other protected operation can be performed while the procedure is executing. Protected entries are similar to a protected procedure with the only difference that the protected entry has a guard condition which must be satisfied. If the guard condition evaluates to TRUE the calling task is allowed to execute the entry. While the guard condition evaluates to FALSE all calling tasks are suspended in an entry queue for that entry, waiting to execute when the guard condition evaluates to TRUE. Protected entries acquire a read/write lock just like protected procedures. Protected functions acquire a shared read-only lock. Protected entries are not allowed to modify the value or state of the protected object. They can only return values.
The previous example can be implemented using a protected object as shown below.

with Ada.Text_IO; use Ada.Text_IO;

procedure deterministic is
   protected Num is
      procedure Increment;
      function report return Integer;
   private
      Value : Integer := 0;
   end Num;

   protected body Num is
      procedure Increment is
      begin
         Value := Value + 1;
      end Increment;

      function report return Integer is
      begin
         return Value;
      end report;
   end Num;

   task type Adder;

   task body Adder is
   begin
      for I in 1 .. 100_000 loop
         Num.Increment;
      end loop;
   end Adder;

begin
   declare
      A1, A2 : Adder;
   begin
      null;
   end;
   Put_Line (Integer'Image (Num.report));
end deterministic;

The value output by this program is always

200000

Interleaving task access to a shared object

The problem of non-deterministic behavior is compounded when tasks must interleave their behaviors. Consider a problem with two bank accounts and two tasks. Each task transfers money from one account to the other.

with Ada.Text_IO; use Ada.Text_IO;

procedure banking is
   protected type Account is
      procedure Deposit(Amt : Positive);
      procedure Withdraw(Amt : Positive);
      function Report return Integer;
   private
      Balance : Integer := 0;
   end Account;
  
   protected body Account is
      procedure Deposit (Amt : Positive) is
      begin
         Balance := Balance + Amt;
      end Deposit;
     
      procedure Withdraw(Amt : Positive) is
      begin
         Balance := Balance - Amt;
      end Withdraw;
     
      function Report return Integer is
      begin
         return Balance;
      end Report;
   end Account;
  
   type Acct_Idx is (Joe, Bob);
  
   Accounts : array(Acct_Idx) of Account;
  
   procedure Print (Label : String) is
   begin
      New_Line;
      Put_Line(Label);
      for I in Accounts'Range loop
         Put_Line(I'Image & " balance:" &
                    Integer'Image(Accounts(I).Report));
      end loop;
   end Print;
  
  
   task type Transfer (Amt : Positive; From : Acct_Idx; To : Acct_Idx);
  
   task body Transfer is
   begin
      for I in 1..100_000 loop
         Accounts(From).Withdraw(Amt);
         Accounts(To).Deposit(Amt);
      end loop;
   end Transfer;
  
begin
   Accounts(Joe).Deposit(200_000);
   Accounts(Bob).Deposit(300_000);
  
   Print("Beginning balances:");
  
   declare
      T1 : Transfer(Amt => 2, From => Joe, To => Bob);
      T2 : Transfer(Amt => 1, From => Bob, To => Joe);
   begin
      null;
   end;
  
   print("Ending balances:");
  
end banking;

The output of this program is:

Beginning balances:
JOE balance: 200000
BOB balance: 300000

Ending balances:
JOE balance: 100000
BOB balance: 400000

If there had been any deadlock the program would have frozen at some point in its execution. Deadlocks will occur when each of the two tasks above holds a lock on a protected object and tries to simultaneously obtain a lock on the other object. Neither task can make any progress because each is waiting for the other task to release its lock.
As you can see from the example above, Ada protected objects manage locks in a manner which prevents deadlocks.

  • 28 January 2020 at 21:16

Parallel summation of a large array without shared data locks


The traditional producer/consumer pattern employs a shared buffer between the producer and the consumer.  Many producer/consumer problems are simply sequential problems with the overhead of multiple tasks and a shared buffer.
Parallel operations, on the other hand, are more naturally concurrent without the locking overhead of a shared buffer. Instead non-overlapping data elements of a collection such as an array are assigned to two or more tasks, and identical tasks process their subsets of the collection without need of locking the collection.

 If the parallel task is to sum all the elements in the array then task 1 in the diagram above will sum the elements in the first half of the array while task 2 sums the elements in the second half of the array. Task 1 and task 2 then simply report their subtotals to the parent task which adds the two values and returns the final total.
The following source code is an Ada package for parallel addition along with a procedure to test the package.

package Parallel_Addition is

   type Data_Array is array(Integer range <>) of Integer;

   type Data_Access is access all Data_Array;

   function Sum(Item : in not null Data_Access) return Integer;

end Parallel_Addition;


The package specification above defines an array type that can be used by the Sum function. The Sum function declares a parameter of the type Data_Accesss so that the function can handle arrays created either on the stack or on the heap.

package body Parallel_Addition is


   ---------

   -- Sum --

   ---------


   function Sum (Item : in not null Data_Access) return Integer is

      task type Adder is

         entry Set (Min : Integer; Max : Integer);

         entry Report (Value : out Integer);

      end Adder;


      task body Adder is

         Total : Integer := 0;

         First : Integer;

         Last  : Integer;

      begin

         accept Set (Min : Integer; Max : Integer) do

            First := Min;

            Last  := Max;

         end Set;

         for I in First .. Last loop

            Total := Total + Item (I);

         end loop;

         accept Report (Value : out Integer) do

            Value := Total;

         end Report;

      end Adder;

      A1  : Adder;

      A2  : Adder;

      R1  : Integer;

      R2  : Integer;

      Mid : constant Integer := (Item'Length / 2) + Item'First;

   begin

      A1.Set (Min => Item'First, Max => Mid);

      A2.Set (Min => Mid + 1, Max => Item'Last);

      A1.Report (R1);

      A2.Report (R2);

      return R1 + R2;

   end Sum;

end Parallel_Addition;


The package body for Parallel_Addition simply implements the Sum function. The Sum function defines a task type named Adder. That task type has two entries. The Set entry receives the minimum and maximum index values to be processed. The Report entry passes the locally calculated subtotal back to the Sum function. Each instance of Adder sums the values in the index range from Min to Max in the array passed as the Sum formal parameter Item, then passes the local sum back through the Report entry.
Two instances of Adder are created as well as two variables to contain results, one result for each Adder task. The variable Mid calculates the middle index value of the array Item.
Adder tasks A1 and A2 suspend at their Set entry until their Set entry is called. The then concurrently process the array slices indicated by their Min and Max values. They then suspend until their Report entry is called.
The Sum function simply calls the two Set entries and then calls the two Report entries. Finally Sum returns the sum of R1 and R2.
The test procedure for the Parallel_Addition package is:

with Parallel_Addition; use Parallel_Addition;

with Ada.Text_IO;       use Ada.Text_IO;

with Ada.Calendar;      use Ada.Calendar;


procedure Parallel_Addition_Test is

   The_Data : Data_Access := new Data_Array (1 .. Integer'Last);

   Start    : Time;

   Stop     : Time;

   The_Sum  : Integer;


begin

   The_Data.all := (others => 1);

   Start        := Clock;

   The_Sum      := Sum (The_Data);

   Stop         := Clock;

   Put_Line ("The sum is: " & Integer'Image (The_Sum));

   Put_Line

     ("Addition elapsed time is " &

      Duration'Image (Stop - Start) &

        " seconds.");

   Put_Line

     ("Time per addition operation is " &

        Float'Image(Float(Stop - Start) / Float(The_Data'Length)) &

        " seconds.");

end Parallel_Addition_Test;


The variable The_Data is an instance of Data_Access which accesses an array containing Integer’Last data elements. The variables Start and Stop are used to capture the time required to calculate the sum of all values in the array.
All the values of the array accessed by the variable The_Data are initialized to 1 to ensure that the resulting sum does not exhibit integer overflow. The variables Start and Stop record the time just before summing the data and just after summing the data. The difference in the two time values is the approximate elapsed time to calculate the sum. The average time per addition operation is simply the elapsed time divided by the number of data elements processed.
An output of this program, run on a Windows 10 computer, is:

The sum is:  2147483647

Addition elapsed time is  5.661118000 seconds.

Time per addition operation is  2.63616E-09 seconds.

The sum is also the number of array elements processed. This large array was used to produce a statistically significant timing sample.

  • 16 September 2019 at 05:55
❌
❌