C'est marrant comme il suffit de parler d'un concept mathématique relativement avancé en termes un tant soit peu profanes pour t'invoquer.
Je n'ai pas vu à quel moment il a été fait mention d'un concept mathématique relativement avancé en termes profanes. Tu disais que git gère un graphe orienté d'états successifs, je t'ai répondu que pijul faisait de même.
Je sais d'avance que la suite de cette conversation sera, en réponse, un autre pavé encore plus indigeste pour moi, que je ne comprendrai carrément pas, car j'ai arrêté les maths suffisamment tôt pour ma satisfaction professionnelle vu que j'aime mon travail, mais trop tôt par rapport à la maitrise d'icelles que j'aimerais avoir, mais bon je me lance quand même.
Si mes réponse apparaissent comme des pavés indigestes, alors c'est que j'ai échoué à atteindre mon objectif. Mon intention principale, quand j'écris sur ce site, est d'être compris par le plus grand nombre et non d'utiliser des termes pédants et abscons. Ton choix d'avoir arrêté les maths suffisamment tôt pour ta satisfaction professionnelle est on ne peut plus respectable : chacun fait et étudie ce qu'il lui plait. Cela étant, si je peux réussir à te faire comprendre ce qui distingue git et pijul sans entrer dans des détails techniques et théoriques, j'aurai atteint mon objectif.
Du peu que je sais j'ai l'impression que le c'est-à-dire est à l'envers.
Comme te l'a déjà répondu Michaël : toute catégorie peut être vu comme un graphe orienté (on les présente souvent ainsi d'ailleurs) mais la réciproque n'est pas vraie; mon c'est-à-dire n'est pas mis à l'envers. Mais laissons donc de côté le concept de catégorie et gardons donc celui de graphe orienté : il sera compris de tout le monde.
Git stocke en premier lieu des "états"-"sommets" qui représentent concrètement et trivialement le contenu brut du dépôt aux instants T(x), et ajoute par dessus un graphe de relations bête et méchant. J'ai l'impression que pijul travaille dans l'autre sens en ayant comme citoyen de première classe les arêtes avec le patch comme contenu, et en déduit des sommets-"état du dépôt".
De ce que j'en ai lu et compris, pijul aussi a pour sommets dans son graphe le contenu du dépôt aux instants T(x), à savoir les fichiers de la branche de travail. En revanche, pijul voit l'évolution de l'historique d'un dépôt comme un succession de patchs appliqués sur lui et c'est ce que représente son graphe en étiquetant chaque arêtes par un patch. Ce qui donne bien aux patchs un statut de citoyens de première classe, mais il ne passe pas son temps à déduire les fichiers par application des patchs par simple soucis d'efficacité :
Fast algorithms: Pijul's pristine can be seen as a "cache" of applied patches, to which new patches can be applied directly, without having to compute anything on the repository's history.
Venons-en maintenant à une propriété qui distingue git et pijul : l'associativité. C'est certes une notion mathématique mais simple à comprendre : elle dit, en gros, dans le cas de l'addition, que (a + b) + c = a + (b + c) ce qui fait qu'en général on se dispense d'écrire les parenthèses et que l'on écrit tout simplement a + b + c.
Il est très utile, en pratique, d'avoir des opérations associatives et lorsque ce n'est pas le cas, il faut faire attention à la manière dont on les regroupe. Si je reprend l'exemple de la multiplication des matrices données dans un autre journal pour réduire le nombre de cache miss :
/* traduction directe de la formule du produit */for(i=0;i<N;++i)for(j=0;j<N;++j)for(k=0;k<N;++k)res[i][j]+=mul1[i][k]*mul2[k][j];/* optimisation pour réduire les cache miss */for(i=0;i<N;i+=SM)for(j=0;j<N;j+=SM)for(k=0;k<N;k+=SM)for(i2=0,rres=&res[i][j],rmul1=&mul1[i][k];i2<SM;++i2,rres+=N,rmul1+=N)for(k2=0,rmul2=&mul2[k][j];k2<SM;++k2,rmul2+=N)for(j2=0;j2<SM;++j2)rres[j2]+=rmul1[k2]*rmul2[j2];
Dans son article, Ulrich Drepper précise bien « we ignore arithmetic effects here which might change the occurrence of overflows, underflows, or rounding », et il a raison : l'addition n'étant pas associative en arithmétique flottante, les deux programmes ne sont pas identiques. Mais son intention était surtout de montrer que l'ordre dans lequel les instructions étaient effectuées avaient son importance sur la gestion du cache CPU.
Quittons cette courte digression et revenons à nos moutons. Si l'arithmétique flottante n'est pas associative, il n'en est pas de même des séries d'instructions dans un langage comme le C : (e1;e2);e3 se comporte comme e1;(e2;e3) ou e1;e2;e3. Par contre, la fusion des patchs et commits en git ne vérifient pas cette propriété. C'est ce qui lui est reproché, entre autre, par les promoteurs de darcs et pijul. Le lien du premier commentaire illustrait ce phénomène, et la documentation de pijul l'illustre avec ces deux schémas :
pij fork1
pij fork2
si chaque point illustre des patchs appliqués, disons A B C, alors avec git on aurait : (A;B);C ≠ A;(B;C). C'est ce qui se passe quand on fait du cherry-picking et du rebase. En revanche, pijul vérifie bien cela et c'est ce qu'illustrait ce graphe :
pijul asso
Si l'on part de l'état O du dépôt, qu'Alice et Bob fork pour aller l'un dans l'état B et l'autre dans l'état C. Puis Alice passe ensuite dans l'état M. Peu importe que l'on fusionne d'abord B et C dans l'état N pour ensuite fusionner N et M, ou que l'on fusionne directement C et M : dans tous les cas on arrivera sur le même état Q. Pour revenir rapidement sur la notion de catégorie, cette propriété d'associativité fait partie de sa définition : un graphe qui ne la vérifie pas ne peut être vu comme une catégorie, en revanche une catégorie vue comme un graphe la vérifiera.
Comme l'a dit pmeunier, git ne vérifiant pas cette propriété (pourtant utile et, dans le fond, désirée par les utilisateurs), il y a des guides de bonnes pratiques pour combler cette lacune, là où, par construction, elle est automatiquement satisfaite dans pijul.
Outre cette propriété d'associativité des patchs, il y en a une autre fort utile : celle qui cherche à capter l'essence de fonctionnalités orthogonales ou indépendantes. Si, dans un commit, je modifie une partie d'un fichier, puis dans le commit suivant j'en modifie une autre qui n'a rien à voir : peu importe l'ordre dans lequel je les réalise, on devrait aboutir au même résultat. Cette propriété s'appelle la commutativité des patchs, à savoir p1;p2 fait la même chose que p2;p1 (ou a + b = b + a). Pijul détecte automatiquement de telle situation et transforme (de manière transparente pour l'utilisateur) le graphe de dépendance des états. Dans une telle situation :
pijul dep1
pijul va chercher s'il ne peut trouver un patchs a(q) telle que dans le graphe suivant :
pijul dep2
la fusion des états A et C donne le même état B que dans la séquence p;q, et en arrière plan on aura dans le graphe de pijul cette situation :
pijul dep3
ce qui permet, entre autre, de paralléliser les calculs, mais rend aussi le graphe plus flexible à l'usage. Les guides de bonnes pratiques expliquent également comment obtenir une telle chose en git : avec pijul, rien à faire, elle est fournie de base sans effort de le part des utilisateurs.
Un dernier point, un peu plus technique que ce qui précède, mais pas si difficile à comprendre, c'est là raison d'être des digle. Lorsque l'on cherche à fusionner deux états, on se retrouve dans la situation suivante :
A
/ \
/ \
O ??
\ /
\ /
B
Le problème est que si l'on prend pour type des sommets celui des fichiers, ce problème n'a pas toujours de solution : c'est ce qu'il se passe lorsqu'il y a conflit. Il y a un principe général qui consiste à dire : si le problème n'a pas de solution, alors agrandissons l'espace du possible et il aura toujours une solution. C'est, pour donner une comparaison, ce qu'on fait les algébristes quand ils ont inventé les nombres complexes : certains polynômes n'ont pas de racines, ce n'est pas grave, il suffit de rajouter des nombres et tout polynôme aura une racine. Raison pour laquelle, en cas de conflit, pijul produit pour sommet un graphe orienté de lignes et non un fichier. De la même façon que l'on peut projeter de plusieurs façons différentes un nombre complexe sur un nombre réel, on peut aplatir de différentes façon un digle en un fichier ou réduire de différentes façons un conflit. Mais cette phase ne résolution, comme dans git, n'est pas effectuée automatiquement par pijul mais reste à la charge des programmeurs.
En espérant avoir éclairci quelques différences entre git et pijul, sans avoir écrit un pavet indigeste.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
[^] # Re: Pourquoi du théorie des patch c'est bien
Posté par kantien . En réponse au journal Pijul, un nouveau gestionnaire de source. Évalué à 5. Dernière modification le 23 septembre 2017 à 11:46.
Je n'ai pas vu à quel moment il a été fait mention d'un concept mathématique relativement avancé en termes profanes. Tu disais que git gère un graphe orienté d'états successifs, je t'ai répondu que pijul faisait de même.
Si mes réponse apparaissent comme des pavés indigestes, alors c'est que j'ai échoué à atteindre mon objectif. Mon intention principale, quand j'écris sur ce site, est d'être compris par le plus grand nombre et non d'utiliser des termes pédants et abscons. Ton choix d'avoir arrêté les maths suffisamment tôt pour ta satisfaction professionnelle est on ne peut plus respectable : chacun fait et étudie ce qu'il lui plait. Cela étant, si je peux réussir à te faire comprendre ce qui distingue git et pijul sans entrer dans des détails techniques et théoriques, j'aurai atteint mon objectif.
Comme te l'a déjà répondu Michaël : toute catégorie peut être vu comme un graphe orienté (on les présente souvent ainsi d'ailleurs) mais la réciproque n'est pas vraie; mon c'est-à-dire n'est pas mis à l'envers. Mais laissons donc de côté le concept de catégorie et gardons donc celui de graphe orienté : il sera compris de tout le monde.
De ce que j'en ai lu et compris, pijul aussi a pour sommets dans son graphe le contenu du dépôt aux instants T(x), à savoir les fichiers de la branche de travail. En revanche, pijul voit l'évolution de l'historique d'un dépôt comme un succession de patchs appliqués sur lui et c'est ce que représente son graphe en étiquetant chaque arêtes par un patch. Ce qui donne bien aux patchs un statut de citoyens de première classe, mais il ne passe pas son temps à déduire les fichiers par application des patchs par simple soucis d'efficacité :
Venons-en maintenant à une propriété qui distingue git et pijul : l'associativité. C'est certes une notion mathématique mais simple à comprendre : elle dit, en gros, dans le cas de l'addition, que
(a + b) + c = a + (b + c)ce qui fait qu'en général on se dispense d'écrire les parenthèses et que l'on écrit tout simplementa + b + c.Il est très utile, en pratique, d'avoir des opérations associatives et lorsque ce n'est pas le cas, il faut faire attention à la manière dont on les regroupe. Si je reprend l'exemple de la multiplication des matrices données dans un autre journal pour réduire le nombre de cache miss :
Dans son article, Ulrich Drepper précise bien « we ignore arithmetic effects here which might change the occurrence of overflows, underflows, or rounding », et il a raison : l'addition n'étant pas associative en arithmétique flottante, les deux programmes ne sont pas identiques. Mais son intention était surtout de montrer que l'ordre dans lequel les instructions étaient effectuées avaient son importance sur la gestion du cache CPU.
Quittons cette courte digression et revenons à nos moutons. Si l'arithmétique flottante n'est pas associative, il n'en est pas de même des séries d'instructions dans un langage comme le C :
(e1;e2);e3se comporte commee1;(e2;e3)oue1;e2;e3. Par contre, la fusion des patchs et commits en git ne vérifient pas cette propriété. C'est ce qui lui est reproché, entre autre, par les promoteurs de darcs et pijul. Le lien du premier commentaire illustrait ce phénomène, et la documentation de pijul l'illustre avec ces deux schémas :pij fork1
pij fork2
si chaque point illustre des patchs appliqués, disons A B C, alors avec git on aurait :
(A;B);C ≠ A;(B;C). C'est ce qui se passe quand on fait du cherry-picking et du rebase. En revanche, pijul vérifie bien cela et c'est ce qu'illustrait ce graphe :pijul asso
Si l'on part de l'état O du dépôt, qu'Alice et Bob fork pour aller l'un dans l'état B et l'autre dans l'état C. Puis Alice passe ensuite dans l'état M. Peu importe que l'on fusionne d'abord B et C dans l'état N pour ensuite fusionner N et M, ou que l'on fusionne directement C et M : dans tous les cas on arrivera sur le même état Q. Pour revenir rapidement sur la notion de catégorie, cette propriété d'associativité fait partie de sa définition : un graphe qui ne la vérifie pas ne peut être vu comme une catégorie, en revanche une catégorie vue comme un graphe la vérifiera.
Comme l'a dit pmeunier, git ne vérifiant pas cette propriété (pourtant utile et, dans le fond, désirée par les utilisateurs), il y a des guides de bonnes pratiques pour combler cette lacune, là où, par construction, elle est automatiquement satisfaite dans pijul.
Outre cette propriété d'associativité des patchs, il y en a une autre fort utile : celle qui cherche à capter l'essence de fonctionnalités orthogonales ou indépendantes. Si, dans un commit, je modifie une partie d'un fichier, puis dans le commit suivant j'en modifie une autre qui n'a rien à voir : peu importe l'ordre dans lequel je les réalise, on devrait aboutir au même résultat. Cette propriété s'appelle la commutativité des patchs, à savoir
p1;p2fait la même chose quep2;p1(oua + b = b + a). Pijul détecte automatiquement de telle situation et transforme (de manière transparente pour l'utilisateur) le graphe de dépendance des états. Dans une telle situation :pijul dep1
pijul va chercher s'il ne peut trouver un patchs
a(q)telle que dans le graphe suivant :pijul dep2
la fusion des états A et C donne le même état B que dans la séquence
p;q, et en arrière plan on aura dans le graphe de pijul cette situation :pijul dep3
ce qui permet, entre autre, de paralléliser les calculs, mais rend aussi le graphe plus flexible à l'usage. Les guides de bonnes pratiques expliquent également comment obtenir une telle chose en git : avec pijul, rien à faire, elle est fournie de base sans effort de le part des utilisateurs.
Un dernier point, un peu plus technique que ce qui précède, mais pas si difficile à comprendre, c'est là raison d'être des digle. Lorsque l'on cherche à fusionner deux états, on se retrouve dans la situation suivante :
Le problème est que si l'on prend pour type des sommets celui des fichiers, ce problème n'a pas toujours de solution : c'est ce qu'il se passe lorsqu'il y a conflit. Il y a un principe général qui consiste à dire : si le problème n'a pas de solution, alors agrandissons l'espace du possible et il aura toujours une solution. C'est, pour donner une comparaison, ce qu'on fait les algébristes quand ils ont inventé les nombres complexes : certains polynômes n'ont pas de racines, ce n'est pas grave, il suffit de rajouter des nombres et tout polynôme aura une racine. Raison pour laquelle, en cas de conflit, pijul produit pour sommet un graphe orienté de lignes et non un fichier. De la même façon que l'on peut projeter de plusieurs façons différentes un nombre complexe sur un nombre réel, on peut aplatir de différentes façon un digle en un fichier ou réduire de différentes façons un conflit. Mais cette phase ne résolution, comme dans git, n'est pas effectuée automatiquement par pijul mais reste à la charge des programmeurs.
En espérant avoir éclairci quelques différences entre git et pijul, sans avoir écrit un pavet indigeste.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.