The chemical abstract machine

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The chemical abstract machine

Full text

Pdf (1.33 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

San Francisco, California, United States

Pages: 81 - 94

Year of Publication: 1989

ISBN:0-89791-343-4

Authors

Gerard Berry	LIX, Ecole Polytechnique, 91 128 Palaiseau, France and Ecole des Mines, Sophia-Antipolis, 06560 Valbonne, France
Gerard Boudol	INRIA Sophia-Antipolis, 06560 Valbonne, France

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 102, Citation Count: 30

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/96709.96717 What is a DOI?

ABSTRACT

We introduce a new kind of abstract machine based on the chemical metaphor used in the &Ggr; language of Banâtre & al. 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 to occur locally. We illustrate the use of this model by describing the operational semantics of the TCCS and CCS process calculi. We also show how to extract a higher-order concurrent &lgr;-calculus out of the basic concepts of the chemical abstract machine.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Samson Abramsky. The lazy A-calculus. In D. Turner, editor, Declarative Programming, Addison Wesley, 1988.
	2	J.-P. Banâtre , A. Coutant , D. Le Metayer, A parallel machine for multiset transformation and its programming style, Future Generation Computer Systems, v.4 n.2, p.133-144, Sept. 1988 [doi>10.1016/0167-739X(88)90012-X]
	3	Jean-Pierre Ban~tre and Daniel Le Metayer. A New Computational Model and lts Discipline of Programming. Technical Report INRIA Report 566, 1986.
	4	Henk Barendregt. The T~pe-Free Larnbda- Calculus. Studies in Logic Volume 108, North- Holland, 1981.
	5	Gdrard Berry. S~quentialitd de l'evaluation formelle des A-expressions. In B. Robinet, editor, Program Transformations 8rd International Colloquium on Programming, pages 67-80, DUNOD, Paxis, 1978.
	6	G. Boudol, Notes on algebraic calculi of processes, Logics and models of concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1989
	7	Gérard Boudol, Towards a Lambda-Calculus for Concurrent and Communicating Systems, Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 1: Advanced Seminar on Foundations of Innovative Software Development I and Colloquium on Trees in Algebra and Programming, p.149-161, March 13-17, 1989
	8	Nicholas Carriero , David Gelernter, Linda in context, Communications of the ACM, v.32 n.4, p.444-458, April 1989 [doi>10.1145/63334.63337]
	9	K. Mani Chandy, Parallel program design: a foundation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	10	Pierre-Louis Curien, Categorical combinators, sequential algorithms, and functional programming (2nd ed.), Birkhauser Boston Inc., Cambridge, MA, 1994
	11	Philippe Darondeau. About fair asynchrony. Theoretical Computer Science, 37:305-336, 1985.
	12	R De Nicola, Extensional equivalence for transition systems, Acta Informatica, v.24 n.2, p.211-237, April 1987
	13	R. De Nicola , M. Hannessy, CCS without &tgr;'s, The International Joint Conference on theory and practice of software development on TAPSOFT '87, p.138-152, January 1987, Pisa, Italy
	14	Rocco De Nicola and Matthew Hennessy. Testing equivalences for processes. Theoretical Computer Science~ 34:83-133, 1984.
	15	Matthew Hennessy, Observing processes, Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, School/Workshop, p.173-200, May 30-June 03, 1988
	16	C.A.R. Hoaxe. Communicating Sequential Pro. cesses. Prentice Hall, 1985.
	17	Peter Landin. The mechanical evaluation of expressions. Computer Journal, 6:308-320, 1964.
	18	R. Milner, Communication and concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
	19	Robin Milner. Program Semantics and Mechanized Proofs, pages 3-44. Mathematical Center Tracts 82, Amsterdam, 1976.
	20	Robin Milner, Joachim Parrow, and David W~lker. A Calculus of Mobile Processes. Technical Report ECS-LFCS-89-85, LFCS, Edinburgh University, 1989.
	21	B. Thomsen, A calculus of higher order communicating systems, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.143-154, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75290]

CITED BY 30

	Vijay A. Saraswat , Martin Rinard , Prakash Panangaden, The semantic foundations of concurrent constraint programming, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.333-352, January 21-23, 1991, Orlando, Florida, United States
	Dave Berry , Robin Milner , David N. Turner, A semantics for ML concurrency primitives, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.119-129, January 19-22, 1992, Albuquerque, New Mexico, United States
	J. M. E. Hyland , C.-H. L. Ong, Pi-calculus, dialogue games and full abstraction PCF, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.96-107, June 26-28, 1995, La Jolla, California, United States
	John Glauert, Object graph rewriting: an experimental parallel implementation, Proceedings of the second international symposium on Parallel symbolic computation, p.119-128, July 20-22, 1997, Maui, Hawaii, United States
	James Riely , Matthew Hennessy, A typed language for distributed mobile processes (extended abstract), Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-390, January 19-21, 1998, San Diego, California, United States
	Matthew Hennessy , James Riely, Resource access control in systems of mobile agents, Information and Computation, v.173 n.1, p.82-120, February 25, 2002
	Ronaldo Menezes, Experience with memory management in open Linda systems, Proceedings of the 2001 ACM symposium on Applied computing, p.187-196, March 2001, Las Vegas, Nevada, United States
	Jean-Pierre Banâtre , Daniel Le Métayer, Programming by multiset transformation, Communications of the ACM, v.36 n.1, p.98-111, Jan. 1993
	P. Lincoln , J. Mitchell , M. Mitchell , A. Scedrov, A probabilistic poly-time framework for protocol analysis, Proceedings of the 5th ACM conference on Computer and communications security, p.112-121, November 02-05, 1998, San Francisco, California, United States
	Satoshi Tojo, Free-ordered CUG on Chemical Abstract Machine, Proceedings of the 15th conference on Computational linguistics, August 05-09, 1994, Kyoto, Japan
	José Meseguer, A logical theory of concurrent objects, ACM SIGPLAN Notices, v.25 n.10, p.101-115, Oct. 1990
	J. F. Giorgi , D. Le Métayer, Continuation-based parallel implementation of functional programming languages, Proceedings of the 1990 ACM conference on LISP and functional programming, p.209-217, June 27-29, 1990, Nice, France
	Oscar H. Ibarra , Zhe Dang , Omer Egecioglu, Catalytic P systems, semilinear sets, and vector addition systems, Theoretical Computer Science, v.312 n.2-3, p.379-399, 30 January 2004
	Oscar H. Ibarra, On the computational complexity of membrane systems, Theoretical Computer Science, v.320 n.1, p.89-109, 12 June 2004
	Nancy Durgin , Patrick Lincoln , John Mitchell , Andre Scedrov, Multiset rewriting and the complexity of bounded security protocols, Journal of Computer Security, v.12 n.2, p.247-311, May 2004
	Oscar H. Ibarra, On membrane hierarchy in P systems, Theoretical Computer Science, v.334 n.1-3, p.115-129, 11 April 2005
	Selvin George , David Evans , Steven Marchette, A biological programming model for self-healing, Proceedings of the 2003 ACM workshop on Survivable and self-regenerative systems: in association with 10th ACM Conference on Computer and Communications Security, p.72-81, October 31-31, 2003, Fairfax, VA
	Masaki Murakami, A formal model of concurrent systems based on bipartite directed acyclic graph, Science of Computer Programming, v.61 n.1, p.38-47, June 2006
	Kohei Honda , Mario Tokoro, A small calculus for concurrent objects, ACM SIGPLAN OOPS Messenger, v.2 n.2, p.50-54, Apr. 1991
	Martín Abadi , Andrew D. Gordon, A calculus for cryptographic protocols: the spi calculus, Proceedings of the 4th ACM conference on Computer and communications security, p.36-47, April 01-04, 1997, Zurich, Switzerland
	Flemming Nielson , Hanne Riis Nielson , Henrik Pilegaard, What is a free name in a process algebra?, Information Processing Letters, v.103 n.5, p.188-194, August, 2007
	Henrik Pilegaard , Flemming Nielson , Hanne Riis Nielson, Active Evaluation Contexts for Reaction Semantics, Electronic Notes in Theoretical Computer Science (ENTCS), v.175 n.1, p.57-70, May, 2007
	Henry G. Baker, Lively linear Lisp: “look ma, no garbage!”, ACM SIGPLAN Notices, v.27 n.8, p.89-98, Aug. 1992
	José Meseguer, Rewriting as a unified model of concurrency, ACM SIGPLAN OOPS Messenger, v.2 n.2, p.86-88, Apr. 1991
	David Soloveichik , Matthew Cook , Erik Winfree , Jehoshua Bruck, Computation with finite stochastic chemical reaction networks, Natural Computing: an international journal, v.7 n.4, p.615-633, December 2008
	Karthikeyan Bhargavan , Cédric Fournet , Andrew D. Gordon , Stephen Tse, Verified interoperable implementations of security protocols, ACM Transactions on Programming Languages and Systems (TOPLAS), v.31 n.1, p.1-61, December 2008
	Ian Mackie , Shinya Sato, A Calculus for Interaction Nets Based on the Linear Chemical Abstract Machine, Electronic Notes in Theoretical Computer Science (ENTCS), v.192 n.3, p.59-70, November, 2008
	Marta Kwiatkowska , Gethin Norman , David Parker , Maria Grazia Vigliotti, Probabilistic Mobile Ambients, Theoretical Computer Science, v.410 n.12-13, p.1272-1303, March, 2009
	B. Ktari , M. Mejri , D. Godbout , H. Fujita, LyeeBuilder, Proceeding of the 2005 conference on New Trends in Software Methodologies, Tools and Techniques: Proceedings of the fourth SoMeT_W05, p.83-99, May 10, 2005
	Robert van Herk , Janneke Verhaegh , Willem F.J. Fontijn, ESPranto SDK: an adaptive programming environment for tangible applications, Proceedings of the 27th international conference on Human factors in computing systems, April 04-09, 2009, Boston, MA, USA