Un Lisp implémenté avec des macros Rust

lisp-in-rs-macros

Un interpréteur Lisp simple à portée lexicale, entièrement fonctionnel, implémenté avec les macros déclaratives de Rust. La macro lisp! développe une valeur Lisp calculée par le code et la convertit en chaîne. Par exemple, lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) se développe en la chaîne "A", et tous les calculs ont lieu à la compilation lorsque rustc développe les macros.

Pourquoi c'est important

Un interpréteur Lisp écrit avec des macros Rust, ce qui est très intéressant. De plus, il tient en moins de 250 lignes, ce qui le rend très concis.

Exemples

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))
); // affiche "hello there" et "TRUE"

Un autre exemple amusant est un quine :

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

Ce code s'évalue lui-même.

Récursion

Ce Lisp ne prend pas actuellement en charge une forme explicite de récursion. Heureusement, la récursion explicite n'est pas nécessaire : il suffit d'avoir des lambdas. On peut écrire une fonction simple qui concatène deux listes :

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

Le résultat est alors "(A B C D)". La fonction append ne mentionne pas append dans son corps, mais elle peut quand même s'appeler récursivement.

Points d'attention à l'utilisation

• La macro lisp! n'évalue qu'une seule expression. Pour en évaluer plusieurs, il faut utiliser (PROGN expr1 expr2 expr3).
• La forme DISPLAY génère une instruction println!("{}", stringify!(...)) après avoir évalué une seule expression, afin d'afficher la version textuelle des tokens.
• La liste vide ne s'auto-évalue pas ; pour obtenir la valeur de liste vide, il faut utiliser NIL ou (QUOTE ()).
• Les listes pointées ne sont pas prises en charge, et cons suppose que son dernier argument est une liste.
• La forme define peut être utilisée n'importe où et s'évalue en liste vide, mais elle ne prend pas en charge la récursion.
• TRUE est le seul atome auto-évalué qui ne soit pas une fonction.

Formes prises en charge

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

Interpréteur métacirculaire

Voici un interpréteur Lisp écrit en Lisp :

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

Ce code fonctionne, mais si l'on essaie d'évaluer ((lambda (X) X) (quote a)) dans l'interpréteur, cela prend plus de 30 secondes et génère plus d'un million de tokens. La récursion via un combinateur Y explicite n'est pas efficace ici. Pour corriger cela, il faudrait ajouter une primitive de récursion explicite. Pour une excellente explication de la manière d'écrire un évaluateur métacirculaire, voir "Roots of Lisp" de Paul Graham.

Explication technique

Voir EXPLANATION.md. Les macros simulent la machine SECD, une machine abstraite simple basée sur une pile pour évaluer le lambda-calcul.

Excellentes ressources

• "Functional Programming: Application and Implementation" de Peter Henderson
• "A functional correspondence between evaluators and abstract machines." (2003), de Mads Sig Ager et autres
• "The Implementation of Functional Programming Languages" de Simon Peyton Jones
• Tous les articles sur Lisp du blog de Matt Might (https://matt.might.net)

TODO

• Ajouter letrec
• Ajouter les définitions récursives

Résumé GN⁺

• L'interpréteur Lisp écrit avec des macros Rust est très intéressant et offre des capacités puissantes avec un code concis.
• Il ne prend pas explicitement en charge la récursion, mais celle-ci peut être implémentée via des lambdas.
• L'interpréteur métacirculaire n'étant pas efficace, il est nécessaire d'ajouter une primitive de récursion explicite.
• "Roots of Lisp" de Paul Graham est une excellente ressource pour comprendre les évaluateurs métacirculaires.
• Parmi d'autres projets offrant des fonctionnalités similaires, on peut recommander des interpréteurs Scheme ou d'autres variantes de Lisp.