Mehr Expressivität wagen

(Dieser Post schließt sich an den letzten zum Thema Snap! an.)qs

In der funktionalen Programmiersprache Haskell gibt es eine berühmte Implementierung des Quicksort-Algorithmus, die nur zwei (!) Zeilen lang ist. Wem Haskell zu exotisch ist, der kann die Idee z. B. in Python so umsetzen:

def qsort(list):
  if not list:
    return []
  else:
    pivot = list[0]
    less = [x for x in list[1:] if x < pivot]
    more = [x for x in list[1:] if x >= pivot]
    return qsort(less) + [pivot] + qsort(more)

In der Nacht vor dem Workshop in München fiel mir ein, dass man diese Implementierung fast direkt nach Snap! übertragen kann, nämlich so:qsHier kann ich leider nicht die schönen list comprehensions aus Haskell oder Python verwenden, sondern nutze die klassische higher-order Funktion filter (in Snap! heißt sie keep items such that). Filter wird mit einer Liste und einem Prädikat (= Funktion, die einen Wahrheitswert berechnet) als Argumenten aufgerufen und liefert eine neue Liste zurück, die nur diejenigen Werte enthält, für die das Prädikat wahr wird — es werden also nur diejenigen Listenelemente „gefiltert“, die eine Bedigung erfüllen. In unserem Fall ist die Bedingung bzw. das Prädikat ein kurzer Lambda-Ausdruck, der prüft, ob das jeweils an die Leerstelle* im grau umrandeten Puzzleteil eingesetzte Element der Liste kleiner als das Pivot-Element ist.

Mir ist schon klar, dass jemand, der sich noch nie mit funktionaler Programmierung beschäftigt hat, das nicht unbedingt sofort intuitiv finden wird — auch mir gefällt gerade deshalb die Python-Version noch besser, weil sie so nahe an der vertrauten mathematischen Mengennotation ist. Aber dass es sich auch beim Snap!-Code um eine ganz direkte Umsetzung des oben umgangssprachlich beschriebenen Prinzips handelt, sollte offensichtlich sein.

Wie wäre es in Java? Natürlich ebenso möglich, aber viel, viel umständlicher. Es fehlen einfach die mächtigeren Werkzeuge zur Manipulation von Listen. Dadurch wird die Umsetzung von Quicksort in Java zwangsweise auf einem wesentlich niedrigeren Abstraktionsniveau stattfinden müssen als in Haskell, Python und Snap!, wo die fünf Schritte des umgangssprachlichen Algorithmus direkt in Code übertragen werden können. Ich glaube, dass es für Schüler schon schwer genug ist, die Grundidee von Quicksort zu verstehen. Ihn bei der Umsetzung in ein Programm dann auch noch sofort „herunterbrechen“ zu müssen auf explizite Schleifen und Anweisungen zum Erstellen und Verändern von Listen, das kommt mir noch viel schwerer vor.

„Stopp mal!“ wird jetzt vielleicht mancher rufen. „Der Algorithmus, so wie du ihn präsentiert hast, ist aber furchtbar ineffizient. Die Liste wird da unnötigerweise zweimal durchlaufen (in beiden Aufrufen von keep items such that). Ich mache das alles in einer Schleife; geht viel schneller.“

Wer das ruft, hat sachlich recht — liegt aber meiner Meinung nach pädagogisch falsch. Schüler müssen zuerst sehen, wie ein Verfahren überhaupt in Code umgesetzt werden kann, und das möglichst high-level. Dann und erst dann sollen sie sich über die Effizienz Gedanken machen. Idealerweise führt die Suche nach einer effizienteren auch zu einer eleganteren Lösung. In Python z.B. sähe die erste Fassung mit nur einem Listendurchlauf vielleicht so aus:

def qsort(L):
  if not L:
    return []
  pivot = L[0]
  less, more = [], []
  for x in L[1:]:
    if x < pivot:
      less.append(x)
    else:
      more.append(x)
  return qsort(less) + [pivot] + qsort(more)

Die Liste wird also nun mittels einer Schleife in zwei neue Listen partitioniert. Aber der Code ist (finde ich) viel schwerer verständlich geworden. Und ist es für den Algorithmus denn wichtig, auf welche Weise die Partitionierung durchgeführt wird? Natürlich nicht! Verstecken wir die Details also in einer Funktion:

def partition(L, pivot):
    less, more = [], []
    for x in L:
        if x < pivot:
            less.append(x)
        else:
            more.append(x)
    return less, more

def qsort(L):
    if not L:
        return []
    pivot = L[0]
    less, more = partition(L[1:], pivot)
    return qsort(less) + [pivot] + qsort(more)

So, jetzt sieht qsort richtig aufgeräumt aus; sogar kürzer als die ursprüngliche Fassung mit den zwei list comprehensions.  Die spezielle Aufgabe der Partitionierung wurde schön isoliert und in eine eigene Funktion partition ausgelagert. Und wenn man sich das so ansieht, kommt plötzlich eine entscheidende Erkenntnis: So etwas wie partition kann man eigentlich öfter brauchen, z.B. wenn man gerade und ungerade Zahlen von einander trennen will oder Worte, die mit Großbuchstaben beginnen, von denen, die es nicht tun, oder Datensätze von weiblichen und männlichen Mitarbeitern. Man könnte dafür eine Reihe von Funktionen schreiben, die jedesmal eine gegebene Liste in zwei neue aufteilt. Diese Funktionen glichen sich komplett — nur der Test zur Entscheidung, wohin ein Listenelement sortiert wird, wäre immer ein anderer.

„Lauter Funktionen, die fast gleich sind… Kann man da nicht etwas zusammenfassen?“ fragt sich da vielleicht der eine oder andere aufgeweckte Oberstufenschüler, der Ähnliches schon bei der Einführung von Funktionen, deren Parametrisierung, der Vererbung, womöglich dem einen oder anderen Design Pattern oder allgemein dem DRY-Prinzip gesehen hat. Und wir antworten: „Aber ja doch — Higher-order functions to the rescue!“

def partition(L, fn):
    falses, trues = [], []
    for x in L:
        if fn(x):
            falses.append(x)
        else:
            trues.append(x)
    return falses, trues

def qsort(L):
    if not L:
        return []
    pivot = L[0]
    def ist_kleiner(x):
        return x < pivot
    less, more = partition(L[1:], ist_kleiner)
    return qsort(less) + [pivot] + qsort(more)

Hier gibt’s nun natürlich einiges zu sehen: Funktionen als Parameter von Funktionen (hier: fn).  Eine Funktion (ist_kleiner), die innerhalb einer anderen Funktion (qsort) definiert wird und dabei Bezug nimmt auf eine Variable außerhalb ihrer eigenen Definition (pivot).*** Trotzdem: Ich glaube, wenn man — anders als wir mit C, Pascal, Java groß Gewordenen — noch gar nicht verinnerlicht hat, dass Funktionen keine Variablenwerte sein dürfen, tut man sich damit gar nicht so schwer.

Diese Version des Algorithmus gefällt mir nun sehr gut: Wir haben einerseits die Effizienz eines einzigen Listendurchlaufs pro Rekursionsionschritt, andererseits haben wir eine neue, vielseitig einsetzbare Funktion partition und wieder eine kurze, knackige Funktion qsort, die nur das enthält, was wirklich nötig ist.

Noch kürzer-knackiger, aber unnötig verwirrend für Schüler wäre qsort mit einem Lambda-Ausdruck, d.h. einer Funktion, die so klein und unwichtig ist, dass sie nicht einmal einen Namen bekommt:

def partition(L, fn):
    falses, trues = [], []
    for x in L:
        if fn(x):
            falses.append(x)
        else:
            trues.append(x)
    return falses, trues

def qsort(L):
    if not L:
        return []
    pivot = L[0]
    less, more = partition(L[1:], lambda x: x < pivot)
    return qsort(less) + [pivot] + qsort(more)

Egal in welcher Version, wir haben nun ein Programm, dass nicht nur effizienter ist als das Ursprüngliche, sondern auch modularer, flexibler, allgemeiner****.  Wenn man dahin kommen könnte, dass Schüler verstehen, warum so etwas gut und erstrebenswert ist…

Nur der Vollständigkeit halber kommt jetzt noch eine eher funktionale Version von partition, ohne Schleife, dafür mit Rekursion.  Kann man so machen, muss man aber überhaupt nicht. Lehrreich — und irgendwie schön — ist diese Version aber vielleicht doch.

def partition(L, fn):
    if not L:
        return [], []
    first, rest = L[0], L[1:]
    falses, trues = partition(rest, fn)
    if fn(first):
        return [first] + falses, trues
    else:
        return falses, [first] + trues

Nun aber zum Titel dieses Artikels: Ich weiß, dass Kollegen, die das Glück haben, einen vierstündigen Informatikkurs in der Oberstufe anbieten zu können, durchaus auf diesem Niveau unterrichten — auch in Java. Ich bin in einer anderen Situation: Meine Oberstufenschüler haben in ihrer gesamten Schulkarriere nur zweimal ein halbes Schuljahr zwei Wochenstunden lang Gelegenheit zu erfahren, was Programmieren überhaupt ist. Das macht insgesamt 80 Schulstunden in ihren letzten beiden Schuljahren, in einem Fach, das für diese Schüler im Abitur minimale Relevanz hat. Für mich ist also jede Minute kostbar, in der ich diesen Schülern ein bisschen das informatische, problemlösende, abstrahierende Denken vermitteln kann.  Jedesmal, wenn ich erklären muss, was void oder static oder public oder float oder int bedeutet (oder den Schülern vermittle, dass sie das zwar dauernd tippen, aber sowieso nicht verstehen müssen/können), verlieren ich und die Schüler Zeit, die sie damit verbringen könnten, an der Lösung eines Problems zu knobeln. Bei so wenig Zeit wünsche ich mir, eine Sprache benutzen zu können, die maximal anfängerfreundlich ist (so wenig und so intuitive Syntax wie möglich) und gleichzeit so ausdrucksstark, dass sie die Schüler nicht beim Denken behindert!

Ich bin ich mir noch nicht sicher, ob Snap! diese Sprache ist. Andererseits: Was für die Studenten der UC Berkeley hervorragend funktioniert, sollte eigentlich auch für deutsche Schüler gut genug sein, oder?

P.S. Warum habe ich eigentlich in meinem Snap!-Quicksort das Pivot-Element zufällig ausgewählt? Wer das weiß, bekommt nen Ball!

P.P.S. Man kann ja in Snap! eigene Kontrollstrukturen programmieren (s. Bild im letzten Post).  Wenn das geht, dann kann man sich doch sicher auch eigene list comprehensions bauen. Vorschläge, anybody?

** Ist diese Leerstelle nicht visuell wunderbar anschaulich dafür, dass dieser Block noch nicht ausgeführt werden kann, weil ihr das Entscheidende, ein Argument, noch fehlt?

*** Übrigens will ich hier gar nicht so tun, als könnte man Ähnliches nicht auch in Java tun.  „Anonyme innere Klassen“ heißt hier das Stichwort. Als ich die vor über 10 Jahren kennenlernte und verstand, was ich in Java damit anfangen kann, war ich sowas von begeistert — und bin tatsächlich, glaube ich, dadurch ein besserer Programmierer geworden. Heute kenne ich aber auch ein paar Sprachen, in denen die zugrundeliegende Idee (closures) so viel einfacher umgesetzt werden kann (z.B. in unserem Python-Beispiel die Funktion ist_kleiner) als in Java.

**** Eigentlich sollte man sollte man qsort nun aber noch mit der Vergleichsfunktion parametrisieren, so dass man z.B. mit qsort(L, ist_groesser) absteigend sortieren könnte.  Aber das überlasse ich als Hausaufgabe euch Lesern.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s