Textos que mudaram minha forma de pensar sobre linguagens de programação
(bernsteinbear.com)- Apresenta vários textos, artigos e vídeos que mudaram de forma fundamental a visão sobre linguagens de programação e compiladores
- Materiais que ampliaram muito o entendimento sobre implementação prática de GC, projeto de otimizadores, alocação de registradores e engines de expressões regulares
- Explicações acessíveis, com exemplos reais de código, sobre algoritmos e estruturas usadas na prática, como Z3, domínios abstratos, forma SSA e E-Graphs
- Cada material explica conceitos complexos de forma concisa, extensível e fácil de entender
Apresentação de textos que transformaram minha visão sobre linguagens de programação e compiladores
- De vez em quando encontro artigos, posts de blog e vídeos sobre linguagens de programação e compiladores que mudam completamente minha forma de pensar sobre o assunto
- No caso de alguns textos, o impacto foi tão forte que nem consigo mais lembrar como eu pensava antes de lê-los
- Abaixo está uma apresentação desses materiais (sem ordem específica)
Sobre GC, otimizadores, domínios abstratos e alocação de registradores
- O texto de Andy Wingo, a simple semi-space collector, mostra muito bem como aplicar na prática os conceitos de coletor de lixo Cheney/cópia/compactação
- A implementação central do GC no texto é muito concisa, extensível e pode ser entendida em meio dia
- O texto de CF Bolz-Tereick, Implementing a Toy Optimizer, provoca uma mudança de perspectiva sobre a abordagem de rewrite de instruções em otimizadores
- Em vez de uma simples busca e substituição, destaca o uso de forwarding pointer e introduz o conceito de union-find
- Toda a série do toy optimizer traz algo novo e interessante em cada texto
- A Knownbits Abstract Domain for the Toy Optimizer, Correctly apresenta ao mesmo tempo um novo domínio abstrato e formas de usar o Z3
- Mostra não só como o Z3 é usado para várias provas de operações numéricas, mas também exemplos de uso como engine de verificação de código Python
- Introduz a ideia de que, se o Z3 não encontrar contraexemplos, isso garante a correção do código
- Em Cranelift, Part 3: Correctness in Register Allocation, Chris Fallin explica uma abordagem de provar diretamente a correção da alocação de registradores para cada entrada
- Em ambiente de produção, o resultado é ou uma alocação correta ou um crash significativo
- Também introduz uma abordagem de explorar o espaço de estados e detectar bugs com técnicas de fuzzing
Sobre parsing, interpretadores, JIT e estruturas abstratas
- Regular Expression Matching: the Virtual Machine Approach, de Russ Cox, apresenta a implementação de uma engine de expressões regulares em cerca de 50 linhas de código fácil de ler
- No processo, também explica de forma clara os princípios de corrotinas, fibras, escalonadores e afins
- micrograd, de Andrej Karpathy, é um exemplo ultracompacto de implementação capaz de fazer uma rede neural funcionar sem bibliotecas externas, ajudando a entender a estrutura e os princípios básicos de machine learning
- Em How I implement SSA form, Fil Pizlo apresenta uma nova forma de melhorar a estrutura de union-find
- Na transformação para SSA, ponteiros adicionais são gerenciados como uma Identity tag dentro do objeto
- Além disso, traz ideias como Phi/Upsilon form, efeitos de heap no estilo TBAA e outros pontos para reflexão
- Speculation in JavaScriptCore, de Fil Pizlo, trata em detalhes de várias formas de implementar otimizadores no JavaScriptCore
- Cada releitura rende novos insights
Projeto de compiladores, parsers, estrutura de IR e E-Graphs
- Na apresentação de Chandler Carruth, Modernizing Compiler Design for Carbon Toolchain (por volta dos 29 minutos), ele explica como definir uma meta de tempo de compilação absurdamente rápida e como desenhar a arquitetura como um todo
- A partir de cerca de 40 minutos, ele destrincha a estrutura por camadas
- A Python Interpreter Written in Python, de Allison Kaptur, ajuda a entender de forma simples como funciona o interpretador de bytecode interno do CPython
- Parsing expressions by precedence climbing, de Eli Bendersky, apresenta o método de parsing Precedence Climbing, mais fácil de entender e com menor custo de desenvolvimento do que um parser recursivo descendente tradicional
- Ruby JIT Challenge, de Takashi Kokubun, mostra geração de código e um novo método de alocação de registradores (stack folding at compile-time)
- [An Incremental Approach to Compiler Construction (PDF)(https://bernsteinbear.com/assets/img/11-ghuloum.pdf) explica uma forma de implementação em passagem única que permite entender de uma vez o projeto tradicional de compiladores em múltiplas etapas
- A abordagem adiciona cada funcionalidade gradualmente, de ponta a ponta
- Lessons from Writing a Compiler, de Fernando Borretti, explica estratégias de implementação de compiladores de forma claramente articulada
- O artigo egg: Fast and extensible equality saturation muda de forma fundamental a percepção sobre otimizadores e a ordem de aplicação de passes
- Propõe pensar em criar um hipergrafo comprimido com todas as versões possíveis da expressão e então escolher a melhor versão
- Em Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations, Chris Fallin mostra que e-graphs também funcionam de forma eficaz em compiladores comerciais reais
- Acyclic Egraphs and Smart Constructors, de Phil Zucker, explora a estrutura de e-graph acíclico e o uso de smart constructors
- No início foi difícil de entender, mas com o tempo o entendimento foi se aprofundando
Armazenamento de AST, análise dinâmica paralela em larga escala e outros
- este comentário no Reddit, de Bob Nystrom, e Flattening ASTs, de Adrian Sampson,
- discutem como armazenar a AST de forma quase tão compacta quanto bytecode, e
- levam a uma discussão mais ampla sobre como armazenar nós de IR dessa forma também possibilitaria análise paralela lock-free em larga escala
- menções de Cliff Click sobre velocidade de alocação de buffer também influenciaram esse modo de pensar
1 comentários
Comentários do Hacker News
Gosto muito deste post; andei estudando bastante pesquisa em ciência da computação recentemente, mas ainda há coisas mencionadas aqui com as quais eu não tinha tido contato. Queria apresentar alguns artigos de que gosto e que não estão aqui: “Open, Extensible Object Models”, de Ian Piumarta, trata de um sistema metaobjeto orientado a objetos mínimo que dá ao programador o máximo de liberdade; basicamente, só define a operação de envio de mensagens, e todo o resto pode ser alterado em tempo de execução. Parece uma versão prática de “Art of the Metaobject Protocol”. “Scripting: Higher-Level Programming for the 21st Century”, de John Ousterhout, trata da dicotomia entre linguagens de programação de sistemas e linguagens de script. Sempre queremos uma linguagem multiparadigma perfeita que faça tudo de forma rápida e produtiva, mas muitas vezes é melhor combinar uma linguagem de sistemas compilada, rápida e complexa com um frontend interpretado, conveniente e flexível. Na verdade, muitas vezes só usar C com Tcl já basta. É leitura obrigatória para quem cria linguagens de programação. Project Oberon, de Niklaus Wirth, é um exemplo de implementação de um sistema computacional completo, da UI de alto nível até o kernel, o compilador e uma arquitetura de CPU parecida com RISC. Ele fez uma defesa poderosa de “lean software” e realmente colocou isso em prática. Numa era como a de hoje, cheia de inferno de dependências e abstrações em excesso, isso parece um artesanato perdido
Gosto muito deste post; textos sobre linguagens de programação mudaram a forma como eu vejo a própria programação. Frequentemente me lembro de uma citação do TAPL (Types and Programming Languages) sobre “segurança”: uma linguagem segura é aquela que impede o programador de atirar no próprio pé e protege as próprias abstrações. Ou seja, é importante a capacidade de garantir a integridade tanto das abstrações fornecidas pela linguagem quanto das abstrações de nível superior criadas pelo programador. Por exemplo, se existe a abstração de array, ela só deveria poder ser alterada quando atualizada explicitamente, e não deveria acabar modificando por engano outra estrutura de dados
Falando de hábitos de desenvolvimento interessantes… Aaron Hsu, famoso por APL, escreve código com uma caneta-tinteiro em estilo caligráfico quando está organizando as ideias. Eu faço algo parecido: pego uma caneta esferográfica barata e desenho algo como fluxogramas de objetos em Python para organizar o pensamento. É uma espécie de UML de baixo custo
Eu também acabo procurando uma caneta-tinteiro quando estou lidando com os problemas mais difíceis. Usá-la dá a sensação de entrar num espaço mental completamente diferente. As limitações de edição acabam incentivando um pensamento mais consistente e linear, mas a possibilidade de transitar livremente entre inglês, código, matemática, diagramas etc. libera a criatividade
A relação entre escrita à mão e melhora da memória já foi demonstrada de fato. Fazer anotações no computador é quase como deixar impressões digitais no cabo de uma ferramenta. Espero que a tecnologia de OCR fique tão boa que seja possível registrar tudo perfeitamente só com escrita à mão e ainda assim armazenar e pesquisar depois
Eu realmente recomendaria assistir às palestras do Rich Hickey, especialmente as mais antigas. Eu também vi esse tipo de palestra e minha forma de enxergar a programação em si mudou completamente
Para mim, junto com “Programming Perl”, do Larry Wall, as palestras do Rich Hickey foram as mais influentes
Dá até vontade de brincar dizendo para pular a palestra “Simple made easy”, porque ela foi tão citada por palestrantes de conferências nos últimos 10 anos que virou clichê. Pessoalmente, gosto mais de “Hammock driven development”, mas ela não é tão adequada para recomendar no ambiente de trabalho
É uma pena que Abdulaziz tenha ficado em silêncio depois de voltar para o Kuwait. Ele foi estagiário da Maxine VM em 2009 e era uma pessoa realmente ótima. Aquele artigo é uma joia de verdade
Teve recentemente um bom post sobre interpretadores baseados em closures para acelerar interpretadores. Usei essa técnica para fazer um interpretador simples de brainfuck e ele ficou bem rápido. Provavelmente não vou usar isso em nenhum outro lugar, mas foi uma experiência útil
Eu queria que existissem textos assim sobre linguagens de mais alto nível, como JavaScript ou .NET. Este autor é claramente muito inteligente, mas trabalha num nível mais baixo do que a maioria dos usuários — ou mais alto?
Os outros textos do blog dele também são excelentes
Sobre micrograd: queria saber se existe mais documentação além do código-fonte no repositório do GitHub
Digo isso como alguém que gosta dessa pessoa, mas os textos aqui não são sobre PL (linguagens de programação) em si; quase tudo é sobre compiladores, exceto o coletor de lixo. Claro, compiladores também são legais, mas isso é um tema diferente de PL