Lisp implementado con macros de Rust

 (github.com/RyanWelly)
1 puntos por GN⁺ 2024-09-15 | 1 comentarios | Compartir por WhatsApp
  • lisp-in-rs-macros es un intérprete Lisp simple con alcance léxico que funciona únicamente con macros declarativas de Rust, y la macro lisp! evalúa el código en tiempo de compilación para generar un valor Lisp convertido en cadena
  • lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) se calcula durante el proceso de expansión de macros de rustc y se expande a la cadena "A"; toda la implementación tiene menos de 250 líneas
  • Los ejemplos usan CAR, LIST, QUOTE, PROGN, DEFINE, LAMBDA, DISPLAY, y el ejemplo de quine muestra una forma en la que el código Lisp se evalúa a sí mismo
  • La recursión explícita no está soportada actualmente, pero con self application se puede escribir comportamiento recursivo como append de listas; aun así, DEFINE en sí no maneja definiciones recursivas
  • El ejemplo de intérprete metacircular parece funcionar, pero evaluar ((lambda (X) X) (quote a)) tarda más de 30 segundos y genera más de un millón de tokens, hasta el punto de que cargo termina con sigkill por lo ineficiente que es

Lisp ejecutándose dentro de macros de Rust

  • lisp-in-rs-macros es un intérprete Lisp con alcance léxico escrito únicamente con macros declarativas de Rust
  • La macro lisp! evalúa el código Lisp recibido y luego convierte en cadena el valor Lisp calculado
  • Por ejemplo, lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) se expande a la cadena "A"
  • Este cálculo no ocurre en tiempo de ejecución, sino en tiempo de compilación mientras rustc expande las macros
  • La implementación tiene menos de 250 líneas

Ejemplo básico de uso

  • Combinando CAR, LIST y QUOTE se puede obtener el primer elemento de una lista
let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");
  • Para evaluar varias expresiones se usa PROGN
    • PROGN evalúa todas las expresiones y devuelve el valor de la última
  • DISPLAY primero evalúa su argumento y luego se expande en una forma como println!("{}", stringify!(evaled_argument)) para convertir los tokens en cadena e imprimirlos
lisp!(PROGN
    (DEFINE message (LAMBDA () (QUOTE "hello there")))
    (DISPLAY (message))
    (DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))) )
    (DISPLAY (NOT NIL))
);
  • El ejemplo de arriba imprime "hello there" y "TRUE"

Quine que se evalúa a sí mismo

  • El ejemplo de quine muestra una forma en la que el código Lisp se evalúa a sí mismo
lisp!
       ((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));
  • Este código se expande a una llamada stringify! como la siguiente
stringify!(((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))))));

Recursión y self application

  • Este Lisp actualmente no soporta recursión explícita
  • Incluso sin recursión explícita, es posible construir comportamiento recursivo solo con lambdas
  • La función append del ejemplo no menciona directamente el nombre append dentro del cuerpo, sino que realiza llamadas recursivas mediante autoaplicación a través del argumento 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)))

)
  • Este código produce "(A B C D)" como resultado

Restricciones de uso

  • La macro lisp! evalúa solo una sola expresión
    • Varias expresiones deben agruparse como (PROGN expr1 expr2 expr3)
  • La lista vacía no es self-evaluating
    • El valor de lista vacía se puede obtener con NIL o (QUOTE ())
    • La lista vacía es el único objeto falsy
  • No se soportan las dotted lists
    • CONS asume que el último argumento es una lista
  • DEFINE puede usarse en cualquier parte y se evalúa como lista vacía, pero no soporta recursión
  • TRUE es el único átomo que se evalúa a sí mismo y no es una función

Formas soportadas

DEFINE
QUOTE
LAMBDA
LET
PROGN
CAR
CDR
CONS
LIST
EQ
ATOM
APPLY
  • DEFINE se parece más a una definición interna de Scheme que a una verdadera definición recursiva al estilo Lisp

Intérprete Lisp escrito en Lisp

  • El repositorio incluye un ejemplo de intérprete metacircular escrito sobre este Lisp
  • El ejemplo define el combinador Y2 para dos argumentos, CADR, CAAR, ASSOC, eval y otros
  • El intérprete parece funcionar, pero al intentar evaluar ((lambda (X) X) (quote a)) tarda más de 30 segundos
  • Esa evaluación genera más de un millón de tokens y finalmente crece lo suficiente como para que cargo termine con sigkill
  • La recursión usando un combinador Y explícito es especialmente ineficiente aquí
  • Se indica que para corregir esto habría que agregar una primitiva de recursión explícita
  • Como walkthrough para escribir un evaluador metacircular, se recomienda "Roots of Lisp" de Paul Graham

Forma de implementación y material de referencia

  • La explicación técnica está en EXPLANATION.md
  • En esencia, las macros simulan una máquina SECD
    • La máquina SECD es una máquina abstracta simple basada en pila para evaluar términos del cálculo lambda

Referencias

  • 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
  • Artículos de blog sobre Lisp de Matt Might: https://matt.might.net

TODO

  • Agregar letrec
  • Agregar define recursivo

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-09-15
Comentarios en Hacker News

  • Ahí va de nuevo la décima ley de Greenspun: https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

    • Esto habla de una base de código cuyo propósito principal no es implementar Lisp, así que no parece encajar del todo aquí
    • Un buen ejemplo de esta ley es cómo C++ redescubre car/cdr a velocidad glacial dentro del lenguaje de plantillas
      Recién en C++26 se podrá obtener el car de un paquete de parámetros de nombres de tipo con Args...[0]
      No entiendo por qué no introducen nil y funciones car/cdr para paquetes de parámetros vacíos, y permiten almacenar paquetes de parámetros en vez del caos sintáctico actual
    • Me viene exacta la frase: “Todo programa en C o Fortran suficientemente complejo contiene una implementación ad hoc, de especificación informal, con muchos bugs y lenta de la mitad de Common Lisp”
    • No sé qué significa “suficientemente complejo”; la definición no es muy buena

  • Hace tiempo probé algo parecido, y había un problema: no se podían definir símbolos con guiones
    Algo como DEFINE MY-FN... no funcionaba, porque Rust divide los tokens en el guion
    Es una diferencia pequeña, pero en la práctica no podías pegar fragmentos reales de código Lisp tal cual y había que cambiar todo a guiones bajos. Me pregunto si esta implementación también tiene ese problema

    • Ahora mismo se asume que todos los átomos son identificadores de Rust. Eso simplifica la implementación porque se puede hacer matching con $x:ident, y por eso no se admiten guiones dentro de los átomos
      En cambio, parece que se podría hacer matching con algo como $x:ident $(- $y:ident)*. Habría que cambiar algunos detalles en ciertas ramas del macro, pero parece posible
    • ¿No hay problema, no? DEFINE MYᜭFN... funciona bien

  • Más que macros, estaría bueno tener una implementación de Lisp bien soportada sobre Rust
    Me pregunto cuánto de la seguridad de memoria se mantendría o se perdería al construirla sobre Rust. ¿Será siquiera posible aprovechar el borrow checker de una forma razonable?

    • Algunos compiladores de Lisp, como SBCL, también permiten una verificación de tipos en tiempo de compilación más amplia, pero esa información la tiene que proporcionar el programador y normalmente forma parte más de la etapa de optimización que del desarrollo incremental cotidiano
      Lisp suele definirse por su naturaleza dinámica, y la verificación de tipos en tiempo de ejecución ocupa una parte importante. Hacer que el programador tenga que preocuparse de antemano por cómo se gestionan los objetos choca con la libertad y expresividad que se espera de ese tipo de sistema
      En cambio, el compilador en sí puede ser relativamente simple. El código general sin declaraciones adicionales es básicamente seguro, y en máquinas virtuales de bytecode como CLISP o en Lisp Machines con verificación de tipos por hardware, incluso ignorar esas declaraciones puede seguir siendo siempre seguro
      SBCL compila código bastante rápido, y he oído que otras implementaciones son aún más rápidas. En cambio, el compilador de Rust parece más propenso a presentar a programadores jóvenes el concepto de thrashing
      Creo que son mundos menos compatibles de lo que parecen a primera vista. Lisp es esencialmente el lenguaje emblemático de la filosofía “The Right Thing”, y C es un lenguaje de “Worse is Better”. Rust no es ninguna de las dos, y parece algo tan distinto que necesitaría un nombre nuevo para reflejar las peores características de ambas filosofías
      Dicho eso, no intento menospreciar el post original; igual sigue siendo un hack muy bueno
    • Steel se ve bien: https://github.com/mattwparas/steel
      También hay otros Lisp (https://github.com/alilleybrinker/langs-in-rust). Aunque parecen mantenerse con menos actividad

  • Fue divertido hacerlo, y también aprendí que rust-analyser no puede manejar macros que generan millones de tokens

  • Se supone que todos deberíamos vitorear “qué divertido”, pero cada vez que veo algo así me molesta el hecho de que se pueda implementar en Rust
    Rust nunca fue un lenguaje simple, pero siento que ahora es mucho más difícil de manejar que al principio

    • Estoy de acuerdo en que Rust no es un lenguaje simple
      Pero no entiendo muy bien por qué te molesta que esto sea posible. El sistema de macros puede generar código de complejidad casi infinita, pero no sé si implementar un Lisp sandboxeado con macros sea una muestra fuerte de que Rust se volvió más difícil de mantener que en sus inicios
      Por otro lado, dado que el sistema de tipos de Rust es Turing-completo, como las plantillas de C++ o el sistema de tipos de Haskell, me dan ganas de ver un Lisp implementado de esa forma
    • Estoy muy en desacuerdo con esa parte. El equipo de Rust ha seguido haciendo el lenguaje más fácil de usar al eliminar restricciones y volver las características más ortogonales
      Ejemplos representativos son las non-lexical lifetimes, impl Trait en posición de retorno y los async traits. Antes de la 1.0 incluso había referencias GC integradas con sintaxis especial, y esas funciones sí se quitaron
    • El único cambio realmente grande y sustancial después de la 1.0 ha sido async. Si quieres vivir sin async, es completamente opcional, una parte totalmente optativa del lenguaje
      Si buscas un lenguaje cuyo principio sea la simplicidad, Rust nunca fue ese lenguaje, y hay muchas otras opciones
    • En realidad, hace falta muy poco para que este tipo de cosas sea posible. Hasta creo que se podría hacer con macros de C, que suelen considerarse simples
      Lo comprobé, y gané esa apuesta: https://github.com/kchanqvq/CSP
    • ¿Los macros no han sido siempre muy poderosos y a la vez complicados? Yo no incluiría la parte de macros en la complejidad del lenguaje
      Sobre todo hablo de “escribirlos”; los veo más como una capacidad adicional que puedes usar o no

  • Vaya, esto usa macro_rules

  • Pero, ¿no se decía que C++ no era un lenguaje cuerdo porque sus plantillas son Turing-completas?

    • C++ no es un lenguaje cuerdo aunque sepas apenas un poco. Al menos los macros de Rust no son sustitución de texto literal, así que es un paso hacia la luz
    • Turing-completo y tarpit de Turing no son lo mismo
      No sé en cuál de los dos cae el sistema de macros de Rust
    • Desarrollar con plantillas de C++ es el infierno. En Rust al menos existe macro_expand, y además las herramientas de Rust están muy bien hechas

  • Tampoco puede faltar Carp. Es un Lisp que usa borrow checking, algo así como el “Rust” del mundo Lisp
    1: https://github.com/carp-lang/Carp