A Calculus of Inheritance

Il documento presenta il calcolo dell'ereditarietà, un fondamento per la programmazione dichiarativa basato su record, definizioni ed ereditarietà che unifica classi e oggetti, risolve il problema della linearizzazione dell'ereditarietà multipla trattando la composizione come unione insiemistica e dimostra una maggiore espressività rispetto al calcolo $\lambda$.

L'essenziale

Immagina di dover costruire una casa. Nel mondo della programmazione tradizionale (quello basato sul "calcolo lambda"), per aggiungere una stanza, devi disegnare un piano preciso, definire le porte, le finestre e poi "chiamare" questa stanza come se fosse un'azione da eseguire. È come se ogni volta che volessi aggiungere un mobile, dovessi riscrivere le leggi della fisica della stanza.

"Un Calcolo dell'Ereditarietà" (A Calculus of Inheritance) è un nuovo modo di pensare alla programmazione, proposto da Bo Yang. Immaginalo non come un insieme di istruzioni da eseguire, ma come un sistema di collage intelligente o un Lego magico.

Ecco come funziona, spiegato con metafore semplici:

1. I Mattoncini Magici: I Record

Invece di usare "funzioni" (azioni), questo sistema usa solo oggetti (chiamati record).

• L'analogia: Pensa a un record come a un cassetto di un armadio. Dentro ci sono etichette (chiavi) e cose (valori).
• Invece di dire "fai questo calcolo", diciamo semplicemente "prendi questo cassetto e metti dentro queste cose".

2. L'Ereditarietà come "Colla" (Unione di Insiemi)

La vera magia sta in come si uniscono questi cassetti.

• Il problema vecchio: Nelle lingue di programmazione classiche, se hai due cassetti che dicono "la porta è rossa" e "la porta è blu", il computer va in confusione. Deve decidere quale porta usare (spesso creando regole complicate e dolorose chiamate "linearizzazione").
• La soluzione di Bo Yang: Qui, l'ereditarietà è come unire due fogli di carta trasparente.
  • Se sul foglio A c'è scritto "Porta: Rossa" e sul foglio B c'è scritto "Finestra: Aperta", quando li sovrapponi, ottieni un foglio unico con entrambe le scritte.
  • Se entrambi dicono "Porta: Rossa", non c'è conflitto: le due scritte si fondono perfettamente.
  • Risultato: Non importa in quale ordine unisci i fogli (commutatività), non importa se li unisci due volte (idempotenza) o se ne unisci tre insieme (associatività). Il risultato è sempre lo stesso e corretto. È come mescolare l'acqua: non importa l'ordine, l'acqua è sempre acqua.

3. Risolvere i "Nomi" senza Confusione (Il problema del "Chi sono io?")

In un sistema complesso, un oggetto può ereditare da più fonti. Come fa a sapere da dove viene una proprietà?

• L'analogia: Immagina di essere in una folla di persone che si tengono per mano (una catena di ereditarietà). Se chiedi "Dove sono i miei genitori?", in un sistema normale potresti ricevere una risposta confusa o un errore se ci sono due rami della famiglia.
• La novità: In questo nuovo calcolo, la risposta è: "Sono ovunque". Il sistema non sceglie un solo ramo; guarda tutti i rami possibili contemporaneamente. Se due rami portano alla stessa cosa, le informazioni si sommano. È come se il computer avesse la capacità di essere in più posti contemporaneamente e di unire tutte le informazioni senza andare in crash.

4. Perché è più potente delle funzioni?

Il calcolo lambda (le funzioni) è potente, ma ha un limite: una volta che hai calcolato un risultato, è "finito". Non puoi aggiungere nuove caratteristiche a quel risultato senza riscrivere il codice originale.

• L'analogia: È come avere una torta già fatta. Se vuoi aggiungere una ciliegia sopra, devi rifare la torta da zero.
• In questo nuovo sistema: La torta è fatta di strati di carta trasparente. Puoi aggiungere una ciliegia (una nuova proprietà) sovrapponendo un nuovo foglio, senza toccare la torta sottostante. Questo risolve il famoso "Problema dell'Espressione": puoi aggiungere nuove funzionalità a vecchi dati senza dover modificare il codice originale.

5. La Magia della "Logica" che emerge dall'Aritmetica

Il paper mostra qualcosa di incredibile: facendo semplici operazioni matematiche con questi "cassetti", il sistema inizia a comportarsi come un database logico.

• Se hai un gruppo di numeri {1, 2} e un altro {3, 4}, e li unisci con l'addizione, il sistema non ti dà un solo numero. Ti dà tutte le combinazioni possibili: {4, 5, 6}.
• È come se il computer facesse automaticamente un "gioco di incroci" (prodotto cartesiano) senza che tu glielo abbia chiesto esplicitamente. Questo permette di fare cose complesse (come il linguaggio logico dei database) usando solo le regole base dell'ereditarietà.

In sintesi

Questo paper ci dice che non abbiamo bisogno di regole complesse per gestire la complessità. Se usiamo un approccio basato sull'unione di oggetti (ereditarietà profonda) invece che sull'esecuzione di funzioni, otteniamo:

1. Nessun conflitto: Le cose si fondono invece di scontrarsi.
2. Flessibilità totale: Puoi aggiungere nuove cose a qualsiasi oggetto in qualsiasi momento.
3. Semplicità: Tutto si riduce a tre concetti: creare un oggetto, definire qualcosa dentro e unire due oggetti.

È come passare dal dover scrivere un manuale di istruzioni per ogni singolo mattoncino, a semplicemente avere un mucchio di mattoncini che, quando li metti vicini, si assemblano da soli perfettamente, creando strutture complesse e robuste senza che nessuno debba dire loro come fare.

Sommario tecnico

Ecco un riassunto tecnico dettagliato del paper "A Calculus of Inheritance" di Bo Yang, presentato in italiano.

Titolo: Un Calcolo dell'Ereditarietà (A Calculus of Inheritance)

1. Il Problema

Il campo dell'ingegneria del software moderno fa ampio uso di linguaggi dichiarativi e di configurazione (es. NixOS, Jsonnet, CUE, Dhall) per gestire sistemi complessi. Tuttavia, esiste un vuoto teorico fondamentale: mentre il $\lambda$-calcolo fornisce la base formale per la programmazione funzionale, non esiste un calcolo analogo per la programmazione dichiarativa.

I modelli computazionali classici presentano limitazioni intrinseche rispetto ai requisiti dei linguaggi di configurazione:

• Le Macchine di Turing e le RAM richiedono stato mutabile.
• Il $\lambda$-calcolo richiede funzioni di prima classe.
• I linguaggi di configurazione moderni sono invece immutabili, privi di funzioni di prima classe, ma comunque Turing-completi (come dimostrato dal sistema di moduli di NixOS).

Inoltre, i sistemi esistenti soffrono di problemi di composizione:

• Problema della linearizzazione: Nei sistemi a ereditarietà multipla (OOP), l'ordine di risoluzione dei metodi è complesso e spesso non commutativo.
• Problema dell'Espressione (Expression Problem): È difficile aggiungere nuove operazioni a nuovi tipi di dati senza modificare il codice esistente, specialmente quando si combinano funzionalità indipendenti.
• Risoluzione del self-reference: I sistemi attuali (come Scala o NixOS) spesso rifiutano o gestiscono male i casi in cui un oggetto eredita da più percorsi che puntano alla stessa definizione (risoluzione multi-percorso).

2. Metodologia

L'autore propone l'Inheritance-Calculus, un modello computazionale minimale che unifica classi, metodi, oggetti e proprietà sotto un'unica astrazione: il record.

Primitivi del Calcolo:
Il calcolo si basa su tre costrutti fondamentali:

1. Record: Un insieme di definizioni (chiave $\to$ valore).
2. Definizione: L'assegnazione di un valore a una chiave.
3. Ereditarietà: Il meccanismo di unione di record.

Meccanismo Semantico:

• Unione come Ereditarietà: L'ereditarietà è modellata semplicemente come l'unione di insiemi (set union). Questo rende l'operazione intrinsecamente commutativa, idempotente e associativa, eliminando la necessità di algoritmi di linearizzazione (come C3).
• Semantica Osservazionale: Il calcolo non esegue passi di riduzione ($\beta$-riduzione) in modo imperativo. Invece, la computazione è guidata da un "osservatore" che interroga percorsi (path) in un albero di mixin lazy.
• Semantica di Punto Fisso: La semantica è definita da sei equazioni ricorsive di primo ordine su percorsi e insiemi di percorsi. L'interpretazione è il minimo punto fisso ($lfp(T_P)$) di un operatore monotone, garantendo la convergenza anche per programmi ricorsivi che divergerebbero nel $\lambda$-calcolo standard.
• Risoluzione Multi-Percorso: A differenza di sistemi che richiedono un "self" singolo, l'Inheritance-Calculus risolve i riferimenti a this attraverso un insieme di percorsi (frontiera), permettendo a più percorsi di ereditarietà di contribuire equamente alle proprietà di un oggetto.

3. Contributi Chiave

1. Definizione Formale: Introduce l'Inheritance-Calculus come modello minimale per la programmazione dichiarativa, basato su record, definizioni ed ereditarietà.
2. Unificazione Concettuale: Dimostra che classi, metodi e oggetti sono la stessa cosa (record profondamente unibili). L'override di metodi è sostituito dalla fusione profonda (deep merge) degli alberi di mixin.
3. Semantica di Primo Ordine: Fornisce una semantica denotazionale e osservazionale basata su equazioni di primo ordine (senza spazi di funzioni o chiusure), che è calcolabile tramite punto fisso.
4. Immersione del $\lambda$-calcolo: Dimostra che il $\lambda$-calcolo può essere macro-espresso nell'Inheritance-Calculus tramite 5 regole locali (trasformazione in forma normale A - ANF).
5. Asimmetria Espressiva: Prova che l'Inheritance-Calculus è strettamente più espressivo del $\lambda$-calcolo lazy (nel senso di Felleisen). Esistono contesti che possono distinguere termini $\lambda$-equivalenti quando vengono tradotti nel calcolo dell'ereditarietà, grazie alla capacità di aggiungere nuove proiezioni osservabili senza modificare le definizioni originali.
6. Immunità alla Non-Estendibilità: Il calcolo risolve il Problema dell'Espressione in entrambe le dimensioni (nuovi dati e nuove operazioni) senza meccanismi dedicati, grazie alla natura aperta dell'unione di record.

4. Risultati e Dimostrazioni

• Corrispondenza con gli Alberi di Böhm: La traduzione dal $\lambda$-calcolo all'Inheritance-Calculus preserva l'equivalenza osservazionale (alberi di Böhm). Tuttavia, l'Inheritance-Calculus converge per alcuni termini che divergono nel $\lambda$-calcolo (grazie alla semantica di punto fisso su grafi ciclici).
• Semantica Relazionale Emergente: Implementando aritmetica e logica booleana in MIXINv2 (l'implementazione pratica del calcolo), l'autore dimostra che le operazioni su valori singoli distribuiscono automaticamente su insiemi di valori. Ad esempio, sommare $\{1, 2\}$ a $\{3, 4\}$ produce il prodotto cartesiano $\{4, 5, 6\}$, realizzando la semantica della programmazione logica (Datalog) senza costrutti specifici.
• Function Color Blindness: Lo stesso codice MIXINv2 può essere eseguito sia in ambienti sincroni che asincroni. La logica di business dichiara slot vuoti, e l'implementazione (sincrona o asincrona) viene iniettata tramite ereditarietà, rendendo il codice "cieco" al colore della funzione (effetto collaterale).
• Validazione Pratica: Tutti gli esempi, inclusa l'aritmetica dei numeri naturali e la risoluzione di problemi complessi, sono stati implementati e testati in MIXINv2, un linguaggio dichiarativo Python che utilizza solo questi tre costrutti.

5. Significato e Implicazioni

Il lavoro di Bo Yang ha implicazioni profonde per la teoria dei linguaggi di programmazione e l'ingegneria del software:

• Nuovo Paradigma Fondamentale: Suggerisce che l'ereditarietà (intesa come unione di strutture dati) è un modello computazionale primario, forse più fondamentale della funzione, per i sistemi dichiarativi.
• Risoluzione di Problemi Storici: Risolve elegantemente il problema della linearizzazione dell'ereditarietà multipla e del Problema dell'Espressione, che hanno afflitto i linguaggi OOP e funzionali per decenni.
• Unificazione di Paradigmi: Colma il divario tra programmazione funzionale, orientata agli oggetti e logica, mostrando che possono essere tutte viste come istanze dello stesso calcolo basato su record e unione.
• Impatto sui Linguaggi di Configurazione: Fornisce una base teorica solida per sistemi come NixOS, spiegando perché funzionano così bene e suggerendo come estenderli o progettarne di nuovi con proprietà formali garantite.
• Semantica Robusta: La capacità di gestire la ricorsione attraverso il punto fisso ($lfp$) offre una via per scrivere programmi ricorsivi che convergono anche in presenza di cicli, superando le limitazioni della riduzione $\beta$ tradizionale.

In sintesi, l'Inheritance-Calculus propone che la "funzione" sia solo zucchero sintattico per l'ereditarietà, offrendo un modello unificato, estensibile e formalmente solido per la programmazione dichiarativa moderna.