Stuff for starting the AutoChem project

Gamma and the chemical paradigm

Gamma is the programming model we propose to start with (even if variants, restrictions, extensions or even very distinct languages might be considered after). In chronological order :

Aspects

Gamma (or Hocl) programs stand between high-level specifications and programs. They are pretty inefficient (usually not in the same complexity class as the corresponding imperative program). In order to obtain effective programs a possible solution is using aspects. The idea would be to have the base functionality expressed by the chemical program and the implementation issues (data structures, evaluation strategy, etc.) expressed within aspects. Just two links:

 

Domain-specific languages

Another direction is to restrict the chemical model in order to guarantee an efficient implementation. Two links for a start :

 

About MGS

MGS is a language related to Gamma. It adds the notion of topology defining the neighborhood of each element in a collection (to be compared with structured Gamma).

Data-parallelism

Data-parallelism focuses on distributing the data across different parallel computing nodes. It contrasts to task parallelism as another form of parallelism. Data-parallelism can be used "for free" in a sequential language by hidding the parallelism in some aggregate data-type whose elements  are located at different processors and relying on a library of primitive operations implemented in a parallel way. Multiset or more generally MGS topological collections can be implemented in a distributed fashion.

This article presents proposes a classification of the various expressions of parallelism in programming languages and shows how to introduce data-parallelism in a data-flow language. The language, called 81/2 (height and a half or Otto e Mezzo) has been developped by the people from MGS. The data-flow stuff is not very interesting for the AutoChem project but the data-parallel part has many things to do with AutoChem.

Data-parallel structure are managed through parralel operation. Together we can consider them as a kind of algebra. Mister Bird and Mister Merteens have developped an algebra of list and David Skillicorn has shown how to interpret the Bird-Merteens algebra as a parrallel calculsus. This paper is a good introduction and show how to refine a Bird-Merteens expression (expressing a computation where the parallelism is implicit) into a more refined expression in an algebra that exposes the parallelism. This approach is an old one and to extend what can be expressed, people have turned to more general skelettons and parallel operation composition, like in the BSP model. But any way, the algebraic approach is worth to know.

A good project on data-parallelism was the NESL project. NESL has developped interesting notion (e.g. nested vectors), several efficient implementation technics and useful examples. I mention it because I think that some of the technics have somethings to do with some Pascal's idea.

The TOM way

We have mentionned in the text of the AutoChem project the use of aspect oriented language to decouple the specification of the parallelism/distribution/etc. from other concerns. In this direction we have to mention the TOM project developped by Pierre-Etienne Moreau at the LORIA. TOM introduce rewriting rules in the target language. TOM presents several interesting features in the context of AutoChem: 

Selected articles are available as well as the habilitation manuscript (but it is in french).

Population protocols

The population protocol model describes a collection of tiny mobile agents that interact with one another to carry out a computation. The agents are identically programmed finite state machines. Interactions between pairs of agents cause the two agents to update their states. These interactions are scheduled by an adversary, subject to a fairness constraint. Input values are initially distributed to the agents, and the agents must eventually converge
to the correct output value. This framework can be used to model mobile ad-hoc networks of tiny devices or collections of molecules undergoing chemical reactions.

A population protocol is a specialized class of chemical program. So, they are interesting to study. A good survey is given in EATCS bulletin N°93, p. 106.