Programming languages practical course: Ada Tasks, generic packages

Programming Languages Practical Course

Ada Assignment

Melanie Rieback
CS Dept., R4.23
Email: melanie@cs.vu.nl

Spring 2004

The objective of this exercise is to check the overall understanding of the Ada language and --- more specifically --- the task and the generic package features of Ada.

Exercise

Write a generic parallel merge-sort program in Ada. Let R be an array of n elements. If n=1, then R is sorted. If n>1, split R into two (almost) identical sub-arrays R₁ and R₂. For each of these two sub-arrays, start a new Ada task to sort it recursively. Once both parallel tasks are finished with sorting their respective sub-array, merge the two sorted sub-array.


    -- Parallel merge sort algorithm --
  - If n = 1 then R is sorted
  - If n > 1 then recursively sort the two half parts of R in parallel
                  and merge the results.

This exercise has two parts. Both parts must be implemented in Ada following the Ada programming style. The code must be usefully documented and cleanly presented.

Part I

Implement a generic package Sort_package containing a procedure named Sort which is able to sort an array of any type of elements. The package should be parameterized through the following parameters:

the type of the elements of the array;
a boolean function receiving two arguments a and b of this array element type and returning the boolean value of a<=b.

The Sort function must implement the parallel merge algorithm described above. The n=1 case is trivial. For the n>1 case, the Sort function should start two sorting tasks to recursively sort the two half parts of the array, and so on. The Sort function must perform input and output communication with these tasks through entry calls (and hence, not through global variables). You have to make sure that the sorting tasks actually can work in parallel and that you clearly understand the semantics of the Ada's rendez-vous mechanism: it is mandatory to let the tasks work concurrently.

Part II

Write the main program which tests the Sort function described above. The main program create a generic instanciation of the package created in part I, specifying the INTEGER type as the type of the array elements. This program must read the number of values to be sorted from the standard input into a variable named N. It must then read the N values from the standard input into an array (the program must not assume that each input line only contains a single value). Once the N values have been read into the array, the main program must sort this array and display the resulting sorted array.

Compiler

In order to do this practical exercise, you must use the GNAT GNU Ada Compiler. This compiler accepts the Ada core language and a number of Ada 95 extensions. The compiler can be found in /usr/local/lang/gnat/bin. The easiest way to build your program is to use the gnatmake tool. The documentation is in /usr/local/lang/gnat/doc.

The compiler requires that each source file only constitutes a single compilation unit. Programs generated with this compiler only can be killed with the kill -9 command, not with Control-C.

Documentation

J.G.P. Barnes, Programming in Ada, Fourth Edition. A good introduction to the Ada language.
ANSI/ISO/IEC, Ada 95 Reference Manual, International Standard ANSI/ISO/IEC-8652:1995, January 1995. The formal specification of the Ada 95 langage.

Contact

For any questions related to this practical exercise, contact Melanie Rieback, office R4.23, e-mail: melanie@cs.vu.nl. Please, ask for an appointment by e-mail.

Evaluation

Archive all source files into a tar file, each source file containing the name(s) and studentnumber(s) of the authors as comments, and mail the tar file to melanie@cs.vu.nl with as subject: submit ada. The archive file must also contain a Makefile or a shell-script named make which builds your program and generates an executable file named main.

The program should be tested on various input sets. In particular, the program should be tested with the following input:

The output must be:

Programs proving unable to behave as required will be graded with a 1.

Do not forget to test your program with the scenario given above.