Synthese und Herausforderungen: Funktionen

Zusammenfassung

Diese Lektion schließt die fünfte Einheit des Kurses ab, die den Funktionen gewidmet ist. Sie rekonstruiert die Kette der Begriffe, die von der Deklaration einer Funktion bis zur Rekursion reicht, über den Aufrufstapel, den Vertrag, die Übergabe der Parameter, den Gültigkeitsbereich und die Speicherdauer der Variablen und den Entwurf durch schrittweise Verfeinerung; sie trennt, was davon in jeder Sprache gilt, von dem, was C++ eigen ist; sie stellt das undefinierte Verhalten der Einheit zusammen, mit dem, wovor der Compiler warnt, was der Sanitizer anhält und was niemand meldet; sie wiederholt in ihrem Abschlusstest die Fertigkeiten des Eingangstests; und sie endet mit sechs Herausforderungen, die die ganze Einheit verbinden.

Lernziele

Ein Problem in Funktionen zerlegen, jede mit ihrer Schnittstelle und ihrem Vertrag (Vorbedingung und Nachbedingung), und sie einzeln testen.
Die Übergabeart jedes Parameters und die Art, die Ergebnisse zurückzugeben, wählen und die Wahl begründen.
Ein Problem rekursiv lösen, seine Korrektheit durch Induktion und seine Terminierung mit einem abnehmenden Maß beweisen und seine Kosten in Aufrufen abschätzen.
Das undefinierte Verhalten der Einheit erkennen (den Pfad ohne return, die hängende Referenz, das überlaufende Ergebnis, den erschöpften Stapel) und das Programm ohne es neu schreiben.
In dem, was in der Einheit gelernt wurde, das, was in jeder Sprache gilt, von dem trennen, was C++ eigen ist.

Was die Einheit erreicht hat

Die Einheit hatte sich vorgenommen zu lehren, wie man ein Problem in benannte Teile zerlegt, jeden mit einer Schnittstelle und einem Vertrag, und wie man Probleme rekursiv löst. Dieses Ziel wurde erreicht, gestützt allein auf das, was die Einführung als bekannt vorausgesetzt hat: die Schleifen der Einheit 4 mit ihrer Invariante und ihrer Variante, die Spezifikation der Lektion 1.1 und das Speichermodell der Einheit 2. Das Programm der befreundeten Zahlen, dessen kopierte Schleife die Teiler der falschen Zahl aufsummierte, wird jetzt mit einer einzigen Funktion geschrieben, die einmal gegen ihren Vertrag geprüft wird.

Funktionen

Die Lektion Funktionen hat gelehrt, eine Funktion zu deklarieren, zu definieren und aufzurufen, und drei Zeitpunkte unterschieden: Beim Kompilieren wird jeder Aufruf gegen eine zuvor gesehene Deklaration geprüft; beim Linken wird die Definition gesucht; bei der Ausführung werden die Argumente berechnet, ein Rahmen auf dem Aufrufstapel angelegt, und die Kontrolle springt in den Rumpf. Sie hat gezeigt, dass es undefiniertes Verhalten ist, das Ende einer Funktion, die nicht void ist, ohne ein return zu erreichen, und sie hat mit dem Vertrag geschlossen, der Vorbedingung und der Nachbedingung, der die Verantwortung zwischen dem Aufrufer und der Funktion aufteilt.

Parameter und Gültigkeitsbereich

Die Lektion Parameter und Gültigkeitsbereich hat untersucht, auf welchen Wegen die Daten hinein- und die Ergebnisse hinausgelangen: Der Wertparameter ist eine Kopie; der Referenzparameter ein zweiter Name für die Zelle des Aufrufers; die konstante Referenz liest, ohne zu kopieren. Daraus folgt die Regel der Wahl (Wert für Kleines, konstante Referenz für Großes, das nur gelesen wird, Referenz nur, wenn das Ändern der Zweck ist) und, für mehrere Ergebnisse, std::pair und std::tuple mit strukturierten Bindungen. Sie hat den Gültigkeitsbereich eines Namens, eine Eigenschaft des Textes, von der Speicherdauer einer Variablen, einer Eigenschaft der Ausführung, unterschieden und mit der Referenz geendet, die ihre Zelle überlebt.

Mit Funktionen entwerfen

Die Lektion Mit Funktionen entwerfen hat gelehrt, durch schrittweise Verfeinerung zu entscheiden, welche Funktionen man schreibt: ein kurzes main, das nur deklarierte Funktionen aufruft, und der Abstieg zu jeder von ihnen, sodass sich die Zerlegung als Baum zeichnen lässt. Sie hat die Kriterien einer guten Schnittstelle festgelegt und die Regel „eine Funktion, eine Aufgabe“ mit ihren Warnzeichen (die Konjunktion im Namen, die Funktion, die nicht auf einen Bildschirm passt, das Flag) und die verborgenen Wirkungen wie die globale Variable; sie hat die Überladung vorgestellt, mit ihrer Rangfolge und dem mehrdeutigen Aufruf; und sie hat die Algorithmen der Einheit 4 als einzeln getestete Funktionen neu geschrieben.

Rekursion

Die Lektion Rekursion hat gelehrt, dass eine Funktion sich selbst aufrufen kann, um eine kleinere Instanz des Problems zu lösen. Sie hat die Korrektheit durch Induktion bewiesen, unter der Annahme, dass der kleinere Aufruf korrekt ist, und die Terminierung mit einem abnehmenden natürlichen Maß; sie hat am Stapel die Rahmen verfolgt, die sich aufschichten und wieder abbauen, und gezeigt, wie er sich erschöpft; sie hat davor gewarnt, dass der Typ des Ergebnisses lange vor dem Stapel überläuft; und sie hat das rekursive und das iterative Fibonacci verglichen: $2\,692\,537$ Aufrufe gegenüber 29 Additionen für $F_{30}$ .