%template for producing IEEE-format articles using LaTeX.
%written by Matthew Ward, CS Department, Worcester Polytechnic Institute.
%use at your own risk.  Complaints to /dev/null.
%make two column with no page numbering, default is 10 point
\documentstyle[twocolumn]{article}
\pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}

%I copied stuff out of art10.sty and modified them to conform to IEEE format

\makeatletter
%as Latex considers descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI} 

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{24pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother

\begin{document}

%don't want date printed
\date{}
\author{John Glauert \\
	\emph{jrwg@sys.uea.ac.uk} \\
	School of Information Systems \\
	University of East Anglia \\
	Norwich NR4 7TJ, UK \\
	Tel: +44 603 592671 \\
	Fax: +44 603 507720}

%make title bold and 14 pt font (Latex default is non-bold, 16 pt)
\title{\Large\bf Parallel Implementation through Object Graph Rewriting}

%for single author (just remove % characters)
\author{J.R.W. Glauert \\
	\emph{jrwg@sys.uea.ac.uk} \\
	School of Information Systems \\
	University of East Anglia \\
	Norwich NR4 7TJ, UK
	}
 
\maketitle

\newcommand{\sembrac}[1]{[\![ #1 ]\!]}
\newcommand{\infer}[3]
           {\vspace{.2cm}
            \hbox{${\displaystyle {\frac {#1}{#2}}\hspace{.5cm}{#3}}$}
            \vspace{.2cm}}
% New macros
%\input{john-pi-macros}
% Process notation
\newcommand{\parprocs}[2]{{#1}\,|\,{#2}}
\newcommand{\restrict}[1]{\backslash{#1}}
\newcommand{\replicate}[2]{!\,{#2}}
\newcommand{\guardedrep}[3]{!\,({#2} \cdot {#3})}
\newcommand{\recdef}[2]{{\bf rec} {\recvar {#1}} \cdot {#2}}
\newcommand{\guardedrec}[3]{{\bf rec} {\recvar {#1}} \cdot {#2} \cdot
(\,\parprocs {#3} {\recvar {#1}}\,)}
\newcommand{\recvar}[1]{{#1}}
\newcommand{\agtuse}[2]{\recvar {#1} ({#2})}
\newcommand{\agtdef}[3]{\agtuse {#1} {#2} = {#3}}
\newcommand{\inpact}[3]{{#1}({#2}) \cdot {#3}}
\newcommand{\inpacta}[2]{{#1}({#2})}
\newcommand{\outact}[3]{\overline{#1}\,{#2} \cdot {#3}}
\newcommand{\outacta}[2]{\overline{#1}\,{#2}}
\newcommand{\match}[3]{{#1}={#2} \cdot {#3}}
\newcommand{\inaction}{0}
\newcommand{\pair}[2]{{#1}\,{#2}}
\newcommand{\triv}{}
%\input{john-proc-macros}
% New Process notation
\newcommand{\Ppar}[2]{{#1},\;{#2}}
\newcommand{\Pcall}[2]{{#1}\,!\,{#2}}
\newcommand{\Pprim}[2]{{#1}\,=\,{#2}}
\newcommand{\Pdef}[2]{{#1}:{#2}}
\newcommand{\Prule}[5]{\Ppar{\Pdef{#1}{#2}}{\Pcall{#1}{#3}} & \rightarrow &
\Ppar{#4}{\Pdef{#1}{#5}}}
\newcommand{\PruleChange}[4]{\Ppar{\Pdef{#1}{#2}}{\Pcall{#1}{#3}} & \rightarrow
& \Pdef{#1}{#4}}
\newcommand{\PruleSpawn}[4]{\Prule{#1}{#2}{#3}{#4}{#2}}

% Translation representation
\newcommand{\transwhere}[4]{& & {\makebox[1.5cm][l]{where}}
\Ppar{\Pdef{#1}{#2}}{\Pcall{#1}{#3}}  \rightarrow  \Ppar{\Pdef{#1}{#2}}{#4}}
\newcommand{\transand}[4]{& & {\makebox[1.5cm][l]{and}}
\Ppar{\Pdef{#1}{#2}}{\Pcall{#1}{#3}}  \rightarrow  \Ppar{\Pdef{#1}{#2}}{#4}}
\newcommand{\F}{Facile}
\newcommand{\Cham}{Chemical Abstract Machine}
\newcommand{\Lc}{$\lambda$--calculus}
\newcommand{\LC}{$\lambda$--Calculus}
\newcommand{\Lx}{$\lambda$--expression}
\newcommand{\Pc}{$\pi$--calculus}
\newcommand{\PC}{$\pi$--Calculus}
\newcommand{\PPC}{Polyadic $\pi$--Calculus}
\newcommand{\PPc}{polyadic $\pi$--calculus}
\newcommand{\RA}{\emph{return-Address} channel}
\newcommand{\Whnf}{weak head-normal form}
% Source representation
\newcommand{\Labs}[2]{\lambda{#1}.\,{#2}}
\newcommand{\Lapp}[2]{{#1}\,{#2}}
\newcommand{\Ltriv}{()}
\newcommand{\Lpair}[2]{({#1},{#2})}
% Translation representation
\newcommand{\transexp}[2]{\sembrac{#1}_{#2}}
\newcommand{\transdef}[3]{\transexp{#1}{#2} & = & {#3}}
% End of macros

%I don't know why I have to reset thispagesyle, but otherwise get page numbers
\thispagestyle{empty}

\subsection*{\centering Abstract}
\emph{Object Graph Rewriting} (OGRe) is a model of computation which combines
ideas from graph rewriting and process calculi. Simple objects, with state given
by term structures, respond to messages, also represented as terms. New objects
may be created and new messages sent, while the original object either remains
unaffected or changes state.

The model was developed as an intermediate language, or abstract machine, for
the implementation of multi-paradigm languages with an initial focus was on the
functional and concurrent language, \F. We outline the syntax and semantics of
OGRe and give a number of examples showing that the model is proving effective
for capturing essential features of other paradigms, such as concurrent logic
and object-oriented programming.

The model supports efficient implementation techniques for sequential machines,
while not hindering parallel implementation. The model as presented is
fine-grain, but larger grains of sequential computation can be extracted by
compile-time analysis. Further, OGRe can be seen as a notation for coordinating
sequential computation threads written in any conventional language.


\section{Introduction and Background}

Designers of multi-paradigm languages need to find a common semantic framework
in which to unite the paradigms available in the language. At the implementation
level it is necessary to consider the characteristics of the computational
models concerned. For example: in conventional languages, dataflow, and strict
functional languages computation proceeds immediately; lazy functional languages
require a demand to say that a computation is needed; computations in concurrent
logic languages may block waiting for instantiation of shared variables.

The present work arose out of a study of implementation techniques for
\F~\cite{Facile}, a multi-paradigm programming language which combines
functional and concurrent programming in a symmetric fashion. In \F, functions
may create channels and spawn processes; a functional expression may compute and
send a value on a channel, or may use a value received on a channel. Process
scripts take the form of functions. Existing practical implementations of the
language~\cite{DistribFacile} use Standard ML to provide the functional part of
the language, with concurrency primitives introduced through a library of new
system functions. In this implementation the process features of \F\ are mapped
to light-weight threads.

The approach taken in the present study has been to develop translations of both
the functional and concurrent features of \F\ into networks of small processes.
In such networks there is a uniform representation of all features of the
language, so that the relative cost of using the concurrent features of \F\ will
be much reduced. The ultimate goal is to exploit the inherent concurrency of the
process networks in an implementation on a parallel machine.

In its pure form, \F\ enhances the \Lc\ with primitives for process spawning and
channel-based communication in the style of CCS \cite{CCS}. Milner using the
\Pc\ \cite{Pi} and its polyadic form~\cite{PolyPi} shows that a \Lx\ may be
translated to a process network in the
\PPc\ which simulates the \Lx\ \cite{FunAsProcs}. Similar work was done by Leth
\cite{Leth91}.

One approach is to use process notations that are 
close to the \PPC\ \cite{PolyPi} in which communication is channel-based.
Translations such as those of Milner may be employed. Such
work is reported in \cite{SemSym} and \cite{Parle92}. In these models the
channels can be thought of as independent entities which act as brokers,
arranging communications between processes. Similar ideas appear in
\cite{MessageBrokers}.

However, in most cases the channels used in the translations mentioned above
were
closely associated with a particular process. This process was the only one to
receive messages from the channel, and furthermore, the process would receive
messages from no other channel. In contrast to the channel-based 
communication of CCS, and the \Pc, a model was developed in which communicating
agents use 
process-based, or point-to-point, communication.

The new model of \emph{Object Graph Rewriting} (OGRe) can be seen as a very
minimal version of Paragon \cite{Paragon}, 
with a very direct correspondence to the 
graph-rewriting framework in which Paragon has been presented.
Although the first application of OGRe has been in the implementation of \F, the
model is general and can be used to model a number of other computational models
rather directly. The characteristics of the model have been chosen carefully in
order to allow a very simple implementation of OGRe on existing hardware.

In the next section we introduce the Object Graph Rewriting model of
computation. A more formal semantics is presented in
Section~\ref{sect:semantics}. Section~\ref{sect:examples} provides an outline of
the way in which the model may be used to model a number of programming language
styles. Section~\ref{sect:implementation} discusses existing language
implementation via OGRe and potential for future exploitation of the model. It
is argued that the design of OGRe makes it possible to generate an efficient
pseudo-parallel implementation on sequential machines or to provide medium- or
fine-grain parallel processes for hardware architectures able to exploit low
level concurrency.

\begin{figure*}[tb]
\begin{eqnarray*}
\Prule {p} {SumSq} {Trip(r,x,y)} {\Ppar {\Pdef {s} {SqY(r,y)}} {\Ppar {\Pdef {m} {Mul}} {\Pcall {m} {Trip(s,x,x)}}}} {SumSq} \\
\Prule {q} {SqY(r,y)} {{\bf IntVal}(xx)} {\Ppar {\Pdef {f} {Fin(r,xx)}} {\Ppar {\Pdef {m} {Mul}} {\Pcall {m} {Trip(f,y,y)}}}} {SqY(r,y)} \\
\Prule {s} {Fin(r,xx)} {{\bf IntVal}(yy)} {\Ppar {\Pdef {a} {Add}} {\Pcall {a} {Trip(r,{\bf IntVal}(xx),{\bf IntVal}(yy))}}} {Fin(r,xx)} \\
\Prule {m} {Mul} {Trip(r,{\bf IntVal}(a),{\bf IntVal}(b))} {\Ppar {\Pprim {t} {{\bf PMul}(a,b)}} {\Pcall {r} {{\bf IntVal}(t)}}} {Mul} \\
\Prule {d} {Add} {Trip(r,{\bf IntVal}(a),{\bf IntVal}(b))} {\Ppar {\Pprim {t} {{\bf PAdd}(a,b)}} {\Pcall {r} {{\bf IntVal}(t)}}} {Add}
\end{eqnarray*}
\caption{OGRe rules for an arithmetic expression}
\label{fig:sumsq}
\end{figure*}

\begin{figure*}[tb]
\begin{eqnarray*}
& & \Pdef{p}{PrintInt},\; \Pdef{s}{SumSq},\; \Pcall{s}{Trip(p,{\bf IntVal}(3),{\bf IntVal}(4))} \\
& \rightarrow & \Pdef{p}{PrintInt},\; \Pdef{s}{SumSq},\; \Pdef{t}{SqY(p,{\bf IntVal}(4))},\,
\Pdef{q}{Mul},\; \Pcall{q}{Trip(t,{\bf IntVal}(3),{\bf IntVal}(3))} \\
& \rightarrow & \Pdef{p}{PrintInt},\; \Pdef{t}{SqY(p,{\bf IntVal}(4))},\; \Pdef{q}{Mul},\;
\Pcall{t}{{\bf IntVal}(9)} \\
& \rightarrow & \Pdef{p}{PrintInt},\; \Pdef{t}{SqY(p,{\bf IntVal}(4))},\;
\Pdef{f}{Fin(p,9)},\; \Pdef{m}{Mul},\; \Pcall{m}{Trip(f,{\bf IntVal}(4),{\bf IntVal}(4))} \\
& \rightarrow & \Pdef{p}{PrintInt},\; \Pdef{f}{Fin(p,9)},\; \Pdef{m}{Mul},\;
\Pcall{f}{{\bf IntVal}(16)} \\
& \rightarrow & \Pdef{p}{PrintInt},\; \Pdef{f}{Fin(p,9)},\; \Pdef{a}{Add},\;
\Pcall{a}{Trip(p,{\bf IntVal}(9),{\bf IntVal}(16))} \\
& \rightarrow & \Pdef{p}{PrintInt},\; \Pcall{p}{{\bf IntVal}(25)}
\end{eqnarray*}
\caption{Evaluation of an arithmetic expression}
\label{fig:sumsqexec}
\end{figure*}

\section{OGRe: A Small Process Language}

The \emph{Object Graph Rewriting} (OGRe) language models a computation by a set
of named processes which exchange messages. Rewriting rules determine the way in
which a process responds to the arrival of a message.

The state of a process is given by a term over the set of process names and a
set of constructor (function) symbols with fixed arities. The symbols are used
to model standard primitive data types, such as integers, and structured values,
such as arrays and lists. Messages are also terms defined in the same way and
are sent to a specific named process.

OGRe computation proceeds according to pattern-directed rewriting rules. When a
process receives a message, the term describing the state of the process and the 
term forming the message are matched against the left-hand sides of the OGRe
rules. When a match is found, the message is absorbed, the state of the process
is changed, and new process and messages may be generated.
Rules may also make use of primitive data functions, such as the arithmetic
operations on numbers.

Figure~\ref{fig:sumsq} shows one of a number of possible ways in which
arithmetic expressions might be translated. $SumSq$ is a rule for summing the
square of $x$ and the square of $y$. It creates a process to multiply $x$ by
itself and a process $SqY$ which will the result and initiate squaring of $y$.
The final result is sent to a process $Fin$ which sums the squares and sends the
result on. The actual arithmetic is performed by $Mul$ and $Add$ which receive a
triple consisting of two arguments and the name of a process to be sent the
result. 

The sequence of execution for a computation using $SumSq$ is shown in
Figure~\ref{fig:sumsqexec}. The initial configuration has a print process and a
$SumSq$ process. A message has been sent to the $SumSq$ with arguments $3$ and
$4$ with the result to be sent for printing. The process $s$ and the message sent
to it constitute an instance of the $SumSq$ rule. Application of the rule will
remove these two terms, replacing them by the right-hand side of the rule, with
suitable substitutions. Processes that become unreferenced have been discarded.
Execution takes six steps, half of which correspond to arithmetic operations. In
fact, given the rules above, it is straightforward to transform $SumSq$ to a rule
containing the expected sequence of primitive arithmetic operations by straightforward symbolic evaluation.

\section{OGRe Semantics}\label{sect:semantics}

The focus of this paper is to illustrate a range of applications for OGRe, with special emphasis on the implementation of \F. This section gives a brief, and  necessarily informal, introduction to the semantics of OGRe.

\subsection{OGRe Processes, Messages, and Rules}

OGRe processes, messages, and rules involve terms over a set of process names, a
set of variables, and a set of symbols with fixed arities. Most of the symbols
are constructors, but a small number represent primitive operations on data
values.

An execution configuration consists of a set of names processes and messages.
Process states are given by terms not including variables or primitive
operations. Messages are addressed to a named process and have as contents terms
of the same form.
In the initial configuration each process has a unique name, the address of
every message is the name of a defined process, and every process name in a
process state or message contents is defined. These properties are preserved by
rewriting.

Computations in OGRe are specified by an ordered set of pattern-directed
rewriting rules. The pattern of a rule consists of a process definition and a
message addressed to the process. The body of a rule consists of a set of
process definitions and messages. The terms in the pattern contain no process
names or primitive operations. No variable may appear more than once in the
pattern. A pattern term may not consist of just a variable.
The names of all processes defined in the body must be unique and must include
the name of the process in the head. All process names in the body must refer to
processes defined in the body. All variables in the body must occur in the
pattern.

\subsection{OGRe Rewriting}

Whenever the execution configuration contains a message it is possible to
rewrite the configuration by considering the contents of the message and the
state of the process to which it is directed. An OGRe rewriting rule matches if
the state of the configuration process is an instance of the state of the
process in the rule pattern, and the contents of the configuration message in is
an instance of the contents of the message in the rule pattern.
It may be that more than one rule matches in this way, in which case the only
admissible rule is the earliest in the ordered set of rules. We place the very
strong condition on the rule system that whenever a message is addressed to a
process, either in the initial term, or following some rewriting steps, there
must be an admissible rule for the message and its target process. This
condition avoids the need to queue messages in an implementation.

When the admissible rule has been identified, rewriting takes place as follows:
To avoid potential name clashes we make an isomorphic copy of the rule with no
process names in common with the execution configuration. We then substitute the
name of the configuration process for the name of pattern process throughout the
rule and apply to the whole rule the substitution which makes the configuration
process and message match the pattern. The rule body may contain primitive
operations, and we require that they should have appropriate arguments. The
primitive operations are applied to their arguments and replaced by the
corresponding results. The final step is to remove the process and message from
the configuration and add the body. A new instance of the process will always be
present, and will often be an exact copy of the original.

OGRe rewriting continues by repeatedly replacing process--message pairs until
all messages are eliminated. Concurrent rewrites may be performed as long as a
given process state takes part in only one rewrite at a time. It is possible to
garbage collect a process whose name does not appear in the state of any other
process nor in the address or contents of any message.

\section{OGRe Applications}\label{sect:examples}

In this section we illustrate the power of OGRe by showing how a number of
models of computation may be represented in a direct way.

\subsection{Modelling Dataflow}

In dataflow, an operator waits for a number of tokens to arrive, carrying data
values. The operator then computes a result and sends it on to a further
operator. We sketch a model of dataflow in OGRe where operation nodes become
processes and data tokens become messages.
In line with the tagged dataflow model of the Manchester Dataflow
Machine~\cite{MDFM}, we will label tokens as left or right arguments using
symbols $L$ and $R$. When processes representing nodes are created, they will
take an argument indicating the node to receive the result, and also which
argument of the successor node will be formed by the result token.
\begin{eqnarray*}
\PruleChange {p} {Sub(d)} {L(x)} {SubR(r,x)} \\
\PruleChange {p} {Sub(d)} {R(y)} {SubL(r,y)} \\
\Prule {p} {SubR(R(d),x)} {R(y)} {{\Pcall {d} {R(x-y)}}}{Done} \\
\Prule {p} {SubR(L(d),x)} {R(y)} {{\Pcall {d} {L(x-y)}}}{Done} \\
\Prule {p} {SubL(R(d),y)} {L(x)} {{\Pcall {d} {R(x-y)}}}{Done} \\
\Prule {p} {SubL(L(d),y)} {L(x)} {{\Pcall {d} {L(x-y)}}}{Done}
\end{eqnarray*}

The first two rules take in the first argument and change the process state to
await the second argument. The next two pairs of auxiliary rules await right, or
left-hand arguments respectively. Two rules handle each of these cases since we
must determine whether the resulting value is to become a left or right-hand
input to the destination node.
Similar rules will exist for other operations.

Nodes which take a literal argument can be modelled by auxiliary nodes with
suitable arguments as illustrated in Figure~\ref{fig:dfexec} which computes
$3-(6*2)$ and sends the result to a function $Print$. The result of the
multiplication will become the right-hand argument of the subtraction node. The
result of the subtraction becomes the left (only) argument of the print
function.
\begin{figure*}[tb]
\begin{eqnarray*}
& &
\Ppar{\Ppar{\Ppar{\Pdef{p}{Print}}{\Pdef{m}{SubR(L(p),15)}}}{\Ppar{\Pdef{a}{Mul(R(m))}}{\Pcall{a}{L(6)}}}}{\Pcall{a}{R(2)}} \\
& \rightarrow &
\Ppar{\Ppar{\Ppar{\Pdef{p}{Print}}{\Pdef{m}{SubR(L(p),15)}}}{\Pdef{a}{MulR(R(m),6)}}}{\Pcall{a}{R(2)}} \\
& \rightarrow &
\Ppar{\Ppar{\Ppar{\Pdef{p}{Print}}{\Pdef{m}{SubR(L(p),15)}}}{\Pcall{m}{R(12)}}}{\Pdef{a}{Done}} \\
& \rightarrow &
\Ppar{\Ppar{\Ppar{\Pdef{p}{Print}}{\Pcall{p}{R(3)}}}{\Pdef{m}{Done}}}{\Pdef{a}{Done}}
\end{eqnarray*}
\caption{Evaluation of a dataflow example}
\label{fig:dfexec}
\end{figure*}

The reader can check that the result would be the same if the right-hand input
to $a$ had been considered first. As tokens move through the graph the completed
nodes are replaced by inactive $Done$ processes which can be garbage collected.

This example indicates the use of processes with state, and tagging of data
value to identify a notional port in the receiving process. The example above
contains no parallelism, but it is clear that in general there might be many
token messages travelling between nodes, and hence many possible concurrent
rewritings. The number of tokens will increase when a result is needed  by
several successors, and a duplication node is used. In Figure~\ref{fig:dup}, we give the rule for
duplications and an example of how it could be used to form the square of a
number:
\begin{figure*}[tb]
\begin{eqnarray*}
\Prule {p} {Dup(L(d),L(e))} {L(x)} {\Ppar {\Pcall {d} {L(x)}} {\Pcall {e}
{L(x)}}}{Done} \\
\Prule {p} {Dup(L(d),R(e))} {L(x)} {\Ppar {\Pcall {d} {L(x)}} {\Pcall {e}
{R(x)}}}{Done} \\
\Prule {p} {Dup(R(d),L(e))} {L(x)} {\Ppar {\Pcall {d} {R(x)}} {\Pcall {e}
{L(x)}}}{Done} \\
\Prule {p} {Dup(R(d),R(e))} {L(x)} {\Ppar {\Pcall {d} {R(x)}} {\Pcall {e}
{R(x)}}}{Done}
\end{eqnarray*}
\begin{eqnarray*}
&
\Ppar{\Ppar{\Ppar{\Pdef{p}{Print}}{\Pdef{m}{Mul(L(p))}}}{\Pdef{d}{Dup(L(m),R(m))}}}{\Pcall{d}{L(6)}}
\end{eqnarray*}
\caption{Duplication of dataflow tokens}
\label{fig:dup}
\end{figure*}

\begin{figure*}[tb]
\begin{eqnarray*}
\Prule {c} {Chan(VQ(v,q))} {Get(r)} {\Pcall {r} {Data(v)}} {Chan(q)} \\
\PruleChange {c} {Chan(q)} {Get(r)} {Chan(RQ(r,q))} \\
\Prule {c} {Chan(RQ(r,q))} {Put(v)} {\Pcall {r} {Data(v)}} {Chan(q)} \\
\PruleChange {c} {Chan(q)} {Put(v)} {Chan(DQ(v,q))}
\end{eqnarray*}
\caption{Rules for Asynchronous Communication}
\label{fig:asynccomm}
\end{figure*}

\subsection{Modelling Communication Channels}\label{sect:syncchannel}

The OGRe model is based on asynchronous direct communication between processes.
There are no intervening channels as in CCS, or the \PPC. However, channel-based
communication can be modelled by OGRe processes. A channel is represented by a
process which co-ordinates communication between producing and consuming
processes. A producer sends a $Put$ message to the channel, with the data as
argument. A consumer sends a $Get$ message with the identity of the process to
receive the data. Data is queued until a consumer is known. Unsatisfied requests
are queued until a producer provides data.

The model in Figure~\ref{fig:asynccomm} supports asynchronous communication since the producer
receives no notification that data has been consumed.
Unsatisfied messages are stacked, so there is no fairness about this particular
model. Surplus data values form a stack, $VQ$, of available values, while
surplus producer names form a stack, $RQ$, of requests. Observe the order in
which requests are satisfied in the example execution in Figure~\ref{fig:comexec}.
\begin{figure*}[tb]
\begin{eqnarray*}
& &
\Ppar{c:Chan(EQ)}{\Ppar{c!Put(3)}{\Ppar{c!Put(4)}{\Ppar{c!Get(x)}{\Ppar{c!Get(y)}{c!Get(z)}}}}} \\
& \rightarrow &
\Ppar{c:Chan(VQ(3,EQ))}{\Ppar{c!Put(4)}{\Ppar{c!Get(x)}{\Ppar{c!Get(y)}{c!Get(z)}}}} \\
& \rightarrow &
\Ppar{c:Chan(VQ(4,VQ(3,EQ)))}{\Ppar{c!Get(x)}{\Ppar{c!Get(y)}{c!Get(z)}}} \\
& \rightarrow &
\Ppar{c:Chan(VQ(3,EQ))}{\Ppar{c!Get(y)}{\Ppar{c!Get(z)}{x!Data(4)}}} \\
& \rightarrow & \Ppar{c:Chan(EQ)}{\Ppar{c!Get(z)}{\Ppar{x!Data(4)}{y!Data(3)}}}
\\
& \rightarrow & \Ppar{c:Chan(RQ(z,EQ))}{\Ppar{x!Data(4)}{y!Data(3)}}
\end{eqnarray*}
\caption{Asynchronous Communication}
\label{fig:comexec}
\end{figure*}
The initial state of the channel holds and empty queue, $EQ$. The two $Put$
actions stack values so the $Get$ actions receive values in the reverse order.

It should be clear that the model for asynchronous channels could be modified to
implement semaphores. No actual data values need be communicated, or stored.

\begin{figure*}[tb]
\begin{eqnarray*}
\Prule {c} {Chan(VQ(v,s,q))} {Get(r)} {\Ppar {\Pcall {r} {Data(v)}} {\Pcall {s}
{Sync}}} {Chan(q)} \\
\PruleChange {c} {Chan(q)} {Get(r)} {Chan(RQ(r,q))} \\
\Prule {c} {Chan(RQ(r,q))} {Put(v,s)} {\Ppar {\Pcall {r} {Data(v)}} {\Pcall {s}
{Sync}}} {Chan(q)} \\
\PruleChange {c} {Chan(q)} {Put(v,s)} {Chan(VQ(v,s,q))}
\end{eqnarray*}
\caption{Rules for Synchronous Communication}
\label{fig:synccomm}
\end{figure*}

Synchronous communication is possible if we arrange that a notification message,
$Sync$, is sent to the producing process when the communication is completed.
The producer must include the identity of the process to receive synchronisation
when a data value is sent. Further computation by the producer can be blocked
until the communication is completed as shown in Figure~\ref{fig:synccomm}.
Note how an unsatisfied request blocks a thread of control as the channel
process changes state but does not generate further activity. When a
communication completes, a new thread is activated as indicated by the two
messages generated, one of which resumes the suspended thread of control.

\subsection{Modelling State and Logic Variables}

The channel model above uses a process to hold the state of the channel as a
list of data values or requests. A simple von Neumann storage cell can be
implemented with $Set$ and $Read$ operations. The $Set$ is acknowledged in order
to provide serialisation. We return the old contents to allow a test-and-set
functionality:
\begin{eqnarray*}
\Prule {c} {Cell(v)} {Set(n,r)} {\Pcall {r} {Data(v)}} {Cell(n)} \\
\PruleSpawn {c} {Cell(v)} {Read(r)} {\Pcall {r} {Data(v)}}
\end{eqnarray*}

\begin{figure*}[tb]
\begin{eqnarray*}
\PruleChange {c} {UVar(q)} {Read(r)} {UVar(Q(r,q))} \\
\PruleSpawn {c} {BVar(v)} {Read(r)} {\Pcall {r} {Data(v)}} \\
\Prule {c} {UVar(q)} {Bind(d,r)} {\Ppar{\Pcall {r}
{Succ}}{\Ppar{\Pdef{f}{Free(q,d)}} {\Pcall{f}{Go}}}} {BVar(d)} \\
\PruleSpawn {c} {BVar(v)} {Bind(d,r)} {\Pcall {r} {Fail}} \\
\PruleSpawn {c} {UVar(q)} {IsVar(r)} {\Pcall {r} {Succ}} \\
\PruleSpawn {c} {BVar(v)} {IsVar(r)} {\Pcall {r} {Fail}} \\
\\
\Prule {f} {Free(Q(r,q),d)} {Go} {\Ppar{\Pcall{f}{Go}}{\Pcall {r} {Data(v)}}}
{Free(q,d)} \\
\PruleChange {f} {Free(E,d)} {Go} {Done}
\end{eqnarray*}
\caption{A model for logical variables in OGRe}
\label{fig:lv}
\end{figure*}

By adding slightly more sophisticated behaviour, we can model a logic variable
in the framework of concurrent logic programming~\cite{Shapiro}. The model
suggested in Figure~\ref{fig:lv} is for illustration only, as the properties of such variable vary
from language to language. We will assume that an attempt may be made to $Bind$
an unbound variable, $UVar$. This will fail if the variable is already bound. A
variable may be $Read$, which will lead to blocking of the computation if the
variable is unbound. There is also an $IsVar$ test for examining the state of
the variable. An unbound variable holds a list of suspended readers.
The initial state of an unbound variable is $UVar(E)$. The rules for $Free$ are
used to release suspended readers. In order to process the rest of the list, the
process sends a further message to itself.

\subsection{Modelling Facile}

The main application of OGRe has been in the implementation of \F. The OGRe
model results in a very low-level translation of 
\F\ features in which potential implementation data-structures become 
visible. For example, \F\ channels can be 
represented as objects which are manipulated in exactly the same way 
as in the  \Cham\ \cite{CHAM} proposed for \F\ in \cite{FacileCHAM}. This
channel representation is closely related to the synchronous channel model in
Section~\ref{sect:syncchannel}.

For the purpose of investigation we present a very small language in 
which we can represent all the features of core \F, along with facilities for 
handling constants and operators as in ML.
This language is the \Lc\ with constants and pairing. The trivial
value and pairing operator could have been considered as normal constants.
\begin{eqnarray*}
e & ::= &  x \mid \Labs{x}{e} \mid \Lapp{e}{e} \mid c \mid () \mid \Lpair{e}{e} 
\end{eqnarray*}

$c$ stands for a constant and $x$ for a variable.

The features of \F\ are encoded in our source language as special constants in
very much the 
same way as in the sequential and
distributed implementations based on SML
\cite{KuoFacile,DistribFacile,MachFacile}.
The functionality is hidden in the definition of the constants $channel$,
$send$, $receive$, and $spawn$.

The function $channel$ takes a trivial value and returns a new channel
value. Every invocation of $channel$ returns a distinct channel value.

The function $send$ takes a pair containing a channel, and a value to
be sent on the channel. A trivial value is returned when the output
action has succeeded. The function
has the effect of the SML/\F\ code $({\bf fn}\,(x,y)\,=>\,x!y)$

$receive$ takes a channel as argument and returns a value received as
the result of an input action. It has the
effect $({\bf fn}\,x\,=>\,x?)$.

The essence of \F\ behaviour
expressions, the scripts of processes, is provided by using delay closures,
functions of type $() \rightarrow ()$.
$spawn$ takes such a function and returns a trivial value having
created a process which runs in parallel. The spawned process executes
the behaviour expression by applying its
representation function to the trivial value,
terminating if the application terminates.
Although the original \F\ language provides more programming flexibility, it is
sufficient for our implementation experiments to concentrate on the four
primitives described above.

The translation scheme maps the syntax to OGRe, based on the syntax of a term.
The translation of a syntactic form takes a parameter which will be the name of
the process to which a result is to be sent. In the translation, we will make
use of a function $fv()$ which yields a list of the free variables in a \Lx. 
The translation of a syntactic construct, given in Figure~\ref{fig:tranfacile},
creates some actions which will form part of the body of a rule, and may also
introduce new constructor symbols and associated rules.

\begin{figure*}[tb]
\begin{eqnarray*}
\transdef {x}{u} {\Pcall {u} {Unit(x)}} \\
\transdef {c}{u} {\Pcall {u}{Unit(c)}} \\
\transdef {\Ltriv}{u} {\Pcall {u} {Triv}} \\
\transdef {\Labs{x}{e}}{u} {\Ppar {\Pcall {u} {Unit(y)}} {\Pdef {y}
{Y(fv(\Labs{x}{e}))}}} \\
\transwhere {y} {Y(fv(\Labs{x}{e}))} {Doub(b,x)} {\transexp{e}{b}} \\
\transdef {\Lapp{e}{e'}}{u} {\Ppar {\transexp{e}{a}} {\Pdef {a} {A(u,fv(e'))}} }
\\
\transwhere {a}{A(u,fv(e'))} {Unit(y)} {\Ppar {\Pdef {b} {B(u,y)}}
{\transexp{e'}{b}} } \\
\transand {b} {B(u,y)} {Unit(z)} {\Pcall {y} {Doub(u,z)} } \\
\transdef {\Lpair{e}{e'}}{u} {\Ppar {\transexp{e}{a}} {\Pdef {a} {A(u,fv(e'))}}
} \\
\transwhere {a} {A(u,fv(e'))} {Unit(y)} {\Ppar {\Pdef {b} {B(u,y)}}
{\transexp{e'}{b}} } \\
\transand {b}{B(u,y)} {Unit(z)} {\Pcall {u} {Doub(y,z)} }
\end{eqnarray*}
\caption{Translation Rules for Facile Constructs}
\label{fig:tranfacile}
\end{figure*}

All the constructor names introduced are distinct. All the process names are
distinct and are different from all the variables used in the source \Lx, with
the exception of $x$ in the translation of an abstraction which stands for
itself.

The intuition behind the translation is that $u$ will be the name of a process
to receive the computed value. In the case of constants, the value is sent to
process $u$.

The encoding of an abstraction returns a handle in the form of the name of a
process $y$. When the function is to be applied to an argument, process $y$
receives a pair of values: a process $b$ to be sent the result, and a process
$x$ which will provide an argument.

An application encodes the function which will return its handle to process $a$.
When the handle, $y$, is received, the argument is evaluated, returning a value
$z$ to process $b$ which will call the function by sending $y$ the argument and
the name $u$ which is, as usual, the process to receive the final result of the
application.

The translation of the constant functions for the various arithmetic and other
operators of \F\ is given 
in Figure~\ref{fig:tranconst}
below. The rules for $Chan$ were given earlier. The arithmetic rules used before
are slightly different to those used for \F:
% JRWG: Could/Should make consistent
\begin{figure*}[tb]
\begin{eqnarray*}
\transdef {succ}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Succ}} } \\
\transwhere {s} {Succ} {Doub(b,x)} {\Pcall {b} {Unit(x+1)}} \\
\transdef {mul}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Mul}} } \\
\transwhere {m} {Mul} {Doub(b,Pair(x,y))} {\Pcall {b} {Unit(x*y)}} \\
\transdef {channel}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Channel}} } \\
\transwhere {c} {Channel} {Doub(b,Triv)} {\Ppar {\Pcall {b} {Unit(c)}} {\Pdef
{c}
{Chan(EQ)}} }\\
\transdef {send}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Send}} } \\
\transwhere {s} {Send} {Doub(b,Pair(c,v))} {\Pcall {c} {Put(v,s)}} \\
\transdef {receive}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Receive}} } \\
\transwhere {r} {Receive} {Doub(b,c)} {\Pcall {c} {Get(b)}} \\
\transdef {spawn}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Spawn}} } \\
\transwhere {s} {Spawn} {Doub(b,p)} {\Ppar {\Pcall {b} {Unit(Triv)}} {{\Ppar
{\Pcall
{p} {Doub(Triv,s)}} {\Pdef {s} {Sink}} } } }\\
\transand {s} {Sink} {Unit(Triv)} {}
\end{eqnarray*}
\caption{Translation Rules for Constant Functions}
\label{fig:tranconst}
\end{figure*}

The translation of the expression $(Mul(3,4),())$ under this
scheme appears
in Figure~\ref{fig:tranexample}.
\begin{figure*}[tb]
\begin{eqnarray*}
\PruleSpawn {s} {{Start}} {{Triv}} {\Ppar {\Pdef {d} {B(a)}} {\Ppar {\Pdef {c}
{D(d)}} {\Ppar {\Pcall {c} {{Unit}(b)}} {\Ppar {\Pdef {b} {{Mul}}} {\Pdef {a}
{{Print}}}}}}} \\
\PruleSpawn {r} {A(a,e)} {{Unit}(f)} {\Ppar {\Pdef {g} {{PairB}}} {\Pcall {g}
{{Trip}(a,e,f)}}} \\
\PruleSpawn {r} {B(a)} {{Unit}(e)} {\Ppar {\Pdef {h} {A(a,e)}} {\Pcall {h}
{{Unit}({Triv})}}} \\
\PruleSpawn {r} {C(d,i)} {{Unit}(j)} {\Pcall {i} {{Doub}(d,j)}} \\
\PruleSpawn {r} {D(d)} {{Unit}(i)} {\Ppar {\Pdef {l} {C(d,i)}} {\Ppar {\Pdef {k}
{F(l)}} {\Pcall {k} {{Unit}(3)}}}} \\
\PruleSpawn {r} {E(l,m)} {{Unit}(n)} {\Ppar {\Pdef {o} {{PairB}}} {\Pcall {o}
{{Trip}(l,m,n)}}} \\
\PruleSpawn {r} {F(l)} {{Unit}(m)} {\Ppar {\Pdef {p} {E(l,m)}} {\Pcall {p}
{{Unit}(4)}}} \\
\PruleSpawn {r} {Mul} {Doub(b,Pair(x,y))} {\Pcall {b} {Unit(x*y)}} \\
\PruleSpawn {r} {PairB} {Trip(u,x,y)} {\Pcall {u} {Unit(Pair(x,y))}}
\end{eqnarray*}
\caption{Example: Translation of $(Mul(3,4),())$}
\label{fig:tranexample}
\end{figure*}

In Figure~\ref{fig:elaborate}
we illustrate the first few steps of the evaluation of a program which starts
with an initial process with state $Start$ being sent the message $Triv$:
\begin{figure*}[tb]
\begin{eqnarray}
& & {\Pdef {s} {Start}}, \:\: {\Pcall {s} {Triv}} \\
\rightarrow & & {\Pdef {a} {Print}}, \:\: {\Pdef {d} {B(a)}}, \:\: {\Pdef {b}
{Mul}}, \:\: {\Pdef {c} {D(d)}}, \:\: {\Pcall {c} {Unit(b)}} \\
\rightarrow & & {\Pdef {a} {Print}}, \:\: {\Pdef {d} {B(a)}}, \:\: {\Pdef {b}
{Mul}}, \:\: {\Pdef {l} {C(d,b)}}, \:\: {\Pdef {k} {F(l)}}, \:\: {\Pcall {k}
{Unit(3)}} \\
\rightarrow & & {\Pdef {a} {Print}}, \:\: {\Pdef {d} {B(a)}}, \:\: {\Pdef {b}
{Mul}}, \:\: {\Pdef {l} {C(d,b)}}, \:\: {\Pdef {p} {E(l,3)}}, \:\: {\Pcall {p}
{Unit(4)}} \\
\rightarrow & & {\Pdef {a} {Print}}, \:\: {\Pdef {d} {B(a)}}, \:\: {\Pdef {b}
{Mul}}, \:\: {\Pdef {l} {C(d,b)}}, \:\: {\Pdef {o} {PairB}}, \:\: {\Pcall {o}
{Trip(l,3,4)}} \\
\rightarrow & & {\Pdef {a} {Print}}, \:\: {\Pdef {d} {B(a)}}, \:\: {\Pdef {b}
{Mul}}, \:\: {\Pdef {l} {C(d,b)}}, \:\: {\Pcall {l} {Unit(Pair(3,4))}} \\
\rightarrow & & {\Pdef {a} {Print}}, \:\: {\Pdef {d} {B(a)}}, \:\: {\Pdef {b}
{Mul}}, \:\: {\Pcall {b} {Doub(d,Pair(x,y))}} \\
\rightarrow & & {\Pdef {a} {Print}}, \:\: {\Pdef {d} {B(a)}}, \:\: {\Pcall {d}
{Unit(12)}}
\end{eqnarray}
\caption{Elaboration of Example}
\label{fig:elaborate}
\end{figure*}
The values $3$ and $4$ are gathered together to form a pair by step (6). This
pair
is sent to the $Mul$ process which sends on the product to the process given by
the first argument to $Doub$.

Many of the rules in the automatically generated code create a process
and immediately send it a message. Since most of the rules generated only
match a single pattern each, it is possible to expand them out and build
rules with larger numbers of actions.
In Figure~\ref{fig:optimised}
we give the result of some simple optimizations applied to the example using
knowledge of the pairing operation, but not arithmetic operations.
\begin{figure*}[tb]
\begin{eqnarray*}
\PruleSpawn {s}{{\bf Start}} {{\bf Triv}} {\Ppar {\Pdef {d} {B(a)}} {\Ppar
{\Pdef {b} {{\bf Mul}}} {\Ppar {\Pdef {a} {{\bf Print}}} {\Pcall {b} {{\bf
Doub}(d,{\bf Pair}(3,4))}}}}} \\
\PruleSpawn {r} {B(a)} {{\bf Unit}(e)} {\Pcall {a} {{\bf Unit}({\bf Pair}(e,{\bf
Triv}))}}
\end{eqnarray*}
\caption{Optimisation of the Example Code}
\label{fig:optimised}
\end{figure*}

Most of the code is inherently sequential, so it will reduce to
something corresponding to normal expression evaluation using a
continuation-passing style.

% JRWG Add a channel example later perhaps

\section{OGRe Implementation}\label{sect:implementation}

We will summarise the current state of implementation of OGRe and outline
potential for future work. A translator has been written in SML which will
convert a \Lx\ to OGRe. The input may either be a text file or an SML program by
using the SML compiler to generate its internal lambda form.
The translator is able to interpret OGRe code or may generate corresponding C
for compilation.

\subsection{OGRe on Sequential Machines}

The current C code provides an efficient simulation of the fine-grain
concurrency of OGRe execution. An OGRe rule may either reduce the number of
messages, by simply changing state and generating no new messages, it may keep
the number constant by generating exactly one message on the body, or it may
increase the number of messages.

The C code uses the execution stack to synchronise computations. The code is
arranged as a loop which matches the rule for a chosen process and message. If a
rule maintains the number of messages, then the newly generated message is
chosen along with its target process and the execution loop is entered again.

If a rule generates several messages, then for all but the last the code calls a
new instance of the execution loop. If a rule generates no messages, the loop
exits. The effect of this is to maintain sequential threads where possible. In
the \F\ translation, only rules for the concurrency features change the number
of messages; the functional part generates code which always produces one new
message per rewrite. Generating no messages corresponds to waiting for
communication, or process termination. Generating extra messages corresponds to
completion of communication, or process creation.

\subsection{OGRe on Shared or Distributed Memory Machines}

Even on a parallel machine it is expected that advantage will be taken of
sequential threads. The execution technique described above can be used, with
loops terminating if some access is blocked (when the access is satisfied a
message will be sent to resume the suspended thread). On a parallel machine with
free processing resources we will want to release multiple messages to other
processors, since they represent available parallel threads of work. Once the
available processors are saturated we will want to return to more of a
sequential mode.
However, if the machine subsequently becomes lightly loaded, work may have been
locked in the stack. As a consequence, it may be desirable to make messages
available for stealing by setting up a descriptor for all messages before
processing then in sequence. Clearly the processor may return to find that such
a message has already been handled.

The model would seem suitable for execution on shared memory machines. For
distributed memory machines it will be necessary to export processes. This
should not be difficult as process states are small. However, it may be that
several connected processes should be exported together. For the actual handling
of messages, the Active Messages~\cite{AM} approach seems very appropriate. The
design decisions of OGRe have been carefully chosen to remove the need for
extensive locking, or queuing of messages, since all processes should be ready
to handle every message they will be sent.

\section{Conclusions}

We have presented a model for \emph{Object Graph Rewriting}. OGRe aims to be
carefully designed low level intermediate code for implementation of a range of
programming languages. The first application of the model is the implementation
of \F\ in such a way that the cost of concurrent and functional styles are kept
in balance. The initial target is sequential machines, though parallel
implementation is under investigation. 

\begin{thebibliography}{9}

\bibitem{Paragon}
P. Anderson, D. Bolton \& P. Kelly:
\emph{Paragon Specifications: Structure, Analysis and Implementation}, \\
Proc PARLE'92. LNCS 605. June 1992. (1992) 

% *** More recent version in ?TCS?
\bibitem{CHAM}
G. Berry \& G. Boudol:
\emph{The  Chemical Abstract Machine},
Proc. POPL 90, p 81-94. (1990) 

\bibitem{AM}
T. v Eicken, D.E. Culler, S.C. Goldstein \& K.E. Schauser,
\emph{Active Messages: a Mechanism for Integrated Communication and
Computation},
International Symposium on Computer Architecture '92, ACM. (1992).

\bibitem{Parle92}
J.R.W. Glauert:
\emph{Asynchronous Mobile Processes
and Graph Rewriting}, 
Proc PARLE'92. LNCS 605. June 1992. pp. 63-78. (1992) 

\bibitem {SemSym}
J.R.W. Glauert, L. Leth \& B. Thomsen:
\emph{A New Translation of Functions as Processes},
SemaGraph '91 Symposium, December 1991. (1991)

\bibitem{MDFM}
J.R. Gurd, C.C. Kirkham, \& I. Watson:
\emph{The Manchester Prototype Dataflow Computer}, Comm. ACM, Vol. 28, No. 1, pp.
34-52, (1985).

\bibitem{Facile}
A. Giacalone, P. Mishra, \& S. Prasad:
\emph{Facile: A Symmetric Integration of Concurrent and
Functional Programming},
IJPP, Vol 18, No 2, p 121-160. (1989) 

\bibitem{DistribFacile}
A. Kramer \& F. Cosquer:
\emph{Distributing Facile},
MAGIC Note 12, ECRC. October 1991. (1991) 

\bibitem{MachFacile}
F. Knabe:
\emph{A distributed protocol for the generalized select command},
MAGIC Note 11, ECRC. July 1991. (1991)

\bibitem{KuoFacile}
Kuo, T.-M.:
\emph{Magic Facile version 0.3},
MAGIC Note 22, ECRC. March 1992. (1992)

\bibitem{Leth91}
L. Leth:
\emph{Functional Programs as Reconfigurable Networks of
Communicating Processes}, \\
Ph.D. Thesis, ICSTM. (1991) 

\bibitem{FacileCHAM}
L. Leth \& B. Thomsen:
\emph{Some Facile Chemistry},
ECRC Technical Report ECRC-92-14. May 1992. (1992) 

\bibitem{CCS}
R. Milner: 
\emph{A Calculus of Communicating Systems},
Springer LNCS 92. (1980)

\bibitem{FunAsProcs}
R. Milner: 
\emph{Functions as Processes},
Automata, Languages, and Programming. Springer LNCS 443. (1990)
Also: Technical Report INRIA Sophia Antipolis, June 1989. 

\bibitem{PolyPi}
R. Milner: 
\emph{The \PPC: A Tutorial},
Technical Report ECS-LFCS-91-180, Edinburgh University, October 1991. (1991)

\bibitem{Pi}
R. Milner, J. Parrow, \& D. Walker: 
\emph{A Calculus of Mobile Processes}, Parts I and II,
Technical Report ECS-LFCS-89-85, Edinburgh University, June 1989. (1989)

\bibitem{Shapiro}
E.Y. Shapiro:
\emph{The Family of Concurrent Logic Programming Languages}, Computing Surveys,
Vol. 21 (3), pp. 412-510. (1989)

\bibitem{MessageBrokers}
M.J. Wise: 
\emph{Message Brokers and Communicating Prolog Processes}, 
Proc PARLE'92. LNCS 605. June 1992. pp. 535-549 (1992) 

\end{thebibliography}

\end{document}

\bibitem[{Abr88}]{Abr88}
S. Abramsky:
\emph{The Lazy Lambda Calculus},     
Chapter 4 in D. Turner (ed.),
Research Topics in Functional Programming, 
pp. 65-116, Addison Wesley, 1988.

\bibitem[{Bur84}]{Bur84}
F.W. Burton: 
\emph{Annotations to Control Parallelism and Reduction Order in
the Distributed Evaluation of Functional Programs},
TOPLAS, Vol 6, No 2, p 159-174. (1984) 

\bibitem [{GKS91}]{Dactl}
J.R.W. Glauert, J.R. Kennaway, \& M.R. Sleep:
\emph{Dactl: An Experimental Graph Rewriting Language},\\
Proc. 4th International Workshop on Graph Gra\-mmars, Bremen, 1990.
Springer LNCS 532. (1991)

\end{document}
%%% End of LaTeX Document %%%
