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

%\input{../../../Bk/tex/include-file}
%\input{../../../Bk/tex/macros.tex}
\input include-file
\input macros

\def\illustrationfileprefix{/home/www/csg-memos/CSG-347-1/PS/}

\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 introduction.tex
\input grsexample.tex
\input grsformal.tex
\input confluence.tex
\input graph-model.tex
\input optimizations.tex
\input conclusion.tex
\newpage
\bibliography{main}
\bibliographystyle{abbrv}
\newpage
\tableofcontents
\end{document}


