Signatures et modèles pour la syntaxe et la sémantique opérationnelle en présence de liaison de variables

Cette thèse traite de la spécification et la construction de la syntaxe et sémantique opérationnelle d’un langage de programmation. Nous travaillons avec une notion générale de “signature” pour spécifier des objets d’une catégorie donnée comme des objets initiaux dans une catégorie appropriée de modèles. Cette caractérisation, dans l’esprit de la sémantique initiale, donne une justification du principe de récursion. Les languages avec liaisons, telles que le lambda calcul pur, sont des monades sur la catégorie des ensembles spécifiées parles signatures algébriques classiques. Les premières extensions de syntaxes avec des équations que nous considérons sont des“quotients” de ces signatures algébriques. Ils permettent, par exemple, de spécifier une opération commutative binaire. Cependant, certaines équations, comme l’associativité, semblent hors d’atteinte. Ceci motive la notion de 2-signature qui complète la définition précédente avec la donnée d’un ensemble d’équations. Nous identifions la classe des “2-signatures algébriques” pour lesquelles l’existence de la syntaxe associée est garantie. Finalement, nous abordons la spécification de la sémantique opérationnelle d’un langage de programmation tel que le lambda calcul avec β-réduction. Nous introduisons à cette fin la notion de monade de réduction et leur signatures, puis les généralisons pour aboutir à la notion de monade opérationnelle.This thesis deals with the specification and construction of syntax and operational semantics of a programming language. We work with a general notion of “signature” for specifying objects of a given category as initial objects in a suitable category of models. This characterization, in the spirit of Initial Semantics, gives a justification of the recursion principle.Languages with variable binding, such as the pure lambda calculus, are monads on the category of sets specified through the classical algebraic signatures. The first extensions to syntaxes with equations that we consider are“quotients” of these algebraic signatures. The yallow, for example, to specify a binary commutative operation. But some equations, such as associativity, seem to remain out of reach. We thus introduce the notion of 2-signature, consisting in two parts: a specification of operations through a usual signature as before, and a set of equations among them. We identify the class of “algebraic 2-signatures” for which the existence of the associated syntax is guaranteed. Finally, we takle the specification of the operational semantics of a programming language such as lambda calculus with β-reduction. To this end, we introduce the notion of reduction monad and their signatures, then we generalize them to get the notion of operational monad