Lisp implementado com macros em Rust

lisp-in-rs-macros

Um interpretador Lisp simples com escopo léxico, totalmente funcional, implementado com macros declarativas de Rust. A macro lisp! expande para valores Lisp calculados pelo código e os converte em strings. Por exemplo, lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) expande para a string "A", e todo o cálculo acontece em tempo de compilação, quando o rustc expande as macros.

Por que isso importa

Um interpretador Lisp escrito com macros de Rust, o que é bastante interessante. Além disso, foi feito em menos de 250 linhas, mantendo-se conciso.

Exemplo

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" e "TRUE"

Outro exemplo divertido é um quine:

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

Esse código avalia a si próprio.

Recursão

Este Lisp atualmente não oferece suporte a uma forma explícita de recursão. Felizmente, recursão explícita não é necessária, basta usar lambdas. É possível escrever uma função simples para concatenar duas 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)))
);

O resultado é "(A B C D)". A função append não menciona append no corpo, mas ainda assim pode ser chamada recursivamente.

Cuidados ao usar

• A macro lisp! avalia apenas uma única expressão. Para avaliar várias expressões, é preciso usar (PROGN expr1 expr2 expr3).
• A forma DISPLAY avalia uma única expressão e depois gera uma instrução println!("{}", stringify!(...)) para imprimir a versão em string dos tokens.
• A lista vazia não é autoavaliável; para obter o valor de lista vazia, use NIL ou (QUOTE ()).
• Listas pontuadas não são suportadas, e cons assume que o último argumento é uma lista.
• A forma define pode ser usada em qualquer lugar e avalia para lista vazia, mas não oferece suporte a recursão.
• TRUE é o único átomo autoavaliável que não é uma função.

Formas suportadas

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

Interpretador metacircular

A seguir está um interpretador Lisp escrito em 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)
);

Esse código funciona, mas tentar avaliar ((lambda (X) X) (quote a)) dentro do interpretador leva mais de 30 segundos e gera mais de um milhão de tokens. A recursão usando um combinador Y explícito não é eficiente aqui. Para resolver isso, seria necessário adicionar uma primitiva de recursão explícita. Para uma excelente explicação sobre como escrever um avaliador metacircular, veja "Roots of Lisp", de Paul Graham.

Explicação técnica

Consulte EXPLANATION.md. As macros simulam a máquina SECD, uma máquina abstrata simples baseada em pilha para avaliar expressões do cálculo lambda.

Ótimos materiais

• "Functional Programming: Application and Implementation", de Peter Henderson
• "A functional correspondence between evaluators and abstract machines.", de Mads Sig Ager e outros (2003)
• "The Implementation of Functional Programming Languages", de Simon Peyton Jones
• Todos os posts sobre Lisp no blog de Matt Might (https://matt.might.net)

TODO

• adicionar letrec
• adicionar definições recursivas

Resumo do GN⁺

• O interpretador Lisp escrito com macros de Rust é bastante interessante e oferece recursos poderosos com código conciso.
• Embora não ofereça suporte explícito a recursão, é possível implementá-la com lambdas.
• O interpretador metacircular não é eficiente, então é necessário adicionar uma primitiva de recursão explícita.
• "Roots of Lisp", de Paul Graham, é um excelente material para entender avaliadores metacirculares.
• Outros projetos com funcionalidades parecidas incluem interpretadores Scheme ou outras variantes de Lisp.