Programação: programando com menos do que nada

 (joshmoody.org)
2 pontos por GN⁺ 2025-10-24 | 1 comentários | Compartilhar no WhatsApp
  • Este texto traz uma narrativa satírica em um contexto de entrevista, na qual o candidato tenta implementar o simples problema do FizzBuzz com combinadores de funções puras baseados em cálculo lambda
  • O protagonista começa em JavaScript, mas gradualmente define os combinadores S, K e I, reconstruindo por conta própria a estrutura básica da linguagem
  • Em seguida, ele passa a representar booleanos, números, listas e strings usando apenas combinadores, e implementa recursão por meio do combinador Y
  • No fim, conclui o FizzBuzz em um estilo totalmente point-free, mas o código cresce até um nível incompreensível para humanos
  • O texto explora com humor a essência das linguagens de programação e o extremo da abstração, revelando a autoironia da cultura de desenvolvedores

O início da entrevista: FizzBuzz e combinadores

  • A história começa com a entrevistadora Dana pedindo ao candidato que resolva o problema do FizzBuzz
    • Em vez de usar um laço comum, o candidato começa definindo os combinadores S e K para resolver o problema
    • Dana estranha a abordagem, mas o candidato continua dizendo que “falta só mais um pouco”
  • O candidato então define vários combinadores como I, B, C, W, T e os usa como componentes básicos de uma nova linguagem
    • Cada combinador implementa conceitos centrais do cálculo lambda, como composição de funções, troca de argumentos e autoaplicação
    • Nos comentários do código aparecem apelidos dos combinadores como “Bluebird, Cardinal, Warbler, Thrush”

Definição de booleanos e números

  • O candidato define TRUE, FALSE, NOT apenas com combinadores, construindo a lógica booleana
    • Dana pergunta se aquilo é cálculo lambda, mas o candidato responde que “cálculo lambda é inchado demais”
  • Em seguida, ele define ZERO, SUCC, PRED, IS_ZERO e monta um sistema numérico (numerais de Church)
    • SUCC implementa o sucessor, PRED o predecessor, e DECREMENT uma operação de decremento que não desce abaixo de 0
    • Os números de ONE até TEN são definidos em sequência

Recursão e o combinador Y

  • O candidato define a função ADD e gradualmente a transforma em uma forma point-free
    • Ele define ADD_MAKER e a envolve com o combinador Y para permitir recursão
    • Dana observa que JavaScript também tem recursão, mas o candidato responde que “em breve isso não será mais JavaScript”
  • Quando a avaliação estrita (eager evaluation) do JavaScript provoca stack overflow, o candidato executa o código em Skoobert, um interpretador JS “preguiçoso” (lazy)
    • O resultado exibe com sucesso 3

Aritmética, listas e strings

  • O candidato implementa todas as operações aritméticas, como SUBTRACT, MULTIPLY, MOD, DIVIDE, com base em combinadores
    • Cada operação é construída combinando recursivamente IS_ZERO, PRED, SUCC e outros
  • Depois, ele define CONS, FIRST, REST, EMPTY e constrói uma estrutura de listas
    • Operações funcionais de ordem superior como MAP, FOLD, RANGE, CONCAT também são implementadas em forma de combinadores
  • Para imprimir listas como strings, ele escreve as funções renderList e showLines
    • Dana já parece ter desistido e não reage mais

Construção de caracteres e strings

  • O candidato define códigos de caracteres de 1 a 9 e depois em unidades de 10 usando combinadores
    • De CHAR_A até CHAR_Z, e de CHAR_0 até CHAR_9, tudo é expresso como combinações numéricas
  • Com a função ARRAY, ele converte strings em listas e gera FIZZ, BUZZ, FIZZBUZZ
    • Com a função extractString, converte a lista em uma string real
    • A saída no console é "fizzbuzz"

Conversão de números para strings

  • Ele define NUMBER_TO_DIGIT_LIST, que transforma um número em uma lista de dígitos, e NUMBER_TO_STRING, que converte isso em string
    • Usa DIVIDE, MOD, TEN etc. para separar cada casa decimal
    • Faz o mapeamento para caracteres numéricos por meio da lista DIGITS_NUMERAL
  • Com isso, a conversão número → caractere → string se torna possível inteiramente dentro do sistema de combinadores

A conclusão do FizzBuzz

  • Ele define FIFTEEN e ONE_HUNDRED, e usa MAP e RANGE para gerar uma lista de 1 a 100
    • Para cada número, verifica múltiplos de 3, 5 e 15 para imprimir "Fizz", "Buzz", "FizzBuzz" ou a string do número
    • O resultado final é exibido com showLines(extractString)(FIZZBUZZ_RESULT)
  • Dana pergunta se agora ele está satisfeito, mas o candidato remove todas as definições de variáveis e reescreve o código usando apenas combinadores puros
    • O resultado é uma expressão gigantesca composta só de S e K, com milhares de linhas

Desfecho e significado

  • O texto explora os componentes fundamentais das linguagens de programação e, ao mesmo tempo, satiriza a tendência de desenvolvedores de tornar problemas simples excessivamente complexos
    • O título, “programar com menos do que nada”, simboliza a tentativa de reconstruir um mundo a partir das unidades mínimas da linguagem
  • A obra é uma peça de literatura técnica que traduz em humor e narrativa uma compreensão profunda de programação funcional, cálculo lambda e lógica de combinadores
    • Ao mesmo tempo, satiriza o “espírito de desenvolvedor que transforma até FizzBuzz em um experimento filosófico”

Leituras relacionadas

1 comentários

 
GN⁺ 2025-10-24
Comentários no Hacker News

  • Como parece que muita gente está pensando “mas afinal, o que é isso?”, vou explicar o ponto principal de um combinator
    Um combinator é uma função que não altera estado global nem captura variáveis externas. Dado o mesmo argumento, sempre produz o mesmo resultado e não causa nenhum efeito no restante do sistema
    Ao combinar essas funções puras, você obtém outro combinator. Ou seja, a composição de funções puras continua sendo uma função pura
    Essas funções também podem ser escritas facilmente em assembly ou C. Por exemplo, se você implementar S e K diretamente em x64 e então compilar Common Lisp em cima disso com base em combinators, no fim das contas o Lisp estará rodando sobre duas funções em assembly
    O desempenho não seria grande coisa, mas se você criar e nomear algumas centenas de padrões frequentes como combinators inline, isso vira uma “máquina” bastante prática
    Essa estrutura também se parece com Forth com medo de mutation, com uma VM de bytecode ou com uma CPU que chama combinators de “instruções”
    No fim, combinators podem ser vistos como uma expressão da ciência da computação aplicada que ignora ao máximo os detalhes de implementação. Por isso dá para dizer que são mais simples que o cálculo lambda
    Se você implementar o cálculo lambda com alguns combinators e colocar Lisp por cima, o volume de trabalho dependente de máquina que precisa existir no fundo da pilha fica extremamente reduzido

    • Parece que em algum lugar uma função chamou a si mesma e recebeu a seed round
    • Fiz algo parecido quando era estudante, embora não com Lisp, mas com uma linguagem simples expandida por macros para cálculo lambda. Foi realmente chocante descobrir que dava para implementar tudo só com S e K. Ao mesmo tempo, também foi impressionante o quanto isso era ineficiente. Ainda assim, a situação melhora bastante conforme o conjunto de instruções cresce
    • Em teoria, tudo isso é possível, mas na prática faz mais sentido escolher uma base computacional muito mais prática do que reescrita de grafos. A menos que você queira experimentar os limites da computabilidade, isso é quase um truque de festa. Além disso, a representação de números também é um problema. No mínimo, seria preciso usar inteiros em complemento de dois e destruidores eficientes para realmente impressionar
    • Fiquei curioso se existe de fato algum Lisp implementado sobre combinators assim. Se existir, portar isso deve ser bem divertido
  • let A = (x) => (y) => (z) => x(z)(y((w) => z))

    Basta combinar isso algumas vezes

    let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A);
let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A);

    “Eu nunca usaria cálculo lambda. É uma linguagem inflada demais.”
    Mas, na prática, a lógica combinatória é ainda mais inflada. São necessários mais bits para expressar o mesmo programa
    O cálculo lambda é, na verdade, uma das linguagens mais concisas que existem
    Mesmo em uma linguagem eager como JavaScript, dá para torná-la lazy envolvendo os argumentos em lambdas dummy. Veja este interpretador JS de BLC como exemplo
    Para mais detalhes, veja este PDF e este exemplo do IOCCC

    • O ponto interessante é que alguns dos interpretadores de cálculo lambda mais rápidos (como uni.c) acabam convertendo expressões lambda em lógica combinatória para avaliá-las. Só que usam um conjunto básico maior do que S e K
    • “bloated language” significa uma linguagem com recursos desnecessários demais. Por exemplo, C++ pode produzir código menor que C, mas ainda assim é uma linguagem muito mais complexa
    • Ficar olhando para esse bloco de código faz os sons que saem da minha boca combinarem quase exatamente com a lista de argumentos
    • Acho que há um erro de parênteses nas definições de K e S. A versão corrigida é esta 
      let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A));
let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)(A(A)))))))(A)(A);
      E para tornar uma linguagem eager em lazy, dá para fazer algo assim 
      let A = x => y => z => () => x()(z())(y()(w => z()));
    • Fica a pergunta: “o que é w?”

  • “Você conhece FizzBuzz?”
    “Claro. A versão de code golf com 10 caracteres, a versão de 12 linhas que um júnior consegue entender, ou a versão completamente absurda para ostentar conhecimento esquisito?”

    • Depois de ver isso, implementei o FizzBuzz mais rápido em C64 BASIC. Foi uma forma divertida de desperdiçar a manhã
      Link do resultado

  • A explicação de lógica combinatória foi realmente excelente. O estilo de escrita me lembrou esta série

    • Foi mais uma performance de demonstração do que propriamente uma explicação. Ainda assim, foi bem marcante
    • Realmente parece ter sido inspirado por aquela série. Teria sido melhor mencionar o nome do autor
    • No Reino Unido, o acesso está bloqueado por causa do Online Safety Act, o que é uma pena

  • Isso me lembrou aquele texto antigo sobre “FizzBuzz em TensorFlow”
    Link

    • Pelo menos este texto aqui eu consegui acompanhar

  • Esse enquadramento de entrevista de programação parece meio equivocado
    O objetivo de uma entrevista é (1) verificar o conhecimento de programação do candidato e (2) verificar a adequação à cultura de programação da empresa
    Por exemplo, se você está contratando para uma vaga de JavaScript e a pessoa está profundamente obcecada por lógica combinatória, talvez ela simplesmente não combine culturalmente com a equipe. Então não seria estranho reprová-la

    • Provavelmente isso faz referência a esta série, embora isso não esteja explícito no texto original
    • Às vezes, os comentaristas do HN parecem pessoas que esqueceram como se divertir
    • Destacar a diversidade da programação faz sentido, mas isso também é só uma forma de selecionar especialização em um ecossistema específico. Na maior parte dos casos, é uma escolha voltada para código legado ou para o uso do ecossistema existente
    • Frases como “se o QI for baixo, reprova” são engraçadas, mas no fim, com dinheiro suficiente, dá para se adaptar a qualquer estilo de OOP/FP/FRP
    • No mundo real, esse tipo de entrevista idealizada quase não existe. Na maioria das vezes, são entrevistadores frustrados impondo sua própria visão de mundo. O trabalho real quase nunca tem relação com o conteúdo da entrevista

  • Já passou da hora de lembrar de Moses Schönfinkel
    Ele inventou a lógica combinatória em 1920, quando era aluno de Hilbert. Depois voltou para a Rússia, sofreu de doença mental e morreu na pobreza em Moscou. Segundo a Wikipédia, seus artigos foram queimados pelos vizinhos para servir de combustível no aquecimento

  • O último bloco de código é tão grande que cria rolagem (166KB)
    S e K são funções curried, recebendo apenas um argumento por vez
    Para mais detalhes, veja esta resposta no StackOverflow

    • A melhor parte foi perceber exatamente o momento em que o realce de sintaxe desistiu enquanto eu rolava a página

  • Adoro esses nomes de pássaros como “Bluebird, cardinal, warbler, thrush”. Quero adotar isso como nova convenção de nomes
    “Barendregt. Church é mainstream demais.”
    “Logo nem vai mais ser JavaScript.”
    Parece Douglas Adams ensinando SICP

    • Esses nomes de pássaros vêm de To Mock a Mockingbird, do Smullyan. Lá aparecem ainda mais pássaros

  • “Então isso é... o Y combinator?”
    “Isso mesmo. Você precisa dele para recursão.”
    Curiosidade: existem infinitos combinadores de ponto fixo. Ou seja, dá para implementar recursão de infinitas formas diferentes sem usar o Y combinator