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:
// 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 classGender {MALE, FEMALE};
structHuman
{
Gender m_gender;
Human(Gender g) : m_gender{g}
{}
virtual ~Human() = default;
};
structMan : public Human
{
Man() : Human{Gender::MALE}
{}
};
structWoman : public Human
{
Woman() : Human(Gender::FEMALE)
{}
};
voidhuman_func(const Human & h)
{
//...
}
voidman_func(const Man & m)
{
//...
}
voidwoman_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.
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.
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
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.
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';
("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
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.
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 (InterruptedExceptionie)
{
}
}
available = false;
notifyAll();
return materials;
}
public synchronized void put(int value)
{
while (available == true)
{
try
{
wait();
}
catch (InterruptedExceptionie)
{
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 (inti = 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 (inti = 0; i < 10; i++)
{
Shop.put(i);
System.out.println("Produced value " + this.number+ " put: " + i);
try
{
sleep((int)(Math.random() * 100));
}
catch (InterruptedExceptionie)
{
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 (InterruptedExceptionie)
{
}
}
available = false;
notifyAll();
return materials;
}
public synchronized void put(int value)
{
while (available == true)
{
try
{
wait();
}
catch (InterruptedExceptionie)
{
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.
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.
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.
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:
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 50intmain(void){charstring[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 valueintlength = strlen(string);// no sense in calling strlen twiceintlength2 = length;// fixed `length` now prints the correct lengthprintf("%s\t%d\n", string, length);// change from <= to <. The array indices where the characters live are// [0, length-1].for(inti = 0; i < length; i++){printf("INDEX = %d CHAR = %c\n", i, string[i]);}// fixed `length2` now prints the correct lengthprintf("%d", length2);charcopy[ARR_SIZE];for(int i = 0; i < length2; i++){// last character in `string` lives at the `length`-1 indexcopy[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 stringprintf("\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.
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;procedureMainisResult : Unbounded_String := Null_Unbounded_String;Input : String (1 .. 80);Length : Natural;beginPut ("Enter a string: ");Get_Line (Item => Input, Last => Length);Put_Line (Input (1 .. Length));for C of reverse Input (1 .. Length) loopAppend (Result, C);end loop;Put_Line (To_String (Result));endMain;
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;proceduremain_2isfunctionreverse_str (src : in String) return String isResult : String (src'Range);r_idx : Positive := Result'First;beginfor value of reverse src loopResult (r_idx) := value;r_idx := r_idx + 1;end loop;return Result;endreverse_str;Input : String (1 .. 80);Length : Natural;beginPut ("enter a string: ");Get_Line (Input, Length);Put_Line (Input (1 .. Length));Put_Line (reverse_str (Input (1 .. Length)));endmain_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.
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 tasks. Each
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;
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 is4.918378900 seconds. Time per addition operation is2.29030E-09 seconds.
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
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.
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;
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.
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.
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.
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.
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
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));
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 is5.661118000 seconds.
Time per addition operation
is2.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.
The stack Abstract Data Type is one of the simplest data
types to create and understand. There are fundamentally two kinds of stack
types.
·bounded stacks which have a pre-determined
capacity
·unbounded stacks which can grow to the limits of
computer memory.
Every stack implementation has some common subprograms.
·Is_Empty – This function returns true if the
stack is empty and false if it is not empty
·Size – A function returning number of elements
currently contained by the stack
·Top – A function returning the top element of a
stack that is not empty
·Push – Push a data element onto the stack
·Pop – A procedure that pops the top element off
the stack, passing the popped element out as a parameter
·Clear – A procedure that empties the stack
·Display – A procedure that displays the current
contents of the stack
A bounded stack may also have the function Is_Full, which
returns true if the stack is full and returns false if it is not full. Notice
that Is_Empty is not simply the inverse of Is_Full. A bounded stack with a
capacity of 10 elements may contain 0 elements, in which case it is empty, or
it may contain some number of elements from 1 through 9, in which case it is
neither empty nor full, or it may contain 10 elements, in which case it is
full.
Unbounded Stack
Unbounded stacks are commonly implemented as specialized
linked lists. Every Push operation results in the dynamic allocation of a new item
onto the stack. Every Pop operation results in one item from the stack being
freed back to the program heap.
The following implementation of an unbounded stack is
defined in an Ada generic package, allowing instances of the unbounded stack to
be created containing any data type.
Ada does provide a pre-defined doubly linked list package as part of its standard container library, but this example re-invents a simple singly linked list to give a complete example of how the unbounded stack can be implemented.
The package specification defines the API for the stack
abstract data type:
generic
type Element_Type is private;
with function Image (Item : in
Element_Type) return String;
package Unbounded_Stack
is
type Stack is tagged private;
function Is_Empty (S : in Stack) return
Boolean;
function Size (S : in Stack) return
Natural;
function Top (S : in Stack) return
Element_Type with
Pre => not S.Is_Empty;
procedure Push (S : in out Stack; Value :
in Element_Type) with
Post => S.Size = S'Old.Size + 1;
procedure Pop (S : in out Stack; Value :
out Element_Type) with
Pre=> not S.Is_Empty,
Post => S.Size = S'Old.Size - 1;
procedure Clear (S : in out Stack) with
Post => S.Is_Empty;
procedure Display (S : Stack);
private
type Cell;
type Cell_Access is access Cell;
type Cell is record
Value : Element_Type;
Next: Cell_Access;
end record;
type Stack is tagged record
Head: Cell_Access := null;
Count : Natural:= 0;
end record;
end Unbounded_Stack;
The package specification defines two generic parameters
which must be specified when an instance of the package is created. The first
generic parameter is the data type that the stack will contain. The second
generic parameter is a function taking an instance of the stack element type
and returning a string representation of the value of that data type.
Several of the functions and procedures have preconditions
and/or post-conditions associated with them. These pre and post conditions
specify the requirements of those functions and procedures.
Function or Procedure Name
Condition
Description
Top
Pre => not S.Is_Empty
This precondition requires the stack to not be empty before calling
the Top function.
Push
Post => S.Size = S'Old.Size + 1
Upon completion of this procedure the size of the stack must increase
by 1.
Pop
Pre=> not S.Is_Empty,
Post => S.Size = S'Old.Size - 1
This procedure cannot be called when the stack is empty. Upon
completion of this procedure the size of the stack must decrease by 1.
Clear
Post => S.Is_Empty
Upon completion of this procedure the stack will be empty.
The private part of the package specification defines the
data types needed to implement a linked list.
The package body contains the implementation of all the
functions and procedures defined in the package specification.
with Ada.Unchecked_Deallocation;
with Ada.Text_IO; use Ada.Text_IO;
package body Unbounded_Stack is
procedure
free is new Ada.Unchecked_Deallocation (Cell, Cell_Access);
--------------
-- Is_Empty
--
--------------
function
Is_Empty (S : in Stack) return Boolean is
begin
return
S.Count = 0;
end
Is_Empty;
----------
-- Size --
----------
function
Size (S : in Stack) return Natural is
begin
return
S.Count;
end Size;
---------
-- Top --
---------
function Top
(S : in Stack) return Element_Type is
begin
return
S.Head.Value;
end Top;
----------
-- Push --
----------
procedure
Push (S : in out Stack; Value : in Element_Type) is
C :
Cell_Access := new Cell;
begin
C.Value
:= Value;
C.Next:= S.Head;
S.Head:= C;
S.Count
:= S.Count + 1;
end Push;
---------
-- Pop --
---------
procedure
Pop (S : in out Stack; Value : out Element_Type) is
C :
Cell_Access := S.Head;
begin
Value:= S.Head.Value;
S.Head:= S.Head.Next;
S.Count
:= S.Count - 1;
free (C);
end Pop;
-----------
-- Clear --
-----------
procedure
Clear (S : in out Stack) is
C :
Cell_Access := S.Head;
begin
while
S.Head /= null loop
C:= S.Head;
S.Head:= S.Head.Next;
S.Count := S.Count - 1;
free
(C);
end loop;
end Clear;
-------------
-- Display
--
-------------
procedure
Display (S : Stack) is
C :
Cell_Access := S.Head;
begin
if
S.Is_Empty then
Put_Line ("The stack is empty.");
end if;
for I in
1 .. S.Count loop
Put_Line (Image (C.Value));
C :=
C.Next;
end loop;
end Display;
end Unbounded_Stack;
Bounded Stack
The bounded stack is also implemented as a generic package.
Instead of using a linked list which can be enlarged with each Push operation,
the bounded stack uses an array defined when an instance of the bounded stack
is declared.
You will also notice that the Is_Full function has been
defined for the bounded stack. Additionally, the Push procedure now has a
precondition requiring the stack not to be full when Push is called. The names
and interfaces for all other functions and procedures are identical between the
bounded stack and the unbounded stack.
generic
type
Element_Type is private;
with
function Image (Item : in Element_Type) return String;
package Bounded_Stack is
type Stack
(Size : Positive) is tagged private;
function
Is_Empty (S : in Stack) return Boolean;
function
Is_Full (S : in Stack) return Boolean;
function
Count (S : in Stack) return Natural;
function Top
(S : in Stack) return Element_Type with
Pre =>
not S.Is_Empty;
procedure
Push (S : in out Stack; Value : in Element_Type) with
Pre=> not S.Is_Full,
Post =>
S.Count = S'Old.Count + 1;
procedure
Pop (S : in out Stack; Value : out Element_Type) with
Pre=> not S.Is_Empty,
Post =>
S.Count = S'Old.Count - 1;
procedure
Clear (S : in out Stack) with
Post =>
S.Is_Empty;
procedure
Display (S : in Stack);
private
type Buff_T
is array (Positive range <>) of Element_Type;
type Stack
(Size : Positive) is tagged record
Buff: Buff_T (1 .. Size);
Index :
Positive := 1;
Tally :
Natural:= 0;
end record;
end Bounded_Stack;
The implementation of the bounded stack differs from the
unbounded stack because stack elements are never dynamically allocated or de-allocated.
with Ada.Text_IO; use Ada.Text_IO;
package body Bounded_Stack is
--------------
-- Is_Empty
--
--------------
function
Is_Empty (S : in Stack) return Boolean is
begin
return
S.Tally = 0;
end
Is_Empty;
-------------
-- Is_Full
--
-------------
function
Is_Full (S : in Stack) return Boolean is
begin
return
S.Tally = S.Size;
end Is_Full;
-----------
-- Count --
-----------
function
Count (S : in Stack) return Natural is
begin
return
S.Tally;
end Count;
---------
-- Top --
---------
function Top
(S : in Stack) return Element_Type is
begin
return
S.Buff(S.Index - 1);
end Top;
----------
-- Push --
----------
procedure
Push (S : in out Stack;Value : in
Element_Type) is
begin
S.Buff(S.Index) := Value;
S.Tally:= S.Tally + 1;
S.Index := S.Index + 1;
end Push;
---------
-- Pop --
---------
procedure
Pop (S : in out Stack; Value : out Element_Type) is
begin
S.Tally
:= S.Tally - 1;
S.Index
:= S.Index - 1;
Value := S.Buff(S.Index);
end Pop;
-----------
-- Clear --
-----------
procedure
Clear (S : in out Stack) is
begin
S.Tally
:= 0;
S.Index
:= 1;
end Clear;
-------------
-- Display
--
-------------
procedure
Display (S : in Stack) is
begin
if
S.Tally = 0 then
Put_Line("The stack is empty.");
else
for I
in reverse 1..S.Index - 1 loop
Put_Line(Image(S.Buff(I)));
end
loop;
end if;
end Display;
end Bounded_Stack;
Since the API for both the bounded and unbounded stack
packages are so similar the use of these packages is very similar.
Using the unbounded stack package
with Ada.Text_IO; use Ada.Text_IO;
with Unbounded_Stack;
procedure Main is
package
Int_Stack is new Unbounded_Stack (Integer, Integer'Image);
use
Int_Stack;
S : Stack;
V : Integer;
begin
Put_Line
("Push 5 values on the stack");
for I in 1
.. 5 loop
S.Push
(I);
end loop;
S.Display;
Put_Line
("Pop 2 values off of stack");
for I in 1
.. 2 loop
S.Pop
(V);
Put_Line
("Popped value" & V'Image);
end loop;
S.Display;
Put_Line
("The top of the stack is" & S.Top'Image);
S.Clear;
S.Display;
end Main;
Using the bounded stack package
with Ada.Text_IO; use Ada.Text_IO;
with bounded_stack;
procedure Main is
package
Int_Stack is new bounded_stack (integer, integer'image);
use
Int_Stack;
S : Stack
(10);
V : Integer;
begin
Put_Line
("Push 5 values on the stack");
for I in 1
.. 5 loop
S.Push
(I);
end loop;
S.Display;
Put_Line
("Pop 2 values off of stack");
for I in 1
.. 2 loop
S.Pop
(V);
Put_Line
("Popped value" & V'Image);
end loop;
S.Display;
Put_Line
("Push 5 values on the stack");
for I in 1
.. 5 loop
S.Push
(I);
end loop;
S.Display;
Put_Line
("The top of the stack is" & S.Top'Image);
S.Clear;
S.Display;
end Main;
In the bounded stack instance the variable S is declared to
be a stack with a capacity of 10 elements. This is done in the line
S : Stack (10);
The (10) sets the Size parameter of the Stack record to 10
for this instance.
The problem description for this weakness enumeration states:
An integer overflow or wraparound occurs when an integer value is incremented to a value that is too large to store in the associated representation. When this occurs, the value may wrap to become a very small or negative number. While this may be intended behavior in circumstances that rely on wrapping, it can have security consequences if the wrap is unexpected. This is especially the case if the integer overflow can be triggered using user-supplied inputs. This becomes security-critical when the result is used to control looping, make a security decision, or determine the offset or size in behaviors such as memory allocation, copying, concatenation, etc.
This problem is prevalent in languages exhibiting structural type definitions rather than nominative type definitions for numeric types[1]. Languages such as C which use structural type definitions provide implicit type conversions between numeric types. Furthermore, structural type definitions of numeric types do not allow the programmer to define a type with a programmer-defined range of valid values. Integer types, for instance, generally come in 8 bit, 16 bit, 32 bit and 64 bit types. There are no provisions in C to define an 8 bit type with a range of -10 through 10. The closest one can do is use a signed char type which provides a range of values from -128 through 127. Furthermore, since C uses only structural information to determine a numeric type integer types experience wrap-around when overflowing or underflowing values.
Using nominative types for numeric data types also allows the specification of a particular data range for a type. Thus, two different types using the same bit representation, such as 8 bits, can be kept separate.
The following example of C code is given in CWE-190 as an example of wrap-around issues:
This code actually exhibits many faults, as well as a potential wrap-around.
·The macros defining JAN, FEB, and MAR evaluate to integer values which are interpreted as month numbers by the function getMonthlySales. There is no assurance that a value greater than 12 cannot be passed to the function, resulting in erroneous behavior.
·Each month’s sales are limited to a maximum of 32767 which may be too small for the monthly revenue for a business. Furthermore, the total of three months sales numbers is also restricted to a maximum of 32767.
A more correct implementation using Ada, which provides nominative numeric types is:
type Months is (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec);
type Sales_Count is range 0..2**31;
function getMonthlySales(Month : Months)return Sales_Count;
function calculateRevenueForQuarter(Count : Sales_Count) return float;
The Ada version implementation shown above defines values for all months and requires the function getMonthlySales to use a parameter of the enumeration type Months, not simply an integer. The C version allows any int value to be passed to the function.
The type Sales_Count is defined to hold any value from 0 through 2^31 (2,147,483,648). Note that this also ensures that a negative sales count cannot be reported. The type Sales_Count will not exhibit wrap-around.
Use of enumerations in C will not provide the same benefits as the Ada enumerated type in the example above. Ada enumerated types are a separate type not implicitly convertible to an integer type, while C enums are simply aliases for int values. The parameter type for the function must still be an int, which does not restrict the parameter values to a set of valid values.
The product uses untrusted input when calculating or using
an array index, but the product does not validate or incorrectly validates the
index to ensure the index references a valid position within the array.
Demonstrative Examples
Example 1 : Java language
public
String getValue(int index) {
return array[index];
}
This may result in ArrayIndexOutOfBounds Exception being
raised if index is outside the range of the array.
Example 2: Java language
private void
buildList (int untrustedListSize) {
if ( 0 > untrustedListSize ) {
die(“Negative value supplied for list
size, die evil hacker!”);
}
Widget[] list = new Widget[ untrustedListSize
];
list[0] = new Widget()’
}
This example attempts to build a list from a user-specified
value, and even checks to ensure a non-negative value is supplied. If, however,
a 0 value is provided, the code will build an array of size 0 and then try to
store a new Widget in the first location, causing an exception to be thrown.
Example 3: C language
int
getValueFromArray(int *array, int len, int index) {
int value;
// check
that the array index is less than the maximum
// length of
the array
if (index
< len) {
// get the
value at the specified index of the array
value =
array[index];
}
// if array
index is invalid then output error message
// and
return value indicating error
else {
printf("Value
is: %d\n", array[index]);
value = -1;
}
return
value;
}
This method only verifies that the given array index is less
than the maximum length of the array but does not check for the minimum value (CWE-839).
This will allow a negative value to be accepted as the input array index, which
will result in a out of bounds read (CWE-125)
and may allow access to sensitive memory. The input array index should be
checked to verify that is within the maximum and minimum range required for the
array (CWE-129).
The programmer allows the user to specify which element in
the list to select, however an attacker can provide an out-of-bounds offset,
resulting in a buffer over-read (CWE-126).
Potential Mitigations using the Ada language
Ada allows the programmer to define numeric types and
subtypes with a specified range of valid values. All instances of a specified
numeric type must all satisfy the range validity requirements specified for
that type.
Example 3 above defines a function returning an int. The
function has two parameters, a pointer to an int, which is intended to point to
an array of ints, and an int index value which is intended to specify an index
in the array.
Within the function a check is made for an invalid index
value and the int value -1 is returned if an error is detected. Nowhere in the
description of the array or the function is there any restriction on the range
of values any of these ints can contain. For instance, it is completely valid
for the array to contain negative values, including -1. If -1 is also used to
indicate an error then the program can never distinguish between an error and
an array value of -1. Much must be changed to fix this fault.
Mitigation 1:
function
getIndex(index : Positive) return String with
Pre => index in String_Array’Range;
function
getIndex(index : Positive) return String is
begin
return String_Array(index);
end
getIndex;
The function specification establishes a pre-condition
requiring the parameter index to be within the range of index values associated
with String_Array. The pre-condition assures that the index value used within
the getIndex function is a valid index of String_Array.
Mitigation 2:
generic
type Element_Type is private;
package
List_Handler is
type List(Size : Positive) is tagged
private;
private
type Element_Array is array (Positive
range <>) of Element_Type;
type List(Size : Positive) is tagged
record
Buffer : Element_Array(1..Size);
end record;
end
List_Handler;
The package specification defines a generic package that can
be instantiated with any type, creating a “List” of that type. The type List is
defined with a discriminant value named Size which determines the size of the
array to be used for a particular instance of List. The discriminant Size is
required to be a value of the pre-defined subtype Positive. The minimum valid
value for an instance of Positive is 1. This prevents the size of the Buffer
element in List from being either negative or 0.
Mitigation 3
type
Int_Array is array(Natural range <>) of Integer;
...
function
getValueFromArray(Nums : Int_Array; index : Natural) return Integer
with Pre => index in Nums’Range;
function
getValueFromArray(Nums : Int_Array; index : Natural) return Integer is
begin
return Nums(index);
end
getValueFromArray;
The type Int_Array is defined as being indexed by a value of
the pre-defined subtype Natural. The minimum value of an instance of Natural is
0. The pre-condition assures that the value of index is within the valid index
values for any instance of Int_Array passed to the function. The function
getValueFromArray always returns a valid array element when the pre-condition
is satisfied. If the pre-condition is not satisfied the call results in an
Assertion_Error exception being raised.
Mitigation 3 alternate
This mitigation fixes the indexing problems without the use
of pre-conditions.
type
Result_Type(Is_Valid : Boolean) is record
case Is_Valid is
when True => Value : Integer;
when False => null;
end case;
end record;
type
Int_Array is array(Natural range <>) of Integer;
function
getValueFromArray(Nums : Int_Array; Index : Natural)
return
Result_Type is
begin
if Index in Nums’Range then
return (Is_Valid => True, Value
=> Nums(Index));
else
return (Is_Valid => False);
end if;
end
getValueFromArray;
The type Result_Type is defined as a variant record. When the discriminant, named Is_Valid, is True the
type contains two fields; Is_Valid and Value. When the discriminant Is_Valid is
False the type only contains the field Is_Valid.
The conditional expression tests the parameter Index. If
Index contains a value within the valid range of index values for the array
Nums then the function returns an instance of Result_Type with the field
Is_Valid containing True and the field Value containing the integer value that
was in Nums(Index), otherwise the function returns an instance of Result_Type
only containing the field Is_Valid and that field contains a False value.
This solution clearly separates the concept of an erroneous
index value from any value contained in the array to be searched. Use of the
variant record allows the function to return two values at the same time. No
Value field is returned when the index is invalid because to do so would
suggest that a valid value was found. This solution prevents a programmer from erroneously
using an invalid return value.
Mitigation 4
with
Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with
Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with
Ada.Integer_IO; use Ada.Integer_IO;
procedure
main is
subtype Item_Index is Integer range 1..4;
type Item_List is array(Index_Type) of
Unbounded_String;
function getOffset return Item_Index is
Offset : Integer;
begin
loop
Put(“Enter a number in the range of 1
through 4: “);
The programmer allows the user to specify the element to
select and the selection will only access the array after a valid index value
has been chosen.
The function getOffset takes no parameters and returns a
value of the subtype Item_Index. The simple loop statement continually prompts
the user until the user enters a valid value. The function then returns that
value. The array of Unbounded_String is only accessed after a valid index value
has been obtained from the user.
Conclusion
These examples show that CWE-129 Improper Validation of
Array Index is far simpler to avoid using Ada than using C, C++, or Java.
The Ada programming language provides four different looping
constructs; the “for” loop, the “while” loop, the simple loop and the container
iterator loop.
The For loop
The Ada “for” loop iterates over a range of discrete values.
Ada discrete values include signed integer values, modular (unsigned) integer
values, and enumeration values. Ada ranges are always specified as
lowest_value..highest value. Every “for” loop has a loop variable which is NOT
declared before it is used. The loop variable has the type of the loop range.
The loop variable cannot be altered within the body of the loop.
Ranges are always specified as lowest_value..highest_value,
even if one wants to iterate through the range in reverse order. Any range
where the first value is greater than the last value is considered an empty
range. To iterate through a range in reverse order simply add the “reverse”
reserved word
The loop variable in this example is named “I”. The first iteration of the loop
variable I contains the value 1.
The second iteration I contains
2. The final iteration of the loop I
contains 10**9 (1000000000).
The output of the program is
counted1000000000 numbers in0.577727576 seconds
The While loop
The Ada while loop iterates while the condition specified at
the top of the loop is true. The condition is always evaluated before the start
of an iteration. The condition must evaluate to a Boolean value (False or
True). Ada Boolean values are an enumeration type, not a numeric type. Ada does
NOT provide any implicit conversion between zero and False or between not-zero
and True as is done in the C language.
Unlike C, C++ or Java, the Boolean expression in Ada does
not need to be enclosed in parentheses “()”.
The output of the program is
counted1000000000 numbers in0.559296318 seconds
The Simple loop
The Ada simple loop continues to iterate until an exit is
executed within the body of the loop. If the body of the loop does not contain
an exit command the loop behaves as an infinite loop. The exit command is
typically found within a conditional expression such as
The iterator loop is used to iterate through containers, and
may be used with arrays. The iterator loop traverses the values of the
container object or array object allowing reading or manipulation of each value
in sequence.
The iterator loop strongly resembles the “for” loop with
some subtle differences. The “loop variable” is actually a member of the
container or array. No range is specified. The iteration proceeds through each
data element in the container or array.
Example Iterator loop
The following example dynamically allocates an array of
10**9 elements. Dynamic memory allocation is used because such an array is too
large to fit on the program stack.
with
Ada.Text_Io; use Ada.Text_IO;
with
Ada.Calendar; use Ada.Calendar;
procedure
Iterator_Loop is
type Nums_Array is Array(1..10**9) of
Integer;
type Nums_Access is access Nums_Array;
Nums : Nums_Access := new Nums_Array;
Start, Stop : Time;
Counter : Integer := 1;
begin
Start := Clock;
for Value of Nums.all loop
Value := Counter;
Counter := Counter + 1;
end loop;
Stop := Clock;
Put_Line("counted " & Nums(Nums'Last)'Image
& " numbers in " &
Duration'Image(Stop - Start) &
" seconds");
end
Iterator_Loop;
The variable Nums is defined to be an access type which
references an instance of Nums_Array. The syntax Nums.all evaluates to the
array referenced by Nums.
The output of the program is
counted1000000000 numbers in3.208108244 seconds
As you can see, iterator loops are much slower than the
other loop constructs.
A matrix is a two dimensional array of elements. Matrices
are commonly used to represent spread sheets or tables of information. A square
matrix is a matrix with the same number of rows and columns. A square matrix is
said to be symmetric if the transpose of the matrix is equal to the original
matrix. Only square matrices can be symmetric.
The code works very well within limits. The limits of its
proper behavior are defined by the declaration of the arrays found on line 7 of
the C source code.
int c, d, a[10][10],
b[10][10], n, temp;
Two matrices are declared. Both matrices have a dimension of
10. While 10 may be a useful arbitrary dimension for an example, this approach
exposes the program to possible buffer overflow. The obvious way to avoid such
buffer overflow in C is to dynamically allocate the two matrices after
inputting the matrix dimension from the user. The downside of using dynamically
allocated matrices is the need to also explicitly use pointers. Specifically,
the line quoted above would need to be changed to the following.
int c, d, **a, **b, n, temp;
This section of the StudyTonight web site is trying to
concentrate on arrays without exposing their relationship to pointers in C.
Similarly, I suspect the example does not define a function
to display the matrices because of the need to pass the matrix as an int **.
Functionally comparable
Ada code
Following is Ada code which performs the same actions as the
C code while avoiding any exposure to buffer overflow and also avoiding
complicated pointer notation.
Ada arrays are first class types. This is true no matter how
many dimensions an array contains.
-- Checking if the original matrix is
the same as its transpose
if A = B then
Put_Line("The matrix is
symmetric.");
else
Put_Line("The matrix is not
symmetric.");
end if;
end;
end
Symmetric_Matrix;
Remarks concerning
the Ada code
A Matrix type is defined as an unconstrained two dimensional
array with each index of the subtype Positive. Each element of type Matrix is
an Integer. Use of an unconstrained array type allows the program to create
instances of Matrix containing exactly the number of elements specified by the
user input.
Every Ada array has several attributes which are always
available to the programmer. This program uses the ‘Range attribute which
evaluates to the range of index values for the array. Since Matrix is a
two-dimensional array there are two range attributes. ‘Range(1) evaluates to
the index values for the first dimension of the array. ‘Range(2) evaluates to
the index values for the second dimension of the array. The procedure Print has
a single parameter M, which is an instance of type Matrix. Since Matrix is an
unconstrained type the parameter M may correspond to any instance of Matrix, no
matter what the sizes of the dimensions may be.
The “declare” block inside the Ada program allows the
definition of Matrix A and Matrix B according to the user input all allocated
from the program stack rather than from the heap, thus avoiding the use of
pointers or their Ada analogs called access types.
The input loop used to fill Matrix A is an iterator loop.
The loop parameter Value references each value in Matrix A in sequence.
Ada implicitly provides equality testing for array
instances. In this program we simply compare Matrix A with Matrix B. If they
are equal then Matrix A is symmetric, otherwise Matrix A is not symmetric.
The output of a representative execution of this program is:
Enter the dimension of the
matrix:
3
Enter the 9 elements of the
matrix:
1 7 3 7 5 -5 3 -5 6
The original matrix is:
173
75
-5
3 -56
The transpose matrix is:
173
75
-5
3 -56
The matrix is symmetric.
The Ada solution is somewhat simpler than the C solution
while also being more secure. If the user chooses to specify a matrix with a
dimension greater than 10 using the C version the variable ‘n’ will be
overwritten with possibly catastrophic effects on the correctness of the
program. The Ada program suffers no such security flaws.
Ada preconditions and post-conditions are implemented using
aspect clauses. While aspect clauses can include many other terms used to
specify program behavior, this posting will focus on preconditions and
post-conditions.
Since its first official version in 1983 the Ada language
has always allowed the programmer to define data types and subtypes with
specific ranges. For example:
type Byte is
range -2**7..2**7 – 1;-- signed integer type
type Unsigned_Byte
is mod 2**8;-- modular type
type
Normalized is digits 5 range 0.0..1.0; -- floating point type
type Money
is digits 10 delta 0.01;-- decimal fixed point type
subtype
Uppers is Character range ‘A’..’Z’; -- character subtype
subtype Positive
is Integer range 1..Integer’Last;
type Days is
(Mon, Tue, Wed, Thu, Fri, Sat, Sun);
When a defined type or subtype is used as a function or
procedure parameter that type or subtype acts as a pre-condition on the call of
the function or procedure.
procedure
Swap(Left, Right : in out Positive);
The procedure example above defines a procedure named Swap. The procedure takes two parameters of
the subtype Positive. Even though subtype Positive is a subtype of Integer and
every instance of Positive is also an instance of Integer, not every instance of
Integer is an instance of Positive.The
Integer type can represent values less than 1, while the subtype Positive
cannot. The Ada compiler writes run-time checks to ensure that the values
passed to Swap are integers within the range of subtype Positive, creating a
precondition for the procedure that all values passed to it must be Integer
values greater than 0.
This use of strong typing in parameter calls provides some
very limited precondition capability. A more robust precondition capability
combined with a post-condition capability was introduced in the Ada 2012
standard.
Preconditions provide a guarantee to the writer of the
function or procedure that a condition will be true when the program is called.
Post-conditions provide a guarantee to the caller of the function or procedure
that a condition will be true when the function or procedure call returns.
The precondition becomes a contract between the caller and
the called subprogram when the subprogram is called. The post-condition becomes
a contract between the caller and the called subprogram when the called
subprogram returns. These contracts are direct implementations of the
requirements for the called subprogram.
Stack Example
The following example shows a stack implementation which
includes definition of some preconditions and some post-conditions.
with function Image(E : Element_Type)
return String;
package
Bounded_Stack is
type Stack(Size : Positive) is tagged
private;
function Is_Full(S : in Stack) return
Boolean;
function Is_Empty(S : in Stack) return
Boolean;
procedure Push(S : in out Stack; Item : in
Element_Type) with
Pre => not S.Is_Full,
Post => not S.Is_Empty;
procedure Pop(S : in out Stack; Item : out
Element_Type) with
Pre => not S.Is_Empty,
Post => not S.Is_Full;
procedure Display(S : in Stack);
private
type Buf is array(Positive range <>)
of Element_Type;
type Stack(Size : Positive) is tagged
record
Stk: Buf(1..Size);
Top: Positive := 1;
Count : Natural := 0;
end record;
end
Bounded_Stack;
This package specification defines the public interface and
the private data definitions for a generic bounded stack ADT.A bounded stack is created with a fixed
maximum size.
The procedure Push pushes an item onto the stack. The precondition
for Push requires the Stack parameter S to not be full (not S.Is_Full). The post-condition requires that after
the successful Push operation the stack will not be empty (not S.Is_Empty). The Pop procedure has
inverse requirements. One can only Pop a value from the stack if the stack is
not empty before the procedure Pop is called (not
S.Is_Empty). After a successful Pop operation the stack will not be full
(not S.Is_Full).
The precondition and the post-condition seem nice enough,
but how do they help the programmer develop correct code? Let’s look first at
the implementation of the subprograms for the generic bounded stack and then at
the “main” procedure used to test this stack ADT.
with
Ada.Text_IO; use Ada.Text_IO;
package body
Bounded_Stack is
-------------
-- Is_Full --
-------------
function Is_Full (S : in Stack) return
Boolean is
begin
return S.Count = S.Size;
end Is_Full;
--------------
-- Is_Empty --
--------------
function Is_Empty (S : in Stack) return
Boolean is
begin
return S.Count = 0;
end Is_Empty;
----------
-- Push --
----------
procedure Push
(S : in out Stack; Item : in
Element_Type) is
begin
S.Stk(S.Top) := Item;
S.Top := S.Top + 1;
S.Count := S.Count + 1;
end Push;
---------
-- Pop --
---------
procedure Pop
(S : in out Stack; Item : out
Element_Type) is
begin
S.Top := S.Top - 1;
Item := S.Stk(S.Top);
S.Count := S.Count - 1;
end Pop;
-------------
-- Display --
-------------
procedure Display (S : in Stack) is
begin
if S.Is_Empty then
Put_Line("Stack is
empty.");
else
for index in reverse 1..S.Top - 1
loop
Put_Line(Image(S.Stk(Index)));
end loop;
end if;
New_Line;
end Display;
end
Bounded_Stack;
Now, let’s focus on the Push and Pop procedures, since their
specifications include preconditions and post-conditions.
----------
-- Push --
----------
procedure Push
(S : in out Stack; Item : in
Element_Type) is
begin
S.Stk(S.Top) := Item;
S.Top := S.Top + 1;
S.Count := S.Count + 1;
end Push;
---------
-- Pop --
---------
procedure Pop
(S : in out Stack; Item : out
Element_Type) is
begin
S.Top := S.Top - 1;
Item := S.Stk(S.Top);
S.Count := S.Count - 1;
end Pop;
Since the precondition for Pop guarantees that the stack is
not full when this procedure is called there is no need to check for a
stack-full condition within the procedure. Similarly there is no need for the
Pop procedure to check if the stack is empty. The precondition for Pop
guarantees that the stack is not empty when Pop is successfully called.
The programmer can simply assume the preconditions are
satisfied while writing the code for a subprogram with preconditions.
Now, let’s look at the “main” procedure used to test this
ADT:
with
Ada.Text_IO; use Ada.Text_IO;
with
Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with
bounded_Stack;
procedure
Main is
type Options is (Push, Pop, Display,
Quit);
package Int_Stack is new
bounded_Stack(Integer, Integer'Image);
use Int_Stack;
S : Stack(5);
function Menu return Options is
package Opts_Io is new Ada.Text_IO.Enumeration_IO(Options);
use Opts_Io;
Value : Options;
begin
Put_Line("-----------------------------------");
Put_Line("Push");
Put_Line("Pop");
Put_Line("Display");
Put_Line("Quit");
Put_Line("-----------------------------------");
Put_Line("Enter your
choice");
Get(Value);
return Value;
end Menu;
Choice : Options;
New_Value : Integer;
Popped_Value : Integer;
begin
loop
Choice := Menu;
case Choice is
when Push =>
Put("Enter the new value to
push on the stack: ");
Get(New_Value);
S.Push(New_Value);
when Pop =>
S.Pop(Popped_Value);
Put_Line("Popped "
& Popped_VAlue'Image);
when Display =>
Put_Line("Stack
contents:");
S.Display;
when Quit =>
exit;
end case;
end loop;
end Main;
This test makes an instance of the Bounded_Stack package
passing in the type Integer and the function Integer’Image. This creates a
stack package containing Integer elements. The variable S is defined to be an
instance of Stack from that package. This instance is set to contain a capacity
of 5 elements.
S : Stack(5);
A function is defined to display and manipulate a text menu
for interacting with the stack.The
function returns the value of type Options input by the user. The executable
part of the Main procedure simply loops through calling the Menu function and
handling the return value of that function until the Quit option is chosen.
The following output shows what happens when the first
option chosen is to Pop a value from the stack. In this case the stack is still
empty because no value has first been pushed onto the stack.
-----------------------------------
Push
Pop
Display
Quit
-----------------------------------
Enter your
choice
Pop
raised
SYSTEM.ASSERTIONS.ASSERT_FAILURE : failed precondition from
bounded_stack.ads:16 instantiated at main.adb:7
[2018-10-20
09:23:58] process exited with status 1, elapsed time: 06.38s
Notice that the program immediately terminated due to the
exception SYSTEM.ASSERTIONS.ASSERT_FAILURE.
Furthermore,
the exception was raised because the precondition stated in the file
bounded_stack.ads, line 16 was violated for the instance of Bounded_Stack
instantiated at line 7 of the file main.adb.
Line 16 of bounded_stack.ads is the line containing the
precondition for the Pop operation.
Now let’s look at the behavior of pushing too many items
onto the stack:
-----------------------------------
Push
Pop
Display
Quit
-----------------------------------
Enter your
choice
push
Enter the
new value to push on the stack: 1
-----------------------------------
Push
Pop
Display
Quit
-----------------------------------
Enter your
choice
push
Enter the
new value to push on the stack: 2
-----------------------------------
Push
Pop
Display
Quit
-----------------------------------
Enter your
choice
push
Enter the
new value to push on the stack: 3
-----------------------------------
Push
Pop
Display
Quit
-----------------------------------
Enter your
choice
push
Enter the
new value to push on the stack: 4
-----------------------------------
Push
Pop
Display
Quit
-----------------------------------
Enter your
choice
push
Enter the
new value to push on the stack: 5
-----------------------------------
Push
Pop
Display
Quit
-----------------------------------
Enter your
choice
display
Stack
contents:
5
4
3
2
1
-----------------------------------
Push
Pop
Display
Quit
-----------------------------------
Enter your
choice
push
Enter the
new value to push on the stack: 6
raised
SYSTEM.ASSERTIONS.ASSERT_FAILURE : failed precondition from
bounded_stack.ads:13 instantiated at main.adb:7
[2018-10-20
09:44:39] process exited with status 1, elapsed time: 38.56s
Again, the exception SYSTEM.ASSERTIONS.ASSERT_FAILURE was
raised, this time the precondition for the Push operation was violated.
In both cases the program was terminated because the precondition
for a procedure call was violated. The preconditions prevented buffer overflow
errors while ensuring the requirements for the Push and Pop procedures.
Traditional programs are sequential, performing actions in a
specified sequence. The classical pattern for sequential program execution is
described as Input, Process, Output. This pattern may be performed once or it
may be performed many times using either iteration or recursion. This pattern
is very effective at doing one thing at a time for one user. The pattern
exhibits serious limitations when dealing with multiple events overlapping in
time, or with multiple users.
For instance, the following sequential program calculates
the sum of the digits in an integer. The program supports one user who enters a
single number.
with
Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
procedure Sum_Digits
is
Num : Natural;
Sum : Integer := 0;
begin
Put("Enter a positive integer:
");
Get(Num);
Put_Line("Given number ="&
Num'Image);
while Num > 0 loop
Sum := Sum + (Num mod 10);
Num := Num / 10;
end loop;
Put_Line("Sum of the digits ="
& Sum'Image);
end
Sum_Digits;
Concurrent Programming
Computer designers soon realized that some problems required
more than one program to run at a time and some business needs required more
than one person at a time to use computing resources. The first solution for
this problem was called time sharing. Operating systems were developed that
allowed several programs to take turns interleaving their sequential processing
so that each program could make some progress in its sequential actions during
a given time period. This provided the illusion of concurrent behavior and also
more efficiently used computer resources. Using the Input, Process, Output
model each program would have periods of low activity while waiting for input
or output data or resources. Other programs could be allowed to execute during
these “waiting” periods.
These early solutions still only used a single central
processor since computers of the time only had a single central processor. The
time sharing approach allowed multiple users to run many different programs or
many instances of the same program simultaneously, but performance was
noticeably impacted as the number of simultaneous users increased. Some systems
could support a dozen users while others could support 50 to 100 users before
performance became bothersome.
Operating systems such as Unix implemented concepts of pipes
and filters allowing many programs to chain input and output to perform complex
processing. Unix pipes were I/O channels within the computer providing
guaranteed delivery of data from one program to another.
For example, if a user wanted to count the number of files
in a directory the user could combine two Unix filters or programs. The “ls”
program lists the files in a directory. The “wc” program counts words or lines
read from its input and outputs the count. The user would simply write
ls | wc –l
The “|” symbol was used to implement a pipe between ls and
wc. The output of the ls command is written to the pipe and that output is sent
to the input of the wc command. The concept was thought of as plumbing data
from one program to another through a “pipe”. The command wc –l caused the wc program to count
only lines, not words or characters. The ls command output the list of files in
the directory with one file name per line of output. The pipe concept was very
sophisticated for its time. The pipe actually caused the two programs to
synchronize their processing. If the pipe was empty the reading program would
be suspended until data arrived. If the pipe was full the writing program would
be suspended until data was consumed by the reading program.
The first attempts to increase performance through hardware
involved locating two or more computer motherboards in the same computer
chassis. Sequential programs could then be distributed across the two or more
central processors to provide increased processing capability to programs and
users. One of the problems of this early approach is that pipes did not
initially work across computer boundaries. A program executing on one
motherboard could not pipe data to a program executing on the other
motherboard. Networking was needed to communicate data between motherboards.
Eventually multi-core processors were developed along with
multi-tasking cores, allowing parallel tasks to be executed on the same central
processor. Those tasks can communicate directly or through shared memory
without the complexities and delays of networking.
Tasks
The commonly used term for separately executing
sub-processes is threads, while the academic term for has long been tasks. The
Ada language has supported the creation of tasks since its first language
standard in 1983, long before the term “threads” became popular for
sub-processes.
Every Ada program executes at least one task, which is
commonly called the main task. Additional tasks can be created. The example
below shows a main task which creates a child task. Both the child task and the
main task run at the same time.
2 Simple Task
with
Ada.Text_IO; use Ada.Text_IO;
procedure
Simple_Task_Main is
task Hello_Task;
task body Hello_Task is
begin
for I in 1..10 loop
Put_Line("=== Hello from the
child task.===");
end loop;
end Hello_Task;
begin
for I in 1..11 loop
Put_Line("Hello from the main
task.");
end loop;
end
Simple_Task_Main;
The interleaving of the outputs from the two tasks will vary
from one execution to another. Following is an output of this program.
3 Simple Task Output
=== Hello
from the child task.===
Hello from
the main task.
=== Hello
from the child task.===
Hello from
the main task.
=== Hello
from the child task.===
Hello from
the main task.
=== Hello
from the child task.===
Hello from
the main task.
=== Hello
from the child task.===
Hello from
the main task.
=== Hello
from the child task.===
Hello from
the main task.
=== Hello
from the child task.===
Hello from
the main task.
=== Hello
from the child task.===
Hello from the
main task.
=== Hello
from the child task.===
Hello from
the main task.
=== Hello
from the child task.===
Hello from
the main task.
Hello from
the main task.
The child task automatically starts when execution of the
main task reaches the “begin” statement in the main task.
Task Interactions
The two tasks shown above do not share any data. Most useful
concurrent programs need to share data among the tasks. Ada provides two
approaches for sharing data. The Ada Rendezvous mechanism allows two tasks to
pass data from one to another in a synchronous manner. Ada Protected Objects
allow data to be shared asynchronously through a shared buffer.
Rendezvous
A task may provide entries. Entries may be called by other
tasks to pass data between the called task and the calling task. The two tasks
synchronize at the calling/called points. If the caller gets to the entry
interface first the caller waits for the called task. If the called task gets
to the entry interface point first the called task waits for the calling task.
The following example demonstrates the use of tasks to
perform parallel addition of the elements of an array. The calling task passes
the first half of an array to one task and the second half of the same array to
another task. Each task totals the elements in its portion of
the array and passes back the sum. The calling task then retrieves the two
sums, and calculates the final sum of array elements. This example also
calculates the time required to perform the parallel sum and displays that
timing as well as the result.
The parallel sum routine is provided in a separate Ada
package. The package specification identifies the data types and function
interface required to call the parallel addition routine. The package body
defines the executable code for the parallel addition routine. Finally, a main
procedure is defined to test the parallel addition and record execution times.
4 Parallel Addition Specification
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 defines two data types. Data_Array
is an unconstrained array of Integer. Data_Access is an access type referencing
Data_Array. Access types are roughly equivalent to references in C++.
The function Sum takes a non-null instance of Data_Access as
an input parameter and returns an Integer; Use of an access type as the
parameter allows the program to handle very large arrays of integer very
efficiently.
5 Parallel Addition Body
package body
Parallel_Addition is
---------
-- Sum --
---------
function Sum (Item : in not null
Data_Access) return Integer is
The package body for Parallel_Addition contains the
implementation of the function Sum. Inside the function Sum a task type named
Adder is defined. First the interface for Adder declares that it has two
entries. The entry named Set reads in two parameters Min and Max, which are the
array indices an instance of Adder will use to access elements of the array
pointed to by the parameter Item passed into function Sum. The entry named
Report passes a single integer out to the calling task of the Adder instance.
The task body of the Adder task type accepts the Set entry,
reading the Min and Max values and assigning them to the local variables First
and Last. The task then sums all the values from index First to index Last.
Finally, the Adder task accepts the Report entry and passes its total to the calling
task.
The calling task in this case is the task that calls the Sum
function.
Two instances of the Adder task, named A1 and A2, are
created. Both instances start executing when the Sum function reaches its
“begin” statement. Both tasks suspend at the accept statement for the Set
entry, waiting for some task to call them. The executable part of the Sum
function then calls the Set entry for each task instance, passing in the
appropriate Min and Max values. The Sum function then calls the Report entries
of each task. The Sum function waits for the tasks to execute the Accept call
for the Report entry, then adds the two reported values and returns that final
total.
The test procedure dynamically allocates an instance of
Data_Array containing 429496729 integers and assigns the value 1 to each
element. A start time of the Sum function is assigned to the variable Start,
the Sum function is called, and a stop time of the Sum function is assigned to
the variable Stop. Finally the sum, the total execution time of the function,
and the average time per addition are displayed.
7 Parallel Addition Test Output
The sum
is:429496729
Addition
elapsed time is1.147519700 seconds.
Time per
addition operation is2.67178E-09
seconds.
A common programming pattern for concurrency is the
Producer-Consumer pattern. This is the pattern used for Unix pipes and filters,
and variations on this pattern continue to be used in many programs. The
simplest producer-consumer pattern employs a single producing task and a single
consuming task. This simple producer-consumer is easily implemented using the
Ada Rendezvous mechanism.
In this example the main task only starts up the producer
and consumer and then waits for them to complete. The producer generates 16
integer values from 0 through 15 then stops. The consumer reads each value
produced by the producer and quits after the producer quits.
Protected Objects
The Rendezvous can be very useful in synchronous
communication between tasks, but is very clumsy when developing asynchronous
task communication solutions. Ada’s solution is the Protected Object.
Ada protected objects are shared data buffers protected from
race conditions between tasks. Protected objects have three kinds of interfaces
to tasks.
Protected Operation
Description
Function
Protected functions provide shared read-only access to the protected
object. Multiple tasks can simultaneously call protected functions of a
protected object. Functions implement a read lock on the protected object
preventing any task from changing the object while it is being read.
Procedure
Protected procedures provide unconditional read/write access to a
protected object. Protected procedures employ an exclusive read/write lock
ensuring only one task at a time has access to the object during execution of
the procedure.
Entries
Protected entries provide conditional read/write access to a
protected object. Protected entries employ an exclusive read/write lock
ensuring only one task at a time has access to the object during execution of
the entry. Tasks calling a protected entry while the controlling condition is
false are automatically suspended in an entry queue. Tasks in an entry queue
are activated and released from the queue when the controlling condition
evaluates to TRUE. The order in which tasks are released from the entry queue
depends upon the chosen queuing policy. The default queuing policy is First
In First Out.
Following is a simple producer-consumer example using a
protected object.
10 Generic Protected Object Specification
generic
type Element_Type is private;
package
Protected_Buffer is
Capacity : constant := 10;
type Index_T is mod Capacity;
type Internal_Buffer is array(Index_T) of
Element_Type;
protected type Buffer_T is
entry Add(Item : in Element_Type);
entry Get(Item : out Element_Type);
private
Buf : Internal_Buffer;
Add_Idx : Index_T := Index_T'First;
Get_Idx : Index_T := Index_T'First;
Count: Natural := 0;
end Buffer_T;
end
Protected_Buffer;
This protected object provides two operations. The Add entry
and the Get entry allow a task to write to the protected object and to read
from the protected object.
The Internal_Buffer type is an array indexed by a modular
type. The valid index values for this array are 0 through 9. Modular types
provide modular arithmetic. In this case 9 + 1 results in 0. Modular types are
very useful for implementing circular buffers.
The implementation of the protected type is:
11 Protected Object
Implementation
package body
Protected_Buffer is
--------------
-- Buffer_T --
--------------
protected body Buffer_T is
---------
-- Add --
---------
entry Add (Item : in Element_Type) when
Count < Capacity is
begin
Buf(Add_Idx) := Item;
Add_Idx := Add_Idx + 1;
Count := Count + 1;
end Add;
---------
-- Get --
---------
entry Get (Item : out Element_Type)
when Count > 0 is
begin
Item := Buf(Get_Idx);
Get_Idx := Get_Idx + 1;
Count := Count - 1;
end Get;
end Buffer_T;
end
Protected_Buffer;
The protected body reveals the conditions associated with
each protected entry. The Add entry is only open to execution when Count is
less than Capacity. The Get entry is only open to execution when Count is
greater than 0.
This implementation of a protected object is designed to
ensure that every value written to the protected object can be read from the
protected object. As we will see later, other behaviors are possible.
12 Protected Producer Consumer
Main
with
Ada.Text_IO; use Ada.Text_IO;
with
Protected_Buffer;
procedure
Main is
package Int_Buf is new Protected_Buffer(Integer);
use Int_Buf;
Shared_Buf : Buffer_T;
task producer;
task body producer is
begin
for I in 0..15 loop
Shared_Buf.Add(I);
end loop;
end producer;
task consumer;
task body consumer is
Num : Integer;
begin
loop
select
Shared_Buf.Get(Num);
Put_Line("Consumed"
& Num'Image);
or
delay 0.001;
exit;
end select;
end loop;
end consumer;
begin
null;
end Main;
13 Protected Main Output
Consumed 0
Consumed 1
Consumed 2
Consumed 3
Consumed 4
Consumed 5
Consumed 6
Consumed 7
Consumed 8
Consumed 9
Consumed 10
Consumed 11
Consumed 12
Consumed 13
Consumed 14
Consumed 15
In this example the producer and consumer tasks never
directly communicate with each other. Instead, the two tasks only communicate
with the protected object. The producer task adds values to the protected
object and the consumer task gets values from the protected object.
Notice that all the lock manipulation is handled
automatically.
There are many variations on the producer-consumer model.
For instance, it is possible to have a producer that produces data faster than
the consumer can consume data. If one uses the protected object implementation
shown above the producer will be slowed down to the rate of the consumer
because the buffer will eventually fill. While this behavior may be desirable
under some circumstances, it may be unacceptable under other circumstances.
Some problem domains may require that the producer work at
full speed, completely uninhibited by the consumer. The result is that the
consumer must under-sample the data produced by the producer.
14 Undersampling Example
with
Ada.Text_IO; use Ada.Text_IO;
procedure
Undersampling is
protected Buffer is
procedure Add(Item : Integer);
entry Get(Item : out Integer);
private
Value : Integer;
Is_New : Boolean := False;
end Buffer;
protected body Buffer is
procedure Add(Item : Integer) is
begin
Value := Item;
Is_New := True;
end Add;
entry Get(Item : out Integer) when
Is_New is
begin
Item := Value;
Is_New := False;
end Get;
end Buffer;
task Producer is
Entry Stop;
end Producer;
task Consumer is
Entry Stop;
end Consumer;
task body Producer is
Num : Natural := 0;
begin
loop
select
Accept Stop;
Exit;
else
Buffer.Add(Num);
Num := Num + 1;
end select;
end loop;
end Producer;
task body Consumer is
Num : Natural;
begin
loop
select
accept Stop;
exit;
else
select
Buffer.Get(Num);
Put_Line("Consumed:"
& Num'Image);
else
null;
end select;
end select;
end loop;
end Consumer;
begin
delay 0.0001; -- wait 0.0001 second
Producer.Stop;
Consumer.Stop;
end
Undersampling;
15 Undersampling output
Consumed: 173
Consumed: 174
Consumed: 195
Consumed: 209
Consumed: 224
Consumed: 238
Consumed: 253
Consumed: 271
Consumed: 286
Consumed: 300
Consumed: 314
Consumed: 328
Consumed: 343
Consumed: 356
Consumed: 372
Consumed: 386
Consumed: 402
Consumed: 416
Consumed: 430
Consumed: 444
Consumed: 459
Consumed: 475
Consumed: 489
Consumed: 503
Consumed: 517
Consumed: 530
Consumed: 545
The main task calls the Stop entries for the producer and
consumer to coordinate the shutdown of the program. Failure to do this will
result in an eventual integer overflow and the corresponding run time
exception.
It is also possible that the consumer may consume data
faster than the data is produced. In this case either the consumer can be
slowed down to wait for the producer, or the consumer can oversample the values.
The following example demonstrates oversampling by the consumer.