×

zbMATH — the first resource for mathematics

The chemical abstract machine. (English) Zbl 0747.68013
Summary: We introduce a new kind of abstract machine based on the chemical metaphor used in the \(\Gamma\) language of J.-P. Banâtre and D. Le Métayer [Sci. Comput. Program. 15(1), 55-77 (1990; Zbl 0715.68054)]. States of a machine are chemical solutions where floating molecules can interact according to reaction rules. Solutions can be stratified by encapsulating subsolutions within membranes that force reactions ot occur locally. We illustrate the use of this model by describing the operational semantics of the TCCS and CCS process calculi and of the fragment of R. Milner, J. Parrow and D. Walker’s [A calculus of mobile processes; Pt. 1, Edinburgh: Univ., Dept. of Computer Sci., (LFCS Report Ser.; ECS-LFCS-89-85)/(Internal Reg.; CSR- 302-89) (1989)]. Calculus of mobile processes used by R. Milner [Functions as processes, ICALP ’90, Lect. Notes Comput. Sci. 443, 167-180 (1990)] to encode the lambda-calculus. We also give ideas on how to extract a higher-order concurrent \(\lambda\)-calculus similar to that of G. Boudol [Towards a lambda-calculus for concurrent and communicating systems; TAPSOFT, Lect. Notes Comput. Sci. 351, 149-161 (1989)] out of the basic concepts of the chemical abstract machine.

MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q55 Semantics in the theory of computing
Software:
UNITY
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abadi, M.; Cardelli, L.; Curien, P.-L.; Lévy, J.-J., Explicit substitutions, Proc. 17th ACM ann. symp. on principles of programming languages, 31-46, (1990)
[2] Abramsky, S., The lazy λ-calculus, (), 65-116
[3] Arnold, A., Sémantique des processus communicants, RAIRO inform. théor. appl., 15, 2, 103-139, (1981) · Zbl 0463.68033
[4] Banâtre, J.-P.; Coutant, A.; Le Métayer, D., A parallel machine for multiset transformation and its programming style, Future generation comput. systems, 4, 133-144, (1988)
[5] Banâtre, J.-P.; Le Métayer, D., The gamma model and its discipline of programming, Science comput. programming, 15, 55-77, (1990) · Zbl 0715.68054
[6] Barendregt, H., The lambda-calculus, its syntax and semantics, Vol. 103, (1981), North-Holland Amsterdam, Studies in Logic · Zbl 0467.03010
[7] Berry, G., Séquentialitéde l’evaluation formelle des λ-expressions, (), 67-80
[8] Boudol, G., Notes on algebraic calculi of processes, (), 261-303, NATO ASI Series F13 · Zbl 0578.68025
[9] Boudol, G., Towards a lambda-calculus for concurrent and communicating systems, (), 149-161, Lecture Notes in Computer Science
[10] Carriero, N.; Gelerntner, D., Linda in context, Comm. ACM, 32, 4, 444-458, (1989)
[11] Chandy, M.; Misra, J., Parallel program design, a foundation, (1988), Addison-Wesley Reading, MA · Zbl 0717.68034
[12] Curien, P.-L.; Curien, P.-L., Categorical combinators, sequential algorithms, and functional programming, (1986), Wiley New York, Research Notes in Theoretical Computer Science · Zbl 0643.68004
[13] Darondeau, P., About fair asynchrony, Theoret. comput. sci., 37, 305-336, (1985) · Zbl 0607.68016
[14] De Nicola, R., Extensional equivalences for transition systems, Acta inform., 24, 211-237, (1987) · Zbl 0636.68069
[15] De Nicola, R.; Hennessy, M., CCS without τ’s, (), 138-152, Lecture Notes in Computer Science · Zbl 0614.68025
[16] De Nicola, R.; Hennessy, M., Testing equivalences for processes, Theoret. comput. sci., 34, 83-133, (1984) · Zbl 0985.68518
[17] De Simone, R., Higher-level synchronising devices in meije-SCCS, Theoret. comput. sci., 37, 245-267, (1985) · Zbl 0598.68027
[18] Degano, P.; De Nicola, R.; Montanari, U., A distributed operational semantics for CCS based on condition/events systems, Acta inform., 26, 59-91, (1988) · Zbl 0656.68061
[19] Hardin, T.; Lévy, J.-J., A confluent calculus of substitutions, France-Japan artificial intelligence and computer science symposium, (1989), Izu
[20] Hennessy, M., Observing processes, (), 173-200, Lecture Notes in Computer Science · Zbl 0683.68021
[21] Hoare, C.A.R., Communicating sequential processes, (1985), Prentice-Hall Englewood Cliffs, NJ · Zbl 0637.68007
[22] Kahn, G., The semantics of a simple language for parallel processing, IFIP congress 1974, 993-998, (1974)
[23] Landin, P., The mechanical evaluation of expressions, Comput. J., 6, 308-320, (1964) · Zbl 0122.36106
[24] Meseguer, J., Rewriting as a unified model for concurrency, SRI international technical report, (1990)
[25] Milner, R., Communicating sequential processes, (1989), Prentice-Hall Englewood Cliffs, NJ, International Series in Computer Science
[26] Milner, R., Functions as processes, (), 167-180, Lecture Notes in Computer Science · Zbl 0766.68036
[27] Milner, R., (), 3-44, Mathematical Center Tracts
[28] Milner, R.; Parrow, J.; Walker, D., A calculus of mobile processes, (), ECS-LFCS-89-85
[29] Plotkin, G., A structural approach to operational semantics, (1981), University of Aarhus, Report DAIMI FN-19
[30] Reisig, W., Petri nets: an introduction, (1985), Springer Berlin, EATCS Monographs on Theoretical Computer Science · Zbl 0555.68033
[31] Thomsen, B., A calculus of higher-order communicating systems, Proc. 16th ACM ann. symp. on principles of programming languages, 143-154, (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.