Représentation et manipulation de structures topologiques dans un langage fonctionnel

摘要

Le calcul spatial est un domaine de recherche qui vise à développer des formalismes, des langages et des architectures matérielles qui permettent d'appréhender la notion d'espace en informatique. Nous présentons MGS, un langage de programmation déclaratif dédié à la représentation et à la manipulation de structures spatiales arbitrairement complexes. Afin d'atteindre ce but, nous avons mis en place un formalisme de calcul non conventionnel fondé sur deux notions, les collections topologiques, une nouvelle structure de données reposant sur la notion de complexe cellulaire développée en topologie algébrique, et les transformations, une forme originale de définition par cas de fonctions pour manipuler par réécriture locale des collections topologiques. Nous illustrons ce formalisme en décrivant la représentation à l'aide des collections topologiques d'une classe particulière d'espaces, les quasi-variétés, et en implantant avec des transformations un algorithme classique de raffinement de maillages.%Spatial computing is a research field that is aimed at developing formalisms, languages and architectures in order to take into account the notion of space in computer science. We present MGS, a programming language dedicated to the representation and the handling of arbitrary complex spatial organizations. To achieve this goal, we define an unconventional formalism based on two notions: topological collections, a new data structure relying on the notion of cellular complex developed in algebraic topology, and transformations, an original kind of case-based definition of functions to handle topological collections by rewriting. We illustrate this formalism by describing the representation in terms of topological collections a particular class of spaces, the quasi-manifolds, and by implementing with transformations a standart mesh refinement algorithm.