Tuesday, August 28, 2012

AdaTutor - Subprograms and Packages (1)

Procedures and Functions

When we compiled procedures Hello and Add, we made it possible for other units to with them and call them.  We can also compile just a specification, supplying the body later.  For example, we could compile

   function English_Upper_Case(S : in String) return String;
and then compile the calling program.  When we later write the body, it must agree with the specification:
   function English_Upper_Case(S : in String) return String is
      Answer : String(S'Range) := S;
   begin
      for I in S'Range loop
         if S(I) in 'a' .. 'z' then
            Answer(I) := Character'Val(Character'Pos(S(I)) - 32);
         end if;
      end loop;
      return Answer;
   end English_Upper_Case;

Functions and procedures may also be declared locally.  In Ada 83, such declarations must follow any simple declarations like S : String(1 .. 5);.

   with Ada.Text_IO; use Ada.Text_IO;
   procedure Greeting is
     S : String(1 .. 5) := "Hello";
     function English_Upper_Case(S : in String) return String is
       Answer : String(S'Range) := S;
     begin
       for I in S'Range loop
         if S(I) in 'a' .. 'z' then
           Answer(I) := Character'Val(Character'Pos(S(I)) - 32);
         end if;
       end loop;
      return Answer;
     end English_Upper_Case;
   begin
     Put_Line(English_Upper_Case(S));
   end Greeting;

It's usually better to declare local functions and procedures to be separate.  These subprograms can in turn declare separate subprograms, to any depth:

   procedure Main is
   function A return Float is separate;
   begin
     ...
   end Main;

   separate (Main)
   function A return Float is
      procedure B is separate;
   begin
     ...
   end A;

   separate (Main.A)
   procedure B is
      procedure C(I : in Integer) is separate;
   begin
     ...
   end B;

   separate (Main.A.B)
   procedure C(I : in Integer) is ... (etc.)

However, is separate may be used only at the outermost level.  The example below is legal as it stands, but we may not make procedure B separate unless we also make function A separate, thus bringing function A to the outermost level.

procedure Main is
   F : Float;
   function A return Float is
      Answer : Float;
      procedure B is
      begin
         ...
      end B;
   begin
      ...
      return Answer;
   end A;
begin
  ...
end Main;

A program that begins separate (...) must be compiled after the program that says is separate, because a subprogram depends on its "parent."

In Ada 95, Hierarchial Libraries provide an alternative to separate subprograms.  We'll learn about Hierarchial Libraries a little later.  Also, the function To_Upper in the Ada 95 package Ada.Characters.Handling is better than our function English_Upper_Case, because it handles accented letters.  We presented our function only to give a simple example that will work in both Ada 83 and Ada 95.

A procedure or function specification gives the name, mode, and type of each parameter.  A function specification also gives the type of the result.  The mode of the parameters can be in, out, or in out.  The subprogram may read from, but not write to, in parameters, and it may write to, but not read from, out parameters. (In Ada 95, it may read out parameters.)  If the mode is omitted, it's assumed to be in.  Thus, these two lines have the same effect:

   procedure Hanoi(N : in Natural; From, To, Spare : in Character);
   procedure Hanoi(N : Natural;    From, To, Spare : Character);

The parameters of a function must always be of mode in, never out or in out.

Note that when several parameters have the same mode and type, they can be placed in one list, separated by commas.  The lists themselves are separated by semicolons.  The two specifications above are equivalent to:

   procedure Hanoi(N : Natural; From: Character; To: Character;
                   Spare: Character);

In any event, the parameters in a call to a procedure or function are always separated by commas:

   Hanoi(5, 'A', 'B', 'C');

Question

  1. procedure P(A; B; C : in Integer);
  2. procedure P(A, B, C : Integer; D, E : in out Float) return Character;
  3. function F(A, B, C : Integer; D, E : in out Float) return Character;
  4. procedure P(A, B, C : Integer; D, E : in out Float);
Which one of the above is legal?

Recall that type conversion from Float to Integer in Ada rounds to the nearest integer.  (The Ada 83 standard doesn't specify which way rounding occurs when the fractional part is exactly 0.5; the Ada 95 standard specifies rounding away from zero in such cases.)  This function Floor computes the largest integer less than or equal to a given Float, always rounding toward negative infinity:

   function Floor(X : in Float) return Integer is
      Answer : Integer := Integer(X);
   begin
      if Float(Answer) > X then
         Answer := Answer - 1;
      end if;
      return Answer;
   end Floor;
Similarly, this function Truncate converts from Float to Integer, always truncating toward zero:
   function Truncate(X : in Float) return Integer is
      Answer : Integer := Integer(X);
   begin
      if Answer > 0 and Float(Answer) > X then
         Answer := Answer - 1;
      elsif Answer < 0 and Float(Answer) < X then
         Answer := Answer + 1;
      end if;
      return Answer;
   end Truncate;

In Ada 95, the attributes 'Floor, 'Ceiling, and 'Truncation, available for any floating point type, are better than the above functions.  If X is of type Float, then Float'Floor(X) is the largest integer <= X, Float'Ceiling(X) is the smallest integer >= X, and Float'Truncation always truncates toward zero.

Default Parameters

The in parameters of a subprogram specification may be given default values.  For example, here's a simplified version of the specification for the procedure Put in Ada.Integer_Text_IO (the actual specification can be found in Annex A.10.1 of the Ada 95 RM):

    procedure Put(Item  : in Integer;
                  Width : in Integer := 6;
                  Base  : in Integer := 10);

This means that, in calls to Put, the Width and Base parameters are optional.  If Width is omitted, it's assumed to be 6, and if Base is omitted, it's assumed to be 10.  If either of these parameters is given in the call, the default value is overridden.  (The default value for Width is shown here as 6.  Actually, it depends on the implementation of Ada.  Of course, the default value for Base is always 10.)

Default parameters let us make our Ada subprograms both flexible and easy to use.  In other languages, we'd often have to choose between these two qualities.  For example, suppose J is an integer. Here are some calls to Put:

 Put(J);
 Put(J, Width => 4);
 Put(J, Base => 16);
 Put(J, Base => 16, Width => 4);

The first parameter in each call could have been given as Item => J, but everyone remembers that the first parameter of Put is the item, so named notation seems unnecessary for this parameter.  However, Width and Base are used less frequently.  We used named notation for these parameters so the reader of our code wouldn't have to remember which parameter comes second and which comes third.  Note that if we omit the second parameter and specify the third, we must use named notation for the third parameter; we're not allowed to write Put(J, ,16); as in some languages.

If we were writing Put in another language, we'd have to choose either making the user specify the width and the base in every call (giving flexibility), or writing Put with only one parameter (giving ease of use).  In Ada, default parameters give us both flexibility and ease of use!

Ada.Text_IO.New_Line has one parameter, Spacing, defaulted to 1.  Thus, we can call New_Line; to get one CR-LF, or, for example, New_Line(3); to get three.

Default values may also be given in record definitions.  If we write

 type Month_Type is (Jan, Feb, Mar, Apr, May, Jun,
         Jul, Aug, Sep, Oct, Nov, Dec);
 subtype Day_Subtype is Integer range 1 .. 31;
 type Date is record
    Day   : Day_Subtype;
    Month : Month_Type;
    Year  : Integer := 1776;
 end record;
 USA : Date;
then USA.Year is set to 1776 when the line declaring USA is elaborated.  Every time an object of type Date is declared, its Year field is set to 1776.  However, there's a difference between default values in records and default parameters in subprograms.  We can't write USA := (4, Jul); all fields of a record must be specified in an aggregate.

Question

   procedure Put(Item  : in Integer;
                 Width : in Integer := 11;
                 Base  : in Integer := 10);
Which one of these is legal?
  1. Put(Item => 23, 5, 10);
  2. Put(23, 5)
  3. Put(23; 5; 10);

< prev   next >

Monday, August 27, 2012

AdaTutor - Outside Assignment 4

Exercise in Recursion

Your fourth Outside Assignment is to write, using recursion, a function specified by

    function Fib(N : in Positive) return Positive;

Fibonacci was a mathematician in the Middle Ages.  The so-called Fibonacci Series is a series of integers.&mnsp; Each number in the series is the sum of the two previous numbers.  The first two Fibonacci numbers are 1.

  N:    1  2  3  4  5  6   7   8   9  10  11   12   13   14   15   16 ...
Fib(N): 1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987 ...

Note that if N = 1 or N = 2, then Fib(N) = 1; otherwise, Fib(N) = Fib(N - 1) + Fib(N - 2).  Writing this function in Ada will be an easy and short assignment.  A test driver is provided in FIBTEST.ADA; a listing is on page 15 of your printed course notes.  As before, if all tests are passed, it displays "Congratulations, you completed the assignment!"  If there's an error, it displays the test case, the answer from your function, and the right answer.

A dummy solution is in FIB.DUM. As before, you shouldn't change the lines highlighted here:

    -- Dummy solution to Outside Assignment 4
separate (Fibtest) function Fib(N : in Positive) return Positive is begin
return 4;
end Fib;

The steps to follow for Outside Assignment 4 are similar to those of the last two Outside Assignments.  They're in your printed course notes on page 16:

  1. Copy FIB.DUM to FIB.ADA to make a copy of the dummy solution.  Also, compile the test driver FIBTEST.ADA. You need do this step only once.
  2. Edit FIB.ADA to become your real solution.  You may skip this step the first time through, to see error messages from the test driver.
  3. Compile FIB.ADA.  If the compiler finds errors, go back to step 2.
  4. Link with the name of the main program Fibtest.  Then execute.  If the test driver displays error messages, go back to step 2.
  5. When the message "Congratulations, you completed the assignment!" is displayed, you'll have a chance to compare your solution with ours.

Please exit AdaTutor temporarily, and try Outside Assignment 4.  Work at your own pace; there's no deadline. Good luck!

Congratulations on Completing Outside Assignment 4!

Our solution to Outside Assignment 4 (in FIB.ANS):

< prev   next >

Sunday, August 26, 2012

AdaTutor - Recursion

Recursion

Ada procedures and functions may call themselves, directly or indirectly.  This process is called recursion.  While recursion often uses a little extra memory and execution time, for certain types of problems it pays large dividends in program simplicity.  That's a very worthwhile exchange!

For example, let's write a function to compute the factorial of a positive integer.  The factorial of an integer is the product of all the integers from that number down to one.  Thus, Factorial(5) = 5 * 4 * 3 * 2 * 1 = 120. Although we could easily write this function with a for loop, we'll use recursion instead.  Note that if N = 1, then Factorial(N) = 1; otherwise, Factorial(N) = N * Factorial(N - 1).

   function Factorial(N : in Positive) return Positive is
      Answer : Positive := 1;
   begin
      if N > 1 then
Answer := N * Factorial(N - 1);
end if; return Answer; end Factorial;

The highlighted line shows where this function calls itself.  Recursive subprograms always call themselves conditionally; otherwise the program would run out of memory, no matter how large the machine.  Here the recursive call is inside an if block.

Note that Answer is initialized to 1.  If the function is called with N = 1, the if statement is False, Answer isn't modified, and 1 is returned as the value of the function.  If the function is called with N = 2, the if statement is True, and the highlighted line is executed.  The machine starts to compute the expression as 2 * ..., and then Factorial is called with N = 1.  It's as if the machine made another copy of the code for Factorial and called that.  Actually there's only one copy of the code, but the machine maintains multiple pointers to it.

When the recursive call is made, the system allocates additional memory for new versions of any local variables like Answer.  Also, the parameters like N are separate for each recursive call.

Suppose the calling program calls Factorial with N = 2.  Then, in computing the expression, Factorial calls itself with N = 1.  In this second call, a new local variable Answer is created, separate from the one in the first call.  Also, parameter N is 1 in the second call, but 2 in the first call.  In the second call, the if statement is False, and 1 is returned.  In the first call, the calculation of the expression is completed, using the value 1 returned by the second call.  Thus, Answer becomes 2 * 1 = 2, and the first call returns the answer 2 to the calling program.

If the calling program calls Factorial with N = 3, the function starts to compute the expression as Answer := 3 * ..., and calls Factorial with N = 2.  In this second call, the function starts to compute Answer := 2 * ..., and calls Factorial with N = 1.  In this third call, the if statement is False, and the answer 1 is returned to the second call.  The second call finishes the computation of the expression Answer := 2 * 1, and returns the answer 2 to the first call.  Finally, the first call finishes computing the expression with Answer := 3 * 2, and returns the answer 6 to the calling program.

This simple function wouldn't have been complicated even without recursion.  In a moment we'll discuss the Tower of Hanoi problem.  The recursive solution is very simple, but a solution without recursion would be very complicated indeed.


Question

In this question, function A calls B, and B conditionally calls A. The specification of function B is given early so that A can call it.
   function B (I : in Integer) return Integer;

   function A (I : in Integer) return Integer is
   begin
      return B(I - 1) + 1;
   end A;

   function B (I : in Integer) return Integer is
      Ans : Integer := 0;
   begin
      if I > 0 then
         Ans := A(I);
      end if;
      return Ans;
   end B;
If the main program calls function A with a parameter equal to 2, what value will A return: 0, 1, 2, or 3? You may need pencil and paper to figure this one out.

The Tower of Hanoi Problem

The "Tower of Hanoi" is a solitaire puzzle that was named when Hanoi was the capital of a free country: French Indochina.  There are three pegs labeled A, B, and C; one of them has a tower of N doughnut-shaped disks of decreasing size, like this:


          |                    |                    |
          |                    |                    |
         =|=                   |                    |
        ==|==                  |                    |
       ===|===                 |                    |
      ====|====                |                    |
     =====|=====               |                    |
  -----------------    -----------------    -----------------
          A                    B                    C

The object is to move the entire tower from one peg to another, say, from A to B.  Only one disk may be moved at a time, and a larger disk may never be placed on top of a smaller one.  The shortest solution to the puzzle with N disks requires 2**N - 1 moves.

For example, we can move five disks from A to B with the following 31 moves: (Read them from left to right, not in columns.)

A to B, A to C, B to C, A to B, C to A, C to B, A to B, A to C, B to C, B to A, C to A, B to C, A to B, A to C, B to C, A to B, C to A, C to B, A to B, C to A, B to C, B to A, C to A, C to B, A to B, A to C, B to C, A to B, C to A, C to B, A to B.


          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
         =|=                   |                    |
      ====|====                |                    |
     =====|=====            ===|===               ==|==
  -----------------    -----------------    -----------------
          A                    B                    C
                    (The Puzzle After the First Five Moves)

Writing a program to display this series of moves would be very complicated without recursion.  Let's develop a recursive solution; we'll see that the resulting Ada program is surprisingly simple!

When we developed a recursive solution for the Factorial function:

          if N = 1,  Factorial(N) = 1
          otherwise, Factorial(N) = N * Factorial(N - 1)
we expressed Factorial(N) in terms of Factorial(N - 1), and gave the trivial solution for N = 1.  The Ada program was easily written from the above.

For the Tower of Hanoi problem, let's develop a solution for N disks in terms of a solution for N - 1 disks.  Suppose we want to move five disks from A to B, using C as a spare peg.  We first move four disks from A to C, then move one disk from A to B, and finally move four disks from C to B.  In general, to move N disks from a source peg to a destination peg, we first move N - 1 disks from the source to the spare, then move one disk from the source to the destination, and finally move N - 1 disks from the spare to the destination.

To move the one disk from the source to the destination, our program will simply display the move.  To move N - 1 disks, the program will call itself.  The solution for zero disks is trivial indeed: the program will do nothing!

The following program is extremely simple: three executable statements inside an if block.  Yet it can display a very complicated series of moves!

with Ada.Text_IO; use Ada.Text_IO;
procedure Hanoi(N : in Natural; From, To, Spare : in Character) is
begin
   if N > 0 then
      Hanoi(N - 1, From, Spare, To);
      Put_Line(From & " to " & To);
      Hanoi(N - 1, Spare, To, From);
   end if;
end Hanoi;

To move five disks from A to B, using C as a spare, we would call Hanoi(5, 'A', 'B', 'C'); and the program would display the 31 moves.

Note that when Hanoi is called with N = 0, it does nothing.  When called with N = 1, the if statement is true, and the three lines within the if block are executed.  But the first and third lines do nothing, because they call Hanoi with N = 0.  The second line displays, for example, A to B.

When called with a larger value of N, the first line within the if block moves N - 1 disks from the source to the spare peg.  The second line displays the move of one disk from the source to the destination, and the third line moves N - 1 disks from the spare peg to the destination.

Most implementations of Ada won't allow Hanoi to be a main program, because it has parameters.  A short main program to call Hanoi is shown here.  A slightly longer program could get N and the names of the three pegs from the user.  In this example, procedure Demo withs a previously compiled procedure rather than a previously compiled package.  We never write a use clause for a procedure or a function, because dot notation doesn't apply, as it does for packages.

with Hanoi;
procedure Demo is
begin
   Hanoi(5, 'A', 'B', 'C');
end Demo;

In summary, our first example of recursion, Factorial, was very simple.  However, that program would have been simple even without recursion.  Our second example, Hanoi, also was very simple, but the program would have been quite complicated without recursion.

Our fourth Outside Assignment will be to write a Fibonacci function Fib, using recursion.  As with Factorial, this function would be easy to write even without recursion.  However, as an exercise we'll write it using recursion.

< prev   next >

Tuesday, August 21, 2012

AdaTutor - Outside Assignment 3

Exercise in Records

Your third Outside Assignment is to write a function specified by
   type Month_Type is (Jan, Feb, Mar, Apr, May, Jun,
                     Jul, Aug, Sep, Oct, Nov, Dec);
   subtype Day_Subtype is Integer range 1 .. 31;
   type Date is record
      Day   : Day_Subtype;
      Month : Month_Type;
      Year  : Integer;
   end record;
   function Tomorrow(Today : in Date) return Date;

Given any date, Tomorrow should return the following date.  Your function will be tested only with legal dates.  As with Outside Assignment 2, a test driver is already written; it's in NEXTDATE.ADA.  A listing is on page 13 of your printed course notes, but you needn't understand the test driver.  If your function fails any test, you'll see the test case, the answer from your function, and the right answer.  Otherwise, you'll see "Congratulations, you completed the assignment!"

The definitions of Month_Type, Day_Subtype, and Date are in the test driver; you shouldn't define them inside your function.  A dummy solution is in TOMORROW.DUM; it looks like this:

   -- Dummy solution to Outside Assignment 3
separate (Nextdate) function Tomorrow(Today : in Date) return Date is begin
return Today;
end Tomorrow;

Again, you'll probably want to remove or change the comment line, and you shouldn't change the lines highlighted above.  You may, but don't have to, include Answer : Date; in the declarative region and make return Answer; the last statement before end Tomorrow;.

Normally, years divisible by 4 are leap years.  But if a year is divisible by 100, it must also be divisible by 400 to be a leap year.  Thus, 2000 is a leap year, but 1900 and 2100 are not.  Note that Today.Year is divisible by 4 if and only if Today.Year mod 4 = 0.  You may assume that Today.Year will always be between 1583 and 3999, because outside this range the calendar gets more complicated.

The steps to follow for Outside Assignment 3 are very similar to those of Outside Assignment 2.  They're in your printed course notes on page 14:

  1. Copy TOMORROW.DUM to TOMORROW.ADA to make a copy of the dummy solution.  Also, compile the test driver NEXTDATE.ADA.  You need do this step only once.
  2. Edit TOMORROW.ADA to become your real solution.  You may skip this step the first time through, to see error messages from the test driver.
  3. Compile TOMORROW.ADA.  If the compiler finds errors, go back to step 2.
  4. Link with the name of the main program Nextdate.  Then execute. If the test driver displays error messages, go back to step 2.
  5. When the message "Congratulations, you completed the assignment!" is displayed, you'll have a chance to compare your solution with ours.

There are many ways to solve this problem.  In our solution we declared an array of Day_Subtype with subscripts of type Month_Type.  Some students use a case construct on Today.Month; some use an if block with elsifs.

This assignment should be a simple exercise in records.  Our solution fits on one screen.  If your solution starts to get long and difficult, you should think the problem through again.  Don't try to save the computer a few microseconds; computers are supposed to save people time.  Instead, minimize the complexity of the program to save yourself programming effort!

Remember that an entire record can be assigned in one statement.  Also, try to calculate the number of days in the month and then test for end of month and end of year in only one place.  This is better than having several blocks of code testing for end of month and end of year in three or four different places in your program.  One last hint: remember that Month_Type'Succ(Today.Month) will raise a Constraint_Error if Today.Month is Dec.

Please exit AdaTutor temporarily, and try Outside Assignment 3.  Work at your own pace; there's no deadline. Good luck!

Congratulations on Completing Outside Assignment 3!

Our solution to Outside Assignment 3 (in TOMORROW.ANS):

< prev   next >

AdaTutor - Records and Arrays (2)

Multidimensional Arrays

Ada arrays may have any number of dimensions, and the subscripts may be of different discrete types.&nsp; For example, assuming Rainbow_Color, Month_Type, and Date have already been defined, we can write

    X : array(Integer       range -10 .. -1,
              Rainbow_Color range Orange .. Blue,
              Month_Type    range Feb .. Jun     ) of Date;

Here the first subscript is of type Integer and has 10 possible values, the second subscript is of type Rainbow_Color and has four possible values, and the third subscript has type Month_Type with five possible values.  Thus we have a three-dimensional array of 10 * 4 * 5 = 200 Dates.  One element of the array might be X(-5, Green, Apr); one field of that element might be X(-5, Green, Apr).Year.  The array in this example probably has no use, other than demonstrating that multiple subscripts need not have the same type.

If one subscript of a multidimensional array type is constrained, they must all be constrained.  We can't write

  -- illegal
  type Rectangle is array(1 .. 5, Integer range <>) of Float;

Multidimensional arrays are initialized or assigned with nested aggregates.  We can create a two-dimensional array of Floats, initializing all 50 elements to 1.0, with Mat : array(0 .. 9, 1 .. 5) of Float := (others => (others => 1.0));.

Here X is a 10-by-10 array of Integers.  All elements are 0, except X(4, 5), which is 1. We qualify the aggregate because others follows named notation:

    type Square10 is array (1 .. 10, 1 .. 10) of Integer;
    X : Square10 := Square10'(4      =>  (5 => 1, others => 0),
                              others =>  (others => 0));

We initialize or assign an array of arrays with nested aggregates, the same as a multidimensional array.  However, we reference a single element differently:

    type Square10 is array(1 .. 10, 1 .. 10) of Integer;
    type Row10    is array(1 .. 10) of Integer;
    type Mat10    is array(1 .. 10) of Row10;
    -- S is a two-dimensional array.
    S : Square10 := (others => (others => 0));
    -- M is an array of arrays.
    M : Mat10    := (others => (others => 0));
    ...
    S(4, 5) := 1; -- a single element of a two-dimensional array
    M(4)(5) := 1; -- a single element of an array of arrays

The "short circuit" forms can prevent us from using array subscripts that are out of range.  For example, if we write

    A : array(1 .. 10) of Float;
    I : Integer;
    ...
    if I in A'Range and then A(I) = 0.0 then
        -----;
        -----;  (block of code)
        -----;
    end if;
then we know the program won't try to evaluate A(I) when I is outside the range 1 to 10.

Question

Whihc one of these is illeagel?
  1.     subtype Day_Subtype is Integer range 1 .. 31;
        type Group is array(Day_Subtype) of Float;
        Gr : Group;
        ...
        Gr(3) := 0.0;
    
    
  2.     type List is array(1 .. 10) of Integer;
        type Page is array(1 .. 20) of List;
        Pg : Page;
        ...
        Pg(5)(10) := 0;
    
  3.     type Row is array (Integer range <>) of Integer;
        R1 : Row;
        ...
        R1(1) := 0;
    

Strings

There's a very important array type declaration built into the Ada language.  As with types Boolean and Character, and subtypes Positive and Natural, this definition comes with Ada and shouldn't be repeated in our programs:

    type String is array(Positive range <>) of Character;
(In Ada 95, type Wide_String is similarly defined as an array of Wide_Character.)  Thus we can declare, for example, S : String(1 .. 5);.  We can't simply write S : String; because we can't declare unconstrained array objects.  (We can declare S : constant String := "Hello"; and in Ada 95, we may write S : String := "Hello"; because the compiler will translate this to S : String(1 .. 5) := "Hello";).  Note that String isn't a special type in Ada; it's just an array of Characters.  Everything we learned about arrays applies to Strings.  For example, we can assign to S using the same syntax that we use when assigning to an array of any other type.  If we write S : String(1 .. 5); we can write:
    S := ('H', 'e', 'l', 'l', 'o');

However, this notation is clumsy, so Ada allows us to abbreviate an array of Character constants using double quotes.  Thus S := "Hello"; is equivalent to the statement above.  If a quotation mark appears inside the string, it must be doubled.  Thus Ada.Text_IO.Put_Line("a ""big"" man"); will display a "big" man.

It may seem disappointing that Ada Strings have fixed length, and that we can't declare a variable S : String;.  Fortunately, Ada 95 comes with several string-handling packages to simulate variable-length strings; see Annex A of the Ada 95 RM.  The name of the Ada 95 package that provides "Unbounded-Length String Handling" is Ada.Strings.Unbounded, described in Annex A.4.5 of the Ada 95 RM.

Also, later we'll learn how to define our own type Text to get around this restriction and simulate variable-length Strings even in Ada 83.

When arrays are assigned, the lengths must be the same on both sides of the :=, and the types must be the same, but the subscripts needn't be the same.  For example, if we have

    type Vector is array(Integer range <>) of Float;
    V1 : Vector(1 .. 5);
    V2 : Vector(2 .. 6) := (others => 0.0);

    S1 : String(1 .. 5);
    S2 : String(2 .. 6) := (others => ' ');
then we can write V1 := V2; and S1 := S2; even though the subscripts are different, because the array lengths are the same and the element types are the same.  But we'll get a Constraint_Error if we write S1 := "Hello there"; or S1 := "Hi"; or V1 := (1.0, 2.0, 3.0);, because these arrays have wrong lengths.  Ada won't automatically truncate Strings or pad with blanks.  Of course, it would be easy to write our own procedure to assign Strings of different lengths, padding or truncating as necessary.

A slice of an array is a portion of an array, and is indicated with a range in the subscript.  A slice is itself an array.  Some languages use the term "substring" to refer to a slice of a String, but in Ada we can take a slice of any kind of array, not just an array of Characters.  So instead of "substring," Ada uses the more general term "slice."  For example, if we have

   A : array(1 .. 10) of Integer := (1, 2, 3, 4, 5,
         6, 7, 8, 9, 10);
then A(1 .. 3) is the array (1, 2, 3) and A(6 .. 9) is the array (6, 7, 8, 9).  Similarly, if we have S : String(1 .. 11) := "Hello there"; then S(8 .. 11) is "here" and S(4 .. 5) is "lo".  We can also write S(1 .. 10) := S(2 .. 11); and A(1 .. 3) := A(4 .. 6); since the lengths are the same on both sides.

If the value preceding .. is greater than the value following it, we have a null range.  A slice with a null range has a length of zero, and is called a null slice.  In the case of a null slice, the subscript is not checked for Constraint_Error.  Thus, even if N is 0 we could write S(1 .. N); which would produce the null string "".  This is legal, even though Ada defines "type String is array(Positive range <>) of Character;".  Assigning a null slice to a null slice does no harm and generates no error; it does nothing.  Also, if S is a null array, then S'Length is 0, and S'First and S'Last don't exist.  Using 'First or 'Last with a null array will raise a Constraint_Error.

Beginners sometimes confuse a Character with a String of length 1.  If we write

    S : String(1 .. 10);
    I : Integer := 5;
then S(I) is a Character and S(I .. I) is a String of length 1.  Also, 'X' is a Character while "X" is a String of length 1.  Thus we could write
    S(I) := 'X';
    S(I .. I) := "X";
but we'd be mixing types if we were to write S(I) := "X"; or S(I .. I) := 'X';.

Fortunately, Ada.Text_IO has a Put for type Character as well as a Put for type String.  (It also has a Get for each of these types.)  Thus we can write either Put(S(I .. I)); or Put(S(I));.  However, Put_Line and Get_Line exist only for Strings, not for Characters.  We'll learn about Ada.Text_IO in more detail later.


Question

  1. Hello : String;
  2. Digit : String(0 .. 9) := "0123456789";
  3. Line : String(1 .. 80) := (others => "*");
  4. Hello : String(2 .. 6) := "Hello";
  5. Hello : String(1 .. 5) := (1 .. 3 => "Hel", 4 => 'l', 5 => 'o');
  6. Prompt : String(1 .. 3) := ">";
  7. Hello : String(1 .. 5) := 'Hello';
Which one of the above is legal?

Array Operators

The operator & concatenates any two arrays of the same type, including two Strings.  It can also concatenate a single element with an array of that element type, or two single elements into an array of length two.  For example, every use of & below is legal:

    C, D : Character := '*';
    S2   : String(1 .. 2);
    S3   : String(1 .. 3) := (others => ' ');
    S5   : String(1 .. 5);

    type Vector is array(Integer range <>) of Float;
    F, G : Float := 1.2;
    V2   : Vector(1 .. 2);
    V3   : Vector(1 .. 3) := (others => 0.0);
    V5   : Vector(1 .. 5);
    ...
    S2 := C & D;  S5 := S2 & S3;  S3 := C & S2;  S3 := S2 & C;
    V2 := F & G;  V5 := V2 & V3;  V3 := F & V2;  V3 := V2 & F;

The operators and, or, xor, and not, defined for Booleans, are also defined for one-dimensional arrays of Boolean.  They operate element by element on the arrays.  Thus, we can simulate sets in Ada.  For example, if we write

    type Set_Of_Chars is array(Character) of Boolean;
    S1 : Set_Of_Chars := Set_Of_Chars'('*' | '#' => True,
                                      others => False);
    S2 : Set_Of_Chars := Set_Of_Chars'('*' | '?' => True,
                                      others => False);
then S1 or S2 is Set_Of_Chars'('*' | '#' | '?' => True, others => False), and S1 and S2 is Set_Of_Chars'('*' => True, others => False).

The operators = and /= can compare two records or two arrays of the same type.  Records are equal if all of their corresponding fields are equal, arrays, if all of their corresponding elements are equal.  Arrays of different lengths are always unequal.  The four remaining relational operators can compare two arrays of the same type.  They're compared element by element until a difference is found.  For example, if we have

    S : String(1 .. 6) := "to all";
    T : String(1 .. 7) := "to Bill";
then S > T because 'a' > 'B' in Ada's definition of type Character.

< prev   next >

Saturday, August 18, 2012

AdaTutor - Records and Arrays (1)

Records

A record lets us group several declarations together and refer to them as one:

   type Month_Type is (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug,
                       Sep, Oct, Nov, Dec);
   subtype Day_Subtype is Integer range 1 .. 31;
   type Date is
    record
      Day   : Day_Subtype;   -- Naturally, Day_Subtype and
      Month : Month_Type;    -- Month_Type must be defined
      Year  : Integer;       -- before type Date is defined.
    end record;
   USA : Date;

In this example, USA has three parts (called "fields"): USA.Day, USA.Month, and USA.Year.  The fields of a record can be of any type, including other records.  Here USA.Day is of type Integer, USA.Month is of type Month_Type, and USA.Year is of type Integer.  The fields of USA may be referenced separately:

      USA.Day   := 4;
      USA.Month := Jul;
      USA.Year  := 1776;

However, USA can also be referenced as one object.  For example, we could have assigned all three fields in one statement: USA := (4, Jul, 1776);.  Here the object on the left is of type Date, and the object on the right is called an aggregate.  The aggregate fits the type Date because it contains an Integer, a Month_Type, and another Integer.  This aggregate is said to use positional notation because its three parts appear in the same order as the three parts of the record definition: first Day, then Month, then Year.

We can specify the parts of an aggregate in any order if we use named notation:USA := (Month => Jul, Day => 4, Year => 1776);.  (The symbol => is read "arrow" and may not contain a space.)  Using named notation often improves program readability, especially if the names of the fields are well chosen.

We can switch from positional to named notation in an aggregate.  But once we use named notation, the compiler loses track of position, so we can't switch back to positional.  For example, the following is legal:

      USA := (4, Year => 1776, Month => Jul);

But the following is illegal because positional notation can't follow named:

      USA := (4, Year => 1776, Jul); -- illegal

Record discriminants, record variants, and tagged records will be discussed in the section on More Records and Types.

Question

  procedure Record_Exercise is
    type Month_Type is (Jan, Feb, Mar, Apr, May, Jun,
                        Jul, Aug, Sep, Oct, Nov, Dec);
    subtype Day_Subtype is Integer range 1 .. 31;
    type Date is
      record
        Day   : Day_Subtype;
        Month : Month_Type;
        Year  : Integer;
      end record;
    D1, D2, D3 : Date;  -- 1
  begin
    D1       := (Month => Jan, Day => 22, Year => 1983);  -- 2
    D2.Day   := 22;
    D2.Month := 1;  -- 3
    D2.Year  := 1983;
    D3       := D2;  -- 4
  end Record_Exercise;
Which commented line in the above program is illegal?
1
2
3
4

Arrays

To declare an array in Ada, we specify the type and range of the subscript, followed by the type of the elements of the array.  The subscript can have any discrete type (integer or enumeration), and the elements of the array can be of any type at all, including records and other arrays.  There are three ways to declare an array in Ada.  Here are three examples of the most direct, but least flexible, way (types Rainbow_Color and Date must be defined earlier):

 A : array(Rainbow_Color range Orange .. Blue) of Date;
    -- A four-element array, each element of which is a record
    -- with three parts.  The allowable subscripts are Orange,
    -- Yellow, Green, and Blue.  Here A(Yellow) is of type Date,
    -- and A(Yellow).Year is of type Integer.
 B : array(Integer range -10 .. 10) of Integer;
    -- An array of 21 Integers, with Integer subscripts.
 C : array(0 .. 30) of Float;
    -- Here (0 .. 30) is understood to mean
    -- (Integer range 0 .. 30), and we have an array of 31
    -- Floats, with Integer subscripts.

A subscript can be an expression; if I is an Integer, we can write C(2*I). If a subscript is out-of-range (for example, A(Red) or C(-32)), the program will raise a Constraint_Error.

This direct method of declaring arrays is usually used to create single arrays for table lookup, etc., where there's no need to have several arrays of the same type.  A better way to declare an array is to specify a type name for the array itself. Then several objects can be declared to have that same type.  For example,

      type Vector100 is array(1 .. 100) of Float;
      type Vector300 is array(1 .. 300) of Float;
      D, E, F : Vector100;
      G, H    : Vector300;

Here D, E, and F are all of type Vector100, so we can write D := E; and assign the entire array with one statement.  Similarly, we can write G := H;, but not G := F;, because G and F have different types.

An even more flexible way to declare arrays is to leave the range of the subscript unspecified with the box symbol, <>, specifying the range when declaring the objects.  For example,

      type Vector is array(Integer range <>) of Float;
      D, E, F : Vector(1 .. 100);
      G, H    : Vector(1 .. 300);

There are two errors to avoid when declaring arrays in this way.  One is to declare a type with the box symbol for the range of the subscript, and then fail to specify the range when declaring a variable:

      type Vector is array(Integer range <>) of Float;
      D1 : Vector; -- illegal

This error is called unconstrained array.  Unconstrained arrays are legal in formal parameters ("dummy arguments") of procedures and functions, and a function can return an unconstrained array type.  (We'll learn about these things later.)  But an unconstrained array is illegal when declaring a variable, because the compiler needs to know the range of the subscript.

In Ada 95, we may constrain the variable array by initializing it:

      D1 : Vector := (2.3, 4.5, 4.0); -- legal in Ada 95 only

Here the compiler assumes the range of the subscript to be 1 .. 3. In Ada 83, however, we must specify the subscript range of a variable explicitly:

      D1 : Vector(1 .. 3) := (2.3, 4.5, 4.0); -- legal

In both Ada 83 and Ada 95, a constant array, which must be initialized, is automatically constrained.  Therefore, the following is legal in both Ada 83 and Ada 95, and the compiler will assume the subscript range to be 1 .. 3:

     D1 : constant Vector := (2.3, 4.5, 4.0); -- legal 

The other error to avoid when declaring arrays in this way is to specify the range of the subscript twice: once when declaring the type and once when declaring the object:

      type Vector100 is array(1 .. 100) of Float;
      D2 : Vector100(1 .. 100);  -- illegal

Even if the two ranges agree, this is illegal and is called doubly constrained array.

Arrays may be initialized and assigned with aggregates, and both positional and named notation may be used.  For example, arrays A and B are equal here:

    type Vector5 is array(1 .. 5) of Float;
    A : constant Vector5 := (2.0, 4.0, 8.0, 16.0, 32.0);
    B : constant Vector5 := (1 => 2.0, 2 => 4.0, 3 => 8.0,
                             4 => 16.0, 5 => 32.0);

The aggregate must fill the whole array, but the reserved word others is available.  Here's an array of 500 Float variables, all initialized to 0.0:

    type Vector500 is array(1 .. 500) of Float;
    V1 : Vector500 := (others => 0.0);

If others follows named notation, it's best to qualify the aggregate with the type name.  Here W(10) = 1.3, W(15) = -30.7, and the rest of the array is 0.0:

    W : Vector500 := Vector500'(10 => 1.3,  15 => -30.7,
                                others => 0.0);

Sometimes we must qualify an aggregate when others is used with named notation; at other times it's optional.  The rules ( Ada 95 RM section 4.3.3, paragraphs 10-15) are complicated.  It's easiest always to qualify an aggregate when others follows named notation, as shown above.

In array aggregates, multiple choices can be denoted with the vertical bar (|), shift-backslash on PC keyboards.  In this array, the elements with odd subscripts are True, while the elements with even subscripts are False:

    type Decade is array(1 .. 10) of Boolean;
    D1 : Decade;
    ...
    D1 := Decade'(1 | 3 | 5 | 7 | 9 => True,  others => False);

Here we assigned to D1 with an executable statement for variety; we could also have initialized D1 in the declarative region with the same aggregate.  Some people read the vertical bar as "and," others as "or."  One can say, "Elements 1, and 3, and 5, and 7, and 9 are True," or one can say, "If the subscript is 1, or 3, or 5, or 7, or 9, the array element is True."


Question

 with Ada.Text_IO, Ada.Integer_Text_IO;
 use Ada.Text_IO, Ada.Integer_Text_IO;
 procedure Array_Quiz is
   subtype Unaccented_Cap_Letter is Character range 'A' .. 'Z';
   type Set_Of_Unaccented_Letters is
      array(Unaccented_Cap_Letter) of Boolean;
   Vowels : Set_Of_Unaccented_Letters :=
       Set_Of_Unaccented_Letters'('A'|'E'|'I'|'O'|'U' => True,
                                  others => False);
   Letter : Unaccented_Cap_Letter;
 begin
   Letter := 'E';
   Put(Boolean'Pos(Vowels(Letter)));
 end Array_Quiz;
What will this program display?
  1. The program will display 1.
  2. The program will display 2.
  3. The program will display TRUE.
  4. The program will display E.

In an array declaration or an array type declaration, we may totally omit the range of the subscript (not even supplying a box), if the type or subtype of the subscript has a reasonable number of possible values.  (We did that in the declaration of type Set_Of_Unaccented_Letters in the last question.)  For example, in

  type Rainbow_Color is (Red, Orange, Yellow, Green, Blue, Indigo,
                         Violet);
  R : array(Rainbow_Color) of Float;

we have an array of seven Floats, because there are seven possible values of type Rainbow_Color.  Similarly,

    V : array(Character) of Boolean;
creates an array of 256 Booleans (128 in Ada 83).  However, J : array(Integer) of Float; is an attempt to declare a very large array indeed!  In a case like this, we can use a subtype in the subscript declaration.  The following creates an array of 31 Floats:
    subtype Day_Subtype is Integer range 1 .. 31;
    J : array(Day_Subtype) of Float;

The attributes 'First and 'Last, which we've seen with discrete types, can also be used with array types and with the array names themselves.  For example,

    type My_Vector is array(30 .. 33) of Integer;
    Mv : My_Vector;
    ...
    Mv(30) := 1000;
    Mv(31) := 20;
    Mv(32) := -70;
    Mv(33) := -500;

Here Mv'First and My_Vector'First are both 30.  Mv'Last and My_Vector'Last are both 33.  Note that 'First and 'Last refer to the subscripts, not to the values of the array elements.  Thus Mv'First is not 1000.  To obtain the value of the first element, we would use Mv'First as a subscriptMv(Mv'First) is 1000.

The attribute 'Range is an abbreviation for 'First .. 'Last.  It can be used with array types and array names, and (in Ada 95 only), with scalar types.  Thus Mv'Range and My_Vector'Range both mean 30 .. 33.  In Ada 95, we can write Integer'Range as an abbreviation for Integer'First .. Integer'Last.  The attribute 'Length is also available: Mv'Length and My_Vector'Length are both 4.

< prev   next >