PPP Exercises: Generic abstract data types and implementations

Exercise:

1. This is the definition of an generic abstract data type for (functional) stacks. Write an implementation 'listStack' for this ADT using 'list'.
   

   Let FunStack =
      Tuple
         T(E <:Ok) <:Ok
         new(E <:Ok) :T(E)
         empty(E <:Ok  stack :T(E)) :Bool
         push(E <:Ok  element :E  stack :T(E)) :T(E)
         pop(E <:Ok  stack :T(E)) :T(E)
         top(E <:Ok  stack :T(E)) :E
      end;
   
   let listStack :FunStack =
      tuple
         Let T(E <:Ok) <:Ok = ... 
         let new(E <:Ok) :T(E)  = ...
          .
          .
          .
      end;	
   

2. Define and implement an abstract data type for stacks of integers 'intStack :IntStack' using 'listStack'.

1. Generic type definition.
   
2. Generic type implementation.
   
3. Choosing an instance of the generic type implementation.

                                    ____ Instance 1
		     Generic       |
	      ____    Type    _____|____ Instance 2
	     | 	  Implementation   |
	     |		           |        ...
	     |			   |
	     |	                   |____ Instance n
	     |	
	     |
             |                      ____ Instance 1
 Generic     |       Generic       |
  Type     __|___     Type    _____|____ Instance 2
Definition   |    Implementation   |
	     |			   |        ...
	     |			   |
	     |	                   |____ Instance n
	     |        ....	
             | 
             |                      ____ Instance 1
	     |	     Generic       |
	     |____    Type    _____|____ Instance 2
	      	  Implementation   |
	     			   |       ...
	     			   |
	     	                   |____ Instance n