Synthèse et défis : fonctions

Résumé

Cette leçon clôt la cinquième unité du cours, consacrée aux fonctions. Elle reconstruit la chaîne des concepts qui va de la déclaration d’une fonction à la récursivité, en passant par la pile d’appels, le contrat, le passage des paramètres, la portée et la durée de stockage des variables et la conception par raffinement successif ; elle sépare ce qui, dans tout cela, vaut dans tout langage de ce qui est propre à C++ ; elle rassemble le comportement indéfini de l’unité, avec ce que signale le compilateur, ce qu’arrête le détecteur et ce que personne ne signale ; elle reprend dans son évaluation de sortie les compétences de l’évaluation d’entrée ; et elle se termine par six défis qui combinent l’unité entière.

Objectifs d’apprentissage

Décomposer un problème en fonctions, chacune avec son interface et son contrat (précondition et postcondition), et les tester séparément.
Choisir le mode de passage de chaque paramètre et la manière de renvoyer les résultats, et justifier ce choix.
Résoudre un problème par récursivité et démontrer sa correction par récurrence et sa terminaison par une mesure qui décroît, en estimant son coût en appels.
Reconnaître le comportement indéfini de l’unité (le chemin sans return, la référence pendante, le résultat qui déborde, la pile épuisée) et réécrire le programme sans lui.
Séparer, dans ce que l’unité a appris, ce qui vaut dans tout langage de ce qui est propre à C++.

L’acquis de l’unité

L’unité s’est proposé d’enseigner à décomposer un problème en parties nommées, chacune avec une interface et un contrat, et à résoudre des problèmes par récursivité. Ce but a été atteint en s’appuyant seulement sur ce que l’introduction a déclaré tenir pour acquis : les boucles de l’unité 4, avec leur invariant et leur variant, la spécification de la leçon 1.1 et le modèle de la mémoire de l’unité 2. Le programme des nombres amiables, dont la boucle copiée additionnait les diviseurs du mauvais nombre, s’écrit maintenant avec une seule fonction, vérifiée une fois pour toutes par rapport à son contrat.

Fonctions

La leçon Fonctions a enseigné à déclarer, définir et appeler une fonction, et a séparé trois moments : à la compilation, chaque appel est vérifié par rapport à une déclaration vue auparavant ; à l’édition de liens, on cherche la définition ; à l’exécution, on calcule les arguments, on crée un cadre sur la pile d’appels et le contrôle saute vers le corps. Elle a montré qu’atteindre la fin d’une fonction qui n’est pas void sans return est un comportement indéfini, et elle s’est achevée sur le contrat, la précondition et la postcondition, qui répartit les responsabilités entre l’appelant et la fonction.

Paramètres et portée

La leçon Paramètres et portée a étudié par quels chemins entrent les données et sortent les résultats : le paramètre par valeur est une copie ; le paramètre par référence, un second nom pour la case de l’appelant ; la référence constante lit sans copier. Il s’ensuit la règle de choix (la valeur pour ce qui est petit, la référence constante pour ce qui est volumineux et seulement lu, la référence seulement si modifier est le but) et, pour plusieurs résultats, std::pair et std::tuple avec des liaisons structurées. Elle a distingué la portée d’un nom, propriété du texte, de la durée de stockage d’une variable, propriété de l’exécution, et elle s’est terminée sur la référence qui survit à sa case.

Concevoir avec des fonctions

La leçon Concevoir avec des fonctions a enseigné à décider quelles fonctions écrire, par raffinement successif : un main bref qui appelle des fonctions seulement déclarées, puis la descente vers chacune d’elles, de sorte que la décomposition se dessine comme un arbre. Elle a fixé les critères d’une bonne interface et la règle « une fonction, une tâche », avec ses signes (la conjonction dans le nom, la fonction qui ne tient pas sur un écran, le drapeau) et les effets cachés, comme la variable globale ; elle a présenté la surcharge, avec son ordre de préférence et l’appel ambigu ; et elle a réécrit les algorithmes de l’unité 4 sous forme de fonctions testées séparément.

Récursivité

La leçon Récursivité a enseigné qu’une fonction peut s’appeler elle-même pour résoudre une instance plus petite du problème. Elle a démontré la correction par récurrence, en supposant correct l’appel plus petit, et la terminaison par une mesure entière naturelle qui décroît ; elle a suivi sur la pile les cadres qui s’empilent et se défont, et a montré comment la pile s’épuise ; elle a averti que le type du résultat déborde bien avant la pile ; et elle a comparé Fibonacci récursif et itératif : $2\,692\,537$ appels contre 29 additions pour $F_{30}$ .