Le langage Python homoiconique

Implémenter le « Lisp in Lisp » de McCarthy en Python

• Lisp, développé par John McCarthy au début des années 1960, possède la propriété d’homoiconicité, ce qui rend le code et les données interchangeables

  • Dans Lisp, la frontière entre code et données devient floue
  • Cela permet à Lisp de se représenter naturellement lui-même

• La demi-page de code en bas de la page 13 du manuel de Lisp 1.5 était Lisp lui-même

  • Alan Kay l’a qualifiée d’« équations de Maxwell du logiciel »
  • Tout l’univers de la programmation y est condensé en seulement quelques lignes de code

• Pour le comprendre, une bonne méthode consiste à réimplémenter en Python le code de « Lisp in Lisp »

  • La plupart des programmeurs ne sont pas familiers avec la syntaxe de Lisp, mais le sont avec celle de Python
  • L’objectif est de le réécrire en Python tout en préservant autant que possible l’esprit du code Lisp

Les M-expressions et S-expressions de Lisp

• Lisp avait à l’origine deux variantes syntaxiques

  • M-expression (méta-expression) : la variante du code
  • S-expression (expression symbolique) : la variante des données
  • Les deux sont sémantiquement équivalentes

• Le code de « Lisp in Lisp » est écrit en M-expression et implémente un Lisp en S-expression

• Une approche consiste à convertir les M-expressions de Lisp en structures de code Python, et à représenter les S-expressions sous forme de listes Python

  • Lisp signifie List Processing et n’utilise qu’une seule structure de données : la liste

Première implémentation

• Les opérations de base de Lisp sont implémentées à l’aide des fonctions de base des listes Python

  • atom(x) : vérifie si x est une liste
  • eq(x,y) : vérifie si x et y sont identiques
  • car(x) : renvoie le premier élément de la liste
  • cdr(x) : renvoie le reste de la liste
  • cons(x,y) : ajoute un atome à une liste
  • append(x,y) : concatène deux listes

• En laissant de côté quelques éléments fondamentaux liés à la récursion, il est possible d’implémenter rapidement, avec l’aide de Llama3-70b, un interpréteur pour un sous-ensemble du code de « Lisp in Lisp »

Deuxième implémentation

• La première implémentation ne comprend pas les lambdas

  • Les lambdas sont le principal moyen de définir et d’appeler des fonctions dans Lisp
  • Sans lambdas, il est impossible d’implémenter la récursion, et sans récursion, on n’obtient pas la complétude de Turing

• Pour implémenter les lambdas, il faut disposer des éléments de base assoc(x,y) et pairlis(x,y)

  • assoc(x,y) effectue une recherche de dictionnaire clé/valeur à l’aide d’une liste d’associations
  • pairlis(x,y) est l’équivalent de zip(x,y) en Python

• Lisp n’ayant pas de loop, même une simple recherche linéaire devait utiliser la récursion

  • En Python, cela peut toutefois être transformé élégamment à l’aide de compréhensions de liste
  • Il en va de même pour evcon et evlis, qui peuvent aussi être convertis en loop

• La fonction eval prend à l’origine deux arguments dans Lisp

  • Le premier est l’expression (s-exp), le second l’environnement (environment), une liste de paires clé/valeur
  • L’environnement conserve les liaisons de variables de LAMBDA
  • La technique utilisée est celle de la portée dynamique (dynamic scoping)

L’avis de GN⁺

• Une tentative intéressante de reproduire en Python la propriété d’homoiconicité propre à Lisp. Il semble toutefois y avoir des limites à la transposition complète des caractéristiques uniques de Lisp. Pour découvrir tout l’attrait de Lisp, le mieux reste sans doute d’apprendre Lisp lui-même.

• L’implémentation en Python de fonctionnalités puissantes de Lisp, comme les fonctions lambda et la portée dynamique, est impressionnante. Mais cela semble encore insuffisant pour une application dans un vrai projet. En revanche, cela paraît utile dans un cadre pédagogique ou de recherche.

• Ce type d’initiative peut en soi devenir une occasion de réfléchir en profondeur à la nature des langages de programmation. Au-delà de la syntaxe et de l’implémentation d’un langage, cela permet d’adopter une perspective fondée sur les paradigmes de programmation.

• Apprendre un langage de la famille Lisp peut aider à acquérir des intuitions sur la programmation fonctionnelle et la métaprogrammation. Il peut aussi être intéressant d’examiner des langages Lisp modernes comme Scheme, Clojure ou Racket.

[kayws426]

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