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).
- This introductory
tutorial is the seminal paper on the MGS project. The
language is
motivated by the simulation of a certain class of dynamical systems:
the dynamical systems that presents a dynamical structure (chaper 1).
The language itself is presented in chapter 2, 3 and 4. Some element
for its formalization (combinatorial topology) are presented
in chapter 5.
- Additional
Booklet to the Habilitation (6.5Mb, .pdf). This booklet
gather 19 papers related to the Otto and (mainly) the MGS projects.
Papers
are classified in three areas:
- Declarative Unconventional
Languages,
- Modelling and Simulation of Dynamical Systems -
Applications,
- and, Elements of Implementation.
This
pdf document is active and you can click on the cited references
to retrieve all MGS papers.
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:
- The term to be rewriten can be associative (i.e. sequence)
or associative-commutative (i.e.: multiset). Their implementation in
the target language is described independantly, like an aspect.
- TOM is inspired by the Elan framework and inherits the
ability to program the rules application strategy.
- TOM enhance the pattern matching capacity by several non-standard features like "anti-pattern".
- There is a lot of knwo-how in pattern-matching compilation.
- They architecture is non-intrusive.
- Etc.
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.