Samstag, September 30, 2006

Semantics, Behavior and Structure

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

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

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

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

add(number,number) -> number

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

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

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

add(1,2) => 3

add(2,5) => 7

etc.

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

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

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

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

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

addd(number,number,number) -> boolean

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

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

addd(1,2,3) => true

addd(1,2,4) => false

addd(1,2,5) => false

addd(2,3,5) => true

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

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

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

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

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

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

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

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

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

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

Another hypothesis is "pair"

pair(number) -> number, number

such that

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

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

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

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

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

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

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

Donnerstag, September 21, 2006

Damals ...

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

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

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

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

Donnerstag, September 14, 2006

Strongtalk

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

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

Dienstag, September 12, 2006

Abstraktion und Vergröberung

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

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

method float squareRoot1(float: number)

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

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

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

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

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

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

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

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

Montag, September 11, 2006

Nachgeschoben: Defizite im Software Engineering

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

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

Mittwoch, September 06, 2006

Hart: IronPython

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

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

Montag, September 04, 2006

Reverse Ajax

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

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

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

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