Le langage Python homoiconique

 (aljamal.substack.com)
2 points par GN⁺ 2024-05-13 | 2 commentaires | Partager sur WhatsApp
  • L’homoiconicité de Lisp est la propriété qui consiste à traiter le code et les données sous la même forme ; transposer le classique « Lisp in Lisp » en Python fait ressortir cette idée dans une syntaxe plus familière
  • À l’origine, Lisp faisait coexister les M-expressions, représentation du code, et les S-expressions, représentation des données, et « Lisp in Lisp » implémentait un Lisp à S-expressions au moyen de M-expressions
  • La version Python représente les S-expressions par des listes Python et transpose les M-expressions en appels de fonctions et en conditions, ce qui permet de construire un interpréteur sans parseur séparé
  • Le premier interpréteur repose sur des opérations primitives de liste comme atom, eq, car, cdr, cons et append ; pour prendre en charge lambda, assoc, pairlis et une liste d’environnement sont ajoutés
  • eval reçoit à la fois l’expression et l’environnement pour gérer les liaisons de variables, et associe arguments et valeurs selon un scope dynamique via pairlis et assoc

L’unification du code et des données montrée par Lisp

  • Lisp a laissé plusieurs idées encore pertinentes des décennies plus tard, à travers le papier sur Lisp de John McCarthy au début des années 1960 et le manuel Lisp 1.5
  • L’une des idées centrales est l’homoiconicité
    • Dans un langage ordinaire, le code est compris comme une suite d’opérations agissant sur des données
    • Lisp traite le code et les données sous la même forme, brouillant la frontière entre opérateurs et opérandes
  • Alan Kay a qualifié le code « Lisp in Lisp » en bas de la page 13 du manuel Lisp 1.5 d’« équations de Maxwell du logiciel »
    • La citation incluse souligne qu’il y voyait une grande révélation : quelques lignes de code contenaient tout l’univers de la programmation

Comment transposer « Lisp in Lisp » en Python

  • L’objectif est de réécrire en Python le classique « Lisp in Lisp » tout en conservant autant que possible l’esprit du code d’origine
  • Lisp possède deux représentations syntaxiques
    • M-expression : représentation du code, abréviation de meta
    • S-expression : représentation des données, abréviation de symbolic
    • Les deux représentations sont sémantiquement équivalentes
  • Le code « Lisp in Lisp » existant est écrit en M-expressions et implémente un Lisp à S-expressions
  • Dans l’implémentation Python, les S-expressions de Lisp sont représentées par des listes Python
    • Lisp est l’abréviation de « List Processing » et fonctionne autour d’une structure de données unique : la liste
    • Les listes Python sont utilisées comme une représentation adaptée pour émuler les S-expressions de Lisp
  • Les M-expressions sont traduites en structures de code Python comme les appels de fonctions et les conditions
    • Grâce à ce mapping, il est possible de créer un interpréteur sans manipulation de chaînes ni implémentation d’un parseur séparé

Un premier interpréteur construit avec des primitives de liste

  • Une implémentation de Lisp nécessite quelques fonctions de base fournies depuis l’extérieur du langage
  • Les primitives de liste utilisées dans l’implémentation Python sont les suivantes
    • atom(x) : vérifie si x est une liste
    • eq(x,y) : vérifie si x et y sont égaux
    • car(x) : premier élément d’une liste
    • cdr(x) : reste de la liste
    • cons(x,y) : ajoute un atome à une liste
    • append(x,y) : concatène deux listes
  • À l’exception de quelques primitives récursives, il a été possible d’utiliser Llama3-70b sur Groq pour créer rapidement un interpréteur exécutant un sous-ensemble du code « Lisp in Lisp »
  • Dans les exemples, les listes Python se comportent comme des S-expressions
  • Le code complet est disponible dans des gists GitHub

Extensions pour lambda et la récursion

  • La première implémentation omet une fonctionnalité importante : lambda
    • lambda est le principal mécanisme de Lisp pour définir et appeler des fonctions anonymes
    • Sans lambda, il est impossible d’implémenter la récursion en Lisp
    • Sans récursion, on n’atteint pas le critère minimal permettant de calculer tout ce qui est calculable : la complétude de Turing
  • Pour ajouter lambda, assoc(x,y) et pairlis(x,y) sont introduits
    • assoc(x,y) est une recherche clé/valeur implémentée avec des listes et utilise une liste d’associations
    • pairlis(x,y) associe deux listes, comme zip(x,y) en Python
  • Dans Lisp d’origine, même un simple scan linéaire devait être traité par récursion
    • C’était dû au fait que Lisp ne disposait pas de boucles à l’origine
    • Dans la traduction Python, assoc et pairlis peuvent être exprimés plus succinctement avec des compréhensions de liste
  • Pour le traitement de COND, le evcon du Lisp d’origine est traduit en boucle, et la même approche est appliquée à evlis dans le traitement de LAMBDA

Liste d’environnement et scope dynamique

  • La fonction eval du Lisp d’origine prend deux arguments
    • Le premier est la S-expression à évaluer
    • Le second est une liste d’environnement composée de paires clé/valeur
  • L’environnement conserve les liaisons de variables dans le traitement de LAMBDA
    • Si une fonction possède une variable x et qu’on lui affecte des données, pairlis associe le symbole x aux données
    • La valeur associée est stockée dans la liste d’environnement ou y est ajoutée
    • Quand x est nécessaire, assoc le recherche dans l’environnement et le réinjecte dans l’expression
  • Ce mode de liaison est appelé scope dynamique
  • L’implémentation finale est une transposition en Python du « Lisp in Lisp » d’origine, et le dernier exemple inclut même l’exécution de lambda

À lire aussi

2 commentaires

 
GN⁺ 2024-05-13
Avis sur Hacker News

  • Si vous vous intéressez à un Lisp de scripting simple et rapide dans l’esprit de Python, les langages de style Clojure Hy et Janet valent le détour

    1. Hy(https://hylang.org/) : il se compile en bytecode Python et, même s’il est généralement plus lent que Python, il est compatible avec toutes les bibliothèques Python
    2. Janet(https://janet-lang.org/) : une machine virtuelle embarquée très légère, dans le style de Lua, d’environ 1 Mo ; pour des opérations comparables, il est à peu près 2 fois plus rapide que Python, et l’interopérabilité avec C est très simple
    • Pour du scripting rapide dans l’esprit de Python, il existe aussi https://github.com/ciel-lang/ciel, un Common Lisp « batteries incluses »
      Il est fourni sous forme de binaire à démarrage rapide et inclut aussi des bibliothèques pour les tâches du quotidien
      Pour la partie CL↔Python, https://github.com/CodyReichert/awesome-cl?tab=readme-ov-fil... mérite aussi d’être consulté
    • Hy serait plus lent que Python ? Au moins à l’exécution, ça ne devrait pas être le cas
      Je suis mainteneur de Hy, et si vous voyez un écart de performances significatif, c’est un bug
      1. Basilisp(https://github.com/basilisp-lang/basilisp) : « un dialecte Lisp compatible-ish Clojure ciblant Python 3.8+ »
    • Cela peut sembler être une marotte, mais Lisp m’a toujours donné l’impression d’être un langage qui appelle la contestation, à cause des parenthèses englobantes obligatoires
      Les M-expressions évitent ce piège ; je me demande donc s’il a existé un vrai langage qui conserve l’homoiconicité et l’élégance conceptuelle de Lisp sans imposer ces parenthèses
    • https://github.com/yaml/yamlscript
      C’est exactement ce à quoi vous pensez. La description est elle aussi très directe : « Programmer en YAML »
      Il n’y a presque rien à ajouter

  • Attendez, ce n’est pas simplement un Lisp implémenté en Python ?
    Ça ne ressemble pas à du Python homoiconique, comme le titre le suggère ; qu’est-ce que j’ai raté ?

    • D’après la dixième loi de Greenspun, c’est exact : https://en.m.wikipedia.org/wiki/Greenspun's_tenth_rule
    • Moi aussi, j’étais assez emballé en pensant que c’était un Python homoiconique que je pourrais faire utiliser à mes collègues sans leur faire accepter Lisp, mais non : c’était juste Lisp
    • Ça en a tout l’air. J’étais curieux parce que je voulais voir ce Python homoiconique, mais je ne suis même pas sûr que ce soit possible
      Pour cela, il faudrait que la syntaxe de Python soit composée de tuples, de listes et de dictionnaires, et que l’interpréteur les évalue directement
    • Quelle est la différence ?

  • Un autre langage fonctionnel qui peut être implémenté de façon concise en Python est le Binary Lambda Calculus
    Une grande partie du code traite le modèle d’entrée-sortie pur du BLC, et, pour la recherche de variables, il indexe un tableau d’environnement avec des indices de de Bruijn au lieu d’utiliser une liste d’associations
    La même page propose aussi des implémentations dans 9 autres langages, et l’auto-interpréteur du BLC est le plus concis avec 232 bits (29 octets), parseur et tokenizer inclus
    [1] https://rosettacode.org/wiki/Universal_Lambda_Machine#Python

  • Le cours d’introduction à la programmation du MIT fait écrire à tous les étudiants un interpréteur Lisp en Python
    C’est une trace de l’époque où ce cours était effectivement donné en Lisp
    https://py.mit.edu/spring24

    • De façon similaire, un cours que j’ai suivi à l’université nous faisait implémenter un interpréteur Lisp basique en Lisp

  • J’ai fait quelque chose de similaire avec des listes JS : https://github.com/andrelaszlo/js-lisp

  • Il est à la fois drôle et ironique de voir les langages modernes redécouvrir, des décennies plus tard, les fonctionnalités étonnantes de Lisp
    Il y a quelques jours, un programme Python qui appelait l’API de mon serveur domestique depuis 9 heures s’est arrêté, ce qui m’a mis en colère. Il s’agissait d’appels d’API similaires, et le programme appelait un LLM avec des modèles de prompts prédéfinis et des contraintes de grammaire
    Avant de relancer séparément les itérations restantes, je voulais sauvegarder l’état du programme et l’arrêter, mais je n’ai trouvé aucun moyen de modifier le code Python en cours d’exécution ni d’inspecter les variables, et j’ai fini par perdre 9 heures de travail
    Quelques jours plus tard, je suis tombé sur https://malisper.me/debugging-lisp-part-1-recompilation/, et j’ai été surpris de découvrir que Common Lisp intégrait ce genre de fonctionnalité au langage depuis des décennies. Il en va de même pour d’autres fonctionnalités, comme le système de macros le plus puissant

    • Ce n’est pas surprenant que les langages modernes redécouvrent des décennies plus tard les fonctionnalités de Lisp. Les langages de la famille Lisp comptent parmi les plus flexibles et les plus expressifs
      Mais c’est aussi le problème. Ils sont trop expressifs
      Lisp m’a toujours fait penser aux arts visuels en techniques mixtes : la liberté d’expression paraît séduisante, mais au final les résultats sont souvent globalement inférieurs à ceux d’arts plus traditionnels à médium unique. On constate que les contraintes du médium sont aussi importantes que l’expressivité
    • Pour inspecter l’état dans une certaine mesure, on peut utiliser Py-spy ou Pystack
      Il y a aussi https://github.com/malor/cpython-lldb
      Pour d’autres méthodes : https://github.com/albertz/pydbattach/
    • Pour un processus qui tourne pendant plusieurs heures, il faut enregistrer le travail sur disque et être prêt à reprendre à partir du point d’interruption
    • Aucune exception n’a été levée ?

  • En quoi cette implémentation est-elle du Python homoiconique ?

  • Existe-t-il un Lisp doté d’un système de types qui aide à contrôler, dans une certaine mesure, la tendance de Lisp à devenir difficile à lire à mesure que les programmes grossissent ?
    Même si ce n’est pas un système de types, je me demande s’il existe d’autres éléments capables de maîtriser cette propriété
    La métaprogrammation est vraiment géniale, mais parfois cela se lit comme les abstractions Haskell les plus obscures que j’aie vues, sans même les signatures de types pour servir de guide
    Je considère les systèmes de types et les linters comme les meilleurs outils pour discipliner automatiquement le code, mais j’ai du mal à imaginer comment contenir les tendances des projets Lisp sans restreindre précisément ce pour quoi on choisit Lisp

    • Si l’on parle d’un Lisp avec système de types, Common Lisp me vient à l’esprit
      SBCL, qui est de fait ce qui se rapproche le plus d’un standard, offre aussi une assez bonne vérification des types à la compilation
      Par exemple, si l’on écrit (+ a b) après (declare (type String a b)), il détecte l’avertissement indiquant que le type dérivé de A est STRING alors qu’il devrait être NUMBER
      Cette vérification de types a été la principale raison pour laquelle je suis passé de Scheme à CL, et je suis ensuite resté pour de petites fonctionnalités appréciables comme les restarts et les continuable asserts
    • Du côté convivial et accessible, il y a Typed Racket ; du côté puissant mais complexe, Shen
    • https://en.wikipedia.org/wiki/Dylan_(programming_language)

  • Un Python orienté expressions serait bien meilleur que le Python actuel
    Cet article ne traite pas vraiment de ce que son titre suggère, mais il constitue une bonne explication de Lisp

    • Un Python orienté expressions ne serait tout simplement plus Python
      Ce n’est pas forcément un problème, mais « reléguer les expressions au rang de syntaxe de seconde classe » est un choix assez fondamental et intentionnel. C’est aussi une conception faite pour compliquer la vie des développeurs qui veulent écrire une soupe de parenthèses
      C’est pourquoi lambda: et := sont volontairement maladroits afin d’en décourager l’usage, et il n’est pas non plus possible d’écrire des fonctions anonymes
      Python est un langage qui dit que, si vous voulez faire quelque chose d’intelligent, il faut le faire avec des itérateurs, pas avec des objets appelables

  • J’aimerais qu’il y ait une absence de syntaxe à la Lisp partout
    Pour moi, c’est mieux ainsi, et heureusement c’est facile à faire en CL
 
kayws426 2024-05-13

Un dialecte de Lisp intégré à Python
https://hylang.org/