In Arraysprachen denken

In der K-Sprache denken

• K-Programmierung erfolgt größtenteils über ein REPL.
• rlwrap für ngn/k ermöglicht das Durchsuchen des Verlaufs mit den Pfeiltasten und ist für die Entwicklung größerer Programme nützlich.
• Funktionen werden im REPL getestet und anschließend in den eigentlichen Code übernommen.
• Die hübsche Ausgabe von ngn/k liefert immer gültige K-Daten zurück und kann zur Beschleunigung von Programmen im Voraus berechnet werden.
• K-Skripte werden so ausgeführt, als hätte man sie ins REPL eingegeben; der Rückgabewert jeder Zeile wird ausgegeben, sofern sie nicht mit einem Semikolon endet.
• Skripte erlauben mehrzeilige Definitionen, was die Lesbarkeit verbessert.
• Um Arbeit in einem Skript zu speichern und im REPL zu verwenden, kann man mit \lfile.k die Datei ausführen und Daten laden.
• Eine Datei kann im REPL mehrfach geladen werden, wobei frühere Daten überschrieben werden.
• Die REPL-Hilfe, auf die man mit \ zugreift, enthält verschiedene nützliche Befehle.

Vereinfachung der Array-Programmierung

• Array-Programmierung ist ein fortlaufender Prozess, komplexe Muster in kleinere, deklarativere und leichter lesbare Muster zu vereinfachen.
• Wie sich komplexe Muster vereinfachen lassen, wird in "Patterns and Anti-Patterns in APL: Escape from the beginner's plateau - Aaron Hsu - Dyalog '17" ausführlich behandelt.

K-Transformation der Matrixmultiplikation

• Der iterative Algorithmus zur Matrixmultiplikation aus dem Wikipedia-Artikel lässt sich direkt nach K übertragen.
• Das schlechtestmögliche Beispiel für in K übertragenen Code erfordert viele Zuweisungen an globale Variablen, verschachtelte Schleifen und zahlreiche Modifikationen.
• Durch Vereinfachung des Codes lassen sich diese Probleme nacheinander lösen.

Vereinfachung der inneren Schleife

• In der inneren Schleife lässt sich sum mit fold (/) vereinfachen.
• ' (each) gibt ein Array zurück und macht dadurch die globale Variable C überflüssig.
• Durch das Entfernen der Variablen i, j und k lässt sich die Schleife vereinfachen.

Schleifen entfernen und globale Variablen minimieren

• Ohne k lässt sich die mittlere Schleife entfernen, indem Zeilen und Spalten direkt einander zugeordnet werden.
• Um j zu entfernen, können die einzelnen Spalten von B mit A[i] gepaart werden.
• Um i zu entfernen, kann eachleft verwendet werden, um jede Zeile von A mit jeder Spalte von B zu paaren.
• Globale Variablen werden nicht mehr benötigt.

Endgültige Form der Matrixmultiplikationsfunktion

• + (Transponieren) ist teuer und kann entfernt werden.
• Statt jede Zeile von x mit jeder Spalte von y zu multiplizieren, lässt sich implizit dieselbe Arbeit erledigen, indem jede Zeile von B mit dem gesamten A abgeglichen wird.
• Am Ende erhält man eine kompakte und explizite Funktion zur Matrixmultiplikation.
• Der Prozess der Code-Vereinfachung umfasst anfangs mehrere Schritte, wird aber mit wachsender Erfahrung in K leichter und intuitiver.
• Matrixmultiplikation ist ein einfacher Ablauf, der gut zur Array-Unterstützung von K passt.
• Weitere Algorithmen, die weniger gut zu K passen, und der Umgang mit ihnen sollen in künftigen Kapiteln behandelt werden.

Meinung von GN⁺

• Dieser Beitrag zeigt, wie sich Algorithmen wie die Matrixmultiplikation mit der K-Sprache vereinfachen und optimieren lassen.
• Unmittelbares Feedback über das REPL und die iterative Verbesserung von Code sind zentrale Merkmale der K-Programmierung und auch für Junior-Softwareentwickler eine nützliche Lernmethode.
• Der Prozess der Code-Vereinfachung ist wichtig, um die eigenen Programmierfähigkeiten zu verbessern, und dieser Beitrag erklärt ihn anhand konkreter Beispiele leicht verständlich.

[GN⁺]

Hacker-News-Kommentare

• Viele stellen den Nutzen und die Verständlichkeit von Array-Sprachen infrage.

  • Array-Sprachen sind nicht für jedes Problem geeignet.
  • Für viele Arten von Problemen sind sie überraschend leistungsfähig.
  • Nutzer von Array-Sprachen sind in der Regel sehr klug.
  • Zu lernen, wie Array-Sprachen funktionieren, ist eine große Herausforderung.
  • In Array-Sprachen „prozeduralen“ Code zu schreiben, ist eine sehr schlechte Idee.
  • Das Verständnis von impliziter Programmierung (tacit programming) ist eine großartige, geist-erweiternde Erfahrung.
  • Die Erfahrung, Verbketten (verb trains) zu verinnerlichen.
  • Das Verständnis dafür, wie arraybasierte Sprachen Arrays beliebiger Dimension behandeln.
  • Das Verständnis dafür, wie under funktioniert.
  • Das Verständnis dafür, wie Funktionsexponenten (function exponents) funktionieren.

• Es gibt viele erstaunliche Aspekte von Array-Sprachen, und die obige Liste ist nur ein Teil davon.

  • Beim Zuschauen, wie Aaron Hsu einen parallelen APL-Compiler entwickelt, wurde man vom tatsächlichen Potenzial von Array-Sprachen überzeugt.
  • Diskussion über die „semantische Dichte“ von APL-Code.

• Wer noch nie von Array-Programmierung gehört hat und eine Einführung möchte, dem sei „The Array Cast“ empfohlen.

• In den 70er-Jahren APL/APL2 entdeckt und sich sofort dafür begeistert, sich aber noch stärker von der Fähigkeit angezogen gefühlt, Funktionen zu komponieren.

  • Haskell ist rein und typisiert und dadurch interessanter und mächtiger als APL.
  • APLs „Notation als Denkwerkzeug“ wirkt wie eine Logik, die übermäßige Kürze rechtfertigt.

• Die wichtigste Erkenntnis beim Arbeiten mit Array-Sprachen:

  • Verben sind Algorithmen.
  • Eine Folge von Verben (oder Adverbien) ist die direkteste Form der Komposition, die man je verwendet hat.
  • Ein Programm ist keine Menge aus Sätzen und Ausdrücken, sondern die Komposition von Algorithmen.
  • Das Konzept, Definitionsbereich und Wertebereich über Arrays, Maps und Funktionen hinweg konsistent zu behandeln.
  • Auswertung von links nach rechts, ohne dass die Augen beim Lesen des Codes „herumspringen“ müssen.
  • Es ist möglich und vorzuziehen, Code zu den Daten zu schicken.
  • Zusätzlicher Vorteil der Sprache K: Views (also Abhängigkeiten) lassen sich direkt implementieren, und Hot Code Loading über den Interpreter ist möglich.

• Frage zu Array-Sprachen: Wie erledigt man Aufgaben wie „alle Zahlen kleiner als N finden, für die Bedingung P gilt“?

  • In Array-Sprachen erzeugt man typischerweise ein Array von 1 bis N, testet die Bedingung auf dem Array und wendet dann eine Maske an, um nur die Elemente zu erhalten, für die die Bedingung wahr ist.
  • Wenn N groß ist und die Bedingung nur selten wahr ist, scheint das Erzeugen unnötig vieler temporärer Arrays eine Verschwendung von Speicher und Ressourcen zu sein.
  • Implementierungen von Array-Sprachen können solche Probleme optimieren oder mit Techniken wie Lazy Evaluation lösen.

• Erfahrung mit der Sprache J: Das Paradigma von Array-Sprachen ist voreingenommen, und es ist unklar, ob es hilfreich ist, jedes Problem als Verschachtelung von Arrays zu betrachten.

  • Frei Datenstrukturen erzeugen zu können, die ein Problem vereinfachen, kann den algorithmischen Teil stark vereinfachen.
  • Um APL/J/K zu verwenden, muss man wegen dieser Voreingenommenheit klüger sein.

• Eindruck beim Lösen von Problemen in K: Die Sprache K ist absichtlich schwer zugänglich.

  • Eine Sprache, die gut zu Rätseln und cleveren Lösungen passt, aber die Arbeit mit numpy-Arrays in Python vermittelt einem ebenfalls Array-Sprachen und das Denken in Arrays.

• Beispiel aus der Array-Sprache J: Mit dot =: +/ . * wird das Skalarprodukt von P und Q berechnet.

• Die Syntax von K ist kürzer, aber man muss viel eingebauten Kontext darüber im Kopf behalten, wie die Sprache K funktioniert.