Tenho o prazer de anunciar a conclusão do meu primeiro compilador para uma linguagem de programação! Malcc é um compilador incremental de Lisp AOT escrito em C.

Vou falar brevemente sobre seus muitos anos de desenvolvimento e o que aprendi no processo. Título alternativo do artigo: "Como escrever um compilador em dez anos ou menos."

(No final, há TL; DR , se você não se importa com o plano de fundo).

Demonstração do compilador

tim ~/pp/malcc master 0 → ./malcc Mal [malcc] user> (println "hello world") hello world nil user> (+ 1 2) 3 user> (def! fib2 (fn* (n) (let* (f (fn* (n1 n2 c) (if (= cn) n2 (f n2 (+ n1 n2) (+ c 1))))) (f 0 1 1)))) <lambda> user> (fib2 25) 75025 user> ^D% tim ~/pp/malcc master 0 → ./malcc examples/hello.mal hello world tim ~/pp/malcc master 0 → ./malcc --compile examples/hello.mal hello gcc -g -I ./tinycc -I . -o hello hello.c ./reader.c ./printer.c ./hashmap.c ./types.c ./util.c ./env.c ./core.c ./tinycc/libtcc.a -ledit -lgc -lpcre -ldl tim ~/pp/malcc master 0 → ./hello hello world tim ~/pp/malcc master 0 → 

Falhas com sucesso

Por quase dez anos, sonhei em escrever um compilador. Sempre fui fascinado pelo trabalho de linguagens de programação, especialmente de compiladores. Embora eu tenha imaginado o compilador como magia negra e entendido que era impossível para um mero mortal como eu fazê-lo do zero.

Mas eu ainda tentei e estudei ao longo do caminho!

Primeiro, o intérprete

Em 2011, comecei a trabalhar em um intérprete simples para o idioma fictício Airball (airball pode ser traduzido como "muff"). Por nome, você pode avaliar o grau de minha incerteza de que funcionará. Era um programa Ruby bastante simples que analisava o código e percorria uma árvore de sintaxe abstrata (AST). Quando o intérprete ainda funcionava, renomeei para Lydia e reescrevi para C para torná-lo mais rápido.



Lembro que a sintaxe de Lydia me pareceu muito inteligente! Eu ainda gosto de sua simplicidade.

Embora Lydia estivesse longe de ser um compilador perfeito, isso me inspirou a continuar experimentando. No entanto, eu ainda estava atormentado por perguntas, como fazer o compilador funcionar: no que compilar? preciso aprender assembler?

Em segundo lugar, o compilador e intérprete de bytecode

Como próximo passo, em 2014, comecei a trabalhar no Scheme-vm , uma máquina virtual para Scheme escrita em Ruby. Eu pensei que uma máquina virtual com sua própria pilha e bytecode seria um estágio de transição de um intérprete com passes AST e um compilador completo. E como Scheme é formalmente definido , não há necessidade de inventar nada.

Eu tenho mexido com o schema-vm há mais de três anos e aprendi muito sobre compilação. No final, percebi que não poderia terminar este projeto. O código se transformou em um verdadeiro caos, mas não havia fim à vista. Sem um mentor ou experiência, eu parecia vagar no escuro. Como se viu, a especificação da linguagem não é a mesma do manual para ela. Lição aprendida!

No final de 2017, adiei o esquema-vm em busca de algo melhor.

Encontro com Mal

Em algum momento de 2018, me deparei com Mal , um intérprete Lisp ao estilo Clojure.

Mal foi inventado por Joel Martin como uma ferramenta de treinamento. Desde então, mais de 75 implementações em diferentes idiomas foram desenvolvidas! Quando olhei para essas implementações, percebi que elas ajudam muito: se eu estiver travado, posso procurar dicas na versão Ruby ou Python. Finalmente, pelo menos alguém fala minha língua!

Também pensei que, se pudesse escrever um intérprete para Mal, poderia repetir os mesmos passos - e criar um compilador para Mal.

Intérprete de Mal em Rust

Primeiro, comecei a desenvolver o intérprete de acordo com o passo a passo . Naquela época, eu estava estudando ativamente o Rust (deixarei para outro artigo), então escrevi minha própria implementação do Mal in Rust: mal-rust . Veja aqui para mais informações sobre esse experimento.

Foi um prazer perfeito! Não sei como agradecer ou elogiar Joel por criar um excelente guia para Mal. Cada etapa é descrita em detalhes , existem fluxogramas, pseudo-código e testes ! Tudo o que um desenvolvedor precisa para criar uma linguagem de programação do início ao fim.

No final do tutorial, consegui executar minha implementação de Mal para Mal, escrita em Mal, além da implementação de Rust. (dois níveis de profundidade, uau). Quando ela trabalhou pela primeira vez, pulei em uma cadeira de emoção!

Compilador Mal C

Assim que provei a viabilidade da ferrugem, imediatamente comecei a pesquisar como escrever um compilador. Compilar para montador? Posso compilar o código da máquina diretamente?

Eu vi o montador x86 escrito em Ruby. Ele me intrigou, mas o pensamento de trabalhar com montador me fez parar.

A certa altura, deparei-me com este comentário no Hacker News , que se referia ao Tiny C Compiler como um "back-end de compilação". Pareceu uma ótima ideia!

O TinyCC possui um arquivo de teste mostrando como usar a libtcc para compilar o código C a partir do programa C. Este é o ponto de partida para o "hello world".

Voltando ao passo a passo de Mal, lembrando meu conhecimento de C, em alguns meses de noites livres e fins de semana, pude escrever o compilador Mal. Foi um verdadeiro prazer.



Se você está acostumado a desenvolver testes, avalie a disponibilidade de um conjunto preliminar de testes. Os testes levam a uma implementação de trabalho.

Não posso falar muito sobre esse processo, a menos que repita: o manual do Mal é um verdadeiro tesouro. A cada passo, eu sabia exatamente o que fazer!

Dificuldades

Olhando para trás, aqui estão algumas dificuldades ao escrever o compilador Mal, onde eu tive que mexer:

1. As macros devem compilar em tempo real e estar prontas para serem executadas em tempo de compilação. Isso é um pouco desconcertante.
   
2. É necessário fornecer um “ambiente” (uma árvore de hashes / matrizes / dicionários associativos com variáveis ​​e seus valores), tanto para o código do compilador quanto para o código final do programa compilado. Isso permite definir macros em tempo de compilação.
   
3. Como o ambiente está disponível no momento da compilação, inicialmente o Malcc detectou erros indefinidos durante a compilação (acesso a uma variável que não foi definida) e, em alguns lugares, isso violou as expectativas do conjunto de testes. No final, para passar nos testes, desliguei esse recurso. Seria ótimo adicioná-lo novamente como um sinalizador de compilador adicional, pois dessa maneira você pode detectar muitos erros com antecedência.
4. Compilei o código C escrevendo em três linhas da estrutura:
   • top : código de nível superior - aqui estão as funções
   • decl : declaração e inicialização de variáveis ​​usadas no corpo
   • body : corpo onde o trabalho principal é realizado
5. Durante todo o dia me perguntei se poderia escrever meu próprio coletor de lixo, mas decidi deixar esse exercício para mais tarde. A biblioteca de coleta de lixo Boehm-Demers-Weiser é fácil de conectar e está disponível em várias plataformas.
   
6. É importante olhar para o código que seu compilador escreve. Sempre que o compilador encontrava uma variável de ambiente DEBUG , ele retornava o código C compilado, onde os erros podiam ser visualizados.

O que eu faria de outra maneira

1. Escrever código C e tentar manter o recuo não foi fácil, então eu não recusaria a automação. Parece-me que alguns compiladores escrevem códigos feios e, em seguida, uma biblioteca especial "decora" antes de emitir. Precisa ser estudado!
   
2. Adicionar linhas durante a geração do código é um pouco confuso. Você pode criar um AST e depois convertê-lo para a última linha do código C. Isso deve colocar o código em ordem e dar harmonia.

Agora conselhos

Eu gosto que demorou quase uma década para o compilador. Na verdade não. Cada passo no caminho é uma lembrança agradável de como me tornei um programador cada vez melhor.

Mas isso não significa que eu "terminei". Ainda existem centenas de métodos e ferramentas que você precisa aprender para se sentir como um verdadeiro autor de compilador. Mas posso dizer com confiança: "Consegui".

Aqui está todo o processo de forma concisa, como criar seu próprio compilador Lisp:

1. Escolha o idioma em que você se sente confortável. Você não deseja aprender simultaneamente um novo idioma e como escrever outro novo idioma.
   
2. Seguindo o manual do Mal, escreva um intérprete.
   
3. Alegrai-vos!
   
4. Siga as instruções novamente, mas em vez de executar o código, escreva o código que executa o código. (Não apenas "refatorando" o intérprete existente. Você precisa começar do zero, embora copiar e colar não seja proibido).

Acredito que esse método possa ser usado com qualquer linguagem de programação que seja compilada em um arquivo executável. Por exemplo, você pode:

1. Escreva o intérprete Mal em Go .
2. Modifique seu código para:
   
   • crie uma linha de código Go e grave-a em um arquivo;
   • compile esse arquivo resultante com go build .

Idealmente, é melhor controlar o compilador Go como uma biblioteca, mas essa também é uma maneira de criar um compilador!

Com a ajuda do guia de Mal e sua criatividade, você pode fazer tudo isso. Se eu pudesse, então você pode!