Unbounded Stack

Let's take a look at an unbounded version of a stack, for comparison.

Unbounded_Stack : generic
   type Element is hidden and <-; 
Unbounded_Stack : module is
   pragma Garbage_Collection (Required => True);
 
   type Stack is module
      Push : procedure (Item : in Element);
      -- Adds Item to the top of the stack.

      Pop : function return Element when not Is_Empty;
      -- Removes the top Element from the stack and returns it.

      Length : function return General_Count_Value;
      -- Returns the number of Elements on the stack.

      Is_Empty : function return Boolean;
      -- Returns Length = 0;
   Stack : end;
Unbounded_Stack : end;

This is quite similar to the specification for the bounded stack. The main difference is that an unbounded stack doesn't have a maximum size, and the concept of "full" has no meaning.

So what happens if you attempt to Push onto the stack when there isn't enough memory for an additional Element? In that case, the predefined exception Memory_Exhausted will be raised.

"pragma Garbage_Collection" in a module indicates if the module requires garbage collection; this module does. If the pragma is omitted, or specifies "Required => False", then the module does not require garbage collection.

Unbounded_Stack : module body is

   Stack : module body is

      type Node;

      type Node_Ptr is reference Node;

      type Node is record

         Value : Element;

         Next  : Node_Ptr;

      end Node;

      Top : Node_Ptr;

      Push : procedure body (Item : in Element) is

         null;

      Push : begin

         Top <- new Node'(Value => Item, Next => Top);

      Push : exception

      when others =>

         raise;

      Push : end;

      Pop : function body return Element is

         Temp : constant Node_Ptr is Top;

      Pop : begin

         Top <- Top.Next;

         return Temp.Value;

      Pop : exception

      when others =>

         raise;

      Pop : end;

      Length : function body return General_Count_Value is

         Result : General_Count_Value is 0;

         Temp   : Node_Ptr is Top;

      Length : begin

         Count : loop

            exit Count when Temp = null;

            Result <- Result + 1;

            Temp <- Temp.Next;

         Count : end loop;

         return Result;

      Length : exception

      when others =>

         raise;

      Length : end;

      Is_Empty : function body return Boolean is

         null;

      Is_Empty : begin

         return Top = null;

      Is_Empty : exception

      when others =>

         raise;

      Is_Empty : end;

   Stack : end;

Unbounded_Stack : end;

reference is NINA's equivalent to Ada's access; I chose "reference" because it's longer and so might discourage unnecessary use.

The simple, singly linked list used here should be clear to anyone familiar with dynamic data structures.

There's no need for manual memory management in Pop because NINA has garbage collection by default. It can be turned off when desired, but in that case you could not use Unbounded_Stack. This module is designed for systems with garbage collection, and NINA's rules prevent it from being used in a system without garbage collection, but modules designed for systems without garbage collection can also be used in systems with garbage collection.