A linguagem Python homoicônica

 (aljamal.substack.com)
2 pontos por GN⁺ 2024-05-13 | 2 comentários | Compartilhar no WhatsApp
  • A homoiconicidade do Lisp é a propriedade de tratar código e dados na mesma forma, e, ao transportar o clássico “Lisp in Lisp” para Python, essa ideia aparece dentro de uma sintaxe mais familiar
  • Originalmente, o Lisp mantinha junto a M-expression, como representação de código, e a S-expression, como representação de dados, e o “Lisp in Lisp” implementa um Lisp de S-expressions usando M-expressions
  • A versão em Python representa S-expressions como listas de Python e traduz M-expressions para chamadas de função e condicionais, compondo um interpretador sem parser separado
  • O primeiro interpretador se apoia em operações primitivas de lista como atom, eq, car, cdr, cons, append, e, para suportar lambda, acrescenta assoc, pairlis e uma lista de ambientes
  • eval recebe a expressão e o ambiente juntos para tratar o vínculo de variáveis e conecta argumentos e valores no estilo de escopo dinâmico por meio de pairlis e assoc

A integração entre código e dados mostrada pelo Lisp

  • O Lisp deixou várias ideias ainda válidas décadas depois por meio do artigo sobre Lisp de John McCarthy e do manual do Lisp 1.5, no começo dos anos 1960
  • Entre elas, o ponto central é a homoiconicidade
    • Em linguagens comuns, o código é entendido como uma sequência de operações agindo sobre dados
    • O Lisp trata código e dados na mesma forma, borrando a fronteira entre operadores e operandos
  • Alan Kay chamou o código “Lisp in Lisp”, no rodapé da página 13 do manual do Lisp 1.5, de “Maxwell's Equations of Software”
    • Há uma citação no sentido de que foi uma grande revelação perceber que algumas linhas de código continham o mundo inteiro da programação

Como transportar “Lisp in Lisp” para Python

  • O objetivo é reescrever o clássico código “Lisp in Lisp” em Python, preservando ao máximo o espírito do código original
  • O Lisp possui duas formas de expressão sintática
    • M-expression: representação de código, abreviação de meta
    • S-expression: representação de dados, abreviação de symbolic
    • As duas formas são semanticamente equivalentes
  • O código tradicional de “Lisp in Lisp” é escrito em M-expression e implementa um Lisp de S-expressions
  • Na implementação em Python, as S-expressions do Lisp são representadas como listas de Python
    • Lisp significa “List Processing” e funciona em torno de uma única estrutura de dados: a lista
    • As listas de Python servem como uma representação adequada para emular as S-expressions do Lisp
  • As M-expressions são traduzidas para estruturas de código do Python, como chamadas de função e condicionais
    • Graças a esse mapeamento, é possível criar o interpretador sem manipulação de strings nem implementação de um parser separado

O primeiro interpretador feito com primitivas de lista

  • Uma implementação de Lisp precisa de algumas funções básicas fornecidas de fora da linguagem
  • As primitivas de lista usadas na implementação em Python são as seguintes
    • atom(x): verifica se x é uma lista
    • eq(x,y): verifica se x e y são iguais
    • car(x): o primeiro elemento da lista
    • cdr(x): o restante da lista
    • cons(x,y): adiciona um átomo à lista
    • append(x,y): concatena duas listas
  • Exceto por algumas primitivas recursivas, foi possível usar Llama3-70b na Groq para montar rapidamente um interpretador que executa um subconjunto do código “Lisp in Lisp”
  • No exemplo, listas de Python se comportam como S-expressions
  • O código completo está disponível em github gists

Extensões para lambda e recursão

  • Na primeira implementação, faltava um recurso importante: lambda
    • lambda é a principal forma de definir e chamar funções anônimas no Lisp
    • Sem lambda, não é possível implementar recursão em Lisp
    • Sem recursão, não se alcança a completude de Turing, o critério mínimo para calcular tudo o que é computável
  • Para incluir lambda, foram adicionados assoc(x,y) e pairlis(x,y)
    • assoc(x,y) faz busca de chave/valor implementada com listas, usando listas de associação
    • pairlis(x,y) agrupa duas listas, como o zip(x,y) do Python
  • O Lisp original precisava tratar até uma simples varredura linear com recursão
    • Isso porque o Lisp original não tinha laços
    • Na tradução para Python, assoc e pairlis podem ser expressos de forma mais concisa com list comprehensions
  • No tratamento de COND, o evcon do Lisp original é traduzido para um laço, e no tratamento de LAMBDA a mesma abordagem é aplicada a evlis

Lista de ambientes e escopo dinâmico

  • A função eval do Lisp original recebe dois argumentos
    • O primeiro é a S-expression a ser avaliada
    • O segundo é uma lista de ambientes formada por pares chave/valor
  • O ambiente mantém o vínculo de variáveis durante o tratamento de LAMBDA
    • Se uma função tem a variável x e recebe um dado, pairlis associa o símbolo x ao dado
    • O valor associado é armazenado ou acrescentado à lista de ambientes
    • Quando x é necessário, assoc o procura no ambiente e o reinsere na expressão
  • Esse modo de vínculo é chamado de escopo dinâmico
  • A implementação final é uma tradução do “Lisp in Lisp” original para Python e inclui, no exemplo final, a execução de lambda

Leituras relacionadas

2 comentários

 
GN⁺ 2024-05-13
Opiniões do Hacker News

  • Se você tem interesse em uma Lisp para scripting simples, rápida e com cara de Python, vale dar uma olhada em linguagens no estilo Clojure como Hy e Janet

    1. Hy(https://hylang.org/): compila para bytecode Python e, embora normalmente seja mais lenta que Python, é compatível com todas as bibliotecas Python
    2. Janet(https://janet-lang.org/): uma máquina virtual embutida bem leve, no estilo Lua, com cerca de 1 MB; é aproximadamente 2 vezes mais rápida que Python em operações semelhantes e a interoperabilidade com C é muito fácil
    • Para scripting rápido com cara de Python, também existe o Common Lisp “com baterias incluídas” https://github.com/ciel-lang/ciel
      É fornecido como um binário de inicialização rápida e também inclui bibliotecas para tarefas do dia a dia
      Para a parte CL↔Python, https://github.com/CodyReichert/awesome-cl?tab=readme-ov-fil... também vale como referência
    • Hy é mais lenta que Python? Pelo menos em tempo de execução, não deveria ser
      Eu sou mantenedor do Hy, e se aparecer uma diferença de desempenho significativa, isso é um bug
      1. Basilisp(https://github.com/basilisp-lang/basilisp): “um dialeto Lisp compatível-ish com Clojure voltado para Python 3.8+”
    • Pode parecer uma implicância, mas Lisp sempre me pareceu uma linguagem que provoca rejeição por causa dos parênteses envolventes obrigatórios
      M-expressions evitam essa armadilha, então fico curioso se já existiu uma linguagem real que mantivesse a homoiconicidade e a elegância conceitual de Lisp sem exigir esses parênteses
    • https://github.com/yaml/yamlscript
      É exatamente aquilo que você está pensando. A descrição também é bem direta: “Program in YAML”
      Quase não há mais o que dizer

  • Espera, isso não é simplesmente uma Lisp implementada em Python?
    Não parece ser um Python homoicônico, como o título sugere; o que estou deixando passar?

    • Pela décima regra de Greenspun, está certo: https://en.m.wikipedia.org/wiki/Greenspun's_tenth_rule
    • Eu também fiquei bem empolgado achando que era um Python homoicônico que eu poderia fazer meus colegas usarem sem convencê-los a adotar Lisp, mas não era; era só Lisp mesmo
    • Parece isso. Fiquei curioso porque queria ver esse Python homoicônico, mas nem sei bem se seria possível
      Para isso, a sintaxe de Python teria de ser composta por tuplas, listas e dicionários, e o interpretador teria de avaliá-los diretamente
    • Qual é a diferença?

  • Outra linguagem funcional que pode ser implementada de forma concisa em Python é o Binary Lambda Calculus
    Uma parte considerável do código lida com o modelo puro de entrada e saída do BLC, e, para busca de variáveis, usa índices de de Bruijn para indexar um array de ambiente em vez de uma lista associativa
    A mesma página também tem implementações em 9 outras linguagens, e o autointerpretador do BLC é o mais conciso, com 232 bits (29 bytes), incluindo parser e tokenizer
    [1] https://rosettacode.org/wiki/Universal_Lambda_Machine#Python

  • O curso introdutório de programação do MIT faz todos os alunos escreverem um interpretador Lisp em Python
    É um vestígio da época em que esse curso, no passado, era de fato ministrado em Lisp
    https://py.mit.edu/spring24

    • De modo parecido, uma disciplina que cursei na universidade também fazia implementar um interpretador Lisp básico em Lisp

  • Já fiz algo parecido com listas em JS: https://github.com/andrelaszlo/js-lisp

  • É engraçado e irônico ver linguagens modernas redescobrindo, décadas depois, recursos incríveis do Lisp
    Alguns dias atrás, fiquei irritado porque um programa Python que estava chamando a API do meu servidor doméstico por 9 horas travou. Eram chamadas de API parecidas, e eu estava chamando um LLM com templates de prompt predefinidos e restrições gramaticais
    Eu queria salvar o estado do programa e encerrar antes de rodar separadamente as iterações restantes, mas não encontrei uma forma de modificar o código Python em execução ou inspecionar as variáveis, e acabei perdendo 9 horas de trabalho
    Alguns dias depois vi https://malisper.me/debugging-lisp-part-1-recompilation/, e fiquei impressionado ao descobrir que Common Lisp já trazia esse tipo de recurso embutido na linguagem havia décadas. O mesmo vale para outros recursos, como o sistema de macros mais poderoso

    • Não é surpreendente que linguagens modernas redescubram, décadas depois, recursos do Lisp. A família Lisp reúne algumas das linguagens mais flexíveis e expressivas que existem
      Mas esse também é o problema. Ela é expressiva demais
      Lisp sempre me lembra artes visuais de mídia mista: a liberdade de expressão parece ótima, mas no fim o resultado muitas vezes acaba sendo, em geral, inferior ao de artes mais tradicionais de mídia única. Fica claro que as restrições do meio são tão importantes quanto a expressividade
    • Para inspecionar o estado até certo ponto, dá para usar Py-spy ou Pystack
      Ou também https://github.com/malor/cpython-lldb
      Mais métodos em https://github.com/albertz/pydbattach/
    • Se é um processo que roda por várias horas, você deve salvar o trabalho em disco e estar preparado para recomeçar do ponto em que parou
    • Nenhuma exceção foi lançada?

  • Como esta implementação é Python homoicônico?

  • Existe algum Lisp com um sistema de tipos que ajude, em alguma medida, a controlar a tendência de Lisp ficar difícil de ler à medida que o programa cresce?
    Mesmo que não seja um sistema de tipos, fico curioso se há algum outro elemento que consiga domar essa característica
    Metaprogramação é realmente incrível, mas às vezes ela parece o Haskell abstrato mais inescrutável que já vi, só que sem sequer assinaturas de tipos para servir de guia
    Vejo sistemas de tipos e linters como as melhores ferramentas para domar código automaticamente, mas tenho dificuldade de imaginar como conter as tendências de projetos Lisp sem restringir justamente o motivo de escolher Lisp

    • Se for um Lisp com sistema de tipos, Common Lisp vem à mente
      O SBCL, que é praticamente o mais próximo de um padrão de fato, também tem uma checagem de tipos em tempo de compilação bem boa
      Por exemplo, se você escrever (declare (type String a b)) e depois (+ a b), ele emite um aviso dizendo que o tipo derivado de A é STRING, mas deveria ser NUMBER
      O principal motivo de eu ter migrado de Scheme para CL foi essa checagem de tipos, e depois continuei por causa de pequenos recursos agradáveis como restarts e continuable asserts
    • No lado mais amigável e acessível há Typed Racket; no lado poderoso, mas complexo, há Shen
    • https://en.wikipedia.org/wiki/Dylan_(programming_language)

  • Um Python orientado a expressões seria muito melhor que o Python atual
    Este texto não é o que o título sugere, mas é uma boa explicação de Lisp

    • Um Python orientado a expressões simplesmente não seria Python
      O que não seria necessariamente ruim, mas “tratar expressões como sintaxe de segunda classe” é uma escolha bastante fundamental e deliberada. Também é um projeto feito para dificultar a vida de desenvolvedores que queiram escrever sopa de parênteses
      Por isso lambda: e := são propositalmente desajeitados para desencorajar o uso, e também não dá para escrever funções anônimas
      Python é uma linguagem que diz: se você quer fazer algo inteligente, faça isso com iteradores, não com objetos chamáveis

  • Eu queria que tudo tivesse a ausência de sintaxe ao estilo Lisp
    Para mim isso é melhor e, felizmente, em CL é fácil fazer assim
 
kayws426 2024-05-13

Uma variação de Lisp incorporada ao Python
https://hylang.org/