Unbounded_Stack Without Garbage Collection

Let's consider a version of Unbounded_Stack that will work without garbage collection. First, we remove the pragma Garbage_Collection from the module specification (or change it to Required => False). Otherwise, the module specification remains the same.

The module body becomes:

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;

         Result : constant Element is Top.Value;

      Pop : begin

         Top <- Top.Next;

         Temp'Free;

         return Result;

      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;

The only thing that changes is the body of Pop. The reason for the change should be clear.

Half-Constrained Arrays, Base Types, and Slicing

Array types can be unconstrained, half-constrained, or fully constrained. These are declared as:

type Name is array (Index_Type range <>) : Component_Type; -- Unconstrained.

type Name is array (Index_Type range Low .. <>) : Component_Type; -- Half constrained.

type Name is array (Index_Type[ range Low ..High]) : Component_Type; -- Constrained.

Note that the index subtype name is required. This is a requirement of range definitions in general, not of array type declarations.

A multi-dimensional array must have the same kind of constraint for all dimensions.

Type String is a half-constrained array type:

type String is array (General_Index_Value range 1 .. <>) : Character;

This can be considered shorthand for

type String'Base is array (General_Index_Value range <>) : Character;
subtype String is String'Base (General_Index_Value range 1 .. <>);

'Base can be applied to any array subtype to refer to the unconstrained base type.

Slicing a constrained or half-constrained array type yields a value of the base type. In the case of a half-constrained array, the result of slicing will slide when needed to meet the constraint of the half-constrained subtype. This applies, for example, in the case of passing a slice of a String to a subprogram that takes a String. The slice will slide to have a lower bound of 1.

It follows that libraries that manipulate half-constrained arrays need to carefully consider which parameters should be of the half-constrained subtype, and which of the unconstrained base type. An Index function into a String, for example, should take String'Base, so that the index into a slice is also the correct index into the original String.

Integer Types

All integer types are defined in NINA using is range:

type identifier is range expression .. expression;

The range expressions must be static universal integer expressions.

The compiler must accept all integer type declarations, regardless of their range. Most will be mapped to an underlying hardware integer; large ones may be mapped to two or more hardware integers chained together. The compiler may use the same representation as the predefined type Unbounded_Integer (see below) for integer types that would require more than two hardware integers to be chained together.

Consider an integer type declaration:

type Name is range Low .. High;

where the range can be implemented as a single hardware integer. This is equivalent to

type Name'Base is new appropriate_hardware_integer;

subtype Name is Name'Base range Low .. High;

If Low is negative, the appropriate_hardware_integer is signed and Name'Base is (roughly) symmetrical around zero; otherwise the appropriate_hardware_integer is unsigned.

Bitwise operations (and, or, xor, not) are defined for all integer types. Shift and rotate operations are defined as attribute operations for all integer types:

T'Shift_Left   : function (Value : in T'Base; Bits : in General_Count_Type) return T'Base;

T'Shift_Right  : function (Value : in T'Base; Bits : in General_Count_Type) return T'Base;

T'Rotate_Left  : function (Value : in T'Base; Bits : in General_Count_Type) return T'Base;

T'Rotate_Right : function (Value : in T'Base; Bits : in General_Count_Type) return T'Base;

Since the type of an object is known, these are also available in Object'Operation form:

V'Shift_Left : function (Bits : in General_Count_Type) return T'Base;

and so on.

All integer types have overflow checking on the base type. For an integer type without overflow checking, one can suppress the check on the type. This results in wrap-around semantics for the base type. Suppressing checks usually results in an erroneous program, but suppressing overflow checking on an integer type is an exception.

So far we have seen only one predefined integer type:

type General_Count_Type is range 0 .. 2 ** 64 - 1;

subtype General_Index_Type is General_Count_Type range 1 .. General_Count_Type'Last;

64 bits is available on many modern processors, and chaining two 32-bit integers together should be no problem on the rest. We rarely need to count more than 2 ** 64 - 1 items, so this should be adequate for most needs, and a larger range may be declared when needed. General_Index_Type is the index type for type String.

The compiler must calculate static universal integer expressions (and subexpressions where possible) exactly, no matter how large. This implies an unbounded-integer capability bounded only by available memory. NINA requires that this capability be made available to the user as the predefined type Unbounded_Integer. Unbounded_Integer may be used the same as any other integer type.

Garbage Collection

By default, NINA programs include garbage collection, but the language provides a way to create programs without garbage collection if that is needed. If a program should not include garbage collection, the main-program procedure should include "pragma Garbage_Collection (Enabled => False);" as the first thing in its declarative part. If this is omitted, or specifies "Enabled => True", then the program includes garbage collection.

Modules are often intended to be reusable; such modules should be designed to work correctly whether garbage is collected or not. This means that any module that does dynamic allocation should also do memory management. Allocated memory is released by using the 'Free procedure defined for every reference type:

procedure T'Free (Pointer : in out T);

Since the type of an object is known, one can also write "V'Free" for any object V of a reference type.

When garbage collection is active, 'Free acts as a hint to the garbage collector that the object is probably safe to collect.

Modules that require garbage collection can be marked with pragma Garbage_Collection as the first thing in the module specification, as we did with Unbounded_Stack. Although the pragma name is the same, the pragma parameter has a different name when it appears in a main-program procedure than when it appears in a module: Required for a module and Enabled for a main-program procedure.

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.

Body of Bounded_Stack

I guess it's time to see the body of the Bounded_Stack module:

Bounded_Stack : module body is

   Stack : module body is

      type Stack_Value is array (General_Index_Value range 1 .. Max_Size) : Element;

      Top   : General_Count_Value is 0;

      Value : Stack_Value;

      Push : procedure body (Item : in Element) is

         null;

      Push : begin

         Top <- Top + 1;

         Value (Top) <- Item;

      Push : exception

      when others =>

         raise;

      Push : end;

      Pop : function body return Element is

         null;

      Pop : begin

         Top <- Top - 1;

         return Value (Top + 1);

      Pop : exception

      when others =>

         raise;

      Pop : end;

      Length : function body return General_Count_Value is

         null;

      Length : begin

         return Top;

      Length : exception

      when others =>

         raise;

      Length : end;

      Is_Empty : function body return Boolean is

         null;

      Is_Empty : begin

         return Top = 0;

      Is_Empty : exception

      when others =>

         raise;

      Is_Empty : end;

      Is_Full : function body return Boolean is

         null;

      Is_Full : begin

         return Top = Max_Size;

      Is_Full : exception

      when others =>

         raise; 

      Is_Full : end;

   Stack : end;

Bounded_Stack : end;

None of these operations can raise an exception that can be handled in the operation's exception handler. The preconditions for Push and Pop are evaluated before execution gets to the elaboration of the subprograms' declarative regions, ensuring that Top has a value suitable for the operations performed on it, and the others have innocuous return expressions that cannot raise an exception (except Memory_Exhausted, which anything may raise).

Using the Bounded Stack

Here I'll use the Bounded_Stack module to output a program's input in reverse order.

use Bounded_Stack;
use NINA.IO.Text;

Reverse_Input : procedure body is

   type V_String (Length : General_Count_Value <- 0) is record

      Value : String (Length) <- String'(others => NUL);

   end V_String;

   "\" : function (Value : in String) return V_String;

   -- Converts Value to a V_String.

   module String_Stack is new Bounded_Stack (Element => V_String);

   "\" : function body (Value : in String) return V_String is

      null;

   "\" : begin

      return V_String'(Length => Value'Length, Value => Value);

   "\" : exception

   when others =>

      raise;

   "\" : end;

   Stack : String_Stack.Stack (Max_Size => 100);

Reverse_Input : begin

   Get_Input : loop

      exit Get_Input when NINA.IO.Text.End_Of_File or Stack.Is_Full;

      Stack.Push (Item => \NINA.IO.Text.Get_Line);

   Get_Input : end loop;

   if Stack.Is_Full then

      NINA.IO.Text.Put_Line (Item => "Too much input.");

   end if;

   Output : loop

      exit Output when Stack.Is_Empty;

      NINA.IO.Text.Put_Line (Item => Stack.Pop.Value);

   Output : end loop;

Reverse_Input : exception

when others =>

   null;

Reverse_Input : end;

Reverse_Input is an example of a main-program procedure body. Main-program procedure bodies are the only subprogram bodies that do not complete a subprogram specification, and the only subprograms at the library level.

"use" is NINA's equivalent of Ada's "with"; NINA has no equivalent of Ada's "use".

In Ada, a type like V_String might allocate enough space for the largest value, but two rules in NINA prevent this. First, a type like V_String is required to only allocate enough space for its current value (plus some small overhead). Second, objects that don't fit on the stack are required to be allocated on the heap. Between these two rules, a type like V_String works perfectly well in NINA, and is pretty much all that is needed for an unbounded string type.

Aggregates are required to be qualified.

"NUL" is the enumeration literal of Character'First.

"\" is a unary operator that exists for conversions. It was chosen to confuse people who like the C-family of languages.

The predefined type String is a half-constrained array type; the lower bound is constrained to 1, while the upper bound must be defined for each String object:

type String is array (General_Index_Value range 1 .. <>) : Character;

The rest should be fairly straightforward. Subprograms are required to have an exception handler with a "when others =>" part. Declarative parts are required to have at least one declaration; "null;" is an acceptable declaration if no others are needed.

Bounded Stack

Let's start with a bounded stack example.

Bounded_Stack : generic
   type Element is hidden and <-;
Bounded_Stack : module is
   type Stack (Max_Size : General_Index_Value) is module
      Push : procedure (Item : in Element) when not Is_Full;
      -- 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;

      Is_Full : function return Boolean;
      -- Returns Length = Max_Size;
   Stack : end;
Bounded_Stack : end;

The generic formal "type Element is hidden and <-;" specifies that the module will not use any operations of Element except assignment ("<-" in NINA) and any explicitly imported operations (none in this case). The actual must not be a no-assignment type. The similar generic formal "type Identifier is hidden;" specifies that the module will only use explicitly imported operations of the type; the actual may be a no-assignment type.

The "when Boolean_expression" part of the subprogram specifications is a precondition; these will be tested when the subprogram is called, and Constraint_Violation will be raised if the condition is False. 

Stack is a "module type." An object of a module type may be used exactly like a module. Module types are no-assignment types; assignment is not defined for them.

General_Count_Value and General_Index_Value are predefined subtypes similar to Ada's Natural and Positive from NINA_Predefined_Environment, NINA's equivalent of Ada's package Standard:

type General_Count_Value is range 0 .. 2 ** 64 - 1;

subtype General_Index_Value is General_Count_Value range 1 .. General_Count_Value'Last;

Introduction

Here I will present the programming language NINA, primarily by example. NINA is a language for programming by composition, based on my experiences with Ada. Probably no one will like NINA but me.