%%% Start of LaTeX Document %%%
\documentstyle[a4,11pt]{article}

\title{Parallel Implementation of Functional Languages \\
                Using Small Processes}
\author{
        {\it John Glauert\thanks{Partially supported by ESPRIT BRA 3074: Semagraph and by ECRC, Munich, during a sabbatical visit}} \\
	School of Information Systems \\
	University of East Anglia \\
	Norwich NR4 7TJ, UK \\
	Tel: +44 603 592671 \\
	Fax: +44 603 507720 \\
	{\em jrwg@sys.uea.ac.uk}}
\date{Submitted to PACT 1995}

\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{\Pdef}[2]{{#1}:{#2}}
\newcommand{\Prule}[5]{\Ppar{\Pdef{#1}{#2}}{\Pcall{#1}{#3}} & \rightarrow & \Ppar{\Pdef{#1}{#5}}{#4}}
\newcommand{\PruleChange}[4]{\Ppar{\Pdef{#1}{#2}}{\Pcall{#1}{#3}} & \rightarrow & \Pdef{#1}{#4}}
\newcommand{\PruleSpawn}[4]{\Prule{#1}{#2}{#3}{#4}{#2}}
\newcommand{\PresRule}[6]{\Ppar{\Pdef{#1}{#2}}{\Pcall{#1}{#3}} & \rightarrow & (\Ppar{\Pdef{#1}{#5}}{#4})\restrict{#6}}
\newcommand{\PresRuleChange}[4]{\Ppar{\Pdef{#1}{#2}}{\Pcall{#1}{#3}} & \rightarrow & \Pdef{#1}{#4}}
\newcommand{\PresRuleSpawn}[4]{\Prule{#1}{#2}{#3}{#4}{#2}}

% Translation representation
\newcommand{\transwhere}[3]{& & {\makebox[1.5cm][l]{where}}
{#1}\;?\;{#2}\;\cdot\;(\,{#3}\,)}
\newcommand{\transand}[3]{& & {\makebox[1.5cm][l]{and}}
{#1}\;?\;{#2}\;\cdot\;(\,{#3}\,)}
\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}{{\em return-Subress\/} 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
\begin{document}
\maketitle
\begin{abstract}
We report on a new computational model for the parallel implementation of declarative languages.

\end{abstract}



\section{Introduction and Background}

In the next section we introduce the Object Graph Rewriting model of computation. A more formal sematics 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 fine grain parallel processes for hardware architectures able to exploit very low level concurrency.

\section{OGRe: A Small Process Language}

The {\em 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 primitve data types and structured values.
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.

The following example shows one of a number of possible ways in which arithmetic expressions might be translated:

\begin{eqnarray*}
\Prule {p} {Sub(r)} {Pair(Int(x),Int(y))} {{\Pcall {r} {Int(x+y)}}} {Sub(r)} \\
\PresRule {p} {SumSq(r)} {Pair(x,y)}
  {\Ppar{\Pdef{q}{Mul(s)}}{\Pcall {q} {Pair(x,x)}}} {SumSq(r)} {q}
\end{eqnarray*}

\section{OGRe Examples}\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 by the following fragment which would compute $3-(6*2)$ and send 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{eqnarray*}
& \Ppar{\Ppar{\Ppar{\Pdef{p}{Print}}{\Pdef{m}{SubR(L(p),3)}}}{\Ppar{\Pdef{a}{Mul(R(m))}}{\Pcall{a}{L(6)}}}}{\Pcall{a}{R(2)}}
\end{eqnarray*}

The sequence of execution might be as follows:
\begin{eqnarray*}
& & \Ppar{\Ppar{\Ppar{\Pdef{p}{Print}}{\Pdef{m}{SubR(L(p),3)}}}{\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),3)}}}{\Pdef{a}{MulR(R(m),6)}}}{\Pcall{a}{R(2)}} \\
& \rightarrow & \Ppar{\Ppar{\Ppar{\Pdef{p}{Print}}{\Pdef{m}{SubR(L(p),3)}}}{\Pcall{m}{R(12)}}}{\Pdef{a}{Done}} \\
& \rightarrow & \Ppar{\Ppar{\Ppar{\Pdef{p}{Print}}{\Pcall{p}{R(-9)}}}{\Pdef{m}{Done}}}{\Pdef{a}{Done}}
\end{eqnarray*}

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. Below, we give the rule for duplications and an example of how it could be used to form the square of a number:

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

\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 modeelled by OGRe processes. A channel is represented by a process which coordinates communication between producing and consuming processes. A producer sends a $Put$ message to the channel, with the data as arguemnt. 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 following model supports asynchronous communication since the producer receives no notfication that data has been consumed:

%\begin{figure*}
\begin{eqnarray*}
\Prule {c} {Chan(OQ(v,q))} {Get(r)} {\Pcall {r} {Data(v)}} {Chan(q)} \\
\PruleChange {c} {Chan(q)} {Get(r)} {Chan(IQ(r,q))} \\
\Prule {c} {Chan(IQ(r,q))} {Put(v)} {\Pcall {r} {Data(v)}} {Chan(q)} \\
\PruleChange {c} {Chan(q)} {Put(v)} {Chan(OQ(v,q))}
\end{eqnarray*}
%\caption{Rules for Asynchronous Communication}
%\label{fig:synccomm}
%\end{figure*}

Unsatisfied messages are stacked, so there is no fairness about this particular model. Observe the order in which requests are satisfied in the following example execution:

%%%%%%

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: 

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

Note how an unsatisifed request blocks a thread of control as the channel process changes state but does not generate further actvity. 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 Logic Variables and State}

\subsection{Modelling Facile}


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



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


\section{Conclusions}

\end{document}

\begin{thebibliography}{ECGS92}

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

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

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

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

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

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

\bibitem[{Gla92}]{Parle92}
J.R.W. Glauert:
{\em Asynchronous Mobile Processes
and Graph Rewriting}, 
Proc PARLE'92. LNCS 605. June 1992. (1992) 

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

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

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

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

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

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

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

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

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

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

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

% *** Correct Title required. MJ Wise?
\bibitem[{Wis92}]{MessageBrokers}
M. Wise: 
{\em Message Brokers and Communicating Prolog Processes}, 
Proc PARLE'92. LNCS 605. June 1992. (1992) 

\end{thebibliography}

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