Context sensitivity and synchronisation as taxonomics for parallel languages

We offer PT, a parameterised structural operational semantics (SOS) which abstracts from interaction with the state and from the dynamics of program reduction. The SOS can be used to mimic particular languages by choosing the appropriate parameters. Interaction with the state is determined by parameters which give both the form of the state and describe the result of applying a function to the state. The dynamics of reduction are controlled through quantifying how interesting a particular reduction is, where the most interesting offered reduction is chosen when more than one reduction is possible. This mechanism captures a number of context-sensitivity and synchronisation effects. We use PT to analyse the context sensitivity and synchronisation properties of a number of multiset transformation languages. We restrict ourselves to multiset transformation languages for reasons of space. Some of the languages compared are new, while others already exist, such as Gamma (Γ) and Calculus of Gamma Programs (CGP). All of the languages are translated into PT to facilitate comparison of their (dis-) similarities. The result of our comparison is a taxonomy of the languages, based on their parameters. Our classification is constructed in such a way that it is possible to define new languages to occupy the currently blank areas of the taxonomy