The Future of Programming: An Interview with Paul Graham

In einem Interview mit ACM» erzählt Paul Graham», der sich unter anderem für einige Lisp-Publikationen, den Yahoo! Store und die einfache bayesische Klassifikation von Spam verantworlich zeichnet, etwas über die Zukunft der Programmiersprachen der nächsten Generation. Die beiden ersten - und wohl interessantesten - Fragen und deren Antworten stehen bereits hier.

Where do you see programming as a discipline in five, ten, or twenty years?

I think in the future programmers will increasingly use dynamic languages. You already see this now: everyone seems to be migrating to Ruby, which is more or less Lisp minus macros. And Perl 6, from n what I've heard, seems to be even more Lisplike. It's even going to have continuations.

Another trend I expect to see a lot of is Web-based applications. Microsoft managed to keep a lid on these for a surprisingly long time, by controlling the browser and making sure it couldn't do much. But now the genie is out of the bottle, and it's not going back in.

I don't think even now Microsoft realizes the danger they're in. They're worrying about Google. And they should. But they should worry even more about thousands of twenty year old hackers writing Ajax applications. Desktop software is going to become increasingly irrelevant.

What has your experience developing a new programming language, Arc, been like?

Interrupted. I haven't spent much time on it lately. Part of the problem is that I decided on an overambitious way of doing it. I'm going back to McCarthy's original axiomatic approach. The defining feature of Lisp, in his 1960 paper, was that it could be written in itself. The language spec wasn't a bunch of words. It was code.

Of course as soon as his grad students got hold of this theoretical construct and turned it into an actual programming language, that plan came to a halt. It had to, with the hardware available then. But with the much faster hardware we have now, you could have working code as the entire language spec.

I hope to get back to work on Arc soon. One of the reasons Y Combinator operates in 3-month cycles is that it leaves me some time to work on other stuff. (The other is that it's actually the right way to do seed investing.)

via connotea.org»

Xerox als Brutstätte der Innovation

Ein Artikel» von Audibleblog verraet etwas über die Geschichte und Innovationskraft von Xerox – einem Unternehmen, das hauptächlich für Kopierer bekannt ist, sich unter anderem aber auch für Erfindungen wie den Laserdrucker, die Computermaus oder aber die graphische Benuzeroberfläche verantwortlich zeichnet. Der Bericht gibt einen schönen Einblick in eine Welt, die wirtschaftliche Interessen und innovative wissenschaftliche Arbeit gut zu vereinbaren scheint.

Ich sage nur mount everest. :)

[mp3]

Java um eine Scriptsprache erweitern

Alles wird gut! Java scheint sich in Version 6 endlich recht modular und allgemein der Öffentlichkeit zu öffnen und Erweiterungsmöglichkeiten um eine Scriptsprache anzubieten. So zumindest der vielversprechende Artikel mit dem Titel Build your own scripting language for Java - An introduction to JSR 22»

In gerade diesem Artikel heißt vollmundig: The upcoming Java Standard Edition 6.0 release will include an implementation of Java Specification Request 223, Scripting for the Java Platform. This JSR is about programming languages and their integration with Java. This article demonstrates the power and potential of JSR 223 through the implementation of a simple Boolean language. Throughout the example, you will see how to program to the Scripting API (javax.script.*), how to package and deploy a language implementation in accordance with the script engine discovery mechanism, and how to make your script engine compilable as well as invocable the JSR 223 way.

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)