A Calculus of Inheritance

O artigo apresenta o cálculo de herança, uma fundação para a programação declarativa que unifica classes, métodos e objetos sob uma abstração de registro onde a herança é modelada como união de conjuntos, eliminando problemas de linearização e demonstrando maior expressividade que o cálculo $\lambda$ ao integrar semânticas de lógica, mixins e resolução de auto-referência.

O essencial

Imagine que você está organizando uma festa gigante. No mundo da programação tradicional (como o cálculo $\lambda$ que usamos para funções), você teria que escrever um manual de instruções detalhado para cada convidado: "Se você vir o João, diga a Maria para trazer o bolo". É tudo sobre como fazer as coisas passo a passo.

Mas o que o autor, Bo Yang, propõe neste artigo é uma abordagem totalmente diferente, chamada Cálculo da Herança (Inheritance-Calculus). Em vez de escrever instruções, você simplesmente junta os convidados e deixa que eles se organizem sozinhos.

Aqui está a explicação simples, usando analogias do dia a dia:

1. A Ideia Central: A "Colagem Mágica"

Pense em Lego.

• Programação Tradicional: Você segue um manual. "Pegue a peça vermelha, encaixe na azul, depois na verde". Se você quiser mudar algo, tem que refazer o manual.
• Cálculo da Herança: Você tem uma caixa de blocos. Você pega um bloco de "Carro" e um bloco de "Asa de Avião". Em vez de escrever um código dizendo "como transformar carro em avião", você simplesmente cola os dois blocos juntos.
  • O resultado é um "Carro-Asa".
  • Se você colar o "Carro" com "Asa de Avião" e depois com "Rodas de Caminhão", a ordem não importa. O resultado final é o mesmo (comutativo).
  • Se você colar o mesmo bloco duas vezes, não fica duplo (idempotente).
  • Você pode colar em qualquer ordem (associativo).

O autor diz que, na computação declarativa (onde você diz o que quer, não como fazer), a herança é apenas essa "colagem" de estruturas de dados.

2. O Problema que Eles Resolveram: A "Batalha dos Pais"

Em linguagens de programação comuns (como Java ou C++), quando um objeto herda de duas outras coisas ao mesmo tempo (herança múltipla), surge um problema: "Se o Pai A diz que a cor é Azul e o Pai B diz que é Vermelho, qual cor o filho terá?"

• Sistemas antigos: Eles criam regras complexas e chatas para decidir quem ganha (chamado de "linearização"). É como ter dois pais brigando e um juiz decidindo quem manda.
• A Solução do Cálculo da Herança: Eles dizem: "E se o filho tiver ambas as cores?"
  • Em vez de escolher um, o sistema funde tudo. Se você tem duas definições para a mesma coisa, elas se misturam profundamente.
  • Isso elimina a briga. É como se você tivesse uma mesa de Lego onde todas as peças se encaixam perfeitamente sem conflito.

3. A Grande Surpresa: A Matemática das Coisas

O artigo mostra algo mágico:

• Lógica e Matemática são a mesma coisa aqui: Se você criar uma regra de adição de números simples, o sistema automaticamente começa a funcionar como uma base de dados de lógica.
• Exemplo: Se você tem um conjunto de números {1, 2} e outro {3, 4}, e pede para somá-los, o sistema não dá apenas "5". Ele calcula todas as combinações possíveis: 1+3, 1+4, 2+3, 2+4.
  • Isso acontece "de graça". O sistema trata os dados como se fossem árvores de decisão que se expandem sozinhas. É como se você pedisse para um cozinheiro fazer uma salada, e ele automaticamente fizesse todas as combinações de ingredientes possíveis para você escolher.

4. Por que isso é importante? (O "Problema da Expressão")

Existe um problema famoso na programação chamado "Problema da Expressão". É difícil adicionar novas funcionalidades a um programa sem quebrar o código antigo ou ter que reescrever tudo.

• Sistemas atuais: Para adicionar uma nova função, você precisa modificar o código original (como mudar o manual de instruções do Lego).
• Cálculo da Herança: Você cria um novo arquivo (um novo bloco) e apenas "cola" no sistema existente. O sistema antigo nem percebe que mudou, mas de repente ganha novas capacidades. É como adicionar um novo módulo a um jogo de vídeo game sem precisar reprogramar o jogo inteiro.

5. A Analogia Final: O "Mapa do Tesouro" vs. O "GPS"

• Programação Tradicional (Cálculo $\lambda$): É como um GPS. Ele te diz: "Vire à direita, ande 200 metros, vire à esquerda". Se o caminho mudar, o GPS precisa ser recalculado.
• Cálculo da Herança: É como um mapa de tesouro onde você só precisa marcar o "X". Você pega o mapa do "Tesouro A" e o mapa do "Tesouro B" e os sobrepõe. Onde eles se cruzam, o tesouro aparece. Você não precisa saber o caminho, apenas a localização final.

Resumo em uma frase:

O autor criou uma nova maneira de pensar sobre computadores onde, em vez de dar ordens passo a passo, você apenas mistura e funde pedaços de informação (como blocos de Lego), e a mágica acontece: o computador descobre sozinho como resolver problemas complexos, sem conflitos e sem precisar reescrever o código antigo.

Isso torna a programação mais flexível, mais fácil de expandir e, curiosamente, faz com que a matemática e a lógica de banco de dados funcionem de forma natural e automática.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "A Calculus of Inheritance" (Um Cálculo de Herança), apresentado por Bo Yang.

1. O Problema

O artigo identifica uma lacuna fundamental na teoria da computação: enquanto o cálculo $\lambda$ serve como modelo computacional fundacional para a programação funcional (baseado em abstração, aplicação e variáveis), não existe um cálculo análogo para a programação declarativa e linguagens de configuração.

Linguagens de configuração modernas (como NixOS, Jsonnet, CUE, Dhall) são ubíquas e poderosas, permitindo a composição de dados estruturados através de herança e mesclagem. No entanto, elas carecem de uma base teórica unificada. Os modelos clássicos de computação falham em capturar suas propriedades essenciais simultaneamente:

• Máquinas de Turing e RAM: Requerem estado mutável.
• Cálculo $\lambda$: Requer funções de primeira classe.
• Linguagens de Configuração: São inerentemente declarativas (valores imutáveis, sem funções de primeira classe).

Além disso, sistemas existentes enfrentam problemas como:

• Problema da Linearização de Múltipla Herança: Em sistemas baseados em mixins (como Scala), a ordem de composição importa, exigindo algoritmos complexos (ex: C3) para resolver conflitos.
• Problema da Expressão (Expression Problem): Dificuldade em adicionar novos tipos de dados e operações independentemente sem modificar código existente.
• Semântica de Auto-referência: Como resolver referências a self quando um objeto é herdado por múltiplos caminhos simultaneamente.

2. Metodologia

O autor propõe o Inheritance-calculus (Cálculo de Herança), um modelo computacional minimalista derivado da implementação prática MIXINv2. A metodologia baseia-se nos seguintes pilares:

• Primitivas Fundamentais: O cálculo reduz a programação declarativa a apenas três primitivas:
  1. Registro (Record): Estruturas de dados aninhadas.
  2. Definição (Definition): Atribuição de propriedades (ℓ ↦→ e).
  3. Herança (Inheritance): Referência a escopos externos e projeção de propriedades ([ℓup.this.] ℓdown...).
• Abstração Unificada: Classes, métodos, objetos e propriedades são unificados sob uma única abstração de "mixin". Não há métodos opacos; todos os valores são registros transparentes.
• Semântica Observacional e de Fixpoint:
  • A semântica é definida por seis equações recursivas de primeira ordem que operam sobre caminhos (sequências de rótulos) e conjuntos de caminhos.
  • A herança é modelada como união de conjuntos (deep merge), tornando-a inerentemente comutativa, idempotente e associativa.
  • A resolução de auto-referência (this) não é de um único alvo, mas de múltiplos alvos (conjunto de caminhos), permitindo que referências se resolvam através de múltiplas rotas de herança simultaneamente.
  • A semântica é computável via menor ponto fixo (lfp) de um operador de consequência imediata ($T_P$), similar à semântica de Datalog.

3. Principais Contribuições

1. Definição do Inheritance-calculus: Um modelo formal minimalista para programação declarativa que elimina a necessidade de funções de primeira classe, substituindo aplicação de função por herança de registros.
2. Resolução do Problema da Linearização: Ao modelar a herança como união de conjuntos (deep merge) e permitir resolução multi-alvo para this, o cálculo elimina estruturalmente o problema da linearização. A composição é sempre comutativa e idempotente.
3. Embarcação do Cálculo $\lambda$: O autor demonstra que o cálculo $\lambda$ pode ser macro-expresso no Inheritance-calculus através de 5 regras locais (conversão para Forma Normal A - ANF). Isso prova que o Inheritance-calculus é Turing-completo.
4. Assimetria Expressiva: O Inheritance-calculus é estritamente mais expressivo que o cálculo $\lambda$ preguiçoso (lazy $\lambda$-calculus) no sentido de Felleisen. Contextos que misturam construtores de herança podem distinguir termos que são equivalentes no cálculo $\lambda$ (baseado em árvores de Böhm), permitindo extensões abertas que alteram a equivalência operacional.
5. Semântica de Primeira Ordem: Ao contrário da semântica denotacional tradicional do $\lambda$-cálculo (que requer espaços de funções e domínios reflexivos complexos), o Inheritance-calculus possui uma semântica puramente de primeira ordem baseada em conjuntos de caminhos, tornando-a mais simples e computável.
6. Imunidade ao Problema da Expressão: O modelo é estruturalmente imune à não-extensibilidade. Novas operações e tipos de dados podem ser adicionados via herança sem modificar os arquivos originais, resolvendo o Problema da Expressão de forma natural.

4. Resultados e Evidências

• Correspondência com Árvores de Böhm: O autor prova que a convergência no Inheritance-calculus corresponde exatamente à existência de uma forma normal de cabeça (head normal form) no cálculo $\lambda$. Termos que divergem no $\lambda$-cálculo podem convergir no Inheritance-calculus sob a semântica de ponto fixo, oferecendo uma semântica mais definida para programas recursivos.
• Semântica Relacional Emergente: A implementação de aritmética e lógica booleana no MIXINv2 demonstra que a união de tries (estruturas de dados dos registros) naturalmente produz a semântica relacional da programação lógica. Operações sobre valores únicos distribuem-se automaticamente sobre conjuntos de valores, implementando joins e produtos cartesianos sem mecanismos dedicados.
• Cegueira de Cor de Função (Function Color Blindness): O mesmo código MIXINv2 pode ser executado em ambientes síncronos e assíncronos sem modificação. A herança atua como injeção de dependência, onde a "cor" (efeito) é determinada na montagem, não no código de negócios.
• Validação Prática: O modelo foi testado em implementações reais (MIXINv2 em Python), incluindo lógica booleana, aritmética de números naturais e um aplicativo web, confirmando a ausência de problemas de linearização e a capacidade de resolver o Problema da Expressão.

5. Significado e Impacto

O trabalho oferece uma nova fundação teórica para a vasta categoria de linguagens de configuração e sistemas de módulos (como NixOS) que já são amplamente utilizados na indústria, mas careciam de uma explicação teórica unificada.

• Unificação de Paradigmas: Demonstra que a programação funcional e a declarativa podem ser unificadas sob um único modelo de herança de registros, onde a aplicação de função é apenas um caso especial de herança.
• Simplicidade Semântica: Substitui a complexidade de espaços de funções e substituição de captura-avaliada por equações de conjuntos de primeira ordem, facilitando a análise formal e a implementação de compiladores/interpretadores.
• Solução para Extensibilidade: Oferece uma solução teórica robusta para o Problema da Expressão, permitindo que sistemas sejam estendidos infinitamente sem reescrita de código, algo que linguagens tradicionais (Java, Scala, Haskell) só conseguem com grandes quantidades de "boilerplate" ou metaprogramação complexa.
• Novas Perspectivas para Sistemas de Arquivos e Configuração: A semântica de união de tries e resolução multi-alvo sugere novos modelos para sistemas de arquivos unificados (UnionFS) e gerenciamento de configuração em escala, onde a sobreposição de camadas é tratada como composição matemática pura e não como sobrescrita sequencial.

Em resumo, o "Inheritance-calculus" propõe que a herança, quando definida como uma união de conjuntos de caminhos com resolução de múltiplos alvos, é uma primitiva computacional suficientemente poderosa para substituir o cálculo $\lambda$ como base para a computação universal, oferecendo vantagens significativas em extensibilidade e simplicidade semântica.