Universität Bremen
FB3 AG BKB CXL
Kleiner Katechismus zur Lösung von Übungsaufgaben in PI3

von Dennis Walter (Stand: 2010-11-01)

Hinweise auf Fehler und Verbesserungsvorschläge sind herzlich willkommen!

Table of Contents

In diesem Dokument werden Hinweise zur und Erwartungen an die Bearbeitung der Übungsaufgaben in der Veranstaltung Praktische Informatik 3 -- Funktionale Programmierung formuliert. Lesen Sie dieses Dokument bevor Sie sich an die Lösung der Aufgaben setzen!

Anforderungen an die Aufgabenlösungen

Eine Aufgabenlösung besteht aus kommentiertem Programmcode, einer Dokumentation der Lösung sowie Testfällen inklusive ihrer Beschreibung. Wir unterscheiden zwischen Quellcode-Kommentaren und Dokumentation (s.u.). Die hier beschriebene Vorgehensweise bezieht sich explizit nicht auf den Literate-Programming-Ansatz, in dem Quellcode und Dokumentation vermischt sind.

Programmcode

  1. Für unsere Zwecke besteht der Programmcode aus einer Menge von Dateien, die Haskell-Quellcode und Kommentare enthalten. Die Dateien enden mit .hs. Jede dieser Dateien entspricht grob dem folgenden Grundgerüst (s. Beispiel00/Modul1.hs) und definiert ein Modul, das den Namen der es beinhaltenden Datei trägt:

    {-| Kurze Modulbeschreibung, ggf. Autoren -}
    module ModulName where
    
    -- * Datentypen
    -- * Hauptfunktionen
    -- * Hilfsfunktionen
    
  2. Abgegebener Quellcode muss übersetzbar sein, auch wenn die erstellte Lösung evtl. nicht vollständig ist. Halbfertige Funktionen sollen auskommentiert werden und können in der Dokumentation erläutert werden (generelle Idee, vermutete verbleibende Fehler, Probleme). Dies ist nötig, damit die Tutoren den Code effizient (ggf. teilautomatisiert) prüfen können. Ggf. können Dummy-Funktionen verwendet werden, um den GHC zum Durchlaufen zu bringen. Beispiel:

    foo :: Bar -> Baz
    {- Nicht fertig gestellt. GHC meldet Typfehler
    foo b = if bazzy b then stripBar b else toBaz b
    -}
    foo b = defaultBaz
    
  3. Im Übungsblatt oder der dazugehörigen Vorlagendatei vorgegebene Signaturen von Funktionen müssen wie angegeben implementiert werden. Die Signaturen dürfen nicht geändert werden.

  4. Jede auf Dateiebene definierte Funktion erhält eine Typsignatur und wird mit mindestens einer Kommentarzeile (auf Deutsch oder Englisch) beschrieben. Die Beschreibung soll knapp aber präzise sein (exportierte, d.h. von anderen Modulen verwendbare Funktionen haben höhere Priorität):

    -- | Yields the /integer square root/ of its argument @x@, i.e.
    -- the @y@ such that @y * y <= x && (y+1) * (y+1) > x@.
    -- Undefined for negative inputs.
    isqrt :: Int -> Int
    isqrt x = ...
    

    Typischerweise soll der Kommentar Angaben zu den Eingaben und gelieferten Resultaten machen, Vorbedingungen und Nachbedingungen anführen und ausdrücken, für welche Eingaben die Funktion ggf. nicht definiert ist und wie auf derartige Eingaben reagiert wird.

  5. Implementierungstechniken müssen nicht erläutert werden, sofern sie nicht Hauptbestandteil der Lösung bzw. besonders pfiffig oder schwer nachvollziehbar sind. Zum Beispiel ist für isqrt lediglich ihre wichtigste Eigenschaft im Kommentar angegeben. Dass intern Randfälle gesondert behandelt werden, dass eine Hilfsfunktion isqrtHelper die Hauptarbeit erledigt, oder gar dass Zwischenwerte x, y per let gebunden werden ist direkt aus dem Code ersichtlich.

Dokumentation

  1. Gute Dokumentation zeichnet sich nicht durch ihre Länge, sondern ihre Lesbarkeit aus. Für die in PI3 gestellten Aufgaben ist eine Dokumentation im Umfang von maximal 4 Seiten pro Übungsblatt vollkommen ausreichend. Gerade am Anfang kann dieser Umfang noch deutlich unterschritten werden.

  2. Ziel der Dokumentation ist es erstens, auf konzeptioneller Ebene eine Beschreibung der Problemlösung zu bieten [1]. Zweitens sollte sie Hinweise auf Besonderheiten bei der Ausführung der erstellten Funktionen bzw. des Programms enthalten [2]. Drittens soll in der Dokumentation aufgeführt werden, was das Programm nicht kann (aber den Anforderungen nach können sollte) und was mögliche Ursachen hierfür sind [3].

    Für Aufgaben bei denen keine Programmierung erforderlich ist, ergibt sich die zu erstellende Dokumentation meist direkt aus der Aufgabenstellung (wie etwa bei einem Korrektheitsbeweis mittels struktureller Induktion o.ä.).

  3. In der Dokumentation sollte auf den Quellcode allerhöchstens auf Schnittstellenebene eingegangen werden! Codeauszüge sind nur in den allerwenigsten Fällen sinnvoll, da codenahe Probleme am besten in Quellcodekommentaren abgehandelt werden. Eine Ausnahme bildet die Diskussion eines Problemfalls, etwa "hier kamen wir einfach nicht weiter: <code>. In Zeile 7 wird ein Typfehler Expected Int, got Integer gemeldet, den wir nicht nachvollziehen können". Der LaTeX-Befehl \lstinputlisting des Listings-Pakets kann hier hilfreich sein.

  4. Für manche Tutoren ist es einfacher, wenn Quellcode und Dokumentation "in einem Rutsch" ausgedruckt werden. In diesem Fall sollte der Quellcode vollständig als Anhang in die Dokumentation eingebunden werden. Ihr Tutor wird Sie hierauf hinweisen.

[1]Geeignete Inhalte sind beispielsweise die mathematische Darstellung von Lösungsansätzen bzw. ein Nachweis der Korrektheit bestimmter Lösungen (hier ist LaTeX für die ansprechende Darstellung von Formeln deutlich geeigneter als ASCII-Codekommentare). Ebenfalls gern gesehen sind kurze Ausführungen über Designentscheidungen (etwa "Das Wörterbuch wurde als endliche Abbildung von Worten zu Listen von Worten (Map Wort [Wort]) repräsentiert. Dies ist bzgl. des Abfragens -- dem Hauptanwendungsfall -- effizienter ist als eine Darstellung als Assoziationsliste ([(Wort, [Wort])])")
[2]Ist zum Beispiel in der Aufgabe freigestellt, welche Kommandozeilenparameter ein Programm erwarten soll, so muss diese Entscheidung hier aufgeführt werden, damit das Programm ohne Aufwand vom Tutor gestartet werden kann.
[3]

Mögliche Angaben sind hier etwa

  • wurde aus Zeitmangel nicht implementiert,
  • Terminiert bei Eingaben größer 100 nicht. Wir vermuten, dass die doppelt rekursive Implementierung von fib a = fib (a - 1) + fib (a - 2) mit ihrer extrem schnell wachsenden Aufrufzahl hierfür verantwortlich ist.

Testfälle

Mittels Testfällen weisen Sie während der Entwicklung nach, dass ihr Programm Fehler enthält. Diese werden behoben, woraufhin derselbe Testfall nun dazu dient zu vermeiden, dass dieselbe Fehlerwirkung erneut, z.B. nach Änderungen, auftritt.

Zudem stellen Sie sicher, dass Ihr Programm ausreichend zuverlässig arbeitet, indem Sie es einerseits ausführen und die zurückgelieferten Resultate mit den von Ihnen erwarteten vergleichen. Andererseits sollen Sie das Programm mit Eingaben ausführen, von denen Sie vermuten, dass sie zu Fehlerwirkungen führen können. Dies betrifft insbesondere sog. Randfälle bzw. Grenzwerte (abhängig vom konkreten Fall können dies leere Listen und Bäume, negative Zahlen, 0, sortierte Listen, große Eingabedaten usw. sein).

Haskell ist ideal zum Testen geeignet. Es ist sehr leicht, Eingabe-Testdaten zu erzeugen (man kann sie einfach hinschreiben...), und wegen der fehlenden Seiteneffekte lassen sich Testläufe beliebig wiederholen und sind nicht von äußeren Nebenbedingungen abhängig.

Beachten Sie beim Testen die folgenden Ratschläge:

  1. Sammeln Sie bereits während der Entwicklung Testfälle, d.h. übernehmen Sie Ausdrücke, die sie vielleicht in den GHCi eingetippt haben und die zu Fehlern führten, als Testfall. Hier zum Beispiel eine fehlerhafte Implementierung der Listenumkehr:

    ghci> reverse (reverse [1, 2]) == [1, 2]
    False
    
    -- In Main.hs
    test_rev_rev :: Bool
    test_rev_rev = reverse (reverse [1, 2]) == [1, 2]
    
  2. Sowohl aufgrund der Eigenschaften von Haskell als auch der Eigenschaften der Übungsblätter ist es häufig der Fall, dass strukturelle Eigenschaften von Datentypen und den auf ihnen definierten Funktionen vorliegen, die eine exzellente Grundlage für Tests bilden. Soll z.B. ein Modul für Container ohne Duplikate entworfen werden, so wäre ein natürlicher Testfall zu prüfen, dass das Einfügen eines Elements und das anschließende Entfernen zu dem Eingangscontainer führt. Dies lässt sich verallgemeinern, indem eine entsprechende Testfunktion geschrieben wird:

    -- Signaturen des Container-Moduls
    insert :: Elem -> Container -> Container
    remove :: Elem -> Container -> Container
    -- Testfunktion
    test_insert_remove :: Elem -> Container -> Bool
    test_insert_remove x c = remove x (insert x c) == c
    

    Die Testfunktion kann dann für konkrete Testfälle mit interessanten Eingaben aufgerufen werden, etwa test_insert_remove myFavouriteElem emptyContainer. Ein nützliches Idiom ist hierbei die Verwendung von Listenkomprehensionen (anfangs noch unbekannt), mit der sich "günstig" viele Kombinationen von Eingaben für die Testfunktion generieren lassen:

    test_ins_rem_many :: Bool
    test_ins_rem_many = and [test_insert_remove x c | x <- listOfContainers, c <- listOfElements]
    
  3. Lagern Sie Tests in entsprechende Dateien aus (TestX.hs für ein Modul X.hs) sobald der Umfang der Lösung eine einzelne Datei übersteigt. Andernfalls sollten Tests als Unterabschnitt in die Quelldatei (dann meist Main.hs) integriert werden. Siehe hierzu Datei-/Verzeichnisstruktur.

  4. Nehmen Sie einen Abschnitt Tests in die Dokumentation mit auf, in dem Sie in aller Kürze darstellen

    • welche (Arten von) Tests sie durchgeführt haben [4],
    • wie diese auszuführen, d.h. zu wiederholen sind [5],
    • welche Tests fehlgeschlagen sind (und ggf. warum)
  5. Benutzen Sie -- sobald die nötigen Grundlagen dafür in der Vorlesung vermittelt wurden -- automatische Test-Tools wie HUnit und QuickCheck, die insbesondere das wiederholte Ausführen von Tests erleichtern.

[4]

Beispielaussage: Als Testfälle für den Datentypen data Nat = Zero | Suc Nat und die Operationen plus :: Nat -> Nat -> Nat sowie times :: Nat -> Nat -> Nat wurden die jeweiligen Assoziativgesetze und Kommutativgesetze für diverse Eingaben geprüft. Zudem wurde nachgewiesen, dass Zero ein Nullelement bzgl. der Multiplikation (s. test_mult_zero) und ein Einselement bzgl. der Addition ist (s. test_add_one). Alle Tests verliefen erfolgreich, bis auf einen. Wir haben keine Erklärung hierfür:

test_add_mult_distrib :: Bool
test_add_mult_distrib = mult (add x7 x9) x8 == add (mult x7 x8) (mult x7 x9)

(Wir sehen: auch beim Testen kann man Fehler machen. Die rechte Seite sollte add (mult x7 x8) (mult x9 x8) sein.)

[5]Idealerweise reicht hier eine so einfache und kurze Aussage wie alle test_XXX Variablen vom Typ Bool repräsentieren Tests oder durch Eingabe von make test werden alle Tests ausgeführt und die Ergebnisse an der Konsole ausgegeben..

Bewertung

Die Bewertung folgt dem üblichen 40/40/20 Schema. 40% der Punkte, die für die Lösung einer Aufgabe erreicht werden können, werden also durch den (kommentierten!) Quellcode erzielt, 40 weitere Prozent durch die Dokumentation, und die restlichen 20 Prozent durch dokumentierte Testfälle. In Einzelfällen, z.B. wenn die Hauptarbeit in der Implementierung steckt und deren Struktur sich direkt aus der Aufgabenstellung ergibt, kann die Implementierung auch stärker gewichtet werden.

Datei-/Verzeichnisstruktur

Freiheit ist das höchste Gut. Sie hält allerdings bei der Gestaltung der Struktur der Abgaben eine wohlverdiente Siesta. Stattdessen wird schlicht und ergreifend die hier angegebene Struktur eingehalten. Wir gehen davon aus, dass die Bearbeitung aller Übungsblätter in einem Grundverzeichnis $pi3 erfolgt. Unterhalb dieses Verzeichnisses besteht die folgende Struktur:

$pi3/
    Beispiel00/
        # Beispielprogramm zur Demonstration des Übersetzens
        Beispiel00.cabal
        Main.hs
        Modul1.hs
        dist/
            # Von cabal erzeugt

            build/
                Blatt01/
                    Main.hi
                    Main.o

            doc/
                html/
                    Uebungsblaetter/
                        index.html
                            # Übersicht über alle dokumentieren Quelldateien
                        # Weitere Dateien

    Blatt01/
        Blatt01.cabal
            # Steuerung des Build-Tools cabal
        Main.hs
            # Zentrale Anlaufstelle mit main-Funktion bzw.
            # Top-Level Definitionen
        Modul1.hs
        Modul2.hs
        # ...

        TestMain.hs
            # Enthält die Testfälle für Modul Main
        TestModul1.hs
            # Testfälle für Modul Modul1
        # ggf. weitere Tests

        Blatt01.pdf
            # Dokumentation der Lösung, ggf. mit Verweis auf weitere
            # zu beachtende Dateien

        *.log *.aux *.odt *.doc *.txt

    Blatt02/
        # Analog zu Blatt01

    # ... weitere Blätter

    Build.cabal
        # Vorlage. Anweisungen für das automatische Build-Tool cabal
    Katechismus.rst
        # Dieses Dokument
    pi3-muster.tex
        # LaTeX-Vorlage für die Dokumentation von Aufgabenlösungen
    pi3.cls
        # LaTeX-Klasse, wird von von pi3-muster.tex benötigt
    haskell-code.sty
        # von pi3.cls benötigt; Hiliting von Haskell-Code.

Anmerkungen hierzu:

  • Zentrale Anlaufstelle für die Tutoren ist die jeweilige Dokumentationsdatei (z.B. $pi3/Blatt01/Blatt01.pdf).
  • Weitere Dateien, die keinen Quellcode enthalten, werden zunächst ignoriert!
  • Erzeugte Dateien (wie *.log) sollen vor der Abgabe gelöscht werden! Dies betrifft nicht ursprüngliche Dateien (wie *.tex *.doc oder *.odt).
  • Ein Gerüst mit den nötigen Verzeichnissen und insbesondere auch einer Vorlage für die Dokumentation erhält man, indem man das PI3-Starterkit herunterlädt und entpackt. Die darin enthaltenen LaTeX-Vorlagen müssen ggf. in jedes Unterverzeichnis kopiert werden -- oder man setzt die TEXINPUTS entsprechend.
  • Tutoren haben das Recht die Annahme der Abgabe zu verweigern, wenn diese die hier vorgestellte Struktur nicht einhält. Die Verweigerung hat keinen Punktabzug zur Folge, sofern die betreffende Übungsgruppe innerhalb 24 Stunden nach der Aufforderung per Mail (durch den Tutoren; an alle Gruppenmitglieder) eine konforme Abgabe abliefert (deren Inhalt keine weiteren Änderungen aufweisen darf).

Verwendung von cabal

Cabal ist ein nützliches Werkzeug zur automatisierten Erzeugung von Haskell-Bibliotheken, ausführbaren Programmen sowie deren API-Dokumentation. Es erzeugt die entsprechenden Dateien in vordefinierten Verzeichnissen und übernimmt das Abhängigkeitsmanagement.

Die Verwendung von cabal ist nicht verpflichtend, wird aber von uns empfohlen. Hat man die Konfiguration einmal durchgeführt, gehen die üblichen Entwicklungsaufgaben (neu kompilieren, Abhängigkeiten heruterladen, API-Dokumentation erzeugen) schneller von der Hand. Wir erläutern die für PI3 relevante Verwendung von cabal anhand des Beispielverzeichnisses (cd $pi3/Beispiel00).

  1. Die Konfigurationsdatei X.cabal (s. Beispiel00/Beispiel00.cabal) ist für cabal was ein Makefile für make ist. Wichtig ist, dass unter Exposed-Modules alle erzeugten Quelldateien gelistet sind:

    Exposed-Modules: Main,
                     Modul1
    

    Der Executable-Abschnitt spielt für die ersten Blätter keine Rolle und sollte daher entfernt werden. Später definiert dieser den Namen und Inhalt des zu erstellenden ausführbaren Programms.

  2. cabal muss nach jeder Änderung an seinen Konfigurationsdaten diese neu lesen (cabal configure) bzw. für eine spätere Installation im Verzeichnis $HOME/.cabal/bin (unter Linux; cabal zeigt auch unter Windows an, in welches Verzeichnis es Dateien kopiert): cabal configure --user

  3. Die Übersetzung aller unter Exposed-Modules gelisteten Module erfolgt per cabal build. Dieser Befehl wird auch zur Entwicklungszeit im Edit-Compile-Debug-Zyklus verwendet. Die Fehlermeldungen sind die des GHC (der von cabal aufgerufen wird).

  4. Die API-Dokumentation (vgl. Javadoc) wird erzeugt mittels cabal haddock bzw. bei vorliegender Installation von HsColour per cabal haddock --hyperlink-source. Die Ausgabe erfolgt nach dist/doc/html/.

Abgabemodalitäten

Zur effizienten Bearbeitung der Lösungen ist es unbedingt erforderlich, dass folgende Anforderungen eingehalten werden:

  1. Die Abgabe erfolgt per Email. Der Betreff lautet

    PI3, Gruppe X, Blatt Y

    Der Anhang der Email besteht aus einem Archiv des Verzeichnisses BlattY, benannt BlattY.zip (Y ist die Nummer des abzugebenden Übungsblattes). Dieses Archiv kann (z.B. unter Linux für Blatt 3) wie folgt erzeugt werden:

    cd $pi3
    rm -f Blatt03/*.log Blatt03/*.aux Blatt03/*.tmp
    zip -r Blatt03.zip Blatt03/
    

    Bei der Verwendung GUI-basierter Archivierer bitte darauf achten, dass das Verzeichnis gepackt wird, und nicht bloß dessen Inhalt.

  2. Die Dokumentation der Lösung muss die folgenden Angaben beinhalten

  • Aktuelles Semester
  • Nummer der Übungsblattes
  • Nummer der Gruppe und Namen der Gruppenmitglieder
  • Name des Tutoren
  • Abgabedatum

Die Einhaltung dieser Anforderung erfolgt am einfachsten, indem die LaTeX-Vorlage für Aufgabenlösungen aus dem PI3-Starterkit verwendet wird.

Beispiel

Eine Beispiellösung ist demnächst verfügbar.