Question on initialization of packages

Question on initialization of packages

[Reinert Korsnes]

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;
   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 ?

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

reinert

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

  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;

private
  type Cell;
  type Stack is access Cell;
  type Cell is
    record
      Next : Stack;
      N    : Integer;
      Value: Item;
    end record;
end Stacks;

---

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;

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

end Stacks;

Re: Question on initialization of packages

[Dmitry A. Kazakov]

On Tue, 17 Jun 2008 10:07:43 +0200, Reinert Korsnes wrote:

> Assume the package definition given below, 
> and the follow code in my program:
> 
>    type Message_t;
>    type Message_ta is access Message_t;
>    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 ?

Hmm, "sure" in which sense? To make it visible for the reader? To specify
in the contract of Stack that it is initially empty?

As for implementation you posted, the stack is empty, because instances of
access types are initialized with null (when not explicitly initialized
otherwise). Below you declare:

>   type Stack is access Cell;

And

   Send_Stack : Message_Stack_p.Stack; -- This will be null = empty


Now side comments:

1.

>   procedure Pop(S: in out Stack; X: out Item) is
>   begin
>     X := S.Value;
>     S := S.Next;
>   end;

This is a memory leak. If you allocated a stack element on push, you should
free it on pop.
 
2. Package initialization is achieved as follows:

package body P is
   ...
begin
   ... -- Initialize package stuff
end P;

3. Package initialization cannot help you here, because the package
declares an abstract data type of which objects can be created long after
the package itself was elaborated (initialized).

4. You have messages. Pointers to messages. These pointers are copied into
dynamically allocated linked list called stack.

How are you going to maintain this? Do you want to prevent messages from
being copied? Then you should reconsider the design of messages allowing
their queuing without stacks. Alternatively, do you want to copy messages
upon queueing (to marshal them)? Then the queue should deal with
unconstrained objects:

   generic
      type Message (<>) is private;
   package Queue is
      ...

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Question on initialization of packages

[Reinert Korsnes]

Dmitry A. Kazakov wrote:

> On Tue, 17 Jun 2008 10:07:43 +0200, Reinert Korsnes wrote:
> 
>> Assume the package definition given below,
>> and the follow code in my program:
>> 
>>    type Message_t;
>>    type Message_ta is access Message_t;
>>    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 ?
> 
> Hmm, "sure" in which sense? To make it visible for the reader? To specify
> in the contract of Stack that it is initially empty?

Yes, yes, to make it visible for the reader.

> 
> As for implementation you posted, the stack is empty, because instances of
> access types are initialized with null (when not explicitly initialized

Yes, but I do not like things depend on the particular implementation :-)


> otherwise). Below you declare:
> 
>>   type Stack is access Cell;
> 
> And
> 
>    Send_Stack : Message_Stack_p.Stack; -- This will be null = empty
> 
> 
> Now side comments:
> 
> 1.
> 
>>   procedure Pop(S: in out Stack; X: out Item) is
>>   begin
>>     X := S.Value;
>>     S := S.Next;
>>   end;
> 
> This is a memory leak. If you allocated a stack element on push, you
> should free it on pop.

How I free it?  I may not have a deep enough understanding here :-)

>  
> 2. Package initialization is achieved as follows:
> 
> package body P is
>    ...
> begin
>    ... -- Initialize package stuff
> end P;
> 
> 3. Package initialization cannot help you here, because the package
> declares an abstract data type of which objects can be created long after
> the package itself was elaborated (initialized).

But I would like to make it clear for all that the stack is
empty at the start of my program !  (also after that I may
change the implementation).

> 
> 4. You have messages. Pointers to messages. These pointers are copied into
> dynamically allocated linked list called stack.
> 
> How are you going to maintain this? Do you want to prevent messages from
> being copied? Then you should reconsider the design of messages allowing
> their queuing without stacks. Alternatively, do you want to copy messages
> upon queueing (to marshal them)? Then the queue should deal with
> unconstrained objects:
> 
>    generic
>       type Message (<>) is private;
>    package Queue is
>       ...
> 

I want to "stack away" messages to be processed later.
Copied, deleted etc.

reinert

Re: Question on initialization of packages

[christoph.grein]

On 17 Jun., 10:50, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:
> As for implementation you posted, the stack is empty, because instances of
> access types are initialized with null (when not explicitly initialized
> otherwise). Below you declare:
>
> >   type Stack is access Cell;
>
> And
>
>    Send_Stack : Message_Stack_p.Stack; -- This will be null = empty

But N is undefined, so you have an empty stack with an undefined
number of elements.

There is no way to make it visible to users that the stack is empty
after declaration of a stack object if you hide the implementation.
You must state this as a comment; this belongs to the contract of the
ADT and you must implement it fulfilling the contract:

private
  type Cell;
  type Stack is access Cell;
  type Cell is record
    Next : Stack;
    N    : Integer := 0;  -- better use Natural here, or will you ever
have a negative number of elements?
    Value: Item;
  end record;
end Stacks;

Your stack should be limited private - or do you want to copy stack
objects? Then you must be careful that deep copies are made. With this
design, you have no control over copying. A copy of a stack will be a
shallow copy.

For freeing cells, see Ada.Unchecked_Deallocation.

Re: Question on initialization of packages

[Dmitry A. Kazakov]

On Tue, 17 Jun 2008 11:14:59 +0200, Reinert Korsnes wrote:

> Dmitry A. Kazakov wrote:
> 
>> On Tue, 17 Jun 2008 10:07:43 +0200, Reinert Korsnes wrote:
>> 
>>> Question: How can I be sure that "Send_Stack" is empty
>>> at the start of the program execution ?
>> 
>> Hmm, "sure" in which sense? To make it visible for the reader? To specify
>> in the contract of Stack that it is initially empty?
> 
> Yes, yes, to make it visible for the reader.

I.e. you want to allow initially non-empty stacks? This does not look like
a good idea.

Anyway, if stack is non-limited, you could do something like

   type Stack (<>) is private;
       -- The box <> enforces object's initialization
   Empty : constant Stack; -- Initial value of an empty stack
   ...
private
   ...
   Empty : constant Stack := null;

then the user will be forced to do:

   Send_Stack : Stack := Empty;

However, I see no reason to have stack copyable in the first line.

>> As for implementation you posted, the stack is empty, because instances of
>> access types are initialized with null (when not explicitly initialized
> 
> Yes, but I do not like things depend on the particular implementation :-)

But this particular implementation fulfills the stack contract, which reads
"stack is initially empty." I see no problem here.

>>>   procedure Pop(S: in out Stack; X: out Item) is
>>>   begin
>>>     X := S.Value;
>>>     S := S.Next;
>>>   end;
>> 
>> This is a memory leak. If you allocated a stack element on push, you
>> should free it on pop.
> 
> How I free it?  I may not have a deep enough understanding here :-)

Per a call to instantiated Ada.Unchecked_Deallocation.

procedure Pop (S: in out Stack; X: out Item) is
   procedure Free is new Ada.Unchecked_Deallocation (Cell, Stack);
   Top : Stack := S;
begin
   if Top =null then
      raise Empty_Stack_Error;
   else
      X := Top.Value;
      S := Top.Next;
      Free (Top);
   end if;
end Pop;

BTW, you don't need to keep the stack depth in its items. Do it in the
stack object. Increment it on push and decrement on pop.

>> 3. Package initialization cannot help you here, because the package
>> declares an abstract data type of which objects can be created long after
>> the package itself was elaborated (initialized).
> 
> But I would like to make it clear for all that the stack is
> empty at the start of my program!

But your program starts even before package elaboration. At that point
there is no stack at all, whether empty or not...

> (also after that I may
> change the implementation).

Any implementation shall respect the stack contract, and see above...

>> How are you going to maintain this? Do you want to prevent messages from
>> being copied? Then you should reconsider the design of messages allowing
>> their queuing without stacks. Alternatively, do you want to copy messages
>> upon queueing (to marshal them)? Then the queue should deal with
>> unconstrained objects:
>> 
>>    generic
>>       type Message (<>) is private;
>>    package Queue is
>>       ...
> 
> I want to "stack away" messages to be processed later.
> Copied, deleted etc.

That does not define what happens with the message object. Do you stack
*the* message or *a* copy/equivalent/digest of?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Question on initialization of packages

[Georg Bauhaus]

Reinert Korsnes schrieb:
> Dmitry A. Kazakov wrote:

>>> Question: How can I be sure that "Send_Stack" is empty
>>> at the start of the program execution ?
>> Hmm, "sure" in which sense? To make it visible for the reader? To specify
>> in the contract of Stack that it is initially empty?
> 
> Yes, yes, to make it visible for the reader.

In any case, users can be enabled to ask whether or not the stack is
empty, as I'm sure you know. In the generic stack package,

   type Stack is ...;
   function Is_Empty(The_Stack: Stack) return Boolean;

Then, since we now have pragma Postcondition,
you could make the Stack controlled, override Initialize
and state the postcondition of being empty after initialization:

   type Stack is new Limited_Controlled with private;

   overriding
   procedure Initialize(Object: in out Stack);
   pragma Postcondition(Initialize, Is_Empty(Object));

Re: Question on initialization of packages

[Reinert Korsnes]

First: many thanks for comments.  
It gave me a nice learning curve today :-)

Dmitry A. Kazakov wrote:

> On Tue, 17 Jun 2008 11:14:59 +0200, Reinert Korsnes wrote:
> 
>> Dmitry A. Kazakov wrote:
>> 
>>> On Tue, 17 Jun 2008 10:07:43 +0200, Reinert Korsnes wrote:
>>> 
>>>> Question: How can I be sure that "Send_Stack" is empty
>>>> at the start of the program execution ?
>>> 
>>> Hmm, "sure" in which sense? To make it visible for the reader? To
>>> specify in the contract of Stack that it is initially empty?
>> 
>> Yes, yes, to make it visible for the reader.
> 
> I.e. you want to allow initially non-empty stacks? This does not look like
> a good idea.

Maybe a bit amataur, but down in the code I now have:

             Node(i).Send_Stack := Message_Stack_p.Empty_Stack;

(thanks to your suggestions here)

Maybe I better could define a procedure "Empty_Stack(Send_Stack)" ?

reinert








> 
> Anyway, if stack is non-limited, you could do something like
> 
>    type Stack (<>) is private;
>        -- The box <> enforces object's initialization
>    Empty : constant Stack; -- Initial value of an empty stack
>    ...
> private
>    ...
>    Empty : constant Stack := null;
> 
> then the user will be forced to do:
> 
>    Send_Stack : Stack := Empty;
> 
> However, I see no reason to have stack copyable in the first line.
> 
>>> As for implementation you posted, the stack is empty, because instances
>>> of access types are initialized with null (when not explicitly
>>> initialized
>> 
>> Yes, but I do not like things depend on the particular implementation :-)
> 
> But this particular implementation fulfills the stack contract, which
> reads "stack is initially empty." I see no problem here.
> 
>>>>   procedure Pop(S: in out Stack; X: out Item) is
>>>>   begin
>>>>     X := S.Value;
>>>>     S := S.Next;
>>>>   end;
>>> 
>>> This is a memory leak. If you allocated a stack element on push, you
>>> should free it on pop.
>> 
>> How I free it?  I may not have a deep enough understanding here :-)
> 
> Per a call to instantiated Ada.Unchecked_Deallocation.
> 
> procedure Pop (S: in out Stack; X: out Item) is
>    procedure Free is new Ada.Unchecked_Deallocation (Cell, Stack);
>    Top : Stack := S;
> begin
>    if Top =null then
>       raise Empty_Stack_Error;
>    else
>       X := Top.Value;
>       S := Top.Next;
>       Free (Top);
>    end if;
> end Pop;
> 
> BTW, you don't need to keep the stack depth in its items. Do it in the
> stack object. Increment it on push and decrement on pop.
> 
>>> 3. Package initialization cannot help you here, because the package
>>> declares an abstract data type of which objects can be created long
>>> after the package itself was elaborated (initialized).
>> 
>> But I would like to make it clear for all that the stack is
>> empty at the start of my program!
> 
> But your program starts even before package elaboration. At that point
> there is no stack at all, whether empty or not...
> 
>> (also after that I may
>> change the implementation).
> 
> Any implementation shall respect the stack contract, and see above...
> 
>>> How are you going to maintain this? Do you want to prevent messages from
>>> being copied? Then you should reconsider the design of messages allowing
>>> their queuing without stacks. Alternatively, do you want to copy
>>> messages upon queueing (to marshal them)? Then the queue should deal
>>> with unconstrained objects:
>>> 
>>>    generic
>>>       type Message (<>) is private;
>>>    package Queue is
>>>       ...
>> 
>> I want to "stack away" messages to be processed later.
>> Copied, deleted etc.
> 
> That does not define what happens with the message object. Do you stack
> *the* message or *a* copy/equivalent/digest of?
> 

Re: Question on initialization of packages

[Martin]

On Jun 17, 1:03 pm, Reinert Korsnes <a...@b.no> wrote:
[snip]
> Maybe a bit amataur, but down in the code I now have:
>
>              Node(i).Send_Stack := Message_Stack_p.Empty_Stack;
>
> (thanks to your suggestions here)
>
> Maybe I better could define a procedure "Empty_Stack(Send_Stack)" ?
[snip]

Absolutely "yes" if "Send_Stack" contains any pointers...unless you
don't mind leaking memory...

Cheers
-- Martin

Re: Question on initialization of packages

[Robert A Duff]

Reinert Korsnes <a@b.no> writes:

> 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;
>    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 ?
>
> How can I make explicite that "Send_Stack" is empty in this case ?

Here's one way:

Declare Stack like this:

    type Stack(<>) is limited private;

The "(<>)" means clients cannot declare objects without initializing
them.  The "limited" means clients cannot copy them.

Declare the full type like this:

    type Stack is limited
        record
            ... -- pointer to first cell, and count can go here
        end record;

Declare a constructor function:

    function Empty_Stack return Stack;

Declare other constructor functions if you want.

Then:

    Send_Stack: Message_Stack_p.Stack := Message_Stack_p.Empty_Stack;

Note that this works only in Ada 2005 mode.

- Bob

Re: Question on initialization of packages

[Jeffrey R. Carter]

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

Re: Question on initialization of packages

[Jeffrey R. Carter]

Georg Bauhaus wrote:
> 
> Then, since we now have pragma Postcondition,

"We" (Ada users) don't have pragma Postcondition. A specific implementation may 
provide it, but it's not part of the standard.

-- 
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

Re: Question on initialization of packages

[Robert A Duff]

"Jeffrey R. Carter" <spam.jrcarter.not@spam.acm.org> writes:

> Georg Bauhaus wrote:
>> Then, since we now have pragma Postcondition,
>
> "We" (Ada users) don't have pragma Postcondition. A specific
> implementation may provide it, but it's not part of the standard.

True, but it's still safe to use it.  On GNAT, it works,
and on other implementations (which don't support it),
it does nothing.

- Bob

Re: Question on initialization of packages

[Dmitry A. Kazakov]

On Tue, 17 Jun 2008 13:08:08 -0400, Robert A Duff wrote:

> "Jeffrey R. Carter" <spam.jrcarter.not@spam.acm.org> writes:
> 
>> Georg Bauhaus wrote:
>>> Then, since we now have pragma Postcondition,
>>
>> "We" (Ada users) don't have pragma Postcondition. A specific
>> implementation may provide it, but it's not part of the standard.
> 
> True, but it's still safe to use it.

No. It is safe only if the expression has no side effects and yields true
in all possible program states.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Question on initialization of packages

[Jeffrey R. Carter]

Robert A Duff wrote:
> 
> True, but it's still safe to use it.  On GNAT, it works,
> and on other implementations (which don't support it),
> it does nothing.

Sure, but then

pragma Almost_Anything_You_Want [(...)];

can be used with any compiler. Saying "we have a pragma X" implies that it's 
part of the standard. "GNAT has a compiler-specific pragma X" is a better way to 
phrase it.

-- 
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