Doshi's blog

Linguistique, maths et programmation (+ un morceau musical)

23/03/2020 — reflexion, linguistique, maths, programmation, musique — ~13mn de lecture

J’aime beaucoup ces 3 sujets. Vraiment. Bon après la linguistique je m’y connais pas des masses non plus, c’est un sujet sur lequel j’aimerais bien m’instruire plus. Et les deux derniers je m’intéresse un peu à des sous-ensembles de ces sujets aussi, mais bref, j’adore quand ya des liens qui se créent entre les 3

Analyse sémantique ?¹

Je regardais tranquillou la dernière vidéo de Mickael Launay sur la commutativité quand à un moment il parle de la décomposition de 3×7. On peut le comprendre comme (3×) 7 ou 3(×7).

Et en fait ça revient à faire une analyse sémantique de l’expression : soit on choisit de dire que l’objet (ou le sujet wink wink) c’est “3”, objet auquel on applique l’action “×7”, soit on prend comme sujet “7” et comme action (3×). Donc dans le premier cas, on décompose en 3+3+3+3+3+3+3 et dans le deuxième cas on décompose en 7+7+7. De ce que j’en ai vu, la majorité de mes amis décomposent 3×7 en 7+7+7 (et du coup 7×3 en 3+3+3+3+3+3+3), mais moi je le fais dans l’autre sens.

Et du coup ça revient à parser l’expression différement. Et ça ressemble un peu à la syntaxe qui diffère dans différents langages. Par exemple, en japonais et en turc, le verbe se place à la fin de la phrase². Du coup je me pose la question, forcément : est-ce que les japonais parsent 3×7 comme “nous” ou dans l’autre sens?

Après en vrai, en écrivant ces lignes je me rends compte que pas besoin d’avoir un verbe en fin de proposition dans ta langue natale pour expliquer ma décomposition (donc l’action en dernier), mais simplement que le sujet vient avant le verbe, donc en vrai c’est un peu con, mais bon je trouvais ça intéressant³

⁂

Les foncteurs

La vidéo de Mickael parle aussi d’un autre truc : les diagrammes commutatifs. Et c’est un truc que je connais déjà, parce que c’est grave utilisé en théorie des catégories en maths, et que c’est un sujet que j’aime bien donc je me suis déjà plongé plusieurs fois dans Wikipedia à cause de ça. Et ça m’est réarrivé. Et là j’ai découvert un truc rigolo :

Le mot “functor”, à la base il a été piqué en linguistique !

Bon je vais pas vous laisser là donc je vais vous expliquer ce que c’est, mais ça risque d’être un peu long, parce que ça existe en linguistique (forcément), en programmation et en maths.

Linguistique

En linguistique, donc⁴, un functor (oui en anglais, parce qu’en français on a pas l’air d’utiliser la traduction “foncteur” mais plutôt mot-outil ou mot grammatical), c’est un mot dont le rôle syntaxique est plus important que son rôle sémantique (genre les prépositions, conjonctions, déterminant …). C’est tout. Un functor en linguistique c’est juste une espèce de scotch grammatical.

Programmation

Bon en programmation, le terme il est employé principalement par 2 langages (en tout cas à ma connaissance) : C++ et Haskell.

C++

En C++, ce qu’on appelle un foncteur, c’est une classe qui surcharge l’opérateur (). En gros dans les classes en C++, on peut évidemment définir des méthodes, normal, mais on peut aussi redéfinir des opérateurs. Par exemple si on choisit de redéfinir la fonction operator=() bah ça va changer comment l’opérateur = il va fonctionner sur notre objet. Il y en a tout plein des comme ça, mais en particulier la fonction operator(). Et redéfinir ce truc va nous permettre d’utiliser notre objet comme si c’était une fonction. Exemple:

class Functor {
    int valeur;
    Functor(int i) : valeur(i) {};

    int fonction_normale(int j) {
        return valeur + j;
    }

    int operator()(int j) {
        return valeur * j;
    }
};

Functor machin(3) // → crée un objet dont l'attribut valeur vaudra 3
machin.fonction_normal(6) // on appelle une méthode de manière normale, et on obtient bien 3 + 6 comme résultat
machin(5) // grâce à operator() on peut utiliser notre objet comme une fonction ! Et on a bien 3 * 5 en résultat

Haskell

En Haskell, un foncteur ça vient directement des maths, de la théorie des catégories. Bon du coup ça va devenir légèrement plus velu à partir de là.

Donc. En Haskell, un foncteur, c’est un truc qui implémente la fonction fmap et la fonction <$ mais celle là je vais la laisser tranquille parce que je sais pas ce qu’elle fait.

Mais fmap c’est quoi ? Demandons à Haskell !

Prelude> :t fmap -- "C'est quoi la "signature" de fmap ?"
fmap :: Functor f => (a -> b) -> f a -> f b

Bon. Ça a l’air velu mais rassurez vous, je vais tout vous expliquer, on va y aller pas à pas, tranquillement⁵

fmap

C’est le nom de la fonction. Chouette (on l’appelle aussi <$>⁶ des fois, pour l’utiliser en infixe, mais c’est la même fonction)

::

Ça ça veut juste dire “est de type” Donc x :: Int nous dit que x est de type Int, et bah fmap :: Functor f => (a -> b) -> f a -> f b nous dit que fmap est de type le-gros-truc-qui-suit-et-oui-c’est-bien-un-type⁷

Functor f =>

Ça veut dire que le f qu’on va rencontrer dans la suite du type de la fonction doit obligatoirement être une instance de Functor (pensez à Functor comme si c’était une boite qui contient des trucs, ça va être utile pour plus tard). C’est utilisé par exemple dans la définition de la fonction > (supérieur à, vous ne revez pas). Son type c’est (>) :: Ord a => a -> a -> Bool donc ça nous dit directement que tous les a qu’on voit dans la signature, ils sont obligatoirement instance de Ord (ce qui signifie juste qu’ils peuvent être triés)

(a -> b) -> f a -> f b

Nous voilà avec le vrai type de la fonction fmap. Regardez les flèches (sans compter celle entre parenthèses) : y’en a 2 (et donc elles séparents 3 trucs). Ces trucs c’est les arguments de la fonction (sauf le dernier qui est la valeur de retour⁸).

Donc, le premier argument c’est (a -> b). La présence d’une flèche nous indique qu’il s’agit d’une fonction ! Donc le premier argument c’est une fonction qui prend un argument de type a en entrée, et qui nous sort un b en sortie (a et b sont juste des noms de types quelconque, ça pourrait être un Int, un Bool, un Char, peut importe⁹.

Le deuxième argument, c’est f a. Comme je vous l’ai dit, f ici c’est un Functor, et comme je vous l’ai dit, on peut y penser comme une boîte. Donc ici, f a, c’est un truc de type a qui est encapsulé dans la boîte f.

Et la valeur de retour, finalement c’est f b donc un truc de type b encapsulé dans la boite f.

Bon ok c’est chouette, ça fait tout plein de mots, mais si vous êtes pas familiers avec le merdier, ça doit toujours être du charabia. J’vais essayer de l’expliquer avec des exemples.

Est-ce que vous connaissez la fonction map ? C’est une fonction qui prend une fonction f et une liste en argument, et qui retourne une nouvelle liste. Par exemple :

square x = x * x
map square [1, 2, 3, 4, 5] -- ⇒ [1, 4, 9, 16, 25]

Donc plus “formellement”, map f [x1, x2, x3, …] = [f(x1), f(x2), f(x3), …]¹⁰

Bon si vous savez lire, vous aurez remarqué que map et fmap ça se ressemble… Et bah c’est pas pour rien. Vous savez ce que c’est le type de map ? C’est ça : map :: (a -> b) -> [a] -> [b]. Donc ce que ça nous dit, c’est que ça prend une fonction de a vers b, une liste de a et ça nous donne une liste de b. Dans notre exemple, a et b en fait c’était le même type, c’est des Int. Et maintenant laissez moi vous montrer quelque chose :

• map  ::              (a -> b) -> [a] -> [b]
• fmap :: Functor f => (a -> b) -> f a -> f b

C’est étrangement similaire non ? Vous vous rappelez quand j’ai dit qu’un foncteur c’était une boite ? En quelque sorte, une liste c’est aussi un type de boite dans lequel on met des trucs, hein ?

Et ouais, en fait les listes, c’est des foncteurs. Et leur fonction fmap, c’est la fonction map.

Et en fait des foncteurs y en a plein, tant que c’est une encapsulation d’un autre type. Par exemple le type Maybe, qui est là pour nous dire si on a une valeur (Just valeur) ou non (Nothing) c’est un foncteur aussi, voili voilou.

Maths

Et maintenant¹¹. Le balourd. Le méchant. Le velu. La théorie des catégories (musique sourde de Inception)

Bon, c’est quoi un foncteur en maths. En fait c’est pas siiiiii compliqué que ça. C’est un peu comme une fonction.

Une fonction, ça prend un nombre et ça ressort un nombre. Chouette. Mais après, ça peut prendre genre 3 nombres et en ressortir 2, non ? J’vois pas pourquoi ça pourrait pas ?

Bah en fait on va abstraire ça. On va appeler ça un morphisme. Un morphisme, donc, c’est comme une fonction, mais plutôt que de prendre un nombre et de retourner un nombre, ça va prendre un truc et ça va ressortir un machin. truc et machin, ça peut être n’importe quelle structure algébrique. J’vais pas expliquer ce que c’est une structure algébrique parce que cet article est déjà méga long mais j’en avais présenté quelques unes ya quelques temps. Mais imaginez ça comme un ensemble avec des opérations définies par dessus.

Bon bah dit comme ça, une fonction c’est juste un cas particulier de morphisme. La structure algébrique d’entrée c’est la même que celle de sortie, et c’est l’ensemble des nombres réels ℝ. On peut noter ça \(ℝ \to ℝ\) pour faire plus court. Et du coup on peut avoir des fonctions qui prennent 3 nombres en entrées et qui sortent 2 nombres en sortie, ça s’écrirait \(ℝ×ℝ×ℝ \to ℝ×ℝ\).

Bon bah un foncteur, c’est encore une généralisation au dessus. Et pour les types d’entrée et de sortie, on va plus parler de structures algébriques mais de catégories¹².

Et bah un foncteur F d’une catégorie \(\mathcal{C}\) vers une catégorie \(\mathcal{D}\), qu’on note allégrement \(F : \mathcal{C} \to \mathcal{D}\) c’est donc

• une fonction qui associe à tout objet \(c \in \mathcal{C}\) un objet \(F(c) \in \mathcal{D}\)
• mais aussi une fonction qui a tout morphisme \(f \in \mathcal{C} : c_1 \to c_2\) un autre morphisme \(F(f) \in \mathcal{D} : F(c_1) \to F(c_2)\)

En vrai j’ai aucune idée de qui lit ces lignes actuellement, donc même si je me doute que toi qui lit ces lignes est assez à l’aise avec les maths, on va dire que ya ptet quelqu’un qui a été intéressé par ce que je raconte mais qui est pas giga à l’aise avec les notations, donc : je vais reprendre et expliquer ce que ça veut dire.

Dans une catégorie, on a des objets, mais aussi des fonctions entre ces objets (par exemple, la catégorie des entiers, dedans ya des entiers, et des fonctions qui transforment des entiers en d’autres entiers)

• Un foncteur, ça va associer à chaque objet \(c\) d’une catégorie \(\mathcal{C}\) un autre objet, \(d\) qui lui est dans la catégorie \(\mathcal{D}\) et qui est l’image (comme pour les fonctions) de \(c\) par le foncteur \(F\). onc \(d = F(c)\).
• Mais un foncteur ça va aussi associer toutes les fonctions qu’il y a dans \(\mathcal{C}\) à des fonctions qui sont dans \(\mathcal{D}\). Prenons une fonction \(f\) dans \(\mathcal{C}\). La fonction \(f\) prend donc des éléments de \(\mathcal{C}\) et les transforme en autres éléments de \(\mathcal{C}\). Mais en fait, ma fonction \(f : c_1 \to c_2\), je peux la faire passer dans le foncteur \(F\), de telle sorte que l’image de \(c_1\) par \(F\) soit égale à l’image de \(c_2\), et c’est ça que ça veut dire \(F(f) : F(c_1) \to F(c_2)\)

Bon là par contre j’arriverais pas à expliquer plus clairement avec les moyens du bord. Mais c’est pas fini. Pour être un foncteur, il faut respecter 2 choses :

• Faut que ça respecte la fonction identité¹³ : \(F(Id_c) = Id_F(c)\)
• Faut que ça respecte la composition : \(F(g \circ f) = F(g) \circ F(f)\)

Et voilà ! J’espère que j’ai été relativement clair en vrai et que c’était pas du charabia de ouf. Et dire que tout ça est parti d’un truc tout con en linguistique…

Et un petit truc marrant pour la route : \(\mathcal{D}^\mathcal{C}\), c’est la catégorie des foncteurs \(F : \mathcal{C} \to \mathcal{D}\) et ses morphismes c’est les transformations qui a un foncteur \(F\) associe un autre foncteur \(G\). Ça devient vite le bordel en maths c’est rigolo :D

⁂

Petit morceau de musique pour la fin parce que j’avais envie

Et pour vous récompenser d’être arrivé au bout (ou pas hein, profitez quand même), j’avais envie de partager un petit morceau de rap que j’ai découvert ya pas longtemps et que j’aime bien. C’est un feat entre Davodka, un rappeur bien chanmé très technique et pas mal old school (dans un style qui ressemble grave à Hugo TSR) et Demi Portion, un rappeur que j’ai découvert ya pas longtemps parce qu’il a fait des vidéos avec Noman Hosni, un humoriste que j’adore et qui me fait beaucoup BEAUCOUP rire (mais si vous decidez d’aller voir ce qu’il fait, CW weed). Bref, voila le morceau