\documentclass[a4paper]{article}
%\input{BoxedEPS}
%\HideDisplacementBoxes
%\SetOzTeXEPSFSpecial  
%\SetRokickiEPSFSpecial  

% 1in margins at left and right
\oddsidemargin=0in
\evensidemargin=0in
\textwidth=6.25in              % A4 paper is 8.25in wide

% 1in margins at top and bottom
\headheight=0pt
\headsep=0pt
\topmargin=0in
\textheight=9.7in              % A4 paper is 11.7in high

\pagestyle{plain}
\setlength{\parindent}{0cm}
\setlength{\parskip}{\medskipamount}
\setlength{\itemsep}{\smallskipamount}

\begin{document}

\newtheorem{thm}{Theorem}[section]
\newtheorem{comment}[thm]{Comment}

\bibliographystyle{acm}

\title{Object Graph Rewriting}

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

\maketitle

\begin{abstract}

\emph{Object Graph Rewriting} (OGRe) is a computational model which
combines ideas from graph rewriting and process calculi. OGRe has been designed
for implementing multi-paradigm languages such as Facile, which combines
functional and concurrent programming.

Simple objects, which have states represented by tree-structured terms,
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 is
inherently concurrent, but fine-grained, so distributed implementation is not
necessarily beneficial.

We introduce OGRe with some simple examples and then provide a formal definition.
\end{abstract}
%

\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{\PparX}[2]{{#1}, {\\ & & \hspace{1cm} #2}}
\newcommand{\Pcall}[2]{{#1}\,!\,{#2}}
\newcommand{\Pprim}[2]{{#1}\,=\,{#2}}
\newcommand{\Pdef}[2]{{#1}:{#2}}
\newcommand{\PruleHead}[3]{& & \Ppar{\Pdef{#1}{#2}}{\Pcall{#1}{#3}} \rightarrow}
\newcommand{\PruleMore}[3]{& & \hspace{0.75cm} \Ppar{#1}{\Ppar{#2}{#3}},}
\newcommand{\PruleEnd}[1]{& & \hspace{0.75cm} {#1};}
\newcommand{\Prule}[5]{\PruleHead{#1}{#2}{#3} \\
  \PruleEnd{\Ppar{#4}{\Pdef{#1}{#5}}}}
\newcommand{\PruleChange}[4]{\PruleHead{#1}{#2}{#3} \\
  \PruleEnd{\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

\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; in lazy functional languages,
computation only takes place when needed, or demanded; computations in concurrent
logic languages may block waiting for instantiation of shared variables.

\subsection*{Process Implementation of Facile}

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. The existing practical
implementation of the language~\cite{DistribFacile} uses Standard ML to provide the
functional part of the language, with concurrency primitives introduced through a
library of new system functions. In that implementation the process features of \F\
map to threads, and are therefore more expensive to use than the functional
features.

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

Building on such process translations of the \Lx\, new translations were developed
to map both the functional and concurrent features of \F\ into networks of small
processes. This provides a uniform representation of all features of the language,
so that the relative cost of using the concurrent features of \F\ is much reduced.
The ultimate goal is to exploit the inherent concurrency of the process networks in
an implementation on a parallel machine.

\subsection*{Asynchronous Process Calculi}

A number of options were considered when selecting the underlying process calculus.
One approach was to use process notations  close to the \PPc\ \cite{PolyPi} in
which communication is name or channel-based. Translations such as those of Milner
may be employed as reported in \cite{NewTrans}.

The full generality of the \Pc\ is not required for these translations.
In~\cite{Parle92} we report a variant of asynchronous \Pc\ (see \cite{HonTok91} and
\cite{Bou92}) in which all output actions are followed by the empty process and
consequently synchronisation between input and output actions is not required. The
variant allows communication of term structures giving equivalent power to an
asynchronous \PPc. It also omitted choice (sum) operators and used only input
guarded replication constructs. Hence it was in the style of the mini asynchronous
\Pc\ which has been the focus for much recent research.

Implementation experiments used the graph rewriting notation
Dactl~\cite{GraGraDac91} to model the mini (synchronous or asynchronous) \Pc.
However the full power of Dactl was not required and the implementation involved
interpretation rather than compilation. 

\subsection*{Object Graph Rewriting}

When the translation schemes mentioned above are analysed further we find that: the
channels used are closely associated with a particular process; this process is the
only one to receive messages from the channel; and furthermore, the process
receives messages from no other channel. Finally, no process which sends a message
needs to synchronise with a remote process able to receive the message.

Exploiting these facts, a process calculus was developed in which communicating
agents use asynchronous process-based (or location-based point-to-point)
communication. This contrasts with the synchronous channel-based (or name-based)
communication of CCS, and the \Pc. 

The essence of this process calculus is captured by a rewriting model \emph{Object
Graph Rewriting} (OGRe) which is reported here. OGRe can be seen as a very minimal
version of Paragon \cite{Paragon}. Although the first application of OGRe has been
in the implementation of \F, the model is general and can be used to implement 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.
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 the existing implementation of 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.

\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. Pattern-directed rewriting rules determine
the way in which a process responds to the arrival of a message.

Computation proceeds by picking a message and the process to which it is directed,
and replacing them by new processes and messages as specified by a matching rewrite
rule.

Figure~\ref{fig:df1} shows a set of OGRe rules and figure~\ref{fig:dfexec} traces a
computation based on the same rules.

Each OGRe process has a name taken from an unbounded set of \emph{process names}
such that each newly created process has a distinct name. 

An OGRe system has a finite set of \emph{state term symbols}, used to construct
process states, and a finite set of \emph{data term symbols}, used to construct
messages, and also subterms of process states and messages. The symbol sets are
disjoint. Each symbol has a fixed arity which determines the number of arguments of
terms which are created. Term arguments may also include process names and
\emph{primitive data values}, such as integers.

OGRe rules may also use \emph{primitive operation symbols} (disjoint from other
symbols) for representing basic functions over primitive data values. Rules also
use variables which are bound during pattern matching to process names, data terms,
or primitive data values.

\subsection*{OGRe Processes} An example of a declaration of an OGRe process with
name $m$ is ${\Pdef {m} {LSubL(p,Int(15))}}$. The process state is given by the
term $LSubL(p,Int(15))$ with a state term symbol and zero or more arguments.
Arguments may be process names, primitive data values and data terms. In the
example above, the process has state term symbol $LSubL$ and two arguments. The
first, $p$, is a process name and the second, $Int(15)$ is a data term with a
primitive data value as argument.

\subsection*{OGRe Messages} An example of a message specification is $\Pcall {a}
{R(Int(2))}$. Messages are directed to a named process and have contents defined by
a data term. In the example, the target process is named $a$ and the data term of
the message has symbol $R$ and a single argument $Int(2)$ which represents a boxed
integer value.

\begin{figure*}
\begin{eqnarray*}
\PruleHead {e} {{Start}} {{POMTrigger}} \\
\PruleMore {\Pdef {p} {PrintL}} {\Pdef {m} {LSubL(p,Int(15))}} {\Pdef {a} {RMul(m)}} \\
\PruleEnd {\Ppar {\Pcall {a} {L(Int(6))}} {\Ppar {\Pcall {a} {R(Int(2))}} {\Pdef {e} {{Start}}}}} \\
\PruleHead {r} {RMul(d)} {L(l)} \\
\PruleEnd {\Pdef {r} {RMulL(d,l)}} \\
\PruleHead {r} {RMul(d)} {R(l)} \\
\PruleEnd {\Pdef {r} {RMulR(d,l)}} \\
\PruleHead {r} {RMulL(d,Int(a))} {R(Int(b))} \\
\PruleEnd {\Ppar {\Pprim {c} {{PMul}(a,b)}} {\Ppar {\Pdef {r} {Done}} {\Pcall {d} {R(Int(c))}}}} \\
\PruleHead {r} {RMulR(d,Int(a))} {L(Int(b))} \\
\PruleEnd {\Ppar {\Pprim {c} {{PMul}(a,b)}} {\Ppar {\Pdef {r} {Done}} {\Pcall {d} {R(Int(c))}}}} \\
\PruleHead {r} {LSubL(d,Int(a))} {R(Int(b))} \\
\PruleEnd {\Ppar {\Pprim {c} {{PSub}(a,b)}} {\Ppar {\Pdef {r} {Done}} {\Pcall {d} {L(Int(c))}}}} \\
\PruleHead {r} {PrintL} {L(v)} \\
\PruleEnd {\Ppar {\Pdef {p} {{Print}}} {\Ppar {\Pdef {r} {Done}} {\Pcall {p} {{Unit}(v)}}}}
\end{eqnarray*}
\caption{OGRe dataflow rules for an arithmetic expression}
\label{fig:df1}
\end{figure*}

\subsection*{OGRe Rules}

Computation in OGRe is determined by pattern-directed rewriting rules. The pattern
for a rule has a pattern for the state term of a process, and a pattern for the data
term for a message directed to that process. The pattern contains a variable that
will be bound to the name of the root process, and may contain other variables which
can match process names, data values, or data terms in the process state or message.

The right hand side of an OGRe rule always contains a redeclaration for the root
process named in the pattern. Often, for \emph{functional} processes, the state is
unchanged, but in rules for \emph{mutable} processes the arguments and even the
symbol of the state term may be changed.

No variable may appear more than once in the pattern, except for the name of the root
process which is also the target of the message. A state term may not consist of just
a variable. All variables naming processes declared in the body must be unique. The
variable naming the root process must be included, but all other variables in the
pattern may only be used as arguments to terms. Variables naming the result of
applying primitive functions must be unique. All variables occurring only in the body
must name results of primitive functions, or processes declared in the body.

Figure~\ref{fig:df1} illustrates a possible application of OGRe by giving an example
set of rules which model a computation by dataflow. This example has been chosen
because it illustrates a range of the features of OGRe. It is not intended as a
realistic example of how OGRe will be used in practice. A number of other
applications are given in the next section.

In dataflow, an operator waits for the arrival of a number of tokens carrying data
values. The operator then computes a result and sends it on to a further operator.
When modelling dataflow in OGRe in this way, 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. The state symbol of the process
indicates which argument of the successor node will be formed by the result token.
Hence a process with state $RMul(p)$ creates a result token which will become the
right-hand argument for process $p$.

The first rule
\begin{eqnarray*}
\PruleHead {e} {{Start}} {{POMTrigger}} \\
\PruleMore {\Pdef {p} {PrintL}} {\Pdef {m} {LSubL(p,Int(15))}} {\Pdef {a} {RMul(m)}} \\
\PruleEnd {\Ppar {\Pcall {a} {L(Int(6))}} {\Ppar {\Pcall {a} {R(Int(2))}} {\Pdef {e} {{Start}}}}}
\end{eqnarray*}
will always match the initial configuration of an OGRe computation. In this case it
creates three new processes and two new messages, both in this case directed to the
same process. The state of the root process, $Start$, is unchanged so the process is
functional.

The rules for $RMul$, $RMulL$ and $RMulR$ in figure~\ref{fig:df1} model dataflow
nodes which multiply their arguments and send their result to a destination node as
its right-hand argument. The two $RMul$ rules take in the first argument and change
the process state to hold the first argument and await the second.  The auxiliary
rules $RMulL$ and $RMulR$ await right, or left-hand arguments respectively. They
compute a result, send it on, and become a $Done$ process.

The processes are \emph{mutable} since the first argument to arrive must be captured
and will affect the behaviour when the second arrives. Dataflow nodes which take a
literal argument can be modelled by auxiliary nodes with suitable arguments as in the
process $\Pdef {m} {LSubL(p,Int(15))}$ which awaits an argument and will subtract it
from $15$. This corresponds to an intermediate state which would arise if a process
$\Pdef {m} {LSub(p)}$ received a message $\Pcall {m} {L(Int(15))}$ where $LSub$ is
defined by analogy with $RMul$.

The rule for $RMulL$
\begin{eqnarray*}
\PruleHead {r} {RMulL(d,Int(a))} {R(Int(b))} \\
\PruleEnd {\Ppar {\Pprim {c} {{PMul}(a,b)}} {\Ppar {\Pdef {r} {Done}} {\Pcall {d} {R(Int(c))}}}}
\end{eqnarray*}
illustrates the final form of element which can appear on the right hand side of a
rule: $\Pprim {c} {PMul(a,b)}$ represents a primitive function to multiply data
values for incorporation in new processes and messages.

\subsection*{OGRe Rewriting}

OGRe computation involves a series of rewrites corresponding to the reception of
messages by processes. Each rewrite consumes a message, but may create new messages
and processes. Messages correspond to tasks to be performed, and when no further
messages exist, computation ceases.

When a process receives a message, the state term of the process and the data term
forming the message are matched against the patterns of the OGRe rules. When a match
is found, the message is absorbed, the state of the process may be changed, and new
process and messages may be generated. Rule application may also apply primitive
functions, such as the arithmetic operations on integers.

A process is only involved in computation if it receives messages. If a process is
not the destination of an existing message, and its name is not the argument of a
state term or data term in some other process or message, then the process can never
receive messages and may be garbage collected.

Figure~\ref{fig:dfexec} shows the sequence of execution for a dataflow computation
which computes $15-(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-hand (and only) argument of the print
function.
\begin{figure*}
\begin{eqnarray*}
& &
\Ppar {\Pdef{e}Start} {\Pcall {e} POMTrigger} \\
& \Rightarrow &
\Ppar
  {\Ppar
    {\Pdef{p}{PrintL}}
    {\Pdef{m}{LSubL(p,Int(15))}}
  }
  {\Pdef{a}{RMul(m)}}, \\
& &
\Ppar
  {\Pcall{a}{L(Int(6))}}
  {\Pcall{a}{R(Int(2))}} \\
& \Rightarrow &
\Ppar
  {\Ppar
    {\Pdef{p}{PrintL}}
    {\Pdef{m}{LSubL(p,Int(15))}}
  }
  {\Pdef{a}{RMulL(m,Int(6))}}, \\
& & \Pcall{a}{R(Int(2))} \\
& \Rightarrow &
\Ppar
    {\Ppar
      {\Pdef{p}{PrintL}}
      {\Pdef{m}{LSubL(p,Int(15))}}
    }
    {\Pdef{a}{Done}} \\
& &
    {\Pcall{m}{R(Int(12))}} \\
& \Rightarrow &
\Ppar
  {\Pdef{p}{PrintL}}
  {\Pdef{m}{Done}} \\
& &
  {\Pcall{p}{L(Int(3))}} \\
& \Rightarrow &
\Ppar
  {\Pdef{p}{Done}}
  {\Pdef{q}{\bf Print}} \\
& &
  {\Pcall{q}{{\bf Unit}(Int(3))}}
\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 unreferenced $Done$
processes are garbage collected.


\subsection*{Further OGRe Constraints}

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 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 execution continues by repeated rewriting of 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 as the destination or in the contents of any message.

As has been mentioned, symbols labelling state and data terms are distinct.
Symbols have fixed arity. Further, we associate a type with symbols so that a
particular argument must always refer to either a process name, a data term, or
primitive data. This enables us to check that all messages will be directed to
processes able to receive them.

\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}

The example in the previous section illustrated a model for dataflow in OGRe.
The example
contained 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 must increase when a result is needed  by
several successors, and a duplication node is used.

\begin{figure*}
\begin{eqnarray*}
\PruleHead {e} {Start} {POMTrigger} \\
\PruleMore {\Pdef {p} {PrintL}} {\Pdef {m} {LMul(p)}} {\Pdef {d} {LRDup(m,m)}} \\
\PruleEnd {\Ppar {\Pcall {d} {L(Int(6))}} {\Pdef {e} {Start}}} \\
\PruleHead {p} {LRDup(d,e)} {L(x)} \\
\PruleEnd {\Ppar {\Pcall {d} {L(x)}} {\Ppar {\Pcall {e} {R(x)}} {\Pdef {p} {Done}}}} \end{eqnarray*}
\caption{Duplication of dataflow tokens}
\label{fig:dup}
\end{figure*}

In Figure~\ref{fig:dup}, we give the rule for duplicating tokens and an example of
how it could be used to form the square of a number. Tracing execution of the
example is left as an exercise for the reader!

Similar rules $LLDup$, $RLDup$, and $RRDup$ would be needed in other
circumstances.

\subsection*{Modelling Communication Channels}

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. In Figure~\ref{fig:asynccomm}, 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 explicitly until a producer provides data.

\begin{figure*}
\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(VQ(v,q))}
\end{eqnarray*}
\caption{Rules for Asynchronous Communication}
\label{fig:asynccomm}
\end{figure*}

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*}
\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 an empty queue, $EQ$. The two $Put$ actions
stack values so that in this trace 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*}
\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 as in Figure~\ref{fig:vN}. The $Set$ message
carries data and the identity of a process to receive acknowledgement in order to
provide serialisation. We return the old contents to provide test-and-set
functionality.
\begin{figure*}
\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*}
\caption{A model for von Neumann cells in OGRe}
\label{fig:vN}
\end{figure*}

Figure~\ref{fig:lv} shows that by adding slightly more sophisticated behaviour, we
can model a logic variable in the framework of concurrent logic
programming~\cite{Shapiro}. The model suggested is for illustration only, as the
properties of such variables 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
extralogical $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.

\begin{figure*}
\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(d)}}}
{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*}

\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}. The channel
representation is closely related to the model for synchronous channel
communication above.

Use of process spawning introduces potential concurrency and channels may be used
to synchronise and communicate between spawned processes. Otherwise, \F\ functions
execute strictly sequentially, adopting the same semantics as ML. The translation
of the functional subset of \F\ is a development of the work reported in
\cite{NewTrans} and \cite{Parle92}. Within this subset, every rewrite generates
precisely one new message so that there is always a single thread of control.

The translation to OGRe is not very direct, involving several OGRe rewrites per
function call. However, there is considerable scope for optimisation by symbolic
evaluation. In particular, the translations produce code with all primitive values
boxed, but optimisation will achieve unboxing in many situations.

\section{OGRe Formalisation}

\begin{comment}
At present I am trying to introduce a more respectable concept of bound and free
variables. There is a mixture of a syntactic presentation and an algebraic presentation.
I will try to fix on the syntactic approach and then perhaps produce something
algebraic. This means changes in this section which will not be applied consistently in
the rest of the document. What were called Processes are now termed Agents, while
Process covers Agents and Messages (and Computations).
\end{comment}

\begin{comment}
Computations can be regarded as an optimisation. I will therefore omit them from the
first version below. I will also (later) try to show that they can be transformed away.
The transformed version will take more "steps" unless (which I might) I regard a
computation as a "step".

Computations are of the form
\begin{eqnarray*}
    n=F(o,p)
\end{eqnarray*}
example
\begin{eqnarray*}
    n=IAdd(3,4)
\end{eqnarray*}
and we can assume that they only appear in programs in rules of the form:
\begin{eqnarray*}
    r:Add(o,p), r!Dest(s) \rightarrow r:Add(o,p), n=IAdd(o,p), s!Res(n)
\end{eqnarray*}
We could consider the computations as being expressed by an equivalent rule without
computations:
\begin{eqnarray*}
    r:Add(3,4), r!Dest(s) \rightarrow r:Add(3,4), s!Res(7)
\end{eqnarray*}
and so on for all possible arguments of $IAdd$.
\end{comment}

\begin{comment}
There is a question whether there should be a distinction between primitive data (such as
binary numbers 3, 4, ... and characters `a', `b', ...) and other data values without
arguments (such as True, False, perhaps).

In the low-level implementation these are distinguished and not allowed to mix in the
same argument position of a symbol. Nor are primitive data values permitted as contents
of messages (they must be boxed). For now, I will not make this distinction since the
implementation simply provides additional context dependent constraints. I will try to
refine the definition to express these additional constraints later.

A further aspect of the implementation is that the types of symbols (arities and classes
of arguments) are mostly derived from context. Here, we assume that they are specified in
advance.
\end{comment}

\begin{comment}
The syntax covers both OGRe rules (the program code) and OGRe data (the program execution
state). OGRe data will contain only agent name variables (and hence no computations or
primitive operation systems).
\end{comment}

\subsection{Version 1}

\subsubsection*{Classes}
\begin{description}
\item [agent class] $AC$
\item [data class] $DC$
\end{description}

\subsubsection*{Symbols}

\begin{description}
\item [agent term symbols] $ATS$
\item [data term symbols] $DTS$ of class $DC$
\end{description}

Agent term symbols are disjoint from data term symbols. Each $ATS$ and $DTS$ is
associated with a sequence of classes. The length of the sequence gives the arity
of the symbol and the classes constrain the form of the arguments (see below).

\subsubsection*{Variables}

\begin{description}
\item [agent name variables] $ANV$ of class $AC$
\item [data term variables] $DTV$ of class $DC$
\end{description}
Data term variables are disjoint from agent name variables.

\subsubsection*{Terms}

\begin{description}
\item [expressions] $E ::= P$ $\mid$ $E , E$
\item [processes] $P ::= A$ $\mid$ $M$
\item [agent] $A ::= n:AT$, where $n \in ANV$
\item [messages] $M ::= n!DT$ where $n \in ANV$
\item [agent terms] $AT ::= F$ $\mid$ $F(TA)$, where $F \in ATS$
\item [data terms] $DT ::= G$ $\mid$ $G(TA)$, where $G \in DTS$
\item [term arguments] $TA ::= DV$ $\mid$ $TA , TA$
\item [data values] $DV ::= DT$ $\mid$ $x$ $\mid$ $n$, where $x \in DTV$ and $n \in PNV$
\end{description}
Expressions contain a number of processes (agents and messages). Agents are named agent
terms. Messages are data terms directed to agents. Agent terms and data terms may have
data terms and variables as arguments

\emph{Constraints:} In $AT$ and $DT$ the arities and classes of symbols are respected.
If a symbol argument is of class $AC$ then it takes the form $n \in ANV$. If a symbol
argument is of class $DC$ then it takes the form $DT$ or $x \in DTV$.


\emph{Definitions:} We consider bound and free ocurrences of variables in expressions.
The function $occurs$ gives the set of variables which \emph{occur} in an expression.
The only binder is  $n:AT$, the agent definition form, which binds all ocurrences of $n$
in the expression. The function $bound$ yields the set of variables \emph{bound} in an
expression. The function $free$ yields the set of variables that occur \emph{free} in an
expression.
\begin{eqnarray*}
occurs(E_1 , E_2) & = & occurs(E_1) \cup occurs(E_2) \\
occurs(n:AT) & = & \{n\} \cup occurs(AT) \\
occurs(n!DT) & = & \{n\} \cup occurs(DT) \\
occurs(F) & = & \{\} \\
occurs(F(AT)) & = & occurs(TA) \\
occurs(G) & = & \{\} \\
occurs(G(AT)) & = & occurs(TA) \\
occurs(TA_1 , TA_2) & = & occurs(TA_1) \cup occurs(TA_2) \\
occurs(x) & = & \{x\}, x \in DTV \\
occurs(n) & = & \{n\}, n \in PNV \\
bound(E_1 , E_2) & = & bound(E_1) \cup bound(E_2) \\
bound(n:AT) & = & \{n\} \\
bound(n!DT) & = & \{ \} \\
free(E) & = & occurs(E) \setminus bound(E)
\end{eqnarray*}

We say that definitions in $E$ are \emph{linear} if every $n \in bound(E)$ is bound by
only one agent definition in $E$. An expression is \emph{closed} if there are no free
ocurrences of variables, and \emph{open} otherwise. We say that ocurrences in a
construct are \emph{linear} if every variable occurs at most once.

\subsubsection*{Rules}

\begin{description}
\item [rules] $R ::= E_l \rightarrow E_r$
\end{description}

\emph{Definitions:} We extend earlier concepts to rules. $E_l$ takes the role of the
\emph{pattern} for the rule. Free variable occurrences in $E_l$ bind variables in $E_r$.
\begin{eqnarray*}
occurs(E_l \rightarrow E_r) & = & occurs(E_l) \cup occurs(E_r) \\
bound(E_l \rightarrow E_r) & = & occurs(E_l) \cup bound(E_r) \\
\end{eqnarray*}


\emph{Constraints:}
$E_l$ is an expression in $E$ satisfying the following:
$E_l$ is of the form $n:AT, n!DT$ where occurrences in $n:AT$ and $n!DT$ are linear.
$free(n:AT) \cap free(n!DT) = \emptyset$.
$occurs(E_r) \subseteq occurs(E_l)$.
$occurs(E_l) \cap bound(E_r) = n$

\emph{Properties:}
The pattern $E_l$ has no repeated ocurrences, except for $n$. Recall that $n$ is bound
in $n:AT$.
Ocurrences in $E_l$ bind ocurrences in $E_r$ and a rule contains no free variables.
There is an agent in $E_r$ with the name $n$. Hence $E_r$ cannot be empty.
No other agent defined in $E_r$ can have a name used in $E_l$ and hence bound by pattern
matching.

And probably others I have omitted.

\subsubsection*{Rewriting}

An OGRe program starts with a ruleset (a set of rules) and an OGRe expression (the
initial state). Execution proceeds by rewriting steps as described below until no
further rewriting is possible.

When applying rules, terms are considered up to associativity and
commutativity of parallel composition. A redex is a pair of an agent and a message
from the program state which is an instantiation of $E_l$ from an OGRe rule. Its
contractum is the corresponding instantiation of $E_r$.

\begin{description}
\item [Ruleset] $RS ::= R ; ...$
\item [Program State] $PS ::= E$
\end{description}

\emph{Constraints:}
$PS$ is a closed expression. Definitions in $PS$ are linear.

\emph{Properties:}
Hence there are no data term variables in $PS$.

A rule $R$ of form $E_l \rightarrow E_r$, \emph{matches} an expression $E$ of form
$m:AT, m!DT$ if there is a substitution $\sigma$ with domain
$bound(E_l \rightarrow E_r)$ such that $\sigma(E_l) = E$. The contractum is
$\sigma(E_r)$.

A \emph{rewrite step} takes a state $E, E'$ to state $\sigma(E_r), E'$, where ruleset
$RS$ contains a rule $E_l \rightarrow E_r$ and $\sigma$ is a substitution such that
$\sigma(E_l) = E$ and definitions in $\sigma(E_r), E'$ are linear.

\emph{Properties:}
$E$ is of form $m:AT, m!DT$. $\sigma$ maps agent names to agent names and data term
variables to data terms. $\sigma$ applies to any agent names in $E_r$ that are not
in $E_l$ and is chosen so that these map to new and distinct agent names not found
in the program state. This ensures that definitions will be linear in the resulting state.

Rewriting of a program continues with the new state. Rewriting terminates when no further
steps can be made.

\begin{comment}
I don't think that Jeong-Ho needs to worry about the rest of this, but it is included as
part of my attempt to formalise some other issues.
\end{comment}

\subsubsection{Garbage Collection}

An agent can be garbage collected if it can never take part in future rewrites. This
will be the case if no message could be created which will be sent to the agent
because there is no use of the agent name in the rest of the program state. It may
be that a set of agents contains a cycle of uses, but none of the set is used by the rest
of the program state. In this case, the whole set can be removed.

Let the program state $PS$ be partitioned into two expressions $E_L, E_G$ where $E_G$
contains only agents. If $free(E_L) = \emptyset$ then agents in $E_G$ can take part in
no further rewrites, and can be removed. $E_G$ will be termed \emph{garbage} in $PS$.
(By this definition, messages can never be garbage).

Let a program state $PS$ be expressed as $E_L, E_G$ where $E_G$ is the maximal set of agents
for which $E_G$ is garbage in $PS$. We term $E_L$ the \emph{live component} of $PS$.

Replacing a program state by its live component does not affect the future choice
of rewriting steps during execution.

\subsubsection{Functional Processes}

We will use the term functional for agents that never change their state as a result of
rewriting.

A rule is said to be \emph{functional} if it has the form $m:AT, m!DT \rightarrow m:AT, E$.
The effect of rewriting according to such a rule will leave the process in the redex
unchanged.

A state term symbol $F$ is said to be \emph{functional} if every rule of the form
$m:F(AT), m!DT \rightarrow E$ is functional. An agent $A$ is said to be \emph{functional}
if its state term has a functional symbol.

Since a functional agent will never change its state, a message sent to such an agent
is either an immediate candidate for taking part in a rewrite, or can never become one.
A message which cannot take part in a rewrite could be regarded as an error and will
certainly remain part of the program state in all subsequent rewrites.

\subsubsection{Deadlock}

A program is \emph{deadlocked} if it terminates, but messages remain.
If a message is sent to a functional agent, but cannot form part of a redex, then
the program can only terminate in deadlock. Other forms of deadlock are possible involving
messages to non-functional agents. If a program terminates without deadlock then it
can be seen that all the remaining agents are garbage.

\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*{Memory Organisation}

State and data terms are represented by consecutive memory words containing a
symbol followed by arguments. Since OGRe symbols are typed, we can, without loss
of generality, insist that all primitive data arguments precede process names and
data terms (both of which are represented by machine pointers). This simplifies
garbage collection as every term contains one or more data words (there is a
symbol at least) followed by zero or more pointers.

Symbols for state terms map to positive integers, distinguishing them from data
symbols which use negative integers.


\subsection*{Rule Matching}

The current C code provides a reasonably efficient simulation of the fine-grain
concurrency of OGRe execution. Code for rules is compiled into a switch statement,
and selected according to the state symbol of the process receiving a message.

A task queue is maintained of messages to be processed and the code for the symbol
of the topmost target process is executed. Matching proceeds by testing for data
symbols as required and building up a table referencing processes and data values
bound to pattern variables. When matching succeeds, new processes may be created
with state arguments derived from values matched to pattern variables. Messages
may be created and queued for further consideration.

Often a rule will generate exactly one new message. This sequential case is
optimised so that no manipulation of the queue is required. If more than one
message is generated, messages are pushed onto the task queue. If no new messages
are generated, the task queue is popped and the next message selected. Execution
ceases when the queue becomes empty.

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.

\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 aim is to achieve good performance on sequential machines, though
without discounting parallel implementation.

\bibliography{OGRe}

\end{document}

%%% End of LaTeX Document %%%
