Programmieren: Mit weniger als nichts programmieren

• Dieser Text erzählt in satirischer Form von einer Bewerbungssituation, in der ein Kandidat versucht, das einfache FizzBuzz-Problem mit reinen Funktionskombinatoren auf Basis des Lambda-Kalküls zu implementieren
• Die Hauptfigur beginnt mit JavaScript, definiert dann aber nach und nach die S-, K- und I-Kombinatoren und rekonstruiert so die grundlegende Struktur der Sprache selbst
• Anschließend werden Boolesche Werte, Zahlen, Listen und Strings ausschließlich mit Kombinatoren dargestellt, und über den Y-Kombinator wird Rekursion implementiert
• Am Ende wird FizzBuzz in einem vollständig point-free Stil fertiggestellt, doch der Code wächst zu einem Ausmaß an, das für Menschen nicht mehr verständlich ist
• Der Text erkundet auf humorvolle Weise das Wesen von Programmiersprachen und die Extreme der Abstraktion und zeigt dabei die selbstironische Seite der Entwicklerkultur

---

Der Beginn des Interviews: FizzBuzz und Kombinatoren

• Die Geschichte beginnt mit der Szene, in der die Interviewerin Dana den Kandidaten bittet, das FizzBuzz-Problem zu lösen
  • Statt einer gewöhnlichen Schleife beginnt der Kandidat damit, die S- und K-Kombinatoren zu definieren
  • Dana ist irritiert, aber der Kandidat sagt nur, dass „es gleich geschafft ist“, und macht weiter
• Der Kandidat definiert weitere Kombinatoren wie I, B, C, W, T und verwendet sie als grundlegende Bausteine einer neuen Sprache
  • Jeder Kombinator implementiert zentrale Konzepte des Lambda-Kalküls wie Funktionskomposition, Argumentvertauschung oder Selbstanwendung
  • In den Code-Kommentaren tauchen auch Spitznamen wie „Bluebird, Cardinal, Warbler, Thrush“ für diese Kombinatoren auf

Die Definition von Booleschen Werten und Zahlen

• Der Kandidat definiert TRUE, FALSE, NOT ausschließlich mit Kombinatoren und baut damit eine boolesche Logik auf
  • Dana fragt, ob das Lambda-Kalkül sei, worauf der Kandidat antwortet, das Lambda-Kalkül sei „zu aufgebläht“
• Danach definiert er ZERO, SUCC, PRED, IS_ZERO und konstruiert so ein Zahlensystem (Church numerals)
  • SUCC implementiert den Nachfolger, PRED den Vorgänger, und DECREMENT eine Verringerung, die nicht unter 0 fällt
  • Die Zahlen von ONE bis TEN werden der Reihe nach definiert

Rekursion und der Y-Kombinator

• Der Kandidat definiert die Funktion ADD und wandelt sie schrittweise in eine point-free-Form um
  • Er definiert ADD_MAKER und umhüllt es mit dem Y-Kombinator, um Rekursion zu ermöglichen
  • Dana merkt an, dass Rekursion auch in JavaScript möglich sei, doch der Kandidat erwidert, dass es „bald kein JavaScript mehr sein wird“
• Als wegen der strikten Auswertung (eager evaluation) von JavaScript ein Stack Overflow auftritt, führt der Kandidat den Code in einem „lazy“ JavaScript-Interpreter namens Skoobert aus
  • Das Ergebnis gibt erfolgreich 3 aus

Arithmetik, Listen und Strings

• Der Kandidat implementiert arithmetische Operationen wie SUBTRACT, MULTIPLY, MOD, DIVIDE vollständig auf Basis von Kombinatoren
  • Jede Operation wird rekursiv aus IS_ZERO, PRED, SUCC und ähnlichen Bausteinen zusammengesetzt
• Danach definiert er CONS, FIRST, REST, EMPTY und baut damit eine Listenstruktur auf
  • Auch funktionale Higher-Order-Operationen wie MAP, FOLD, RANGE, CONCAT werden vollständig in Kombinatorform umgesetzt
• Um Listen als Strings auszugeben, schreibt er die Funktionen renderList und showLines
  • Dana scheint inzwischen bereits aufgegeben zu haben und reagiert kaum noch

Aufbau von Zeichen und Strings

• Der Kandidat definiert Zeichencodes von 1 bis 9 sowie in 10er-Schritten mithilfe von Kombinatoren
  • Von CHAR_A bis CHAR_Z und von CHAR_0 bis CHAR_9 wird alles als Zahlenkombination ausgedrückt
• Über die Funktion ARRAY werden Strings in Listen umgewandelt und daraus FIZZ, BUZZ, FIZZBUZZ erzeugt
  • Mit extractString wird die Liste wieder in einen echten String umgewandelt
  • Die Konsolenausgabe ist "fizzbuzz"

Umwandlung von Zahlen in Strings

• Es werden NUMBER_TO_DIGIT_LIST zur Umwandlung einer Zahl in eine Liste ihrer Ziffern sowie NUMBER_TO_STRING zur Umwandlung in einen String definiert
  • Mit DIVIDE, MOD, TEN und weiteren Bausteinen werden die einzelnen Stellen getrennt
  • Über die Liste DIGITS_NUMERAL erfolgt das Mapping auf Zahlenzeichen
• Dadurch wird die Umwandlung Zahl → Zeichen → String vollständig innerhalb des Kombinator-Systems möglich

Die Vollendung von FizzBuzz

• FIFTEEN und ONE_HUNDRED werden definiert, und mit MAP und RANGE wird eine Liste von 1 bis 100 erzeugt
  • Für jede Zahl wird geprüft, ob sie ein Vielfaches von 3, 5 oder 15 ist, und entsprechend "Fizz", "Buzz", "FizzBuzz" oder der Zahlen-String ausgegeben
  • Mit showLines(extractString)(FIZZBUZZ_RESULT) wird das Endergebnis ausgegeben
• Dana fragt: „Bist du jetzt zufrieden?“, doch der Kandidat entfernt alle Variablendefinitionen und schreibt den Code nur noch mit reinen Kombinatoren neu
  • Das Ergebnis ist ein mehrere tausend Zeilen langer riesiger Ausdruck, der nur aus S und K besteht

Schluss und Bedeutung

• Der Text erforscht die grundlegenden Bausteine von Programmiersprachen und persifliert zugleich die Tendenz von Entwicklern, einfache Probleme unnötig zu verkomplizieren
  • Der Titel „Mit weniger als nichts programmieren“ symbolisiert den Versuch, die Welt aus den kleinsten Einheiten einer Sprache neu zu konstruieren
• Das Werk ist technische Literatur, die ein tiefes Verständnis von funktionaler Programmierung, Lambda-Kalkül und Kombinatorlogik mit Humor und Erzählung verbindet
  • Zugleich zeigt es satirisch den „Entwicklergeist, der sogar FizzBuzz in ein philosophisches Experiment verwandelt“

[GN⁺]

Hacker-News-Kommentare

• Da viele sich offenbar fragen „Was soll das eigentlich?“, hier der Kernpunkt von combinatorn:
  Ein combinator ist eine Funktion, die keinen globalen Zustand verändert und keine externen Variablen einfängt. Gibt man ihr dieselben Argumente, liefert sie immer dasselbe Ergebnis und beeinflusst den Rest des Systems überhaupt nicht.
  Kombiniert man solche reinen Funktionen, entsteht wieder ein weiterer combinator. Das heißt: Die Komposition reiner Funktionen bleibt weiterhin eine reine Funktion.
  Solche Funktionen lassen sich auch problemlos in Assembler oder C schreiben. Wenn man zum Beispiel S und K direkt auf x64 implementiert und darauf Common Lisp combinator-basiert kompiliert, läuft Lisp letztlich auf zwei Assemblerfunktionen.
  Die Performance wäre wohl nicht besonders gut, aber wenn man ein paar Hundert häufig verwendete Muster als Inline-Combinator definiert und benennt, wird daraus eine durchaus praktische „Maschine“.
  Diese Struktur ähnelt auch Forth, das mutation scheut, einer Bytecode-VM oder einer CPU, die combinatoren als „Instruktionen“ bezeichnet.
  Letztlich kann man combinatoren als einen Ausdruck der angewandten Informatik verstehen, bei dem Implementierungsdetails so weit wie möglich ignoriert werden. Deshalb kann man sagen, dass sie einfacher als Lambda-Kalkül sind.
  Wenn man Lambda-Kalkül mit einigen combinatoren implementiert und darauf Lisp aufsetzt, reduziert sich die Menge an maschinenabhängiger Arbeit ganz unten im Stack extrem.

  • Ich habe das Gefühl, irgendwo hat sich eine Funktion selbst aufgerufen und dabei eine seed round bekommen.
  • Ich habe als Student einmal etwas Ähnliches gemacht (kein Lisp, sondern eine kleine Sprache, die in Lambda-Kalkül makroexpandiert wurde), und es war wirklich schockierend, dass sich alles nur mit S und K umsetzen lässt. Gleichzeitig war es aber auch erstaunlich, wie ineffizient das ist. Mit größerem Instruktionssatz wird es allerdings deutlich besser.
  • Theoretisch geht das alles, aber praktisch sollte man eine wesentlich brauchbarere Grundlage für Computing wählen als Graph Rewriting. Wenn man nicht gerade die Grenzen der Berechenbarkeit ausloten will, ist das fast nur ein Partytrick. Dazu kommt noch das Problem der Zahlendarstellung. Wenigstens Zweierkomplement-Integer und effiziente Destruktoren braucht man, damit es wirklich beeindruckend wird.
  • Ich frage mich, ob es tatsächlich ein auf combinatoren implementiertes Lisp gibt. Falls ja, wäre das vermutlich ziemlich unterhaltsam zu portieren.

• let A = (x) => (y) => (z) => x(z)(y((w) => z))
  

  Das muss man nur ein paarmal zusammensetzen.

  let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A);
  let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A);
  

  „Ich benutze niemals Lambda-Kalkül. Das ist eine viel zu aufgeblähte Sprache.“
  Tatsächlich ist combinatory logic aber noch aufgeblähter. Um dasselbe Programm auszudrücken, braucht man mehr Bits.
  Lambda-Kalkül ist vielmehr eine der kompaktesten Sprachen, die es gibt.
  Selbst in einer eager Sprache wie JavaScript kann man etwas lazy machen, indem man Argumente in Dummy-Lambdas verpackt. Ein Beispiel gibt es in diesem JS-BLC-Interpreter.
  Siehe dazu auch dieses PDF und das IOCCC-Beispiel.

  • Interessant ist, dass die schnellsten Lambda-Kalkül-Interpreter (z. B. uni.c) Lambda-Ausdrücke letztlich in combinatory logic umwandeln und so auswerten. Sie verwenden nur eine größere Grundmenge als S und K.
  • Mit „bloated language“ ist eine Sprache mit unnötig vielen Features gemeint. C++ ist zum Beispiel vielleicht kürzer als C, aber trotzdem eine viel komplexere Sprache.
  • Wenn ich mir diesen Codeblock anschaue, klingen die Laute, die mir dabei entweichen, fast genauso wie die Argumentlisten.
  • In den Definitionen von K und S scheint ein Klammerfehler zu sein. Die korrigierte Version ist:

    let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A));
    let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)(A(A)))))))(A)(A);
    

    Und eine eager Sprache kann man ungefähr so lazy machen:

    let A = x => y => z => () => x()(z())(y()(w => z()));
    

  • Man fragt sich unweigerlich: „Was ist eigentlich w?“

• „Kennst du FizzBuzz?“
  „Natürlich. Die 10-Zeichen-Codegolf-Version, die 12-Zeilen-Version, die selbst ein Junior versteht, oder die völlig absurde Version zum Angeben mit obskurem Wissen?“

  • Nachdem ich das gesehen hatte, habe ich das schnellste FizzBuzz in C64 BASIC implementiert. Ein unterhaltsam verschwendeter Morgen.
    Ergebnislink

• Die Erklärung von combinator logic war wirklich großartig. Der Schreibstil erinnerte mich an diese Serie.

  • Weniger eine Erklärung als vielmehr eine Vorführ-Performance. Trotzdem ziemlich eindrucksvoll.
  • Scheint definitiv von dieser Serie inspiriert zu sein. Es wäre noch besser gewesen, den Autor namentlich zu erwähnen.
  • Schade, dass der Zugriff in Großbritannien wegen des Online Safety Act blockiert ist.

• Das erinnerte mich an den Artikel „FizzBuzz in TensorFlow“, den ich vor Jahren gelesen habe.
  Link

  • Diesem Artikel hier konnte ich wenigstens noch folgen.

• Dieses Framing von Programmierinterviews wirkt etwas verfehlt.
  Der Zweck eines Interviews ist, (1) das Programmierwissen des Bewerbers zu prüfen und (2) zu sehen, ob er zur Programmierkultur des Unternehmens passt.
  Wenn man zum Beispiel für eine JavaScript-Position rekrutiert und jemand tief in combinatory logic steckt, passt das kulturell womöglich nicht. Dann ist eine Absage auch nicht seltsam.

  • Vermutlich ist diese Serie die Referenz, auch wenn das im Originaltext nicht ausdrücklich gesagt wird.
  • Manchmal wirken HN-Kommentatoren, als hätten sie jeden Sinn für Spaß verloren.
  • Die Vielfalt des Programmierens zu betonen ist schon richtig, aber das ist eben nur eine Art, Spezialisten für ein bestimmtes Ökosystem auszuwählen. Meistens geht es dabei um Legacy-Code oder darum, ein bestehendes Ökosystem zu nutzen.
  • Aussagen wie „wer einen niedrigen IQ hat, fällt durch“ sind zwar lächerlich, aber letztlich kann man sich bei genug Geld an jeden OOP/FP/FRP-Stil anpassen.
  • In der Realität gibt es solche idealen Interviews fast nie. Meist sind es frustrierte Interviewer, die ihr eigenes Weltbild durchdrücken. Mit der tatsächlichen Arbeit hat das meist fast nichts zu tun.

• Es ist Zeit, sich an Moses Schönfinkel zu erinnern.
  Er erfand 1920 als Schüler Hilberts die combinatory logic. Nach seiner Rückkehr nach Russland litt er an psychischen Erkrankungen und starb verarmt in Moskau. Laut Wikipedia wurden seine Aufsätze von Nachbarn zum Heizen verbrannt.

• Der letzte Codeblock ist so groß, dass ein Scrollbalken erscheint (166 KB).
  S und K sind curried Funktionen, die immer nur ein Argument gleichzeitig annehmen.
  Mehr dazu in dieser StackOverflow-Antwort.

  • Am lustigsten war der Moment beim Scrollen, in dem das Syntax-Highlighting einfach aufgegeben hat.

• Ich liebe diese Vogelnamen wie „Bluebird, cardinal, warbler, thrush“. Ich möchte das als neue Benennungskonvention übernehmen.
  „Barendregt. Church ist doch viel zu Mainstream.“
  „Bald ist es nicht mal mehr JavaScript.“
  Es wirkt, als würde Douglas Adams SICP unterrichten.

  • Die Vogelnamen stammen aus Smullyans To Mock a Mockingbird. Dort kommen noch viele weitere Vögel vor.

• „Ist das also … der Y combinator?“
  „Genau. Für Rekursion braucht man ihn.“
  Fun Fact: Es gibt unendlich viele Fixpunktkombinatoren. Man kann Rekursion also auf unendlich viele Arten auch ohne den Y combinator implementieren.