In Rust-Makros implementiertes Lisp

 (github.com/RyanWelly)
1 Punkte von GN⁺ 2024-09-15 | 1 Kommentare | Auf WhatsApp teilen
  • lisp-in-rs-macros ist ein einfacher Lisp-Interpreter mit lexikalischem Scope, der ausschließlich mit deklarativen Makros in Rust arbeitet; das Makro lisp! wertet Code zur Compile-Zeit aus und erzeugt einen in einen String umgewandelten Lisp-Wert
  • lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) wird während des Makro-Erweiterungsprozesses von rustc berechnet und zu dem String "A" expandiert; die gesamte Implementierung umfasst weniger als 250 Zeilen
  • Die Beispiele verwenden CAR, LIST, QUOTE, PROGN, DEFINE, LAMBDA, DISPLAY, und das Quine-Beispiel zeigt eine Form, in der Lisp-Code zu sich selbst ausgewertet wird
  • Explizite Rekursion wird derzeit nicht unterstützt, aber mit self application lassen sich rekursive Abläufe wie das Anhängen von Listen schreiben; DEFINE selbst verarbeitet jedoch keine rekursiven Definitionen
  • Das Beispiel eines metazirkulären Interpreters scheint zu funktionieren, ist aber extrem ineffizient: Die Auswertung von ((lambda (X) X) (quote a)) dauert über 30 Sekunden und erzeugt mehr als eine Million Tokens, sodass cargo per sigkill beendet wird

Lisp, das in Rust-Makros läuft

  • lisp-in-rs-macros ist ein Lisp-Interpreter mit lexikalischem Scope, der vollständig mit deklarativen Makros in Rust geschrieben ist
  • Das Makro lisp! wertet den übergebenen Lisp-Code aus und wandelt anschließend den berechneten Lisp-Wert in einen String um
  • Zum Beispiel expandiert lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) zu dem String "A"
  • Diese Berechnung geschieht nicht zur Laufzeit, sondern durch rustc zur Compile-Zeit bei der Makro-Erweiterung
  • Die Implementierung umfasst weniger als 250 Zeilen

Grundlegende Verwendungsbeispiele

  • Durch die Kombination von CAR, LIST und QUOTE kann das erste Element einer Liste geholt werden
let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");
  • Um mehrere Ausdrücke auszuwerten, wird PROGN verwendet
    • PROGN wertet alle Ausdrücke aus und gibt den Wert des letzten Ausdrucks zurück
  • DISPLAY wertet zuerst sein Argument aus und expandiert dann in der Form println!("{}", stringify!(evaled_argument)), um die Tokens in einen String umzuwandeln und auszugeben
lisp!(PROGN
    (DEFINE message (LAMBDA () (QUOTE "hello there")))
    (DISPLAY (message))
    (DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))) )
    (DISPLAY (NOT NIL))
);
  • Das obige Beispiel gibt "hello there" und "TRUE" aus

Quine, das sich selbst auswertet

  • Das Quine-Beispiel zeigt eine Form, in der Lisp-Code zu sich selbst ausgewertet wird
lisp!
       ((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));
  • Dieser Code expandiert zu einem stringify!-Aufruf wie dem folgenden
stringify!(((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))))));

Rekursion und self application

  • Dieses Lisp unterstützt derzeit keine explizite Rekursion
  • Auch ohne explizite Rekursion lässt sich mit Lambda allein rekursives Verhalten erzeugen
  • Die append-Funktion im Beispiel erwähnt den Namen append im Rumpf nicht direkt, sondern führt rekursive Aufrufe über Selbstanwendung mit dem Argument self aus
lisp!(PROGN
(DEFINE append
    (LAMBDA (self X Y)
        (COND
            ((EQ X NIL) Y)
            (TRUE (CONS (CAR X) (self self (CDR X) Y)))
        )))
(append append (QUOTE (A B)) (QUOTE (C D)))

)
  • Dieser Code erzeugt als Ergebnis "(A B C D)"

Einschränkungen bei der Verwendung

  • Das Makro lisp! wertet nur einen einzelnen Ausdruck aus
    • Mehrere Ausdrücke müssen mit (PROGN expr1 expr2 expr3) gebündelt werden
  • Die leere Liste ist nicht self-evaluating
    • Der Wert der leeren Liste kann mit NIL oder (QUOTE ()) erhalten werden
    • Die leere Liste ist das einzige falsy Objekt
  • Dotted Lists werden nicht unterstützt
    • CONS setzt voraus, dass das letzte Argument eine Liste ist
  • DEFINE kann überall verwendet werden und wird zur leeren Liste ausgewertet, unterstützt aber keine Rekursion
  • TRUE ist das einzige self-evaluating Atom, das keine Funktion ist

Unterstützte Formen

DEFINE
QUOTE
LAMBDA
LET
PROGN
CAR
CDR
CONS
LIST
EQ
ATOM
APPLY
  • DEFINE ist eher eine Form ähnlich internen Definitionen in Scheme als eine echte rekursive Definition im Lisp-Stil

Ein in Lisp geschriebener Lisp-Interpreter

  • Das Repository enthält ein Beispiel für einen metazirkulären Interpreter, der auf diesem Lisp geschrieben ist
  • Das Beispiel definiert einen Y2-Kombinator für zwei Argumente, CADR, CAAR, ASSOC, eval und mehr
  • Der Interpreter scheint zu funktionieren, aber der Versuch, ((lambda (X) X) (quote a)) auszuwerten, dauert über 30 Sekunden
  • Diese Auswertung erzeugt mehr als eine Million Tokens und wächst schließlich so stark, dass cargo per sigkill beendet wird
  • Rekursion mit einem expliziten Y-Kombinator ist hier besonders ineffizient
  • Um das zu beheben, wird vorgeschlagen, ein explizites Rekursions-Primitive hinzuzufügen
  • Als Walkthrough zum Schreiben eines metazirkulären Evaluators wird Paul Grahams "Roots of Lisp" empfohlen

Implementierungsansatz und Referenzen

  • Die technische Erklärung steht in EXPLANATION.md
  • Die Makros simulieren im Kern eine SECD machine
    • Die SECD machine ist eine einfache stapelbasierte abstrakte Maschine zur Auswertung von Lambda-Kalkül-Termen

Referenzen

  • Functional Programming: Application and Implementation von Peter Henderson
  • Ager, Mads Sig, et al. "A functional correspondence between evaluators and abstract machines."
  • The Implementation of Functional Programming Languages von Simon Peyton Jones
  • Matt Mights Blogbeiträge zu Lisp: https://matt.might.net

TODO

  • letrec hinzufügen
  • Rekursives define hinzufügen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-09-15
Hacker-News-Kommentare

  • Greenspuns zehntes Gesetz schlägt wieder zu: https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

    • Es geht hier eher um Codebasen, deren Hauptzweck nicht die Implementierung von Lisp ist, also passt es hier nicht ganz.
    • Ein gutes Beispiel für dieses Gesetz ist, dass C++ innerhalb seiner Templatesprache car/cdr in gletscherhaft langsamem Tempo neu erfindet.
      Erst mit C++26 wird man mit Args...[0] an das car eines Type-Name-Parameter-Packs kommen können.
      Ich verstehe nicht, warum man nicht einfach nil sowie car/cdr-Funktionen für leere Parameter-Packs einführt und es erlaubt, Parameter-Packs zu speichern, statt des jetzigen syntaktischen Durcheinanders.
    • Dabei fällt mir sofort der Satz ein: „Jedes hinreichend komplexe C- oder Fortran-Programm enthält eine Ad-hoc-, informell spezifizierte, fehlerhafte und langsame Implementierung der Hälfte von Common Lisp.“
    • Ich weiß nicht, was „hinreichend komplex“ genau bedeuten soll; das ist ziemlich schwammig definiert.

  • Ich habe früher einmal etwas Ähnliches gemacht, und dabei gab es das Problem, dass man Symbole mit Bindestrichen nicht definieren konnte.
    So etwas wie DEFINE MY-FN... ging nicht, weil Rust am Bindestrich den Token trennt.
    Das ist nur ein kleiner Unterschied, aber in der Praxis konnte man echte Lisp-Codefragmente nicht einfach hineinkopieren und musste alles in Unterstriche umwandeln. Ich frage mich, ob diese Implementierung dasselbe Problem hat.

    • Im Moment wird davon ausgegangen, dass alle Atome Rust-Identifier sind. Das vereinfacht die Implementierung, weil man dann mit $x:ident matchen kann, und deshalb werden Bindestriche in Atomen nicht unterstützt.
      Stattdessen müsste man wohl so etwas wie $x:ident $(- $y:ident)* matchen. Ein paar Details in einigen Makro-Zweigen müsste man ändern, aber es scheint machbar.
    • Sieht für mich nicht nach einem Problem aus? DEFINE MYᜭFN... funktioniert einwandfrei.

  • Es wäre schön, nicht nur Makros zu haben, sondern eine gut unterstützte Lisp-Implementierung auf Basis von Rust.
    Ich frage mich, wie viel Speichersicherheit man behält oder verliert, wenn man sie auf Rust aufsetzt. Ob sich der Borrow Checker auf eine vernünftige Weise überhaupt nutzen ließe?

    • Einige Lisp-Compiler wie SBCL können auch umfangreichere Typprüfungen zur Compile-Zeit durchführen, aber diese Informationen müssen vom Programmierer bereitgestellt werden und gehören meist eher zur Optimierungsphase als zur alltäglichen inkrementellen Entwicklung.
      Lisp wird üblicherweise über seine dynamische Natur definiert, und Laufzeit-Typprüfungen machen einen großen Teil davon aus. Wenn man vom Programmierer verlangt, sich im Voraus Gedanken über die Objektverwaltung zu machen, kollidiert das mit der Freiheit und Ausdrucksstärke, die man von solchen Systemen erwartet.
      Dafür kann der Compiler selbst vergleichsweise einfach sein. Gewöhnlicher Code ohne zusätzliche Deklarationen ist standardmäßig sicher, und in Bytecode-VMs wie CLISP oder auf Lisp-Maschinen mit Hardware-Typprüfung könnten solche Deklarationen sogar ignoriert werden und trotzdem immer sicher bleiben.
      SBCL kompiliert Code ziemlich schnell, und ich habe gehört, dass andere Implementierungen noch schneller sind. Dagegen dürfte der Rust-Compiler jungen Programmierern eher den Begriff Thrashing näherbringen.
      Ich denke, das sind zwei Welten, die weit weniger kompatibel sind, als es auf den ersten Blick scheint. Lisp ist im Kern die Vorzeigesprache der Philosophie „The Right Thing“, und C ist eine Sprache von „Worse is Better“. Rust ist keines von beidem; es wirkt wie etwas völlig anderes, das einen neuen Namen braucht, weil es die schlechten Eigenschaften beider Philosophien widerspiegelt.
      Das soll den ursprünglichen Beitrag aber nicht herabsetzen, es ist trotzdem ein cooler Hack.
    • Steel sieht ganz ordentlich aus: https://github.com/mattwparas/steel
      Es gibt auch andere Lisps (https://github.com/alilleybrinker/langs-in-rust). Sie scheinen allerdings weniger aktiv gepflegt zu werden.

  • Es hat beim Bauen Spaß gemacht, und ich habe außerdem gelernt, dass rust-analyser keine Makros verarbeiten kann, die mehrere Millionen Tokens erzeugen.

  • Eigentlich soll hier wohl jeder begeistert „macht Spaß“ rufen, aber immer wenn ich so etwas sehe, gefällt mir nicht, dass Rust so etwas überhaupt möglich macht.
    Rust war ohnehin nie eine einfache Sprache, aber inzwischen wirkt sie auf mich deutlich schwerer beherrschbar als am Anfang.

    • Ich stimme zu, dass Rust keine einfache Sprache ist.
      Ich verstehe nur nicht ganz, warum du es schlimm findest, dass so etwas möglich ist. Das Makrosystem kann zwar fast unendlich komplexen Code erzeugen, aber ich weiß nicht, ob eine in Makros eingesperrte Lisp-Implementierung wirklich ein starkes Beispiel dafür ist, dass Rust schwerer wartbar geworden ist als früher.
      Andererseits würde ich auch gern ein Lisp sehen, das mit Rusts Typsystem umgesetzt ist, einfach weil dessen Typsystem wie C++-Templates oder Haskells Typsystem Turing-vollständig ist.
    • Dem würde ich deutlich widersprechen. Das Rust-Team entfernt fortlaufend Einschränkungen und macht Features orthogonaler, damit die Sprache leichter zu verwenden bleibt.
      Gute Beispiele dafür sind non-lexical lifetimes, impl Trait an der Rückgabeposition und asynchrone Traits. Vor 1.0 gab es sogar eingebaute GC-Referenzen mit spezieller Syntax, und solche Features wurden auch wieder entfernt.
    • Die einzige wirklich große praktische Änderung seit 1.0 ist async. Wenn du ohne async leben willst, ist das völlig optional und ein komplett wählbarer Teil der Sprache.
      Wenn du eine Sprache willst, deren Prinzip Einfachheit ist, dann war Rust nie so eine Sprache, und es gibt viele andere Optionen.
    • Tatsächlich braucht es gar nicht viel, damit so etwas möglich wird. Ich glaube, das ginge sogar mit den C-Makros, die als einfach gelten.
      Ich habe nachgesehen, und ich habe diese Wette gewonnen: https://github.com/kchanqvq/CSP
    • Sind Makros nicht schon immer sowohl sehr mächtig als auch gleichzeitig knifflig gewesen? Ich würde die Makro-Seite nicht zur Sprachkomplexität dazuzählen.
      Vor allem meine ich die Seite des „Schreibens“ von Makros; ich sehe das eher als optionales Zusatzfeature, das man nutzen kann, aber nicht muss.

  • Wow, das verwendet tatsächlich macro_rules.

  • Aber hieß es nicht immer, C++ sei keine vernünftige Sprache, weil Templates Turing-vollständig sind?

    • C++ ist schon keine vernünftige Sprache, wenn man nur ein bisschen darüber weiß. Zumindest sind Rust-Makros keine wortwörtliche Textersetzung; das ist ein Schritt ins Licht.
    • Turing-vollständig und ein Turing-Tarpit sind nicht dasselbe.
      Ich weiß nicht, zu welcher Kategorie Rusts Makrosystem gehört.
    • Mit C++-Templates zu entwickeln ist die Hölle. In Rust gibt es wenigstens macro_expand, und auch die Rust-Tools sind ziemlich gut gemacht.

  • Carp darf man auch nicht vergessen. Ein Lisp mit Borrow Checker, so etwas wie das „Rust“ der Lisp-Welt.
    1: https://github.com/carp-lang/Carp