\documentstyle[11pt]{article}
%\documentstyle[a4,11pt]{article}
%\documentstyle[11pt]{mnotes}    

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

\title{Parallel Implementation of Functional Languages \\
                Using Small Processes}
\author{
        {\it John Glauert\thanks{Work done on sabbatical at ECRC, Munich}} \\
	School of Information Systems \\
	University of East Anglia \\
	Norwich NR4 7TJ, UK \\
	{\em jrwg@sys.uea.ac.uk}}
%\reportref{Draft}
\date{Parallel Implementation Workshop, Aachen, September 1992}

\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}[2]{({\nu}\,{#1})\,(\,{#2}\,)}
\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{\PruleChange}[3]{{#1}\;?\;{#2} & := & {#3}}
\newcommand{\PruleSpawn}[3]{{#1}\;?\;{#2} & \rightarrow & (\,{#3}\,)}
\newcommand{\Prule}[4]{{#1}\;?\;{#2} & \rightarrow & (\,{#3}\,)\;:=\;{#4}}
\newcommand{\Ppar}[2]{{#1}\,|\,{#2}}
\newcommand{\Pcall}[2]{{#1}\,!\,{#2}}
\newcommand{\Pdef}[2]{{#1}:\,{#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-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
\begin{document}
\maketitle
\begin{abstract}
We report work in progress on the implementation of languages that integrate concurrent and functional programming styles.

A translation scheme is presented for mapping such languages into process networks using
a simple notation based on communication between named processes. The translation of functional code is sequential, but parallelism arises from use of concurrency constructs in the source language.

Early implementation experiments have used graph rewriting techniques, although work on a more direct implementation is in progress.
\end{abstract}

\section{Introduction and Background}
This paper reports work done at ECRC in close collaboration with Bent Thomsen and Lone Leth.
The work has focussed on techniques for implementing the \F\ language
\cite{Facile} which enhances the \Lc\ with primitives for process spawning and channel-based communication in the style of CCS \cite{CCS}.

Recent work by 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}.

The approach taken by the \F\ group at ECRC 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.
The ultimate goal
is to exploit the inherent concurrency of the process networks in an implementation
on a parallel machine.

Our first approach used process notations that are 
close to the \PPC\ \cite{PolyPi} in which communication is channel-based. This work is reported in \cite{SemSym} and \cite{Parle92}. In such 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, it turned out that in most cases a channel used in the translations was closely associated with a particular process which was the only process to receive messages from the channel. Further, the process would not receive messages from any other channel.

This led us to investigate a model of communicating agents using process-based, or 
point-to-point, communication. This is in contrast to the channel-based 
communication of CCS, and the \Pc.
The  model 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. Later we present a mapping from the new notation to the graph-rewriting language Dactl \cite{Dactl}.

The process-communication 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}.

\section{A Source Language}

For the purpose of investigation we have used 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.

\subsection{Source Language Syntax}
The 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.

% By comparison, the original syntax given for Core \F\ is:
% \begin{eqnarray*}
% e & ::= & x \mid \Labs{x}{e} \mid \Lapp{e}{e}  \mid {\bf channel} 
%   \mid e!e \mid e? \mid {\bf code}(be) \mid {\bf spawn}(be) \\
% be & ::= & {\bf terminate}\,\mid\,{\bf activate}\,e\,\mid\,be \| be
% \end{eqnarray*}

Although the original \F\ language provides more programming flexibility, it is sufficient for our implementation experiments to concentrate on the four primitives described above.

% As indicated in \cite{KuoFacile}, \F\ behaviour expressions do not need
% to be represented as a separate class in the source language. Further,
% there is no need for $terminate$ since this can now be represented  by
% $activate\,()$. We can use expression evaluation to spawn parallel
% processes, so there is no need for parallel composition.

\subsection{Source Language Semantics}

Although the language treated in this paper is slightly different from the original \F\ language, it is clear that there is a direct correspondence between expressions in this language and in the original. Hence we may use the semantics found in \cite{Facile}. We will assume that programs are always closed terms.

It is worth recalling the reduction relation for the \Lc\ sublanguage of \F. The language is given by:
\begin{eqnarray*}
e & ::= &  x \mid \Labs{x}{e} \mid \Lapp{e}{e} \\
v & ::= &  \Labs{x}{e}  
\end{eqnarray*}
$v$ is the class of {\Whnf}s for closed terms.
\begin{center}
\begin{tabular}{lcccl}
$APPL: \:\: {\infer{e \:{\rightarrow}\: e''}
       {e\;e' \:{\rightarrow}\: e''\;e'}
       { }}$
& &
$APPR_v: \:\: {\infer{e' \:{\rightarrow}\: e''}
       {v\;e' \:{\rightarrow}\: v\;e''}
       { }}$
& &
$BETA_v: \:\: (\lambda x.e)\;v \:{\rightarrow}\: e\,[v/x]$
\end{tabular}
\end{center}
We will call the reduction relation defined as the least relation satisfying these rules the {\em sequential\/} strategy. To reduce an application, first the operator will be reduced to \Whnf\, then the operand, and only when both are abstractions will the limited beta-reduction rule be applied. No reduction is performed under $\lambda$s so only a \Whnf\ will be produced.

The sequential strategy is very close to the {\em call-by-value} strategy given by the rules:
\begin{center}
\begin{tabular}{lcccl}
$APPL: \:\: {\infer{e \:{\rightarrow}\: e''}
       {e\;e' \:{\rightarrow}\: e''\;e'}
       { }}$
& &
$APPR: \:\: {\infer{e' \:{\rightarrow}\: e''}
       {e\;e' \:{\rightarrow}\: e\;e''}
       { }}$
& &
$BETA_v: \:\: (\lambda x.e)\;v \:{\rightarrow}\: e\,[v/x]$
\end{tabular}
\end{center}
This is a non-deterministic strategy since operator and operand may be reduced in either order before beta-reduction.

For the pure \Lc\ both of these strategies converge for the same set of terms, but for \F\, as in SML, it is convenient to use the sequential strategy in order to be able to reason about any side effect resulting from evaluation. The lack of implicit concurrency in the expression part of \F\ contrasts with the explicit concurrency provided by the process part.

It would be possible to exploit safe implicit concurrency, where the evaluation order of operator and operand does not affect the observable behaviour of an expression. The approach we have explored is to decorate the hidden apply operators in expressions in the manner of \cite{Bur84}. Sequential application, denoted by $@_s$, is reduced according to $APPR_v$ while call-by-value application, $@_v$, uses $APPR$. The other rules apply to both forms. The combination gives a reduction relation for expressions with a mixture of application styles.

To complete the discussion we note that our earlier work \cite{SemSym} proposed the combination of the {\em normal-order} strategy of the Lazy-\LC\ \cite{Abr88} and an {\em eager} strategy. The first has just $APPL$ and the general $BETA$ rule:
\begin{center}
\begin{tabular}{lccl}
$APPL: \:\: {\infer{e \:{\rightarrow}\: e''}
       {e\;e' \:{\rightarrow}\: e''\;e'}
       { }}$
& &
$BETA: \:\: (\lambda x.e)\;e' \:{\rightarrow}\: e\,[e'/x]$
\end{tabular}
\end{center}
The eager strategy adds $APPR$:
\begin{center}
\begin{tabular}{lcccl}
$APPL: \:\: {\infer{e \:{\rightarrow}\: e''}
       {e\;e' \:{\rightarrow}\: e''\;e'}
       { }}$
& &
$APPR: \:\: {\infer{e' \:{\rightarrow}\: e''}
       {e\;e' \:{\rightarrow}\: e\;e''}
       { }}$
& &
$BETA: \:\: (\lambda x.e)\;e' \:{\rightarrow}\: e\,[e'/x]$
\end{tabular}
\end{center}
The normal-order strategy is sequential and, as is well known, is strongly normalising for terms with a \Whnf. The relation specified by the eager strategy contains the same normal forms, but it is a larger relation, allowing speculative evaluation of operands. There may be infinite reduction sequences even for terms with normal forms. We may combine these strategies using $@_n$ and $@_e$ for normal-order and eager application operators respectively; $APPR$ only applies when the application operator is $@_e$.

Many approaches to parallel implementation of functional programming languages can be seen as combinations of these strategies, with the addition of concurrent reduction which corresponds to use of consistent multi-step stategies. Call-by-value reduction mixed with normal-order reduction may change convergence properties and does not support pipelining. Mixing normal-order and eager evaluation retains convergence properties as long as the choice of reduction steps is fair. In either case if the reductions other than the normal-order step are {\em ``needed''}, convergence will be maintained. This corresponds to only varying the reduction strategy in the presence of strict arguments.

\section{A Simple Process Notation}

In this section we introduce a very simple and highly restrictive process model based on communication with named processes.
The model has adequate expressive power for our
purpose of translating a language such as \F, but might not seem attractive for general purpose use.

\subsection{Informal Description of the Process Model}

% Well, I'm not sure this is the right way to put it but:
The process model manipulates a world of terms forming a many-sorted algebraic structure:
\begin{itemize}
\item Terms are built up from primitive data values, including a domain of process names, and constructor symbols with fixed arities.
\item A process has a name and is associated with a term which holds all the process state.
\item Messages are terms which are directed to named processes.
\end{itemize}
Process names are almost pointers to terms, hence the representation of a process network is 
only a step away from a directed-graph representation. 

The following examples are taken from a more complete example later and illustrate the creation of a process with name $l$ whose name is known to the new process $k$. The initial state of $l$ is a term involving subterms $d$ and $i$ not shown here. A message containing a numeric value is sent to the process $k$.

\begin{eqnarray}
& & {\Pdef {l} {C(d,i)}}, \:\: {\Pdef {k} {F(l)}}, \:\: {\Pcall {k} {Unit(3)}}
\end{eqnarray}

The behaviour of processes is determined by pattern-directed rules which describe what happens when a message is received by a process:
\begin{itemize}
\item Patterns are left-linear open terms, hence they may contain variable names, but such names may not be repeated.
\item Matching of rules is based on two patterns. The sets of variable names in the two patterns are disjoint. Neither pattern may be a solitary 
variable, hence every pattern has at least a root symbol.
\item The first pattern of a rule matches the state of the process, the other matches
the incoming message. Pattern variables are bound to corresponding subterms during matching.
\item Every message sent to a process must match exactly one rule.
\item Actions are performed when a rule is matched, substituting values of bound variables in the normal way.
Rules contain no free variables.
\end{itemize}

The following example shows the rule which will be used by processes $k$ above:
\begin{eqnarray*}
\PruleSpawn {F(l)} {{Unit}(m)} {\Ppar {\Pdef {p} {E(l,m)}} {\Pcall {p} {{Unit}(4)}}}
\end{eqnarray*}

The condition that a process must handle every incoming message avoids the implication that an implementation might need to store 
messages and retry them later if the process state changes. An alternative semantics 
would be for unmatched messages to be discarded.
Also, the requirement that exactly one rule is matched avoids the need to
specify the semantics of overlapping rules. It is clear that 
pattern matching could be translated into nested matching operations revealing any potential non-determinism.

When a message is received:
\begin{itemize}
\item A process may create new terms.
\item A process may create new processes and has access to their names.
\item A process may send messages to processes it can name.
\item A process may copy the name of a process it can name. Hence it can send such names to other processes.
\item A process may change its own state. The process name subsequently refers to the new state.
\end{itemize}

Note that a process may not inspect the state of another process; it may only send it messages or pass on its name. Messages must be handled completely by their target process before
another message is considered. 

\subsection{Syntax and Informal Semantics of the Process Model}
In the proposed syntax, lower-case identifiers are bound variable names. Other identifiers are constructor symbols.
The most general form for a rule is a pair of patterns, followed by actions
to be performed if a process whose state matches the first pattern receives a message matching the second pattern:
\begin{eqnarray*}
\Prule {ProcState} {MsgPattern} {\Ppar {Action} {\Ppar {\cdots} {Action}}} {NewState}
\end{eqnarray*}
The actions are zero or more process creations,
zero or more message creations, and an optional revised state for the process.
The syntax $\Pcall {p} {Msg}$ denotes sending a message to a named process, 
while $\Pdef {p} {InitState}$ creates a process with an initial state, as illustrated above.

Processes might be better called actors or objects since they only act when messages are sent to them. When a message arrives at a process exactly one rule should match.
We have required that the message is handled completely by a process before
another message is considered. This is very conservative: if a process involves no state change there should be no need for such serialisation; if a process does involve a state change then once all new terms and processes referenced in the new state have been created, and the state has been changed, then other
messages could be handled.

Notionally, at least, the actions all occur simultaneously. However, in
practice there are some dependencies:
\begin{itemize}
\item Any new processes and terms are built.
\item The process state is changed if required.
\item Sending of any messages is initiated.
\end{itemize}
Clearly it would be meaningless for any messages sent as a result of invoking
a rule to be processed before processes and terms they reference have been created.

\subsection{An Example of the Process Model}

As an example we will address the hardest case which occurs in the translation of the source 
language given earlier.
This concerns communication which is the only language feature requiring synchronisation. 

The chosen representation of a \F\ channel is exactly like that in the \F\ \Cham\ of \cite{FacileCHAM}.
The state of a channel holds a queue of pending output offers and a queue of pending input requests.
At least one of the queues will be empty.

A channel receives input and output requests and either satisfies the request or queues it. Requests contain
continuations in the form of process names. Hence a receiver sends an $In(r)$ message with the identity of the process to handle the received message. Senders send $Out(v,s)$ where $v$ is the value to be output and $s$ a process to receive acknowledgement that the communication has succeeded.

Messages are sent to both sender and receiver when
a communication is closed.
\begin{eqnarray*}
\PruleChange {Chan(iq,NOQ)} {In(r)} {Chan(IQ(iq,r),NOQ)} \\
\PruleChange {Chan(NIQ,oq)} {Out(v,s)} {Chan(NIQ,OQ(oq,v,s)} \\
\Prule {Chan(iq,OQ(oq,v,s))} {In(r)} {\Ppar {\Pcall {r} {v}} {\Pcall {s} {Triv}}} {Chan(iq,oq)} \\
\Prule {Chan(IQ(iq,r),oq)} {Out(v,s)} {\Ppar {\Pcall {r} {v}} {\Pcall {s} {Triv}}} {Chan(iq,oq)}
\end{eqnarray*}
When a process representing a new channel is created, the initial state has both queues empty:
\begin{eqnarray*}
& {\Pdef {ch} {Chan(NIQ,NOQ)}} &
\end{eqnarray*}

It is synchronisation of concurrent computations which requires state changes. None of the rules generated for the \Lc\ part of \F\ needs to involve a change in process state.

\section{A Translation Scheme for \F}

The translation is 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. 

\subsection{Translation of the Source Language}
The translation of a syntactic construct creates some actions which will
form part of the body of a rule, and may also introduce new constructor
symbols and associated rules:
\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(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(u,fv(e'))} {Unit(y)} {\Ppar {\Pdef {b} {B(u,y)}} {\transexp{e'}{b}} } \\
\transand {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(u,fv(e'))} {Unit(y)} {\Ppar {\Pdef {b} {B(u,y)}} {\transexp{e'}{b}} } \\
\transand {B(u,y)} {Unit(z)} {\Pcall {u} {Doub(y,z)} }
\end{eqnarray*}
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 translation of the various constant functions for arithmetic and the operators of \F\ is as follows:
\begin{eqnarray*}
\transdef {succ}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Succ}} } \\
\transwhere {Succ} {Doub(b,x)} {\Pcall {b} {Unit(x+1)}} \\
\transdef {mul}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Mul}} } \\
\transwhere {Mul} {Doub(b,Pair(x,y))} {\Pcall {b} {Unit(x*y)}} \\
\transdef {channel}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Channel}} } \\
\transwhere {Channel} {Doub(b,Triv)} {\Ppar {\Pcall {b} {Unit(c)}} {\Pdef {c} {Chan(NIQ,NOQ)}} }\\
\transdef {send}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Send}} } \\
\transwhere {Send} {Doub(b,Pair(c,v))} {\Pcall {c} {Out(v,s)}} \\
\transdef {receive}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Receive}} } \\
\transwhere {Receive} {Doub(b,c)} {\Pcall {c} {In(b)}} \\
\transdef {spawn}{u} {\Ppar {\Pcall {u} {Unit(f)}} {\Pdef {f} {Spawn}} } \\
\transwhere {Spawn} {Doub(b,p)} {\Ppar {\Pcall {b} {Unit(Triv)}} {{\Ppar {\Pcall {p} {Doub(Triv,s)}} {\Pdef {s} {Sink}} } } }\\
\transand {Sink} {Unit(Triv)} {}
\end{eqnarray*}
The rules for $Chan$ were given earlier.

It should be noted that the types are not really correct here; a typed source language is required, as before. However,
the constructors used correctly reflect the arities of the terms.

\subsection{An Example of a Translated Expression}

The following is the translation of the expression $(Mul(3,4),())$ under the new scheme:
\begin{eqnarray*}
\PruleSpawn {{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 {A(a,e)} {{Unit}(f)} {\Ppar {\Pdef {g} {{PairB}}} {\Pcall {g} {{Trip}(a,e,f)}}} \\
\PruleSpawn {B(a)} {{Unit}(e)} {\Ppar {\Pdef {h} {A(a,e)}} {\Pcall {h} {{Unit}({Triv})}}} \\
\PruleSpawn {C(d,i)} {{Unit}(j)} {\Pcall {i} {{Doub}(d,j)}} \\
\PruleSpawn {D(d)} {{Unit}(i)} {\Ppar {\Pdef {l} {C(d,i)}} {\Ppar {\Pdef {k} {F(l)}} {\Pcall {k} {{Unit}(3)}}}} \\
\PruleSpawn {E(l,m)} {{Unit}(n)} {\Ppar {\Pdef {o} {{PairB}}} {\Pcall {o} {{Trip}(l,m,n)}}} \\
\PruleSpawn {F(l)} {{Unit}(m)} {\Ppar {\Pdef {p} {E(l,m)}} {\Pcall {p} {{Unit}(4)}}} \\
\PruleSpawn {Mul} {Doub(b,Pair(x,y))} {\Pcall {b} {Unit(x*y)}} \\
\PruleSpawn {PairB} {Trip(u,x,y)} {\Pcall {u} {Unit(Pair(x,y))}}
\end{eqnarray*}

We illustrate the first few steps of the elaboration of a program which starts with an initial process with state $Start$ being sent the message $Triv$:
\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}
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$.

\section{Implementation of the Process Model by Graph Rewriting}

An implementation of the process model, and hence of \F\ programs translated into the model, can be made using graph rewriting techniques.

The model is based on very similar principles to Paragon \cite{Paragon}. Indeed we could have used a subset of the syntax of Paragon, although our model is much simpler overall. 

It is also possible to map the process model to a graph rewriting system in the extended graph rewriting language Dactl \cite{Dactl}. An system has been written in SML which translates source programs into an internal form of the process notation, and also generates an executable Dactl program. The examples in this paper are taken straight from the output of the system.

%How do I get _ after Call? verbatim manages below.
Creation of a process maps to creation of a named graph term. Sending a message to a process involves creating an active graph term with the symbol {\tt Call} and subterms representing the destination process and the message to be sent. Apart from a small number of utility rules, all the rules are for the symbol {\tt Call}.

The rules for communication, using the symbol {\tt Chan}, are the only ones involving a change of state. These rules, in the utility module $AProcs$, overwrite the contents of the destination process state.

Below is the module for the Dactl translation of the earlier example, followed by the utility module used by all programs, with apologies to those unfamiliar with the language.

\begin{verbatim}
MODULE Facile;
IMPORTS AProcs;

SYMBOL OVERWRITABLE  Start_; A; B; C; D; E; F;

RULE
  INITIAL -> *Call_[Start_ Triv_];
  Call_[ h_:Start_ Triv_ ] ->
              d:B[a], c:D[d], *Call_[c Unit_[b]], b:Mul_, a:Print_;

  Call_[ h_:A[a e] Unit_[f] ] -> g:PairB_, *Call_[g Trip_[a e f]];
  Call_[ h_:B[a] Unit_[e] ] -> h:A[a e], *Call_[h Unit_[Triv_]];
  Call_[ h_:C[d i] Unit_[j] ] -> *Call_[i Doub_[d j]];
  Call_[ h_:D[d] Unit_[i] ] -> l:C[d i], k:F[l], *Call_[k Unit_[3]];
  Call_[ h_:E[l m] Unit_[n] ] -> o:PairB_, *Call_[o Trip_[l m n]];
  Call_[ h_:F[l] Unit_[m] ] -> p:E[l m], *Call_[p Unit_[4]];
ENDMODULE Facile;


MODULE AProcs;
IMPORTS OS_Core; Arithmetic;

SYMBOL CREATABLE PUBLIC CREATABLE Triv_; Unit_; Doub_; Trip_; Print_;
SYMBOL CREATABLE PUBLIC CREATABLE Channel_; Send_; Receive_; Spawn_;
SYMBOL CREATABLE PUBLIC CREATABLE Pair_; Succ_; Add_; Sub_; Mul_; Div_;
SYMBOL CREATABLE PUBLIC CREATABLE PairB_; AddB_; SubB_; MulB_; DivB_;
PATTERN PUBLIC SuccB_ = Succ_;

SYMBOL REWRITABLE PUBLIC REWRITABLE Call_;
SYMBOL REWRITABLE Print; Sink;
SYMBOL OVERWRITABLE Chan;
SYMBOL CREATABLE NIQ; IQ; NOQ; OQ; In; Out; Terminate;

RULE
  Call_[ PairB_ Trip_[u x y] ] -> *Call_[ u Unit_[Pair_[x y]] ];

  Call_[ c: Chan[iq:NIQ oq] Out[v s] ] -> c := Chan[iq OQ[oq v s]];
  Call_[ c: Chan[IQ[iq r] oq] Out[v s] ] ->
              *Call_[r Unit_[v]], *Call_[s Unit_[Triv_]], c := Chan[ iq oq ];
  Call_[ c: Chan[iq oq:NOQ] In[r] ] -> c := Chan[ IQ[iq r] oq ];
  Call_[ c: Chan[iq OQ[oq v s]] In[r] ] ->
              *Call_[r Unit_[v]], *Call_[s Unit_[Triv_]], c := Chan[ iq oq ];

  Call_[ Channel_ Doub_[u Triv_] ] -> *Call_[ u Unit_[Chan[NIQ NOQ]] ];
  Call_[ Send_ Doub_[s Pair_[c v]] ] -> *Call_[ c Out[v s] ];
  Call_[ Receive_ Doub_[r c] ] -> *Call_[c In[r]];
  Call_[ Spawn_ Doub_[u p] ] ->
              *Call_[u Unit_[Triv_]], s: Sink, *Call_[p Doub_[Triv_ s]];
  Call_[ Sink Unit_[Triv_] ] -> *Terminate;

  Call_[ Succ_ Doub_[u n] ] -> #Call_[ u ^#Unit_[^*IAdd[n 1]] ];
  Call_[ Add_ Doub_[u Pair_[x y]] ] -> #Call_[ u ^#Unit_[^*IAdd[x y]] ];
  Call_[ Sub_ Doub_[u Pair_[x y]] ] -> #Call_[ u ^#Unit_[^*ISub[x y]] ];
  Call_[ Mul_ Doub_[u Pair_[x y]] ] -> #Call_[ u ^#Unit_[^*IMul[x y]] ];
  Call_[ Div_ Doub_[u Pair_[x y]] ] -> #Call_[ u ^#Unit_[^*IDiv[x y]] ];

  Call_[ AddB_ Trip_[u x y] ] -> #Call_[ u ^#Unit_[^*IAdd[x y]] ];
  Call_[ SubB_ Trip_[u x y] ] -> #Call_[ u ^#Unit_[^*ISub[x y]] ];
  Call_[ MulB_ Trip_[u x y] ] -> #Call_[ u ^#Unit_[^*IMul[x y]] ];
  Call_[ DivB_ Trip_[u x y] ] -> #Call_[ u ^#Unit_[^*IDiv[x y]] ];

  Call_[ Print_ Unit_[v] ] -> *SEQ[PrintF["Result: "] Print[v]];
  Print[Pair_[l r]] =>
              *SEQ[PrintF["("] Print[l] PrintF[","] Print[r] PrintF[")"]];
  Print[Triv_] => *PrintF["()"];
  Print[n:INT] => *PrintF["%d" n];
ENDMODULE AProcs;
\end{verbatim}

\section{Direct Implementation of the Process Model}

The next stage of the work aims to produce an efficient sequential implementation of
a functional language with the features of \F\ using this model. Later work will address parallel
implementation as well.

\subsection{Optimisation}

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.

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

\subsection{Processing Messages}

The rules are like very primitive methods in an object-oriented model.
Hence the processing of a message is like a procedure call. The
pattern of process state term and the message determines what code is executed.
All the state of a process is in its term representation. There is no
environment to worry about.

If the actions of a rule generate no messages, a thread of control
terminates. See the first two rules for $Chan$ and the rule $Sink$.

If the actions of a rule generate one message, a sequential thread
continues. The new message can be prepared and control may jump to the
code indicated by the symbol of the target process.

If the actions of a rule generate multiple messages, additional threads
of control are required. This applies to the last two rules for $Chan$ and code for
$spawn$. A stack-based implementation on a single processor would have
the effect of remembering the work to be done, and returning to it when
the current thread completes (possibly because an attempted
communication blocks). The advantage is that no record of the thread
needs to be placed on some form of run queue. With a parallel
machine, the problem is that this potential work is not available for
evaluation on other processors.

There is no need to use a stack at all if messages representing new
threads are created as heap objects and linked into a rudimentary run
queue. The number of actions generating multiple messages is expected to be a
small proportion of all messages, so the cost of creating these very
simple thread descriptors may be acceptable even on a sequential machine.

\section{Conclusions}

The ideas presented here represent work which is still very much in progress, although early indications are that for straightforward functional code it will be possible to produce an implementation comparable with existing high-quality compilers.

The benefit of the technique should be that there will be little penalty for using the process facilities of a language like \F. By comparison, with existing implementations of the language, process spawning is only beneficial if large grains of computation are available.

The implementation model used appears to match well with recent techniques for programming multiprocessors \cite{AM}. Hence there is the promise of an effective parallel implementation in future.

\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, Addison 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 Grammars, 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}, 
Proc PARLE'92. LNCS 605. June 1992. (1992) 

\end{thebibliography}

\end{document}