In Arraysprachen denken

• K-Programmierung konzentriert sich darauf, im REPL erprobten Code in Skripte zu überführen und große imperative Muster immer weiter auf kleinere deklarative Array-Muster zu reduzieren
• ngn/k-Skripte werden zeilenweise wie REPL-Eingaben ausgeführt, und mit \l file.k lassen sich gespeicherte Daten und Funktionen ins REPL laden
• Wenn man die Matrixmultiplikation mit der dreifachen Schleife nach Wikipedia direkt überträgt, entstehen viele globale Variablen, verschachtelte Schleifen und Mutationen, was den Stärken von K widerspricht
• Der Verbesserungsprozess verdichtet sich über +/ fold, ' each, /: eachright, \: eachleft, das Entfernen der Transposition und die Umwandlung in tacite Form von matmul: {x{+/x*y}\:y} zu matmul: (+/*)\:
• Das Beispiel der Matrixmultiplikation zeigt, dass K-Können darin besteht, Codeverdichtung immer wieder anzuwenden, um komplexe Abläufe in besser lesbare Array-Ausdrücke zu verwandeln

---

REPL-zentrierter K-Entwicklungsablauf

• Der vollständige Quellcode ist auf GitHub in matmul.k zu sehen
• K-Programmierung findet größtenteils im REPL statt und eignet sich gut dafür, auf bestehendem Code schnell zu experimentieren und ihn zu verbessern
• Die Kombination aus ngn/k und rlfe unterstützt einen Verlauf mit Pfeil nach oben/unten und reicht aus, um größere K-Programme zu entwickeln
• Es ist ein natürlicher Ablauf, Funktionen zuerst im REPL zu testen und sie dann in den eigentlichen Code zu übernehmen
• Das Prettyprinting von ngn/k gibt immer gültige K-Daten zurück, sodass sich manche Werte vorab berechnen lassen, um Programme zu beschleunigen

Ausführungsmodell von K-Skripten

• K-Skripte werden so ausgeführt, als hätte man sie im REPL eingegeben
  • Jede Zeile wird der Reihe nach ausgeführt
  • Wenn eine Zeile nicht mit einem Semikolon endet, wird ihr Rückgabewert ausgegeben
• Skripte erlauben mehrzeilige Definitionen, was die Lesbarkeit verbessern kann
• Um gespeicherte Daten und Funktionen im REPL zu verwenden, führt man \l file.k aus
  • Die Datei wird ausgeführt
  • Die Daten der Datei werden geladen
  • Wenn dieselbe Datei mehrfach geladen wird, überschreibt sie die vorherigen Daten
• Über die REPL-Hilfe, die mit \ erreichbar ist, lassen sich weitere Befehle finden

Wie man in einer Arraysprache Muster verkleinert

• K und Array-Programmierung sind ein Prozess des fortlaufenden Vereinfachens von Mustern
• Selbst große und schwer handhabbare Muster lassen sich auf mehr als eine Weise auf kleinere, deklarativere und besser lesbare Formen reduzieren
• Eine ausführliche Diskussion dazu gibt es in Patterns and Anti-patterns in APL: Escaping the Beginner's Plateau - Aaron Hsu - Dyalog '17
• Ein häufiger Ausgangspunkt ist die Situation, einen bekannten Algorithmus von GeeksforGeeks oder Wikipedia nach K zu übersetzen
• Das Beispiel verwendet die Matrixmultiplikation

Wenn imperative Matrixmultiplikation direkt übertragen wird

• Der Wikipedia-Artikel Matrix multiplication algorithm füllt die Matrix C mit einer dreifachen Schleife über i, j, k und einer Akkumulation in sum
• Wenn man das direkt nach K übersetzt, weist man viele globale Werte wie A, B, n, m, p, C, i, j, k und sum zu
• Dieser Code benutzt K wie eine imperative Sprache und passt daher nicht gut zum Design von K
• Das Problem lässt sich auf drei Punkte eingrenzen
  • Es gibt viele globale Zuweisungen
  • Mehrere Ebenen verschachtelter Schleifen bleiben erhalten
  • Es gibt häufige Mutationen

Von der innersten Schleife aus zusammenfalten

• Die innerste Schleife initialisiert sum mit 0 und akkumuliert beim Durchlauf von k die Werte A[i;k]*B[k;j]
• Die erste Verbesserung besteht darin, die Summierung mit dem Fold / in +/ umzuwandeln
  • Die globale Variable sum verschwindet
  • Es wird auf eine Form wie C[i;j]::+/... reduziert
• Anschließend kann man ausnutzen, dass ' each ein Array zurückgibt, sodass man die Rückgabewerte der verschachtelten Schleifen direkt verwenden kann, ohne C zu verändern
• Nach diesem Schritt bleiben nur noch drei Schleifen ohne Mutation übrig, und die zentralen Variablen sind i, j, k

Der Prozess, k, j und i zu eliminieren

• Die drei Variablen haben folgende Rollen
  • i indiziert jede Zeile von A
  • j indiziert jede Spalte von B
  • k indiziert jede Spalte von A und jede Zeile von B
• k paart jede Zeile von A mit jeder Spalte von B zur Multiplikation, daher kann man den Zwischenindex entfernen und direkt zuordnen
  • In diesem Schritt entfallen eine Schleife und m
• Um j zu entfernen, muss man jede Spalte von B holen und mit A[i] paaren
  • Dazu transponiert man B und paart mit eachright /: jedes Element
• i kann auf dieselbe Weise entfernt werden
  • Mit eachleft \: paart man jede Zeile von A mit jeder Spalte von B
• Nach diesem Prozess ergibt sich ohne globale Variablen die folgende Form

matmul: {x{+/x*y}/:\:+y}

Entfernen der Transposition und finale tacite Form

• Die Transposition + ist teuer und kann entfernt werden
• Die bisherige Methode ist die naive Methode, bei der jede Zeile von x mit jeder Spalte von y multipliziert wird
• Stattdessen kann man jede Zeile von B auf das gesamte A anwenden, um dieselbe Arbeit implizit auszuführen

matmul: {x{+/x*y}\:y}

• Diese Funktion lässt sich durch Anwendung der Regeln aus Chapter 3 in eine tacite Form umwandeln
• Das Endergebnis ist wie folgt

matmul: (+/*)\:

Arraysprach-Intuition durch Übung aufbauen

• matmul: (+/*)\: ergibt eine K-typische Matrixmultiplikationsfunktion
• Der Verdichtungsprozess kann anfangs nach vielen Schritten aussehen
• Je mehr man K übt, desto leichter und intuitiver wird die Codeverdichtung
• Matrixmultiplikation ist ein einfaches Verfahren, das gut zu Ks Array-Unterstützung passt
• In späteren Kapiteln sollen Algorithmen behandelt werden, die weniger gut zu K passen, sowie der Umgang mit ihnen

[GN⁺]

Hacker-News-Kommentare

• Die überzeugendste Demonstration des Potenzials von Array-Sprachen war für mich tatsächlich das Video, in dem Aaron Hsu erklärt, wie er den parallelen APL-Compiler Co-dfns entwickelt: https://www.youtube.com/watch?v=gcUWTa16Jc0&t=860s
  Er hat auf HN unter dem Namen arcfide auch mehrfach über semantische Dichte geschrieben und erklärt, dass APL-Code so entworfen sei, dass man Funktionsweise, umgebenden Kontext und Abhängigkeiten fast ohne Scrollen auf einem Bildschirm sehen kann: https://news.ycombinator.com/item?id=13571159
  Die Sichtweise ist, dass Code so knapp werden kann, dass der Name eines Algorithmus fast so lang ist wie die ausgeschriebene Implementierung des Algorithmus selbst; dann liest man Code in idiomatischen Einheiten wie englische Phrasen, und statt wiederverwendbare Abstraktionen zu bauen, kann es schneller sein, direkt alle auf dem Bildschirm sichtbaren Verwendungen zu ändern

  • Ich frage mich, ob LLMs mit begrenztem Kontextfenster vielleicht besser mit APL klarkommen als mit anderen Sprachen
  • Ich denke, dass man so lange Erklärungen schreiben muss, liegt daran, dass der Code hässlich aussieht. Wenn man Zeichen gewählt hätte, die weniger unschön wirken, wenn sie nebeneinanderstehen, hätte man wohl nicht 18 Stunden darauf verwenden müssen, Leute davon zu überzeugen, dass die Sprache gar nicht so schlecht ist

• Wenn man sich mit Array-Programmierung nicht gut auskennt, würde ich als Einstieg The Array Cast empfehlen: https://www.arraycast.com/episodes/
  Der RSS-Feed ist hier: https://www.arraycast.com/episodes?format=rss

  • Ich habe die ersten etwa fünf Folgen von The Array Cast gehört, in der Hoffnung, überzeugt zu werden, war am Ende aber nicht überzeugt. Die Hosts meinten, dass die kurze Notation und die nicht-ASCII-Symbole von Array-Sprachen mit der Zeit in Ordnung seien und dass sich das wegen der Vorteile lohne, aber die meisten dieser Vorteile kannte ich bereits aus Higher-Order Functions in heutigen Mainstream-Sprachen
    map/filter/reduce gibt es ohnehin fast überall, und es wirkte so, als würde übersehen, dass man sie nutzen kann, ohne dafür erst ein neues Notationssystem mit ideografisch anmutenden Zeichen lernen zu müssen
  • Dadurch habe ich zwar BQN kennengelernt, aber ob ich es in einer echten Produktionsumgebung einsetzen würde, weiß ich noch nicht. Ich mag es, aber außer R, NumPy und Julia wirken die meisten Array-Sprachen fremd, und wenn man sich tief in APL, J oder BQN einarbeitet, entfernt man sich womöglich selbst von den Leuten, die einem später helfen könnten

• Ich bin in den 70ern sofort auf APL/APL2 angesprungen, als ich es auf Papierterminals mit echtem Überdrucken kennengelernt habe, aber nachdem ich später mit ML und Haskell funktionale Programmierung kennengelernt hatte, wurde mir klar, dass das, was ich an APL wirklich mochte, weniger die Arrays als vielmehr die Fähigkeit zur Funktionskomposition war
  Haskell ist vollständig rein und Typsysteme ziehen sich dort durch alles, wodurch es in dieser Hinsicht viel besser ist; außerdem war es für mich unterhaltsamer und mächtiger als APL. Ich habe viele kleine und mittlere Projekte damit gebaut, auch einen Prototypen, der zeigt, dass sich der Parser von LLVM Flang mit Parser Combinators implementieren lässt, und ich löse jedes Jahr Advent of Code insgesamt in ein paar hundert Zeilen. Wer APL mag, sollte Haskell ruhig einmal ausprobieren
  Inzwischen wirkt der APL-Aspekt einer „Notation als Werkzeug zum Denken“ für mich wie eine Rechtfertigung übertriebener Kürze. Um die Kraft von Komposition zu zeigen, ist das gut, aber es kann die Klarheit auch beeinträchtigen

  • Ich wiederhole mich bei diesem Thema ständig, aber seit ich point-free Haskell einigermaßen gut beherrsche, fasse ich J und K kaum noch an. Mit Funktoren/Funktionalobjekten wird es sogar mächtiger als Verb Trains, und <=< gibt es bereits; wenn man das Pendant zu fmap verwendet, läuft es wirklich sehr gut
    |||, +++, &&&, *** sind auch gut, und man kann sich sogar eigene UTF-8-Operatoren bauen, um alles kürzer und hübscher zu machen. Schade nur, dass echter beruflicher oder öffentlich einsehbarer ernsthafter Haskell-Code nur selten auf diese Weise großzügig mit vertikalem Bildschirmplatz umgeht
  • Es wäre schön, einen Link zum Advent-of-Code-Quelltext zu sehen

• Ich frage mich, wie man in Array-Sprachen allgemein Probleme der Form „Finde alle Zahlen kleiner als N, für die das Prädikat P wahr ist“ behandelt. Beispiele wären etwa das Finden aller Primzahlen kleiner als 1000 oder aller pythagoreischen Tripel mit z kleiner als 1.000.000.
  In einer imperativen Sprache würde man in einer Schleife das Prädikat prüfen, in einer funktionalen Sprache Rekursion oder map/filter auf Lazy Lists verwenden; bei einer Array-Sprache verstehe ich es normalerweise so, dass man ein Array 1..N erzeugt, das Prädikat darauf anwendet, ein Masken-Array bildet und dann mit dieser Maske das ursprüngliche Array filtert.
  Wenn N so groß wie 1 Milliarde ist und das Prädikat fast nie wahr ist, wirkt das Erzeugen von 1..N und der Maske als zwei riesige temporäre Arrays in Bezug auf Speicher und Ressourcen sehr verschwenderisch. Ich frage mich, ob Array-Sprachen durch dieses ständige Erzeugen temporärer Arrays langsam werden oder ob Implementierungen das mit Verfahren wie Lazy Evaluation optimieren.

  • Ja, das verschwendet viel Speicher. Allerdings ist Speicher billig, und falls nötig kann man die Berechnung blockweise aufteilen. Dass der Speicher wirklich komplett ausgeht, ist selten, aber Blocking ist nützlich, um in niedrigeren Cache-Ebenen zu bleiben.
    Bei Skalarsprachen ist es umgekehrt: Dort ist die Verarbeitung eines Werts nach dem anderen der Standard, sodass die potenzielle Parallelität verschwendet wird, die Array-Sprachen mit SIMD-Algorithmen nutzen. Auch das fällt nur deshalb kaum als Problem auf, weil man an den Status quo gewöhnt ist, und die Lösung ist ebenfalls Blocking.
    Ob Array-Sprachen tatsächlich gut sind, hängt vom Problem ab. In den meisten praktischen Anwendungen ist Performance überhaupt nicht wichtig, und der Ruf von k scheint eher daher zu kommen, dass kdb als Datenbank schnell ist, nicht dass die k-Implementierung selbst eine besonders schnelle Sprache wäre. Trotzdem kann man überraschend schnell werden, wenn man sich statt auf maschinenspezifische Detailoptimierungen auf elegante Array-Algorithmen konzentriert: https://mlochbaum.github.io/BQN/implementation/versusc.html
  • Es gibt einige Umgehungen. Lazy Evaluation ist eine Möglichkeit, und Kap verwendet sie: https://aplwiki.com/wiki/KAP
    Eine andere naheliegende Methode ist, den gesamten Ausdruck per Loop Fusion zusammenzuführen, sodass keine temporären Arrays entstehen. Eine einfachere Option ist, Eingabe- und Ausgabe-Arrays in Chunks von einigen Dutzend KB aufzuteilen, um unnötigen temporären Speicherverbrauch zu begrenzen; soweit ich weiß, macht das keine Array-Sprache automatisch, und ich würde das irgendwann gern in CBQN ausprobieren. Benutzer können das auch manuell tun, und um die Performance zu maximieren, muss man das tatsächlich oft tun.
  • Die Intuition ist im Großen und Ganzen richtig, aber in der Praxis ist das selten ein Problem. In der k-Familie, zum Beispiel in ngn/k, gibt es für !10000000 eine Lazy-Struktur, die die iota von 0 bis zehn Millionen nicht als tatsächliches Array aus zehn Millionen Integern erzeugt, sondern nur als einfachen Bereich behandelt.
    Natürlich kann durch bestimmte Operatoren am Ende doch ein solches Array entstehen. Außerdem gibt es Optimierungen wie das Umformen von Mustern wie +|x, also x umdrehen und das erste Element nehmen, in das bloße Nehmen des letzten Elements.
  • Es wirkt, als würdest du annehmen, dass die Array-Erzeugung wörtlich so stattfindet. Es gibt keinen Grund, warum eine Array-Sprache intern nicht chunkweise arbeiten könnte. Selbst wenn man ein Array mit 10 Milliarden Integern anfordert, muss es dieses nicht naiv exakt so erzeugen.
  • Viele Array-Sprachen haben dieses Problem tatsächlich. Genauer gesagt besteht das Problem darin, dass der einfache und intuitive Ansatz tendenziell viel mehr berechnet als nötig.
    Natürlich kann man es anders schreiben und so vermeiden, aber solche Lösungen werden oft länger und weniger elegant. Der APL-Dialekt Kap, an dem ich arbeite, verschiebt Berechnungen, bis das Ergebnis wirklich gebraucht wird, und deckt viele Fälle ab, sodass man den intuitiven Stil beibehalten kann, ohne Ergebnisse zu berechnen, die später verworfen werden.

• Die wichtigste Erkenntnis aus der Arbeit mit Array-Sprachen, insbesondere mit k, ist für mich Folgendes: Verben sind Algorithmen, und in imperativen bzw. objektorientierten Sprachen muss man gemeinsame Algorithmen wie find, sort oder group oft selbst implementieren.
  Eine Folge von Verben oder Adverbien war die direkteste Form von Komposition, die ich je verwendet habe, und Komposition ist einfach und natürlich. Ein Programm wirkt nicht mehr wie eine Sammlung von Anweisungen und Ausdrücken, sondern wie eine Komposition von Algorithmen.
  Wenn man bei Arrays, Maps und Funktionen die Konzepte von Definitionsbereich und Wertebereich konsistent behandelt, werden Designentscheidungen einfacher, und wenn von rechts nach links ausgewertet wird, muss der Blick beim Lesen des Codes nicht dauernd hin- und herspringen.
  Es ist möglich und bevorzugt, Code zu den Daten zu schicken, statt Daten in den Code zu holen. Die meisten größeren k-Projekte passen ohne Kommentare in eine Netzwerk-MTU, also 1540 Byte. Ein weiterer Bonus von k ist, dass Views funktionale Beziehungen direkt implementieren können und dass durch Hot Code Loading über den Interpreter Anwendungen möglich sind, die „für immer“ laufen.

• Mein persönlicher, voreingenommener und begrenzter Eindruck vom Lösen von K-Sprach-Aufgaben zur Vorbereitung auf Bewerbungsgespräche ist, dass die Sprache absichtlich kryptisch ist. Für Rätsel und clevere Lösungen ist sie gut geeignet.
  Aber wenn es darum geht, Array-Sprachen und das Denken in Arrays zu lernen, ist die Erfahrung mit NumPy-Arrays in Python meiner Meinung nach hilfreicher.

  • Ich frage mich, für welches Interview das war.

• Nach etwa 50 Stunden mit J hatte ich das Gefühl, dass dieses Paradigma ehrlich gesagt zu stark in eine Richtung kippt.
  Ich bin nicht sicher, ob es als Denkwerkzeug hilfreich ist, jedes Problem als Verschachtelung von Arrays zu betrachten. Wenn man frei Datenstrukturen bauen kann, die das Problem gut erfassen, kann der algorithmische Teil viel einfacher werden.
  Ich glaube, um APL/J/K zu verwenden, muss man klüger sein. In flexibleren Sprachen sind Ansätze, die dort direkt möglich sind, hier oft nicht möglich; man muss das Problem erst umformen, und dafür ist oft deutlich mehr Denkarbeit nötig.

• Dieses Beispiel basiert auf K, aber eine weitere Array-Sprache ist J: http://jsoftware.com
  In J schreibt man dot =: +/ . *, P =: 2 3 4, Q =: 1 0 2, P dot Q, und das ergibt das Skalarprodukt 10 von P und Q.

  • Die ursprüngliche Array-Sprache ist APL, und das Skalarprodukt kann man als dot←+.× schreiben. Wenn die ausgeschriebene Notation aber fast so kurz ist wie ein passender kurzer Name, gibt es wenig Grund, überhaupt einen Namen zu vergeben, zumal man dann womöglich noch Leerzeichen um den Namen herum setzen muss.
  • Ich sehe noch nicht ganz, welchen Vorteil das gegenüber Haskell hat. Man kann auch dot = (sum.) . zipWith (*), p = [2, 3, 4], q = [1, 0, 2], p `dot` q schreiben.
    Für mich sieht der Unterschied nur darin aus, dass sum und zipWith ausgeschriebene Namen haben und dass kein Lifting oder keine Strukturtransformation „wie von Zauberhand“ passiert.
  • In KlongPy schreibt man das Skalarprodukt als dot::{+/x*y}. P::[2 3 4], Q::[1 0 2], und dann dot(P;Q).

• An den Beispielen ist für mich nicht klar, welchen Sinn das hat. Ist die Performance in irgendeiner Weise besser?
  Die Syntax für Matrixmultiplikation ist zwar kürzer, aber das scheint auch daran zu liegen, dass man eine Menge eingebauten Kontext darüber im Kopf haben muss, wie die Sprache K funktioniert

  • Dass es knapper ist, hat an sich schon Wert. Vor allem wenn man bedenkt, dass Mathematik zunehmend Konzepte in Definitionen auf höherer Ebene verdichtet. Wenn Konzepte auf höherer Ebene zu primitiven Bausteinen werden, kann man schneller denken und komplexere Dinge bauen
  • Die Performance kann besser sein. Computer sind sehr schnell darin, Arrays zu durchlaufen, besonders wenn SIMD genutzt werden kann, aber das ist nicht alles
    Es lohnt sich, mit einer Array-Sprache zu spielen, bis man das Paradigma versteht. Imperativer Code lässt sich oft besser im Array-Stil ausdrücken, und lange, kleinteilige Funktionen können allein durch Array-Operationen oder in Kombination mit anderen Stilen stark vereinfacht werden
  • Auch Weitschweifigkeit hat ihren Preis, und wenn man glaubt, dass nur wirklich komplexe Funktionen das Recht haben, weitschweifig zu sein, wird der Sinn schnell klar
    Vergleicht man in Haskell (+) <$> Just 1 <*> Just 2 mit do x <- Just 1; y <- Just 2; Just (x + y), würde ich bei dieser Komplexität immer die erste Form bevorzugen. Die zweite nimmt mehr Platz ein und wirkt dadurch, als würde etwas Komplizierteres passieren
    Bei komplexeren Aufgaben würde ich lieber in kleine Funktionen zerlegen, damit eine Variante der ersten Form sinnvoll bleibt, statt die zweite Form zu verwenden. Das ist ein Kompromiss, bei dem „ein Teil der Anfänger kann es schnell lesen“ gegen „alle über Anfängerniveau können es lesen“ eingetauscht wird
    Wenn man darauf optimiert, dass „ein Teil der Anfänger es lesen kann“, sind die Grenzerträge meiner Meinung nach sehr gering; stattdessen sollte das Ziel sein, dass „alle über Anfängerniveau“ oder je nach Fall sogar „alle ab mittlerem Niveau“ es lesen können

• Für jede Sprache gibt es viele Gründe, sie zu verwenden, und viele Gründe, sie nicht zu verwenden. Aber entscheidend sind nicht kurze Notation, relative Klarheit oder die Fähigkeit, zu schnellem Code kompiliert zu werden, sondern ob ein später hinzukommender Programmierer den Code für den realen Einsatz tatsächlich ändern und warten kann
  Viel zu oft wollen Programmierer nur zeigen, wie gut ihre Leet-Fähigkeiten sind, und denken nicht an die armen Leute, die den Code später übernehmen müssen. Realistisch gesehen muss viel Leet-Code langfristig weggeworfen oder komplett neu geschrieben werden, um etwas zu bekommen, das dauerhaft unterstützt werden kann
  Es hat lange gedauert, bis ich das verstanden habe, und danach habe ich versucht, sauberen, einfachen und verständlichen Code zu schreiben, den andere warten können. Viel zu oft wird Wegwerfcode zur grundlegenden Infrastruktur einer Organisation, verfestigt sich dort und wird für die nächste Generation zu etwas Unverständlichem