Composition de programmes

En mathématiques, un nombre rationnel est un nombre qui peut s'exprimer comme le quotient de deux nombres entiers. Les nombres rationnels constituent un sous-ensemble important des nombres réels. Un nombre rationnel tel que 1/3 ou 17/29 est généralement écrit comme suit :

<Numérateur> / <dénominateur>

dans lequel <numérateur> et <dénominateur> représentent des valeurs entières. Les deux parties sont nécessaires pour caractériser exactement la valeur du nombre rationnel. Si l'on effectue réellement la division des nombres entiers, on obtient une approximation de type float, et l'on perd la précision exacte des nombres entiers.

>>> 1/3
0.3333333333333333
>>> 1/3 == 0.333333333333333300000 # La division d'entiers donne une approximation
True

Cependant, nous pouvons créer une représentation exacte pour les nombres rationnels en combinant le numérateur et le dénominateur.

Nous avons constaté en utilisant des abstractions fonctionnelles que nous pouvons commencer à programmer de manière productive avant de mettre en œuvre certaines parties de notre programme. Commençons par supposer que nous ayons déjà un moyen de construire un nombre rationnel à partir d'un numérateur et d'un dénominateur. Supposons également qu'étant donné un nombre rationnel, nous ayons un moyen de retrouver le numérateur et le dénominateur qui le constituent. Supposons en outre que le constructeur et les sélecteurs soient disponibles comme les trois fonctions suivantes :

• rational (n, d) renvoie le nombre rationnel dont le numérateur est n et le dénominateur d.
• numer (x) renvoie le numérateur du nombre rationnel x.
• denom (x) renvoie le dénominateur du nombre rationnel x.

Nous utilisons ici une stratégie puissante de conception de programmes : des vœux pieux. Nous n'avons pas encore dit comment est représenté un nombre rationnel, ni comment les fonctions numer, denom et rational doivent être mises en œuvre. Pourtant, si nous définissions ces trois fonctions, nous pourrons ajouter, multiplier, imprimer et tester l'égalité des nombres rationnels :

>>> def add_rationals(x, y):
        nx, dx = numer(x), denom(x)
        ny, dy = numer(y), denom(y)
        return rational(nx * dy + ny * dx, dx * dy)

>>> def mul_rationals(x, y):
        return rational(numer(x) * numer(y), denom(x) * denom(y))

>>> def print_rational(x):
        print(numer(x), '/', denom(x))

>>> def rationals_are_equal(x, y):
        return numer(x) * denom(y) == numer(y) * denom(x)

Nous avons maintenant les opérations sur des nombres rationnels définies à l'aide des fonctions de sélection, numer et denom, et du constructeur rational, mais nous n'avons pas encore défini ces fonctions. Ce dont nous avons besoin, c'est d'un moyen d'assembler un numérateur et un dénominateur en une valeur composite.

Pour nous permettre de mettre en œuvre le niveau concret de notre abstraction de données, Python fournit une structure composée appelée list, qui peut être construite en plaçant les expressions entre crochets séparées par des virgules. Une telle expression s'appelle une liste littérale.

>>> [ 10 , 20 ]
[10, 20]

Il existe deux façons de consulter les éléments d'une liste. La première est notre méthode familière d'affectation multiple, qui décompose une liste en ses éléments individuels et lie chaque élément à un autre nom.

>>> pair = [10, 20]
>>> pair
[10, 20]
>>> x, y = pair
>>> x
10
>>> y
20

Une deuxième méthode pour accéder aux éléments d'une liste est par l'utilisation d'un indice placé entre crochets. Contrairement à une liste littérale, une expression entre crochets suivant directement une autre expression ne s'évalue pas à une valeur de liste, mais sélectionne un élément à partir de la valeur de l'expression précédente.

>>> pair[0]
10
>>> pair[1]
20

Les listes Python (et les séquences ou tableaux dans la plupart des autres langages de programmation) ont un indice qui commence à 0, ce qui signifie que l'indice 0 sélectionne le premier élément de la liste, l'indice 1 sélectionne le second, et ainsi de suite. Une intuition qui supporte cette convention d'indexation est que l'indice représente le décalage d'un élément par rapport au début de la liste.

La fonction équivalente à l'opérateur crochets d'indiçage d'élément s'appelle getitem, et elle utilise également des indices commençant à 0 pour sélectionner les éléments d'une liste.

>>> from operator import getitem
>>> getitem(pair, 0)
10
>>> getitem(pair, 1)
20

Les listes à deux éléments ne sont pas la seule méthode de représentation de paires de Python. Toute façon de regrouper deux valeurs peut être considérée comme une paire. Les listes sont une méthode courante pour le faire. Les listes peuvent également contenir plus de deux éléments, comme nous le verrons plus loin dans ce tutoriel.

Représenter des nombres rationnels. Nous pouvons maintenant représenter un nombre rationnel par deux entiers : un numérateur et un dénominateur.

>>> def rational(n, d):
        return [n, d]

>>> def numer(x):
        return x[0]

>>> def denom(x):
        return x[1]

Avec les opérations arithmétiques que nous avons définies plus tôt, nous pouvons maintenant manipuler des nombres rationnels avec les fonctions que nous avons définies.

>>> half = rational(1, 2)
>>> print_rational(half)
1 / 2
>>> third = rational(1, 3)
>>> print_rational(mul_rationals(half, third))
1 / 6
>>> print_rational(add_rationals(third, third))
6 / 9

Comme le montre l'exemple ci-dessus, notre implémentation des nombres rationnels ne simplifie pas les nombres rationnels à leur fraction irréductible. Nous pouvons remédier à cette lacune en modifiant la mise en œuvre de la fonction rational. Si nous avons une fonction permettant de calculer le plus grand dénominateur commun (PGDC) de deux entiers, nous pouvons l'utiliser pour simplifier le numérateur et le dénominateur et obtenir une fraction irréductible avant de construire la paire. Comme pour beaucoup d'outils utiles, une telle fonction existe déjà dans la bibliothèque Python et s'appelle gcd :

>>> from fractions import gcd
>>> def rational(n, d):
        g = gcd(n, d)
        return (n//g, d//g)

L'opérateur de division entière, //, exprime la division entière, qui arrondit la partie fractionnaire du résultat de division. Puisque nous savons que g est un diviseur commun de n et de d, la division entière est exacte dans ce cas. Cette nouvelle mise en œuvre de rational garantit que les nombres rationnels sont exprimés sous la forme de fractions irréductibles.

>>> print_rational(add_rationals(third, third))
2 / 3

Cette amélioration s'est faite en modifiant le constructeur sans changer les fonctions qui implémentent les opérations arithmétiques réelles.

Avant de poursuivre avec d'autres exemples de données composées et d'abstraction de données, considérons certaines des questions soulevées par l'exemple des nombres rationnels. Nous avons défini les opérations en termes du constructeur rational et de sélecteurs numer et denom. En général, l'idée sous-jacente de l'abstraction de données est d'identifier un ensemble d'opérations de base dans lequel s'exprimeront toutes les manipulations de valeurs d'un certain genre, puis d'utiliser uniquement ces opérations de manipulation des données. En limitant l'utilisation des opérations de cette façon, il est beaucoup plus facile de modifier la représentation des données abstraites sans modifier le comportement d'un programme.

Pour les nombres rationnels, différentes parties du programme manipulent des nombres rationnels en utilisant différentes opérations, comme décrit dans ce tableau.

Dans chaque couche ci-dessus, les fonctions de la dernière colonne forment une barrière abstractionnelle. Ces fonctions sont appelées par un niveau supérieur et implémentées en utilisant un niveau d'abstraction inférieur.

Une violation de cette barrière se produit chaque fois qu'une partie du programme qui pourrait utiliser une fonction de niveau supérieur utilise plutôt une fonction de niveau inférieur. Par exemple, il est souhaitable, pour écrire une fonction qui calcule le carré d'un nombre rationnel, d'utiliser mul_rational, ce qui ne présuppose rien sur la mise en œuvre interne d'un nombre rationnel.

>>> def square_rational(x):
        return mul_rational(x, x)

Se référer directement aux numérateurs et dénominateurs violerait une barrière d'abstraction :

>>> def square_rational_violating_once(x):
        return rational(numer(x) * numer(x), denom(x) * denom(x))

Supposer que les rationnels sont représentés par des listes à deux éléments violerait deux barrières d'abstraction :

>>> def square_rational_violating_twice(x):
        return [x[0] * x[0], x[1] * x[1]]

Les barrières d'abstraction rendent les programmes plus faciles à maintenir et à modifier. Moins les fonctions dépendent d'une représentation particulière, moins il y a de changements à faire lorsque l'on veut modifier cette représentation. Ces trois implémentations de square_rational renvoient le résultat correct, mais seule la première est robuste pour les changements à venir. La fonction square_rational ne nécessiterait pas de mise à jour même si nous avons modifié la représentation des nombres rationnels. En revanche, square_rational_violating_once devrait être modifié chaque fois que les signatures du sélecteur ou du constructeur ont changé, et square_rational_violating_twice nécessiterait une mise à jour chaque fois que la mise en œuvre interne de nombres rationnels a changé.

Les barrières d'abstraction façonnent la manière dont nous pensons aux données. Une représentation valide d'un nombre rationnel ne se limite pas à une mise en œuvre particulière (comme une liste à deux éléments) ; c'est une valeur renvoyée par rational qui peut être transmise à numer et denom. En outre, la relation appropriée doit s'appliquer au constructeur et aux sélecteurs. À savoir, si nous construisons un nombre rationnel x à partir des entiers n et d, alors il faut que numer (x) / denom (x) soit égal à n / d.

En général, nous pouvons exprimer des données abstraites en utilisant une collection de sélecteurs et constructeurs, ainsi que certaines propriétés de comportement. Tant que les propriétés de comportement sont satisfaites (par exemple, la propriété de division ci-dessus), les sélecteurs et les constructeurs constituent une représentation valide d'une sorte de données. Les détails de mise en œuvre sous une barrière d'abstraction peuvent changer, mais si le comportement ne l'est pas, l'abstraction des données reste valide et tout programme écrit à l'aide de cette abstraction de données restera correct.

Ce point de vue peut être appliqué de manière générale, y compris les valeurs de paires que nous avons utilisées pour implémenter des nombres rationnels. Nous n'avons jamais vraiment dit beaucoup de choses sur ce qu'était une paire, seulement que le langage fournissait les moyens de créer et de manipuler des listes à deux éléments. Le comportement dont nous avons besoin pour implémenter une paire, c'est qu'il assemble deux valeurs. Si l'on énonce la propriété de comportement comme suit :

• Si une paire p a été construite à partir des valeurs x et y, alors select(p, 0) renvoie x et select(p, 1) retourne y.

Alors nous n'avons pas besoin du type de liste pour créer des paires. Au lieu de cela, nous pouvons mettre en place deux fonctions pair et select qui répondent à cette description tout comme une liste à deux éléments :

>>> def pair(x, y):
        """Renvoie une fonction qui représente une paire."""
        def get(index):
            if index == 0:
                return x
            elif index == 1:
                return y
        return get

>>> def select(p, i):
        """Renvoie l'élément d'indice i de la paire p."""
        return p(i)

Avec cette mise en œuvre, nous pouvons créer et manipuler des paires :

>>> p = pair(20, 14)
>>> select(p, 0)
20
>>> select(p, 1)
14

Cette utilisation de fonctions d'ordre supérieur ne correspond nullement à notre notion intuitive de ce que devraient être les données. Néanmoins, ces fonctions suffisent à représenter des paires dans nos programmes. Les fonctions sont suffisantes pour représenter les données composées.

La raison pour laquelle nous montrons cette représentation fonctionnelle d'une paire n'est pas que Python fonctionne réellement de cette façon (il est préférable d'utiliser directement des listes, pour des raisons d'efficacité), mais que cela peut fonctionner de cette façon. La représentation fonctionnelle, bien qu'un peu obscure, est un moyen parfaitement adapté pour représenter les paires, car elle remplit les seules conditions que les paires doivent satisfaire. La pratique de l'abstraction des données nous permet de changer facilement les représentations sous-jacentes.