Lisp implementado con macros de Rust

lisp-in-rs-macros

Un intérprete Lisp simple con alcance léxico, completamente funcional, implementado con macros declarativas de Rust. La macro lisp! expande a un valor Lisp calculado por el código y lo convierte en una cadena. Por ejemplo, lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) se expande a la cadena "A", y todo el cálculo ocurre en tiempo de compilación cuando rustc expande las macros.

Por qué importa

Es un intérprete Lisp escrito con macros de Rust, lo cual es muy interesante. Además, está hecho en menos de 250 líneas, así que también es bastante conciso.

Ejemplos

let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");

lisp!(PROGN
  (DEFINE message (LAMBDA () (QUOTE "hello there")))
  (DISPLAY (message))
  (DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))))
  (DISPLAY (NOT NIL))
); // imprime "hello there" y "TRUE"

Otro ejemplo divertido es un quine:

lisp!((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))) (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));

Este código se evalúa a sí mismo.

Recursión

Este Lisp actualmente no soporta una forma explícita de recursión. Por suerte, la recursión explícita no es necesaria; basta con lambdas. Se puede escribir una función simple para concatenar dos listas:

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)))
);

El resultado es "(A B C D)". La función append no menciona append en su cuerpo, pero igual puede llamarse recursivamente.

Precauciones de uso

• La macro lisp! evalúa solo una expresión. Para evaluar varias expresiones, hay que usar (PROGN expr1 expr2 expr3).
• La forma DISPLAY evalúa una sola expresión y luego genera una sentencia println!("{}", stringify!(...)) para imprimir la versión en cadena de los tokens.
• La lista vacía no se autoevalúa; para obtener el valor de una lista vacía hay que usar NIL o (QUOTE ()).
• Las listas punteadas no están soportadas, y cons asume que su último argumento es una lista.
• La forma define puede usarse en cualquier parte y se evalúa como lista vacía, pero no soporta recursión.
• TRUE es el único átomo autoevaluado que no es una función.

Formas soportadas

• DEFINE
• QUOTE
• LAMBDA
• LET
• PROGN
• CAR
• CDR
• CONS
• LIST
• EQ
• ATOM
• APPLY

Intérprete metacircular

Lo siguiente es un intérprete Lisp escrito en Lisp:

lisp!(PROGN
  (DEFINE Y2
    (LAMBDA (h)
      ((LAMBDA (x) (h (LAMBDA (a b) ((x x) a b))))
        (LAMBDA (x) (h (LAMBDA (a b) ((x x) a b)))))))
  (DEFINE CADR (LAMBDA (X) (CAR (CDR X))))
  (DEFINE CAAR (LAMBDA (X) (CAR (CAR X))))
  (DEFINE CADAR (LAMBDA (X) (CAR (CDR (CAR X)))))
  (DEFINE CADDR (LAMBDA (X) (CAR (CDR (CDR X)))))
  (DEFINE CADDAR (LAMBDA (X) (CAR (CDR (CDR (CAR X))))))
  (DEFINE CAADAR (LAMBDA (X) (CAR (CAR (CDR (CAR X))))))
  (DEFINE ASSOC (Y2 (LAMBDA (ASSOC) (LAMBDA (X ENV)
    (IF (EQ (CAAR ENV) X) (CADAR ENV) (ASSOC X (CDR ENV))))))
  )
  (DEFINE eval (Y2 (LAMBDA (EVAL) (LAMBDA (E A)
    (COND
      ((ATOM E) (ASSOC E A))
      ((ATOM (CAR E))
        (COND
          ((EQ (CAR E) (QUOTE quote)) (CADR E))
          ((EQ (CAR E) (QUOTE atom)) (ATOM (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE car)) (CAR (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE cdr)) (CDR (EVAL (CADR E) A)))
          ((EQ (CAR E) (QUOTE equal)) (EQ (EVAL (CADR E) A) (EVAL (CADDR E) A)))
          ((EQ (CAR E) (QUOTE cons)) (CONS (EVAL (CADR E) A) (EVAL (CADDR E) A)))
          (TRUE (EVAL (CONS (ASSOC (CAR E) A) (CDR E)) A))
        ))
      ((EQ (CAAR E) (QUOTE lambda)) (EVAL (CADDAR E) (CONS (LIST (CAADAR E) (EVAL (CADR E) A)) A)))
    ))))
  )
  (eval (QUOTE (quote (A))) NIL)
  (eval (QUOTE ((lambda (X) X) (quote a))) NIL)
);

Este código funciona, pero si se intenta evaluar ((lambda (X) X) (quote a)) en el intérprete, tarda más de 30 segundos y genera más de un millón de tokens. La recursión con un combinador Y explícito no es eficiente aquí. Para resolverlo, haría falta agregar una primitiva de recursión explícita. Para una excelente explicación de cómo escribir un evaluador metacircular, consulta "Roots of Lisp" de Paul Graham.

Explicación técnica

Consulta EXPLANATION.md. Las macros simulan la máquina SECD, una máquina abstracta simple basada en pila para evaluar expresiones del cálculo lambda.

Materiales recomendados

• "Functional Programming: Application and Implementation" de Peter Henderson
• "A functional correspondence between evaluators and abstract machines." (2003) de Mads Sig Ager y otros
• "The Implementation of Functional Programming Languages" de Simon Peyton Jones
• Todos los artículos sobre Lisp en el blog de Matt Might (https://matt.might.net)

TODO

• Agregar letrec
• Agregar definiciones recursivas

Resumen de GN⁺

• El intérprete Lisp escrito con macros de Rust es muy interesante y ofrece funciones potentes con un código conciso.
• Aunque no soporta recursión de forma explícita, es posible implementarla mediante lambdas.
• El intérprete metacircular no es eficiente, por lo que hace falta agregar una primitiva de recursión explícita.
• "Roots of Lisp" de Paul Graham es un excelente recurso para entender un evaluador metacircular.
• Otros proyectos con funciones similares podrían ser intérpretes de Scheme u otras variantes de Lisp.