Lisp implementado com macros de Rust

 (github.com/RyanWelly)
1 pontos por GN⁺ 2024-09-15 | 1 comentários | Compartilhar no WhatsApp
  • lisp-in-rs-macros é um interpretador Lisp simples com escopo léxico que funciona apenas com macros declarativas de Rust, e a macro lisp! avalia o código em tempo de compilação para gerar um valor Lisp convertido em string
  • lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) é calculado durante o processo de expansão de macros do rustc e expandido para a string "A"; a implementação completa tem menos de 250 linhas
  • Os exemplos usam CAR, LIST, QUOTE, PROGN, DEFINE, LAMBDA, DISPLAY, e o exemplo de quine mostra uma forma em que o código Lisp é avaliado para si mesmo
  • Recursão explícita não é suportada no momento, mas é possível escrever comportamentos recursivos como append de listas com self application; no entanto, DEFINE em si não trata definições recursivas
  • O exemplo de interpretador metacircular parece funcionar, mas avaliar ((lambda (X) X) (quote a)) leva mais de 30 segundos e gera mais de um milhão de tokens, a ponto de o cargo ser finalizado com sigkill, de tão ineficiente

Lisp executado dentro de macros de Rust

  • lisp-in-rs-macros é um interpretador Lisp com escopo léxico escrito apenas com macros declarativas de Rust
  • A macro lisp! avalia o código Lisp recebido e depois converte o valor Lisp calculado em string
  • Por exemplo, lisp!(CAR (CONS (QUOTE A) (QUOTE (B)))) é expandido para a string "A"
  • Esse cálculo acontece em tempo de compilação, durante a expansão de macros pelo rustc, e não em runtime
  • A implementação tem menos de 250 linhas

Exemplo básico de uso

  • É possível combinar CAR, LIST e QUOTE para obter o primeiro elemento de uma lista
let output = lisp!(CAR (LIST (QUOTE A) (QUOTE B) (QUOTE C)));
assert_eq!(output, "A");
  • Para avaliar várias expressões, usa-se PROGN
    • PROGN avalia todas as expressões e retorna o valor da última
  • DISPLAY primeiro avalia o argumento e depois se expande em uma forma como println!("{}", stringify!(evaled_argument)), convertendo os tokens em string para exibição
lisp!(PROGN
    (DEFINE message (LAMBDA () (QUOTE "hello there")))
    (DISPLAY (message))
    (DEFINE NOT (LAMBDA (X) (COND (X NIL) (TRUE TRUE))) )
    (DISPLAY (NOT NIL))
);
  • O exemplo acima imprime "hello there" e "TRUE"

Quine avaliado para si mesmo

  • O exemplo de quine mostra uma forma em que o código Lisp é avaliado para si mesmo
lisp!
       ((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))));
  • Esse código se expande para a seguinte chamada de stringify!
stringify!(((LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s)))
       (QUOTE (LAMBDA (s) (LIST s (LIST (QUOTE QUOTE) s))))));

Recursão e self application

  • Este Lisp atualmente não oferece suporte a recursão explícita
  • Mesmo sem recursão explícita, é possível criar comportamento recursivo apenas com lambdas
  • A função append do exemplo não menciona diretamente o nome append no corpo; ela faz chamadas recursivas por meio de self application usando o 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)))

)
  • Esse código produz "(A B C D)" como resultado

Restrições de uso

  • A macro lisp! avalia apenas uma única expressão
    • Várias expressões precisam ser agrupadas em (PROGN expr1 expr2 expr3)
  • A lista vazia não é autoavaliável
    • O valor de lista vazia pode ser obtido com NIL ou (QUOTE ())
    • A lista vazia é o único objeto falsy
  • Dotted lists não são suportadas
    • CONS assume que o último argumento é uma lista
  • DEFINE pode ser usado em qualquer lugar e é avaliado como lista vazia, mas não oferece suporte a recursão
  • TRUE é o único atom autoavaliável que não é uma função

Forms suportadas

DEFINE
QUOTE
LAMBDA
LET
PROGN
CAR
CDR
CONS
LIST
EQ
ATOM
APPLY
  • DEFINE está mais próximo de uma definição interna ao estilo Scheme do que de uma definição recursiva Lisp propriamente dita

Interpretador Lisp escrito em Lisp

  • O repositório inclui um exemplo de interpretador metacircular escrito sobre esse Lisp
  • O exemplo define o combinador Y2 para dois argumentos, CADR, CAAR, ASSOC, eval e outros
  • O interpretador parece funcionar, mas tentar avaliar ((lambda (X) X) (quote a)) leva mais de 30 segundos
  • Essa avaliação gera mais de um milhão de tokens e acaba ficando grande o bastante para o cargo ser encerrado com sigkill
  • A recursão com combinador Y explícito é especialmente ineficiente nesse caso
  • O texto diz que seria necessário adicionar uma primitive de recursão explícita para corrigir isso
  • Como walkthrough para escrever um avaliador metacircular, é recomendado "Roots of Lisp", de Paul Graham

Forma de implementação e materiais de referência

  • A explicação técnica está em EXPLANATION.md
  • As macros essencialmente simulam uma máquina SECD
    • A máquina SECD é uma máquina abstrata simples baseada em pilha para avaliar termos do cálculo lambda

Materiais de referência

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

TODO

  • adicionar letrec
  • adicionar define recursivo

Leituras relacionadas

1 comentários

 
GN⁺ 2024-09-15
Opiniões no Hacker News

  • A décima regra de Greenspun apareceu de novo: https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

    • Isso fala de bases de código cujo objetivo principal não é implementar Lisp, então não parece se aplicar muito bem aqui
    • Um bom exemplo dessa regra é que C++ está redescobrindo car/cdr dentro da linguagem de templates, em velocidade glacial
      Só no C++26 será possível obter o car de um pacote de parâmetros de nomes de tipos com Args...[0]
      Não entendo por que não introduzem um nil para pacotes de parâmetros vazios e funções car/cdr, e permitem armazenar pacotes de parâmetros, em vez dessa bagunça sintática atual
    • Vem imediatamente à cabeça a frase: “qualquer programa em C ou Fortran suficientemente complexo contém uma implementação ad hoc, especificada informalmente, cheia de bugs e lenta de metade do Common Lisp”
    • Não sei o que “suficientemente complexo” quer dizer, e a definição não é muito boa

  • Já tentei fazer algo parecido antes, mas havia o problema de não conseguir definir símbolos com hífen
    Algo como DEFINE MY-FN... não funcionava, porque o Rust dividia os tokens no hífen
    É uma diferença pequena, mas não dava para colar trechos reais de código Lisp como estavam; era preciso trocar tudo por underscores. Fico curioso se esta implementação é igual

    • Por enquanto, ela assume que todos os átomos são identificadores Rust. Isso facilita a implementação, porque dá para casar com $x:ident, então hífens dentro de átomos não são suportados
      Em vez disso, acho que daria para casar algo como $x:ident $(- $y:ident)*. Seria preciso mudar alguns detalhes das ramificações da macro, mas parece viável
    • Não parece haver problema, não? DEFINE MYᜭFN... funciona bem

  • Seria bom ter uma implementação de Lisp baseada em Rust e bem suportada, não só macros
    Fico curioso sobre quanto da segurança de memória seria preservada ou perdida ao construir em cima de Rust. Será que é mesmo possível aproveitar o borrow checker de uma forma sensata?

    • Alguns compiladores Lisp, como o SBCL, também permitem verificação de tipos em tempo de compilação mais ampla, mas essa informação precisa ser fornecida pelo programador e normalmente é mais parte de uma etapa de otimização do que do desenvolvimento incremental cotidiano
      Lisp costuma ser definido por sua natureza dinâmica, e a verificação de tipos em tempo de execução é uma grande parte disso. Fazer o programador se preocupar antecipadamente com a forma de gerenciamento de objetos entra em conflito com a liberdade e a expressividade esperadas nesse tipo de sistema
      Em compensação, o compilador em si pode ser relativamente simples. Código comum sem declarações adicionais é seguro por padrão e, em uma máquina virtual de bytecode como CLISP ou em máquinas Lisp com verificação de tipos por hardware, essas declarações podem ser ignoradas e ainda assim tudo continua seguro
      O SBCL compila código bem rápido, e ouvi dizer que outras implementações são ainda mais rápidas. Já o compilador Rust é mais propenso a apresentar a jovens programadores o conceito de thrashing
      Vejo os dois como mundos mais incompatíveis do que parecem à primeira vista. Lisp é essencialmente a linguagem representante da filosofia “The Right Thing”, e C é uma linguagem “Worse is Better”. Rust não é nenhum dos dois; parece algo totalmente diferente, a ponto de precisar de um novo nome que reflita os traços ruins das duas filosofias
      Não digo isso para desmerecer o texto original; ainda é um hack muito legal
    • Steel parece bom: https://github.com/mattwparas/steel
      Há outros Lisps também (https://github.com/alilleybrinker/langs-in-rust). Mas parecem ser mantidos de forma menos ativa

  • Foi divertido criar isso, e também aprendi que o rust-analyser não consegue lidar com macros que geram milhões de tokens

  • Sei que o clima é todo mundo aplaudir dizendo “que divertido”, mas toda vez que vejo algo assim fico desgostoso com o fato de isso ser possível em Rust
    Rust já não era uma linguagem simples, mas acho que se tornou algo muito mais difícil de lidar do que no início

    • Concordo que Rust não é uma linguagem simples
      Mas não entendo muito bem por que você desgosta do fato de isso ser possível. O sistema de macros consegue gerar código quase infinitamente complexo, mas não sei se implementar um Lisp sandboxed com macros é um exemplo forte de que Rust ficou mais difícil de administrar do que era no começo
      Por outro lado, como o sistema de tipos de Rust é Turing-completo, assim como templates de C++ ou o sistema de tipos de Haskell, também fico com vontade de ver um Lisp implementado desse jeito
    • Discordo fortemente dessa parte. A equipe do Rust vem tornando a linguagem continuamente mais fácil de usar ao remover restrições e tornar os recursos mais ortogonais
      Exemplos representativos são lifetimes não lexicais, impl Trait em posição de retorno e traits assíncronas. Antes da versão 1.0, havia até referências com GC embutidas com sintaxe especial, mas recursos assim foram removidos
    • A única grande mudança prática desde a 1.0 foi async. Se quiser viver sem async, isso é totalmente opcional, uma parte completamente opcional da linguagem
      Se você quer uma linguagem que tenha simplicidade como princípio, Rust nunca foi essa linguagem, e há muitas outras opções
    • Na verdade, é preciso muito pouco para que algo assim seja possível. Acho que até daria para fazer com macros de C, que são consideradas simples
      Conferi, e ganhei essa aposta: https://github.com/kchanqvq/CSP
    • Macros não foram sempre extremamente poderosas e, ao mesmo tempo, complicadas? Eu não incluiria a parte de macros na complexidade da linguagem
      Refiro-me especialmente a “escrever” macros; vejo isso mais como um recurso extra que você pode usar ou não

  • Uau, isso usa macro_rules

  • Mas não era que C++ não era uma linguagem sã porque os templates são Turing-completos?

    • Basta conhecer um pouco de C++ para saber que não é uma linguagem sã. Pelo menos macros em Rust não são literalmente substituição textual, então é um passo em direção à luz
    • Turing-completo e Turing tarpit são coisas diferentes
      Não sei em qual dos dois lados o sistema de macros do Rust cai
    • Desenvolver com templates de C++ é um inferno. Rust pelo menos tem macro_expand, e o fato de as ferramentas de Rust serem bem feitas pesa muito

  • Carp também não pode ficar de fora. É um Lisp que usa borrow checking, uma espécie de “Rust” do mundo Lisp
    1: https://github.com/carp-lang/Carp