\documentstyle[tgrind,fullpage,epsf,ncs]{article}
\title{Implementing Data Abstractions}
\author{Greg Hudson}

\newcommand{\ptable}{{\tt p\_table}}
\newcommand{\wtdigraph}{{\tt wt\_digraph}}
\newcommand{\pstest}{{\tt ps2\_test}}
\newcommand{\nodeid}{{\tt node\_id}}

\newcommand{\psbox}[3]{\mbox{\special{psfile=#1}\hspace{#2}\rule{0pt}{#3}}}

\begin{document}

\maketitle
\section{Introduction}

In this problem set, we were asked to implement and test two data
types, a parametrized table (\ptable) and a weighted directed graph
(\wtdigraph).

I chose to implement \ptable\ in a simple, inefficient manner.  If
necessary, \ptable\ can be optimized later without changing any of the
code that uses it.  I chose to implement \wtdigraph\ in terms of
\ptable, so that a more efficient \ptable\ would also yield a more
efficient graph.

\section{Amendments to the Specification}

The original specification needed some modification, and I needed to
add a couple of operations to \ptable\ in order to support all the
operations I needed in the weighted digraph.

I require that \ptable\ have an \verb+equal+ operation on its key
type, since it is not possible to determine if a new key is equivalent
to any existing keys without an equality test.

The {\tt unparse} operation on \ptable\ requires that both its key
types and value types have an \verb+unparse+ operation.
Unfortunately, this means that you cannot unparse tables whose key
types or value types are strings or characters, but CLU makes it
exceedingly difficult or impossible to special-case these types.

I chose to add {\tt keys} and \verb+keys_and_values+ operations to
\ptable, primarily because I needed them for \wtdigraph.  However,
these operations are not specific to \wtdigraph, and I consider
traversal of keys and (key, value) pairs to be an important part of a
table abstraction.

The \wtdigraph\ specification had a slight bug in the signature of
\verb+successors_and_weight+, which should have \verb+yields(node_id,
int)+ in place of \verb+yields(node, int)+.

The specification of \verb+add_edge+ in \wtdigraph\ is a little bit
unclear; I replaced ``Signals {\em duplicate} if the edge already
exists'' with ``Signals {\em duplicate} if an edge from {\em initial}
to {\em final} already exists in {\em graph}.''

I also felt free to change the variable names in my specifications,
along with small details of the text, while leaving the meaning of the
specification intact.  In a couple of cases in the \wtdigraph\
specification, I corrected typos where the specification referred to a
nonexistent argument.

\section{Overall Structure}

The program has three modules, named \ptable, \wtdigraph, and
\pstest.

The module \ptable\ implements a parametrized table.  It includes
operations to add, change, delete, look up, and enumerate associations
between an arbitrary key type and value type.

The module \wtdigraph\ implements a weighted directed graph.  It
includes operations to add nodes, to add, delete, and change the
weights of edges between nodes, and to enumerate the nodes in the
weighted graph.

The module \pstest\ implements the \verb+start_up+ procedure, and
performs black-box and glass-box testing of the \ptable\ and
\wtdigraph\ data abstractions.

The following diagram shows the dependencies between the modules; an
arrow from one module to another indicates that the first module
depends on the second.

\bigskip
\epsfbox{mdd.eps}

\section{Module Specifications}

I have not included a specification for \pstest, since it is trivial
(the \verb+start_up+ procedure).

\subsection{Specification For the Parametrized Table Abstraction}

\begin{verbatim}

p_table = data type[key_t, value_t: type] is create, lookup, insert, change,
    delete, empty, keys, keys_and_values, unparse
    where key_t has equal: proctype(key_t, key_t) returns(bool)
    
    Overview
    A parametrized table is a mutable structure associating keys of type
    key_t with value of type value_t.
    
    create = proc() returns(cvt)
        Effects    Creates and returns an empty table.
    
    lookup = proc(table: p_table[key_t, value_t], key: key_t) returns(value_t)
        signals(not_found)
        Effects    If there is an entry in <talbe> whose key matches
                   <key>, returns its associated value.  Signals
                   not_found if there is no entry whose key matches
                   <key>.

    insert = proc(table: cvt, key: key_t, value: value_t) signals(duplicate)
        Modifies   <table>
        Effects    Modifies <table> by inserting an entry whose key is
                   labelled <key> and whose associated value is <val>.
                   Signals duplicate if a key labeled <key> already
                   exists.

    change = proc(table: cvt, key: key_t, new_val: value_t) signals(not_found)
        Modifies   <table>
        Effects    Modifies <table> by changing the value associated
                   with <key> to <new_val>.  Signals not_found if there
                   is no entry whose key is <key>.

    delete = proc(table: cvt, key: key_t) signals(not_found)
        Modifies   <table>
        Effects    Modifies <table> by removing the entry whose key is
                   Signals not_found if there is no entry whose key is
                   <key>.

    empty = proc(table: cvt) returns(bool)
        Effects    Returns true if there are no entries in <table>,
                   otherwise returns false.

    keys = iter(table: cvt) yields(key_t)
        Effects    Yields each key in <table> exactly once.
    
    keys_and_values = iter(table: cvt) yields(key_t, value_t)
        Effects    Yields each <key, value> pair in <table> exactly
                   once.

    unparse = proc(table: p_table[key_t, value_t]) returns(string)
        where key_t has unparse: proctype(key_t) returns(string),
              value_t has unparse: proctype(value_t) returns(string)
        Effects    Returns a human-readable string that describes the
                   current contents of <table>.
        
  end p_table

\end{verbatim}

\subsection{Specification For the Weighted Directed Graph Abstraction}

\begin{verbatim}

wt_digraph = data type is create, add_node, add_edge, add_node_and_edge,
    remove_edge, change_weight, edge_weight, nodes, successors_and_weight,
    unparse
    
    Overview
    wt_digraph is a mutable directed graph with edge weights.
    
    create = proc() returns(cvt)
        Effects    Creates and returns an empty wt_digraph.
    
    add_node = proc(graph: cvt, node: node_id) signals(duplicate)
        Modifies   <graph>
        Effects    Modifies <graph> by inserting <node>.  Signals
                   <duplicate> if there is already a node of that name.
    
    add_edge = proc(graph: cvt, initial, final: node_id, weight: int)
        signals(no_node(string), duplicate)
        Modifies   <graph>
        Effects    Modifies <graph> by inserting an edge from the
                   node <initial> to the node <final> with edge
                   weight <weight>.  Signals no_node if <initial> or
                   <final> is not the name of a node in <graph>, and
                   returns the name of the missing node.  Signals
                   <duplicate> if the edge already exists.
    
    add_node_and_edge = proc(graph: cvt, initial, new: node_id, weight: int)
        signals(no_node(string), duplicate)
        Modifies   <graph>
        Effects    Modifies <graph> by inserting a node named <new> and
                   inserting an edge from the node <initial> to the
                   node <new> with the edge weight <weight>.  Signals
                   no_node if <initial> is not the name of a node in
                   <graph>, and returns the name of the missing node.
                   Signals duplicate if a node named <new> already
                   exists.  <graph> is not modified if either
                   exception is raised.
    
    remove_edge = proc(graph: cvt, initial, final: node_id) signals(no_edge)
        Modifies   <graph>
        Effects    Modifies <graph> by removing the edge from the
                   node <initial> to the node <final>.  Signals
                   no_edge if the edge does not exist.
    
    change_weight = proc(graph: cvt, initial, final: node_id, weight: int)
        signals(no_edge)
        Modifies  <graph>
        Effects    Modifies <graph> by changing the weight to
                   <weight> on the edge from the node <initial> to the
                   node <final> in <graph>.  Signals no_edge if the
                   edge does not exist.
    
    edge_weight = proc(graph: cvt, initial, final: node_id) returns(int)
        signals(no_edge)
        Effects    Returns the weight on the edge from the node
                   <initial> to the node <final> in <graph>.  Signals
                   no_edge if an edge from <initial> to <final>
                   already exists in <graph>.
    
    nodes = iter(graph: cvt) yields(node_id)
        Effects    Yields each node in <graph> exactly once.
    
    successors_and_weight = iter(graph: cvt, initial: node_id)
        yields(node_id, int)
        signals(no_node(string))
        Effects    Yields each direct successor in <graph> of the
                   node <initial> exactly once together with the
                   weight on the edge to it from <initial>.  Signals
                   no_node if the node <initial> does not exist, and
                   returns the name of the missing node.
    
    unparse = proc(graph: cvt) returns(string)
        Effects    Returns a human-readable string that describes the
                   current contents of <g>.
    
  end wt_digraph

\end{verbatim}

\section{Module Implementations}

\subsection{Implementation of the Parametrized Table Abstraction}

I initially considered the possibility of implementing \ptable\ with a
hash table.  Unfortunately, the restriction on recursive types in CLU
makes it impossible to define linked lists within a data abstraction,
so a hash table which used chaining to resolve collisions would
require implementing a separate list type.  More importantly, a
hashing \ptable\ would require a \verb+hash+ operation on the key
type; I regarded this as unnacceptable, since the built-in string type
in CLU does not have a hash operation, strings are common key types
for tables, and built-in CLU types cannot be extended.

Neither did I want to require an ordering of the keys, so I did not
implement \ptable\ with a binary tree.  Instead, I used a simple
linear array of (key, value) associations.

A search for the association of a key takes O(n) time in this
implementation, so insertion, deletion, and mutation of associations
all take O(n) time.

The implementation of all \ptable\ operations except for \verb+unparse+
is trivial.  A private operation \verb+search+ searches for an
association with a given key; from there, most operations are simple
if-then-else statements.

My implementation of \verb+unparse+ is somewhat inscrutable, because
the problem set requires that I implement it in O(n) time.  Therefore,
I use a character array intead of multiple string append operations.
If CLU provided a built-in mutable string type, this would be
preferrable.

\tgrindfile{p_table.tex}

\subsection{Implementation of the Weighted Digraph Abstraction}

In order to implement \wtdigraph, I first decided to think about the
graph as a map from nodes in the graph to their adjacency lists; in
turn, I treat the adjacency list of a node N as a map from the
destination nodes of each edge emerging from N to the weights of those
edges.

Because I happen to have a convenient type for implementing maps with
finite domains, I implement \wtdigraph\ as a \ptable\ with key type
\nodeid and value type \verb+association_list+, where
\verb+association_list+ is in turn a \ptable\ with key type \nodeid and
value type \verb+integer+.

With this implementation, all operations are trivial.  Each directed
graph operation corresponds to at most three parametrized table
operations.  Most of the work is in mapping the \ptable\ exceptions
onto the appropriate \wtdigraph\ exceptions.

\tgrindfile{wt_digraph.tex}

\subsection{Implementation of the Testing Module}

These are all very straightforward.  Often a test depends on the state
produced by a previous test, so care should be taken while modifying a
particular test.

\tgrindfile{ps2_test.tex}

\section{Validation Strategy}

Probably the most important aspect of my validation strategy is
choosing a simple implementation.  Because all of my procedures
involve a few lines of code and no hard concepts, it is unlikely that
any of them will be in error.

I also validate the \ptable\ and \wtdigraph\ types with rigorous,
near-path-complete testing, in the module \pstest.  I test each loop
with zero, one, and two iteration, and all paths through code which
does not involve loops.

For each operation, I implement black-box tests and glass-box tests.
Because the implementations are so simple, the black-box tests are
often path-complete by themselves, so I do not always have separate
glass-box tests.

\end{document}

