Couples, paires et graphes

vendredi 27 mars 2020
par  Alain BUSSER

Une paire est un ensemble à deux éléments. Alors que d’une part le couple (a,b) n’est en général pas égal au couple (b,a) et l’équivalent, comme ensemble, du couple (a,a) est un singleton, pas une paire. Dans cet article on va voir comment ces objets peuvent être construits dans divers formalismes (théorie des ensembles, lambda-calcul) et implémentés en machine (notamment en Python). Et on verra des applications de cette notion, avec les dictionnaires de Python et les graphes.

Une légende dit que c’est alité par une maladie, que Descartes aurait eu l’idée d’associer les points du plan à des couples de nombres. Voici ce qu’en écrit Cauchy, en 1823 :

La notion de couple, même avant d’être formalisée, est donc omniprésente en mathématiques, notamment en géométrie repérée et en analyse, faisant intervenir des couples (x,y). Un graphe orienté est un ensemble de couples (inclus dans le produit cartésien) donc cette notion est fondamentale, puisque les relations (en particulier les fonctions) sont des graphes orientés.

Emballer pour accoupler

La théorie des ensembles consiste à regrouper des objets (les éléments) dans des collections (les ensembles d’objets). Par exemple si on veut regrouper les éléments a et b :

on peut mettre une enveloppe (« patatoïde ») autour des 2 éléments :

Mais la paire obtenue n’est pas un couple, puisque d’une part on ne peut distinguer les rôles de a et b, d’autre part si a = b, on n’obtiendra qu’un singleton alors qu’un couple doit vraiment avoir deux élements (le premier élément, et le deuxième élément).

Envelopper séparément a et b ne résout pas le problème :

En effet cela produit 2 singletons (ensembles à un seul élément chacun, et si a = b on n’aura qu’un seul singleton, avec de surcroît l’absence d’ordre entre les singletons.

Voici une autre manière d’emballer qui permet un vrai accouplement et pas seulement un appariement :

Voici comment le couple (a,b) est modélisé dans la théorie des ensembles de Tarski et Grothendieck :

Ceci est bien un couple

Tout d’abord, les couples (a,b) et (b,a) sont bel et bien différents l’un de l’autre :

(a,b) (b,a)

Ensuite, le couple (a,a) peut être modélisé par cette technique :

Les entiers naturels entièrement emballés

Chez Alfred North Whitehead et Bertrand Russel, la théorie des ensembles permet de construire les entiers :

L’ensemble vide modélise l’entier 0 :

  1. En emballant 0 on obtient 1 :
  2. En emballant 0 et 1 on obtient 2 :
  3. En emballant 0, 1 et 2 on obtient 3 :

La construction des entiers naturels par des ensembles remonte à Von Neumann.

La construction des entiers naturels par Von Neumann n’est pas si naturelle que ça (celle des numéraux de Church non plus). La modélisation des couples en théorie des ensembles souffre du même problème, et il semble préférable de considérer la notion de couple comme une notion primitive. La notion est abordable intuitivement dès le milieu de cycle 2, en notant a→b le couple (a,b). C’est la notation avec les parenthèses qui est moins intuitive.

D’autres modélisations ont été proposées depuis plus d’un siècle.

ordre total sur l’algèbre de Boole

Une algèbre de Boole, comme son nom l’indique, est munie d’une addition (notée +) et d’une multiplication (notée ×). Mais il est possible d’y définir aussi une relation d’ordre, comme le constata George Boole en 1847 : Dans le chapitre XI des lois de la pensée, il propose de dire que a≤b lorsqu’il existe c tel que a=b×c [1].

On connaît un tel c vérifiant a=b×c : c’est a lui-même. La définition moderne de l’inégalité dans une algèbre de Boole est

a ≤ b si et seulement si a×b=a

Cette relation d’ordre n’est pas totale : il n’est pas certain, si on choisit au hasard deux éléments a et b d’une algèbre de Boole, que a≤b ou b≤a. Par contre, dans l’algèbre de Boole à deux éléments (appelée ici « l’algèbre de Boole » par opposition à « une algèbre de Boole »), on a

  • 0≤0
  • 0≤1
  • 1≤1

mais pas 1≤0 : la relation d’ordre est alors totale.

Dans son article cité ci-dessous, Kuratowski transporte cette relation d’ordre sur le couple (a,b) en modélisant ce couple par une fonction f vérifiant f(0)=a et f(1)=b.

Cela revient à modéliser le couple a→b par le diagramme sagittal

0→a
1→b

Comme on a 0≤1, la relation d’ordre entre 0 et 1 se transmet à a et b, donnant la relation d’ordre a≤b. Dans le langage moderne des catégories et foncteurs (voir la partie sur les monades) on peut dire que si l’algèbre de Boole 0→1 est une catégorie, alors la fonction étudiée par Kuratowski est un foncteur vers la catégorie à deux élements a→b.

Le couple (a,a) peut alors être construit par la fonction constante

0→a
1→a

Et les couples (a,b) et (b,a) sont effectivement différents :

(a,b) (b,a)
0→a

1→b
0→b

1→a

On verra plus bas que c’est de cette manière (avec 0 et 1 vus comme adresses mémoire) que les couples sont implémentés dans les ordinateurs. La même idée est reprise dans le λ-calcul.

Mais cette définition n’est pas, on le verra plus bas, celle adoptée par Kuratowski : elle est circulaire car pour définir une fonction, on doit avoir déjà la notion de couple.

Histoire de couples

Cantor et Frege proposaient de modéliser le couple (a,b) comme ensemble des relations R telles que aRb. Cette définition est circulaire car une relation est un ensemble de couples.

En 1914, Felix Hausdorff propose cette modélisation du couple (a,b) :

La ressemblance avec l’idée initiale de Kuratowski (voir la partie sur l’algèbre de Boole) cache le fait que cette définition ne fonctionne pas si a=0 ou b=1.

À la même époque, Norbert Wiener propose cette autre modélisation :

L’idée est de séparer a et b par des emballages différents. Cette définition est correcte, mais on a vu ci-dessus qu’il y a plus simple (moins de papier d’emballage nécessaire).

En 1921, Casimir Kuratowski s’intéresse, comme on l’a déjà vu dans la partie sur l’algèbre de Boole, à l’idée de définir un couple comme un ensemble muni d’une relation d’ordre :

On constate que Kuratowski utilise l’expression paire ordonnée plutôt que le mot couple et la notation des parenthèses pour désigner les ensembles et pas les n-uplets. Voici son modèle pour le couple (a,b) :

Il est très proche du modèle de Tarski-Grothendieck, à part que a est suremballé. Ce souci constant de mettre les éléments a et b au même niveau est dû à la crainte (chez Wiener comme chez Kuratowski) du paradoxe de Russel.

Pourquoi Kuratowski a-t-il abandonné la définition un couple est un ensemble ordonné au profit de cette construction ? Parce que là encore, la définition est circulaire, la relation d’ordre étant une relation, donc un ensemble de couples.

En 1931, Kurt Gödel écrit ceci dans son célèbre article [2] :

Cela correspond à ce modèle, intermédiaire entre celui de Kuratowski et celui de Tarski-Grothendieck :

Gödel propose aussi cette variante :

On remarque que Gödel parle de geordnete Paare comme Kuratowski, et note lui aussi les ensembles entre parenthèses. Il a besoin de parler de relations (pour la logique des prédicats) et définit une relation (ou un prédicat) comme un ensemble de couples. C’est à cette occasion qu’il construit un couple comme un ensemble d’ensembles.

C’est chez Bourbaki que la modélisation vue ci-avant semble être apparue pour la première fois.

La lambada se danse en couple, le lambda-calcul parfois aussi

Dans la mathématique bourbakiste, on a donc cette construction :

  • Une fonction est un ensemble de couples.
  • Un couple est un ensemble (dont l’un des éléments est lui-même une paire ou un singleton).
  • La notion d’ensemble est primitive et tout le reste est basé dessus.

Pour Alonzo Church, la situation est plutôt inverse :

  • La notion de fonction est primitive (« tout est fonction »).
  • L’encodage de Church permet alors de construire les couples à partir des fonctions, dans le λ-calcul.
  • Les couples sont tellement omniprésents qu’il est possible de modéliser les listes par les couples.
  • Munie d’une fonction de hachage, une liste peut alors modéliser un ensemble.

On verra plus bas comment les couples permettent de modéliser des listes. Pour la construction du couple (a,b) en λ-calcul, c’est plutôt simple : on applique la fonction a à la fonction b. Le λ-calcul de Church étant non typé, il est en effet possible d’appliquer une fonction à elle-même (modélisation du couple (a,a) en appliquant la fonction a à elle-même). Et le résultat de l’application de a à b n’est pas nécessairement le même qu’en appliquant la fonction b à a.

Cependant on préfère appliquer une fonction aux deux arguments a et b : le couple (a,b) est donc modélisé par la fonction qui, à toute fonction z, associe z(a,b) :

Pour utiliser les couples, il faut trois choses :

  • une projection sur le premier élément (notée par des crochets couple[0] en Python) nommée first ci-après ;
  • une projection second sur le second élément (notée couple[1] en Python) ;
  • un constructeur de couple, noté cons ci-après.

La première projection est visible dans la moitié gauche de cette image (la moitié droite est le couple (a,b) comme on l’a vu ci-dessus :

Voici les étapes du λ-calcul (réductions successives) mené sur first (a,b) :

On retrouve bien a comme réduction finale : le premier élément du couple (a,b) est bien a.

Quant à la seconde projection, elle donne, appliquée au couple (a,b), la valeur finale b, comme on le voit sur les étapes de cette réduction (seconde projection dans la moitié gauche, couple (a,b) dans la moitié droite) :

Enfin, comme on a vu plus haut comment le couple (a,b) est représenté en λ-calcul, la fonction cons de construction d’un couple est simplement la fonction qui, à xet y, associe le couple (x,y) :

couples et listes

C’est John McCarthy, à la fin des années 1950, qui a le premier programmé le λ-calcul sur un ordinateur. Il s’agissait d’un IBM 704 dont chaque instruction machine mesure 36 bits. Le calcul de l’adresse mémoire sur laquelle il fallait opérer, se fait en soustrayant deux parties de l’instruction :

  • L’adresse de base appelée content of adress register, abrégé en CAR (15 bits sur les 36),
  • et un décrément permettant un adressage plus fin, et stocké dans un champ de 15 bits appelé content of decrement register, abrégé en CDR.

MacCarthy choisit de stocker le premier élément d’un couple dans le CAR, et le second dans le CDR. Voici une vérification de ce fait par une séance de Scheme [3] :

  1. > '(a b)
  2. (a b)
  3. > (car '(a b))
  4. a
  5. > (cdr '(a b))
  6. (b)

Télécharger

La réponse ressemble au modèle de Tarski-Grothendiek vu ci-avant mais si (b) est entre parenthèses contrairement à a, c’est parce qu’en réalité (a b) n’est pas un couple mais une liste, comme on le verra un peu plus bas.

Il a fallu mettre devant (a b) le symbole quote, encore utilisé aujourd’hui en calcul formel, pour ne pas évaluer le couple (a,b). Cela est dû à ce qu’en programmation fonctionnelle, par défaut, le couple (a,b) représente l’application de la fonction a à la fonction b [4]. Par exemple l’évaluation de (cube 3) est l’application de la fonction cube au nombre 3 :

  1. > (define (cube x) (* x x x))
  2. cube
  3. > (cube 3)
  4. 27

Télécharger

La suite de la construction de McCarthy passe par un nouvel objet appelé nil :

  1. > nil
  2. ()

Télécharger

Enfin, en plaçant un nombre a dans le car d’un couple, et un pointeur vers un autre couple dans le cdr, McCarthy modélise une liste dont le premier élément est a et le reste est la liste restant après avoir enlevé a. Les couples (car,cdr) permettent ainsi à McCarthy de représenter des listes en machine, et il a appelé le langage obtenu du nom de List Processor, abrégé en Lisp. Lisp est donc un langage de programmation spécialisé dans le traitement de listes, et les couples ont servi à McCarthy à modéliser les listes de façon récursive. Avec un vocabulaire particulier :

  • le premier élément d’une liste s’appelle son car,
  • la liste privée de son premier élément (c’est une liste donc) est le cdr,
  • le second élément de la liste est le car de son cdr, abrégé en cadr,
  • la liste privée de ses deux premiers éléments est le cddr (cdr du cdr de la liste de départ)
  • le troisième élément de la liste est la car du cddr soit le caddr de la liste :
  1. > (define L '(1 2 3 4))
  2. L
  3. > L
  4. (1 2 3 4)
  5. > (car L)
  6. 1
  7. > (cdr L)
  8. (2 3 4)
  9. > (cadr L)
  10. 2
  11. > (caddr L)
  12. 3

Télécharger

Dans les langages de programmation qui ont succédé à Lisp, les couples sont typiquement représentés en machine par deux éléments stockés à des adresses consécutives.

couples en Python

La notion de couple (a,b) se généralise

  • aux triplets (a,b,c)
  • aux quadruplets (a,b,c,d)
  • aux quintuplets (a,b,c,d,e)

et plus généralement aux n-uplets [5]. Les anglo-saxons utilisent la lettre « t » au lieu de « n » et abrègent t-uplet en tuple. C’est le terme qui a été gardé en Python :

Un couple est un tuple à deux éléments.

Le stockage en mémoire d’un couple est probablement assez similaire à celui de Lisp : deux objets côte à côte en mémoire. Par exemple l’expression

a.__sizeof__()

affiche 28 si a est une liste de deux entiers, et 20 seulement si a est un couple de deux entiers. Ceci signifie qu’un couple d’entiers occupe 20 octets en mémoire, alors que chaque entier occupe 14 octets. Les 4 octets de différence doivent être consacrés, au moins en partie, au type de l’entier (« int »).

Python peut aussi dessiner un couple avec son module graphviz, puisqu’un couple n’est jamais qu’un graphe orienté à deux sommets. Pour dessiner le couple (a,b) on peut

  • mettre a dans le sommet A ;
  • mettre b dans le sommet B ;
  • dessiner une arête allant du sommet A au sommet B.

Cela donne ce script avec export au format png du couple dessiné :

  1. from graphviz import Digraph
  2.  
  3. arrow = Digraph(format="png")
  4.  
  5. arrow.node('A','a')
  6. arrow.node('B','b')
  7. arrow.edge('A','B')
  8.  
  9. arrow.render('flèche',view=True)

Télécharger

Voici le dessin obtenu :

Une variable est un couple

Dans cet article de l’Encyclopédie, d’Alembert écrit que

on appelle quantités variables en Géométrie, les quantités qui varient suivant une loi quelconque. Telles sont les abscisses & les ordonnées des courbes, leurs rayons osculateurs, &c.

On les appelle ainsi par opposition aux quantités constantes, qui sont celles qui ne changent point, comme le diametre d’un cercle, le parametre d’une parabole, &c.

On exprime communément les variables par les dernieres lettres de l’alphabet x, y, z.

Pour les encyclopédistes, une variable possède donc un nom (pour l’« exprimer ») et une quantité.

Un modèle de mémoire informatique a été proposé en 1977 par Dana Scott, comme fonction qui, à un emplacement mémoire, associe son contenu :

Ainsi, à un lieu L, on associe une valeur V. Ce que Scott nomme lieu correspond au nom de la variable [6].

Comme une fonction est un ensemble de couples, une variable est donc un couple :

  1. Son premier élément est le nom de la variable (de type str c’est-à-dire élément d’un langage).
  2. Son second élément est la valeur de la variable (souvent un nombre, mais pas nécessairement).

Voici une petite expérience en Python, pour prouver qu’une variable est effectivement un couple : sur une calculatrice, il y a un bouton var permettant de voir les variables. En Python, c’est la fonction globals qui permet de connaître les variables.

Au début on a quelque chose comme

  1. >>> globals()
  2. {'__package__': None, '__name__': '__main__', '__spec__': None, '__doc__': None, '__loader__': <class '_frozen_importlib.BuiltinImporter'>, '__builtins__': <module 'builtins' (built-in)>}

Télécharger

Ensuite on crée une variable v par affectation :

v = 3

Et v est apparu dans le dictionnaire des variables :

  1. >>> globals()
  2. {'__package__': None, '__name__': '__main__', 'v': 3, '__spec__': None, '__doc__': None, '__loader__': <class '_frozen_importlib.BuiltinImporter'>, '__builtins__': <module 'builtins' (built-in)>}

Télécharger

On voit que la variable v est apparue et que son premier élément est bien entre guillemets : c’est un nom. Les couples sont peut-être peu reconnaissables dans cette écriture d’un dictionnaire Python, mais ils sont bel et bien stockés sous le nom d’« items » :

  1. >>> globals().items()
  2. dict_items([('__package__', None), ('__name__', '__main__'), ('v', 3), ('__spec__', None), ('__doc__', None), ('__loader__', <class '_frozen_importlib.BuiltinImporter'>), ('__builtins__', <module 'builtins' (built-in)>)])

Télécharger

La variable v qu’on a créée ci-dessus apparaît sous cette forme :

('v', 3)

ce qui confirme que Python est conforme au modèle de Scott et Strachey.

application à Sofus

Pour l’instant, la programmation de Sofus en Python fait appel à la programmation objet : dans Sofus (en Python), une variable est un objet doté de méthodes « sofusiennes » comme le doublement. Dans Python, comme on l’a vu ci-dessus, une variable est un couple (item d’un dictionnaire). Il suffit alors de créer un dictionnaire appelé valeur (voir ci-dessous les variables de bash pour la raison de ce nom) et qui contiendra les variables de Sofus :

  1. valeur = {}
  2.  
  3. def vérifier(nom):
  4.     if nom not in valeur:
  5.         raise Exception("La variable "+nom+" n'existe pas")

Télécharger

La fonction vérifier a pour but d’afficher un message d’erreur en français si on essaye d’appliquer une fonction sofusienne à une variable qui n’existe pas. Une variable qui n’existe pas est une variable dont le nom ne figure pas parmi les clés (on appelle clé le premier élement du couple) du dictionnaire.

Comment construire ce fameux dictionnaire de variables ? Comme toujours en Python, on crée une variable par une affectation, qui consiste à accoupler un nom de variable avec une valeur (ici, numérique) :

  1. def affecter(nom,valeur_initiale):
  2.     valeur[nom] = valeur_initiale

Télécharger

Cette fonction, en apparence très simple, fait beaucoup de choses :

  • Si la variable n’existe pas, Python la crée (en ajoutant le couple (nom,valeur_initiale) au dictionnaire valeur).
  • Sinon, Python remplace la valeur actuelle de la variable par valeur_initiale.

Si on veut incrémenter la variable entière de nom n, on n’écrit pas

affecter('n',n+1)

mais

affecter('n',valeur['n']+1)

de manière similaire à bash que l’on verra plus bas. Mais il est plus simple dans ce cas, d’utiliser

augmenter_de('n',1)

En effet le code source de Sofus est entièrement partagé entre

  • les 4 opérations :
  1. def augmenter_de(nom,incrément):
  2.     vérifier(nom)
  3.     valeur[nom] += incrément
  4. def diminuer_de(nom,décrément):
  5.     vérifier(nom)
  6.     valeur[nom] = décrément
  7. def multiplier_par(nom,facteur):
  8.     vérifier(nom)
  9.     valeur[nom] *= facteur
  10. def diviser_par(nom,diviseur):
  11.     vérifier(nom)
  12.     if diviseur == 0:
  13.         valeur[nom] = float('inf')
  14.     else:
  15.         valeur[nom] /= diviseur

Télécharger

(avec le choix de diviser par 0 sans erreur blocante pour permettre le calcul de fonctions homographiques)

  • les fonctions sofusiennes :
  1. def inverser(nom):
  2.     vérifier(nom)
  3.     if valeur[nom] == 0:
  4.         valeur[nom] = float('inf')
  5.     else:
  6.         valeur[nom] = 1/valeur[nom]
  7. def doubler(nom):
  8.     vérifier(nom)
  9.     valeur[nom] *= 2
  10. def tripler(nom):
  11.     vérifier(nom)
  12.     valeur[nom] *= 3
  13. def quadrupler(nom):
  14.     vérifier(nom)
  15.     valeur[nom] *= 4
  16. def quintupler(nom):
  17.     vérifier(nom)
  18.     valeur[nom] *= 5

Télécharger

  • et les fonctions sur les pourcentages :
  1. def augmenter_pourcent(nom,pourcentage):
  2.     vérifier(nom)
  3.     valeur[nom] *= (1+pourcentage/100)
  4. def diminuer_pourcent(nom,pourcentage):
  5.     vérifier(nom)
  6.     valeur[nom] *= (1-pourcentage/100)
  7. def multiplier_pourcent(nom,pourcentage):
  8.     vérifier(nom)
  9.     valeur[nom] *= pourcentage/100
  10. def diviser_pourcent(nom,pourcentage):
  11.     vérifier(nom)
  12.     if pourcentage == 0:
  13.         valeur[nom] = float('inf')
  14.     else:
  15.         valeur[nom] /= pourcentage/100

Télécharger

C’est tout ! Avec l’ajout de tests de parité pour programmer la suite de Collatz, voici l’intégralité du langage de programmation Sofus :

  1. valeur = {}
  2.  
  3. def vérifier(nom):
  4.     if nom not in valeur:
  5.         raise Exception("La variable "+nom+" n'existe pas")
  6.  
  7. def affecter(nom,valeur_initiale):
  8.     valeur[nom] = valeur_initiale
  9. def augmenter_de(nom,incrément):
  10.     vérifier(nom)
  11.     valeur[nom] += incrément
  12. def diminuer_de(nom,décrément):
  13.     vérifier(nom)
  14.     valeur[nom] = décrément
  15. def multiplier_par(nom,facteur):
  16.     vérifier(nom)
  17.     valeur[nom] *= facteur
  18. def diviser_par(nom,diviseur):
  19.     vérifier(nom)
  20.     if diviseur == 0:
  21.         valeur[nom] = float('inf')
  22.     else:
  23.         valeur[nom] /= diviseur
  24.  
  25. def inverser(nom):
  26.     vérifier(nom)
  27.     if valeur[nom] == 0:
  28.         valeur[nom] = float('inf')
  29.     else:
  30.         valeur[nom] = 1/valeur[nom]
  31. def doubler(nom):
  32.     vérifier(nom)
  33.     valeur[nom] *= 2
  34. def tripler(nom):
  35.     vérifier(nom)
  36.     valeur[nom] *= 3
  37. def quadrupler(nom):
  38.     vérifier(nom)
  39.     valeur[nom] *= 4
  40. def quintupler(nom):
  41.     vérifier(nom)
  42.     valeur[nom] *= 5
  43. def est_pair(nom):
  44.     vérifier(nom)
  45.     return valeur[nom]%2 == 0
  46. def est_impair(nom):
  47.     vérifier(nom)
  48.     return valeur[nom]%2 == 1
  49. def est_divisible_par(nom,diviseur):
  50.     vérifier(nom)
  51.     if diviseur == 0:
  52.         return False
  53.     else:
  54.         return valeur[nom]%diviseur == 0
  55.  
  56.  
  57. def augmenter_pourcent(nom,pourcentage):
  58.     vérifier(nom)
  59.     valeur[nom] *= (1+pourcentage/100)
  60. def diminuer_pourcent(nom,pourcentage):
  61.     vérifier(nom)
  62.     valeur[nom] *= (1-pourcentage/100)
  63. def multiplier_pourcent(nom,pourcentage):
  64.     vérifier(nom)
  65.     valeur[nom] *= pourcentage/100
  66. def diviser_pourcent(nom,pourcentage):
  67.     vérifier(nom)
  68.     if pourcentage == 0:
  69.         valeur[nom] = float('inf')
  70.     else:
  71.         valeur[nom] /= pourcentage/100

Télécharger

En enregistrant le code source ci-dessus sous le nom de sofus.py il suffit, pour programmer en Sofus, de commencer son script (ou d’entrer dans la console)

from sofus import *

Par exemple, pour calculer une valeur approchée du nombre d’Or, ce script convient :

  1. affecter('phi',1)
  2. for _ in range(20):
  3.     inverser('phi')
  4.     augmenter_de('phi',1)

Télécharger

Après cela, on obtient la valeur approchée en évaluant l’expression

valeur['phi']

Un autre exemple, issu du programme de 1re générale :

Quelle est la hauteur (nombre de disques) de la plus petite tour de Hanoï qu’on ne peut résoudre en moins d’un million de mouvements ?

On a besoin de deux variables, disques qui compte les disques, et déplacements qui est le nombre minimum de déplacements nécessaires permettant de résoudre la tour de Hanoï. Pour 0 disques, il y a 0 déplacements :

  1. affecter('disques',0)
  2. affecter('déplacements',0)
  3. while valeur['déplacements']<1e6:
  4.     augmenter_de('disques',1)
  5.     doubler('déplacements')
  6.     augmenter_de('déplacements',1)

Télécharger

et pour étudier la suite de Collatz :

  1. affecter('u',65)
  2. while valeur['u']>1:
  3.     if est_impair('u'):
  4.         tripler('u')
  5.         augmenter_de('u',1)
  6.     diviser_par('u',2)
  7.     print(valeur['u'])

Télécharger

variables en bash

On a évoqué ci-dessus la fonction qui, au nom d’une variable, associe la valeur de cette variable. C’est cette fonction que Scott appelle état de la machine. Cette fonction est notée, en bash, par le symbole « dollar ». Ainsi la séquence suivante n’a pas le même effet qu’en Python :

  1. ♟️ variable=3
  2.  
  3. ♟️ echo variable
  4. variable

Télécharger

Le type essentiel de bash est la chaîne de caractères, on n’a donc pas besoin d’utiliser les guillemets pour préciser que le mot qu’on écrit est une chaîne de caractères. Du coup on a demandé à bash d’afficher (« echo ») le mot variable et non le contenu de la variable. Ceci par contre donne un comportement similaire à celui de Python :

  1. ♟️ variable=3
  2.  
  3. ♟️ echo $variable
  4. 3

Télécharger

L’expression $variable signifie « ce qui est dans la variable », dans la droite ligne de la théorie de Scott et Strachey.

Le second type de base de bash est l’entier naturel. Ci-dessus bash a compris que 3 n’est pas une chaîne de caractères mais un nombre (entier).

L’incrémentation de la variable v (passage de la valeur 3 à la valeur 4) ne peut toutefois être faite en affectant v à la valeur $v+1 :

  1. ♟️ v=3
  2. ♟️ echo v+1
  3. v+1
  4. ♟️ echo $v+1
  5. 3+1
  6. ♟️ echo $(($v+1))
  7. 4
  8. ♟️ echo $v
  9. 3
  10. ♟️ let "v=$v+1"
  11. ♟️ echo $v
  12. 4

Télécharger

Ce résumé « la valeur de la variable » par le symbole « $ » n’est pas spécifique de bash, on le trouve également en perl et en php.

Voici une application à Sofus (simplifié car ne portant que sur des entiers) :

#!/bin/bash
function afficher {
   cowsay -f koala $(($1))
}
function mettre {
   let "$3=$1"
}
function augmenter {
   let "$1=$1+$3"
}
function diminuer {
   let "$1=$1-$3"
}
function multiplier {
   let "$1=$1*$3"
}
function diviser {
   let "$1=$1/$3"
}
function doubler {
   let "$1=$1*2"
}
function tripler {
   let "$1=$1*3"
}
function quadrupler {
   let "$1=$1*4"
}
function quintupler {
   let "$1=$1*5"
}
function sextupler {
   let "$1=$1*6"
}
function octupler {
   let "$1=$1*8"
}
function décupler {
   let "$1=$1*10"
}

L’avantage de cette version par rapport à la version Python est qu’elle ne nécessite pas de parenthèses pour écrire les fonctions, ce qui donne à la programmation dans cette version de Sofus, une plus grande proximité avec la langue française. Par exemple si le code source ci-dessus a été téléchargé sous le nom sofus.sh et rendu exécutable [7] :

♟️ source sofus.sh
♟️ mettre 13 dans v
♟️ afficher v
____
< 13 >
----
 \
  \
      ___  
    {~._.~}
     ( Y )
    ()~*~()  
    (_)-(_)  
♟️ tripler v
♟️ afficher v
____
< 39 >
----
 \
  \
      ___  
    {~._.~}
     ( Y )
    ()~*~()  
    (_)-(_)  
♟️ augmenter v de 1
♟️ afficher v
____
< 40 >
----
 \
  \
      ___  
    {~._.~}
     ( Y )
    ()~*~()  
    (_)-(_)  
♟️ diviser v par 2
♟️ afficher v
____
< 20 >
----
 \
  \
      ___  
    {~._.~}
     ( Y )
    ()~*~()  
    (_)-(_)  
♟️

typage d’un programme

Supposons pour simplifier l’exposé que les variables ont des valeurs réelles ; alors selon la théorie de Scott

  • Une variable est un couple de la forme (s,x) où s∈L (un langage) et x∈R (valeur réelle).
  • Un état de l’ordinateur est donc une fonction L→R
  • Le type d’une instruction est alors (L→R)→(L→R) (effet de bord).
  • Un programme est une suite d’instructions, c’est-à-dire une fonction qui, à tout indice n∈N, associe une instruction. Le type d’un programme est donc N→((L→R)→(L→R)).

Pour peu qu’un programme implémente une fonction RR, l’implémentation est plus compliquée que la fonction implémentée. Ceci explique peut-être qu’il ait fallu attendre les années 1970 pour que Scott et Strachey créent (pour la première fois) une sémantique des programmes informatiques.

Emballages

Il n’y a pas que pour construire un couple en théorie des ensembles, que l’idée d’emballer dans plusieurs couches un (ou plusieurs) objet mathématique, s’est révélée fructueuse. On va voir ici, comme un bonus à cet article, trois exemples d’utilisation en informatique :

monades

Catégories et foncteurs

Un ensemble de couples est un graphe orienté. Un multiensemble (où chaque couple peut apparaître plusieurs fois) de couples tel que pour chaque sommet s, le couple (s,s) est dans le multiensemble, s’appelle une catégorie. Les sommets du graphe s’appellent alors les objets de la catégorie. Les couples de la forme (s,s) sont notés s→s ou ids et appelés identités. En effet dans une catégorie les flèches représentent typiquement des fonctions, appelées morphismes.

Étant données deux catégories A et B, une fonction f entre les deux catégories est un foncteur si

  • Pour toute flèche a→b, de la catégorie A, f(a)→f(b) est une flèche de la catégorie B.
  • Pour tout objet a de la catégorie A, f(ida)=idf(a)

En d’autres termes, un foncteur transporte les arêtes d’une catégorie vers les arêtes d’une autre catégorie, de manière cohérente avec la structure de multigraphe. La notion a été inspirée par les travaux de Henri Poincaré en topologie : Un foncteur permet d’associer les homéomorphismes d’un espace topologique, à des homomorphismes de son groupe de Poincaré [8].

Un exemple archétypal de foncteur est la fonction map de Python. Par exemple, à partir de la catégorie des réels, map transforme une fonction RR en une fonction (NR)→(NR) (à une liste L1 de réels, elle associe une liste de réels). Ce genre de foncteur, en Haskell, s’appelle une monade :

Une monade est un foncteur M assorti de deux fonctions

  • unit (ou return) de type a → M a
  • join de type M M a → M a

En, bref, la monade M permet d’emballer a dans un paquet cadeau M a, sans qu’il y ait besoin de suremballer, puisqu’une deuxième couche peut être réduite (par join) à une seule.

La construction des ensembles peut être faite en programmation fonctionnelle, par cette monade :

à ces deux objets a et b unit associe ces deux ensembles

Dans ce cas la jointure est la réunion ensembliste (à un ensemble d’ensembles elle associe leur réunion).

Une monade sert donc à emballer ou empaqueter une fonction (en Haskell tous les objets sont des fonctions). On parle d’encapsulation.

Listes de Python

De même on peut englober un réel (flottant de Python) dans une liste, pour en faire une monade :

  1. def unit(x:float)-> list:
  2.     return [x]
  3.  
  4. def join(MMx:list) -> list :
  5.     return [x for Mx in MMx for x in Mx]
  6.  
  7. def bind(monade, f) -> list:
  8.     return join(map(unit,map(f,monade)))

Télécharger

Avec ça on aura

  1. >>> unit(3)
  2. [3]
  3. >>> join([[1],[2],[3]])
  4. [1,2,3]

Télécharger

Avec ces deux primitives unit et join on peut définir bind qui est utilisé en Haskell (à la place de join) pour définir une monade.

Leibniz

Noter que dans sa monadologie, Leibniz évoquait un concept quelque peu opposé à celui des monades de Haskell :

1. La Monade, dont nous parlerons ici, n’est autre chose qu’une substance simple, qui entre dans les composés ; simple, c’est-à-dire sans parties.

Leibniz semble décrire plutôt les éléments qui sont dans l’ensemble, que l’ensemble.

L’idée de déballer le paquet pour aller chercher ce qui est dedans (jointure) est également niée par Leibniz :

7. Il n’y a pas moyen aussi d’expliquer comment une Monade puisse être altérée ou changée dans son intérieur par quelque autre créature, puisqu’on n’y saurait rien transposer, ni concevoir en elle aucun mouvement interne, qui puisse être excité, dirigé, augmenté ou diminué là dedans, comme cela se peut dans les composés, où il y a des changements entre les parties. Les Monades n’ont point de fenêtres, par lesquelles quelque chose y puisse entrer ou sortir. Les accidents ne sauraient se détacher, ni se promener hors des substances, comme faisaient autrefois les espèces sensibles des scolastiques. Ainsi ni substance, ni accident peut entrer de dehors dans une Monade.

On peut se demander à quoi ça sert, en Haskell, d’emballer une fonction dans un paquet cadeau. En fait, les monades sont très utilisées pour gérer les effets de bord chers à Dana Scott, en ajoutant quelque chose (le contexte, des variables globales ou l’environnement) dans le paquet. Les monades les plus importantes sont IO (entrées-sortie) et State (état de la machine). Elles sont similaires au itérateurs de Python, qui à chaque appel, gardent mémoire de l’état de l’itération. Mais en Python, enrober une fonction avec une variable globale, se fait par un décorateur.

décorateurs

En Python, ce sont les fonctions que l’on décore. En fait il ne s’agit pas que d’emballer la fonction dans du papier cadeau, mais plutôt de la transformer (par des ajouts).

Pour voir à quoi cela peut servir de modifier une fonction après l’avoir définie, on va prendre pour exemple un problème qui se pose chaque fois que l’on veut représenter graphiquement une fonction prenant de grandes valeurs. Par exemple l’hyperbole représentant la fonction inverse est difficile à afficher avec matplotlib.pyplot :

matplotlib.pyplot

Pour représenter graphiquement une fonction, un moyen simple est de fournir à matplotlib.pyplot une liste X d’abscisses et une liste Y d’ordonnées. On commence donc le script par un import :

  1. from matplotlib.pyplot import *

Ensuite on construit les listes X et Y, par exemple

  1. X = [x/10 for x in range(100)]
  2. Y = [1/x for x in X]

Télécharger

Enfin on crée l’affichage et on le regarde, avec

  1. plot(X,Y)
  2. show()

Télécharger

Mais ça ne marche pas, on a un message d’erreur quand on essaye de diviser par 0.

Pour pouvoir représenter graphiquement une fonction qui n’est pas définie en 0, on s’arrange pour remplacer 0 par une valeur proche mais possédant un inverse. La fonction représentée graphiquement est donc définie ainsi :

  1. def inverse(x):
  2.     if x==0:
  3.         x = 1e-6
  4.     return 1/x

Télécharger

Comme on a approché 0 par 10-6, la première ordonnée est 1000000 et on ne voit pas bien l’hyperbole. Pour résoudre ce problème, on propose de limiter les ordonnées (par exemple en leur imposant d’être comprises entre -1 et 1). La fonction faisant cela est une fonctionnelle (fonction dont la valeur d’entrée et la valeur renvoyée sont elles-mêmes des fonctions), que voici :

  1. def limiter(f):
  2.     def fL(x):
  3.         if -1<=f(x)<=1:
  4.             return f(x)
  5.         elif f(x)<-1:
  6.             return -1
  7.         else:
  8.             return 1
  9.     return fL

Télécharger

La valeur d’entrée f est donc la fonction à limiter, pour ce faire on définit une fonction fL (fonction limitée) dépendant de la variable x∈R et qui coïncide avec f(x) si x est entre -1 et 1, avec -1 ou 1 sinon. La fonctionnelle limiter modifie la fonction f selon cet algorithme :

  • elle définit une fonction locale fL, qui est la version limitée de f (les valeurs renvoyées sont entre -1 et 1) ;
  • elle renvoie cette fonction ;
  • pour en faire un décorateur, il reste à remplacer la fonction non limitée, par la fonction limitée.

Pour mieux voir l’hyperbole, il suffit maintenant de précéder la définition de la fonction inverse, d’un appel à la limiter :

  1. @limiter
  2. def inverse(x):
  3.     if x==0:
  4.         x = 1e-6
  5.     return 1/x

Télécharger

Cette seule ligne ajoutée avant la définition de la fonction donne une hyperbole bien mieux visible :

On peut se demander à quoi cela sert de décorer une fonction, plutôt que de la modifier directement. L’intérêt essentiel des décorateurs est qu’ils peuvent servir plusieurs fois.

Exemples

  1. @limiter
  2. def cube(x):
  3.     return x**3

Télécharger

Limiter la fonction cube permet de mieux voir son comportement au voisinage de l’origine.

  1. @limiter
  2. def ln(x):
  3.     if x<=0:
  4.         x = 1e-6
  5.     return log(x)

Télécharger

  1. @limiter
  2. def exponentielle(x):
  3.     return exp(x)

Télécharger

D’autres exemples de décorateurs qui peuvent trouver de l’intérêt en mathématiques, sont à chercher dans l’analyse fonctionnelle :

ou toute autre méthode d’approximation d’une fonction.

sucre

Le sucre syntaxique s’applique à un langage de programmation. L’expression s’inspire du fondant (pâtisserie) :

  • D’une part on enrobe le langage (on lui rajoute des choses sans rien lui enlever).
  • D’autre part le résultat a un goût agréable (sucré) : le nouveau langage (enrichi) est plus naturel.

Par exemple CoffeeScript est décrit comme du sucre syntaxique sur JavaScript. Ce qui signifie que pour obtenir la fonction Javascript suivante :

  1. var sinus;
  2.  
  3. sinus = function(x) {
  4.   return sin(x / pi * 180);
  5. };

Télécharger

on entre simplement ceci dans l’interpréteur CoffeeScript :

sinus = (x) -> sin x/pi*180

C’est plus court et plus proche de la langue naturelle. Ce que l’on résume par l’expression sucre syntaxique.

Histoire de parenthèses

Toujours en CoffeeScript, si on écrit simplement

sin x

l’équivalent JavaScript obtenu est

sin(x);

Au début du 18e siècle, l’image de x par f était notée fx. Le premier à utiliser des parenthèses pour englober l’argument et noter f(x) à la place, est Leonhard Euler, dans cet article de 1734 sur le calcul infinitésimal (longueurs de courbes) :

Dans la seconde phrase, il écrit que f(x/a+c) est l’image de x/a+c par la fonction f. La notation s’est très largement généralisée jusqu’à aujourd’hui, au point que les parenthèses sont considérées, en Python, comme une opération de passage des arguments à la fonction.

Pourtant une autre notation que f(x) existe depuis longtemps, c’est f x. Par exemple

  • on écrit aussi souvent sin x que sin(x) ;
  • on écrit aussi souvent cos x que cos(x) ;
  • on écrit plus souvent ln x que ln(x).

La notation utilisée dans CoffeeScript a donc du sens, elle est également présente dans les langages de programmation fonctionnelle comme Haskell, dans Ruby, et comme on l’a vu dans CoffeeScript : dans ces langages, les parenthèses sont optionnelles. Le sucre c’est l’absence (facultative) de parenthèses, la syntaxe c’est les parenthèses que l’on peut (et parfois, doit) mettre quand même. Les règles du λ-calcul expliquent quand on peut se passer de parenthèses, et lorsqu’on en a la possibilité, on le fait pour éviter d’être submergé.

Autres exemples

Le saviez-vous ? Dans la langue française, les mots sont séparés par des espaces, pas par des parenthèses. Si, si, vérifiez si vous voulez. Avec CoffeeScript on a

version CoffeeScript version JavaScript
avancer de trente pas avancer(de(trente(pas)));
tourner vers la gauche de trois tours tourner(vers(la(gauche(de(trois(tours))))));
diviser v par 2 diviser(v(par(2)));
tripler v tripler(v);
augmenter v de 2 augmenter(v(de(2)));
mettre deux dans x mettre(deux(dans(x)));
print "coucou" print("coucou");

Ce dernier exemple est ce qui est arrivé en passant de Python 2 à Python 3 : print qui jusqu’alors était (correctement, du point de vue linguistique) une instruction, est devenu une fonction. Ce faisant Python a perdu en naturel ce qu’il a gagné en efficacité.

Syntaxe et grammaire

La phrase « Augmente v de 2 » (écrite à l’impératif pour montrer que c’est une phrase) ne comporte pas de sujet : celui-ci est implicite car à l’impératif, le sujet est toujours l’interlocuteur à qui on donne un ordre. Il reste alors 3 éléments à analyser grammaticalement dans cette phrase :

  • « augmente » est le verbe de cette phrase, il indique une action à effectuer ;
  • « v » est le complément d’objet direct, il indique sur quoi doit porter l’action (qu’est-ce qu’il faut augmenter) ;
  • « de 2 » est le complément d’objet indirect, il indique comment augmenter v ; il est formé de deux mots :
    • « de » est une préposition (c’est à cela en général, qu’on reconnaît un complément indirect), il indique le rapport entre ce qui précède et ce qui suit :
    • « 2 » est un nom indiquant la quantité dont il faut augmenter v.

Spacy confirme cette structure de la phrase, par ce graphe :

On a vu dans la partie sur bash, que cette même phrase (sans la majuscule au début) est correctement comprise et interprétée par bash :

  1. ♟️ echo $v
  2. 3
  3. ♟️ augmenter v de 2
  4. ♟️ echo $v
  5. 5

Télécharger

Quel miracle permet à bash de « comprendre » aussi bien la langue française ? Vous l’avez deviné, c’est le sucre syntaxique. Pour rappel voici la fonction écrite en bash :

function augmenter {
   let "$1=$1+$3"
}

Elle fait que le premier argument (supposé être une variable) est affecté par la somme de sa valeur actuelle, et de celle du troisième argument. Le second argument n’est donc pas utilisé. Les commandes suivantes auraient eu le même effet :

  1. augmenter v par 2
  2. augmenter v pour 2
  3. augmenter v plus 2
  4. augmenter v dans 2
  5. augmenter v de 2
  6. augmenter v augmentant 2
  7. augmenter v autour 2
  8. augmenter v vautour 2
  9. augmenter v maison 2
  10. augmenter v camion 2
  11. augmenter v 2 2
  12. augmenter v 42 2
  13. augmenter v sur 2
  14. augmenter v v 2

Télécharger

alors qu’elles n’ont pas vraiment de sens.

L’affectation fonctionne de la même manière :

function mettre {
   let "$3=$1"
}

Le second argument n’est pas utilisé, il n’est donc pas nécessaire qu’il soit « dans ». Voici la structure grammaticale de la phrase « mettre 3 dans v » :

Note : cette manière d’écrire l’affectation d’une variable remonte au tout début des langages informatiques évolués, puisqu’elle est dûe à Grace Hopper qui est l’auteur du premier compilateur. Cette fois-ci, le nombre 3 est complément d’objet direct, et la variable v est dans le complément d’objet indirect « dans v ». Depuis Fortran, l’usage est aujourd’hui de noter l’affectation comme une relation infixe (= ou := ou ←) et de mettre le nom de la variable à gauche, ce qui en fait le sujet de la phrase. « v←3 » se traduit alors par la forme passive de la phrase précédente, comme « v prend 3 » ou « v accepte 3 » ou « v est affecté par 3 ». Ce qui est moins proche de la langue usuelle, que la forme active « mettre 3 dans v ». C’était du moins l’opinion de Grace Hopper.

La modification en place des variables de Sofus permet également d’écrire des phrases sans complément d’objet indirect, comme celle-ci qui n’a que le complément d’objet direct :

Noter que le graphe syntaxique permet de voir la différence entre « doubler » et « le double » puisque cette expression n’est même pas une phrase complète (il n’y a pas de verbe) :


[1Ce faisant, Boole assimile l’implication logique, à la divisibilité : une conséquence d’une prémisse est un multiple de celle-ci, au sens de l’algèbre de Boole.

[2Dans lequel il représente le couple d’entiers (a,b) par l’unique entier 2a×3b : c’est le codage de Gödel, d’un grand intérêt théorique mais ayant peu d’intérêt pratique, à cause de la taille des entiers ainsi générés.

[3Effectuée dans la console script fu qui se trouve en bas des flitres de Gimp.

[4Si f est une fonction et v est une variable, (f v) désigne l’application de f à v (qu’on note également f(v) du moins depuis Euler, ou parfois v.f notamment en théorie des groupes) mais Dirac utilise des chevrons dans la notation bra-ket : dans cette vision géométrique, il s’agit d’un produit scalaire entre le premier élément du couple (le bra) et le second élément du couple (le ket). On peut donc utiliser le mot bra au lieu de car et le mot ket au lieu de cdr.

[5On peut définir une suite comme un n-uplet de taille infinie. L’évaluation paresseuse permet à haskell de manipuler ces objets.

[6En fait, à l’époque des travaux de Scott et Strachey, chaque lieu était un registre, portant un nom fixe. En Python, on associe un nom (de variable) à chaque lieu, par une fonction appelée référence (informatique), et on joue l’économie en ne mettant une valeur qu’en un lieu unique (Avant, il était possible de mettre le même nombre 3 en u et en v. En Python on place chaque valeur possible en un lieu unique, qui peut varier au cours de l’exécution). La fonction L→V de Scott possède donc une fonction réciproque, notée id en Python. Par exemple id(3) donne l’emplacement mémoire où est rangé le nombre 3. En composant id par la référence on retrouve la fonction évoquée ici (qui, à un nom, associe une valeur).

[7Si ça ne fonctionne pas tel quel, c’est probablement à cause de l’affichage où un nounours donne la valeur de la variable dans un phylactère. Dans ce cas essayer sudo apt-get install cowsay ou, si on n’arrive pas à installer cowsay, remplacer la ligne cowsay -f koala $(($1)) par echo $(($1)).

[8Ce sont des travaux dans ce domaine qui ont valu à Grigori Perelman à la fois une médaille Fields et un prix Clay. On s’en souvient non parce que le nom de Poincaré y est associé, que parce que Perelman a refusé les deux.


Commentaires