Service-oriented programming has dramatically changed the way software applications are developed. Auto- matic composition of services reduces human interaction on choosing the set of services that satisfy a specific request. Automatic composition has mainly been done in a centralised way with the composition specified at design time or in a decentralised manner through multi-agent systems planing. These approaches present several limitations when used in dynamically changing environments like pervasive computing scenarios. Very few proposals investigate the design of the com- position arising as a result of an ongoing self-organising process that permanently adapts to context and environmental changes. In this paper we define three chemically inspired approaches for self-composition of services operating on top of a shared tuple space. We show how tuple spaces can be exploited to design spontaneous and emergent compositions that deal with context information and a dynamic set of available services. Then we prove that our algorithms can be generalised to produce compositions of services with very common features. and show how our algorithms can be easily implemented to provide self-composition of actual Web services.