denkspuren

How to Avoid Plagiarism?

2011-12-21T13:58:00.000+01:00

The purpose of any scientific activity is to gain insight, to understand something, to advance knowledge in a field, to make some theory applicable etc. In any case, your are standing on someone else shoulders – a statement attributed to Isaac Newton (1642-1726), who revolutionized physics. Even a genius like Newton rarely creates something from scratch. There is always a basis, a foundation, work done by other people, we built our research upon.

The issue is: Give credit where credit is due!

In science, you do so by referencing the work (books, papers, articles and – in rare cases – web sites) of others your scientific outcome (books, papers, articles and – in rare cases – web sites) relies and is built on. It is a way to say “Thank you for letting me stand on your shoulders that helped me do my work.” This might include referencing private communication. Here, I don't mean any sort of assistance you received while you were stuck, but personal contacts, which decisively influenced your research by having research-related conversations, orally, by email etc. Give credit where credit is due!

The other issue is: Be honest about your contribution, no matter how tiny it is.

Most scientific work does not create a sort of Big Bang of insights, understandings etc. Mostly, science advances in very small, more baby-like steps. That's ok and there is nothing wrong with this. Do not feel bad about your tiny contribution to science. The point is: Make absolutely clear what the state-of-the-art in your field regarding your topic is and what your contribution is no one else did before. It is about making a difference, literally speaking.

You do so by summarizing and referencing the work of others relevant to your field. For that you need to carefully revise and inspect the current state-of-the-art. Sometimes that's not easy and requires you to do a lot of work, usually systematically searching databases covering the vast knowledge of your field and reading a lot of papers. Nonetheless, it is important work. To make a difference you need to show the difference no matter how small the difference is.

Not giving credit and letting your contribution appear more impressive than it actually is is regarded as an academic fraud. It is called plagiarism.

I hope you got the point: This one-pager is not about the technicalities to reference and quote other peoples work correctly. On this topic, there are tons of resources available elsewhere. “How to avoid plagiarism?” is about creating a mindset. It is a mindset of showing respect to others and being honest about your contribution. Make a difference – but without plagiarism.

Having immersed the mindset, you might understand why academia reacts quite drastic to uncovered cases of plagiarism. Students might get exmatriculated, researchers might loose academic titles and their jobs or positions. Plagiarism is not so much about a code of ethics but putting the scientific method at risk:

We cannot advance science by cheating on each other.

Das Kanban-Board des Steve Jobs

2011-11-17T20:56:00.000+01:00

War Steve Jobs ein Anhänger der Kanban-Methode? Ja, ich glaube schon. Er hat Kanban gewissermaßen praktiziert. Anders zwar, auf seine Weise, aber es hat ihm einen Überblick über den aktuellen Arbeitsstand bei Apple samt einem Blick in die Zukunft ermöglicht.

Doch zunächst: Was ist Kanban?

Kanban ist eine der jüngsten agilen Methoden der Software-Entwicklung. Eine zentrale Stellung nimmt dabei das sogenannte „Kanban-Board“ ein. Als Kanban-Board dient z.B. eine (magnetische) Tafel oder eine Pin-Wand. Darauf finden sich Karten angeheftet. Die Karten repräsentieren Arbeitspakete; sie weisen einen Titel für das Arbeitspaket aus, den Namen der Person, die mit dem Arbeitspaket befasst ist, das Datum der Deadline etc. Das Kanban-Board ist in Bereiche unterteilt, die ein Spiegelbild des Entwicklungsprozesses sind. So gibt es Bereiche die beispielsweise "Inkubation", "Analyse", "Entwicklung", "Test" und "Abnahme" heißen. Die Verteilung der Karten in den Bereichen gibt die aktuelle Situation der Arbeitspakete in den einzelnen Arbeitsschritten wider. Das Kanban-Board ist nicht nur eine Dokumentation des Status quo, sondern dient auch als Steuerinstrument, um sicher und ohne Überlastung den Entwicklungsprozess zu durchlaufen -- und fordert dabei die stete Auseinandersetzung mit der Frage heraus "Was können wir besser machen?".

Kanban-Boards verfehlen leicht ihren Sinn und Zweck, wenn sie ein virtuelles Leben führen. Den Kanban-Vertreter(inne)n ist ein physisches Board sehr wichtig. Da soll was an der Wand hängen und für alle Beteiligten unübersehbar sein. Jeder soll über den aktuelle Arbeitsstand im Bilde sein. Das Kanban-Board soll auch Treffpunkt sein für kurze Treffen zur Abstimmung über die zu erledigende Arbeit, für den Austausch über Probleme, Rückstände oder Fortschritte.

Das Kanban-Board des Steve Jobs lag in einem Gebäudeteil auf dem Apple-Campus, im Design-Studio von Jonathan ("Jony") Ive, dem Chefdesigner von Apple. Es war weniger ein Board, als denn eine Reihe von langen Stahltischen, die in einem großen Raum aufgestellt waren. Auf den Tischen lagen echt aussehende Design-Modelle der laufenden Arbeiten. -- Das ist nachzulesen in Kapitel 25 der nach dem Tode von Jobs erschienenen Biographie "Steve Jobs" von Walter Isaacson, auf Deutsch veröffentlicht im C. Bertelsmann-Verlag. Die nachfolgenden Seitenangabe beziehen sich auf diese Ausgabe.

Jobs kam praktisch täglich in das Design-Studio von Ive und hatte dabei seine "Kanban-Tische" direkt im Blick. Er sah dort alle in Planung befindlichen Produkte und "konnte direkt erspüren, ob und wie sie in die Strategie von Apple hineinpassten. Er konnte mit seinen Fingern das in Entwicklung befindliche Design befühlen und begreifen." (S.405) Oder, um Ive sprechen zu lassen: "Dieser große Raum ist der einzige Ort in der ganzen Firma, wo man sich einfach nur umzuschauen braucht und alles sieht, was wir gerade in Arbeit haben." (S. 406)

Genau das ist die Funktion eines Kanban-Boards! Steve Jobs hatte von Software-Entwicklung und Hardware-Bau kaum Ahnung -- ganz im Gegensatz zu Bill Gates. Bei ihm war das Design, das Aussehen, die Formgebung seiner Produkte derart zentral, dass er alles dem Design unterwarf und das alles mit dem Design verwoben war. Mit dem Design began und endete alles. Insofern ist es nur konsequent, "Kanban-Tische" im Fall von Jobs zu haben. Für einen Außenstehenden standen dort "nur" Design-Modelle. Für ihn manifestierte sich in den Design-Modelle der gesamte Entwicklungsstand seiner Produkte. Auf einen Blick! Was für ein großartiges Management-Tool!

Über den Wolken muss die Freiheit wohl grenzenlos sein ...

2011-11-09T22:55:00.000+01:00

In einer Wolke kann man sich der schönen Illusion hingeben, man habe so etwas wie Privatsphäre. Ein paar Meter weit kann man sehen, gerade genug, um sich selbst nicht aus dem Auge zu verlieren. Einem Außenstehenden versperrt der Dunst den Blick.

Welch wunderbare Illusion!

Ich nutze z.B. Google Docs. Ein paar Texte und Tabellen sind unter meinem Account abgelegt -- irgendwo in der Datenwolke, der Cloud von Google. Gerne gebe ich mich dem Glauben hin, meine Daten seien dort "privat" und "sicher". Vielleicht liegen Ihre Daten gleich nebenan, nur ein kleines winziges Bisschen entfernt auf der Festplatte im Google-Rechenzentrum. Wir sehen einander nur nicht, im Nebel der Cloud.

Machen wir uns nichts vor: natürlich ist der Nebel eine Illusion. Google sieht alles. Man analysiert dort fleißig alle nur verfügbaren Daten. Meine Daten ebenso wie Ihre Daten. Für Google gibt es keinen Nebel. Google sieht alle Daten in der Wolke, die Spannendes an Informationen herzugeben weiß. Und sollte irgendwo, irgendwann eine Panne passieren, so lichtet sich möglicherweise der Nebelschleier für einen Moment -- und Ihre und meine Daten bieten sich der Welt feil, und wir müssen uns der Peinlichkeit der Offenbarung des Privaten stellen.

Wissen Sie, was ich gerne möchte? Über den Wolken fliegen. Auch wenn es in diesen luftigen Höhen eiskalt ist, der Blick auf sonnengeflutete Wolkenlandschaften entschädigt alles. Durch eine Wolke fliegen ist uninteressant. Aber über den Wolken, da ist die Freiheit grenzenlos ...

Grenzlose Freiheit ist, wenn jeder in der Cloud prinzipiell meine Daten sehen könnte -- aber nichts davon hätte, weil alles verschlüsselt ist. Grenzenlose Freiheit ist, wenn Google (oder welcher Clouddienst auch immer) meine Daten nicht zu interpretieren wüsste. Verschlüsselt eben. Auf dem Client, im Browser, in der App, dort würde ent- und verschlüsselt werden. Niemals jedoch würde auch nur ein einziges privates Bit meine Rechner oder mein Smartphone verlassen, ohne vor den neugierigen Blicken Dritter wirklich geschützt zu sein.

Warum sollte uns irgendjemand diese Freiheit schenken? Wohl kaum einer! Die Freiheit über den Wolken, die Freiheit über der Cloud ist wirtschaftlich uninteressant. Grenzenlose Freiheit hat nur der, der in der Cloud keine Privatsphäre kennt oder will. Grenzenlos frei ist auch der, der unter der Wolke lebt -- und ohne den Datenrummel in der Cloud auskommt.

Von der Leichtigkeit, ein Startup zu gründen

2011-11-02T13:02:00.000+01:00

Am vergangenen Wochenende fand der Entrepreneuship Summit in Berlin statt. Etwa 1200 Teilnehmer füllten den Henry-Ford-Bau der Freien Universität Berlin. Vorträge wechselten sich ab mit Impulsgruppen. Ging es am Samstag noch etwas zaghaft zu, kam am Sonntag mehr Bewegung und Stimmung auf. Man hatte sich am Vortag zaghaft beschnuppert, orientiert und allmählich in ein Gefühl gemeinschaftlicher Absichten eingefunden. So "störte" eine kleine Gruppe den Programmablauf am Sonntagmorgen und rief zum "Funky Business" auf; man wolle sich in Berlin-Tempelhof zusammentun und ein kleines Silicon Valley aufbauen -- nur besser. Sowas, so mein spontaner Gedanke, ist eben nur in einer Großstadt möglich. Und vielleicht sind die Berliner sogar experimentierfreudiger als andere Großstädter; vielleicht eben auch williger, das Scheitern mit in Kauf zu nehmen.

Veranstaltet hat den Summit die Stiftung Entrepreneurship. Dahinter steht als treibende Kraft Prof. Dr. Günter Faltin. Er hat mit seinen Studierenden das Unternehmertum real in der freien Wildbahn des Marktes ausprobiert. Herausgekommen ist dabei die sogenannte Teekampagne, die sich rühmen darf, den Teemarkt neu aufgemischt zu haben. Günter Faltin hat das und seine Gedanken zum Unternehmertum festgehalten in dem Buch "Kopf schlägt Kapital". Ein absolut lesenswertes Buch! Seine Art des "Entrepreneurship Design" prägte die Veranstaltung durch und durch. Es ist die neue "Leichtigkeit des Unternehmertums", mit der man von einer Idee zu einer Unternehmensgründung kommt. Heute lässt sich eine Vielzahl von Komponenten "einkaufen". Es ist nicht mehr nötig ein Büro zu haben, die Buchhaltung zu führen, selbst Produktionsanlagen zu betreiben, Bestellung und Versand in die Hand zu nehmen. Es genügt, sich aus diesen Komponenten das eigene Unternehmen masszuschneidern. Man muss nicht mehr Alleskönner sein. Man kann sich ganz auf das konzentrieren, was den Kern eines Unternehmens ausmacht: Die Geschäftsidee, die Konzeption der Idee und ihre Ausrichtung am Markt.

Den einen oder anderen mag das erinnern an die "4-Hour Workweek" ("Die 4-Stunden Arbeitswoche") von Tim Ferriss. Er vertritt eine ähnlich autonome, komponentenbasierte Unternehmensarchitektur, in Teilen sogar radikaler als Prof. Faltin. So war es denn kein Zufalls, dass ein Vortrag eine Videoeinspielung war, in der Prof. Faltin Tim Ferriss interviewte. Bedauerlicherweise war die noch am Samstagmorgen angekündigte Video-Liveschaltung mit Ferriss nicht zustande gekommen.

Ich kann nicht aus eigener Erfahrung mitreden. Aber es hat in der Tat den Anschein, als sei es nie zuvor so leicht und risikoarm gewesen, ein Unternehmen zu gründen. Manch junger Unternehmer setzt sein Unternehmenskonzept so konsequent auf, dass Kosten erst entstehen, wenn Kunden das Produkt bestellen oder die Dienstleistung nutzen. Das ist ein faszinierendes Extrem. Der Gründer der Laktasekampagne (der Name deutet es an, die Teekampagne war das Vorbild) Martin Lipsdorf sagte, er habe sein Unternehmen mit 700€ an den Start gebracht. Hui! Das hat was, oder?

Sascha Lobo -- wer ihn nicht kennt: eine auffallend unauffällige Erscheinung, wäre da nicht die rote Irokesen-Frisur -- berichtete als selbsternannter "Scheiterexperte" vom Scheitern. Auch das war also Thema. So leicht es heutzutage sein mag, ein Startup zu gründen, so leicht ist auch das Scheitern geworden. Es ist ja nicht gleichzeitig leichter geworden, sich auf dem Markt zu behaupten und in einer Nische einzunisten. "Fail often and adapt", das könnte man als Botschaft da raushören. (Ein Buchtipp am Rande: "Adapt: Why Success Always Starts with Failure" von Tim Harford.) Die Lernzyklen sind kürzer geworden. Man kann sich allmählich "warmgründen", bis es klappt! Und man sollte sich ohnehin darauf einstellen, die Geschäftsidee immer wieder anzupassen und zu tunen. Das berichteten einige Gründer in einer Impulsgruppe.

Wer sich Mut holen möchte zum Gründen: Ich bin sicher, im Oktober 2012 findet wieder ein Entrepreneurship Summit in Berlin statt. Einfach hinfahren und Erfahrungen austauschen. Ich habe 75€ Teilnahmegebühr bezahlt, der Betrag sollte für künftige Entrepreneure erschwinglich sein.

P.S.: An meine Zunft der Softwareschrauber: Die "School of Design Thinking" des Hasso Plattner Instituts (HPI) aus Potsdam war mit einem Vortrag zu "Enabling Innovation with Design Thinking" vertreten. Da geht es zwar nicht nur um Innovationen mit Software. Aber wenn Software eine Rolle spielt, dann macht es kaum einen Unterschied. Da werden "Prototypen" mit Stift und Papier, Knete, Playmobil und Lego realisiert. Anders lässt sich die prototypische Entwicklung eines Produkts an einem Tag gar nicht durchziehen. Dahinter steckt Methode. Kurze Zyklen, das Scheitern inbegriffen, sollen eine Innovation zu einem nützlichen, marktfähigen Produkt reifen lassen. Das Ganze hat mich sehr neugierig gemacht. Eine "School of Design Thinking" an der Hochschule Heilbronn, das wäre mal was ... fehlt uns doch nur ein kapitalkräftiger Förderer! Das "Design Thinking" ist sehr personalintensiv in der Betreuung der studentischen Gruppen.

Ein Blick in die Zukunft

2011-10-30T00:21:00.000+02:00

Was hat einem ein Zukunftsforscher zu erzählen? Am Dienstag, den 25. Oktober, hielt Lars Thomsen an der Hochschule Heilbronn einen Vortrag über die Zukunft. 520 Wochen, sprich 10 Jahre, ließ er uns in die Zukunft schauen. Thomsen hatte aufmerksame Zuhörer. Die Aula war voll. Etwas mehr als eine Stunde hörten alle gebannt einem Vortrag zu, der ohne eine einzige Folie auskam. Ohne Zweifel ist Thomsen ein geübter Redner, der sein Thema ausgezeichnet zu vermitteln und zu verpacken weiß!

Worüber er sprach? Sie hätten dabei sein sollen. Ich versuche eine grobe Zusammenfassung von vier "Megatrends", wie Thomsen sie nennt:

Die Rechenleistung von Computern wird sich weiterhin jährlich verdoppeln. In 10 Jahren sind die Desktops, Laptops, Netbooks, Tabs und Smartphones 1000x leistungsfähiger als die heutigen Geräte. Es wird das "Ende der Dummheit" einläuten. Computer werden uns ganz neue Helferlein sein, da sie beginnen, uns zu verstehen. Sie werden EMails mitlesen, eingehende Nachrichten geeignet sortieren, Anfragen teils selbstständig beantworten. Das brauchen wir dringend. Jedes Jahr steigt der Mailverkehr um 18%. Wir Menschen sind schon jetzt mit der Datenflut überfordert. Es wird mehr und mehr Programme geben, die ein primitives Verständnis haben von dem, was wir tun, was unsere Gewohnheiten und Wünsche sind. Und die werden dieses Verständnis nutzen, uns zu helfen.

Unser Umgang mit Energie wird sich vollkommen verändern -- schon aus reiner Notwendigkeit. Die fossilen Rohstoffe sind begrenzt. Schon immer hat es auf unserem Planeten ein Einlagern und Freigeben von Kohlenstoff gegeben. Das, was der Mensch jedoch an CO2 in kürzester Zeit auf dem Planeten freigesetzt hat, ist wohl einmalig in der Geschichte der Erde. Klimatische Grenzen werden sich verschieben, neue Vegetationsgebiete kommen auf. Der Umstieg auf alternative Formen der Energiegewinnung und -speicherung ist unausweichlich. In China werden Solarmodule produziert, die Preise für Photovoltaik sind dadurch allein in der Zeit von Januar bis September um 22% gefallen -- ein sich fortsetzender Trend. Gut möglich: Künftig mögen die Solarzellen billiger sein als Dachziegel. Die Speicherung von Energie wird in Form eines Smartgrids gelöst werden. Die intelligente, dezentrale Organisation von Energiezu- und abflüssen im Energienetz wird die zentrale Energieversorgung ablösen.

2016 wird ein Elektroauto so viel kosten wie ein Benziner. Elektroautos sind dem Treibstoffwagen in vielerlei Hinsicht überlegen. Ein Blick unter die Motorhaube offenbart eine Boardelektronik, die kaum mehr als drei Coladosen einnimmt. Die Bodenplatte wird mit Akkus aufgefüllt, was zudem den Schwerpunkt extrem tief legt und exzellente Fahreigenschaften garantiert. Schon jetzt sieht ein Porsche alt aus im Sprint gegen moderne Elektroautos. Das derzeit kostentreibende Element im Elektroauto sind die Akkus. Doch hier macht sich ein Preisverfall von 12% pro Jahr bemerkbar. Noch in diesem Jahrzehnt wird das Auto mit Verbrennungsmotor nur noch etwas für Enthusiasten sein. Wer das Röhren in seinen Ohren höhren will, wer das Zittern eines aufdrehendes Motors spüren möchte, der muss sich als Nostalgiker einen teuren Benziner oder Diesel leisten -- vermutlich als Zweit- oder Drittwagen.

Die Medizin hat längst nicht ihr Potenzial ausgereizt. Sie lässt sich reduzieren auf das "Schneiden und Zusammenflicken" und den Einsatz von Chemie. Es kommen derzeit im Wesentlichen 37 Grundsubstanzen in Medikamenten zum Einsatz. Der Rest ist Hoffnung. Die "Medizin 2.0" baut auf den Selbstheilungskräften des Genoms auf. Die Menschen haben es gelernt, die 770MB Erbinformation, die jede Zelle mit sich herumträgt, auszulesen. Nun geht es darum, die darüber kodierten Eigenschaften und Aubläufe gezielt zu nutzen. Ein Beispiel: Eine Firma schenkt schwerhörigen Menschen ihr Gehör zurück. Nicht durch ein Hörgerät! Die feinen Häarchen im Ohr, die für das Hören gebraucht werden, werden wieder zum Wachstum stimuliert. Dazu wird ein Stopp-Gen, das unbegrenztes Haarwachstum verhindert, gezielt ausgeschalter und später wieder eingeschaltet. Mit den nachgewachsenen Harchen hört es sich prima. Viele von uns durfen auf solche medizinischen Fortschritte hoffen. Die Lebenserwartung unter den lebenden Menschen (nicht also erst in einer späteren Generation), steigt pro Jahr um 3-4 Monaten. Wer künftig steinalt wird, wird sich gerne von der Medizin "frisch" halten lassen.

Spannend, nicht wahr?! Thomsen hat noch eine Menge mehr erzählt. Er sprach vom Versagen des Geldes, aber auch von dem, was uns Menschen auszeichnet: Wir sind soziale Wesen, das wird sich nicht ändern. Vermutlich werden wir neue Wirtschafts- und Arbeitsformen ausprobieren. Und was Studenten gerne hören mögen: Man wird sich später auf dem Berufsmarkt um sie reißen. Es wird einen Mangel an (aus)gebildeten Menschen geben. Selbst Länder wie China werden aggressiv Fachkräfte aus dem Ausland anheuern, um ihren Hunger nach wirtschaftlichen Wachstum zu stillen.

Ich habe keine Ahnung, ob sich die Zukunft so entwickeln wird. Vieles, was Thomsen erzählt, wirkt erschreckend plausibel. Wenn Sie diesen Blogbeitrag in 10 Jahren, also im Jahr 2021 lesen, dann werden Sie wissen, ob Thomsen nicht nur ein hervorragender Redner, sondern auch ein wirklich guter Zukunftsforscher ist.

Clojure per Kommandozeile in Windows: CLASSPATH-Setting

2011-04-19T22:13:00.000+02:00

Möchte man die Clojure-REPL interaktiv unter Windows nutzen, helfen gut gesetzte Umgebungsvariablen und ein einzeiliges Batch-File ungemein. Schmerzfrei wird der Dialog mit Clojure aber erst dann, wenn der CLASSPATH der JVM auf die nötigen jar-Files gesetzt ist. Ist auch das Verzeichnis der interaktiven Konsolen-Session dabei, funktioniert auch z.B. ein load-Aufruf aus Clojure heraus, um die dort befindlichen clj-Dateien zu laden.

Der folgende Einzeiler ruft die Clojure-REPL auf. Die Umgebungsvariable PATH muss das Verzeichnis mit java.exe beinhalten, die Umgebungsvariable CLOJURE sei auf das aktuelle Clojure-Verzeichnis gesetzt:

java -cp %CLOJURE%\*;*; clojure.main %1 %2 %3 %4 %5 %6 %7 %8

Zur Erläuterung: Das Wildcardzeichen "*" sorgt dafür, dass alle jar-Files im CLOJURE-Verzeichnis in den CLASSPATH aufgenommen werden, ebenso wie mit dem zweiten Wildcard "*" alle jar-Files im aktuellen Verzeichnis. Hinweis: Ohne das Semikolon als abschließendes Trennzeichen funktioniert das Wildcard-Zeichen nicht.

Complexity, Size and Focus

2010-10-07T11:24:00.000+02:00

Why is it so hard to understand software? Or to put it more to the point: What makes it so hard to write understandable software? This question is the driving theme of this article: the quest to uncover techniques of complexitiy management that go beyond established principles of software engineering such as information hiding and modularization and which are unbound to specific paradigms like object-orientation or functional programming.

For that reason I studied two kinds of software systems in depth: telecommunication systems, modeling and programming languages. I did so for two reasons: First, telecommunication systems are among the oldest, largest and most successful systems. They are highly reliable, roboust and scalable. What are their key design principles that make them stand such demanding requirements? Second, each modeling and programming language is its creators attempt to provide a set of language conceptions to address and manage complexity. A language – be it a programming or modeling language – is, so to speak, the destillate of another persons opinion, experience and expert knowledge about how to write „better“ programs or how to design „better“ software.

My observation and claim is that two factors are most responsible for what I capture under the term „complexity“: size and focus. Size refers to number of lines of code and number of features, focus refers to intellectual comprehensibility.

The code basis of todays operating systems goes into million lines of code. Recently, Linux was reported to reach 10 million lines of code. Windows 7 is estimated to be of the same size. These numbers do not include application software typically shipped with these operating systems. Applications such as OpenOffice also count some ten million lines of code. The latest release of the Eclipse IDE (Integrated Development Environment), version 3.6, counts 33 million lines of codes. Since there is a relation between code size and the number of faults to be expected per 1000 lines of code (numbers vary from 25 to about 1 error per 1000 lines of code), such huge-sized software is highly interspersed with faults.

Another dimension of size is number of features: Todays software is extremely feature-rich. A whole industry of education and consulting is build around teaching and configuring the use of software, which is too feature-rich to use out of the box. Office applications and SAP R5 come into mind. This observation also refers to programming languages used to build these systems. The most spreaded languages are C, C++, C# and Java. Java, for instance, is such feature-rich that it requires a programmer to learn and understand a language specification of almost 700 pages of text. It is no exaggeration that most Java programmers only master a personalized subset of these 700 pages.

The sheer size of code of todays software makes it impossible for a software developer to understand software systems in its entirety. The sheer volume of code is overwhelming und impossible to master. It is a valid question whether this size complexitiy is inherent to the problem domain or a symptom of a certain design philosophy that has become main stream and is manifested in lanaguages like C(++), C# and Java. Alternative approaches indicate the latter: TeX, a typesetting system designed in the 1980s by Donald E. Knuth, is still top-class in its typesetting quality and widely spread in academia and among textbook authors; many publishers prefer manuscripts produced in TeX. TeX is based on a language kernel with primitives for typesetting and it can be easily extended via a powerful macro system. Besides bug fixes, the TeX kernel has been kept stable for almost 30 years now. Nonetheless, the system adapted constantly via its macro system with grwoing demands and new technologies coming up. Another example is Postscript.

There are also alternatives to feature-rich languages like C(++), C# and Java. Kernel-based languages like Lisp/Scheme, Prolog, Forth and Smalltalk are easy to understand. Their implementations fit on some few pages of code. They easily incorporated new paradigms and trends (e.g. object-orientation and aspect-orientation) due to their extensibility.

Another aspect of complexitiy management is focus. From a cognitive viewpoint, complexity is a human beings incapability to intellectually manage information which is (a) too much and (b) spread in time and space. It is a combination of information overload and a lack of recognizing temporal and/or spacial patterns. Two techniques address these issues: one is condensation, the other is localization. Condensation comes in two forms: abstraction building and modeling. Abstraction building can be reversed by refinement without loss of information; modeling condenses at the price of loosing information thereby simplifying things. A simplification introduces faults and errors; an oversimplification overstresses the acceptance of incorrectness. Localization is a technique to bring together (to bring in focus), what was spread and distributed before and thus appeared to be unrelated and unconnected. To concentrate on a problem (domain) means to put it in focus, to dissolve and localize relevant parts and highlight their relations, which might be spatial (i.e. structural) and/or temporal (behavioral). The act of localization establishes a new context, a new perspective or point of view, a new universe of discourse, a new domain.

In software engineering, several techniques have been developed for abstraction and localization. Among many other ideas we just would like to mention abstract data types, object-orientation and meta-object protocols, aspect-orientation, meta-programming and macro systems. All these approaches have one thing in common: they try to rearrange parts in a software description, they try to bring in focus, they localize. We call the flexibility of a language to adapt to different localization needs its expressiveness.

Interestingly, the other aspect of condensation, modeling, is rarely used in a systematic manner in software engineering with a clear understanding of the degree of incorrection and impreciseness introduced with a model. This understanding of modeling differs significantly from the common interpretation of the term. Typically, modeling is more meant to be a form of visual programming or a means to visually create code templates.

The assumption is that small size systems are a natural consequence of systems designed with extremely expressive languages. Empirical data point into this direction: Systems developed in expressive languages like Lisp/Scheme, Prolog, Python or Ruby argue with code size reduction compared to languages like C, C++, C# and Java. These languages (Lisp etc.) are quite expressive, whereas C and others strictly separate the language from the problem domain. If a certain localization need is not covered by language features, frameworks need to be designed and implemented to simulate expressiveness.

I think that software engineering has yet underestimated the use and the value of highly expressive languages and highly extensible kernel-based systems.

Superhacker

2010-05-14T07:39:00.002+02:00

Es gibt dieses wunderbare Bild der Hacker! Ich meine die Geeks, nicht die Kriminellen. Hacker leben mit dem Computer, sie scheinen eins mit ihm zu sein. Computer und Hacker gehen eine Symbiose ein. Hacken ist Leben, Leben ist Hacken. Menschen und soziale Kontakte sind eine wunderbare Sache -- sofern man mit ihnen im Chat oder in anderen virtuellen Welten kommuniziert und sie dort trifft. Hacker sind mindestens 10x produktiver als normal sterbliche Programmierer. Und Hacker sind nicht nur produktiver, ihr Code scheint nicht von dieser Welt zu sein. Kein Mensch versteht die Kryptik und die Gedankengänge im Code eines Hackers.

Kurzum, wir bewundern die Hacker. Ein bissel hätten wir gerne von ihnen "vererbt" bekommen, wir, denen das Programmieren nicht ganz so locker von der Hand geht.

Gibt es die Hacker überhaupt? Oder sind sie ein Mythos? Ja und nein.

Es gibt Menschen, die das Bedienen ihrer Maschinen gründlich erlernt haben. Die 1000 Tastenkürzel kennen, mit Emacs arbeiten, alle Unix-Befehle kennen und im 10 Finger-System schreiben. Die Arbeit geht rasend von statten, wenn man diesen Tastaturakrobaten zuschaut. Fenster wechseln so schnell, das man glauben könnte, der Monitor habe einen Wackelkontakt. Das so ziemlich überflüssigste Interface für sie ist die Maus.

Dann gibt es welche, die mit den vielen kleinen Helferlein und Tools umzugehen wissen. Da wird Windows rasch gescripted, ein Makro programmiert, ein Makefile konfiguriert, im Hintergrund laufen inkrementelle Backups. Das sind die Automatisierer. Denn wozu von Hand machen, was eine Maschine besser, alleine und vor allem viel schneller erledigen kann. Für sie ist Linux die Idealwelt. Aber sie ziehen auch eine Freude daraus, dass sie dieselbe Magie auch mit Windows hinkriegen. Und mache von ihnen haben sich auf die Zauberkunst mit Excel spezialisiert.

Und es gibt die, die das Programmieren als Handwerk gelernt und verinnerlicht haben. Design Patterns sind für diese Menschen ein Klacks. Standardalgorithmen und -probleme können auf Zuruf während eines Telefonats runtergezimmert werden. Die Handwerker kennen ihre Bibliotheken und APIs in- und auswendig. Für sie ist Eclipse eine mächtige Schaltzentrale und die vielen offenen Fenster sind auf mindestens zwei Riesenmonitore verteilt. Sie haben mindestens genauso viel im Blick wie Börsenmarkler.

Kennen Sie die Sammler? Sie sammeln Programmiersprachen und konzentrieren sich natürlich auf die exotischen Exemplare. Java und C# hat schließlich jeder. Sie Sammler sind oft auch liebenswerte Spinner. Sie können einem stundenlang begeisterte Vorträge über ihre neueste Entdeckung halten. Die neueste Sprache ist immer eine Steigerung zu dem, was letzten Monat noch aktuell war. Sie schreiben immerzu kleine Programme, manchmal auch etwas größere, und zwar in Sprachen, die keiner versteht. Aber sie kennen sich aus. Im Grunde gibt es für sie keine Probleme, sondern nur falsche Programmiersprachen.

Tastaturakrobaten, Automatisierer, Programmierhandwerker, Sammler -- sie alle können etwas, was der Otto Normal-Programmierer nicht kann. Es sind Künstler, Handwerker, Besessene. Sie sind zweifelsohne jeweils auf ihre Art produktiver. Sie lösen Probleme geschickter, schneller und überzeugender als Andere. Manchmal nennen wir sie Hacker, besonders dann, wenn sie mehrere dieser Fähigkeiten vereinen. Aber sind das wirklich die Hacker?

Ich habe ein ganz anderes Bild vom Hacker; ich will sie mal "Superhacker" nennen. Manche von ihnen sind Tastaturakrobaten, manche Automatisierer, alle beherrschen das Programmierhandwerk eher besser als schlecht, und einige sammeln Programmiersprachen. Aber keines dieser Talente ist entscheidend. Superhacker denken! Das ist ihr eigentliches Talent, ihre eigentliche Stärke. Superhacker durchleuchten Probleme von verschiedenen Perspektiven. Sie skizzieren mögliche Lösungen. Diskutieren Ansätze und Vorgehensweisen. Sie brauchen dafür ihre Zeit. Manchmal findet sich eine elegante Problemlösung in einer exotischen Sprache begründet. Aber von Sprachen sind diese Menschen im Prinzip unabhängig. Sie kombinieren für eine Lösung Altbekanntes und Neues.

Und das Ergebnis: Brillant kurzer Code. Code, der verständlich ist. Code, der verblüfft ob seiner Offensichtlichkeit. Code, dessen Genialität seine Einfachkeit ist. Code, der wartbar ist und andere Designer und Software-Entwickler inspiriert. Code, der Zukunft hat und klare Entscheidungen für ein Design trifft.

Die Superhacker sind in der Regel nicht mehr produktiv in ihrem Tagesoutput als andere Software-Entwickler auch -- auch wenn es solche Wunder-Hacker geben mag. Das Geheimnis ihrer Produktivität schlägt sich nieder im Einfluss, den sie auf andere Entwickler ausüben. Das Geheimnis ihrer Produktivität zeigt sich in der überdurchschnittlichen Qualitätssteigerung der durch sie beeinflussten Produkte. Sie sichern Märkte. Sie sichern Zukunft.

Die Superhacker, die Denker, sind Menschen, deren Produktivität deshalb hochgradig skaliert. Über den Umweg des Einflusses auf andere steigern sie die Produktivität in einem Unternehmen vielleicht um ein, zwei, drei oder vielleicht sogar einmal fünf Prozentpunkte, im Glücksfall um 10 Prozent. Ähnliches mag für die Qualitätssicherung gelten. Darüber tragen Sie zum Umsatz und Gewinn eines Unternehmens in einem Ausmaß bei, der keinen Vergleich findet zum Einfluss eines "Normalprogrammierers". Die normalen Hacker steigern ihre Produktivität -- nicht die der anderen!

Übrigens gibt es eine etwas seriösere Bezeichnung für Superhacker: Man nennt sie auch Softwarearchitekten.

Factor @ Heilbronn University

2010-01-28T13:28:00.013+01:00

It was an experiment -- and it went much better than I had imagined: I used Factor (a concatenative programming language) as the subject of study in a project week at Heilbronn University in a course called "Software Engineering of Complex Systems" (SECS). Maybe we are the first university in the world, where concatenative languages in general and Factor in specific are used and studied. Factor is the most mature concatenative programming language around. Its creator, Slava Pestov, and some few developers have done an excellent job.

Why concatenative programming? Why Factor?

Over the years I experimented with a lot of different languages and approaches. I ran experiments using Python, Scheme and also Prolog in my course. It turned out that I found myself mainly teaching how to program in Python, Scheme or Prolog (which still is something valuable for the students) instead of covering my main issue of concern: mastering complexity. In another approach I used XML as a tool for lightweight modeling to explore and study some techniques. The approach is innovative and still worth to be developed further but I wasn't satisfied.

My goal in the course "Software Engineering of Complex Systems" is to present and discuss practical techniques to conquer complexity in software systems. I did and still do a lot of research in this area. To make a long story short, I have come to the conclusion that Language-Driven Software Engineering (LDSE) is a very powerful and promising approach to conquer complexity. It's more than creating and using Domain Specific Languages (DSLs). It's consistently designing and creating languages throughout all levels and layers of a software implementation.

During my research I stumbled across Joy and Factor and learned about the concatenative paradigm. A series of excellent articles written by Manfred von Thun, creator of Joy, taught me the theory and fundamentals of concatenative languages. Factor, Slava Pestov's implementation of a practical concatenative language, turned out to be the best showcase I could think of: Factor is almost self-contained and extends itself by creating vocabularies of words using other vocabularies of words. Programs in Factor are written the very same style. Factor is seeing LDSE in action. I realized that it's the concatenative paradigm which enforces you to design software from a language-driven point of view.

How did the course go?

First I discussed the issue of complexity in software systems. Before I used Factor in the project week, I introduced the concatenative paradigm in the course. I presented it's mathematical foundation and used a pattern-driven approach to define the semantics of concatenative words as syntactic transformations. Finally, we defined a simplified grammar of Factor which we extended to cover pattern matching and template instantiation. All this served the purpose to smoothly prepare the ground for Factor. We also reflected and discussed a lot about what complexity is about and how it can be managed.

During the project week, my students (about 30 persons) worked with Factor four out of five days almost 8 hours per day. For my students it was full contact combat with an almost unknown programming paradigm and an exotic language. But they did really well. On day 1, the students worked through the introductory material supplied with Factor. On day 2, we studied types and object-orientation in Factor. On day 3, parsing and macros were studied in Factor. For these two days, the students worked with tutorials and worked their way through a number of exercise, which required them to write tiny programs in Factor to pass unit tests. On day 4, we worked on a topic unrelated to Factor. On day 5, two students thoroughly presented their project work, a real-world application in Factor, they had done in another course in the previous semester. We concluded the week with discussing and reflecting Factor's capabilities and the power of the concatenative paradigm in general.

Before I forget to mentioned it: Tim, research assistant in the software engineering department and PhD student, created the tutorials and the exercises and helped out a lot in class. Without him, the course wouldn't have been possible!

The students enjoyed the week very much. The evaluation of the course shows that they liked getting a new and different viewpoint on software development, object-orientation, parsing etc. They definitely realized and experienced that Factor helps them becoming better software engineers although Java is their main language.

Isn't Facor, aren't concatenative languages too esoteric to be useful?

Yes and no. There is no question that Factor is a niche language no one in industry shows interest for (besides Google, so far ;-). There might be some companies out there which use Forth and might be open for "concatenative thinking". However, even though the concatenative paradigm is almost unknown, concatenative languages are functional languages and functional languages are gaining in popularity. There's little doubt that learning functional programming broadens your scope and complements a student's skill set.

The fun part is that the concatenative approach to functional programming is much more simpler than the lambda calculus, which is traditionally taught. The math is simple and no intellectual barrier and formal transformations are easy to understand since there are no variable bindings and nesting scopes. Key concepts are stripped to their bare minimum. Did you ever try to explain the idea of continuations in Scheme? You might spend a good amount of time explaining continuations and running exercises. It's not unlikely that some students still don't get it. Continuations seem to be an extremely complex thing and appear to be somewhat mystical. In Factor, and in concatenative languages in general, continuations are a triviality! In principle, it's a snapshot of the data and the call stack. No big deal, since you juggle around with both stacks all the time. Are generic functions a specialty of CLOS. They come out naturally in a pattern-based approach to define concatenative words.

But my point goes beyond that. The way you create abstractions and refactor your programs in a concatenative language enforces you to continuously reflect about your design decisions. You have an enormous freedom of how you shape and constrain the design space of options at hand. It lets you think about words and vocabularies of words. It is thinking about creating and using languages. It combines software engineering and software programming in a way I haven't experienced in any other paradigm. That's why I introduced Factor in my course: You will start to engineer software, you'll explore new ways of creating abstractions and design frameworks.

Factor itself is an excellent case study for this approach. Factor starts from a relatively small kernel (which I -- admittedly -- haven't cleanly dissected, yet) and then consequently adds feature by feature with using Factor to extend Factor. A neat concatenative kernel turns itself into a powerful piece of software using a language-driven approach right from the start. Slava Pestov proves that this approach does result in a fast, interactive and highly reflective language. For me, Factor is a masterpiece of software engineering! It's definitely worth studying it!

Conclusion

What I experienced over the last two semesters is that some students become deeply attracted by Factor. Even if not, almost all students sense that there is a new world worth entering that takes them to a new level of understanding. It broadens their scope and skill set. Eventually, they'll leave the concatenative path for doing their Java/C# assignments in other courses or when they do some programming for a living. Still, I'm convinced that concatenative programming has an impact that lasts.

Do I sound too enthusiastic? Possibly, but I prefer to teach things I'm enthusiastic about! I'm still a student regarding the concatenative paradigm myself, I'm learning a lot each and every day about this paradigm. And one is for sure: I will continue to use Factor in the next semesters.

---
Update (2010-01-29) I received quite some requests to publish the Factor material we produced for the project week. The material is in German. Comments, ideas, corrections and improvements are welcome!

Day 1 - Intro: Getting started (Factor docu), Q&As

Day 2 - Object-Orientation: Intro, Tutorial, Q&As

Day 3 - Parsing and Macros: Intro, Tutorial, Q&As

Day 4 - Unrelated Topic:

Day 5 - Real-World Application in Factor: Presentation, Report, Sources (thanks to Andreas Maier and Marcel Steinle)

By the way, Daniel Ehrenberg indicated that Heilbronn University is not the first using Factor in a course. That's great to hear. Factor starts spreading!

In case you are interested in our research on concatenative languages, there is a paper available: "Concatenative Programming: An Overlooked Paradigm in Functional Programming".

Scripting Languages

2010-01-21T18:48:00.002+01:00

Recently, I had an interesting discussion about "What's the distinguishing feature of so-called scripting languages?" We easily agreed on calling Python, Ruby, Groovy, Tcl, Perl etc. as scripting languages. But then the trouble started: What distinguishes Python, Ruby etc. from Java, C#, C++ and similar languages? Is it dynamic typing? Are they more introspective? Isn't it so that meta-programming is no difficulty at all with scripting languages?

Some whisper that a Python or Ruby programmer is as much as 2-5 times more productive than a Java/C# programmer. As a matter of fact, programs written in so-called scripting languages tend to be significantly shorter than their "unscripted" counterparts. Such a discussion typically moves over into an almost religious debate about static and dynamic typing. Programs in Python and Ruby might be shorter but they are unsafe because of dynamic typing. Static typing is the way to go for large programs being developed with many developers -- say the Java and C# advocates. And they have a point. Write unit tests, say the Pythoneers and Rubyists, which you are supposed to write anyhow. As a side-effect, your unit tests easily uncover all typing related bugs. You're not better off with a statically typed language, they say.

While such discussions are interesting our main question remains unanswered. What's the distinguishing feature of scripting languages? Most scripting languages are dynamically typed. But C# for example is catching up here. Are scripting languages interpreted languages? Python compiles to byte code internally, so does Java. Do they have unique reflective and introspective capabilities? To some extend, yes, but Java and C# are also quite powerful in this respect. Is programm size the only criteria? Regarding size, Haskell is a serious competitor. Haskell is statically typed (it requires a minimum of explicit type declarations) and quite dense in expressivity.

I think that the name "scripting language" is not very helpful these days anymore. It's historically motivated. In the early days of computing, users had to interact with their machines by typing in commands in a command line. Soon, the command line was embedded in a so-called shell. Famous shells under Unix are the bourne shell (bsh), csh, tcsh; another specialized automation tool for software developers is "make". The shell provided means to automate -- script -- repetitive tasks. This kind of "programming" inspired languages like Perl. These languages weren't regarded as "serious" languages like e.g. C/C++. They were typically interpreted and relatively slow in execution. However, these languages matured over time and inspired other designers to create "glue" languages like Python or Tcl/Tk. Because of their interpretative nature it was easy to add introspective features and meta-programming facilities. The idea of being a scripting or "glue" language vanished over time. They became full-fledged implementation languages on their own right and kept the philosophy of being flexible and easy to use to solve problems. I think it is not appropriate anymore to call them "scripting languages".

However, some of these "scripting languages" introduced a feature none of the compile-execute languages offered: The "programmable command line" languages introduced interactivity!

And that is the key point, it's the distinguishing feature: Interactivity requires to design a language in a certain way. To be interactive, relatively small chunks of text must represent syntactically valid program fragments in order to query or incrementally modify the run-time environment.

The way to interact with the run-tim environment in non-interactive compile-execute languages is via the debugger. A tool that is rarely taught in combination with a non-interactive programming language. It's quite much a different experience to work with a debugger or interactively via an interactive command-line. A debugger is built around a representation of the run-time model and usually establishes a bridge towards the language the original program is written in. Interactive languages connect your programming experience with the run-time model in a consistent language-related way but still might shield some implementation details from the programmer a debugger shamelessly unveils.

So the point is that interactive languages have a severe impact (a) on the syntactic language design and (b) they establish a certain way of how you perceive and experience the run-time environment of your language. This explains the shortness of interactive programs, it also explains the agility in the development process and its perceived prouctivity: quickly testing a program at the console results in immediate feedback to the programmer. This helps learning a language a lot and helps get a better run-time understanding. It's just fun and feels cool. There are only two languages I know of which have taken the implications of interactivity (small chunks of text represent valid syntactic programs and an incremental run-time experience) to an extreme: Forth and Factor!

This does not mean, that non-interactive languages are not useful and important! They just feel a bit different. Due to their lack of interactivity they feel less "handy", so to speak.

Die Denkspuren auf Twitter

2009-12-23T12:02:00.003+01:00

Einige meiner Leser(innen) scheinen es noch nicht zu wissen: Die Denkspuren gibt es seit einiger Zeit auch auf Twitter (twitter.com/denkspuren). Ich war anfangs skeptisch, ob ich mit Twitter etwas anfangen könne, aber ich wollte das Experiment wagen. Mittlerweile habe ich mich eingezwitschert ...

Auf diesem Blog ist es ruhiger geworden. Dabei habe ich 2009 vielleicht so viel geschrieben wie nie zuvor -- allerdings nicht auf diesem Blog. Ich hatte ursprünglich erwartet, dass mir mein Forschungssemester (März-August 2009) mehr Zeit für den Denkspuren-Blog schenken würde. Interessanterweise trat das Gegenteil ein. Die Forschung zu den konkatenativen Sprachen hat sich derart interessant und aufregend entwickelt (wie man es vielleicht aus den September-Beiträgen erahnen mag), dass ich jede freie Minute in die Entwicklung und Ausarbeitung von Ideen investiere. Dabei kommt dieser Blog momentan zu kurz. Ich bin gespannt, wie sich das 2010 entwickeln wird.

All meinen Leser(innen) ein schönes Weihnachtsfest und ein gutes neues Jahr 2010.

Concatenative Programming via Rewriting in Scheme

2009-09-17T11:09:00.003+02:00

The kernel of a concatenative programming language can be easily implemented using a rewriting system. As a proof-of-concept the presented implementation fully relies on Scheme's rewriting system at macro expand time! All one needs is define-syntax and -- in order to provide access to Scheme's built-in procedures -- a single defmacro.

(Apologies, if the formatting makes the code below hard to read. If you like to get the Scheme code, just drop me an email.)

Rewriting rules concerning the data stack (ds) are written as follows:


(rule swap   : (@d ... snd fst) ==> (@d ... fst snd)) 
      ^^^^     ^^^^^^^^^^^^^^^^     ^^^^^^^^^^^^^^^^^
      word     datastack before      datastack after

Note that the topmost element of the data stack is the rightmost element in the notation above.

Rewriting rules concerning the data _and_ the program stack (ps) are written as


(rule call   : (@d ... (@q ...)) (@p ...) ==> (@d ...) (@q ... @p ...))
      ^^^^     ^^^^^^^^^^^^^^^^^ ^^^^^^^^     ^^^^^^^^ ^^^^^^^^^^^^^^^
      word          ds before    ps before    ds after    ps after

Note that the topmost element of the program stack is the leftmost(!) element. Letting the data stack and the program stack "touch" their heads, makes it easier to describe the process when a word or quotation moves from the top of the program stack to the top of the data stack. The item just appears to move over to the other side.

Quotations are written as lists. The notation for patterns is according to the conventions for syntax-rules in Scheme. The use of a "@" in patterns has no special syntactic meaning, it's just a personal preference.

To run a concatenative program type


> (run () (2 3 plus))
       ^^ ^^^^^^^^^^
       ds     ps

If you type this in at the console, the result just shows the resulting data stack since the program stack is empty.

Here are some examples and their results (indicated by "-->"):


> (run (1 2) (3 4)) --> (1 2 3 4)
> (run () (2 1 swap dup 1 plus)) --> (1 2 3)
> (run (1 2) ((plus dup) call)) --> (3 3)
> (run () (4 5 1 2 eq (plus) (minus) ifte)) --> (-1)
> (run () (4 5 1 2 eq neg (plus) (minus) ifte)) --> (9)

This is the way, I implemented the rewriting system with Scheme macros only. I use PLT Scheme, choose language "Pretty Big".

First, we need to import "defmacro". In addition, we need a nice macro hack from Oleg Kiselyov, see "How to write symbol? with syntax-rules". We use it in the definition of 'run'.


(require mzlib/defmacro)

(define-syntax symbol??
  (syntax-rules ()
    ((symbol?? (x . y) kt kf) kf)  ; It's a pair, not a symbol
    ((symbol?? #(x ...) kt kf) kf) ; It's a vector, not a symbol
    ((symbol?? maybe-symbol kt kf)
      (let-syntax
 ((test
    (syntax-rules ()
      ((test maybe-symbol t f) t)
      ((test x t f) f))))
 (test abracadabra kt kf)))))

The rule macro transforms rewrite rules into new macros. For example, the rule for 'swap'


(rule swap   : (@d ... snd fst) ==> (@d ... fst snd))

creates the following new macro


((swap (@d ... snd fst) ps) (run (@d ... fst snd) ps))

That means, whenever an s-expression with 'swap' being leftmost is encountered, such like '(swap (1 2 3) (4 5))', the macro is applied. In the example, the result is '(run (1 3 2) (4 5))'.


(define-syntax rule
  (syntax-rules (: ==>)
    ((_ word : (@d1 ...) ==> (@d2 ...))
     (define-syntax word
       (syntax-rules ()
         ((_ (@d1 ...) ps) (run (@d2 ...) ps)))))
    ((_ word : (@d1 ...) ==> (@d2 ...)
               (@d3 ...) ==> (@d4 ...))
     (define-syntax word
       (syntax-rules ()
         ((_ (@d1 ...) ps) (run (@d2 ...) ps))
         ((_ (@d3 ...) ps) (run (@d4 ...) ps)))))
    ((_ word : (@d1 ...) (@p1 ...) ==> (@d2 ...) (@p2 ...))
     (define-syntax word
       (syntax-rules ()
         ((_ (@d1 ...) (@p1 ...)) (run (@d2 ...) (@p2 ...))))))
    ((_ word : (@d1 ...) (@p1 ...) ==> (@d2 ...) (@p2 ...)
               (@d3 ...) (@p3 ...) ==> (@d4 ...) (@p4 ...))
     (define-syntax word
       (syntax-rules ()
         ((_ (@d1 ...) (@p1 ...)) (run (@d2 ...) (@p2 ...)))
         ((_ (@d3 ...) (@p3 ...)) (run (@d4 ...) (@p4 ...))))))
    ))

The run macro keeps the rewriting process running until the program stack is empty. The assumption is that there is a rewriting rule defined for symbols used on the program stack.


(define-syntax run
  (syntax-rules ()
    ((run (@d ...) ()) ; we are done
     '(@d ...))
    ((run (@d ...) (wrd @p ...)) ; inspect next wrd on program stack
     (symbol?? wrd
               (wrd (@d ...) (@p ...)) ; activate macro associated with wrd
               (run (@d ... wrd) (@p ...)))))) ; move wrd on top of data stack

In order to have access to Scheme's built in procedures, we introduce a rewriting rule for a word called 'alien'. In Scheme, a procedure such as '+' can also be called using apply:


> (+ 2 3)
5
> (apply + '(2 3))
5

Thus, 'alien' expects the arguments and a symbol on top of the data stack, each wrapped in a quotation/list. To interact with Scheme, we need to use defmacro _alien.


(defmacro _alien (op q ds ps)
  `(run (,@ds ,(apply (eval op) q)) ,ps))
 
(define-syntax alien
  (syntax-rules ()
    ((_ (@d ... (@q ...) (op)) (@p ...))
     (_alien op (@q ...) (@d ...) (@p ...)))))

Now let us define some rewriting rules:


(rule swap   : (@d ... snd fst) ==> (@d ... fst snd))
(rule dup    : (@d ... fst) ==> (@d ... fst fst))
(rule quote1 : (@d ... fst) ==> (@d ... (fst)))
(rule quote2 : (@d ... snd fst) ==> (@d ...(snd fst)))
(rule quote3 : (@d ... trd snd fst) ==> (@d ... (trd snd fst)))
(rule call   : (@d ... (@q ...)) (@p ...) ==> (@d ...) (@q ... @p ...))
(rule ifte   : (@d ... #f  (@t ...) (@e ...)) (@p ...) ==> (@d ...) (@e ... @p ...)
               (@d ... obj (@t ...) (@e ...)) (@p ...) ==> (@d ...) (@t ... @p ...))
(rule plus   : (@d ...) (@p ...) ==> (@d ...) (quote2 (+) alien @p ...))
(rule minus  : (@d ...) (@p ...) ==> (@d ...) (quote2 (-) alien @p ...))
(rule mult   : (@d ...) (@p ...) ==> (@d ...) (quote2 (*) alien @p ...))
(rule div    : (@d ...) (@p ...) ==> (@d ...) (quote2 (/) alien @p ...))
(rule eq     : (@d ...) (@p ...) ==> (@d ...) (quote2 (eq?) alien @p ...))
(rule neg    : (@d ... #f) ==> (@d ... #t)
               (@d ... obj) ==> (@d ... #f))

And we are done ;-)

For information about concatenative languages, see concatenative.org.

Type Inference for "call" in Concatenative Languages

2009-09-14T16:24:00.003+02:00

I think I solved the problem of type inference for "call" in concatenative languages. In a private mail, Slava Pestov (the creator of Factor) challenged me with the problem of inferring types for the bi and bi@ combinator. In essence, the problem boils down to "call". The solution, Christopher Diggins proposes in his papers on Cat is not without complications.

First let me introduce a notation for describing the effect of a word via substitutions. I use pattern matching. $X matches a single word, #X matches a single word _or_ quotation, and @X matches any number of words/quotations. To refer to a quotation, I use squared brackets. For example, "[ $X ]" matches a quotation with a single word inside like "[ 7 ]". Furthermore, I explicitly distinguish the data stack and the program stack and separate them with a bar "|". Here are some example substitutions:


@D #X | dup @P ==> @D #X #X | @P
@D #X #Y | swap @P ==> @D #Y #X | @P
@D $X $Y | + @P ==> @D $Z | @P
@D [ @X ] [ @Y ] | append @P ==> @D [ @X @Y ] | @P

As you can see, @D and @P explicitly catch the "rest" of the data stack and the program stack, respectively. The rules are precise specifications on the effects a word has on the data _and_ the program stack. Attachments like are type annotations.

The combination of a data and program stack represents a "continuation". A substitution rule substitutes a matching continuation by another continuation.

Since concatenative programs are written in continuation passing style, so to speak, we can decompose the substitution of a continuation @DS | @PS into ( @DS | @P ) | @S with @PS = @P @S, meaning that @P and @S stand for any decomposition of @PS. For example, the program "dup *" can be decomposed into "dup" and "*". Instead of evaluating ( @DS | dup * @R ) with some instance of a data stack @DS, we can also first evaluate ( @DS | dup ), which must result in an empty program stack and a data stack @DS', and then evaluate ( @DS' | * @R ). For this process, we also write ( @DS | dup ) | * @R.

Now we have everything in place to define the substitution rule for call:


@D [ @Q ] | call @P ==> ( @D | @Q ) | @P

The right hand side of the rule uses a continuation so that that further substitution rules for whatever is on @P can be applied and don't hinder stack effect inference.

Let's take the program "call +" as an example. To avoid naming conflicts in the following, we repeat the rules for "call" and "+" and rename some pattern variables.


(1) @D1 [ @Q ] | call @P1  ==> ( @D1 | @Q ) | @P1
(2) @D2 $X $Y | + @P2 ==> @D2 $Z | @P2

The question to answer is:


(?) @D | call + @P ==> @D' | @P

Rule (1) applies:


@D | call + @P ==> ( @D1 | @Q ) | @P1
with @D = @D1 [ @Q ] and @P1 = + @P
               ==> ( @D1 | @Q ) | + @P
with @D = @D1 [ @Q ]

Rules (2) applies:


               ==> @D2 $Z | @P2
with @D = @D1 [ @Q ]
and @D2 $X $Y = ( @D1 | @Q )
and @P = @P2

We can conclude that


@D1 [ @Q ] | call + @P ==> @D2 $Z | @P
with
( @D1 | @Q ) ==> @D2 $X $Y |

We are done! The result says that "quote +" expects a quotation [ @Q ] at the very top of the data stack with @D1 underneath. The result will be a data stack with elements @D2 and an integer $Z on top. But there is a constraint which demands that the continuation ( @D1 | @Q ) returns a data stack with two integers on top and @D2 underneath.

I don't find a way to express this any shorter. This is just the way it is. The example shows that type inference of "call +" is possible. Problems just occur if stack effect declarations (at least for the purpose of type inference) are limited to the data stack only. Consider Factor's stack effect declaration for call


call ( callable -- )

which does not capture the effect the created continuation has on the data stack.

Code-Generierung und Patching

2009-07-07T00:48:00.002+02:00

Code-Generierung hat einen Vorteil, der oft übersehen wird: Man kann den generierten Code patchen, sprich Fehler darin beheben, ohne die Generator-Software anzufassen.

Ich arbeite derzeit an einem Projekt, in dem aus XML-Dateien HTML-Dateien samt zugehörigem JavaScript generiert werden. Die XML-Dateien spezifizieren ein Dialogsystem, die per JavaScript gesteuerten HTML-Seiten führen das Dialogsystem aus.

Nun ist es so, dass ich die Generatorsoftware nicht geschrieben habe. Zwar habe ich Zugriff auf den Quellcode, doch möchte ich am Code vorerst nichts ändern. Die Generatorsoftware hat sich in einem vorangegangenen Projekt bewährt, arbeitet zuverlässig und nimmt an den XML-Spezifikationen zahllose Konsistenzüberprüfungen vor -- und das ist Gold wert. Hier heißt es Finger weg, solange es geht, getreu der Devise: Never touch a running/working system.

Im jetzigen Projekt wird jedoch anhand neuer XML-Spezifikationen deutlich, dass der Generator HTML-Code erzeugt, der Missverständnisse in den Anforderungen an das System offenbart. Der Generator erzeugt also Code, der nicht "passt". Und das, obwohl das System funktional sehr gut spezifiziert ist. That's life.

Es ist nicht ohne Risiken, die Generatorsoftware direkt anzupassen: Ich baue mir möglicherweise neue Fehler ein, breche bestehende Funktionalitäten und riskiere Inkompatibilitäten zum generierten Code aus der ersten Projektphase.

Eine Alternative ist, sich Programme zu schreiben, die die Probleme im generierten Code beheben (patchen). Diese Strategie lässt die Generatorsoftware unangetastet und intakt. Stattdessen beschränkt und fokussiert sich alle Aufmerksamkeit auf das Endprodukt, auf den durch die Patch-Programme modifizierten generierten Code. Genau darauf sollen sich auch die Testing-Energien konzentrieren, nicht auf die Generator-Software. Da die Komplexität der Patch-Programme -- im Vergleich zur Generatorsoftware -- gering und überschaubar ist, ist auch mit weniger Programmierfehlern zu rechnen. Zuguterletzt sind die Patch-Programme hervorragende Spezifikationen für die Änderungen, die in einem späteren Schritt an der Generatorsoftware vorgenommen werden können.

Patching ist nicht nur eine simple Technik der Fehlerkorrektur, sondern es kann eine sehr gezielte Engineering-Aktivität sein, die hilft, bessere Software zu entwickeln.

RewriteParser & RewriteParser-Kombinatoren

2009-05-07T21:19:00.004+02:00

In der Vergangenheit habe ich über "Objekt-orientierte Parser-Kombinatoren in Python" geschrieben -- ein Thema, das mich immer noch fasziniert. Es ist so unglaublich einfach, einen Parser mit Parser-Kombinatoren zu entwickeln. Das ist gepaart mit einer Flexibilität, die traditionelle Parser-Ansätze a la lex & yacc nicht bieten.

In diesem Beitrag geht es (i) um die Verallgemeinerung eines Text-Parsers zum Parsen beliebiger Objektfolgen mit Hilfe zweier Stacks und (ii) um Parser, die ich RewriteParser nenne, und deren Kombination mit einem ganz speziellen RewriteParser-Kombinator, RPC*. Ich habe auf eine konkrete Programmiersprache verzichtet, damit das Prinzip klarer zutage tritt.

Um die Idee der Parser-Kombinatoren nicht auf das Parsen von Zeichenketten zu beschränken, verallgemeinern wir die Idee, parsen beliebige Objekte von einem Stack und legen die Ergebnisse auf einem anderen Stack ab. Ein Parser (und somit auch ein Parser-Kombinator) nimmt zwei Stacks entgegen, ich nenne sie inStack und outStack, und liefert neben einem Flag für erfolgreiches Parsen zwei Stacks zurück, inStack' und outStack'. Zur Info: meine Stacks sind funktional, sprich immutabel.

Was macht ein Parser generell? (1) Er prüft, ob ein bestimmtes Muster auf dem inStack zu finden ist -- dafür gibt es eine Funktion Crit(erion):Stack->Bool. (2) Er konsumiert kein oder mehr Elemente vom inStack -- die konsumierende Funktion heiße Consume:Stack->Stack. (3) Er produziert kein oder mehr Elemente für den Ausgabe-Stack -- der produzierte Stackanteil werde über Produce:Stack->Stack erzeugt.

Wir können das etwas formaler beschreiben mit P(arser), Consume und Produce als Funktionen und SUCCESS = True, FAILURE = False. Der '+'-Operator produziert einen neuen Stack aus dem Aneinanderhängen zweier gegebener Stacks.


P(Crit,Consume,Produce)(inStack,outStack) --> success,inStack',outStack'
if !Crit(inStack): return FAILURE, inStack, outStack
return SUCCESS, inStack', outStack'
with inStack' + Consume(inStack) == inStack
and outStack' == outStack + Produce(inStack)

Die "with"-Schreibweise ist vielleicht etwas ungewöhnlich, aber sie besagt nur, dass der inStack' ein um Consume(inStack) reduzierter inStack ist. Und dass der outStack immer nur um Produce(inStack) anwachsen kann zu outStack'. Ich nutze für die Stackreduktion weiter unten kurzfristig auch das "-":


inStack' == inStack - Consume(inStack)

Ein Parser-Kombinator, der ein oder mehr Parser in irgendeiner Weise verknüft (bisweilen ist die Verknüpfung konfigurierbar), muss sich an dieselben Spielregeln halten: er ist auch wieder ein Parser, der möglicherweise Teile vom inStack oder den ganzen inStack konsumiert und möglicherweise etwas zum outStack beiträgt. Beachten Sie nochmal, dass Konsum und Produktion ausschließlich eine Funktion vom inStack sind! Der outStack kann z.B. als Gedächtnis nicht genutzt werden!

Nachfolgend beschreibe ich einen Parser-Kombinator der zwei Parser komponiert: PC kombiniert zwei Parser P1 = P(Crit1,Consume1,Produce1) und P2 = P(Crit2,Consume2,Produce2):


PC(P1,P2)(inStack, outStack) --> success, _inStack, _outStack
success', inStack', outStack' = P1(inStack, outStack)
if !success': return FAILURE, inStack, outStack
success'', inStack'', outStack'' = P2(inStack', outStack')
if !success'': return FAILURE, inStack, outStack
return SUCCESS, inStack'', outStack''

Man könnte auch für den Erfolgsfall zusammenfassen:


inStack'' == inStack' - Consume2(inStack') <==>
inStack'' == inStack - Consume1(inStack) - Consume2(inStack - Consume1(inStack))

und


outStack'' == outStack + Produce1(inStack) + Produce2(inStack)

Die Komposition zweier Parser tut genau das, was man erwartet: erst konsumiert der erste Parser etwas vom inStack und legt sein Ergebnis auf dem outStack ab, dann folgt der zweite Parser, der weiteres vom inStack konsumiert und zusätzlich etwas auf dem outStack ablegt.

Nachfolgende möchte ich eine Parser-Klasse vorstellen, die ich RewriteParser nenne. Sie verallgemeinern das Parser-Prinzip; sie sind aus meinen Spielereien und der Suche nach immer wieder neuen, verbesserten, generischeren Parser-Kombinatoren hervorgegangen. Allerdings hat es eine Weile gedauert, bis ich ihre neue Eigenschaft destilliert hatte.

Der Unterschied zum Parser ist: Der Rewrite-Parser (RP) kann den inStack modifizieren! Der outStack kann nachwievor nicht gelesen, sondern nur produzierend (d.h. mit der Ablage neuer Elemente) bedient werden.


RP(Crit,Rewrite,Produce)(inStack,outStack) --> success,inStack',outStack'
if !Crit(inStack): return FAILURE, inStack, outStack
return SUCCESS, inStack', outStack'
with inStack' == Rewrite(inStack)
and outStack' == outStack + Produce(inStack)

Die Modifikation ist gering. Rewrite ist ebenso wie Consume eine Funktion, Rewrite:stack->stack. Sie konsumiert jedoch nicht nur einen Teil des inStack, sondern kann ihn vollständig umschreiben und beispielsweise neue Elemente auf dem inStack ablegen (z.B. als Gedächtnis etwa in Form von Annotationen). Der nachfolgende RewriteParser arbeitet dann mit diesem modifizierten inStack.

Schauen wir uns jetzt einmal einen RewriteParser-Kombinator an, der zwei Parser in eine Kompositionsbeziehung miteinander bringt. Wir berücksichtigen nun wieder den outStack. Es gilt RP1 = RP(Crit1,Rewrite1,Produce1), RP2 = RP(Crit2,Rewrite2,Produce2).


RPC(RP1,RP2)(inStack,outStack) --> success, _inStack, _outStack
success', inStack', outStack' = RP1(inStack,outStack)
if !success': return FAILURE, inStack, outStack
success'', inStack'', outStack'' = RP2(inStack',outStack')
if !success'': return FAILURE, inStack, outStack
return SUCCESS, inStack'', outStack''

Um das Kompositionsverhalten im Erfolgsfall verstehbar zu machen, auch hier wieder die Auflösung:


inStack'' == Rewrite2(inStack') <==> (mit inStack' == Rewrite1(inStack))
inStack'' == Rewrite2(Rewrite1(inStack))

Voila! Die Komposition zweier RewriteParser ist die Komposition ihrer Rewrite-Funktionen angewendet auf den inStack!


outStack'' == outStack' + Produce2(inStack')
outStack' == outStack  + Produce1(inStack)

mit


inStack' == Rewrite1(inStack)

ergibt sich


outStack'' == outStack + Produce1(inStack) + Produce2(Rewrite1(inStack))

Das Ergebnis für den OutStack überrascht nicht. Hier legen RP1 und RP2 ihre Ergebnise der Verarbeitung von inStack bzw. inStack' ab

Wir können schon einmal festhalten: Die Kombination von RewriteParsern entspricht der Funktionskomposition plus Seiteneffekte!

Es gibt einen kleinen Kniff, der die Sache nun vollends interessant macht. Berücksichtigen wir bei der Komposition doch den Output von RP1, outStack', beim Input von RP2. Damit ist es nicht mehr nötig, RP2 als Ausgabe-Stack outStack' zu geben, da er den prinzipiell bei Produce berücksichtigen kann, sondern outStack. Ebenso benötigt RP1 nun nur einen EMPTYSTACK.

Diesen modifizierten RPC bezeichne ich RPC*.


RPC*(RP1,RP2)(inStack,outStack) --> success, _inStack, _outStack
success', inStack', outStack' = RP1(inStack,EMPTYSTACK)
if !success': return FAILURE, inStack, outStack
success'', inStack'', outStack'' = RP2(inStack'+outStack',outStack)
if !success'': return FAILURE, inStack, outStack
return SUCCESS, inStack'', outStack''

Es ergibt sich nun für inStack'':


inStack'' == Rewrite2(inStack'+outStack')
inStack'  == Rewrite1(inStack)
outStack' == EMPTYSTACK + Produce1(inStack)
---
inStack'' == Rewrite2(Rewrite1(inStack)+Produce1(inStack))

Und für outStack'' ergibt sich:


outStack'' == outStack + Produce2(inStack'+outStack')
outStack'' == outStack + Produce2(Rewrite1(inStack)+Produce1(inStack))

Das Ergebnis hat zwei bemerkenswerte Eigenschaften. Zum einen: Darin ist vollständig der Parser-Kombinator RPC nachbildbar über geeignete Rewrite- und Produce-Funktionen. RPC* ist also erheblich mächtiger. Zum anderen: Es kommt wunderbar aus, dass das Argument zu Rewrite2 in inStack'' und zu Produce2 in outStack'' das gleiche ist! Das Ergebnis inStack'' kann entweder auf "normale" Funktionskomposition reduziert werden oder es bekommt ein Ergebnis einer Vorverarbeitung durch Produce1(inStack) dazu! Mit diesem Input arbeitet auch Produce2 und kann das Gedächtnis beim Hinzufügen eines Ergebnisses zu outStack berücksichtigen.

Für diejenigen, die sich mit konkatenativer Programmierung schon einmal befasst haben (siehe z.B. Factor, Joy oder Cat), sei verraten, dass sich das konkatenative Paradigma mit RewriteParsern und RPC* vollständig umsetzen lässt. Oder anders herum: Konkatenative Programmierung kann man verstehen als die Programmierung mit RewriteParsern, die durch PRC* komponiert werden.

Ich weiß, das war viel. Aber vielleicht werden Sie den Nutzen der RewriteParser erkennen, wenn Sie selber einmal mit Parser-Kombinatoren arbeiten und programmieren.

Abwrackprämie am Limit

2009-03-30T10:56:00.010+02:00

(Update 31. März 2009: Der Geschäftsführer der Babiel GmbH, Herr Dr. Rainer Babiel, hat mich gebeten noch einmal ausdrücklich darauf hinzuweisen, dass seine Firma nicht für das BAFA-Webformular rund um die Abwrackprämie verantwortlich ist. Das betrifft auch das Hosting. Dies geht auch aus den Nachträgen zu diesem Blogbeitrag hervor.)

Ich gehöre auch zu denen, die sich heute morgen mit einer Funkuhr bewaffnet vor den Rechner setzten, um am Wettrennen um die Reservierung der "Abwrackprämie" teilzunehmen. Der Wettstreit wurde um 8 Uhr vom Bundesamt für Wirtschaft und Ausfuhrkontrolle eröffnet unter www.ump.bafa.de.

Bereits vor einer Woche habe ich mich schon zusammen mit einem Freund über den vorherzusehenden Zusammenbruch aufgeregt. Denn was die Sache so heikel macht: Jeder über die Webseite gestellte Antrag wird mit einer Zeitmarke versehen. Wer zuerst auf dem Webserver der BAFA registriert wird, der wird vorrangig bei der Gewährung der Umweltprämie für Altfahrzeuge behandelt. Bekanntlich ist der Geldtopf für die Prämie limitiert.

Um 8 Uhr lief rein gar nichts. Nicht einmal ein "ping" ging an den Webserver durch. Um 8:14 Uhr bekam ich einen ersten "Sneak Preview" auf das Formular. Ein nettes Gimmick hat man sich da ausgedacht: Mit der Auswahl des Fahrzeugherstellers beginnt die Webseite irgendetwas nachzuladen, ich vermute den Fahrzeugtyp -- und kriegt natürlich keinen Kontakt mehr zum Server, da der überlastet ist.

Ich rufe bei der BAFA an und melde meinen Protest an. Natürlich sitzt dort eine ebenso überlastete Dame im CallCenter. Über 90% der Anrufe seien Beschwerden zum Thema, sagt sie. Über das Impressum der BAFA finde ich heraus, wer für den Internet-Auftritt verantwortlich und technischer Provider ist. Ich rufe dort um 10:05 Uhr an. Die Dame der Babiel GmbH kann mir lediglich verraten, dass man um das Problem des überlasteten Webauftritts wisse und man an seiner Behebung arbeite. Eine alternative IP-Adresse habe sie nicht. Und wann man den Server wieder im Griff habe, könne sie auch nicht sagen.

Tja. Ich bin fassungslos -- und verärgert. Wie kann man so naiv sein? Nach diesem medialen und politischen Getöse um die Abwrackprämie ist ja wohl nicht schwer vorherzusehen gewesen, dass heute morgen Autohäuser, Privatmenschen und viele Journalisten für unzählige HTTP-Requests auf www.ump.bafa.de sorgen würden. 2.500 Euro sind ein mächtiger Anreiz für den Besuch der Webseite. Und wie kann man ein Formular entwerfen, das die Serverlast mit Nachladerei noch erhöht und den Frust aller Reservierungswilligen nur steigert?

Die BAFA stellt Regelungen auf, deren technische Umsetzung die von ihr beauftragte Firma nicht zu beherrschen scheint. Damit ist die Reservierung der Umweltprämie kein faires Verfahren mehr. Es ist keine Sache der Schnelligkeit mehr sondern ein Glücksspiel, wer hier wann zuerst seinen Antrag elektronisch einreichen kann. Das wird eine Welle des Protests erzeugen. Die BAFA kann als Lösung eigentlich nur noch die Reihenfolge der heutigen Reservierungen per Losentscheid erstellen. Fraglich bleibt, ob man seinen Antrag heute überhaupt noch per Webformular stellen kann. Mittlerweile ist es fast 11 Uhr. Über drei Stunden hat niemand das Problem lösen können.

Nachtrag 0:39 Uhr, 31. März: Unfassbar! Ein letzter Versuch vor dem Weg ins Bett beschert mir unverhofft ein Erfolgserlebnis: Der Antrag ist durch! Nach etwas mehr als 16 Stunden! Die zugeteilte Vorgangsnummer liegt über einer Million. Was mir das sagen soll, weiß ich nicht. Hoffentlich nichts Ungutes.

Nachtrag 22:52 Uhr: Die Webseite zur Reservierung der Umweltprämie scheint gänzlich vom Netz zu sein. In einer Pressemitteilung bedauert das BAFA "technische Schwierigkeiten" und verkündet "externer Dienstleister arbeitet an Lösung". Wir dürfen gespannt sein, was es mit den in der Pressemitteilung erwähnten Denial-of-Service-Attacken auf sich haben soll -- das BAFA will morgen um 10 Uhr weitere Hinweise auf seinen Webseiten veröffentlichen. Ich bin gespannt, ob sich der BAFA-Datenschutzbeauftragte Ulrich Schydlo (siehe BAFA-Impressum) morgen aufgeweckt zeigt. Allein die unverschlüsselten Formulareingaben hätte er wohl kaum tolerieren dürfen. Sollten die heise-Meldungen stimmen, dann hätte er allen Grund vehement einzuschreiten.

Nachtrag 18:58 Uhr: Auf heise.de ist vor einer halben Stunde von massiven Pannen in Sachen Datenschutz berichtet worden: "Auto-Abwrackprämie: Daten(schutz)pannen bei Online-Reservierung". Die Bestätigungsmails werden angeblich nicht immer an die richtigen Antragsteller(innen) geschickt. Ich bin nicht einen Schritt weiter gekommen. Im Moment sieht es nicht besser als kurz nach 8 Uhr heute morgen aus.

Nachtrag 17:04 Uhr: Die Reaktionszeiten des Portals haben sich spürbar verbessert. Nun kann ich wiederholt meine Daten angeben, um dann dabei unterbrochen zu werden mit dem Hinweis:

Willkommen auf dem Antragsportal für die Umweltprämie!

Leider ist das Antragsportal zur Zeit überlastet. Bitte versuchen Sie es in einigen Minuten erneut. Vielen Dank für Ihr Verständnis.

Auf mein Verständnis sollte man nach einem Tag nicht mehr hoffen!

Nachtrag 15:05 Uhr: Immerhin, ich bin bis zur Gotcha-Seite vorgedrungen. Ich klicke auf weiter und komme zur einer Seite mit dem wörtlichen Hinweis:

Aktuell laden sehr viele Antragsteller einen Kaufvertrag hoch.

Die Anzahl paralleler Uploads ist aber begrenzt. Diese Seite aktualisiert sich automatisch, bis Sie Ihren Upload starten können.
Verzichten Sie bitte daher auf die Funktion 'Neu laden'

Die Wartezeit sollte 60 Sekunden nich überschreiten.

Ja, da steht "nich überschreiten". Übrigens muss man als Vollendung dieser Unprofessionalität den Versand der eigenen Daten über eine unsichere Verbindung hinnehmen! Das ist schon fast ein regelrechter Datenskandal!

Nachtrag 12:58 Uhr: Im Impressum der BAFA ist mittlerweile ein Hinweis erschienen, dass die Formularseite für die Reservierung der Umweltprämie nicht von der Babiel GmbH gehostet wird. Als ich dort gegen 10 Uhr anrief, wusste die Firma selbst das noch nicht ...

Nachtrag 11:53 Uhr: Die folgende Meldung findet sich auf der Homepage der BAFA -- auch das hat Stunden gedauert:

Aufgrund von technischen Problemen kommt es derzeit zu Schwierigkeiten beim Aufruf und beim Ausfüllen des Reservierungsantrags, die nicht im Einflussbereich des BAFA liegen. Das BAFA unternimmt alles in seiner Macht stehende, damit dieses Problem schnellstmöglich behoben wird. Bis dahin bitten wir um Ihr Verständnis.

Die Meldung an sich ist bereits amüsant. Die technischen Probleme liegen nicht im Einflussbereich der BAFA. Dennoch will man Mächte aktivieren, die Einfluss auf den Einflussbereich nehmen. Spannend!

Konkatenative Programmiersprachen

2009-03-01T22:14:00.002+01:00

Mit dem heutigen Tag beginnt offiziell mein Forschungssemester. Mein Thema: "A Model of Computation in Space and Time" -- darüber werde ich vielleicht ein anderes Mal was schreiben.

Was sich in den letzten Wochen mehr und mehr aufdrängt, ist, das ein Schlüssel zu meinem Thema in den konkatenativen Sprachen liegt. Ich weiß es noch nicht sicher, aber mit jedem Tag finde ich mehr und mehr Gründe, mich mit dieser Klasse von Sprachen auseinander zu setzen.

Was, Sie haben noch nie etwas von concatenative languages gehört?

Verwunderlich ist das nicht. Konkatenative Sprachen führen zu unrecht ein vollkommenes Schattendasein. Wenn Sie sich für Ruby, Python, Groovy, Scheme, Lisp, Clojure, Haskell, F#, Prolog begeistern können, dann sollten konkatenative Sprachen wie Joy, Cat und Factor ein gefundenes Fressen für Sie sein. Diese drei Sprachen führen Sie in eine ganz neue Programmierwelt ein.

Konkatenative Sprachen gehören zu den funktionalen Sprachen. Manfred von Thun hat auf seiner Webseite zu Joy einen wunderbaren Satz an Beiträgen zusammengestellt, die behutsam in diese rein funktionale Welt konkatenativer Programmierung mit Joy einführen. Auch die Sprache Cat von Christopher Diggins ist interessant. Cat ist in C# implementiert und ein Studium wert.

Während Joy und Cat mehr Experimentalcharakter haben, ist Factor eine ernstzunehmende Programmiersprache, die der Pragmatik zuliebe auf ein striktes funktionales Paradigma verzichtet. Für mich ist Factor die spannendste Sprache, die am Programmierhorizont zu sichten ist. Ich habe Factor schon ein Weilchen auf dem Radar und schrieb vor einem Jahr "Factor: In der Kürze liegt die Würze". Ihr Schöpfer, Slava Pestov (übrigens hat er auch jEdit entwickelt), wird übermorgen, am 3. März 2009, 25 Jahre alt! Vielleicht mag das insbesondere die Informatik-Studierenden unter meinen Lesern motivieren. Andererseits: Slava Pestovs Biographie liest sich fast wie die eines Wunderkindes, der früh einen Draht zur Mathematik und Informatik fand. Seine Sprache Factor ist so voll gefüllt mit modernen Programmierkonzepten und so intelligent aufgebaut -- ich finde es mehr als beachtlich, wie man so jung derart smart und zielstrebig eine so qualitativ hochwertige Programmiersprache auf die Beine stellen kann, die einen Guido van Rossum (Schöpfer von Python) oder einen Matz (Yukihiro Matsumoto, Schöpfer von Ruby) alt aussehen lassen.

Vielleicht habe ich Sie jetzt ja neugierig gemacht ...

Ist der Kassen-Bug von Lidl ein Bug?

2009-02-28T11:51:00.007+01:00

Mein Posting "Lidl und der Kassen-Bug" ist seit seinem Erscheinen immer noch der am meisten gelesene Beitrag in meinen Denkspuren. Nie hätte ich daran geglaubt, dass er diese Popularität genießen würde, denn er ist einer von den Beiträgen, die mir selber weniger bedeuten. "Lidl und der Kassen-Bug" erschien am 15. April 2008. Ich hatte den Tipp von einem meiner Studierenden bekommen. Allerdings wollte ich mit eigenen Augen sehen, ob der Tipp wirklich das versprochene Ereignis auslöst, bevor ich darüber blogge.

Als ich über den Kassen-Bug berichte, gibt es einen kleinen, fast schon aufregenden Peak in den Visits (ich nutze Google Analytics). Die seinerzeit noch üblichen 20, 30, 40 oder auch mal 50 Visits an einem Tag schrauben sich am 15. April auf ungekannte 97 Visits hoch. Am Folgetag gibt es 190 Visits zu verzeichnen, dann 124, dann 100, ... und dann ist schon wieder alles beim alten. Ein paar Tage später, mit Beginn der neuen Woche beginnt es zu rumpeln. Genau eine Woche später, am 22. April scheint der Beitrag auf das Radar von Lesern zu kommen, die sonst die Denkspuren nicht besuchen. Am 4. Mai verzeichne ich den absoluten Besuchsrekord: 5.362 Visits an einem Tag! Es ist ein Peak, aber in der Folgezeit habe ich immer noch ungewohnt hohe und teils stark schwankende Besuchszahlen. Allein in der Zeit vom 22. April bis zum 21. Mai 2008 zählt Google Analytics 25.150 Visits und 34.586 Pageviews. Anfang Juni ist der "Spuk" vorbei. Die Besuchszahlen pendeln sich allmählich wieder auf die Ausgangsdimensionen ein. Ich darf seitdem lediglich im Mittel eine etwas höhere Besuchszahl verzeichnen, meist in der Spannbreite von 35 bis 70 Visits/Tag. In den letzten 30 Tagen (29. Januar - 27. Februar) gab es 1.608 Visits und 1.987 Pageviews.

Das Ganze war für mich eine absolut interessante Lehrstunde in Sachen Dynamik, die das Web entwickeln kann! Beliebte Seiten, wie golem.de, hatten über "Lidl und der Kassen-Bug" berichtet und einen Teil des Ansturms ausgelöst. Ich hätte diese Entwicklung niemals für diesen Beitrag vorauszusagen gewagt. Never ever!

In den Kommentaren zu dem Posting (in meinem Blog und anderswo) spekulieren einige meiner Leser(innen) sehr phantasiereich über die Umstände der möglichen Entstehung des Kassen-Bugs. Einige haben sogar konkrete Codezeilen vor Augen. Nur eine sehr kleine Fraktion hält das von mir als Bug deklarierte Ereignis gar nicht für einen Fehler. Kann es sein, dass der Kassen-Bug bei Lidl gar kein Bug, sondern ein Feature ist?

Gut möglich. Dafür spricht, dass die Kasse bei dem Null-Betrag weder abstürzt noch abraucht (das wäre ein Spaß, was?! ;-), sondern ein definiertes Verhalten zeigt. Dagegen spricht, dass die Kassierer und Kassiererinnen auf dieses Kassenverhalten gar nicht vorbereitet sind. Sie reagieren ratlos, weil sie den Fehler nicht kennen, oder lösen das Problem mit einem Workaround ("Ich zieh das hier wieder ab, dann geht die Kasse wieder und sie zahlen das hier dann gesondert, ok?"). Was für ein Interesse sollte ein Discounter daran haben, bei einer Nullsumme die Kasse zu blockieren, wenn der Workaround so simpel ist?

Ist der Kassen-Bug nun ein Bug oder ein Feature?

Ich plädiere zwar auf Bug, glaube die Argumente auf meiner Seite, aber das will nichts heißen. Meinen kann man im Web viel. Letztlich ist die Frage nicht zu beantworten. Es sei denn, wir verlassen die Komfortzone des Browserfensters, begeben uns in die Welt da draußen und klären das Phänomen des Kassen-Bugs auf.

Wollen Sie wissen, ob der Kassen-Bug ein Bug ist? Wollen Sie mir das Gegenteil beweisen?

Finden Sie's raus! Besuchen Sie den nächsten Lidl und fragen Sie bei der Filialleitung nach. Vielleicht kommen Sie da weiter. Oder greifen Sie zum Telefon, rufen bei Lidl an und bitten um Kontakt mit dem "Kassen-Verantwortlichen"; man könnte es bei der Lidl-eigenen IT-Abteilung versuchen. Wer ist der Hersteller der Kassen? Kann man Ihnen dort in der Entwicklungsabteilung einen Hinweis geben oder das Problem aufklären? Irgendwo da draußen in der Realwelt gibt es jemanden, der uns die Frage "Bug oder Feature?" beantworten kann.

Der Erste bzw. die Erste, der/die mir bis zum 31. März 2009 eine EMail schickt mit einer nachvollziehbaren Antwort unter Quellenangaben wie z.B. Gesprächspartner samt Telefonnummer (ich möchte Ihre Angaben überprüfen können), dem verspreche ich ein kleines Buchgeschenk. Da wir das Darwin-Jahr haben, habe ich für Sie das Buch von Joachim Bauer "Das kooperative Gen" ausgesucht. Sie dürfen sich bei akzeptierter Antwort aber auch gerne ein anderes Buch bis 20 Euro wünschen.

Viel Erfolg!

[Nachtrag vom 10. März: Meinen herzlichen Glückwunsch an Marius Heisler. Dank seiner Recherchen weiß ich nun, dass der Kassen-Bug bei Lidl definitiv kein Feature ist. Heute hat mir die Pressestelle von Lidl das bestätigt. Die Pressesprecherin spricht selber von einer Kasse, "die sich aufgehängt hat". Sie bittet jedoch um Verständnis, "dass wir darüber hinaus keine detaillierten Angaben zur Softwarethematik machen möchten". Schade eigentlich.]

Was sind das für Zustände?

2009-01-19T19:44:00.006+01:00

Zustandsmaschinen dienen in der Informatik zur Modellierung von Verhalten. Sie werden besonders gerne zur Spezifikation technischer Systeme eingesetzt. Oben im Bild sehen Sie ein einfaches Zustandsdiagramm. Zustandsdiagramme sind eine verbreitete Notation zur Darstellung von Zustandsmaschinen. Die Notation ist in der Unified Modeling Language (UML) standardisiert.

In dem Beispiel geht es um einen Roboterarm. Der Roboterarm ist entweder in dem Zustand "idle", "moving up/down" bzw. "welding" (schweißen); Zustände werden durch Rechtecke mit runden Ecken abgebildet. Der Start- und der Endzustand sind durch besondere Symbole hervorgehoben: durch einen Kreis (Start) bzw. einen Punkt im Kreis (Ende).

Die Pfeile beschreiben Übergänge (Transitionen) von einem Zustand in einen anderen und zwar abhängig von einem Ereignis. Die Ereignisse sind hier durch Buchstaben abgekürzt und stehen immer links vom Schrägstrich "/". Es sind Ereignisse, die der Roboter über seine Sensoren wahrnimmt. Die meisten der Ereignisse werden durch Steuerungssensoren wahrgenommen. Wenn ein Anwender den "down"-Knopf drückt, dann löst er damit das "d"-Ereignis aus. Ein "up" führt zu einem "u"-Ereignis, ein "s" zu "stop" und ein "o" ist die Folge eines "on"- bzw. "off"-Signals. Einzig das "c"-Ereignis wird durch einen Kontakt-Sensor ("contact") im Roboterarm ausgelöst. Dann "fühlt" der Roboterarm einen Widerstand.

Zu jedem Ereignis ist rechts vom Schrägstrich angegeben, was der Roboterarm für eine Aktion folgen lässt. Grundsätzlich möglich sind die Aktionen "move down", "move up", "stop moving", "weld" (schweiße), "initialize" und "shut down".

Befindet sich der Roboterarm im Zustand "idle" und tritt das Ereignis "d" auf (sprich, der Anwender hat den "down"-Knopf gedrückt"), dann bewegt sich der Roboterarm nach unten. Der Zustand wechselt von "idle" auf "moving down". Weitere "d"-Ereignisse bleiben ohne Folge, da sich der Roboterarm bereits in der Abwärtsbewegung befindet. Im Zustand "moving down" bewegt ein "u" den Arm wieder nach oben, ein "c" stößt die Schweiß-Aktivität an. Beim "u"-Ereignis wechselt der Zustand zu "moving up", beim "c"-Ereignis zu "welding".

Eine solche Zustandsmaschine kann man systematisch in Code übertragen. Der Vorgang ist derart schematisch, dass man ihn leicht automatisieren kann. Dafür übertragen wir in einem ersten Schritt das Diagramm in ein maschinenlesbares Format. Ich habe mich für XML entschieden. (Hinweis: Für die nachstehenden Code-Auszüge verwende ich den syntaxhighlighter. Möglicherweise gibt es Darstellungsprobleme, wenn Sie z.B. einen RSS-Reader nutzen. Dann besuchen Sie einfach direkt die Blogseite zum Posting.)

<?xml version="1.0" encoding="utf-8"?> <fsm name="Robot" version="1.0" … > <states> <state name="start" type="init"/> <state name="end" type="final"/> <state name="idle"/> <state name="moving up"/> <state name="moving down"/> <state name="welding"/> </states> <transitions> <transition fromState="start" toState="idle" event="o"> printf(">>> initialize\n"); </transition> <transition fromState="idle" toState="end" event="o"> printf(">>> shut down\n"); </transition> <transition fromState="idle" toState="moving down" event="d"> printf(">>> move down\n"); </transition> <transition fromState="moving down" toState="moving down" event="d"> /* don't do anything */ </transition> <transition fromState="moving down" toState="idle" event="s"> printf(">>> stop moving\n"); </transition> <transition fromState="moving down" toState="moving up" event="u"> printf(">>> move up\n"); </transition> <transition fromState="moving down" toState="welding" event="c"> printf(">>> weld\n"); </transition> <transition fromState="welding" toState="moving up" event="u"> printf(">>> move up\n"); </transition> <transition fromState="moving up" toState="idle" event="s"> printf(">>> stop moving\n"); </transition> <transition fromState="moving up" toState="moving down" event="d"> printf(">>> move down\n"); </transition> </transitions> </fsm>

Das Eingangstag <fsm> steht für finite state maschine. Es folgt die Liste der (endlich vielen) Zustände, wobei der Start- und der Endzustand beliebig benannt werden können, sie dafür aber mit Hilfe des type-Attributes auszuweisen sind. Die Liste der Transitionen ist nahezu selbsterklärend. Die Aktionen geben wir als Programmcode in der Sprache C an. Das ist in dem Beispiel die Sprache, in der wir den Roboterarm programmieren, was nicht untypisch für Steuergeräte oder eingebettete Systeme ist. Zu Demonstrationszwecken ersetzen einfache printf-Statements "echte" Aktionen.

Das Interface des zu generierenden Codes -- Funktionsprototypen in C -- sieht wie folgt aus. Es ist absichtlich so einfach gehalten.


char * get_initState(void);
char * get_finalState(void);
char * get_toState(char *fromState, char *event);
void do_action(char *fromState, char *event);

Es ist einfach zu erraten, wie der generierte Code zu "get_initState" und "get_finalState" aussieht:


char * get_initState(void) { return "start"; }
char * get_finalState(void) { return "end"; }

Die Funktion "get_toState" liefert auf Angabe von "fromState" und "event" den dazugehörigen "toState" zurück. Ein Beispiel:


char * get_toState(char *fromState, char *event) {
  if (strcmp("idle",fromState) == 0 && strcmp("o",event) == 0)
      return "end";
}

Ein Kinderspiel, nicht wahr? Die Funktion "do_action" arbeitet ganz ähnlich, sie bettet im if-Rumpf den Aktionscode zur Transition ein:


void do_action(char *fromState, char *event) {
  if (strcmp("idle",fromState) == 0 && strcmp("o",event) == 0) {
    printf(">>> shut down\n");
}

Wenn wir einen Code-Generator haben, der die XML-Darstellung in diese Code-Schemata umwandelt, dann benötigen wir nur noch ein Abarbeitungsprogramm, das Steuerprogramm im Roboterarm, das auf Ereignisse wartet (Tastendrücke in unserem Beispiel), gemäß Zustandsmaschine die entsprechenden Aktionen ausführt und in einen neuen Zustand wechselt oder den bisherigen beibehält. (Die Funktion _getch() ist übrigens eine nicht standardgemäße Bibliotheksfunktion aus Pelles C zum Lesen eines Zeichens von der Tastatur.)

#include <stdio.h> #include <stdlib.h> #include <conio.h> // not C99 #include <assert.h> #include "fsm.c" int main() { char event[2] = "?"; // [0]: signal character, [1]: \0 (end of string) char * currentState; char * nextState; char * finalState; currentState = get_initState(); finalState = get_finalState(); printf("initializing: initState = %s, finalState = %s\n",currentState, finalState); assert (strcmp(currentState,finalState) != 0); // CONTROLLER for (;;) { printf("scanning ...\n"); event[0] = _getch(); printf("<<< signal %s\n",event); nextState = get_toState(currentState,event); if (strcmp(nextState,"") == 0) { printf("critical situation\n>>> move to safety position\n"); break; } do_action(currentState,event); currentState = nextState; if (strcmp(currentState,finalState) == 0) break; } printf("I'm done\n>>> shut down\n"); return EXIT_SUCCESS; }

Wie aus dem Code ersichtlich ist, ignoriert die Steuerung nicht etwa Ereignisse für die keine Transition in einem Zustand definiert ist, sondern aktiviert eine Safety-Routine. Das ist ein durchaus sinnvolles Vorgehen bei Steuerungsaufgaben, die im Fehlerfall schwerwiegende Folgen nach sich ziehen können.

Stellt sich nur noch die Frage, wie der Code-Generator aussieht. Ich habe ihn in Python programmiert. Das Programm ist nicht sonderlich elegant, erfüllt aber zur Anschauung seinen Zweck.

import sys, time from xml.dom.minidom import parse assert len(sys.argv) > 1, "file needed for code generation" fsm = parse(sys.argv[1]) states = fsm.getElementsByTagName("state") transitions = fsm.getElementsByTagName("transition") for state in states: statename = state.getAttribute("name") statetype = state.getAttribute("type") if statetype == "init": initState = statename elif statetype == "final": finalState = statename ## Assert that inital and final state are given assert initState, "An init state must be given" assert finalState,"A final state must be given" ## CodeGeneration: get_initState and get_finalState get_initState = 'char * get_initState(void) { return "%s"; }\n' % initState get_finalState = 'char * get_finalState(void) { return "%s"; }\n' % finalState ## Assert constraints on fromState and toState statenames = [state.getAttribute("name") for state in states] for transition in transitions: assert transition.getAttribute("fromState") in statenames,\ "fromState is given in list of states" assert transition.getAttribute("toState") in statenames,\ "toState is given in list of states" ## Assert determinism stateevents = [] for transition in transitions: stateevent = (transition.getAttribute("fromState"), transition.getAttribute("event")) assert stateevent not in stateevents, "FSM must be deterministic" stateevents.append(stateevent) ## CodeGeneration: get_toState ## ~~~~~~~~~~~~~~~~~~~~~~~~~~~ code = """ char * get_toState(char *fromState, char *event) { """ for state in states: for transition in transitions: if transition.getAttribute("fromState") == state.getAttribute("name"): code += """ if (strcmp("%s",fromState) == 0 && strcmp("%s",event) == 0) return "%s"; """ % (state.getAttribute("name"), transition.getAttribute("event"), transition.getAttribute("toState")) code += """ return ""; } // end of function """ get_toState = code ## CodeGeneration: do_action ## ~~~~~~~~~~~~~~~~~~~~~~~~~ code = """ void do_action(char *fromState, char *event) { """ for state in states: for transition in transitions: if transition.getAttribute("fromState") == state.getAttribute("name"): code += """ if (strcmp("%s",fromState) == 0 && strcmp("%s",event) == 0) { // ACTION CODE %s } """ % (state.getAttribute("name"), transition.getAttribute("event"), transition.firstChild.data) code += """ } // end of function """ do_action = code header = """/* THIS IS GENERATED CODE -- PLEASE DO NOT EDIT THIS FILE */ /* CodeGeneration by %s, %s */ #include <string.h> #include <stdlib.h> #include <stdio.h> """ % (sys.argv[0], time.ctime()) print header + get_initState + get_finalState + get_toState + do_action

Wenn Sie mögen, können Sie nun mit der Ergänzung um weitere Features beginnen. Wie wäre es mit hierachischen Zustandsmaschinen? Timer sind etwas sehr nützliches. Und wie wäre es mit nebenläufigen Zustandsmaschinen? Sehr leicht ist es, die Zustände um Aktionen zu bereichen. Ein Feature aus der UML sind Aktionen beim Eintritt (entry) und beim Verlassen (exit) eines Zustands. Transitionen kann man um Guards erweitern. Guards knüpfen das Ereignis an eine Bedingung, die zusätzlich erfüllt sein muss.

Sie werden feststellen, dass es gar nicht so schwer ist, sich ein XML-Schema für sehr komplexe und mit allen Featuren ausgerüstete Zustandsmaschinen auszudenken und dazu einen Code-Generator zu entwickeln.

(P.S.: Die an dieser Stelle zuvor berichteten Probleme mit dem Syntax-Highlighting haben sich gelöst. Allerdings scheint der Chrome-Browser Schwierigkeiten bei der Darstellung des letzten Code-Auszugs, dem Python-Code, zu haben. Strange! Kennt jemand einen Workaround?)

Nominiert für die Auslese08

2009-01-16T13:12:00.002+01:00

Ich rechne es meiner treuen Leserschaft zu, zwei meiner Beiträge für die Auslese08 im Wissenschaftscafe nominiert zu haben. Vielen Dank dafür -- es freut mich natürlich sehr, zur Vorschlagsliste der 80 Blogbeiträge zu gehören. Wenngleich ich mir keine Hoffnungen mache, in die engere Auswahl zu kommen. Ich habe auf noch keiner Party die Stimmung hochgepeitscht mit einer Frage wie "Was ist ein System?". Und Gedanken zu "Syntax und Semantik" lassen auch nicht jedes Herz höher schlagen :-) Spaß macht es mir dennoch, und es ist schön zu wissen, dass zumindest einige Leser solche Freuden mit mir teilen.

Let it float!

2009-01-09T14:15:00.005+01:00

Minus 50 plus 50 macht Null -- in manchen Fällen muss man sich so ein Ergebnis autorisieren lassen. Plus 38.29 minus 38.29 macht auch Null und -- wenn man es nicht so genau nehmen will -- sogar reich!

Von diesem schönen und oben abgebildeten Fehler berichtet Michael Haupt auf seinem Blog in dem Beitrag "Ich bin reich!". Ein Fehler mit Pilgerwert. Ob ich irgendwann einmal diesen Zettel anfassen und in den Händen halten darf? Das sollte ich bei meinem nächsten Besuch in Potsdam tun!

Herr Haupt wird genauso wie ich innigst hoffen, dass der Fehler von keinem unserer Studierenden "eingebaut" worden ist. Denn der Fehler ist fast so alt wie der erste Computer. Fließkommszahlen, floats, sollte man niemals auf Gleichheit überprüfen. Rundungsfehler können einem einen gewaltigen Strich durch die Rechnung machen (siehe oben). Finanzrechnungen sollte man stets genau rechnen, zum Beispiel in Cents und mit Integern und einem definierten Verhalten bei Rechnungen, die nicht in Cents sondern in gebrochenen Cents (z.B. bei einer Division) aufgehen.

Denken unter 150

2008-12-14T00:44:00.000+01:00

184 Puls. Die Zone, in der ich nur noch renne. Kein Gedanke, kein denken -- nur kämpfen. Ich laufe gegen meinen Körper an. Längst bin ich im anaeroben Bereich. Ich kann nicht mehr soviel Sauerstoff in meine Lungen pumpen, wie ihn mein Körper benötigt. Ich spüre regelrecht, wie meine Zellen auf Hochtouren laufend die letzten Energien mobilisieren. Alles schmerzt. Warum tue ich mir diesen Berg eigentlich an? Gleich ist Schluss. Noch 23 Sekunden, die muss ich noch durchhalten, irgendwie.

"Wie lautet die Binärzahl von 197?"

Wie bitte? Die Aufgabe hämmert in meinem Kopf. Noch 18 Sekunden. Ich kann jetzt nicht rechnen. Ich schaue auf die Uhr. Noch 16 Sekunden den Körper durch die Qual treiben. Mein Puls fällt ab. Ich kann das Tempo nicht mehr halten. 197 ist kleiner als 256 und größer als 128. Mehr bekomme ich reflexartig nicht hin. Kämpfen steht im Vordergrund. Bei dem Puls kann ich keinen klaren Gedanken fassen. Wie auch? Ich versuche gerade meinen Körper zu bezwingen, das Limit noch für einen Moment aufrecht zu erhalten. Noch 6 Sekunden. Wie langsam die Zeit vergehen kann. Nicht aufgeben. Noch 4 Sekunden. Ja, gleich -- in meinem Kopf tobt der Wahnsinn. Ich kämpfe mit jedem Gedanken gegen all die Körpersignale an, die nicht mehr in 2 Sekunden, sondern sofort aufhören wollen. Da, 0 Sekunden. Erlösung.

Stoppuhr an!

Wie lange dauert es, bis ich einen "Denkpuls" erreicht habe? Bis sich mein Körper soweit von der Belastung erholt hat, dass mein Hirn wieder bereit für Input ist? Dass es bereit ist für eine Aufgabe? Dass es die Aufgabe lösen kann?

Im Moment geht gar nichts. Ich atme tief und heftig. Spucke auf den Asphalt. Luft. Luft. Ich will nur atmen. In meinen Ohren, überall hämmert der Puls. Aber er fällt. Jetzt ist er unter 176. Denken? Nein. Geht nicht. Ich gehe. Die Schmerzen lassen nach. Der ganze Körper lechzt nach Erholung.

Ab welchem Puls kann ich die Aufgabe lösen? Wie lautet die Binärzahl von 197?

Erste Denkreflexe melden sich. 197 ist größer als 128, hatten wir schon, also haben wir "ganz links" eine 1. Ungerade Zahl, also "ganz rechts" eine 1. Sonst? Achja, 8 Bits reichen.

Mehr geht nicht. Mein Puls fällt. So langsam regelt sich die Atmung wieder ein. 160 Puls. Erste Gedanken raten mir zu einem systematischen Vorgehen. Nächste Bitstelle? 64. Was ergibt 128 plus 64. Es fühlt sich nach weniger als 197 an. Wieviel weniger? Eine einfache Addition. Im Kopf -- derzeit unmöglich. Ich brauche noch etwas Pause.

Ich wage einen neuen Versuch. Puls knapp über 150. 128 plus 64 macht etwas mehr als 180, fehlen noch 8 plus 4, also 12. 192, das könnte sein. Ich habe noch kein Vertrauen in meine Denke. Vieles ist mechanisch abgeleitet. Eine echte Kontrolle im Hirn fehlt. Dafür bin ich noch zu sehr aus der Puste.

Ich spekuliere weiter. 128 plus 64 macht 192. Die 197 war gegeben, bleiben 5 übrig. Eine 1 hatte ich schon für das Ungerade-sein spendiert. Bleiben noch 4 übrig. Ok. Bitmuster "ganz rechts" 101, Bitmuster "ganz link" 11. Ich komme etwas zur Ruhe. Bin kurz vor 140 Puls. Jetzt weiß ich's. Ich habe fünf Bitstellen berechnet, noch drei weitere Bitstellen mit Null fehlen. Ergebnis: 11000101. Uff.

Hätte ich mir eine ernstere Aufgabe gestellt, ich bin mir sicher, erst in einem Bereich von 120 bis 130 Puls wäre eine Problemlösung möglich, mit ersten sinnvollen Gedanken um die 140 abwärts.

Angeregt zu diesem (virtuellen) Experiment hat mich das Buch von Josh Waitzkin: The Art of Learning -- An Inner Journey to Optimal Performance, Free Press, 2007. Er beschreibt in diesem Buch seine Lernerfahrungen als junges Schachgenie und später als Kampfsportler. In beiden Disziplinen ist bzw. war er sehr erfolgreich. Wem weder das Schachspiel noch der Kampfsport fremd sind, der wir seine Freude an diesem Buch haben und es vielleicht genauso wie ich verschlingen. Denn faszinierend sind seine Berichte und Einsichten schon, praktisch und anwendbar sind sie auch. So berichtet er unter anderem davon, wie wichtig der Zusammenhang zwischen körperlicher Fitness und der Fähigkeit zu sehr kurzer geistiger Erholung ist -- um Hochleistungen erbringen zu können, geistige ebenso wie sportliche. Es ist auch ein Weg, um bessere Klausuren schreiben und Prüfungen ablegen zu können.

Das ist die eine Buchempfehlung, die ich zu Weihnachten für Sie habe. Die andere ist ein Buch von John Medina: Brain Rules -- 12 Principles for Surviving and Thriving at Work, Home, and School, Pear Press, 2008. Und da erfahren wir, dass schon ein wenig körperliche Ertüchtigung die geistige Performanz boostet. Das ist Regel Nr. 1. Weitere elf Regeln verraten Ihnen noch mehr darüber, wie unser Gehirn tickert und wie wir gut mit ihm umgehen können. Selbst wenn Sie sich für das Buch nicht weiter interessieren, besuchen Sie die Webseite zu den Brain Rules -- es lohnt sich.

Syntax und Semantik

2008-11-17T22:37:00.001+01:00

Was ist Syntax, was ist Semantik? Diese zwei Begriffe beschäftigen mich immer wieder, siehe zum Beispiel auch "Uniform Syntax" (23. Feb. 2007). Beide Begriffe spielen eine entscheidende Rolle bei jeder Art von maschinell-verarbeitbarer Sprache. Vom Dritten im Bunde, der Pragmatik, will ich an dieser Stelle ganz absehen.

Die Syntax bezieht sich auf die Form und die Struktur von Zeichen in einer Sprache, ohne auf die Bedeutung der verwendeten Zeichen in den Formen und Strukturen einzugehen. Syntaktisch korrekte Ausdrücke werden auch als "wohlgeformt" (well-formed) bezeichnet.

Die Semantik befasst sich mit der Bedeutung syntaktisch korrekter Zeichenfolgen einer Sprache. Im Zusammenhang mit Programmiersprachen bedeutet Semantik die Beschreibung des Verhaltens, das mit einer Interpretation (Auslegung) eines syntaktisch korrekten Ausdrucks verbunden ist.

[Die obigen Begriffserläuterungen sind angelehnt an das Buch von Kenneth Slonneger und Barry L. Kurtz: Formal Syntax and Semantics of Programming Languages -- A Laboratory Based Approach, Addison-Wesley, 1995, Kapitel 1.]

Die Grenze zwischen Syntax und Semantik ist fließend und lässt sich schön am Beispiel mit Hilfe regulärer Ausdrücke erläutern. Spezifizieren wir eine Syntax für die Angabe der Uhrzeit. Gemeint sind minutengenaue Zeitangaben im 24-Stunden-Format.

Ein einfacher regulärer Ausdruck beschreibt die Syntax sehr direkt: "\d\d:\d\d" -- dieser Ausdruck kam schon in der Einführung "Reguläre Ausdrücke" zur Anwendung und ist dort ausführlich beschrieben. Dieser reguläre Ausdruck ist zu allgemein, denn die Angabe "14:72" wäre genauso möglich wie "25:13". Das sind keine Uhrzeitangaben. Ein regulärer Ausdruck, der nur gültige, 4-stellige Zeitangaben erlaubt, ist "([01]\d)|(2[0-3]):[0-5]\d".

Worauf es mir hier ankommt, ist Folgendes: Der erste reguläre Ausdruck spezifiziert eine Uhrzeitsyntax, die so allgemein gefasst ist, dass eine Nachverarbeitung (Teil der Semantik(!)) prüfen muss, ob die Kombination von Stunden und Minutenangaben eine gültige Uhrzeit ist. Der zweite reguläre Ausdruck hingegen erfasst gültige, vierstellige Uhrzeitangaben vollständig syntaktisch. Jegliche Weiterverarbeitung, sprich jegliche Semantik kann sich darauf verlassen, mit ausschließlich gültigen Uhrzeitangaben zu arbeiten.

Wir beobachten an diesem Beispiel, dass es einen Spielraum gibt, was Syntax und was Semantik in einer Sprache ist. Je allgemeiner die Syntax, desto mehr Form- und Strukturwissen muss als Teil der Semantik behandelt werden. Je spezifischer die Syntax ist, desto weniger muss sich die Semantik um eine Erkennung bemühen. Im Idealfall ist die Semantik von aller Klärung befreit, wenn die Syntax eindeutig ist.

Im Fall der Uhrzeit ist es relativ leicht möglich, Uhrzeitangaben vollständig syntaktisch zu spezifizieren. Das geht nicht immer. Nehmen wir Datumsangaben. Eine vollständige syntaktische Spezifikation, welche Monate 30 bzw. 31 Tage haben, ist noch machbar -- ob sie sinnvoll ist, ist die Frage. Denn spätestens für den Monat Februar ist mit regulären Ausdrücken nicht mehr entscheidbar, ob 28 oder 29 Tage die korrekte Angabe sind. Es sind 29 Tage, sofern das Jahr ein Schaltjahr, also durch 4 teilbar ist. Es bleibt jedoch bei 28 Tagen, wenn die Jahreszahl durch 100 teilbar ist, nicht jedoch durch 400. Eine Datumsangabe kann nicht vollständig syntaktisch erkannt werden -- es sei denn, die Syntax hätte Rechenfähigkeiten.

Und damit sind wir genau an dem Punkt angelangt, was Syntax von Semantik unterscheidet: Syntax ist der Anteil einer Sprachdefinition, der gültige Zeichenfolgen einer Sprache erkennt (Form- und Strukturerkennung) und zwar mit einem Formalismus, der keine Rechenfähigkeit hat, sprich, der nicht Turing-äquivalent ist. Dieser syntaktische Anteil liefert die Vorverarbeitung. (In der Theorie der formalen Sprachen sind damit reguläre (Typ-3) bzw. kontextfreie (Typ-2) Grammatiken gemeint, siehe Chomsky-Hierarchie.). Die Semantik betrifft alle weitere Symbol-Verarbeitung, die mit einem Formalismus beschrieben ist, der Turing-äquivalent ist.

Mit diesem Verständnis von Syntax und Semantik kann man sinnvoll den Begriff der syntaktischen Obergrenze definieren: Die syntaktische Obergrenze reizt die Form- und Strukturerkennung aus und minimiert den semantischen Anteil, der eventuell notwendig ist, um die Erkennung von Formen und Strukturen eindeutig zu machen. Zum Beispiel beschreibt ein regulärer Ausdruck die syntaktische Obergrenze für eine Datumsangabe im Format "Tag-Monat-Jahr" (TT-MM-JJJJ), wenn semantisch einzig die Tagesangabe für den Februar überprüft werden muss. Das Muster "\d\d-\d\d-\d\d\d\d" liegt offensichtlich nicht an der syntaktischen Obergrenze. Der Semantik-Anteil muss umfangreiche Gültigkeitsprüfungen vornehmen.

Man kann in diesem konkreten Beispiel auch auf einen Formalismus für die Syntax zurückgreifen, der zwar Rechenfähigkeiten hat, in seinem Verarbeitungshorizont jedoch strikt begrenzt ist. Dann liegt eine kontextsensitive Grammatik vor (Typ-1). Kontextsensitive Grammatiken sind eher die Ausnahme. (Anmerkung: Grundsätzlich ist auch ein Formalismus für die Syntax denkbar, der Turing-äquivalent ist (Typ-0), allerdings fällt dann die Grenzziehung zwischen Syntax und Semantik schwer. Ein anderes Kriterium muss dann gefunden werden.)

Meine These ist, dass diese Zerlegung einer Verarbeitung in einen Anteil, der aus einem nicht Turing-äquivalenten Mechanismus und einem Turing-äquivalenten Mechanismus besteht, ein stets wiederkehrendes Thema in der Informatik ist. Pipe-Filter-Architekturen sind ein Beispiel, die Zerlegung eines Programms in Interfaces und Verhalten ein anderes. Interessanterweise habe ich bislang keinen Hinweis darauf gefunden, dass dieses Zerlegungsmuster bereits von jemand anderem postuliert worden wäre. Ich glaube, man könnte dieses Zerlegungsmuster sehr viel systematischer in der Software-Entwicklung einsetzen.

Ein Anmerkung, siehe im vorletzten Absatz, ist hinzu gekommen, um die Diskussion etwas abzurunden. (2008-11-18)

Studieren mit der PS3

2008-11-04T01:36:00.000+01:00

Ungefähr 1000 PS3-Spielkonsolen dürften in etwa der Rechenleistung unseres Gehirns gleichkommen. Vielleicht ist das eine gewagte Schätzung, so ganz seriös sind solche Computer/Hirn-Vergleiche nie. Aber wer als "Niko" Bellic in die Welt von GTA IV eintaucht, dem wird diese Zahl vermutlich gar nicht so abwegig vorkommen. Es ist unglaublich, wieviel Welt so eine Spielkonsole simulieren kann.

In der PS3 leistet ein Spezialprozessor, der Cell-Chip, diese beachtliche Arbeit. Ein etwa 10 Jahre altes Rechenzentrum im Schachtelformat. Mehrere Einheiten arbeiten parallel und fressen Zahlen, was das Zeug hält.

Es hat eine ganz eigene Faszination, wenn man Linux auf die PS3 installiert und sich die Konsole zum ersten Mal meldet. Man hat Kontakt mit dieser geballten Rechenkraft aufgenommen. Plötzlich gehorcht sie einem aufs Wort. Und irgendwie hört man die Maschine nach Arbeit rufen. Das bisschen Linux, die paar Befehle, die über die Konsole reinwandern, die machen so ein Maschinchen nicht müde. Da steht ein Apparat, der es gewohnt ist, Sie durch Häuserschluchten zu jagen, Ihnen Aliens aufzuhetzen, Sie unter Beschuss zu nehmen und Ihnen wilde Verfolgungsjagden zu liefern. Diese Maschine hat Hunger! Diese Maschine sucht die Herausforderung und die Auseinandersetzung!

Nehmen Sie die Herausforderung an?

Geben Sie der Maschine Futter, programmieren Sie die PS3 selbst! Jagen Sie die PS3 mit Ihren Programmen an den Rand des Machbaren! Fangen Sie da an, wo der PC schlapp macht!

Einen Start bietet Ihnen unsere Webseite http://ps3.hs-heilbronn.de.

Einladung in die Schreibbar

2008-10-27T10:53:00.001+01:00

Daran kommt keine Studentin und kein Student vorbei: am Verfassen einer wissenschaftlichen Arbeit. Früher gab es (in den technisch orientierten Fächern) die Studien- und die Diplomarbeit, jetzt ist eine Bachelor oder Master Thesis zu schreiben. Seinerzeit hatte man die Chance, sich mit der Studienarbeit auf die Diplomarbeit vorzubereiten. Die Studienarbeit war so etwas wie eine Fahrschule zum wissenschaftliche Arbeiten und Schreiben. Jetzt geht es mit der Bachelor oder Master Thesis relativ unvorbereitet auf die Wissenschaftspiste. Plötzlich muss man alles beherrschen: das Zitieren, das Referenzieren, das Gliedern, Schreiben, Bewerten, Recherchieren etc. Es macht es nicht einfacher, dass man für eine Bachelor Thesis nicht gerade viel Zeit hat.

In der Schreibbar, "da werden Sie geholfen"! Die Schreibbar möchte das erste deutschsprachige Blog sein, das das wissenschaftliche Arbeiten zum Thema hat und Studierenden dabei Hilfestellung und Anleitung bietet. Die Schreibbar hat einen gewissen Fokus auf technisch-orientierte Fächer, aber sie wird in ihrem Themenspektrum sicher vielen Studierenden eine Hilfe sein.

Schauen Sie doch einfach mal vorbei. Meine Mitstreiterinnen und ich, wir würden uns auf Ihren Besuch freuen.

Link: schreibbar.wordpress.com

Reguläre Ausdrücke

2008-10-20T11:46:00.001+02:00

Eine typische Aufgabenstellung, mit der sich ein Software-Entwickler bzw. eine Software-Entwicklerin immer wieder konfrontiert sieht, ist die Verarbeitung von Textdateien. In der Regel interessiert die Verarbeitung von Textdateien oder Zeichenströmen, die von Maschinen für Maschinen gedacht sind. Solche Textdateien folgen klaren, eindeutigen Regeln des Aufbaus. Sonst ist die maschinelle Verarbeitung eher schwierig bis unmöglich.

Bei der Verarbeitung von Textdateien bzw. Zeichenströmen kommt man an regulären Ausdrücken (regular expressions) nicht vorbei. Mit ihnen kann man Zeichenfolgen in einem Text suchen und weiter verarbeiten. Reguläre Ausdrücke stehen in praktisch jeder Programmiersprache als nachladbare Bibliothek zur Verfügung (so z.B. in Java) oder sie sind bereits fester Bestandteil der Sprache (wie z.B. in Perl oder JavaScript). Jeder moderne Texteditor erlaubt die Suche nach Zeichenketten mit Hilfe von regulären Ausdrücken.

Reguläre Ausdrücke selbst sind Zeichenketten (strings). Die in dem String verwendeten Zeichen folgen bestimmten Vereinbarungen (Konventionen). Zum Beispiel steht die Zeichenfolge "\d" in einem regulären Ausdruck nicht für die Folge der Zeichen "\" und "d". Der Backslash "\" ist ein sogenanntes escape symbol. Die normale Bedeutung des Zeichens "\" als Backslash wird ausgehebelt. Zusammen mit dem "d" bekommt es eine Sonderfunktion. Die Zeichen "\d" stehen für eine beliebige Ziffer (digit) von 0 bis 9. Gleichwertig dazu ist der reguläre Ausdruck "[0-9]". In der Tat ist "\d" nicht mehr als eine Kurzform für "[0-9]". Die eckigen Klammer haben ebenso wie der Backslash eine Sonderbedeutung. Die zwischen den eckigen Klammern gelisteten Zeichen stellen Alternativen dar. Ein "[012]" steht entweder für eine "0" oder eine "1" oder eine "2". Ein Digit ist also ein "[0123456789]". Die von/bis-Notation "[0-9]" verkürzt den Schreibaufwand.

Und was ist, wenn man die Sonderbedeutung von "\", "[" bzw. "]" aufheben möchte? Dann kommt wieder das Escape-Zeichen, der Backslash, zum Einsatz. Ein "\\" meint genau das Zeichen "\". Und ein "\[" bzw. "\]" schaltet die Sonderbedeutung der eckigen Klammern aus und meint nun ausdrücklich die Zeichen "[" und "]".

Nachfolgende ist eine kurze Einführung in die Arbeit mit regulären Ausdrücken in der Programmiersprache Python gegeben. Diese Einführung ist weder vollständig noch umfassend. Ziel ist, Ihnen die Einstiegshürde zu nehmen.

In Python werden reguläre Ausdrücke über eine Bibliothek (ein Modul) zur Verfügung gestellt.


>>> import re

Ist die Suche nach einem Muster erfolgreich, liefert das re-Modul ein "Muster erkannt"-Objekt zurück. Schlägt die Suche fehl, wird None als Wert ausgeliefert.


>>> re.search("ll","hello")
<_sre.SRE_Match object at 0x00B8DBB8>
>>> re.search("ll","hexxo")
>>> re.search("ll","hexxo") == None
True

Neben der search-Methode steht auch eine match-Methode zur Verfügung. Ein Match erwartet im Gegensatz zum Search eine Passung des regulären Ausdrucks mit dem Anfang des übergebenen Strings. Bei Search wird im gesamten String nach dem Muster gefahndet.


>>> re.search("ll","hello")
<_sre.SRE_Match object at 0x00B8DB80>
>>> re.match("ll","hello")

Zur effizienten Verarbeitung können reguläre Ausdrücke intern compiliert werden. Das macht vor allem dann Sinn, wenn ein Muster mehrfach zum Einsatz kommt.


>>> hhmmRE = re.compile("\d\d:\d\d")
>>> hhmmRE
<_sre.SRE_Pattern object at 0x00B24870>
>>> hhmm = hhmmRE.search("It's 14:00!")
>>> hhmm
<_sre.SRE_Match object at 0x00B8DC28>

Match-Objekte bieten eine Reihe von Methoden an. Man kann z.B. den zum Muster passenden String erfragen oder sich die Position des Muster-Treffers im String angeben lassen.


>>> hhmm.group()
'14:00'
>>> hhmm.start()
5
>>> hhmm.end()
10
>>> hhmm.string
"It's 14:00!"
>>> hhmm.string[hhmm.start():hhmm.end()]
'14:00'

Teile eines regulären Ausdrucks können in Gruppen strukturiert werden. Auf die einzelnen Teile kann dann über das Match-Objekt zugegriffen werden. Angenommen, wir wollen die Stunden und die Minuten einer Uhrzeitangabe separat erfassen. Runde Klammern in einem regulären Ausdruck markieren Gruppen, die von 1 an aufsteigend durchgezählt werden.

Zusätzlich verbessern wir unser Suchmuster dahingehend, dass auch Uhrzeiten mit einstelliger Stundenangabe (z.B. 7:00 Uhr) erkannt werden. Ein Fragezeichen markiert als Sondersymbol die Optionalität des voranstehenden Zeichens. Ein "\d?" steht für einen Digit, der optional ist.


>>> hhmmRE = re.compile("(\d?\d):(\d\d)")
>>> hhmm = hhmmRE.search("Let's meet at 2:00 pm.")
>>> hhmm
<_sre.SRE_Match object at 0x00B97578>
>>> hhmm.group(1)
'2'
>>> hhmm.group(2)
'00'

Gruppen können auch mit sprechenden Namen assoziiert werden, was aus software-technischer Sicht zu empfehlen ist. Beim Durchzählen von Gruppen kann sich ein Programmierer oder eine Programmiererin leicht verzählen. Referenzbezüge mit sprechenden Namen sind weniger fehleranfällig.

Eine benamte Gruppe wird mit "(?P<name>...)" markiert.


>>> hhmmRE = re.compile("(?P<hh>\d?\d):(?P<mm>\d\d)")
>>> hhmm = hhmmRE.search("Let's meet at 13:45.")
>>> hhmm.group("hh")
'13'
>>> hhmm.group("mm")
'45'

Soweit der Einstieg mit Python. Es gibt noch eine Menge zu regulären Ausdrücken zu entdecken. Sie sind ein leistungsfähiges Werkzeug bei der Verarbeitung von Strings.

Es lohnt nicht unbedingt, sich ein Buch zu regulären Ausdrücken zuzulegen, auch wenn es zu diesem Thema exzellente Werke gibt. Einen raschen Überblick zur Historie und zum theoretischen Hintergrund liefern Ihnen beispielsweise der deutsche und der englische Wikipedia-Eintrag. Dort finden Sie auch etliche hilfreiche Weblinks. Im "Tagesgeschäft" sollte die Dokumentation zu den regulären Ausdrücken in der von Ihnen verwendeten Programmiersprache vollends ausreichen.

Zuweisung, Verzögerung, Rekursion - alles Lambda, oder was?!

2008-09-27T10:24:00.006+02:00

Es mag Spaß machen, einigermaßen komplexe Programme in eine einzige, unleserliche Zeile zu stopfen. In der Programmiersprache Perl sind die "one-liners" ja beinahe Kult.

Von geradezu didaktischem Wert ist die Konstruktion von Einzeilern für Python von Dan Piponi. Bei ihm lernt man, was die Mächtigkeit von Lambda-Ausdrücken ausmacht. Zuweisung, Verzögerung, Rekursion -- das alles kann man leicht mit Lambdas ausdrücken. Mit ihrer Hilfe kann man sich beliebige Einzeiler basteln, siehe "On writing Python one-liners".

Nicht, dass ich Sie zu Einzeilern ermutigen möchte. Aber Lambda-Ausdrücke sollte jeder Programmierer kennen. Sie sind die Wunderwaffe der funktionalen Programmierer!

Objekt-orientierte Parser-Kombinatoren in Python

2008-09-23T11:27:00.001+02:00

Ich möchte Ihnen eine Technik zur Syntaxanalyse vorstellen, die zwar gar nicht so neu ist, aber immer wieder Aufmerksamkeit erregt. Zum Beispiel in der Smalltalk-Gemeinde durch einen Beitrag von Gilad Bracha zu Newspeak ("Executable Grammars in Newspeak"). In der Haskell-Welt machen Parser-Kombinatoren und die Forschung zu ihnen immer wieder von sich reden, siehe z.B. aktuell "Parser Combinators for Ambiguous Left-Recursive Grammars" von R.A. Frost, R. Hafiz und P. Callaghan, PADL 2008.

Im Folgenden setze ich voraus, dass Sie wissen, was ein Parser ist und Ihnen auch die EBNF zur Darstellung von Grammatiken bekannt ist. Wenn wir weiter unten von einer Parser-Funktion reden, dann meinen wir eine Funktion, die einen String entgegennimmt, diesen parst und ein geeignetes Ergebnis der Parse-Analyse zurückgibt.

Der Begriff des Kombinators kommt aus der Ecke der funktionalen Programmiersprachen. Ein Kombinator ist eine Funktion höherer Ordnung, eine Higher-Order Function (HOF), die selbst eine Funktion zurückgibt. Eine HOF ist eine Funktion, die Funktionen als Argumente entgegennimmt und gegebenenfalls eine Funktion zurückgibt. Von einem Kombinator wird dann gesprochen, wenn die HOF syntaktisch als Infix notiert werden kann. Anschaulich: Statt der bei Funktionen verbreiteten Prefix-Notation combinatorX(functionA,functionB) steht in der Infix-Notation der Kombinator in der Mitte: functionA combinatorX functionB. Damit wird hervorgehoben, dass der Kombinator, ähnlich einem Operator wie etwa "+", zwei Funktionen "kombiniert".

Ein Parser-Kombinator verknüpft Parser-Funktionen und liefert selber eine Parser-Funktion zurück. Nehmen wir an, wir haben eine Parser-Funktion token(), die Token erkennt. Angenommen, der Parser-Kombinator für Sequenzen oder Folgen von Parser-Funktionen kann mit einem Komma "," notiert werden. So lässt sich dann sehr kompakt ein Parser ausdrücken, der zwei Token-Parser als Sequenz kombiniert: token("Hell"),token("o"). Mit dieser Schreibweise kann die Struktur einer EBNF-Beschreibung einer Grammatik direkt als Kombination von Parser-Funktionen ausgedrückt werden. Die Funktionen bilden die Struktur einer EBNF-Beschreibung nach ("function follows form").

Da der Parser-Kombinator selber wieder ein Parser ist, können wir ihn mit einem String aufrufen: (token("Gut"),token("en"))("Guten Tag!")

In vielen Programmiersprachen ist es nicht so ohne weiteres möglich, die Syntax zur Schreibweise von Funktionen zu ändern. Eine Infix-Notation verbietet sich meist. So bleibt einem nur, Parser-Kombinatoren in der nicht ganz so eleganten Prefix-Notation zu nutzen. Ein sehr schönes Beispiel, wie man mit Python Parser-Kombinatoren bauen kann, liefert ein Autor namens "Stefan" (Kürzel "sma") im deutschen Python-Forum in dem Beitrag "Kleine Parser-Kombinator-Bibliothek" (16. Feb. 2008, 16:31). Wenn Sie diesen Beitrag lesen, werden Sie das Folgende besser verstehen.

Will man einen Parser-Kombinator konsequent objekt-orientiert anlegen, dann wird die Idee der Kombination von Parser-Funktionen abgelöst durch eine Kombination von Parser-Objekten, die wieder ein Parser-Objekt statt einer Parser-Funktion liefern. Die Kombination von Objekten, die wieder ein Objekt zurückliefern ist sehr elegant und einfach realisierbar durch Konstruktor-Methoden.

Werden wir konkret. Mit den folgenden zwei Parser-Klassen führen wir einen Token-Parser bzw. einen Parser für reguläre Ausdrücke ein. In Python kann man Objekte aufrufbar (callable) machen, indem man sie mit einer __call__-Methode ausstattet. Ein Objekt wird damit gleichermaßen zu einer "zustandsbehafteten Funktion". Die __repr__-Methode dient zur Überschreibung der standardmäßigen Selbstrepräsentation eines Objekts, vergleichbar mit der "toString"-Methode in anderen Sprachen.


import re, types

class Parser(object): pass

class Token(Parser):
    def __init__(self,token,annotation=None):
        self.token, self.annotation = token, annotation
        assert isinstance(annotation,types.StringType) or annotation == None
    def __call__(self,text):
        if text.startswith(self.token):
            return Node(self,self.token), text[len(self.token):]
        return None, text
    def __repr__(self):
        return "Token('" + str(self.token) + "')"

class RegExp(Parser):    
    def __init__(self,regexp,annotation=None):
        self.regexp, self.annotation  = re.compile(regexp), annotation
        assert isinstance(annotation,types.StringType) or annotation == None
    def __call__(self,text):
        match = self.regexp.match(text)
        if match: return Node(self,match.group()),text[match.end():]
        return None, text
    def __repr__(self):
        return "RegExp(" + str(self.regexp.pattern) + ")"

Schauen wir uns einmal den Gebrauch der Token-Klasse über die Kommandozeile an:


>>> Token("Hey")
Token('Hey')
>>> Token("Hey")("Hey!")
(Hey, '!')
>>> Token("Hey")("Heu")
(None, 'Heu')
>>>

Der Token-Parser liefert immer ein Tupel zurück. Der erste Teil des Tupels ist None, wenn der Parser nicht erfolgreich ist. Bei Erfolg wird ein Knoten-Objekt zurückgegeben. Der zweite Teil des Tupels ist der String-Anteil, den es noch zu parsen gilt. Bei Erfolg ist es der Rest-String (hier "!"), bei Misserfolg der gesamte übergebene String ("Heu").

Hier, der Vollständigkeit halber, der Code zu Node, den Sie der Parser-Klasse voranstellen müssen:


class Node(object):
    def __init__(self,parser,result):
        self.parser = parser
        self.result = result
    def __repr__(self): # reconstruct the parsed input
        if self.result == None: return ""
        if isinstance(self.result,types.TupleType):
            assert all([isinstance(e,Node) for e in self.result])
            return "".join([str(element) for element in self.result])
        return str(self.result)

Nun wird es interessant. Kommen wir zu den Kombinatoren der Parser-Objekte um Sequenzen bzw. Alternativen abzubilden:


class NaryOperator(Parser):
    def __init__(self,annotation="",*parsers):
        assert all([isinstance(parser,Parser) for parser in parsers])
        assert isinstance(annotation,types.StringType)
        self.parsers, self.annotation = parsers, annotation

class Sequence(NaryOperator):    
    def __init__(self,annotation,*parsers):
        NaryOperator.__init__(self,annotation,*parsers)
        assert len(self.parsers) >= 1
    def __call__(self,text):
        results = ()
        text_ = text
        for parser in self.parsers:
            node, text_ = parser(text_)
            if not node: return None, text
            results += (node,)
        assert len(results) == len(self.parsers)
        return Node(self,results), text_
    def __repr__(self):
        return "("+",".join([str(parser) for parser in self.parsers])+")"
        
class Alternative(NaryOperator):
    def __init__(self,annotation,*parsers):
        NaryOperator.__init__(self,annotation,*parsers)
        assert len(self.parsers) >= 1
    def __call__(self,text):
        for parser in self.parsers:
            node, text_ = parser(text)
            if node: return Node(self,node), text_
        return None, text
    def __repr__(self):
        return "("+"|".join([str(parser) for parser in self.parsers])+")"

Sie sehen, dass ich die Annotation von Parser-Objekten erlaube, womit später die Verarbeitung des erzeugten Parsebaums vereinfacht wird. Das soll hier aber nicht unser Thema sein. Schauen wir uns den Gebrauch der Parser-Kombinatoren an:


>>> s = Sequence("",Token("Gut"),Token("en"))
>>> s
(Token('Gut'),Token('en'))
>>> s("Guten Tag!")
(Guten, ' Tag!')
>>> s("Was ein Tag!")
(None, 'Was ein Tag!')
>>> a = Alternative("",Token("Gut"),Token("en"))
>>> a
(Token('Gut')|Token('en'))
>>> a("Guten Tag!")
(Gut, 'en Tag!')
>>> a("Tag!")
(None, 'Tag!')

Parser-Kombinatoren sind also tatsächlich selbst wiederum Parser -- genau so soll es sein!

Lassen Sie uns noch ein paar einwertige Parser-Kombinatoren hinzufügen, damit wir alles zusammen haben, um eine Grammatik vollständig beschreiben zu können:


class UnaryOperator(Parser):
    def __init__(self,parser,annotation=None):
        assert isinstance(parser,Parser)
        assert isinstance(annotation,types.StringType) or annotation == None
        self.parser, self.annotation = parser, annotation

class Optional(UnaryOperator):
    def __call__(self,text):
        node, text = self.parser(text)
        if node: return Node(self,node), text
        return Node(self,None), text
    def __repr__(self):
        return str(self.parser) + "?"

class ZeroOrMore(UnaryOperator):
    def __call__(self,text):
        results = ()
        while True:
            node, text = self.parser(text)
            if not node: break
            results += (node,)
        return Node(self,results), text
    def __repr__(self):
        return str(self.parser) + "*"

class OneOrMore(UnaryOperator):
    def __call__(self,text):
        results = ()
        text_ = text
        while True:
            node, text_ = self.parser(text_)
            if not node: break
            results += (node,)
        if results == (): return None, text
        return Node(self,results), text_
    def __repr__(self):
        return str(self.parser) + "+"

Ein Konsolenbeispiel zu OneOrMore:


>>> OneOrMore(Token('a'))('aaabbbccc')
(aaa, 'bbbccc')
>>> OneOrMore(Token('a'))('bbbccc')
(None, 'bbbccc')

Wir sind fast am Ziel! Wenn Sie eine Grammatik aufschreiben, in der es rekursive Bezüge gibt, werden Sie auf ein Problem stoßen. Probieren Sie mal Folgendes:


group   = Sequence("group",Token("{"),doc,Token("}"))
config  = Sequence("config",Token("["),doc,Token("]"))
comment = Sequence("comment",RegExp(r'%.*\n'))

doc = ZeroOrMore(Alternative("doc",comment,config,group))

Sie können nicht in "group" auf "doc" verweisen, bevor Sie "doc" eingeführt haben! Würden Sie die Regel von "doc" dem "group" voranstellen, hätten Sie dasselbe Problem, nur anders herum.

Eine Lösung ist, eine Delay-Klasse einzuführen, mit der Sie ein Parser-Objekt anlegen und seine "Logik" per set-Methode nachrüsten. In einer OO-Umgebung ist das eine sehr einfache Lösung, in einer funktionalen Programmierumgebung müssten Sie sich etwas anderes einfallen lassen.


class Delay(Parser):
    def set(self,parser,annotation=None):
        assert isinstance(parser,Parser)
        assert isinstance(annotation,types.StringType) or annotation == None
        self.parser = parser
        self.annotation = annotation
    def __call__(self,text):
        return self.parser(text)
    def __repr__(self):
        if self.parser.annotation:
            return "{"+ str(self.parser.annotation) + "}"
        return "{" + self.parser.__class__.__name__ + "}"

Nun können wir die aus dem letzten Post vorgestellte einfache Grammatik für LateX ("Eine einfache Grammatik für LaTeX") mit unserem objekt-orientierten Parser-Kombinator beschreiben und mit ihr arbeiten:


doc = Delay()

text = RegExp(r"[^\\\{\}\[\]%]+","text")

group   = Sequence("group",Token("{"),doc,Token("}"))
config  = Sequence("config",Token("["),doc,Token("]"))
comment = Sequence("comment",RegExp(r'%.*\n'))

commandToken = RegExp(r"\\\\?[^\\\{\}\[\]%\s]*","commandToken")

commandConfig = Sequence("commandConfig",Optional(comment),config)
commandGroup  = Sequence("commandGroup" ,Optional(comment),group)

command = Sequence("command",
                   commandToken,
                   Optional(commandConfig,"head"),
                   ZeroOrMore(commandGroup,"tail"))
                   
doc.set(ZeroOrMore(Alternative("doc",command,comment,config,group,text)))

Ein erster Härtetest einer jeden Grammatik ist, ob der geparste Input als Output wieder erzeugt werden kann. Wenn Sie Spaß daran haben, probieren Sie es einmal mit einem LaTeX-File.

(Eine Anmerkung am Rande: Die Konstruktortechnik, hier zur Kombination von Parser-Objekten verwendet, habe ich schon einmal kurz erwähnt in dem Blogbeitrag "Uniform Syntax")

Eine einfache Grammatik für LaTeX

2008-09-18T01:06:00.003+02:00

Informatiker schreiben ihre Artikel, Berichte und Arbeiten natürlich mit TeX bzw. mit LaTeX -- sonst gehört man einfach irgendwie nicht dazu ;-) Es gibt unzählige Erweiterungen (im LaTeX-Slang "packages" genannt), die ebenso unzählige Features und Gimmicks nachrüsten für so ziemlich jedes Problem, das man sich vorstellen kann.

Für die Überarbeitung eines Artikels hatte mir der Verlag die Auflage gemacht, alle Änderungen zur vorigen Version hervorzuheben. In Microsoft Word ein Klacks, in LaTeX zugegebenermaßen ein Umstand. Aber mit \usepackage{changes} steht einem glücklicherweise ein Paket zur Verfügung, das an dieser Stelle aushilft. So übersäte ich mein LaTeX-Dokument mit \added{...}, \deleted{...} und \replaced{...}{...}.

Für eine erneute Überarbeitung wollte ich nun die vielen Änderungsauszeichnungen aus dem LaTeX-Dokument entfernen und zwar so, dass die Änderungen selbst im Text zurückbleiben. Natürlich automatisch und nicht per Hand. Das heißt, etwas vereinfacht gesagt: In dem LaTeX-Dokument können die \deleted{...}-Auszeichner samt Inhalt einfach verschwinden, von einem \added{...} muss der Inhalt in der geschweiften Klammerung erhalten bleiben, von einem \replaced{...}{...} nur der Inhalt der ersten geschweiften Klammerung.

Diese kleine Herausforderung ist ein fast klassisches Informatik-Problem. Die Anwendung von regulären Ausdrücken für einfache Ersetzungen funktioniert in LaTeX nicht, da LaTeX-Auszeichner verschachtelt sein können und somit das schließende Ende zu einer geöffneten geschweiften Klammer "{" nicht zuverlässig gefunden werden kann. Also muss man das LaTeX-Dokument parsen. Da TeX seine Grammatik zur Laufzeit ändern kann, ist auch das im Prinzip ein hoffnungsloses Unterfangen -- doch ganz so schlimm ist es in der Realität erfreulicherweise nicht. Für 99.99% aller LaTeX-Dokumente kommt ein sehr regelmäßiges Schema zum Tragen. Nur findet man dazu wenig im Netz.

Ich habe mir einen Parser in Python geschrieben (einen "Parser Combinator"), mit dem ich mit einigen einfachen Grammatiken für LaTeX-Dokumente experimentiert habe. Hier das Ergebnis, das mir für meine Zwecke gereicht hat:


text   := RegExp(r"[^\\\{\}\[\]%]+")

group  := "{" doc "}"
config := "[" doc "]"
comment := RegExp(r'%.*\n')

commandToken := RegExp(r"\\\\?[^\\\{\}\[\]%\s]*")

commandConfig := comment? config
commandGroup  := comment? group

command := commandToken commandConfig? commandGroup*

doc := ( command | comment | config | group | text )*

Ein kleiner Hinweis: Der reguläre Ausdruck für "text" schließt alle die Zeichen aus, die bei "group", "config" und "comment" eine Sonderrolle haben. Auf diese Weise holt sich der Parser mit "text" immer möglichst zusammenhängende Textblöcke rein, ohne jedoch die Trigger "\[]{}%" für die anderen Regeln zu überlaufen.

Wenn Sie also mal in der Verlegenheit sind, eine Nachverarbeitung für LaTeX-Dokumente vornehmen zu müssen, so mag Ihnen diese einfache Grammatik den Einstieg möglicherweise erleichtern.

Sollte ich einmal Zeit dazu haben, dann erkläre ich Ihnen, wie man sich in einer objekt-orientierten Sprache einen Parser Combinator schreibt. Das geht erstaunlich einfach.

Add-ons for Chrome - or - A new architecture for browsers

2008-09-07T00:38:00.001+02:00

On September 2nd, on Tuesday, Google released Chrome -- their own web browser. Chrome has a simple, unobtrusive user interface, it's based on WebKit, it's powered by a new JavaScript implementation, it runs a process for each new tab, and it promises a new approach to safe browsing. On this one, Chrome failed. Chrome has some severe security holes Google needs to fix. Nonetheless, I like the new browser.

Some hours after Google had released Chrome, I read a lot of comments about the Chrome experience. Most users seemed to be quite enthusiastic, some few were not. But one sort of comments caught my attention: Some folks argued that Firefox users will stay with Firefox. Why? Because of all these nice add-ons you can extend Firefox with.

My spontaneous reaction was: Who needs add-ons?

Before you laugh at me. I run Firefox with extensions like Firebug, Web Developer, ScrapBook and others. I use them extensively and like them a lot. Who wants to miss Firebug, for instance? Nobody, right?! I wouldn't use a browser without my beloved add-ons. And one is for sure. A browser without extension capabilities won't make it in the long run. (Ok, I'm not sooo sure.)

So what made me think "Who needs add-ons"?

I contemplated some time over my spontaneous reaction. Forgive me, I don't know much about how to write extensions for Firefix. I am an extension user, not an extension programmer. But my gut feeling tells me that the approach to extensions in Firefox is wrong. It's the worst Google could do to copy the extension mechanism of Firefox. I should rephrase my first reaction: "Who needs such an add-on architecture?"

Instead of criticizing Firefox's extension mechanism, of which I don't know much about, let me sketch an alternative approach to extensions.

Assume a "naked" browser: no buttons to click on, no url field, no menu, nothing. Assume that all the browser does after startup is run a JavaScript program. Let's call this program the "Controller". The key point is: You can change the Controller. Don't like the default Controller? Change it. The Controller is under your control!

The default Controller is a JavaScript program that creates buttons to click on and implements a history of web pages visited. It provides the url input field and displays suggestions while you type. It lets you have menus and so on.

Got it? The Controller is a program that creates a user interface that mimics Firefox. Or Chrome. Or IE. Or Opera. Or Safari. Whatever you want.

If you type in a url in the url field and hit enter, it's the Controller, which -- so to speak -- creates an IFrame and loads the given web page into that frame. So the web page remains fully under control of the Controller.

It does not require that much imagination to see that the Controller can easily be extended by -- right, by extensions or add-ons. These extensions are just other JavaScript programs, which are plugged into the Controller.

To oversimplify things, I envision a browser, which consists only of an HTML and CSS rendering engine and a virtual machine running JavaScript. The rest is initiated by an ordinary JavaScript program using web technology. In other words: My favorite browser is fully programmable with web technology.

The idea is simple, isn't it? It thrills me.

The development of such a "naked" browser inevitably raises questions like:

How do we guarantee that the Controller doesn't loose control?

How do we compose add-ons? How do we avoid interference of add-ons?

Do we need a component architecture? Or do we need a service-oriented architecture?

How do we ensure safe browsing and secure execution?

It's much about architecture thinking and a JavaScript implementation that supports fundamental notions of modularization, safety and security. These are aspects which should IMHO drive the standardization activities of JavaScript. Implementors of browsers should radically rethink the way browsers are built and function. Google did a first, tiny step in that direction with Chrome. But there's more to strive for.

Multi-Stage Programming in Scheme

2008-09-03T09:09:00.001+02:00

Vor nicht allzu langer Zeit habe ich mich in einem Beitrag mit "Multi-Stage Programming" (MSP) beschäftigt. Ich warf in dem Blog-Posting die Frage auf, ob MSP im Grunde nicht mit der Makroprogrammierung wie z.B. in Scheme oder Lisp vergleichbar sei.

In der Tat kann das MetaOCaml-Beispiel, die Auflösung der Power-Funktion, sehr leicht mit defmacro, dem Urmakro aus Lisp, in Scheme nachgebildet werden. Hier kommt PLT-Scheme zum Einsatz -- mit Dank an Tim für den Code:


(require (lib "defmacro.ss"))
; POWER MACRO 
(define-macro power
  (lambda (n x)
    (if (= n 0)
        '1
        `(* ,x (power ,(- n 1) ,x)))))
(power 2 4)

Stellt man dem Code in PLT-Scheme noch ein


(require (lib "../macro-debugger/expand.ss"))

voran und gibt dann interaktiv ein


(expand/step '(power 2 2))

ein, dann öffnet sich ein Fenster zum schrittweisen Makroauflösen. Ich habe ein wenig mit den Check-Boxen experimentiert: Mit "Enable macro hiding?" und "Hide mzscheme syntax" sieht die Auflösung unkryptisch aus.

Nun lese ich die Tage von Oleg Kiselyov etwas über "MetaScheme, or untyped MetaOCaml". In seinem Beitrag implementiert er "the four MetaOCaml special forms -- bracket, escape, cross-stage persistence (aka `lift'), and run -- in R5RS Scheme." Er argumentiert, dass eine 1:1-Übersetzung der MetaOCaml Special Forms in Scheme ("MetaOCaml's bracket is like quasiquote, escape is like unquote, and `run' is eval") nicht zum gewünschten Ergebnis führt. Vor allem übersieht Scheme die Bindungsstrukturen, die MetaOCaml natürlich sauber berücksichtigt.

Kiselyov bietet die MetaOCaml Special Forms als Macros für R5RS an, die nun dasselbe Verhalten zeigen wie die Special Forms in MetaOCaml. Eine beeindruckende Lösung, die -- wie alles bei Kiselyov -- ein tiefes Verständnis für Scheme aufweist. Sie verrät aber auch, wie MSP implementiert werden kann.

Eine Einsicht bleibt dennoch: Macros sind der Fast Track zu MSP in Scheme bzw. Lisp -- ohne Netz und doppelten Boden.

Browsing aufpoliert: Google Chrome

2008-09-02T09:03:00.005+02:00

Firefox, Opera, Safari, Internet Explorer -- die großen "Player" im Browser-Markt versuchen sich immer wieder an neuen, oft kleinen Features, die das Surfen im Internet angenehmer, komfortabler, sicherer und vielleicht auch ein wenig spaßiger gestalten sollen. Jüngst stellte Microsoft seinen neuen Internet Explorer 8 in der Beta-Version vor.

Seit gestern ist es semi-offiziell. Google möchte heute der Welt einen eigenen und etwas anderen Browser bescheren: Google Chrome ("A fresh take on the browser", 1. Sep. 2008). Man scheint es sehr ernst zu nehmen. Ein unterhaltsames Comic soll den Anwender bzw. die Anwenderin vom Vorteil und Nutzen des aufpolierten Browser-Modells überzeugen: "Google Chrome: Behind the Open Source Browser Project".

Technisch hat man das Browser-Modell auf neue Beine gestellt. Mehrere Webseiten lassen sich, wie gehabt, über Tabs gleichzeitig öffnen und organisieren. Doch nun stellt jeder Tab einen eigenen Prozess dar, was echte Parallelität liefert. So blockiert eine "hängende" Seite in einem Tab nicht die Arbeit des ganzen Browsers und damit der anderen Tab-Seiten. Erstaunlich, dass es zu diesem Mehr-Prozess-Fundament des Engagements von Google bedurfte. Doch scheint dieses Feature zusammen mit der neuen JavaScript-Engine namens V8 in der Techie-Szene bereits Begeisterung hervorzurufen (John Resig: "Google Chrome Process Manager"). Selbstredend ist auch Google Gears in Google Chrome integriert. Und Chrome soll open-source sein!

Ich bin gespannt -- und warte schon auf den Link zum Download! Bis dahin: Haben auch Sie viel Spaß an der Vorfreude mit dem Comic.

[[Update: Zwei Tipps zu Chrome. Der Browser verrät einige Interna durch sogenannte "about"-Seiten, siehe "Google Chrome's about:Pages". Ein paar Bedienhinweise liefert "Google Chrome Tips".]]

Zu den Ursprüngen: Das Internet

2008-08-26T16:54:00.003+02:00

Ich weiß nicht, ob Sie auch zu den Freaks gehören, die gerne technische Standards lesen und sich immer mal wieder auf den RFC-Seiten der IETF, der Internet Engineering Task Force, wiederfinden. Manche mögen die technischen Sachverhalte, die in den "Request for Comments" (RFCs) dargelegt sind, für langweilig halten. Ich finde sie spannend. Man lernt eine Menge über das Internet. Wie es funktioniert, welche Ideen es angeleitet und getrieben haben und welche Konzepte und Ideen den einzelnen Netzschichten und Protokollen zugrunde liegen. Eine Unmenge an interessanten Informationen findet sich da, frei verfügbar und für jeden zugreifbar. Ein Wissen, das nicht unbedingt in den Lehrbüchern zu den "Rechnernetzen" oder "Web-Technologien" zu finden ist.

Via Ehrensenf (Sendung vom 26. August) bin ich auf eine wunderbare Webseite der National Science Foundation (NSF) gestoßen. Auf der Seite "NSF and the Birth of the Internet" setzen sich die Amerikaner medial sehr gelungen als Erfinder und Pioniere des Internets in Szene und erzählen seine Geschichte. Eine Geschichte mit Menschen zum "Anfassen", ein Zurückblättern in eine Welt, in der es noch keine Blogs, Chats, ICQs, EMails, Internet-Telefonie und all das gab. Unvorstellbar, nicht wahr?

Vielleicht können Sie nach dem Besuch der NSF-Seite nachvollziehen, warum ein Blättern und Lesen in den alten RFCs aus den 80ern so aufregend und spannend sein kann. Leider lassen die jüngeren RFCs einiges an Qualität und Brillanz vermissen, die noch die "alten" RFCs auszeichnete.

Multi-Stage Programming

2008-08-15T11:55:00.005+02:00

Neben den Programmiersprachen gibt es eine Vielzahl von verschiedenen Techniken und Ansätzen des Gebrauchs, des Einsatzes, der Verwendung und der Erweiterung von Programmiersprachen. Alle diese Techniken bzw. Ansätze enden auf "Programming": Generative Programming, Aspect-Oriented Programming, Object-Oriented Programming, Context-Oriented Programming, Subject-Oriented Programming -- es gibt unzählige solcher Bezeichnungen. Hinter den meisten dieser Namen stecken interessante Ansätze, die auf nur wenigen Konzepten oder Ideen beruhen.

In den vergangenen Tagen habe ich mich mit "Multi-Stage Programming" (MSP) beschäftigt. Dieser Blog-Beitrag ist eine Aufbereitung des Papers "A Gentle Introduction to Multi-Stage Programming" von Walid Taha. Das Paper ist auf seiner Publikationsseite zu finden. Alle Zitate und Code-Beispiele stammen aus dem Paper.

Ich bitte um Nachsicht und um Korrekturen, sollten sich in der folgenden Darstellung des Papers von Taha Fehler finden. Ich bin kein MSP-Experte und bringe dazu auch keine hands on-Erfahrung mit. Auch über klärende Kommentare freue ich mich, insbesondere, was den Vergleich mit Makros angeht.

---

Multi-Stage Programming (MSP) ist eine besondere Form der generativen Programmierung und damit eine Technik der Meta-Programmierung. Zwei Gedanken führen zum MSP: (1) Programmgenerierung bringt einige Probleme mit sich, die in der Generierungsproblematik selber liegen, die also inhärent sind. (2) Es gibt wenig Unterstützung für die Erstellung von Generatoren in Hochsprachen wie Java oder C.

MSP ist der Ansatz mit einer Sprache zu arbeiten, die ausdrücklich zur Generierung von Programmen in ihrer eigenen Sprache geeignet ist und die die mit der Programmgenerierung verbundenen Probleme vermeidet.

Was sind die Probleme?

Man kann Programme in Textform mit Strings generieren. Das Problem: Man kann Programme konstruieren, die syntaktisch ungültig sind.

Eine andere Option ist, ein Programme durch Datentypen zu kodieren, z.B. mit einem abstrakten Syntaxbaum (AST). Es werden immer syntaktisch korrekte Programme zurück geliefert. Das Problem: Datentypen können zwar syntaktische korrekte Programme garantieren, nicht aber, ob diese auch well-typed sind.

MSP nimmt sich dieser Problematik an: MSP stellt sicher, dass ein generiertes Programm syntaktisch korrekt und well-typed ist. Darüber hinaus verhindert MSP Namenskonflikte und unbeabsichtigte Variablenübernahmen. Das klingt gut, besonders, wenn man mit statisch typisierten Sprachen arbeiten möchte.

Drei Basiskonzepte für MSP in MetaOCaml

MetaOCaml ist eine Erweiterung zu OCaml für MSP. Lediglich drei Konzepte werden in der Sprachwelt von OCaml mit MetaOCaml verankert mit denen eine typkonforme Manipulation von Programmfragmenten in OCaml möglich ist.

Brackets ".< >." können einen Ausdruck (expression) umgeben. Sie verzögern seine Ausführung. Brackets konservieren einen Ausdruck als Code-Fragment zur späteren Berechnung (= Compilierung und Ausführung), im Beispiel ".<1+2>.":


# let a = 1+2;;
val a : int = 3
# let a = .<1+2>.;;
val a : int code = .<1+2>.

Neben der Verzögerung weiß ein Bracket um den Typen, den ein geklammerter Ausdruck im Falle der Ausführung zurück gibt. Oben kann man sehen, wie "int code" als Typ auf der Kommandozeile ausgegeben wird. Die Typen "int code" und "int" sind unterschiedlich und lassen sich nicht mixen. Ein "1 + .<5>." ist nicht erlaubt.

Mit einem Escape ".~" können verzögerte Ausdrücke zu neuen verzögerten Ausdrücken komponiert werden. Das "a" bezieht sich aus dem vorangegangenen Beispiel.


# let b = .<.~a * .~a >. ;;
val b : int code = .<(1 + 2) * (1 + 2)>.

Schlussendlich wird mit einem Run ".!" ein verzögerter Ausdruck compiliert und ausgeführt:


# let c = .! b;;
val c : int = 9

Eine Funktion, die Brackets und Escapes enthält (anscheinend auch Annotationen genannt), wird als staged bezeichnet; eine normale Funktion ohne Annotationen als "unstaged". Mit den Annotationen kann die Reihenfolge der Ausführung (evaluation order) explizit spezifiziert werden.

That's it! So einfach sich das anhört, aber gerade die eingebaute Typsicherheit bringt es mit sich, dass man in der Tat nur gültige Programme aus verzögerten Ausdrücken komponieren kann. Für dynamisch typisierte Sprachen wäre das nicht möglich. Mit MSP kann man Staged Interpreters bauen. Sie gelten als ebenso einfach zu bauen wie "normale" Interpreter, sind aber nahezu so effizient wie Compiler.

The primary goal of MSP is to help the programmer reduce the runtime overhead of sophisticated abstraction mechanisms.

Staged Programms = Programming with Makros?

Es schleicht sich allmählich der Verdacht ein, dass es sich bei Bracket, Escape und Run lediglich um ein Makrosystem handelt, das darauf achtet, typkonforme Konstrukte zu erzeugen. Trifft dieses Mapping auf Lisp zu, wenn man mal von der Typisierung absieht? Bracket = Quote, Escape = Makrodefinition, Run = Makroauflösung?

Ein Beispiel, das diese Beobachtung stützt findet sich in Kapitel 2.2 "A Classic Example". Die Power-Funktion x^n löst sich auf in die n-fache Anwendung der Multiplikation von x. x^3 liefert also x*x*x. Das kann in einer rein funktionalen Programmiersprache nur iterativ ausgedrückt werden. In MetaOCaml sieht das wie folgt aus:


let rec power (n, x) =
match n with
0 -> 1 | n -> x * (power (n-1, x));;

Nehmen wir an, wir machen häufig Gebrauch von der Quadratfunktion power2:


let power2 (x) = power (2,x);;

Oder alternativ in etwas anderer Ausdrucksweise, die wir unten wieder verwenden werden:


let power2 = fun x -> power (2,x);;

Ärgerlich ist der Overhead, das bei jeder Quadrierung der parametrisierte Aufruf power(2,x) eine Rekursion ausführt. Das führt zu Performanzverlusten. Günstiger wäre es, power2 iterationslos auf "x*x" abzubilden. Annotieren wir power(n,x) entsprechend, dann kann man diese Auflösung forcieren:


let rec power (n, x) =
match n with
0 -> .<1>. | n -> .<.~x * .~(power (n-1, x))>.;;

Damit hat sich aber auch der Typ des zweiten Arguments (x) verändert: Hier muss ein Code vom Typ Integer übergeben werden, z.B. .<3>., so dass power (2,.<3>.) aufgelöst wird zu:


.< .<3>. * .<3>. * .<1>. >.

Das ist auch der Grund, warum der match-Fall für 0 abgebildet wird auf .<1>. und nicht 1, so sonst die Multiplikation nicht mehr konform Typen vom Typ "code of type int" verkettet.

Folglich kann nun power2 definiert werden über eine staged function:


let power2 = .! . .~(power (2,..))>.;;

power2 erzeugt eine verzögerte Funktion mit x als Eingabeparameter. Bereits zur Compilezeit wird über das Escape ein Aufruf der Funktion power vorgenommen (so verstehe ich das zumindest), wobei x via .. typmäßig angepasst wird. Der Aufruf von power liefert ein verzögertes x*x*1 zurück. Das Run .! erlaubt dem Compiler auch diesen Code gleich weiter zu übersetzen, so als ob er direkt x*x*1 übersetzt hätte.

Das Ergebnis ist also, dass wir über das power-"Makro", Code generieren konnten, der so effizient ist wie handgeschriebener Code für power2.

In Kapitel 3 "Implementing DSLs Using Staged Intepreters" demonstriert Taha, wie man mit stage programming eine DSL umsetzen kann, die im Stil eines Interpreters geschrieben wird, durch Staging jedoch soviel wie möglich zur Compilezeit erledigt. Im Endeffekt soll damit zur Ausführungszeit der DSL eine Performanz erreicht werden, die der Performanz entspricht, hätte man einen Compiler für die DSL geschrieben. Natürlich ist mit einem Compiler als Zielsprache die Implementierungssprache gemeint, mit der auf der staged Interpreter geschrieben wird. Ansonsten ist der Vergleich natürlich absurd. So heißt es bei Taha:

A staged interpreter is a translator

Das Paper demonstriert an einer sehr simplen DSL den Bau eines Staged Interpreters, und merkt dann an: "... further reserach is need [Schreibfehler im Original] to show that we can apply MSP to realistic programming languages.". Das heißt: Wir müssen noch lernen, unserer MSP strukturiert in verschiedenen Themenbereichen einzusetzen.

Der Computer als "verlängertes" Hirn

2008-08-11T22:47:00.005+02:00

Schließen Sie die Augen! Konzentrieren Sie sich! Gehen Sie in Gedanken durch das Zimmer oder den Raum, in dem Sie sich gerade befinden. Beginnen Sie, vor Ihrem geistigen Auge die Möbel umzuräumen. Wie wäre es mit ein paar Pflanzen in der Ecke? Bekommen sie dort genug Licht? Lassen Sie die Morgensonne durch das Fenster scheinen. Dann die Mittags- und zu guter letzt die Abendsonne. Gefällt Ihnen, wie sich die Lichtverhältnisse ändern? Geht es der Pflanze an ihrem Standort gut? Streichen Sie die Tapeten in Gedanken einmal rot, blau oder gelb. Wie wäre es mit grün? Mehr hellgrün oder dunkelgrün?

Ihnen geht es sicher wie mir. Ich bin mit meiner Vorstellungskraft überfordert. Ich kann mein Arbeitszimmer gedanklich zwar irgendwie einfärben, aber willentlich klare Farben aussuchen und diese Szenerie vor dem geistigen Auge so zu betrachten als sei es real -- unmöglich. Wie ich mir Lichteindrücke vorstellen soll, ich habe keine Ahnung.

Prof. Dr. Temple Grandin kann sowas. Sie beschreibt es in ihrem Buch "Thinking in Pictures". Ihr Gedächtnis speichert "Filme". Sie hat die Fähigkeit, sich in ihrer "Filmwelt" dreidimensional zu bewegen und die Welt aus verschiedenen Blickwinkeln zu betrachten. Sie kann auch Änderungen in der Vorstellungswelt vornehmen. Wir dürfen uns das vermutliche wie eine Simulationswelt denken, in der man beliebige Kamerafahrten machen und beliebige Eingriffe durchspielen kann. So eine Art Grand Theft Auto IV im Kopf. Wobei man nicht nur Spieler, sondern auch Spieleentwickler ist. Frau Grandin nutzt ihre Begabung zum Entwurf von Anlagen zur Viehhaltung und -schlachtung.

Es ist beeindruckend, zu welchen Ausnahme-Leistungen unser Gehirn in der Lage ist. Doch der Preis für solche Inselbegabungen scheint hoch zu sein. Temple Grandin ist Autistin. Autismus ist eine Entwicklungsstörung, die die betroffenen Menschen in ihrem Vermögen zu sozialer und kommunikativer Interaktion erheblich einschränkt. Frau Grandin ist insofern eine Ausnahme, als dass sie einen Weg der Kommunikation mit uns Nicht-Autisten gefunden hat.

Doch es geht mir in diesem Beitrag weniger um den Autismus. Als ich das erste Kapitel zu Grandins Buch las, war ich beeindruckt von dieser Fähigkeit. Mit solchen Hirnleistungen kann man Dinge tun und erreichen, die Otto-Normal-Hirn verwehrt sind.

Oder?

Ja, das ist richtig. Aber wir Menschen haben uns ein wunderbares Werkzeug erschaffen, das sozusagen als "verlängertes" Hirn fungieren kann: der Computer. Mit einem Computer können wir Simulationen durchführen. Wir können uns in selbst erschaffenen Welten bewegen, können Autos crashen lassen ohne einem Dummy ein Haar zu krümmen. Wir können das Wetter vorhersagen, die Höhe der Altersrente errechnen, Risikoanalysen durchführen und und und.

Aber nutzen wir dieses Werkzeug eigentlich systematisch?

Haben Sie in Schule, Ausbildung oder Studium jemals mit Simulationen gearbeitet? Haben Ihre Lehrer, Ausbilder oder Dozenten Sie dazu animiert, selber Gedankenexperimente mit dem Rechner auszuführen. Sei es um Häuser an virtuellen Baugruben zu errichten, um zu verstehen, wie ein Staubsauber funktioniert (Wie saugt man Luft an?) und wie es auf Autobahnen zu Staus aus dem Nichts kommen kann. Welche einfachen Regeln erklären die Streifen auf dem Zebra? Haben Sie's mal am Rechner ausprobiert? Heute schon die zu erwartende Projektdauer per Monte-Carlo-Simulation ermittelt?

Der Computer ist ein wunderbares Werkzeug. Jedem von uns steht diese "Hirnprothese" zur Verfügung. Nur nutzen wir sie nicht. Jedenfalls nicht zur Modellierung und Simulation alltäglicher Phänomene. Wir haben's nicht gelernt, den Rechner als Verstehens- und Entscheidungshilfe zu verwenden; haben nicht einmal die richtigen Programme dazu zur Hand und auf dem Rechner installiert. Eigentlich schade.

Im Kampf gegen Monstersysteme

2008-08-04T11:31:00.005+02:00

Im Urlaub war es wieder soweit: Das, was wir Informatiker den Menschen um uns herum so zumuten, das machte mir ein fürchterlich schlechtes Gewissen.

Was war geschehen? Eigentlich nichts spektakuläres. Die Vermieterin unserer Ferienwohnung brauchte Hilfe bei der Einrichtung ihres neu erworbenen Laptops. In drei Stunden war der Rechner mit Windows Vista hergerichtet, die neuesten Updates installiert, Flash Player, Adobe Reader, OpenOffice nachgerüstet -- das Übliche halt. Schon dabei wurde mir ganz mulmig.

Und dann, am nächsten Abend, begann ich der guten Frau eine Einführung in Vista zu geben. "Hier klicken, da klicken, gucken Sie mal, alles ganz einfach, dann hier klicken, da klicken. Huch, die Firewall meldet sich. Wissen Sie, was das ist? Nein? Egal, hier klicken, da klicken, dann geht's weiter. Lassen sie sich von sowas nicht irritieren." Was fühlte ich mich elend. "Wenn Sie Ihre Kochrezepte anschauen wollen, hier klicken, da klicken, sehen Sie, OpenOffice startet, dann hier klicken, da klicken. Voilà. Einfach, gell?" Und ich wusste, dass ich log. Nix einfach! Ganz und gar nicht einfach. Da sitzt eine ältere Frau neben mir, die ich in einer Informationsflut ertränkte, die gerade einmal ins Internet möchte, EMails und Briefe schreiben will, vielleicht einmal mit Videotelefonie übers Internet Familienkontakte pflegen möchte und ansonsten an die Archivierung und den Ausbau ihrer Sammlung von Kochrezepten denkt.

Wozu muss so jemand ein komplexes Betriebssystem erlernen? Was belästigen wir die Menschen mit der Nachfrage zu Software-Updates? Welche Arten von Entscheidungen verlangt da eigentlich eine Firewall? Warum muss Otto-Normal-Verbraucher erst einen VHS-Kurs zu OpenOffice machen, bevor er oder sie sich einigermaßen in den Büro-Programmen zurechtfindet?

Warum in aller Welt sind unsere Betriebssysteme, Browser und Anwendungen so kompliziert?

Wir sind's selber schuld! Wir erschaffen wahre Monster, derer wir selber nicht mehr Herr sind. Auf dem "Workshop on Self Sustaining Systems (S3) 2008" am Hasso-Plattner-Institut (HPI) illustrierte Ian Piumarta Mitte Mai als Invited Speaker die Komplexität heutiger Systeme anhand folgender Zahlen: Windows Vista besteht seinen Angaben zufolge aus 50 Millionen Zeilen Programmcode, Mac OSX aus 86 Millionen Zeilen, OpenOffice aus 10 Millionen Zeilen Code (Links zum Foliensatz und zum Talk "Late-bound Object Lambda Architectures" als Video). Solche Systeme sind allein ihrer schieren Größe wegen von einem Entwickler bzw. einer Entwicklerin nicht mehr überschau- und verstehbar. Kein Wunder, das ein BugFixing das nächste jagt und manche Probleme oder Fehler über Monate, wenn nicht gar Jahre, im System bleiben, obwohl sie bekannt sind.

Kann es sein, dass wir den Bau solcher Systeme grundlegend falsch angehen? Piumarta glaubt, dass das alles viel einfacher geht, gehen muss, dass es auch mit 20.000 Zeilen Code möglich sein muss, eine Umgebung auf einem Rechner zu erstellen, die all das abdeckt, was moderne Betriebssysteme bereitstellen. Mit 20.000 Zeilen Code ist eine Größe erreicht, die einem 400 Seiten-Buch entspricht. Ein Umfang, der von einem Menschen in wenigen Wochen vollständig erfassbar und verdaubar ist.

Ich glaube, dass Piumarta mehr als Recht mit seinem Anliegen hat. Die Systeme, die wir heutzutage bauen, sind zu komplex. Es geht einfacher, es muss einfacher gehen. Piumarta selbst liefert in seinem Vortrag einige Beispiele dazu. Wir müssen lernen Systeme zu bauen, die einfach und klein im Kern sind, damit einfach verstehbar sind, und skalieren. Erst damit schaffen wir die Grundlage für Systeme, die vielleicht irgendwann auch einmal einfach bedienbar sind und sich zuschneiden lassen auf die Bedürfnisse ganz spezieller Nutzergruppen.

Wer sich für solche Überlegungen interessiert, dem sei der oben verlinkte Vortrag ans Herz gelegt. Über das zugrunde liegende Objektsystem habe ich schon einmal berichtet im Beitrag "'Open, reusable object models' in Python". Mehr an solchen radikalen Überlegungen lassen sich beim Viewpoint Research Institute unter "Fundamental New Computer Technologies" finden. Geistiger Urheber vieler dieser Gedanken ist übrigens Alan Kay, ein Urgestein der Informatik.

Hinweis: Monster-Bild von Kaptain Kobold

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

2008-07-10T13:52:00.005+02:00

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

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

Einleitung

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

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

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

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

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

Programmcode: EmptyList, Cons, Pair, List

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

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


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

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

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

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

Programmcode: EmptyStack und Stack

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


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

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

Diskussion

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


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

Paare können direkt erzeugt werden.


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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

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

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

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

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

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

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

17 Fragen

2008-07-07T17:14:00.004+02:00

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

Komponenten-Orientierung: Service vs. Funktionsbaustein

2008-06-24T11:48:00.002+02:00

Wenn man sich mit Komponenten-Orientierung befasst, wird man feststellen, dass es zwei "Schulen" gibt, die etwas unterschiedliche Sichten auf den Komponenten-Begriff haben. Die eine Denkschule hat die Enterprise Applications vor Augen. Bei den Unternehmensanwendungen stehen Themen wie Persistenz, Transaktionen, Verteilung, Webservices etc. im Vordergrund. Im Systems Engieering dominieren hingegen Gesichtspunkte der Modularisierung und Komposition.

Für einen Systems Engieer kann jede Software-Komponente grundsätzlich auch durch einen funktionsgleichen Baustein aus Hardware ersetzt werden -- und umgekehrt. Für Enterprise-Entwickler wird eine Komponente als Software-Einheit gesehen, die vielmehr einen Service realisiert, der zur Erfüllung definierter Aufgaben herangezogen werden kann. Der Systems Engineer baut Systeme, die er aus Komponenten und Subsystemen zusammensetzt. Der Enterprise-Entwickler baut Netze von Mehrwertdiensten, die aus der Kollaboration (möglicherweise transparent verteilter) mehrerer Services entstehen.

So erklärt sich auch, dass in der Enterprise-Welt etwa im Java Kontext die Plain Old Java Objects (POJOs) als Basis für eine Komponente vollauf genügen. Vom Entwickler wird lediglich gefordert, seine POJOs so weit als möglich nur gegen Interfaces zu programmieren. Komponenten-Frameworks wie Spring erledigen dann den Rest. Sie kümmern sich um die Verschaltung von Komponenten, um das Lifecycle-Management und bieten einfache Anbindungen an andere Service-Komponenten, die Persistenz, Zugriffssteuerung etc. ermöglichen.

Systems Engineers benötigen einen konzeptionellen Überbau, wenn Software-Einheiten als Komponenten fungieren sollen. Denn die meisten objekt-orientierten Programmiersprachen bieten keine Komposition an. Objekte lassen sich via Referenzen zwar zu Kollaborationsnetzen verschalten (die Denke der Enterpriseler), nicht jedoch zu Kompositionsbeziehungen. Eine Komponente ist ein Container, der andere Komponenten kapselt und verwaltet. In der Kommunikation zwischen Komponenten arbeiten Systems Engineers typischerweise mit Nachrichten, nicht mit Methoden-Aufrufen. Methoden-Aufrufe sind zu software-spezifisch; Nachrichten taugen in einem Harware- wie auch in einem Software-Umfeld zur Kommunikation. Sie machen alle Kommunikation per se asynchron und frei von impliziten Objekt-Referenzen.

Es ist wichtig, von dieser Unterscheidung zu wissen. Die UML 2 bietet beiden "Schulen" Möglichkeiten zur Modellierung von Komponenten an. Nur kümmert sich die UML nicht darum, den Werkzeugkasten zur Modellierung in die Fächer "Service-Komponenten" und "Komponenten als Funktionsbausteine" zu zerlegen. Darum muss sich der Modellierer selber kümmern.

Alles ist ein Eingabegerät

2008-06-18T19:35:00.004+02:00

Ich weiß, ich bin spät dran, wenn schon Spiegel-Online darüber berichtet in "Massenmordversuch an der Maus" (Christian Stöcker, 18. Juni 2008). Aber diese Idee ist so schön und abgefahren, das muss man sich ansehen -- ich habe ein Faible für solche Ideen (siehe auch "Sichtweisen in 3D: Balance halten"). Genug der Worte. Nehmen Sie eine Flasche, einen Tacker, einen Stift, Ihren Fingerverband, was auch immer ... oder eine Maus, und legen Sie los:

Ärgern Sie sich auch darüber, weder selbst darauf gekommen zu sein, noch -- falls Sie die Idee hatten -- es umgesetzt zu haben?

Was könnte man damit alles machen? Haben Sie Ideen?

Von der falschen Rede

2008-06-13T14:45:00.000+02:00

Eine kleine Anekdote: In der Vorlesung zu den Grundlagen der Informatik sprach ich heute von Rekursion und Iteration. Ich erklärte, was Rekursion ist. Die Studierenden merkten auf und unterbrachen mich: "Sie meinen Rekursion!". "Wie bitte? Habe ich etwas anderes gesagt?" "Ja, sie sagten Iteration." "Oh sorry, ich meinte Rekursion." Da hatte mir mein Hirn einen Streich gespielt, der mir vollkommen unbemerkt blieb. Ich glaubte mich etwas sagen zu hören, was ich nicht gesagt hatte. Kennen Sie das? Haben Sie bestimmt auch schon einmal erlebt.

Also startete ich einen neuen Versuch "Rekursion ist, wenn sich die Funktion selber wieder aufruft." Und schoss die Frage hinterher: "Habe ich Rekursion gesagt?" "Ja", lautete die Antwort unisono.

Während ich weiter sprach, blieben meine Gedanken an der letzten Frage hängen: Irgendwie war die Frage dumm gewesen. Stellen Sie sich einmal vor, das wäre nur mein Gedanke, meine Sprachabsicht gewesen. Tatsächlich hätte ich aber (fälschlicherweise) gesagt: "Iteration ist, wenn sich die Funktion selber wieder aufruft". Und meine Frage wäre mir ebenso falsch über die Lippen gekommen "Habe ich Iteration gesagt?". Dann wäre die Antwort der Studierenden mit "Ja" ebenso korrekt gewesen. Sprich, meine Nachfrage "Habe ich Rekursion gesagt?" war vollkommen unsinnig und überflüssig. Zumindest aus einer logischen Betrachtungsweise. Wenn mein Hirn mir einen Streich spielt und mir meine gedachten Worte unbemerkt mit der Lautbildung eines anderen Wortes über die Lippen kommen, dann bin ich chancenlos. Oder?

In der Tat bin ich das, wenn mein Gehör die Rede anderer ebenso konsistent falsch hört. Die eigene Rede ist davon ausgenommen, da das Ohr bezüglich der eigenen Rede extrem voreingenommen ist. Es weiß ja, was es hören soll -- und das verführt zu einer gewissen Nachlässigkeit. Also muss das Sprechen und das Hören zeitlich entzerrt werden. Ich muss aktiv Feedback einholen. Und solange die Anteile zur Sprachbildung und Spracherkennung nicht über den gleichen Fehler gekoppelt sind, dann sind Abweichungen erkennbar, wenn man das richtige Feedback einfordert.

Wie hätte nach meiner Erläuterung der Rekursion die Nachfrage lauten sollen? Richtig: "Wie nennt man den Prozess des Selbstaufrufs einer Funktion." Die Studis hätten "Rekursion" gesagt und ich hätte eine Chance zur Fehlererkennung gehabt, da mein Sprechen das Wort nicht wieder falsch einbringen konnte.

Die Moral von der Geschicht? Stellen Sie niemals Ja/Nein-Fragen, wenn Sie Ihren Geisteszustand überprüfen wollen. Oder, um den Bezug zum Software Engineering herzustellen: Stellen Sie einem Kunden, wenn Sie z.B. Anforderungen erheben wollen, möglichst keine Ja/Nein-Fragen. Ja/Nein-Fragen erhöhen das Risiko, dass Sie eigene Inkonsistenzen oder ein irrtümliches Verständnis nicht aufdecken.

Tipps zur Teamarbeit

2008-05-27T14:42:00.002+02:00

Ein (Projekt-)Team ist ein Gruppe von Menschen, an die eine Herausforderung oder eine Aufgabe herangetragen wird und von der man die zielgerichtete Bewältigung der Herausforderung erwartet. Oft geschieht das unter Randbedingung wie begrenzten Geldmitteln und Zeitbeschränkungen. Die Teammitglieder sind außerdem gegenseitig voneinander abhängig, um die Herausforderung bewältigen zu können.

Arbeitsteilung und Spezialisierung sind die Wunderwaffen der Teamarbeit. Ein gutes Team bewältigt eine Herausforderung schneller als ein schlechtes Team. Ein gutes Team teilt die Arbeit besser auf und bildet bessere Experten aus als ein schlechtes Team. Ein gutes Team schafft schneller oder mehr. Nachfolgend ein paar Tipps, die Ihnen helfen sollen, gute und effektive Teamarbeit zu leisten.

Definieren Sie eine Teamleitung. Machen Sie eine Person zu Ihrer Teamleitung und übertragen Sie ihr die Verantwortung zur Koordination des Teams. Im Zweifel hat die Teamleitung das Recht Entscheidungen zu treffen, damit eine Handlungsunfähigkeit mangels Entscheidung aufgelöst werden kann. Die Teamleitung trägt die Verantwortung für das Team und damit auch für das Ergebnis.

Nutzen Sie Ihre Stärken -- oder machen Sie sich stark. Teilen Sie sich die Arbeit gemäß den Spezialisierungen im Team auf und/oder nutzen Sie die Arbeitsteilung, um einzelne Personen zu Experten werden zu lassen. Klären Sie, wer welche Kompetenzen und Interessen mitbringt. Nutzen Sie die Stärken und Talente eines jeden Teammitglieds. Oder bauen Sie Stärken auf.

Keine Aufgabe, die nicht zielführend ist. Fragen Sie sich bei jeder Aufgabe, warum diese Aufgabe sein muss. Eine Aufgabe ist dann überflüssig, wenn auch ohne sie ein Erfolg denkbar ist.

Keine Aufgabe ohne ein klar definiertes Ergebnis. Das Ergebnis ist dann klar definiert, wenn entscheidbar ist, wann die Aufgabe beendet ist. Beispiel: "Ich schau mir mal JavaScript an" ist kein definiertes Ergebnis, "Ich stelle eine Übersicht der Kontrollstrukturen von JavaScript zusammen" hingegen schon.

Keine Aufgabe ohne Klarstellung, für wen das Ergebnis ist. Betrachten Sie Ihre Aufgabe und das Ergebnis als Dienstleistung, als Service für den Empfänger des Ergebnisses. Betrachten Sie den Empfänger als Kunden – und machen Sie ihn glücklich! Denken Sie daran, dass Ihr Kunde von dem Ergebnis profitieren und nicht mehr Zeit als nötig zum Verarbeiten des Ergebnisses investieren möchte. Dennoch sind Quellen, Begründungen etc. anzugeben, denn die Plausibilität ihrer Ergebnisse muss im Zweifelsfall nachvollziehbar sein.

Keine Aufgabe, die länger als zwei Wochen benötigt. Die Zeitspanne von maximal zwei Wochen ist für viele Menschen ein guter Maßstab. "Kleine" Aufgaben sind psychologisch wichtig. Es zwingt außerdem dazu, eine Herausforderung in überschaubare Aufgabe runterzubrechen und erlaubt der Teamleitung ein besseres Nachhalten über den Stand der Dinge.

Keine Aufgabe ohne einen(!) Aufgaben-Verantwortlichen. Wer treibt eine Aufgabe voran, wer kümmert sich darum, dass sie in Angriff genommen wird, wer hält den Arbeitsforschritt nach, wer meldet rechtzeitig Probleme, wer erklärt eine Aufgabe für erledigt? Der Verantwortliche bzw. die Verantwortliche erntet Ruhm wie auch Tadel. Bei kleinen Aufgaben fallen die Rollen zusammen: dann ist eine Person sowohl Aufgaben-Verantwortliche als auch Ausführende. Bei größeren Aufgaben mag man sich die Arbeit teilen, die Verantwortung jedoch nicht. Denn: Verantwortung ist nicht teilbar!

Lernen Sie, auf das Ende einer Aufgabe hinzuarbeiten -- alles andere ist uninteressant. Nehmen wir an, Sie haben die Aufgabe, die Kontrollstrukturen von JavaScript in einer Übersicht zusammenzustellen. Diese Aufgabe ist schnell erledigt, Sie bedarf vielleicht gerade einer halben Stunde, selbst wenn Sie als Informatik-Student noch nie mit JavaScript Kontakt hatten. Natürlich ist es verführerisch, im Web Links zu JavaScript zu verfolgen und vieles Interessantes über die Sprache in Erfahrung zu bringen; ergebnisorientiert ist das nicht.

Definieren Sie Zeiten zur thematischen Orientierung und zum zielorientierten Kompetenzaufbau. Wir sind Menschen, wir können nicht andauernd in Ergebnissen arbeiten und denken. Wir benötigen Zeiten, um uns zu orientieren oder um Kompetenzen aufzubauen, ohne uns dem Druck und dem Stress von Zielen und Ergebnissen unterwerfen zu müssen. Diese Zeiten sind notwendig um (a) überhaupt Ergebnisse und Ziele definieren zu können (Orientierung) und um (b) in die Lage versetzt zu werden, sich Ergebnisse erarbeiten zu können (Kompetenzaufbau). Aber begrenzen Sie diese Zeiten und vereinbaren Sie sich auf ein Thema. Und: Das Thema muss zielführend sein. Beachten Sie, dass sich Kompetenzen in der Regel anhand konkreter Aufgaben aufbauen lassen. Themenarbeit endet mit einem kurzen Tätigkeits- und Erkenntnisbericht an das Team, schließlich ist auch der Lern- oder Orientierungsprozess für das Team von Interesse.

Keine Person im Team ohne aktuelle Aufgabe oder Themenzeit. Sobald eine Person gar nichts tut und etwa einer anderen Person bei der Arbeit zuschaut (gerne maskiert unter "Wir arbeiten zusammen."), läuft irgendetwas schief mit der Teamarbeit. Es kann an mangelnder Koordination bzw. Kommunikation des Teams liegen. Möglicherweise sind aber auch einfach zu viele Personen in einem Team, mehr, als die Aufgabe hergibt.

Arbeiten Sie allein. Sobald mehr als eine Person das Gleiche tut, findet keine Arbeitsteilung mehr statt. Teamarbeit schließt gemeinsames Arbeiten zur gleichen Zeit in einer gemeinsamen Umgebung nicht aus, aber sie verfehlt ihr Ziel, wenn zwei oder mehr Personen grundlos das Gleiche tun. (Auch hier ist die Maskierung "Wir arbeiten zusammen." nicht selten.) Es ist eine der größten Herausforderungen, die Teamarbeit mit sich bringt: alleine arbeiten zu können. Es sind typische Verhaltensmuster von Unsicherheit und Flucht vor der Herausforderung, die Menschen dazu bewegen, mit jemand anderem an der gleichen Aufgabe zusammen arbeiten zu wollen. Auch wenn es paradox zu sein scheint: Teamfähigkeit heißt, weite Strecken über autonom arbeiten zu können. Anders ist Teamarbeit z.B. über das Web in Form von remote collaboration gar nicht möglich.

Definieren Sie regelmäßige, kurze Treffen zur Koordination. Die Arbeiten müssen regelmäßig unter allen Teammitgliedern abgestimmt werden, wobei Anwesenheit (physisch oder virtuell) mehr als sinnvoll ist. Solche Treffen sind kurz zu halten, da diese Zeiten keine Produktivzeiten sind.

Schaffen Sie Möglichkeiten zur Kommunikation. Menschen in einem Team müssen kommunizieren, um eine Identität als Gruppe entwickeln zu können -- und das gilt es gezielt zu kultivieren. Zum Beispiel durch Kommunikationsecken (die berühmte Ecke oder Küche mit der Kaffeemaschine), gemeinsame Arbeitsräume, gemeinsame Mittagessen, Mailing-Listen, Diskussionsforen, Chat-Rooms etc.

Schaffen Sie sich Zeitblöcke zur ungestörten, konzentrierten Arbeit. Ob Sie an einer Aufgabe arbeiten oder mit einem Themenblock beschäftigt sind, Sie brauchen Zeitblöcke von 1 1/2 bis 4 Stunden, um produktive Arbeit leisten zu können. In dieser Zeit sollten sie ungestört sein und auch für Ihre Teammitglieder nicht zur Verfügung stehen.

Zusammenfassung

Teamarbeit ist Arbeitsteilung -- was wörtlich zu nehmen ist: Sie teilen sich die Arbeit. In aller Regel wird mit der Arbeitsteilung eine Spezialisierung einhergehen. Sie arbeiten meist ergebnisorientiert, gelegentlich themenbezogen. Eine Aufgabe ist zeitlich klar begrenzt und hat ein definiertes Ergebnis. Es gibt einen Aufgaben-Verantwortlichen und eine Person bzw. Personengruppe, für die das Resultat der Aufgabe von Nutzen ist. Die Aufbereitung des Resultats sollte an der Zielgruppe ausgerichtet sein. Themenarbeit ist ebenfalls zeitlich klar begrenzt, zielorientiert und endet mit einem Bericht ans Team.

Übrigens sollte ein Team nicht aus zu vielen Personen bestehen. Jenseits von elf, zwölf Personen bilden sich automatisch Untergruppen heraus, die ein Team in wenig gut steuerbare Einheiten zerfallen lassen.

Informatik als angewandte Philosophie

2008-05-21T13:07:00.001+02:00

Was war zuerst: Die Henne oder das Ei? Oder setzen wir noch früher an: Was bitte ist ein Ei, was genau ein Huhn? Informatiker setzen sich auf ihre eigene Art und Weise mit solchen Fragen auseinander -- eigentlich sogar tagtäglich. Zwar sprechen sie selten von Hühnern oder Eiern, aber sie haben Antworten zu bieten.

Wollen Sie auch erfahren, was Informatiker so gedankenverloren in den Kaffee schauen lässt und warum Milchtüten eine echte Herausforderung sind?

Dann möchte ich Sie herzlich einladen zu meinem Vortrag "Informatik als Angewandte Philosophie: Gedanken über Bits und Bytes" am Dienstag, 3. Juni 2008, um 17:30 Uhr bis 19 Uhr. Der Vortrag findet statt im Rahmen der Ringvorlesung "Mensch-Umwelt-Zukunft" an der Hochschule Heilbronn (Max-Planck-Str. 39) im Raum E010.

Ich freue mich auf Ihren Besuch. Und wenn Sie Wünsche, Anregungen, Gedanken haben, zu denen Sie gerne etwas hören möchten, dann lassen Sie es mich wissen.

Forth gedacht: JavaScript 2

2008-05-12T00:05:00.000+02:00

Forth ist eine der Programmiersprachen aus der Frühzeit der Informatik. Die Sprache entstand Anfang der 70er Jahre und wurde von Charles H. Moore erschaffen -- und sie hat bis heute überlebt. Sie ist stack-basiert, äußerst einfach aufgebaut, sie kann mühelos ohne Betriebssystem auskommen und ist beliebig erweiterbar. Die Programme sind schnell und äußerst kompakt, weshalb Forth gerade im Bereich der eingebetteten Systeme noch immer gerne genutzt wird. Und man kann mit Forth Programme interaktiv entwickeln; ein Vorteil, den man von interaktiven, dynamisch-typisierten Sprachen kennt. Was das spannende ist: Forth ist ein entscheidender Baustein im neuesten JavaScript 2 (ECMAScript 4) für den Mozilla-Browser Firefox 4.0.

In der zukünftigen Generation des Firefox-Browsers 4.0 (ich spreche nicht von Firefox 3.0, der bald fertig gestellt sein wird) wollen die Mozilla-Entwickler das dann aktuelle JavaScript 2.0 auf einer Virtuellen Maschine (VM) mit JIT-Kompilierung (just in time compilation) ausführen lassen. Im November 2006 erhielt die Mozilla-Organisation die dafür notwendige Technologie von Adobe Systems. Adobe spendete das etwa 135.000 Zeilen Code umfassende Tamarin an Mozilla. Tamarin ist der Name der VM, die Adobe seit Flash 9 für die Ausführung von ActionScript einsetzt. Derzeit läuft ein Projekt namens ActionMonkey bei Mozilla, das die aktuelle JavaScript-Implementierung für Firefox (SpiderMonkey) und das Tamarin-Projekt zusammenbringt.

Der ByteCode von Tamarin wird in Files mit der Endung .abc abgelegt; sie sind das Analogon zu .class-Files für die Java VM. Der abc-ByteCode wird in Forth als Zwischensprache (Intermediate Language, IL) übersetzt. Für Forth gibt es dann einen C-Interpreter. Wer hier generell einen Einstieg finden möchte, dem sei der Blog "Hacking with Caffein" von Mason Chang empfohlen, insbesondere der Beitrag "Getting started with Tamarin and Forth" (27. März 2008). Man darf gespannt sein, wie sich das ActionMonkey-Projekt machen wird und ob sich Forth als IL in der Virtuellen Maschine halten wird!

Wer sich für ein modernes "Forth" interessiert, der sei auf Factor verwiesen. Siehe dazu auch "Factor: In der Kürze liegt die Würze".

Was ist ein System?

2008-04-29T23:31:00.003+02:00

In der Informatik bleibt der Begriff des Systems seltsam unbesetzt. Begriffsprägungen aus der Elektrotechnik oder der Kybernetik lassen sich nicht so recht übertragen. Umso überraschender ist es, dass der Systembegriff des Soziologen Niklas Luhmann als Anregungsquelle taugt und sich überraschend gut mit Konzepten aus der Informatik füllen lässt. Hier ein Versuch interdisziplinärer Annäherung.

Niklas Luhmann war ein Sozialwissenschaftler, er hatte 30 Jahre die Professur für Soziologie an der Universität Bielefeld inne und starb 1998 im Alter von 70 Jahren. Er gilt als einer der Begründer der soziologischen Systemtheorie. Sein Lebenswerk galt der Entwicklung einer "Theorie der Gesellschaft", die er über mehrere Veröffentlichungen hinweg entwarf. Sein Werk ist immens und hat einen bleibenden Einfluss zum Verständnis gesellschaftlicher Systeme hinterlassen.

Luhmann interessierten soziale, psychische und biologische Systeme -- Systeme, die der Inbegriff des Lebendigen sind. Er nennt sie autopoietische, sich selbst erschaffende Systeme. Technische Systeme sind keine Systeme, so Luhmann. Eine Abgrenzung, die ich problematisch finde. Ich habe den Eindruck, dass sich Systeme, wie sie die Informatik erschafft, deutlich näher an der Luhmann'schen Systemdefinition orientieren, als man es auf den ersten Blick glauben mag,

Nach Luhmann definieren sich Systeme nicht aus Elementen und ihren Beziehungen. Das ist ein typisch technisches Systemverständnis, wie es besonders bei Ingenieuren sehr verbreitet ist. Systeme bestehen nicht aus Dingen oder Elementen, Systeme bestehen aus Operationen. Luhmann sagt: "Nur ein System kann operieren, und nur Operationen können ein System produzieren." (Zitat nach Berghaus 2004, S. 39). Durch das Operieren entsteht eine Differenz von System und Umwelt -- wir werden noch besprechen, was das meint. Ein System existiert nur, wenn es operiert. Einer Operation müssen weitere Operationen folgen bzw. folgen können. Das ist die Forderung nach der so genannten Anschlussfähigkeit eines Systems. Ein System muss sich also als operativ geschlossen darstellen.

Durch sein Operieren bildet das System eine Differenz aus, es erschafft sich ein Inneres in Abgrenzung zu einem Äußeren. Dieses Äußere nennen wir die Umwelt des Systems. Entscheidend ist, dass es das System selbst ist, das diese Unterscheidung durch sein Operieren macht. Gleichzeitig bildet diese selbst erzeugte Grenzziehung auch die Grundlage des Systems, seine Umwelt beobachten zu können. Jede Beobachtung ist Unterscheidung, und jede Unterscheidung ist Beobachtung. Wer beobachtet, differenziert, grenzt ab, unterscheidet.

Zu guter Letzt fordert Luhmann von Systemen die Fähigkeit zur Selbstreproduktion. Ein System muss selbst wieder etwas Operierendes hervorbringen können. Das ist die Autopoiesis eines Systems. Die Sprachwurzeln des Begriffs kommen aus dem Altgriechischen und sind leicht zu merken: "auto" wie in auto-matisch oder Auto-mobil heißt "selbst"; die "Poesie" ist im griechischem Wortsinne eine "Erschaffung". Autopoiesis ist also die "Selbsterschaffung".

Ich möchte dieses Systemverständnis in Bezug auf soziale, psychische und biologische Systeme hier nicht ausbreiten, das würde zu weit führen. Wer sich genauer dafür interessiert, dem sei das Buch von Margot Berghaus empfohlen: "Luhmann leicht gemacht", Böhlau-Verlag, 2. Auflage, 2004. Von Luhmann selber ist die "Einführung in die Systemtheorie", herausgegeben von Dirk Baecker, Carl-Auer-Verlag, 4. Auflage, 2008, für einen Laien einigermaßen verständlich.

Fassen wir zusammen, was Luhmann als System definiert:

Ein System entsteht durch Operationen.

Einer Operation müssen Operationen folgen (können); sonst hört das System auf zu operieren, sprich zu existieren.

Durch die Operation wird eine Differenz, eine Unterscheidung erzeugt, durch die sich das System von einer Umwelt abgrenzt.

Die Differenzbildung begründet und beschränkt die Fähigkeit, die Umwelt beobachten zu können.

Systeme sind autopoietisch, d.h. sie können sich mit ihren Operationen selbst reproduzieren.

Das alles scheint schwer verständlich und kryptisch. Dennoch ist die Nähe zu Konzepten aus der Informatik auffällig. Starten wir einen Versuch, die Luhmann'sche Begriffswelt mit Informatik-Konzepten aufzuladen.

Jedem Informatiker ist der Begriff der Operation vertraut. Eine Operation ist ein atomarer Verarbeitungsschritt. Ein Beispiel ist die Ausführung eines Maschinenbefehls.

Um ein System durch Operationen entstehen zu lassen, muss eine Folge von Operationen irgendwann zu einer Operation führen, die bewirkt, dass es einen Rücksprung zu einer bereits ausgeführten Operation gibt. Der Fluss der Operationen muss zu einem Zirkelschluss führen, damit das System operativ bleibt. Denn nur durch andauerndes Operieren entsteht ein System. Wir wollen diesen geschlossenen Kreislauf von Operationen einen aktiven Prozess nennen. Den Begriff des Prozesses kennen sie zum Beispiel aus der Welt der Betriebssysteme.

Die Operationen des aktiven Prozesses greifen notwendigerweise auf Speicherinhalte zu -- ansonsten passiert nichts Spannendes. Mit anderen Worten, ein aktiver Prozess ist mit einem endlichen Satz an Zuständen und Zustandswerten assoziiert. Darüber entsteht die Differenz zur Umwelt. Alles, was nicht zu den Operationen und zu dem Zustandsraum eines Prozesses gehört, ist die Außenwelt des Prozess-Systems. Der Zustandsraum ist sozusagen der verinnerlichte Teil einer Rechenwelt in den Grenzen eines abgeschlossenen Flusses von Operationen.

Das schließt nicht aus, dass ein anderer Prozess ebenso dieselben Speicherinhalte bzw. Zustände verinnerlicht. Vielmehr sind diese geteilten Bereiche die einzige Möglichkeit zur Kommunikation von Prozessen untereinander. Die Veränderung des Werts einer gemeinsamen Speicherzelle ist Mitteilung einerseits und Beobachtung andererseits. Prozesse können auf diese Weise Informationen austauschen. Wir nennen solch eine geteilte Domäne eine Schnittstelle oder ein Interface. Ein Interface ist kein System!

Wie Sie sehen, führt der abgeschlossene Fluss von Operationen zu einer Assoziation mit einem Speicherbereich und damit zu einer Abgrenzung vom Rest des Speichers. Teilen sich abgeschlossene Operationsflüsse Speicherbereiche, dann kann diese Gemeinsamkeit zur Kommunikation genutzt werden. Das alles ist in Einklang mit der Systemdefinition nach Luhmann!

Prozesse können derart angelegt werden, dass sie sich selbst zu kopieren vermögen. Ist ihnen über eine Operation die Fähigkeit gegeben, einen separaten Fluss von Operationen auf der Kopie in Gang zu setzen, dann hat sich das Prozess-System reproduziert! Prozesse können, sofern sie eine Operation zur Initiierung eines eigenständigen Operationsflusses haben, als autopietisch bezeichnet werden.

Das wird einem Luhmann und vielen anderen Systemtheoretikern sicher widerstreben. Denn Autopoiesis wird als auszeichnendes Merkmal lebender Systeme verstanden. Es scheint auch intuitiv nicht einleuchtend, ein Informatik-System als lebendig zu bezeichnen. Andererseits muss eine Definition des Lebendigen eine klare Aussage machen, was genau das Lebendige vom Nicht-Lebendigen unterscheidet, und dies in einer Weise tun, die durchaus auch den Raum lässt, von Menschenhand geschaffene Systeme eines Tages als lebendig zu klassifizieren.

Lidl und der Kassen-Bug

2008-04-15T17:50:00.003+02:00

Es gibt Fehler, im Informatiker-Jargon "Bugs", die etwas anrühriges haben. Ich bat den Menschen an der Kasse bei Lidl um einen Moment Geduld und meine Kinder um Ruhe, um nicht den wunderbaren Moment zu verpassen, bei dem es passierte. Der Lidl-Mensch fluchte kurz auf -- und ich war entzückt! "Einen Moment, davon muss ich ein Foto machen!" Und dann machte ich noch eines.

Ich bin heute extra für diesen Fehler zu Lidl gepilgert -- ich wollte es mit eigenen Augen sehen. Gestern hat mir ein Student (vielen Dank Herr Breyer) von diesem Fehler in einer EMail berichtet. Ein richtig schöner Fehler, ein Klassiker geradezu. Ein Fehler, den man selten zu Gesicht bekommt, so einer mit Museumswert. Dafür wäre ich sogar noch weiter gereist als bis zum nächsten Lidl.

Der Fehler tritt auf, wenn Sie an der Kasse Waren im Wert von 0 Euro (Null Euro) bezahlen. Dann streikt das System. Die kurze Einkaufsliste dazu: Geben Sie zwei Pfandflaschen zurück und Lidl steht mit 50 Cent bei Ihnen in der Kreide. Zu dem Pfandzettel, den Ihnen der Automat ausspuckt, besorgen Sie sich eine Wasserflasche (19 Cent plus 25 Cent Pfand macht 44 Cent) und begehen die Umweltsünde und greifen nach einer Einkaufstüte für 6 Cent. Ab zur Kasse damit. Minus 50 Cent plus 50 Cent machen 0 Cent bzw. 0 Euro. Rien ne va plus!

Herrlich, die Kasse streikt und ruft nach "Autorisierung". Wie Sie auf dem rechten Bild sehen, hat die Schlange hinter mir gleich das Weite gesucht. "Das kommt so einmal im halben Jahr vor", erfuhr ich vom Kassierer.

Ich habe im Netz einen Blogeintrag gefunden, der belegt, dass der Fehler mindestens seit Mitte November 2007 bekannt ist (Alphawinkel.de: "Der tägliche Blödsinn: Lidl und die Kasse", 13. Nov. 2007). Vermutlich tritt der Fehler zu selten auf, als dass Lidl ein schnelles Bug-Fixing für nötig erachtet.

Das Faszinierende jedoch ist, dass dieser Fehler überhaupt auftritt. Warum hat man bei der Programmierung des Kassensystems diesen einfachen Testfall übersehen? Haben Sie oben beim Lesen kurz gestockt, als ich schrieb

Der Fehler tritt auf, wenn Sie an der Kasse Waren im Wert von 0 Euro (Null Euro) bezahlen.

Haben Sie für einen Moment gedacht "Wie soll das denn gehen"? Dann sind wir der Ursache schon auf der Spur. Wir selbst mit unseren eingefahrenen Denkmustern sind das Problem.

Die Kunst des Testens ist, Grenzfälle möglich zu machen, nicht sie für unmöglich zu halten.

[Nachtrag: Lesen Sie auch auf den Denkspuren: "Ist der Kassen-Bug von Lidl ein Bug?"]

Kleinprojekte und ihre Kosten

2008-04-15T11:34:00.003+02:00

Was in Büchern zum Software-Projektmanagement gerne übergangen wird, sind die Kleinprojekte. Vielleicht, weil das Management von Kleinprojekten als trivial angesehen wird. Dabei sind es die Kleinprojekte, von denen es so zahllos viele gibt.

Als Kleinprojekt definiere ich ein Vorhaben, das beim Auftragnehmer von ein bis fünf Personen abgewickelt wird, das wenige Wochen bis einige Monate dauert und in der Regel den Auftraggeber ein paar Tausend bis wenige Zehntausend Euro kostet.

Das Tagesgeschäft von vielen Kleinunternehmen ist geprägt von Kleinprojekten. Freiberufler müssen sich immer wieder auf Kleinprojekte einlassen. Der Schritt in die Selbstständigkeit bedeutet für viele die Abwicklung unzähliger Kleinprojekte -- ein Leben von der Hand in den Mund mit geringen Gewinnspannen. Und viele Informatik-Studierende versuchen, sich mit Kleinprojekten (oder auch Kleinstprojekten) ein Zubrot zu verdienen. Grund genug, sich mit dieser Sorte von Projekten einmal genauer zu befassen.

Diese Woche habe ich in der Projektmanagement-Vorlesung eine Fallstudie besprochen. Ein reales, kleines Softwareprojekt, an dem ich auch beteiligt war bzw. bin -- es steht kurz vor dem Abschluss. Ich habe dazu die Projekthistorie aufgerollt und mich dabei ausschließlich auf die spannende Phase vor der eigentlichen Software-Entwicklung konzentriert, die ich hier Vor-Entwicklungsphase nenne. Es geht also um die Zeit, in der mit dem Kunden diskutiert, überlegt, gebrütet und gelöst wird -- bis man verstanden hat, worum es eigentlich geht und was entwickelt werden soll. Mögliche Resultate sind Anforderungsdokumente, Konzeptpapiere, Prototypen und ein Vertrag bzw. ein Auftrag zur eigentlichen Entwicklung, sprich zur Realisierung der ausgereiften Idee. Diese Phase ist mit Aufwendungen und mit Kosten verbunden. Wissen Sie, wie hoch die Kosten da liegen? Haben Sie eine ungefähre Vorstellung wie der Kostenverlauf über die Zeit aussieht und mit welchem Kostenverhältnis der Kunde rechnen darf?

Zur Fallstudie. Damit Sie eine grobe Vorstellung haben, es geht inhaltlich um eine webbasierte Anwendung mit einer relationalen Datenbank dahinter. Technisch unspektakulär, etwas, was in aller Welt immer wieder entwickelt wird. Am Ende wird sich herausstellen, dass die Softwarekonzeption samt prototypischem Datenbankschema durch ein sechsseitiges Dokument ausreichend dokumentiert ist. Es handelt sich also tatsächlich um ein "richtiges" Kleinprojekt. Dennoch ist erstaunlich, welcher Aufwände es bedarf, um von dem Kundenanliegen zu dieser klaren Dokumentation zu gelangen.

Ich habe Folgendes zur frühen Projektphase aufgelistet: Wann gab es Treffen, was war der Anlass, wer war vom Kunden, wer vom Auftragnehmer dabei? Und: Wann wurde ein Resultat (in der Regel ein Dokument oder ein Prototyp) rausgegeben? Wer war an der Erstellung wie lange beteiligt -- und wen hat es wie viel Zeit zum "konsumieren" (lesen, verstehen, ausprobieren) gekostet? Ich habe dann noch auf der Kunden- wie auf der Auftragnehmerseite zwei Rollen unterschieden: einmal die Personengruppe, deren Zeit mehr kostet (Leitungsfunktionen, Manager, Koordinatoren) und die Gruppe, deren Zeit weniger kostet (Entwickler, Tester, technische Schreiber). Mit der Zuordnung möchte ich niemanden diskriminieren, sie spiegelt nur grob die Kostenverteilung wieder, wie wir sie in der Realität antreffen. So ungenau das ist, es hilft uns, einen Eindruck zu gewinnen.

Übrigens habe ich mit Tiefstpreisen gerechnet: Die "Billigen" kosten 50 Euro die Stunde, die "Teuren" doppelt so viel. Das dürfen Sie gerne im Kopf nach oben korrigieren. (Bevor Sie unglückliche Mutmaßungen anstellen: Ich habe in dem Projekt unentgeltlich gearbeitet, meine Arbeitskraft in der Modellrechnung jedoch monetär berücksichtigt.) Zeitaufwände habe ich aus dem Gedächtnis rekonstruiert, da ich keine zuverlässigen Aufzeichnungen dazu habe, und bin mit meinen Schätzungen sehr sportlich vorgegangen. Sportlich heißt auch hier, dass ich mit Minimalaufwänden gearbeitet habe, die real in den meisten Fällen höher liegen dürften.

Die Ergebnisse: In der Historie der frühen Projektphase habe ich in einem Zeitraum von 5 Monaten (Juli bis Dezember 2007) 13 Termine bzw. Ereignisse erfasst. Davon sind 6 Termine Besprechungen (4 Vis-a-Vis, 2 Telefonkonferenzen) und 7 Termine markieren den Versand eines entscheidenden Dokuments, entweder als Neuerstellung oder als Update. Die mit diesen Terminen bzw. Ereignissen assoziierten Kosten belaufen sich für den Kunden auf etwa 1600 Euro, für den Auftragnehmer auf 4300 Euro.

Ich finde das sehr beachtlich. Der Kunde muss als Auftraggeber etwa 6000 Euro ausgeben, einzig um sein Anliegen in dieser Projektphase zu kommunizieren, zu reflektieren, zu diskutieren, zu revidieren, zu konkretisieren und zu präzisieren. In der Zeit hat der Auftragnehmer noch keinen einzigen Euro verdient! Er hat diesen Prozess lediglich gemeinsam und in Kooperation mit seinem Kunden durchlaufen und zu einem Resultat getrieben, der dann erst den Startpunkt für die konkreten Entwicklungsaktivitäten eines Softwareprodukts bildet.

Ich halte übrigens die Kostenanteile meiner Erfahrung nach für relativ typisch, kann dies allerdings nicht durch Fakten aus anderen Projekten belegen. Das Verhältnis liegt bei etwa 2:5. Von 7 Anteilen, die der Kunde für diese Projektphase ausgeben muss (6000 Euro durch 7 macht ca. 850 Euro), muss der Kunde seine eigenen Kosten etwa mit 2 Anteilen (die 1600 Euro, gleich etwa 2 Mal 850 Euro) veranschlagen, die für den Auftragnehmer mit 5 Anteilen (4300 Euro).

Interessant ist zu beobachten, wie die Kostenentwicklung über die Zeit aussieht. Die Analyse der 13 Termine bzw. Ereignisse zeigt, dass für den Kunden die Aufwände am Anfang liegen. In den ersten Treffen werden viele Mitarbeiter vom Kunden involviert (das kostet viel), was am hohen Diskussions- und Klärungsbedarf liegt. Der Auftragnehmer hingegen hat die ganze Zeit über relativ gleichbleibende Aufwände: er muss am Ball bleiben und seine Arbeit im Hintergrund machen. Die Erstellung etwa eines Prototypen ist nicht unaufwendig. Für die weitere Abstimmung und Klärung beschäftigt der Kunde nun nur noch eine Person, die die Verantwortung für das Projekt trägt.

Ich habe diesen Kostenverlauf etwas überzeichnet in dem Bild oben in rot eingetragen. Die Verteilung der Kosten beim Kunden verläuft über die Zeit wie ein sich zuspitzendes Dreieck; die Aufwände werden zunehmend geringer. Beim Auftragnehmer zeigt das langgezogene Rechteck die Konstanz der Kosten an. Bringt man beide Kostenanteile zusammen, sieht man den Verlauf der Gesamtkosten.

In dem Bild habe ich darüber hinaus in grau den Kostenverlauf für das Projekt eingetragen, wie er sich qualitativ für die sich anschließende Entwicklung des Softwareprodukts und seiner Einführung beim Kunden ergeben hat. Während der Entwicklung entstehen für den Kunden kaum Kosten -- er wartet auf das Produkt. Mit der Fertigstellung nimmt der Aufwand für den Kunden wieder zu: Die Abnahme des Produkts muss durchgeführt werden und die mit der Einführung des Produkts verbundenen Schulungen boosten die Kosten noch einmal.

Der Auftragnehmer hat während der Entwicklungszeit relativ konstante Kosten. Ein, zwei oder drei Entwickler werden in dieser Zeit in Kleinprojekten oft beschäftigt. Ist das Produkt fertig, halten die Aufwände noch kurz an, um eventuelle Korrekturen oder kleinere Änderungen durchzuführen, sie nehmen dann aber ab.

Es ist nicht aus zeichnerischen Gründen so, dass die Vor-Entwicklungsphase so lange dauert und die eigentliche Entwicklungszeit so kurz ist. Ist das Anliegen des Kunden einmal geklärt und erfasst, kann die Entwicklung recht zügig abgewickelt werden. Aber es kann dauern, bis das Anliegen hinreichend gut verstanden und aufgearbeitet ist; in diesem Fall hat sich das auf ganze 5 Monate verteilt.

Wo kann der Auftragnehmer eigentlich seine Gewinne einrechnen? Kaum in der Vor-Entwicklungsphase, denn hier geht es darum, Unsicherheiten abzuarbeiten und Klärung herzustellen. Es ist schwer kalkulierbar, wie viele Termine dazu ausreichen werden, wenn man das Kundenanliegen noch nicht einmal verstanden hat. Das ist ja genau das Merkmal dieser frühen Phase: vieles ist unklar, unscharf, uneindeutig, unausgesprochen. Hier geht es lediglich darum, kostendeckend zu arbeiten. Ein Grund, warum diese Phase gerne aufwandsorientiert abgerechnet wird -- nur wollen das die Auftraggeber für Kleinprojekte meist nicht tun, da ihnen ein Verständnis für die Problematik dieser Vor-Entwicklungsphase fehlt. Denn in ihren Augen geht es ja nur um diese kleine Sache, dieses kleine Projekt, das ja eigentlich klar ist. Außerdem neigt ein Auftraggeber zur Blindheit gegenüber seinen eigenen, internen Kosten in dieser Phase (das Dreieck), da diese für Kleinprojekte selten klar abgerechnet werden. Veranschaulicht man sich noch einmal den Kostenverlauf beim Kunden, scheint es durchaus verständlich, dass Kunden nach dem Initialaufwand wenig interne Kosten "spüren". Das Gefühl des internen Kostenverlaufs wird auf den Auftragnehmer projiziert.

Erst nach der Vor-Entwicklungsphase kann gut kalkuliert werden. Ein gemeinsames Verständnis des Kundenanliegens liegt vor, die Angelegenheit ist planbar geworden. Ergo wird der Auftragnehmer hier beginnen, seine Gewinnmargen einzurechnen. Ich habe das durch die schraffierten Bereiche markiert. Allerdings ist aufgrund der Kürze der Entwicklungszeit die Marge nicht sehr "lange" ausschöpfbar -- auch ein Merkmal von Kleinprojekten. Kommen nur ein, zwei, drei ungeplante Entwicklertage hinzu, weil etwa der Kunde auf einer Nachbesserung besteht oder, viel simpler, ein Entwickler krank ist, dann steht das Kleinprojekt für den Auftragnehmer bereits kurz vor der Verlustzone. Wesentlich ertragreicher und noch besser kalkulierbar sind Schulungsmaßnahmen beim Kunden. Nur bedarf nicht jedes Softwareprodukt einer Schulung.

Wie Sie vielleicht anhand dieser Ausführungen erahnen, sind Kleinprojekte ein taffes Unterfangen, die den Auftragnehmern nicht viel Gewinne schenken. Reich wird damit keiner. Es macht auch klar, warum viele Unternehmungen scheitern, wenn sie nicht den Sprung in die Klasse der mittelgroßen Projekte bis Großprojekte schaffen, dort sind die Gewinnmargen größer.

Wenn Sie Ihre Erfahrungen mit Kleinprojekten teilen möchten, ich freue mich auf Ihre Kommentare. Können Sie meine Fallstudie bestätigen? Oder haben Sie andere Erfahrungen mit Kleinprojekten gemacht?

Sichtweisen in 3D: Balance halten

2008-03-31T12:45:00.005+02:00

Wie sehen wir dreidimensional? Die meisten Menschen denken dabei ans Stereosehen: Unsere beiden Augen liefern zwei Bilder, die ein und dieselbe Szenerie aus geringfügig abweichenden Blickwinkeln betrachten. Diese Winkelabweichung genügt, um Tiefeninformationen aus den Bilddaten abzuleiten.

Das ist so richtig, wie es auch nur die halbe Wahrheit ist. Das Stereosehen erlaubt es uns, im direkten Nahbereich von wenigen Metern Distanzen im Raum einschätzen zu können. Aber Sie können auch mit nur einem Auge dreidimensional sehen! Glauben Sie nicht? Dann schauen Sie sich mal das Video von Johnny Chung Lee an, einem genialen Kopf, der seinesgleichen sucht. Das Video, das seit Ende 2007 im WWW kursiert, zeigt Ihnen eine aufregend andere Art des Einsatzes der WiiRemote -- und ist gleichzeitig ein brillantes Lehrstück über unsere Grundlagen des 3D-Sehens!

Unser Gehirn verrechnet also auch diese Winkelverschiebungen um in Tiefeninformation. Dazu muss sich etwas bewegen: entweder man sich selbst oder die Szenerie. Lee dreht hier den Spieß um: Er lässt den Computer umrechnen, wie sich die Szenerie verändert, wenn wir uns vor dieser Szenerie bewegen -- und erzeugt damit die Illusion der Tiefe eines Raumes. So rechnen beide: Gehirn und Computer. Die Täuschung ist perfekt!

Hat man einmal gesehen, auf welche einfache und originelle Art und Weise man mit diesen neuen Schnittstellen umgehen kann, kommen einem auch gleich ganz andere Ideen. Vor wenigen Tagen zeigte mir ein Student sein N95-Handy von Nokia mit einer kleinen Applikation, die die Bewegungssensoren im Handy nutzt: eine "Wasserwaage" (siehe Bild oben). Der rote Punkt im Display kommt in der Mitte zur Ruhe, wenn sich das Display des Handys in der Waage befindet. Ansonsten wandert der Punkt nach rechts bzw. links. Die Applikation ist in Python geschrieben und läuft auf dem Python-Port für S60-Handys. Wir haben übrigens nicht mehr ausfindig machen können, wer der Autor des Programms ist und ob es eine Webseite dazu gibt. Hinweise sind willkommen.

Wenn Sie ein Handy haben, das Sensoren für zwei Achsen hat (X- und Y-Achse), dann können Sie die Lee-Idee entweder direkt auf dem Handy umsetzen oder Sie lassen sich etwas anderes einfallen. Mein Vorschlag wäre folgender: Stellen Sie sich vor, auf Ihrem Handydisplay stünde senkrecht ein Stab mit einer roten Kugel als Kopf, eine Stecknadel. Sie schauen in der Draufsicht auf das Display, sprich, Sie sehen nur die rote Kugel von oben als Kreis. Nun kippen Sie das Handy hin und her. Sie sehen nun die Stecknadel von der Seite, je nach Neigungsgrad. Es wird sich ein starker, visueller 3D-Eindruck einstellen, ähnlich wie bei dem Video, das Sie oben gesehen haben. Wenn Sie wollen, können Sie die "Stecknadel" bei Neigung allmählich kipppen lassen, so dass die Herausforderung darin besteht, die Nadel wieder in Balance zu bekommen. Ein nettes Spielchen! Wenn Sie noch einen Sensor für die dritte Achse haben (Z-Achse), können Sie die Nadel auch "hochwerfen" und auf einer virtuellen Ebene im Raum landen lassen. Sie erahnen es. Man kann sich ganz neue und ganz andere Spielideen und Anwendungsgebiete einfallen lassen.

Mag sich jemand an eine Umsetzung machen? Oder haben Sie noch andere nette, mehr oder minder sinnvolle (Spiel-)Ideen?

Der freie Wille

2008-03-04T12:38:00.003+01:00

Bild von hcm80

Wie frei sind wir Menschen eigentlich in unseren Entscheidungen? Kann eine Maschine, ein Computerprogramm einen "freien Willen" haben? Was überhaupt ist die willentliche Freiheit der Entscheidung?

Nähern wir uns den Fragen aus der Sicht der Informationstheorie. Die moderne Informationstheorie begründet sich auf Claude Shannon. Shannon sagt, vereinfacht gesprochen: Je überraschender ein Ereignis ist, desto höher ist sein Informationsgehalt. Ein Beispiel: Jeden Morgen sehen Sie auf dem Weg zur Arbeit einen Mann mit einem roten Schal an der Bushaltestelle stehen. Immer der rote Schal. Schal und Mann scheinen ein untrennbar zu sein. Es überrascht sie wenig, ihn jeden Morgen mit dem roten Schal zu sehen. Sie erwarten es regelrecht. Der rote Schal ist keine Neuigkeit, keine Information mehr für Sie. Er gehört einfach dazu. An einem Morgen, Sie erinnern sich noch genau, es war der 1. Mai, da steht er plötzlich da mit einem grünen Schal. Große Überraschung, hoher Neuigkeitswert. Diese Überraschung verstehen wir im Sinne von Shannon als Information.

Die Überraschung, oder anders herum, Ihre Erwartung hängt zusammen mit der Wahrscheinlichkeit des Ereignisses. Eine hohe Wahrscheinlichkeit drückt Ihren Erwartungswert aus. Tritt das Ereignis im Rahmen Ihrer Erwartungshaltung auf, dann sind sie nicht überrascht. Geringer Informationswert.

Schauen wir uns nun einmal an, was wir aus dieser Sicht als "freien Willen" verstehen könnten:

Nehmen wir Ihre Freundin Alica. Sie kochen für sie und machen ihr drei Teller fertig: einen Teller mit Spaghetti ohne alles, einen Teller Spaghetti mit Tomatensauce und einen Teller Spaghetti mit Tomatensauce und Parmesan. Sie wissen, dass Alica weder ein "trockenes" Essen noch Käse mag. Ihre Erwartung ist, dass Sie den Teller mit der Tomatensauce nehmen wird. Und so ist es dann auch!

Hat sich Alica frei entschieden? Aus Ihrer Sicht hat sich Alica gemäß Ihren Erwartungen verhalten. Das wirkt auf Sie nicht so, als sei Alica frei in Ihrer Entscheidung gewesen. Sie hat sich genommen, was sie mag, und gemieden, was sie nicht mag. Sie hat sich vollkommen inneren Antrieben für Vorlieben und Abneigungen hingegeben. Eigentlich konnte Alica gar nicht anders!

Alica hätte sich frei in der Entscheidung gezeigt, wenn sie z.B. zur Variante mit dem Parmesan-Käse gegriffen hätte. Das hätte Sie sehr überrascht -- und wäre eine echte Neuigkeit gewesen.

Die Freiheit einer Entscheidung begründet sich für einen Außenstehenden also damit, wie sehr sich jemand gegen Erwartungen verhält. Der Erwartungswert drückt Ihre Kenntnis aus über Motive, Vorlieben, Wünsche, Sehnsüchte und bisherige Erfahrungen mit der Person, die Sie gemacht haben.

Und wie kann sich Alica "frei" verhalten? Indem sie Ihre Erwartungshaltung durchbricht. Indem sich Alica gänzlich anders verhält als erwartet. Die Überraschung ist umso größer, je mehr Alicas Verhalten Neuigkeitswert hat.

Da wir Menschen aber nur einen sehr schlechten Zugang zu unsere Innenwelten haben, können wir uns nicht sicher sein, wie wir eine Entscheidung gegen Erwartungen fällen sollen -- außer, man nimmt einen Würfel! Genauer, einen gezinkten Würfel, der seine Seiten genau gegenläufig zu den Erwartungen zufällig oben zum liegen kommen lässt.

Das irritiert, nicht wahr? Aber es ist eine konsequente Sicht der Dinge mit den Augen der Informationstheorie.

Freiheit ist der Moment, an dem wir uns willentlich gegen erwartete Verhaltensmuster entscheiden und einen Würfel zur Hand nehmen, der uns aus den Möglichkeiten der Optionen per Zufall eine raussucht. Sie haben richtig gelesen: Sie müssen würfeln! Freiheit wird dann gelebt, wenn diese zufällige Entscheidung ohne Leid, ohne Reue, ohne Bedauern genauso gelebt werden kann wie jede andere Wahl, die der Würfel getroffen hätte!

Wie bitte, sich dem Zufall unterwerfen ist Freiheit? Das gelegentliche, willentliche "unterwerfen" ist Freiheit, denn sonst verhielten Sie sich nur zufällig. Wobei der Begriff "Unterwerfung" schon falsch ist. Ein freier Mensch unterwirft sich nicht, er lebt jede Option in gleicher Weise. Sonst ist er nicht frei, oder? Das höhrt sich schon sehr nach östlicher Philosophie an!

Nichts gegen östliche Philosophien. Aber wenn Sie mich fragen, ich verzichte auf die Freiheit und esse lieber immer nur Spaghetti mit Tomatensauce!

Und genau da sind wir an dem Punkt angelangt: Ich bin nicht wirklich frei zu essen, was man mir vorsetzt. Ich habe Vorlieben. Ich bin berechenbar. Nun kann man sich fragen, wie weit man das Spiel treiben möchte: Ist Ihr Hobby eine freie Wahl? Ist Ihr Partner bzw. Partnerin frei gewählt? Ist Ihre Ausbildung, Ihr Wohnort, Ihre Automarke, Ihr DVD-Player, ist das alles eine Wahl des freien Willens? Wie oft haben Sie gewürfelt bzw. würfeln lassen?

Wenn man meiner Argumentation folgen mag (mir ist selbst nicht ganz wohl dabei), dann können wir Software-Programmen relativ leicht freien Willen einpflanzen. Wir lassen sie an einigen Stellen einfach gelegentlich würfeln und provozieren unerwartete Verhaltensweisen. Und schon wählt der Computer Spaghetti mit Parmesan -- und hat nicht einmal ein Problem damit!

Ein Zufallssimulator aus Software verhält sich zwar nicht wirklich zufällig. Sein Verhalten ist vorhersehbar, wenn man den Wert zur Initialisierung des Simulators kennt -- auch seed genannt. Man nennt es also nicht umsonst einen Simulator. Insofern ist der "freie Wille" in einer reinen Software-Maschine auch nur eine Simulation. Diese Simulation verhält sich aber freier als wir es sind.

Laut Gerhard Roth, einem anerkannten Hirnforscher, ist unser "freier Wille" vermutlich mehr Illusion als uns lieb ist. So sollten wir froh sein, dass wir wenigstens Computer frei sein lassen können. Vielleicht sind Computer nicht willentlich frei, aber immerhin frei -- wenn wir ihnen die Freiheit gewähren.

Gruseliger Schluss, was?!

Wie lerne ich eine Programmiersprache an einem Tag?

2008-02-25T21:01:00.010+01:00

(Foto von jbvkoos)

Lassen Sie sich mal an einem Tag für acht oder zehn Stunden, oder wenn es Sie so richtig gepackt hat, für 12 Stunden auf eine neue Programmiersprache ein! Sie werden sehen, dass Sie erstaunlich weit kommen. Weiter als Sie es vielleicht für möglich gehalten haben. Das geht, wenn Sie sich der Sache ein wenig mit System nähern. Hier ein paar Tipps und Vorschläge. Ich beziehe mich im Folgenden beispielhaft auf JavaScript.

Bevor es los geht, ein kleiner Hinweis: Sie werden keine Sprache an einem Tag lernen können, wenn Sie nicht bereits mit mindestens einer modernen Programmiersprache gut vertraut sind. Die erste Hürde muss also schon genommen sein. Ab der ersten Hürde wird es immer leichter ;-)

Vorbereitung: Besorgen Sie sich ein Buch zu der Programmiersprache, die Sie interessiert. Am besten in Papierform -- mit Papier lässt sich sehr schnell und zügig arbeiten. Legen Sie sich für Ihre Streifzüge durch das Buch Stift und Textmarker bereit. Beschaffen Sie sich den Standard zu Ihrer neuen Programmiersprache. Meist finden sie ihn frei zugänglich im Web. Ein Standard ist ein technisches Dokument, das die Programmiersprache genau beschreibt und definiert. Manchmal gibt es keinen formalen Standard, sondern ein Buch oder Dokument, das die Sprache verbindlich definiert. Suchen Sie danach. Und zu guter letzt: Installieren Sie sich die neue Sprache auf Ihrem Rechner, damit Sie sofort damit herumspielen können. Ja, spielen -- die Sache soll Spaß machen!

Um all das kümmern Sie sich am besten ein paar Tage bevor Sie sich mit der Sprache dann für einen Tag beschäftigen wollen. Los geht's!

Syntax anschauen: Beginnen Sie mit einen Blick in die Syntax, also den Regeln, wie gültige Programme aussehen dürfen. Die Syntaxregeln werden Sie vermutlich im Standard finden, meist im Anhang. Viele Bücher zu Programmiersprachen verzichten bedauerlicherweise sogar auf eine klare Angabe der Syntaxregeln; jetzt wissen Sie, warum Sie ihn sich beschaffen sollten. Schauen Sie zum Beispiel in den Annex A des Standards zu JavaScript, ECMA-262, 3rd Edition. Auf wenigen Seiten erfahren Sie interessante Dinge über die Sprache, etwa eine Liste reservierter Schlüsselwörter (keywords). Von "break", "case", "catch", ... bis hin zu "var", "void", "while", "with". Ganze 25 Schlüsselwörter gibt es zu erkunden. Damit gibt es ein erstes klares Arbeitsprogramm: Verstehen, wofür jedes dieser Schlüsselwörter da ist. Verbergen sich hier neue, interessante Konzepte?

In der Syntaxbeschreibung werden Sie bei JavaScript zum Beispiel auch entdecken, dass reguläre Ausdrücke zur Sprache gehören. Wenn Ihnen das nichts sagt: unbedingt lernen! Nicht jetzt, an diesem Tag -- sonst kommen wir nicht durch -- aber reguläre Ausdrücke sind ein mächtiges Werkzeug bei der Suche nach Mustern in Zeichenketten. Muss man können! Hat praktisch jede moderne Sprache mindestens als Bibliothek im Gepäck.

Welche Datentypen gibt es? Jetzt kann Ihr Buch zum Einsatz kommen. Blättern Sie durch das Inhaltsverzeichnis, verschaffen Sie sich einen Überblick über die Themen. Beschränken Sie sich rein auf Kapitel zu Ihrer neuen Sprache. Ignorieren Sie Bibliotheken, Erweiterungen oder Spezialanwendungen. Das ist jetzt alles uninteressant. Fangen Sie an mit den Datentypen: Welche Basistypen gibt es, welche "Sammeltypen" gibt es? JavaScript hat lediglich drei primitive Datentypen: Zahlen, Zeichenketten und Booleans. Dazu kommen noch zwei triviale Typen: null und undefined. Daneben gibt es noch den Datentyp des Objekts als Sammeltyp. Und das war es schon -- JavaScript präsentiert sich erstaunlich einfach. Hätten Sie's gedacht? Zwar redet man auch von Arrays, die jedoch ebenfalls Objekte sind; Funktionen, Zeitwerte, reguläre Ausdrücke und Fehler sind lediglich besondere Arten von Objekten.

Ein wichtiger Punkt ist noch: Wie wird mit Typen umgegangen? Handelt es sich bei Ihrer neuen Programmiersprache um dynamische oder statische Typen? Sie wissen vielleicht, das dynamisch typisierte Sprache, wie Python, Ruby oder JavaScript, zunehmend an Boden gewinnen. Die Art mit solchen Sprachen zu arbeiten ist eine gänzlich andere als mit statisch typisierten Sprachen wie Java oder C#. Noch wichtiger jedoch ist: Wie werden Datenwerte manipuliert? Wie heißt es so schön im Informatik-Slang: by value oder by reference? Wie werden Daten zugewiesen, wie wird beim Aufruf von Methoden, Prozeduren, Funktionen mit ihnen umgegangen? In JavaScript ist die Welt einfach geregelt: Primitive Typen werden "by value" behandelt, Objekte "by reference". Nur Strings passen nicht so ganz in das Schema. Strings sind immutable, nicht veränderbar, weshalb es keine Rolle spielt, wie sie behandelt werden.

Welche Anweisungen gibt es? Viele Anweisungen werden Ihnen bekannt vorkommen, wie z.B. "if", "switch", "while", "break", "return" etc. Suchen Sie nach Abweichungen, nach Anweisungen und/oder deren Verwendung, die Sie so aus Ihnen bekannten Sprachen nicht kennen. Den meisten ist die "for"-Schleife aus JavaScript bekannt, nicht jedem jedoch das "for/in".

Wie wird mit Variablen umgegangen? Müssen Variablen deklariert werden? Muss der Typ einer Variablen mit angegeben werden? Wie ist der Scope einer Variablen? Wenn Sie noch nie etwas vom lexikalischen Scope gehört haben -- jetzt müssen Sie sich damit auseinander setzen, denn die meisten Programmiersprachen arbeiten mit lexical scope, so auch JavaScript. Allerdings kennt JavaScript keinen Block-Scope, wie er sich zum Beispiel durch ein Schleifenkonstrukt wie "for" ergibt.

Fundamental ist das Konzept der Variablen, wenn Sie sich als Kenner einer imperativen (anweisungsorientierten) Sprache plötzlich mit einer funktionalen Sprache, wie z.B. Haskell oder Scheme/Lisp, beschäftigen. Plötzlich halten Variablen ihre Werte nicht über die Lebensdauer eines Funktionsaufrufs hinaus. Dauerhafte Wertzustände werden nicht mehr durch Objekte gekapselt; überhaupt arbeitet man in der funktionalen Welt niemals mit impliziten Zuständen. Scheme und Lisp erlauben zwar Ausnahmen, aber Sprachen wie Haskell sind da sehr konsequent und bringen einen mit vollkommen neuen Dingen in Berührung wie zum Beispiel der Zustandsmonade.

Welche Operatoren gibt es? Plus "+", Minus "-", Objekt-Schöpfung "new" etc., all das sind Operatoren. Ohne Operatoren läuft nicht viel. Hier verstecken sich die eigentlichen Arbeitsknechte. Meist sind für Operatoren Vorrangsregeln definiert (wie "Punkt- vor Strich-Rechnung"), die man grob kennen sollte. Ganz wichtig ist es zu klären, was in Ihrer neuen Sprache Gleichheit (equality) von Identität (identity) unterscheidet -- hier spielen "by value" und "by reference" wieder eine wichtige Rolle. Ein anderer wichtiger Operator ist die Zuweisung.

Welche speziellen Konzepte gibt es, die wesentlich für die Sprache sind? Für diese Frage ist es sehr schwer, eine Richtschnurr vorzugeben. Sie müssen zum Kern der Sprache vordringen. Was ist hier anders? Welche Konzepte, welche Konstrukte gibt es, die wesentlich den Charakter und die Denke der Programmiersprache prägen? In JavaScript sind es Funktionen (JavaScript hat ein sehr funktionales Herz) und Objekte/Arrays. JavaScript ist nicht, wie Sie es vermutlich von den meisten OO-Sprachen her kennen, klassen-basiert, sondern prototyp-basiert -- und kennt auch eine Form der Vererbung. Wenn das neu für Sie ist, dann ist hier ein Einstieg gefunden in die Welt von JavaScript. In den Objekten und Funktionen liegt der andere Ansatz verborgen, der JavaScript auszeichnet. Sie beherrschen JavaScript nicht, wenn Sie an dieser Stelle auf einen Abstieg in die Tiefen von JavaScript verzichten. Wenn Sie sich danach noch mit Modulen und Namensräumen beschäftigen, dann haben Sie JavaScript erobert.

Spielen Sie herum -- aber bleiben Sie fokussiert! Tippen Sie kleine Programmschnipsel in einen Editor oder eine IDE, machen Sie Ihre ersten Gehversuche mit der neuen Sprache. Dann prägen sich mache Dinge schneller ein oder man kann sein Verständnis für das eine oder andere Feature austesten. Aber lassen Sie sich nicht ziellos treiben. Ihr Ziel ist, an diesem einen Tag eine neue Sprache so gut und systematisch zu erfassen, wie möglich. Wenn Ihnen etwas Interessantes über den Weg läuft, notieren Sie es sich für später.

Wie geht es nach so einem Tag weiter? Das hängt ganz davon ab, warum Sie sich mit der neuen Sprache auseinander gesetzt haben. Wenn Sie sich weiter mit der Sprache beschäftigen wollen, nutzen Sie die Sprache für Ihr nächstes kleines Projekt oder Vorhaben. Learning by doing ist noch immer der erfolgreichste Weg.

Natürlich bedarf es einiger Wochen bis Monate, bis Sie sich in eine neue Sprache wirklich eingefunden haben; bis sie anfangen, in der Sprache zu denken und fließend in ihr zu sprechen. Mir sind schon des öfteren Talente über den Weg gelaufen, die in acht bis zwölf Wochen von Neulingen zu echten Experten in einer Sprache heranwuchsen. Das gelingt aber nur zusammen mit einem Projekt, das einem täglich die Auseinandersetzung mit der neuen Sprache abfordert.

---

Verraten Sie es mir: Hat Ihnen dieser Beitrag und seine Thematik gefallen? Haben Sie noch weitere Tipps für das Erlernen einer Programmiersprache?

Vom Entwurf zum Programm

2008-02-13T12:42:00.004+01:00

Was lernt man nicht alles für feine Dinge als Softwaretechniker: Die Software-Entwürfe entstehen am Reißbrett, oftmals hart erarbeitet, und sie präsentieren sich als schicke Diagramme. Dabei bedienen wir uns einer "Geheimnotation" namens Unified Modeling Language (UML), die für Laien kaum verständlich ist. Da gibt es Kästchen, Linien, Rauten, Zahlen, Benamungen, Textanmerkungen -- das wirkt alles sehr imposant. Es braucht einiges an Zeit, ehe man die hohe Kunst des Software-Entwurfs erlernt hat.

Irgendwann findet man sich jedoch auf der Programmier-Baustelle wieder. Hier werden die Entwürfe in für einen Computer verständliche Anweisungen umgesetzt. Und, wenn man genau hinschaut, geht es hier schlimmer zu als auf jeder echten Baustelle. Der Programmcode hat nur lose Ähnlichkeiten mit den Entwürfen. Programmierer ziehen mal hier und mal dort eine Wand ein, halten an anderer Stelle einen Durchbruch für angemessen, und das Maßband scheint ihnen völlig abhanden gekommen zu sein. "Pi mal Daumen" -- ja, so ungefähr entspricht das dem Entwurf. Wer seine Aufgabe als Bauherr auf der Programmier-Baustelle ernst nimmt, der kann verzweifeln.

Ein kleines Beispiel gefällig?

Schauen Sie sich mal oben das Bild an. Ein UML-Diagramm, das ich in einer Vorlesung nutze. Es ist ein Entwurf für ein OO-Framework. Hübsch anzusehen, gell? Ich weiß, das Diagramm ist nicht perfekt -- aber darauf kommt es mir hier nicht an.

Zu diesem OO-Framework gibt es eine einfache Implementierung in Python von mir. Auch die spreche ich mit den Studierenden durch. Vor wenigen Wochen, als ich versuchte, den Code zu erklären, griff ich zur Kreide. Ich begann, die Referenzbezüge, so wie sie im Python-Code aufgebaut sind, in einer informellen Notation an die Tafel zu malen, in der Hoffnung, so werde sich der Wald lichten. Tat er aber nicht. Das Ganze entwickelte sich zu einer wunderschönen Fallstudie, wie schwer sich Entwurf und Implementierung tun, aufeinander zu passen.

Was haben die beiden Bilder gemeinsam? Man erkennt Ähnlichkeiten. Die großen Kästchen tragen die gleichen Namen. Aber sonst? An der Tafel sind verwirrend viele Linien hinzugekommen. Wie kommt's?

Ein Kernproblem ist, dass die Ausdrucksmittel aus dem UML-Diagramm keine klare Entsprechung in meiner Zielsprache, der Programmiersprache Python haben. Ich muss also mit "Workarounds" arbeiten, die die Intentionen aus dem Entwurf umsetzen. Zum Beispiel die Kompositionen. In der UML baut eine Komposition besondere Zugriffsbezüge und Abhängigkeiten in den Lebensbezügen auf. In den gängigen OO-Sprachen, wie auch in Python, Java, C# oder Ruby gibt es jedoch keine Komposition. Die meisten OO-Sprachen basieren auf Objekt-Referenzen, die keine Zugriffsbezüge durch Namensräume regeln, jedoch auf den Lebenszyklus von Objekten einen erheblichen Einfluss haben. Also bildet man die Intention der Komposition auf anderen Wegen ab und sorgt sich um einen gesitteten Umgang mit Referenzen. Ähnliches gilt für das "instanceOf".

Und hier gehen die Probleme los. Wer das intendierte Mapping von Code und Entwurf nicht kennt -- dieses Mapping wird nämlich selten, eher gar nicht dokumentiert --, der steht in der Gefahr, irgendwann einmal am Code Änderungen vorzunehmen, die den Entwurf verletzen und der austarierten Balance von Code und Entwurf radikal Schaden zufügt. So entstehen Fehler, die in aller Regel schwer zu entdecken, wenn, dann meist folgenreich sind und deren Beseitigung erhebliche Anstregungen kostet.

Ein anderes Beispiel. In Python nutze ich gerne Dictionaries (sie kennen ähnliches vielleicht als HashMaps oder assoziatives Arrays) -- und zwar als Caches für einen schnellen Zugriff auf Objekte unter einem Schlüssel. Es sind die "Qualifier" (die kleinen Boxen an den großen Boxen) auf dem Tafelbild. Streng genommen, mit Blick auf den Entwurf, bräuchte ich sowas nicht. Doch der Einsatz von Dictionaries macht den Python-Code oft einfacher und übersichtlicher. Der Preis: Ich entferne mich vom Entwurf. Die Dictionaries beginnen ein Eigenleben zu führen.

Wenn Sie Studentin oder Student der Informatik sind, dann haben sie wahrscheinlich zahllose, weitere solche Beispiele auf Lager, die einen erheblichen "Clash" aufzeigen zwischen Entwurf und Umsetzung. Bisweilen entsteht das UML-Diagramm zum Entwurf erst nachträglich, nach der Programmierung, und schönt und verhübscht die "Häßlichkeiten" des Codes erheblich.

Sind Codegeneratoren ein Ausweg, die aus UML-Diagrammen direkt den Programm-Code (z.B. für Python) erzeugen? Jaein. Zum einen ist es gar nicht so einfach, gute schematische Code-Templates für die Code-Generation zu entwickeln. Der Versuch, Komposition sauber in einer rein referenz-basierten Sprache nachzubilden, ist nicht wenig aufwendig und versucht einer Sprache etwas überzustülpen, wofür sie nicht gemacht wurde. Das ist zumindest bei einem Blick auf das Laufzeitverhalten nicht ganz außer acht zu lassen. Allein die Nachbildung von Singletons, ein lapidarer Stereotyp in der UML, ist nicht trivial, besonders wenn Singletons thread-safe sein sollen.

Doch das eigentliche Problem liegt in meinen Augen tiefer. Code-Generierung aus Entwürfen ist ok, sofern man einen ausführbaren Entwurf haben möchte. Nicht immer ist das sinnvoll. Wichtig ist zu erkennen, dass es einen Unterschied gibt zwischen Entwurf (Design) und Umsetzung (Implementierung). Eine Umsetzung muss einen Entwurf erfüllen. Nicht mehr und nicht weniger. Das wird wenig verstanden. Ich habe versucht in meinen Posts zu User, Domain und Realization Model darauf in einem anderen Kontext einzugehen. Denn häufig sehe ich nicht nur Studierende, sondern auch Profis einen Fehler machen: Es wird weniger über einen Entwurf nachgedacht! Es wird Programmcode mit Hilfe von UML-Diagrammen beschrieben, nicht ein Entwurf! Dann wird der Code-Generator nur zum Erfüllungsgehilfen von mit Diagrammen "gemaltem" Code.

Glauben Sie nicht? Wann haben Sie das letzte Mal Mehrfachvererbung angewendet? Das wird Ihnen als Ausdrucksmittel in der UML für Ihre Entwürfe angeboten und kann ganz hilfreich sein. Was? Mehrfachvererbung nutzen Sie nicht? Warum? Weil Sie Java- oder C#-Programmierer sind? Erwischt! :-)

TrueCrypt "entschlüsselt"

2008-01-07T15:04:00.000+01:00

Sollten Sie Windows- oder Linux-User sein und TrueCrypt noch nicht kennen -- ich kann Ihnen dieses OpenSource-Programm nur empfehlen. Es verschlüsselt eine Festplatte entweder vollständig oder einzelne Files darauf und hängt diese wie ganz gewöhnliche Plattenpartitionen in Ihr Filesystem ein. Komfortabler geht's fast nicht. Ich schütze mit Hilfe von TrueCrypt unter anderem meine Backups auf einer externen Festplatte gegen unberechtigten Zugriff. Wenn Sie eine Einstiegshilfe benötigen, so mag Ihnen vielleicht der Beitrag "Sicher aufbewahrt" von Andreas Beier (heise mobil, 2005-04-25) dienlich sein.

Vor wenigen Tagen hat Björn Edström auf seinem Blog die Arbeitsweise von TrueCrypt erklärt. "TrueCrypt explained" ist ein sehr lesenswerter Beitrag, besonders für diejenigen unter Ihnen, die TrueCrypt etwas detaillierter verstehen wollen. Der Beitrag ist auch ein schönes Anschauungsbeispiel dafür, dass solche Software im Prinzip gar nicht so komplex und schwer zu entwickeln ist, wie man vielleicht vermuten mag.

Das 2 Millionen-Studium

2007-12-12T21:02:00.000+01:00

2 Millionen Minuten -- so lange dauert ein vierjähriges Studium. Das rechnet uns der Filmemacher Robert A. Compton in seinem Film "Two Million Minutes" vor. Die Flash-Animation zur Filmwebseite baut eine bedrohliche Kulisse auf: Indische und chinesische Studierende nutzen die zwei Millionen Minuten ihres Studiums deutlich mehr und umfassender als amerikanische Studierende. Es scheint nur eine Frage der Zeit zu sein, bis dieses Potential an Bildung der amerikanischen Vorherrschaft in den Naturwissenschaften, in den Ingenieurswissenschaften und in der Informatik die Ränge abläuft. Anbei: Wir Europäer kommen in dem Film gar nicht vor.

Wenn Sie mögen, hier der Trailer:

Ist es wirklich so schlimm? Heute hat die Bertelsmann-Stiftung die Ergebnisse einer Repräsentativbefragung vorgestellt: "Wer regiert die Welt?". Befragt wurden 8.999 Bürger aus Brasilien, China, Deutschland, Frankreich, Großbritannien, Indien, Japan, Russland und den USA. Wie sie die internationale Rolle ihrer Länder sehen etc. Für das Jahr 2020 rechnen die Befragten mit einer gleichberechtigten Rolle Chinas als Weltmacht neben den USA. Mit deutlichem Abstand folgen fast gleichauf Russland, die EU, Japan und Indien.

China, Russland, Indien -- das sind keine Überraschungskandidaten. Wenn man in jüngster Zeit erlebt, wie sehr gut ausgebildete russische und indische Informatiker mit StartUps und mit Innovationen auf die Märkte drängen -- man kann ans Grübeln kommen.

Fazit? Work smarter, not harder?! Ja, immer doch, aber ich glaube -- ehrlich gesagt -- das wird nicht reichen, wenn wir dem Wettbewerb stand halten wollen. Ein guter Teil der Informatik-Ausbildung und des Könnens ist reines "Handwerk", so wie in vielen anderen Studiengängen auch. Da bekommt Übung und Erfahrung nur der, der etwas tut. Mit Smartheit allein wird niemand ein guter Pianist; mit viel Übung kommt man allerdings schon sehr weit.

Googles Chart-API und seine Nachhaltigkeit

2007-12-09T12:43:00.000+01:00

Am Nikolaustag hat Google das Web um ein weiteres API (Application Programming Interface) bereichert: das Chart-API. Der Gebrauch des APIs ist einfach und das Resultat schön anzusehen. Kein Wunder also, dass sich die Ankündigung des Chart-APIs wie ein Lauffeuer in der Bloggosphäre verbreitet. Mit einem einfachen HTTP-Request wie diesem als src-Attribut in einem img-Tag


http://chart.apis.google.com/chart?cht=p3&chd=s:Uf9a&chs=200x100&chl=A|B|C|D">

ergibt sich der folgende visuelle Effekt:

Das API scheint wirklich nützlich zu sein, wenngleich das Interface für Menschen wenig intuitiv ist. Insofern darf man gespannt sein auf die ersten Webseiten, die einem mit einer graphischen Oberfläche beim Erstellen solcher Charts helfen und ein einfaches Experimentieren mit den Parametervarianten ermöglichen. Das sollte mit ein wenig HTML-Code und JavaScript zu machen sein.

Solche APIs gehen in die richtige Richtung: Sie machen Web-Seiten rein beschreibend (deklarativ), die Kern-Information und damit die Semantik von Daten bleibt erhalten und sie verführen zum Gebrauch, da sie sinnvoll und nützlich sind. Es würde mich nicht wundern, wenn in Zukunft solche deklarativen Service-APIs, zusammen mit den sogenannten Microformaten und Meta-Daten (z.B. in Form von Tags) das Web mehr und besser um semantische Information bereichern als es die ganzen bisherigen Standardisierungsversuche des W3C zum semantischen Web geschafft haben. Zumindest dann, wenn Menschen bei der Erstellung von webfähigen Inhalten zur Anreicherung um semantische Informationen verleiten werden sollen.

Ein Problem jedoch bleibt beim Einsatz von APIs: Was, wenn der Google-Dienst einmal ausfällt oder nicht verfügbar ist (z.B. da man offline ist)? Dann durchziehen eine Webseite Informationslöcher. Was, wenn Google das API ändert ohne kompatibel zu früheren Versionen zu sein?

Es wird zunehmend wichtiger, sich mit der Problematik der Nachhaltigkeit (um den Begriff auch mal in so einem Kontext zu verwenden) von Web-Seiten auseinander zu setzen. Wie können Webseiten zuverlässig gerendert (d.h. vollständig visuell aufbereitet) werden, auch wenn die dazu benötigten Web-Dienste nicht jederzeit und immer zur Verfügung stehen? Ein Grundproblem aller verteilten, dezentralen Systeme. Dabei sind einfache Ein-/Ausgabedienste wie Googles Chart-API noch das geringste Problem.

Eine simple Möglichkeit besteht darin, ein einmal über das Chart-API angefordertes Bild abzuspeichern und als Alternative lokal oder auf einem Webserver vorzuhalten. Um diesen Vorgang im Hintergrund zu automatisieren, kann man etwa mit Erweiterungen zum Browser arbeiten oder einen Webserver diese Arbeit machen lassen. Mir fallen einige Lösungsstrategien dazu ein. Und das ist genau der wunde Punkt daran: Lösungsmöglichkeiten zur Nachhaltigkeit von Webseiten gibt es viele. Doch was hilft es, wenn es so viele Nachhaltigkeitslösungen wie Service-APIs gibt? Man wird sich in Zukunft mit offline-Techniken als nahtlose Fortsetzung des online-Zustandes befassen müssen -- und sich gleichzeitig um die Nachhaltigkeit der Darstellung deklarativer Informationen kümmern müssen. Dienste wie Google Gears sind dabei ein Teil möglicher, brauchbarer Lösungsansätze.

Körpersprache für Informatiker?

2007-12-06T09:18:00.000+01:00

Dem Informatiker, besser: dem Hacker (dem "guten" wie dem "bösen"), hängt ein Vorurteil an: Wir sind Menschen, die bis tief in die Nacht vor unseren Maschinen hängen -- und tagsüber Räume notfalls abdunkeln. Wir beschallen uns via Kopfhörer mit Musik, um uns akustisch von der Welt zu isolieren. Wir tauchen für Stunden ab, sind nicht ansprechbar. Die totale Versenkung. Wir sind eins mit der Maschine, mit dem Programm, mit dem ByteCode. Das Programm bin ich, ich bin das Programm. Und zum Glück kann man zum Mittagessen um 2 Uhr morgens noch Pizza beim Pizza-Service bestellen.

Stimmt alles! ;-)

Nur sind wir deswegen noch lange keine sozialen Krüppel, die solche Videos benötigen, um das Verhalten unserer Mitmenschen zu disassemblieren und zu interpretieren.

Amüsiert frage ich mich, welche Berufsgruppe oder Menschengruppe solche Videos wirklich braucht -- die schon fast wieder gut sind, so schlecht wie sie sind.

[Video entdeckt im "Mixing Memory"-Blog: "Who Does This Remind You Of?" posted on: December 2, 2007 8:23 PM, by Chris.]

Ein neuer Markt: Von Wissenschaftsblogs und Kunstgalerien

2007-12-04T00:29:00.000+01:00

Liebe Wissenschaftsblogger,

das Web 2.0, dieses Mitmach-Web, ist ein Medium, das findige Unternehmen nach Marktpotenzialen ausloten. Wir Wissenschaftler bzw. Wissenschaftsjournalisten sind offenbar eine interessante Zielgruppe. Wir produzieren Content, der gefragt ist. Und dagegen ist überhaupt nichts zu sagen!

Aber ach, was red ich. Wollte ich Ihnen nicht eine Geschichte erzählen von einem Freund im Geiste, einem Künstler?

Da war ein Künstler, dessen Bilder einem Großgaleristen gefielen. So sagte der Galerist zu dem Künstler: "Ich will eine Künstler-Community aufbauen! Ich biete Dir meine Galerie zur Ausstellung Deiner Bilder an. Nicht allein, Deine Bilder zeige ich zusammen mit Werken anderer Künstler. Du wirst Deinen Wirkungskreis erhöhen und Du wirst weitere Künstler kennenlernen. Bist Du dabei? Übrigens, das Ganze kostet Dich nichts; ich leg' Dir noch ein paar Euro im Monat drauf."

Der Künstler freute sich. Dass zwischen den Bildern Werbeplakate hängen sollten, nahm der Künstler seufzend zur Kenntnis. Aber irgendwie muss ja auch der Großgalerist Geld bei der Sache verdienen können. Kunst und Kommerz -- das muss sich ja nicht ausschließen.

Dann kam der Vertrag vom Galeristen mit der Post. Da stand zum Beispiel, er solle doch nach Möglichkeit an jedem Werktag ein Bild malen. Wie das?! Er malte ein Bild im Monat, manchmal sogar zwei oder drei, wenn es sehr gut lief vier oder fünf -- aber Fließbandkreativität? Seltsam, das klang alles so anders als im Gespräch mit dem Galeristen. Der Künstler verstand nicht viel von Juristerei, also zog er einen Anwalt zu Rate. Und der sagte ihm: "Laß die Finger von dem Vertrag. Der Galerist erhält alle Rechte an deinen Bildern, sie gehören dir nicht mehr. Er darf deine Bilder sogar übermalen, wenn er Lust dazu hat. Und übrigens: Gegen Diebstahl und Vandalismus musst du deine Bilder selber versichern. Ich kenne keine Versicherung, die das für 'ein paar Euro' macht."

Da sprach der Künstler mit dem Galeristen. Der fiel ihm sogleich ins Wort: "Warum so ein Misstrauen, mein Lieber?! Du glaubst doch nicht, dass ich reich werde mit meiner Galerie. Die paar Werbeverträge! Und wer spricht denn von Zensur, wer hat dir denn diese Flausen in den Kopf gesetzt? Ich kann mir doch gar nicht die Mitarbeiter leisten, all die Bilder von dir und deinen Künstlerkollegen durchsehen zu lassen und sie zu 'korrigieren'. Was sollte ich für ein Interesse daran haben. Klar, wir werden mal einen Bildband mit den besten Werken von der Künstler-Community herausbringen. Aber das ist doch alles in Deinem Sinne, oder?"

Der Künstler unterschrieb den Vertrag nicht. Er war froh, sich einen Rechtsbeistand geholt zu haben. Und so malte er weiter: frei!

Sie sehen, ich blogge immer noch unter Google. Gebt auf Euch acht, liebe Wissenschaftsblogger. Freiheit kann man einem Künstler gleich auch in kleinen unabhängigen Galerien genießen. Oder in einem Wissenschafts-Cafe! Man sieht sich ;-)

"Dienst oder Dienstmerkmal nicht möglich."

2007-11-28T16:39:00.000+01:00

Letzte Woche war ich auf der USAB 2007 (Usability & HCI for Medicine and Health Care; HCI steht für Human Computer Interaction) und begeisterte mich an der Keynote von Harold Thimbleby, der an der Swansea University (UK) lehrt. Thema: "User-Centered Methods are Insufficient for Safety Critical Systems". Irgendetwas hat er in mir losgetreten, und seitdem laufe ich etwas aufgeweckter durch die Gegend, was die Gestaltung von Mensch/Computer-Schnittstellen betrifft. Zwei Beispiele aus den letzten Tagen:

Flughafen Frankfurt am Main. Ich bin eben gelandet, bin zum Ausgang raus und steure die Automaten an, um mein Parkticket für das Auto zu bezahlen. Ich schiebe die Parkkarte in den Automaten, das Geld hinterher, bekomme die Parkkarte zurück und realisiere erst in dem Moment, dass ich eine Quittung über die Parkgebühr benötige. Schnell noch die Quittungstaste gedrückt -- die mir den Dienst verweigert. Ihr fehle eine Parkkarte! Also schiebe ich die Parkkarte wieder in den Automaten in der Hoffnung, nachträglich eine Quittung anfordern zu können. Geht nicht, "Parkgebühren bezahlt". Mir bleibt nichts anderes übrig als mich an der Ausfahrtschranke an den Parkwächter zu wenden und ihn um eine Quittung zu bitten. Der Vorgang dauert etwa 3-4 Minuten, wobei der Parkwächter sich einmal am Rechner vertippt, um festzustellen, ob meine Karte bereits bezahlt ist.

Verblüffend, wie die Entwickler der Bezahlautomaten das Szenario der nachgeforderten Quittung schlicht ignoriert haben, gell? Vor mir war ein Mann beim Parkwächter an der Reihe, der überraschenderweise exakt dasselbe Problem hatte. Vermutlich kommt das an einem Flughafen wie Frankfurt etliche Male am Tag vor. Wie kann man sowas übersehen?

Gestern. Ich rufe meine Frau im Büro an. Die Leitung ist besetzt. Ein Stimme fragt mich, ob ich gerne den automatischen Wiederwahl-Dienst bei Freiwerden der Leitung nutzen möchte. Ich möge dazu "Ja" in den Hörer sprechen. Ich sage "Ja" und bekomme zu hören: "Dienst oder Dienstmerkmal nicht möglich."

Warum in aller Welt bekomme ich eine Option angeboten, die nicht ausgeführt werden kann? Kann der Computer das nicht vorher ermitteln und mir den Service nur anbieten, wenn er verfügbar ist? Gut möglich, dass mir jetzt ein Software-Entwickler lang und breit erklären kann, warum das so sein muss. Die Software könne das nicht vorher erkennen. Das war ein Punkt in Thimblebys Keynote: Ist ein schlechtes Design eine Entschuldigung? Wenn eine Software nicht vorher ermitteln kann, ob sie dem Nutzer ein Leistungsmerkmal anbieten kann oder nicht, dann ist sie schlecht entworfen.

Haben Sie ähnliche Erfahrungen gemacht? Wenn Sie mögen, berichten Sie mir davon!

User, Domain and Realization Models

2007-11-24T02:12:00.000+01:00

In my previous post on "Modeling Illusions" I distinguished between the illusion, manifested by a domain model, and the model that does the trick, the realization model. The interesting question is: How do these two models relate to each other?

If I managed to explain things well, you should have understood that both models implement the same interface and that they behave exactly the same for an external observer. Otherwise, it would be useless to talk about an "illusion". From the outside, there is no way to tell which model is actually operating "behind the wall". From this viewpoint, both models are interchangeable.

Note that this statement highlights a very crucial point. If you cannot say what's behind the wall, you experience and develop a consistent mental model of the interface and it's behavior from the outside. We call this mental model the user model of the interface.

So we are having three models: From an external viewpoint, we have a user model a user associates with the interface; it is the user's perception of the illusion. Behind the wall, from an inner perspective, the interface is either implemented by a domain model, describing the illusion from an inner perspective, or by a realization model, an alternative description for the illusion.

The relation between the models is as follows: In terms of size, better: information content, the following formula holds:

user model <= domain model < realization model

Ideally, the user model and the domain model match. However, the realization model must be "bigger" than the domain model. Both, the domain model and the realization model, must have the capability to generate the same external user experience. But there must be more to the realization model. Otherwise why should you call it a realization? You could also say that the realization has more information content than the domain model by definition.

From a software engineering standpoint, the realization model should be developed in such a way that it can be easily verified against the domain model(!). It should be easy to show that the state model the realization model implements includes the state model of the domain model. Alas, this is not standard practice. Only very few software engineers know and understand the cascade of these three models: user model (external interface experience), domain model and realization model (alternative interface implementations). To distinguish and actually use domain and realization models is a very powerful technique to manage complexity. This technique is, however, of limited use, when there is no way to show that the realization model actually realizes the domain model.

There are some techniques around to keep the realization and the domain model "in sync". One is to use generative techniques to generate the realization model out of the domain model (catchword "Domain Specific Modeling"). Another is to use Aspect-Orientation, which enables a designer to add realization aspects to an domain model. Formal methods may help prove that the realization model is consistent with the domain model. So there are some important tools around in the toolbox of a software engineer.

By the way: User models are crucial in (User) Interface Design!

Modeling Illusions

2007-11-19T12:17:00.000+01:00

A very important tool in software engineering (SE) is modeling illusions. In SE, engineers most often focus solely on realizations not illusions. However, illusions are the magic to create self-contained worlds (or domains), to separate design spaces and thereby simplify design. Modeling illusions is an art which is rarely understood and applied.

What do I mean by illusions? Let me give you some examples: Look at your desktop on your computer screen -- it's an illusion. There is no desktop in your computer. See the little small icon you call a dustbin or trash can? It's an illusion. Take a screwdriver and open your computer; you won't find a dustbin in there. Your files on your hard disk are organized in directories which are nested in a hierarchy. It's an illusion. Your hard disk actually has multiple platters and read/write heads, and each platter is organized in tracks and sectors (see also "How Hard Disks Work"). You work with databases, handle tables, keys, relationships? The world implied by SQL is an illusion. Look at any serious, high-performance database implementation. It's about B-trees and similar stuff.

The essence is: You have to distinguish an illusion from it's realization. What they share and have in common is the (user) interface. It's the interface that creates an illusion!

You got it? What I'm after is the following:

Any interface creates an illusion. A software engineer should describe the illusion from two different viewpoints: One model describes the elements of the illusion, how they can be used, how they relate and interact and so on. It's a domain model of the illusion. The other model describes how the illusion was done; it unveals the trick of the "magician". It's a realization model of the illusion. Others might also call it an "implementation model".

My point is: Software Engineers usually miss the point to consider each model as a model in it's own right. They are sloppy with the domain model but careful with the realization model. This is bad, because domain models are one of the most valuable modeling techniques to reduce complexity for system's understanding. A domain model can be taken as serious as a realization model and being made executable. Then, you have a choice: You can look at your interface and work either with an executable model of the illusion or you can look at your interface and work with an executable model of the illusion's realization, thereby looking behind the scenes. The domain model lets us ignore the complexities of the realization; but the domain model is complete and creates a self-contained illusion. It is as if the magic were true. The realization model opens up a new level of complexity.

Let me give you a final example -- it also complements my criticism on "The law of leaky abstractions":

What kind of illusion does TCP create for you? The TCP user interface provides a connection-oriented communication service. It creates the illusion of a reliable connection to communicate data with someone else (you asked to accept the connection beforehand). That's the illusion.

If we look at how the trick is done, the realization, we see a state machine realizing a nice rendezvous with a remote state machine sending IP datagrams back and forth. These two state machine implement the so-called TCP protocol. TCP relies on IP.

If you do socket programming (that's using TCP connections, for the ones who do not know), the socket library of your favorite programming language offers you to work with the illusion of a TCP connection. Beyond that socket libraries fall short of the notion of a connection. Nobody really cares about a rock-solid domain model of TCP, they all do in Unix/Linux and Windows is creating realizations. In a rock-solid domain model a TCP connection would be associated with some statistic properties. You could ask the connection about some statistic properties: How reliable is the connection, how many data packages got lost and had to be retransmitted etc.? If a domain model of TCP were carefully done and accessible in socket libraries, nobody would be so naive to believe that TCP would come at no costs and actually be 100% reliable. If you abstract these details away, you might do so for the purpose of simplification, but you should know what you're doing.

E8 und die "Theory of Everything"

2007-11-15T21:44:00.000+01:00

Das lässt Sie sicher auch stutzig werden, wenn Sie hören, jemand habe die "Theory of Everything" gefunden -- auch wenn es dabei "nur" um Physik geht. In der Tat suchen die theoretischen Physiker nach so einer Theorie, die alle physikalischen Phänomene unter einen Hut bringt. Klingt hart und ziemlich schwer.

Nun will ein Surfer (nein, so ein Wasser-Surfer, der in Hawaii surft) genau diese Theorie gefunden haben, so berichtet der Telegraph in "Surfer dude stuns physicists with theory of everything" (Roger Highfield, 6:01pm GMT 14/11/2007). Klar, so mal eben beim Surfen drauf gekommen! Unsinn. Doch wenn Sie den Artikel weiter lesen, dann wird die Sache schon ernster. Da ist ein Fachmann am Werk. Das mit dem Surfer verkauft sich halt ein bissel besser. Unser "Dude" Garrett Lisi scheint's drauf zu haben. Quellensuche.

Lisis Artikel hat den schlichten, anspruchsvollen Titel "An Exceptionally Simple Theory of Everything", Sie können ihn bei arXiv.org runterladen. Ich verstehe darin zwar ehrlich gesagt kein Wort, aber das Ganze wirkt solide, ist sehr schön geschrieben (lesen Sie mal Einleitung und Schluss) und hat das Entscheidende, was so eine Theorie braucht: die Theorie macht Vorhersagen, die sie falsifizierbar, sprich widerlegbar machen. Lisi zeigt einen Weg auf, wie die vier fundamentalen Grundkräfte (die starke und schwache Wechselwirkung, die elektromagnetische Kraft und die Gravitation) in eine mathematische Struktur namens E8 abgebildet werden können. Bei dieser Abbildung bleiben ein paar wenige Plätze "unbesetzt". Lisi sagt damit neue Phänomene (Teilchen) voraus, womit seine Theorie entweder bestätigt oder ad absurdum geführt werden kann.

Jetzt bin ich doch gespannt, was die anderen "Surfer" (genau, die Physiker) dieser Welt dazu zu sagen haben. Ist unser Universum wirklich E8?

Wollen Sie meine Meinung dazu hören? "E" ist der fünfte Buchstabe im Alphabet. "E" mal 8 macht 40. Die Antwort auf alles lautet aber 42. Ich fürchte, Lisi muss nachbessern ;-)

Update: Ich scheine mit "E" * 8 = 40 <> 42 nicht allein zu sein, wie ich gerade in einem anderen Blog entdecke. Nur gibt es Leute, die solche Kritik (da sie vielleicht davon etwas verstehen) besser ausdrücken können. Letztlich bin ich jedoch ahnungslos. So ist das, wenn ich nicht über Informatik schreibe. Spaßig finde ich solche Sachen trotzdem. Es ist dem Glauben an den Fortschritt geschuldet.

Mini-Laptops

2007-11-08T16:10:00.000+01:00

Seit über zwei Monaten sind Zimtsterne, Marzinpankugeln und all die vielen Weihnachtsleckereien in den Supermärkten zu haben. Mir ist es unergründlich, warum die Marktstrategen glauben, uns auf einer monatelangen "Freßspur" zum Fest führen zu müssen.

Allmählich erinnern auch die PC-Hersteller an das große Fest. Heute schon gewünscht? Ich bin vor zwei, drei Tagen auf den Eee PC von Asus gestoßen. Irgendwie macht mich das Ding an. Klein, portabel, WLAN, alle wichtigsten Anwendungen dabei, USB- und Beamer-Anschluss. Kleine Tastaturen stören mich nicht. Der Preis macht Appetit! Damit können sich auch viele Studierenden einen kleinen aber feinen Rechenzwerg leisten. (Zur Software-Entwicklung ist der Laptop sicher weniger geeignet und man muss sich vermutlich auf sehr einfache Werkzeuge beschränken.) Das Gerät wäre mir ein schöner Reisebegleiter. Die ersten Testberichte klingen auch gut, siehe z.B. bei heise mobil. Lieber noch hätte ich einen XO Laptop, der mir brillant konzipiert zu sein scheint und den ich allein deshalb gerne einmal genauer unter die Lupe nehmen möchte. Doch es wird vermutlich schwer sein, in Europa an solch ein Gerät zu kommen.

Nun bin ich gespannt, mit welchen Konkurrenzprodukten andere Hersteller im "Mini-Laptop-Segment" aufwarten werden. Denn noch hat's ja ein bissle Zeit mit dem Wünschen.

Update 19. Nov.: Wie spannend, die Preise für ähnliche Produke beginnen zu purzeln, siehe "VIA und FIC wollen beim EeePC-Preis mithalten" (heise news, 2007-11-18).

Hey Django!

2007-11-01T19:06:00.000+01:00

Wie lässt sich zügig eine webbasierte Anwendung entwickeln, die auf einer relationalen Datenbank aufsetzt?

Da ich gerade ein Projekt betreue, bei dem es genau auf diese beiden Punkte ankommt (webbasiert und datenbankgetrieben), gab ich mir selber einen Tag, um mir eine "moderne" Entwicklungsumgebung und ein "modernes" Framework anzuschauen. Der erste Kandidat: Zoho Creator; der zweite: Django.

Zoho ist eine Firma, die sich -- wie einige andere auch -- dem Nachbau von Desktop-Software auf rein webbasierter Basis widmet, meist ergänzt um Features zur Kollaboration. Darunter finden sich Nachbauten von Word und Excel, eine Projektmanagement-Software, ein Wiki. Meine Aufmerksamkeit erregte jedoch bereits vor einiger Zeit ZOHO Creator, eine vollständig browserbasierte Entwicklungsumgebung zum Bau von Datenbank-Anwendungen. Zoho wirbt mit einer kinderleichten Programmierung, die selbst Amateuren Erfolge bescheren soll.

Dieses Versprechen kann Zoho Creator nicht einhalten. Der Einstieg gelingt zwar schnell, aber ich verzweifelte schon an relativ einfachen Problemen. Die erzwangen das Verlassen der visuell-orientierten Programmierumgebung (die wirklich fein gemacht ist!). Der Wechsel ins "Free-flow Scripting" erwies sich aufgrund einer mageren Dokumentation als Frust- und weniger als Flow-Erlebnis. Nach drei Stunden gab ich auf.

Django reiht sich ein in die Schlange der Frameworks, die "Ruby on Rails" gleich eine ungekannte Leichtigkeit der Webprogrammierung proklamieren. Meine Wahl fiel auf Django, da ich eine exzellente Dokumentation vorfand und mit einer mir vertrauten Programmiersprache operieren wollte. Django läuft unter Python.

Der Einstieg quälte sich etwas dahin, da es eine Menge Lesematerial zu verdauen gilt -- die Intros sind sehr gut und aktuell. Ich wurde jedoch skeptisch, da ich vieles "fressen" musste ohne es zu verstehen. Dann, nach zwei Stunden, als mein Datenbankschema endlich stand, durfte ich die Vorzüge erfahren, die "late binding"-Programmiersprachen mit sich bringen: Änderungen am Code übernimmt der Webserver automatisch; man kann unmittelbar am Browser den Erfolg der Bemühungen austesten. Die Entwicklung wird flüssig, man hat permanentes Feedback. Nach etwas mehr als einem halben Tag hatte ich einen guten Teil des Projekts umgesetzt. Von Null! Das nenne ich "Flow-Scripting". Allerdings muss man sich mit Python auskennen, sonst steht man bei Fehlermeldungen etwas verloren da.

Interessant ist, dass man bei Django sehr deklarativ programmiert (wie auch bei Ruby on Rails). Man beschreibt, konfiguriert, hat funktional so gut wie keine Zeile programmiert und bekommt ein vollständiges Administrations-WebInterface "geschenkt". Ähnlich deskriptiv geht im Grunde auch Zoho Creator vor -- nur mangelt es dem Produkt entweder an Reife oder an Dokumentation.

Mein Resümee: Zoho Creator macht vor, wie man ausgezeichnete interaktive Oberflächen mit Ajax-Technologie entwickeln kann; da kann sich manch andere Firma ein Scheibchen von abschneiden. Frameworks wie Django oder "Ruby on Rails" zeigen, wie flüssig und leicht die Entwicklung von webbasierten Anwendungen von der Hand gehen kann. Das ist weniger eine Frage der IDE als vielmehr des Frameworks.

Billigflug: Gun Fighter

2007-10-29T10:58:00.000+01:00

Erinnern Sie sich noch an Tetris? An die herabfallenden Klötzchen? Es ist eine kleine Ewigkeit her, gell?! Mit Tetris verbindet mich die faszinierende Erfahrung, dass man nach acht oder zehn Stunden ununterbrochenem Tetris-Spiel davon träumt und die ganze Nacht über weiter Klötzchen dreht, sie nach links oder rechts bewegt, Space-Taste drückt und sie herabfallen lässt. Eine ziemlich gute Simulation, die das Hirn da vollbringt; der sogenannte Tetris-Effekt. Das hat mich seinerzeit wirklich beeindruckt. Am frühen Morgen, wieder vorm Computer sitzend (wach, aber eigentlich macht es keinen großen Unterschied ;-), ist der Highscore vom Vorabend mühelos gebrochen. Das Hirn hat im Schlaf gelernt, Tetris noch besser zu spielen. (Dazu gibt es übrigens auch einen netten Artikel auf ScientificAmerican.com von Kristin Leutwyler: Tetris Dreams, October 16, 2000.)

Denk ich an Tetris, denk ich an Space Invaders, Phoenix, Pac Man, Ping Pong und ähnliche Spielchen -- die Computerspiele meiner Jugendjahre. Das ist ein Weilchen her. Vielleicht können Sie sich vorstellen, mit was für großen Augen ich Ende August in Halle in einem Supermarkt diese Pappschachtel entdeckte (siehe Bild). Ballerspiele aus den 80igern im Format zweier handlicher "Joysticks" mit Fernsehanschluss für sagenhafte 6.49 Euro. Klar, das musste ich haben. An dem Abend schwelgte ich mit meinem besten Freund in den guten alten Zeiten. Wir steuerten Raumschiffe, lenkten Panzer, fuhren Autorennen, eroberten den Weltraum, ballerten uns den Weg frei -- und hatten eine Menge Spaß dabei.

Die Nacht schlief ich dann ganz normal. Keine Träume in Pixelgraphik. Schade.

Sloppy Abstractions

2007-10-26T20:18:00.000+02:00

There is a very powerful engineering technique, computer scientists make also use of: abstraction. But did you know that abstractions can be leaky?

I had heard about "The Law of Leaky Abstractions" some time ago; now, it again caught my attention, because Philip Wadler mentioned it on his blog. Reason enough to read Joel Spolsky's post (written November 2002) more carefully.

Spolsky's "Law of Leaky Abstractions" says

All non-trivial abstractions, to some degree, are leaky.

He explains his "law" mainly on the example of the TCP protocol (his actor analogy is brilliant and funny) and concludes:

I said that TCP guarantees that your message will arrive. It doesn't, actually. If your pet snake has chewed through the network cable leading to your computer, and no IP packets can get through, then TCP can't do anything about it and your message doesn't arrive.
[...]
This is what I call a leaky abstraction. TCP attempts to provide a complete abstraction of an underlying unreliable network, but sometimes, the network leaks through the abstraction and you feel the things that the abstraction can't quite protect you from.

Spolsky is absolutely correct with his description on TCP -- but I do not agree to his conclusion. There's nothing leaky here. Take network designers. They are fully aware of the services and the quality of the services TCP provides to the next layer in a protocol stack; they also know the limitations of TCP. They know that TCP can fail. And you do as well! What makes ebay so freaky exciting? To deliver your last bid on the very last moment before the auction is over -- and hope the very best for your network connection. You are very much aware that your network might go down in that very moment; TCP won't safe you! Right?!

If you forget that TCP might fail completely, you weren't that pedantic on understanding TCP. You were quite sloppy with your abstraction -- that's all.

The difference between a junior and a senior developer is that a senior doesn't have that many sloppy abstractions a junior has.

Merk Dir mal ein Bit!

2007-10-16T15:27:00.000+02:00

Haben Sie schon einmal daran gedacht, sich einfrieren und später, irgendwann in der Zukunft, wieder auftauen zu lassen? Das würde etwa die Wartezeit bei einem Flug zum Mars erheblich verkürzen. Was auch immer Ihr persönlicher Grund für eine solche Aktion sein möge, lassen Sie die Finger davon. Mal abgesehen davon, dass das Einfrieren und Auftauen von Zellen eine äußerst heikle Angelegenheit ist -- es kostet Sie nur Geld und lässt Sie strohdumm werden! Ganz richtig: Es macht Sie dumm! Warum? Lassen Sie mich mit einem kleinen Exkurs beginnen: Wie wird Information gespeichert?

Es gibt zwei Arten der Speicherung von Information. Ich möchte Ihnen das anschaulich an zwei Beispielen erläutern:

Nehmen Sie ein kleines Behältnis, eine Schatulle etwa, die ein Steinchen aufnehmen kann. Ist die Schatulle leer, hat die Schatulle den Wert Null gespeichert. Ist das Steinchen in der Schatulle, wollen wir das als den Wert Eins verstehen.

Das ist das wohl am weitesten verbreitete Verständnis eines Informationsspeichers: in einem Gedächtnis (einer Art Riesenschatulle) kann Wissen "abgelegt" werden.

Doch es gibt eine interessante Alternative dazu: Nehmen Sie eine Tasse mit Kaffee und rühren Sie den Kaffee rechts herum: Eins. Rühren Sie ihn links herum: Null. Die Rotationsrichtung des Kaffees enthält die Information! Wenn Sie zu lange warten, sorgen Reibungsverluste dafür, dass dem System Energie entzogen wird und sich irgendwann ein undefinierter Zustand ergibt: der Kaffee rotiert nicht mehr, die Information ist vergessen.

Wir haben also zwei Fälle vorliegen:

Informationsträger ist Materie und örtlich gebunden (Raum)

Informationsträger ist Energie und zeitlich gebunden (Fluß)

In technischen Systemen wird das Rotierenlassen von Energie zur Informationsspeicherung durch Rückkopplung erreicht. Rückkopplung ist die Rückführung von Ausgängen an Eingänge. Ein sehr schönes Beispiel ist das Flipflop, das z.B. aus zwei NOR-Gattern besteht. Der Schaltkreis selbst ist materielle Information und räumlich gebunden. Der in die materiellen Bahnen geleitete Energiefluss (vereinfacht gesagt der Strom) kann in eine stabile "Rotationsrichtung" versetzt werden -- und merkt sich darüber ein Bit: linksdrehend bzw. rechtsdrehend.

Was passiert, wenn wir ein Flipflop im laufenden Betrieb einfrieren und wieder auftauen? Der Vorgang des Einfrierens entspricht dem Entzug von Energie. Lediglich bei Supraleitung, also Nahe des absoluten Temperaturnullpunktes wäre ein Flusserhalt möglich. Unter "normalen" Umständen vergisst das Flipflop alles und nimmt nach dem Auftauen eine zufällige Rotationsrichtung an. Das Flipflop hat seine Vergangenheit schlichtweg vergessen.

Unser Gehirn besteht aus Nervenzellen, Neuronen, die sich untereinander vernetzen -- das materielle "Schaltungsbild" unseres Denkapparats. Auch hier ist Rückkopplung der Schlüssel zu unserem Gedächtnis. Ohne Rückkopplung wären wir im wahrsten Sinne des Wortes zu keiner "reflektierten" Handlung fähig. Der Teil unseres Denkens, der sich nicht in der Vernetzung der Neuronen niedergeschlagen hat, "kreist" auf diesen rückgekoppelten Bahnen. Würden wir unser Gehirn einfrieren, käme es zum Stillstand des Denkens und aller Erinnerungen, die in uns ihre Kreise ziehen. Dumm gelaufen.

Also: Legen Sie lieber ein Bit ins Gefrierfach! Auch dumme Hefe löscht den Durst!

Get Lively

2007-10-06T13:25:00.000+02:00

Yesterday (Friday, Oct 5, 2007), Dan Ingalls announced the Sun Labs Lively Kernel on the squeak-dev mailing list. Squeak is an implementation of the Smalltalk programming language and Dan Ingalls is one of the lead developers of Squeak. So, you might guess what Lively is?! Something that is very close in spirit and conception to Smalltalk. You've never heard of Smalltalk? Never mind, have a look at Lively, it's fascinating and quite cool -- and completely implemented in JavaScript using SVG capabilities of a web browser.

The main goal of the Lively Kernel is to bring the same kind of simplicity, generality and flexibility to web programming that we have known in desktop programming for thirty years, but without the installation and upgrade hassles than conventional desktop applications have.

[...]

The Lively Kernel places a special emphasis on treating web applications as real applications, as opposed to the document-oriented nature of most web applications today. In general, we want to put programming into web development, as opposed to the current weaving of HTML, XML and CSS documents that is also sometimes referred to as programming.

(http://research.sun.com/projects/lively/, 2007-10-06)

If you are interested in Dan Ingalls way of reasoning, read "The Design Principles Behind Smalltalk" -- a document, which is more than 25 years old and still worth reading. Two other members of the Lively Project, Tommi Mikkonen and Antero Taivalsaari, have written another interesting paper, which might help understand, why they developed Lively: "Web Applications - Spaghetti Code for the 21st Century".

By the way, my students and I started analyzing Lively in my course "Modeling Software Architecture". I'm curious on the insights we will gain.

Ur-Taschenrechner

2007-09-28T12:11:00.000+02:00

Mögen Sie einen Blick in die Urzeit des Computerbaus werfen? Bei Spiegel-Online gibt es einen netten Beitrag dazu: "Der erste Taschenrechner wog 1,5 Kilo" (Konrad Lischka, 27. Sep. 2007). Schauen Sie sich mal die Bilder zu den alten Taschenrechnern an! Schaurig schön.

Vom Zählen und vom Sehen

2007-09-26T23:38:00.000+02:00

Mein ältester Sohn, bald sechs Jahre alt, hat die vergangenen Tage die "großen Zahlen" für sich entdeckt. Genauer gesagt, er entdeckt das Regelsystem, nach dem Folgen von Zahlen ausgesprochen werden: 3-2-0, dreihundertzwanzig; 1-4-0, einhundertvierzig. Es ist beachtlich, wie hart ein kleines Menschenkind daran üben muss -- einem Computer wäre das in Kürze beigebracht. Ein kurzes Programm würde für immer und ewig "große Zahlen" richtig in Wortfolgen übersetzen. Meinem Sohn müssen wir die Regeln wieder und wieder erklären. Es bewahrt ihn nicht vor Fehlern. Ein mühsamer Prozess, der spielerisch umgesetzt zwar Spaß macht, aber eines schön verdeutlicht: unsere Hirne sind nicht gerade für solche Regeln gemacht.

Auf der anderen Seite habe ich noch keinem meiner Kinder erklären müssen, wie die Regeln fürs Sehen funktionieren. Noch besser, ich kenne sie selber nicht. Innerhalb kürzester Zeit weisen Kinder Fähigkeiten in der Verarbeitung von Bildern auf, die wir bislang weder mit Hochleistungsrechnern noch ausgefuchsten Algorithmen nachbilden können. Die Mühelosigkeit, mit der wir uns in der Welt bewegen und mit unseren Sinnen orientieren können, ist purer Hohn für all die kläglichen Versuche, Computern menschliche Fähigkeiten angedeihen zu lassen. Geht es aber bereits um einfache Regelsysteme, stechen uns die Computer wiederum gnadenlos aus. Auf ihre Weise verstehen es Computer, uns beim Schach den Rang abzulaufen -- da findet ein spannendes Kräftemessen zwischen der Arbeitsweise von Neuronen und der von Computern statt.

Interessanterweise gibt es aber immer wieder Menschen, die ebenfalls mit solchen Regelsystem ausgezeichnet umzugehen wissen: Mathematiker oder Physiker zum Beispiel. Aber auch Musiker. Zum Teil sind es extreme Einzelbegabungen. Faszinierend daran ist, das neuronale Netze auch so etwas beherrschen können. Was ist es nur, was neuronale Netze zu solchen "formalen Leistungen" befähigt? Ich weiß es nicht.

Computer-basierte Beratung in der Medizin

2007-09-21T09:39:00.000+02:00

Die computer-basierte, medizinische Beratung von Patienten wird zunehmend auch in Deutschland als ein hilfreicher Baustein in der Vorsorge und Therapie entdeckt. Auf dem Bild sehen Sie ein solches Beratungssystem im Einsatz. Der Patient interagiert mit dem drucksensitiven Bildschirm des TabletPCs über einen speziellen Stift. Zum Einsatz kommt dieses System gerade in einer Studie, die in Praxen von Hausärzten durchgeführt wird.

Dieses Beratungssystem ist entwickelt worden im Rahmen einer Forschungskooperation der Hochschule Heilbronn und der Philipps-Universität Marburg. Dafür hat sich ein interdisziplinäres Team zusammengefunden aus Medizinern, Psychologen und Software Engineers. Sie dürfen raten, an welchem Teil ich beteiligt bin :-)

Die erste Fassung der Beratungssoftware ist übrigens im vergangenen Sommersemester 2007 an der Hochschule Heilbronn im Rahmen einer Veranstaltung entstanden, dem "Labor für Software Projekte". Mittlerweile ist die Software neu geschrieben und weiter entwickelt worden.

Bei der aktuellen Untersuchung, die die Marburger Mediziner und Psychologen derzeit mit dem Beratungssystem durchführen, geht es um eine Akzeptanzstudie. Untersucht werden chronisch erkrankte Patienten; im konkreten Fall Patienten mit diabetes mellitus (im Volksmund "Zuckerkrankheit") und/oder einer Erkrankung der Herzkranzgefäße. Da körperliche Aktivierung ein wichtiger Bestandteil der Therapie bei diesen Erkrankungen ist, versucht das Beratungssystem den Patienten eine angepasste Beratung zum Thema geben. Welche Bedeutung hat körperliche Aktivität? Wie lässt sich mehr körperliche Aktivität im Alltag einbinden? Bevor das Beratungssystem darauf eingeht, ermittelt es durch Fragen die Motivationsstufe des Patienten bzw. der Patientin (Grundlage ist das Transtheoretische Modell, TTM) und leitet dann über in eine stufenspezifische Beratung.

Wir haben das System diese Woche (Ende September 2007) auf dem 8. Kongress für Gesundheitspsychologie und dem 41. Kongress der Deutschen Gesellschaft für Allgemeinmedizin und Familienmedizin (DEGAM) vorgestellt und positives Feedback erhalten. Eine weitere Vorstellung wird es im November auf der USAB 2007 (Usability & HCI for Medicine and Health Care) geben.

Wenn Sie Interesse an einer Beteiligung, Mitarbeit oder Kooperation als Mediziner, Psychologe oder Informatiker haben, ich würde mich freuen, wenn Sie sich bei mir melden.

Für die Software-Techniker unter Ihnen: Über die software-technische Aspekte werde ich in einem späteren Blogeintrag berichten.

Blogpause

2007-07-13T00:54:00.000+02:00

Liebe Blogleser(innen), ich werde mir eine Blogpause gönnen bis Mitte September. Eine Denkpause wird es nicht sein, es gibt interessante Projekte, die ich in dieser Zeit vorantreiben möchte. In dem einen Projekt wird es gehen um formale Grundlagen zur Aspekt-Orientierung -- ein Thema, was mich schon länger beschäftigt. Neu dagegen ist eine Entdeckung, Verhältnisse in Raum und Zeit mit Hilfe einer Prozessalgebra zu beschreiben. Damit kann man z.B. User Interfaces und Maskenwechsel prototypen und formal verifizieren. Im Augenblick kommt eine pragmatische Version davon in einem medizinischen Beratungssystem zum Einsatz.

Dann liegt noch einiges andere an: ein Queue-Konzept, bei dem sich Consumer und Producer gegenseitig über die Queue synchronisieren können. Ein Anfang zu einem Tutorial zu Alloy soll entstehen. Und und und.

Natürlich werde ich bis zum Beginn der Vorlesungen im Wintersemester nicht mit allem durchkommen. Aber sicher werde ich von dem einen oder anderen Ergebnis nach der Blogpause berichten. Bis dahin wünsche ich allen eine gute Zeit.

Editing and Persistence

2007-07-02T09:49:00.001+02:00

In this post, I want to present a generalization of the ideas, which are behind HTML, CSS and JavaScript. We will end up with a broad understanding of what is meant by editing und persistence in the context of an object model.

Most of you know HTML, the HyperText Markup Language, which is at the heart of web technology. For those who don't know it: The content of a web page is described with HTML. HTML structures the content of a web page hierarchically. Furthermore, the content is annotated by so-called tags. A tag indicates the logical purpose of a piece of content. Is some content supposed to be a header, a paragraph, a highlighted word etc.? For further info see e.g. Wikipedia on HTML or any other of the hundreds of resource about HTML.

HTML is flanked by two other guys. One guy is called CSS, the other JavaScript. When you look at a HTML page in a browser, the graphics engine (the rendering engine) takes the HTML stuff and calculates a visual presentation out of it. There are some predefined rules, which let a header, for instance, appear in big, fat letters. With CSS (Cascading Style Sheets) you can define your own style information. You can do quite some fancy things with CSS in order to change the default behavior of the rendering engine. Have a look at CSS Zen Garden -- the same content is presented in astonishingly different ways, just the CSS is exchanged.

Before we come to the other guy, JavaScript, you have to know that your browser internally converts HTML into an alternative representation, an object model called DOM (Document Object Model). It's a data structure, which represents HTML in form of a tree. The fun part is that the tree has a defined interface (we call it an API, Application Programmer Interface) to inspect the tree, navigate through it, add or delete nodes or node attributes. You couldn't do this in HTML. So once HTML is consumed by the browser, HTML "disappears" and continues to live in the browser in a different form: as a DOM. The object model can be traversed at any time and the HTML form can be reconstructed. An HTML page can be transformed into DOM and vice versa.

JavaScript is a programming language all browsers understand. With JavaScript you can manipulate HTML and CSS via DOM. CSS is also accessible via DOM. This gives you quite some power to dynamically change content and its appearance. It's the miracle behind some fancy visual effects, web designers create on some web pages with JavaScript.

In addition, JavaScript can overwrite all standard reactions on user initiated events. When you click on a link with the mouse, you usually get transferred to a new location in the web and a new web page is opened. With JavaScript you can do something else and generate a new user experience.

As I said at the very beginning: What I am after in this post is to generalize the ideas, which are behind HTML, CSS and JavaScript. So, let's look at the figure above. The object model captures three aspects: form, style and syntax.

We call the logical model of a language (like HTML) its form. The form contains language conceptions and their relations. Together with a syntax definition, a notation, the logical model can be serialized as a stream of characters. It's a both way thing. The character stream can be transformed into a form and vice versa. In case of HTML, it's the HTML syntax, the textual form which is send as messages via HTTP.

To produce a projection, a visual representation of the form, the rendering engine processes the form and a style definition -- something like CSS, for example. That's the way, how something appears on the screen.

Events that are generated by e.g. the user and timers are digested by a processor, something like a JavaScript interpreter. The processor can modify the object model in any way. A modification has an immediate effect on the projection. The projection always presents the current "shape" of the form.

The upper part of our figures makes up what can be called editing, the lower part realizes persistence.

Just some years ago, the traditional form of writing code had a misconception (and it's still widely spread): To edit code one uses a more or less advanced text editor. If you call the structure of a programming language its form and its textual notation its syntax, it's somewhat strange why one wants to work on a serialization format and not on the form directly, benefiting from advanced projections and a powerfull I/O-model. That is where modern IDEs like Eclipse move to. Internally, Eclipse builds up a model of the code, which represents its form -- technically speaking, it is an Abstract Syntax Tree (AST). This give you cool features like automated refactoring, word completion etc. However, the actual syntax of, say, Java or C#, is too restricted and too simple, to be an suitable snapshot of the code's form. And that's a pitty. There are only very few new approaches, like Intentional Programming, which realized the limitations a today's code syntaxes.

To summarize, what we discussed here:

HTML is just a serialization format for the exchange of content that is otherwise represented in form of an object model called DOM. This serialization format is the prerequisite to send content around in HTTP messages. But the HTML format is nothing a browser works internally with. It's the object model instead.

If we apply the editing/persistence-model on programming languages, we have to conclude that programming languages are historically driven by a text-based serialization format, which is -- today -- not appropriate anymore.

Kann man Programmieren lernen?

2007-06-26T01:00:00.000+02:00

Kann man das Programmieren erlernen? Sicher! Aber kann es jeder erlernen?

Ich bin über einen Blog auf einen interessanten Artikel gestossen ("The camel has two humps (working title)" von Saeed Dehnadi und Richard Bornat). Darin berichten die Autoren von den vielen vergeblichen Versuchen, die es gegeben hat, das Programmieren erfolgreich zu unterrichten. Denn zwischen 30 und 60 Prozent der Studierenden an Universitäten und Hochschulen scheitern regelmäßig am ersten Programmierkurs. Bei allen Bemühungen: Die hohen Durchfallquoten scheinen unabänderlich zu sein.

Die Autoren behaupten, die Programmierbegabung mit einem Test ermitteln und damit vorhersagen zu können, ob ein Kandidat bzw. eine Kandidatin das Programmieren erfolgreich erlernen wird. Ich halte die durchgeführte Studie für methodisch kritisch, darum sind die Aussagen und Spekulationen mit großer Vorsicht zu genießen. Dennoch lassen Sie uns einmal anschauen, was Dehnadi und Bornat da untersucht haben.

Die beiden gehen davon aus, dass sich dem Programmierunerfahrenen, dem Novizen, beim Umgang mit imperativen Sprachen drei Hürden stellen -- und zwar in der angegebenen Reihenfolge:

Zuweisungen und Zuweisungsfolgen

Rekursion und Iteration

Nebenläufigkeit

In einem Test stellen Dehnadi und Bornat den Studierenden vor dem ersten Kontakt mit einer Programmiersprache einige Fragen zu Zuweisungen bzw. zu Folgen von Zuweisungen; sie testen also lediglich die erste Hürde. Die Probanden müssen via Multiple Choice erraten, welche Werte nach den Zuweisungen gültig sind.

Nach den Tests unterscheiden Dehnadi und Bornat drei Gruppen. Die Annahme ist, dass sich die Probanden ein mentales Modell von der Arbeitsweise von Zuweisungen machen. Versuchen die Probanden, sich bei der Suche nach Lösungen strikt an Regeln zu halten, seien die Ergebnisse auch noch so unsinnig oder seltsam? Oder versuchen sie, etwas sinnvolles aus jeder einzelnen Aufgabe zu holen und entsprechend zu antworten? Oder verweigern sie die Antwort, da diese Zuweisungen wenig Sinn zu machen scheinen? Eine Gruppe, die Konsistenten, beantwortet die meisten bis alle Fragen mit dem gleichen mentalen Modell; das sind die, die sich einer Maschine gleich an ein Regelwerk halten. Die Inkonsistenten sind die, die bei verschiedenen Fragen verschiedene mentale Modelle anwenden; es sind die, die versuchen, jede Zuweisungsaufgabe für sich genommen sinnhaft zu beantworten. Die Blanken verweigern die Antwort auf die meisten oder alle Fragen; sie mögen nicht rätseln, was diese ganze Kryptik für einen Sinn machen soll.

Obwohl jede der drei Gruppen eine absolut vernünftige Strategie für ihr Handeln verfolgt, die durchaus als intelligent bezeichnet werden kann, kommt lediglich das Vorgehen der Konsistenten der Arbeitsweise eines Rechners gleich. Ein Rechner befolgt Regeln der Ausführung und wendet diese stur an. Ob die Ergebnisse Sinn machen oder nicht, hinterfragt ein Rechner nicht.

Interessant ist nun, wie sich die Probanden im Laufe der Zeit entwickeln. Alle belegten einen Programmierkurs und schlossen den Kurs mit einer Prüfung ab. Dehnadi und Bornat wollen nun festgestellt haben, dass einzig die Konsistenten zu bemerkenswert guten oder mittelmäßigen Programmierern werden. Die Inkonsistenten und Blanken bleiben bemerkenswert programmierschwach. Es will fast so scheinen, als lege der frühe Test als Novize die Zukunft in Ketten: einem Inkonsistenten bzw. Blanken scheint der Eintritt in die Programmierwelt verwehrt. Die Autoren schreiben:

[...] it is extremely difficult to teach programming to the inconsistent and blank groups. It might be possible to teach them, if we concentrated on trying to persuade them to see a programming language as a system of rules ([...]).

Vor diesem Hintergrund scheint es besonders fragwürdig, so die Autoren, Java als erste Programmiersprache zu unterrichten. Java wird nicht über ein einfaches Regelwerk definiert, sondern über einen mehrere Hundert Seiten umfassenden Standard.

Mich machen diese Ergebnisse nachdenklich. Was sind die Konsequenzen daraus? Sollten manche Studierenden lieber die Finger von der Informatik lassen, weil ihre Hirne nicht so regelbasiert wie Computer tickern? Andererseits: Nicht jeder Software Engineer muss ein Programmierstar sein. Oder haben wir schlicht noch nicht das richtige Unterrichtsmodell für Programmiersprachen gefunden? Ich hoffe sehr, dass dieser Untersuchung weitere Studien folgen, die besser und erkenntnisreicher sind.

Suchen mit Strategie

2007-06-18T15:21:00.000+02:00

In den vergangenen Wochen habe ich mich viel mit XML befasst. Für die Verarbeitung eines XML-Dokuments habe ich mir ein Python-Programm geschrieben, das die XML-Darstellung direkt in einen Objektbaum abbildet -- alle weiteren Bearbeitungsschritte führe ich dann in dem Objektmodell aus. Jedes Objekt in diesem Baum hat einen Vorgänger (parent) und keinen oder mehr Nachfolger (childs). Das ist sehr ähnlich zu DOM.

Bei der Verarbeitung einer solchen Baustruktur tritt ein Problem immer wieder auf: Sie suchen Knoten (= Objekte) in dem Baum, die einem oder mehreren Kriterien genügen. Für diese Aufgabe kann man eine sehr flexible query-Funktion programmieren:


def query(criteria):
    assert callable(criteria)
    result = []
    for element in allElements():
        try:
            if criteria(element) == True:
                result.append(element)
        except: pass
    return result

Dieser query-Funktion übergibt man ein Kriterium in Form eines Lambda-Ausdrucks (das ist eine anonyme, sprich namenlose Funktion; so etwas gibt es jetzt auch in C# 3.0). Zum Beispiel:


query(lambda e: e.tag == "page")

Dieser Aufruf sucht aus dem Objektmodell alle Objekte raus, die in der XML-Darstellung das Tag "page" tragen.

Ein Nachteil dieser Suchabfrage ist, dass alle Elemente (allElements()) durchgegangen werden. Optimiert werden könnte das durch eine Suchstrategie, die nur relevante Elemente nach einem bestimmten Verfahren der Suche zum Test vorlegen würde. Hier die optimierte Version:


def query(criteria,strategy=yieldElements):
    assert callable(criteria) and callable(strategy)
    result = []
    for element in strategy():
        try:
            if criteria(element) == True:
                result.append(element)
        except: pass
    return result

Dazu zwei Strategien. Die erste Strategie (yieldElements) generiert wie gehabt alle Elemente. Die zweite Strategie (yieldInnerElements) generiert alle Elemente, die im Sinne einer XML-Darstellung "innerhalb" eines gegebenen Elements liegen. Die Strategie ist also parametrisiert.


def yieldElements():
    for klass in elementClasses:
        for element in klass.instances:
            yield element


def yieldInnerElements(element):
    def _yieldInnerElements():
        def yieldInnerNodes(node):
            for n in node.childs:
                yield n
                for child in yieldInnerNodes(n):
                    yield child
        return yieldInnerNodes(element)
    return _yieldInnerElements

Wieder ein Beispiel für eine Abfrage:


query(lambda e: e.tag == "page",yieldInnerElements(chapterOne))

Jetzt werden lediglich die Objekte mit dem Tag "page" herausgesucht, die als Kinder bzw. Kindskinder etc. innerhalb eines chapterOne-Objekts des Objektmodells zu finden sind.

Eine interessante Einsicht ist, dass jede Strategie auch als Teil eines Kriteriums in criteria verstanden werden kann. Die explizite Formulierung einer Strategie optimiert lediglich die Vorlage von Elementen zum Kriteriumstest und beschleunigt das Suchverfahren. Strukturwissen um die Organisation der Daten kann so effizient ausgenutzt werden. Die Parallelen zum Constraint Programming sind kein Zufall!

Maschinelles 3D-Sehen

2007-06-07T12:58:00.000+02:00

Bislang hat es viele Versuche gegeben, Computern (bzw. Robotern) das Sehen beizubringen -- mit mäßigem Erfolg. Basis für eine erfolgreiche Orientierung im Raum ist die Fähigkeit, die Welt dreidimensional wahrzunehmen. Wir Menschen bekommen das mit unseren zwei Augen hervorragend hin. Und deshalb hat man versucht, das Erfolgsmodell aus der Natur, das "Stereosehen", zu imitieren.

Allerdings ist man damit nicht weit gekommen. Es ist schon bei einem Bild extrem aufwendig und schwierig, aus den zahllosen Bildpunkten abzuleiten, wo Objektgrenzen entlang verlaufen. Bei zwei Bildern wird es nicht weniger einfach, zumal die zwei Bilder in Bezug gesetzt werden müssen und daraus mehr oder weniger präzise eine Information über die Raumtiefe gewonnen werden muss. Das ist so schwierig, dass man es bis heute nicht wagt, autonome Fahrersysteme am "normalen" Straßenverkehr teilnehmen zu lassen. Es gibt auch keine kleinen staubsaugenden oder rasenmähenden Roboter zu kaufen, die sich sicheren Auges zügig durch Wohnung oder Garten bewegen.

Ein Teil des Problems liegt daran, dass unser Stereosehen nur im Nahbereich sehr gut arbeitet. Unsere Augen liegen nur ein paar Zentimeter auseinander, zu wenig, um sehr genaue Entfernungsinformationen daraus berechnen zu können. Information über die Entfernung von etwas wird zu einem großen Teil von unserem Gehirn aus Erfahrungswissen über Größenverhältnisse, Bewegungsverhalten etc. abgeleitet. Das alles zusammen gibt uns die Illusion einer räumlichen Orientierungsfähigkeit, wie sie faktisch durch unseren reinen Sehapparat nicht gegeben ist.

Es ist also fraglich, ob das Stereosehen als Vorlage für maschinelles 3D-Sehen taugt. Müssen wir uns vielleicht nach gänzlich anderen Techniken umschauen? Es gibt sie, die neue Technik des 3D-Sehens, entwickelt von Prof. Dr. Schwarte aus Siegen. Mit Hilfe der PMD-Technologie (PMD steht für "Photonic Mixer Device") liefert eine PMD-Kamera zu jedem Pixel eine Tiefeninformation -- und das bei nur einem Kameraauge! Die Technik ist faszinierend. Sie wird fraglos unsere Zukunft verändern. Können Sie sich das vorstellen? Ein Blick in die Zukunft: In ein paar Jahren halten Sie Ihre Handykamera auf ein Motiv und Sie bekommen ein Raumbild der Szene! Damit ist es für eine Bildverarbeitung ganz einfach, Objektgrenzen in einer Szene zu ermitteln. Denn es wird gesehen, dass das eine Objekt vor oder hinter dem anderen Objekt liegt.

Ich bin sehr gespannt, was diese Zukunft bringen wird. Es werden neue Algorithmen für diese Technik entwickelt werden müssen. Man wird diese neue Technik zu nutzen lernen müssen. Bei aller Begeisterung, die ich dafür aufbringe, es wird sicher 10 oder 15 Jahre dauern, bis diese Technik unseren Alltag zu durchdringen beginnt.

Nehmen wir einmal an, wir sind 20 Jahre weiter und die Maschinen haben keine Probleme mehr beim 3D-Sehen. Dann gibt es immer noch viel zu tun. Was unterscheidet einen Profi-Tennisspieler von einem normalen Tennisspieler? Weder ist es die Fähigkeit zum 3D-Sehen bei der Ballerkennung, noch Reaktionsschnelligkeit. Wenn ein Roboter in der Profi-Liga mitspielen möchte, so muss er lernen zu sehen, was mit dem Ball wahrscheinlich passieren wird, bevor der Ball den Schläger des Gegners verlässt und die Flugbahn berechnet werden kann.

Ähnliches gilt im Straßenverkehr. Gute Autofahrer ahnen vorher, was passieren könnte und verhalten sich entsprechend. Auch hier ist unser Gehirn in der Einschätzung von Verkehrsituationen technischen Lösungen weit voraus. Wir werden das Problem mit Computern anders lösen müssen, analog zum 3D-Sehen: nicht das Vorbild imitieren, sondern technische Lösungen finden, die qualitativ ähnliches leisten, aber die Stärken der Technik ausnutzen.

Zahlenspielerei

2007-05-02T01:18:00.000+02:00

In meinem Blogeintrag "Hochstapelei" habe ich Ihnen gezeigt, wie sich rein mit den Mitteln der Objekt-Orientierung ein Stack realisieren lässt. Zur Konstruktion eines solchen Datentyps reicht es vollkommen aus, mit Konstruktoren, Methoden, Attributen und der Möglichkeit des Vergleichs von Objekten zu arbeiten. Keine sonstigen eingebauten Operationen, kein weiterer Datentyp (außer Bool) ist nötig.

Auf die gleiche Weise lassen sich auch die natürlichen Zahlen inklusive Null als Typ einführen. Das Geheimnis liegt wieder in der Nutzung des Konstruktors verborgen; das Beispiel ist in Python umgesetzt. Wir machen uns eine Zahlendarstellung zu nutze, die ihren Ursprung in der Mathematik hat: Ausgehend von der Zahl Null ist jede andere Zahl ein Nachfolger von Null. Eine Rangordnung wird hergestellt durch eine Nachfolgekette. Wir nennen den direkten Nachfolger von Null "Eins", den Nachfolger von Eins "Zwei" usw. Ein Nachfolger einer Zahl wird durch die Methode "inc" (inkrementiere) generiert. Der Vorgänger einer Zahl kann mit der Methode "dec" (dekrementiere) ermittelt werden. Eine Zahl heißt "Null", wenn sie keinen Vorgänger hat.


class Number(object):
    def __init__(self,predecessor=None):
        assert isinstance(predecessor,type(None)) or \
               isinstance(predecessor,type(self))
        self.predecessor = predecessor
    def is_zero(self):
        return isinstance(self.predecessor,type(None))
    def inc(self):
        return Number(self)
    def dec(self):
        assert not isinstance(self.predecessor,type(None)),\
               "Number is not zero"
        return self.predecessor

Eine wichtige Methode, die nicht fehlen sollte, überprüft die Gleichheit von zwei Zahlen. Zwei Zahlen sind dann gleich, wenn Sie die gleiche Anzahl von Vorgängern haben. Das Konzept der "Anzahl" ist jedoch nicht zugreifbar, da wir just dabei sind Zahlen zu definieren. Doch es gibt einen kleinen Kniff, der uns das Problem löst: Rekursion. Wir dekrementieren die zu vergleichenden Zahlen gemeinsam so lange, bis entweder beide Zahlen Null sind oder nur eine Zahl Null ergibt. Im ersten Fall (beide Zahlen sind Null) wissen wir, dass die Zahlen gleich sein müssen; ist nur eine Zahl Null, liegt Ungleichheit vor.

Aus praktischen Gründen überschreiben wir die Gleichheitsmethode "__eq__" von Python, um den Vergleichsoperator "==" einsetzen zu können.


    def __eq__(self,number):
        assert isinstance(number,type(self))
        if self.is_zero() and number.is_zero(): return True
        if self.is_zero() or  number.is_zero(): return False
        return self.dec().__eq__(number.dec())

Einem erfahrenen Python-Programmierer wird im ersten Code-Fragment aufgefallen sein, dass ich "self.predecessor" nicht direkt mit None vergleiche, sondern den vielleicht etwas umständlich anmutenden Umweg über "isinstance" gehe. Grund ist die "__eq__"-Methode. Ich kann keine Number mit None vergleichen, ohne den Aufruf von "__eq__" zu provozieren. Dort will ich aber nur einen Vergleich zweier Zahlen implementieren, nicht den Vergleich mit None.

Eine weitere Methode setzt den plus-Operator um. Die "__repr__"-Methode gibt eine geeignete Repräsentation eines Number-Objekts aus.


    def plus(self,number):
        assert isinstance(number,type(self))
        if number.is_zero(): return self
        return self.inc().plus(number.dec())
    def __repr__(self):
        if self.is_zero(): return "0"
        return "1+%s" % self.predecessor

Wenn Sie ein wenig Zahlenspielerei mögen, dann tippern Sie doch auf der Console zum Beispiel Folgendes ein:


>>> zero = Number()
>>> zero
0
>>> one = zero.inc()
>>> one
1+0
>>> two = one.inc()
>>> one == Number(Number())
True
>>> one == Number().inc()
True
>>> three = one.plus(two)
>>> three
1+1+1+0
>>> five = three.plus(Number().inc().inc())
>>> five
1+1+1+1+1+0
>>> five.dec()
1+1+1+1+0

Beschleicht Sie übrigens so ein komisches Gefühl? Sind das nicht komische Zahlen, die sich über die Idee der Nachfolge realisieren? Ist das nicht Kindergarten-Arithmetik, die Addition (plus) auf so eine alberne "Nimm weg, gib woanders dazu"-Art zu definieren?

Lassen Sie sich von der Einfachheit und der Speicherineffizienz nicht täuschen. Die Verwendung von z.B. Binärzahlen ist lediglich eine speichereffiziente Ablage einer Zahl. Auch die binäre Addition (0+0=0, 0+1=1, 1+0=1, 1+1=0 mit einem Übertrag von 1) kann man als optimierten Algorithmus für die binäre Zahlendarstellung verstehen.

Hochstapelei

2007-04-27T16:12:00.000+02:00

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.

Breakpoint mit Farbrausch

2007-04-13T00:16:00.000+02:00

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.

Design by Contract in Practice

2007-04-10T23:57:00.000+02:00

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.

Von Beruf Software Engineer

2007-04-05T00:32:00.000+02:00

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)

Was ist Software-Architektur?

2007-03-28T00:44:00.000+02:00

Was ist Software-Architektur? Wenn Sie nach einer Definition im Internet recherchieren, werden Sie auf eine Unmenge von Vorschlägen stoßen. Wenngleich kein vollkommener Konsens besteht, so findet die Definition von Bass et al. (Software Architecture in Practice, 2nd Ed., Addison-Wesley, 2003) offenbar den meisten Anklag. In der deutschsprachigen Literatur zum Thema wird sie auch gerne herangezogen.

The software architecture of a program or computing system is the structure or structures of the system, which comprises software elements, the externally visible properties of those elements, and the relationships among them.

Ich halte diese Definition für zu kurz gegriffen -- Sie stimmt nicht mit meinen Erfahrungen aus der Praxis überein. Architektur hat nach meinem Verständnis sehr viel mit Ökonomie zu tun.

Die Architektur ist die ökonomischste Form der Beschreibung "innerer" Anforderungen, die nicht mit der Implementierung des Systems identisch ist.

Unter den "inneren" Anforderungen verstehe ich alle Maßgaben an eine Implementierung, der sich eine Organisation unterwirft (siehe auch das Bild). Das beschränkt sich nicht einzig auf Blaupausen zur Software-Organisation und arbeitsteiligen Entwicklung (dem Design), sondern bezieht auch Qualitätsmerkmale mit ein. Ob ein Softwaresystem fehlertolerant, wartbar etc. sein soll, interessiert den Kunden herzlich wenig. In der Realität ist diese Sicht etwas zu schwarz/weiß, aber sie soll klar machen, dass es Gesichtspunkte bei der Architektur gibt, die sich eine Organisation auferlegt, z.B. um ihr Software-Produkt am Markt für ein, zwei Jahrzehnte(!) am Markt positionieren und halten zu können. Es gibt Dinge, die müssen weit über den Horizont eines Kunden entschieden und bei der Software-Entwicklung durchgesetzt werden.

Am Dienstag, 27. März 2007, habe ich meine Sicht der Dinge zusammen mit weiteren Ausführungen im Workshop "Software-Architektur und Migration" im Rahmen der Konferenz "Software Engineering 2007" zur Diskussion gestellt. Ich schloss meinen Vortrag (Titel: "Was ist Software-Architektur? Ein Abgleich mit der Praxis") mit folgendem Fazit:

Architektur ist Ausdruck der "internen" Anforderungen

Architektur unterliegt ökonomischen Antriebskräften

Komponenten-Orientierung und Sichtkonzepte greifen als Modellierungsparadigmen für Architekturen zu kurz

Modellierungsansätze müssen Domänen-Modelle integrieren

Es fehlt eine Methodik zur Architekturmodellierung

Zu meiner eigenen Überraschung erhielt ich in vielen Punkten Zustimmung; es entstand eine lebhafte Diskussion. Möglicherweise (die Diskussionen dazu waren zu kurz) habe ich den Nerv eines Problems getroffen. Auf alle Fälle gibt es zum Thema "Software-Architektur" noch einiges zu forschen und zu bewältigen. Wir sind noch lange nicht am Ende eines umfassenden Verständnisses von Software-Architektur angekommen.