Using a language effectively requires more than a knowledge of it's syntax and semantics. An acquaintaince with common problems, and the various methods to solve these problems can simplify the process of writing programs, and in this respect Ada is no exception. This chapter is involved in exposing some of the more common idioms of programming in Ada.
Abstraction is one of the most important part of programming, and it should always be considered when programming solutions. You must always make an effort to distinguish what service a type is providing and how it is implemented. You expose the what, but try to hide the how.
Similarly a knowledge of how to hide things in Ada is important. Ada provides for (predominantly) orthogonal concepts of type/behaviour, and modularity/controlling visibility. The semantics of a program (how it runs, what it does) are independent of whether you design the program carefully for modularity and robustness in the face of change. Clearly though it is more often than not worth the effort to design a system competently.
Abstractions allow us to present only that which we want the user to be concerned with, and not giving access to information which is irrelavent. For example in the all too often used stack example, the user should not be too concerned with whether the implementation uses arrays or linked lists.
A rough stab at an abstraction could be...
package stacks is max :constant := 10; subtype count is integer range 0..max; subtype index is range 1..max; type list is array(index) of integer; type stack is record values : list; top : count; end record; overflow :exception; underflow :exception; procedure push(item :in out stack; value :in integer); procedure pop(item :in out stack; value : out integer); function full(item :stack) return boolean; function empty(item :stack) return boolean; -- return an empty initialized stack function init return stack; end;
Here however the details of the implementation are rather obvious; the how tends to get in the way of the what. This can be changed simply by moving whatever is not relavent into the private section...
package stacks is type stack is private; -- This is called a partial view of the type stack -- It makes info about its implementation inaccessable. overflow :exception; underflow :exception; procedure push(item :in out stack; value :in integer); procedure pop(item :in out stack; value : out integer); function full(item :stack) return boolean; function empty(item :stack) return boolean; -- return an empty initialized stack function init return stack; private -- full view of the type, along with other private details. max :constant := 10; subtype count is integer range 0..max; subtype index is range 1..max; type list is array(index) of integer; type stack is record values : list; top : count; end record; end;
Although the programmer who uses your abstraction can see all the details if they have access to the code, they can't write their programs to rely on this information. Also the separation clearly enforces the notion of what is important for the abstaction, and what is not.
Alternatively we could change the private section to reflect a linked list implementation...
package stacks is type stack is private; -- make info about its implementation inaccessable. -- this is called a partial view of the type stack overflow :exception; underflow :exception; procedure push(item:in out stack; value:in integer); procedure pop(item:in out stack; value : out integer); function full(item:stack) return boolean; function empty(item:stack) return boolean; -- return an empty initialized stack function init return stack; private type stack; type ptr is access stack; type stack is record value :integer; next :ptr; end; end;
A user program could then use either package as follows...
with stacks; use stacks; procedure demo is a :stack := init; b :stack := init; temp :integer; begin for i in 1..10 loop push(a,i); end loop; while not empty(a) loop pop(a, temp); push(b, temp); end loop; end;
The concept of being able to substitute a different implementation, or more precisely, only relying on the public interface, is a very important design principle for building robust systems.
(Note that these two implementations aren't quite identical. Consider the case where we have
with stacks; use stacks; procedure not_quite_right is a, b:stack begin push(a,1); push(a,2); b := a; end;
An array implementation will work correctly when copied, but a linked list implementation will only copy the head pointer. Both a and b will then point to the same linked list. The solution to this is presented later on. For the examples presented here on, assume that this problem has been fixed).
It is important to establish the difference between what services a type provides, and how it implements that service. For example a list abstraction (that has appropriate routines, and itself may be implemented as a linked list, or an array) can be used to implement a queue abstraction. The queue abstraction will have only a few operations:
add_to_tail remove_from_head full empty init
We want to ensure there is a clear distinction between the abstraction and the implementation in our program. Preferably the compiler should check and ensure that no-one makes the mistake of calling routines from the implementation, rather than the abstraction.
Below is an example package which can lead to problems.
package lists is type list is private; procedure add_to_head(item:in out list; value :in integer); procedure remove_from_head(item:in out list; value :out integer); procedure add_to_tail(item:in out list; value:in integer); procedure remove_from_tail(item:in out list; value: out integer); function full(item: list) return boolean; function empty(item:list) return boolean; function init return list; private type list is... -- full view of type. end; with lists; use lists; -- abstraction of lists package queues is type queue is new list; -- inherits operations from the list type -- i.e. the following are "automagically" (implicity) declared -- -- procedure add_to_head(item:in out queue; value :in integer); -- procedure remove_from_head( -- item :in out queue; -- value : out integer); -- etc. end queues;
Here type queue inherits all of the operations of the list type, even those that aren't appropriate, such as remove_from_tail. With this implementation of queue, clients of the abstraction could easily break the queue, which should only allow insertion at the tail, and removal from the head of the list.
For example a client of the queues package (something that "with queues"), could easily do the following
with queues; use queues; procedure break_abstraction is my_Q :queue; begin add_to_head(my_Q, 5); add_to_tail(my_Q, 5); -- queues should only add at the tail, remove from the head, -- or vice-versa end;
What we need to do is advertise a different abstraction, but reuse the list abstraction privately.
with lists; -- this is only used in the private section. package queues is type queue is private; procedure remove_from_head(item:in out queue; value :out integer); procedure add_to_tail(item:in out queue; value:integer); function full(item: queue) return boolean; function empty(item:queue) return boolean; function init return queue; private type queue is new lists.list; end; package body queues is -- Perform a type conversion (from queue to list), and then call -- the appropriate list routine. use lists; -------------------------------------------------------------------- procedure remove_from_head(item:in out queue; value :out integer) is begin lists.remove_from_head(list(item), value); end; -------------------------------------------------------------------- function full(item: queue) return boolean is begin return lists.full(list(item)); end; ... function init return queue is begin return queue(lists.init); end; end;
Let's say we wish to create a stack package, but we don't want to recode all of the routines. We may already have a linked list implementation that could form the basis of the storage for the stack. The list package stores integers.
Assume the package lists is defined as follows...
package lists is type list is private; underflow :exception; procedure insert_at_head(item:in out list; value :in integer); procedure remove_from_head(item:in out list; value:out integer); procedure insert_at_tail(item:in out list; value :in integer); procedure remove_from_tail(item:in out list; value: out integer); function full(item:list) return boolean; function empty(item:list) return boolean; -- returns an empty initialized list function init return list; private ... end;
We can then make use of Ada's ability to hide the full view of a type in the private section. Here we declare a brand new type (as far as the client is concerned), which is actually implemented as a derived type. The client can't "see" this - the "under the hood" details remain well hidden.
We implement the stack as...
with lists; package stacks is type stack is private; underflow :exception; procedure push(item:in out stack; value:in integer); procedure pop(item:in out stack; value : out integer); function full(item:stack) return boolean; function empty(item:stack) return boolean; -- return an empty initialized stack function init return stack; private -- create a new type derived from an existing one. -- This is hidden from the clients of the type type stack is new lists.list; -- stack inherits all the operations of type list. -- They are _implicity_ declared as -- -- procedure insert_at_head(item:in out stack; value :in integer); -- procedure remove_from_head(item :in out stack; -- value: out integer); -- ... -- function full(item:stack) return boolean; -- function empty(item:stack) return boolean; -- function init return stack; end;
We now have to relate the implicity declared routines to those that are advertised publically. This is done by a simple "call through" mechanism.
package body stacks is procedure push(item:in out stack; value:in integer) is begin insert_at_head(item, value); end; -- you can make it more efficient by... pragma inline(push); procedure pop(item:in out stack; value : out integer) is begin remove_from_head(item, value); exception => when lists.underflow => raise stacks.underflow; end; ... end stacks;
This is ok for publically advertised routines that have different names from the implicity declared routines (those inhertied from type list).
However in the package specification there are two functions full which have the profile
function full(item:stack) return boolean;
One is explicity declared in the public section, one implicity declared in the private section. What's going on? The first function specification in the public part of the package is only a promise of things to come. It is an as-yet unrealised function. It will be completed in the package body. As well we have another (implicity) declared function which just happens to have the same name and profile. You still have to describe to the Ada compiler how you are going to implement the function declared in the public part of the package. The Ada compiler can see that both functions have the same name and profile, but it does not assume that public function should be implemented by the private function.
For example imagine that integer_lists.full always return false, to indicate that the linked list was never full, and could always grow. As the implementor of the stack package you may have decided that you wanted to enforce a limit on the stack, so that it would only contain 100 elements at most. You would then write the function stacks.full accordingly. It would be incorrect for the implementation of function full to default back to the linked list implementation.
Because of the visibility rules of Ada, the explicit public declaration completely hides the implicity declared private one, and so is not accessable at all. The only solution is to call on the function in the list package, which you have to do explicity.
package body stacks is
function full(item:stack) return boolean is
begin
-- call the original full in the other package.
return lists.full(lists.list(item));
-- type conversion of parameter
end;
...
end stacks;
This seems all terribly obtuse and annoying. Why does Ada force this upon you? The reason you are encountering this sort of problem is because of the nature of constructing programs with independent name spaces (different scopes where identical names do not clash with each other). Ada is merely providing a solution to a problem that is an inevitable consequence of name spaces. The alternative, of having to work with a language in which there can be no names the same is worse than this solution. So don't shoot the messenger just because you don't like the message :-).
This is a very important point to note. Don't go on unless you understand this point.
The full package body for stacks would be
use lists; package body stacks is procedure push(item:in out stack; value:in integer) is begin insert_at_head(item, value); end; procedure pop(item:in out stack; value : out integer) is begin remove_from_head(item, value); exception => when lists.underflow => raise stacks.underflow; end; -- note how the exception advertised in the other package -- is "translated" to an exception defined within this package. function full(item:stack) return boolean is begin return lists.full(list(item)); end; function empty(item:stack) return boolean is begin return lists.empty(list(item)); end; -- return an empty unitialized stack function init return stack is begin return stack(lists.init); end; end stacks;
Often a generic package that implements a suitable data structure can be used to implement another abstraction. This is very similar to the section presented previously.
Assume the package generic_lists is defined as...
generic type element is private; package generic_lists is type list is private; underflow :exception; procedure insert_at_head(item:in out list; value :in element); procedure remove_from_head(item:in out list; value:out element); procedure insert_at_tail(item:in out list; value :in element); procedure remove_from_tail(item:in out list; value: out element); function full(item:list) return boolean; function empty(item:list) return boolean; -- returns an empty initialized list function init return list; private ... end;
We can instantiate this generic to create a new package that will store the integers for us. The question is "where do we want to instantiate it, such that it won't get in the way of the abstraction, or cause other developement problems?". The solution to this (as it is to a lot of these type of questions) is in the private section of the package.
We can then use the generic as follows...
with generic_lists; package stacks is type stack is private; underflow :exception; procedure push(item:in out stack; value:in integer); procedure pop(item:in out stack; value : out integer); function full(item:stack) return boolean; function empty(item:stack) return boolean; -- return an empty initialized stack function init return stack; private -- Instantiate the generic to create a new package. package integer_lists is new generic_lists(integer); type stack is new integer_lists.list; -- stack inherits all the operations of type list, as before. end;
The package body is the same as previously described.
Here we can enforce privacy, without changing what the type does for a client.
Abstractions can be implemented by using composition (composing new abstractions by putting existing abstractions together, typically in a record) and by forwarding subprogram calls onto the appropriate component object. (This is all pretty simple stuff!).
with lists; use lists; package queues is type queue is private; procedure remove_from_head(item:in out queue; value :out integer); procedure add_to_tail(item:in out queue; value:integer); function full(item: queue) return boolean; function empty(item:queue) return boolean; function init return queue; private -- a queue is composed from the following items... type queue is record values:list; no_of_elements:integer; end record; end; package body queues is procedure remove_from_head(item:in out queue; value:out integer) is begin remove_from_head(item.values, value); item.no_of_elements := item.no_of_elements - 1; end; procedure add_to_tail(item:in out queue; value:integer) is begin add_to_tail(item.values, value); item.no_of_elements := item.no_of_elements + 1; end; procedure reset (item: in out queue) is ... function full(item: queue) return boolean is begin return full(item.values); end; function empty(item:queue) return boolean is begin return item.no_of_elements = 0; end; end;
In this example calls on a queue are "forwarded" onto the list component, which is responsible for implementing some aspect of the queue abstraction (in this case a major part!).
Both implementations of the stack described above provided a common set of routines, that is push, pop etc. In Ada we can state the commonalities using a common type. The common type will describe what routines are to be provided, and their profiles, but not actually describe how to implement them. Type derived from this type are forced to implement each subprogram in its own way. This is called an abstract type. It is an abstraction abstraction!
The reason we go to all of this trouble is to tell the clients of the stack that no matter what implementation they choose, they can be sure of getting at least the functionality described by the abstract type.
package stacks is type stack is abstract tagged null record; -- An abstract type with no fields, and no "real" operations. -- Ada required the "tagged" description for abstract types underflow :exception; overflow :exception; procedure push(item:in out stack; value:in integer) is abstract; procedure pop(item:in out stack; value : out integer) is abstract; function full(item:stack) return boolean is abstract; function empty(item:stack) return boolean is abstract; function init return stack is abstract; end;
Here we have made the type abstract - this package just provides a series of subprogram that must be implemented by someone else. We could also have made the type private...
package stacks is type stack is abstract tagged private; -- subprograms ... private type stack is abstract tagged null record; end;
Either in the same package (or more typically in another package) we can extend the type, and create a real type that implements the abstract type...
with lists; with stacks; package unbounded_stacks is type bounded_stack is new stacks.stack with private; -- bounded_stack is derived from the empty stack record, -- with some extra bits added on that are described -- in the private section. procedure push(item:in out unbounded_stack; value:in integer); procedure pop(item:in out unbounded_stack; value : out integer); function full(item:unbounded_stack) return boolean; function empty(item:unbounded_stack) return boolean; -- return an empty initialized unbounded_stack function init return unbounded_stack; private -- Extend the empty stacks.stack record with one -- 'more' field. -- All calls will have to be forwarded onto the -- internal linked list. type unbounded_stack is new stacks.stack with record values:lists.list; end record; end;
As described in the section on composition, you will have to forward calls onto the linked list within the unbounded_stack. The package body would therefore be...
package body unbounded_stacks is procedure push(item:in out unbounded_stack; value:in integer) is begin lists.insert_at_head(item.values, value); end; procedure pop(item:in out unbounded_stack; value : out integer) is begin lists.remove_from_head(item.values, value); exception when lists.underflow => raise stacks.underflow; end; ... end unbounded_stacks;
In Ada, types and packages are almost completely independent of each other. This allows you to devise a solution to a problem in terms of types and operations, and later decide on how these parts should be split into pieces to meet the software engineering requirements of ease of modification, encapsulation, modularisation, reduced recompilation costs, namespace management etc.
This has been demonstrated already, in the choice to hide implementation details in the various packages above. However Ada also provides further choices that can be made in this regard.
In language such as C, there is only one namespace. There is no hierachy of names; no ability to 'hide' or qualify a name. A good analogy is the first version of the Mac OS, which had no directories. All filenames had to be different, and could not conflict with predefined system filenames. The solution typically adopted in C to resolve this problem is to prepend some form of semantic information in the name. For example all posix thread routines are prepended with 'pthread_'.
Ada83 solved this problem by allowing packages which contain their own namespace, in which locally defined names don't conflict with other names (the analogy is for one level of subdirectories (actually not quite accurate, as a package can contain other entities...)).
Ada95 however expands the namespace concept with the inclusion of child packages to allow for truly hierachic namespaces. Child packages are typically used to model some form of hierachy present in the problem domain. For example a unix binding may implement packages
unix -- can be an empty "place holder" package unix.file -- file routines unix.process -- process operations
Alternatively the package hierachy can be used to reflect the inhertiance hierachy of an object oriented type. Note however the package hierachy does not define the inhertiance hierachy - the type declarations do that.
The example given earlier of an abstract stack, and a concrete implementation of an unbounded stack is a good example of how we could have chosen a different organisation, without affecting the meaning of the abstraction.
with stacks; use stacks; with lists; package stacks.unbounded is type unbounded_stack is new stack with private; -- partial view of the bounded_stack -- override the primitive operations with concrete services procedure push(item:in out bounded_stack; value:in integer); procedure pop(item:in out bounded_stack; value : out integer); function full(item:bounded_stack) return boolean; function empty(item:bounded_stack) return boolean; function init return unbounded_stack; private ... end;
We could create another type, bounded_stack, and decide to put it into the package stacks.bounded.
package stacks.bounded is type bounded_stack is new stacks.stack with private; ... end;
As discussed earlier in the implementation of a stack with a linked list, making a copy of such a type through an assignment statement doesn't quite work. The problem is that copying often only copies a pointer to the head of a list (or tree) and does not copy the entire list. Another problem is that the space allocated to a linked list is often not recovered when an object goes out of scope.
An example which highlights these problems is...
with lists; use lists; procedure bad_voodoo is a, b:list; result :integer; procedure loose_memory is c :list; begin insert_at_head(c, 1); insert_at_head(c, 2); end; -- when you get to here, c goes out of scope -- and you lose the memory associated with the nodes! begin insert_at_head(a, 1); insert_at_head(a, 2); insert_at_head(b, 3); insert_at_head(b, 4); b := a; -- b and a now point to the same list, and all of b's nodes -- have been lost! remove_from_tail(a, result); -- affects both a and b end;
In Ada95 you can solve these problems by providing special routines that are "automagically" called when a values are being copied, when they go out of scope, or when they are initialized. For this to happen, the object in question must be derived from a special type called Controlled, defined in package Ada.Finalization.
The three routines automagically called are called Initialize, Adjust and Finalize. They are called in the following contexts...
with lists; use lists; procedure demo is a :list; -- Initialize(a); b :list := Init; -- Initialize not called begin insert_at_head(a, 1); insert_at_head(a, 2); insert_at_head(b, 3); insert_at_head(b, 4); a --> | 2 |-->| 1 |--> null b --> | 4 |-->| 3 |--> null b := a; ------------------------------------------ Finalize(b); Free b's nodes, before it is overwritten a --> | 2 |-->| 1 |--> null b --> null Copy a to b. Now they _both_ point at the same list a --> | 2 |-->| 1 |--> null b ----^ Adjust(b); b has to duplicate the list it currently points at, at then point at the new list. a --> | 2 |-->| 1 |--> null b --> | 2 |-->| 1 |--> null ------------------------------------------ end; Finalize(a), Finalize(b). Delete the memory associated with both a and b. a --> null b --> null
Here we finally give the full details for package List. The code for it looks like...
with Ada.Finalization; package lists is type List is private; underflow :exception; procedure insert_at_head(item:in out list; value :in integer); procedure remove_from_head(item:in out list; value:out integer); procedure insert_at_tail(item:in out list; value :in integer); procedure remove_from_tail(item:in out list; value: out integer); function full(item:list) return boolean; function empty(item:list) return boolean; -- returns an empty initialized list function init return list; private -- Normal stuff for the list type Node; type Ptr is access Node; type Node is record Value :Integer; Next :ptr; end record; -- Only the head of the list is special... type List is new Ada.Finalization.Controlled with record Head :Ptr; end record; -- No need for Initialize (pointers are automatically set to null) -- procedure Initialize(item:in out list); procedure Adjust(item:in out list); procedure Finalize(item:in out list); end;
Note that the routines were declared in the private section. This prevents clients from calling them when it is inappropriate.
The package body would be implemented as follows...
with unchecked_deallocation;
package body lists is
-- routine for deallocating nodes
procedure free is new unchecked_deallocation(node,ptr);
------------------------------------------------------------
-- Implement all the other stuff (insert_at_head, remove_from_head...)
...
--------------------------------------------------------------
-- given a ptr to a list, this will allocate a new
-- identical list
function Copy_List(item:ptr) return ptr is
begin
if item = null then
return null;
else
return new node'(item.value,Copy_List(item.next));
end if;
end;
------------------------------------------------------------
-- In the assignment b := a, b has just been
-- overwritten by the contents of a. For a linked
-- list this means that both a and b point at the
-- same object. Now have to make a physical copy
-- of the items pointed at by b, and replace the head
-- ptr with a pointer to the copy just made
procedure Adjust(item:in out list) is
begin
item.head := Copy_List(item.head);
end;
------------------------------------------------------------
-- delete all the memory in the about to be
-- destoyed item
procedure Finalize(item:in out list) is
upto:ptr := item.head;
temp :ptr;
begin
while upto /= null loop
temp := upto;
upto := upto.next;
free(temp);
end loop;
item.head := null;
end;
end;
The use of controlled types gives a good degree of control over dynamic objects. It simplifies the life of a client of the type as it relieves them of the worry of having to manage the types memory. It also allows for easy substitution of dynamic and non dynamic solutions to problems.
Typically once the 3 routines (initialize, adjust, finalize) have been written, the rest of the services can be written without regard to these features.
In C++ you can enforce the initialization of all objects by supplying a class with a constructor, which is called when an object is created. The same effect in Ada is achieved by assigning a value the result of calling a function.
For example
package stacks is type stack is tagged private; function init return stack; -- other operations ... private type list is array(1..10) of integer; type stack is record values :list; top :integer range 0..10; end record; end; with stacks; use stacks; procedure main is a : stack := init; b : stack; begin null; end;
In this example the object a is properly initialized to represent an empty stack. You can only use functions provided in the package; you can't set it any other way, because the type is private. However as can be seen, the object b has not been initialized. The language has not enforced an initialization requirement.
The only way to do this is through the use of record discriminants. The partial view of the type is declared to have discriminants, even if the full view does not. As the number of fields that a record has may depend on a discriminant, and because Ada likes constrained objects (one's whose size is known) the combination of discriminant and private type causes the compiler to enforce all objects of the type to be initialized.
package stacks is type stack(<>) is private; -- declare that stack _may_ have discriminant... function init return stack; -- other operations ... private type list is array(1..10) of integer; -- ...even if you have no intention of it having such type stack is record values :list; top :integer range 0..10; end record; end; with stacks; use stacks; procedure main is a : stack := init; b : stack; -- now this is illegal. You _must_ call a function -- to initialize it. begin null; end;
This is all quite non intuitive, and rather counter to the Ada notion of readability (IMHO). Certainly C++ manages this is a more programmer friendly way.
Sometimes there is a need for two (or more) types that are mutually recursive, that is they have pointers that point at each other. An example is a doctor and a patient, who wish to maintain pointers at each other. Unless you wish to place them together in the same package, Ada does not properly support you. The best you can do if you want to retain separate compilation, is to define two base types, then join them together later in other packages.
package doctors_and_patients is type doctor is abstract tagged null record; type doctor_ptr is access all doctor'class; type patient is abstract tagged null record; type patient_ptr is access all patient'class; end; with doctors_and_patients; use doctors_and_patients; package doctors is type doc is new doctor with private; -- subprograms ... private type doc is new doctor with record pat:patient_ptr; ... end record; end; -- similarly for patient type
If you can forsee all operations required, or at least those required by each other, you can place them in package doctors_and_patients. Futher operations can be added along with subsequent type declarations (for example type doc).
It's probably worth point out here that package bodies can see into package specs, so...
with doctors; use doctors; package body patients is -- The patients body can access the doctor's services -- declared in the doctor's spec ... end patients; with patients; use patients; package body doctors is -- The doctors body can access the patients services -- declared in the patient's spec end doctors;