In meinem Blogeintrag "Hochstapelei" habe ich Ihnen gezeigt, wie sich rein mit den Mitteln der Objekt-Orientierung ein Stack realisieren lässt. Zur Konstruktion eines solchen Datentyps reicht es vollkommen aus, mit Konstruktoren, Methoden, Attributen und der Möglichkeit des Vergleichs von Objekten zu arbeiten. Keine sonstigen eingebauten Operationen, kein weiterer Datentyp (außer Bool) ist nötig.
Auf die gleiche Weise lassen sich auch die natürlichen Zahlen inklusive Null als Typ einführen. Das Geheimnis liegt wieder in der Nutzung des Konstruktors verborgen; das Beispiel ist in Python umgesetzt. Wir machen uns eine Zahlendarstellung zu nutze, die ihren Ursprung in der Mathematik hat: Ausgehend von der Zahl Null ist jede andere Zahl ein Nachfolger von Null. Eine Rangordnung wird hergestellt durch eine Nachfolgekette. Wir nennen den direkten Nachfolger von Null "Eins", den Nachfolger von Eins "Zwei" usw. Ein Nachfolger einer Zahl wird durch die Methode "inc" (inkrementiere) generiert. Der Vorgänger einer Zahl kann mit der Methode "dec" (dekrementiere) ermittelt werden. Eine Zahl heißt "Null", wenn sie keinen Vorgänger hat.
Eine wichtige Methode, die nicht fehlen sollte, überprüft die Gleichheit von zwei Zahlen. Zwei Zahlen sind dann gleich, wenn Sie die gleiche Anzahl von Vorgängern haben. Das Konzept der "Anzahl" ist jedoch nicht zugreifbar, da wir just dabei sind Zahlen zu definieren. Doch es gibt einen kleinen Kniff, der uns das Problem löst: Rekursion. Wir dekrementieren die zu vergleichenden Zahlen gemeinsam so lange, bis entweder beide Zahlen Null sind oder nur eine Zahl Null ergibt. Im ersten Fall (beide Zahlen sind Null) wissen wir, dass die Zahlen gleich sein müssen; ist nur eine Zahl Null, liegt Ungleichheit vor.
Aus praktischen Gründen überschreiben wir die Gleichheitsmethode "__eq__" von Python, um den Vergleichsoperator "==" einsetzen zu können.
Einem erfahrenen Python-Programmierer wird im ersten Code-Fragment aufgefallen sein, dass ich "self.predecessor" nicht direkt mit None vergleiche, sondern den vielleicht etwas umständlich anmutenden Umweg über "isinstance" gehe. Grund ist die "__eq__"-Methode. Ich kann keine Number mit None vergleichen, ohne den Aufruf von "__eq__" zu provozieren. Dort will ich aber nur einen Vergleich zweier Zahlen implementieren, nicht den Vergleich mit None.
Eine weitere Methode setzt den plus-Operator um. Die "__repr__"-Methode gibt eine geeignete Repräsentation eines Number-Objekts aus.
Wenn Sie ein wenig Zahlenspielerei mögen, dann tippern Sie doch auf der Console zum Beispiel Folgendes ein:
Beschleicht Sie übrigens so ein komisches Gefühl? Sind das nicht komische Zahlen, die sich über die Idee der Nachfolge realisieren? Ist das nicht Kindergarten-Arithmetik, die Addition (plus) auf so eine alberne "Nimm weg, gib woanders dazu"-Art zu definieren?
Lassen Sie sich von der Einfachheit und der Speicherineffizienz nicht täuschen. Die Verwendung von z.B. Binärzahlen ist lediglich eine speichereffiziente Ablage einer Zahl. Auch die binäre Addition (0+0=0, 0+1=1, 1+0=1, 1+1=0 mit einem Übertrag von 1) kann man als optimierten Algorithmus für die binäre Zahlendarstellung verstehen.
Auf die gleiche Weise lassen sich auch die natürlichen Zahlen inklusive Null als Typ einführen. Das Geheimnis liegt wieder in der Nutzung des Konstruktors verborgen; das Beispiel ist in Python umgesetzt. Wir machen uns eine Zahlendarstellung zu nutze, die ihren Ursprung in der Mathematik hat: Ausgehend von der Zahl Null ist jede andere Zahl ein Nachfolger von Null. Eine Rangordnung wird hergestellt durch eine Nachfolgekette. Wir nennen den direkten Nachfolger von Null "Eins", den Nachfolger von Eins "Zwei" usw. Ein Nachfolger einer Zahl wird durch die Methode "inc" (inkrementiere) generiert. Der Vorgänger einer Zahl kann mit der Methode "dec" (dekrementiere) ermittelt werden. Eine Zahl heißt "Null", wenn sie keinen Vorgänger hat.
class Number(object):
def __init__(self,predecessor=None):
assert isinstance(predecessor,type(None)) or \
isinstance(predecessor,type(self))
self.predecessor = predecessor
def is_zero(self):
return isinstance(self.predecessor,type(None))
def inc(self):
return Number(self)
def dec(self):
assert not isinstance(self.predecessor,type(None)),\
"Number is not zero"
return self.predecessor
Eine wichtige Methode, die nicht fehlen sollte, überprüft die Gleichheit von zwei Zahlen. Zwei Zahlen sind dann gleich, wenn Sie die gleiche Anzahl von Vorgängern haben. Das Konzept der "Anzahl" ist jedoch nicht zugreifbar, da wir just dabei sind Zahlen zu definieren. Doch es gibt einen kleinen Kniff, der uns das Problem löst: Rekursion. Wir dekrementieren die zu vergleichenden Zahlen gemeinsam so lange, bis entweder beide Zahlen Null sind oder nur eine Zahl Null ergibt. Im ersten Fall (beide Zahlen sind Null) wissen wir, dass die Zahlen gleich sein müssen; ist nur eine Zahl Null, liegt Ungleichheit vor.
Aus praktischen Gründen überschreiben wir die Gleichheitsmethode "__eq__" von Python, um den Vergleichsoperator "==" einsetzen zu können.
def __eq__(self,number):
assert isinstance(number,type(self))
if self.is_zero() and number.is_zero(): return True
if self.is_zero() or number.is_zero(): return False
return self.dec().__eq__(number.dec())
Einem erfahrenen Python-Programmierer wird im ersten Code-Fragment aufgefallen sein, dass ich "self.predecessor" nicht direkt mit None vergleiche, sondern den vielleicht etwas umständlich anmutenden Umweg über "isinstance" gehe. Grund ist die "__eq__"-Methode. Ich kann keine Number mit None vergleichen, ohne den Aufruf von "__eq__" zu provozieren. Dort will ich aber nur einen Vergleich zweier Zahlen implementieren, nicht den Vergleich mit None.
Eine weitere Methode setzt den plus-Operator um. Die "__repr__"-Methode gibt eine geeignete Repräsentation eines Number-Objekts aus.
def plus(self,number):
assert isinstance(number,type(self))
if number.is_zero(): return self
return self.inc().plus(number.dec())
def __repr__(self):
if self.is_zero(): return "0"
return "1+%s" % self.predecessor
Wenn Sie ein wenig Zahlenspielerei mögen, dann tippern Sie doch auf der Console zum Beispiel Folgendes ein:
>>> zero = Number()
>>> zero
0
>>> one = zero.inc()
>>> one
1+0
>>> two = one.inc()
>>> one == Number(Number())
True
>>> one == Number().inc()
True
>>> three = one.plus(two)
>>> three
1+1+1+0
>>> five = three.plus(Number().inc().inc())
>>> five
1+1+1+1+1+0
>>> five.dec()
1+1+1+1+0
Beschleicht Sie übrigens so ein komisches Gefühl? Sind das nicht komische Zahlen, die sich über die Idee der Nachfolge realisieren? Ist das nicht Kindergarten-Arithmetik, die Addition (plus) auf so eine alberne "Nimm weg, gib woanders dazu"-Art zu definieren?
Lassen Sie sich von der Einfachheit und der Speicherineffizienz nicht täuschen. Die Verwendung von z.B. Binärzahlen ist lediglich eine speichereffiziente Ablage einer Zahl. Auch die binäre Addition (0+0=0, 0+1=1, 1+0=1, 1+1=0 mit einem Übertrag von 1) kann man als optimierten Algorithmus für die binäre Zahlendarstellung verstehen.