\documentstyle[twocolumn,icse99]{article}

% Changes: 
%  References to 97 are now to 99
%  Page limit is now 10 pages instead of 11
%  Abstract limit is now 200 words instead of 100
%  Contact information is now icse99@cs.cmu.edu and 412-268-5056.
%  Acknowledgements have been changed to note ICSE 97 contribution.
%  URL for author kit changed: needs to be filled in.
%  All other font and sizing information is the same:
%    check whether it still applies.

\newcommand\sel{\; \; | \; \;}
\newcommand\WF{\mbox{\sf WF}}
\newcommand\Source{\mbox{\sf Source}}
\newcommand\Target{\mbox{\sf Target}}
\newcommand\Graph{\mbox{\sf Graph}}

\def\imp{\rightarrow}
\def\edge#1#2#3{#1\stackrel{#2}{\imp}#3}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\OO}[1]{O\left( #1\right)}
\newcommand{\OM}[1]{\Omega\left( #1 \right)}
\newcommand{\Prob}[1]{\Pr\left\{ #1 \right\}}
\newcommand{\Set}[1]{\left\{ #1 \right\}}
\newcommand{\Seq}[1]{\left\langle #1 \right\rangle}
\newcommand{\Range}[1]{\left\{1,\ldots, #1 \right\}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ignore}[1]{}



\newcommand{\inclaim}[2]{\trivlist \item[\hskip \labelsep{\bf Claim #1.}{\em #2}
]}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\cA{{\cal A}}
\def\cB{{\cal B}}
\def\cC{{\cal C}}
\def\cD{{\cal D}}
\def\cE{{\cal E}}
\def\cF{{\cal F}}
\def\cG{{\cal G}}
\def\cH{{\cal H}}
\def\cI{{\cal I}}
\def\cJ{{\cal J}}
\def\cK{{\cal K}}
\def\cL{{\cal L}}
\def\cM{{\cal M}}
\def\cN{{\cal N}}
\def\cO{{\cal O}}
\def\cP{{\cal P}}
\def\cQ{{\cal Q}}
\def\cR{{\cal R}}
\def\cS{{\cal S}}
\def\cT{{\cal T}}
\def\cU{{\cal U}}
\def\cV{{\cal V}}
\def\cW{{\cal W}}
\def\cX{{\cal X}}
\def\cY{{\cal Y}}
\def\cZ{{\cal Z}}
%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%  Defining theorem-like environments %%%%%%%%%%
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{algorithm}{Algorithm}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{notation}[definition]{Notation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{comment}{Comment}
\newtheorem{assumption}{Assumption}



\begin{document}

\title{Softening Dependencies between Interfaces}

\author{
        \hspace*{-2ex}
        \parbox{2.3in} {\begin{center}
	{\authornamefont Dean Allemang }\\ 
        Synquiry, Inc.\\
        1st line of address\\
        2nd line of address\\
        last line, including country \\
	Telephone number\\
	First author's email address
	\end{center} }
        \parbox{2.3in} {\begin{center}
        {\authornamefont Karl Lieberherr }\\
	Demeter Research Group\\
	College of Computer Science\\
	Northeastern University\\
	Cullinane Hall\\
	Boston, MA 02115\\
	+1 617 373 2077\\
	lieber@ccs.neu.edu
	\end{center} }
        \parbox{2.3in} {\begin{center}
        {\authornamefont Third N. Lastauthor}\\
	Dipartimento di Elettronica\\
	Politecnico di Milano\\
	P.za Leonardo da Vinci, 32\\
	20133 Milano, Italia\\
	+39 2 555 93540\\
	author3@netaddress
	\end{center} }
}



\maketitle
\copyrightspace
%
% If you want to print drafts of the paper with a draft 
% notice in the copyright space, comment out the \copyrightspace
% line above and include the \submitspace line below instead.
%
% \submitspace{Draft of paper submitted to ICSE 99.}


% Page number on the initial page can be omitted in both the review and
% final submission (and should be removed in the final submission).  The
% line below does that.

\thispagestyle{empty}  % suppresses page number on first page

% In the review submission, page numbers should appear (they can be omitted
%  from the first page).  The pagestyle command below puts them in.
% In the final submission of accepted papers, page numbers should be
%  omitted; remove or comment out the pagestyle line below to omit them. 

\pagestyle{plain}

% Use \section* instead of \section to suppress numbering for
% the abstract, acknowledgements, and references.

\section*{ABSTRACT}
Our thesis is that we can simplify the task for both API writers and
users. API writers can focus on the basic functions of the API
without having to provide high-level functions that are used
only rarely. API users benefit from tool support which 
allows them to define customized APIs easily.
We prove the thesis using an example that shows the general
approach. Our approach is applicable to extending interfaces in
general.

An application programming interface (API) has to satisfy two
conflicting requirements: on the one hand it has to be detailed to
allow fine-grained access to low-level information. On the other hand,
an API should also provide "common" higher level access methods which
are expressed in terms of the primitive operations. The tension is that
the need for high-level methods is application-specific and there is a
danger of overloading, the API with too many methods.

In this paper we present a solution to this dilemma which allows for
convenient customized extension of the basic API. The extension
technique uses traversal strategies to succinctly define the
composition of high level methods out of low level methods. The
specification of methods using traversal strategies is more convenient
than writing the methods directly in a programming language for two
reasons: The method specifications are usually shorter and they are
more robust to changes in the basic API.

This is a sample paper using the format and guidelines 
required for the {\it ICSE 99 Conference Proceedings}. It 
includes instructions for preparing a camera-ready copy of 
your accepted submission.

\subsection{Keywords}
Succinct subgraph specifications, Adaptive Programming

Requires much additional text and rewording.

\section{INTRODUCTION}

An application programming interface (API) has to satisfy two
conflicting requirements: on the one hand it has to be detailed to
allow fine-grained access to low-level information. On the other hand,
an API should also provide "common" higher level access methods which
are expressed in terms of the primitive operations. The tension is that
the need for high-level methods is application-specific and there is a
danger of overloading, the API with too many methods.

In this paper we present a solution to this dilemma which allows for
convenient customized extension of the basic API. The extension
technique uses traversal strategies to succinctly define the
composition of high level methods out of low level methods. The
specification of methods using traversal strategies is more convenient
than writing the methods directly in a programming language for two
reasons: The method specifications are usually shorter and they are
more robust to changes in the basic API.


The {\it Proceedings} of ICSE 99 represent the final archival 
records of the conference. To give the book a high quality 
appearance we ask that authors follow these guidelines. In 
essence, we ask you to make your document look as much 
like this document as possible. The easiest way to do this is 
simply to replace the flow content of this file with your own 
material.
 
This \LaTeX document has several customizations and commands
tags to help you format your text (including redefinitions
of sectioning commands, and new commands like \verb|\copyrightspace|).
An electronic copy of this file, as well as files for Word and 
FrameMaker formats,
may be downloaded from the ICSE 99 web site \cite{EAK}.

\section{EXAMPLE}

The ACME API in simplified form.

\begin{verbatim}
Dean: You need to correct this 
and make a correct picture.

System =  Connectors Attachments Components.
Connector = ["s" <parent> System] RoleList.
Component = ["s" <parent> System] PortList.
Role = ["connector" <parent> Connector] RoleName.
Port = ["component" <parent> Component] PortName.
Attachment = Role Port.

RoleList ~ "(" {Role} ")".
PortList ~ "(" {Port} ")".

Connectors ~ "(" {Connector} ")".
Attachments ~ "(" {Attachment} ")".
Components ~ "(" {Component} ")".

RoleName = Ident.
PortName = Ident.

\end{verbatim}

Get the connector for a specific port name of a component.

shortest path semantics:
\begin{verbatim}
Component::{Connector, Role r} 
  getConnector(PortName n) {
    {Component -> Port:p -> Attachment -> 
     Role:r -> Connector}
  }
\end{verbatim} 

Should we indicate where p is used?

Find all Connectors attached to Component:

shortest path semantics:
\begin{verbatim}
Component::Connectors getConnector2() {
{  Component -> PortList -> Port:p -> 
   Attachment -> Role -> Connector}
}
\end{verbatim} 

Get component associated with connector through role r.

shortest path semantics
Connector::Component getComponent(Role r){
  {Connector -> Role -> Attachment -> 
	Port -> Component}

\subsection{Motivation for shortest path semantics}

In this paper the purpose of a strategy graph is to succinctly
define a single path in a graph.
In this context of defining a single path the shortest path
semantics is useful and is
captured by the general theory of strategy graphs
covered in \cite{strategies-tr:LP97} using appropriate constraint maps.
The shortest path between two points in a graph is an intuitive concept
which is accessible to programmers. It can be nicely visualized
and is efficiently computable (longest path would be a bad alternative
because it cannot be efficiently computed: it is NP-hard).
The shortest path semantics also behaves well under evolution.
In the extreme case we can always express the path in detail by
giving all intermediate points. But the graphs appearing
in practice are not
very dense and therefore only some intermediate points need to
be mentioned.

The shortest path semantics also behaves well for bidirectional edges.
The shortest path constraint makes sure that only one of the
directions will be used which is desirable in practice.

\section{SYNTAX AND SEMANTICS OF METHOD SPECIFICATIONS}

We introduce a notation for customized API method specifications.
This notation not only uses strategy graphs with shortest path
semantics but also a notation for object transportation
\cite{harrison:aql-94} and
for dealing with arguments is provided.

A strategy is extended for object transportation as follows:
Instead of using the strategy \{A -> B -> C\}, we can use the strategy
\{A:a -> B:b -> C\}. The meaning is straightforward: the most recently
encountered objects a and b are available to the right.
For example, between B and C there is a functional edge which requires
an A-object and a B-object as arguments.

Functional edges take their arguments from the context.
For example, a function f(A a, B b) will take a and b from the
transported objects or the arguments to the customized method
specification. If this leads to ambiguity, a standard mapping 
from formal to actual arguments may be used.

It is useful to allow for multiple return values to
have access to internal information on the selected path.

\begin{verbatim}
Component::
  {Connector:c, Role:r, Port:p} 
  getConnector3(PortName n) 
    {Component -> Port:p -> Attachment -> 
     Role:r -> Connector}
\end{verbatim} 

defines a method getConnector3 which takes as argument a PortName
and returns three objects c, r and p. They can be referenced 
further down in the traversal.


\subsection{Robustness under change}

Let's consider the strategy graph {A -> B} with shortest path semantics and a 
graph G which has multiple paths from A to B out of which
we want to select exactly one. We assume that the shortest path from A
to B is the one we want.
Now, let's assume that G changes so that the shortest path is nolonger
the desired one. We have to refine the strategy to one of the form
{A -> I1 -> ... -> In -> B}, where I1 to In are intermediate nodes.
It is important that no drastic change to the strategy graph is needed;
it is only a refinement and in practice the number of intermediate
nodes needed is small.

\section{DEFINITIONS}
%%%%%%%%%%%%%%%%%%%%%%
A directed graph is a pair $(V,E)$ where $V$ is a set of
{\em nodes}, and $E\subseteq V\times V$ is a set of {\em edges}.
Given a directed graph $G=(V,E)$,
a {\em path} is a sequence $p=\Seq{v_0v_1\ldots v_n}$,
where $v_i\in V$ for $0\le i\le n$, and $\edge{v_{i-1}}{}{v_i}\in E$
for all $0<i\le n$.                           
In practice we use labeled graphs; the generalization is straightforward.

We first define the basic concept of expansion.

\begin{definition}
Let $V_1,V_2$ be arbitrary sets, and let $\cN:V_2\rightarrow V_1$ be
a function. We say that a sequence $p_1$ of elements of $V_1$
is an {\sf expansion under $\cN$} of a sequence $p_2$ of elements of $V_2$
if $\cN(p_2)$ is a subsequence of $p_1$, where $\cN$ is applied to each element
in the sequence.
\end{definition}
%
With this definition, we define the concept of a path set.
In the following $G_1$ represents the API graph and 
$G_2$ represents a succinct representation of paths in $G_1$.
We call $G_2$ a strategy graph.

\begin{definition}
\label{def-PS}
Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be directed graphs, let
$\cN:V_2\rightarrow V_1$ be a function, and let $s,t\in V_2$.
$PathSet_{st}(G_1,G_2,\cN)$ is defined
to be the set of all paths in $G_1$ which are expansions under $\cN$
of any $s-t$ path in $G_2$.
\end{definition}

The identity of $s$ and $t$ is assumed to be fixed, and
we shall omit  subscripts henceforth.
A special mapping we shall use is the identity mapping which we denote $\cI$.
Note, for example, that $PathSet(G,G,\cI)$ is exactly the set of all $s-t$
paths in $G$. 

In this paper we consider the special case where there is exactly one 
$s-t$ path in $G_2$  and therefore the path set
$PathSet_{st}(G_1,G_2,\cN)$ consists of exactly one path in $G_1$.

The first node of a path $p$
is called the {\em source} of $p$, and the last node in $p$
is called the {\em target} of $p$,
denoted $\Source(p)$ and $\Target(p)$, respectively.
The elements other than the source and the target of a path
are the {\em interior} of the path.
For a graph $G$ and nodes $u,v$
we define $P_G(u,v)$ to be the set of all paths in $G$ with source
$u$ and target $v$.
A path is called simple, if no edge appears more than once in the path.


\subsection{Using a constraint map}
\label{ssec-full-strategy}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Strategy graphs
impose positive constraints on paths, in the sense that they specify
which nodes must be traversed in which order.
It turns out that it is quite useful to also have negative constraints:
what nodes and edges cannot be used between the specified milestones.
We formalize this idea with the concepts of element predicates
and constraint maps.

\begin{definition}
Given a class graph $G=(V,E)$, an {\sf element predicate} $EP$ for $G$
is a predicate over $V\cup E$.
Given  a strategy graph $S$,
a function $\cB$ mapping each edge of $S$ to an element predicate for $G$ is
called a {\sf constraint map} for $S$ and $G$.
\end{definition}

The constraint map is used to specify, for each edge in the strategy graph,
which elements of the graph
may be used in the traversal corresponding to that edge.
Formally, we have the following definition.

\begin{definition}
\label{def-sat}
Let $S$ be a strategy graph,
let $G$ be a class graph,
let $\cN$ be a name map for $S$ and $G$,
and let $\cB$ be a constraint map for $S$ and $G$.
Given a strategy-graph path $p=\Seq{a_0a_1\ldots a_n}$,
we say that a class-graph path $p'$  is
a {\sf satisfying expansion} of $p$ with respect to $\cB$
under  $\cN$ if there exist paths $p_1,\ldots,p_n$ such that
 $p'=p_1\cdot p_2\cdots p_n$ and:
 \begin{enumerate}
 \item
 \label{cond-st}
 For all $1\le i\le n$, $\Source(p_i)=\cN(a_{i-1})$ and
 $\Target(p_i)=\cN(a_i)$.
 %\item
 %\label{cond-1}
 %For all $1\le i<n$, $\cN(a_i)$ does not occur in in the interior of $p_i$.
 \item
 \label{cond-sat}
 For all $1\le i\le n$, the interior
 elements of $p_i$ satisfy the element predicate
 $\cB(\edge{a_{i-1}}{}{a_i})$.
 \end{enumerate}
 \end{definition}

Using the constraint map, we now define a more elaborate way
in which a strategy expresses a path set.

\begin{definition}
\label{def-strategy-paths}
Let $\cS=(S,s,t)$ be a strategy, let
 $G=(V,E)$ be a graph,  let $\cN$ be a name map for $S$ and $G$,
 and let $\cB$ be a constraint map for $S$ and $G$.
 Then $PathSet_{st}(G,S,\cN,\cB)$  is  the set of paths in $G$
which are satisfying expansions of any $s-t$ path in $G$ 
 w.r.t. $\cB$ under $\cN$.
\end{definition}

\section{COMPILATION ALGORITHM}
\label{sec-alg}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In this section we sketch how to implement traversal strategies
efficiently by compiling them into  executable programs.
The details are in \cite{strategies-tr:LP97}.
We focus on the special case we need for API composition:
There is only a single path in the path set.
Formally, the compilation problem is defined as follows.

\begin{description}
\item[Input:]
A  strategy $\cS=(S,s,t)$, a 
graph $G=(V,E)$, a name map $\cN$ for
$S$ and $G$, and a constraint map $\cB$ for $S$ and $G$.
\item[Output:]
The shortest path among all paths in $G$ which are a 
satisfying expansion of the $s-t$ path in $S$
 w.r.t. $\cB$ under $\cN$.
\end{description}
The path produced by the compiler is translated into a sequence of 
nested function calls.

Using the general techniques of \cite{strategies-tr:LP97} the compilation
can be accomplished as follows. Compute the traversal graph
$TG(G,S,\cN,\cB)$. $TG$ can be viewed as the intersection automaton of 
the two automata for $G$ and $S$.
If the strategy graph $S$ contains $k$ edges, the graph $G$ is copied
$k$ times and for each copy a constraint map is applied.
The constraint map is determined in the case of this paper by
a shortest path computation. If there are multiple shortest paths of
the same length the non-uniqueness is reported.
Computing the path in TG from the source of TG to the target of TG
yields the desired result.

The complexity of the traversal graph computation is 
$O(|\cS|^2\cdot|G|\cdot d_o)$, where
$d_o$ be the maximal
number of edges outgoing from a node in graph $G$.
Dijkstra's algorithm for computing the shortest path from
a node needs to be applied $k$ times and each application
costs $O(|V| + |E|)$, where $V$ and $E$ are nodes and edges in $G$.
Therefore the compilation algorithm is efficient and useful for
practical purposes. The algorithm, without the shortest path
computation, has been implemented
in Demeter/Java and is used successfully \cite{cse:preventive}.

\section{SPECIFYING FUNCTION COMPOSITIONS}

So far we have outlined the general approach to 
defining ``long paths'' using ``short paths''. This approach works very well
in practice \cite{karl:demeter}.
Special care needs to be taken when the graphs are dense.
For example, it is helpful to use a tree of strategy graphs.
Here we use a simpler approach based on constraint maps.

There are numerous ways of defining the constraint maps. 
Some approaches which have been used: bypassing, only-through, use-only.
For API composition, a shortest path approach seems best.
A strategy edge from A to B, assuming the identity name map, means
that we delete from the graph all nodes and edges, except the
ones on the simple shortest path from A to B.
We also need only-through to select between an edge in the case
of two nodes connected by two edges.

\subsection{DIFFERENCES TO AP}
This paper does not talk about visitors or APPCs \cite{mezini:98}.
Visitors and APPCs are used to define behavior on top
of traversing. The only
purpose of strategies in this paper
is to concatenate method calls and not to execute additional
methods during the traversal.

In other works on AP \cite{lieber-palsberg-xiao94,strategies-tr:LP97}
traversal strategies are used to define traversals through
object graphs. The object graphs help to control the traversals.
In this paper, the purpose of a strategy is to define a sequence
of nested function calls.

Also in other works on AP the focus has been to improve 
object-oriented programs  \cite{lieber-palsberg-xiao94,karl:demeter}.
The technique presented here is useful to any paradigm 
where functions are nested.
But the technique shown in this paper can be generalized 
to allow for abstract classes and inheritance in the API graph
\cite{lieber-palsberg-xiao94,strategies-tr:LP97}.

\section{AP STORY}

It has been
observed (see, e.g., \cite{cacm-oscar}) that changes 
in class or type definitions,
which are abundant during software evolution, may necessitate re-writing
large portions of the function definitions, even if the underlying
algorithm remains essentially the same.

Our central claim is a novel paradigm, 
called Adaptive Programming (AP)
\cite{karl:demeter}, to attack the software evolution problem.  
An adaptive program is a program that
takes as a parameter a {\em description} of a graph
on which it is to operate.  
The graph has types as nodes and the edges denote functional
relationships between nodes (which includes the structural ones).
The graphs are not only data structures but also contain
functional edges.
Adaptive programs are {\em polymorphic} in the graphs
they can use.  Action code is thus associated with the
partially-specified (i.e., parameterized) graphs.  The
connection between the actual and parameterized graphs is made
using a simple language that selects subgraphs of the actual object
structure.  The adaptive compiler is given as input an adaptive program
and a complete description of the actual graph to be used,
and it outputs code in a conventional object-oriented language.

The major advantage of adaptive programs is that they decouple the
behavior of the program from the irrelevant details of the actual data
structure or the
lower level software. 
The result is automation of the process of adaptation to new
class structures, thus allowing for rapid modification and evolution of
software.

Sethi \cite{sethi:bear}\index{AUTHOR Sethi, Ravi}
summarizes information hiding with the informal
{\bf representation independence principle}.

\begin{quote}
A program should be designed so that the representation of an object
can be changed without affecting the rest of the program.
\end{quote}

We propose a stronger principle,
the {\bf adaptive programming principle}.\index{adaptive programming principle}
\begin{quote}
A program should be designed so that the interfaces of
objects can be changed within certain constraints without
affecting the program {\em at all}.
\end{quote}

The interface of an object is the set of functions that can
be called for the object to manipulate its data.
The adaptive programming principle implies
that the program must be written
parameterized by interface information. Indeed, an
adaptive program is parameterized by constraints that say what 
kind of interface information is expected by the program.

\section{IMPLEMENTATION}

Refer to Demeter/Common Lisp \cite{demeter:98}.
Refer to Demeter/Java: \cite{cse:preventive}.

\section{CONCLUSIONS}

We have shown how high-level methods can be defined in terms
of low-level methods without commiting,
even in the implementation of the high-level methods,
to the detailed structure of the low-level methods.
This sufficiently loosens the connection between 
interface layers to automate many  maintenance
tasks which are done manually today.


So far we have written the short hand method compositions against a
detailed class graph. It is sometimes better to write the method
compositions against an interface class graph so that they become more
reusable. The interface class graph is later embedded into the
implementation class graph using techniques similar to the ones
presented in this paper. Each edge in the interface class graph is
expressed either as a short hand method composition or as an adaptive
program \cite{mezini:98}.

This paper has focussed on a simple use of APIs.
The techniques presented here can be extended to use APIs in
an aspect-oriented way \cite{aop:ecoop97}. In a first step we could allow to 
call additional methods before, after or around the calls to the
API methods. In a second step we could allow general strategies
resulting in path sets which may even be infinite.
In a third step we use visitors or APPCs to define the behavior.
This results in an aspect-oriented style of using an API because 
the API is written separately as a graph. The visitors or APPCs
describe application-specific aspects. This controls code tangling
between the API and behaviors and between the behaviors.

Adaptive programming does more than abstracting the format of
data structures out of the problem.
Adaptive programming is about building a new layer of software on top of
earlier layers of software in such a way that the new layer only
needs approximate knowledge of the old layers. The new layer is loosely
coupled to the old layers allowing the old layers to change within
certain limits with the new layer adapting automatically. 

Terminology: Short-hand method composition?
	     Succinct method compositions?
			  Customized API methods?


\section{PAGE LIMIT AND PAGE SIZE}
Submissions in different categories have page 
limits that must be adhered to. Technical papers, for example, should 
be no longer than 10 pages. Submissions that exceed the 
limit for their category will not be reviewed.
 
All material on each page should fit within a rectangle of 
18 x 23.5 cm (7" x 9.25"), centered on the page, beginning 
1.9 cm (.75") from the top of the page, with a .85 cm (.33") 
space between two 8.4 cm (3.3") columns. Use either US 
Letter or A4 paper. Right margins should be justified, not 
ragged.

\section{TYPESET TEXT}
Submissions should be prepared on a typesetter or word 
processor. Please use a 10-point Times Roman font, or other 
Roman font with serifs, as close as possible in appearance to 
Times Roman (in which these guidelines have been set). Note 
that different components (such as title, authors, headers -- 
see below) use the same font, but with different sizes and 
styles. The target is to have a 10-point text, as you see here.
(If your ``normalsize'' article font is not already 10-point, you may
have to put in explicit fonts to get 10-point text.  Suggested
hardcoded fonts, if needed, can be found in comments
at the top of the style file.)
Please do not use sans-serif or non-proportional fonts except 
for special purposes, such as distinguishing source code text 
(e.g., \verb|#include <iostream.h>|). Fonts similar to Times 
Roman include Times, Computer Modern Roman, and Press.
 
If you do not have a laser printer, you may be able to arrange 
for a business to print your document for you. If no laser 
printer is available, then please ask the conference office for 
assistance. 

\subsection{Title and Authors}
The title (18-point bold), authors' names (12-point bold), 
and affiliations (12-point) run across the full width of the 
page -- one column 17.8 cm (7") wide. Please also include 
phone numbers and e-mail addresses. See the top of this 
page for three names with different addresses. Note that each 
of the names/addresses has its own parbox.
If only one address is needed, center all 
address text in a single parbox. For two addresses, use 
two parboxes, and so on. For more that three authors, you 
may have to improvise (if necessary, you may place some 
address information in a footnote). 

\subsection{Abstract and Keywords}
Every submission (except summaries of Workshops) should 
begin with an abstract of no more than 200 words, followed 
by a short list of keywords. The abstract and keywords should be 
placed in the left column of the first page. The abstract 
should be a concise summary of the work and resulting 
conclusions. Keywords should help readers determine if the 
paper contains topics they are interested in.

\subsection{First Page Copyright Notice}
Leave at least 2.5 cm (1") of blank space at the 
bottom of the left column of the first page only. This space is 
reserved for the copyright notice that will be added during 
final printing.

\subsection{Subsequent Pages}
For pages other than the first page, start at the top of the page 
and continue in double-column format. It is preferable (but 
not required) that the two columns on the last page have 
approximately equal length. This can be accomplished by 
adjusting the length of the left column on the last page.

\subsection{References and Citations}
Use the standard {\it Communications of the ACM} format for 
references -- that is, a numbered list at the end of the 
article, ordered alphabetically by first author, and referenced 
by numbers in brackets (e.g., ``\cite{Anderson:Impacts}").
See the examples of citations at 
the end of this document.

References should be published materials accessible to the 
public. Internal technical reports may be cited {\it only} if they 
are easily accessible (i.e., you can give the address to obtain 
it within your citation) and may be obtained by any reader. 
Proprietary information should {\it not be} cited. Private 
communications should be acknowledged, not referenced 
(e.g., "[Robertson, personal communication]").

\subsection{Page Numbering, Headers and Footers}
Page numbers {\it should} be included in your submission for review. 
There are headers built into the style file for page numbers.
Do not add other headers or footers.
Final submission of accepted papers should {\it not} include any 
page numbers; they will be added for you when the 
publications are assembled.  (To omit page numbers in the final
submission, omit the \verb|\pagestyle{plain}| command
near the start of this file.)

\section{SECTIONS}
The title of a section should be in Times Roman 10-point 
bold in all capitals. Please number the sections.  Do not
number the abstract, acknowledgements, or references sections.

\subsection{Subsections}
The title of subsections should be in Times Roman 10-point 
bold with only the initial letters of each word capitalized. 
For subsections and subsubsections, a word like {\it the} and {\it a} 
is not capitalized unless it is the first word of the heading.

\subsubsection{Subsubsections}
The heading for subsubsections should be in Times Roman 
10-point italic with initial letters of each word capitalized.
 
\section{FIGURES}
Figures should be inserted at the appropriate point in your 
text. Figures may extend over the two columns up to 17.8 
cm (7") if necessary. Black and white photographs (not 
Polaroid prints) may be mounted on the camera-ready paper 
with glue or double-sided tape. (To avoid smudges, attach 
figures by paste or tape applied to their {\it back} surfaces only.)

\section{LANGUAGE, STYLE AND CONTENT}
The written and spoken language of ICSE 99 is English. 
Spelling and punctuation may consistently use any dialect 
of English (e.g., British, Canadian or US). Please write for 
an international audience:
 
\begin{smallitem}
\item Write in a straightforward style. Use simple sentence 
structure. Try to avoid long sentences and complex sentence 
structure. Use semicolons carefully.
 
\item Use common and basic vocabulary (e.g., use the word 
``unusual" rather than the word ``arcane").
 
\item Briefly define or explain all technical terms.
 
\item Explain all acronyms when they first appear in your text 
such as, ``World Wide Web (WWW)"
 
\item Explain ``insider" comments. Be sure that your whole 
audience will understand any reference whose meaning 
you do not explain (e.g., do not assume that everyone 
has used a Macintosh or MS-DOS).
 
\item Use unambiguous forms for representing culturally 
localized concepts, such as times, dates, and currencies, 
(e.g., ``1-5-98" or ``5/1/98" may mean 5 January or 1 
May, and ``seven o'clock" may mean 7:00 am or 1900).
\end{smallitem}
 
Authors are responsible for ensuring that their work is 
conducted in a professional and ethical manner \cite{Anderson:Impacts}, 
including (but not limited to) fully informed consent of 
participants in studies, protection of personal data 
(e.g., \cite{Mackay:Ethics}), 
and permission to use others' copyrighted materials.

\section{INFORMATION AND QUESTIONS}

For more information, contact
icse99@cs.cmu.edu, or phone +1 412 268 5056.

\section*{ACKNOWLEDGEMENTS}
This document has been adapted from the ICSE 97 Conference Proceedings
Format specification.
That was in turn adapted from the
Style Sheet 
defined for CHI 96 by Michael J. Muller, Bonnie Nardi, and 
Michael J. Tauber, and numberous people in the CHI 
community. Their contributions are gratefully acknowledged.


\bibliographystyle{abbrv}
\bibliography{biblio}
\begin{thebibliography}{1}

\bibitem{Anderson:Impacts}
R.~E. Anderson.
\newblock Social impacts of computing: {C}odes of professional ethics.
\newblock {\em Social Science Computing Review}, 10(2):453--469, (Winter 1992).

\bibitem{EAK}
ICSE 99 {W}eb {S}ite. {A}vailable at
  $<$http://sunset.usc.edu/icse99/$>$.

\bibitem{Mackay:Ethics}
W.~E. Mackay.
\newblock Ethics, lies and videotape...
\newblock In {\em Proc. CHI'95}, pages 138--145, Denver, CO, May 1995. ACM
  Press.

\end{thebibliography}
\end{document}