CS 214 Lab 11: Ada

Begin by making an ada subdirectory in labs/11. Then copy the files Makefile, max.adb, list_package.ads, and list_package.adb from the course labs/11/ada directory into your new directory. Use a text editor to open these files, and take a moment to study their contents. Note that list_package.ads contains declarations for, and list_package.adb contains definitions for some list operations, including Init(), Empty(), Length() and Append(). Study these definitions carefully, to get a sense for what "data members" our List type needs to provide...

Declaring An Ada List Type. In 2005, Ada added a library Ada.Containers that provides doubly-linked lists, sets, maps, and vectors. However, since Ada has no singly-linked list type, we will build our own.

The file list_package.ads contains a public declaration of the name List, whose implementation details we must supply in the private section of the package.

Since a list consists of linked nodes, we might begin by creating a List_Node aggregate type that stores an integer and a pointer to a List_Node: 


   type List_Node is
          record
           Its_Value : Integer;
           Its_Next : Node_Ptr;
          end record;
Our first problem is how to declare the pointer field. Since the Ada type system uses name equivalence to determine compatibility, we need to create a named type to declare this field. In Ada, the keyword access is used to denote a pointer type, so we can precede the declaration of List_Node with the declaration: 

   type Node_Ptr is access List_Node;
This solves our first problem, but creates a second problem: the identifier List_Node is now being used before it is declared, which is illegal in Ada. But if we place the declaration of Node_Ptr after the declaration of List_Node, then Node_Ptr will not be declared within our record.

To solve this problem, Ada provides a forward declaration mechanism. More precisely, we can precede our declaration of Node_Ptr with a partial declaration of List_Node: 


   type List_Node;
and then provide the full declaration of List_Node after the declaration of Node_Ptr. This declaration is sufficient to inform the Ada compiler that List_Node is a type, which is all it needs at this point.

Note that our List_Node type is wholely declared in the private section of the package, keeping it inaccessible to programs that use the package.

Now that we have implemented the nodes that will make up our list, we are ready to implement the list itself.

Our List has 3 "data members": first, two pointers:

plus an integer Its_Length to store the number of values in the list. Using this information, add a List declaration to the appropriate place in list_package.ads.

Note that while the name List is declared as a type in the public section of the class, it is declared as a private type; and its implementation details are "hidden" in the private section of the package. This allows a program that uses the package to use the name List, but prevents such a program from accessing any of the implementation details of the List type. This is in keeping with the information hiding goal of modularity.

Defining List Objects. Switch for a moment to max.adb and note that

  1. it uses our List_Package,
  2. it illustrates the definition of a List object, and
  3. it illustrates the use of (some of our) provided List operations.
Note in particular that since Ada provides no constructor mechanism, we must explicitly call our Init() procedure to initialize the "data members" of each List object.

Take a moment to build the project, to make sure that this much is syntactically correct. Continue when your project builds successfully.

Defining a Print Procedure. To display the values in a List, we must write a subprogram that traverses the list, displaying each of its values in turn. Move to list_package.adb and scan through its contents, until you reach the documentation for the Put() procedure. We can begin by creating a stub procedure named Put(), that satisfies the specification given in the introduction to this exercise: 


   procedure Put(A_List : in List) is
   begin 
   end Put;
To fill in this stub, we can use the following algorithm to traverse the List: 
   1. Initialize a Node_Ptr named Temp_Ptr to the address of the first node.
   2. While Temp_Ptr is not null:
       a. Display the value of Temp_Ptr's node.
       b. Advance Temp_Ptr to the next node.
To implement our algorithm, we need to learn about Ada pointers.

Ada uses the normal assignment operator for pointer assignments: 

   PointerAssignment ::=   identifier := Expression
where identifier is a pointer variable, and Expression is an expression yielding a pointer value.

As illustrated by the already-defined List operations, a "data member" or field of an Ada aggregate can be accessed through a pointer using the normal "dot" (.) operator: 

   Expression        ::=   identifier.identifier
where the first identifier is a pointer to an aggregate, and the second identifier is a field within that aggregate. Using this information, we can declare Temp_Ptr, and initialize it to the address of the first node in A_List: 
   procedure Put(A_List : in List) is
     Temp_Ptr : Node_Ptr := A_List.Its_First;
   begin 
   end Put;
To perform step 2 of our algorithm, we can use Ada's pretest loop, and test the value of Temp_Ptr against the Ada keyword null. We can thus construct a loop to traverse our List: 
   procedure Put(A_List : in List) is
     Temp_Ptr : Node_Ptr := A_List.Its_First;
   begin 
     while Temp_Ptr /= null loop
     end loop;
   end Put;
(Note that we can use the relational /= operation to compare pointers and correctly encode the loop condition.)

Within this loop, we can add statements to display the value of the Its_Value field of the node pointed to by Temp_Ptr, and to change the value of Temp_Ptr to the value of the Its_Next field of the node to which Temp_Ptr points: 

   procedure Put(A_List : in List) is
     Temp_Ptr : Node_Ptr := A_List.Its_First;
   begin 
     while Temp_Ptr /= null loop
        Put(' '); Put(Temp_Ptr.Its_Value);
        Temp_Ptr := Temp_Ptr.Its_Next;
     end loop;
   end Put;
That completes the implementation of our algorithm.

In max.adb, uncomment the calls that Put() the three lists. Then build and run your program, and verify that this much works correctly before continuing.

Finding the Maximum of a List. If necessary take a moment to review the specification for this operation. To find the maximum value in a list, we can use this algorithm: 

   1. Initialize a Node_Ptr named Temp_Ptr to the address of the first node in A_List.
   2. Initialize Max_Value to a very negative integer (e.g., -999999).
   3. While Temp_Ptr is not null:
       a. If the value of Temp_Ptr's node is greater than Max_Value,
             Change Max_Value to the value of Temp_Ptr's node.
       b. Advance Temp_Ptr to the next node.
   4. Return Max_Value.
Using everything you have learned thus far, define an Ada function that implements this algorithm.

Declaring the Operations. When you have your operations defined, use copy-paste to copy the first line of each new operation from list_package.adb to the appropriate place in list_package.ads. Then replace the word is with a semicolon, to convert that line into a declaration of the operation.

Testing. Uncomment the final three statements that invoke the Max() function. To test its correctness, build and run your program, and verify that your code is working correctly.

Experiment. What happens if your program (max.adb) tries to declare a Node_Ptr in order to access the fields of a List_Node directly? Add some code at the end of your program to answer this question. When you have the answer, comment that code out and continue.

Turn In. When all is correct, create a script file in which you (i) use make to show that your program compiles correctly, (ii) run your program, and (iii) use cat to display the contents of each of your two .adb files.

That concludes the Ada part of this lab.

Calvin > CS > 214 > Labs > 11 > Ada

This page maintained by Joel Adams.