Embed Size (px)
Citation preview
Introduction Les catégories La pratique Applications informatiques Conclusion
LA THÉORIE DES CATÉGORIESQU’EST-CE QUE C’EST ? QUEL INTÉRÊT EN INFORMATIQUE ?
Romuald THION
Liris – Équipe BD
Vendredi 22 avril 2011
R. Thion Théorie des catégories 1
Introduction Les catégories La pratique Applications informatiques Conclusion
Plan
1 Introduction
2 Les catégories
3 La pratique
4 Applications informatiques
5 Conclusion
R. Thion Théorie des catégories 2
Introduction Les catégories La pratique Applications informatiques Conclusion
1 Introduction
2 Les catégories
3 La pratique
4 Applications informatiques
5 Conclusion
R. Thion Théorie des catégories 3
Introduction Les catégories La pratique Applications informatiques Conclusion
Disclaimer
R. Thion Théorie des catégories 4
Introduction Les catégories La pratique Applications informatiques Conclusion
Pourquoi cet exposé ?
La théorie des catégoriesmaths contemporaines (post Bourbaki)cadre assez peu connu, voire ésotériqueintellectuellement séduisant
Intérêt pour les informaticienscadre fortement typédémarche constructivespécification versus implémentation
Un outil majeur de l’informatique théorique. . .. . . Qui aurait sa place en bases de données ?
R. Thion Théorie des catégories 5
Introduction Les catégories La pratique Applications informatiques Conclusion
Pourquoi cet exposé ?
La théorie des catégoriesmaths contemporaines (post Bourbaki)cadre assez peu connu, voire ésotériqueintellectuellement séduisant
Intérêt pour les informaticienscadre fortement typédémarche constructivespécification versus implémentation
Un outil majeur de l’informatique théorique. . .. . . Qui aurait sa place en bases de données ?
R. Thion Théorie des catégories 5
Introduction Les catégories La pratique Applications informatiques Conclusion
Pourquoi cet exposé ?
La théorie des catégoriesmaths contemporaines (post Bourbaki)cadre assez peu connu, voire ésotériqueintellectuellement séduisant
Intérêt pour les informaticienscadre fortement typédémarche constructivespécification versus implémentation
Un outil majeur de l’informatique théorique. . .. . . Qui aurait sa place en bases de données ?
R. Thion Théorie des catégories 5
Introduction Les catégories La pratique Applications informatiques Conclusion
Présentation informelle
Une catégorie comme. . .une structure algèbriqueun cadre où faire des mathématiquesune alternative aux ensembles
Dana S. Scott – Relating theories of the λ-calculus (1980)What we are probably seeking is a “purer” view of functions : a theoryof functions in themselves, not a theory of functions derived from sets.What, then, is a pure theory of functions ?Answer : category theory.
R. Thion Théorie des catégories 6
Introduction Les catégories La pratique Applications informatiques Conclusion
Présentation informelle
Une catégorie comme. . .une structure algèbriqueun cadre où faire des mathématiquesune alternative aux ensembles
Dana S. Scott – Relating theories of the λ-calculus (1980)What we are probably seeking is a “purer” view of functions : a theoryof functions in themselves, not a theory of functions derived from sets.What, then, is a pure theory of functions ?Answer : category theory.
R. Thion Théorie des catégories 6
Introduction Les catégories La pratique Applications informatiques Conclusion
1 Introduction
2 Les catégories
3 La pratique
4 Applications informatiques
5 Conclusion
R. Thion Théorie des catégories 7
Introduction Les catégories La pratique Applications informatiques Conclusion
Une catégorie C
d’une collection d’objets : A,B,C . . .d’une collection de morphismes (ou flèches) : f, g, h . . .pour chaque morphisme, un domaine (dom) et un codomaine(cod) : f : A→ B (fortement typé)d’une opération de composition associant à chaque paire demorphismes f et g telles que cod(f) = dom(g) un morphismeg f : dom(f)→ cod(g)
Satisfaisant les deux conditions suivantes
1 la composition est associative : (h g) f = h (g f)
2 pour chaque objet A, un morphisme identité idA : A→ A t.q.pour tout f : A→ B on ait idB f = f et f idA = f
Et rien d’autre . . .
R. Thion Théorie des catégories 8
Introduction Les catégories La pratique Applications informatiques Conclusion
Une catégorie C
d’une collection d’objets : A,B,C . . .d’une collection de morphismes (ou flèches) : f, g, h . . .pour chaque morphisme, un domaine (dom) et un codomaine(cod) : f : A→ B (fortement typé)d’une opération de composition associant à chaque paire demorphismes f et g telles que cod(f) = dom(g) un morphismeg f : dom(f)→ cod(g)
Satisfaisant les deux conditions suivantes
1 la composition est associative : (h g) f = h (g f)
2 pour chaque objet A, un morphisme identité idA : A→ A t.q.pour tout f : A→ B on ait idB f = f et f idA = f
Et rien d’autre . . .
R. Thion Théorie des catégories 8
Introduction Les catégories La pratique Applications informatiques Conclusion
ExemplesBestiaire
Catégorie Objets Morphismes
Set ensembles fonctions totalesPfn ensembles fonctions partiellesRel ensembles relations binairesMon monoïdes homomorphismes de monoïdesGrp groupes homomorphismes de groupesΩ-Alg Ω-algèbres Ω-homomorphismesPos posets fonctions de monotonesCPO posets complets fonctions continues
Des implémentations de la définition de catégorieToutes ces catégories sont concrètes :
les objets sont des ensembles munis de structures.
R. Thion Théorie des catégories 9
Introduction Les catégories La pratique Applications informatiques Conclusion
ExemplesBestiaire
Catégorie Objets Morphismes
Set ensembles fonctions totalesPfn ensembles fonctions partiellesRel ensembles relations binairesMon monoïdes homomorphismes de monoïdesGrp groupes homomorphismes de groupesΩ-Alg Ω-algèbres Ω-homomorphismesPos posets fonctions de monotonesCPO posets complets fonctions continues
Des implémentations de la définition de catégorieToutes ces catégories sont concrètes :
les objets sont des ensembles munis de structures.
R. Thion Théorie des catégories 9
Introduction Les catégories La pratique Applications informatiques Conclusion
Pour ou contre ?
En défaveurtrop abstrait (abstract nonsense)poids notationnel accablantrien de plus que dans Set (fondamentalement)
En faveurse débarasser des « détails » de Set
« penser transformations »généraliser et réutiliser des constructions
R. Thion Théorie des catégories 10
Introduction Les catégories La pratique Applications informatiques Conclusion
Pour ou contre ?
En défaveurtrop abstrait (abstract nonsense)poids notationnel accablantrien de plus que dans Set (fondamentalement)
En faveurse débarasser des « détails » de Set
« penser transformations »généraliser et réutiliser des constructions
R. Thion Théorie des catégories 10
Introduction Les catégories La pratique Applications informatiques Conclusion
1 Introduction
2 Les catégories
3 La pratique
4 Applications informatiques
5 Conclusion
R. Thion Théorie des catégories 11
Introduction Les catégories La pratique Applications informatiques Conclusion
Pratique des catégories
Particularités de la pratique1 définition et raisonnement sur les morphismes2 rôle de l’unicité (l’universalité, la canonicité, l’optimalité . . . )3 utilisation de diagrammes pour décrire les propriétés4 abstraction de constructions ou propriétés sur des objets connus
Processus de catégorisationPasser de = (en algèbre) à ∼= (via morphismes)
La construction est « réussie » si on retrouve les mêmes lois
R. Thion Théorie des catégories 12
Introduction Les catégories La pratique Applications informatiques Conclusion
1. Raisonner sur les morphismesDémarche constructive
On ne considère jamais l’égalité entre objets,seulement entre les morphismes.
Objet terminalUn C-objet 1 est terminal si, pour tout C-objet A il existe un uniquemorphisme noté ! : A→ 1
On caractérise un objet via ses morphismes.
Isomorphismef : A→ B est un isomorphisme si il existe g : B → A tel quef g = idB et g f = idA.
Intuitivement, une transformation réversible qui préserve la structure.
R. Thion Théorie des catégories 13
Introduction Les catégories La pratique Applications informatiques Conclusion
1. Raisonner sur les morphismesDémarche constructive
On ne considère jamais l’égalité entre objets,seulement entre les morphismes.
Objet terminalUn C-objet 1 est terminal si, pour tout C-objet A il existe un uniquemorphisme noté ! : A→ 1
On caractérise un objet via ses morphismes.
Isomorphismef : A→ B est un isomorphisme si il existe g : B → A tel quef g = idB et g f = idA.
Intuitivement, une transformation réversible qui préserve la structure.
R. Thion Théorie des catégories 13
Introduction Les catégories La pratique Applications informatiques Conclusion
2. Rôle de l’unicité
PropositionLes objets terminaux d’une catégorie sont isomorphes.
(Preuve) Soient A et B terminaux, et !A : A→ B et !B : B → A lesuniques morphismes entre ces objets.!A et !B sont composables : !B!A : A→ A. Or idA : A→ A existe(axiome) et est l’unique morphisme A→ A, car A est terminal. Donc,!B!A = idA.Similairement pour !A!B = idB : A sont B isomorphes.
Il n’y a (catégoriquement) aucun intérêt à distinguer les terminauxentre eux.
R. Thion Théorie des catégories 14
Introduction Les catégories La pratique Applications informatiques Conclusion
3. Diagrammes commutatifs
« Le carré commute »G(f) ηA = ηB F (f)
R. Thion Théorie des catégories 15
Introduction Les catégories La pratique Applications informatiques Conclusion
3. Diagrammes commutatifs
« Le carré commute »G(f) ηA = ηB F (f)
R. Thion Théorie des catégories 15
Introduction Les catégories La pratique Applications informatiques Conclusion
4. Intuition dans Set
Produit cartésien : A×B = (a, b) | a ∈ A ∧ b ∈ BComment définir le produit sans faire intervenir ∈, en considérant
uniquement des transformations (fonctions) entre objets (ensembles) ?
première projection π1 : A×B → Aseconde projection π2 : A×B → Bla structure (A×B, π1, π2) est optimalequelques soient f : C → A et g : C → B on peut construire〈f, g〉 : C → A×B définie par 〈f, g〉(x) = (f(x), g(x))
R. Thion Théorie des catégories 16
Introduction Les catégories La pratique Applications informatiques Conclusion
1 Introduction
2 Les catégories
3 La pratique
4 Applications informatiques
5 Conclusion
R. Thion Théorie des catégories 17
Introduction Les catégories La pratique Applications informatiques Conclusion
Applications informatiquesA categorical manifesto (Joseph Goguen)“This paper tries to explain why and how category theory is useful incomputing science, by guiving guidelines for applying seven basic categoricalconcepts : category, functor, natural transformation, limit, adjoint, colimit andcomma category. Somes examples, intuition, and references are given foreach concept, but completeness is not attempted.”
Utilisationsthéorie des graphes (catégorie ≈ algèbre des chemins)théorie des automates (systèmes et comportement, bisimulation)théorie des types (polymorphisme)programmation fonctionnelle (modèles du λ-calcul, effets)substitutions de variables et unificationsystèmes de réécriture
R. Thion Théorie des catégories 18
Introduction Les catégories La pratique Applications informatiques Conclusion
Applications informatiquesA categorical manifesto (Joseph Goguen)“This paper tries to explain why and how category theory is useful incomputing science, by guiving guidelines for applying seven basic categoricalconcepts : category, functor, natural transformation, limit, adjoint, colimit andcomma category. Somes examples, intuition, and references are given foreach concept, but completeness is not attempted.”
Utilisationsthéorie des graphes (catégorie ≈ algèbre des chemins)théorie des automates (systèmes et comportement, bisimulation)théorie des types (polymorphisme)programmation fonctionnelle (modèles du λ-calcul, effets)substitutions de variables et unificationsystèmes de réécriture
R. Thion Théorie des catégories 18
Introduction Les catégories La pratique Applications informatiques Conclusion
Une application « grand public »
Catégories et programmation fonctionnelleobjet = typee.g., Bool, Int, Unitmorphismes = fonctionse.g., not : Bool→ Bool
morphismes 1→ A = constantes de type Ae.g., true, false : Unit→ Bool
équations = même fonctions d’après la sémantique du languagee.g., false = not trueendo-foncteurs = constructeurs de typese.g., List : C→ C
transformations naturelles = fonctions polymorphiquese.g., revA : List(A)→List(A)
R. Thion Théorie des catégories 19
Introduction Les catégories La pratique Applications informatiques Conclusion
Une application « grand public »
Notions of computation and monads (Eugenio Moggi)monade : une construction catégorique< F : C→ C, η : 1C→F, µ : F F→F >
utilisé dans le langage Haskellun sucre spécifique, commun à toutes les instances
Effets en programmation fonctionnellepartialité : F (A) = A+ 1
exceptions : FE(A) = A+ E
non-déterminisme : F (A) = A?
gestion d’états : FS(A) = (S ×A)S
lecteur : FE(A) = AE
R. Thion Théorie des catégories 20
Introduction Les catégories La pratique Applications informatiques Conclusion
Une application « grand public »
Notions of computation and monads (Eugenio Moggi)monade : une construction catégorique< F : C→ C, η : 1C→F, µ : F F→F >
utilisé dans le langage Haskellun sucre spécifique, commun à toutes les instances
Effets en programmation fonctionnellepartialité : F (A) = A+ 1
exceptions : FE(A) = A+ E
non-déterminisme : F (A) = A?
gestion d’états : FS(A) = (S ×A)S
lecteur : FE(A) = AE
R. Thion Théorie des catégories 20
Introduction Les catégories La pratique Applications informatiques Conclusion
1 Introduction
2 Les catégories
3 La pratique
4 Applications informatiques
5 Conclusion
R. Thion Théorie des catégories 21
Introduction Les catégories La pratique Applications informatiques Conclusion
Quid des bases de données ?
Data Base Mappings and Monads : (Co)Induction (Zoran Majkic)“Thus DB category, as a base category for the semantics of databases andmappings between them, is different from the Set category used dominantlyfor such issues, and needs the full investigation of its properties.”
Simplicial Databases (David I. Spivak)“The theory of relational databases is generally formulated withinmathematical logic. We provide a more modern and more flexible approachusing methods from category theory and algebraic topology [. . . ] Using aninefficient language can hamper ones ability to implement, work with, andreason about a subject.”
Un goût de catégorification . . . gratuite
R. Thion Théorie des catégories 22
Introduction Les catégories La pratique Applications informatiques Conclusion
Quid des bases de données ?
Data Base Mappings and Monads : (Co)Induction (Zoran Majkic)“Thus DB category, as a base category for the semantics of databases andmappings between them, is different from the Set category used dominantlyfor such issues, and needs the full investigation of its properties.”
Simplicial Databases (David I. Spivak)“The theory of relational databases is generally formulated withinmathematical logic. We provide a more modern and more flexible approachusing methods from category theory and algebraic topology [. . . ] Using aninefficient language can hamper ones ability to implement, work with, andreason about a subject.”
Un goût de catégorification . . . gratuite
R. Thion Théorie des catégories 22
Introduction Les catégories La pratique Applications informatiques Conclusion
A calculus for collections and aggregates (Lellahi, Tannen)“This paper proposes a calculus for programming with collection data typesand aggregate operations on such collections. From a philosophicalperspective, such a calculus should play for database query languages therole that the lambda calculus plays for functional programming languages.From a practical perspective, such a calculus can form the foundation of anintermediate language : the surface syntax of queries can gets translated intoterms of the calculus and the equational theory of the calculus derivesprogram equivalences used in optimization.”’
Constructions catégoriquesproposition d’un calcul sur les collections (cf. Nested RelationalCalculus), dont la sémantique est donnée à l’aide de catégories,notion générale de collection : monades,notion générale d’aggrégats : algèbres sur un endo-foncteur,théorèmes vérifiés dans les structures : pour l’optimisation.
R. Thion Théorie des catégories 23
Introduction Les catégories La pratique Applications informatiques Conclusion
A calculus for collections and aggregates (Lellahi, Tannen)“This paper proposes a calculus for programming with collection data typesand aggregate operations on such collections. From a philosophicalperspective, such a calculus should play for database query languages therole that the lambda calculus plays for functional programming languages.From a practical perspective, such a calculus can form the foundation of anintermediate language : the surface syntax of queries can gets translated intoterms of the calculus and the equational theory of the calculus derivesprogram equivalences used in optimization.”’
Constructions catégoriquesproposition d’un calcul sur les collections (cf. Nested RelationalCalculus), dont la sémantique est donnée à l’aide de catégories,notion générale de collection : monades,notion générale d’aggrégats : algèbres sur un endo-foncteur,théorèmes vérifiés dans les structures : pour l’optimisation.
R. Thion Théorie des catégories 23
Introduction Les catégories La pratique Applications informatiques Conclusion
La théorie des catégoriesun vocabulaire de concepts et de constructions,une façon de penser morphismes,généraliser et transférer entre domaines.
Intérêt des catégories en BD ?Abstraire les constructions/transformations classiques des basesde données relationnellese.g., contraintes d’intégrité, chase, réécriture . . .Pour les appliquer/instancier sur de nouvelles structurese.g., graphes RDF, arbres XML, BD objets, NRC . . .
R. Thion Théorie des catégories 24
Introduction Les catégories La pratique Applications informatiques Conclusion
La théorie des catégoriesun vocabulaire de concepts et de constructions,une façon de penser morphismes,généraliser et transférer entre domaines.
Intérêt des catégories en BD ?Abstraire les constructions/transformations classiques des basesde données relationnellese.g., contraintes d’intégrité, chase, réécriture . . .Pour les appliquer/instancier sur de nouvelles structurese.g., graphes RDF, arbres XML, BD objets, NRC . . .
R. Thion Théorie des catégories 24
Introduction Les catégories La pratique Applications informatiques Conclusion
Ceci n’est pas une catégorie (R. Magritte)
R. Thion Théorie des catégories 25
Introduction Les catégories La pratique Applications informatiques Conclusion
RéférencesDeutsch, A. ; Nash, A. & Remmel, J. B. The chase revisited. 2008.PODS sur l’universalité du chase
Pierce, B. C. Basic Category Theory for Computer Scientists. 1991.Livre d’introduction de référence
Lellahi, S. K. & Tannen, V. A Calculus for Collections and Aggregates.1997. Un équivalent du λ-calcul pour les BD
Rydeheard, D. E. & Burstall, R. M. A Categorical Unification Algorithm.1986. Algo de Martelli & Montanari décrit catégoriquement
Rutten, J. J. M. M. Universal coalgebra : a theory of systems. 2000.Transpositions de concepts algébriques aux automates
Moggi, E. Notions of computation and monads. 1991. Formalisation dela notion d’effet
Liang, S. & Hudak, P. Modular Monadic Semantics. 1998. Combinermodulairement les effets
Goguen, J. A. A Categorical Manifesto. 1991.
R. Thion Théorie des catégories 26
