Direkt zum Hauptbereich

Posts

Es werden Posts vom 2009 angezeigt.

Die Denkspuren auf Twitter

Einige meiner Leser(innen) scheinen es noch nicht zu wissen: Die Denkspuren gibt es seit einiger Zeit auch auf Twitter ( twitter.com/denkspuren ). Ich war anfangs skeptisch, ob ich mit Twitter etwas anfangen könne, aber ich wollte das Experiment wagen. Mittlerweile habe ich mich eingezwitschert ... Auf diesem Blog ist es ruhiger geworden. Dabei habe ich 2009 vielleicht so viel geschrieben wie nie zuvor -- allerdings nicht auf diesem Blog. Ich hatte ursprünglich erwartet, dass mir mein Forschungssemester (März-August 2009) mehr Zeit für den Denkspuren-Blog schenken würde. Interessanterweise trat das Gegenteil ein. Die Forschung zu den konkatenativen Sprachen hat sich derart interessant und aufregend entwickelt (wie man es vielleicht aus den September-Beiträgen erahnen mag), dass ich jede freie Minute in die Entwicklung und Ausarbeitung von Ideen investiere. Dabei kommt dieser Blog momentan zu kurz. Ich bin gespannt, wie sich das 2010 entwickeln wird. All meinen Leser(innen) ein schöne

Concatenative Programming via Rewriting in Scheme

The kernel of a concatenative programming language can be easily implemented using a rewriting system. As a proof-of-concept the presented implementation fully relies on Scheme's rewriting system at macro expand time! All one needs is define-syntax and -- in order to provide access to Scheme's built-in procedures -- a single defmacro. (Apologies, if the formatting makes the code below hard to read. If you like to get the Scheme code, just drop me an email.) Rewriting rules concerning the data stack (ds) are written as follows: (rule swap : (@d ... snd fst) ==> (@d ... fst snd)) ^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^ word datastack before datastack after Note that the topmost element of the data stack is the rightmost element in the notation above. Rewriting rules concerning the data _and_ the program stack (ps) are written as (rule call : (@d ... (@q ...)) (@p ...) ==> (@d ...) (@q ... @p ...)) ^^^^ ^^^^^^^^^^^^^^^^^ ^^^^^^^^

Type Inference for "call" in Concatenative Languages

I think I solved the problem of type inference for "call" in concatenative languages. In a private mail, Slava Pestov (the creator of Factor ) challenged me with the problem of inferring types for the bi and bi@ combinator. In essence, the problem boils down to "call". The solution, Christopher Diggins proposes in his papers on Cat is not without complications. First let me introduce a notation for describing the effect of a word via substitutions. I use pattern matching. $X matches a single word, #X matches a single word _or_ quotation, and @X matches any number of words/quotations. To refer to a quotation, I use squared brackets. For example, "[ $X ]" matches a quotation with a single word inside like "[ 7 ]". Furthermore, I explicitly distinguish the data stack and the program stack and separate them with a bar "|". Here are some example substitutions: @D #X | dup @P ==> @D #X #X | @P @D #X #Y | swap @P ==> @D #Y #X | @P @D $X

Code-Generierung und Patching

Code-Generierung hat einen Vorteil, der oft übersehen wird: Man kann den generierten Code patchen , sprich Fehler darin beheben, ohne die Generator-Software anzufassen. Ich arbeite derzeit an einem Projekt, in dem aus XML-Dateien HTML-Dateien samt zugehörigem JavaScript generiert werden. Die XML-Dateien spezifizieren ein Dialogsystem, die per JavaScript gesteuerten HTML-Seiten führen das Dialogsystem aus. Nun ist es so, dass ich die Generatorsoftware nicht geschrieben habe. Zwar habe ich Zugriff auf den Quellcode, doch möchte ich am Code vorerst nichts ändern. Die Generatorsoftware hat sich in einem vorangegangenen Projekt bewährt, arbeitet zuverlässig und nimmt an den XML-Spezifikationen zahllose Konsistenzüberprüfungen vor -- und das ist Gold wert. Hier heißt es Finger weg, solange es geht, getreu der Devise: Never touch a running/working system. Im jetzigen Projekt wird jedoch anhand neuer XML-Spezifikationen deutlich, dass der Generator HTML-Code erzeugt, der Missverständnisse in d

RewriteParser & RewriteParser-Kombinatoren

In der Vergangenheit habe ich über " Objekt-orientierte Parser-Kombinatoren in Python " geschrieben -- ein Thema, das mich immer noch fasziniert. Es ist so unglaublich einfach, einen Parser mit Parser-Kombinatoren zu entwickeln. Das ist gepaart mit einer Flexibilität, die traditionelle Parser-Ansätze a la lex & yacc nicht bieten. In diesem Beitrag geht es (i) um die Verallgemeinerung eines Text-Parsers zum Parsen beliebiger Objektfolgen mit Hilfe zweier Stacks und (ii) um Parser, die ich RewriteParser nenne, und deren Kombination mit einem ganz speziellen RewriteParser-Kombinator, RPC*. Ich habe auf eine konkrete Programmiersprache verzichtet, damit das Prinzip klarer zutage tritt. Um die Idee der Parser-Kombinatoren nicht auf das Parsen von Zeichenketten zu beschränken, verallgemeinern wir die Idee, parsen beliebige Objekte von einem Stack und legen die Ergebnisse auf einem anderen Stack ab. Ein Parser (und somit auch ein Parser-Kombinator) nimmt zwei Stacks entgegen, ic

Abwrackprämie am Limit

(Update 31. März 2009: Der Geschäftsführer der Babiel GmbH, Herr Dr. Rainer Babiel, hat mich gebeten noch einmal ausdrücklich darauf hinzuweisen, dass seine Firma nicht für das BAFA-Webformular rund um die Abwrackprämie verantwortlich ist. Das betrifft auch das Hosting. Dies geht auch aus den Nachträgen zu diesem Blogbeitrag hervor.) Ich gehöre auch zu denen, die sich heute morgen mit einer Funkuhr bewaffnet vor den Rechner setzten, um am Wettrennen um die Reservierung der "Abwrackprämie" teilzunehmen. Der Wettstreit wurde um 8 Uhr vom Bundesamt für Wirtschaft und Ausfuhrkontrolle eröffnet unter www.ump.bafa.de . Bereits vor einer Woche habe ich mich schon zusammen mit einem Freund über den vorherzusehenden Zusammenbruch aufgeregt. Denn was die Sache so heikel macht: Jeder über die Webseite gestellte Antrag wird mit einer Zeitmarke versehen. Wer zuerst auf dem Webserver der BAFA registriert wird, der wird vorrangig bei der Gewährung der Umweltprämie für Altfahrzeuge behande

Konkatenative Programmiersprachen

Mit dem heutigen Tag beginnt offiziell mein Forschungssemester. Mein Thema: "A Model of Computation in Space and Time" -- darüber werde ich vielleicht ein anderes Mal was schreiben. Was sich in den letzten Wochen mehr und mehr aufdrängt, ist, das ein Schlüssel zu meinem Thema in den konkatenativen Sprachen liegt. Ich weiß es noch nicht sicher, aber mit jedem Tag finde ich mehr und mehr Gründe, mich mit dieser Klasse von Sprachen auseinander zu setzen. Was, Sie haben noch nie etwas von concatenative languages gehört? Verwunderlich ist das nicht. Konkatenative Sprachen führen zu unrecht ein vollkommenes Schattendasein. Wenn Sie sich für Ruby, Python, Groovy, Scheme, Lisp, Clojure, Haskell, F#, Prolog begeistern können, dann sollten konkatenative Sprachen wie Joy, Cat und Factor ein gefundenes Fressen für Sie sein. Diese drei Sprachen führen Sie in eine ganz neue Programmierwelt ein. Konkatenative Sprachen gehören zu den funktionalen Sprachen. Manfred von Thun hat auf seiner We

Ist der Kassen-Bug von Lidl ein Bug?

Mein Posting " Lidl und der Kassen-Bug " ist seit seinem Erscheinen immer noch der am meisten gelesene Beitrag in meinen Denkspuren. Nie hätte ich daran geglaubt, dass er diese Popularität genießen würde, denn er ist einer von den Beiträgen, die mir selber weniger bedeuten. " Lidl und der Kassen-Bug " erschien am 15. April 2008. Ich hatte den Tipp von einem meiner Studierenden bekommen. Allerdings wollte ich mit eigenen Augen sehen, ob der Tipp wirklich das versprochene Ereignis auslöst, bevor ich darüber blogge. Als ich über den Kassen-Bug berichte, gibt es einen kleinen, fast schon aufregenden Peak in den Visits (ich nutze Google Analytics). Die seinerzeit noch üblichen 20, 30, 40 oder auch mal 50 Visits an einem Tag schrauben sich am 15. April auf ungekannte 97 Visits hoch. Am Folgetag gibt es 190 Visits zu verzeichnen, dann 124, dann 100, ... und dann ist schon wieder alles beim alten. Ein paar Tage später, mit Beginn der neuen Woche beginnt es zu rumpeln. Genau

Was sind das für Zustände?

Zustandsmaschinen dienen in der Informatik zur Modellierung von Verhalten. Sie werden besonders gerne zur Spezifikation technischer Systeme eingesetzt. Oben im Bild sehen Sie ein einfaches Zustandsdiagramm. Zustandsdiagramme sind eine verbreitete Notation zur Darstellung von Zustandsmaschinen. Die Notation ist in der Unified Modeling Language (UML) standardisiert. In dem Beispiel geht es um einen Roboterarm. Der Roboterarm ist entweder in dem Zustand "idle", "moving up/down" bzw. "welding" (schweißen); Zustände werden durch Rechtecke mit runden Ecken abgebildet. Der Start- und der Endzustand sind durch besondere Symbole hervorgehoben: durch einen Kreis (Start) bzw. einen Punkt im Kreis (Ende). Die Pfeile beschreiben Übergänge (Transitionen) von einem Zustand in einen anderen und zwar abhängig von einem Ereignis. Die Ereignisse sind hier durch Buchstaben abgekürzt und stehen immer links vom Schrägstrich "/". Es sind Ereignisse, die der Roboter übe

Nominiert für die Auslese08

Ich rechne es meiner treuen Leserschaft zu, zwei meiner Beiträge für die Auslese08 im Wissenschaftscafe nominiert zu haben. Vielen Dank dafür -- es freut mich natürlich sehr, zur Vorschlagsliste der 80 Blogbeiträge zu gehören. Wenngleich ich mir keine Hoffnungen mache, in die engere Auswahl zu kommen. Ich habe auf noch keiner Party die Stimmung hochgepeitscht mit einer Frage wie " Was ist ein System? ". Und Gedanken zu " Syntax und Semantik " lassen auch nicht jedes Herz höher schlagen :-) Spaß macht es mir dennoch, und es ist schön zu wissen, dass zumindest einige Leser solche Freuden mit mir teilen.

Let it float!

Minus 50 plus 50 macht Null -- in manchen Fällen muss man sich so ein Ergebnis autorisieren lassen. Plus 38.29 minus 38.29 macht auch Null und -- wenn man es nicht so genau nehmen will -- sogar reich ! Von diesem schönen und oben abgebildeten Fehler berichtet Michael Haupt auf seinem Blog in dem Beitrag " Ich bin reich! ". Ein Fehler mit Pilgerwert. Ob ich irgendwann einmal diesen Zettel anfassen und in den Händen halten darf? Das sollte ich bei meinem nächsten Besuch in Potsdam tun! Herr Haupt wird genauso wie ich innigst hoffen, dass der Fehler von keinem unserer Studierenden "eingebaut" worden ist. Denn der Fehler ist fast so alt wie der erste Computer. Fließkommszahlen, floats, sollte man niemals auf Gleichheit überprüfen. Rundungsfehler können einem einen gewaltigen Strich durch die Rechnung machen (siehe oben). Finanzrechnungen sollte man stets genau rechnen, zum Beispiel in Cents und mit Integern und einem definierten Verhalten bei Rechnungen, die nicht in C