Dienstag, 13. September 2016

Trendumkehr in Datenreihen

Es muss auch kurze Blogposts geben! Nach meinem jüngsten Blog-Exzess über Dominanzrelationen folgt hier ein Beitrag über ein vor längerer Zeit von Gerhard Lukert ersonnenes Verfahren, um Trendumkehrpunkte in Datenreihen zu ermitteln.

Es gibt Zahlenfolgen, die, wie die Börsenkurse an aufeinanderfolgenden Börsentagen, durch ihre Irregularität gekennzeichnet sind. Und zugleich kann man nach zugrundeliegenden Mustern, nach Trends, nach irgendwie um diese Irregularität "bereinigten" Informationen fragen. Im Fall der Börsenkurse leben Analysten davon, mit irgendwelchen Hilfslinien oder numerischen Verfahren aus den Daten Trends vorherzusagen.

Gerhard Lukerts Fragestellung war eine astrologische: ihn interessierten Tage, die besonders von einer Wende im Wachstumsverhalten geprägt sind. Solche Tage nennt er Umkehrtage. Ein Verfahren, um solche Umkehrtage, die besonders markant die Trendwende in sich tragen, könnte nach Gerhard Lukert

eine nützliche Sache sein, weil die Umkehrtage signifikant "andere" Konstellationentypen haben müssten als die Trendfolgetage; es sind die eigentlich kritischen bzw. impulsgebenden Tage.

Sein Verfahren geht so, dass er aus der ursprünglichen Zahlenfolge zwei neue Zahlenfolgen ermittelt – die Folgen der oberen und der unteren Umkehrpunkte, in denen sich jeweils der Trend umkehrt: bei den oberen Umkehrpunkten hören die Zahlen auf zu wachsen, bei den unteren Umkehrpunkten hören sie auf zu fallen.

Auf diese beiden Teilfolgen der oberen und unteren Umkehrpunkte kann dasselbe Verfahren jeweils noch einmal angewendet werden. Dabei ergeben sich vier neue Teilfolgen. Da ihn nur ein besonders reiner Ausdruck der Trendumkehr interessiert, behält er nur die oberen Umkehrpunkte der oberen und die unteren Umkehrpunkte der unteren Umkehrpunkte der vorherigen Iteration, so dass er auch in diesem Schritt mit zwei Teilfolgen verbleibt. Bei jedem Schritt dünnen sich die Folgen weiter aus, und die verbleibenden Punkte enthalten gewissermaßen besonders viel Essenz der Trendumkehr. Man verbleibt mit sehr wenigen Daten- (und damit in der Regel Zeit-)Punkten, die die Qualität dieser Umkehr besonders gut ausdrücken.

Auf der Webseite http://ruediger-plantiko.net/filter/ kann man das Verfahren ausprobieren. Die Eingabe der Zahlenreihe kann aus einer Textdatei erfolgen oder über die Zwischenablage in das Eingabefeld. Mit dem Doppelkreuz # werden Kommentare eingeleitet, die beim Einlesen ignoriert werden, sie können auch am Ende einer Zeile stehen. Auch Leerzeilen werden ignoriert. Am Beginn der Zeile muss eine Zahl stehen, die von JavaScript als Zahl erkannt werden kann. Danach kann, von Leerzeichen oder einem Semikolon getrennt, ein Bezeichner folgen, der dann auch im Graphen angezeigt wird. Enthalten die Zeilen nur eine Zahl, so wird die Zeilennummer als Bezeichner verwendet.

Mit Daten auswerten, oder den Buttons ◀ und ▶ zum Fortsetzen der Iterationen, können die Umkehrpunkte ermittelt und in einem Graphen zusammen mit der ursprünglichen Zahlenfolge angezeigt werden.

Die Anzeige des Graphen erfolgt mit c3.js, einem auf Graphen spezialisierten Zusatz zu der bekannten Bibliothek d3.js für Data Driven Documents.

Hier ein Screenshot nach Datenauswertung:

Hier noch ein paar Bemerkungen zur Implementierung (in filter.js). Beim Parsen der Eingabe werden zunächst die Kommentare und Leerzeilen entfernt. Danach wird aus jeder Datenzeile eine Zahl und ein nachfolgender Bezeichner eingelesen. Zusammen mit dem zur eindeutigen Benennung vorangestellten Index wird so ein Array von Arrays (AoA) erzeugt, wobei jedem Folgenelement ein vierelementiges Array zugeordnet ist: das erste Element erhält den Index, das zweite Element den Zahlenwert, das dritte den Bezeichner und das vierte das Wachstumsverhalten als Signum (also mit den Werten -1, 0 oder 1) im Vergleich zum Vorgänger.

  function parseInput( stream ) {
    const DATA_PATTERN = /^([-+.eE\d]+)(?:\s*|;)(.*)/;
    const COMMENT_PATTERN = /\s*#.*$/;
    var series = [];
    stream.split('\n').forEach( function(line,i) {
      try {
        line = line.replace(COMMENT_PATTERN,"");
        if (!line.match(/\S/)) return; // Leerzeilen überspringen
        var pair = parseLine(line,i);
        series.push( [ series.length, pair[0], pair[1] ] );
      } catch (e) {
        e.message += " (Zeile "+(i+1)+": '"+line+"')";
        throw e;
      }
    });
    return series.map( appendGrowth );

    function parseLine( line, i ) {
      var m = line.match(DATA_PATTERN);
      if (m === null || m.length === 0) {
        throw new Error("Zeile muss mit einer Zahl beginnen");
      }
      checkNumeric( m[1] );
      return [ 1*m[1], m[2] || '#'+(i+1) ]
    }

  }
Hier ermittelt appendGrowth das Signum der Datenänderung im Vergleich zum Vorgänger. Stimmt der Wert des Vorgängers mit dem aktuellen Wert überein, wird weiter zurückgeschaut, bis man einen echt größeren oder echt kleineren Wert gefunden hat. Die Funktionsschnittstelle entspricht dabei der Schnittstelle von Array-Iteratorfunktionen wie map, so dass dieses Signum mit dem Aufruf .map( appendGrowth ) den (vorher nur dreielementigen) Daten-Arrays hinzugefügt werden kann.
  function appendGrowth(data,i,total) {

    return data.concat( getGrowth( ) );

// Der Wert ist immer -1, 0 oder +1 
    function getGrowth( ) {
      var sign = 0;
// Zurückspulen, bis ein echtes Zu- oder Abnehmen gefunden wurde
      for (let j=i-1;j>=0&&sign===0;j--) {
        sign = Math.sign( data[1] - total[j][1] );
      }
      return sign;
    }
  }
Die zentrale Funktion getTurningPoints ermittelt aus einer Zahlenfolge series die Folge ihrer Umkehrpunkte, und zwar je nach Funktion condition die Folge der oberen oder der unteren Umkehrpunkte. Hierzu wird, wie man vom Namen erwarten könnte, die JavaScript-Funktion Array.prototype.filter verwendet. Die Elemente der entstehenden Teilmenge, die ja vierelementige Arrays sind, werden dann kopiert, das das vierte Element, das Wachstumsverhalten, für jede Reihe neu ermittelt werden muss.
  function getTurningPoints(series,condition) {

    var newSeries = 
          series
            .filter( conditionSatisfied )
            .map( copy )
            .map( appendGrowth );
    return newSeries;

// Auf Umkehrpunkt prüfen (bis zum vorletzten Datenpunkt möglich)
    function conditionSatisfied(data, i) {
      return (i < series.length - 1) &&
             condition(data[3],series[i+1][3])
    }

// Kopie der ersten drei Elemente
    function copy(data) {
      return data.slice(0,3);  
    }

  }
Aus dieser Funktion resultieren die Funktionen getUpperTurningPoints und getLowerTurningPoints, die sich nur durch die verwendete condition beim Aufruf von getTurningPoints unterscheiden:
  function getUpperTurningPoints(series) {
    return getTurningPoints( series, stopsIncreasing );
  }

  function getLowerTurningPoints(series) {
    return getTurningPoints( series, stopsDecreasing );
  }

  function stopsIncreasing(currentGrowth,nextGrowth) {
    return (currentGrowth>0) && (nextGrowth<0);
  }

  function stopsDecreasing(currentGrowth,nextGrowth) {
    return (currentGrowth<0) && (nextGrowth>0);
  }

Sonntag, 4. September 2016

Zu Dir hin hast Du uns geschaffen

Im heutigen Evangelium (Lk 14,26-27) heisst es:
So jemand zu mir kommt und hasset nicht seinen Vater, Mutter, Weib, Kind, Brüder, Schwester, auch dazu sein eigenes Leben, der kann nicht mein Jünger sein. Und wer nicht sein Kreuz trägt und mir nachfolgt, der kann nicht mein Jünger sein.
Wie schroff, ja brutal! Sich und die Seinen hassen? Das ist doch Hate Speech! Da müssen wir etwas machen!

Die moderne Einheitsübersetzung versucht den heutigen Leser zu besänftigen, indem sie das harte hasset durch gering achtet ersetzt. Ich bleibe bei hasset, denn erstens steht es im Original (griechisch μισεῖ, in der Vulgata steht da odit, die Sachlage ist eindeutig), und zweitens ist hier eine emotionale Beteiligung gemeint, die weit über ein blosses "Geringachten" hinausgeht. Wenn das anstössig ist – dann sei es eben so.

Wie ist das zu verstehen? Verstösst diese Aufforderung nicht direkt gegen das vierte Gebot Du sollst deinen Vater und deine Mutter ehren? Ganz sicher nicht! Es sagt nur, dass es einen Ruf gibt, der noch stärker sein muss als der Ruf der Welt mit ihrer horizontalen Eigengesetzlichkeit, in die wir eingebettet sind, ja die unsere Identität in dieser Welt ausmacht. Wir stehen in dem Strom von Tradition und Fortschritt, in der Kette von Ahnen und Nachfahren, in dem besonderen geschichtlichen Sein unseres Volkes und unserer Rasse, und all diesem sind wir verpflichtet - aber all dies hat kein Recht, uns von unserem transzendenten Quell wegzuziehen. Man muss Gott mehr gehorchen als den Menschen, sagte es einer von Jesu grössten Schülern zu späterer Gelegenheit. All das Horizontale, das in dieser Welt Weiterwachsende, hat natürlich seine Berechtigung, aber es stillt nicht unseren metaphysischen Durst. Das Wasser des Lebens strömt nicht aus diesen Quellen.

Wie der Hirsch nach dem Wasser der Quelle dürstet, so dürstet meine Seele nach Dir, Herr, singt, ruft verzweifelt, ja weint der Psalmist. Es ist das Verlangen nach dem Wasser, das den Durst auf ewig stillt. Wer kann dieses Sehnsuchts- und Klagelied lesen und unberührt davon bleiben?

Wie der Hirsch schreit nach frischem Wasser, so schreit meine Seele, Gott, zu dir.
Meine Seele dürstet nach Gott, nach dem lebendigen Gott. Wann werde ich dahin kommen, dass ich Gottes Angesicht schaue?
Meine Tränen sind meine Speise Tag und Nacht, weil man täglich zu mir sagt: Wo ist nun dein Gott?
Wenn ich des innewerde, so schütte ich mein Herz aus bei mir selbst; denn ich wollte gerne hingehen mit dem Haufen und mit ihnen wallen zum Hause Gottes mit Frohlocken und Danken unter dem Haufen derer, die da feiern.
Was betrübst du dich, meine Seele, und bist so unruhig in mir?
Harre auf Gott ! denn ich werde ihm noch danken, dass er meines Angesichts Hilfe und mein Gott ist.

Die Seele, die nach diesem Wasser dürstet, das den Durst auf ewig stillt, stösst Vater und Mutter, Frau und Kinder, Brüder und Schwestern unwirsch weg, wenn diese sie davon abhalten wollen.

Dies ist der "Hass", der im Wort Jesu gemeint ist. Er gilt dieser Welt, die sich vor die Seele hinpflanzt und sagt: mir allein sollst Du dienen, es gibt nichts ausser mir. Oder, wenn wir die moderne Variation dieser Sonate spielen: Dir allein sollst Du dienen - Du bist Dein eigener Herr, Du bist frei, verwirkliche Dich selbst, es ist Dein Recht! Niemand hat das Recht, Dich davon abzuhalten!

All diese Stimmen - sie mögen sanft säuselnd, dem Ego schmeichelnd, oder auch den Opferdienst fordernd daherkommen - all diese Stimmen weist die Seele schroff ab, die sich nach Gott sehnt, die Gottes Liebesangebot an die erste Stelle setzt.

Nun ist, was der Versucher sagt, nie ganz falsch – er redet immer so, dass man ihm aus seiner Rede keinen Strick drehen kann: natürlich sind wir frei – und es ist etwas Grosses um diese Freiheit, da sie uns Gott ähnlich macht – und natürlich sollen wir alle Schicksalszusammenhänge freudig bejahen, in die wir gestellt sind - wir sollen aus ganzer Kraft Vater bzw. Mutter sein, den Ehepartner und die Kinder lieben, Brüder und Schwestern lieben, unser Volk lieben – aber zuallererst zieht es die Seele zu ihrem Schöpfer, vor dem sie ganz allein steht. Ohne trügerische Sicherheit, ungeborgen und ungeschützt durch irgendwelche Zusammenhänge, in denen er sich verstecken könnte, gilt jedem einzelnen ganz ausschliesslich die Ansprache, die der lebendige Gott an ihn richtet.

Und selbstverständlich gibt es hier Grade der Kraft – Abstufungen, in denen man Jesu Aufruf ernst nimmt. Ich habe nicht diejenigen zu verurteilen (wie man es aus einem "irdischen" Pflichtverständnis tun könnte), die diesen Aufruf radikal ernstgenommen und sich völlig aus den Weltzusammenhängen herausgelöst haben - in die Einsamkeit einer Einsiedlerklause oder eines Klosters gingen, um sich ganz ungestört dem Ruf Gottes zu öffnen. Hier ist es wie mit der Bergpredigt: es gibt eine Ebene, in der sie radikal ernstgenommen werden kann, zu der sich einige wenige auch berufen fühlen: die Heiligen. Ihr Leben ist fortan nicht mehr dem Gesetz der Schwerkraft unterworfen. Ihr Verhalten folgt keinen nach irdischen Maßstäben nachvollziehbaren Regeln - sie leben noch hier, aber eigentlich schon nicht mehr hier.

Aber auch die vielen, die nicht so weit gehen können oder wollen, spüren, dass sie in dieser Existenz hier nur ein Zeichen oder Gleichnis sind; sie spüren in allem den geheimnisvollen Verweis auf eine höhere Ganzheit, die nur in das irdische Sein hineinragt.

Beda Venerabilis kommentiert das Jesuswort wie folgt:

Es gibt einen Unterschied zwischen "allem entsagen" und "alles verlassen"; denn nur wenige Vollkommene haben die Kraft, alles zu verlassen, das heisst die Sorgen dieser Welt hinter sich zu lassen. Aber es ist die Aufgabe aller Gläubigen, allem zu entsagen, das heisst die Güter dieser Welt so zu besitzen, dass sie dennoch durch sie nicht in der Welt festgehalten werden.
In einem alten indischen Weisheitstext, der Bhagavadgita, beeindruckte mich eine Stelle so, dass sie lange meine Homepage zierte:
Wer nicht der Welt verhaftet ist, frei von Selbstsucht, voller Entschlossenheit, sicher und mit ruhiger Aufrichtigkeit in der Hingabe, ohne Berauschtheit beim Erfolg, ohne sich entmutigen zu lassen beim Misserfolg — wer so handelt, wird sattva-artig genannt.
Das drückt etwas Ähnliches aus wie das Entsagen, von dem Beda spricht: es geht um ein inneres Sich-Herausziehen aus den Gesetzen dieser Welt. Ohne dabei das, was man tut, etwa nicht mehr aus ganzem Herzen und ganzer Kraft zu tun.

Die östliche Geisteswelt preist den Seelenzustand, in dem "nichts mehr anhaftet". Sie realisiert damit das, was Nietzsche später das "Frei von" nannte. Denjenigen, die die Befreiung von allem predigen – und das geht an den westlichen Liberalismus ebenso wie an diese östlichen Weisheitslehren – schleudert Zarathustra seine berühmte Frage entgegen:

Frei nennst du dich? Deinen herrschenden Gedanken will ich hören und nicht, dass du einem Joche entronnen bist.
Frei wovon? Was schiert das Zarathustra! Hell aber soll mir dein Auge künden: frei wozu?
Die Freiheit als solche, so kostbar sie ist, ist eben ein leerer Raum. Die entscheidende Frage ist, ob wir sie dazu nutzen, das in uns liegende, in uns hineinragende göttliche Gesetz zu verwirklichen.

Auf die Frage nach dem Frei wozu? hüllen sich die östlichen Weisheitslehrer in lächelndes Schweigen. Aber unsere christlichen, westlichen Weisheitslehrer geben uns genau auf diese Frage Auskunft - zum Beispiel Augustinus von Hippo (354-430):

Groß bist du, Herr, und über alles Lob erhaben. Und da will der Mensch dich preisen, dieser winzige Teil deiner Schöpfung. Du selbst regst ihn dazu an; denn du hast uns zu dir hin geschaffen, und unruhig ist unser Herz, bis es ruht in dir.

Sonntag, 31. Juli 2016

Reise eines Plantikos nach Plantikow

Schon immer hatte es mich aus reiner Neugierde gereizt, mir einmal das kleine pommersche Dorf Plantikow anzusehen, das seit 1945 Błądkowo heißt und – wie der größere Teil Pommerns – heute zu Polen gehört. Wie mein Name nahelegt, stammen meine Vorfahren aus diesem Örtchen – mein Ur-Urgroßvater Plantikow wirkte hier als Pfarrer, genau so wie eine Reihe seiner Vorväter. Heute findet man Plantikows und Plantikos überall auf der Welt. In Deutschland listet telefonbuch.de sieben Plantikos und 66 Plantikows auf, die Zahlen können wir wohl mit einem Faktor drei oder vier multiplizieren (für nicht Verzeichnete und Familienangehörige).

Was ist Plantikow für ein Ort? Wie fühlt es sich an, als Nachfahre auf einem Boden zu stehen, auf dem schon Vorfahren vor Jahrhunderten wandelten? Gibt es einen genius loci – ein Fluidum, das dem Ort anhaftet und für das man sich empfänglich machen kann? Selbst dann, wenn die Bevölkerung mittlerweile vollständig ausgetauscht wurde und somit heute den polnischen Nationalcharakter atmet?

Um meine Neugierde zu stillen, machte ich mich in diesem Sommer auf zu einer Erkundung der Gegend.

Plantikow ist mit seinen knapp 200 Einwohnern etwas größer als ein Weiler, hat aber eine lange Geschichte und wurde urkundlich schon 1269 erwähnt. Das nächstgelegene Städtchen ist Daber (Dobra) mit immerhin schon über 2000 Einwohnern. Den Namen Daber trägt auch ein winziges Bächlein, das durch Plantikow fließt. Hier kann man es fließen sehen:

Plantikow wurde früher - wie in bäuerlichen Gegenden üblich - als Gut von einer Familiendynastie verwaltet, belegt ist seine Übergabe als Rittergut durch Kaiser Karl IV. (1316-1378) an den Grafen Ulrich von Dewitz (1323−1363). Die längste Zeit seiner Geschichte entstammten Plantikows Gutsherren ebendiesem Adelsgeschlecht der Dewitz.

Im Wikipedia-Artikel zu Pommern ist nachzulesen, dass es ursprünglich von westgermanischen Rugiern und Goten besiedelt wurde, im Zuge der Völkerwanderung rückten dann ab dem Ende des 5. Jahrhunderts auch slawische Stämme nach. Dänen, Polen und das Heilige Römische Reich kämpften um die Vorherrschaft über Pommern. Nach polnischer Unterwerfung durch Herzog Bolesław III. Schiefmund (1116-1121) und einem kurzen Gastspiel unter dänischer Herrschaft ging Pommern in der Schlacht bei Bornhöved (1227) endgültig an das Deutsche Reich über, dem es dann über sieben Jahrhunderte - bis 1945 - angehörte. Die Nachkriegsgeschichte ist bekannt: die in Pommern wohnenden Deutschen wurden vertrieben und durch Polen ausgetauscht, dies geschah auch unter Druck der Sowjetunion, die den ganzen polnischen Staat nach Westen verschob, um sich selbst nach Europa hin zu vergrößern.

Stettin ist die in der ganzen westpommerschen Region dominierende Stadt, was Einwohner und Wirtschaftskraft betrifft. Die klassische Definition zieht die Oder als Grenzfluß zwischen Vor- und Hinterpommern. Die polnische Grenze verläuft jedoch westlich von Stettin, so daß heute die gesamte Stadt der Wojwodschaft Westpommern zugerechnet wird, dem historischen Hinterpommern. Wenn man vom Westen kommend (z.B. Berlin) auf der A11 nach Osten Richtung Danzig fährt, überquert man bei Stettin die Grenze; ab dort wird diese Autobahn als A6 weitergeführt (immer noch die Europastraße E28), in Gollnow (Goleniów, 20'000 Ew.) spaltet sich diese einerseits in die S3, die nordwärts bis zur Insel Wolin am riesigen Stettiner Haff führt - da ist man bei Swinemünde schon fast wieder in Deutschland (westlich der Grenze kommt man dann zur Insel Usedom und nach Heringsdorf), und andererseits in die S6, die die Europastraße E28 dann über Köslin (Koszalin) bis nach Danzig weiterführt.

In der Anreisenacht verpasste ich die Abzweigung in Gollnow und fuhr weiter bis nach Wolin, wo mich (nachdem ich bei jeder Ausfahrt vergeblich nach "Nowogard" gespäht hatte) das viele Wasser um mich herum endlich davon überzeugte, dass ich mich verfahren haben musste. So kam ich eine Stunde später als geplant in Nowogard an und mußte den Portier des schönen und preisgünstigen Hotels Willa Zbyszko aus dem Bett klingeln. Er kam im Nachthemd und sehr verschlafen, aber freundlich heraus.

Die Stadt Naugard / Nowogard liegt an einem schönen See, eben dem "Jezioro Nowogardzkie", den ich in einer vielleicht einstündigen Wanderung umrundete.

Die Stadt selbst beeindruckt mit ihrer steil zum Himmel ragenden Marienkirche im gotischen Stil (erbaut im 14. Jahrhundert).

Nun aber ging es nach Plantikow!

Es ist eine Ansammlung einiger Häuser, hauptsächlich Bauernhöfe, die an der Straße von Ostrzyca nach Dobra liegt. Die Straße macht mitten in Plantikow einen Knick. An diesem Knick liegt der Dorfkern, gerade dort, wo die Dobra unter der Straße durchgeführt wird. Man findet einen kleinen Spielplatz und ein schön gepflegtes Blumenbeet,
vor allem aber die traurig stimmende Ruine der ehemaligen Dorfkirche, die von einem Storchennest geziert wird:
Auf einer kleinen Erinnerungstafel nahe der Kirche hat ein Geschichtsfreund einige uralte Ansichtskarten von Plantikow ausgestellt.

Auf dieser kann man sehen, wie die Kirche zu besseren Zeiten einmal ausgesehen hat:

Interessant ist auch diese hier, denn sie zeigt auch einen Dorfteich, von dem jedoch heute nichts mehr übrig ist:
Den Ortsausgang Richtung Dobra ziert dann wieder ein liebevoll geschmücktes Kruzifix:
An den Bauernhöfen prangt immer stolz ein Schild mit EU-Sternenkranz und einer polnischen Inschrift, auf dem folgenden Foto kann man es gerade noch erkennen. Es muß sich um EU-Gelder handeln, die im Rahmen eines Subventionsprogramms an die polnischen Landwirte verteilt werden. Die EU-Loyalität, die man sich aufgrund dieser Zahlungen erhofft, bleibt aber zurückhaltend. Die Polen haben ein gesundes Nationalgefühl und spüren, wenn es der nationalen Souveränität an den Kragen geht. Wer kann es ihnen verübeln, daß sie zu den Subventionen dennoch nicht Nein sagen.
Mein Vater wußte von einem nahe Plantikow gelegenen See - dem Plantikow-See. Der Dorfteich aus der Ansichtskarte wird es wohl nicht gewesen sein. Eine erste Umrundung des Dorfes brachte auch keine Ergebnisse. Überall nur Felder, die gerade gemäht wurden, und Weiden.
Natürlich gab es kleinere Gewässer, die aber niemals ein See gewesen sein können – wie dieses hier:
Vom Dorfkern aus ging allerdings nach Süden ein Waldstückchen aus, das aber von keiner Seite begehbar schien. Am Abend konsultierte ich Google Earth – und mitten in diesem offenbar nicht begehbaren Wald war tatsächlich etwas, das ein See sein könnte!
So machte ich mich am nächsten Tag noch einmal auf (unter den nachvollziehbar mißtrauischen Augen einiger Dorfbewohner, denen ich mich aber weder auf Deutsch noch auf Englisch verständlich machen konnte – und hätte ich es machen können, hätten sie mich vermutlich für irre gehalten), wanderte zuerst am Ortsausgang Richtung Dobra den südwärtigen Feldweg herunter und schlug mich dann ins Dickicht. Der Wald war wirklich unerschlossen, außer Tieren wird hier lange niemand durchgegangen sein. Die Mücken waren meine Begleiter, und ich mußte an ihren Gesang in Marguerite Lobecks Sommerspiel denken, deren Aufführung ich kürzlich wieder genießen durfte:
Wir Mücken entschweben
den Grüften und leben
in Lüften,
um uns zu entzücken
im Glanze der Sonne,
im Tanze voll Wonne.
Wir Mücken sind Geister,
erkoren vom Meister
um Toren, die überall Lücken
und Schwächen entdecken, zu stechen,
zu necken!
Immer mehr Libellen und Frösche zeigten mir, daß ich auf dem richtigen Weg zum Wasser war. Es mußte doch diesen See geben! Irgendwann stieß ich auf das Dobra-Bächlein und folgte ihm nordwärts. Der Himmel zog sich zu, es ging nun in den Abend hinein. Ein paar Tröpfchen kamen vom Himmel.

Schließlich stieß ich auf die Wasserflächen!

Der Wald gab eine erste kleine Lichtung frei, über die sich ein fast zugewachsener See erstreckte:

Während ich weiterwanderte, kam auch von oben mehr Nässe - als wären meine Rufe nach dem Wasser sehr gründlich erhört worden. Und da offenbarte sich schon ein zweiter See. Er enthielt noch mehr offene Wasserfläche als der erste.

Der Regen beharrte auf seinem Recht beachtet zu werden und erhöhte nun seine Intensität. Er wuchs sich zu einem dieser vollen, kräftigen Gewitterregen aus, mit denen wir in diesem Sommer oft beglückt werden. Es dauerte nicht lange, bis die Bäume des Waldes mich nicht mehr vor ihm schützten. Ich wurde komplett durchnäßt.

Als ich das Waldstück verließ, war es schon spät geworden. Die Sonne schickte sich an unterzugehen, und Błądkowo hatte ich nicht mehr in Sicht. Eilig trat ich den Rückweg ins Dorf an und beendete meinen Tagesausflug.

Ob es einen Plantikow-See gibt, ob ich wirklich den Fragmenten eines solchen Sees begegnet bin, kann ich nicht mit Sicherheit sagen. Ein schönes, intensives Naturerlebnis war mein kleiner Waldgang allemal. Es ist immer wieder erstaunlich, wie schnell man bei ganz urtümlichen Stimmungen landet, sobald man sich auch nur ein bißchen von den ausgetretenen Wegen und den urbar gemachten, besiedelten und bewirtschafteten Gebieten entfernt.

Zur Eingangsfrage nach dem genius loci: ich habe nichts gespürt: keinen Hauch, kein Fluidum, keinen Schauer – nichts, was irgendwie einem Déjà-vu ähnlich war. Und eigentlich ist das auch klar: Die Ahnen haben mir den Boden bereitet, aber sie sind nicht mehr da. Was da ist, sind nur noch Überreste ihres Schaffens. So wie die Einwohner Plantikows nach dem Krieg flohen und die, die den Treck verpaßt hatten, vertrieben wurden, so haben auch die Ahnen die Form verlassen, in der sie gelebt und gewirkt haben. Auch ihre körperlichen Überreste, ihre Gebeine, ihr Staub oder was immer von ihnen übrig ist, sind ja verlassen: es wäre nichts an ihnen, das ein Déjà-vu-Erlebnis auslösen würde. Auf dem, was sie ihren Nachfahren weitergereicht haben, gründet meine Existenz. Das ist alles.

Donnerstag, 21. Juli 2016

Jenseits von Schere, Stein und Papier

Eine Relation "ist stärker als" modellieren

Vor kurzem stellte sich ein Lernender in der Programmierkunst die Aufgabe, ein Spiel ähnlich dem bekannten Schere, Stein, Papier! zu entwickeln: der Spieler wählt eine "Waffe", danach wählt die Maschine mittels Zufallsgenerator eine. Die Maschine prüft dann, welche Waffe "stärker" ist und gibt aus, wer gewonnen hat.

Die Menge der Waffen abzubilden, war einfach: er entschied sich für einen Array, der einfach eine Liste der verfügbaren Waffen in Form von Strings enthielt:
var weapons = ["pistol","bomb","knife"];
Wie aber sollte er nun - und das war die Frage, mit der er sich ans Forum wandte - die Funktion definieren, die ihm liefert, welche Waffe stärker ist als welche?
function isStronger(weapon1,weapon2) {
  // ???
}
Die Relation "ist stärker als", die er sich dabei als Beispiel gewählt hat, hatte er durch bomb > knife, knife > pistol, pistol > bomb definiert (wie er diese Relation begründen mag, ist ein anderes Thema: siegt die Pistole über die Bombe, weil der treffsichere Pistolero rechtzeitig den Zünder kaputtschießt? Und das Messer siegt über die Pistole, weil der Kämpfer es schneller parat hat? Die Begründungen des klassischen "Stein-Papier-Schere"-Spiels kommen mir da plausibler vor - aber darum geht es hier nicht).

Die von ihm gewählte Relation gehört zu denen, in denen das Spiel überhaupt sinnvoll ist, da es keine stärkste Waffe gibt. Jede Waffe ist unter dieser Relation stärker als eine andere und schwächer als eine andere. Gäbe es stattdessen eine stärkste Waffe, wäre das Spiel langweilig: man müßte nur diese stärkste Waffe wählen und könnte nicht mehr verlieren – allenfalls geht es unentschieden aus, wenn die Maschine (der Zufallsgenerator) dieselbe Waffe gewählt hat.

Wie also wäre die Relation mit Programmcode zu modellieren? Eine einfache Antwort wäre, die unterschiedlichen Fälle mit dem zu Recht unbeliebten switch/case zu programmieren:

function isStronger(weapon1,weapon2) {
  switch(weapon1) {
    case "bomb":
      switch(weapon2) {
        case "bomb":
          return false;
        case "knife":
          return true;
        case "pistol":
          return false;
        default:
          throw new Error('Unknown weapon "'+weapon2+'"')
      }
    case "knife":
      switch(weapon2) {
        case "bomb":
          return false;
        case "knife":
          return false;
        case "pistol":
          return true;
        default:
          throw new Error('Unknown weapon "'+weapon2+'"')
      }
    case "pistol":
      switch(weapon2) {
        case "bomb":
          return true;
        case "knife":
          return false;
        case "pistol":
          return false;
      default:
        throw new Error('Unknown weapon "'+weapon2+'"')
      }
    default:
      throw new Error('Unknown weapon "'+weapon1+'"')
  }
}
Dieser Code, obwohl unglaublich aufgebläht, ist immerhin korrekt, leistet das Gewünschte: er liefert für jedes mögliche Paar von Waffen die Angabe, welche stärker als welche ist.

("Aber ist das nicht das Wichtigste: dass der Code tut, was er soll?" - fragen Leute, die Clean Code und/oder The Pragmatic Programmer nicht gelesen haben...)

Obendrein enthält der Code auch ein Fehlerhandling durch Abfangen der Defaultzweige. Andererseits wird der Array weapons überhaupt nicht benötigt. Es ist alles ausprogrammiert. Die Gefahr von Tippfehlern, wenn weitere Waffen dazukommen, ist erheblich.

Eine übliche Refaktorisierung des switch/case-Statements besteht darin, statt Code eine Datenstruktur zu verwenden und die cases durch Zugriffe auf diese Datenstrukturen mit Index oder mit dem Dot-Operator zu ersetzen.

In diesem Fall könnte das so aussehen:

var isStronger = (function(){
   var stronger = {
     "bomb":{ 
       "bomb":false,
       "knife":true,
       "pistol":false
     }
     "knife":{ 
       "bomb":false,
       "knife":false,
       "pistol":true
     }
     "pistol":{ 
       "bomb":true,
       "knife":false,
       "pistol":false
     }
   }   
   return function(weapon1,weapon2) {
       return stronger[weapon1][weapon2]
   }
})();
Das hält immerhin die benötigte Information ("ist stärker als") vom eigentlichen Code getrennt.
Das Fehlerhandling, auf das es mir hier nicht ankommt, habe ich weggelassen - es wäre leicht nachzutragen: der Zugriff stronger[weapon1][weapon2] liefert den Wert undefined, wenn weapon2 nicht bekannt ist. Er löst die abzufangende Ausnahme TypeError aus, wenn weapon1 nicht bekannt ist (die durch den Zugriff auf das Member weapon2 des Wertes undefined entsteht).

Nun enthält auch dieser Code noch Redundanzen: es ist auch ausprogrammiert, dass eine Waffe nie stärker ist als sie selbst. Ausserdem genügt es offenbar anzugeben, wer stärker ist als wer. Denn aktuell ist jede Relation doppelt enthalten.

Eine Relation wie "ist stärker als" kann in Form einer Matrix modelliert werden, in der jede Zeile für den ersten und jede Spalte für den zweiten Kandidaten im Vergleich steht. Ist der Vergleich positiv, wird an dieser Stelle eine 1 notiert; ist "stärker als" nicht erfüllt, eine 0.
Man muss die Einsen in der Matrix durchgehen, um die Relation auszubuchstabieren. Wenn wir die Relation "ist stärker als" mit dem Symbol ≻ notieren und die "Waffen" durchnumerieren, so codiert die hier dargestellte Matrix also die Relation
  1 ≻ 2
  2 ≻ 3
  3 ≻ 1
Spiegelt man die Matrix an der Hauptdiagonalen, so müssen für alle Plätze außerhalb dieser Hauptdiagonalen Einsen mit Nullen vertauscht werden. Die Plätze auf der Diagonalen sind immer 0 (denn keine Waffe ist stärker als sie selbst). Um zu sagen, welche Waffe stärker als welche ist, sind also nur die Plätze oberhalb der Diagonalen beliebig mit Einsen oder Nullen zu besetzen. Das ist die einzige benötigte Information. Insbesondere gibt es 23 = 8 verschiedene Möglichkeiten, "ist stärker als" auf der Menge mit drei Waffen zu definieren.
Die Entfernung von Redundanz reduziert wieder die Gefahr von Tippfehlern und beschränkt die Information der stronger-Datenstruktur auf das Wesentliche:
var isStronger = (function(){
   var stronger = {
     "bomb":["knife"],
     "knife":["pistol"],
     "pistol":["bomb"]
     }
   }   
   return function(weapon1,weapon2) {
       return stronger[weapon1].indexOf(weapon2) >= 0
   }
})();
Da bei der hier gewählten Relation eine Waffe immer stärker als genau eine andere ist, hätte man für diese konkrete Relation statt eines Hashs of Arrays (HoA) auch dieses Wissen einfließen lassen und einen Hash of Strings wählen können:
var isStronger = (function(){
   var stronger = {
     "bomb":"knife",
     "knife":"pistol",
     "pistol":"bomb"
     }
   }   
   return function(weapon1,weapon2) {
       return stronger[weapon1] == weapon2
   }
})();
Nur ist diese Version leider nicht verallgemeinerbar: es ist absehbar, dass weitere Waffen dazukommen werden. Es ist dann, wie man leicht sehen kann, überhaupt nicht mehr möglich, ein "ist stärker als" zu definieren, in dem jede Waffe stärker als genau eine andere Waffe ist. Der Ansatz mit dem Hash of Arrays ist daher in Hinblick auf die Erweiterbarkeit vorzuziehen.
Wenn wir das konkrete Wissen einfließen lassen wollen, wäre es sowieso viel einfacher. Denn die von ihm gewählte Relation "ist stärker als" ist ja eine ringförmige Anordnung.

Es gewinnt jeweils der, der in diesem orientierten Kreis unmittelbar vor dem anderen liegt. Wenn wir den Array der weapons ins Spiel bringen, lässt sich diese Regel für ist stärker als mit dem Modulo-Operator % implementieren:
function isStronger(weapon1,weapon2) {
  var i1 = weapons.indexOf(weapon1);
  var i2 = weapons.indexOf(weapon2);
  return (3 + i1 - i2) % 3 == 2;
}
Hier steckt also das ganze Wissen um die konkrete Relation "ist stärker" nicht mehr in einer Datenstruktur, sondern in einer Formel. Wenn man die Relation ändert - oder auch nur erweitert, indem man eine neue Waffe hinzufügt, muss man sich eine neue Formel überlegen. Und um die Formel zu verstehen, muss man sie - zugegeben! - etwas gründlicher anschauen als im vorigen Beispiel die Datenstruktur. Andererseits erkennt man an der Verwendung des Modulo-Operators, dass eine zyklische Struktur zugrundeliegt. Bei der expliziten Modellierung mit der Datenstruktur sieht man das erst auf den zweiten Blick.

Klassifizierungsprobleme

Einfache Fragen verlangen oft danach, in einen größeren Zusammenhang gestellt zu werden. "Schere - Stein - Papier" wirft die Fragen auf:
  1. Wie ist überhaupt eine Relation "stärker als" rein formal zu definieren?
  2. Welche Relationen dieser Art gibt es, und wie lassen sie sich beschreiben?
In diesem Blogpost ist die erste Frage - nach dem Begriff dieser Relationen - bereits in natürlicher Sprache beantwortet. Formal können wir von einer Relation im strengen, mengentheoretischen Sinn sprechen, notieren wir sie wieder mit dem Zeichen ≻, die folgende Eigenschaften hat:
  1. Sie ist asymmetrisch, das heißt für zwei beliebige Elemente x, y gilt nie zugleich x≻y und y≻x.
  2. Sie ist total, das heißt zwei beliebige Elemente x, y stehen immer in Relation zueinander: eines von beiden ist "≻" als das andere.
Wir reden also über die asymmetrischen, totalen Relationen auf einer endlichen Menge. Solche Relationen heißen in der Literatur auch Dominanzrelationen. Die beiden Eigenschaften lassen sich zu einer einzigen zusammenfassen:
Für zwei beliebige Elemente x,y der Menge gilt immer genau eine der drei Beziehungen x=y, x≻y oder y≻x.
Solche Relationen werden gelegentlich auch Turnierrelationen genannt, weil jede Relation dem möglichen Ausgang eines Turniers von n Spielern entspricht, wobei jeder Teilnehmer einmal gegen jeden anderen Teilnehmer spielt.
Die zweite Frage ist ein typisches Klassifikationsproblem. Man könnte ja sagen: die Antwort ist: es gibt so viele Relationen dieser Art, wie es Besetzungen des oberen Dreiecks einer n×n-Matrix mit den Werten 0 oder 1 gibt. Da das obere Dreieck einer n×n-Matrix n(n-1)/2 Plätze hat, gibt es also 2n(n-1)/2 mögliche Dominanzrelationen auf der Menge mit n Elementen.

Alles richtig. Aber ist die Frage damit wirklich beantwortet?

Nein: wir wissen nicht, welche dieser Relationen sich nur durch Umbenennung der Elemente unterscheiden. Nehmen wir z.B. die Relation
  1 ≻ 2
  2 ≻ 3
  1 ≻ 3
Sie entspricht folgendem Graphen:
Betrachten wir nun die folgende Relation:
  3 ≻ 2
  2 ≻ 1
  3 ≻ 1
Ist es wirklich eine andere? Wenn wir uns den Graphen ansehen, würden wir sagen: es ist die gleiche, nur wurden die Elemente anders benannt - 3 heißt jetzt 1 und 1 heißt 3:
Insgesamt gibt es auf der dreielementigen Menge 23=8 Dominanzrelationen. Von diesen acht haben aber sechs den gleichen Graphen wie den gerade abgebildeten, entsprechend den 3! = 6 Möglichkeiten, die Elemente 1, 2 und 3 in einer Reihe hinzuschreiben (Permutationen).
Es bleiben zwei weitere Relationen übrig, die aber ebenfalls auseinander durch Vertauschung von Elementen hervorgehen (hierfür müssen genau zwei Elemente miteinander vertauscht werden). Es sind die Relationen, die einer kreisförmigen Anordnung entsprechen. Einerseits diese:
Und andererseits diese:
Wie man sieht, gehen diese beiden Graphen auseinander hervor, wenn man die Elemente 1 und 3 vertauscht. Sie können daher als "die gleiche Relation" betrachtet werden, denn auf die Benennung der einzelnen Elemente kommt es ja nicht wirklich an.

Das ist ein typischer Abstraktionsvorgang in der Mathematik. In diesem Fall operiert die symmetrische Gruppe Sn der Permutationen der n-elementigen Menge auf der Menge aller Dominanzrelationen dieser n-elementigen Menge, nennen wir sie Dn. Das heißt, es gibt eine Abbildung Sn×Dn⟼Dn, die jedem Paar aus einer Permutation pSn und einer Dominanzrelation ≻∈Dn eine neue Dominanzrelation ≻pDn zuordnet, definiert durch

x ≻p y :⟺ p(x) ≻ p(y) für alle Elemente x, y,

wobei die Gruppenoperation verträglich mit der Hinereinanderausführung ist, d.h. es gilt (≻p)q = ≻qp für alle Permutationen p,q und alle Dominanzrelationen .

Die ursprüngliche Menge Dn zerfällt unter der Operation dieser Gruppe in einzelne zueinander elementfremde Teilmengen, deren Elemente jeweils durch die Operation der Gruppe auseinander hervorgehen, die sogenannten Orbits der Gruppenoperation (oder auch: die Äquivalenzklassen bezüglich der Äquivalenzrelation, die durch die Gruppenoperation definiert wird).

Die Frage ist dann: beschreibe für jeden Orbit einen typischen Repräsentanten, am besten durch eine Konstruktionsbeschreibung. Dann könnte man sagen, man hat das Klassifikationsproblem gelöst, "man hat jede Dominanzrelation einmal gesehen".

Im Falle der dreielementigen Menge erzeugt die Operation der symmetrischen Gruppe offensichtlich zwei Orbits. Der eine enthält sechs Relationen, durch die die drei Elemente zu einer Kette angeordnet werden: es gibt jeweils ein größtes Element, ein mittleres und ein kleinstes Element. Der zweite Orbit ist nur zweielementig. Er entspricht der Anordnung der Elemente in einem orientierten Kreis, wobei jedes Element nur "größer" ist als sein direkter Vorgänger im Kreis. Bei der dreielementigen Menge gibt es nur zwei verschiedene Möglichkeiten (entsprechend den Orientierungen), die Elemente in einem Kreis anzuordnen. Daraus gehen die beiden Dominanzrelationen des zweiten Orbits hervor. Tatsächlich sind diese beiden Relationen äquivalent, denn eine beliebige Vertauschung zweier Elemente führt sie ineinander über.

Wie aber sieht es im allgemeinen Fall aus?

Die Ketten

Die Relationen, die ich eben Ketten genannt habe, gibt es für beliebige Grundmengen: man kann sie konstruieren, indem man jedem Element der Menge einen "score" zuweist und dann die Relation durch das "größer als" auf der Zahlenmenge definiert:
function rel(a,b) {
  return score(a) > score(b)
}
Einzige Bedingung, um eine Dominanzrelation zu erhalten, ist daß die verwendete score-Funktion injektiv sein muß: verschiedene Elemente müssen auch verschiedene Scores haben (für Elemente a,b mit gleichem Score wäre die Totalität verletzt, es würde weder a≻b noch b≻a gelten.
Durch die Score-Funktion kommen die Elemente in Form einer Kette auf dem Zahlenstrahl zu liegen, und die Reihenfolge, in der sie auf dem Zahlenstrahl liegen, bestimmt bereits die Relation. Es würde also reichen, Score-Funktionen in die Zahlenmenge {1,2,3,...,n} zu betrachten. Die Abbildung in diese Menge ist dann sogar bijektiv. Die Menge der möglichen Abbildungen entspricht der Menge der Permutationen, der symmetrischen Gruppe Sn.

Bei Ketten gibt es ein Element, das größer als alle anderen ist, dann ein zweitgrößtes Element usw. Die Dominanzrelation läßt sich symbolisch so notieren wie dieses Beispiel:
5 > 6 > 1 > 7 > 3 > 2 > 4

Die Dominanzrelation ≻ ergibt sich dann als transitive Hülle dieser Kette, indem man a≻b setzt, wenn a weiter links als b auf der Kette liegt.

Das bedeutet, mit Hilfe von Score-Funktionen landen wir nur in einer einzigen Äquivalenzklasse, einem einzigen Typ von Dominanzrelationen, dem einfachst möglichen. Die durch Score-Funktionen definierten Dominanzrelationen sind alle untereinander äquivalent.

Notation

Eine Dominanzrelation ist durch die Stellen im oberen Dreieck ihrer darstellenden Matrix definiert, die mit einer Eins besetzt sind. Das gibt eine Möglichkeit, sie in eindeutiger Form zu notieren:
{i1:j1 i2:j2 ... ik:jk}
Dabei sind i1,i2,... die Zeilennummern und j1,j2,... die Spaltennummern der Stellen, an denen in der Matrix eine 1 steht. Diese Stellen sollen nach aufsteigender Zeilennummer und in einer Zeile nach aufsteigender Spaltennummer notiert sein. Dann fungiert der so gebildete String als eindeutige Charakterisierung der Relation: haben zwei Dominanzrelationen einen zeichenweise übereinstimmenden String, so sind sie identisch.
Wenn wir nun zur Informatiker-Konvention übergehen und mit der Null statt der Eins zu zählen beginnen, so steht zum Beispiel die Notation
{0:3 0:5 1:4}
für folgende Dominanzrelation auf der sechselementigen Menge {0,1,2,3,4,5}:
Die Notation {0:3 0:5 1:4} ist also die Kurzform für die Relation
  1>0
  2≻0
  0≻3
  4≻0
  0≻5
  2≻1
  3≻1
  1≻4
  5≻1
  3≻2
  4≻2
  5≻2
  4≻3
  5≻3
  5≻4
Man kann diese Notation so verstehen, dass man genau die "überraschenden" dieser fünfzehn Relationspaare notiert - genau diejenigen, die nicht der normalen "Grösser-als"-Relation unter den natürlichen Zahlen entsprechen.

Differenzrelationen

Das Stein-Papier-Schere-Beispiel suggeriert ein Konstruktionsverfahren für gewisse totale asymmetrische Relationen beliebiger Ordnung, die ich Differenzrelationen nennen möchte.
Wie oben beschrieben, kann man die Stein-Papier-Schere-Relation auf die Subtraktion der Indices reduzieren, die Funktion lässt sich wie folgt hinschreiben:
function isStronger(i,j) {
  return (3 + i - j) % 3 == 2;
}
Die Relation auf der dreielementigen Menge {0,1,2} wird also auf die Subtraktion wie folgt zurückgeführt
i ≻ j :⇔ i - j ∊ { -1,2 }
Das lässt sich verallgemeinern: Auf der n-elementigen Menge {0,1,...n-1} kann man Relationen der Art
i ≻ j :⇔ i - j ∊ S
definieren, wobei die Menge S eine Teilmenge der Menge aller möglichen Differenzen D := { -(n-1),-(n-2),...,-1,0,1,...n-1} ist mit folgenden Eigenschaften:
  • Es gilt S∩-S=∅ (insbesondere muss also 0∉S sein), sonst wäre die Relation nicht asymmetrisch,
  • und es gilt S∪-S∪{0} = D, sonst wäre die Relation nicht total.
Jede derartige Menge S enthält also genau n-1 Elemente und ist von der Form
S = { ±1, ±2, ..., ±(n-1) },
wobei die Vorzeichen frei wählbar sind. Die 2n-1 möglichen Wahlen der Vorzeichen ergeben also ebensoviele verschiedene (aber nicht notwendig inäquivalente) Relationen, die ich mit Δ("vorzeichenfolge") notiere. Z.B. steht
Δ(-+-++)
für die Relation
i ≻ j :⇔ i - j ∊ {-1,2,-3,4,5}
auf der sechselementigen Menge {0,1,2,3,4,5}.

Relationen kombinieren

Man kann Relationen immer aus Relationen niedriger Ordnung konstruieren wie folgt:
  1. Man zerlegt die Grundmenge in k einzelne Teilmengen
  2. Auf jeder dieser k Teilmengen wählt man eine Relation Ri, i=1,...,k
  3. Weiter wählt man eine Relation R auf der Menge mit k Elementen.
  4. Auf der Gesamtmenge definiert man nun, dass x in Relation zu y steht, falls
    • sie beide in der i-ten Teilmenge liegen und sie dort in der Relation Ri stehen,
    • oder sie in verschiedenen Teilmengen i und j liegen, und i und j in der Relation R stehen
Jede der k Teilmengen wird also aus Sicht von R als "ein Element" aufgefasst. Aber innerhalb der einzelnen Teilmengen gelten die Relationen Ri.
Kombinierte Relationen dieser Art notiere ich in der Form
C( R1(i11,i12,...i1n1) R2(...) ... | R(k) )
Dabei stehen R1, ... Rk, R für die Relationen in der oben beschriebenen Notation. Hinter jeder der Einzelrelationen Ri wird die (angeordnete) Folge der Ziffern angeführt, auf denen sie operiert.
So steht z.B. die Notation
C({0:4 0:5 1:5}(0,1,3,4,5) {}(2)|{0:1}(2))
für diese Relation:
Wie man sieht, lassen sich die Ziffern {0,1,3,4,5} zu einer Gruppe zusammenfassen, die kollektiv zum verbleibenden Element 2 in der Relation ≻ steht.
Die Objekte eines Klassifikationsproblems, die sich auf schon bekannte Objekte zurückführen lassen - wie die kombinierten Relationen - sind weniger interessant als die übrigbleibenden, nicht zusammengesetzten, die "einfachen" oder "irreduziblen" Objekte.

Eine Invariante: die Kardinalität

Kennzahlen, die sich bei einem Klassifikationsproblem unter der Gruppenoperation nicht verändern, nennt man Invarianten. Für Relationen kann man eine "Kardinalität" definieren:
Die Kardinalität (0:i0 1:i1... (n-1):in-1) notiert die Anzahlen der Elemente, die in Relation zu keinem, zu einem, zu zwei usw. Elementen stehen.
Zum Beispiel hat die obige kombinierte Relation die Kardinalität
(0:1 3:5),
was bedeutet: ein Element (nämlich die 2) ist nicht grösser als irgendein anderes, alle übrigen Elemente sind grösser als genau drei andere Elemente.
Für diese Anzahlen spielt es offensichtlich keine Rolle, wie die einzelnen Elemente benannt sind oder ob man sie umbenennt.

Das kann man ausnutzen, um schnell zu ermitteln, dass zwei Relationen nicht äquivalent sind: wenn sie verschiedene Kardinalitäten haben, können sie nicht äquivalent sein.

Gilt auch umgekehrt, dass zwei Relationen mit gleicher Kardinalität zueinander äquivalent sind? Für die obige Kardinalität ist das so: es gibt 144 Relationen der Kardinalität (0:1 3:5), und sie sind alle äquivalent zu der gezeigten.

Die Kardinalität bestimmt eine Relation bis auf Äquivalenz aber nur auf Mengen mit bis zu vier Elementen. Schon bei fünfelementigen Mengen gilt das nicht mehr: so haben zum Beispiel die Relationen Δ(+++-) und Δ(+---) zwar dieselbe Kardinalität, nämlich (1:2 2:1 3:2), sind aber nicht zueinander äquivalent.
Wären diese beiden Relationen äquivalent, müsste es eine Permutation geben, die die beiden Graphen ineinander überführt. Dabei müsste die 2 in die 2 abgebildet werden, denn sie ist jeweils das eindeutig bestimmte Element, das genau über zwei andere Elemente dominiert. Die 2 aber bildet rechts (in Δ(+---)) einen Dreierzyklus mit 4 und 3:
2≻4
4≻3
3≻2
Aufgrund der Äquivalenz müssten 4 und 3 zwei Elementen im linken Graphen (dem von Δ(+++-)) entsprechen, die ebenfalls mit der 2 einen Dreierzyklus bilden. Dort gibt es aber keinen Dreierzyklus, der die 2 enthält. Also sind die beiden Relationen inäquivalent, obwohl sie dieselbe Kardinalität haben.

Die Zykelzahl

Invarianten findet man in diesem Problem, indem man Eigenschaften des Graphen zu beschreiben versucht, die nicht von der konkreten Benennung der Elemente abhängen.

Neben der Kardinalität ist beispielsweise auch die Zykelzahl eine Invariante: man kann die Anzahl wirklich verschiedener Dreierzyklen (wie "Papier,Stein,Schere") zählen, die Zahl der Viererzyklen usw. "Wirklich verschieden" bedeutet dabei: bis auf zyklische Vertauschung der zur Beschreibung des Zyklus verwendeten Elemente. "Papier,Stein,Schere" bezeichnet denselben Zyklus wie "Stein,Schere,Papier" oder "Schere,Papier,Stein" – in einem Zyklus ist es ja egal, bei welchem Punkt ich mit der Aufzählung seiner Elemente beginne.

Auch die so gewonnene Zykelzahl ist eine Invariante. Es zeigt sich, dass die Invariante zwar häufig auch verschiedene Äquivalenzklassen gleicher Kardinalität noch auseinanderhalten kann. Bis zu N=5 ist jede Äquivalenzklasse durch Kardinalität und Zykelzahl eindeutig beschrieben. Ab N=6 reicht aber auch die Zykelzahl nicht mehr aus. So haben beispielsweise die Relationen {0:2 0:5} und {0:2 0:3 0:5} dieselbe Kardinalität (1:2 2:1 3:1 4:2) und dieselbe Zykelzahl (3:4 4:4 5:3 6:1), also vier Dreier-, vier Vierer-, drei Fünfer- und einen Sechserzyklus, sind aber nicht zueinander äquivalent.

Ergebnisse

Wie sieht nun die Klassifikation der totalen asymmetrischen Relationen aus? Je mehr Elemente die Grundmenge hat, desto unübersichtlicher wird die Lage natürlich.
Auf der Menge mit N=3 Elementen gibt es, wie schon diskutiert, 6 = 3! zueinander äquivalente "Ketten", also Relationen, die sich von einer Stärkefunktion ableiten lassen. Dazu kommen zwei zueinander äquivalente Relationen vom "Stein-Papier-Schere"-Typ, die sich als Differenzrelation Δ(+-) (oder Δ(-+)) konstruieren lassen. Diese haben die Eigenschaften, dass alle Elemente immer grösser als genau ein anderes Element sind:
Die Kardinalität definiert hier noch eindeutig die Äquivalenzklasse. Das ist auch für N=4 noch der Fall. Dort gibt es bereits vier Äquivalenzklassen, neben den 24 = 4! Ketten gibt es eine Klasse mit 24 Relationen, die auch die Differenzrelation Δ(--+) enthält, sowie zwei weitere Klassen mit je acht Elementen, die sich als zusammengesetzte Relationen darstellen lassen:
Auch für N=5 Elemente können wir noch alle zwölf Äquivalenzklassen von Relationen durch eines der beschriebenen Konstruktionsverfahren repräsentieren - als Kette, als Differenzrelation, oder als zusammengesetzte Relation aus Relationen niederer Ordnung. Hier tritt erstmals der Fall auf, dass die Kardinalität nicht mehr eindeutig die Äquivalenzklasse definiert:
Für N=6 gibt es bereits 56 Äquivalenzklassen. Hier treten erstmals Relationen auf, die sich nicht durch eines der beschriebenen Konstruktionsverfahren herstellen lassen, zum Beispiel die bereits oben behandelte Relation {0:3 0:5 1:4}, oder die Relation {0:2 0:5 1:3}, die in ihrer Komplexität schon ein bisschen an den kabbalistischen Baum der Sephiroth denken lässt. Vielleicht lässt sie sich ja durch ein anderes Produktionsverfahren darstellen?

Wer die Listen dieser Relationen auch für N=6 oder N=7 (Vorsicht, ca. 100 Sekunden Rechenzeit für N=7, es müssen ca. 40 Millionen Äquivalenzprüfungen durchgeführt werden) studieren will, für den habe ich einen Relationsrechner in JavaScript implementiert und hier online gestellt:

http://ruediger-plantiko.net/relations/
Die Implementierung repräsentiert Relationen mit Hilfe von Bitfeldern der Länge N*(N-1)/2.

Die Folge

1,2,4,12,56,456,6880,191536,9733056,...
der Anzahl der Äquivalenzklassen von Dominanzrelationen definiert die OEIS-Zahlenfolge A000568. Unter diesem Link gibt es weitere Informationen und Literaturhinweise.

Nachtrag am 31.7.2016 - die ganze Chose in C++

Meine JavaScript-Implementierung zur Erforschung der Dominanzrelationen auf http://ruediger-plantiko.net/relations/ läuft bis zu N=6 befriedigend schnell; danach explodieren die Laufzeiten relativ rasch. Mit N=7 kommt man noch in ca. einer Minute durch. N=8 habe ich nicht mehr ausprobiert. Liegt es an der Scriptsprache JavaScript, die für solche Algorithmen eher ungeeignet ist? Die Frage liess mir keine Ruhe, und so reimplementierte ich das ganze in C++ - hier der Code auf ideone.com:
http://ideone.com/KBihCA
Das Ergebnis stellte klar: auch mit C++ liess sich die Laufzeit nur ungefähr verdreifachen. Vielleicht ist, wenn man alles optimiert in C hinschreibt, auch ein Faktor 10 noch denkbar. Aber das rettet uns nicht. Auch das C++-Programm ist chancenlos für die rund 35 Billionen Relationen (genauer: 245 = 35'184'372'088'832), die für N=10 gegenseitig auf Äuivalenz zu prüfen wären und schließlich 9'733'056 Äquivalenzklassen ergeben werden.

Eine Laufzeitanalyse mit gprof zeigt das erwartbare Ergebnis, dass weit über 95% der Laufzeit im Test auf Äuivalenz liegen - auf diese Prüfung kommt es natürlich an. Meine Optimierung ging schon dahin, statt sämtliche N! Permutationen auszuprobieren, um eine zu finden, die die Relationen ineinander überführt,

  • zuerst die Kardinalitäten der beiden Relationen zu berechnen (da eine der beiden Relationen aus dem Pool der Repräsentanten bereits ermittelter Äuivalenzklassen stammt, muss sie für diese nicht immer neu berechnet werden);
  • sind diese ungleich, so sind die Relationen inäquivalent;
  • sind sie gleich, so muss die Permutation die Elemente mit jeweils gleicher Kardinalität ineinander überführen;
  • ich versuche daher sukzessive die einzelnen Elemente mit Kardinalität 1, 2, usw. durch Permutation so ineinander zu überführen, dass auf den bislang bereits untersuchten Elementen beide Relationen miteinander übereinstimmen. Sobald dies für irgendeine Kardinalität nicht mehr funktioniert, sind die Relationen inäquivalent.
  • erst wenn sie all diese Prüfungen bestanden haben, sind sie äquivalent.

Aber ich habe natürlich den direkten brute force Zugang gewählt. Wenn es nur um die Konstruktion dieser Äuivalenzklassen mit Angabe je eines Repräsentanten geht, ist es vermutlich nicht nötig, sämtliche möglichen Relationen durchzugehen.

Samstag, 2. Juli 2016

Muss Freiheit vor Demokratie Angst haben?

In einer Diskussion auf Twitter wurde mir folgender Einwurf von Friedrich August von Hayek als Mem zugesandt:

Da dieses Argument weit verbreitet ist und ich mich darin als der "dogmatische Demokrat" angesprochen fühle, schaue ich es mir gerne einmal genauer an.

Das Argument hat im Kern drei Mitspieler:

  1. Kostbare Werte, nämlich das nicht ausgesprochene Gegenstück zu der am Schluss des Arguments angeführten "willkürlichen Gewalt": warum nämlich ist die "willkürliche Gewalt" nicht gut? Weil sie etwas der Willkür Enthobenes bedroht, etwas, das durch Mehrheitsbeschluß nicht außer Kraft gesetzt werden soll. Dieses Etwas nenne ich der Einfachheit halber die "kostbaren Werte".

    Wir gehen bei von Hayek nicht fehl, bei diesen "kostbaren Werten" an gewisse universelle Rechte wie Leben, Eigentum und Freiheit zu denken, die der Staat im Interesse der Bürger immer und grundsätzlich zu schützen habe.

  2. Der Staat, der über die Einhaltung der kostbaren Werte wachen muss, im Dienste des Volkes.

  3. Das Volk, das seine Staatsbediensteten als Delegierte seines Willens ernennt, um gemeinschaftliche Aufgaben, die das ganze Volk betreffen, zu regeln - insbesondere um über die kostbaren Werte zu wachen.
Das Argument lautet nun:
  • Demokratie bedeutet: die Mehrheit des Volkes entscheidet unbedingt.
  • Dann kann das Volk auch die Abschaffung der kostbaren Werte entscheiden, insbesondere des Prinzips der Demokratie selbst.
  • Damit gerät die Demokratie mit sich selbst in Widerspruch.

    Also muss der Staat die kostbaren Werte ggf. auch gegen den Volkswillen durchsetzen.

Das Ideal der Demokratie ist demnach in sich nicht konsequent, da es zumindest potentiell seine eigene Selbstaufhebung enthalten kann: die Wähler könnten mehrheitlich beschließen, die Demokratie abzuschaffen. Also, schließt Hayek, darf es nicht rein, nicht "dogmatisch" gelebt werden, sondern muß ergänzt werden.

Und zwar wie?

Das folgt implizit: wenn die Demokratie alleine nicht genügt, muß sie durch nicht-demokratische Herrschaft ergänzt werden. Der Staat muß demnach die Möglichkeit haben, gegen den Willen des Volkes zu handeln, wenn dieser Volkswille nach Einschätzung der Staatsbediensteten den kostbaren Werten widerspricht.

Dieses Risiko besteht in jeder Herrschaftsform

Grundsätzlich ist den Prämissen des Arguments zuzustimmen. Selbstverständlich kann der Inhaber der Macht sich gegen das Prinzip entscheiden, aufgrund dessen er an der Macht ist. Aber das gilt nicht nur für die Demokratie, sondern ebenso für jede andere Herrschaftsform. Auch der Monarch oder Tyrann kann zurücktreten und sein gesamtes Herrschaftssystem zugunsten eines anderen preisgeben. Eine Räterepublik kann sich für ihre Selbstabschaffung zugunsten einer parlamentarischen Demokratie entscheiden, und umgekehrt. Dagegen gibt es keine Garantie.

Jede Herrschaftsform steht grundsätzlich unter dem Vorbehalt ihrer potentiellen Selbstabschaffung. Das ist kein Wesensmerkmal speziell der Demokratie, sondern ein allgemeines Merkmal menschlicher Organisation. Wir sind gar nicht in der Lage, ein Herrschaftssystem mit Ewigkeitsgarantie aufzustellen.

Wenn wir diesen grundsätzlichen Einwand akzeptieren, verbleiben wir nur noch mit der Frage: wie lässt sich die menschliche Organisation am besten gestalten, so dass dass, was den Menschen kostbar ist, am wenigsten gefährdet ist? Auf diese Frage gibt das Argument aber keine Antwort. Es suggeriert nur unausgesprochen, eine Mischung aus demokratischen und nicht-demokratischen Herrschaftselementen würde die kostbaren Werte besser absichern.

Darüber aber lässt sich trefflich streiten, denn alles hängt von der Qualität dieser nicht-demokratischen Herrschaftselemente ab, deren Legitimation immer durch das Juvenalische quis custodiet custodes – wer überwacht die Bewacher? – in Frage gestellt ist. Teilhaber an der Macht, die nicht dem Volkswillen verpflichtet sind, stellen in meinen Augen ein noch viel größeres Risiko für die kostbaren Werte dar als demokratisch legitimierte Staatsbedienstete.

Damit könnte ich diesen Blogpost beenden, denn es ist alles gesagt, was sich rein logisch zu diesem Argument sagen lässt: Die Prämissen stimmen, die Schlussfolgerung nicht: eine Herrschaftsform kann man auch dann unterstützen, wenn sie unter dem Vorbehalt steht, sich potentiell selbst abschaffen zu können - vor allem, weil dies ebenso für jede andere Herrschaftsform gilt.

Das Argument ist aber vor allem deshalb interessant, weil es unterschwellig bestimmte Bilder über das Volk, den Staat und die kostbaren Werte transportiert, die es aufzuschlüsseln lohnt.

Daher endet dieser Blog hier noch nicht. Stattdessen will ich diese unterschwelligen Bilder noch sichtbar machen.

Das Volk: ein Pöbelhaufen, vor dem der Liberale sich fürchten muss?

Das Argument stellt statt des - nur allzu berechtigten - Misstrauens gegen die Machtinhaber (die Wächter, die die kostbaren Werte durchsetzen sollen, aber als Inhaber von Macht der Kontrolle bedürfen) das Misstrauen gegen das Volk in den Vordergrund, wechselt also die Perspektive: statt vom Volk aus kritisch auf das von ihm erschaffene und in Dienst gesetzte Organ "Staat" zu schauen, wird vom Staat aus mißtrauisch auf das Volk geschaut.

Damit dieser Perspektivwechsel beim Leser ankommt, muss das Volk als eine amorphe, beliebigen Launen und Moden gegenüber anfällige Masse gezeichnet werden, vor dem man sich als ordentlicher Liberaler, der sein Leben mit Grundsätzen lebt, zu fürchten habe: alle diese Grundsätze würden durch den nächsten Volksentscheid wieder zur Disposition gestellt. Daher müsse man diese Grundsätze mit institutionell abgesicherter Macht gegen das Volk durchsetzen.

Ein von Hayek denkt natürlich immer auch an die Wirtschaft: Unternehmen brauchen Planungssicherheit. Das Volk kann ihnen da einen Strich durch die Rechnung machen. Nur kann dies ein Monarch eben genausogut, wie wir schon festgestellt haben. Und die Laune eines einzelnen Monarchen kann sich noch viel verheerender auswirken als die über die Gesellschaft ausgemittelten Launen aller ihrer Mitglieder. Dasselbe gilt für alle nicht demokratisch legitimierten Machthaber, auch wenn sie voll auf Hayekscher Linie die von ihm erkannten kostbaren Werte durchzusetzen versprechen.

Die Herrschaft von Menschen, die keiner demokratischer Kontrolle unterstehen, ist immer ein viel grösseres Einfallstor für die menschliche Willkür als die Volksherrschaft selbst.

Hat ein Demokrat keine eigenen Prinzipien?

Aber wenn Du nur für die amorphe Masse "Volk" sprichst, hast Du doch keine eigenen Prinzipien! Wenn das Volk heute so und morgen so entscheidet und Du diese Herrschaftsform gutheißt, mußt Du eigentlich ein Nihilist sein, denn Du selbst hast ja dann nichts, wofür Du stehst!

Auch dieser Vorwurf, der unterschwellig mittransportiert wird, ist falsch. Selbstverständlich hat der Demokrat eigene Überzeugungen, für die er kämpft und wirbt. Das können auch Ansichten sein, die nicht von der Mehrheit geteilt werden. Der Demokrat sieht nur keine andere legitime Möglichkeit dafür, seine Ansichten allgemein durchzusetzen, als die, eine Mehrheit für sie zu gewinnen.

Umgekehrt bejubelt der Demokrat, nur weil er Demokrat ist, nicht jeden Entscheid des Volkes. Die Mehrheit hat selbstverständlich nicht immer recht. Wenn die Mehrheit entscheidet, daß 2 + 2 gleich 5 ist, ist das noch lange nicht wahr. Aber: die Gefahr, daß der Große Bruder über seine Medien verlautbaren lässt, daß 2+2=5 sei, ist in seinen Augen eine viel größere! Im Vergleich zu allen anderen Herrschaftsformen ist die Volksherrschaft der beste Weg, um das für die Gesellschaft Richtige zu ermitteln. Dies gilt zumindest so lange, wie ein offener, freier Diskurs zwischen allen in der Gesellschaft kursierenden Ansichten möglich ist.

Und an dieser Stelle ist die Demokratie mit den Freiheitsrechten grundsätzlich verwoben. Um auf demokratischem Wege das jeweils Richtige ermitteln zu können, muss Meinungsfreiheit herrschen. Die Freiheit muß sich also nicht von der Demokratie bedroht fühlen - im Gegenteil, sie ist ein wichtiger Bestandteil gelebter Demokratie.

Wird Demokratie durch Manipulierbarkeit der Menschen in Frage gestellt?

Der offene, auch der polemisch zugespitzte, mit harten Bandagen geführte Diskurs, um die eigene Position zu verdeutlichen, ist das Lebenselixier der Demokratie. Fehlt dieser oder wird er - wenigstens in den Hauptstrommedien - erschwert oder vereinseitigt, kann Demokratie nicht richtig funktionieren. Die demokratische Urteilsbildung wird erheblich erschwert. Der Staat kann sich auf einen falschen Kurs begeben, und es kommt keine Gegenkraft zustande, um den Kurs zu korrigieren.

Man lebt dann gewissermaßen in der Lüge, lebt ein falsches Leben. Ich glaube aber nicht, dass die Menschen beliebig, dauerhaft und unbegrenzt manipulierbar sind. Irgendwann wachen sie auf aus der Lüge, reiben sich die Augen, rufen "Der Kaiser ist ja nackt!" - und stellen wieder wahrhaftigere Verhältnisse her.

Wer Menschen für beliebig manipulierbar hält, denkt zu schlecht über sie, hält sie für reine Opfer, mit denen man machen kann, was man will. (Und wer ist eigentlich dieser man? Ist dieser man aus anderem Holz geschnitzt?) Ein fragwürdiges Menschenbild.

Es ist ein Erbe linken Denkens, den Menschen für beliebig formbar zu halten. Das ist falsch. Der Mensch ist nicht beliebig formbar, sondern hat eine Substanz, die sich im wesentlichen gleich bleibt. Vergeßt das Zuchtprojekt des "Neuen Menschen!" Es wird ihn nicht geben. Findet euch lieber mit dem Menschen ab, wie er nun einmal ist.

Zu seiner Ausstattung gehören aber nicht nur Aggression, Machtwille, Neid, Rachsucht, Eifersucht und Krieg. Gott sei Dank (im wahrsten Sinn des Wortes) ist ihm auch ein Erkenntnisorgan für das Wahre (sein Verstand) und das Gute (sein Gewissen) eingebaut. Auch dies bleibt, und darauf wird er sich immer wieder zurückbesinnen, bei allen Abirrungen. Es ist ein eingebauter Kompass. Die Kompassnadel kann gestört werden, aber nicht dauerhaft. Wo er gezwungen wird, gegen seine Natur zu leben - und gegen das, was ihm seine innere Stimme als das Wahre und das Gute zu erkennen gibt - wird das Wahre und Gute irgendwann wieder hervorbrechen und die Normalität wiederhergestellt.

Das gilt für einzelne wie für Völker. Sie können Ausflüge in den Wahn unternehmen, aber ihr eigenes Gespür für das Wahre und Gute wird sich letztlich durchsetzen. Da bin ich optimistisch.

Ein Wagnis bleibt es natürlich - aber das gilt, wie gesagt, nicht nur für eine demokratische, sondern für eine beliebig verfasste Gesellschaft, für Gesellschaft schlechthin. In der Demokratie sind nur die Chancen für eine Kurskorrektur am besten.

Freitag, 26. Februar 2016

Die Swiss Ephemeris im Google Portable Native Client (PNaCl)

Rechenintensive Programme in einer öffentlichen Web-Anwendung anzubietet, bringt logischerweise eine erhöhte CPU-Last auf dem Server mit sich, die von der Zahl der Benutzer abhängt, die die Anwendung gerade nutzen. Das bringt auch eine Verlangsamung für alle anderen Anfragen, die der Server beantworten muss.

Es geht also beispielsweise in der Astrologie nicht um astrologische Standard-Webauftritte, in denen ein oder zwei Horoskopdaten berechnet werden, um dem Benutzer sein Geburtshoroskop und seine laufenden Transite zu präsentieren, sondern um Hochlastanwendungen mit tausenden von Planetenberechnungen. Mir fallen auf Anhieb zwei Arten astrologischer Anwendungen ein, die als Webanwendung eine zeitweise erhöhte Rechenlast auf dem Server bringen können:

  • Statistische Signifikanztests, bei denen man nach der Monte-Carlo-Methode sehr viele Pseudo-Stichproben mit zufälligen Geburtszeiten und -orten erzeugt, die man in Hinsicht auf eine bestimmte Kennzahl gegen die reale Stichprobe antreten lässt, um einen Schätzwert für die Irrtumswahrscheinlichkeit zu ermitteln. Mit diesem Ziel hatte ich 2014 das Projekt astrotest begonnen.
  • Orakelmaschinen, die versuchen, aus einer gegebenen Sammlung von Horoskopen in regelmässigen Zeitabständen die astrologische Wetterlage zu ermitteln und Trends für einzelne Personen, Nationen, Wirtschaftszweige usw. zu ermitteln. Auch dies wird sehr rechenintensiv, vor allem wenn die ganze von der klassischen Astrologie beschriebene Serie von Hilfshoroskopen zu Rate gezogen wird (Solarhoroskop, Lunarhoroskop, Transite, wiederkehrende Konstellationen, Sonnenaufgangshoroskop, Augenblickshoroskop, sowie Relokationen von Horoskopen auf eine grosse Menge von Erdorten).

In solchen Fällen stellt sich die Frage nach Alternativen zur Webanwendung. Man könnte auf die klassische Desktopanwendung zurückgreifen. Dann wälzt man zwar richtig die Rechenlast vom Server auf den Rechner des Anwenders, wo sie hingehört, aber man handelt sich wieder die klassischen Probleme der Desktopanwendungen ein: Die Installation ist oft kein einfacher Vorgang; es gibt Abhängigkeiten von der Systemumgebung; das ausgelieferte Binary muss in der (möglichst frei wählbaren) Zielarchitektur des Rechnermodells ausführbar sein, das sich der Anwender ausgesucht hat. Eine Java Runtime würde das Problem der Plattformabhängigkeit lösen, aber in der Wartung bleibt das Problem der Softwareverteilung und der verschiedenen Versionen des installierten Programms auf verschiedenen Rechnermodellen bestehen.

Eine schöne Alternative stellt Googles Portable Native Client (PNaCl) dar, der in den Kern des Chrome-Browsers integriert ist (keine Erweiterung! Keine spezielle Installation nötig!) Ähnlich einem Applet (aber ohne UI) ist ein PNaCl-Modul ein Stück Binärcode, das mit der Umgebung der einbettenden Webseite kommunizieren kann. Der Binärcode ist portabel und wird unmittelbar nach dem Laden in Maschinencode und (erlaubte) Betriebssystemaufrufe der Zielarchitektur übertragen, was in der Ausführung laut Google einen Überhang von etwa fünf Prozent im Vergleich zu rein nativem Code bedeutet. Wie beim Applet, ist sein Binärcode also plattformübergreifend.

Ob ein solches Konzept Erfolg hat, hängt davon ab, ob es eine gute Toolunterstützung gibt. Da C/C++ immer noch in den obersten Rängen der Verbreitung von Programmiersprachen rangiert, hat Google sich dafür entschieden, eine Build-Toolkette zu bauen, die sehr nahe an der von C/C++ Compilern orientiert ist. Insbesondere sind C und C++ die beiden bislang unterstützten Sprachen für den Quellcode.

Auch die nützlichen und verbreiteten C-Bibliotheken wie <pthread.h> für die POSIX-Mehrfädigkeit und <stdio.h> für die I/O-Funktionen werden unterstützt. Letztere arbeitet sehr gut mit verschiedenen Filesystem-Konzepten auf dem Browser zusammen. So kann man ein HTML5-Filesystem auf dem Browser "mounten", um danach mit den Standardfunktionen wie fopen(), fread(), fwrite() usw. auf bestehende Dateien zuzugreifen oder neue zu erstellen.

Bei der Entwicklung der Swiss Ephemeris wurden die Abhängigkeiten zu anderen Bibliotheken bewusst schmal gehalten, es wird nur eine Auswahl von Standardbibliotheken vorausgesetzt, insbesondere natürlich auch das Standard-I/O. Es war daher zu erwarten, dass man sie mit relativ wenig Aufwand dem PNaCl-Build-Prozess unterziehen kann - und so war es auch, wie sich herausstellte.

Wärend andere, um neue Technologien zu erforschen, "Hallo Welt"-Anwendungen schreiben, schreibe ich "Hallo SwissEph"-Anwendungen: Ich habe eine Test-Anwendung erstellt, die im Web in einem Chrome-Browser der Version 47 oder höher lauffähig ist und einen Aufruf der Funktion swe_calc_ut mit variablen, in der Webseite angebbaren Parametern durchführt. Dabei werden einige Ephemeridenfiles (sepl_18.se1, semo_18.se1, seas_18.se1) beim Starten der Applikation in das lokale HTML5-Filesystem des Browsers eingelesen.

Man kann sich diese kleine Machbarkeitsstudie live auf meinem Rechner ansehen. Wer Interesse an den Details hat, liest meine Notizen auf dem Weg dahin.

Den Test hat PNaCl bestanden. Ich überlege, das Projekt astrotest vollständig auf diese Technologie umzustellen, nicht zuletzt weil die aktuell verwendete UI-Technik von astrotest - ein Internet Explorer als Benutzeroberfläche, der via Active X Dateien liest und ausführt - ein aussterbendes Modell ist. Wer die doch recht spezialisierten Berechnungen, die astrotest anbietet, ausführen möchte, ist sicher gerne bereit, einen gängigen Browser in der neuesten Version zu installieren und darin einen Link aufzurufen.

Sonntag, 17. Mai 2015

Römische Exerzitien - oder noch einmal: Daten und Code

Ich hatte hier schon früher einmal über Daten und Code reflektiert: Die Trennung zwischen Code und Daten ist demnach nicht so klar, wie es zunächst den Anschein hat - Daten können selbst wieder steuernde Logik enthalten, die dem dazu passenden Code als einer Ausführungsmaschine vorgelegt werden. Die so ausgeführten Daten sind dann selbst wieder Code - auf einer höheren Ebene, gewissermassen Meta-Code. Die Customizingdaten eines SAP-Systems sind ein Beispiel für Daten als Meta-Code. Ebenso aber auch eine CSS-Datei mit Gestaltungsanweisungen, oder die Anweisungen eines makefiles. Man spricht bei diesem auf ein konkretes Steuerungsproblem zugeschnittenem, nicht für universelle Programmieraufgaben verwendbarem Meta-Code auch von domänenspezifischen Sprachen.

Ein solcher Ansatz spaltet eine Lösung in einen "höheren", eher inhaltlichen Teil, und ein sich gleich bleibendes Ausführungsmodell, das für viele ähnliche Aufgaben wiederverwendet werden kann. Diese Trennung von Schichten MetaCode/Code ermöglicht oft eine besonders klare Lösung des Problems.

Nehmen wir zur Veranschaulichung das Taschenrechnermodell. Man kann sich leicht ein Datenformat für alle mit einem Taschenrechner lösbare Aufgaben überlegen, etwa als ein tiefer JSON-Array. So kann z.B. die Rechnung (2+3)*(5+6) in Baumform

[ "*", ["+", 2, 3], ["+", 5, 6]]
notiert werden. Das erste Arrayelement enthält den Code der Operation, die nachfolgenden Elemente sind Argumente der Operation, die aber selbst auch wieder Rechenergebnisse sein können. So ergibt sich die Baumstruktur.

Ein solches Datenformat als semantisches Modell kann beispielsweise als Schnittstelle der GUI-Applikation eines Rechners verwendet werden, oder auch das Resultat eines Parsers, der Ausdrücke in einer Formelsprache analysieren kann.

Für die Ausführung von Rechnungen solcher Art müssen zunächst einmal die erlaubten Rechenoperationen definiert werden:

var Operations = {
  "+":function() { return (
        Array.prototype.slice.call( arguments )
             .reduce( function( result, next) { return result + next }, 0)
      )},
  "*":function() { return (
        Array.prototype.slice.call( arguments )
             .reduce( function( result, next) { return result * next }, 1)
      )},
  usw.
}
Zu erklären, wie die Datenstruktur abgearbeitet wird, ist dann die Aufgabe des eigentlichen Ausführungsmodells:
function execute(data) {

  if (!isOperation(data)) return data;  // identity

  var args = data.slice(1).map( execute );
  return Operations[data[0]].apply(null,args);

    function isOperation(data) {
      return data instanceof Array &&
             data.length >= 2 &&
             Operations.hasOwnProperty( data[0] )
      }
  }
Wie man sieht, wird die Baumstruktur rekursiv abgearbeitet (Aufruf von execute im map der Operationsargumente), und alle Datenobjekte, die nicht als Operation erkannt werden, d.h. nicht ein Array sind oder nicht ein bekanntes Operationssymbol an erster Stelle haben, werden als direkter Wert behandelt, also identisch zurückgegeben.

Die Ausführungsmaschine liefert, wenn ihr die obige Rechnung vorgelegt wird,

execute( [ "*", ["+", 2, 3], ["+", 5, 6]] )
wie erwartet den Wert 55.

Dieser fruchtbare Ansatz, Daten als steuernden Metacode zu verwenden und von seiner Ausführung zu trenen, kann im kleinen auch bei der Implementierung von Funktionen nützlich sein. Das fiel mir vor kurzem bei der bekannten und immer wieder beliebten Programmieraufgabe auf, Zahlen in das römische Zahlenformat umzurechnen.

Das römische "biquinäre" Zahlensystem kennt besondere Symbole für die Zehnerpotenzen und für deren Fünffache:

I: 1                 V: 5
X: 10                L: 50
C: 100               D: 500
M: 1000              ↁ: 5000
ↂ: 10000
Um eine gegeben Zahl als römische Zahl darzustellen, wird sie in so gross wie möglich zu wählende biquinäre Summanden zerlegt, die der Grösse nach absteigend notiert werden. Dazu kommt eine Subtraktionsregel: Um der besseren Lesbarkeit willen notierte man die Vier lieber als IV statt als IIII, ebenso die Neun als IX statt als VIIII. Wenn also in einer Zahl ein kleineres Zahlsymbol vor einem grösseren steht, so gilt es als von diesem abzuziehen.

Diese Regeln enthalten Logik. Man könnte diese Logik mit allerlei switch/case oder if/else Konstrukten implementieren. Man kann die Logik aber auch in Datenform notieren und nur noch eine kleine Ausführungseinheit dazuschreiben, die die Daten (den Meta-Code) abarbeitet, aber völlig frei von Fallunterscheidungen ist.

Dazu helfen einige Beobachtungen. Die Zahlen von 0 bis 9 übersetzen sich ja in

0-> ""     1-> "I"     2->"II"     3->"III"     4->"IV"
5-> "V"    6-> "VI"    7->"VII"    8->"VIII"    9->"IX"
Die Zehner übersetzen sich sinngemäss gleich:
 0-> ""     10-> "X"     20->"XX"     30->"XXX"     40->"XL"
50-> "L"    60-> "VI"    70->"VII"    80->"VIII"    90->"IX"
Was heisst hier "sinngemäss gleich"? Statt I, V und X treten hier die Symbole X,L und C in genau derselben Bedeutung auf. Das Schema für die Anordnung der Zeichen bleibt das gleiche.

Und so geht es weiter mit den Hundertern und Tausendern.

Folgendes ist festzustellen:

  • Die Übersetzung einer Dezimalzahl kann Stelle für Stelle erfolgen, das Ergebnis ist die Verkettung der Übersetzungen der einzelnen Stellen,
  • die Übersetzungen der einzelnen Stellen sind voneinander unabhängig
  • die Übersetzungen folgen für jede Stelle dem gleichen Schema, wobei nur ein jeweils anderer Zeichenvorrat verwendet wird: die Einer und Fünfer der betrachteten Stelle und die Einer der nächsthöheren Stelle.

Das führt zur folgenden Implementierung der Funktion toRoman in JavaScript - siehe auch das jsfiddle:

var toRoman = (function(){ 
    
  var S=[ [],  [0],   [0,0],   [0,0,0],   [0,1], 
          [1], [1,0], [1,0,0], [1,0,0,0], [0,2] ],     
      F="IVXLCDMↁↂ" 
  
  return function(number) {
      var s=number+"",
          l=s.length
      return s.split('').map(function(digit,i) {
        var level = 2*(l-i-1)
        return S[digit].map( function(j) {
          return F.charAt(level+j)  
          }).join('')
       }).join('')
      }
  
  })()
Hier enthält das Datum S die Schablonen der möglichen Ziffernfolgen, wobei 0, 1 und 2 für die Einer, Fünfer und Einer der nächsthöheren Stelle steht.

Die Ausführung ist in JavaScript noch etwas länglich, da zwischen Arrays und Strings umgerechnet werden muss; von der Idee her ist sie aber nur ein doppelter Lookup: Der erste Lookup ermittelt die Schablone S[digit], deren Plätze dann in einem zweiten Lookup mit den jeweils passenden Elementen des römischen Zahlzeichenvorrats F.charAt(level+j) besetzt werden.

In einer pur funktionalen Sprache wie Haskell, in der obendrein Strings konsequent als Arrays von Zeichen behandelt werden, kann ich die Einfachheit dieser Implementierungsidee noch reiner hervortreten lassen. Der komplette Algorithmus lautet hier (hinterlegt bei ideone):

toRoman n = 
  let 
    digitPatterns = [ [],    [0],   [0,0],   [0,0,0], [0,1],
                     [1],  [1,0], [1,0,0], [1,0,0,0], [0,2]]
    symbols = "IVXLCDMↁↂ"
    r( n, s ) | n < 10   = map (\x -> symbols !! (x+2*s) ) (digitPatterns !! n)  
              | n >= 10  = r(div n 10, s+1) ++ r(mod n 10, s)

  in r(n,0)