Donnerstag, Juli 10, 2008

Typen in Wandlung: Das Paar, die Liste und der Stack

Ich habe meinen lieben HardCore-Informatik-Leser(inne)n schon lange keinen Programmcode mehr als Denkspur hinterlassen. Heute ist es mal wieder soweit. Zwei Punkte haben mich umgetrieben: (1) Die Fähigkeit von Objekten, ihren Typ zu verändern. (2) Der Vergleich von Liste und Stack.

Es wird ein langes Posting werden, aber vielleicht haben Sie Lust auf diese kleine Denk-Reise. Ein wenig setze ich voraus, dass Sie sich mit Scheme/Lisp und dort mit den Datentypen der Liste und des Paars auskennen. Und was ein Stack ist, wissen Sie als Informatiker sowieso.

Einleitung

Ein einfaches Beispiel mag die Idee von einem Objekt veranschaulichen, das seinen Typ ändern kann: Eine Ellipse ist beispielsweise über die Größe der Hauptachse und die Größe der Nebenachse eindeutig definiert. Sind Haupt- und Nebenachse gleich groß, dann haben wir einen Kreis, und die Unterscheidung in Haupt- und Nebenachse wird hinfällig; es genügt die Angabe eines Wertes, des Radius'. So kann ein sich veränderndes Ellipsen-Objekt zum Kreis-Objekt werden.

Nachfolgend möchte ich anhand der Datenstrukturen von Liste und Paar (beide bilden die Grundlage der Programmiersprache Scheme) zeigen, dass die Typbestimmung und -anpassung zur Laufzeit eine reizvolle Technik ist, die elegant mit Objekt-Orientierung umgesetzt werden kann. In Scheme wird die Liste wie auch das Paar mit ein- und derselben Grundoperation erzeugt, der cons-Operation. Einzig und allein die Verwendung einer leeren Liste an einer bestimmten Stelle im Konstruktor entscheidet, ob das resultierende Objekt eine Liste oder ein Paar ist.

Es zeigt sich aber auch ein schwerwiegendes Problem: Die OO-Lösung koppelt die Typen (Liste und Paar) in der Vererbungshierarchie über den Typen der leeren Liste miteinander. Das macht es andererseits unmöglich, die Liste wie einen Stack zu benutzen. Und das, obwohl Liste und Stack praktisch identisch sind. Ohne die Kopplung wäre das eine triviale Anpassung.

Die dynamische Typauflösung verträgt sich nicht mit der Konstruktion eines durchgehenden objekt-orientierten Typsystems. Ich frage mich, ob diese Kopplung von Liste, Paar und leerer Liste nicht zwangsläufig zu Problemen im Typsystem führen muss. Handelt es sich hier gar um einen Designfehler in Scheme/Lisp? [Anbei: Ich würde mich freuen, Gedanken und Hinweise von Typ-Experten zu bekommen.]

Bevor die Anwendung des Codes die Sachverhalte demonstrieren soll, bietet es
sich an, den Python-Code durchzugehen.

Programmcode: EmptyList, Cons, Pair, List

Die Codezeilen für __repr__ blasen den Code ein wenig auf. Ansonsten ist der Code schlank, er trägt alle Konzepte (EmptyList, List und Pair) explizit vor und nutzt Vererbung, um die Gemeinsamkeiten von List und Pair via Shared klar hervorzuheben. Die Klasse Cons dient dazu, die Typfestlegung erst durch den Gebrauch einer EmptyList() am "Ende" der Konstruktion via Cons möglich zu machen. Der Typ wird also, wenn man so möchte, dynamisch angepasst.

Es sei bereits an dieser Stelle darauf hingewiesen, dass der Code für List und Pair zwar wunderbar symmetrisch aussieht, es im Kern aber nicht ist. List und EmptyList bilden eine Allianz gegen Pair, obwohl List und Pair als gleichberechtigte Partner in der Vererbungshierarchie auftauchen. Diese Asymmetrie ist für die Unmöglichkeit verantwortlich, warum List nicht mit Stack überein gebracht werden kann. Wir kommen darauf noch zurück.


class EmptyList(object):
def is_empty(self): return type(self) == EmptyList
def __repr__(self): return "()"

class Cons(object):
def __new__(cls,car,cdr):
if type(cdr) in (List,EmptyList): return List(car,cdr)
return Pair(car,cdr)

class Shared(EmptyList):
def __init__(self,car,cdr):
self._car, self._cdr = car, cdr
def car(self): return self._car
def cdr(self): return self._cdr
def __repr__(self):
return "(%s %s" % (self._car,self._cdr.__repr__()[1:])

class List(Shared):
def __init__(self,car,cdr):
assert type(cdr) in (List,EmptyList)
Shared.__init__(self,car,cdr)
def __repr__(self):
if type(self._cdr) != List: # => type is EmptyList
return "(%s)" % self._car
return Shared.__repr__(self)

class Pair(Shared):
def __init__(self,car,cdr):
assert type(cdr) not in (List, EmptyList)
Shared.__init__(self,car,cdr)
def __repr__(self):
if type(self._cdr) != Pair:
return "(%s . %s)" % (self._car, self._cdr)
return Shared.__repr__(self)


Programmcode: EmptyStack und Stack

Vergleicht man den Aufbau des Stack mit dem der Liste, so fällt die absolute
Gleichheit ins Auge. EmptyStack entspricht EmptyList, Stack entspricht List.
Ich habe den Stack natürlich nicht ohne Absicht genau der gleichen Bauweise
unterworfen. Es ist lediglich abzugleichen, dass oben bei der Liste via
Shared Vererbung genutzt wird, um die gleichen Anteile von Pair und List
zusammenzufassen.


class EmptyStack(object):
def push(self,element): return Stack(element,self)
def is_empty(self): return type(self) == EmptyStack
def __repr__(self): return "[]"

class Stack(EmptyStack):
def __init__(self,ontop,bottom):
assert type(bottom) in (Stack,EmptyStack)
self.ontop, self.bottom = ontop, bottom
def top(self): return self.ontop
def pop(self): return self.bottom
def __repr__(self):
if type(self.bottom) != Stack: # => type is EmptyStack
return "[%s]" % self.ontop
return "[%s %s" % (self.ontop,self.bottom.__repr__()[1:])


Diskussion

Beginnen wir mit der leeren Liste. Sie können all das in einer interaktiven Python-Console ausprobieren.


>>> EmptyList()
()
>>> EmptyList().is_empty()
True


Paare können direkt erzeugt werden.


>>> Pair(1,2)
(1 . 2)
>>> Pair(1,2).is_empty()
False
>>> Pair(Pair(1,2),Pair(3,4))
((1 . 2) 3 . 4)
>>> Pair(Pair(1,2),Pair(3,4)).car()
(1 . 2)
>>> Pair(Pair(1,2),Pair(3,4)).cdr()
(3 . 4)


Ein Paar darf in seinem cdr keine leere Liste beheimaten -- das Paar würde sonst zur Liste mutieren.


>>> Pair(1,EmptyList())
Traceback (most recent call last):
...
AssertionError


Listen können direkt erzeugt werden. Im Konstruktor wird strikt eingefordert, dass der cdr selbst eine Liste oder eine EmptyList ist.


>>> List(1,2)
Traceback (most recent call last):
...
AssertionError
>>> l1 = List(1,EmptyList())
>>> l1
(1)
>>> l1.is_empty()
False
>>> l2 = List(1,List(2,EmptyList()))
>>> l2
(1 2)
>>> List(l1,List(3,l2))
((1) 3 1 2)
>>> List(3,List(l2,EmptyList()))
(3 (1 2))


Die Klassen List und Pair erzwingen ein vorheriges Festlegen auf einen Typen. Mittels Cons kann in gewohnter Lisp-Manier der Konstruktor bemüht werden. Abhängig vom cdr wird der entsprechende Typ (Liste oder Paar) automatisch erzeugt. Ein Punkt im Ausgabestring gibt wie zuvor an, ob es sich um ein Paar handelt oder nicht.


>>> Cons(1,2)
(1 . 2)
>>> Cons(1,EmptyList())
(1)
>>> Cons(1,Cons(2,Cons(3,EmptyList())))
(1 2 3)
>>> Cons(1,Cons(2,Cons(3,4)))
(1 2 3 . 4)


Car und cdr arbeiten natürlich wie Lisp/Scheme.


>>> Cons(1,2).car()
1
>>> Cons(1,2).cdr()
2
>>> Cons(1,Cons(2,Cons(3,EmptyList()))).car()
1
>>> Cons(1,Cons(2,Cons(3,EmptyList()))).cdr()
(2 3)
>>> Cons(1,Cons(2,Cons(3,EmptyList()))).cdr().car()
2


Kommen wir zum Stack, der -- wenn man möchte -- wie eine Liste aufgesetzt werden kann. Ich habe die Beispiele zur Liste hier übernommen. Ersetzt man gedanklich die vormals runden Klammern durch eckige, dann kommt exakt dasselbe raus. Wen wundert's, da doch der Code praktisch dergleiche ist?!


>>> EmptyStack()
[]
>>> EmptyStack().is_empty()
True
>>> Stack(1,2)
Traceback (most recent call last):
...
AssertionError
>>> s1 = Stack(1,EmptyStack())
>>> s1
[1]
>>> s1.is_empty()
False
>>> s2 = Stack(1,Stack(2,EmptyStack()))
>>> s2
[1 2]
>>> Stack(s1,Stack(3,s2))
[[1] 3 1 2]
>>> Stack(3,Stack(s2,EmptyStack()))
[3 [1 2]]


Der Unterschied zwischen einer Liste und einem Stack besteht jedoch im grundsätzlichen Gebrauch. In Scheme/Lisp kann eine Liste ausschließlich über den Konstruktor cons erzeugt werden (wir lassen set-car! und set-cdr! außen vor, wir bleiben rein funktional).


>>> l = Cons(1,Cons(2,EmptyList()))
>>> l
(1 2)
>>> l.car()
1
>>> l.cdr()
(2)


Ein Stack hingegen wird ausgehend vom EmptyStack über push-Operationen gefüllt.


>>> s = EmptyStack().push(2).push(1)
>>> s
[1 2]
>>> s.top()
1
>>> s.pop()
[2]


Schaut man in die Umsetzung der push-Operation, so verbirgt sie nur den Konstruktor-Aufruf, der im Hintergrund ausgeführt wird.

Im Grunde können die Liste und der Stack als vollkommen gleichwertige Datenstrukturen aufgefasst werden. Für eine Liste gälte es lediglich, eine der Push-Operation entsprechende Methode hinzuzufügen, die man "add" oder besser noch "prefix" nennen könnte. (Das "prefix" scheint mir als Gegenentwurf zu "append" gut zu passen, da die Liste ja sozusagen nach vorne wächst und nicht über Anhängsel erweitert wird.) Den Stack könnte man analog den Aufbau über eine Konstruktor-Funktion erlauben, wie hier schon geschehen. Das sind, wenn man so möchte, Details, die es anzugleichen gilt. Liste gleich Stack, Stack gleich Liste.

Im Scheme/Lisp-Kontext ist das jedoch nicht ganz korrekt. Und das hat mit dem Pair-Typen zu tun. Das Pair bringt einen neuen Twist in die Angelegenheit.

Da bei Pair im cdr jedes beliebige Element stehen kann außer EmptyList und List, verbietet sich die Möglichkeit, von einem Ausgangselement (z.B. der Zahl 7) via push bzw. prefix ein Pair zu konstruieren! Denn das hieße, dass jeder Objekttyp (Zahl, String, Boolean etc.) diese push/prefix-Operation anbieten müsste. EmptyList könnte eine solche Operation für die Konstruktion von Listen anbieten. Dort passt die Operation logisch hin. Aber warum um alles in der Welt sollte eine 7 ein push kennen und realisieren. In OO-Denke hieße das, dass der Typ an der Spitze des Typsystem eine push-Operation anbieten muss, von dem alle anderen Typen erben. Damit wäre allen Objekten im System die Grundmöglichkeit gegeben, sich via push in einen Container namens Pair zu verfrachten. Ein eigenartiges Typsystem wäre das.

Aus dieser Problematik heraus hat man natürlich das push/prefix bei Scheme nicht im Angebot. Der minimalen Asymmetrie im nicht gleichen Umgang mit EmptyList durch Pair und List ist es geschuldet, dass Listen nicht dasselbe Interface wie Stacks anbieten und damit in letzter Konsequenz auch nicht als solche zu gebrauchen sind.

Man sieht die Folgen dieser Konzeption (der asymmetrischen Verschneidung von Listen und Paaren) auch im Python-Code. List und Pair erben von EmptyList über den Zwischenschritt von Shared. Ergo kennen beide die Operation is_empty(). Tatsächlich ist ein is_empty() für Pairs vollkommen überflüssig, da die Anfrage an den falschen Typen adressiert wird. Ein Pair kann niemals empty sein! Genauso wenig, wie eine Zahl jemals empty sein kann.

Ich finde es verwunderlich, dass man bei List, Pair und EmptyList im Grunde kein konsistentes OO-Typgebäude errichten kann, was dem "gefühlten" Zusammenhang von Pair, List und EmptyList gerecht wird _und_ offen bleibt für Erweiterungen.

Montag, Juli 07, 2008

17 Fragen

Marc Scheloske, der Betreiber des Wissenschafts-Cafes, hat mit mir ein Interview geführt. Marc macht diese Interviews seit einiger Zeit mit den unterschiedlichsten Bloggern und stellt seinen Interview-Partnern 17 Fragen. Viel Spaß beim Lesen! Und halten Sie sich mal eine Weile im Wissenschafts-Cafe auf, ich könnte mir vorstellen, dass es Ihnen dort gefällt!