Wednesday, August 29, 2018

Comparison of Array Based Stacks in C and Ada


Comparison of Array Based Stacks in C and Ada

The stack is one of the simplest data structures. Array-based stacks can be implemented in all languages supporting arrays, even including early versions of Fortran which did not support pointers.

This comparison is based upon C code published at http://www-cs.ccny.cuny.edu/~peter/dstest.html
The C code published at http://www-cs.ccny.cuny.edu/~peter/dstest.html supports the book Advanced Data Structures authored by Peter Braß and published by Cambridge University Press.

The Ada code uses Ada2012, which added aspect specifications, pre and post conditions, type invariants and subtype predicates to the Ada language. Descriptions of these and other features added in the Ada 2012 version are available at The Ada 2012 Rationale

Array Stack

The C code for Array Stack is shown below.

Example 1 ArrayStack.c
#include <stdio.h>
#include <stdlib.h>

typedef int item_t;

typedef struct {item_t *base; item_t *top; int size;} stack_t;

stack_t *create_stack(int size)
{   stack_t *st;
    st = (stack_t *) malloc( sizeof(stack_t) );
    st->base = (item_t *) malloc( size * sizeof(item_t) );
    st->size = size;
    st->top = st->base;
    return( st );
}

int stack_empty(stack_t *st)
{   return( st->base == st->top );
}

int push( item_t x, stack_t *st)
{   if ( st->top < st->base + st->size )
    {   *(st->top) = x; st->top += 1;  return( 0 );
    }
    else
       return( -1 );
}

item_t pop(stack_t *st)
{   st->top -= 1;
    return( *(st->top) );
}

item_t top_element(stack_t *st)
{   return( *(st->top -1) );
}

void remove_stack(stack_t *st)
{   free( st->base );
    free( st );
}



int main()
{  stack_t *st;
   char nextop;
   st = create_stack(50);
   printf("Made Array-Based Stack of size 50\n");
   while( (nextop = getchar())!= 'q' )
   { if( nextop == 'i' )
     { int insitem;
       scanf(" %d", &insitem);
       push( insitem, st );
       printf(" pushed %d. The current top item is %d\n", insitem,
           top_element(st) );
     } 
     if( nextop == 'd' )
     { int de_item;
       getchar();
       de_item = pop(st);
       printf("  popped item %d", de_item);
       if( stack_empty(st) )
         printf(" the stack is now empty\n");
       else
         printf(" the top element is now %d\n",  top_element(st) );

     }
     if( nextop == '?' )
     { getchar();
       if( stack_empty(st) )
         printf("the stack is empty\n");
       else
         printf("the top element is %d\n", top_element(st) );
     }
    
   }
   remove_stack(st);
   printf(" removed stack\n");
   return(0);
}

The author claims that his book is not a text on Object Oriented Programming, but instead a text on advanced data structures.  None of the examples in the URL referenced above employ C header files. I assume that was done to simplify publication, placing both the data structure, including its associated functions, and a main program to demonstrate the structure, in a single file.

Issues with ArrayStack.c

While the author could have used array indexing to access the values of the array at the heart of the stack_t struct, he chose to perform pointer arithmetic directly. From a style point of view it is often preferred to use array indexing to access the elements of an array.

The push function

Example 2 push function
int push( item_t x, stack_t *st)
{   if ( st->top < st->base + st->size )
    {   *(st->top) = x; st->top += 1;  return( 0 );
    }
    else
       return( -1 );
}
Note that this code only actually pushes a value onto the stack if the stack is not full. This is a correct behavior. When the array is full this function returns -1.
Example 3 Calling push
   while( (nextop = getchar())!= 'q' )
   { if( nextop == 'i' )
     { int insitem;
       scanf(" %d", &insitem);
       push( insitem, st );
       printf(" pushed %d. The current top item is %d\n", insitem,
           top_element(st) );
     } 

The example  of calling the push function ignores the return value. This means that the push operation fails silently. The user is given no indication that the push fails. In fact, the printf statement following the push function call tells the user that the push succeeds, whether it does nor not.

The pop function

Example 4 The pop function
item_t pop(stack_t *st)
{   st->top -= 1;
    return( *(st->top) );
}
Please note that the pop function does not check for an empty stack. Logically, it is erroneous to pop a value from an empty stack. This function simply decrements the pointer st->top and returns whatever value is at that memory location. Since no check is made for an empty stack, the result can be to return the value at some memory location before the first element of the dynamically allocated array pointed to by st->base. This is a form of buffer overflow.
The main function calls the pop function before checking if the stack is empty. Checking the state of the stack before calling pop would be the correct behavior. Nothing in the main function prevents pop from being called when the stack is empty.
     if( nextop == 'd' )
     { int de_item;
       getchar();
       de_item = pop(st);
       printf("  popped item %d", de_item);
       if( stack_empty(st) )
         printf(" the stack is now empty\n");
       else
         printf(" the top element is now %d\n",  top_element(st) );

     }
If the pop function is called several times when the stack is empty the st->top pointer will continue to be decremented. If, after that the push function is called, the pushed value will be assigned to a memory location before the first element of the array, corrupting memory outside of the array.

The top_element function

A somewhat milder version of the problem with the pop function is present in the top_element function. This function returns the value of in the address one less than the current st-top pointer.
Example 5 The top_element function
item_t top_element(stack_t *st)
{   return( *(st->top -1) );
}
As you can see, the top_element function does not check for an empty stack.

The stack_empty function

Example 6 The stack_empty function
int stack_empty(stack_t *st)
{   return( st->base == st->top );
}
Note that this function will only return True when st->top points to the first element of the allocated array. It will return False when st->top points to any memory location before the beginning of the array. Since the function pop can move the pointer st->top to memory locations before the beginning of the array this function is highly unreliable.

Conclusions concerning ArrayStack.c

While this code may convey the general approach to implementing an array-based stack data structure, the actual implementation is faulty in many ways. All of the faults are associated with the primitive implementation of arrays in the C language. C arrays are simply a block of memory accessed by pointers. C provides no array bounds checking.
The code for this implementation may execute very efficiently, but it does no good when the code is executing erroneously.

Bounded_Stack

The Ada code for a bounded stack type is shown below. The following example implements a generic stack using an array with the size of the array determined at compile time.
Ada requires a package to implement both a specification, which is analogous to a C header file, and a body, which contains the implementation of the procedures and functions declared in the specification.

The file bounded_stack.ads

The file bounded_stack.ads contains the interface specification for a generic stack based upon an array.
generic
   type Element_Type is private;
   Default_Value : Element_Type;
package Bounded_Stack is
   type Stack(Size : Positive) is tagged private;
   function Is_Empty(Item : Stack) return Boolean;
   function Is_Full(Item : Stack) return Boolean;
   procedure Push(Item : in out Stack; Value : in Element_Type) with
     Pre => not Is_Full(Item),
     Post => not Is_Empty(Item);
   procedure Pop(Item : in out Stack; Value : out Element_Type) with
     Pre => not Is_Empty(Item),
     Post => not Is_Full(Item);
   function Top(Item : in Stack) return Element_Type with
     Pre => not Is_Empty(Item);
   procedure Clear(Item : in out Stack) with
     Post => Is_Empty(Item);
private
   type Buffer is array(Positive range <>) of Element_Type;
   type Stack(Size : Positive) is tagged record
      Buf   : Buffer(1..Size) := (Others => Default_Value);
      Index : Positive := 1;
      Count : Natural  := 0;
   end record;
end Bounded_Stack;
This is a generic package, as indicated by the reserved word “generic” at the start of the file. This package has two generic parameters; Element_Type, which designates any non-limited type, and Default_Value, which is used to initialize every instance of the stack with a properly define default value.
Declaring the type Stack to be private means that the details of the type are hidden from any calling subprogram or task. The subprogram declarations following the type declaration, and preceding the reserved word “private” are the only means given to manipulate the stack.

The procedure Push

Example 7 The procedure Push
   procedure Push(Item : in out Stack; Value : in Element_Type) with
     Pre => not Is_Full(Item),
     Post => not Is_Empty(Item);
The declaration of the procedure Push contains a lot of information.
The parameter Item must be an instance of the type Stack. The parameter Item will be modified during the execution of the procedure Push. The parameter Value is an instance of Element_Type, and it will not be modified during execution of the procedure Push.
The procedure Push has a simple pre-condition, namely that the instance of Stack passed to this procedure cannot be full before calling Push.
The procedure Push has a simple post-condition, namely that the instance of Stack passed to the procedure Push will not be empty upon completion of the procedure Push.
The pre-condition and the post-condition are enforced by the compiler.

The procedure Pop

Example 8 The procedure Pop
   procedure Pop(Item : in out Stack; Value : out Element_Type) with
     Pre => not Is_Empty(Item),
     Post => not Is_Full(Item);
The procedure Pop also contains a lot of information.
The parameter Item is an instance of Stack which will be modified during the execution of the procedure Pop.
The parameter Value is an instance of Element_Type which will be set during the execution of the procedure Pop.
The pre-condition for procedure Pop is that the instance of Stack passed to the procedure cannot be empty.
The post-condition for procedure Pop is that the instance of Stack passed to the procedure will not be full upon completion of the procedure Pop.

The function Top

The function Top returns the value of the stack top stack element without changing the stack itself.
Example 9 The function Top
   function Top(Item : in Stack) return Element_Type with
     Pre => not Is_Empty(Item);
The parameter Item is an instance of the type Stack which is not modified during execution of the function Top.
The pre-condition for the function Top is that the instance of Stack passed to the function cannot be empty.

The procedure Clear

The procedure clear empties a stack.

   procedure Clear(Item : in out Stack) with
     Post => Is_Empty(Item);
Clear modifies the instance of Stack passed to it.
The post-condition specifies that the instance of Stack will be empty upon completion of the procedure Clear.

The file Bounded_Stack.adb

The file Bounded_Stack.adb contains the implementation of all the functions and procedures declared in the package specification.
All the code within the package body contained in the file Bounded_Stack.adb has visibility to all the code in the file Bounded_Stack.ads.
package body Bounded_Stack is

   --------------
   -- Is_Empty --
   --------------

   function Is_Empty (Item : Stack) return Boolean is
   begin
      return Item.Count = 0;
   end Is_Empty;

   -------------
   -- Is_Full --
   -------------

   function Is_Full (Item : Stack) return Boolean is
   begin
      return Item.Count = Item.Size;
   end Is_Full;

   ----------
   -- Push --
   ----------

   procedure Push(Item : in out Stack; Value : in Element_Type) is
   begin
      Item.Buf(Item.Index) := Value;
      Item.Index := Item.Index + 1;
      Item.Count := Item.Count + 1;
   end Push;

   ---------
   -- Pop --
   ---------

   procedure Pop (Item : in out Stack; Value : out Element_Type) is
   begin
      Value := Item.Top;
      Item.Index := Item.Index - 1;
      Item.Count := Item.Count - 1;
   end Pop;

   ---------
   -- Top --
   ---------

   function Top (Item : in Stack) return Element_Type is
   begin
      return Item.Buf(Item.Index - 1);
   end Top;

   -----------
   -- Clear --
   -----------

   procedure Clear(Item : in out Stack) is
   begin
      Item.Count := 0;
      Item.Index := 1;
   end Clear;

end Bounded_Stack;
You may notice that the implementations of the functions and procedures in Bounded_Stack.adb are very simple. There is no explicit check for empty or full stack conditions. The pre-conditions specified in each procedure or function specification are implicitly checked by code generated by the compiler. The post-conditions specified for each procedure or function are implicitly checked by code generated by the compiler. Failure of any specified pre-condition or post-condition results in an exception which, if unhandled,  terminates the program.

The file main.adb

with Bounded_Stack;
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure Main is
   package Int_Stack is new Bounded_Stack(Element_Type  => Integer,
                                          Default_Value => 0);
   use Int_Stack;
   My_Stack : Stack(Size => 10);
   Value : Integer;
begin
   while not My_Stack.Is_Full loop
      Put("Enter an integer: ");
      Get(Value);
      My_Stack.Push(Value);
   end loop;
   Put_Line("Printing and popping the stack:");
   while not My_Stack.Is_Empty loop
      My_Stack.Pop(Value);
      Put_Line(Integer'Image(Value));
   end loop;
   My_Stack.Pop(Value);
   Put_Line(Integer'Image(Value));
end Main;

The output of this program is:

Enter an integer: 1
Enter an integer: 2
Enter an integer: 3
Enter an integer: 4
Enter an integer: 5
Enter an integer: 6
Enter an integer: 7
Enter an integer: 8
Enter an integer: 9
Enter an integer: 0
Printing and popping the stack:
 0
 9
 8
 7
 6
 5
 4
 3
 2
 1

raised SYSTEM.ASSERTIONS.ASSERT_FAILURE : failed precondition from bounded_stack.ads:12 instantiated at main.adb:6
The main procedure pops all the values off the stack then attempts to pop one more value off the stack. Rather than corrupting the stack pointer the program raises the exception SYSTEM.ASSERTIONS.ASSERT_FAILURE. The exception message points to the pre-condition for the pop procedure requiring the stack to be not empty.

Comparison of three algorithms for summing an array of integers

This article shares a comparison of the time taken to sum an array of integers. This article tests three algorithms for summing the array. •...