Freitag, Dezember 22, 2006

Karl-Steinbuch-Stipendium

Wenn Sie sich in Ihrer Freizeit mit interessanten Informatik-Projekten und -Ideen befassen, haben Sie (als Student bzw. Studentin in Baden-Württemberg) schon einmal darüber nachgedacht, sich Ihr Engagement fördern zu lassen? Denken Sie doch einmal darüber nach, ob es Sinn für Sie macht, sich um ein Stipendium zu bewerben. Aktuell (und immer wieder aktuell) ist die Ausschreibung des Karl-Steinbuch-Stipendiums.

Dienstag, Dezember 12, 2006

Constraint Programming

In der letzten Zeit habe ich mich ein wenig mit einer möglichen Umsetzung des UML-Reasoner beschäftigt. Um ein Gefühl für den "Artenreichtum" eines Klassendiagramms auf der Objektebene (der Instanzebene) zu bekommen, spielte ich ein wenig rum. Zwei Klassen und eine eingerichtete Assoziation bildeten meine Ausgangsbasis. Maximal fünf Instanzen zu jeder Klasse sollte es geben. Ich schrieb mir einfache Routinen, die mir aus zwei Mengen ({a1, a2, a3, ...} und {b1, b2, b3, ...}) mit je fünf Elementen alle möglichen Relationen von der einen zur anderen Menge erzeugten -- unter jeweils unterschiedlichen Annahmen. Beispielsweise kann man das Paar (a1,b1) als gleichwertig mit (a2,b2) betrachten. Schließlich geht es ja nur um den Link von einer Instanz aus der ersten Menge zu einer Instanz aus der zweiten Menge. Man kann jedoch auch anders argumentieren, wenn man Instanz-Relationen über die Zeit betrachtet. Dann kann (a1,b1) die Folge einer anderen Konstellation sein als (a2,b2) und auch eine andere Fortsetzung finden. Wirklich? Bisweilen verstieg ich mich in haarigen Argumentationsketten.

Wie auch immer, eines wurde mir klar: Je nach Annahme explodiert mein Raum an Möglichkeiten enorm und nimmt fast erschreckende Ausmaße an. Wie soll da noch in sinnvoller Zeit der ganze Raum an Möglichkeiten generiert und auf Design-Beschränkungen überprüft werden. Gibt es einen anderen Ansatz?

Ich wandte mich Prolog zu, einer logischen Programmiersprache. Aber irgendwie überzeugte mich das nicht. Prolog geht ähnlich vor: es wird der gesamte Suchraum generiert und dann werden logische Beschränkungen überprüft. Das ist der so genannte "generate and test"-Ansatz. Damit kommt man auch nicht weiter.

Also begann ich Constraint Programming zu studieren, der nächste, naheliegende Ansatz. Es gibt dazu ein erfreulich dünnes und gutes Buch von Thom Frühwirth und Slim Abdennadher, "Essentials of Constraint Programming" (Springer, 2003) mit dem man sich innerhalb von ein, zwei Stunden in das Thema einarbeiten kann, vorausgesetzt man überspringt die Mathematik. Constraint Programming arbeitet nach der "constraint and generate"-Methodik. Der Ansatz ist sehr schön beschrieben in dem Buch "Concepts, Techniques, and Models of Computer Programming" von Peter Van Roy und Seif Haridi (MIT Press, 2004) -- das nächste Buch, das ich zu Rate zog. Sie können das mit der Programmiersprache Oz mit Hilfe von Mozart auch selber ausprobieren. Das Buch von Roy und Haridi basiert auf Oz.

Um Constraint Programming (CP) zu betreiben brauchen Sie jedoch keine spezielle Programmiersprache. Im Grunde kann CP als Bibliothek "nachgeladen" werden, sofern eine solche Bibliothek für Ihre Programmiersprache verfügbar ist. Es geht aber auch gänzlich ohne Bibliothek, wenn man das Prinzip verstanden hat. Per Zufall bin ich auf einen Artikel von Peter Norvig (übrigens Director of Research bei Google) gestoßen, der die Idee des Constraint Programming mit dem Wechselspiel aus Constraint Propagation and Search am Beispiel eines Sudoku-Lösers demonstriert; siehe "Solving Every Sudoku Puzzle". Der Code ist in Python geschrieben, verblüffend kurz und erweist sich als effizient für selbst "schwere" Sudokus.

Wenn Sie sich durch das Norvig-Beispiel gearbeitet haben, erahnen Sie es vielleicht auch: Ich glaube, hier ist der Schlüssel zu einer praktikablen Umsetzung des UML-Reasoners verborgen.

Donnerstag, Dezember 07, 2006

Inversion of Control

Did you every try to implement an interpreter for the Scheme programming language yourself? I enjoyed it a lot -- and still enjoy it, since I haven't finished my little Scheme project yet. It is a lot of fun to implement Scheme in Scheme, but I use Python in order to make sure I understand each and every bit of the Scheme language. While a basic Scheme implementation is easy to realize, a more advanced implementation supporting so-called continuations is a nice challenge. First you have to understand the concept of continuations, which is quite a challenge in its own. Second, you need to have an idea how to make them happen in your host language.

Just to give you a rough idea: In Scheme, you get a sort of read and restore access to the current state of the computational process. There is a special procedure in Scheme, which you can use anywhere in a Scheme program; the procedure is called "call with current continuation" ("call/cc" for short) -- but that's not so important here. When executed, this special procedure saves the current state of the computational process and packages this information within something called a continuation. A continuation is a first-class entity in Scheme; you can pass it around and store. Once a continuation gets called, the state of the computational process stored within the continuation is restored. Simply speaking, program execution continues at exactly that point, where the continuation was created. To give you an analogy, think of exceptions as you know them from other programming languages. When you "try" something, the "except" clause restores the computational state of affairs in case an exception is thrown, no matter when and where deeper down in the call chain the exception is raised. Unfortunately, exceptions are functionally weaker than continuations are. You can build an exception system with continuations, but not the other way around. You cannot store an exception, raise it outside the calling context of a "try" and throw it again later on. That's the kind of thing you can do with continuations. Exceptions are a poor man's continuations.

Besides Scheme, there are only some few languages, which natively support continuations. Among those is Ruby. In most cases however, you are left without any support for continuations -- and that's not too bad. It forces you to really understand what continuations are and how to implement them. That's the situation I was faced with.

If you do not have full control over the computational process, as is needed for an implementation of continuations, you have to think of a way to regain execution control. What you end up with is either writing a compiler, which transforms Scheme programs into a form called Continuation Passing Style (CPS), or you write an interpreter maintaining its own call stack. The call stack represents the state of the computational process. Having access to the call stack is key for an implementation of continuations. The current continuation is the current situation of the call stack.

I opted for writing an interpreter. In the following, I will show you the way how I did this with Python. But before you hesitate to read on: You do not need to know or understand Scheme. What I'm after in this post is not Scheme; it's the way how to regain execution control. Scheme and the implementation of continuations is just one motivating example. I'll give you more examples later on; examples, which are relevant for anybody with an interest in software design.

For setting the scene, I need to tell you something about a cool feature in Python, namely generators. A generator looks like a regular function definition. As you know from other languages, a "return" statement within a function terminates execution of the function and possibly returns some data. Within a generator definition you do not use "return" statements. Instead, you use "yield" statements much like return statements, but a "yield" works differently. A "yield" returns data but it does not terminate the generator. The execution state of the generator is preserved and execution can be resumed later on. (Sounds like another poor man's continuations, eh?!) To give you an example, here is an extract of an interactive Python session:


>>> def countdown():
... yield 2
... yield 1
... yield 0
...


If try to call this function, it won't work as you might expect. It doesn't return a 2 or something like that. A generator object is returned instead.


>>> countdown()



With the generator object you can iteratively step from one "yield" statement to the next via the generator's "next()"-method, get some value back from the "yield" statement and, later on, resume execution where it left-off.


>>> cd = countdown()
>>> cd.next()
2
>>> cd.next()
1
>>> cd.next()
0
>>> cd.next()
Traceback (most recent call last):
File "", line 1, in
StopIteration
>>>


The exception "StopIteration" indicates that the generator is done. Generators support the same protocol as Iterators do. So, a generator can be used within a "for" statement. Creating the generator object, calling "next()" and exiting when StopIteration is raised, all this is done automagically for you in the background.


>>> for i in countdown(): print i
...
2
1
0


A more flexible definition of countdown could look like this:


>>> def countdown(n):
... assert n >= 0
... while n >= 0:
... yield n
... n = n - 1
...


I think that you get the basic idea. With "yield", a "function" (actually a generator) can return control to the caller of the "function" at any time on appearance of a "yield" statement. A "function" does not need to finish its computation before it can return something.

In my Scheme interpreter I use generators to return control, whenever the evaluator of a basic Scheme expression needs to call the evaluator of another Scheme expression. Instead of doing something like this (what you would conventionally do) ...


def do_something(n):
result = do_something_else(n)
return result


... I do that, a slight modification to the code in order to return control, whenever I call another function.


def do_something():
result = (yield do_something_else,n)
yield result


Got it? Control is returned to the caller of "do_something". The generator hands over the method object and the arguments to the caller. Now, it is up to the caller to call "do_something_else" on behalf of "do_something". After that the result of "do_something_else" is sent into the generator and the generator proceeds. Just to give you an insight how I use this technique for my Scheme interpreter, here is a code snippet without further comment.


class If(object):
def __init__(self,test,consequent,alternate=None):
self.test = test
self.consequent = consequent
self.alternate = alternate

def eval(self,env):
if (yield Command(eval,self.test,env)) != False:
yield Command(eval,self.consequent,env)
elif self.alternate:
yield Command(eval,self.alternate,env)

def __repr__(self):
repr = "(if %s %s)" % (self.test,self.consequent)
return self.alternate and (repr[:-1]+" %s)" \
% self.alternate) or repr


The overall pattern behind this approach is Inversion of Control (IoC): Delegate method calls to a centralized instance (in this case I used "yield" statements for that purpose) so that this instance gets full control over who is when to call next.

By the way, I don't feel comfortable calling Inversion of Control a pattern. It's not that easy to boil IoC down. It cannot be captured by a simple code template. I would say it's a meta-pattern or a design principle. There are other techniques to achieve IoC. Metaprogramming is one example.

Whatever you call it, Inversion of Control is a very powerful thing. IoC is about getting control over the flow of execution. You can use it to achieve quite fancy things. It might be the basis for an architectural infrastructure. Let me give you some examples.

Suppose you do not want to use threads, since there is some cost penalty associated to them. You choose to go for cooperative multithreading. What is cooperative multithreading about? The basic idea is that only one task of multiple concurrent tasks actually gets the control thread. The task returns control on own initiative back to a dispatcher and scheduler. That's why it is called "cooperative": Each task is assumed to give control back as soon as possible, so that other tasks on the scheduler's list can continue. Guess how one could implement this? With the help of generators using the technique I just showed you.

Another example: Your language does not support pre- and post-conditions (see my post about "Netze spannen mit Design by Contract"). Again, use Inversion of Control. It's up to the controller to call a method. Before calling a method, the controller just needs to check if there is a method registered representing the pre-condition and call it beforehand. Similarly, the method representing the post-condition is called after the main method. By the way, you can use this to add aspect-orientation to your system!

A final example: Suppose that you want to monitor a certain component in your system. You are interested in all methods calls going out and coming in. Since the interaction with the environment is complex, you log all method calls and the results they return. You record everything. Now, you can remove the environment and let the component re-run a certain scenario. The controller can now "replay" the recorded reactions and stimuli of the environment. Thereby, you can test and debug your component under test in isolation.

This was a rather long post. But I hope that you now understand that without Inversion of Control, there is something very valuable missing in your toolbox. Inversion of Control is an important structuring technique of your code. Some projects make heavily use of this principle (see e.g. Apache Excalibur). It is one of this magic techniques, wizards use ;-)

Sonntag, Dezember 03, 2006

Haskell-Kurs

Haskell ist eine moderne, funktionale Programmiersprache mit vielen interessanten Features wie z.B. Pattern Matching, Currying und Lazy Evaluation. Mark C. Chu-Carroll hat auf seinem Blog "Good Math, Bad Math" einen Haskell-Kurs begonnen, den ich jedem nur empfehlen kann, der sich für Programmiersprachen jenseits von Java, C#, PHP, Python, Ruby, Perl und anderen (also all jenen, die als imperative Sprachen bezeichnet werden) interessiert. Ich bin schon sehr gespannt darauf, wenn Mark uns Monaden erklären wird und was für ihn die "Leim"-Qualität von Haskell ausmacht.

Dienstag, November 28, 2006

Ajax und Usability

AJAX (Asynchronous JavaScript + XML) ist im Grunde nichts anderes als eine Agenten-Technologie: Sie delegieren einige Aufgaben an ihn, den Agenten (ein JavaScript-Programm) -- und dabei kommen erstaunliche Dinge heraus, wie die vielen neuen Webseiten belegen, die das ausmachen, was man heute das "Web 2.0" nennt.

Früher, in der guten alten Zeit, da war das Web noch das, wofür es einmal geplant war: ein Netz von aufeinander verweisenden Textseiten, ein sogenannter Hypertext. Diese Grundidee bestimmt in Form des HyperText Transfer Protocols (HTTP) bis heute die Architektur des World Wide Webs. Auf die Auswahl eines solchen Verweises (Klick) sendet Ihr Browser eine HTTP-Anfrage (request) an einen Server, der irgendwo in den Weiten des Webs seinen Dienst tut. Der Server beantwortet die Anfrage mit einer HTTP-Antwort (reply), die den neuen "Text" enthält.

Seit einigen Jahren sind die Browser mit einer neuen Fähigkeit ausgestattet: man kann sie Programme, genauer: JavaScript-Programme, ausführen lassen. Damit kann ein Server ein Programm an einen Browser übertragen -- einen Agenten. Der Agent übernimmt jetzt Aufgaben, die er still und leise im Hintergrund ausführt. Er kann weiterhin HTTP-Anfragen hinausschicken, auch wenn Sie nichts tun. Er kann z.B. nachfragen, ob es neue Informationen beim Server gibt, die er Ihnen anzeigen soll.

Das JavaScript-Programm hat zudem Zugriff auf die gesamte an den Browser übertragene Information, und es kann diese Information aktiv verändern. Damit sind ganz neue Effekte möglich. Z.B. erscheint plötzlich eine Nachricht vom Server in Ihrem Browserfenster, obwohl Sie selber gar nichts gemacht haben. Der Agent war fleißig und hat für Sie g'schafft.

Vor zwei Wochen war ich auf dem World Usability Day (WUD) in Stuttgart. Dort war das Web 2.0 ein ganz großes Thema und fand enormen Zulauf. Es ist eine interessante Frage, wie es um die Benutzerfreundlichkeit und Barrierefreiheit von Web 2.0-Anwendungen bestellt ist. AJAX-Technologie erlaubt es, den Anwender beim Surfen so gut zu beobachten, wie nie zuvor. Jede Mausbewegung, jeder Klick, die dazwischen verbrauchte Zeit, all das ist erfassbar und kann zu Zwecken der Usability unmittelbar ausgewertet werden. Und gegebenenfalls können Änderungen sofort vorgenommen werden. Ein Vorteil, den Desktop-Anwendungen nicht haben. AJAX befreit auch von alten und lieb gewordenen Vorstellungen, wie Menüs, Bedienungsführung etc. auszusehen haben. Ein Blick auf eine beliebige Web 2.0-Anwendung zeigt, wie freudig hier experimentiert wird. Jede Seite sieht anders aus und überrascht mit neuen Ideen und Effekten. Desktop-Anwendungen haben sich in Aussehen und Art der Bedienung weitgehend aneinander angeglichen. Man geht mit festen Erwartungen z.B. an die Menüstruktur heran. Beim Web 2.0 ist alles anders.

Aus dieser Sicht habe ich ein paar Thesen zur Usability von AJAX-basierten Webanwendungen formuliert:
  • Das Web 2.0: Das größte Usability-Experiment der Welt
  • Das Web 3.0: Die Ära einer "neuen" Usability
  • Usability bestimmt wesentlich den Erfolg zukünftiger Angebote
  • Desktop-Anwendungen werden sich neu definieren müssen
  • Der Preis: Der gläserne Anwender bzw. die gläserne Anwenderin
Aber das ist nur eine Sicht auf das Thema. Einen Satz noch interessanterer Thesen finden Sie hier.

Mittwoch, November 22, 2006

Das will ich auch zu Weihnachten haben!

Gucken und staunen, schmunzeln und sich fragen, warum man das nicht längst schon selber programmiert hat ...

http://scienceblogs.com/mixingmemory/2006/11/this_is_what_i_want_for_christ.php

A Lesson to Learn from Compiler Construction

Some few days ago, I was struck by an insight. This insight concerned a certain way of structuring a software problem in order to reduce complexity. I realized that I used this pattern subconsciously for quite some time. However, I wasn't really aware of it until I had a discussion with one of my diploma students end of 2005. We had a discussion about the component framework he was supposed to built. I was bubbling over with ideas -- and the diploma student became more and more frightened about all these features, I was so enthusiastic about. Neither did he comprehend what I was after, nor did he see the slightest chance to get all this implemented. Suddenly, it occurred to me that there was a way out of this complexity: "Gosh, why do I torture this poor guy with all my ideas. What I'm really after is something much more simpler. If I break things down, I just need some core functions implemented, which make up the basic component framework and let it run. The rest, my fancy features, can be understood as a way of use of this simple component framework."

As it turned out, the simple component framework consists of the notion of a component, which can be composed of other components, communication channels between components and that's it, basically. The more complex component framework, which I originally had in my mind, has some nice "add-ons": two-way interfaces called ports, communication channels to model distribution called complex connectors, typed ports, stuff like that. (It's an extended version of the ROOM language, the Real-Time Object-Oriented Modeling language. Some of its concepts made it into the UML 2.0 standard.)

While the simple component framework is relatively easy to built, the more advanced component framework is not built at all. Instead, the conceptions of the advanced framework and their allowed combination of use are defined by a configuration format. The format sets the rules, what kind of arrangements are allowed, and enforces contextual consistency. It's a declarative approach. A concrete configuration describes a setup according to the rules and conventions. For example, two ports can be connected by a connector only if the associated communication protocols match.

The point is that this configuration can be translated into a configuration of the "simple" component framework. Ports and complex connectors, for example, can be mapped to components of the simple component framework. Of course, ports and complex connectors are not equal to components, otherwise you wouldn't have come up with these conceptions in the advanced component framework. There is semantics attached to these concepts! A port serves a certain purpose, it's a kind of interface, whereas a component is just a component. The purpose of a simple component is just to do what its behavioral specification promises to do. In this sense, you are allowed to do whatever you want to do with a component. A port, however, must be used in connection with a "hosting" component. A port is to be used in a certain way for a certain purpose, which makes up its semantics. The key issue to understand is that ports (and complex connectors as well) can be mapped to components for the purpose of execution! But there is a price to be paid: the loss of semantics within the simple component framework. To compensate this loss of semantics, one could allow to annotate components in the simple component framework with meta-information. This is also a very helpful technique in order to trace debug information back to its source in the advanced component framework.

What I explained here is a clear cut between a simple operational level and a more complex configurational level. This directs the resolution of complexity to different levels. If you think about it for some time, you might notice that this technique is used e.g. in compiler construction. Java is a configuration schema enforcing certain rules and conventions. Classes, methods, attributes and so on serve a certain purpose. But they are all translated to a very basic level of commands, a ByteCode format, which can be executed by a virtual machinery, the Java Virtual Machine.

After I have written all this down, I ask myself: What the heck was the reason I was struck by an insight? Am I stupid? Isn't all this obvious? It is, if you design a compiler for a language. But sometimes, when you approach a problem from a different angle, not having language design issues in mind, you might overlook this. I read a book about ROOM, which discusses implementation issues of the ROOM component language in quite detail. But while didactically excellent, it uses a more complicated approach, which didn't let me realize that there is another road down the hill. Luckily, now I'm enlightened! ;-)

Montag, November 20, 2006

Der Mensch als Subroutine

Computerprogramme "borgen" sich die Intelligenz eines Menschen für "Unteraufgaben", die Menschen (noch) weitaus besser lösen können als der Computer. Darüber las ich in dem Post "Hijacking intelligence". Faszinierender Ansatz, nicht wahr? Dabei ist das schon Realität geworden. In dem weiterführenden Link las ich zum ersten Mal etwas über Amazon's Mechanical Turk.

Montag, November 13, 2006

The Meta-Model of the UML


Modeling languages, like the Unified Modeling Language (UML), are designed according to a schema called meta-level architecture (aka meta-data architecture). While the term may sound mystik, meta-level architectures are actually not that difficult to understand.

Let us have a closer look at the architecture of meta-levels on an informal level. We will start at the top left, see the figure. To make the discussion concrete, we refer to conceptions as you know them from modeling with classes and objects. The abbreviation CD stands for Class Diagram. A class diagram consists of classes, associations, inheritance and so on. These conceptions, the conceptions you are allowed to use for a CD are defined by CM, the Class Model, as we call it. The CM is a specification of conceptions, of which a concrete CD is an instance of. That's why there is an arrow labeled with "instanceOf" between CD and CM. The Class Meta-Model (CMM) specifies the language constructs available for use on CM. In other words, the CM is one concrete specification of a modeling language, whose specification concepts are defined by CMM. In that sense, CM is an instance of CMM. All this is pretty straight forward and not in conflict with the common understanding of meta-level architectures.

However, and this is often overlooked, the same argumentation holds on the row below. An Object Diagram (OD) consists of objects, values, references etc. These conceptions are defined by the Object Model (OM). The Object Meta-Model (OMM) specifies the language constructs available for use on OM. Again, this is pretty straight and clear. Now comes the interesting part.

Of course, the world of classes and the world of objects are somehow interconnected. This interconnection is defined through a relationship between the Class Model (CM) and the Object Model (OM). This relationship determines how OD and CD are related. Objects are instances of classes, meaning that a certain class is the input to a factory, which "produces" an object, whose type property is a pointer to the class and whose values are data stores including pointers to the class attributes. That is what we call an "instanceOf" relationship. This relationship is defined by the OM/CM arrow.

The means to describe an interconnection between OM and CM is defined by the arrow between OMM and CMM. Otherwise, one could only describe self-contained models of OM and CM, but not interrelate these models, which -- in turn -- would prevent to specify the "instanceOf" relationship between OD and CD. As one can observe, the reasoning is absolutely "symmetric".

Now, let's do some grouping. Let us refer to OD as meta-level zero (M0) and to CD as meta-level one (M1). CM and OM together constitute meta-level two (M2), CMM and OMM constitute meta-level three (M3).

We are done and have come up with a completely coherent description of the meta-level architecture, which -- in principle -- could be extended by further, higher levels.

One might ask, why we have not grouped OD and CD in the very same way, as we have done it for OM and CM and for OMM and CMM, respectively. Such an argument would call for a three-level meta-architecture instead of a four-level meta-architecture. However, there is finer point in here. Of all arrows labeled with "instanceOf", there is only one arrow, whose semantics can be arbitrarily defined in the meta-level architecture: it is the arrow between OD and CD, which is in fact defined on M2. In that sense, the "instanceOf" arrow between OD and CD is of a different kind than that all the other "instanceOf" arrows -- it is of a different "quality", so to speak.

By the way, could there be reasons to introduce higher levels in the meta-level architecture, like M4, M5 etc? Yes, there could. The arrow between OMM and CMM on M3 is a necessity in order to have means to define the relationship between CM and OM in M2. If you want to define the relationship between OMM and CMM yourself, you need a higher level, which provides the infrastructure to do so. The four-level meta-architecture is the smallest number of levels needed by a modeling language designer in order to have means to specify M0, M1 and their interrelationship of instantiation. In practice, higher levels are possible but rarely needed.

Note that you will find a lot of figures in literature depicting the meta-level architecture, which are not accurate -- if not almost false. Even the UML 2.0 Standard (and previous versions of the UML Standard) is not 100% correct in its description of the meta-level architecture. Even though I said that the meta-level architecture is easy to understand, many miss to get the full picture and forget about the relation between M0 and M2.

Donnerstag, November 09, 2006

Der UML-Reasoner

Die Unified Modeling Language (UML) hat in etwa den Stellenwert als Ausdrucksmittel in der Softwareentwicklung, wie es das Englische in der Geschäftswelt hat: Die UML ist weit verbreitet, jeder "spricht" sie und jeder versteht sie. Es ist die Sprache, in der sich Software-Entwickler mitteilen und in der sie ihre Entwürfe und Entwurfsentscheidungen dokumentieren. Die Fähigkeit, UML-Diagramme zumindest lesen zu können, ist eine Basisfähigkeit für jeden, der in der Entwicklung objekt-orientierter Softwaresysteme involviert ist, und betrifft Programmierer und Entwicklungsleiter gleichermaßen.

Das Lesen, kritische Hinterfragen und selbstständige Erstellen von UML-Diagrammen ist keine einfache Fähigkeit. Bereits das Lesen von Klassendiagrammen erfordert sehr viel Übung. Es ist nicht trivial, selbst aus einfachen Kombinationen von Klassen und Assoziationen zwischen den Klassen die Auswirkungen auf der Ebene der Objekte abzuleiten, geschweige denn Fehler bzw. Mängel zu entdecken. Damit haben Studierende ebenso wie Entwickler aus der Praxis ihre Schwierigkeiten. So überrascht es kaum, dass sogar in der industriellen Praxis Klassendiagramme oftmals vieles an Qualität, Präzision und damit an Ausdrucksgehalt vermissen lassen. Die Folgen: Unklare, mangelhafte Diagramme verursachen erhebliche Kosten (Klärungsbedarf, Rücksprachen, Korrekturen etc.) während z.B. der Implementierungs- oder Testphase.

Da wäre es doch hilfreich, wenn man ein Werkzeug zur Verfügung hätte -- ich nenne es "UML-Reasoner" --, das eine interaktive Auseinandersetzung mit einem UML-Klassendiagramm erlaubt. An das Werkzeug, den UML-Reasoner, können Fragen zum Klassendiagramm gestellt werden: Zum Beispiel: "Ist es erlaubt, dass eine Instanz der Klasse A zwar mit einer Instanz der Klasse B verlinkt ist, nicht aber umgekehrt?" Der UML-Reasoner liefert die Antwort (ja oder nein) und begründet detailliert seine Antwort. Das Klassendiagramm kann innerhalb der UML-Reasoner-Umgebung modifiziert werden, so dass sich der Benutzer bzw. die Benutzerin interaktiv ein Design(-Verständnis) erarbeiten kann.

Der UML-Reasoner erzeugt außerdem auf Wunsch Beispiel-Szenarien von Objekt-Relationen, wie sie aus einem Klassendiagramm abgeleitet werden können. Der Benutzer bzw. die Benutzerin hat anhand der Beispiele eine Hilfestellung um entscheiden zu können, ob ein Beispiel-Szenario den ins Klassendiagramm gelegten Absichten (Intentionen) entspricht oder nicht.

Der UML-Reasoner wäre ein Werkzeug, mit dem man in einen interaktiven Dialog mit seinen Entwürfen eintritt und sollte zu besseren Entwurfsentscheidungen und genaueren Entwürfen führen. Wäre so ein Werkzeug nicht eine tolle Sache?

Eine Realisierung dazu könnte möglicherweise von Konzepten aus der logischen Programmierung profitieren.

Freitag, November 03, 2006

Die Welt als Computer: relativ einfach, oder?

Zug fahren ist doch was schönes! Ich sitze da, schemenhaft rast die Landschaft in der Dunkelheit an mir vorüber, und dröge vor mich hin. Es ist nach 21 Uhr, ich bin müde. Es grübelt in mir. Genauer, das Radio in meinem Kopf düddelt vor sich hin. Der Sprecher in meinem Kopf labert mal dieses, mal jenes. Der redet immer so nett zusammenhangslos daher, wenn ich müde bin. Wahrscheinlich sind wir beide müde. Mal angenommen, vermeldet mein Radiosprecher im Kopf auf einmal etwas deutlicher und gähnt, mal angenommen, die Welt, das ganze Universum würde durch einen gigantischen Riesencomputer berechnet werden. Ein Supercomputer ließe all das hier ablaufen. Was dann? Müsste dann nicht -- denk nach, Junge -- ja müsste dann nicht; ja klar, dann ist die Rechenzeit begrenzt, endliche Ressourcen und so, und dann, dann müsste doch; ja ich glaube, dann ist die Relativitätstheorie doch eine notwendige Konsequenz daraus. Oder? Unglaublich!

Wie bitte? Wer hat da was gesagt? Mein Hirn kommt auf Touren. Moment mal, Radiosprecher, wie war das? Wie kommst Du darauf? Wir diskutieren ein Weilchen miteinander. Der Laptop muss raus. Aufschreiben. Gerade das einzige Mittel, den Radiosprecher da oben in einen einigermaßen strukturierten Dialog zu zwingen.

Also, nochmal von vorne. Nehmen wir einmal an, diese Welt, das ganze Universum würde durch einen gigantischen Supercomputer berechnet werden. Vielleicht ist das Universum selbst der Computer!? Egal. Wenn diese Maschine endliche Ressourcen hat, dann hat sie erstens einen endlichen Speicher und zweitens kann sie nicht beliebig schnell rechnen. Soweit wir das heute wissen, ist das Universum endlich. Macht Sinn. Dann passt das Universum in einen Speicher. Einen unvorstellbar großen Speicher, aber es geht vom Prinzip her. Abgehakt.

Doch was hat es mit der begrenzten Rechenkapazität auf sich? Ich denke, es könnte ungefähr so gehen: Der Supercomputer rechnet von einem Zustand des Universums den nächsten aus und daraus wiederum den übernächsten Zustand des Universums und so weiter. Wie in einem Film: Bild für Bild. Das gibt den Ablauf über die Zeit. Zeit vergeht, und es tut sich was in dem Universum, der Supercomputer rechnet. Nun greift der Supercomputer zu einem besonderen Kniff, um die Rechenzeit gut zu verteilen: Teile, Kollektive von Teilchen im Universum, die sich bewegen, also eine gemeinsame Geschwindigkeit haben, bekommen weniger Rechenzeit zugewiesen. Je schneller etwas wird, desto seltener wird der Zustand in diesem Teilsystem, in diesem Relativsystem, neu berechnet. Der Superrechner hat also ein Grundrechentempo für die Welt und alles, was sich in dieser Welt bewegt, bekommt als kleine Teilwelt seltener Rechenzeit zugewiesen, um den neuen Zustand in dieser Teilwelt zu berechnen. So verhindert der Scheduler, dass "schnelle" Teilwelten ihm mehr und mehr Rechenzeit abverlangen.

Was bedeutet das? Angenommen, Sie setzen sich in eine Rakete und fliegen schneller und schneller. Ziemlich schnell nach einer Weile. Da der Supercomputer Ihnen seltener Rechenzeit zuweist um Ihren neuen Systemzustand zu berechnen, vergeht bei Ihnen gewissermaßen die Zeit langsamer. Sie atmen langsamer, denken langsamer, altern langsamer. Sie selber bemerken das aber nicht. Für Sie selber läuft alles ganz normal ab. Sie merken nicht, wenn der Scheduler Sie seltener in der Zeit voranschreiten lässt. Wenn Sie dann, nach einer Stunde wieder auf der Erde landen, sind Jahre, wenn nicht gar Jahrzehnte dort vergangen. Da ging es "schneller" zu, der Supercomputer hat hier mehr Rechenzeit investiert.

Kennen Sie das woher? Ja, genau, die Relativitätstheorie macht genau solche Vorhersagen über unsere Welt. Und bisher scheint die Relativitätstheorie gut zu stimmen. Und wenn wir schon dabei sind: Was hat es eigentlich mit der Lichtgeschwindigkeit auf sich? Das ist die maximale Geschwindigkeit, mit der sich irgendwas in unserer Welt bewegen kann. Ahnen Sie was? Das ist die Geschwindigkeit, bei der der Supercomputer am Limit arbeitet. Wenn alle Teilchen im Universum sich mit Lichtgeschwindigkeit bewegen, dann ist der Rechner ausgereizt. Schneller geht nicht. Die Lichtgeschwindigkeit als Ausdruck der begrenzten Rechenkapazität unseres Supercomputers. Und das Betriebssystem ist so gebaut, dass es kein Teilchen schneller als Lichtgeschwindigkeit transportiert, auch wenn gerade der Rest des Universums langsamer ist und Rechenzeit frei wäre. Der Supercomputer arbeitet konservativ. Jedes Teilchen bekommt das selbe Geschwindigkeitslimit, so dass, wenn alle die Geschwindigkeit voll ausfahren, der Supercomputer so gerade noch mitkommt. Man hätte das auch anders machen können. Aber der Superprogrammierer hat sich offenbar für diese Variante entschieden. Jedes Teilsystem, das sich mit Lichtgeschwindigkeit bewegt, bekommt folglich keine Rechenzeit mehr zugewiesen. Kurzum: Wer sich mit Lichtgeschwindigkeit bewegt, dessen Zeit steht still -- nur merken Sie das nicht. Der Scheduler kommt eben nicht vorbei, friert Ihren Lebenszustand ein und lässt Sie weder altern noch sonstwas. Der Rechner ist eben am Anschlag. Der kann Sie nicht mehr "weiterlaufen" lassen. Er setzt die Lichtgeschwindigkeit als Limit!

Ist Ihnen noch etwas aufgefallen. Der Scheduler weist uns nicht linear, also gleichmäßig, weniger Rechenzeit zu, wenn wir uns bewegen. Es ist offenbar ein Quantencomputer am Werk, der erst allmählich, bei sehr hohen Geschwindigkeiten, in der Nähe der Lichtgeschwindigkeit zu verzögern beginnt. Auch das ein Effekt, den die Relativitätstheorie vorhersagt.

Na, hat Ihnen dieser Unsinn auch so viel Spaß gemacht wie mir? Wenn das, was ich mir da mit meinem Radiospecher im Kopf zusammenphantasiert habe, auch nur einigermaßen stimmt, dann müßte sich aus der Relativitätstheorie tatsächlich ableiten lassen, was für eine Art Computer uns berechnet. Ist es wirklich ein Quantenrechner, wie ich es vor mich hinspinne? Oder ein traditionelles Multi-Prozessor-System? Auch über das Betriebssystem, den Scheduler und so, auch darüber müsste man eigentlich was rausfinden können. Sinngemäß: Läuft unsere Welt unter Windows, Linux, einem Echtzeit-Betriebssystem? Ich habe ja nur Vermutungen vor mich hingesponnen, aber es müsste sich aus der Relativitätstheorie ein ziemlich gutes Modell von diesem Supercomputer ableiten lassen. ... Hm, ich glaube, ich geh jetzt lieber schlafen und träum von meinem Supercomputer und dem Universum darin. Irgendwie bin ich mittlerweile zuhause angekommen, das Bett ist nicht fern. Alles ist relativ, nicht wahr? Wer hat das nochmal gesagt?

+++ schnarch +++

Mittwoch, November 01, 2006

Referenzen im Blick

Letzte Woche blieb mein Blick an einem Stückchen Programmcode hängen. Der Code war zwar nicht falsch -- er würde zweifellos die geforderte Arbeit tun --, aber es verbarg sich dahinter ein übler Denkfehler. In einem anderen Zusammenhang würde das Programm unerwünschte Seiteneffekte erzeugen. Ob der Programmautor sich dessen bewusst war?

Es ging darum Zahlen zu summieren. Nach Eingabe einer Zahl n soll die Funktion die Summe aus 1 + 2 + 3 + ... + n errechnen. Beispiel: Eingabe 5 => 1 + 2 + 3 + 4 + 5 = 15. Eine entsprechende Funktion ist einfach programmiert, hier am Beispiel mit Python. Python markiert Blöcke über Einrückungen statt über geschweifte Klammern oder ähnliches. (Da ich Schwierigkeiten mit dem Online-Editor habe, sind die führenden Leerezeichen durch Punkte markiert).

def sum1toN_V1(n):
....assert n >= 1
....res = 0
....for i in range(1,n+1): res += i
....return res


Um den Code zu verstehen, muss man einzig wissen, was range(1,n+1) macht: es liefert eine Liste von Zahlen von 1 bis n+1 zurück. Zum Beispiel ergibt sich für n=5 range(1,6) => [1,2,3,4,5]. In der for-Schleife werden die Zahlen nacheinander dem Wert i zugewiesen. (Für die Pythoniker unter Ihnen: xrange ist bei großen n vorzuziehen, ist aber ein wenig schwieriger zu erklären und hier im Moment unwichtig.) Pro Durchgang wird der aktuelle Summenwert aus i und dem Vorgängerwert der Hilfsvariablen res gebildet und in res gespeichert. Das assert-Statement stellt sicher, dass die Funktion nur mit positiven Eingaben arbeitet; das assert-Statement ist als Voraussetzung (precondition) zu verstehen. Siehe dazu auch "Netze spannen mit Design by Contract".

Nebenbei bemerkt: Die Summe kann auch rekursiv berechnet werden. Oben, Version 1, beschreibt ein iteratives Vorgehen

Der Code, an dem sich mein Blick verfing, sah nur minimal anders aus:

def sum1toN_V2(n):
....assert n >= 1
....for i in range(1,n): n += i
....return n


Der Programmierer hat es geschafft, die Variable res und damit eine ganze Zeile einzusparen. Er hat die Eingabe n genommen, addiert die fehlenden Zahlen aus der Reihe von 1 bis n-1 hinzu und gibt das Ergebnis aus. Raffiniert, oder?

Ja und Nein! Version 2 funktioniert zwar, aber Sie sollten sowas niemals programmieren. Gerade in einer dynamisch typisierten Programmiersprache wie Python ist das evil. Warum?

Denken Sie daran: Moderne Sprachen arbeiten fast ausschließlich mit Referenzen auf Objekte. Eine Referenz ist eine Art Zeiger auf ein Objekt. Einzig Zahlen, Strings und andere Basistypen werden typischerweise direkt durch ein Objekt und nicht durch eine Referenz darauf realisiert. Darum haben Sie bei Version 2 mit Zahlen Glück. Machen Sie dasselbe mit Referenzen, dann können Sie eine böse Überraschung erleben.

Um das zu demonstrieren, führe ich eine Klasse Number ein, die als Attribut einen Wert (value) hat. Lassen Sie sich von dem "self" nicht irritieren; es kommt ungefähr einem "this" in Java gleich. Die __init__-Methode ist der Konstruktor in Python.

class Number(object):
....def __init__(self,value):
........self.value = value


Passen wir die Funktion von eben auf die Verarbeitung von Numbers an:

def sum1toN_V3(n):
....assert n.value >= 1
....for i in range(1,n.value): n.value += i
....return n


Machen wir einmal einen Testlauf. Solche kleinen Programme kann man bei Python wunderbar einfach über die Konsole eintippen und interaktiv ausprobieren:

>>> a = Number(10)
>>> a.value
10
>>> b = sum1toN_V3(a)
>>> b.value
55
>>> a.value
55

Böse, gell?! Die Berechnung hat "nebenbei" a verändert. Ein Seiteneffekt, den Sie sich in aller Regel nicht wünschen. Es liegt an den Referenzen und call by reference. Sie haben der Summenfunktion eine Referenz auf das Number-Objekt a übergeben. Das Objekt wird über die Referenz manipuliert, die Referenz wird zurückgegeben und b zugewiesen. Folglich verweisen a und b auf ein und dasselbe Objekt.

Version 2 verhält sich dagegen unkritisch, da Zahlen nicht als Referenzen durchgereicht werden:

>>> a = 10
>>> a
10
>>> b = sum1toN_V2(a)
>>> b
55
>>> a
10


Mir selbst ist ein solcher Fehler im Umgang mit Referenzen auch schon unterlaufen. Wahrscheinlich muss da jeder Programmierer bzw. jede Programmiererin durch. Aber es hilft, wenn man diese Fehlerquelle im Kopf verankert hat. Man fällt ihr dann nicht so leicht zum Opfer. Und eine Lehre lässt sich daraus ziehen: Sie müssen exakt wissen, was eine Programmiersprache über Referenzen abbildet und was von dieser Regel ausgenommen ist.

Um die oben beschriebene Summenfunktion rankt sich übrigens eine Anekdote um Carl Friedrich Gauß. Sie kennen die Geschichte vielleicht. Carls Schullehrer stellte der Klasse die Aufgabe, die Zahlen von 1 bis 100 zu addieren. Reine Beschäftigungstherapie, der Lehrer wollte seine Ruhe haben. Klein Carlchen tat sich als Ruhestörer hervor, er war dafür zu clever. Er bemerkte eine besondere Eigenschaft. In der Zahlenreihe von 1 bis 100 ergeben die erste und letzte Zahl genau denselben Wert, nämlich 101, wie die zweite und die vorletzte Zahl usw. Das Spielchen kann man genau 50 mal machen. 50 mal 101 macht 5050. Fertig. Schenkt man dem wunderbaren Buch von Daniel Kehlmann "Die Vermessung der Welt" (Rowohlt Verlag) Glauben, dann bezog Carl dafür ein letztes Mal Prügel. Aber sein Talent ward entdeckt und wurde fortan gefördert.

P.S.: Ein Pythoniker hätte die Summenfunktion anders geschrieben, da es die eingebaute Funktion sum gibt. Damit hätte es ganz knapp gelautet:

def sum1toN(n):
....assert n >= 1
....return sum(range(1,n+1))

Mittwoch, Oktober 25, 2006

Vorprojekt-Phase: Das Kunden-Orakel und die Hellseherei

"Guten Tag, mein Name ist Kluge, Martina Kluge, ich bin Geschäftsführerin der Firma BrainTeaser, man hat sie mir empfohlen."

Da steht sie, die liebe Frau Kluge. Ihre Präsenz erfüllt das ganze Büro, obwohl sie noch gar nicht eingetreten ist. Große, intelligente Augen blicken Sie neugierig an. Ihr Freund Heinrich, von ihm ist die Empfehlung, hat den Besuch schon vorgewarnt. Sie sei ein Wirbelwind, sagte er Ihnen am Telefon -- und er klang dabei amüsiert. Nun denn ...

"Bleiben Sie sitzen", sagt Frau Kluge freundlich, lächelt hinreißend und löst sich aus der Tür. Ihre Augen haben offenbar einen neuen Fixpunkt gefunden, auf den Sie regelrecht zustürzt. Sie strebt auf das voll beschriebene Whiteboard mit den Projektplanungen der nächsten sechs Monate zu. Das Ergebnis zweier Nächte Planungsarbeit mit Ihrem Kollegen Gerd. Das Zeug ist wichtig.

"Darf ich?"

Eigentlich nicht, eigentlich wollten Sie gerade "Nein" sagen -- aber es ist zu spät. Es kommt Ihnen vor, als habe Frau Kluge die ganze Planung mit nur einem einzigen Wischer vernichtet. Hoffentlich hat Gerd ein gutes Gedächtnis, seufzen Sie in sich hinein und haben den Gedanken längst aufgegeben sich vorzustellen. Wozu auch? Links neben Ihrer Bürotür ist das Schildchen mit Ihrem Namen nicht zu übersehen. Frau Kluge wird zweifellos wissen, wer Sie sind.

"Ich brauche sowas hier."

Ein paar flotte Striche. Ein Kästchen hier, eines da, ein Strich dazwischen.

"Wir wollen für unsere Kunden einen neuen Dienst anbieten. Über's Internet. Sie verstehen?! Ein neues Portal, ein neues Medium. Hier, da", Kluges Finger zeigt auf den einen Kasten, "ist unsere Datenbank mit allen Kundendaten. Name, Adresse, Sie wissen schon. Da drüben", ihr Finger wandert rüber, "da sollen die Applikationen andere Dienste aus unserem Unternehmen mit den Kundendaten auf eine ganz neue Art verknüpfen." Kluges Augen leuchten.

Für die nächste halbe Stunde ist Frau Kluge nicht zu bremsen. Obwohl Sie den Verlust Ihrer Planung noch nicht ganz verwunden haben, haben Sie geistesgegenwärtig nach Bleistift und Papier gegriffen und machen sich Notizen. Sie hätten doch einen Stenographie-Kurs machen sollen. Mehr als verständnisvolles Zunicken gesteht Ihnen Frau Kluge nicht zu. Sie redet und redet.

Am Ende fragt Sie Frau Kluge mit ihrem hinreißenden Lächeln:

"Können Sie uns die Software dazu entwickeln?"

Pause. Ruhe. Stille im Büro. Sie dürfen zum ersten Mal etwas sagen! Wie wollen Sie dieser Frau einen Wunsch abschlagen? Dieses Lächeln! Viel besser noch: Das ganze Vorhaben klingt gigantisch. Eine echte Herausforderung. So hört es sich jedenfalls an. Sie haben Fragen, 1000 Fragen. Eigentlich haben Sie fast gar nichts verstanden. Es klingt aber irgendwie toll.

"Ja? Bauen Sie uns das?"

Da Sie ein guter Mensch sind, ein guter Software Engineer dazu, sind Sie nett und aufrichtig zu Frau Kluge. Sie drücken Ihre Begeisterung aus, fassen in wenigen Worten zusammen, was Sie glauben verstanden zu haben. Ja, das klingt interessant, sehr interessant sogar. "Wir sollten das unbedingt in Angriff nehmen", hören Sie sich sagen, "die Idee klingt sehr überzeugend." Und dann gestehen Sie ihr, dass noch viel Arbeit vor Ihnen beiden liegt. Sie müssen erst verstehen lernen, was sie will, in welcher Welt sie lebt, welchen Zweck genau das Produkt verfolgt etc. Und dann, wenn das verstanden ist, dann können Sie ihr verraten, wie Sie weiter machen wollen. Wie ein Projekt dazu aussehen könnte. Ob eine Vorstudie erforderlich ist. Oder Prototyping. Oder oder.

Frau Kluge freut sich. Sie scheint kein "Ja" als Antwort erwartet zu haben. Sie freue sich über die weitere Zusammenarbeit. Sie scheint sich der Komplexität des Vorhabens vollkommen bewußt zu sein, wenn Sie sie so reden hören. Und natürlich müsse man jetzt in kleinen Schritten vorgehen. Sie wisse, ehrlich gesagt, ja auch noch nicht im Detail, wie das alles funktionieren solle. Aber die Idee, davon sei sie überzeugt.

Kurz darauf sitzen Sie wieder allein in Ihrem Büro. Sie rufen als erstes Gerd an. Er soll versuchen, die Planungen zu rekonstruieren. Dann trommeln Sie zwei ihrer besten Leute zusammen für ein Treffen nach dem Mittagessen. Sie wollen von dem Treffen mit Frau Kluge berichten und das weitere Vorgehen besprechen.

14:08 Uhr. Sie haben Niklas und Kristina von Kluges Monolog berichtet -- und dazu selber eine Dreiviertelstunde gebraucht. Beide sind beeindruckt. Ein interessantes Projekt, das sich da anbahnen könnte.

"Wie sollen wir vorgehen Kristina? Was glaubst Du?", fragen Sie.

"Wir haben alle Fragen über Fragen. Aber ich glaube, es ist nicht sehr geschickt, Frau Kluge mit unseren Fragen zu bombardieren."

"Das denke ich auch.", sagt Niklas, "Unsere Fragen resultieren ja aus einer gewissen Unkenntnis heraus. Es ist nur allzu menschlich, sich selbst aus vagen, unscharfen Angaben heraus ein erstes Bild zu machen. Diese Vorstellung, die wir uns jetzt machen, kann vollkommen falsch sein und an Frau Kluges Problemwelt vorbeizielen."

Kristina: "Wir müssen Wissen fließen lassen, von Frau Kluge zu uns. Das wird am leichtesten gelingen, wenn wir es schaffen, einen Dialog aufzubauen."

Niklas: "Ja, ein Beispiel wäre, unser erstes Verständnis in Szenarien zu beschreiben und die Szenarien aus verschiedenen Rollen zu beleuchten. Mit dem System sollen die Kunden arbeiten, Administratoren, aber auch Autoren und Redakteure in Frau Kluges Firma werden benötigt, um das System zu pflegen und mit Informationen zu füttern. So sieht das jedenfalls im Moment für mich aus."

Sie: "Wir würden immerhin merken, ob wir richtige Annahmen machen -- und worüber sich Frau Kluge bereits Gedanken gemacht hat."

Kristina: "Ich glaube auch, dass das eine gute Idee ist. Wir könnten das ergänzen um Papier-Prototypen, die das System konzeptionell abbilden und helfen, ein Szenario anzustoßen."

Sie: "Mir gefällt solch ein Ansatz. Gibt es noch weitere Ideen und Möglichkeiten, einen Dialog über das zu entwickelnde System in Gang zu setzen?"

Kristina: "Ich hatte neulich erst ein Buch in den Händen, das systematisch eine Fülle von 'Dialog-Techniken' zusammengetragen hat. Alles Techniken um in solchen frühen Phasen zu erfassen, was irgendwann mal in ein Anforderungsdokument münden wird. Ich kann das gerne mal nachlesen, vielleicht eine Vorauswahl machen und Euch vorstellen."

Sie: "Das klingt gut. Lass uns das so machen."

Niklas: "Sag mal, Du hast doch Frau Kluge bestimmt eine Telefonnummer abgeluchst, eine Kontaktperson, die auch viel über Kluges Visionen weiß und vielleicht mehr auf der technischen Seite steht. Die könnte ich ja mal kontaktieren."

Sie schmunzeln in sich hinein: "Ja, ich habe in der Tat eine Nummer, ein IT-Mensch aus Frau Kluges Firma. Das wäre sehr schön, wenn Du Dich telefonisch mit ihm in Verbindung setzen könntest."

Kristina: "Wann sollen wir uns wieder treffen? Ich könnte meinen Teil bis morgen gegen 16 Uhr erledigt haben. Ich habe zwar noch ein paar andere Dinge zu tun, aber das ließe sich einbauen."

Sie: "Schön. Wie sieht es denn überhaupt mit eurer Arbeitsbelastung aus? Ihr seid beide in laufenden Projekten involviert. Der Auftrag von Frau Kluge scheint Potential zu haben und könnte uns viel Geld bringen. Aber wir dürfen die aktuellen Projekte nicht gefährden. Könnt ihr euch darum auch kümmern, damit wir euch vernünftig einplanen? Können wir das morgen um 17 Uhr miteinander besprechen? Um 18 Uhr sind wir spätestens fertig."

Niklas: "Ok, machen wir. Ich werde bis dahin sicher auch mit dem IT-Menschen gesprochen haben."

---

Ein Tipp noch: Kristina wird ein Kapitel lesen aus dem Buch "Requirements-Engineering und Management" von Chris Rupp aus dem Hanser-Verlag, 2007, 4. Auflage. Und zwar genau das Kapitel, das auf der Webseite zum Buch als Leseprobe angeboten wird ;-)

Freitag, Oktober 20, 2006

Bucheinblicke

Manche Ideen taugen als Produktidee und lassen sich mit viel Glück erfolgreich auf den Markt bringen. Das "Web 2.0" ist voll mit solchen Versuchen. Andere Ideen schrammen an einer Grenze, die rechtlich vermutlich nicht ganz unbedenklich ist -- was aber auch konstruktiv als Kunstform umgemünzt werden kann.

Ein Beispiel: Amazon bietet eine "Search Inside"-Funktion bei ausgewählten Büchern in ihrem Verkaufsportal an. Sie geben einen Suchbegriff ein, und Ihnen wird eine Liste geliefert mit allen Seiten, die diesen Begriff enthalten. Klicken Sie nun eine Seite an, wird Ihnen die Buchseite als Bild vollständig angezeigt.

Es bedarf keiner großen Mühe, um sich mittels geschickter Suchabfragen den Einblick in ein ganzes Buch zu verschaffen. Hatten Sie die Idee auch schon? Die Idee liegt derart provokant nahe, auch der nächste Schritt, diesen Vorgang mit einem Programm zu automatisieren, dass sich eine Frage aufdrängt: Wie verträgt sich eine solche, eigentlich sehr kundenorientierte Funktion mit Urheberrechten?

Ich will darauf keine Antwort geben. Originell finde ich jedoch den Ansatz, es als Kunstprojekt zu inszenieren.

P.S.: Amazon hat die "Search Inside"-Funktion mittlerweile eingeschränkt.

Mittwoch, Oktober 11, 2006

Prozessor mit 10 Fingern

Computer rechnen mit Einsen und Nullen, nicht wahr?! Meistens, aber nicht immer. Ich kann mich dunkel erinnern, mal von einem Rechner gelesen zu haben, einem Rechner aus grauer Vorzeit, der mit einem höherwertigen Zahlensystem rechnete. Im 6er-, 10er- oder 12er-System, ich weiß es nicht mehr. Doch jetzt kann ich das Kramen in den grauen Zellen sein lassen. Es wird ihn wieder geben, den Computer mit "10 Fingern". (Für den Hinweis vielen Dank an AnA.) IBM hat erste Details verraten über den kommenden Power6-Prozessor. 5GHz und eine dezimale Fließkommaeinheit (Floating Point Unit, FPU) sollen den Prozessor auszeichnen, so vermeldet bei golem.

Die Verwendung des 10er-Systems lasse den Prozessor schneller rechnen, so heißt es in der Meldung. Aber warum? Details sind in der Meldung nicht zu finden, auch nicht auf den verlinkten Seiten. Meine Vermutung ist, dass die FPU auf Schaltungsebene mit mehrwertigen Logiken arbeitet, auf der die Zahlen durch verschiedene Spannungslevel abgebildet werden. In absehbarer Zeit wird das Geheimnis gelüftet werden.

Montag, Oktober 09, 2006

RFID

Eigentlich sind die kleinen Funk-Chips kalter Kaffee -- eine fast schon uralte Idee, die jedem Nachrichten-Techniker wie selbstverständlich vorkommen mag. Im Gespräch sind diese Chips schon seit vielen, vielen Jahren. Doch allmählich scheint ein Markt für ihren Einsatz zu entstehen. Es sieht so aus, als würde RFID (Radio Frequency Identification) Wirklichkeit werden. Die Marktprognosen sehen bestens aus (heise-Meldung).

Vor kurzem bin ich durch eine andere heise-Meldung auf eine Informationsbroschüre zu RFID gestoßen. Herausgegeben hat sie das Forum InformatikerInnen für Frieden und gesellschaftliche Verantwortung e.V. (FIfF). Die Broschüre ist angenehm zu lesen. Sie beschäftigt sich unter anderem mit der Technik, Anwendungen von RFID, Risiken & Ängsten und kryptographischen Methoden. Eine ausführliche Liste mit Links bietet interessierten Lesern Einstiegspunkte. (Übrigens finden Sie auf der Webseite von FIfF auch eine ähnlich aufgebaute Broschüre zur elektronischen Gesundheitskarte.)

Ich frage mich, ob man mit diesen Funk-Chips etwas machen kann, worauf bislang noch keiner gekommen ist. Hm ...

Mittwoch, Oktober 04, 2006

Idee zum WebCaching

Immer wieder treibt mich das Thema "HTTP-Caching" um -- ich nenne es auch gerne WebCaching, auch wenn der Begriff es nicht ganz trifft. Caching ist ein wichtiges Thema in vielen Bereichen, in denen es um Performanz geht. Prozessorarchitekturen, Datenbanken und webbasierte Systeme etc. nutzen Caching sozusagen als Turbolader. Vermeintlich langsame Systeme können durch geschickte Caching-Strategien rasend schnell werden, indem sie die von ihnen erwarteten Reaktionen vorhalten.

Kurz etwas Hintergrund zu HTTP und HTTP-basiertem Caching, bevor ich zu meiner Caching-Idee komme.

HTTP ist ein Anfrage/Antwort-Protokoll. Der Client, z.B. Sie über Ihren Webbrowser, schickt eine HTTP-Anfrage (request) an einen Webserver, und der Server beantwortet die Anfrage mit einer HTTP-Rückmeldung, einem HTTP-Reply. Es ist immer dasselbe. Ausschließlich der Client schickt Requests an den Server; und der Server reagiert nur auf diese Anfragen mit einem Reply. Das Prinzip ist sehr einfach.

Wenn Sie eine normale Webseite aufrufen, wird in aller Regel eine Vielzahl von HTTP-Requests an den Webserver geschickt. All das regelt der Browser automatisch für Sie und hängt ab von den Inhalten einer Webseite (Bilder, CSS etc.), die noch nachzuladen sind. Wenn Sie dieses Spielchen einmal verfolgen wollen, es gibt mit LiveHTTPHeaders eine nette Erweiterung für den Firefox, die Sie installieren können.

Caching funktioniert nur, wenn sich zwischen Client und Server eine oder mehrere Cache-Einheiten befinden, die den ganzen HTTP-Traffic mit abbekommen und gegebenenfalls HTTP-Requests "abfangen" und statt des Servers ein Reply an den Client zurückgeben. Der Server ist damit entlastet.

Bevor der Cache einen HTTP-Request abfängt, muss er wissen, für welche Requests er die Reply übernehmen darf. Dazu markiert der Server beim Versand einer Reply den HTTP-Header mit einem Hinweis, dass ein Cache die Nachricht für eine gewisse Zeit vorhalten darf. Der mitlesende Cache merkt sich das und antwortet zukünftig auf gleiche Anfragen in Stellvertretung für den Server.

Um es ein wenig konkreter zu machen: Sie dürfen sich einen Request wie eine Anfrage vorstellen die lautet "Gib mir den Inhalt der Webseite www.xyz.de/test.html", woraufhin der Webserver www.xyz.de bzw. ein zwischengeschalteter Cache den Inhalt test.html zurück liefert.

Bei diesem Ansatz gibt es ein Problem: Ändert sich test.html beim Webserver und ist die Caching-Zeit beim Cache noch nicht abgelaufen, liefert der Cache die "veraltete" Seite zurück -- und der Server kann den "neuen" Inhalt nicht ausliefern, da der Cache den HTTP-Request nicht durchläßt.

Irgendwie muss also der Cache vom Server über die Ungültigkeit von test.html im Cache informiert werden. Dazu gibt es jedoch kein standardisiertes Protokoll. Wenn Inhalte vor Ihrer Zeit im Cache ungültig werden, Pech gehabt. Wenn man auf Lösungen Marke Eigenbau verzichten möchte, dann muss man sich etwas einfallen lassen, was vollkommen verträglich ist mit der Standard-Webtechnologie.

Meine Idee dazu:

Der Client fragt test.html beim Server an. Der Server liefert zwar test.html mit einem Reply aus, jedoch enthält test.html nicht den eigentlichen Seiteninhalt, sondern ein JavaScript-Programm. Dieses Programm weist den Client an (sofern JavaScript ausgeführt werden darf), eine Seite test-001.html per Request vom Server anzufragen und den Inhalt von test-001.html zum Inhalt von test.html zu machen (Stichwort DOM, Document Object Model). Dieser Inhaltstausch ist wichtig, damit die Seite auch unter test.html per Bookmark gemerkt werden kann. Der Server gibt also test.html nicht zum Cachen frei, jedoch test-001.html (z.B. für eine Stunde).

Jede neue Anfrage nach test.html belastet zwar den Server damit, eine kurze Antwort auszuliefern, die das JavaScript-Programm enthält, aber die Folgeanfrage nach test-001.html wird vom Cache beantwortet. Dem Server wird damit der wesentliche Traffic vom Leib gehalten.

Ändert sich test.html beim Server, wird eine neue Version test-002.html generiert. Erreicht nun den Server ein neuer HTTP-Request für test.html, liefert er test.html mit einem leicht geänderten JavaScript-Programm aus, das nun nicht mehr zum Nachladen von test-001.html auffordert, sondern nach test-002.html verlangt. Damit wird der Cache "umgangen", der Server kann die aktuelle test-002.html-Seite ausliefern und fürs Caching (z.B. wieder für eine Stunde) freigeben.

Haben Sie die Idee im Kern verstanden?

Ich kann mir gut vorstellen nicht der Erste zu sein, der diese Idee hat. Wenn Sie eine entsprechende Seite finden, ich würde mich freuen davon zu erfahren. Vielleicht haben Sie noch andere interessante Ideen? Sicher gibt es noch andere Varianten zum Caching.

Samstag, September 30, 2006

Semantics, Behavior and Structure

Two persons talking about a "car" must have the same (or at least a very similar) understanding of what the term means. The meaning of the term is determined by its use in an operational context. A persons assumptions and expectations of the effects of this use express his or her understanding.

The key point here is that semantics have to do with hypotheses about things in action. A hypothesis reflects the capability of a person to predict the effects of an operation on things. As a prerequisite, we have to demand that operations on things are causal, i.e. there is a dimension of time resulting in a timely relation of cause and effect: the cause is before the effect.

To formalize things, let's say that we have entities and operations, which provide an operational context for the entities. For the purpose of experimenting with the ideas presented, we use numbers as entities and functions as operations. A function (as you know it e.g. from Scheme or Python) relates input to output with the output being the effect of processing the input by the function. The processing aspect of a function consumes time and enforces causality.

Let us take a function called "add" with the following signature:

add(number,number) -> number

The function takes two numbers as an input and computes a number. Here, we define "number" to be a positive integer including zero.

Let's assume that we do not have any knowledge about what "add" actually does. From the signature definition we just know what "number" is -- an infinite set of elements. The function "add" is the operational context in which the numbers are used. Anything we can learn about numbers is only in the context of "add". So, the question is: What is the semantics (the meaning) of "add"? What kind of knowledge does "add" unveil about numbers used in the "add"-context.

The only way to get an answer on this is to play around with "add" and build up hypotheses about cause and effect, about input and output.

add(1,2) => 3

add(2,5) => 7

etc.

Typing in some operations makes you come up with a hypothesis called "sum". In all cases you verified "sum", sum(x,y) turns out to deliver the same result as add(x,y) does. The more cases you tested, the better your hypothesis. If you have two competing hypotheses, prefer the one, which is the most simplest; this principle is known as Occam's razor. A hypothesis, which does not enable you to make a sound guess on the output produced on any kind of input, is an incomplete hypothesis.

Playing around a bit further, you might learn that add(x,y) always seems to be equal to add(y,x); a hypothesis, which you decide to call "'add' is commutative", meaning "add" is not sensitive to the order of the input given. Of course, this hypothesis is also integrated in your understanding of "sum".

You might also formulate the hypothesis that 0 is a sort of neutral element, since you observe add(x,0) = x and add(0,y) = y.

As you can see, learning is the process of formulating a working hypotheses and gaining confidence in their likelihood of being correct. The result of learning is knowledge, an established set of hypotheses. Hypotheses reflect your internalized meaning of the things you observe in action.

Let's look at another function called "addd" (note that there is a third "d"). It's signature is

addd(number,number,number) -> boolean

A boolean is a value that can be either true or false.

As you might have guessed, there is a connection to "add". And in fact, "addd" behaves quite similar. Let's give it a try:

addd(1,2,3) => true

addd(1,2,4) => false

addd(1,2,5) => false

addd(2,3,5) => true

The difference to "add" is that this function invites me to explore the structural relations of the input given, since only certain combinations of numbers are regarded as correct whereas others are not. Still, our hypothesis of commutativity with regards to the first two input parameters holds

addd(x,y,z) = addd(y,x,z)

Also, our hypothesis of "sum" still seems to be correct:

addd(x,y,sum(x,y)) => true

The interesting part now is that we can easily formulate much more hypotheses about "addd" than about "add". In the case of "add", we formulated hypotheses about behavior; in the case of "addd", we come up with hypotheses about structure.

Here are some examples of hypotheses about "addd", all of which are making statements about the relationships between the input numbers. For instance: Given two numbers x and z, we have a hypothesis "sub_y" such that

addd(x,sub_y(z,x),z) => true

Analogously, given two numbers y and z, we have a hypothesis "sub_x" such that

addd(sub_x(z,y),y,z) => true

Because of our hypothesis of commutativity, we can conclude that for a given z the hypotheses "sub_x" and "sub_y" are the same, which we could call "sub".

Another hypothesis is "pair"

pair(number) -> number, number

such that

addd(pair(z),z) => true

Take z = 3 as an example, "pair" could return either 1, 2 or 2, 1 or 3, 0 or 0, 3.

The difference between "add" and "addd" is that "add" describes a behavioral relation of cause and effect on numbers, whereas "addd" describes a relation of cause and effect of an verification process. The verification process checks, if the way "addd" relates the input given fulfills certain properties. Your were asked to formulated hypotheses about these properties!

That is, "add" is a behavioral, but causal relation and "addd" is a logical relation, behavioral just in the sense of making a logical statement after an input has been given. Functional relations describe behavior, logical relations describe structure. Behavior is a matter of time; structure is a matter of correctness. In other words, behavior has a time aspect, structure hasn't.

As can be concluded from the examples given, behavior can be easily transformed into a structure presentation; the structure can then be investigated for behavioral hypotheses. However, as we have seen, much more hypotheses can be derived from structure, because structure doesn't have any inherent notion of causality. If causality is not a constraining factor, the space to explore and investigate broadens. Several hypotheses can be formulated, which interpret the aspect of time differently in the structure. The hypothesis of "sub" can only be deduced from "addd", but not from "add"!

What all this shows is that behavior and structure are connected and that there is more knowledge to uncover from structure than from behavior.

[A side remark: If you think about implementing "addd" via "add" or vice versa, you'll end up with a backtracking mechanism systematically searching for combinations of numbers, which solve the problem at hand. This is exactly, how logical programming works, see e.g. Prolog.]

Donnerstag, September 21, 2006

Damals ...

Wenn Sie, wie ich, mit den ersten Rechnern groß wurden, die den rührseligen Namen "Heimcomputer" trugen, die klein und erschwinglich waren und in Ausmaß und Gewicht mühelos mit heutigen Laptops konkurrieren konnten, dann fühlen Sie sich vielleicht in diesem Beitrag auch erinnert an damals. An die Zeit, in der 1 MHz Ferrari-Gefühle aufkommen ließ und einige Kilobytes Speicher Reichtum bedeuteten.

Das "Rechenzentrum" unseres Gymnasiums befand sich in der Sternwarte -- der kühlste Raum der ganzen Schule, immer ein wenig zugig. Dort tat ein Commodore seinen Dienst. Natürlich bekam nicht jeder Zugang zu diesem Wunder an Rechenkraft. Irgendwann kam ich auch in den Genuß dieses Privilegs. Ich kann mich noch dunkel daran erinnern, wie ich einmal aus einer Zeitung -- ich glaube es war die CHIP -- ein Maschinenprogramm im Binärcode abtippte, nur um am Bildschirm Zeuge einer Diffusionssimulation zu werden. Das war ganz wunderbar, da der grüne Monitor noch so schön nachleutete und die durch Kreise abgebildeten Gasmoleküle beim Flug einen Schweif hinter sich her zogen.

Mein erster Rechner war ein ZX81 mit 4 KB. Darauf folgte ein Sinclair Spectrum, für kurze Zeit ein Sinclair QL, dessen Bandlaufwerk mit immerzu die Bänder zerknickte, später ein Atari ST. Und irgendwann besaß ich einen PC, einen 386er, den ich für meine Studienarbeit ganze drei Wochen(!) lang Zeichensätze für das TeX-Programm ausrechnen ließ. Die Qualität dessen, was sich anschließend mit TeX, genauer mit LaTeX, produzieren ließ, entschädigte das lange Warten.

Wer weiter in alten Erinnerungen schwelgen möchte, es gibt das Homecomputermuseum.de.

Donnerstag, September 14, 2006

Strongtalk

Der Computational Theologist von Sun Java, Gilad Bracha, hat am 11. September die Freigabe der Smalltalk-Implementierung "Strongtalk" als Open Source Software in seinem Blog bekannt gegeben. Smalltalk, wer es nicht weiß, gehört mit zu den ältesten Programmiersprachen, ist objekt-orientiert und hat viele andere Sprachen beeinflusst; Infos dazu z.B. unter Wikipedia. Smalltalk war seiner Zeit deutlich voraus und ist es in gewisser Hinsicht bis heute, weshalb sich immer noch eine Fangemeinde für diese Sprache findet.

Beachtlich finde ich, womit sich Leute wie Bracha beschäftigen, abseits von Java. Mir scheint sich dahinter ein Trend auszudrücken, den ich auch an anderen Stellen glaube zu beobachten (siehe z.B. IronPython). Dynamisch typisierte Programmiersprachen scheinen zunehmend ernst genommen zu werden. Man sieht ihre Vorzüge und bemüht sich um die schmerzfreie Koexistenz von statischer und dynamischer Typisierung. Das beste aus beiden Welten soll miteinander verschmolzen werden.

Dienstag, September 12, 2006

Abstraktion und Vergröberung

Bei der Modellierung von Systemen kommen zwei Techniken zum Einsatz: das eine ist die Abstraktion, das andere die Vergröberung. Was unterscheidet eigentlich das eine vom anderen? Meint beides nicht dasselbe?

Der Vorgang des Abstrahierens bzw. der Abstraktion lässt sich formal leicht fassen. Ein praktisches Beispiel soll beim Verständnis helfen. Nehmen wir die Spezifikation einer Methode

method float squareRoot1(float: number)

Die Methode "squareRoot1" beschreibt das Ergebnis auf eine eingegebene Fließkommazahl. Es wird eine Fließkommazahl zurück gegeben. Die folgende Methode schränkt die Eingaben per Vorbedingung (pre-condition) auf positive Werte ein und sichert eine positive Fließkommazahl als Ergebnis per Nachbedingung (post-condition) zu.

method float squareRoot2(float: number)
pre: number > 0
post: result > 0

Methode "squareRoot2" verfeinert die Eigenschaften der ersten Methode; es werden Details zur Konkretisierung der Eigenschaften hinzugefügt. Man nennt dies entsprechend property refinement oder auch behavioral refinement. Jede Eingabe/Ausgabe-Historie der verfeinerten Methode (squareRoot2) ist auch eine gültige E/A-Historie der abstrakten Methode (squareRoot1). Die konkretere Methode impliziert im mathematisch formalen Sinn die abstrakte Methode. Das ist die Essenz der Abstraktion, eine Verfeinerungsbeziehung. Genau das ist auch gemeint, wenn jemand sagt "Ein Interface abstrahiert von der Implementierung".

Analog kann man weitere Spielarten der Verfeinerung definieren wie z.B. interface refinement und communication refinement, die Abstraktes und Konkretes in einen definierten Bezug zueinander setzen. Wer sich für die formalen Grundlagen interessiert, dem sei das Buch empfohlen von Manfred Broy und Ketil Stolen: Specification and Development of Interactive Systems, Springer, 2001.

Bei der Vergröberung werden nicht nur einfach Details ausgeblendet, es werden Vereinfachungen vorgenommen. Eine vergröberte Sicht auf etwas reduziert auf einen wesentlichen Aspekt, es engt ein Modell, eine Systemaussage auf einen erfassbaren Bereich ein. Ohne die Vergröberung sind komplexe Systeme überhaupt nicht versteh- und analysierbar.

Der Übergang vom vergröberten Modell zu einem konkreten System erfordert Präzisierung: das Ergänzen und Revidieren von Eigenschaften. Damit gilt nicht mehr, dass die E/A-Historie eines präzisierten Modells auch eine gültige E/A-Historie des vergröberten Modells ist. Wohl gibt es eine Ähnlichkeit zwischen den E/A-Historien, sie sind nicht völlig unabhängig voneinander. Man könnte, so man denn wollte, ein Ähnlichkeitsmaß für E/A-Historien definieren, um den Grad der Vergröberung zu messen. Die semantische Aussagequalität der Vergröberung ist folglich nicht im präzisierten Modell enthalten und kann daraus nicht abgeleitet werden.

Das klingt für mich danach, als könnte man Abstraktion und Vergröberung aus informationstheoretischer Sicht fassen. Das sollte gehen!

Ein Unglück mit dem Begriff der Vergröberung ist, dass die Vergröberung ebenfalls gerne als Abstraktion bezeichnet wird. Dann wird man allerdings begrifflich zu grob und verliert das Abstrakte ;-)

Montag, September 11, 2006

Nachgeschoben: Defizite im Software Engineering

Huch, wo ist er denn? Ich habe einige Posts schon fertig geschrieben, sie aber noch nicht veröffentlicht. Vorhin habe ich einen dieser Posts frei gegeben -- und er erschien nicht. Bis ich bemerkte, dass er unter dem Datum seiner Entstehung eingelistet wurde. Tricky!

Also, wer es noch nicht gesehen hat: Die "Defizite im Software Engineering" sind "nachträglich" im August erschienen.

Mittwoch, September 06, 2006

Hart: IronPython

Leute, die -- wie ich -- Liebhaber der Programmiersprache Python sind, dürfen sich über die just erschienene Python-Version für .NET freuen: IronPython, Release 1.0. Der Heise-Verlag hat das heute auch in einer News gemeldet, siehe hier.

[Update 2006-09-15: Im Video-Interview (auf's Bild klicken) zeigt Jim Hugunin, der Entwickler von IronPython, am Bildschirm, wie elegant sich IronPython in die .NET-Welt einfügt.]

Montag, September 04, 2006

Reverse Ajax

Seit einer Weile schon beschäftige ich mich immer wieder mit AJAX und mache mir Gedanken über die Architektur eines neuen WebFrameworks, das die durch AJAX gegebenen Möglichkeiten so weit wie möglich ausreizt.

Bei der Webtechnologie gibt es eine Beschränkung, die am zugrunde liegenden Protokoll HTTP liegt. HTTP definiert ein striktes Anfrage/Antwort-Prozedere, das ausschließlich vom Client, dem Webbrowser, ausgehen kann. Der Client stellt eine Anfrage (request) an den Server, der Server antwortet mit einem Reply. Der Server kann den Client nicht eigenmächtig über neue Ereignisse informieren. Man muss sich etwas originelles einfallen lassen, wie ein Server einen Browser z.B. über neue News auf einem Nachrichtenportal informieren kann.

Eine Idee, auf die man rasch kommt, ist die regelmäßige Nachfrage. Der Client fragt im Hintergrund für den Surfer unbemerkt z.B. jede Minute beim Server nach: "Willst Du mir Infos übermitteln?" Falls ja, werden die Infos an den Client übermittelt. Das ist nichts anderes als eine ajaxifizierte Lösung einer altbekannten Technik, dem Polling.

Auf zwei weitere Ansätze bin ich selbst noch nicht gekommen. Wenn man sie gelesen hat, dann kann man sich fast fragen, wieso man selbst nicht gleich die Idee hatte, siehe Reverse Ajax. Ok, es gibt Leute, die kommen darauf ;-)

Donnerstag, August 31, 2006

Hightech-Strategie für Deutschland

Wußten Sie, dass die deutsche Branche für Informations- und Kommunikationstechnologien (IKT) rund 750.000 Menschen beschäftigt und der Markt für IKT in Deutschland ca. 134 Milliarden Euro beträgt? Wußten Sie, dass mehr als jeder zweite Halbleiter aus Europa "Made in Germany" ist? Über 90% aller Prozessoren arbeiten nicht in einem PC, sondern in einem sogenannten "eingebetteten System" -- interessant, nicht wahr? (Seien Sie sicher, da läuft kaum Java oder C# drauf ;-) Ach, schon gewußt, wie bedeutsam simulierte Realitäten, Grid Computing und das Internet der Dinge sind?

All diese Informationen habe ich aus der gestern (Mittwoch, 30. August 2006) vom Bundesministerium für Bildung und Forschung (BMBF) veröffentlichten "Hightech-Strategie für Deutschland" (wählen Sie die Langfassung, auch hier zu beziehen), siehe S. 54 ff. Ich finde, da lohnt es sich hineinzuschauen.

Dienstag, August 29, 2006

Netze spannen mit Design by Contract

Was verbirgt sich hinter diesem Methodenaufruf?

method float squareRoot(float: number)

Eine Methode namens "squareRoot" (Quadratwurzel), die zu ihrem Aufruf eine Fließkommazahl "number" erwartet und eine Fließkommazahl zurückgibt. Es ist unschwer zu erraten, was die Methode tut. Sie berechnet die Wurzel zu einer Zahl. Sicher?

Die Vermutung, was die Methode macht, begründet sich einzig auf der Namensgebung. Namen sind äußerst wichtig -- nicht nur beim Programmieren. Ein Name löst bei uns Menschen eine Menge aus. Wir verbinden mit Namen Erfahrungswerte, ordnen ihnen Bedeutung (Semantik) zu etc. Allerdings klären Namen nicht unbedingt alles ab. Akzeptiert die Methode auch negative Zahlen als Eingabe? Was passiert dann? Liefert die Methode nur die positive Lösung zu einer Wurzel oder auch die negative Lösung? (Die Wurzel aus 4 ist 2, aber auch -2 ist ein gültiges Ergebnis: -2 mal -2 = 4.)

Es gibt Techniken, Methoden wesentlich präziser zu spezifizieren als rein über die Typen, wie das z.B. bei Java, C# und vielen anderen objektorientierten Sprachen der Fall ist. Mit sogenannten Vor- und Nachbedingungen, pre-conditions und post-conditions läßt sich obiges Beispiel genauer fassen:

method float squareRoot(float: number):
pre: number >= 0
post: result >= 0 and result * result == number

Die Methode wird detailliert über die Vorbedingung, die angibt, was die Methode bei ihrem Aufruf vom Aufrufenden erwartet: "Gibst Du mir eine Fließkommazahl, die positiv ist, dann garantiere ich Dir die Einhaltung der Nachbedingung." Die Variable "result" ist vordefiniert und veweist auf den Rückgabewert der Methode, das Ergebnis. Die Methode garantiert über die Nachbedingung, dass das Ergebnis größer Null ist und mit sich selbst multipliziert gleich "number" ist.

Jetzt ist zweifelsfrei geklärt, unter welchen Bedingungen die Methode arbeitet und was sie zusichert bzw. garantiert. Dabei bleibt völlig offen, wie die Methode programmiert ist und wie sie den Wurzelwert ermittelt.

Diese Art der Spezifikation einer Methode hat einen Namen und ist als Design by Contract (DbC) bekannt; sie geht auf Betrand Meyer zurück und findet Verwendung in der von ihm entwickelten Programmiersprache Eiffel.

Leider wird DbC im Software Engineering noch viel zu wenig verwendet. Dabei ist es eine so wichtige, klarstellende und leistungsfähige Technik. Interfaces werden ähnlich schwach wie die Methode ganz oben definiert. Sie kennen das bestimmt von Java, C# oder einer anderen Programmiersprache. Die reinen Typ-Angaben spannen zwar ein Netz, innerhalb dessen die Software läuft -- und ein Compiler prüft, ob das Netz aus Typangaben auch sauber gespannt ist. Aber die Netzmaschen sind zu groß. Es können noch viele Fehlannahmen und Fehler durch das Netz fallen.

Design by Contract erlaubt es Ihnen, das Netz so engmaschig zu spannen, wie es Ihnen sinnvoll erscheint. Vielleicht hätte es bei der obigen Postcondition genügt, einzig ein positives Ergebnis zuzusichern. Man könnte das Netz aber auch engmaschiger spannen und die Genauigkeit des Ergebnisses spezifizieren (was bei endlicher Fließkomma-Arithmetik notwendig ist).

Freitag, August 25, 2006

Fuzzing

In der aktuellen c't 18/2006 wird das Fuzzing vorgestellt (Christiane Rütten: Datensalat -- Schwachstellensuche mit Fuzzing ). Das Fuzzing hat nichts mit Fuzzy-Logik zu tun. Gemeint ist eine weitgehend automatisierte Suche nach Programmfehlern. Das Fehlverhalten eines Programms versucht das Fuzzing zu provozieren durch die Generierung zufälliger Eingabewerte bis hin zur gezielten Mutation bekannter, gültiger Eingabewerte. Die Grundidee ist zwar nicht neu, aber das Fuzzing scheint erst jetzt zur Blüte zu kommen. Mit dieser Technik sind in jüngster Zeit viele Schwachstellen in allen gängigen Web-Browserns gefunden worden.

Das Fuzzing ist geeignet für Kommunikationsprotokolle jeglicher Art und natürlich auch für Datenformate. Nach dem Lesen des c't-Artikels bekomme ich geradezu Lust, es einmal selber zu probieren. Es gibt so viele Protokolle und Implementierungen, da dürfte ein Erfolgserlebnis nicht lange auf sich warten lassen. Es gibt auch schon fertige Tools, die man dazu nutzen kann.

Donnerstag, August 24, 2006

Defizite im Software Engineering

Dieses Paper "Defizite im Software Engineering" von Siegfried Wendt bringt es brillant auf den Punkt, wenn er von Präsenzwissen und der Anschauungssemantik spricht, Abstraktion von Vergröberung unterscheidet, das Problem der Arbeitsteilung beleuchtet und Ausbildungsdefizite im Software Engineering aufzeigt. So klar hat mir das noch keiner vor Augen geführt.

Der Artikel ist erschienen in Informatik-Spektrum 16/1 (1993): 34 - 38. Heidelberg: Springer, siehe hier. Siegfried Wendt ist emeritierter Professor; er war der Gründungsrektor des Hasso-Plattner-Instituts in Potsdam.

Wie alt ist die Informatik?

Wie alt ist die Informatik? 60 Jahre? 70 Jahre? 80 Jahre? 1941 baute Konrad Zuse die Z3, den wohl ersten funktionstüchtigen Computer. Zuvor entstehen in den 1930er Jahren für die Informatik so grundlegende Arbeiten wie etwa die von Alan Turing und Alonzo Church. Es scheint also hinzukommen mit den 70, 80 Jahren. So alt ist das, was wir heute als Informatik bezeichnen.

Die Prinzipien der Datenspeicherung und der Datenverarbeitung sind allerdings viel älter, sehr viel älter -- 3.5 Milliarden Jahre. Vor so langer Zeit kehrte genug Ruhe auf dem Planeten Erde ein. Das Leben konnte entstehen und gleich zu Beginn schuf die Evolution einen Code, der die Baupläne des Lebens speicherte. Wir nennen das heute den genetischen Code. Die ganzen biochemischen Prozesse, die diesen Code zu lesen verstehen und zur Produktion von Aminosäuren verwenden, sind im Grunde nichts anderes als eine biochemische Datenverarbeitungsanlage, ein Computer.

Der Code steckt ausnahmslos in jeder unserer Zellen. In einer Hautzelle ebenso wie in einer Nervenzelle. Der Mensch dürfte aus etwa 10 Trillionen Zellen bestehen (so zu lesen bei Bill Bryson: Eine kurze Geschichte von fast allem, Goldmann, 2005, S. 382) -- eine unvorstellbar große Zahl. In jeder Zelle speichert die DNA den genetischen Code. Etwas mehr als 3 Milliarden Informationseinheiten werden durch mehrere DNA-Stränge in Form von 46 Chromosomen gespeichert -- in jeder Zelle! Jede Informationseinheit wird durch 2 Bit codiert. Das gesamte menschliche Genom ließe sich also mühelos auf einem modernen 8 GBit-Stick abspeichern. Das wir davon 10 Trillionen mit uns herumtragen ist eigentlich Wahnsinn.

Die Informatik ist in meinen Augen also ziemlich alt -- steinalt. Über den genetischen Code gibt es noch interessantes zu berichten. Dazu einmal später mehr.

[Update: Die 10 Trillionen Zellen, aus denen ein Mensch bestehen soll, haben mir keine Ruhe gelassen -- die Zahl schien mir einfach zu hoch. Eine kurze Recherche hat an den Tag gebracht, dass es 10-100 Billionen sind (siehe z.B. der "Mensch in Zahlen"). Immer noch fürchertlich viele, aber das ist schon plausibler. Die Trillion ist ein typischer Übersetzungsfehler.]

JavaScript Port-Scanning

So kann man sich irren. Bislang hielt ich JavaScript für ziemlich harmlos. Der in einer Webseite eingebundene JavaScript-Code wird im Browser clientseitig ausgeführt und ermöglicht eindrucksvolle Effekte, wie es neuerdings AJAX-Applikationen demonstrieren. JavaScript bleibt dabei gewissermassen im Gefängnis der Ausführungsumgebung des Browsers eingesperrt. Schaden kann JavaScript dabei nicht anrichten. JavaScript hat z.B. keinen Zugriff auf das Dateisystem.

Aber mit JavaScript kann man dennoch durch die Gitterstäbe des Browsergefängnisses spähen! Und das sogar ziemlich weit. Es ist möglich Port-Scans durchzuführen und das Rechnernetz eines ahnungslosen Surfers auszuspähen. Die verwendete Technik dahinter hat etwas bestechendes -- einmal abgesehen davon, was man damit anrichten kann. Ich wurde darauf in einer heise-Meldung aufmerksam.

Die Idee ist so einfach wie genial: Nehmen wir im ersten Schritt die Suche nach ausspähbaren Zielen. Das Image-Objekt in JavaScript kennt ein Attribut "src" (für source, Quelle) , das einfach mit einer IP-Adresse des Ziels versehen wird. Damit wird versucht, ein Bild vom Ziel zu laden. Darüber läßt sich herausfinden, ob das Ziel existiert -- ein ping. Weitere Details finden Sie in dem verlinkten SPI-Paper. Es lohnt sich auch, den Code auf der Beispielseite zu studieren, insbesondere scanner3.js ist dabei von Interesse.

Mittwoch, August 23, 2006

Semacodes lesen

Es gibt Leute, die haben so schön einfache Ideen. Kennen Sie Semacodes? Das ist ein zweidimensionaler Barcode. Die Bahn benutzt z.B. diesen Code für Online-Tickets, auch die Post bedient sich der Semacodes. Ein quadratisches Feld aus lauter schwarzen und weißen Kästchen kodiert binär die Daten.

Was man für Semacodes benötigt, ist ein Lesegerät. Und hier ist irgendwann ein pfiffiger Mensch auf die Idee gekommen, da ja nun fast jeder mit einem Fotohandy herumläuft, die Kamera als Lesegerät zu nutzen. Ein Java-Programm reicht aus, das die Bildverarbeitung erledigt, was nicht ganz einfach, aber auch nicht so schwer ist ... fertig. Wenn Sie wollen, nehmen Sie das gleich zum Einstiegspunkt ins Web. So auch die Idee des Semapedia-Projekts.

Hier noch ein paar ähnliche Ideen dazu.

InformaTiCup 2006

Die GI, die Gesellschaft für Informatik e.V., schreibt dieses Jahr ihren 2. Wettbewerb für Studierende aus, den InformatTiCup. Die Aufgaben finde ich sehr reizvoll und eine schöne Herausforderung für kleine Teams.

Montag, August 21, 2006

Disclaimer -- rechtliche Hinweise

[Anmerkung: Wenn Sie diesen Eintrag z.B. über einen Feed erhalten, so ignorieren Sie ihn bitte. Ich habe mich entschlossen, den Disclaimer als normalen Blog-Eintrag einzustellen, da das Blogging-System von Google zur Zeit keine wirklich praktische Möglichkeit bietet, umfangreiche rechtliche Hinweise geeignet zu positionieren.]

1. Haftungsbeschränkung

Inhalte dieser Website

Der Anbieter übernimmt keine Gewähr für die Richtigkeit, Vollständigkeit und Aktualität der bereitgestellten Inhalte. Die Nutzung der Inhalte der Website erfolgt auf eigene Gefahr des Nutzers.

Externe Links

Diese Website enthält Verknüpfungen zu Websites Dritter ("externe Links"). Diese Websites unterliegen der Haftung der jeweiligen Betreiber. Der Anbieter hat bei der erstmaligen Verknüpfung der externen Links die fremden Inhalte daraufhin überprüft, ob etwaige Rechtsverstöße bestehen. Zu dem Zeitpunkt waren keine Rechtsverstöße ersichtlich. Der Anbieter hat keinerlei Einfluss auf die aktuelle und zukünftige Gestaltung und auf die Inhalte der verknüpften Seiten. Das Setzen von externen Links bedeutet nicht, dass sich der Anbieter die hinter dem Verweis oder Link liegenden Inhalte zu Eigen macht. Eine ständige Kontrolle dieser externen Links ist für den Anbieter ohne konkrete Hinweise auf Rechtsverstöße nicht zumutbar. Bei Kenntnis von Rechtsverstößen werden jedoch derartige externe Links unverzüglich gelöscht.

Kein Vertragsverhältnis

Mit der Nutzung des Blogs des Anbieters kommt keinerlei Vertragsverhältnis zwischen dem Nutzer und dem Anbieter zustande. Insofern ergeben sich auch keinerlei vertragliche oder quasivertragliche Ansprüche gegen den Anbieter.

2. Urheberrecht

Die auf dieser Website veröffentlichten Inhalte unterliegen dem deutschen Urheberrecht. Jede vom deutschen Urheberrecht nicht zugelassene Verwertung bedarf der vorherigen schriftlichen Zustimmung des Anbieters oder jeweiligen Rechteinhabers. Dies gilt insbesondere für Vervielfältigung, Bearbeitung, Übersetzung, Einspeicherung, Verarbeitung bzw. Wiedergabe von Inhalten in Datenbanken oder anderen elektronischen Medien und Systemen. Inhalte und Rechte Dritter sind dabei als solche gekennzeichnet. Die unerlaubte Vervielfältigung oder Weitergabe einzelner Inhalte oder kompletter Seiten ist nicht gestattet und strafbar. Lediglich die Herstellung von Kopien und Downloads für den persönlichen, privaten und nicht kommerziellen Gebrauch ist erlaubt.

Links zur Website des Anbieters sind jederzeit willkommen und bedürfen keiner Zustimmung durch den Anbieter der Website. Die Darstellung dieser Website in fremden Frames ist nur mit Erlaubnis zulässig.

3. Datenschutz

Durch den Besuch der Website des Anbieters können Informationen über den Zugriff (Datum, Uhrzeit, betrachtete Seite) auf dem Server gespeichert werden. Diese Daten gehören nicht zu den personenbezogenen Daten, sondern sind anonymisiert. Sie werden
ausschließlich zu statistischen Zwecken ausgewertet. Eine Weitergabe an Dritte, zu kommerziellen oder nichtkommerziellen Zwecken, findet nicht statt.

Die Verwendung der Kontaktdaten des Impressums zur gewerblichen Werbung ist ausdrücklich nicht erwünscht, es sei denn der Anbieter hatte zuvor seine schriftliche Einwilligung erteilt oder es besteht bereits eine Geschäftsbeziehung. Der Anbieter und alle auf dieser Website genannten Personen widersprechen hiermit jeder kommerziellen Verwendung und Weitergabe ihrer Daten.

4. Anwendbares Recht

Es gilt ausschließlich das maßgebliche Recht der Bundesrepublik Deutschland.

5. Besondere Nutzungsbedingungen

Soweit besondere Bedingungen für einzelne Nutzungen dieser Website von den vorgenannten Nummern 1. bis 4. abweichen, wird an entsprechender Stelle ausdrücklich darauf hingewiesen. In diesem Falle gelten im jeweiligen Einzelfall die besonderen Nutzungsbedingungen.

Quelle: Juraforum.de - Disclaimer, Urteile, Rechtsanwälte, Gesetze & Lexikon