Introduction to Ada and Data Abstraction
for Pascal Programmers

Data structures are fundamental building blocks of programs. Since they are so common to a wide range 
of other programs, one of the motivations involved in implementing various data structures is to provide 
for their reuse by other programs and programmers (the clients of the data structure). Ideally, we would 
provide abstractions of the behavior of a particular data structure, presenting a standard interface that the 
client could use to manipulate the data structure in a uniform manner regardless of  the way in which the 
data structure is implemented. That is, the clients could be written in a representation independent 
manner. Moreover, since the only manipulation of the data structure allowed are those provided by the 
standard interface, the integrity of the data structure can be maintained. Data structures implemented in 
this fashion are called Abstract Data Types or ADTs.

Pascal has no mechanisms to enforce this separation between the external view of a data structure and the 
internal representation and implementation. Data structures texts using standard Pascal typically suggest 
providing for reuse by keeping text files of source code available that client programmers can insert into 
their programs using editors. The problem with this approach, of course, is that the clients then have 
uncontrolled access to the components of the data structure, and are even able to modify the code of the 
procedures and functions that manipulate those data. This means there is danger of corruption of the data 
structure.

As you have seen in your introductory data structures course, Turbo Pascal provides the unit as a 
mechanism to provide this kind of separation.  The unit provides:
       -	an interface part that defines a set of declarations (constants, types, variables, and the headers of 
procedures and functions) that can be accessed by client programs;
       -	an implementation part that includes all the code to implement the procedures and functions 
made available in the interface part, as well as any supplemental declarations hidden from client 
programs but available to code in the implementation part; and
       -	an initialization part containing any code that should be executed before any client of the unit, 
allowing variables to be initialized as necessary.

Units are compiled into a library, which keeps the client from modifying the code used to manipulate the 
data structure. Clients access the unit by coding a uses statement at the beginning of their code, which 
causes the Turbo Pascal compiler to link the compiled unit to the client program, making all of its 
declarations available.

	Unit stacku;

	Interface 			{the following can be accessed by clients}
	   const Maxsize = 100;
	   Type
	       Index = 1..Maxsize;
	       Toprange = 0..Maxsize;
	       Stack = record
		Top: Toprange;
		Elements: array [Index] of Integer
	       end;
		
	       procedure Clear (var S: Stack);
	       procedure Push (Item: Integer; var S: Stack);
	       procedure Pop (var S: Stack);
	       function Top: Integer (S: Stack);
		{ other functions to manipulate a Stack}

	Implementation				{This is hidden from clients}
	       procedure Clear (var S: Stack);
		begin
		     S.Top := 0
		end;
	       procedure Push (Item: Integer; var S: Stack);
		begin
		     if  S.Top < Maxsize then
		          begin
			S.Top := S.Top + 1;
			S.Elements[S.Top] := Item
		          end;		{no error indication in simple example}
	       end;
	       {Pascal code for other procedures and functions}
	end.

A client program can then make use of the Stack unit in this way:

	Program Simple (Input, Output);
	       uses Stacku;			{make stack declarations and functions available}
	       var	Num: Integer;
		S: Stack;
	       begin
		Clear (S);
		Readln (Num);
		Push (Num, S);
			{and so on}
	       end.

This has the advantage of  encapsulating the declaration of the stack type and the procedures and 
functions that manipulate it into one compilable component. One disadvantage if we want to be sure to 
protect the integrity of our stacks is that variables of type Stack can be directly manipulated by the client 
program if they know the makeup of the type. That is, within the client program Simple it would be 
possible to modify Top (for example, by writing something like S.Top := S.Top -1;).

Since reuse of program segments was one of the motivating factors behind developing Ada, it should 
come as no surprise that Ada provides a mechanism to perform a similar encapsulating function. The 
mechanism in Ada is the package. 

However, Ada improves on the Turbo Pascal mechanism by allowing the implementor of an ADT to 
prevent a client program from manipulating variables of the type defined by the ADT. In Ada a type made 
public in a package may be specified to be private or limited private. In a client program, a variable of a 
private type can only be assigned to another variable or expression of the same type, compared for equality 
or inequality with an expression of the same type, or manipulated using the procedures and functions 
made visible by the package. Specifying the type as limited private limits the client to manipulating 
variables of that type using only the procedures and functions provided by the package (i.e., neither ":=" 
nor "=" can be used). This provides greater ensurance of integrity of the data structure implemented by the 
package.

Ada also separates the specification of the public and private parts of the ADT from the implementation 
(referred to as the body in Ada). Typically, the specification and body are in different physical files and 
may be compiled separately. That allows different implementations of a package to be provided in 
different libraries for the same specification.

The stack example given above would look like the following in Ada:

	Package Stackp is
				-- the following can be accessed by clients
	   Maxsize: constant := 100;
	   Subtype Index is Integer range 1..Maxsize;
	   Subtype Toprange is Integer range 0..Maxsize;
	   Type Stack is private;	-- only :=, =, /= operations and following
				-- primitives will be accessible by clients		
	   procedure Clear (var S: Stack);
	   procedure Push (Item: Integer; var S: Stack);
	   procedure Pop (var S: Stack);
	   function Top: Integer (S: Stack);
		-- other functions to manipulate a Stack

	private			-- these can't be accessed by clients
	    Subtype Index is Integer range 1..Maxsize;
	    Subtype Toprange is Integer range 0..Maxsize;
	    Type Stack is record
		Top: Toprange;
		Items: array (Index) of Integer
	       end record;
	end Stackp;

	Package body Stackp is				--This is hidden from clients
	       procedure Clear (S: in out Stack) is
		begin
		     S.Top := 0;
		end Clear;
	       procedure Push (Item: in Integer; S: in out Stack) is
		begin
		     if  S.Top < Maxsize then
		          begin
			S.Top := S.Top + 1;
			S.Items (S.Top) := Item;
		          end;		--no error indication in simple example
		end Push;
	       -- Ada code for other procedures and functions
	end Stackp;

A client program can then make use of the Stack package in this way:

	       with Stackp;		-- make stack declarations and functions available
	       use Stackp;		-- avoid using Stackp.Push, etc.
	Procedure Simple is
	       Num: Integer;
	       S: Stack;
	       begin
		Clear (S);
		Readln (Num);
		Push (Num, S);
			--and so on
	       end Simple;

Ada provides an additional advantage over the features allowed by Turbo Pascal. Note that in both 
examples above, the Stack type was declared by explicitly defining the type of elements held in the stack. 
Ada allows us to declare a generic package, in which the type of element to be held in the stack can be 
provided as a parameter by the client program, and the number of elements to be held in a stack can also 
be parameterized. So we get something like this:

	Generic
	    Type Element is private;	-- to be provided by client
	Package Stackp is
				-- the following can be accessed by clients
	   Type Stack (Size: Positive) is private;	-- only :=, =, /= operations and following
						-- client provides Size
		
	   procedure Clear (var S: Stack);
	   procedure Push (Item: Integer; var S: Stack);
	   procedure Pop (var S: Stack);
	   function Top: Integer (S: Stack);
		-- other functions to manipulate a Stack

	private			-- these can't be accessed by clients
	    Type Elements is array (Positive range <>) of Element;	-- number of elements not specified
	    Type Stack (Size: Positive) is record
		Top: Natural := 0;;
		Items: Elements (1..Size);
	       end record;
	end Stackp;

	Package body Stackp is				--This is hidden from clients
	       procedure Clear (S: in out Stack) is
		begin
		     S.Top := 0;
		end Clear;
	       procedure Push (Item: in Integer; S: in out Stack) is
		begin
		     if  S.Top < Maxsize then
		          begin
			S.Top := S.Top + 1;
			S.Items (S.Top) := Item;
		          end;		--no error indication in simple example
		end Push;
	       -- Ada code for other procedures and functions
	end Stackp;

A client program can then make use of the Stack package in this way:

	       with Stackp;		-- make stack declarations and functions
	Procedure Simple is
	       Package IntStack is new Stack (Integer);	-- instantiate package to 
							-- create specific instance
	       use IntStack;					-- avoid typing IntStack.Push, etc.
	       Num: Integer;
	       S: Stack (100);				-- 100 elements in stack
	       begin
		Clear (S);
		Readln (Num);
		Push (Num, S);
			--and so on
	       end Simple;