Hochstapelei

Wissen Sie, was ein Stack ist? In der Informatik ist damit eine Datenstruktur gemeint. Auf einem Stack, zu deutsch "Stapel", können Sie Datenelemente ablegen und wieder entfernen. Ein Stack organisiert die Datenablage in einer Form, die man mit "last in, first out" bezeichnet: Das letzte auf einem Stapel abgelegte Element ist auch das erste, das Sie wieder vom Stapel nehmen können.

Für einen Stapel ist eine Handvoll Methoden definiert. Der Konstruktor, der einen Stack erzeugt; eine push-Methode, mit der Sie ein Element auf dem Stack ablegen können; eine top-Methode, die Ihnen verrät, was "oben" auf dem Stack liegt (das Element verbleibt auf dem Stack); eine pop-Methode, die Ihnen das oberste Element vom Stack entfernt; und eine is_empty-Methode, mit der sich feststellen lässt, ob ein Stack leer ist oder nicht.

Wenn Sie einen Stack in einer OO-Sprache umsetzen wollen, dann ist eine typische Vorgehensweise die Folgende: Sie suchen eine Datenstruktur, die Ihre Programmiersprache anbietet und die der Idee und Arbeitsweise eines Stacks so nahe kommt wie möglich. Diese Datenstruktur "verbergen" Sie dann hinter den Methoden.

Zum Beispiel bietet die Liste oder ein Array eine einigermaßen gute Implementierungshilfe. Ihre Umsetung (hier in Python) könnte wie folgt aussehen; ich greife dabei auf die interne Datenstruktur der Liste zurück.

LAST = -1

class Stack1(object):
    def __init__(self):
        self.elements = []
    def push(self,element):
        self.elements.append(element)
    def top(self):
        assert not self.is_empty()
        return self.elements[LAST]
    def pop(self):
        assert not self.is_empty()
        self.elements.pop()
    def is_empty(self):
        return self.elements == []

Wie Sie sehen, ist die Verwendung der Liste wirklich naheliegend. Es gibt Methoden, wie zum Beispiel "pop", die für Listen direkt angeboten werden und den gewünschen Effekt haben. Andere Methoden, hier etwa "append", firmieren für die Liste lediglich unter einem anderen Namen. Der Stack präsentiert sich als eine für einen besonderen Einsatzzweck zurückgeschnittene Liste. Übrigens, die eingestreuten assert-Statements sind als PreConditions zu verstehen. Mehr dazu finden Sie in meinem Beitrag "Design by Contract in Practice".

Geht es auch gänzlich anders? Was, wenn uns keine anderen Datentypen als Annäherung oder Hilfsmittel zur Verfügung stehen? Lässt sich rein mit den Boardmitteln der Objekt-Orientierung ein Stack umsetzen? Reicht der Einsatz von Konstruktoren, Attributen und Methoden aus?

Ja, es geht -- unter einer winzigen Voraussetzung: Sie müssen die Möglichkeit haben, Attributwerte auf ihre Gleichheit hin zu überprüfen. Am Rande: Das belegt, wie fundamental die Idee der Gleichheit in der Informatik ist; eng damit verwandt ist die Idee der Identität.

class Stack2(object):
    def __init__(self,top=None,bottom=None):
        assert (top,bottom) == (None,None) or \
               isinstance(bottom,Stack2)
        self.ontop, self.bottom = top, bottom
    def push(self,element):
        return Stack2(element,self)
    def top(self):
        assert not self.is_empty()
        return self.ontop
    def pop(self):
        assert not self.is_empty()
        return self.bottom
    def is_empty(self):
        return self.bottom == None

Diese zweite Variante eines Stacks ist nicht eine Zeile länger als die erste. Und doch ist hier vieles anders. Diese Stack-Klasse hat zwei Attribute, "ontop" und "bottom". Das Attribut "ontop" repräsentiert das oberste Element auf dem Stack, "bottom" den "Rest" darunter. Dieser "Rest" kann None oder seinerseits ein Stack sein. Ein Stack mit "bottom" gleich None steht für einen leeren Stack; aus diesem Grund fordert auch das Assert-Statement im Konstruktor ein None für "top" ein. Denn ein leerer Stack, der einen "ontop"-Wert hat, das verwirrt und macht keinen Sinn.

Das ganze Geheimnis der Funktionsweise dieses Stacks liegt in der Verwendung des Konstruktors. Im Konstruktor wird ein "top"-Wert für das oberste Element und ein darunter liegender Stack eingefordert, um die Datenstruktur aufbauen zu können. Die Methoden "top" und "pop" sind nur Abfragen dieser im Konstruktor übergebenen Werte. Konsequenterweise verändert sich damit das Verhalten der "push"-Methode. Sie wird zum Generator neuer Stack-Objekte. Das Ablegen eines Elements auf einem Stack erzeugt einen neuen Stack, mit dem Element als "ontop" und dem vormaligen Stack als "bottom".

Dieses Beispiel zeigt zwei Dinge schön auf:

Zum einen ist es faszinierend zu sehen, wie man im Grunde rein mit Konstruktoren und Attributen alles zur Verfügung hat, um einen Stack zu realisieren. Es wird im Hintergrund keine Liste mehr benötigt, wie noch in der ersten Variante. Objekt-Orientierung ist, wenn Sie so wollen, in sich selbst abgeschlossen. Sie können sich eine Datenwelt erschaffen, ohne auf andere Datentypen zurückgreifen zu müssen. Mit einer kleinen Ausnahme: Sie müssen Objekte miteinander vergleichen können. Wenn Sie sich schon einmal mit ADTs (Abstrakten DatenTypen) befasst haben, werden Sie entdecken, dass es sich um die objekt-orientierte Fassung eines Stack-ADTs handelt.

Zum anderen: Es ist unmöglich, Design-Änderungen immer so durchzuführen, dass die Interfaces (die zugreifbaren Methoden) davon unberührt bleiben. Sie können machen, was Sie wollen, Sie bekommen das Interface von Variante 1 und von Vairante 2 nicht irgendwie vereinheitlicht. Die Rückgabewerte sind unterschiedlich. Die beiden Varianten dokumentieren fundamental alternative Design-Ansätze für den Stack. Es ist eine Illusion zu glauben, man könne einmal getroffene Interface-Entscheidungen für alle Zeit beibehalten und einzig und allein gegen Interfaces programmieren. Fundamental unterschiedliche Design-Alternativen ziehen nicht selten Änderungen an den Interfaces nach sich, die weit reichende Konsequenzen haben können. Wer Interfaces fixieren möchte, der schränkt die Suche nach Design-Alternativen erheblich ein.

Das ist eine interessante Lehre für das Software Engineering: So gut und wichtig Interfaces im Softwarebau sind, sie sind kein Wundermittel. Wer Systeme weiterentwickeln möchte, wer sie verbessern möchte, der muss auch bereit sein, Interfaces zu ändern -- mit allen damit verbundenen Konsequenzen.