El lenguaje Python homoicónico (Homoiconic)

 (substack.com/aljamal)
2 puntos por GN⁺ 2024-05-13 | 2 comentarios | Compartir por WhatsApp
  • La homoiconicidad de Lisp es la propiedad de tratar el código y los datos con la misma forma; al trasladar el clásico “Lisp in Lisp” a Python, esta idea se revela dentro de una sintaxis más familiar
  • Originalmente, Lisp tenía tanto M-expressions, la representación del código, como S-expressions, la representación de los datos, y “Lisp in Lisp” implementa un Lisp de S-expressions usando M-expressions
  • La versión en Python representa las S-expressions como listas de Python y traslada las M-expressions a llamadas a funciones y condicionales, construyendo un intérprete sin un parser separado
  • El primer intérprete se basa en operaciones primitivas de listas como atom, eq, car, cdr, cons y append; para soportar lambda, se agregan assoc, pairlis y una lista de entornos
  • eval recibe una expresión junto con un entorno para manejar bindings de variables, y mediante pairlis y assoc conecta argumentos y valores con un esquema de scope dinámico

La integración de código y datos que mostró Lisp

  • Lisp dejó muchas ideas que siguen vigentes décadas después, a partir del paper de Lisp de John McCarthy de principios de la década de 1960 y del manual de Lisp 1.5
  • Entre ellas, la idea central es la homoiconicidad
    • En los lenguajes comunes, el código se entiende como una secuencia de operaciones que actúan sobre datos
    • Lisp trata el código y los datos con la misma forma, difuminando la frontera entre operadores y operandos
  • Alan Kay llamó al código “Lisp in Lisp”, que aparece al final de la página 13 del manual de Lisp 1.5, las “ecuaciones de Maxwell del software”
    • Se incluye una cita con el sentido de que fue una gran revelación ver que unas pocas líneas de código contenían todo el mundo de la programación

Cómo trasladar “Lisp in Lisp” a Python

  • El objetivo es reescribir en Python el código clásico “Lisp in Lisp” manteniendo al máximo el espíritu del código original
  • Lisp tiene dos representaciones sintácticas
    • M-expression: representación del código, abreviatura de meta
    • S-expression: representación de datos, abreviatura de symbolic
    • Ambas representaciones son semánticamente equivalentes
  • El código existente de “Lisp in Lisp” está escrito en M-expression e implementa un Lisp de S-expressions
  • En la implementación en Python, las S-expressions de Lisp se representan como listas de Python
    • Lisp es abreviatura de “List Processing” y funciona alrededor de una única estructura de datos: la lista
    • Las listas de Python se usan como una representación adecuada para emular las S-expressions de Lisp
  • Las M-expressions se traducen a estructuras de código como llamadas a funciones y condicionales de Python
    • Gracias a este mapeo, se puede crear un intérprete sin manipular strings ni implementar un parser separado

Un primer intérprete creado con operaciones primitivas de listas

  • Una implementación de Lisp necesita algunas funciones básicas provistas desde fuera del lenguaje
  • Las operaciones primitivas de listas usadas en la implementación en Python son las siguientes
    • atom(x): verifica si x es una lista
    • eq(x,y): verifica si x e y son iguales
    • car(x): primer elemento de una lista
    • cdr(x): el resto de una lista
    • cons(x,y): agrega un átomo a una lista
    • append(x,y): concatena dos listas
  • Salvo algunas operaciones primitivas recursivas, fue posible crear rápidamente un intérprete que ejecuta un subconjunto del código “Lisp in Lisp” usando Llama3-70b en Groq
  • En el ejemplo, las listas de Python funcionan como S-expressions
  • El código completo está disponible en github gists

Extensiones para lambda y recursión

  • A la primera implementación le falta una funcionalidad importante: lambda
    • lambda es la forma principal de definir y llamar funciones anónimas en Lisp
    • Sin lambda en Lisp, no se puede implementar recursión
    • Sin recursión, no se alcanza la completitud de Turing, el criterio mínimo para poder computar todo lo computable
  • Para incorporar lambda, se agregan assoc(x,y) y pairlis(x,y)
    • assoc(x,y) es una búsqueda de clave/valor implementada con listas y usa una lista asociativa
    • pairlis(x,y) empareja dos listas, como zip(x,y) en Python
  • El Lisp original tenía que manejar incluso un simple escaneo lineal mediante recursión
    • Esto se debía a que el Lisp original no tenía loops
    • En la traducción a Python, assoc y pairlis pueden expresarse de forma más concisa con list comprehensions
  • En el manejo de COND, el evcon original de Lisp se traduce a un loop, y en el manejo de LAMBDA se aplica el mismo método a evlis

Lista de entornos y scope dinámico

  • La función eval del Lisp original recibe dos argumentos
    • El primer argumento es la S-expression a evaluar
    • El segundo argumento es una lista de entornos formada por pares clave/valor
  • El entorno mantiene los bindings de variables en el manejo de LAMBDA
    • Si una función tiene una variable x y se le asignan datos, pairlis empareja el símbolo x con esos datos
    • El valor emparejado se guarda o se agrega a la lista de entornos
    • Cuando se necesita x, assoc lo busca en el entorno y lo vuelve a sustituir en la expresión
  • Este método de binding se llama scope dinámico
  • La implementación final es una traslación del “Lisp in Lisp” original a Python e incluye hasta la ejecución de lambda en el último ejemplo

Lecturas relacionadas

2 comentarios

 
GN⁺ 2024-05-13
Opiniones de Hacker News

  • Si te interesa un Lisp de scripting simple y rápido con estilo Python, vale la pena ver Hy y Janet, lenguajes al estilo Clojure

    1. Hy(https://hylang.org/): compila a bytecode de Python y suele ser más lento que Python, pero es compatible con todas las bibliotecas de Python
    2. Janet(https://janet-lang.org/): una máquina virtual embebible muy ligera, al estilo Lua, de alrededor de 1 MB; en operaciones similares es aproximadamente 2 veces más rápida que Python y la interoperabilidad con C es muy sencilla
    • Para scripting rápido con estilo Python, también existe https://github.com/ciel-lang/ciel, Common Lisp con baterías incluidas
      Se ofrece como un binario de inicio rápido e incluye bibliotecas para tareas cotidianas
      Para el lado CL↔Python, también vale la pena consultar https://github.com/CodyReichert/awesome-cl?tab=readme-ov-fil...
    • ¿Hy es más lento que Python? Al menos en tiempo de ejecución no debería serlo
      Soy mantenedor de Hy, y si ves una diferencia de rendimiento significativa, eso es un bug
      1. Basilisp(https://github.com/basilisp-lang/basilisp): “un dialecto Lisp compatible-ish con Clojure que apunta a Python 3.8+”
    • Puede parecer un capricho, pero Lisp siempre me pareció un lenguaje que invita a la polémica por sus paréntesis envolventes obligatorios
      Las M-expressions evitan esta trampa, así que me pregunto si existió algún lenguaje real que mantuviera la homoiconicidad y la elegancia conceptual de Lisp sin exigir esos paréntesis
    • https://github.com/yaml/yamlscript
      Es exactamente lo que estás pensando. La descripción también es muy directa: “Program in YAML”
      Casi no hace falta decir más

  • Espera, ¿esto no es simplemente un Lisp implementado en Python?
    No parece ser Python homoicónico, como sugiere el título; ¿me estoy perdiendo algo?

    • Según la décima regla de Greenspun, es correcto: https://en.m.wikipedia.org/wiki/Greenspun's_tenth_rule
    • Yo también me emocioné bastante pensando que era Python homoicónico, algo que podría hacer que mis colegas lo usaran sin tener que convencerlos de adoptar Lisp, pero no lo era: era simplemente Lisp
    • Eso parece. Me dio curiosidad porque quería ver ese Python homoicónico, pero ni siquiera estoy seguro de que sea posible
      Para eso, la sintaxis de Python tendría que estar compuesta por tuplas, listas y diccionarios, y el intérprete tendría que evaluarlos directamente
    • ¿Cuál es la diferencia?

  • Otro lenguaje funcional que se puede implementar de forma concisa en Python es Binary Lambda Calculus
    Una parte considerable del código se ocupa del modelo de entrada/salida puro de BLC, y para la búsqueda de variables indexa un arreglo de entornos con índices de de Bruijn en vez de usar una lista asociativa
    En la misma página también hay implementaciones en otros 9 lenguajes, y el autointérprete de BLC es el más conciso: 232 bits (29 bytes), incluyendo parser y tokenizer
    [1] https://rosettacode.org/wiki/Universal_Lambda_Machine#Python

  • El curso introductorio de programación del MIT hace que todos los estudiantes escriban un intérprete de Lisp en Python
    Es un vestigio de la época en que esa clase se daba realmente en Lisp
    https://py.mit.edu/spring24

    • De manera similar, una clase que tomé en la universidad también nos hacía implementar un intérprete de Lisp básico en Lisp

  • Alguna vez hice algo parecido con listas de JS: https://github.com/andrelaszlo/js-lisp

  • Es gracioso e irónico que los lenguajes modernos redescubran, décadas después, las funciones sorprendentes de Lisp
    Hace unos días me enojé porque se detuvo un programa en Python que llevaba 9 horas llamando a la API de mi servidor casero. Eran llamadas de API parecidas, y estaba invocando un LLM con plantillas de prompts y restricciones gramaticales predefinidas
    Antes de ejecutar por separado las iteraciones restantes, quería guardar el estado del programa y cerrarlo, pero no encontré una forma de modificar el código Python en ejecución ni de inspeccionar variables, así que terminé perdiendo 9 horas de trabajo
    Unos días después vi https://malisper.me/debugging-lisp-part-1-recompilation/, y me sorprendió que Common Lisp tuviera este tipo de funciones integradas en el lenguaje desde hace décadas. Lo mismo pasa con otras funciones, como el sistema de macros más potente

    • No sorprende que los lenguajes modernos redescubran décadas después funciones de Lisp. La familia Lisp incluye algunos de los lenguajes más flexibles y expresivos
      Pero ese también es el problema. Tienen demasiada expresividad
      Lisp siempre me ha hecho pensar en el arte visual de medios mixtos: la libertad de expresión suena bien, pero al final el resultado suele ser peor que el de artes más tradicionales de un solo medio. Se hace evidente que las restricciones del medio son tan importantes como la expresividad
    • Para inspeccionar el estado hasta cierto punto, se pueden usar Py-spy o Pystack
      O también está https://github.com/malor/cpython-lldb
      Hay más métodos en https://github.com/albertz/pydbattach/
    • Si es un proceso que corre durante varias horas, debería guardar el trabajo en disco y estar preparado para reiniciar desde el punto donde se interrumpió
    • ¿No se lanzó ninguna excepción?

  • ¿En qué sentido esta implementación es Python homoicónico?

  • ¿Existe algún Lisp con un sistema de tipos que ayude a controlar, hasta cierto punto, la tendencia de Lisp a volverse difícil de leer a medida que los programas crecen?
    Aunque no sea un sistema de tipos, me pregunto si hay algún otro elemento que pueda domar esa característica
    La metaprogramación es realmente genial, pero a veces se lee como las abstracciones de Haskell más crípticas que he visto, y ni siquiera hay firmas de tipos que sirvan de guía
    Creo que los sistemas de tipos y los linters son las mejores herramientas para disciplinar automáticamente el código, pero me cuesta imaginar cómo se podrían contener las tendencias de un proyecto Lisp sin restringir precisamente las razones por las que uno elegiría Lisp

    • Si hablamos de un Lisp con sistema de tipos, pienso en Common Lisp
      SBCL, que en la práctica es lo más cercano a un estándar, también tiene una verificación de tipos en tiempo de compilación bastante buena
      Por ejemplo, si después de (declare (type String a b)) escribes (+ a b), detecta una advertencia indicando que el tipo derivado de A es STRING, pero debería ser NUMBER
      La principal razón por la que me pasé de Scheme a CL fue esa verificación de tipos, y luego me quedé por otras funciones pequeñas pero agradables, como los restarts y los continuable asserts
    • Del lado más amigable y accesible está Typed Racket; del lado potente pero complejo está Shen
    • https://en.wikipedia.org/wiki/Dylan_(programming_language)

  • Un Python orientado a expresiones sería muchísimo mejor que el Python actual
    Este artículo no trata de lo que sugiere el título, pero sí es una buena explicación de Lisp

    • Un Python orientado a expresiones simplemente no sería Python
      Igual estaría bien, pero “tratar las expresiones como sintaxis de segunda clase” es una decisión bastante fundamental e intencional. También es un diseño pensado para complicarles la vida a los desarrolladores que quieran escribir sopa de paréntesis
      Por eso lambda: y := son deliberadamente torpes, para desalentar su uso, y tampoco se pueden escribir funciones anónimas
      Python es un lenguaje que te dice que, si quieres hacer algo inteligente, lo hagas con iteradores, no con objetos invocables

  • Ojalá todo tuviera la ausencia de sintaxis al estilo Lisp
    A mí eso me gusta más y, por suerte, en CL es fácil hacerlo
 
kayws426 2024-05-13

Un dialecto de Lisp integrado en Python
https://hylang.org/