Weihnachtsbaeume mit J
Copyright (C) 2008, 2009 Martin Neitzel
(,{.)' #'#~(|.,.1:++:)i.11
#
###
#####
#######
#########
###########
#############
###############
#################
###################
#####################
#
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|
+-----+--------+