\markboth{Thatte}{Thatte}
\documentstyle[11pt]{article}

\baselineskip=16pt

\raggedbottom

%\thispagestyle{empty}

\newcommand{\etc}{etc}
\newcommand{\etal}{{\em et al}}
\newcommand{\eg}{{\em e.g.}}
\newcommand{\ie}{{\em i.e.}}

\newcommand{\CC}{C\raisebox{0.4ex}{\scriptsize ++}}
\newcommand{\cc}{C\raisebox{0.5ex}{\tiny ++}}

% Standard Spacing for WISR - do not change!!
%
% Page dimensions.
%
\oddsidemargin  0.26in % Leave enough for binding margin
\evensidemargin 0.26in %
\topmargin      -1.00in % (adjusted for printer bias)
\headheight      .00in  % (no headers)
\headsep         .75in  % (top margin + headers + skip)
\footheight     12.0pt  % ??? (seems to work ok)
\footskip       25.0pt  % ??? ( "   "  )
\textheight     9.425in % (instructions: 9 1/8" min, 9 7/16" max)
\textwidth      6.5in   %
%
% Paragraph changes.
%

\markboth{Thatte}{Thatte}
\pagestyle{myheadings}

\parindent=0pt
\parskip=10pt
%
% can make the title box even smaller
%
\def\@maketitle{\vbox to 2.6in{\hsize\textwidth
    \linewidth\hsize \vfil \centering
    {\large \@title \par}
    \vskip 2em
    {\normalsize
    \begin{tabular}[t]{c}\@author
    \end{tabular}\par}
    \vfil} }


%\dump


\begin{document}
\bibliographystyle{ieeetr}

\title{Synthesizing Interface Stubs for Reusable Classes}

\author{Satish R. Thatt\'e \\ 
\\
Department of Mathematics and Computer Science\\ 
Clarkson University, Potsdam, NY 13699-5815 \\ 
Tel: (315) 268-2395 \\
E-mail: satish@sun.mcs.clarkson.edu\\
Fax: (315) 268-6670 \\
}

\date{}

\maketitle

\begin{abstract}

The problem of fitting together reusable components in spite of differences in
protocol and representation choices is well-known. I discuss a novel approach to
the protocol problem based on a formal logic of adaptability of interface types
to {\em automatically} synthesize interface stubs to achieve an exact fit between
the available ``socket'' for a reusable part and the actual part. The underlying
notion of  {\em adaptability} turns out to be related to but distinct from both
subtyping and inheritance.  The important related problem of data and object
mobility in the presence of representation differences such as those
between polar and cartesian representations of points appears to be
amenable to a solution based on transformational knowledge in the form of
equational laws used in conjunction with unification/matching techniques. 

\vspace{0.2in}
\noindent
{\bf Keywords:} class libraries, interface adaptation,
object mobility, stub generation

\vspace{0.2in}
\noindent
{\bf Workshop Goals:} Learning; networking; advance state of the
art of class libraries and object interoperability.

\vspace{0.2in}
\noindent
{\bf Working Groups:} reuse and OO methods, reuse and formal methods, tools
and environments, reuse education.

\end{abstract}

\newpage

\section{Background}

I have started to get involved in thinking and learning about reuse issues
in the context of object-oriented systems over the last year or so. My
background is in programming languages and type theory and I have recently
been working on some type-theoretic problems that have applications in
automatic stub generation for adaptation of object interfaces including 
data transformations based on knowledge expressed in the form of equational
theories. I am particularly interested in exploring the methods involved in
enhancing interoperability of classes and objects at both small and large
grained levels in environments that are heterogeneous in some sense
(ranging from hardware platforms to ``ontology'').


\section{Position}

This paper starts from the position that object technology is the most
promising vehicle for realizing the goal of large-scale software reuse.  This
is now a common perception that provides much of the motivation for the current
industry-wide shift towards  object-oriented software design methods.  
An obvious potential bottleneck in the practical realization of this vision is
the weakness of current component integration tools especially in the context of
heterogeneous systems, where heterogeneity is broadly understood to mean
anything ranging from different languages/hardware platforms to different
sources for code components.  This problem has been recognized and partly
addressed, \eg, in the CORBA \cite{OMG-CORBA} standard for distributed
components\footnote{Although the main motivation for CORBA comes
from distributed systems integration, CORBA-compliant ORB's may of course be used
for integrating objects located on the same node or even in the same address
space.}, and in IBM's SOM
\cite{IBM-SOM} library management system for class libraries. However, neither
CORBA nor SOM adequately deal with the inflexibility of the interfaces
(signatures) offered by objects to the outside world. I believe that such
inflexibility is at least a serious nuisance and could become a real problem
whether the objects are connected statically by being compiled together or are
dynamically connected using, say, CORBA's notion of a dynamic invocation
interface (DII). 

Focusing on the static (class library) case first, note that in the typical
lifecycle of a large component-based system, there are likely to be many
rebuilding episodes in which some of the old components are replaced by
functionally equivalent (or superior) new components.   For instance, in
replacing an old library of container classes with a better one, or in
accommodating an upgrade for a database system which also results in a
rationalization of the API.  In both cases, there is likely to be a protocol
mismatch between the expected and actual interfaces for the new objects.
The application programmer is now faced with the task
of somehow adapting the new objects to bridge the difference between their
expected and available interfaces---the obvious solution is to create stubs to
connect the old interfaces to the new ones\footnote{Even when the functionality
of a reused class needs to be extended to fulfill the requirements of the
application, the problem can often be {\em factored} into a stub generation
problem and an extension problem.}. The task is not difficult in principle; in
fact in most practical cases it is conceptually trivial. However, if a number of
interdependent classes are involved, along with the complications of
genericity, inheritance and overloading, the technical difficulty and
opportunity for error are likely to be substantial. Conceptual triviality
and technical complexity is a very uninviting combination for most people,
and as such the task of synthesizing interface stubs is likely to be
unwelcome and an obstacle to the optimal evolution of both class libraries and
component-based systems.  At the same time, its relatively mechanical nature 
makes it an inviting target for automatic inference.

The stub generation problem also occurs in both the static and dynamic
invocation interfaces of an ORB.  In the context of static invocation,
the interface repository is used in a way
that resembles the use of a class (or stub) library
and the remarks above about class libraries apply.  In using the DII, the
alternatives for an application are either to write complex code that can analyze
and use an  interface found in the repository in the form of what amounts to a
data-structure at run-time, or to assume a generic interface for the required
server and rely on the ORB to supply a dynamic stub-generation service to bridge
the protocol gap\footnote{Of course, there is theoretically the third option of
hand-coding a stub interactively once the required interface is found, but this
would require all users to be system experts.}, possibly with some interactive
help. The latter is obviously the more attractive option.

Conceptually there are two somewhat orthogonal issues in stub generation.
One is the formalization of ``compatibility'' between interface types that is
a generalization of substitutability in the usual subtyping
relation, and allows functionality preserving changes in method names, parameter
order, \etc.  The other is both built-in and user-definable mechanisms for type
isomorphism between parameter and result types of methods that would allow data
and object interchange between client and server objects in spite of differences
in representation and structure.  I have made some progress in  solving both
problems. The main ideas and current state of this work are summarized below.

\subsection*{Formalization of Compatibility\footnote{A detailed discussion
of current results is given in \cite{Thatte-popl94}.}}

Compatibility is a new kind of conformance that can be formalized using an {\em
adaptability} relation  between interface types, which is related to but distinct
from both subtyping and subclassing.  
As with the latter, the relation is quite simple except where
the object (interface) types are recursive.  Recursive interfaces are
 commonly found in small
library classes and are rare for large active components like servers. 

The main conceptual difficulty in formalizing the logic of adaptability is the 
misleading similarity of the concept with both subtyping and inheritance. 
Clearly, if a class $A$ can emulate
$B$, then an 
$A$-object can be used (with some disguise) where a $B$-object is needed.
Treating the disguise as a coercion, this sounds exactly like the normal
notion of subtyping.  However, a formal application of this intuition leads
to an impasse where obviously compatible interfaces cannot be shown to be
related. The main
insight needed to distinguish subtyping from adaptability is that 
adaptability is  bijective whereas subtyping is  injective, when both are
seen as mappings realized by coercions.  In other words, the set of objects
belonging to a subtype typically forms only a part of the set of objects
belonging to each of its supertypes, but if the interface of a class $A$ is
adapted to {\em implement} the interface specification of a class $B$, then every
$B$-object is emulated by a hidden $A$-object, and every $A$-object can be
converted to a $B$-object by attaching a suitable interface stub. These ideas
(along with certain functionality preserving protocol transformations) can be
formalized in a natural way in the form of a logic of adaptability  and stub
inference.   The inference process can also be automated using an algorithm that 
modifies and extends the (complete) subtype inference algorithm of Amadio
and Cardelli \cite{Amadio-Cardelli-popl91} for recursive types.

Some interesting issues arise in extending adaptability to generic classes. 
The main difficulty (assuming that their instantiation is user-specified) is
the representation of their interface types since the type parameters of
such classes are typically constrained by implicit assumptions about their
functionality---for instance they may be used in the implementation as
though they support certain operations. It has been found that representing
such constraints with full generality requires F-bounded polymorphism
\cite{CCHOM-fpca89} which is significantly more complex than ordinary
bounded polymorphism \cite{CarWeg85}. However, since the reusable generic
class and the actual parameters it is used with often come from different
domains (the latter typically from the application domain), it is natural to
use adaptability rather than  subtyping bounds for the parameters and the
proof-theoretic properties  of adaptability permit the use of ordinary
bounded polymorphism without loss of generality.  It is worth noting that
the interface adaptation of even a single generic class can be quite complex
since the actual parameters for it often need stubs, besides the stub needed
for the generic class itself.  

Some important issues relating to adaptability have yet to be addressed.  One is
the extension to frameworks, which can be thought of as collections of
classes related by subtyping and/or inheritance.   The existing logic
ensures that the application classes can be related by any {\em structural}
 subtyping relation consistent with  the subtyping relations among the
reusable classes used to implement them.  However, there are many unresolved
semantic issues. The entire framework is at present built around a simple
core-OOL based on the $\lambda$-calculus extended with labeled records. I
have not yet extended the logic or algorithms to account for the
idiosyncrasies of any realistic language.

\subsection*{Type Isomorphism for Flexible Data Transport 
between Clients and Servers}

This is a multifaceted problem with many existing approaches.  An
excellent survey of the current state of the art is given by Wileden,
\etal\,\,\cite{WWRT-CACM91}.  Most current systems support what one might
call {\em data structure isomorphism} (DSI) which is used in  data
transport among components based on different platforms (languages,
processors, operating systems).  The typical solution is to define a
universal data type definition notation (\eg, IDL \cite{OMG-CORBA} or XDR
\cite{Sun-Networking}) along with language bindings to translate
data to and from the standard format.  Data transformations
necessary for transport can then be automated---typical RPC stub generation
techniques already automate such transformations during transport for
distributed client-server interactions \cite{Sun-Networking}.  
The main shortcoming of DSI is its lack of support
for  bridging the differences between alternative representations of 
abstract types, such as the polar and cartesian representations of
points in a plane.  We need {\em abstract type} 
isomorphism (ATI) to fully support data mobility in a heterogeneous environment
when data formats differ in more than platform-specific idiosyncrasies. 
I am interested in exploring an approach where user knowledge about the
equivalence of various representations can be expressed declaratively in the form
of equational laws (seen as bijections with two-way coercions) between
representation types.  The problem of establishing equivalence between
representation types then reduces to the word problem in algebraic theories for
which there are well-established automated techniques based on canonical
term-rewriting.  There are good research tools available to experiment with these
techniques \cite{Kapur-Zhang-RRL,Larch-LP-TR}.  Inefficiencies due to multistage
transformations can be eliminated by using techniques such as deforestation
\cite{Wadler-deforestation} if the transformations are themselves expressed
declaratively using a functional language.  Note that such transformations are of interest whether or not encapsulation of data-representation is important.  

For a discussion of a closely related problem in the  context of
type reconstruction in functional languages, and the associated equational
unification theory, see \cite{Thatte-fpca91,Thatte-FAU93}.

\section{Comparison} \label{comparisons-section}

To my knowledge there has been no previous work on automated
tools for generating interface stubs of the kind described above,
but there are many frameworks and actual systems which provide a suitable
habitat for such an extension.  These are of two kinds: class library
management systems and component connection and interoperability
frameworks.  A few of these, along with some alternative approaches,
are described below.

IBM has implemented a class library framework called SOM
\cite{IBM-SOM}.  SOM provides language  neutral packaging and upwardly 
compatible binary libraries with support for dynamic linking which permits
changes without recompilation of clients and even cross-language subclassing
without access to source code.  SOM also supports the use of object-oriented
technology from procedural languages.   The interface stubbing techniques
described above clearly complement these strengths and would further enhance
the reusability of classes in SOM libraries.

Wileden, \etal\ \cite{WWRT-CACM91}, describe an approach to what they call
specification level interoperability which is quite similar in spirit to
the notion of abstract type isomorphism discussed above.  However, their
implementation appears to focus on pairs of language-specific stubs  to
ferry calls and results between static client-server pairs. They do not support
knowledge-based automated exploration/selection of possible isomorphisms
among representations.  In fact, the prototype described in the paper does
not support object mobility at all, although they do recognize the need for
it as a future extension.

CORBA \cite{OMG-CORBA} is perhaps now the most widely accepted framework for
interoperability of distributed components.  It contains DSI support for
data transport at a relatively high level of abstraction based on a type
definition facility called IDL.  The basic framework contains no notion of
automated support for interface adaptation or abstract type isomorphism
although both could be seen as ``components'' (in the CORBA terminology)
that define extensions of the basic functionality.
CORBA contains an interface repository which would be the natural habitat
for such an extension.

Bart \cite{Beach-ICSE92} is interesting as a concrete ORB
(although it does not claim adherence to the CORBA standard) that
exemplifies one currently popular approach to object mobility in
heterogeneous distributed systems.   Bart is realized as a single ``bus''
that carries (and stores) relational data and works  mainly in broadcast
mode.  The translation of all shared objects to and from the relational form
must be specified {\em explicitly} by the  developers of attached
components\footnote{There is a striking similarity to the shared
tuple-space of Linda.}.  This allows great flexibility since the
representations of objects can be mapped into tuples in arbitrary
ways\footnote{The flexibility is further enhanced in Bart by a Prolog-like
language called SGL that allows the definition of new
relations based on the extensionally represented ones.}. On the other hand,
it also means a lot more work as opposed
to automated  matching of (say) IDL versions of the representation types by
the bus.  Note also that automated interface stub
generation offers an alternative mode for object mobility in homogeneous
contexts where code as well as data is mobile.  This alternative respects
object encapsulation absolutely.  Such an alternative is not possible within
the Bart framework. 

Genesereth's facilitators \cite{Genesereth-agents} are much more ambitious
ORBs that support a strong distribution model as opposed to Bart's weak one
(there is no single shared bus---each component connects to others through
its own facilitator). Facilitators are supposed to use an extension of
first-order logic to exchange information about port specifications and to
negotiate connections using theorem proving techniques.  A similar but
simpler model is described by Konstantas \cite{Konstantas-Cells} where each
distributed component consists of a ``nucleus'' that communicates with
the outside world through a ``membrane'' (a kind of ORB) and the entire
system has a ``multicellular'' structure.   An interesting aspect of
membranes is that they contain interface type managers that negotiate type
compatibility with foreign membranes.  This appears to call for stub
generation techniques of the kind I propose.

\bibliography{thatte}

\section{Biography}

{\bf Satish R. Thatt\'e} is an Associate Professor of mathematics and 
computer science at Clarkson University.  The focus of his current research
is language design and software engineering issues connected with static
and dynamic type systems.  In the past he has worked in functional
programming and symbolic computation including term rewriting systems and
equational unification.  He has previously taught at the University of
Michigan and the University of California at San Diego.  He received a Ph.D.
in Computer Science from the University of Pittsburgh in 1982.


\end{document}



