Parallel Implementation through Object Graph Rewriting

J.R.W. Glauert jrwg@sys.uea.ac.uk

School of Information Systems University of East Anglia Norwich NR4 7TJ, UK

Abstract

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

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

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

1 Introduction and Background

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

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

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

In its pure form, Facile enhances the λ–calculus with primitives for process spawning and channelbased communication in the style of CCS [13]. Milner using the π–calculus [16] and its polyadic form [15] shows that a λ–expression may be translated to a process network in the polyadic π–calculus which simulates the λ–expression [14]. Similar work was done by Leth [11].

One approach is to use process notations that are close to the Polyadic π–Calculus [15] in which communication is channel-based. Translations such as those of Milner may be employed. Such work is reported in [5] and [4]. In these models the channels can be thought of as independent entities which act as brokers, arranging communications between processes. Similar ideas appear in [18].

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

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

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

2 OGRe: A Small Process Language

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

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

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

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

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

3 OGRe Semantics

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

3.1 OGRe Processes, Messages, and Rules

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

An execution configuration consists of a set of names processes and messages. Process states are

p : SumSq, p! T rip(r, x, y) → s : SqY (r, y), m : Mul, m! T rip(s, x, x), p : SumSq
q : SqY (r, y), q! IntVal(xx) → f : F in(r, xx), m : Mul, m! T rip(f, y, y), q : SqY (r, y)
s : F in(r, xx), s! IntVal(yy) → a : Add, a! T rip(r, IntVal(xx), IntVal(yy)), s : F in(r, xx)
m : Mul, m! T rip(r, IntVal(a), IntVal(b)) → t = PMul(a, b), r! IntVal(t), m : Mul
d : Add, d! T rip(r, IntVal(a), IntVal(b)) → t = PAdd(a, b), r! IntVal(t), d : Add

Figure 1: OGRe rules for an arithmetic expression

p : P rintInt, s : SumSq, s! T rip(p, IntVal(3), IntVal(4))

→ p : P rintInt, s : SumSq, t : SqY (p, IntVal(4)), q : Mul, q! T rip(t, IntVal(3), IntVal(3))
→ p : P rintInt, t : SqY (p, IntVal(4)), q : Mul, t! IntVal(9)
→ p : P rintInt, t : SqY (p, IntVal(4)), f : F in(p, 9), m : Mul, m! T rip(f, IntVal(4), IntVal(4))
→ p : P rintInt, f : F in(p, 9), m : Mul, f ! IntVal(16)
→ p : P rintInt, f : F in(p, 9), a : Add, a! T rip(p, IntVal(9), IntVal(16))
→ p : P rintInt, p! IntVal(25)

Figure 2: Evaluation of an arithmetic expression

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

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

3.2 OGRe Rewriting

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

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

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

4 OGRe Applications

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.

4.1 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 [6], 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.

p : Sub(d), p! L(x) → p : SubR(r, x)
p : Sub(d), p! R(y) → p : SubL(r, y)
p : SubR(R(d), x), p! R(y) → d! R(x − y), p : Done
p : SubR(L(d), x), p! R(y) → d! L(x − y), p : Done
p : SubL(R(d), y), p! L(x) → d! R(x − y), p : Done
p : SubL(L(d), y), p! L(x) → d! L(x − y), p : Done

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

Nodes which take a literal argument can be modelled by auxiliary nodes with suitable arguments as illustrated in Figure 3 which computes 3 − (6 ∗ 2) and sends the result to a function P rint. 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.

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

This example indicates the use of processes with state, and tagging of data value to identify a notional port in the receiving process. The example above contains no parallelism, but it is clear that in general there might be many token messages travelling between nodes, and hence many possible concurrent rewritings. The number of tokens will increase when a result is needed by several successors, and a duplication node is used. In Figure 4, we give the rule for duplications and an example of how it could be used to form the square of a number:

4.2 Modelling Communication Channels

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

The model in Figure 5 supports asynchronous communication since the producer receives no notification that data has been consumed. Unsatisfied messages are stacked, so there is no fairness about this particular model. Surplus data values form a stack, V Q, of available values, while surplus producer names form a stack, RQ, of requests. Observe the order in which requests are satisfied in the example execution in Figure 6. The initial state of the channel holds and empty queue, EQ. The two P ut actions stack values so the Get actions receive values in the reverse order.

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

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

p : P rint, m : SubR(L(p), 15), a : Mul(R(m)), a! L(6), a! R(2)

→ p : P rint, m : SubR(L(p), 15), a : MulR(R(m), 6), a! R(2)
→ p : P rint, m : SubR(L(p), 15), m! R(12), a : Done
→ p : P rint, p! R(3), m : Done, a : Done

Figure 3: Evaluation of a dataflow example

p : Dup(L(d), L(e)), p! L(x) → d! L(x), e! L(x), p : Done
p : Dup(L(d), R(e)), p! L(x) → d! L(x), e! R(x), p : Done
p : Dup(R(d), L(e)), p! L(x) → d! R(x), e! L(x), p : Done
p : Dup(R(d), R(e)), p! L(x) → d! R(x), e! R(x), p : Done

p : P rint, m : Mul(L(p)), d : Dup(L(m), R(m)), d! L(6)

Figure 4: Duplication of dataflow tokens

the process to receive synchronisation when a data value is sent. Further computation by the producer can be blocked until the communication is completed as shown in Figure 7. Note how an unsatisfied request blocks a thread of control as the channel process changes state but does not generate further activity. When a communication completes, a new thread is activated as indicated by the two messages generated, one of which resumes the suspended thread of control.

4.3 Modelling State and Logic Variables

The channel model above uses a process to hold the state of the channel as a list of data values or requests. A simple von Neumann storage cell can be implemented with Set and Read operations. The Set is acknowledged in order to provide serialisation. We return the old contents to allow a test-and-set functionality:

c : Cell(v), c! Set(n, r) → r! Data(v), c : Cell(n)
c : Cell(v), c! Read(r) → r! Data(v), c : Cell(v)

By adding slightly more sophisticated behaviour, we can model a logic variable in the framework of concurrent logic programming [17]. The model suggested in Figure 8 is for illustration only, as the properties of such variable vary from language to language. We will assume that an attempt may be made to Bind an unbound variable, UV ar. This will fail if the variable is already bound. A variable may be Read, which will lead to blocking of the computation if the variable is unbound. There is also an IsV ar test for examining the state of the variable. An unbound variable holds a list of suspended readers. The initial state of an unbound variable is UV ar(E). The rules for F ree are used to release suspended readers. In order to process the rest of the list, the process sends a further message to itself.

4.4 Modelling Facile

The main application of OGRe has been in the implementation of Facile. The OGRe model results in a very low-level translation of Facile features in which potential implementation data-structures become visible. For example, Facile channels can be represented as objects which are manipulated in exactly the same way as in the Chemical Abstract Machine [2] proposed for Facile in [12]. This channel representation is closely related to the synchronous channel model in Section 4.2.

For the purpose of investigation we present a very small language in which we can represent all the features of core Facile, along with facilities for handling constants and operators as in ML. This language is the λ–calculus with constants and pairing. The trivial value and pairing operator could have been considered as normal constants.

e ::= x | λx. e | e e | c | () | (e, e)

c stands for a constant and x for a variable.

c : Chan(V Q(v, q)), c! Get(r) → r! Data(v), c : Chan(q)
c : Chan(q), c! Get(r) → c : Chan(RQ(r, q))
c : Chan(RQ(r, q)), c! P ut(v) → r! Data(v), c : Chan(q)
c : Chan(q), c! P ut(v) → c : Chan(DQ(v, q))

Figure 5: Rules for Asynchronous Communication

c : Chan(EQ), c!P ut(3), c!P ut(4), c!Get(x), c!Get(y), c!Get(z)

→ c : Chan(V Q(3, EQ)), c!P ut(4), c!Get(x), c!Get(y), c!Get(z)
→ c : Chan(V Q(4, V Q(3, EQ))), c!Get(x), c!Get(y), c!Get(z)
→ c : Chan(V Q(3, EQ)), c!Get(y), c!Get(z), x!Data(4)
→ c : Chan(EQ), c!Get(z), x!Data(4), y!Data(3)
→ c : Chan(RQ(z, EQ)), x!Data(4), y!Data(3)

Figure 6: Asynchronous Communication

The features of Facile 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 [10, 8, 9]. 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/Facile code (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 (fn x => x?).

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

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

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

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

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

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

The translation of the constant functions for the various arithmetic and other operators of Facile is

c : Chan(V Q(v, s, q)), c! Get(r) → r! Data(v), s! Sync, c : Chan(q)
c : Chan(q), c! Get(r) → c : Chan(RQ(r, q))
c : Chan(RQ(r, q)), c! P ut(v, s) → r! Data(v), s! Sync, c : Chan(q)
c : Chan(q), c! P ut(v, s) → c : Chan(V Q(v, s, q))

Figure 7: Rules for Synchronous Communication

c : UV ar(q), c! Read(r) → c : UV ar(Q(r, q))
c : BV ar(v), c! Read(r) → r! Data(v), c : BV ar(v)
c : UV ar(q), c! Bind(d, r) → r! Succ, f : F ree(q, d), f ! Go, c : BV ar(d)
c : BV ar(v), c! Bind(d, r) → r! F ail, c : BV ar(v)
c : UV ar(q), c! IsV ar(r) → r! Succ, c : UV ar(q)
c : BV ar(v), c! IsV ar(r) → r! F ail, c : BV ar(v)
f : F ree(Q(r, q), d), f ! Go → f ! Go, r! Data(v), f : F ree(q, d)
f : F ree(E, d), f ! Go → f : Done

Figure 8: A model for logical variables in OGRe

given in Figure 10 below. The rules for Chan were given earlier. The arithmetic rules used before are slightly different to those used for Facile:

The translation of the expression (Mul(3, 4), ()) under this scheme appears in Figure 11.

In Figure 12 we illustrate the first few steps of the evaluation of a program which starts with an initial process with state Start being sent the message T riv: The values 3 and 4 are gathered together to form a pair by step (6). This pair is sent to the Mul process which sends on the product to the process given by the first argument to Doub.

Many of the rules in the automatically generated code create a process and immediately send it a message. Since most of the rules generated only match a single pattern each, it is possible to expand them out and build rules with larger numbers of actions. In Figure 13 we give the result of some simple optimizations applied to the example using knowledge of the pairing operation, but not arithmetic operations.

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

5 OGRe Implementation

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

5.1 OGRe on Sequential Machines

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

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

[[x]]_{u} = u! Unit(x)
[[c]]_{u} = u! Unit(c)
[[()]]_{u} = u! T riv
[[λx. e]]_{u} = u! Unit(y), y : Y (fv(λx. e))
where y : Y (fv(λx. e)), y! Doub(b, x) → y : Y (fv(λx. e)), [[e]]_{b}
[[e e′]]_{u} = [[e]]_{a}, a : A(u, fv(e′))

where a : A(u, fv(e′)), a! Unit(y) → a : A(u, fv(e′)), b : B(u, y), [[e′]]_{b}

and b : B(u, y), b! Unit(z) → b : B(u, y), y! Doub(u, z)
[[(e, e′)]]_{u} = [[e]]_{a}, a : A(u, fv(e′))

where a : A(u, fv(e′)), a! Unit(y) → a : A(u, fv(e′)), b : B(u, y), [[e′]]_{b}

and b : B(u, y), b! Unit(z) → b : B(u, y), u! Doub(y, z)

Figure 9: Translation Rules for Facile Constructs

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

5.2 OGRe on Shared or Distributed Memory Machines

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

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

6 Conclusions

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

References

[1] P. Anderson, D. Bolton & P. Kelly: Paragon Specifications: Structure, Analysis and Implementation, Proc PARLE’92. LNCS 605. June 1992. (1992)

[2] G. Berry & G. Boudol: The Chemical Abstract Machine, Proc. POPL 90, p 81-94. (1990)

[[succ]]_{u} = u! Unit(f), f : Succ

where s : Succ, s! Doub(b, x) → s : Succ, b! Unit(x + 1)

[[mul]]_{u} = u! Unit(f), f : Mul

where m : Mul, m! Doub(b, P air(x, y)) → m : Mul, b! Unit(x ∗ y)

[[channel]]_{u} = u! Unit(f), f : Channel

where c : Channel, c! Doub(b, T riv) → c : Channel, b! Unit(c), c : Chan(EQ)

[[send]]_{u} = u! Unit(f), f : Send

where s : Send, s! Doub(b, P air(c, v)) → s : Send, c! P ut(v, s)

[[receive]]_{u} = u! Unit(f), f : Receive

where r : Receive, r! Doub(b, c) → r : Receive, c! Get(b)

[[spawn]]_{u} = u! Unit(f), f : Spawn

where s : Spawn, s! Doub(b, p) → s : Spawn, b! Unit(T riv), p! Doub(T riv, s), s : Sink

and s : Sink, s! Unit(T riv) → s : Sink,

Figure 10: Translation Rules for Constant Functions

s : Start, s! T riv → d : B(a), c : D(d), c! Unit(b), b : Mul, a : P rint, s : Start
r : A(a, e), r! Unit(f) → g : P airB, g! T rip(a, e, f), r : A(a, e)
r : B(a), r! Unit(e) → h : A(a, e), h! Unit(T riv), r : B(a)
r : C(d, i), r! Unit(j) → i! Doub(d, j), r : C(d, i)
r : D(d), r! Unit(i) → l : C(d, i), k : F (l), k! Unit(3), r : D(d)
r : E(l, m), r! Unit(n) → o : P airB, o! T rip(l, m, n), r : E(l, m)
r : F (l), r! Unit(m) → p : E(l, m), p! Unit(4), r : F (l)
r : Mul, r! Doub(b, P air(x, y)) → b! Unit(x ∗ y), r : Mul
r : P airB, r! T rip(u, x, y) → u! Unit(P air(x, y)), r : P airB

Figure 11: Example: Translation of (Mul(3, 4), ())

[3] T. v Eicken, D.E. Culler, S.C. Goldstein & K.E. Schauser, Active Messages: a Mechanism for Integrated Communication and Computation, International Symposium on Computer Architecture ’92, ACM. (1992).

[4] J.R.W. Glauert: Asynchronous Mobile Processes and Graph Rewriting, Proc PARLE’92. LNCS 605. June 1992. pp. 63-78. (1992)

[5] J.R.W. Glauert, L. Leth & B. Thomsen: A New Translation of Functions as Processes, SemaGraph ’91 Symposium, December 1991. (1991)

[6] J.R. Gurd, C.C. Kirkham, & I. Watson: The Manchester Prototype Dataflow Computer, Comm. ACM, Vol. 28, No. 1, pp. 34-52, (1985).

[7] A. Giacalone, P. Mishra, & S. Prasad: Facile: A Symmetric Integration of Concurrent and Functional Programming, IJPP, Vol 18, No 2, p 121-160. (1989)

[8] A. Kramer & F. Cosquer: Distributing Facile, MAGIC Note 12, ECRC. October 1991. (1991)

[9] F. Knabe: A distributed protocol for the generalized select command, MAGIC Note 11, ECRC. July 1991. (1991)

[10] Kuo, T.-M.: Magic Facile version 0.3, MAGIC Note 22, ECRC. March 1992. (1992)

s : Start, s! T riv  (1)
→  a : P rint, d : B(a), b : Mul, c : D(d), c! Unit(b)  (2)
→  a : P rint, d : B(a), b : Mul, l : C(d, b), k : F (l), k! Unit(3)  (3)
→  a : P rint, d : B(a), b : Mul, l : C(d, b), p : E(l, 3), p! Unit(4)  (4)
→  a : P rint, d : B(a), b : Mul, l : C(d, b), o : P airB, o! T rip(l, 3, 4)  (5)
→  a : P rint, d : B(a), b : Mul, l : C(d, b), l! Unit(P air(3, 4))  (6)
→  a : P rint, d : B(a), b : Mul, b! Doub(d, P air(x, y))  (7)
→  a : P rint, d : B(a), d! Unit(12)  (8)

Figure 12: Elaboration of Example

s : Start, s! Triv → d : B(a), b : Mul, a : Print, b! Doub(d, Pair(3, 4)), s : Start
r : B(a), r! Unit(e) → a! Unit(Pair(e, Triv)), r : B(a)

Figure 13: Optimisation of the Example Code

[11] L. Leth: Functional Programs as Reconfigurable Networks of Communicating Processes, Ph.D. Thesis, ICSTM. (1991)

[12] L. Leth & B. Thomsen: Some Facile Chemistry, ECRC Technical Report ECRC-92-14. May 1992. (1992)

[13] R. Milner: A Calculus of Communicating Systems, Springer LNCS 92. (1980)

[14] R. Milner: Functions as Processes, Automata, Languages, and Programming. Springer LNCS 443. (1990) Also: Technical Report INRIA Sophia Antipolis, June 1989.

[15] R. Milner: The Polyadic π–Calculus: A Tutorial, Technical Report ECS-LFCS-91-180, Edinburgh University, October 1991. (1991)

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

[17] E.Y. Shapiro: The Family of Concurrent Logic Programming Languages, Computing Surveys, Vol. 21 (3), pp. 412-510. (1989)

[18] M.J. Wise: Message Brokers and Communicating Prolog Processes, Proc PARLE’92. LNCS 605. June 1992. pp. 535-549 (1992)