Freitag, April 27, 2007

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.

Freitag, April 13, 2007

Breakpoint mit Farbrausch

Haben Sie auch schon von "Breakpoint 2007" gehört? Vorgestern machte mich Herr Arz auf die Meldung bei golem aufmerksam ("Breakpoint 2007 - Gewinner der Demo-Party stehen fest", 11. April 2007). Das Team "Farbrausch" hat im Bereich "PC-Demo" den Titel geholt. Aus einer gerade mal 180 KByte großen ausführbaren Datei entzaubert "Farbrausch" einen 7minütigen Film -- mir verschlägt sowas den Atem. Ich habe mir das Video auf YouTube angeschaut. Es wirkt fast wie Hexerei!

Machen wir einmal sehr ungünstige Annahmen, was die Bildqualität betrifft: 320 x 200 Bildpunkten mit 8 Bit für die Farbkodierung und 15 Frames pro Sekunde (fps). Das macht für einen etwa 7minütigen Beitrag (7 x 60 Sekunden = 420 Sekunden) eine Datenmenge von 3.225.600.000 Bits aus, sprich 403.200.000 Bytes, also ungefähr 400 MB. Das File kommt jedoch nur mit ca. 180 KB daher! Dem entspricht eine Kompressionsrate um den Faktor 2000 (400/0,18). Ein Kompressionsstandard wie MPEG-2 komprimiert um den Faktor 10-20. Es liegen Welten zwischen 2000 und 20!

Diese Zahlen sollen Ihnen nur ein Gefühl dafür geben, dass hier wahrhafte Künstler ("Hacker" im guten Sinne des Wortes) am Werk sind. Ich habe absichtlich schlechte Annahmen gemacht, der Film von "Farbrausch" ist qualitativ wesentlich hochwertiger. In den 180 KB steckt nicht nur eine Graphik-Engine, auch die "Filmwelt" muss sehr spärlich kodiert sein, die zum Teil mit recht aufwendigen Vorberechnungen erst einmal erstellt werden muss, bevor ein Video ablaufen kann. Sie werden vermutlich einiges an Rechenpower benötigen, damit die 180 KB vernünftig laufen. Und die Audio-Spur habe ich gänzlich vernachlässigt.

Was Sie daraus noch lernen können, und das ist vielleicht als Software-Engineer gar nicht so uninteressant: Ein normaler Kompressionsalgorithmus wie MPEG-2 ist zwar bereits ein Algorithmus für eine besondere Art von Datenmaterial, er arbeitet aber mit recht generellen Techniken zur Kompression von Bildflächen. Was die Hacker da treiben, ist nur zu erreichen mit einer domänenspezifischen Kodierung einer "Filmwelt" -- einer Sprache, wenn Sie so wollen. Mit dieser Spezialsprache ist eine Kompaktheit zu erreichen, die ansonsten undenkbar ist. Domänenspezifische Sprachen haben in der Tat ihren Platz und ihren Sinn. Mit ihnen sind solche Hexereien zu bewerkstelligen.

Dienstag, April 10, 2007

Design by Contract in Practice

Design by Contract (DbC) is a very valuable specification technique -- I already posted about it in German (Netze spannen mit Design by Contract). However, you should be aware that DbC also tends to complicate matters if state is involved. In this case, we need a complementing approach.

To give you a simple example, have a look at a thing called "Account". The "Account" is purely specified via pre- and post-conditions (require and ensure); "context" enables you to capture a context required for a subsequent post-condition. The code is written in a syntax close to Python. A contract precedes the method signature.

class Account(object):
ensure: self.balance == 0
def __init__(self)

require: 0 < amount <= self.balance
context: balance = self.balance
ensure: self.balance == balance - amount
def withdraw(self,amount)

require: amount > 0
context: balance = self.balance
ensure: self.balance == balance + amount
def deposit(self,amount)

context: balance = self.balance
ensure: res == balance
def query(self)

The very first "ensure" specifies that an implementation provides a state preserving instance variable called “self.balance” and that its value is set to 0. The way to specify changes in state (here "self.balance") is shown in "withdraw" and "deposit". If there are no changes in state, "query" gives an example of that.

Now let us add an implementation fulfilling the contracts. It's quite straight forward.

class Account(object):
ensure: self.balance == 0
def __init__(self):
self.balance = 0

require: 0 < amount <= self.balance
context: balance = self.balance
ensure: self.balance == balance - amount
def withdraw(self,amount):
self.balance -= amount

require: amount > 0
context: balance = self.balance
ensure: self.balance == balance + amount
def deposit(self,amount):
self.balance += amount

context: balance = self.balance
ensure: res == balance
def query(self):
return self.balance

Something is weird here: The implementation (4 lines) looks just like a reformulation of the “context” and “ensure” blocks (7 lines). In addition, the implementation is much more easier to grasp and to understand. No doubt, the contracts are way too heavy compared to the implementation. We could easily condense our specification if the implementation is regarded as part of the specification.

class Account(object):
def __init__(self):
self.balance = 0

require: 0 < amount <= self.balance
def withdraw(self,amount):
self.balance -= amount

require: amount > 0
def deposit(self,amount):
self.balance += amount

def query(self):
return self.balance

That's easy and lightweight, isn't it?

Things have become much more simpler, the code is definitely easier to read and to grasp. But is this still a specification? Yes, but the viewpoint has changed. Design by Contract is a technique, which tells you, whether an implementation fulfills the contracts or not. DbC cannot generate answers for you, it can just verify if your answer (an implementation) is valid or not. This is somewhat impractical if a state space needs to be maintained for DbC to verify an implementation; in some sense you’re doing double work. In a purist approach you would maintain independent state spaces: one for specification purposes and another for the implementation. An alternative style is to create an executable specification, which lets you experience the right answers by trying it out. It’s a way to show, what withdrawal, deposition etc. actually do, so that you can understand their behavior. In our example, we mixed both styles, taking advantage of each style, where it fits best.

If you write your code this way, you are coding a specification, which is executable. And that’s quite some fun. The risk is that you start to mix in implementation issues with an eye on performance, optimizations etc. You shouldn’t. You are writing a specification using your favorite programming language. That's it! No more, no less.

Donnerstag, April 05, 2007

Von Beruf Software Engineer

Na, was glauben Sie, wie Ihr Beruf als Software Engineer in 10, 20 Jahren aussehen wird? Zu Beginn des Wintersemesters 2006 habe ich meine Studierenden im Hauptstudium befragt, wie sie die Zukunft des Software Engineering in 10 Jahren sehen. Folgende Liste kam dabei heraus:

  • mehr Konzeption von Software: Anforderungen, Modellierung

  • Software aus Komponenten “zusammenstecken”, Code-Generierung

  • mehr Planung und Organisation von Software-Projekten

  • viel Planung und Kommunikation mit Kunden

  • Hohe Qualitätssicherung bei Outsourcing der Programmierung

  • Teamarbeit: internationale, verteilte Arbeit und Kommunikation

  • Pflege, Weiterentwicklung, Optimierung von Altsystemen

  • sicherer Arbeitsplatz: es entsteht immer mehr Software => Wartung

  • neue Technologien, da HW immer leistungsfähiger wird

  • Entwicklung mit leistungsfähigen CASE-Werkzeugen und IDEs

  • Fortschritte in HMI, Webtechnologie, KI, Virtual Reality, …

  • Notwendigkeit ständiger Weiterbildung

  • es wird eine neue Programmiersprache geben => weniger Fehler

  • Agile Softwareentwicklung als Standard


Eine interessante Liste, nicht wahr? Andere interessante Gedanken hat sich Hans Beck in Telepolis gemacht. Er geht davon aus, dass Software-Entwickler es lernen müssen, sich in abstrakten (Denk-)Welten zu bewegen ("Von der Notwendigkeit, sich in abstrakten Welten bewegen zu können", 28. März 2007). Ein, wie ich glaube, lesenswerter Artikel.


--
P.S.: Da nicht jeder mit den Abkürzungen oben vertraut ist: HW (Hardware), CASE (Computer Aided Software Engineering), IDE (Integrated Development Environment), HMI (Human Machine Interface), KI (Künstliche Intelligenz)