Kapitel 8: Schrittweise Verfeinerung

Programmierung ist in hohem Maße die Wissenschaft, Probleme mit dem Computer zu lösen. Da Probleme oft schwierig sind, können auch Lösungen - und die Programme, die diese Lösungen implementieren - schwierig sein. Um Ihnen die Entwicklung dieser Lösungen zu erleichtern, müssen Sie eine Methodik und Disziplin anwenden, die den Umfang dieser Komplexität auf ein handhabbares Maß reduziert.

In den Anfangsjahren der Programmierung war das Konzept des Rechnens als Wissenschaft mehr oder weniger ein Experiment im Wunschdenken. In jenen Tagen wusste niemand viel über das Programmieren und nur wenige dachten, es sei eine technische Disziplin im herkömmlichen Sinne. Mit zunehmender Programmreife entwickelte sich jedoch eine solche Disziplin. Der Eckpfeiler dieser Disziplin ist das Verständnis, dass das Programmieren in einem sozialen Umfeld stattfindet, in dem Programmierer zusammenarbeiten müssen. Wenn Sie in die Industrie einsteigen, werden Sie mit ziemlicher Sicherheit einer von vielen Programmierern sein, die an der Entwicklung eines großen Programms arbeiten. Darüber hinaus wird dieses Programm mit ziemlicher Sicherheit weiterleben und eine Wartung erfordern, die über die ursprünglich beabsichtigte Anwendung hinausgeht. Jemand möchte, dass das Programm eine neue Funktion enthält oder auf andere Weise funktioniert. In diesem Fall muss ein neues Team von Programmierern die erforderlichen Änderungen an den Programmen vornehmen. Wenn Programme in einem individuellen Stil geschrieben sind und keine oder nur geringe Gemeinsamkeiten aufweisen, ist es äußerst schwierig, alle Menschen dazu zu bringen, produktiv zusammenzuarbeiten.

Um dieses Problem zu bekämpfen, begannen die Programmierer, eine Reihe von Programmiermethoden zu entwickeln, die gemeinsam aufgerufen werden Softwareentwicklung . Wenn Sie über gute Kenntnisse in der Softwareentwicklung verfügen, können andere Programmierer Ihre Programme nicht nur leichter lesen und verstehen, sondern Sie können diese Programme auch einfacher schreiben. Einer der wichtigsten methodischen Fortschritte beim Software Engineering ist die Strategie von Top-Down-Design oder Schrittweise Verfeinerung , das darin besteht, Probleme zu lösen, indem man mit dem gesamten Problem beginnt. Sie zerlegen das gesamte Problem in Teile und lösen dann jedes Teil, wobei Sie diese gegebenenfalls weiter zerlegen. Diese Top-Down-Strategie wird ergänzt durch iteratives Testen Hier stellen Sie sicher, dass die kleineren Teile der Lösung funktionieren, bevor Sie fortfahren.

Eine Übung zur schrittweisen Verfeinerung

Um das Konzept der schrittweisen Verfeinerung zu veranschaulichen, bringen wir Karel bei, ein neues Problem zu lösen. Stellen Sie sich vor, Karel lebt jetzt in einer Welt, die ungefähr so aussieht:

Auf jeder der Säulen befindet sich ein Turm mit beeper s unbekannter Höhe, obwohl einige Säulen (wie die 7. und 9. in der Beispielwelt) leer sein können. Karels Aufgabe ist es, alle beeper in jedem dieser Türme zu sammeln, sie wieder in der östlichsten Ecke der ersten Reihe beeper und dann in ihre Ausgangsposition zurückzukehren. Wenn Karel seine Arbeit im obigen Beispiel beendet hat, sollten daher alle 25 beeper in den Türmen wie folgt in der Ecke der 9. Spalte und der 1. Reihe gestapelt werden:

Wichtig ist, dass Sie diese Karel-Initiale annehmen könnenbeginntmit null beeper s in seiner Tasche. Jeder abgeholte beeper wird seiner Tasche hinzugefügt. Wenn er beeper s in die Ecke stellt, kann karel das benutzen beepersInBag() Prüfung.

Der Schlüssel zur Lösung dieses Problems besteht darin, das Programm auf die richtige Weise zu zerlegen und es dabei zu testen. Diese Aufgabe ist komplexer als die anderen, die Sie gesehen haben, weshalb die Auswahl geeigneter Teilprobleme für eine erfolgreiche Lösung wichtiger ist.

Das Prinzip des Top-Down-Designs

Die Schlüsselidee bei der schrittweisen Verfeinerung besteht darin, dass Sie den Entwurf Ihres Programms von oben beginnen, was sich auf die Ebene des Programms bezieht, die konzeptionell am höchsten und abstraktesten ist. Auf dieser Ebene ist das beeper klar in drei unabhängige Phasen unterteilt. Zuerst muss Karel alle beeper s sammeln. Zweitens muss Karel sie an der letzten Kreuzung hinterlegen. Drittens muss Karel in seine Ausgangsposition zurückkehren. Diese konzeptionelle Zerlegung des Problems legt nahe, dass die run Methode für dieses Programm die folgende Struktur aufweist:

   public void run() {
      sammleAlleConoS();
      conoAlleConoS();
      nachHauseZurückkehren();
   }

Auf dieser Ebene ist das Problem leicht zu verstehen. Natürlich gibt es noch einige Details in Form von Methoden, die Sie noch nicht geschrieben haben. Trotzdem ist es wichtig, jede Ebene der Zerlegung zu betrachten und sich davon zu überzeugen, dass Sie, solange Sie glauben, dass die zu schreibenden Methoden die Teilprobleme korrekt lösen, eine Lösung für das gesamte Problem haben .

Iteratives Testen unterwegs

move Sie die Struktur für das gesamte Programm definiert haben, ist es Zeit, move mit dem ersten Teilproblem move , das darin besteht, alle beeper s zu beeper . Diese Aufgabe ist an sich komplizierter als die einfachen Probleme aus den vorhergehenden Kapiteln. beeper Sie alle beeper s beeper , müssen Sie die beeper s in jedem Turm beeper bis Sie die letzte Ecke erreichen. Die Tatsache, dass Sie eine Operation für jeden Turm wiederholen müssen, legt nahe, dass Sie hier eine while-Schleife benötigen. Die while-Schleife wiederholt den Vorgang von sammleEinenTurm und dann umziehen.

Vorsicht: Es ist gefährlich zu versuchen, das gesamte Programm ohne zu schreiben testen es wie du gehst. Wenn Sie einen Fehler machen, wird es schwierig sein, den Fehler zu finden. Wir wissen, dass wir den Prozess des Einsammelns eines Turms wiederholen werden. Lass uns schreiben und Prüfung Sammeln eines einzelnen Turms, bevor wir den setzen SammleEinenTurm in einer for-Schleife verarbeiten. SomitvorübergehendWir können mit der folgenden Definition von sammleAlleConoS beginnen:

   private void sammleAlleConoS() {
      /* temporäre Implementierung zu Testzwecken */
      sammleEinenTurm();
      move();
   }

Wenn Sie eine komplexe Schleife haben, testen Sie dieKarosserieder Schleife, bevor Sie die gesamte Schleife schreiben.

Raffinierter Sammelturm

Wenn sammleEinenTurm aufgerufen wird, steht Karel entweder an der Basis eines beeper s beeper Turms oder an einer leeren Ecke. Im ersten Fall müssen Sie die beeper s im Turm sammeln. In letzterem kannst du einfach move an. Diese Situation klingt wie eine Anwendung für die if-Anweisung, in der Sie Folgendes schreiben würden:

   if(beepersPresent()){
      sammleDenEigentlichenTurm();
   }

Bevor Sie dem Code eine solche Anweisung hinzufügen, sollten Sie überlegen, ob Sie diesen Test durchführen müssen. Oft können Programme einfacher gestaltet werden, indem man beobachtet, dass auf den ersten Blick besondere Fälle genauso behandelt werden können wie die allgemeinere Situation. Was passiert im aktuellen Problem, wenn Sie beeper , dass sich auf jeder Allee ein Turm mit beeper einige dieser Türme nicht mehr als beeper Hoch sind? Die Nutzung dieser Erkenntnisse vereinfacht das Programm, da Sie nicht mehr prüfen müssen, ob sich auf einer bestimmten Straße ein Turm befindet.

Die sammleEinenTurm-Methode ist immer noch so komplex, dass ein zusätzlicher Zerlegungsgrad erforderlich ist. Um alle beeper in einem Turm zu sammeln, muss Karel die folgenden Schritte beeper :

Biegen Sie links ab, um die beeper im Turm zu sehen.
beeper alle beeper im Turm und beeper an, wenn keine beeper mehr gefunden werden.
Drehe dich um und wende dich dem Boden der Welt zu.
Kehre zur Wand zurück, die den Boden darstellt.
Biegen Sie links ab, um bereit zu sein, move bis zur nächsten Ecke.

Diese Gliederung stellt erneut ein Modell für die sammleEinenTurm-Methode bereit, das wie folgt aussieht:

   private void sammleEinenTurm(){
      turnLeft();
      conoVonConoS();
      turnAround();
      moveAnDieWand();
      turnLeft();
   }

Methodenvor- und -nachbedingungen

Die biegenSieLinksAb-Befehle am Anfang und am Ende der sammleEinenTurm-Methode sind für die Richtigkeit dieses Programms von entscheidender Bedeutung. Wenn sammleEinenTurm aufgerufen wird, befindet sich Karel immer irgendwo in der 1. Reihe in Richtung Osten. Nach Abschluss des Vorgangs funktioniert das gesamte Programm nur dann ordnungsgemäß, wenn Karel an derselben Ecke wieder nach Osten zeigt. Bedingungen, die erfüllt sein müssen, bevor eine Methode aufgerufen wird, werden als bezeichnet Voraussetzungen ; Bedingungen, die nach Beendigung der Methode gelten müssen, werden als bezeichnet Nachbedingungen .

Wenn Sie eine Methode definieren, werden Sie weitaus weniger Probleme haben, wenn Sie genau aufschreiben, welche Vor- und Nachbedingungen vorliegen. Sobald Sie dies getan haben, müssen Sie sicherstellen, dass der von Ihnen geschriebene Code immer die Nachbedingungen erfüllt, vorausgesetzt, dass die Vorbedingungen von Anfang an erfüllt waren. Denken Sie beispielsweise darüber nach, was passiert, wenn Sie sammleEinenTurm anrufen, während Karel sich in der ersten Reihe in Richtung Osten befindet. Mit dem ersten Befehl biegenSieLinksAb wird Karel nach Norden ausgerichtet, was bedeutet, dass Karel ordnungsgemäß an der Säule von beeper s ausgerichtet ist, die den Turm darstellt. Die conoVonConoS-Methode - die noch geschrieben werden muss, aber dennoch eine konzeptuell verständliche Aufgabe erfüllt - ist einfach move s, ohne sich umzudrehen. So wird Karel am Ende des Aufrufs zu conoVonConoS weiterhin nach Norden ausgerichtet sein. Der drehDichUm-Aufruf lässt Karel also nach Süden. Wie bei conoVonConoS sind bei der move Methode move keine Umdrehungen erforderlich, sondern lediglich move s, bis sie auf die Begrenzungswand trifft. Da Karel nach Süden ausgerichtet ist, befindet sich diese Begrenzungsmauer am unteren Bildschirmrand direkt unter der ersten Reihe. Der abschließende Befehl biegenSieLinksAb verlässt Karel daher in der ersten Reihe nach Osten, was die Nachbedingung erfüllt.

Vorgang wiederholen

Sie run Ihr Programm und es löscht erfolgreich einen Turm und verlässt Karel in der versprochenen Nachbedingung. Wahoo! Sie haben gerade einen Meilenstein bei der Lösung dieser schwierigen Aufgabe erreicht! Wir müssen nun den Vorgang des Löschens eines Turms mit einer while-Schleife wiederholen.

Aber wie sieht diese while-Schleife aus? Zunächst sollten Sie über den Bedingungstest nachdenken. Sie möchten, dass Karel anhält, wenn er am Ende der Reihe an die Wand stößt. Sie möchten also, dass Karel weitermacht, solange der Raum vor Ihnen frei ist. Sie wissen also, dass die sammleAlleConoS-Methode eine while-Schleife enthält, die den vorneIstKlar-Test verwendet. An jeder Position soll Karel alle beeper im Turm sammeln, die an dieser Ecke beginnen. Wenn Sie dieser Operation einen Namen geben, der so etwas wie sammleEinenTurm sein könnte, können Sie eine Definition für die sammleAlleConoS-Methode schreiben, obwohl Sie die Details noch nicht ausgefüllt haben.

Sie müssen jedoch vorsichtig sein. Der Code für sammleAlleConoS sieht nicht so aus:

   private void sammleAlleConoS(){
      /* Buggy-Schleife! */
      while(frontIsClear()) {
         sammleEinenTurm();
         move();
      }
   }

Diese Implementierung ist aus genau dem Grund fehlerhaft, aus dem die erste Version der allgemeinen PlaceConoLinie aus Kapitel 6 ihre Aufgabe nicht erfüllt hat. In dieser Version des Codes ist ein Zaunpfostenfehler beeper , da Karel auf der letzten Allee prüfen muss, beeper ein beeper Turm vorhanden ist. Die korrekte Implementierung ist:

   private void sammleAlleConoS(){
      while(frontIsClear()) {
         sammleEinenTurm();
         move();
      }
      sammleEinenTurm();
   }

Beachten Sie, dass diese Methode genauso aufgebaut ist wie das Hauptprogramm aus dem in Kapitel 6 vorgestellten PlaceConoLinie-Programm. Der einzige Unterschied besteht darin, dass dieses Programm sammleEinenTurm aufruft, während das andere piepserSetzen heißt. Diese beiden Programme sind Beispiele für eine allgemeine Strategie, die folgendermaßen aussieht:

   private void sammleAlleConoS(){
      while(frontIsClear()) {
          Führen Sie eine Operation aus.
         move();
      }
       Führen Sie den gleichen Vorgang für die letzte Kurve durch.
   }

Sie können diese Strategie immer dann move , wenn Sie eine Operation an jeder Ecke ausführen müssen, während Sie sich move auf einem Pfad befinden, der an einer Wand endet. Wenn Sie sich an die allgemeine Struktur dieser Strategie erinnern, können Sie sie verwenden, wenn Sie auf ein Problem stoßen, für das eine solche Operation erforderlich ist. Solche wiederverwendbaren Strategien tauchen häufig in der Programmierung auf und werden als solche bezeichnet Programmiersprachen oder Muster . Je mehr Muster Sie kennen, desto einfacher fällt es Ihnen, eines zu finden, das zu einer bestimmten Art von Problem passt.

Beenden

Obwohl die harte Arbeit geleistet wurde, gibt es noch einige offene Fragen, die gelöst werden müssen. Das Hauptprogramm ruft zwei Methoden auf - conoAlleConoS und nachHauseZurückkehren - die noch nicht geschrieben wurden. Ebenso ruft sammleEinenTurm conoVonConoS und move AnDieWand auf. Glücklicherweise sind alle vier Methoden so einfach, dass sie ohne weitere Zerlegung move können, insbesondere wenn Sie in der Definition von nachHauseZurückkehren move AnDieWand verwenden. Hier ist die vollständige Implementierung:

Nächstes Kapitel