Re: Question on initialization of packages

["Jeffrey R. Carter" <spam.jrcarter.not@spam.acm.org>]

Reinert Korsnes wrote:
> I try to use a stack in my Ada program.
> 
> Assume the package definition given below, 
> and the follow code in my program:
> 
>    type Message_t;
>    type Message_ta is access Message_t;

You probably don't need this access type. You generally don't need access types 
in Ada, except in the implementation of dynamic data structures.

>    package Message_Stack_p is new Stacks(Message_ta);
>    Send_Stack    : Message_Stack_p.Stack;
> 
> 
> Question: How can I be sure that "Send_Stack" is empty
> at the start of the program execution ?

By supplying an appropriate default initial value to objects of the type. In 
this case, the default initial value of type Stack is null, which you probably 
interpret as an empty stack.

> How can I make explicite that "Send_Stack" is empty in this case ?

Through comments in the specification of Stacks.

> generic
>   type Item is private;
> package Stacks is
>   type Stack is private;

Do you want Stack to have := and "="? Given that it's just an access value, it 
doesn't really make much sense for clients to assign or compare values. If you 
do want assignment, you either need to make it clear that Stack has reference 
assignment and comparison, rather than Ada's customary value assignment, or you 
need to make Stack's implementation controlled and override the Adjust and 
Finalize operations.

>   procedure Push(S: in out Stack; X:  in Item);
>   procedure  Pop(S: in out Stack; X: out Item);
>   function N_elements(S : Stack) return Integer;

A good rule for naming is to save the best name for parameters, and use a 
different name for the type. So I would use something like

type Element is private;
type Stack_Handle is private;

procedure Pop (Stack : in out Stack_Handle; Item : out Element);

so that procedure calls can look like

Pop (Stack => Operands, Item => Token);

> private
>   type Cell;
>   type Stack is access Cell;
>   type Cell is
>     record
>       Next : Stack;
>       N    : Integer;

What does it mean for N to be negative? If that's meaningless, use an 
appropriate subtype (such as Natural) to make that clear, and to let the 
run-time checks alert you if such a condition ever occurs.

>       Value: Item;
>     end record;
> end Stacks;

Probably you should keep N in the stack header:

type Cell_Ptr is access Cell;

type Stack is record
    Length : Natural  := 0;
    First  : Cell_Ptr := null;
end record;

rather than keeping copies in every item in the stack.

> package body Stacks is
> 
>   procedure Push(S: in out Stack; X: in Item) is
>   begin
>     if S /= null then
>        S := new Cell'(S,S.N+1,X);
>     else
>        S := new Cell'(S,1,X);
>     end if;
>   end;
> 
>   procedure Pop(S: in out Stack; X: out Item) is
>   begin
>     X := S.Value;
>     S := S.Next;
>   end;

Here you have a memory leak. Even if you fix that, if you store uncontrolled 
access values in the stack (as you're doing with your type Message_Ta), you may 
still have a memory leak.

>   function N_elements(S: Stack) return Integer is
>   begin
>     if S /= null then
>        return S.N;
>     else
>        return 0;
>     end if;
>   end;
> 
> end Stacks;

But really you shouldn't be implementing your stack ADT directly, and trying to 
do your memory management yourself. Instead implement it in terms of an existing 
sequence data structure, such as Ada.Containers.Doubly_Linked_Lists, and let 
that data structure do the work for you. Such an approach is more likely to be 
correct than doing it yourself. The only reason you would implement your stack 
directly is if this is a learning exercise to learn about the use of access 
types. In that case you will throw it away when you're done, and use a stack 
package built on top of an existing data structure for "real" code.

You can probably find a stack package in one of the many Ada libraries that are 
available. Check adapower.com and adaworld.com. If you don't mind using Ada 95 
(everything you've written is valid Ada 95), there are sequential and protected 
stack packages available as part of the PragmAda Reusable Components:

http://pragmada.home.mchsi.com/

-- 
Jeff Carter
"I'm a kike, a yid, a heebie, a hook nose! I'm Kosher,
Mum! I'm a Red Sea pedestrian, and proud of it!"
Monty Python's Life of Brian
77