[PDF] SÉMANTIQUES ET SYNTAXES VECTORIELLES LA LOGIQUE

View - Download SÉMANTIQUES ET SYNTAXES VECTORIELLES LA LOGIQUE

Previous PDF

Next PDF

UNIVERSITÉPARISDIDEROT- PARIS7

École doctorale

Sciences Mathématiques de Paris CentreTHÈSE

pour l"obtention du diplôme de

DOCTEUR DE L"UNIVERSITÉ PARIS DIDEROT

SpécialitéINFORMATIQUE

SÉMANTIQUES ET SYNTAXES VECTORIELLES

DE

LA LOGIQUE LINÉAIRE

Présentée et soutenue publiquement par

Christine TASSON

le 4 décembre 2009, devant le jury composé de

Président du jury: Martin HYLAND

Directeurs de thèse: Pierre-Louis CURIEN

Thomas EHRHARD

Rapporteurs: Yves LAFONT

Thomas STREICHER

Examinateurs: Olivier LAURENT

Damiano MAZZA

ii

REMERCIEMENTSJe voudrais commencer par remercier mes directeurs de thèse. C"est avec une grande gé-

nérosité que Thomas Ehrhard a partagé avec moi sa profonde vision scientifique ainsi que ses

recherches. J"espère que notre collaboration ne s"arrêtera pas avec cette thèse. Jamais avare

de son temps et de son expérience, Pierre-Louis Curien m"a guidée et aidée dans toutes les pistes que j"ai suivies. Leur tandem de choc m"a ouvert la voie dans le monde passionnant de la recherche. Je remercie Yves Lafont et Thomas Streicher d"avoir accepté de rapporter ma thèse, ainsi que d"avoir lu mon manuscrit avec tant d"attention. Je suis très heureuse que Martin Hyland, Olivier Laurent et Damiano Mazza aient accepté de faire partie de mon jury. Je les remercie plus particulièrement pour les discussions que nous avons pu avoir au cours de mes années de doctorat. Je tiens aussi à dire un grand merci à Lionel, Alexis, Pierre, Michele, Nicolas et Samy qui

ont relu les versions préliminaires de cette thèse et dont les questions, remarques et encourage-

ments m"ont permis de mener ce travail à bien. Depuis mes premiers pas dans le monde de la recherche, j"ai croisé beaucoup de chercheurs et professeurs qui m"ont inspirée et fait aimer ce métier : Rick Blute, Ryu Hasegawa, Jacques Garrigues, Christian Urban, Hubert Comon-Lundh, Michel Cognet... Je les en remercie. Un grand merci à Odile, Audrey et Michèle pour leur efficacité, ainsi que pour la bonne humeur qu"elles distillent quotidiennement

Je tiens aussi à remercier mes collègues et amis sans qui ces trois années auraient été bien

fades : Lionel et Pierre, que je ne pourrai jamais trop remercier pour leur amour des navettes,

leur goût pour les espaces de finitude, pour leur accueil généreux, ainsi que pour la recette de

notre pain quotidien; Michele et Daniel avec qui j"ai passé des heures à dessiner des triangles

et des traits au tableau; Benjamino et Irene qui m"ont fait découvrir la meilleure glace de Rome; Nico, Sam, Malo, Sylvain et la loge; Lisa, Mathilde et Sarah; Séverine, de Bari à Cerisy que de souvenirs; la bande du 6C12 Sylvain, Sam, Fabien, Raph et Pasquale; Marie, la Suède, la course et les macarons; Barabara et sa bonne humeur; Joachim et son théatre; Gim et

ses rollers; Pierre et noir dés"; Grégoire, Medhi, Stéphane, Jonas, Thibaud, Stéphane, Antoine,

Guillaume...

Ce travail n"aurait pas pu être mené à bien sans soupape de dépressurisation. Je tiens donc

à remercier Alain, Francis et les autres du subaqua de m"avoir initiée à la sagesse de l"apnée.

Merci aussi à William et à Valérie de m"avoir accueillie avec une telle générosité dans le monde

artistique de la coiffure. Merci aussi à tous les cobayes qui sont passés sous mon peigne et mes ciseaux pendant ces trois années : Sam (indomptable), Marie (quelle masse), Nicolas iii

REMERCIEMENTS(presque crépu), Sam (dont les blagues défrisent même à 7h45), Séverine (glamour), Paolo

(crête), Michel (stylé), Paolo (la mêche), Pierre-Louis (sourcilleux), Sylvain (Brad Pitt), Gim

(semi rasé), Barbara (triangulée), Claire (blond suédois), Mathilde (quelle couleur), Lisa (même

pas peur), Alexandre (ondulant), Julius (CAP), Raph (comme sur la photo qui fait moins d"un centimètre carré), Amélie, Fabien, Faten, Alice... Last but not least, merci à mes amis Rachel, Alice et Cédric et à ma famille récemment

élargie. Mes derniers remerciements sont évidemment pour Alain à qui je dédie ce manuscrit.

iv

TABLE DES MATIÈRESIntroduction1

I Prélude : la logique linéaire

7

I.1 Syntaxe

8

I.2 Sémantique

12

I.3 Orthogonalité

25

A Sémantique

37

Introduction

39

II Espaces de finitude relationnels

43

II.1 Généralités

44

II.2 Structure additive, limites et co-limites

51

II.3 Structure multiplicative

56

II.4 Structure exponentielle

58

III Espaces de Lefschetz

67

III.1 Topologies linéaires

71

III.2 Structure additive, limites et co-limites

93

III.3 Structure multiplicative

103

III.4 Structure exponentielle

157
v

TABLE DES MATIÈRESB Syntaxe173

Introduction

175

IV Totalité dans les espaces de finitude

179

IV.1 Rappels sur les espaces de finitude

180
IV.2 Extensions du-calcul. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

IV.3 Étude sémantique de la totalité

186
IV.4-calcul barycentrique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

V Développement de Taylor dans les réseaux

203

V.1 Logique linéaire différentielle

205
V.2 Développement de Taylor pour le-calcul. . . . . . . . . . . . . . . . . . . . 208

V.3 Réseaux

212
V.4 Réciproque du développement de Taylor syntaxique 220

Perspectives

249

Bibliographie

256

Table des figures

257

Index261

vi

INTRODUCTIONCette thèse propose une exploration des sémantiques vectorielles de la logique linéaire. Elle

contribue à l"étude sémantique et syntaxique de la formule de Taylor. Programmes et preuves.Il peut paraître à première vue étrange de mélanger logique et langages de programmation. En fait, ces deux domaines parlent des mêmes objets avec des points de vue différents.

Intuitivement, la démonstration d"un théorème mathématique, c"est-à-dire d"une formule

logique, fournit un algorithme permettant d"obtenir la conclusion du théorème à partir de ses

hypothèses. Ainsi, la preuve de toute formule possède un contenu informatique.

Réciproquement, un programme induit une démarche répondant à un problème (par exemple,

calculer un résultat, vérifiant une propriété spécifiée, à partir d"une donnée d"un certain type).

Cette démarche peut être vue comme un enchaînement d"étapes logiques qui fournissent une preuve de la formule spécifiant le programme. On peut donc parler de façon équivalente de programmes comme de preuves. De plus, cette correspondance s"étend au niveau calculatoire. Plus précisément, en logique,

l"élimination des coupures est l"opération qui consiste à remplacer les lemmes utilisés dans une

démonstration par leur preuvemutatis mutandis. On obtient ainsi une preuve indépendante de tout autre résultat. En informatique, cette opération revient à remplacer dans un programme tous les appels à des procédures externes par leur codemutatis mutandis.

En résumé, les trois niveaux d"une logique - formules, règles de déduction et élimination des

coupures - sont respectivement en correspondance avec les trois éléments des langages de programmation typés - système de types, règles de typage et évaluation des programmes. On appelle cette correspondance entre la logique et les langages de programmation l"iso- morphisme deCurry-Howard[How80]. Sémantique.Par définition, la sémantique apporte un sens aux syntaxes de la logique et des langages de programmation. Nous allons voir qu"en retour, ces syntaxes nourrissent la séman- tique. En logique, la sémantique permet de donner un sens aux formules ainsi que des indications sur leurs propriétés et sur l"existence d"une preuve. En informatique, la sémantique permet d"une part d"étudier le comportement des pro- grammes - on parle de sémantiqueopérationnelle- et d"autre part de leur donner un sens 1

INTRODUCTIONmathématique puis de s"en servir pour étudier leurs propriétés au cours de leur évaluation par

la machine - on parle de sémantiquedénotationnelle. Mais la sémantique n"est pas seulement un outil pour étudier les syntaxes de la logique ou des langages de programmation. Les relations entre la sémantique et la syntaxe sont bien plus riches. D"une part, elle fournit des outils mathématiques pour raisonner sur les programmes. D"autre part, elle permet en partant de notions mathématiques, de raffiner ou étendre la syntaxe des langages de programmation informatique de manière inédite. Le plus bel exemple de ce phéno- mène étant la logique linéaire décrite au paragraphe suivant.

La complétude dénotationnelle est une situation où la sémantique capture les propriétés

d"une syntaxe. Pour aboutir à ce genre de résultat, on peut restreindre la sémantique d"un lan-

gage afin de capturer et de décrire au mieux ses propriétés. À l"inverse, on peut étendre le langage de programmation pour que l"interprétation des pro- grammes atteignent plus de construction de sa sémantique. C"est ainsi que de nouveaux lan- gages de programmation peuvent émerger d"études sémantiques.

D"un côté, on aura transformé une structure syntaxique en une structure mathématique et de

l"autre, on aura créé une syntaxe reflétant une structure mathématique. D"une manière générale, les langages de programmation sont introduits pour répondre

à des besoins pratiques. Leur étude sémantique peut faire émerger de nouvelles structures

mathématiques ou plus modestement apporter un nouveau point de vue sur des structures

déjà existantes. Inversement, certaines sémantiques, assez éloignées des syntaxes usuelles,

apporteront de nouvelles caractéristiques aux langages de programmation. Logique linéaire.L"histoire de la logique linéaire illustre ce va-et-vient entre la syntaxe et la sémantique.

Elle a été introduite à la suite de l"étude sémantique d"un langage de programmation (le

-calcul avec second ordre [Gir86]). En étudiant ce modèle (les espaces cohérents), Girard a

constaté que tout espace interprétant une implication peut être obtenu en deux étapes résultant

de l"interprétation de deux nouveaux opérateurs (l"exponentielle et l"implication linéaire). Gi-

rard a alors introduit une nouvelle logique dans laquelle l"implication est remplacée par ces deux opérateurs [ Gir87 La décomposition de l"implication dans la logique linéaire s"interprète algorithmiquement en termes de gestion des ressources informatiques. En effet, lors d"un calcul, le nombre d"uti- lisations d"un argument peut varier. En logique linéaire, au lieu d"octroyer à un programme un accès infini à l"argument, on va former un paquet contenant potentiellement une infinité de copies de cet argument (son exponentielle) et le fournir à un programme (dit linéaire) qui consulte une seule fois son argument, c"est-à-dire ce paquet. La logique linéaire peut donc se comprendre comme une logique des ressources informatiques.

Née d"une étude sémantique, la logique linéaire a à son tour fait l"objet d"études séman-

tiques. Chacune de ces études a apporté un éclairage différent sur la logique linéaire.

D"une part, la sémantique quantitative [

Gir88 ], introduite afin d"interpréter des programmes 2

Introduction

non déterministes ou probabilistes, permet de mieux comprendre la gestion des ressources dans

la logique linéaire. En effet, même si cette sémantique a été introduite avant la logique linéaire,

elle en forme un modèle [ Has02 ]. Dans ce modèle, les types sont interprétés par des ensembles et les programmes par des foncteurs analytiques [ Joy86 ] (l"équivalent catégorique des séries

entières). L"interprétation d"un programme peut notamment être décomposée en une somme de

polynômes homogènes (à une traduction près de ces notions dans la catégorie des ensembles).

Dans les langages de programmation, un polynôme homogène de degréncorrespond à un pro- gramme qui utilise exactementnfois son argument. La décomposition d"un programme en sé-

ries formelles revient donc à récrire le programme en associant à chaque entiernun algorithme

effectuant exactementnappels à la ressource. On appelle cette décompositionla formule de Taylor syntaxique[ER08]; elle correspond dans la sémantique, au développement en série de

Taylor.

Par ailleurs, plusieurs axiomatisations catégoriques ont été proposées afin de caractériser les

modèles de la logique linéaire [ See89 Bie95 Ben95 ]. Celles-ci ont permis de mettre en évi- dence deux univers dans la logique linéaire. Le premier est le mondelinéairedans lequel les

ressources doivent toutes être utilisées exactement une fois. Le second estnon-linéaire, les res-

sources de ce monde peuvent être effacées et dupliquées. De plus, il existe un passage entre

ces deux mondes à travers un opérateur nomméexponentiellecar il permet de transformer le linéaire en non-linéaire. Enfin, dans les langages de programmation, on considère parfois que"l"interaction entre un programme et son environnement est réversible». Lorsqu"elle est transposée en logique via

l"isomorphisme de Curry-Howard, cette propriété est appeléedualité1. Elle est centrale en lo-

gique linéaire. La sémantique des jeux [ AM99 ] et la ludique [ Gir01 ] se sont ainsi attachées

à l"étude des interactions entre entrées/sorties d"un programme, questions/réponses d"un dia-

logue. Soulignons que si les jeux ont une origine antérieure à la logique linéaire, ils ont été

largement développés suite à son introduction. Ils ont notamment offert une solution au pro-

quotesdbs_dbs24.pdfusesText_30

[PDF] Inches To Millimeter Conversion Chart - WalzCraft

[PDF] Unités: volumes, conversions Quoique le litre est communément

[PDF] calculs conversion d 'unites - Pharmacie des HUG

[PDF] calculs conversion d unites - Pharmacie des HUG

[PDF] Cours des réseaux Informatiques

[PDF] guerre d 'algérie et manuels algériens de langue arabe - Cairn

[PDF] Plan de toulouse Centre - Toulousefr

[PDF] UNIVERSITE PARIS 13 Référence GALAXIE : 4271

[PDF] Calendrier 2017 - Premier Semestre - iCalendrier

[PDF] Calendrier 2018 - Premier Semestre - iCalendrier

[PDF] STÉ

[PDF] Dictionnaire universel de medecine (etc) - Résultats Google Recherche de Livres

[PDF] CAPÍTULO II LA ORGANIZACIÓN 21 Concepto - Biblioteca UDEP

[PDF] El sistema de producción y operaciones - Nulan

[PDF] Les différents types de fournisseurspdf