Thursday, September 6, 2012

AdaTutor - Access Types, User Defined Types, and Derived Types

Access Types

Access types are sometimes called "pointers" in other languages.  However, the name "pointer" fell into disrepute, because of "dangling reference" problems.  Especially in C and C++, it's easy to make mistakes with pointers.  The results of pointer errors are unpredictable; often the system crashes.  With Ada's access types, dangling references are impossible, unless we deliberately instantiate Ada.Unchecked_Deallocation (discussed in the Advanced Topics section) or use the attribute 'Unchecked_Access (discussed later in this section).  So Ada uses the reserved word access rather than the term "pointer."

If we define type Date as before, and write USA : Date; then USA has three fields: Day, Month, and Year. However, if we write

   type P is access Date;
   D1, D2 : P;
then D1 and D2 are capable of accessing ("pointing to") objects of type Date.  In most implementations of Ada, this means that D1 and D2 can each contain the machine address of the start of a record of type Date.  However, this detail depends on the implementation of Ada.  D1 and D2 themselves don't have fields, but the objects they can access have fields.

At present D1 and D2 access nothing.  However, if we execute D1 := new Date;, then, at run time, enough memory for one record of type Date is allocated, and D1 is made to access ("point to") to it.  This new object of type Date doesn't have a name; only the object of the access type has a name (D1).  By contrast, when we elaborate USA : Date; we create an object that has a name (USA), but nothing can access ("point to") it.

We can refer to the fields of the nameless object accessed by D1 as if D1 itself had fields.  Thus, we can write D1.Day, D1.Month, and D1.Year, and use these on either side of an assignment: D1.Day := 12;.  The entire object accessed by D1 is D1.all, so we could write D1.all := (12, Oct, 1492);.  Note that D1.Day is simply an abbreviation for D1.all.Day.  Note also that D1.Day in Ada corresponds to D1->Day in C and C++.  Also, in Ada if A1 accesses an array rather than a record, then A1.all(5) may be abbreviated A1(5).

We can execute D2 := new Date'(4, Jul, 1776); giving the new object a value when it's created.  We can also declare D3 : P := new Date; to make D3 access an object when D3 is created, or even write D3 : P := new Date'(4, Jul, 1776); to make D3 access an object and also give the object a value.

We can write D3 := null; to make D3 access nothing.  When an object of an access type is declared and no initialization is given, it's automatically initialized to null, so D4 : P; means D4 : P := null;.  When such an object is null, it accesses nothing.  In this case, trying to reference the object accessed (D4.Day or D4.all, etc.) will raise a Constraint_Error, but will not do other damage such as crashing the system.  Of course, we can test to see if an object of an access type is null: if D4 = null then ... end if; .

Copying an object of an access type isn't the same as copying the object accessed.  If we execute D1.all := (12, Oct, 1492); and then D2.all := D1.all;, the entire record is copied.  If we change D1.Day with D1.Day := 13;, D2.Day is still 12.  However, is we execute D1.all := (12, Oct, 1492); and then D2 := D1;, the address in D1 is copied to D2, so that D2 now accesses the same object as D1.  Thus, if we change D1.Day with D1.Day := 13;, then D2.Day is also 13, because it references the same memory location.

If we have D1 := new Date'(12, Oct, 1492); and D2 := new Date'(4, Jul, 1776); and then execute D2 := D1;, D2 now accesses what D1 accesses, and nothing any longer accesses the object containing (4, Jul, 1776).  Most systems cannot automatically reclaim the memory occupied by that object.  In the Advanced Topics section, we'll learn to use Ada.Unchecked_Deallocation to release the memory occupied by the object that D2 accesses before we execute D2 := D1;.

In Ada 95, it's possible to access an object that has a name.  This is useful when interfacing our program to other languages that use pointers, like C.  If we declare

   type P is access all Date;
   USA : aliased Date := (4, Jul, 1776);
   D1  : P;
then we can make D1 access USA by executing D1 := USA'Access;.  We can now refer to D1.Day, D1.Month, and D1.Year as well as USA.Day, USA.Month, and USA.Year.

We can give D1 read-only access to USA by changing the first declaration above to “type P is access constant Date;” in that case, we can read, but not store into, D1.Day, D1.Month, and D1.Year (as well as the whole record D1.all).  We can still read and store into USA.Day, USA.Month, USA.Year, and the whole record USA.  To prevent ourselves from storing directly into USA, we can write “USA : aliased constant Date := (4, Jul, 1776);”.  In that case, we can still execute D1 := USA'Access;, but now we can't update USA either directly or through D1; we can only read it.

The 'Access attribute in Ada 95 performs an accessibility check to assure that the lifetime of the object accessed is at least as long as the lifetime of the access type.  This eliminates the danger of dangling references, that is, accessing an object that no longer exists in memory.  For example, the highlighted line below is illegal and will be caught by the compiler:

package Schedule is             
   type Date is ...;             
   type P is access all Date;    
   ...                           
end Schedule;                   
                              
with Schedule; use Schedule;
procedure Test is
   Today : aliased Date;
   T     : P := Today'Access; -- illegal
begin
   ...
end Test;

The highlighted line is illegal because T could be stored in a global variable (some variable declared outside the procedure Test), or be passed to another routine.  Procedure Test could then reach its end, causing Today to cease to exist, because Today is declared inside Test.  But the copy of T could still exist, and it would then access an object that no longer exists in memory, with unpredictable results.  Ada guards against the dangling reference problem that plagues some other languages.

However, Ada lets us get around the accessibility check if we want to. Our example becomes legal if we replace Today'Access with Today'Unchecked_Access:

package Schedule is             
   type Date is ...;             
   type P is access all Date;    
   ...                           
end Schedule;                   
                              
with Schedule; use Schedule;
procedure Test is
   Today : aliased Date;
   T     : P := Today'Unchecked_Access; -- legal
begin
   ...
end Test;

In this case, the programmer must be very careful to assure that no copies of T are ever referenced when the object accessed (Today) has gone out of existence.

We'll discuss accessibility checks further when we talk about access parameters in the section on More Records and Types.

Note that if we have type Acc_Str is access String; and A : Acc_Str; then we can write A := new String'("Hello"); or A := new String(1 .. 5); but not simply A := new String;.  The object created must be constrained, so the compiler will know how much memory to allocate.

Access types are especially useful for creating linked lists.  A simple linked list can be thought of as a chain.  Each link contains some useful data (perhaps one integer, perhaps pages of information), and an object of an access type to access the next item in the chain.  There's also an object of an access type, usually called Head, that accesses the first link in the chain.  The last link accesses nothing.  A linked list of integers might look something like this:

      ____       __________          __________          __________ 
     |  --|---->| Int   10 |   ,--->| Int   27 |   ,--->| Int   34 |
     |____|     | Next  ---|---'    | Next  ---|---'    | Next null|
      Head      |__________|        |__________|        |__________|

To add another integer to the chain, keeping the integers in ascending order, we simply break the chain at the appropriate point and insert another link.

To set up our linked list, we'd like to write type P is access Link; and write

type Link is record
   Int  : Integer;
   Next : P;
end record;

However, the declaration of type P involves Link, and the declaration of type Link involves P, so neither declaration can come first!  Ada provides a special means of solving this problem.   We can write

   type Link;
   type P is access Link;
   type Link is record
      Int  : Integer;
      Next : P;
   end record;

The first line is called an incomplete type declaration.  It simply tells the compiler that type Link exists.  That's all the information the compiler needs to compile the second line.  The second line tells the compiler that objects of type P will be able to access objects of type Link, but for this line the compiler doesn't need to know details of the type of object accessed.  The second line must be followed by the full declaration of type Link.

Question

   type Person is record
      Name : String(1 .. 10);
      Age  : Natural;
   end record;
   type P is access Person;
   P1 : P := new Person'("Susan     ", 21);
   P2 : P := new Person'("John      ", 35);
   ...
   P2     := P1;
   P1.Age := 22;
What is P2.Age?
  1. P2.Age is 21.
  2. P2.Age is 22.
  3. P2.Age is 35.

Let's use an access type to write a program that gets integers in random order from the keyboard, maintaining a linked list of them.  When 0 is input, the program outputs the integers in ascending order.  This program will be a good stepping-stone to Outside Assignment 5.  To simplify inserting an integer into the linked list, Head will access an unused Link, which will in turn access the first actual link in the chain:

     ____      __________         __________         __________ 
    |  --|--->| Int      |   ,-->| Int   10 |   ,-->| Int   27 |
    |____|    | Next  ---|---'   | Next  ---|---'   | Next  ---|--
     Head     |__________|       |__________|       |__________|  '
                                                     __________   '
                                                    | Int  34  |<-'
                                                    | Next null|
                                                    |__________|

We could create our linked list using arrays rather than an access type.  However, we'd have to specify the size of the arrays, placing a limit on the number of integers the program can handle.  With the access type, the only limit is the amount of available memory.  We'll be able to move our program to a larger machine to increase this limit, without changing any code - not even one line to specify the size of an array.

Here's our program ...

   with Ada.Text_IO, Ada.Integer_Text_IO;
   use Ada.Text_IO, Ada.Integer_Text_IO;
   procedure LL_Demo is
      type Link;
      type P is access Link;
      type Link is record
         Int  : Integer;
         Next : P;
      end record;
      Head : P := new Link;
      I    : Integer;
      procedure Add_I_To_Linked_List is separate;
      procedure Display_Linked_List is separate;
   begin
      Put("Type an integer: ");  Get(I);  Skip_Line;
      while I /= 0 loop
         Add_I_To_Linked_List;
         Put("Type an integer: ");  Get(I);  Skip_Line;
      end loop;
      Display_Linked_List;
   end LL_Demo;

   separate (LL_Demo)
   procedure Display_Linked_List is
      -- Skip unused link at the head of the list.
      Tmp : P := Head.Next;
   begin
      while Tmp /= null loop
         -- Display integer in the current link.
         Put(Tmp.Int);  New_Line;
         -- Go to next link in the list.
         Tmp := Tmp.Next;
      end loop;
   end Display_Linked_List;

   separate (LL_Demo)
   procedure Add_I_To_Linked_List is
      -- Begin search of where to insert at start of list.
      Tmp : P := Head;
   begin
      -- Note use of "and then" to avoid trying to reference
      -- an object through a null access value.
      while Tmp /= null and then Tmp.Next /= null
         and then Tmp.Next.Int < I loop
         Tmp := Tmp.Next;  
      end loop;             
      -- Create new link and insert in list.
      Tmp.Next := new Link'(I, Tmp.Next);
   end Add_I_To_Linked_List;

The best way to follow these two subprograms is to draw a linked list on a piece of scrap paper and "hand execute" the subprograms.

Question

   type Link;                          -- 1
   type P is access Link;
   type Link is record
       F : Float;                      -- 2
       S : String(1 .. 10);            -- 3
       A : array(1 .. 10) of Integer;  -- 4
   end record;
   L1 : Link;                          -- 5
   P1 : P;
Which commented line in the above is illegal?

In Ada 95 an access type can access a subprogram.  Thus, the system can decide at run time which of several subprograms to call.  This is called Dynamic Selection.  For example, if we write

   type P is access procedure;
then objects of type P can access any procedure that takes no parameters.  If Test is such a procedure, we could write Proc_Ptr : P := Test'Access;.

Similarly, if we write

   type Q is access procedure (S : in String);
then objects of type Q can access any procedure that has one String parameter of mode in.Proc_Ptr : P := Test'Access; Finally, if we write
   type R is access function (X : in Integer) return Integer;
then objects of type R can access any function that has one Integer parameter and returns type Integer.

Here's an example of Dynamic Selection:

   package P is
      type Int_Function is access function(X : in Integer)
         return Integer;
      F : array(1 .. 2) of Int_Function;
      function Square(X : in Integer) return Integer;
      function Cube(X : in Integer) return Integer;
   end P;

   with P; use P;
   procedure Dynamic_Selection_Demo is
      X, Y : Integer;
   begin
      F(1) := Square'Access;
      F(2) := Cube'Access;
      X := 3;
      for I in 1 .. 2 loop
         -- Decides at run time which function to call.
         Y := F(I)(X);
      end loop;
   end Dynamic_Selection_Demo;

Note that F(I)(X) is simply an abbreviation for F(I).all(X).  The first time through the loop, the highlighted line above will call the function Square and set Y to 9; the second time through the loop the same line will call Cube and set Y to 27.

In the section on More Records and Types, under Tagged Records and Dynamic Dispatching, we'll learn another way to make an Ada 95 system decide at run time which of several subprograms to call.

In Ada 95, objects that access subprograms may also be used as parameters ("dummy arguments") of other subprograms.  For example:

   type Int_Function is access function(X : in Integer)
      return Integer;

   procedure Demo (Fcn : in Int_Function) is
      X, Y : Integer;
   begin
      ...
      Y := Fcn(X);
      ...
   end Demo;

If F(1) is set to Square'Access and we call Demo(F(1));, then Demo will set Y to Square(X).  If F(2) is Cube'Access and we call Demo(F(2));, then Demo will set Y to Cube(X).  When Demo calls function Square or function Cube, we refer to this action as call back.

< prev   next >

No comments: