Abstract
Gamma was originally proposed in 1986 as a formalism for the definition of programs without artificial sequentiality. The basic idea underlying the formalism is to describe computation as a form of chemical reaction on a collection of individual pieces of data. Due to the very minimal nature of the language, and its absence of sequential bias, it has been possible to exploit this initial paradigm in various directions. This paper reviews most of the work around Gamma considered as a programming or as a specification language. A special emphasis is placed on unexpected applications of the chemical reaction model, showing that this paradigm has been a source of inspiration in various research areas.
This paper is a revised version of Gamma and the chemical reaction model: ten years after [10]. It has been reorganized and includes additional sections on applications of the chemical reaction model. Sections presenting large examples, extensions of the formalism and implementations issues have been seriously shortened. The reader is referred to [10] and the original papers for further details on these topics.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
S. Abramsky, Computational interpretations of linear logic, Theoretical Computer Science, Vol. 111, pp. 3–57, 1993.
R. Allen and D. Garlan, Formalising architectural connection, Proceedings of the IEEE 16th International Conference on Software Engineering, pp. 71–80, 1994.
J.-M. Andreoli and R. Pareschi, Linear Objects: logical processes with bui lt-ininheritence, New Generation Computing, Vol. 9, pp. 445–473, 1991.
J.-M. Andreoli, P. Ciancarini and R. Pareschi, Interaction abstract machines, in Proc. of the workshop Research Directions in Concurrent Object Oriented Programming, 1992.
R. Back, Refinement calculus, part II: parallel and reactive programs, in Proc. of the workshop on Stepwise Refinement of Distributed Systems: Models, Formalisms, Correctness, 1989, Springer Verlag, LNCS 430.
J.-P. Banătre, A. Coutant and D. Le Métayer, A parallel machine for multiset transformation and its programming style, Future Generation Computer Systems, pp. 133–144, 1988.
J.-P. Banătre, A. Coutant and D. Le Métayer, Parallel machines for multiset transformation and their programming style, Informationstechnik, Oldenburg Verlag, Vol. 2/88, pp. 99–109, 1988.
J.-P. Banătre and D. Le Métayer, The Gamma model and its discipline of programming, Science of Computer Programming, Vol. 15, pp. 55–77, 1990.
J.-P. Banătre and D. Le Métayer, Programming by multiset transformation, Communications of the ACM, Vol. 36-1, pp. 98–111, January 1993.
J.-P. Banătre and D. Le Métayer, Gamma and the chemical reaction model: ten years after, in Coordination Programming: Mechanisms, Models and Semantics, Imperial College Press, 1996.
P. Bertin, D. Roncin and J. Vuillemin, Programmable active memories: a performance assessment, in Proc. of the workshop on Parallel architectures and their efficient use, 1992, Springer Verlag, LNCS, pp. 119–130.
G. Berry and G. Boudol, The chemical abstract machine, Theoretical Computer Science, Vol. 96, pp. 217–248, 1992.
G. Boudol, Some chemical abstract machines, in Proc. of the workshop on A decade of concurrency, 1994, Springer Verlag, LNCS 803, pp. 92–123.
Chandy M. and Misra J., Parallel program design: a foundation, Addison-Wesley, 1988.
N. Carriero and D. Gelernter, Linda in context, Communications of the ACM, Vol. 32-24, pp. 444–458, April 1989.
T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to algorithms, MIT Press, 1990.
M. Chaudron and E. de Jong, Schedules for multiset transformer programs, in Coordination Programming: Mechanisms, Models and Semantics, Imperial College Press, 1996.
M. Chaudron and E. de Jong, Towards a compositional method for coordinating Gamma programs, in Proc. Coordination’96 Conference, Lecture Notes in Computer Science, Vol. 1061, pp. 107–123, 1996.
P. Ciancarini, D. Fogli and M. Gaspari, A logic language based on multiset rewriting, in Coordination Programming: Mechanisms, Models and Semantics, Imperial College Press, 1996.
P. Ciancarini, R. Gorrieri and G. Zavattaro, An alternate semantics for the calculus of Gamma programs, in Coordination Programming: Mechanisms, Models and Semantics, Imperial College Press, 1996.
D. Cohen and J. Muylaert-Filho, Introducing a calculus for higher-order multiset programming, in Proc. Coordination’96 Conference, Lecture Notes in Computer Science, Vol. 1061, pp. 124–141, 1996.
C. Creveuil, Techniques d’analyse et de mise en æuvre des programmes Gamma, Thesis, University of Rennes, 1991.
C. Creveuil, Implementation of Gamma on the Connection Machine, in Proc. of the workshop on Research Directions in High-Level Parallel Programming Languages, Mont-Saint Michel, 1991, Springer Verlag, LNCS 574, pp. 219–230.
C. Creveuil and G. Moguérou, D’eveloppement syst’ematique d’un algorithme de segmentation d’images’ a l’aide de Gamma, Techniques et Sciences Informatiques, Vol. 10, No 2, pp. 125–137, 1991.
E. de Jong, An industrial case study: a railway control system, Proc. Second int. Conf. on Coordination Models, Languages and Applications, Springer Verlag, LNCS 1282, 1997.
Dershowitz N. and Manna Z., Proving termination with multiset ordering, Communications of the ACM, Vol. 22-28, pp. 465–476, August 1979.
Dijkstra E. W., The humble programmer, Communications of the ACM, Vol. 15-10, pp. 859–866, October 1972.
L. Errington, C. Hankin and T. Jensen, A congruence for Gamma programs, in Proc. of WSA conference, 1993.
W. Fontana, Algorithmic chemistry, Proc. of the workshop on Artificial Life, Santa Fe (New Mexico), Addison-Wesley, 1991, pp. 159–209.
P. Fradet and D. Le Métayer, Shape types, in Proc. of Principles of Programming Languages, POPL’97, ACM Press, pp. 27–39, 1997.
P. Fradet and D. Le Métayer, Structured Gamma, Science of Computer Programming, 31, pp. 263–289, 1998.
Gelernter D., Generative communication in Linda, ACM Transactions on Programming Languages and Systems, Vol. 7,1, pp. 80–112, January 1985.
K. Gladitz and H. Kuchen, Parallel implementation of the Gamma-operation on bags, Proc. of the PASCO conference, Linz, Austria, 1994.
C. Hankin, D. Le Métayer and D. Sands, A calculus of Gamma programs, in Proc. of the 5th workshop on Languages and Compilers for Parallel Computing, Yale, 1992, Springer Verlag, LNCS 757.
C. Hankin, D. Le Métayer and D. Sands, A parallel programming style and its algebra of programs, in Proc. of the PARLE conference, LNCS 694, pp. 367–378, 1993.
B. Hoffmann. Shapely Hierarchical Graph Transformation, Symposium on Visual Languages and Formal Methods (VL FM’01) in the IEEE Symposia on Human-Centric Computing Languages and Environments (HCC’01), IEEE Press, 2001.
A. A. Holzbacher, M. Périn and M. Südholt, Modeling railway control systems using graph grammars: a case study, Proc. Second int. Conf. on Coordination Models, Languages and Applications, Springer Verlag, LNCS 1282, 1997.
P. Inverardi and A. Wolf, Formal specification and analysis of software architectures using the chemical abstract machine model, IEEE Transactions on Software Engineering, Vol. 21, No. 4, pp. 373–386, April 1995.
A. Jeffrey, A chemical abstract machine for graph reduction, TR 3/92, University of Sussex, 1992.
H. Kuchen and K. Gladitz, Parallel implementation of bags, in Proc. ACM Conf. on Functional Programming and Computer Architecture, ACM, pp. 299–307, 1993.
D. Le Métayer, Higher-order multiset programming, in Proc. of the DIMACS workshop on specifications of parallel algorithms, American Mathematical Society, Dimacs series in Discrete Mathematics, Vol. 18, 1994.
D. Le Métayer, Describing software architecture styles using graph grammars, IEEE Transactions on Software Engineering (TSE), Vol. 24(7), pp. 521–533, 1998.
L. Leth and B. Thomsen, Some Facile chemistry, TR 92/14, ECRC, 1992.
K. Li, P. Hudak, Memory Coherence in Shared Virtual Memory Systems, in Proc. of ACM Symposium on Principles of Distributed Computing, pp. 229–239, 1986.
Lin Peng Huan, Kam Wing Ng and Yong Qiang Sun, Implementing higher-order Gamma on MasPar: a case study, Journal of Systems Engineering and Electronics, Vol. 16(4), 1995.
Lin Peng Huan, Kam Wing Ng and Yong Qiang Sun, Implementing Gamma on MasPar MP-1, Journal of Computer Science and Technology.
H. McEvoy, Gamma, chromatic typing and vegetation, in Coordination Programming: Mechanisms, Models and Semantics, Imperial College Press, 1996.
H. McEvoy and P.H. Hartel, Local linear logic for locality consciousness in multiset transformation, Proc. Programming Languages: Implementations, Logics and Programs, PLILP’95, LNCS 982, pp. 357–379, 1995.
D. Mentré, D. Le Métayer, T. Priol, Formalization and Verification of Coherence Protocols with the Gamma Framework, in Proc. of the 5th Int. Symp. on Software Engineering for Parallel and Distributed Systems (PDSE-2000), ACM, 2000.
R. Milner, Communication and concurrency, International Series in Computer Science, Prentice Hall, Englewood Clifis, NJ, 1989.
R. Milner, Functions as processes, Mathematical Structures in Computer Science, Vol. 2, pp. 119–141, 1992.
L. Mussat, Parallel programming with bags, in Proc. of the workshop on Research Directions in High-Level Parallel Programming Languages, Mont-Saint Michel, 1991, Springer Verlag, LNCS 574, pp. 203–218.
M. Périn, Sp’ecifications graphiques multi-vues: formalisation et vërification de cohërence, PhD thesis, Universit’e de Rennes 1, 2000.
M. Rem, Associons: a program notation with tuples instead of variables, ACM Trans. on Programming Languages and Systems, Vol. 3,3, pp. 251–261, 1981.
M. Reynolds, Temporal semantics for Gamma, in Coordination Programming: Mechanisms, Models and Semantics, Imperial College Press, 1996.
R. Sedgewick, Algorithms in C, Addison-Wesley publishing company, 1990.
W.-P. de Roever, Why formal methods are a must for real-time system specification, in Proc. Euromicro’92, Panel discussion, June 1992, Athens.
H. Ruiz Barradas, Une approche à la d’erivation formelle de systèmes en Gamma,Thesis, University of Rennes 1, July 1993.
D. Sands, A compositional semantics of combining forms for Gamma programs, in Proc. of the Formal Methods in Programming and their Applications conference, Novosibirsk, 1993, Springer Verlag, LNCS 735, pp. 43–56.
D. Sands, Composed reduction systems, in Coordination Programming: Mechanisms, Models and Semantics, Imperial College Press, 1996.
L. Van Aertryck and O. Ridoux, Gammalog as goal-directed proofs, internal report. 62. M. Vieillot, Synthèse de programmes Gamma en logique reconfigurable, Technique et Science Informatiques, Vol. 14, pp. 567–584, 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Banătre, JP., Fradet, P., Le Métayer, D. (2001). Gamma and the Chemical Reaction Model: Fifteen Years After. In: Calude, C.S., PĂun, G., Rozenberg, G., Salomaa, A. (eds) Multiset Processing. WMC 2000. Lecture Notes in Computer Science, vol 2235. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45523-X_2
Download citation
DOI: https://doi.org/10.1007/3-540-45523-X_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43063-6
Online ISBN: 978-3-540-45523-3
eBook Packages: Springer Book Archive