Cours 5: Sémantique dénotationnelle

Introduction

\[A, B ≝ α \mid A → B\\ M, N ≝ x^A \mid λx^A. M \mid MN\]

Sémantique dénotationnelle: “modèle” d’une théorie équationnelle:

\[(λx.M)N = M[N/x]\\ \text{+ passage au contexte}\]

Interprétations:

\[⟦x⟧ = \text{ensemble quelconque}\\ ⟦A → B⟧ = ⟦B⟧^{⟦A⟧}\\ \text{Si } x_1:C_1, ⋯, x_n:C_n ⊢ M:A \quad\text{ alors }\quad ⟦M⟧ : ⟦C_1⟧ × ⋯ × ⟦C_n⟧ ⟶ ⟦A⟧\]

Exemples:

\[f: A → A, x:A ⊢ f(f \underbrace{x}_{∈ fv(f)}): A\] \[⟦f(fx)⟧: \begin{cases} ⟦A⟧^{⟦A⟧} × ⟦A⟧ &⟶ ⟦A⟧ \\ (h, a) &\mapsto h(h(a)) \end{cases}\]

---

\[Γ, x:A ⊢ x:A\] \[⟦x⟧_{Γ, x:A} ≝ \begin{cases} ⟦Γ⟧ × ⟦A⟧ &⟶ ⟦A⟧ \\ (γ, a) &\mapsto a \end{cases}\]

---

---

\[\cfrac{Γ, x:A ⊢ M:B}{Γ ⊢ λx. M: A → B}\] \[⟦λx. M⟧_{Γ} ≝ \begin{cases} ⟦Γ⟧ &⟶ ⟦B⟧^{⟦A⟧} \\ γ &\mapsto \begin{cases} ⟦A⟧ &⟶ ⟦B⟧ \\ a &\mapsto ⟦M⟧_{Γ, x:A}(γ, a) \end{cases} \end{cases}\] \[\cfrac{Γ ⊢ M:A → B \qquad Γ ⊢ N:A}{Γ ⊢ MN:B}\] \[⟦MN⟧_{Γ} ≝ \begin{cases} ⟦Γ⟧ &⟶ ⟦B⟧ \\ γ &\mapsto ⟦M⟧_Γ(⟦N⟧_Γ(γ)) \end{cases}\]

Système T

Pareil, avec l’interprétation en plus du “if then else”

Sytème F

On n’arrive pas à donner une sémantique ensembliste!

En $λ$-calcul pur

\[⟦M⟧_{x_1, ⋯, x_n}: D^n ⟶ D\\ fv(M) ⊆ \lbrace x_1, ⋯, x_n \rbrace\]

Un $λ$-terme clos est dans:

\[1 ⟶ D\]

Problème de cardinalité! Comme les $λ$-abstractions sont des $λ$-termes:

\[D^D \hookrightarrow D\]

Donc les théoriciens des modèles ont discrédité pendant longtemps le $λ$-calcul en avançant qu’il n’a pas de modèles ensemblistes.

Mais arrive la logique catégorique (vision généralisée de la théorie des modèles): il n’y a aucune raison de se restreindre à la catégorie $Set$! Il y a des tas d’autres catégories qui peuvent fournir des modèles!

⟶ Dana Scott: interprétation du $λ$-caclul dans des treillis au début, puis des Complete Partial Orders (CPOs).

Laissez place à la Logique Catégorique

La sémantique “naïve” précédente peut être définie pour n’importe quelle catégorie cartésienne close (CCC)!

Catégories Cartésiennes Closes (CCC): Rappels de base

Produit $A, B ∈ 𝒞$:

Limite du diagramme discret $A \qquad B$, i.e. un triplet $(A × B, \, π_1: A×B ⟶ A,\, π_2: A×B ⟶ B)$ avec $A × B ∈ 𝒞$ tel que pour tout $(C, \, f: C ⟶ A,\, g: C ⟶ B)$, le diagramme suivant commute:

\[\begin{xy} \xymatrix{ C \ar[r]^g \ar[d]_f \ar@{.>}[rd]^{⟨f, g⟩} & B \\ A & A×B \ar[l]_{π_1} \ar[u]^{π_2} } \end{xy}\]

Objet terminal $1 ∈ 𝒞$ (produit 0-aire):

limite du diagramme vide; i.e. $𝒞(A, 1)$ est un singleton pour tout $A∈𝒞$

Catégorie cartésienne:

lorsqu’elle a tous les produits binaires et un objet terminal, i.e a tous les produits finis

Modulo l’axiome du choix (pour choisir le produit, qui n’est unique qu’à unique isomorphisme près), on a un bifoncteur:

\[×: 𝒞 × 𝒞 ⟶ 𝒞\]

Qui fait de $𝒞$ une catégorie monoïdale.

Adjonction

Si $F: 𝒞 ⟶ 𝒟, \; G: 𝒟 ⟶ 𝒞$ sont des foncteurs:

Adjonction à gauche $F \dashv G$:

s’il existe un isomorphisme naturel

\[𝒟(FA, B) ≃ 𝒞(A, GB)\]

Exemple: Construction libre

Les structures algébriques libres habituellement sont données par des adjoints à gauche de foncteurs d’oubli:

\[F \dashv U\]

où

• $F: Set ⟶ Grp$ par exemple
• $U: Grp ⟶ Set$ est le foncteur d’oubli

L’adjonction dit qu’un morphisme de groupe entre le groupe libre et $G$ est exactement une fonction des générateurs vers le carrier set de $G$:

\[Grp(FX, G) ≃ Set(X, UG)\]

Clôture

Soit $𝒞$ une catégorie cartésienne. Soit $A∈ 𝒞$. On pose

\[R_A ≝ \bullet × A: \begin{cases} 𝒞 &⟶ 𝒞 \\ Γ &\mapsto Γ×A \end{cases}\]

On dit que $𝒞$ est close si pour tout $A ∈ 𝒞$, $R_A$ a un adjoint à droite:

\[R_A = \bullet × A \dashv A → \bullet\]

i.e pour tous $A, B$:

\[𝒞(Γ×A, B) ≃ 𝒞(Γ, A → B)\]

Exemples:

Sont une CCC:

• $Set$
• $FinSet$ (ensembles finis)

Théorie de Lawvere

Théorie de Lawvere $𝒯$:

catégorie cartésienne $𝒯$ telle qu’il existe $\star ∈ 𝒯$ tq:

\[∀A ∈ 𝒯, \; A ≃ \star^n\]

Il s’agit d’une généralisation des théories équationnelles (qu’on rencontre en algèbre universelle). Les théories de Lawvere sont aussi appelées théories algébriques.

Exemple: Théorie des groupes

Soit $𝒢$ une catégorie cartésienne engendrée par $\star$ et trois morphismes

• $e: 1 ⟶ \star$
• $m: \star^2 ⟶ \star$
• $n: \star ⟶ \star$

avec la diagonale $δ ≝ ⟨id, id⟩$

\[\begin{xy} \xymatrix{ \star × (\star × \star) ≃ (\star × \star) × \star \ar[r]^{m × id} \ar[d]_{id × m} & \star^2 \ar[d]^m \\ \star^2 \ar[r]_{m} & \star } \end{xy}\] \[\begin{xy} \xymatrix{ 1 × \star \ar[r]^{≃} \ar[d]_{e × id} & \star & \star × 1 \ar[l]_{≃} \ar[d]^{id × e} \\ \star^2 \ar[ru]_{m} & & \star^2 \ar[lu]^{m} } \end{xy}\]

Plus: diagramme de l’inverse

Un modèle de $𝒯$:

est un foncteur préservant les produits $M: 𝒯 ⟶ 𝒞$, où $𝒞$ est une catégorie cartésienne close.

La donnée d’un tel foncteur correspond à la donnée de:

• $M(\star) ∈ 𝒞$

Ici:

• un modèle $M: G ⟶ Set$ de $𝒢$ est exactement un groupe
• un modèle $M: G ⟶ Top$ est un groupe topologique

• Argument de Eckman-Hilton: un modèle $M: G ⟶ Grp$ est un groupe abélien

  • de même: une catégorie monoïdale dans la catégorie des catégories monoïdales est une catégorie monoïdale symmétrique
  • un monoïde dans la catégorie des monoïdes est un monoïde commutatif

Toute théorie équationnelle sans inégalité (donc pas les corps) peut être exprimée en termes de théories de Lawvere!

Ici, $\star$ est une sorte. Mais on pourrait avoir plusieurs sortes:

Théories multi-sortée (à $r$ sortes):

pour tout $A∈ 𝒯$, il existe $n_1, ⋯, n_r$ tels que

\[A ≃ \star_1^{n_1} × ⋯ × \star_r^{n_r}\]

Ex: avec une sorte pour les vecteurs, une pour les scalaires:

• interprétation dans $Set$ ⟶ espaces vectoriels
• interprétation dans $Top$ ⟶ espaces topologiques

Modèles du $λ$-calcul simplement typé

La sémantique du $λ$-calcul simplement typé peut être défini dans n’importe quelle CCC

C’est une sorte de “théorie de Lawvere” à l’ordre supérieur:

• on a des générateurs et les produits finis (théorie de Lawvere)

• et en plus: l’exponentielle

  • l’adjonction est la règle de la déduction naturelle

    \[\cfrac{Γ, A ⊢ B}{Γ ⊢ A → B}\]
• la $β$-réduction est l’équation

• les $λ$-termes sont les morphismes:

  • un $λ$-terme de type $A$ dont les variables libres sont dans $Γ$ est un morphisme $Γ ⟶ A$

Donc un modèle du $λ$-calcul simplement typé est un foncteur

\[M: Λ_{ST} ⟶ 𝒞\]

préservant le produit et l’exponentielle.

Modèles du $λ$-calcul pur

Pour avoir un modèle du $λ$-calcul pur (non typé), il suffit de trouver une CCC $𝒞$ avec un objet $D ∈ 𝒞$ tq

\[\begin{xy} \xymatrix{ D ⟶ D \ar@/^/[r]^f & D \ar@/^/[l]_g } \end{xy}\] \[f \triangleleft g \qquad\text{ i.e }\qquad g \circ f = id_{D ⟶ D}\]

ce que l’on appelle une rétraction

On appelle alors $D$ un objet réflexif.

CPOs

Soit $(D, ≤)$ un ordre partiel, et $Δ ⊆ D$.

$Δ$ est filtrant:

si $∀x, y∈ Δ. ∃z ∈ Δ, x,y ≤ z$

Un ordre partiel complet (CPO):

est un ordre partiel $(D, ≤, ⊥)$ avec un plus petit élément $⊥$ et tel que tous les ensembles ensembles filtrants (directed set) ont un sup, dénoté par $∨ Δ$

NB: en topologie, les fonctions continues sont exactement celles qui préservent les limites de suites indexées par les ensembles filtrants.

Si toute fonction continue préserve les limites de suites, la réciproque n’est pas vraie: il ne suffit pas de préserver les limite de suites pour être continue. Les suites indexées par des ensembles filtrants est la bonne notion.

NB: “Domaines de Scott”: CPOs avec des propriétés en plus.

Dans la littérature, on appelle “domaine” un CPO avec des propriétés en plus (les espaces cohérents en sont un cas particulier).

On va les utiliser pour PCF (extension du $λ$-calcul simplement typé Turing-complète).

Scott-continuité

Soient $D, E$ des cpos.

Une fonction $f: D ⟶ E$ est Scott-continue:

si elle préserve les sups d’ensembles filtrants

Pour tout $Δ ⊆ D$ filtrant:

\[f(Δ) ≝ \lbrace y∈ E \mid y=f(x), x ∈ Δ \rbrace \quad\text{ est filtrant}\]

et

\[\bigvee f(Δ) = f(∨ Δ)\]

Catégorie des CPOs

On note CPO la catégorie des cpos et des fonctions continues.

Théorème (Scott):

CPO est une CCC.

De plus, elle admet un objet réflexif.