Langages et programmation : récursivité, modules et mise au point

Quand tu ouvres un fichier Python dans un éditeur, celui-ci traite des caractères. Quand un interprète exécute ce fichier, il donne un sens à ses constructions. Le même programme est donc une donnée pour un autre programme. Un compilateur traduit une représentation vers une autre ; un interprète applique les règles du langage pendant l’exécution. Cette distinction n’impose pas une frontière absolue : une implantation peut combiner traduction intermédiaire et interprétation.

Pour voir ce mécanisme, utilisons des tuples au lieu d’analyser du texte. L’instruction ('SET', 'x', 3) associe 3 au nom x. ('ADD', 'x', 2) remplace sa valeur par la valeur précédente plus 2. ('PRINT', 'x') ajoute cette valeur à une liste de sorties simulées. SET peut réaffecter un nom ; ADD et PRINT exigent qu’il ait déjà été défini. La liste de tuples décrit le programme, elle n’exécute rien à elle seule.

La syntaxe fixe les formes autorisées ; la sémantique fixe leur effet. Ici, seuls les noms x, y et z, les trois opérations annoncées et des constantes entières de −100 à 100 sont admis. Un booléen n’est pas une constante numérique de ce langage. Le programme contient au plus 100 instructions. Ce choix pédagogique rend les traces courtes et le domaine précis ; il ne décrit pas la grammaire de Python.

Le validateur parcourt tout le programme avant l’interprétation. Il contrôle les formes et les noms définis au fil des instructions. Cette vérification préalable est possible ici parce que l’exécution est linéaire, sans branche ni boucle. Le moteur part ensuite d’un dictionnaire vide. Pour chaque instruction, il conserve un instantané avant et après, avec une copie du dictionnaire et une sortie sous forme de tuple.

Une copie superficielle suffit dans ce modèle car les valeurs sont des entiers immuables. Accepter une liste comme constante permettrait au programme appelant de changer après coup une ancienne trace : c’est pourquoi elle est refusée. Aucun texte n’est évalué comme du code, aucun fichier ni réseau n’est utilisé. Lis d’abord les trois branches du moteur, puis le validateur : les contrôles protègent le contrat sans remplacer l’explication du calcul.

Un problème de décision demande une réponse oui ou non pour chaque instance : « cet entier est-il premier ? » ou « ce programme termine-t-il sur cette entrée ? ». Il est décidable s’il existe un algorithme qui répond correctement et termine sur toute instance du domaine. Être décidable ne signifie pas être rapide. La complexité étudie les ressources nécessaires ; la décidabilité demande d’abord si un tel algorithme existe.

Dans le modèle idéal du calcul, sans limite fixée de mémoire ou de temps, les langages généralistes usuels peuvent exprimer les mêmes fonctions calculables. Changer de langage ne résout donc pas le problème général de l’arrêt. Cette équivalence ne concerne pas tous les langages restreints : notre langage SET/ADD/PRINT est sans boucle, et tous ses programmes valides terminent. Les bornes d’un ordinateur réel ne sont pas la définition mathématique de la calculabilité.

Pour comprendre l’impossibilité générale, supposons un programme H toujours correct, qui termine et répond si le programme de texte p s’arrête sur l’entrée x. Construisons alors conceptuellement D(p) : si H(p, p) prédit l’arrêt, D boucle sans fin ; sinon D s’arrête. Le texte de D est une donnée, notée d. Examinons D(d). Si H(d, d) répond oui, D(d) boucle : réponse fausse. S’il répond non, D(d) s’arrête : réponse fausse encore. Les deux cas contredisent l’hypothèse de H.

Cette preuve n’affirme pas que toute question particulière d’arrêt est insoluble. Un variant peut prouver la terminaison d’une fonction précise ; une répétition du même état complet dans un système déterministe prouve un cycle. Répéter seulement un compteur partiel ou une ligne du programme ne suffit pas : le reste de l’état peut avoir changé. Le laboratoire décrit une machine où le nom de l’état est volontairement toute l’information déterminant la transition suivante.

Chaque état non terminal de cette machine finie possède exactement un successeur connu ; HALT est terminal. L’observateur avance dans la limite d’un budget de transitions. Il distingue arrêt atteint, cycle prouvé et inconnu à la limite. Les états obtenus exactement au dernier pas sont examinés avant la conclusion de budget. Avec N états non terminaux, N transitions suffisent ici pour atteindre HALT ou répéter un état ; cette propriété de ce modèle fermé ne fournit aucun décideur pour tous les programmes.

Une fonction récursive s’appelle elle-même, directement ou par l’intermédiaire d’autres fonctions. Pour en écrire une, cherche un cas que tu sais résoudre immédiatement, puis une réduction vers ce cas. La factorielle fournit un exemple simple : 0! vaut 1 ; pour n positif, n! vaut n × (n − 1)!. Le cas de base donne une valeur sans nouvel appel ; le cas récursif utilise le résultat d’un problème plus petit.

Pour calculer 3!, le premier cadre possède son n égal à 3 et attend le résultat de factorielle(2). Le suivant garde n égal à 2 et attend factorielle(1). L’appel avec 0 rend 1. Les cadres reprennent alors dans l’ordre inverse : 1 × 1, puis 2 × 1, puis 3 × 2. Le paramètre n d’un cadre n’est pas remplacé par celui du suivant. Les variables locales et le point de reprise appartiennent à chaque appel.

Un variant permet de justifier que les appels se rapprochent du cas de base. Ici, n est un entier naturel et diminue de 1 à chaque appel récursif : il ne peut pas diminuer ainsi indéfiniment sans atteindre 0. Cela justifie la terminaison mathématique sur le domaine annoncé, pas à lui seul la valeur du résultat. Il faut encore vérifier la base 0! = 1 et la relation qui recompose les sous-résultats.

Le laboratoire borne n entre 0 et 100 pour conserver une trace manipulable. Ce n’est pas une borne de la définition de la factorielle. Chaque appel ajoute une entrée, puis un retour ; pour n = 3, la fonction récursive calculer a quatre cadres au maximum et huit événements, sans compter l’enveloppe qui prépare la trace. À coût unitaire par opération arithmétique, le calcul comporte n multiplications et n + 1 appels ; les grands entiers rendent le coût réel des multiplications variable.

Une profondeur excessive peut provoquer RecursionError en Python même si la fonction mathématique termine. Inversement, remplacer n − 1 par n + 1 éloigne du cas de base : le calcul récursif abstrait ne le rejoint pas, et Python finit par signaler une erreur de profondeur. Une telle erreur n’est donc pas l’observation d’une exécution infinie. Dans le transfert sur listes imbriquées, on vérifie aussi l’absence de cycle et une profondeur bornée avant de commencer la somme.

Un module regroupe une responsabilité derrière une interface. En Python, un fichier mesures.py peut définir des classes et fonctions réutilisables ; un autre fichier les importe au lieu de les recopier. Une API, ou interface de programmation, décrit les opérations offertes au client. Elle peut être locale, comme celle d’une bibliothèque : une API n’est pas nécessairement un service Web et ne demande pas toujours une clé ou un compte.

Lis un contrat dans cet ordre : nom de l’opération, paramètres, valeur renvoyée et unité, erreurs, effets éventuels. Notre client appelle temperature_celsius() sans argument et attend un flottant entre −50 et 60. Les données sont fictives. La version V1 du fournisseur renvoie un entier en dixièmes de degré ; V2 renvoie un dictionnaire en millièmes accompagné d’un statut. Les deux formats ne doivent pas remonter jusqu’au code d’affichage.

L’adaptateur concentre les différences. Il appelle lire() en V1, mesure() en V2, vérifie la réponse puis divise par 10 ou 1 000. Un statut autre que « ok », une clé manquante, un booléen ou une valeur hors domaine produit ValueError. Il ne remplace pas une mesure invalide par zéro. Une exception levée par le fournisseur lui-même n’est pas silencieusement absorbée ; dans cet exercice, les fournisseurs sont des objets locaux aux méthodes déterministes.

Pour 215 dixièmes et 21 500 millièmes, le client obtient le même flottant 21,5. Mais V2 peut aussi porter 21 537 millièmes, une précision que V1 ne représente pas exactement. La compatibilité se vérifie sur les observations communes, pas en prétendant que tous les formats ont la même précision. L’affichage à une décimale arrondit le texte présenté ; il ne doit pas remplacer la valeur utilisée par les calculs. Un flottant reste une représentation approchée.

Copie les définitions du laboratoire, sans les tests, dans mesures.py. Dans le même dossier, crée client.py avec le code de l’exemple résolu, puis lance python3 client.py. Les docstrings sont accessibles par help(mesures.AdaptateurMesure) après import mesures. Importer un module exécute ses instructions de niveau supérieur : garde les démonstrations sous la garde __name__ == '__main__' si tu en ajoutes. Le préfixe _ signale un détail interne par convention, il ne rend pas un attribut inaccessible.

Un paradigme est une manière d’organiser un programme. Le style impératif décrit des changements d’état successifs, avec affectations, conditions et boucles. Le style fonctionnel privilégie la composition de fonctions et la construction de nouvelles valeurs. Le style objet réunit un état et des méthodes au sein d’objets. Python permet de combiner ces styles ; leur nom ne garantit ni la correction, ni l’absence d’effets, ni une meilleure performance.

Comparons un même calcul : additionner les carrés des valeurs paires de [1, 2, 3, 4]. Le filtre retient 2 et 4, le carré produit 4 et 16, l’addition donne 20. L’impératif fait évoluer un accumulateur local de 0 à 4 puis à 20. La version fonctionnelle compose filter, map et sum : est_pair et carre sont des fonctions transmises comme données, non des appels écrits avec leurs parenthèses.

Une fonction pure dépend de ses arguments et ne provoque pas d’effet observable extérieur. Modifier un accumulateur local n’est donc pas modifier la liste reçue. À l’inverse, une fonction écrite avec une seule expression peut appeler une fonction qui affiche ou mute un objet : sa forme ne la rend pas pure. Un effet peut être nécessaire, par exemple pour afficher un résultat ; il doit être assumé et séparé du calcul lorsqu’on veut le tester.

La version objet conserve une copie sous forme de tuple d’entiers, puis sa méthode calculer() lit cet état. Modifier la liste d’origine ne modifie donc pas l’objet construit. Cette indépendance dépend ici de l’immuabilité des éléments : transformer en tuple une liste de listes ne suffirait pas à copier les listes internes. Le préfixe _valeurs signale un attribut interne, sans constituer une protection d’accès du langage.

Les trois versions partagent le domaine, le résultat et les tests : liste ou tuple d’au plus 1 000 entiers de −100 à 100, booléens refusés, source inchangée. Elles parcourent les valeurs ; les formes fonctionnelles ne suppriment pas le travail de filtrage ou de calcul. Choisis selon le besoin : boucle claire pour une progression d’état, composition pour une chaîne de transformations, objet pour associer un état stable à plusieurs opérations. Compare aussi les cas vide, négatif, répété et les appels successifs.

Commence par le contrat, pas par une modification du code. Un test relie une entrée, une attente et une observation. L’attente, appelée oracle, vient de la spécification ou d’un calcul indépendant. Pour l’intervalle fermé [0 ; 10], les bornes 0 et 10 appartiennent à l’intervalle ; −1 et 11 n’y appartiennent pas. Le test du seul milieu 5 ne distingue pas plusieurs conditions fautives d’une condition correcte.

Choisis des familles d’entrées, puis leurs frontières : valeur en dessous, égale, à l’intérieur, au-dessus, intervalle réduit à un point, bornes inversées et mauvais types. True est un booléen même si isinstance(True, int) vaut vrai en Python ; un contrat d’entiers stricts peut le refuser. Tester toutes les valeurs d’un petit domaine prouve le résultat sur ce domaine seulement. Une série de succès ne démontre pas à elle seule la correction pour toutes les entrées possibles.

Un symptôme indique où chercher, pas encore la cause. Pour x ≥ a ou x ≤ b, prends x = −1, a = 0 et b = 10. La première condition est fausse mais la seconde est vraie : « ou » accepte la valeur extérieure. L’appartenance exige que les deux conditions soient vraies. La bonne correction est « et » ou l’inégalité chaînée a ≤ x ≤ b ; le contre-exemple devient un test permanent.

Deux autres erreurs se lisent avec un cas minimal. Le dernier indice d’une liste non vide est len(t) − 1 : t[len(t)] déborde. Une fonction qui renvoie « positif » pour n > 0 et « négatif » pour n < 0, sans autre branche, renvoie None pour zéro. Nommer une variable secondes alors qu’elle contient des minutes peut cacher une conversion erronée. Relie chaque défaut à une entrée discriminante, au résultat attendu et à la première étape qui diverge.

Les flottants représentent de nombreux décimaux de façon approchée : 0.1 + 0.2 n’est généralement pas exactement 0.3 en Python. Une comparaison par proximité demande une règle liée au besoin. math.isclose exige |a − b| ≤ max(abs_tol, rel_tol × max(|a|, |b|)) : la tolérance relative est proportionnelle à la plus grande valeur absolue ; près de zéro, une tolérance absolue positive peut être nécessaire. Notre fonction limite les valeurs à ±10¹², les tolérances à des nombres finis et refuse booléens, NaN et infinis.

Une tolérance ne corrige pas une erreur d’unité ou un algorithme faux. La proximité n’est pas forcément transitive : avec une tolérance absolue de 1, 0 est proche de 0,75, qui est proche de 1,5, mais 0 n’est pas proche de 1,5. Documente donc son usage au lieu de remplacer toutes les égalités. Les assertions conviennent aux tests ; les contrôles du contrat utilisent ici des exceptions explicites, car Python peut supprimer les assert en mode optimisé.