In Rust-Makros implementiertes Lisp

 (github.com/RyanWelly)
1 Punkte von GN⁺ 2024-09-15 | Noch keine Kommentare. | Auf WhatsApp teilen

lisp-in-rs-macros

Ein einfacher Lisp-Interpreter mit lexikalischem Scope, der vollständig mit deklarativen Makros in Rust funktioniert. Das Makro lisp! expandiert zu Lisp-Werten, die vom Code berechnet und in Strings umgewandelt werden. Zum Beispiel expandiert lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) zu dem String "A", und alle Berechnungen finden zur Compile-Zeit statt, wenn rustc die Makros expandiert.

Warum das wichtig ist

Ein in Rust-Makros geschriebener Lisp-Interpreter ist äußerst interessant. Außerdem ist er mit weniger als 250 Zeilen sehr kompakt.

Beispiele

let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");

lisp!(PROGN
  (DEFINE message (LAMBDA () (QUOTE "hello there")))
  (DISPLAY (message))
  (DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))))
  (DISPLAY (NOT NIL))
); // gibt "hello there" und "TRUE" aus

Ein weiteres interessantes Beispiel ist ein Quine:

lisp!((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))) (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));

Dieser Code wertet sich selbst aus.

Rekursion

Dieses Lisp unterstützt derzeit keine explizite Form von Rekursion. Glücklicherweise braucht man keine explizite Rekursion, sondern nur Lambdas. Man kann eine einfache Funktion schreiben, die zwei Listen zusammenfügt:

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)))
);

Das Ergebnis ist "(A B C D)". Die Funktion append erwähnt append im Funktionskörper nicht, kann aber dennoch rekursiv aufgerufen werden.

Hinweise zur Nutzung

  • Das Makro lisp! wertet nur einen einzelnen Ausdruck aus. Um mehrere Ausdrücke auszuwerten, muss (PROGN expr1 expr2 expr3) verwendet werden.
  • Die Form DISPLAY erzeugt nach der Auswertung eines einzelnen Ausdrucks eine println!("{}", stringify!(...))-Anweisung und gibt die String-Version der Tokens aus.
  • Die leere Liste wertet sich nicht selbst aus; um einen leeren Listenwert zu erhalten, muss NIL oder (QUOTE ()) verwendet werden.
  • Punktlisten werden nicht unterstützt, und cons geht davon aus, dass das letzte Argument eine Liste ist.
  • Die Form define kann überall verwendet werden und wertet zu einer leeren Liste aus, unterstützt aber keine Rekursion.
  • TRUE ist das einzige sich selbst auswertende Atom, das keine Funktion ist.

Unterstützte Formen

  • DEFINE
  • QUOTE
  • LAMBDA
  • LET
  • PROGN
  • CAR
  • CDR
  • CONS
  • LIST
  • EQ
  • ATOM
  • APPLY

Metazirkulärer Interpreter

Das Folgende ist ein in Lisp geschriebener Lisp-Interpreter:

lisp!(PROGN
  (DEFINE Y2
    (LAMBDA (h)
      ((LAMBDA (x) (h (LAMBDA (a b) ((x x) a b))))
        (LAMBDA (x) (h (LAMBDA (a b) ((x x) a b)))))))
  (DEFINE CADR (LAMBDA (X) (CAR (CDR X))))
  (DEFINE CAAR (LAMBDA (X) (CAR (CAR X))))
  (DEFINE CADAR (LAMBDA (X) (CAR (CDR (CAR X)))))
  (DEFINE CADDR (LAMBDA (X) (CAR (CDR (CDR X)))))
  (DEFINE CADDAR (LAMBDA (X) (CAR (CDR (CDR (CAR X))))))
  (DEFINE CAADAR (LAMBDA (X) (CAR (CAR (CDR (CAR X))))))
  (DEFINE ASSOC (Y2 (LAMBDA (ASSOC) (LAMBDA (X ENV)
    (IF (EQ (CAAR ENV) X) (CADAR ENV) (ASSOC X (CDR ENV))))))
  )
  (DEFINE eval (Y2 (LAMBDA (EVAL) (LAMBDA (E A)
    (COND
      ((ATOM E) (ASSOC E A))
      ((ATOM (CAR E))
        (COND
          ((EQ (CAR E) (QUOTE quote)) (CADR E))
          ((EQ (CAR E) (QUOTE atom)) (ATOM (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE car)) (CAR (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE cdr)) (CDR (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE equal)) (EQ (EVAL (CADR E) A) (EVAL (CADDR E) A)))
          ((EQ (CAR E) (QUOTE cons)) (CONS (EVAL (CADR E) A) (EVAL (CADDR E) A)))
          (TRUE (EVAL (CONS (ASSOC (CAR E) A) (CDR E)) A))
        ))
      ((EQ (CAAR E) (QUOTE lambda)) (EVAL (CADDAR E) (CONS (LIST (CAADAR E) (EVAL (CADR E) A)) A)))
    ))))
  )
  (eval (QUOTE (quote (A))) NIL)
  (eval (QUOTE ((lambda (X) X) (quote a))) NIL)
);

Dieser Code funktioniert, aber wenn man im Interpreter ((lambda (X) X) (quote a)) auszuwerten versucht, dauert das mehr als 30 Sekunden und erzeugt über eine Million Tokens. Rekursion mit einem expliziten Y-Kombinator ist hier nicht effizient. Um das zu lösen, muss eine explizite Rekursions-Primitive hinzugefügt werden. Eine hervorragende Erklärung zum Schreiben eines metazirkulären Evaluators findet sich in Paul Grahams "Roots of Lisp".

Technische Erklärung

Siehe EXPLANATION.md. Die Makros simulieren eine SECD-Maschine, eine einfache stackbasierte abstrakte Maschine zur Auswertung von Lambda-Kalkül-Ausdrücken.

Hervorragende Materialien

  • Peter Hendersons "Functional Programming: Application and Implementation"
  • "A functional correspondence between evaluators and abstract machines." (2003) von Mads Sig Ager u. a.
  • Simon Peyton Jones' "The Implementation of Functional Programming Languages"
  • Alle Artikel über Lisp im Blog von Matt Might (https://matt.might.net)

TODO

  • letrec hinzufügen
  • rekursive Definitionen hinzufügen

Zusammenfassung von GN⁺

  • Der in Rust-Makros geschriebene Lisp-Interpreter ist äußerst interessant und bietet mit kompaktem Code leistungsstarke Funktionen.
  • Obwohl explizite Rekursion nicht unterstützt wird, lässt sich Rekursion über Lambdas implementieren.
  • Der metazirkuläre Interpreter ist nicht effizient, daher ist das Hinzufügen einer expliziten Rekursions-Primitive notwendig.
  • Paul Grahams "Roots of Lisp" ist eine hervorragende Ressource, um metazirkuläre Evaluatoren zu verstehen.
  • Als andere Projekte mit ähnlicher Funktionalität werden Scheme-Interpreter oder andere Lisp-Varianten empfohlen.

Verwandte Beiträge

Noch keine Kommentare.

Noch keine Kommentare.