I recently read the Berry and Boudol's chemical abstract machine [1, 2]. I found the way they describe the semantic really nice and quite intuitive for a process calculus.

The aspect that really appealed me is that, in the chemical abstract machine (ChAM hereafter), configurations are multiset of processes (and processes are similar to those of CCS, but it does not really matter), e.g. {{ a.b.0, /a.0, /b.0 }}, and the semantics is define on the multiset, with rules similar to a.P, /a.Q <-> P, Q, which means "if you find a a.P and a /a.Q in the multiset, you can replace them with P and Q.

Since the rules are on elements of the multiset, there is no need for a structural congruence like the one we usually have in e.g. the $\pi$-calculus. Also, from a moral point of view, such an approach seem more pleasant to me, since we explicitly have no structure, like concurrent processes (opposed to structured term to which we have to add a congruence to get rid of the structure).

Yet, as far as I know, the semantics of almost all process calculus are defined with SOS rules.

Hence my question : why is an approach à la chemical abstract machine not more popular/common?

I ignore two aspects of the ChAM in my question:

  1. Processes of the ChAM include a construct for parallel processes, which semantics is a | b <-> a, b, which syntactically allow composition à la CCS. Yet this does not affect the semantics, since such processes have to get separated before reducing.
  2. Rules are often written with two ways arrows (<-> in the question), expressing that the rule can apply in two ways. One could argue that this is a drawback for the ChAM, since the calculus possibly loops forever (by doing and undoing a rule). I think this argument is not convincing since we could get rid of the two way semantics, and force forward progress. In fact, the same argument could apply to reversible process calculi ($\rho\pi$, RCCS, etc.), where reversibility is intended

[1] http://www.sciencedirect.com/science/article/pii/030439759290185I

[2] https://doi.org/10.1145/96709.96717


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.