Join-pattern

The feature distinguishing JoinCalculus is its support for join patterns (or chords in CeeOmega, as in striking multiple keys upon a piano). Instead of receiving each message individually, a join pattern waits until a whole pattern-matched collections of messages are available in the MessageQueue, then handles them all simultaneously with one handler (potentially requiring replies to many different processes). ActorsModel behavior would be a specific case of JoinCalculus, in which one never requires more than one message to invoke a handler (see comparison to ActorsModel on that page).

It's a pattern base on :

• Behavioral patterns are used in communications between entities and make it easier and more flexible for these entities to communicate.
• Concurrency pattern patterns deal with the multi-threaded programming paradigm.

The three keywords used by Join-Patterns: Asynchronous, Synchronous and When.

http://www.parallelcsharp.com/files/tree.gif

Description

http://www.parallelcsharp.com/files/en.tetris.gif

Join patterns are a powerful concurrency abstraction to coordinate multiple events. <br\> Join patterns are a high-level concurrency construct to synchronize (coordinate) simultaneous events.<br\> The semantics of join definitions can be expressed as a multi-set rewrite system operation on a shared store.<br\> Join patterns as Bounded Transactions.<br\> a Join method call with only asynchrononous arguments is non-blocking.<br\> Join patterns are an attractive declarative way to synchronize both threads and asynchronous distributed computations.<br\> A method may be declared to execute when communication has occurred on a particular set of local channels, forming a join pattern. Communications are queued until or unless some method is enabled and run. More precisely, a message that enables some join pattern causes its method to run (on some other thread) otherwise the message is queued until one of its patterns is enabled; a request that enables some join pattern runs its method (on the same thread) otherwise the request blocks until one of its patterns is enabled. 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.

History

• π-calculus

The π-calculus allows 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. π-calculus

• Join-Calculus

The Join-calculus developed at INRIA Rocquencourt by Cédric Fournet et al. the join-calculus is as expressive as the full π-calculus. Encodings of the π-calculus in the join-calculus, and vice-versa, have been demonstrated. <br\> The Join Calculus provides the basis for a number of language extensions and libraries to support expressive concurrency abstraction in the form of join patterns. <br\> The Join Calculus is an asynchronous variant of Milner's Pi-calculus with better locality and better static scoping rules.<br\> The Join Calculus is both a name passing calculus and a core language for concurrent and distributed programming.<br\>

• Distributed Join-Calculus

Distributed Join-Calculus allows to express mobile agents moving between physical sites. Agents are not only programs but core images of running processes with their communication capabilities.

• ...

Implementations and libraries

	JErlang	Boost	Distributed Join-Calculus	Polyphonic C#	MC#	Parallel C#	Cω	Scala Joins	F#
design pattern	?	?	?	?	?	?	?	?	?
parallel programming	?	?	V	?	?	?	?	?	?
Mobile Agents	?	?	V	?	?	?	?	?	?

Join-pattern in classic programming literature

Partical example from the classic programming literature implemented with C♯ .

• Barriers

class SymmetricBarrier {
public readonly Synchronous.Channel Arrive;
public SymmetricBarrier(int n) {
    // create j and init channels (elided)
    var pat = j.When(Arrive);
    for (int i = 1; i < n; i++) pat = pat.And(Arrive);
    pat.Do(() => { });
}
}

• Dining philosophers problem

var j = Join.Create();
Synchronous.Channel[] hungry;
Asynchronous.Channel[] chopstick;
j.Init(out hungry, n); j.Init(out chopstick, n);
for (int i = 0; i < n; i++) {
    var left = chopstick[i];
    var right = chopstick[(i+1) % n];
    j.When(hungry[i]).And(left).And(right).Do(() => {
    eat(); left(); right(); // replace chopsticks
    });
}

• Mutual exclusion

class Lock {
public readonly Synchronous.Channel Acquire;
public readonly Asynchronous.Channel Release;
    public Lock() {
        // create j and init channels (elided)
        j.When(Acquire).And(Release).Do(() => { });
        Release(); // initially free
    }
}

• Producers/Consumers

class Buffer<T> {
public readonly Asynchronous.Channel<T> Put;
public readonly Synchronous<T>.Channel Get;
    public Buffer() {
        Join j = Join.Create(); // allocate a Join object
        j.Init(out Put);
        // bind its channels
        j.Init(out Get);
        j.When(Get).And(Put).Do // register chord
        (t => { return t; });
    }
}

• Reader-writer locking

class ReaderWriterLock {
private readonly Asynchronous.Channel idle;
private readonly Asynchronous.Channel<int> shared;
public readonly Synchronous.Channel AcqR, AcqW,
RelR, RelW;
public ReaderWriterLock() {
    // create j and init channels (elided)
    j.When(AcqR).And(idle).Do(() => shared(1));
    j.When(AcqR).And(shared).Do(n => shared(n+1));
    j.When(RelR).And(shared).Do(n => {
    if (n == 1) idle(); else shared(n-1);
    });
    j.When(AcqW).And(idle).Do(() => { });
    j.When(RelW).Do(() => idle());
    idle(); // initially free
}
}

• Rendezvous
• Semaphores

class Semaphore {
public readonly Synchronous.Channel Acquire;
public readonly Asynchronous.Channel Release;
    public Semaphore(int n) {
        // create j and init channels (elided)
        j.When(Acquire).And(Release).Do(() => { });
        for (; n > 0; n--) Release(); // initially n free
    }
}

Fundamental features and concepts

• message passing
• synchronous : returns a result
• asynchronous : returns no result
• design patterns
• concurent programming
• pattern matching
• parallel programming
• multi-core hardware
• distributed programming

Application domain

Mobile Agent

In computer science, a mobile agent is a composition of computer software and data which is able to migrate (move) from one computer to another autonomously and continue its execution on the destination computer. (extract of http://en.wikipedia.org/wiki/Mobile_agent )

• A Calculus of Mobile Agents

It's really hard to match concurrency and distribution. That's why the Distributed Join-Calculus was created to allow this. The Distributed Join-Calculus is a extension of Join-Calculus with explicit locations and primitives for mobility. It allows express mobile agents moving between physical sites. Agents are not only programs but core images of running processes with their communication capabilities. The novelty of the distributed join-calculus is the introduction of locations. A location resides on a physical site, and contains a group of processes. It's possible to move atomically a location to another site. The mobile agents is represented by locations. For these reasons, locations are organized in a tree. This calculus also provides a simple model of failure. The crash of a physical site causes the permanent failure of all its locations. More generally, any location can halt, with all its sublocations. The failure of a location can be detected at any other running location, allowing error recovery.

So the Join-calculus is the core of a distributed programming language. In particular, the operational semantics is easily implementable in a distributed setting with failures. So the distributed join-calculus treats channel names and location names as rst class values with lexical scopes. A location controls its own moves, and can only move towards a location whose name it has received. This provides a sound basis for static analysis and for secure mobility. This is complete for expressing distributed con gurations. In the absence of failure, however, the execution of processes is independent of distribution. This location transparency is essential for the design of mobiles agents, and very helpful for checking their properties.

New Type Programming

• Scalable Join Patterns

Join pattern in programming languages

The join-calculus programming language is based on the join-calculus process calculus. It is implemented as an interpreter written in OCaml, and supports statically typed distributed programming, transparent remote communication, agent-based mobility, and failure-detection.

Java

• Join Java
• fork-join (Java 7.0)

JErlang

The J is for Join, erjang is Erlang for the JVM.

• JErlang

C++

Boost

• Boost

c#

• Library The Russo's Library
• Joins concurrency library

Polyphonic C#

Polyphonic C# is an extension of the C# programming language.

• Polyphonic C#

MC#

MC# language is an adaptation of the basic idea of the Polyphonic C# language (more precisely, of the basic idea of the join calculus) for the case of concurrent distributed computations.

• MC#

Parallel C#

Parallel C# extend Polyphonic C#.

• Parallel C# NICOOOOOOOOOOOOOOOOOOOOOOO GRAPHIQUE ICIIIIIIIIIIIIIIIIIIIIIIII

Cω

• Cω
• Research Microsoft : Cω
• The Joins Concurrency library

Langage hérité du C# inventé par Microsoft Resarch (Claudio Russo). Cω = C# + Join Patterns <br\> C'est un langage neutre qui supporte d'autres langages comme le Visual Basic, il est plus dynamique, il est plus simple à modifier et il simple de transformer du Cω en C# <br\> On peut notamment souligner le fait qu'il facilite l'implémentation avec les Join Patterns comparé au C#. <br\> "Cω promised C# 1.x users a more pleasant world of concurrent programming" by Claudio Russo [1]

Scala

• Scala Joins Library
• Join definitions in Scala
• Implementing Joins Using Extensible Pattern Matching

JoCalm

• JoCalm language

Visual Basic

An extension of Visual Basic 9.0 with asyn-chronous concurrency constructs, called Concurrent Basic (for short CB), offer the join patterns. CB (builds on earlier work on Polyphonic C#, Cω and the Joins Library) 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.

F#

• Implementing Joins Using Extensible Pattern Matching

L'étude des jointures dans le contexte des "extensible pattern matching" présent en F# ou Scala. Mais aussi l'intégration des jointures dans les "actor-based concurrency framework". Il justifie le fait que les Join Patterns peuvent être utilisé dans le contexte de la synchronisation avancée comme un nouveau type d'envoie de message et d'envoie de jeton entre communiquant.

Explication des patterns matching : http://en.wikipedia.org/wiki/Pattern_matching

Scheme

• Parallel Join Patterns with Guards and Propagation : <br\>

Version test in English : <br\> The Join Patterns allows a new programming type especially for the multi-core architectures available in many programming situations. This is based on the Guards and Propagation. <br\> So a example of this novelty has been implemented in Scheme. <br\> Guards is essential to guarantee that only data with a matching key is updated/retrieved.<br\> Propagation can cancel a item, reads its contents and puts backs a item into a store. Of course, the item is also in the store during the reading.<br\> 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 ??? (A REMPLIR)<br\> So the concurrent join pattern application executed in parallel on a multi-core architecture doesn't guarantee that parallel execution lead to conflits. To Guarantee this and a high degree of parallelism, a Software Transactional Memory (STM) within a highlytuned concurrent data structure based on atomic compare-and-swap (CAS) is use. This allows to run many concurrents operations in parallel on multi-core architecture.<br\> Moreover, a atomic execution is use to prevent the "false conflit" between CAS and STM. <br\>

Version reste a faire FR : <br\>

4.1 --> pas sûr, mais je crois qu'il utilise un join pattern par but dans du code. et au final il cherche à joindre tous les résultats. Cela permet d'avoir à implémenter séparément le pb (but par but) et ainsi d'avoir le résultat qui correspond comme si on avait implémenter tous les buts en même temps. Donc on a un but = un thread. Il nomme cela du MiniJoin. Ainsi un peu comme dans notre premier article il se servent des buts réalisés pour résoudre de nouveaux buts (dans le premier article c'était avec des messages).

5 --> détail de l'algo pour montrer comment ajouter les guards et la propagation dans les join patterns.

ccl --> Ils ont donc fait une exécution parallèle basé sur les buts en scheme pour mettre des gardes et de la propagation dans les join patterns. <br\> <br\> note pour autre partie : Le Join Calculus (Fournet et Gonthier de 1996) permet de faire de la prog concurrentiel abstraite très facilement. A voir : 4 implémentation du join patterns --> Itzstein and Jasiunas 2003 et --> Benton et al. 2004 ou encore Mandel and Maranget 2008 et pour finir notre ami Russo 2008.

Other similar design patterns

• Sequence pattern
• Split pattern (parallel split)
• Map reduce

See also

• Join_Java – Join Java is a programming language that extends the standard Java programming language
• Joins_(concurrency_library) – Joins is an asynchronous concurrent computing API from Microsoft Research for the .NET Framework.
• Join-calculus - The join-calculus was developed to provide a formal basis for the design of distributed programming languages.

References

• Cédric, Fournet; Luc, Maranget (2006-08-15). "The Join-Calculus language". Institut National de Recherche en Informatique et Automatique. Retrieved 2012-10-09.
• "JoinCalculus". Cunningham & Cunningham, Inc. October 25, 2009. Retrieved 2012-10-09.
• Fournet, Cédric; Gonthier, Georges; Levy, Jean-Jacques; Maranget, Luc; Remy, Didier (1996). "A Calculus of Mobile Agents" (PDF). Le Chesnay: Concurrency Theory. {{cite journal}}: Cite journal requires |journal= (help)
• Maludzinski, Slawomir; Dobrowolski, Grzegorz (2007). "Agent Environment and Knowledge in Distributed Join Calculus": 298–300. {{cite journal}}: Cite journal requires |journal= (help)
• Russio, Claudio (2007). "The Joins Concurrency Library" (PDF). Cambridge: Practical Aspects of Declarative Languages. {{cite journal}}: Cite journal requires |journal= (help)
• Maranget, Luc; Le Fessant, Fabrice (25 Sepetmember 2007). "Compiling Join-Patterns". Le Chesnay France. {{cite journal}}: Check date values in: |date= (help); Cite journal requires |journal= (help)
• Haller, Phillip; Van Cutsem, Tom (2008). "Implementing Joins using Extensible Pattern Matching" (PDF). Lausanne: Coordination Models and Languages: 1–15. {{cite journal}}: Cite journal requires |journal= (help)
• Sulzmann, Martin; S. L. Lam, Edmund. "Parallel Join Patterns with Guards and Propagation". Denmark. {{cite journal}}: Cite journal requires |journal= (help)
• Fournet, Cédric; Gonthier, Georges (2002). "The Join Calculus: a Language for Distributed Mobile Programming" (PDF). Caminha: 1–66. {{cite journal}}: Cite journal requires |journal= (help)
• Ma, Qin; Maranget, Luc (5 April 2004). "Compiling Pattern Matching in Join-Patterns" (PDF). INRIA: 417–431. {{cite journal}}: Cite journal requires |journal= (help)
• Singh, Satnam (6 January 2007). "Higher Order Combinators for Join Patterns using STM". {{cite journal}}: Cite journal requires |journal= (help)
• MONSIEUR, Geert (2010), Pattern-based Coordination in Process-based Service Compositions, Leuven Belgium: Katholiek Universiteit Leuven
• Russo, Claudio V. (23 October 2008). "Join Patterns for Visual Basic". Nashville, Tennessee, USA: 53. {{cite journal}}: Cite journal requires |journal= (help)
• Aaron, Turon; Russo, Claudio V. (27 October 2011). "Scalable Join Patterns" (PDF). Portland, Oregon, USA. {{cite journal}}: Cite journal requires |journal= (help)
• Guzev, Vadim B. (April 2008). "Parallel C#: The Usage of Chords and Higher-Order Functions in the Design of Parallel Programming Languages" (PDF). Moscow, Russia. {{cite journal}}: Cite journal requires |journal= (help)

External link

• Concurrent Basic
• INRIA, Join Calculus homepage