\documentstyle[epsf,fullpageusa,tightlist]{jsc-zena}


\input fixqmsfonts
\input laktex

%%%%%% Commutative diagrams
%%
\input diagrams
\input prooftree 
%%%%% Change size of diagrams
%%
\CellSize=2em

%%%%%%%%% IDRAW MACROS FROM SHAIL
\input psadobe

\input macros

\begin{document}

\title{Properties of a First-order  Functional Language with Sharing}

\author{{\it Zena M. Ariola}\\
Computer \& Information Science Department  \\
University of Oregon \\
{\it Arvind}\\
Laboratory for Computer Science\\
Massachusetts Institute of Technology
}

\maketitle{}

\begin{abstract}
A calculus and a model for a first-order functional language with
sharing is presented.  In most implementations of functional languages,
argument subexpressions in a function application are shared to avoid
their repeated evaluation.  Recursive functions are typically
implemented using graphs with cycles.  Compilers for these languages
sometimes employ non-left-linear and left-cyclic rules for
optimizations. A Graph Rewriting System (GRS) to address these
concerns is developed.  It is shown that a GRS without
interfering rules is confluent. 
Along the lines of L\'evy's term model
for the $\lambda$-calculus, a semantics of such a GRS is also presented.
An application of the term model to compiler optimizations is
discussed.

%\bigskip
%
%{\bf Keywords and phrases}:
%Graph Rewriting Systems,
%Term Rewriting Systems,
%Non-left-linear Rules,
%Cyclic Terms and Rules,
%Non interfering Rules,
%Confluence,
%Term Models,
%Compiler Optimizations.
\end{abstract}

\input grsexample.tex
\end{document}


