There are lots of easy to understand recursive algorithms. One of the easiest is is a function sum(x) which sums up all the integers from 1 to x. Here is the function implemented in Ada.

function sum(n: integer) return integer is
begin
   if n = 1 then 
      return 1;
   else 
      return (n + sum(n-1));
   end if;
end sum;

Here the function sum(x) recurses until the value of x becomes 0. At this point the recursion is essentially done, and the calls to sum() backtrack. This is shown in the summary below for sum(5).

sum(5) = (5 + sum(4))                          recursive call sum(4)
       = (5 + (4 + sum(3)))                    recursive call sum(3)
       = (5 + (4 + (3 + sum(2))))              recursive call sum(2)
       = (5 + (4 + (3 + (2 + sum(1)))))        recursive call sum(1), return 1
       = (5 + (4 + (3 + (2 + 1))))             return (2 + 1)
       = (5 + (4 + (3 + 3)))                   return (3 + 3)
       = (5 + (4 + 6))                         return (4 + 6)
       = (5 + 10)                              return (5 + 10)
       = 15

There are four recursive calls to sum() in addition to the original call, which is not considered recursive, because the function may actually terminate, e.g. if sum(1) is invoked. So if the function were to call sum(10000), there would be 9,999 recursive calls. The problem with recursion of course is that many of these simplistic algorithms are just as easy to implement as iterative algorithms.

Here is the same algorithm represented iteratively:

function sumi(n: integer) return integer is
   s : integer;
begin
   s := 0;
   for i in 1..n loop
      s := s + i;
   end loop;
   return s;
end sumi;

It might seem odd to think of a compound interest as a problem which could be solved by recursion, but it does make sense. The algorithm for calculating compound interest is of course very simple:

interest = current_balance × interest_rate
new_balance = current_balance + interest
current_balance = new_balance

Of course this calculation is done numerous times depending on how many times the interest is to be compounded. If we were to write a simple function in Ada it would look like this:

with text_io; use text_io;
with ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with ada.Float_Text_IO; use Ada.Float_Text_IO;

procedure compound is
   newBal, currBal, intRate, monRate : float;
   numMon : natural;

   function compound_interest(bal: float; intr: float; n: natural) return float is
      interest: float;
      newbal: float := bal;
   begin
      for i in 1..n loop
         interest := newbal * intr;
         newbal := newbal + interest;
      end loop;
      return newbal;
   end compound_interest;

begin
   put("Balance ($)? "); new_line;
   get(currBal); skip_line;
   put("Interest rate (e.g. 5.3)? "); new_line;
   get(intRate); skip_line;
   put("Number of months (1-12)? "); new_line;
   get(numMon); skip_line;

   monRate := intRate / 100.0 / 12.0;
   newBal := compound_interest(currBal,monrate,numMon);
   put("The new balance is $");
   put(newBal, 1, 2, 0);
end compound;

Here is the program running:

Balance ($)?
1000
Interest rate (e.g. 5.3)?
5
Number of months (1-12)?
12
The new balance is $1051.16

This nonrecursive procedure is fine, but we can also solve it recursively. If we say that the balance, b, after 0 months is the amount of the original deposit, d, and the interest rate is r, then we can write:

At month 0: b(0) = d
At month 1 : b(1) = b(0) + b(0) * r
At month 2 : b(2) = b(1) + b(1) * r
...

Then we can form a recursive definition of the form:

b(m) = b(m-1) + b(m-1) * r

Therefore we can use this to create a recursive function:

b(0) = d
b(m) = b(m-1) + b(m-1) * r

Here is a recursive version of the function compound_interest().

function compound_interestR(bal: float; intr: float; n: natural) return float is
   newbal: float;
begin
   if n = 0 then
      return bal;
   elsif n = 1 then      
      return bal + bal * intr;
   else
      newbal := compound_interestR(bal,intr,n-1);
      return newbal + newbal * intr;
   end if;
end compound_interestR;

The following simple Ada program prints a month in the form:

 SUN MON TUE WED THU FRI SAT
           1   2   3   4   5
   6   7   8   9  10  11  12
  13  14  15  16  17  18  19
  20  21  22  23  24  25  26
  27  28

It uses a simple process which asks the user the number of days in the month and the starting day of the week. The program demonstrates the overloading of packages in Ada, enumerations, types, subtypes, and output.

Here is the algorithm for displaying the month:

Output the heading with the names of the days of the week.
Output the initial blanks.
Set day = the first day input by the user.
loop date in 1 to number_of_days_in_the_month
   output(date)
   if (day = Saturday) then
      insert a new line
      day = Sunday
   else
      day = next day
   end
end loop
   

Here is the program written in Ada:

with text_IO; use text_io;

procedure month is

   subtype month_days is positive range 1..31;
   type week_days is (Sun,Mon,Tue,Wed,Thu,Fri,Sat);
   package positive_io is new integer_io(positive);
   use positive_io;
   package day_io is new enumeration_io(week_days);
   use day_io;
   answer: character;
   firstday: week_days;
   numberofdays: month_days;

   procedure get_number_of_days(nd: out month_days) is
   begin
      put("Enter the number of days in the month: ");
      new_line;
      get(nd);
      skip_line;
   end get_number_of_days;

   procedure get_first_day(fd: out week_days) is
   begin
      put("Enter the first day of the new month: ");
      put("e.g. Sun, Mon, etc.");
      new_line;
      get(fd);
      skip_line;
   end get_first_day;

   procedure display_month(nd: in month_days; fd: in week_days) is
      day: week_days := fd;
      four_blanks: constant string := "    ";
      width : constant integer := 4;
   begin
      for day in week_days loop
         put(' ');
         put(day);
      end loop;
      new_line;
      for blank_days in Mon..fd loop
         put(four_blanks);
      end loop;
      for date in 1..nd loop
         put(date,width);
         if day = Sat then
            day := Sun;
            new_line;
         else
            day := week_days'succ(day);
         end if;
      end loop;
      new_line;
   end display_month;

begin
   loop
      get_number_of_days(numberofdays);
      get_first_day(firstday);
      display_month(numberofdays,firstday);
      put("Do you wish to see another month? "); new_line;
      put("yes(y) or no(n): "); new_line;
      get(answer); skip_line;
      exit when answer = 'n' or answer = 'N';
   end loop;
end month;

You will notice on Line 9, the redefinition of the package enumeration_io to permit the output of the headings, and the input of the first day of the month in an intuitive manner. Also a subtype, month_days, is created on Line 5 of the program which helps ensure proper input by constraining the values allowed in month_days.

The program repeatedly prompts the user for information, and prints the associated month. Here is the programming running:

Enter the number of days in the month:
31
Enter the first day of the new month: e.g. Sun, Mon, etc.
Wed
 SUN MON TUE WED THU FRI SAT
               1   2   3   4
   5   6   7   8   9  10  11
  12  13  14  15  16  17  18
  19  20  21  22  23  24  25
  26  27  28  29  30  31
Do you wish to see another month?
yes(y) or no(n):
n

What happens if the number of days entered by the user is outside the constraints set? The program will raise a constraint error of the form:

raised CONSTRAINT_ERROR : month.adb:19 range check failed

But this can be fixed by modifying the user input routines. Here is how the procedure get_number_of_days() has been fixed.

   procedure get_number_of_days(nd: out month_days) is
      monthlen : month_days;
   begin
      loop
         begin
            put("Enter the number of days in the month: ");
            new_line;
            get(monthlen);
            skip_line;
            if monthlen in 28..31 then
               exit;
            else
               raise constraint_error;
            end if;
         exception
            when others =>
               skip_line;
               put("Bad input. Enter a value between 28-31.");
               new_line;
         end;
      end loop;
      nd := monthlen;
   end get_number_of_days;

On Lines 10-14 there is an if statement which determines if the input is valid. Input outside of the values 28-31 raises a constraint_error, but this time it is dealt with by the procedure on Lines 15-19 (instead of the system). If an exception is raised, then a message is output to the user, and in this case the loop iterates again. If the input is valid, the input loop is exited. This is a good example of how easy it is to deal with various exceptions in Ada. Here is a sample of the program running with invalid input:

Enter the number of days in the month:
42
Bad input. Enter a value between 28-31.
Enter the number of days in the month:

With a basic linked list that really only builds the list and prints it out, let’s add another function to reverse the list. The procedure below works by extracting the head element repeatedly and building it back in reverse.

procedure reverseList(head: in out list) is
   temp: list := null;
   revl: list := null;
begin
   while head /= null loop
      temp := head;
      head := head.next;
      temp.next := revl;
      revl := temp;
   end loop;
   head := revl;
end reverselist;

What is happening here? The list temp holds the extracted item, while revl holds the reversed list. Line 5 loops through the list. Line 6 extracts a node the list (head). Line 7 sets the list head to the next item, and Line 8 adds the extracted node to the reverse list. Finally Line 9 sets the input list pointer to the reversed list. Finally on Line 11, the input list pointer is set to the reversed list.

For something a little more interesting, here’s the recursive version of the procedure:

function reverseListR(head: in list) return list is
   rest: list;
begin
   if head = null or else head.next = null then
      return head;
   end if;
   rest := reverseListR(head.next);
   head.next.next := head;
   head.next := null;
   return rest;
end reverselistR;

Amazingly linked lists in Ada are no different than they are in C, except actually they may be somewhat easier to interpret. You can find out about basic pointers in Ada here (although in Ada they are termed “access values”.

Let’s jump right in and create a linked list, in this case to store a series of words. We will start out with some declarations.

type node;

type list is access node;

type node is record
   word: unbounded_string;
   next: list;
end record;

head: list;

For some people the declaration of node on Line 1 will seem a little odd, but it helps resolve the circularity of the definitions. The declaration on Line 3 refers to node, and the declaration of node (Line 5) refers to list. Line 1 is somewhat of an incomplete declaration as it simply tells the compiler that node is the name of a type of some sort so that the name can be used on Line 3. Nothing else very exciting here – Lines 5-8 declares node to be a record containing the data (word), and the pointer to the next node (next).

Next, we’ll create a procedure buildList() which will create the list, adding one word at a time. There isn’t anything magical here, just a stock-standard list implementation. Remember, lists are LIFO structures, so the last term that gets added is the head of the list.

procedure buildList(head: in out list; aword: in unbounded_string) is
   newNode: list;
begin
   newNode := new node'(word=>aword, next=>null);
   newNode.next := head;
   head := newNode;
end buildList;

On Line 4, the new node is created using new, which takes a free block of memory from the heap and reserves it for use as a node type variable. At the same time it assigns the string (aword), to word, and sets next to null. Lines 5 and 6 insert the new item into the list.

Next, we are going to add a procedure, printList(), to print the list.

procedure printList(head: in list) is
   scanPtr: list;
begin
   scanPtr := head;
   loop
      exit when scanPtr = null;
      put(scanPtr.word);
      scanPtr := scanPtr.next;
      put(" ");
   end loop;
end printList;

The variable scanPtr is a node used to scan the list. Line 5 is the exit strategy for the loop, exiting when the list becomes empty. Line 7 prints the word, and line 8 goes to the next word. Now we need some code to actually run the program.

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Strings.unbounded; use Ada.Strings.unbounded;
with Ada.Strings.unbounded.text_io; use Ada.Strings.unbounded.text_io;

procedure linkedlist is

   -- code from above goes here
   aword: unbounded_string;

begin
   loop
      put("> ");
      get_line(aword);
      exit when aword = "q";
      buildList(head, aword);
   end loop;

   put_line("the list as read :");
   printList(head);
   new_line;

end linkedlist;

Nothing special here. Lines 11-16 provides a loop, prompting the user for words, and building the list until “q” is entered, terminating the input. Here is the programming running:

> the
> cat
> sat
> on
> the
> hat
> q
the list as read :
hat the on sat cat the

The last piece of the program binds the packages together. Here we read in the filename using the procedure getfilename(), and the main program which provides a menu based system to access all the subprograms in the prorgam.

with ada.Text_IO; use Ada.Text_IO;
with ada.strings.unbounded; use ada.strings.unbounded;
with ada.strings.unbounded.Text_IO; use ada.strings.unbounded.Text_IO;
with ada.directories; use ada.directories;
with imagestr; use imagestr;
with imagepgm; use imagepgm;
with imageprocess; use imageprocess;

procedure image is
   fnameI, fnameO : unbounded_string;
   img0 : imagep;
   opt : character;
   buf : unbounded_string;
   lb,ub : float;
   bit : integer;

   -- Procedure to
   procedure getfilename(fname: out unbounded_string; t: in character) is
      res : character;
      buf : unbounded_string;
   begin
      if t = 'r' then
         loop
            put_line("Enter PGM filename: ");
            get_line(fname);
            exit when exists(to_string(fname));
         end loop;
      elsif t = 'w' then
         loop
            put_line("Enter PGM filename: ");
            get_line(fname);
            if exists(to_string(fname)) then
               put_line("Overwrite? (y/n):");
               buf := get_line;
               res := element(buf,1);
               if res = 'y' then
                  exit;
               end if;
            else
               exit;
            end if;
         end loop;
      end if;
   end getfilename;

begin

   loop
      put_line("        Image Processing");
      new_line;
      put_line(" 1. Read in PGM image from file");
      put_line(" 2. Apply image invertion");
      put_line(" 3. Apply LOG function");
      put_line(" 4. Apply contrast stretching");
      put_line(" 5. Apply histogram equalization");
      put_line(" 6. Write PGM image to file");
      put_line(" 7. Apply reduce grays");
      put_line(" 8. Quit");
      put_line(" Choice? ");
      buf := get_line;
      opt := element(buf,1);

      case opt is
         when '1' => getfilename(fnameI,'r');
                     readpgm(img0,fnameI);
         when '2' => imageinv(img0);
         when '3' => imagelog(img0);
         when '4' => put_line("lower bound:");
                     buf := get_line;
                     lb := float'value(to_string(buf));
                     put_line("upper bound:");
                     buf := get_line;
                     ub := float'value(to_string(buf));
                     imagestretch(img0,lb,ub);
         when '5' => histequal(img0);
         when '6' => getfilename(fnameO,'w');
                     writepgm(img0,fnameO);
         when '7' => put_line("bit value (1-8):");
                     buf := get_line;
                     bit := integer'value(to_string(buf));
                     reducegrays(img0,bit);
         when others => exit;
      end case;

   end loop;

end image;

The getfilename(), will get a user-input name for a file, based on whether it is for reading or writing. For a file that is to be read, the procedure will continue looping until a valid filename is input. For writing, if the file already exists the user is prompted to indicate whether or not they want the file overwritten.

The Fortran program can also be translated to Ada. Below is the Ada program. It contains some code to output the resulting value of pi to the text file piCalc1000ADA.txt. In this code a is a “dynamic” array of integers, which is allocated using a declare block. In reality a is just of type pia, declared at a later point in the program.

with ada.Text_IO; use Ada.Text_IO;
with ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with ada.strings.unbounded; use ada.strings.unbounded;
with ada.strings.unbounded.Text_IO; use ada.strings.unbounded.Text_IO;

procedure piSpigotDYN is

    n, len : integer;
    q, x, nines, predigit : integer;
    type pia is array(integer range <>) of integer;
    infp : file_type;

begin
    create(infp,out_file,"piCalc1000ADA.txt");
    n := 1000;
    len := 10 * n / 3;

    declare
       a : pia(1..len);
    begin

    a := (1..len => 2);
    nines := 0;
    predigit := 0;

    for j in 1..n loop
       q := 0;
       for i in reverse 1..len loop
          x := 10 * a(i) + q * i;
          a(i) := x mod (2*i-1);
          q := x / (2*i-1);
       end loop;
       a(1) := q mod 10;
       q := q / 10;
       if q = 9 then
          nines := nines + 1;
       elsif q = 10 then
          put(infp,predigit+1,width=>1);
          for k in 1..nines loop
             put(infp,0,width=>1);
          end loop;
          predigit := 0;
          nines := 0;
       else
          put(infp,predigit,width=>1);
          predigit := q;
          if nines /= 0 then
             for k in 1..nines loop
                put(infp,9,width=>1);
                nines := 0;
             end loop;
          end if;
       end if;
    end loop;
    put(infp,predigit,width=>1);

    close(infp);
    end;
end piSpigotDYN;

A while back I posted on the Spigot algorithm in Pascal (and C) for calculating the first 1000 decimal places of π. Now converting it to Fortran is quite easy.

program piSpigot

   integer :: n, len
   integer :: i, j, k, q, x, nines, predigit
   integer, dimension(3500) :: a

   n = 1000
   len = (10 * n) / 3

   a = 2
   nines = 0
   predigit = 0
   999 format(I1)

   do j = 1,n
      q = 0
      do i = len,1,-1
         x = 10 * a(i) + q * i
         a(i) = mod(x,2*i-1)
         q = x / (2*i-1)
      end do
      a(1) = mod(q,10)
      q = q / 10
      if (q == 9) then
         nines = nines + 1
      elseif (q == 10) then
         write(*,999,advance='no') predigit+1
         do k = 1, nines
            write(*,999,advance='no') 0
         end do
         predigit = 0
         nines = 0
      else
         write(*,999,advance='no') predigit
         predigit = q
         if (nines /= 0) then
            do k = 1,nines
               write(*,999,advance='no') 9
               nines = 0
            end do
         end if
      end if
   end do
   write(*,999,advance='no') predigit

end program piSpigot

This algorithm is good, but it could be improved upon by making the array dynamic. All that really involves is reworking some code at the top of the program. In the snippet of code below, the array a is made allocatable (Line 5), I/O is added to prompt for the number of decimal points required to be calculated, and then on Line 11 the space for a is allocated. At the end of the program, the memory is deallocated.

program piSpigot

   integer :: n, len
   integer :: i, j, k, q, x, nines, predigit
   integer, dimension(:), allocatable :: a

   write(*,*) 'Number of decimal points? '
   read(*,*) n
   len = (10 * n) / 3

   allocate(a(len))
   ...
   deallocate(a)
end program piSpigot

When used separately, get and get_line rarely cause issues. When used together, there can be some issues. Consider the following code:

a : integer;
s : string(1..4);

get(a);
s := get_line;
put(a);
put_line(s);

Here is the dialog obtained when running the program containing this code:

4

raised CONSTRAINT_ERROR : testgetm.adb:14 length check failed

It allows the user to input the number 4, but then balks and pulls an exception. What went wrong? To see what happened we have to consider exactly what these input functions do. As we have seen, calls to get for numeric and string input skip over blanks and line terminators that come before the number. That’s why it is possible to press the <return> key several times between numbers being entered. However these get functions do not skip over any blanks and line terminators that come after the number. After the integer variable a is read, the input pointer is set to the line terminator after 4.

Because get_line stops reading when it encounters a line terminator, it stops and sets the length of the string to zero to indicate a null string. As the size of the (fixed) string is expected to be 4 characters in length, an exception is actioned. One way to circumvent this is to type the string on the same line as the number 4. For example:

6tool
          6tool

This illustrates another feature of numeric input. The get function for numeric data stops reading when a non-numeric character is encountered. The non-numeric character “t” is not read and is still available to be read by the next call to an input function.

This solution is not really optimal. A better idea is to use the function skip_line. When skip_line is called, it moves the input pointer to the next line. It is most useful when using a get_line function after getting a numeric value. Here is an example of its use:

a : integer;
s : string(1..4);

get(a);
skip_line;
s := get_line;
put(a);
put_line(s);

Note that if we use a unbound_string instead of the fixed string, then the program will not convulse, but it also will skip the string input… but it will print out a string. Why? Well the unbound_string will actually store the line terminator in the string… so it does read something, just not what it wanted.

To make things more consistent, it is also possible to read all input in as strings using get_line, and convert the string to numbers. Below is an example of the code. The first value is input to the unbound_string buf, which is then converted to a string, and then an integer, and assigned to the integer variable a.

a : integer;
buf : unbounded_string;

buf := get_line;
a := integer'value(to_string(buf));
buf := get_line;
put(a);
put_line(buf);

Note that weird things can also occur when using consecutive get_line() statements. For example consider the code:

s,t : string(1..4);
get_line(s,len);
put(s); put(len);
get_line(t,len);
put(t); put(len);

Here is an example of it running:

tool
tool          4�#           0

The first string input “tool”. works, the second string reads in the line terminator. The same does not occur using the alternate form of get_line. For example the code below works as it should.

s,t : string(1..4);
s := get_line;
put(s);
t := get_line;
put(t);

So Ada uses packages to implement a form of encapsulation, which actually existed before the whole hoopla with C++ evolved. Packages have a specification, and an implementation. In the example below, we will create three packages to generate an image comprised of random values, i.e. a noise image. Here is an example (it can be saved as a text image).

The first package only has a specification, and is called datas. It includes the data structures needed by the other packages (i) image, and (ii) print (and also the main program). Here is what the specification looks like (datas.ads):

package datas is
   type randRange is new Integer range 0..255;
   type randImg is array(1..500,1..500) of randRange;
end datas;

It includes a type randRange, which specifies integers in the range 0..255, and a type randImg, which is a 2D array of type randRange. Next is the package image – its task is to generate an image of random numbers in the range 0..255. Here is the specification (image.ads):

with ada.numerics.discrete_random;
with datas; use datas;

package image is
   package Rand_Int is new ada.numerics.discrete_random(randRange);
   use Rand_Int;
   procedure makeImage(img : out randImg);
end image;

It creates a new instance of the package discrete_random, to deal with generating numbers in the range 0..255. It also contains a function makeImage(), which uses the types in package datas to generate an image. Here is the package implementation (image.adb):

package body image is

procedure makeImage(img : out randImg) is
   gen : Generator;
begin
   reset(gen);
   for i in 1..img'last(1) loop
      for j in 1..img'last(2) loop
         img(i,j) := random(gen);
      end loop;
   end loop;
end;

end image;

The last package, print just prints out the image as a series of rows (to standard output, but it can be redirected to a file, e.g. a.out >randim.txt). Here is the specification (print.ads):

with ada.Text_IO; use Ada.Text_IO;
with ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with datas; use datas;

package print is
   procedure printImage(img : in randImg);
end print;

And the associated implementation (print.adb):

package body print is

procedure printImage(img : in randImg) is
begin
   for i in 1..img'last(1) loop
      for j in 1..img'last(2) loop
         put(randRange'Image(img(i,j)));
      end loop;
      new_line;
   end loop;
end;

end print;

Finally the main program that calls them all (test.adb)

with image; use image;
with print; use print;
with datas; use datas;

procedure test is
   im : randImg;

begin
   makeImage(im);
   printImage(im);
end test;

This program can be compiled simply using the main file:

% gnatmake -Wall test.adb

Obviously packages can be compiled,bu they can’t be linked or executed. Each of the packages can also be compiled separately:

% gnatmake -Wall image.ads image.adb
% gnatmake -Wall print.ads print.adb
% gnatmake -Wall datas.ads
% gnatmake -Wall test.adb

Ada is a very strict language, but then it has to be, as it was designed for creating real-time systems. It does have some idiosyncrasies, but then all languages do. Let’s look at the two functions get() and get_line().

get()

The function get(), reads a value from the standard input. It knows what to read based on the argument it is given. For example the following piece of code allows an integer to be read into value x.

x : integer;
get(x);

Here are the characteristics of get():

• For numbers it skips whitespaces (including newlines).
• For characters and strings it reads exactly the right number of characters, but excludes newlines in count.

For example consider the following code:

s : string(1..4);
get(s);

Then the input from the user could be either one of:

tool

t
o
o
l

get_line()

The function get_line(), reads an entire line, i.e. a string. It stops reading when it encounters a line terminator (or rather if the end of the line is encountered, it automatically calls skip_line). Ada offers two ways to use get_line:

s : string(1..4);
len : natural;
s := get_line;
get_line(s,len);

The first (Line 3) treats get_line like a function, the other (Line 4) treats it like a procedure. Note there is a second parameter in the latter call, len. This returns the length of the string read in (the second parameter should be omitted for unbound_string). When using these two, there are different outcomes. Consider the following code, which reads in a fixed string.

s : string(1..4);
s := get_line;
put(s);

This code will only work when the string input is exactly 4 characters in length. Any other length will throw an exception. This is unlike C which allows more or less to be read. Alternatively, consider the following code:

s : string(1..4);
len : natural;
get_line(s,len);
put(s); put(len);

In this case, the value stored in s will be any string less than or equal to 4 characters in length, with the size stored in len. To circumvent these issues, often an unbound_string is used, which will basically read any size string up until the line terminator (typically a <return>). The code would look like this:

buf : unbounded_string;
buf := get_line;
put(buf);

Further reading:

• Input of Strings and Characters, EOL and EOF

The type system of Ada is not merely strongly typed, but sometimes referred to as being super-strongly typed, because it does not allow for any level of implicit conversions. None. Consider the following code in C:

#include <stdio.h>
int main(void) {
   float e;
   int a;
   e = 4.7631;
   a = e;
   printf("%d\n", a);
   return 0;
}

This is valid code that will compile, run and produce the expected result – the result printed out is 4. C has no issues performing an implicit conversion. Ada on the other hand won’t even compile similar code. Here is the Ada equivalent:

with ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure testtyped is
    a : integer;
    e : float;
begin
   e := 4.7631;
   a := e;
   put(a);
end testtyped;

When an attempt is made to compile this, the following error will occur:

testtyped.adb:8:09: expected type "Standard.Integer"
testtyped.adb:8:09: found type "Standard.Float"

The problem here is that a and e are clearly not the same. Instead, one has to explicitly convert between types, which promotes good design by preventing the mixing of types. In this case, Line 9 in the above code becomes:

a := integer(e);

Also at run-time, errors such as illegal memory accesses, buffer overflows, range violations, off-by-one errors, and array access are tested. These errors can then be handled safely instead of the way languages like C do. For example, consider the following C code:

#include <stdio.h>
int main(void) {
   int x[100];
   x[101] = 1;
   printf("%d\n", x[101]);
   return 0;
}

Again, this is valid code that will compile, run and produce unexpected results. A value is actually stored outside the array x. Consider the same code written in Ada:

with ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure testarrOOB is
    x : array (1..100) of integer;
begin
   x(101) := 1;
   put(x(101));
end testarrOOB;

Compiling the program will result in the following warnings:

testarroob.adb:6:06: warning: value not in range of subtype of "Standard.Integer" defined at line 4
testarroob.adb:6:06: warning: "Constraint_Error" will be raised at run time
testarroob.adb:7:10: warning: value not in range of subtype of "Standard.Integer" defined at line 4
testarroob.adb:7:10: warning: "Constraint_Error" will be raised at run time

It does produce an executable, but running the executable results in an exception being triggered:

raised CONSTRAINT_ERROR : testarroob.adb:6 range check failed

Why is this important? Because in real-time systems, errors such as this have to be avoided. Now ask yourself why it is possible the F-35 code written in C++ does work as intended.

When used separately, get and get_line rarely cause issues. When used together, there can be some issues. Consider the following code:

a : integer;
s : string(1..4);

get(a);
s := get_line;
put(a);
put_line(s);

Here is the dialog obtained when running the program containing this code:

4

raised CONSTRAINT_ERROR : testgetm.adb:14 length check failed

It allows the user to input the number 4, but then balks and pulls an exception. What went wrong? To see what happened we have to consider exactly what these input functions do. As we have seen, calls to get for numeric and string input skip over blanks and line terminators that come before the number. That’s why it is possible to press the <return> key several times between numbers being entered. However these get functions do not skip over any blanks and line terminators that come after the number. After the integer variable a is read, the input pointer is set to the line terminator after 4.

Because get_line stops reading when it encounters a line terminator, it stops and sets the length of the string to zero to indicate a null string. As the size of the (fixed) string is expected to be 4 characters in length, an exception is actioned. One way to circumvent this is to type the string on the same line as the number 4. For example:

6tool
          6tool

This illustrates another feature of numeric input. The get function for numeric data stops reading when a non-numeric character is encountered. The non-numeric character “t” is not read and is still available to be read by the next call to an input function.

This solution is not really optimal. A better idea is to use the function skip_line. When skip_line is called, it moves the input pointer to the next line. It is most useful when using a get_line function after getting a numeric value. Here is an example of its use:

a : integer;
s : string(1..4);

get(a);
skip_line;
s := get_line;
put(a);
put_line(s);

Note that if we use a unbound_string instead of the fixed string, then the program will not convulse, but it also will skip the string input… but it will print out a string. Why? Well the unbound_string will actually store the line terminator in the string… so it does read something, just not what it wanted.

To make things more consistent, it is also possible to read all input in as strings using get_line, and convert the string to numbers. Below is an example of the code. The first value is input to the unbound_string buf, which is then converted to a string, and then an integer, and assigned to the integer variable a.

a : integer;
buf : unbounded_string;

buf := get_line;
a := integer'value(to_string(buf));
buf := get_line;
put(a);
put_line(buf);

Note that weird things can also occur when using consecutive get_line() statements. For example consider the code:

s,t : string(1..4);
get_line(s,len);
put(s); put(len);
get_line(t,len);
put(t); put(len);

Here is an example of it running:

tool
tool          4�#           0

The first string input “tool”. works, the second string reads in the line terminator. The same does not occur using the alternate form of get_line. For example the code below works as it should.

s,t : string(1..4);
s := get_line;
put(s);
t := get_line;
put(t);

So Ada uses packages to implement a form of encapsulation, which actually existed before the whole hoopla with C++ evolved. Packages have a specification, and an implementation. In the example below, we will create three packages to generate an image comprised of random values, i.e. a noise image. Here is an example (it can be saved as a text image).

The first package only has a specification, and is called datas. It includes the data structures needed by the other packages (i) image, and (ii) print (and also the main program). Here is what the specification looks like (datas.ads):

package datas is
   type randRange is new Integer range 0..255;
   type randImg is array(1..500,1..500) of randRange;
end datas;

It includes a type randRange, which specifies integers in the range 0..255, and a type randImg, which is a 2D array of type randRange. Next is the package image – its task is to generate an image of random numbers in the range 0..255. Here is the specification (image.ads):

with ada.numerics.discrete_random;
with datas; use datas;

package image is
   package Rand_Int is new ada.numerics.discrete_random(randRange);
   use Rand_Int;
   procedure makeImage(img : out randImg);
end image;

It creates a new instance of the package discrete_random, to deal with generating numbers in the range 0..255. It also contains a function makeImage(), which uses the types in package datas to generate an image. Here is the package implementation (image.adb):

package body image is

procedure makeImage(img : out randImg) is
   gen : Generator;
begin
   reset(gen);
   for i in 1..img'last(1) loop
      for j in 1..img'last(2) loop
         img(i,j) := random(gen);
      end loop;
   end loop;
end;

end image;

The last package, print just prints out the image as a series of rows (to standard output, but it can be redirected to a file, e.g. a.out >randim.txt). Here is the specification (print.ads):

with ada.Text_IO; use Ada.Text_IO;
with ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with datas; use datas;

package print is
   procedure printImage(img : in randImg);
end print;

And the associated implementation (print.adb):

package body print is

procedure printImage(img : in randImg) is
begin
   for i in 1..img'last(1) loop
      for j in 1..img'last(2) loop
         put(randRange'Image(img(i,j)));
      end loop;
      new_line;
   end loop;
end;

end print;

Finally the main program that calls them all (test.adb)

with image; use image;
with print; use print;
with datas; use datas;

procedure test is
   im : randImg;

begin
   makeImage(im);
   printImage(im);
end test;

This program can be compiled simply using the main file:

% gnatmake -Wall test.adb

Obviously packages can be compiled,bu they can’t be linked or executed. Each of the packages can also be compiled separately:

% gnatmake -Wall image.ads image.adb
% gnatmake -Wall print.ads print.adb
% gnatmake -Wall datas.ads
% gnatmake -Wall test.adb

Ada is a very strict language, but then it has to be, as it was designed for creating real-time systems. It does have some idiosyncrasies, but then all languages do. Let’s look at the two functions get() and get_line().

get()

The function get(), reads a value from the standard input. It knows what to read based on the argument it is given. For example the following piece of code allows an integer to be read into value x.

x : integer;
get(x);

Here are the characteristics of get():

• For numbers it skips whitespaces (including newlines).
• For characters and strings it reads exactly the right number of characters, but excludes newlines in count.

For example consider the following code:

s : string(1..4);
get(s);

Then the input from the user could be either one of:

tool

t
o
o
l

get_line()

The function get_line(), reads an entire line, i.e. a string. It stops reading when it encounters a line terminator (or rather if the end of the line is encountered, it automatically calls skip_line). Ada offers two ways to use get_line:

s : string(1..4);
len : natural;
s := get_line;
get_line(s,len);

The first (Line 3) treats get_line like a function, the other (Line 4) treats it like a procedure. Note there is a second parameter in the latter call, len. This returns the length of the string read in (the second parameter should be omitted for unbound_string). When using these two, there are different outcomes. Consider the following code, which reads in a fixed string.

s : string(1..4);
s := get_line;
put(s);

This code will only work when the string input is exactly 4 characters in length. Any other length will throw an exception. This is unlike C which allows more or less to be read. Alternatively, consider the following code:

s : string(1..4);
len : natural;
get_line(s,len);
put(s); put(len);

In this case, the value stored in s will be any string less than or equal to 4 characters in length, with the size stored in len. To circumvent these issues, often an unbound_string is used, which will basically read any size string up until the line terminator (typically a <return>). The code would look like this:

buf : unbounded_string;
buf := get_line;
put(buf);

Further reading:

• Input of Strings and Characters, EOL and EOF

The type system of Ada is not merely strongly typed, but sometimes referred to as being super-strongly typed, because it does not allow for any level of implicit conversions. None. Consider the following code in C:

#include <stdio.h>
int main(void) {
   float e;
   int a;
   e = 4.7631;
   a = e;
   printf("%d\n", a);
   return 0;
}

This is valid code that will compile, run and produce the expected result – the result printed out is 4. C has no issues performing an implicit conversion. Ada on the other hand won’t even compile similar code. Here is the Ada equivalent:

with ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure testtyped is
    a : integer;
    e : float;
begin
   e := 4.7631;
   a := e;
   put(a);
end testtyped;

When an attempt is made to compile this, the following error will occur:

testtyped.adb:8:09: expected type "Standard.Integer"
testtyped.adb:8:09: found type "Standard.Float"

The problem here is that a and e are clearly not the same. Instead, one has to explicitly convert between types, which promotes good design by preventing the mixing of types. In this case, Line 9 in the above code becomes:

a := integer(e);

Also at run-time, errors such as illegal memory accesses, buffer overflows, range violations, off-by-one errors, and array access are tested. These errors can then be handled safely instead of the way languages like C do. For example, consider the following C code:

#include <stdio.h>
int main(void) {
   int x[100];
   x[101] = 1;
   printf("%d\n", x[101]);
   return 0;
}

Again, this is valid code that will compile, run and produce unexpected results. A value is actually stored outside the array x. Consider the same code written in Ada:

with ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure testarrOOB is
    x : array (1..100) of integer;
begin
   x(101) := 1;
   put(x(101));
end testarrOOB;

Compiling the program will result in the following warnings:

testarroob.adb:6:06: warning: value not in range of subtype of "Standard.Integer" defined at line 4
testarroob.adb:6:06: warning: "Constraint_Error" will be raised at run time
testarroob.adb:7:10: warning: value not in range of subtype of "Standard.Integer" defined at line 4
testarroob.adb:7:10: warning: "Constraint_Error" will be raised at run time

It does produce an executable, but running the executable results in an exception being triggered:

raised CONSTRAINT_ERROR : testarroob.adb:6 range check failed

Why is this important? Because in real-time systems, errors such as this have to be avoided. Now ask yourself why it is possible the F-35 code written in C++ does work as intended.

The problem with switch

The switch statement in C/C++ is horrible. It was never really that well thought out. The main problem is that the default label is entirely optional. There is no requirement to handle all possible values of an expression. The other issue is the break statement, which if not included may result in an unintended fall-through. In comparison, Ada provides a case statement which is safer. Firstly, a case statement in Ada must cover every possible value of the case expression, it will be checked at compile time. For example here is an example which classifies temperatures for an oven.

with ada.Text_IO; use Ada.Text_IO;
with ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure safecase is

   n : integer;

begin
   put("Enter an oven temperature (F): ");
   get(n);
   case n is
      when 200 .. 299 => put_line("cool oven");
      when 300 .. 325 => put_line("slow oven");
      when 326 .. 350 => put_line("moderately slow oven");
      when 351 .. 375 => put_line("moderate oven");
      when 376 .. 400 => put_line("moderately hot oven");
      when 401 .. 450 => put_line("hot oven");
      when 451 .. 500 => put_line("very hot oven");
      when others => put_line("temperature out of bounds");
   end case;

end safecase;

If the others line were omitted, then the following compiler error would propagate, implying values 199 and below, and 501 and above are not accounted for.

safecase.adb:11:04: missing case values: -16#8000_0000# .. 199
safecase.adb:11:04: missing case values: 501 .. 16#7FFF_FFFF#

A when branch can specify a single value, or a range of values, or any combination separated by the | symbol. The optional others branch covers the values not included in earlier branches. When execution of the statements in the selected branch has been completed, control resumes after the end case statement. Unlike C++, Ada does not allow fall-through to the next branch.

The problem with statements

In C/C++ there are simple statements , and compound statements enclosed in {}. It is therefore easy to create a logic error simply by failing to enclose more than one statement in a compound. Below is an example of a piece of code in which the logic is erroneous:

for (i=0, i<50; i=i+2)
   a[i] = 0;
   a[i+1] = 1;

The code is not contained within a compound statement, so only the first statement is associated with the for loop. Ada has no concept of a simple statement, and all control structures are “blocked”. For example the code above in Ada would be:

for i in 1..50 loop
   a(i*2-1) := 0;
   a(i*2) := 1;
end loop;

The problem with function returns

C++ only provides a single type of subprogram – the function. It is possible for a function to omit the name of the return type, in which case the return type is set to int. A function that returns nothing (i.e. a procedure) has a void return type. Theoretically every function should have a return type as it should be used to indicate whether a function succeeds or fails (hence the default to int). Many programmers of course don’t bother with indicating the success of a function, and hence ignore the return value. Failure to heed a function failure can result in the failure of a safety-critical system. Consider the following C++ program:

#include <iostream>

int doubled(int x){
   return x*2;
}

int quadruple(int x){
   return doubled(doubled(x));
}

int main(){
   quadruple(5);
   return 0;
}

When this is compiled (even with warnings) there is no issue, even though the function call to quadruple() is treated like like a statement, with the return sent off to the nether world. It is then easy to have such failings happen in a large program, and hard to trace a source of error. Ada return values can be used for the same purposes as C/C++ return values, but they cannot be ignored. Here is the same program coded in Ada.

with ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure safefunc is
   n : Integer;

   function quadruple (x: Integer) return Integer is
      function double (x: Integer) return Integer is
      begin
         return x * 2;
      end double;
      result : Integer;
   begin
      result := double(double(x));
      return result;
   end Quadruple;

begin
   quadruple(5);
end safefunc;

Compiling this will lead to an error on line 18, the source of the call to quadruple():

safefunc.adb:18:04: cannot use call to function "quadruple" as a statement
safefunc.adb:18:04: return value of a function call cannot be ignored

This has to be fixed by adding a return value, of the form:

n := quadruple(5);

Ada was designed to support safety in modern safety critical systems. The examples outlined offer an insight into how Ada is better than C++ for such systems. Neither C nor C++ were designed to support the needs of real-time safety-critical systems.

Safety critical software is incredibly important for systems designed for applications such as aerospace, rail transportation, power stations and the like. This the F-35 hey, built largely in C++. In some cases these systems have been built in languages such as C and C++, largely because they have a very inexpensive labour force. However the use of these languages, as opposed to Ada have significant hidden costs and incur safety risks due in part to the unweildy and awkward nature of the languages. This post compares some of the features of C++ and Ada.

The problem with arrays

There are a number of issues with arrays in C++:

• Every array index must begin at zero. Due to this array indexing is always off-by-one from the element number of the array resulting in a tendency to index past the end of the array.
• C++ does not do bounds checking automatically, instead relying on it to be manually coded.
• The use of 0-based arrays means that 2D arrays are indexed using a single index which is derived using a formula. This maps very closely to how the array is stored in memory, but does not support the idea of matrix in an unambiguous manner.
• Arrays are indexed using integers.

In comparison, Ada arrays include a declaration of both the index-type, and the element type. All operations performed on the array are subjected to bounds checking, and the array indices may be of any discrete type. Below is an example of creating an array in Ada to hold a 1000×1000 image.

procedure safearrays is

subtype imgIndex is integer range 1..1000;
subtype uint8 is integer range 0..255;
type image is array(imgIndex,imgIndex) of uint8;
image1 : image;

begin
   for x in image1'range(1) loop
      for y in image1'range(2) loop
         image1(x,y) := 0;
      end loop;
   end loop;

end safearrays;

Subtypes can be used to constrain the valid range on index and array values. In this case the subtype uint8 is created to hold unsigned integers with values 0..255, and the subtype imgIndex is used to hold the index range for the image. The type image is then created using these types. If any attempt is made to access an element outside the array image, the following error occurs (where X is the line number):

raised CONSTRAINT_ERROR : safearrays.adb:X index check failed

The Ada syntax has a number of benefits. Firstly Ada arrays are first class types, not structures created as an afterthought using pointers. No pointers are involved, to at least they are handled internally. Ada also implicitly checks array bounds, meaning unlike C/C++ there will never be an issue with accessing a piece of memory not associated with an array. The Ada Range attribute means that bounds do no have to be hard coded, which makes it easier to maintain a piece of code.

The problem with strings

Let’s face it strings in C/C++ are generally horrible. Nobody should have to deal with a string terminator, the null character, ‘\0’. This means strings always have to be one element larger than the characters being stored. This means if a string is created, the null character must be added, otherwise there is the risk of issues with array bounds, or garbage being extracted from elements with no value. C/C++ provide a whole string library to manipulate strings, for example strcpy() to copy a string. Like numeric arrays, no bounds checking is performed on strings.

There are of course inherent safety concerns with C++ strings. The first is that they do not automatically maintain information about the length of the information contained in a string, and need the strlen() function to do that, assuming the string is null terminated. The second is that they do not prevent information being stored beyond the physical end of the string. A missing null character might mean the standard string functions process beyond the bounds of the string. C++ does provide a String class. Below is an example which creates a string, str, of length 10 (although in reality it should only hold 9 characters). Values are then assigned to all 10 elements of str, and 20 elements of str are printed out, as well as the length of the string.

#include <iostream>
#include <cstring>

using std::cout;
using std::endl;

int main(){
   char str[10];
   for (int i=0; i<10; i=i+1)
      str[i] = 65+i;
   for (int i=0; i<20; i=i+1)
      cout << str[i];
   cout << strlen(str) << endl;
   return 0;
}

The output is as expected from C++ – the first 10 uppercase characters followed by a bunch of garbage, and a length of 11.

    ABCDEFGHIJ
    
    `�11

Ada provides a predefined array fixed type, String. This can either be specified using bounds (line 1), or an unconstrained array (line 2), where the bounds are deduced from the initialization expression.

1   quoteyoda : String(1..30) := "Do or do not, there is no try!";
2   quoteyoda : constant String := "Do or do not, there is no try!";

Ada provides three forms of strings: the type String is a fixed length string, the type Bounded_String provides a fixed buffer than contains string data up to the length of the buffer, and Unbounded_String which uses a dynamically allocated buffer to contain data without having to define the length. There is no need for special functions to copy from one String to another, or one Bounded_String to another, however functions are provided to convert between types, for example a String to an Unbounded_String. The main benefit of strings in Ada is that memory outside the buffer associated with the string cannot be corrupted. Here is a simple example in Ada which tries to access the 11th element of the array str.

with Ada.Text_IO; use Ada.Text_IO;

procedure safestr is
str : String(1..10);
begin
   str := "ABCDEFGHIJ";
   put(str);
   put(str(11));
end safestr;

It is not possible. Compiling it produces the following messages:

safestr.adb:8:12: warning: value not in range of subtype of "Standard.Integer" defined at line 4
safestr.adb:8:12: warning: "Constraint_Error" will be raised at run time

And executing the code causes “raised CONSTRAINT_ERROR : safestr.adb:8 range check failed“. So Ada catches the error, and C++ using the standard array of characters fails to.

As mentioned before, strings in Ada can be tricky. Normal strings are fixed in length, and Ada is very stringent about this. Consider a piece of code like this:

with ada.Text_IO; use Ada.Text_IO;
with ada.strings.unbounded; use ada.strings.unbounded;

procedure ustr2strfail is
   function tub(Source : String) return unbounded_string renames ada.strings.unbounded.to_unbounded_string;
   type lexicon is array(1..10) of unbounded_string;
   words : lexicon := (tub("gum"),tub("sin"),tub("cry"),
           tub("lug"),tub("star"),tub("fault"),tub("sleeper"),
           tub("a"),tub("vader"),tub("nordic"));
   aword : string(1..10);
begin
   aword := to_string(words(7));
   put(aword);
end ustr2strfail;

This will compile fine, however when it runs, the following error will propogate:

raised CONSTRAINT_ERROR : ustr2strfail.adb:12 length check failed

This means that although the unbounded string is converted to a string using the function to_string(), it only works if the length of the unbounded string equals the length of the string aword. So in the code above, aword has a length of 10, and when an attempt is made to assign it the unbounded string, “sleeper”, it fails. It would work if sleeper was padded out with 3 spaces after it. How to fix this? Do exactly that, pad the words. Here is a subroutine that does this:

with ada.Text_IO; use Ada.Text_IO;
with ada.strings.unbounded; use ada.strings.unbounded;
with ada.strings.unbounded.Text_IO; use ada.strings.unbounded.Text_IO;
with ada.strings.fixed; use ada.strings.fixed;

procedure ustr2str is
   subtype string10 is string(1..10);
   R : string10;
   function tub(Source : String) return unbounded_string renames ada.strings.unbounded.to_unbounded_string;
   type lexicon is array(1..10) of unbounded_string;
   words : lexicon := (tub("gum"),tub("sin"),tub("cry"),
           tub("lug"),tub("star"),tub("fault"),tub("sleeper"),
           tub("a"),tub("vader"),tub("nordic"));

   function padString(V: unbounded_string) return string10 is
      temp : constant string := to_string(V);
      res : string10;
   begin
      ada.strings.fixed.move(temp, res, drop=>ada.strings.right);
      return res;
   end padString;

begin
   R := padString(words(7));
   put(R);
end ustr2str;

It uses the procedure move(), from the ada.strings.fixed package. It has the following basic form:

procedure Move (Source  : in  String;
                Target  : out String;
                Drop    : in  Truncation := Error;
                Justify : in  Alignment  := Left;
                Pad     : in  Character  := Space);

The procedure move() copies characters from Source to Target. If Source has the same length as Target, then the effect is to assign Source to Target. If Source is shorter than Target then, Justify is used to place the Source into the Target (default = Left). Pad specifies the padding, default is Space. Drop is used if Source is longer than Target.