Unfug auf der Kommandozeile

David G. Wiseman» hat auf seiner Seite eine Liste lustiger Kommandozeilenkommandos» hinterlassen. Mein Favorit ist hierbei

% %blow
%blow: No such job.

Ahem.

Von Text zu Text

So ergab es sich am heutigen Tage, dass nach einiger Zeit der Probierens, es (ja was denn eigentlich?) mir nun endgültig gelang, ein mehr oder minder komplexes Dokument in in ein mehr oder minder anderes komplexes Dokument in HTML zu konvertieren. Schier unendlich hohe Hürden mussten gemeistert werden, ehe das Dokument so stand, wie es nun steht.

Doch immer langsam mitte Pferde. Eigentlich dachten wir (Clemens» und ich), dass es doch eine tolle Sache wäre, wenn man die Dokumentation für ein Softwareprodukt» doch gerne nur einmal schreibt, gerade so, dass man sie auch ausdrucken kann, und dass man dann eine Version für die Veröffentlichung im Internet automatisch generieren lässt. Soweit so gut. Recht schnell war dann auch schließlich das -Dokument fertig gestellt. Also *zack* wacker zu einem frickelig zusammengehackten Stück Software in Perl gegriffen (auch bekannt unter dem vielversprechenden Namen latex2html»). Irgendwie wollte das jedoch überhaupt nicht hinhauen. Nach einer kleinen Suche, tauchte dann noch ein kleines anderes Stück Software mit Namen tex2page» auf. In Scheme geschrieben, schnell installiert und es macht genau das, was man von ihm verlangt.

Danke für diese Eingebung. Ich werde niemals nie nimmer wieder auf frickelige Perl-Software ausweichen und stets dem λ-kalkülisierten Scheme treu bleiben. In tiefer Verbeugung und mit ewiger Dankbarkeit dem Entwickler von tex2page».

Wer die Ergebnisse einmal vergleichen möchte, findet unten die beiden Links, die jeweils einmal auf das ursprüngliche PDF, das aus dem -Dokument erzeugt wurde, sowie die automatisch generierte HTML-Version davon verweisen.

• PDF»
• HTML»

Funktionen und Mengen

Da habe ich mir doch mal wieder ein paar Gedanken zu den guten alten Konzepten der Mengen gemacht und bin zu der Überzeugung gekommen, dass Mengen nicht nur durch ihre Aufzählung allein genügend charakterisiert sind. Vielmehr sollte es doch auch eine implizite Möglichkeit geben, Mengen zu beschreiben. Dies passiert eben ganz einfach durch die Verwendung von Funktionen. So lässt sich etwa die Menge {1, 2, 3} mit den Element 1, 2 und 3 ja auch durch eine Prädikatsfunktion wie folgt beschreiben.

         / tt  falls x∈{1, 2, 3}
  f x = |
         \ ff  sonst

Zunächst scheint es, als hätten wir die Aufzählung nur einfach wegabstrahiert. Jedoch kann die Aussage x∈{1, 2, 3} ebenso in eine äquivalente Form x=1 ∨ x=2 &or x=3 gebracht werden.

Schauen wir nun, was bei Negation dieser impliziten Charakterisierung passiert. Welche Menge beschreibt etwa die Funktion g x = ¬(f x)? Schauen wir einmal, welche Elemente alle darin enthalten sind.

g 1 = ¬(f 1) = ¬tt = ff
g f = ¬(f f) = ¬ff = tt
g g = ¬(f g) = ¬ff = tt

Interessanterweise enthält g also nicht nur alle natürlichen Zahlen außer der 1, 2 oder 3, sondern enthält auch alle Funktionen, insbesondere also auch f und sich selbst. Wir haben also mit g eine Menge beschrieben, die sich selbst enthält - und sich insbesondere echt enthält, also eine echte Teilmenge von sich selbst ist. Ein Widerspruch?

Sollte die Verwirrung noch nicht ausreichend sein, versuchen wir nun einmal eine Menge zu konstruieren, die sich selbst beschreibt - die also nicht nur eine (echte) Teilmenge von sich selbst ist, sondern sich selbst ist. Wir benötigen also eine Funktion, die, wenn auf sich selbst angewendet, tt als Ergebnis liefert, und ansonsten eben ff. Versuchen wir es also mit der folgenden Definition.

       / tt  falls x = h
h x = |
       \ ff  sonst

Die Funktion scheint soweit zu funktionieren, erzeugt jedoch das neue Problem, etwas über die Vergleichbarkeit zweier Funktionen aussagen zu müssen. Im strengen Sinne sind zwei Funktionen genau dann gleich, wenn sie gleiche Urbild- und Bildmengen besitzen. Es spielt also keine Rolle, in welcher Art und Weise die Mengen zueinander erzeugt werden. Lediglich die Beschreibung des Verhältnisses der beiden Mengen ist entscheidend. Nicht jedoch die Berechnungsvorschrift. So sind inbesondere die folgenden Funktionen im Sinne dieses Verständnisses alle gleich:

m1 x = x + x
m2 x = 2 * x
m3 x = (x + x + x + x) / 4

Verträgt sich dies denn auch mit unserer Definition von h? Ich würde behaupten ja. Denn wenngleich ich eine scheinbar andere Funktion als Argument von h auf h anwenden würde, liefert h bei den entsprechenden Eingaben, das intendierte Verhalten. Insbesondere folgt damit aber auch, dass h bei syntaktisch unterschiedlichen Eingaben jeweils tt liefert, die Menge jedoch trotzdem nur eine Element (eben h) enthält.

Fazit: Wir haben es also geschafft, uns von einer expliziten Mengendarstellung hin zu einer impliziten Darstellung zu bewegen und können nun etwas beschreiben, dessen Beschreibung sich selbst enthält. Ob das nur gut geht?!

Diplomarbeit angemeldet

Nach mittlerweile <censored> Semestern, durfte ich nun endlich zur Tat schreiten und meine Diplomarbeit anmelden. Der ruhmlose Titel lautet "Pläne und Spiele – eine Anwendung für spielbasiertes Model Checking". Was tatsächlich dahinter steckt, wird in spätestens sechs Monaten in jeder gut sortierten Bereichsbibliothek für Informatik in Dortmund zu lesen sein. Um es noch präziser jedem, der es nicht wissen will, vor die Stirn zu schmettern: Meine Abgabetermin wurde auf den 10.8.2006 festgesetzt. Das birgt nun natürlich den unschätzbaren Vorteil, für alles und jeden immer die geniale Ausrede parat zu haben, im Moment so wenig Zeit zu haben, weil man ja seine Diplomarbeit (die man unter uns Diplomanden auch mal ganz pfiffig mit 'DA' abkürzt) schreibt.

Also, auf geht's. Ich hab jetzt nämlich keine Zeit.

Das Halteproblem

Das Halteproblem, beschreibt die Tatsache, dass es kein Programm geben kann, das für ein anderes Programm entscheiden kann, ob dieses hält oder nicht. Endlosschleifen lassen sich für den allgemeinen Fall also nicht durch einen einfachen (oder auch komplizierten) Algorithmus ausfindig machen. Dass noch nicht einmal Namen, die man für Aufrufe verfolgen könnte, notwendig für eine Endlosschleife sind, zeigt das folgende Beispiel.

    (λ () . (λ x. (x x)) (λ x. (x x)))

Einen anschaulichen Beweis für dieses Problem habe ich heute bei Structure & Interpretation of Computer Programs wiedergefunden, den ich kurz vorführen möchte.

Angenommen, es gäbe eine Funktion safe(f, a), die für eine Funktion f und ein Argument a, herausfindet, ob f(a) definiert ist oder nicht - ob ein die Funktion f berechnendes Programm also irgendwann zu einem Ergebnis kommt, oder ewig lange in einer Endlosschleife verharrt und damit kein Resultat liefert. Formal beschreiben wir die Funktion safe wie folgt.

              / tt    falls f(a)≠⊥
safe(f, a) = |
              \ ff    sonst

Die Annahme einer solchen Funktion führt jedoch zu einem Widerspruch, wenn wir folgende Funktion betrachten.

        / ⊥    falls safe(d, d)
d(x) = |
        \ 3    sonst

Doch wozu wertet nun d(d) aus? Dies hängt von safe und insbesondere von safe(d, d) ab. Wir schauen uns die beiden Fälle einfach mal an.

safe(d, d)=true
Dann gilt d(d)=⊥. safe würde jedoch nur true liefern, wenn d(d)≠⊥ gilt. Als kann nicht gelten safe(d, d)=true.

safe(d, d)=false
Dann jedoch gilt d(d)=3. safe kann jedoch nur false liefern, wenn gilt d(d)=⊥. Es kann also auch nicht gelten safe(d, d)=false.

In beiden Fällen haben wir einen Widerspruch produziert und können daher nur annehmen, dass eine gewünschte Funktion safe mit besagten Eigenschaften nicht existieren kann. Schade.

Y f = f(Y f)

Heute mal etwas Theorie zum Thema λ-Kalkül. Hierbei handelt es sich um eine von Alonzo Church etablierte Theorie zur Ausführung von Funktionen. Hierbei nehmen wir Funktionen als anonyme Funktionen λ an und können die Identität (also die Funktion, die alle Argumente auf sich selbst abbildet) wie folgt darstellen:

    λx.x

Die anonyme Funktion λ bildet ihr einziges Argument x auf sich selbst ab. Wir trennen in diesem Falle die Argumente (also x) von ihrer Anwendung durch einen kleinen '.' ab.

Wenn wir eine Funktion nun auf ein Argument anwenden, schreiben wir es einfach rechts daneben und erhalten im obigen Sinne der Definition der Identität folgende Gleichung:

    (λx.x) 1 = 1

Diese erhalten wird, indem wir die Argumente für die an den λ-Operator gebundenen Variablen einsetzen; die Funktion also auf 1 anwenden.

Nun können Argumente aber nicht nur einfach elementare Werte sein, sondern selbst wiederum Funktionen. Wir könnten also die Identität auch auf sich selbst anwenden und erhielten

    (λx.x)(λx.x) = (λx.x)

Die Identität verändert sich selbst also nicht. Ebenso sehen wir, dass Ergebnisse von Funktionen ebenfalls wiederum Funktionen sein können.

Kommen wir nun zu einer etwas interessanteren Funktion

    Y = (λf.(λx. f(x x))(λx. f(x x)))

und nennen diese Y.

Was passiert nun, wenn wir Y auf f anwenden?

(*) Y f = (λx. f(x x))(λx. f(x x))

Y f ist also eine Funktion, die auf eine Funktion angewendet wird. Wollen wir diese Anwendung noch verfolgen und den rechten Teil der obigen Gleichung etwas vereinfachen, so erhalten wir

    Y f = f((λx. f(x x)) (λx. f(x x)))

nachdem wir (λx. f(x x)) für x in f(x x) eingesetzt haben.

Nun erkennen wir aber, dass wir f auf der rechten Seite der Gleichung gerade auf (*), also auf Y f, anwenden und somit zu der interessanten Gleichung

    Y f = f(Y f)

kommen. Y liefert uns also für eine gegebene Funktion f deren Fixpunkt.

Probieren wir diese Funktion nun einmal aus und versuchen den Fixpunkt der Eins-Funktion (λx.1) zu bestimmen

    Y (λx.1) =
    (λf.(λx. f(x x))(λx. f(x x)))(λx.1) =
    (λx. (λx.1)(x x))(λx. (λx.1)(x x)) =
    (λx. 1)(λx. 1) =
    1

Juhu, es hat geklappt. Der Fixpunkt der Eins-Funktion ist demnach 1.

Wer Spaß daran gefunden hat, möge einmal versuchen, den Fixpunkt unserer oben beschriebenen Identiät auf diese Weise zu berrechnen. Er wird sicherlich erstaunt ob des bestimmten Fixpunktes sein. :)

Das wollte ich eigentlich nur mal gesagt haben. :)

Structure and Interpretation of Computer Programs

Lange ist es her seit meine letzte Nachricht an die Menschheit in dieses öffentliche Forum meiner Seite verkündet wurde. Nun bin ich aber wieder zurück und wünsche in guter höflicher Manier allen meinen Lesern - und ich weiß, dass es wenige sind - ein Frohes Neues Jahr.
Um diesen Eintrag noch weiter begründen zu können, möchte ich auf eine meiner tollsten Entdeckungen in der Informatiklandschaft hinweisen: Scheme. Hierbei handelt es sich um eine Programmiersprache (genauer: einen Lisp-Dialekt), der mich in seiner Eleganz und Mächtigkeit, Probleme und deren Lösung zu beschreiben, schlichtweg umgehauen hat.
Neben dem Buch Struktur und Interpretation von Compterprogrammen», das unabhängig von der verwendeten Sprache ein grandioses Standardwerk der Infoamtikausbildung am MIT» bildet, haben mich die Autoren selbst in einer sehr professionell gestalteten Vorlesung» auf Grundlage dieses Buches aus den 80er Jahren überzeugt. Neben Videos dieser Veranstaltung, ist auch eine Textversion des o.g. Buches auf dieser Seite zu finden, die sich "leider" zunehmender Beliebtheit zu erfreuen scheint und daher nicht immer so gut erreichbar ist, wie man es sich wünscht.
In diesem Sinne:

(define null
  (λ (f)
    (λ (x) x)))

(define 1+ n
  (λ (f)
    (λ (x) (f ((n f) x)))))
(Alonzo Church)

Umfangreiche Unterlagungen zu einer Model-Checking-Vorlesung

Die RWTH-Aachen bietet reichhaltige Informationen» – wozu Videos, Uebungsblaetter und Skripten gehoeren – zu einer Model-Checking-Vorlesung aus dem Wintersemester 2003/2004. Wirklich hinschauenswert.

Gute Ausreden eines Programmierers.

Programmer Excuses

In Software

From C. Enrique Ortiz' Weblog: Developer's Top 10 replies when code doesn't work.

10. 'That's weird...'
9. 'It's never done that before.'
8. 'It worked yesterday.'
7. 'You must have the wrong version.'
6. 'It works, but it hasn't been tested.'
5. 'Somebody must have changed my code.'
4. 'Did you check for a virus?'
3. 'Where were you when the program blew up?'
2. 'Why do you want to do it that way?'

and finally ...

1. 'I thought I fixed that.'

optische Täuschung

Eine wirklich interessante Illusion kann man auf dem obigen Bild erstaunen. Eigentlich sind nur pinke Punkte zu sehen. Konzentriert man sich jedoch auf das Kreuz in der Mitte, so sieht man auf einmal einen grünen Punkt wandern. Schließlich verschwinden die pinken Punkte sogar gänzlich und nur ein grüner Punkt wandert noch umher.

Quelle: patmedia.net