PPP Exercises: Libraries and Modules

Create a subdirectory '~/tycoon/src/Test'. Construct the following library 'Test' by saving it into a file called 'Test.tl' within this subdirectory.

library Test
with
   library machineenv
   library stdenv
   library bulkenv
interface
   Tree
module
   tree :Tree
end;

At the Tycoon toplevel enter the command 'do makeLibraries Test;' that

compiles this library, and
defines it as new root library.

Implement the module 'tree' (file 'tree.tm') satisfying the following interface 'Tree' (file 'Tree.ti'). Note that the files have to be saved within the subdirectory 'Test'.

interface Tree
export
   T(E <:Ok) <:Ok

   error :Exception end
  
   mkLeaf(E <:Ok  e :E) :T(E)
   (* Make a leaf node with element 'e'. *)
  
   mkNode(E <:Ok  left, right :T(E)) :T(E)
   (* Make an inner node with two subtrees 'left' & 'right'. *) 

   isLeaf(E <:Ok  t :T(E)) :Bool
   (* Return 'true' if 't' is a leaf, otherwise 'false'. *)

   getValue(E <:Ok  t :T(E)) :E
   (* Return the value of a leaf. Raise error if 't' is a node. *)

   getLeft, getRight(E <:Ok  t :T(E)) :T(E)
   (* Return left or right subtree of node 't'.
      Raise error if 't' is a leaf. *)
 
end;

To compile your module enter 'do make tree;' at the Tycoon toplevel.

Write a function 'printTree' that prints a formatted tree:

printTree(E <:Ok  t :tree.T(E)  fmt(:E) :String) :Ok

Test this function with a tree of the following structure:

      /\
     /  \
    /    \
   /      \
  /\      /\
 /  \    /  \
/\  /\  /\  /\
1 2 3 4 5 6 7 8

Ulrike Steffens, 1994