Join-pattern


Join-patterns provides a way to write concurrent, parallel and distributed computer programs by message passing. Compared to the use of threads and locks, this is a high level programming model using communication constructs model to abstract the complexity of concurrent environment and to allow scalability. Its focus is on the execution of a chord between messages atomically consumed from a group of channels.
This template is based on join-calculus and uses pattern matching. Concretely, this is done by allowing the join definition of several functions and/or channels by matching concurrent call and messages patterns. It is a type of concurrency pattern because it makes easier and more flexible for these entities to communicate and deal with the multi-threaded programming paradigm.

Description

The join-pattern is like a super pipeline with synchronisation and matching. In fact, this concept is summarise by match and join a set of message available from different message queues, then handles them all simultaneously with one handler. It could be represented by the keywords to specify the first communication that we expected, with the to join/pair other channels and the to run some tasks with the different collected messages. A constructed join pattern typically takes this form:

j.When.And.....And.Do

Argument of may be a synchronous or asynchronous channel or an array of asynchronous channels. Each subsequent argument to must be an asynchronous channel.
More precisely, when a message matches with a chain of linked patterns causes its handler to run otherwise the message is queued until one of its patterns is enabled; if there are several matches, an unspecified pattern is selected. Unlike an event handler, which services one of several alternative events at a time, in conjunction with all other handlers on that event, a join pattern waits for a conjunction of channels and competes for execution with any other enabled pattern.
Join-pattern is defined by a set of pi-calculus channels that supports two different operations, sending and receiving, we need two join calculus names to implement it: a channel name for sending, and a function name for receiving a value. The meaning of the join definition is that a call to returns a value that was sent on a channel. Each time functions are concurrently, triggers the return process and synchronizes with other joins.

J ::= //join patterns

In most of cases, the order of synchronous calls is not guaranteed for performance reasons. Finally, during the match the messages available in the queue could be stolen by some intervening thread; indeed, the awakened thread may have to wait again.

History

π-calculus - 1992

The π-calculus belongs to the family of process calculi, allows mathematical formalisms for describing and analyzing properties of concurrent computation by using channel names to be communicated along the channels themselves, and in this way it is able to describe concurrent computations whose network configuration may change during the computation.

Join-Calculus - 1993

Join patterns first appeared in Fournet and Gonthier’s foundational join calculus, an asynchronous process algebra designed for efficient implementation in a distributed setting. The join-calculus is a process calculus as expressive as the full π-calculus. It was developed to provide a formal basis for the design of distributed programming languages, and therefore intentionally avoids communications constructs found in other process calculi, such as rendezvous communications.

Distributed Join-Calculus - 1996

The Join-Calculus is both a name passing calculus and a core language for concurrent and distributed programming. That's why the Distributed Join-Calculus based on the Join-Calculus with the distributed programming was created on 1996. This work use the mobile agents where agents are not only programs but core images of running processes with their communication capabilities.

JoCaml, Funnel and Join Java - 2000

and Funnel are functional languages supporting declarative join patterns. They present the ideas to direct implement a process calculi in a functional setting.
Another extensions to Java, JoinJava, were independently proposed by von Itzstein and Kearney.

Polyphonic C# - 2002

Cardelli, Benton and Fournet proposed an object-oriented version of join patterns for C# called Polyphonic C#.

Cω - 2003

Cω is adaptation of join-calculus to an object-oriented setting. This variant of Polyphonic C# was included in the public release of Cω in 2004.

Scala Joins - 2007

is a library to use Join-Pattern with Scala in the context of extensible pattern matching in order to integrate joins into an existing actor-based concurrency framework.

JErlang - 2009

is a language which natively supports the concurrent, real time and distributed paradigm. Concurrency between processes was complex, that's why the project build a new language, using based on the Join-calculus.

Join-pattern in classic programming literature

"Join-patterns can be used to easily encode related concurrency idioms like actors and active objects."

class SymmetricBarrier


var j = Join.Create;
Synchronous.Channel hungry;
Asynchronous.Channel chopstick;
j.Init; j.Init;
for


class Lock


class Buffer


class ReaderWriterLock


class Semaphore

Fundamental features and concepts

Mobile agent

A mobile agent is an autonomous software agent with a certain social ability and most importantly, mobility. It is composed of computer software and data which can move between different computers automatically while continuing their executions.
The mobile agents can be used to match concurrency and distribution if one uses the Join-calculus. That's why a new concept named "distributed Join-calculus" was created; it's an extension of Join-calculus with locations and primitives to describe the mobility.
This innovation use agents as running processes with their communication capabilities to allow an idea of location, which is a physical site expressing the actual position of the agent. Thanks to the Join-calculus, one location can be moved atomically to another site.
The processes of an agent is specified as a set which define its functionality including asynchronous emission of a message, migration to other location. Consequently, locations are organized in a tree to represent the movement of the agent easier. With this representation, a benefit of this solution is the possibility to create a simple model of failure. Usually a crash of a physical site causes the permanent failure of all its locations. But with the join-calculus a problem with a location can be detected at any other running location, allowing error recovery.
In 2007, an extension of the basic join calculus with methods which make agents proactive has come out. The agents can observe an environment shared between them. With this environment, it is possible to define shared variables with all agents.

Compilation

Join-languages are built on top of the join-calculus taken as a core language. So all the calculus are analysed with asynchronous processes and the join pattern provides a model to synchronize the result.
To do this, it exists two Compilers :
This two compiler works with the same system, an automaton.

let A | B = P
and A | C = Q
;;

It represents the consumption of message arrive at a completed join model. Each state is a possibly step for the code execution and each transitions is the reception of a message to change between two steps. And so when all messages are grab, the compiler execute the body join code corresponding to the completed model joint.
So in the join-calculus, the basic values are the names like on the example is A,B or C. So the two compiler representing this values with two ways.
Join compiler use a vector with Two slots, the first to the name it-self and the second to a queue of pending messages.
Jocaml use name like a pointer on definitions. This definitions store the others pointer of the others names with a status field and a matching date structure by message.
The fundamental difference is when the guard process is executed, for the first, it was verify if all names are the pending messages ready whereas the second use only one variable and access at the others to know if the model is completed.
Recent research describe the compilation scheme as the combination of two basic steps: dispatching and forwarding. The design and correctness of the dispatcher essentially stems from pattern matching theory, while inserting an internal forwarding step in communications is a natural idea, which intuitively does not change process behavior. They made the observation that the worth observing is a direct implementation of extended join-pattern matching at the runtime level would significantly complicate the management of message queues, which would then need to be scanned in search of matching messages before consuming them.

Implementations and libraries

There are many uses of the Join-patterns with different languages. Some languages use join-patterns as a base of theirs implementations, for example the Polyphonic C# or but others languages integrate join-pattern by a librairy like Scala Joins for Scala or the Joins library for VB. Moreover, the join-pattern is used through some languages like Scheme to upgrade the join-pattern.

JErlangCBJoins LibraryPolyphonic C#Parallel C#CωScala JoinsF#SchemeJoin JavaHumeJoCaml
Patterns matching
Scheduler between join-patterns : first match : first/round robin : random : first/round robin : random
Generics
Overriding

Join Java

is a language based on the Java programming language allowing the use of the join calculus. It introduces three new language constructs:
Example:

class JoinExample

Example:

class ThreadExample

Join fragments can be repeated in multiple Join patterns so there can be a case when multiple Join patterns are completed when a fragment is called. Such a case could occur in the example below if B, C and D then A are called. The final A fragment completes three of the patterns so there are three possible methods that may be called. The ordered class modifier is used here to determine which Join method will be called. The default and when using the unordered class modifier is to pick one of the methods at random. With the ordered modifier the methods are prioritised according to the order they are declared.
Example:

class ordered SimpleJoinPattern

The closest related language is the Polyphonic C#.

JErlang

In Erlang coding synchronisation between multiple processes is not straightforward. That's why the
JErlang, an extension of Erlang was created, The J is for Join. Indeed, To overcome this limitation JErlang was implemented, a Join-Calculus inspired extension to Erlang.
The features of this language are:

operation ->
receive
and and ->
;
and and ->
;
and and ->
;
end
end


receive
and
when ->
commit_transaction
end


receive
and ->

end
...
receive
and and ->
perform_transaction
end


receive
prop and ->
perform_action;
and ->
logout_user
end
...
receive
and and ->
perform_transaction
end


receive
and
and ->
Pid1 !,
Pid2 !
end

C++

Yigong Liu has written some including all useful tools like asynchronous and synchronous channels, chords, etc. It's integrated in the project .

template
class buffer: public joint ;

This example shows us a thread safe buffer and message queue with the basic operations put and get.

C#

Polyphonic C#

is an extension of the C# programming language. It introduces a new concurrency model with synchronous and asynchronous methods and chords.

public class Buffer

This is a simple buffer example.

MC#

language is an adaptation of the Polyphonic C# language for the case of concurrent distributed computations.

public handler Get2 long & channel c1
& channel c2

This example demonstrates the using of chords as a synchronization tool.

Parallel C#

is based Polyphonic C# and they add some new concepts like movables methods, high-order functions.

using System;
class Test13

This example demonstrates how to use joins.

Cω

adds new language features to support concurrent programming. The Joins Concurrency Library for C# and other.NET languages is derived of this project.

Scalable Join Patterns

It's an easy to use declarative and scalable join-pattern library. In opposite to the Russo library, it has no global lock. In fact, it's working with a compare-and-swap CAS and Atomic message system. The library use three improvements for the join-pattern :
is the first language where the join-pattern was implemented. Indeed, at the beginning all the different implementation was compiled with the JoCaml Compiler.
is an extension of the OCaml language. It extends OCaml with support for concurrency and synchronization, the distributed execution of programs, and the dynamic relocation of active program fragments during execution

type coins = Nickel | Dime
and drinks = Coffee | Tea
and buttons = BCoffee | BTea | BCancel;;
* "&" in the right hand side means: parallel process
* synchronous_reply : "reply" "to" channel_name
* synchronous channels have function-like types
* asynchronous channels have types
* only the last statement in a pattern rhs expression can be an asynchronous message
* 0 in an asynchronous message position means STOP.
*)
def put = print_endline s ; 0
;;
def serve = match drink with
Coffee -> put
| Tea -> put
;;
def refund = let s = Printf.sprintf "Refund %d" v in put
;;
let new_vending serve refund =
let vend = if credit >= cost
then
else
in
def coin & value = value & reply to coin
or coin & value = value & reply to coin
or button & value =
let should_serve, remainder = vend 10 v in
else 0 )
& value & reply to button
or button & value =
let should_serve, remainder = vend 5 v in
else 0 )
& value & reply to button
or button & value = refund & value & reply to button
in spawn value ;
coin, button
;; *
let ccoin, cbutton = new_vending serve refund in
ccoin; ccoin; ccoin;
Unix.sleep; cbutton;
Unix.sleep; cbutton;
Unix.sleep; cbutton;
Unix.sleep
;;

gives
Coffee
Tea
Refund 5

Hume

is a strict, strongly typed functional language for limited resources platforms, with concurrency based on asynchronous message passing, dataflow programming, and a Haskell like syntax.
Hume does not provide synchronous messaging.
It wraps a join-pattern set with a channel in common as a box, listing all channels in an in tuple and specifying all possible outputs in an out tuple.
Every join-pattern in the set must conform to the box input tuple type specifying a '*' for non required channels, giving an expression whose type conform to the output tuple, marking '*' the non fed outputs.
A wire clause specifies
  1. a tuple of corresponding input origins or sources and optionally start values
  2. a tuple of output destinations, being channels or sinks.
A box can specify exception handlers with expressions conforming to the output tuple.

data Coins = Nickel | Dime;
data Drinks = Coffee | Tea;
data Buttons = BCoffee | BTea | BCancel;
type Int = int 32 ;
type String = string ;
show u = u as string ;
box coffee
in -- input channels
out -- named outputs
match
-- * wildcards for unfilled outputs, and unconsumed inputs
->
in
vend drink cost credit = if credit >= cost
then
else ;
serve drink = case drink of
Coffee -> "Cofee\n"
Tea -> "Tea\n"
box control
in
out
match
'n' ->
| 'd' ->
| 'c' ->
| 't' ->
| 'x' ->
| _ ->
stream console_outp to "std_out" ;
stream console_inp from "std_in" ;
-- dataflow wiring
wire cofee
-- inputs

-- outputs destinations

wire control


Visual Basic

Concurrent Basic - CB

An extension of Visual Basic 9.0 with asynchronous concurrency constructs, called Concurrent Basic, offer the join patterns. CB adopts a simple event-like syntax familiar to VB programmers, allows one to declare generic concurrency abstractions and provides more natural support for inheritance, enabling a subclass to augment the set of patterns. CB class can declare method to execute when communication has occurred on a particular set of local channels asynchronous and synchronous, forming a join pattern.

Module Buffer
Public Asynchronous Put
Public Synchronous Take As String
Private Function CaseTakeAndPut As String _
When Take, Put
Return s
End Function
End Module

This example shows all new keywords used by Concurrent Basic: Asynchronous, Synchronous and When.

Joins library (C# and VB)

This library is a high-level abstractions of the Join Pattern using objects and generics. Channels are special delegate values from some common Join object.

class Buffer

This example shows how to use methods of the Join object.

Scala

There is a library in Scala called "Scala Joins" to use the Join-Pattern, it proposes to use pattern matching Pattern Matching as a tool for creating models of joins. You can find examples of the use of the join pattern in scala here: .
The pattern matching facilities of this language have been generalized to allow representation independence for objects used in pattern matching. So now it's possible to use a new type of abstraction in libraries. The advantage of join patterns is that they allow a declarative specification of the synchronization between different threads. Often, the join patterns corresponds closely to a finite state machine that specifies the valid states of the object.
In Scala, it's possible to solve many problem with the pattern matching and Scala Joins, for example the Reader-Writer.

class ReaderWriterLock extends Joins

With a class we declare events in regular fields. So, it's possible to use the Join construct to enable a pattern matching via a list of case declarations. That list is representing by => with on each side a part of the declaration. The left-side is a model of join pattern to show the combinaison of events asynchronous and synchronous and the right-side is the body of join which is executed with the join model is completed.
In Scala, it's also possible to use the Scala's actor library with the join pattern. For example, an unbounded buffer:

val Put = new Join1
val Get = new Join
class Buffer extends JoinActor

Actor-based concurrency is supported by means of a library and we provide join patterns as a library extension as well, so there are the opportunity to combine join patterns with the event-driven concurrency model offered by actors. Like you see in the example, it's the same way to use join pattern with actors, it just do it a list of case declaration in the method receive to show when the model is completed.
Practically the same tools are available in F# to use join pattern
and are newer implementations of the Join Pattern, improving upon Dr. Philipp Haller's .

Haskell

is an implementation of the Join Pattern in Haskell.

Scheme

The Join Patterns allows a new programming type especially for the multi-core architectures available in many programming situations with a high-levels of abstraction. This is based on the Guards and Propagation. So an example of this innovation has been implemented in Scheme.
Guards is essential to guarantee that only data with a matching key is updated/retrieved. Propagation can cancel an item, reads its contents and puts backs an item into a store. Of course, the item is also in the store during the reading. The guards is expressed with shared variables. And so the novelty is that the join patern can contains now propagated and simplified parts. So in Scheme, the part before / is propagated and the part after / is removed.
The use of the Goal-Based is to divise the work in many tasks and joins all results at the end with the join pattern. A system named "MiniJoin" has implemented to use the intermediate result to solve the others tasks if it's possible. If is not possible it waits the solution of others tasks to solve itself.
So the concurrent join pattern application executed in parallel on a multi-core architecture doesn't guarantee that parallel execution lead to conflicts. To Guarantee this and a high degree of parallelism, a Software Transactional Memory within a highlytuned concurrent data structure based on atomic compare-and-swap is use. This allows to run many concurrents operations in parallel on multi-core architecture. Moreover, an atomic execution is used to prevent the "false conflict" between CAS and STM.

Other similar design patterns

Join Pattern is not the only pattern to perform multitasks but it's the only one that allow communication between resources, synchronization and join different processes.