%%% Start of LaTeX Document %%%
\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{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}}
%\reportref{Draft}
\date{Submitted to PARLE'93}

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

{\em Keywords}: Parallel Programming Languages; Language Constructs; Implementation Issues

This paper is not for consideration for a poster session.
\end{abstract}

\newpage

\part*{Parallel Implementation of Functional Languages Using Small Processes}

\section{Introduction and Background}

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 \F\ language
\cite{Facile} enhances the \Lc\ with primitives for process spawning and
channel-based communication in the style of CCS \cite{CCS}. 

A study of implementation techniques for \F\ is in progress at ECRC. The 
approach taken 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.

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

However, in most cases the channels used in the translations mentioned above were
closely associated with a particular process. This process was the only one to
receive messages from the channel, and furthermore, the process would receive
messages from no other channel.

This led to the investigation of 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 sketch
a mapping from the new notation to the related 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}.

The work reported here has benefitted from a close collaboration with 
0.Lone Leth and Bent Thomsen.

\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 will be used to translate the \F\ language and has adequate expressive power for the purpose.

The model is not intended for
general purpose use, although it can be seen as providing a small and useful subset of the facilities of Paragon \cite{Paragon}.

\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. That is, 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 some 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.

In most of the examples we avoid overlapping patterns so that exactly one rule will match. 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 intuition behind the translation is that $u$ will be the name of a process to receive the computed value. In the case of constants, the value is sent to process $u$.

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

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

The translation of the 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$.

\subsection{Optimisation of Process Programs}

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.

The following is the result of some simple optimisations applied to the example using knowledge of the pairing operation, but not arithmetic operations:
\begin{eqnarray*}
\PruleSpawn {{\bf Start}} {{\bf Triv}} {\Ppar {\Pdef {d} {B(a)}} {\Ppar {\Pdef {b} {{\bf Mul}}} {\Ppar {\Pdef {a} {{\bf Print}}} {\Pcall {b} {{\bf Doub}(d,{\bf Pair}(3,4))}}}}} \\
\PruleSpawn {B(a)} {{\bf Unit}(e)} {\Pcall {a} {{\bf Unit}({\bf Pair}(e,{\bf Triv}))}}
\end{eqnarray*}

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

\section{Implementation of the Process Model}

A prototype implementation of the process model, and hence of \F\ programs translated
into the model, has been made using graph rewriting techniques.
A direct implementation is available, converting process programs to C. It is also possible to map the process model to a graph rewriting system in the
extended graph rewriting language Dactl.

A system has been written
in SML which translates source programs into an internal form of the process
notation, and also generates an executable C or Dactl program. The examples in this
paper are taken straight from the output of the system.

\subsection{Implementation via Dactl}
The language Dactl is described elsewhere and readers are directed to \cite{Dactl} for details. The translation illustrated below involves a close correspondence between process rules and Dactl rewriting rules.

%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 optimised version of the earlier example, followed
by key components of the utility module used by all programs.

\small{\begin{verbatim}
MODULE Facile;
IMPORTS AProcs;

SYMBOL OVERWRITABLE  Start_; B;

RULE
  INITIAL -> *Call_[Start_ Triv_];
  Call_[ h_:Start_ Triv_ ] ->
          d:B[a], b:Mul_, a:Print_, *Call_[b Doub_[d Pair_[3 4]]];
  Call_[ h_:B[a] Unit_[e] ] ->
          *Call_[a Unit_[Pair_[e Triv_]]];
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 PairB_; Pair_; Succ_; Add_; Sub_; Mul_; Div_;

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_[ 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}}

Execution of this Dactl code produces output:
\begin{verbatim}
     Result: (12,())
\end{verbatim}

An example involving communication is the source program:
\begin{verbatim}
     (\c. ( Spawn (\t.Send(c,4)),  (Receive c) )) (Channel())
\end{verbatim}

Which is converted to the process network:
\begin{eqnarray*}
\PruleSpawn {{\bf Start}} {{\bf Triv}} {\Ppar {\Pdef {b} {E}} {\Ppar {\Pdef {a} {{\bf Print}}} {\Ppar {\Pdef {h} {A(a,b)}} {\Ppar {\Pdef {f} {{\bf Channel}}} {\Pcall {f} {{\bf Doub}(h,{\bf Triv})}}}}}} \\
\PruleSpawn {A(a,d)} {{\bf Unit}(e)} {\Pcall {d} {{\bf Doub}(a,e)}} \\
\PruleSpawn {E} {{\bf Doub}(l,{\bf c})} {\Ppar {\Pdef {o} {G(l,{\bf c})}} {\Ppar {\Pdef {m} {{\bf Spawn}}} {\Ppar {\Pdef {aa} {L({\bf c})}} {\Pcall {m} {{\bf Doub}(o,aa)}}}}} \\
\PruleSpawn {F(l,p)} {{\bf Unit}(q)} {\Pcall {l} {{\bf Unit}({\bf Pair}(p,q))}} \\
\PruleSpawn {G(l,{\bf c})} {{\bf Unit}(p)} {\Ppar {\Pdef {u} {F(l,p)}} {\Ppar {\Pdef {s} {{\bf Receive}}} {\Pcall {s} {{\bf Doub}(u,{\bf c})}}}} \\
\PruleSpawn {L({\bf c})} {{\bf Doub}(ca,{\bf t})} {\Ppar {\Pdef {da} {{\bf Send}}} {\Pcall {da} {{\bf Doub}(ca,{\bf Pair}({\bf c},4))}}} \\
& & \\
\PruleSpawn {{\bf Channel}} {{\bf Doub}(b,{\bf Triv})} {\Ppar {\Pcall {b} {{\bf Unit}(c)}} {\Pdef {c}
{{\bf Chan}(NIQ,NOQ)}} }\\
\PruleSpawn {{\bf Send}} {{\bf Doub}(b,{\bf Pair}(c,v))} {\Pcall {c} {{\bf Out}(v,s)}} \\
\PruleSpawn {{\bf Receive}} {{\bf Doub}(b,c)} {\Pcall {c} {{\bf In}(b)}} \\
\PruleSpawn {{\bf Spawn}} {{\bf Doub}(b,p)} {\Ppar {\Pcall {b} {{\bf Unit}({\bf Triv})}} {{\Ppar {\Pcall {p} {{\bf Doub}({\bf Triv},s)}} {\Pdef {s} {{\bf Sink}}} } } }\\
\PruleSpawn {{\bf Sink}} {{\bf Unit}({\bf Triv})} {}
\end{eqnarray*}

The translation to Dactl produces output:
\begin{verbatim}
     Result: ((),4)
\end{verbatim}

The $Spawn$ call is necessary as $Send$ and $Receive$ are synchronous and strict left-to-right evaluation of the tuple could not proceed since the communication would block.

\section{Direct Implementation of the Process Model}

A prototype direct implementation of the model has been produced, generating C as the target language. 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{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 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 technique appears somewhat involved if the only target were to translate functional programs. However, the objective of the work is to implement languages which integrate the functional and process paradigms.

The benefit of the technique is 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 and Communicating Prolog Processes}, 
Proc PARLE'92. LNCS 605. June 1992. (1992) 

\end{thebibliography}

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