Un Lisp implémenté avec des macros Rust

 (github.com/RyanWelly)
1 points par GN⁺ 2024-09-15 | 1 commentaires | Partager sur WhatsApp
  • lisp-in-rs-macros est un interpréteur Lisp simple à portée lexicale qui fonctionne uniquement avec les macros déclaratives de Rust, et la macro lisp! évalue le code à la compilation pour produire une valeur Lisp convertie en chaîne
  • lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) est calculé pendant l’expansion des macros par rustc et se développe en la chaîne "A" ; l’implémentation complète fait moins de 250 lignes
  • Les exemples utilisent CAR, LIST, QUOTE, PROGN, DEFINE, LAMBDA, DISPLAY, et l’exemple de quine montre du code Lisp qui s’évalue en lui-même
  • La récursion explicite n’est pas prise en charge pour l’instant, mais il est possible d’écrire des comportements récursifs comme un append de liste via la self application ; en revanche, DEFINE lui-même ne gère pas les définitions récursives
  • L’exemple d’interpréteur métacirculaire semble fonctionner, mais l’évaluation de ((lambda (X) X) (quote a)) prend plus de 30 secondes et génère plus d’un million de tokens, au point que cargo finit tué par sigkill, ce qui le rend très inefficace

Un Lisp qui s’exécute dans les macros Rust

  • lisp-in-rs-macros est un interpréteur Lisp à portée lexicale écrit uniquement avec les macros déclaratives de Rust
  • La macro lisp! évalue le code Lisp fourni, puis convertit en chaîne la valeur Lisp calculée
  • Par exemple, lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) se développe en la chaîne "A"
  • Ce calcul n’a pas lieu à l’exécution, mais à la compilation, pendant l’expansion des macros par rustc
  • L’implémentation fait moins de 250 lignes

Exemple d’utilisation de base

  • En combinant CAR, LIST et QUOTE, on peut récupérer le premier élément d’une liste
let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");
  • Pour évaluer plusieurs expressions, on utilise PROGN
    • PROGN évalue toutes les expressions et renvoie la valeur de la dernière
  • DISPLAY évalue d’abord son argument, puis se développe sous la forme println!("{}", stringify!(evaled_argument)) afin d’afficher les tokens convertis en chaîne
lisp!(PROGN
    (DEFINE message (LAMBDA () (QUOTE "hello there")))
    (DISPLAY (message))
    (DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))) )
    (DISPLAY (NOT NIL))
);
  • L’exemple ci-dessus affiche "hello there" et "TRUE"

Un quine qui s’évalue en lui-même

  • L’exemple de quine montre du code Lisp qui s’évalue en lui-même
lisp!
       ((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));
  • Ce code se développe en l’appel stringify! suivant
stringify!(((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))))));

Récursion et self application

  • Ce Lisp ne prend actuellement pas en charge la récursion explicite
  • Même sans récursion explicite, il est possible de créer des comportements récursifs avec uniquement des lambda
  • Dans l’exemple, la fonction append ne mentionne jamais directement le nom append dans son corps ; elle effectue l’appel récursif via auto-application au moyen de l’argument self
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)))

)
  • Ce code produit "(A B C D)"

Contraintes d’utilisation

  • La macro lisp! n’évalue qu’une seule expression
    • Pour plusieurs expressions, il faut les regrouper dans (PROGN expr1 expr2 expr3)
  • La liste vide n’est pas auto-évaluée
    • On peut obtenir la valeur liste vide avec NIL ou (QUOTE ())
    • La liste vide est le seul objet falsy
  • Les dotted lists ne sont pas prises en charge
    • CONS suppose que son dernier argument est une liste
  • DEFINE peut être utilisé n’importe où et s’évalue en liste vide, mais la récursion n’est pas prise en charge
  • 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
  • DEFINE est plus proche des définitions internes de Scheme que d’une vraie définition récursive à la Lisp

Un interpréteur Lisp écrit en Lisp

  • Le dépôt contient un exemple d’interpréteur métacirculaire écrit dans ce Lisp
  • L’exemple définit un combinateur Y2 à deux arguments, CADR, CAAR, ASSOC, eval, etc.
  • L’interpréteur semble fonctionner, mais évaluer ((lambda (X) X) (quote a)) prend plus de 30 secondes
  • Cette évaluation génère plus d’un million de tokens et finit par grossir au point que cargo se fait tuer par sigkill
  • La récursion avec un combinateur Y explicite est ici particulièrement inefficace
  • L’auteur indique qu’il faudrait ajouter une primitive de récursion explicite pour corriger cela
  • Pour un walkthrough sur l’écriture d’un évaluateur métacirculaire, "Roots of Lisp" de Paul Graham est recommandé

Implémentation et ressources

  • Les explications techniques se trouvent dans EXPLANATION.md
  • Les macros simulent essentiellement une machine SECD
    • La machine SECD est une machine abstraite simple à pile pour évaluer des termes du lambda-calcul

Ressources

  • Functional Programming: Application and Implementation by Peter Henderson
  • Ager, Mads Sig, et al. "A functional correspondence between evaluators and abstract machines."
  • The Implementation of Functional Programming Languages by Simon Peyton Jones
  • Billets de blog de Matt Might sur Lisp : https://matt.might.net

TODO

  • Ajouter letrec
  • Ajouter un define récursif

À lire aussi

1 commentaires

 
GN⁺ 2024-09-15
Avis sur Hacker News

  • La dixième règle de Greenspun a encore frappé : https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

    • Ça parle de bases de code dont l’objectif principal n’est pas d’implémenter Lisp, donc ça ne semble pas vraiment s’appliquer ici
    • Un bon exemple de cette règle, c’est que C++ redécouvre car/cdr dans le langage de templates à une lenteur glaciaire
      Il faudra attendre C++26 pour pouvoir obtenir le car d’un pack de paramètres de noms de types avec Args...[0]
      Je ne comprends pas pourquoi on n’introduit pas un nil pour les packs de paramètres vides et des fonctions car/cdr, et pourquoi on ne permet pas de stocker des packs de paramètres au lieu du bazar syntaxique actuel
    • Ça me fait immédiatement penser à la phrase : « Tout programme C ou Fortran suffisamment complexe contient une implémentation ad hoc, informellement spécifiée, boguée et lente de la moitié de Common Lisp »
    • Je ne sais pas ce que veut dire « suffisamment complexe », et la définition n’est pas terrible

  • J’avais essayé quelque chose de similaire il y a quelque temps, mais il y avait un problème : impossible de définir des symboles avec des tirets
    Des choses comme DEFINE MY-FN... ne fonctionnaient pas, parce que Rust découpe les tokens au niveau des tirets
    C’est un petit détail, mais ça empêchait de coller tels quels de vrais morceaux de code Lisp : il fallait tout remplacer par des underscores. Je me demande si cette implémentation a le même souci

    • Pour l’instant, tous les atomes sont supposés être des identifiants Rust. C’est parce que ça rend l’implémentation plus simple, puisqu’on peut faire la correspondance avec $x:ident, donc les tirets dans les atomes ne sont pas pris en charge
      En revanche, je pense qu’on pourrait faire une correspondance du genre $x:ident $(- $y:ident)*. Il faudrait modifier quelques détails dans certaines branches de macros, mais ça semble possible
    • Ça n’a pas l’air de poser problème, non ? DEFINE MYᜭFN... fonctionne bien

  • J’aimerais bien qu’il existe une implémentation de Lisp basée sur Rust et bien prise en charge, pas seulement des macros
    Je me demande dans quelle mesure on conserverait ou perdrait la sûreté mémoire en la construisant au-dessus de Rust. Est-il vraiment possible d’exploiter le borrow checker de façon sensée ?

    • Certains compilateurs Lisp comme SBCL permettent aussi une vérification de types à la compilation plus étendue, mais ces informations doivent être fournies par le programmeur, et relèvent en général davantage d’une phase d’optimisation que du développement incrémental quotidien
      Lisp est généralement défini par son caractère dynamique, et la vérification des types à l’exécution en est une grande partie. Forcer le programmeur à se préoccuper à l’avance de la manière dont les objets sont gérés entre en conflit avec le degré de liberté et d’expressivité attendu de ce type de système
      En contrepartie, le compilateur lui-même peut rester relativement simple. Le code ordinaire sans déclarations supplémentaires est sûr par défaut, et sur une machine virtuelle à bytecode comme CLISP ou sur des machines Lisp avec vérification matérielle des types, ces déclarations peuvent être ignorées tout en restant toujours sûres
      SBCL compile le code assez rapidement, et j’ai entendu dire que d’autres implémentations sont encore plus rapides. À l’inverse, le compilateur Rust est davantage susceptible de faire découvrir aux jeunes programmeurs le concept de thrashing
      Je pense que, malgré les apparences, ce sont deux mondes difficilement compatibles. Lisp est par essence le langage emblématique de la philosophie « The Right Thing », tandis que C est le langage du « Worse is Better ». Rust n’est ni l’un ni l’autre ; c’est quelque chose d’assez différent pour mériter un nouveau nom reflétant les mauvais côtés de ces deux philosophies
      Cela dit, je ne veux pas dénigrer l’article original : ça reste un hack très chouette
    • Steel a l’air pas mal : https://github.com/mattwparas/steel
      Il existe aussi d’autres Lisp (https://github.com/alilleybrinker/langs-in-rust). Ils semblent toutefois moins activement maintenus

  • Je me suis bien amusé à le faire, et j’ai aussi appris que rust-analyser n’arrive pas à gérer une macro qui génère des millions de tokens

  • L’ambiance voudrait que tout le monde s’exclame « c’est amusant », mais chaque fois que je vois ce genre de chose, je n’aime pas le fait que ce soit possible en Rust
    Rust n’a jamais été un langage simple, mais j’ai l’impression qu’il est devenu bien plus difficile à maîtriser qu’au début

    • Je suis d’accord pour dire que Rust n’est pas un langage simple
      En revanche, je ne comprends pas vraiment pourquoi le fait que ce soit possible te dérange. Le système de macros peut générer du code d’une complexité presque illimitée, mais je ne suis pas sûr qu’implémenter un Lisp sandboxé avec des macros soit un exemple très probant montrant que Rust serait devenu plus difficile à gérer qu’à ses débuts
      Cela dit, comme le système de types de Rust est Turing-complet, à la manière des templates C++ ou du système de types de Haskell, ça me donne envie de voir un Lisp implémenté de cette façon aussi
    • Je ne suis pas du tout d’accord sur ce point. L’équipe Rust continue de rendre le langage plus facile à utiliser en supprimant des contraintes et en rendant les fonctionnalités plus orthogonales
      Les exemples typiques sont les durées de vie non lexicales, impl Trait en position de retour et les traits asynchrones. Avant la 1.0, il y avait même des références GC intégrées avec une syntaxe spéciale, et ce genre de fonctionnalités a été supprimé
    • Le seul vrai gros changement depuis la 1.0, c’est async. Si on veut vivre sans async, c’est entièrement possible : c’est une partie totalement optionnelle du langage
      Si tu veux un langage qui fasse de la simplicité un principe, Rust n’a jamais été ce langage-là, et il existe beaucoup d’autres options
    • En réalité, très peu de choses sont nécessaires pour rendre ça possible. Je pense qu’on pourrait même le faire avec les macros C, pourtant considérées comme simples
      J’ai vérifié, et je gagne ce pari : https://github.com/kchanqvq/CSP
    • Les macros n’ont-elles pas toujours été à la fois très puissantes et délicates ? Je n’inclurais pas vraiment les macros dans la complexité du langage
      Je parle surtout du fait de les « écrire » : c’est plutôt une fonctionnalité supplémentaire qu’on peut utiliser ou non

  • Wow, ça utilise macro_rules

  • Mais on ne disait pas que C++ n’était pas un langage sain parce que ses templates sont Turing-complets ?

    • Il suffit d’en connaître un peu sur C++ pour voir que ce n’est pas un langage sain. Au moins, les macros Rust ne sont pas de la substitution textuelle littérale, c’est un pas vers la lumière
    • Turing-complet et tarpit de Turing, ce n’est pas la même chose
      Je ne sais pas de quel côté se situe le système de macros de Rust
    • Développer avec les templates C++, c’est l’enfer. Rust a au moins macro_expand, et le fait que l’outillage Rust soit bien conçu compte beaucoup

  • Carp mérite aussi d’être mentionné. C’est un Lisp qui utilise la vérification des emprunts, un peu le « Rust » du monde Lisp
    1 : https://github.com/carp-lang/Carp