Pervasive environments are composed as spontaneous aggregation of heterogeneous and independent devices, which may seamlessly consume, but also provide, software resources over the network. As result, applications emerge from the dynamic composition of the resources available within the environment. This requires applications of being semantic-aware, to reason about and learn from the environment. However, due to the inherent high degree of dynamism characterizing pervasiveenvironments, semantics cannot be established a-priori, rather it should "emerge" from online negotiations among involved parties. This paper, formalizes emergent semantics principles into formal foundations, and shows, as proof of concept, how to engineer such foundations into a fully distributedsemantic service discovery.