Cette thèse s'articule autour de la gestion de ressources explicites dans les langages fonctionnels, en mettant l'accent sur des propriétés de calculs avec substitutions explicites raffinant le lambda-calcul. Dans une première partie, on s'intéresse à la propriété de préservation de la beta-normalisation forte (PSN) pour le calcul lambda s. Dans une seconde partie, on étudie la propriété de confluence pour un large ensemble de calculs avec substitutions explicites. Après avoir donné une preuve générique de confluence basée sur une série d'axiomes qu'un calcul doit satisfaire, on se focalise sur la métaconfluence de lambda j, un calcul où le mécanisme de propagation des substitutions utilise la notion de multiplicité, au lieu de celle de structure. Dans la troisième partie de la thèse on définit un prisme des ressources qui généralise de manière paramétrique le lambda-calcul dans le sens où non seulement la substitution peut être explicite, mais également la contraction et l'affaiblissement. Cela donne un ensemble de huit calculs répartis sur les sommets du prisme pour lesquels on prouve de manière uniforme plusieurs propriétés de bon comportement comme par exemple la simulation de la beta-réduction, la PSN, la confluence, et la normalisation forte pour les termes typés. Dans la dernière partie de la thèse on montre différentes ouvertures vers des domaines plus pratiques. On s'intéresse à la complexité d'un calcul avec substitutions en premier lieu. On présente des outils de recherche et on conjecture des bornes maximales. Enfin, on finit en donnant une spécification formelle du calcul lambda j dans l'assistant à la preuve Coq.

Dans les langages fonctionnels, l'efficacité dépend crucialement du choix de la stratégie d'évaluation et d'un modèle d'implantation adapté. Nous développons d'abord un λ-calcul avec substitutions explicites qui évite les problèmes habituels liés à la substitution et à l'α-conversion, dans lequel on peut définir les stratégies usuelles, mais aussi des stratégies avec un meilleur partage de calcul. Ensuite, nous développons un modèle d'implantation efficace pour ce calcul. Pour cela, nous proposons une représentation innnovante des variables libres, d'abord dans le cadre très général de la récriture d'ordre supérieur, puis avec plus de détails dans notre cas particulier. Nous obtenons ainsi un λ-calcul avec substitutions explicites sans noms ni indices, dans lequel les te! rmes sont annotés avec de l'information qui indique comment les substitutions doivent être propagées, et qui constitue un modèle d'implantation efficace pour nos stratégies. Des machines abstraites sont alors définies, implantées et comparées expérimentalement aux meilleurs évaluateurs connus. Finalement, nous étudions les relations entre machines abstraites traditionnelles et réseaux d'interaction, deux modèles d'implantation courants mais très différents. Plus précisément, nous montrons comment certaines stratégies peuvent être implantées dans les réseaux d'interaction d'une façon très naturelle, rapprochant ainsi deux modèles utilisés pour l'implantation de stratégies efficaces.

Les substitutions explicites ont été introduites comme un raffinement du lambda-calcul, celui-ci étant le<br />formalisme utilisé pour étudier la sémantique des langages de programmation. L'objet de cette thèse<br />est l'étude de leurs propriétés de normalisation forte et de préservation de la normalisation forte. Ce<br />manuscrit rend compte de plusieurs travaux autour de ces propriétés de normalisation, regroupés en<br />trois volets.<br /><br />Le premier d'entre eux formalise une technique générale de preuve de normalisation forte utilisant<br />la préservation de la normalisation forte. On applique cette technique à un spectre assez large de calculs<br />avec substitutions explicites afin de mesurer les limites de son utilisation. Grâce à cette technique, on<br />prouve un résultat nouveau : la normalisation forte du lambda-upsilon-calcul simplement typé.<br /><br />Le deuxième travail est l'étude de la normalisation d'un calcul symétrique non-déterministe issu de<br />la logique classique formulée dans le calcul des séquents, auquel est ajouté des substitutions explicites.<br />La conjonction des problèmes posés par les calculs symétriques et ceux posés par les substitutions<br />explicites semble vouer à l'échec l'utilisation de preuves par réductibilité. On utilise alors la technique<br />formalisée dans le premier travail, ce qui nous demande de prouver tout d'abord la préservation de la<br />normalisation forte. A cette fin, on utilise un fragment de la théorie de la perpétuité dans les systèmes<br />de réécriture.<br /><br />La définition d'une nouvelle version du lambda-ws-calcul avec nom, le lambda-wsn-calcul, constitue le troisième<br />volet de la thèse. Pour prouver sa normalisation forte par traduction et simulation dans les réseaux<br />de preuve, on enrichit l'élimination des coupures de ceux-ci avec une nouvelle règle, ce qui nous oblige<br />à prouver que cette nouvelle notion de réduction est fortement normalisante.

Cette thèse étudie les propriétés calculatoires des présentations d'opérades, ou systèmes de réécriture de diagrammes de Penrose, et leurs liens avec divers types de systèmes de réécriture classiques. Grâce à des nouveaux critères pour la terminaison et la confluence, on démontre la conjecture sur la convergence de la présentation L(Z2) des Z/2Z-espaces vectoriels, une théorie équationnelle commutative. On montre que les présentations d'opérades sont des généralisations des systèmes de réécriture de mots et des réseaux de Petri et qu'elles fournissent un calcul de gestion explicite des ressources pour les systèmes de réécriture de termes linéaires à gauche. Enfin, on étudie les obstructions à ce même résultat concernant le lambda-calcul. Des annexes présentent les liens entre les opérades et d'autres structures de l'algèbre universelle, ainsi qu'un calcul de substitutions explicites.