Antoine Spicher
email: antoine.spicher@u-pec.fr

Olivier Michel
email: olivier.michel@u-pec.fr

Jean-Louis Giavitto
email: jean-louis.giavitto@ircam.fr

Spatial Computing in MGS

Keywords: unconventional programming paradigm, spatial computing, MGS, topological collection, topological rewriting, dynamical systems with a dynamical structure

motivates and introduces the tutorial on MGS and spatial computing presented at UCNC 2012.

Spatial Computing

The notion of space appears in several application domains of computer science. Spatial relationships are involved in computer aided design applications, geographic databases, image processing. . . to cite a few. In these applications, space and spatial organization arise as the purpose or the result of a computation.

On the other hand, space can also play the role of a computational resource (e.g., in parallel computation) or of a constraint to the computation itself (e.g., in distributed systems).

Spatial Computing is an emerging research field that recognizes that space can be an input to computation or a key part of the desired result of the computation [START_REF] De Hon | Computing Media and Languages for Space-Oriented Computation[END_REF][START_REF] Beal | Organizing the aggregate: Languages for spatial computing[END_REF]. Computations are performed in space and concepts like position, distance metric and shape matter. Space is then no longer an issue to abstract away, but a first-order effect that we have to make explicit in programs, to use, produce or optimize.

Spatial Computer in Physical Space

From the point of view of the computing devices, spatial computers are collections of local computational devices distributed through a physical space, in which: the interaction between localized agents is strongly dependent on the distance between them, and the "functional goals" of the system are generally defined in terms of the system's spatial structure (e.g., formation control in robotics, self-assembly, etc.).

Not all spatially distributed systems are spatial computers. The Internet and peer-to-peer overlay networks may not in general best be considered as spatial computers, both because their communication graphs have little relation to the Euclidean geometry in which the participating devices are embedded, and because most applications for them are explicitly defined independent of network structure.

Spatial computers, in contrast, tend to have more structure, with specific constraints and capabilities that can be used in the design, analysis and optimization of algorithms.

Systems that can be viewed as spatial computers are abundant, both natural and man-made, and blur the distinction between "space as a result" and "space as a resource". For example, in wireless sensor networks and animal or robot swarms, inter-agent communication network topologies are determined by the distance between devices, while the agent collectives as a whole solve spatially-defined problems like "analyze and react to spatial temperature variance" or "surround and destroy an enemy." Similarly, in biological embryos, each developing cell's behavior is controlled only by its local chemical and physical environment, but the eventual structure of the organism is a global property of the dynamic organization of the cellular arrangement.

Abstract Spaces in Computation

The elements of a physical computing system are spatially localized and when a locality property holds, only elements that are neighbors in physical space can interact directly. So the interactions between parts are structured by the spatial relationships of the parts.

However, even for non physical systems, usually an element does not interact with all other elements in the system. For instance, in a program3 , from a given element in a data structure, only a limited number of other elements can be accessed [START_REF] Giavitto | Data structure as topological spaces[END_REF]: in a simply linked list, the elements are accessed linearly (the second after the first, the third after the second, etc.); from a node in a tree, we can access the father or the sons; in arrays, the accessibility relationships are left implicit and implemented through incrementing or decrementing indices (called "Von Neumann" or "Moore" neighborhoods if one or several changes are allowed).

Thus the interactions between the elements of a system induce a neighborhood relationship that spans an abstract space. We will show that the structure of the interactions has a topological nature: the set of elements can be organized through the interactions as an abstract simplicial complex [START_REF] Giavitto | Computation in space and space in computation[END_REF] which is a spatial representation of the interactions in the system.

MGS is an experimental declarative programming language [START_REF] Giavitto | Mgs: a rule-based programming language for complex objects and collections[END_REF][START_REF] Giavitto | The topological structures of membrane computing[END_REF] used as a vehicle to experiment, to investigate, and to validate new concepts and tools for spatial computing. MGS relies on 3 ideas:

a data structure is a field, or more precisely, a topological chain; a computation is a chain transformation; chain transformations can be specified using a new kind of rewriting.

A field is a classical notion in physics that associate a value to each point of a space (the temperature in a room is a field). A topological chain is a similar notion: it associates a value to the parts of a space built by gluing elementary parts following some constraints. The difference is that the underlying space is built by associating parts of various dimensions and is not restricted to be a set of points (points are elementary parts of zero dimension).

We use the term topological collection to stress the spatial view on data structures, and also because we relax some of the mathematical constraints used to give a nice algebraic structure to topological chains. Topological collections can be used to model a physical space or a logical one: we will give some examples where topological collections are used to model musical processes or to solve analogy, without referring to the actual euclidean space.

MGS embeds the idea of topological collections and their transformations into the framework of a simple dynamically typed functional language. Collections are just new kinds of values. MGS proposes several construction to build new topologies from existing ones and the rich type structure has proven useful to face various simulation problems in systems biology, chemistry, synthetic biology, etc.

Transformations are functions acting on collections. They are defined by a specific syntax using rewriting rules. They are first-class values and can be passed as arguments or returned as the result of an application. Such mechanism enables the definition of powerful polytypic operators [START_REF] Jeuring | Polytypic programming[END_REF], as for example the generic definition of discrete analogs of the differential operators used to manipulate fields in physics [START_REF] Giavitto | Topological rewriting and the geometrization of programming[END_REF].

Computability versus Expressive Power

Topological collections and their transformation enable the unification in a same programming language of several biologically or biochemically inspired computational models, namely: Gamma [START_REF] Banâtre | Gamma and the chemical reaction model: Fifteen years after[END_REF] and the CHAM, P systems [START_REF] Pȃun | From cells to computers: computing with membranes (P systems)[END_REF], L systems [START_REF] Rozenberg | Lindenmayer Systems[END_REF], cellular automata [START_REF] Neumann | Theory of Self-Reproducing Automata[END_REF] and their variants. These models can be rephrased as the iteration of simple transformations on a topological collection; the difference coming from the topology of the space underlying the collection. However, we do not claim that we have achieved a useful theoretical framework encompassing the cited formalisms. We advocate that few notions and a single syntax can be consistently used to allow the merging of these formalisms for programming purposes.

The field of unconventional computing models, which is devoted to the study of the complexity of problems using a predefined set of (more or less exotic) basic operations, is not under focus here. The development of MGS is related to the field of unconventional programming models: MGS is used to study the expressive power of the spatial metaphor. The literature on programming language contains a wealth of informal claims on the relative expressive power of programming languages. However, this very notion remains difficult to formalize: for instance, we cannot compare the set of computable functions that a programming language can represent since nearly all programming languages are universal. As far as we know, there are only a few attempts to formalize this notion of expressiveness, see [START_REF] Felleisen | On the expressive power of programming languages[END_REF][START_REF] Mitchell | On abstraction and the expressive power of programming languages[END_REF]. These works mainly rely on the idea of translating a language into another, using a limited and predefined form of translation (if any translation is allowed, a universal language can be the target of the translation of any other one). However, these notions fail to explain why object-oriented languages (like C++ or Java) are usually considered as more expressive than their imperative counterpart (like C).

The spatial metaphor has been proven useful at least at two levels in the development of new programming model. It is an heuristic to develop alternative mechanisms in programming languages or to invent new algorithms (for instance, a variety of successful established techniques for self-organization and self-adaptation arise from explicitly spatial metaphors, e.g., self-healing gradients). The spatial metaphor proposes also new techniques originated in topology and geometry to specify and to analyze programs. These tools depart from the logical foundations of computer science and put forward alternative and complementary views in the nature of programming and computation.

Applications to (DS) 2

In fine, unconventional programming languages have to be validated on real applications. A target application domain for MGS is the modeling and simulation of dynamical systems and especially those that exhibit a dynamic structure [START_REF] Giavitto | Mgs: a rule-based programming language for complex objects and collections[END_REF] (in short (DS) 2 for "Dynamical System with a Dynamic Structure"). This kind of dynamical systems is very challenging to model and simulate. For instance, many biological systems, e.g. in biological development, can be viewed as a dynamical system in which not only the values of state variables, but also the set of state variables, its organization and the evolution function, change over time. New programming concepts must be developed to ease their modeling and simulation.

Applications of MGS in the biological field are described for example in [START_REF] Spicher | Using rewriting techniques in the simulation of dynamical systems: Application to the modeling of sperm crawling[END_REF][START_REF] Spicher | Declarative modeling of a neurulation-like process[END_REF][START_REF] Barbier De Reuille | Computer simulations reveal properties of the cell-cell signaling network at the shoot apex in Arabidopsis[END_REF][START_REF] Michel | Rule-based programming for integrative biological modeling -application to the modeling of the λ phage genetic switch[END_REF][START_REF] Spicher | Understanding the Dynamics of Biological Systems: Lessons Learned from Integrative Systems Biology, chapter Interaction-Based Simulations for Integrative Spatial Systems Biology[END_REF][START_REF] Giavitto | The modeling and the simulation of the fluid machines of synthetic biology[END_REF]. The relations between MGS and the simulation of discrete dynamical systems are investigated in [25, ?], the link between the MGS rule application strategies and stochastic simulation is sketched in [START_REF] Spicher | Stochastic p systems and the simulation of biochemical processes with dynamic compartments[END_REF].

MGS has also been used in other application area like self-assembly [START_REF] Giavitto | Systems Self-Assembly: multidisciplinary snapshots, chapter Simulation of self-assembly processes using abstract reduction systems[END_REF], autonomic computing [START_REF] Giavitto | Software-Intensive Systems and New Computing Paradigms[END_REF] or automatic music analysis [START_REF] Bigo | Building topological spaces for musical objects[END_REF]. "Conventional" questions still apply to "unconventional" program, and for instance, the model-checking of a small fragment of MGS is presented in [START_REF] Giavitto | Integrated regulatory networks (irns): Spatially organized biochemical modules[END_REF].

All the examples presented during the tutorial are examples of actual MGS programs. The MGS interpreter is freely accessible from the MGS home page at http://mgs.spatial-computing.org.

The importance of space in the computation process itself has long been recognized, for example with the use of spatial relationships to structure and reason about programs; see[START_REF] Coffman | System deadlocks[END_REF] for an early reference.

Acknowledgements

We would like to express our gratitude to H. Klaudel, F. Delaplace and F. Pommereau at the Univ. of Evry, P. Prusinkiewicz at the Univ. of Calgary, and J. Cohen at the Univ. of Nantes for numerous discussions on biological modeling and formalization. We benefited from inspiring interactions with the unconventional computing community and especially S. Stepney at the Univ. of York, C. Teuscher at Portland State Univ., J. Durand-Lose at Univ. of Orleans, the membrane computing community with G. Paun at Univ. of Sevilla and M. Gheorghe at the Univ. of Sheffield. The chemical model of computation has been often challenging and we thanks J.-P. Bantre, T. Priol and P. Fradet at INRIA. Annick Lesne, R. Doursat, P. Bourgine and the french complex system community has provided a lot of motivations and insights. And great thanks are obviously due to the first supporters of the spatial computing movement: J. Beal at BBN, F. Gruau at Univ. of Paris South, S. Dulman and many others. This work has been funded by the CNRS, the Univ. of Evry, the Univ. of Paris-Est, Ircam, Inria and the ANR projects Autochem and SynBioTIC.


Antoine Spicher
email: antoine.spicher@u-pec.fr

Olivier Michel
email: olivier.micher@u-pec.fr

Jean-Louis Giavitto
email: jean-louis.giavitto@ircam.fr

Arbitrary Nesting of Spatial Computations

Modern programming languages allow the definition and the use of arbitrary nested data structures but this is not generally considered in unconventional programming models. In this paper, we present arbitrary nesting in MGS, a spatial computing language. By considering different classes of neighborhood relationships, MGS can emulate several unconventional computing models from a programming point of view. The use of arbitrary nested spatial structures allows a hierarchical form of coupling between them. We propose an extension of the MGS patternmatching facilities to handle directly nesting. This makes possible the straightforward emulation of a larger class of unconventional programming models.

I. INTRODUCTION

Modern programming languages allow data structure to be nested so that a valid element of a structure can also be in its turn another structure. Generally, this is not considered in unconventional programming models. For instance, the state of a cell in a cellular automata is not (the state of) another cellular automata. Another example: the value labeling a symbol in parametric Lindenmayer system is not (a string representing a derivation in) another Lindenmayer system.

In chemical computing, as exemplified in Gamma [START_REF] Banâtre | Gamma and the chemical reaction model: Fifteen years after[END_REF], chemical solutions are abstracted as multisets (a generalization of the notion of set in which members are allowed to appear more than once) and a molecule corresponds to an elementary data and not another chemical solution. Nested multisets are considered in membrane systems 1 [START_REF] Paun | Computing with membranes[END_REF] but are studied as a completely different computational model. Indeed, the management of the nesting entails the introduction of new mechanisms (transport rules in the case of membrane systems).

In this paper we consider arbitrary nesting in MGS, a spatial computing language where space is managed through the structure of the data. MGS relies on neighborhood relationships to represent physical (spatial distribution, localization of the resources) or logical constraints (inherent to the problem to be solved) in a computation. 1 Nested multisets are also considered in High Order Chemical Language [START_REF] Banâtre | Programming self-organizing systems with the higher-order chemical language[END_REF]. In Structured Gamma [START_REF] Fradet | Structured gamma[END_REF], elements of the multiset are linked by relations defined by a graph grammar. It is then theoretically possible to encode a given static nest of multisets using relations specified by a specific graph grammar to implement membership test and to make a distinction between elements and nested multisets.

By considering different classes of neighborhood relationships, MGS can emulate several unconventional computing models from the point of view of the programming. The use of arbitrary nested spatial structures allows a hierarchical form of coupling between them. Furthermore, we propose an extension of the MGS pattern-matching facilities to handle nesting explicitly. This makes possible the concise expression of various algorithms as well as the straightforward emulation of a larger class of unconventional programming models.

Outlines: This paper is organized as follows. The next section introduces the emerging field of spatial computing and the notions of topological collection and transformation developed in MGS. Section III discusses the relevance of nesting in the context of spatial computing and section III-D proposes a new pattern matching construct to make the handling of nested structures mores easier. Section IV exemplifies the use of nested spaces with three direct applications. The first encodes terms used to represents boolean formulae with nested sets. The computation of a disjunctive normal form on this representation is explained. The second example computes quadtrees, a recursive data structure for partitioning a two dimensional space. The last one is dedicated to the informal translation of the fraglet computational model into MGS. Related and future work concludes this article.

II. BACKGROUND A. Computing in Space, Space in Computation and Spatial Computing

Spatial Computing is an emerging field of research [START_REF] De Hon | Computing Media and Languages for Space-Oriented Computation[END_REF] where the computation is structured in term of spatial relationships where only "neighbor" elements may interact.

For example, the elements of a physical computing system are spatially localized and when a locality property holds, only elements that are neighbor in space can interact directly. So the interactions between parts are structured by the spatial relationships of the parts.

Even for non physical system, usually an element does not interact with all other elements in the system. For instance, from a given element in a data structure, only a limited number of other elements can be accessed [START_REF] Giavitto | Data structure as topological spaces[END_REF]: in a simply linked list, the elements are accessed linearly (the second after the first, the third after the second, etc.); from a node in a tree, we can access the father or the sons; in arrays, the accessibility relationships are left implicit and implemented through incrementing or decrementing indices (called "Von Neumann" or "Moore" neighborhoods if one or several changes are allowed).

More generally, if an element e in a system interacts during a computation with a subset E = {e 1 , . . . , e n } of other elements, it also interacts with any subset E included in E. This closure property induces a topological organization: the set of elements can be organized as an abstract cellular complex which is a spatial representation of the interactions in the computation [START_REF] Giavitto | Computation in space and space in computation[END_REF]. This abstract space instantiates a neighborhood relationship that represents physical (spatial distribution, localization of the resources) or logical (inherent to the problem to be solved) constraints.

In addition, space can be an input to computation or a key part of the desired result of the computation, e.g. in computational geometry applications, amorphous computing [START_REF] Abelson | Amorphous computing[END_REF], claytronics [START_REF] Aksak | Claytronics: highly scalable communications, sensing, and actuation networks[END_REF], distributed robotics or programmable matter... to cite a few examples where notions like position and shape are at the core of the application domain.

B. The MGS approach to Spatial Computing

The MGS project recognizes that space is not an issue to abstract away but that computation is performed distributed across space and that space, either physical or logical, serves as a mean, a resource, an input and an output of a computation.

1) Topological Collections: In MGS, the notion of space is handled through a slight generalization of the notion of field. In physics, a field assigns a quantity to each point of a spatial domain [START_REF] Leavens | Fields in physics are like curried functions or physics for functional programmers[END_REF].

MGS handles spatial domains defined by abstract cellular complex [START_REF] Tucker | An abstract approach to manifolds[END_REF]. An abstract cellular complex is a formal construction that builds a space in a combinatorial way through more simple objects called topological cells. Each topological cell abstractly represents a part of the whole space: points are cells with dimension 0, lines are cells with dimension 1, surfaces are 2 dimensional cells, etc. The structure of the whole space, corresponding to the partition into topological cells, is considered through incidence relationships, relating a cell and the cells in its boundary.

In this approach a field is a finite labeling of a cellular complex: a cellular complex may count an infinite number of cells but MGS restricts itself on fields labeling only a finite number of these cells. Such fields are called topological collections to stress the importance of the neighborhood relationships induced by the incidence relationships. Topological collections are a weakening of the notion of topological chain developed in algebraic topology [START_REF] Munkres | Elements of Algebraic Topology[END_REF] and have been introduced in [START_REF] Giavitto | The topological structures of membrane computing[END_REF] to describe arbitrary complex spatial structures that appear in biological systems [START_REF]Modeling the topological organization of cellular processes[END_REF] and other dynamical systems with a time varying structure [START_REF] Giavitto | Topological collections, transformations and their application to the modeling and the simulation of dynamical systems[END_REF], [START_REF] Giavitto | Topological rewriting and the geometrization of programming[END_REF]. Topological collections generalize fields because they associate a quantity with 0-cells (points in space) but also with arbitrary n-cells.

Graphs are examples of one dimensional cellular complexes: they are made of only 0-and 1-cells. In this paper, we will stick to topological collections where the underlying complex is a graph. In [START_REF] Giavitto | Data structure as topological spaces[END_REF] it has been showed how usual data structures (sets, multisets, lists, trees, arrays. . . ) can be seen as one dimensional topological collections: the elements in a data structure are the quantities assigned by the field to the nodes of a graph.

A specific neighborhood relationship has also a special importance in the rest of this paper: the full relation. With this relation, every node is neighbor of every other nodes. This corresponds to a node-labeled complete graph and to the multiset data structure.

2) Transformations: Usually in Physics, fields and their evolution are specified using differential operators. MGS generalizes these operators in a rewriting mechanism, called transformation. A transformation is the application of some local rules following some strategy. The application of a local rule a =⇒ b in a collection C:

1) selects a subcollection A that matches the pattern a;

2) computes a new subcollection B as the result of the evaluation of the expression b instantiated with the collection A; 3) and substitutes B for A in C. A local rule specifies a local evolution of the field: the left hand side (lhs) of the rule typically matches elements in interaction and the right hand side (rhs) computes local updates of the field.

Patterns pat are expressions defined inductively starting from the pattern variables "x" (matching exactly one element in a collection) and several operators used to compose more complex patterns: the neighborhood between two subcollections " pat, pat ", the repetition "pat * ", the guard "pat/exp" and the typing "pat:T " (elements matched by pat have to be of type T ).

Transformations are a powerful means to define functions on topological collections complying with the underlying spatial structure. For instance, discrete analog of differential operators can be defined using transformations [START_REF]Topological rewriting and the geometrization of programming[END_REF]. For multisets, transformations reduce simply to associative-commutative rewriting [START_REF] Dershowitz | Associativecommutative rewriting[END_REF] also called multiset rewriting.

III. NESTED SPACES

In classical Physics, a field can be classified as a scalar field or a vector field according to whether the value of the field at each point is a scalar or a vector. However, it is not usual to consider "field valued fields". From the MGS perspective, this notion simply corresponds to the idea of nested topological collections. Such a feature is relevant and valuable in at least three areas: for the representation of and the computation on hierarchical or inductive data structures; in the modeling and the simulation of multiscale systems; and in the emulation of "stratified" computational models.

A. Inductive Data Structures

The possibility to nest arbitrarily data structures is now pervasive in modern programming languages. Its usefulness to represent hierarchical data (e.g., XML) or inductive structure (e.g., list, trees) is well established. We give an example of the use of nested spaces in an algorithmic application relying on multisets in section IV-A.

B. Multiscale Systems

The modeling of a natural system often implies entities appearing on distinct temporal and spatial scales: each level addresses a phenomenon over a specific window of length and time. These scales appear for logical reasons (at a particular scale, the system exhibits uniform properties and can be modeled by homogeneous rules acting on objects relevant at this scale) or for efficiency reasons (e.g., the reductionist simulation of the whole system from first principles is computationally not tractable while we are only interested in coarsegrained description).

Multiscale models and simulations arise when interactions between scales must be considered. For spatial scales, it means that simultaneous spatial representations must be managed as in adaptive mesh refinement [START_REF] Berger | Adaptive mesh refinement for hyperbolic partial differential equations[END_REF]. This method relies on a sequence of "nested rectangular grids" on which a PDE is discretized. It is important to realize that these subgrids are not patched into the coarse grid but overlaid to track the feature of interest. A simplistic example is presented in section IV-B. Another example, in the area of discrete modeling, is the complex automata framework [START_REF] Hoekstra | Towards a complex automata framework for multi-scale modeling: Formalism and the scale separation map[END_REF] corresponding to a "graph of cellular automata".

Sometimes scales can be separated, that the coupling between scales can be localized at some isolated interaction points in space and time. Then, the resulting computation corresponds to a hierarchical process with a directed flow of information. This is not always the case and we will introduce a dedicated pattern-matching mechanism in section III-D to ease the reference between scales.

C. Stratified Computational Models

Some models of computation exhibit naturally an inductive structure. For instance, the state of a membrane system is a multiset of symbols and (inductively) membrane systems. This structure leads directly to a nested organization of "multiset of symbols and multisets". Some computational models are also best described as a combination of two paradigms: the second being substituted for some generic parts in the first. We list a few examples issued from various compartmentalization devices introduced over a basic chemical framework. In membrane systems, strings have been considered instead of symbols [START_REF] Castellanos | Computing with membranes: P systems with worm-objects[END_REF]. This leads obviously to "multiset of sequences of symbols and multisets". Nested multisets are restricted to the description of membranes organized by inclusion only. Tissue P systems [START_REF] Martín-Vide | Tissue p systems[END_REF] arrange the membranes and their interactions following an arbitrary graph, calling for a "graph of multisets". Spatial P systems [START_REF] Barbuti | Spatial p systems[END_REF] are a variant of P systems which embodies the concept of space and position inside a membrane. Membranes and objects are positioned in a two-dimensional discrete space. Hence, we have to consider "grids of multisets and grids and symbols".

In section IV-C, we will sketch the encoding of fraglets, a molecular biology inspired execution model for computer communications leading to "graph of multisets of sequences".

D. Matching Nested Structures

In the next section, we give examples of the three usages of nested spaces we have identified above section III. The use of nested spaces does not require a priori new control structures. For example, if the reactions between symbols of a P systems are coded by a transformation EvalRule, then we can defines a function Apply and an auxiliary transformation ApplyNested to thread EvalRule over the nested structure:

fun Apply(x) = EvalRule(ApplyNested (x)) and trans ApplyNested = x:bag =⇒ Apply(x) This piece of code is enough to trigger the chemical rules specified by EvalRule through the entire structure. But the transport rules, used for example to expel one molecule from a membrane to the enclosing one, are a little bit heavier to write because they imply the simultaneous matching of two levels in the nested structure.

The usual MGS pattern constructions are "flat": the pattern variables of a transformation T refer to elements of the collection on which T is applied [START_REF] Giavitto | Pattern-matching and rewriting rules for group indexed data structures[END_REF]. To make easier the handling of nested collections, we extend the current syntax with a new construction allowing references to elements of a nested collection. The pattern construct

[ pat | x ] matches a collection C nested within the current one. The pattern pat must match a subcollection C in C and the variable x is bound to the collection C deprived of C . For example, the pattern

x, [ 2, 3 | y ] as z matches only one occurrence in the sequence (0, (1, 2, 3, 4), 5) and binds x to 0, z to the nested sequence (1, 2, 3, 4) and y to the sequence [START_REF] Banâtre | Gamma and the chemical reaction model: Fifteen years after[END_REF][START_REF] Paun | Computing with membranes[END_REF]. The notation [ pat | ... ] can be used to spare a variable if the rest of the subcollection is not used elsewhere. In this declaration, formula is a sum type: a formula is either a boolean variable (represented by a string value), or the negation of a formula nested in a record with one field f, or the conjunction (resp. disjunction) of formulae nested in a set with subtype And (resp. Or). With these types, the formula ¬(p ∧ q) ∨ r can be represented as follows: { f = "p"::"q":: And:() }::"r":: Or:() where e::S inserts an element e in the set S and C:() denotes the empty collection of type C.

IV. COMPUTING WITH NESTED COLLECTIONS

The computation of the disjunctive normal form can be achieved by iterating until a fixpoint is reached, the following transformation:

trans x:Or =⇒ DNF (x)

x:Not =⇒ DNF (x) } Each rule is a straightforward translation in MGS of a well known transformation of a boolean formula into an equivalent one. In this program, the map and fold are the usual map and fold functions: map(f ,s) applies the function f to each elements of the collection s and returns the collection of results; fold(f ,z,s) reduces the elements of the collection s using the binary function f and starting from z. The function join is used to append two collections and choose is used to pick-up one element in a collection. Finally, the expression λf f ::s is a lambda expression that appends its argument (here a formula) to the collection s.

B. A Simple Space Subdivisions Scheme

This example shows the building of a quadtree that partitions a set of points in 2D space. Quadtrees recursively subdivide a rectangular spatial domain into four regions. The subdivision is recursively iterated until there is less than n points in each region (we take n = 2 in the following). Figure 1 gives an example where the points are more or less aligned along a curve. This adaptive mesh is described by the following type definitions:

type QuadTree = Grid[QuadTree] | Cloud and gbf Grid = < n, e ; 2e=0, 2n=0 > and collection Cloud = set[Point2D] and record Point2D = { x:real, y:real } GBF are collections with a regular neighborhood whose topology is specified though a group presentation. Here, the GBF Figure 1. Top: Adaptive mesh refinement using quadtrees on a set of 100 points. Bottom: The corresponding nested structure pictured as an inclusion tree.

Grid specifies a 2×2 torus with two directions n and e. Such grid describe a partition in four adjacent regions.

The recursive subdivision is computed by the following transformation:

trans MakeQuadTree = c:Cloud / size(c) > 2 =⇒ MakeQuadTree(SplitCloud (c))
The function SplitCloud makes the real work:

fun SplitCloud (c:Cloud) = let g = barycenter(c) in let c 0 , c 1 = split(λp p.x<g.x, c) in let c 00 , c 01 = split(λp p.y<g.y, c 0 ) in let c 10 , c 11 = split(λp p.y<g.y, c 1 ) in Grid:(c 00 @0, c 01 @e, c 10 @n, c 11 @(n+e))

Function SplitCloud divides a cloud of points c into four subclouds c ij depending on the positions of the points compared to the barycenter (above or below, on the left or on the right).

Then it builds a new Grid collection where the four cells are labeled by the clouds c ij . Function barycenter computes the center of mass of a cloud of points (it is easily expressed using a fold over the elements of the set.) The function split takes a predicate and a collection, and returns two collections: the elements of the first one satisfy the predicate and the second one gathers the remaining elements. The syntactic construction T :(. . . v i @c i . . . ) builds a collection of type T where the value v i is associated with the cell c i . The process is illustrated on figure 1. There is no need of the new pattern matching construct because there is no need to "mix" the elements of a top level collection with the elements of a nested one. It is the recursive calls of MakeQuadTree that create the nested structure from a flat cloud of points.

C. Fraglet

Fraglets are tiny computation fragments or sequences of tokens that flow and react through a computer network. They have been introduced in [START_REF] Tschudin | Fraglets-a metabolistic execution model for communication protocols[END_REF] as an execution model for computer communications inspired by molecular biology. They have been designed to lay the ground for automatic network adaption and optimization processes as well as the synthesis and evolution of protocol implementations. Table I sketches the core instructions.

For example, the fraglets below together with a fraglet [length tail] located on the same node of the network, will compute the length of tail by generating the fraglet [total n] (where n is the size of tail):

[counter 0] [matchp length empty stop cnt] [matchp stop match counter total] [matchp cnt pop cnt1] [matchp cnt1 split match counter incr counter * length] [matchp incr exch sum 1]
In this program, the fraglets can be interpreted as follows: fraglet [counter 0] defines a local variable with initial value 0; fraglets starting with matchp define functions; finally fraglet [length tail] is the application of function length on the list tail.

In the following we encode the fraglet formalism by implementing a fraglet interpreter in MGS. For the sake of simplicity, we do not consider here the localization of the fraglets on the nodes of a communication network and the communication rules between nodes 2 . Let consider the following MGS type declaration: The state of the system is represented by a multiset inhabited by a population of fraglets; fraglets are sequences of tokens (symbols or integers). For each fraglet operator, Table I gives the formal fraglet instruction, its informal semantics and its translation into an MGS transformation rule. For example, the split instruction consists in extracting the subsequence of tokens in the fraglet located between the operator (the first element in the sequence) and the first occurrence of the special token * . This operation is straightforwardly translated in MGS: the pattern matches in a fraglet the operator 'split (the syntactic construction @0 checks that the operator is located at the first position in the sequence) followed by a subsequence terminated by the special token 'time. The subsequence is specified by (x/x != 'time) * that matches a repetition of elements different from 'time.

2 Nevertheless the reader is invited to pay attention that this restriction is done for the sake of the simplicity: the whole formalism can be specified in MGS using an additional level of nesting by considering a graph labeled by multisets of fraglets.

V. RELATED WORK Topological collections are reminiscent of Data-fields, studied e.g. by B. Lisper [START_REF] Lisper | On the relation between functional and data-parallel programming languages[END_REF]. Data-fields are a generalization of the array data structure where the set of indices is extended to all Z n (see also [START_REF] Giavitto | A data parallel Java client-server architecture for data field computations over Z Z n[END_REF]). We have introduced the concept of group based fields, or GBF [START_REF] Giavitto | Group based fields[END_REF], [START_REF] Giavitto | Rapport scientifique en vue d'obtenir l'habilitation à diriger des recherches[END_REF], to extend data-fields towards more general regular data structures. Topological collections emphasize data structures as a set of places independently of their occupation by values. This approach is also shared by the theory of species of structures [START_REF] Bergeron | Combinatorial species and treelike structures, ser. Encyclopedia of mathematics and its applications[END_REF]. Motivated by the development of enumeration techniques for labeled structures, the emphasis is put on the transport of structures along bijections while spatial computing focuses on topological relationships.

Disentangling the elements in a data structure from their organization has several advantages. In [START_REF] Jay | A semantics for shape[END_REF], B. Jay develops a concept of shape polymorphism where a data structure is also a pair (shape, set of data). The shape describes the organization of the data structure (restricted to tabular organizations) and the set of data describes the content of the data structure. This separation allows the development of shape-polymorphic functions and their typing: the shape of the result of a shapepolymorphic function application depends only on the shape of the argument, not of its content. The same line is developed in the field of polytypic programming for algebraic data type [START_REF] Jeuring | Polytypic programming[END_REF]. MGS transformations are naturally polytypic and extend far beyond arrays and algebraic data type. Polytypism in MGS relies on a generic implementation of pattern matching [START_REF] Giavitto | Pattern-matching and rewriting rules for group indexed data structures[END_REF] not on overloading or ad-hoc polymorphism.

Transformations are a kind of rewriting that differs in many ways from graph rewriting. Their formalization in [START_REF] Spicher | Declarative mesh subdivision using topological rewriting in mgs[END_REF] is not based on the usual graph morphisms and pushouts like in [START_REF] Ehrig | Graph grammars: An algebraic approach[END_REF] but is inspired by the approach of J.-C. Raoult [START_REF] Raoult | Set-theoretic graph rewriting[END_REF] where graph rewriting based on a (multi-)set point of view is developed. The proposed model is close to term rewriting modulo associativity and commutativity (where the left hand side of a rule is removed and the right hand side is added). This kind of approach also allows to extend results from term rewriting to topological rewriting (as we did for termination in [START_REF] Giavitto | Software-Intensive Systems and New Computing Paradigms[END_REF]). Note that the notions of topological collection and topological rewriting are more general than labeled graphs and graph rewriting, and may handle higher dimensional objects, a feature relevant in a lot of application areas [START_REF] Tonti | On the mathematical structure of a large class of physicial theories[END_REF].

Nested data structure are now widespread in programming languages but are less natural in the context of data bases. The importance of organizing the accesses to the element in a complex structure trough primitive operations related to the type constructor is stressed in [START_REF] Buneman | Principles of programming with complex objects and collection types[END_REF]. In MGS, accesses rely on pattern matching, and the pattern matching constructs reflect the spatial structure underlying a collection. Nevertheless, structural recursion, advocated in [START_REF] Buneman | Principles of programming with complex objects and collection types[END_REF], is straightforward as showed by the programs in sections IV-A and IV-B.

VI. CONCLUSIONS AND FUTURE WORK

In this paper, we have presented the advantages of nesting in a spatial model of computation, the MGS experimental language. The language MGS, has been used in the context of P systems [START_REF] Giavitto | The topological structures of membrane computing[END_REF] and in several large modeling projects in systems biology [START_REF] Barbier De Reuille | Computer simulations reveal properties of the cell-cell signaling network at the shoot apex in Arabidopsis[END_REF], [START_REF]Modeling the topological organization of cellular processes[END_REF], [START_REF] Spicher | Understanding the Dynamics of Biological Systems: Lessons Learned from Integrative Systems Biology[END_REF].

One interest of the spatial paradigm à la MGS is its ability to subsume several computational models in a single uniform formalism, as long as one focuses on programming [START_REF] Michel | Rule-based programming for integrative biological modeling -application to the modeling of the lambda phage genetic switch[END_REF], [START_REF] Spicher | Understanding the dynamics of biological systems[END_REF]. We showed the benefits of considering nested spatial computing through three kind of examples: in algorithmic, in simulation of multiscale phenomena and in the emulation of other programming models.

The management of nested collections is achieved through three kinds of devices: 1) collections are first-citizen values and can be used as the values of another collection; 2) a specific pattern construction [ p | . . . ] makes possible, within the current pattern, to refer to the elements matched by a pattern p in a nested collection; 3) recursive type declarations generate predicates used to constrain the nesting and to control the pattern matching facilities.

These three features together enable a very concise and readable programming style, as exemplified in section III-D.

All the presented examples are actual MGS programs, at the exception of some slight syntactic sugar. The work presented in this paper may be enriched and extended in several directions. The pattern matching we have presented can be seen as operating at an "horizontal level" on the elements of a collection and at a "vertical level" when descending to match some elements of a nested collection. The constructions dedicated to the horizontal level are very expressive, allowing for example the matching of an unknown number of elements. The handling of the vertical level is actually restricted to the [ pat | . . . ] operator. Other construction can be designed, by analogy with the vertical level. For example, an operator to allow references through an unknown number of nesting, in a manner analog to the iteration operator " * ", would be interesting to mimic path queries in XML. Note however that the distinction between horizontal and vertical level is questionable. An alternative approach would be to unify the nested collection by looking for the spatial relationships holding in the whole structure, irrespectively of the horizontal or the vertical view. The topology of this "flat whole structure" can be build as the topology of a fiber space over the top collection. The investigation of this framework remains to be done.

  A. Disjunctive Normal Form Since the logical conjunction and disjunction operators are associative, commutative and idempotent, a logical formula can be encoded by nested sets. Let consider the following type declaration: type formula = string | Not | And | Or and record Not = { f:formula } and collection And = set[formula] and collection Or = set[formula]

  DNF = { ( * Simplifying unaries * ) [ [ x | ... ]:Not | ... ]:Not =⇒ x x:And / size(x) == 1 =⇒ choose(x) x:Or / size(x) == 1 =⇒ choose(x) ( * Flattening nested ops * ) [ f :And | g ]:And =⇒ join(f ,g) [ f :Or | g ]:Or =⇒ join(f ,g) ( * De Morgan's laws * ) [ x:Or | ... ]:Not =⇒ fold(::, And:(), map(λf { f = f }, x)) [ x:And | ... ]:Not =⇒ fold(::, Or:(), map(λf { f = f }, x)) ( * Distributivity * ) [ x:Or | s ]:And =⇒ map(λf f ::s, x) ( * Induction * ) x:And =⇒ DNF (x)

type

  Token = int | 'nul | 'exch | ... and collection Fraglet = seq[Token] and collection State = bag[Fraglet]

Table I SUBSET

 I OF THE FRAGLETS CORE INSTRUCTIONS (FROM[START_REF] Tschudin | Fraglets-a metabolistic execution model for communication protocols[END_REF]) AND THEIR MGS TRANSLATION.

ACKNOWLEDGMENTS

The authors would like to thanks H. Klaudel, F. Pommereau, F. Delaplace and J. Cohen for many questions, encouragements and sweet cookies. This research is supported in part by the ANR projects SynBioTIC.