\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{2}

% DEFINE THE DUE DATE
\def\due{February 19, 1991}

% title command
\newcommand{\mytitle}{{\large\noindent 6.170 \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
\newcommand{\mypage}{\newpage{\large\noindent 6.170 \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\noindent{\fbox{\large\bf Problem #1}}\vspace{.25in}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\begin{document}

\mytitle

\begin{center}
{\Large\bf Implementing Data Abstractions}
\end{center}

\prob{1: A String Table}

For the implementation of {\em string-table}, I changed three things in
the specifications. First, I added a {\bf where} clause to the header.
It states that the parameterized type {\em vt} must have an {\bf
unparse} function. The complete header is now:

\begin{verbatim}
string_table = cluster [vt: type] is create, lookup, insert, change, delete, 
                                     empty, keys, keysnvals, unparse
    where vt has unparse: proctype (vt) returns (string)
\end{verbatim}

\noindent I did this to make the implementation of the {\bf unparse}
function for {\em string-table} easier; I didn't have to deal with value
types that didn't know how to unparse themselves into strings.

The last two changes I made to the specs were the addition of two
iterators for {\em string-table}: {\bf keys} and {\bf keysnvals}. Here
are the specs for these interators:

\begin{verbatim}
   keys = iter (t: string_table) yields (string)
       % effects  Yields each key in the table exactly once
   keysnvals = iter (t: string_table) yields (string, vt)
       % effects  Yields each key-value pair in the table exactly once
\end{verbatim}

\noindent I added these iterators because they seemed generally useful,
and because they made implementing the {\em wt-digraph} cluster easier.

Generalizing the {\em string-table} abstraction would be relatively
simple. The generalized {\em table} abstraction wouls have two
parameterized types, one for the keys and one for the values. The header
would look something like:

\begin{verbatim}
table = cluster [kt: type, vt: type] is create, lookup, insert, change, 
                                        delete, empty, keys, keysnvals, 
                                        unparse
\end{verbatim}

\noindent The keys would now be treated like the values were treated
originally. Whenever a key is an argument or result, instead of putting
{\em string} as its type, put {\em kt} as its type. Certain
restrictions, like the key type {\em kt} must have an {\bf equal}
procedure, will have to be put on the range of types that can be a key
type.

As for my choice of underlying representation for {em string-table}, I
chose to use records to represent key-value pairs since records are
mutable, as is needed by the mutablity of a {\em string-table}. Again, I
choose an array to represent the table since it mutable, as well as easy
to deal with.

\mypage

\prob{2: A Weighted Directed Graph}

For the implementation of {\em wt-digraph}, I did not change any of the
specifications. My original choice of representation was not the {\em
string-table} of {\em string-table} of {\em int}. I had originally tried
to implement it using arrays and records. However, in the process of
coding, I found it cumbersome and inefficient; handling exceptions
became a problem. Therefore, I looked at implementing it using {\em
string-table}. I found that most of the code I had needed was already
written in {\em string-table}. Because of the exception generation in
{\em string-table}, exception handling (and generation) in {\em
wt-digraph} became much easier. In my first implementation, I was
duplicating most of the code I wrote in {\em string-table}. One tradeoff
to using {\em string-table} to implement {\em wt-digraph}, however, it
that the number of loops executed for a particular procedure in {\em
wt-digraph} is hidden. Thus, it is not easy to judge the performance (in
terms of speed) of {\em wt-digraph} by just looking at the code. But the
ease in implementation using {\em string-table} makes up for this.

\vspace{.25in}
\prob{Testing strategy}

My testing strategy was rather simple. For black-box testing, I made
sure that my code behaved according to how the specifications said it
would perform. I checked the normal cases and the cases in which
exceptions were raised. For glass-box testing, I tested the possible
paths through my code that were not tested by the black-box testing. For
example, I tested the behavior of loops for zero, one, and many passes
through the loop. In the case of testing {\em wt-digraph} I found that
all possible paths through the code were tested by the black-box
testing. This is mainly because I had no internal loops (other than for
the iters) in my code.The test cases are not always path-complete. For
example, testing the behavior of a loop for zero through infinite passes
would be infeasible.

\end{document}
