Dev cria interpretador estilo Python em 1.024 bytes de C

O desafio

Austin Z. Henley, engenheiro da Microsoft, conta que escreve código à mão nos fins de semana como passatempo. Seu desafio mais recente: criar um interpretador de Python em 1024 bytes de C, sem macros nem bibliotecas externas. O alvo era conseguir rodar um programa FizzBuzz com a sintaxe característica de Python: def, dois-pontos, indentação e if sem parênteses.

Primeira tentativa

Henley, que já escreveu muitos parsers de descida recursiva (inclusive o compilador Teeny Tiny), começou tentando caber em 512 bytes. Implementou primeiro casos simples como 1 + 2 e depois atribuições e condicionais, mas percebeu que havia construído apenas uma calculadora e que já havia estourado o limite. Decidiu então dobrar a meta para 1024 bytes e listar os elementos que fazem o código "parecer Python".

Arquitetura

Diferente do CPython, que tokeniza o código, gera uma árvore sintática abstrata, otimiza, emite bytecode e interpreta esse bytecode, o interpretador de Henley não faz nada disso. O estado fica em poucas variáveis globais: um array fixo de 999 posições guarda o código-fonte sem a maioria dos espaços, e um array de 256 inteiros funciona como tabela de símbolos.

As expressões são processadas por um parser de descida recursiva comum, avaliadas durante o próprio parsing. Não há nenhum tratamento de erros: o interpretador assume que as palavras-chave estão corretas, que os limites de tokens são válidos e remove a maior parte dos espaços em branco (mantendo indentação e espaços dentro de strings). Variáveis são limitadas a nomes de uma única letra minúscula, o que permite consultar a tabela de símbolos diretamente pelo caractere.

Controle de fluxo

A execução de blocos continua enquanto a indentação não diminui, usando a pilha de chamadas do próprio programa C para a recursão. Como nada é compilado, os laços while e for funcionam saltando para trás e reanalisando o código-fonte a cada iteração: o interpretador guarda a posição da expressão de condição e retorna a ela após executar o corpo. Funções operam da mesma forma: a definição grava a posição do corpo na tabela de símbolos, e a chamada salva o ponto do chamador, salta para o corpo e restaura a posição ao terminar. Segundo o autor, é possível fazer muito mesmo sem representação intermediária, e o estado mantido é mínimo.

Minificação

Para reduzir o código (a versão legível passa de 4800 bytes), Henley recorreu a dicas de code golf em C do Stack Overflow e a recursos específicos do GNU C89. As técnicas incluem nomes de variáveis e funções de uma letra, confiar no linking automático da libc, usar globais como variáveis temporárias (zeradas por padrão), declarações implícitas de int do C89, usar parâmetros de função como temporários preservados na pilha, valores ASCII em vez de literais de caractere, operadores ternário e vírgula, e operações bit a bit no lugar de operações lógicas. Um exemplo: a função parse_sum virou e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}.

Para caber no limite, ele cortou recursos: as comparações (<, >, ==) foram quase removidas, pois ocupam muitos bytes e a veracidade de inteiros ainda funciona sem elas com formas como if n%15:. Ele estima que, se o objetivo fosse apenas rodar o FizzBuzz, poderia ficar abaixo de 800 bytes.

Resultado e conclusão

A versão final golfeada tem exatamente 1024 bytes. Os recursos implementados incluem variáveis e literais inteiros de uma letra, atribuição, aritmética com + - * % e precedência, comparações (uma por expressão), veracidade de inteiros, if/else, laços while e for x in range(y) (ambos com blocos else), definição e chamada de funções sem argumentos (inclusive recursivas), blocos por indentação sem escopo, print de string literal ou expressão inteira, e comentários.

Henley diz que não pretende fazer outro desafio de code golf em breve, porque o processo foi tedioso, com vai-e-vem constante entre a versão golfeada e a legível. Ambas as versões estão no GitHub, e ele desafia os leitores a fazerem seus próprios "Python em 1024 bytes".