Weihnachtsbaeume mit J

Yippie, ich habe die Verlosung beim //SEIBERT/MEDIA-Entwicklergolf gewonnen!

Damit niemand glaubt, ich habe einfach irgendetwas auf der Tastatur hingeklimpert und dann einen Baum druntergemalt, hier noch einmal der Code und Erlaeuterungen dazu.

Vorab aber vielen Dank an //SEIBERT/MEDIA fuer die Ausrichtung des Wettbewerbs und das nette Geschenk!

Ueber J

J ist eine Programmiersprache aus den 90'ern, die Ihre Wurzeln in der Sprache APL (erstmals aus den 60'ern) hat. Informatiker wuerden die Sprache mit folgenden Begriffen beschreiben:

In erster Linie "funktional" (d.h. mit first-class und higher-order functions), mit spaeter an die Sprache drangeklebten "normalen" Kontroll-Strukturen und objekt-orientierten Symbol-Lookups.
Operationen mit doppelter Bedeutung, je nach prefix- bzw. Infix-Verwendung wird eine davon angewandt. Insgesamt ca. 240 built-in Funktionen in der core-languange, groesstenteils die Ascii-Sonderzeichen evtl. gefolgt von "." oder ":".
*alle* Daten sind n-dimensionale Arrays, *alle* Operationen iterieren implizit ueber Arrays (SIMD-Parallelitaet)
"phrasal forms" fuer implizite MISD/MIMD-Parallelitaet; diverse Funktionale, um Funktionen in unterschiedlichen Datenfluss-Wegen zu verbinden.

Praktiker wuerden die Sprache so beschreiben:

Hoppla, ein Taschenrechner auf Drogen -- ich brauche gar keine klassischen "Programme" mehr zu schreiben, um meine Daten zu beackern.
Eines der wesentlichen Anwendungs-Felder ist das Portfolio-Management im Boersen-Umfeld, bei denen es GELD bedeutet, wenn man SCHNELL auf geaenderte Randbedingungen reagieren kann.
J ist eine "Very High-Level Language" -- sie abstrahiert komplett von klassischen Rechnerarchitekturen, der Programmier==Benutzer wird nicht mehr dadurch ausgebremst, dass er sich um Speicher- verwaltung oder das Runterbrechen der Daten auf CPU-geeignete skalare Einzelwerte kuemmern muss.

Ich hatte das Glueck, APL im Rahmen meines Informatik-Studiums in den 80ern kennenlernen zu koennen. In den 90ern habe ich die Entwicklung von J als modernem Dialekt mit verfolgt und spaeter auch aktiv mit begleitet. Ich sollte also wissen, wie man einen ASCII-Baum damit malt.

Interpreter fuer J gibt es kostenfrei von den Entwicklern der Sprache unter /http://jsoftware.com/. Unterstuetzte Plattformen sind Windows und Linux, 32 und 64bit.

Ein schlichter Baum

(,{.)' #'#~(|.,.1:++:)i.11 # ### ##### ####### ######### ########### ############# ############### ################# ################### ##################### # Die Zeile (,{.)' #'#~(|.,.1:++:)i.4 sieht fuer einen uneingeweihten natuerlich eher nach Modemrauschen aus als nach einem Programm. Wie wird daraus ein Weihnachtsbaum?

Als erstes schaffen wir etwas mehr Uebersicht durch Leerzeichen zwischen den einzeln Tokens:

( , {. ) ' #' # ~ ( |. ,. 1: + +: ) i. 4 Wir beackern das Schritt fuer Schritt und fangen an dem RECHTEN Ende an. i. 4 liefert einen "Index-Vektor" der Laenge 4: ==> 0 1 2 3 Die lange Klammern-Konstruktion ( |. ,. 1: + +: ) enthaelt eine Sequenz von 5 Funktionen. Diese werden aber nicht als lineare "Pipeline" kombiniert, sondern etwas raffinierter:

ZWEI Funktionen (f g) zusammen bilden einen sogannten "Haken". Anwendung auf ein Argument x bedeutet in klassischer math. Notation: f(x,g(x)).
DREI Funktionen (f g h) zusammen bilden eine sogennante "Gabel" und (f g h)(x) wird als g( f(x), h(x)) bestimmt.
LAENGERE Sequenzen werden rechts-assoziativ in Gabeln und Haken zerlegt:
(e f g h) <==> (e (f g h)) (ein Haken mit ein Gabel)
(d e f g h) <==> (d e (f g h)) (eine Gabel mit einer Gabel)
...
(a b c d e f g h) <==> (a (b c (d e (f g h)))) etc.

Nun also konkret

( |. ,. 1: + +: ) 0 1 2 3 <==> (|. 0 1 2 3) ,. ((1: 0 1 2 3) + (+: 0 1 2 3)) mit den Funktionen |. Spiegeln 1: Konstanten-Funktion "1" +: Verdoppeln (ist als "skalar" definiert, und wird entprechend automatisch auf jedes einzelne Element angewandt, um wieder einen Ergebnis-Vektor zu liefern) <==> 3 2 1 0 ,. (1 + 0 2 4 6) mit der Funktion + Addition (ist als "skalar" definiert und fuehrt auch zu einer impliziten Schleife mit Vektor-Ergebnis). <==> 3 2 1 0 ,. 1 3 5 7 mit der Funktion ,. Element-weises Zusammenhaengen: ==> 3 1 2 3 1 5 0 7 also eine 4x2-Matrix. Die naechste Funktion, die wir brauchen, ist # Copy, und hier ist ein Beispiel: 3 1 2 # 'abc' ==> 'aaabcc' Wohlgemerkt: links die Wiederholung-Angaben (ein Vektor), rechts "die Daten". Wir sind jetzt bei folgendem Zwischenschritt angekommen: 3 1 ( , {. ) ' #' #~ 2 3 1 5 0 7

Die Tilde ~ ist ein funktionaler Operator: sie wendet das Copy # unter Vertauschung von rechten und linken Argument an, also so, wie wir es brauchen.

Da das Copy auf Wiederholungs-Vektoren definiert ist und wir eine ganze 4 Zeilen-Matrix als Argument haben, gibt es wieder eine implizite Schleife mit vier Teil-Ergebnissen

# 3 blanks + 1 # ### 2 blanks + 3 # ##### 1 blank + 5 # ####### 0 blanks + 7 #

Die kuerzeren Teil-Ergebnisse werden implizit rechts mit blanks gepaddet, um alles auf eine gemeinsame Laenge zu bringen. Das Ergebnis ist eine rechteckige 4x7-Zeichenmatrix.

Jetzt brauchen wir nur noch den Stamm. Dazu recyclen wir einfach den Wipfel des Tannenbaums. Erinnert sich noch jemand zufaellig an die Definition des "Haken" oben?

(f g)x [J] <==> f(x,g(x)) [Mathematik]. "Die Zusammenhaengung vom Rumpf mit dem Wipfel vom Rumpf." [Deutsch] Also hier mit , Zusammenhaengen {. Erstes Element # # ### ### (, {.) ##### ==> ##### ####### ####### #

Fertig.

Der zweite Baum

' x' {~ ( }: , 1: ,: {. ) ( ,.~ |.) = i. 6 xx x x x x x x x x xxxxxxxxxxxx xx Der Ausdruck enthaelt viele bekannte Sprachelemente, aber ein ganz anderes Konstruktionsverfahren des Baumes. Ich liste daher als Puzzle-Aufgabe zur selbststaendigen Analyse des Ausdrucks hier nur die Uebersicht der alten und neuen Funktionen: i. 4 (alt) Index-Vekor 0 1 2 3 = 'ente' "Selbst-Identifizierung": Bitmatrix, welches Element 1 0 0 1 wo auftritt. 0 1 0 0 0 0 1 0 |. (alt) Spiegeln (hier auf Matrix) ,. Element-weises Zusammenhaengen (hier auf Matrizen) f~ (alt) Funktional "Funktion f mit Vertauschung der Argumente" {. (alt) Erstes Element ,: Zusammenhaengen entlang einer neuen Achse: 2 3 ,: 5 6 7 8 2 3 0 0 5 6 7 8 'a' ,: 'ente' aaaa ente 1: (alt) Abbildung auf die Konstante "1" , (alt) Zusammenhaengen (hier zweier Matrizen) }: alles bis auf das letztes Element (hier auf Matrix) { Array-Indizierung (0-basiert) 2 1 { 'ente' tn Sowie ein Zwischenergebnis: ( }: , 1: ,: {. ) ( ,.~ |.) = i. 6 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 Viel Spass beim Reverse-Engineereing!

Der dritte Baum

Meine zuerst eingereichte und laengste Variante sollte so ungefaehr die Laenge des internen kurzen Perl-Codes haben, aber etwas mehr "Wumm!": 'MerryChristmas!' ;&((|.,'|'"_,])"1@(}.\@|.,#{.{:)) 'HappyNewYear!' +-------------------------------+---------------------------+ | | | | | | s|s | r|r | | as|sa | ar|ra | | mas|sam | ear|rae | | tmas|samt | Year|raeY | | stmas|samts | wYear|raeYw | | istmas|samtsi | ewYear|raeYwe | | ristmas|samtsir | NewYear|raeYweN | | hristmas|samtsirh | yNewYear|raeYweNy | | Christmas|samtsirhC | pyNewYear|raeYweNyp | | yChristmas|samtsirhCy | ppyNewYear|raeYweNypp | | ryChristmas|samtsirhCyr | appyNewYear|raeYweNyppa | | rryChristmas|samtsirhCyrr | HappyNewYear|raeYweNyppaH | | erryChristmas|samtsirhCyrre | !|! | | MerryChristmas|samtsirhCyrreM | | | !|! | | +-------------------------------+---------------------------+

Da kommen zuviele neue Sprachelemente drin vor, als dass ich das komplett erklaeren mag, aber ein erstes Fragment davon erklaert den groben Ansatz:

( }.\@|. , # {. {: ) 'HappyNewYear!' r ra rae raeY raeYw raeYwe raeYweN raeYweNy raeYweNyp raeYweNypp raeYweNyppa raeYweNyppaH ! ist eine Semi-Baum-Matrix, dessen gespiegelte Zeilen vor ein '|' vor sich selbst gepappt werden. Das (|.,'|'"_,])"1 dafuer ist eigentlich schon unverschaemt lang und haesslich. Anyway: J-Programmierer denken so ungefaehr auf dieser Ebene und kuemmern sich dann um die Details.

Der Code wird typischerweise interaktiv im Interpreter entwickelt. Man nimmt sich sein Ausgangs-Argument und zimmert sich daraus Schritt fuer Schritt in Richtung Endergebnis.

Es ist dabei nie ein Problem hier oder da noch mal ein Spielegung einzuschieben oder das letzte Element wegzuwerfen etc. -- wenn man sich im reichhaltigen Werkzeugkasten von J einigermassen auskennt. Man braucht im ersten halben Jahr staendig einen Spickzetttel, um bspw. die vier Funktionen {. {: }. }: auseinanderzuhalten. Irgendwann ist das aber kein Problem mehr.

Der Doppelbaum war natuerlich auch nicht in einem Rutsch entstanden. Irgendwann war der angepeilte Baum fertig:

tree 'foo!' | o|o oo|oo foo|oof !|! und der Ausbau auf 'foo_' ;&tree 'bar.' +---------+---------+ | | | | | | o|o | r|r | | oo|oo | ar|ra | | foo|oof | bar|rab | | _|_ | .|. | +---------+---------+ ist dann intellektuell nicht wirklich schwer. Fuer die Einrechung beim Wettbewerb vollzieht man dann einfach ein "inlining" der entwickelten Hilfsfunktionen.

Schlussbetrachtung

Am Ende noch der obligatorische Schwanzlaengenvergleich mit dem besten internen Ergebnis: NB. Die Laengen und ihr der Verhaeltnis zueinander: '(,{.)'' #''#~(|.,.1:++:)i.11' (,;%)&# 'say" "x(30-$_)."xx"x$_ for 1..25,1' +-----+--------+ |26 34|0.764706| +-----+--------+