Paradigmi funzionale e logico

Come descrivere una trasformazione o una relazione

A fianco del paradigma imperativo (basato sulla macchina di von Neumann e sulla modifica passo-passo dello stato in memoria), l’informatica teorica ha sviluppato i paradigmi dichiarativi, in cui il programma non è una sequenza di ordini per la CPU, ma una descrizione formale di cosa è il risultato cercato:

  1. Il Paradigma Funzionale (Lisp, Scheme, ML, Haskell, OCaml, Erlang, e costrutti funzionali in Python/JavaScript/Rust), fondato sul -calcolo (Lambda Calcolo) di Alonzo Church (1936): il calcolo è la valutazione di funzioni matematiche pure.
  2. Il Paradigma Logico (Prolog, Datalog, Answer Set Programming), fondato sulla Logica dei Predicati del Primo Ordine: il programma è una base di conoscenza di fatti e regole logiche, e l’esecuzione consiste nel dimostrare un teorema (interrogazione o query).

1. Il Paradigma Funzionale

Nel paradigma funzionale puro, una funzione non è una procedura che altera variabili in RAM, ma una mappa matematica che associa ad ogni valore di input un unico valore di output.

Principi cardine della programmazione funzionale

  1. Immutabilità dei dati (Assenza di assegnamento distruttivo):
    Non esistono variabili mutabili il cui valore cambia nel tempo! Una volta legato un simbolo a un valore (let x = 5), quel legame resta immutabile. Per “modificare” una lista non si sovrascrivono le sue celle, ma si costruisce una nuova lista trasformata lasciando intatta l’originale.
  2. Funzioni pure, assenza di Side Effects e Trasparenza Referenziale:
    Poiché non esiste stato globale mutabile, una funzione chiamata con gli stessi argomenti restituisce sempre lo stesso risultato. Ogni espressione è referenzialmente trasparente, rendendo immediata la parallelizzazione su più core (nessuna race condition!).
  3. Ricorsione al posto dei cicli iterativi:
    In un ciclo while (i < n) { i++; } è indispensabile mutare la variabile i ad ogni iterazione. Poiché nel funzionale puro le variabili sono immutabili, i cicli non esistono: ogni iterazione viene espressa tramite ricorsione (spesso ottimizzata in coda tramite Tail Call Optimization).
  4. Funzioni come “Cittadini di Prima Classe” (First-Class Citizens) e di Ordine Superiore (Higher-Order Functions):
    Le funzioni sono valori esattamente come i numeri interi: possono essere assegnate a variabili, passate come argomento ad altre funzioni e restituite come risultato. Una funzione che prende in input o restituisce un’altra funzione si chiama funzione di ordine superiore.

La triade delle funzioni di ordine superiore: map, filter, reduce (fold)

Invece di scrivere cicli for manuali, nella programmazione funzionale si elaborano le collezioni componendo tre operatori universali:

flowchart LR
    L0["Lista iniziale<br/><code>[1, 2, 3, 4]</code>"]
    FIL["<b>filter</b>(x pari)<br/>Seleziona gli elementi<br/>che soddisfano il predicato"]
    L1["<code>[2, 4]</code>"]
    MAP["<b>map</b>(x ↦ x²)<br/>Trasforma ogni elemento<br/>applicando f(x)"]
    L2["<code>[4, 16]</code>"]
    RED["<b>reduce / fold</b>(+)<br/>Combina tutti gli elementi<br/>in un unico valore"]
    RIS["Risultato<br/><code>20</code>"]
    L0 --> FIL --> L1 --> MAP --> L2 --> RED --> RIS
  1. map(f, lista): applica la funzione a ciascun elemento di producendo la nuova lista .
  2. filter(p, lista): applica il predicato booleano ad ogni elemento e restituisce una nuova lista contenente solo gli elementi per cui .
  3. reduce(op, lista, init) (detta anche fold): combina progressivamente tutti gli elementi della lista tramite l’operatore binario op a partire dal valore neutro init (es. sommatoria o produttoria).
# Esempio di stile funzionale puro in Python (con funzioni anonime lambda)
from functools import reduce
 
numeri = [1, 2, 3, 4, 5, 6]
 
# 1. filter: tieni solo i numeri pari -> [2, 4, 6]
pari = list(filter(lambda x: x % 2 == 0, numeri))
 
# 2. map: eleva ciascuno al quadrato -> [4, 16, 36]
quadrati = list(map(lambda x: x * x, pari))
 
# 3. reduce: somma tutti gli elementi -> 4 + 16 + 36 = 56
somma_totale = reduce(lambda acc, x: acc + x, quadrati, 0)

Come si realizzano le funzioni di ordine superiore in C?

Anche in C è possibile passare una funzione come argomento a un’altra funzione usando i puntatori a funzione! Ad esempio, la funzione standard qsort di <stdlib.h> è una funzione di ordine superiore che riceve un puntatore alla funzione di confronto int (*compar)(const void *, const void *).


2. Il Paradigma Logico (Prolog)

Nel paradigma logico, ideato negli anni ‘70 da Robert Kowalski e Alain Colmerauer (creatore del linguaggio Prolog, PROgramming in LOGic), programmare non significa scrivere né comandi imperativi né funzioni da valutare, bensì dichiarare relazioni vere su un dominio del discorso tramite Clausole di Horn (un sottoinsieme della logica dei predicati del primo ordine).

I 3 mattoni di un programma Prolog

In Prolog i nomi che iniziano con lettera minuscola (mario, luca, genitore) sono costanti (atomi) o nomi di predicati, mentre i nomi che iniziano con lettera MAIUSCOLA (X, Y, Z, Nonno) sono variabili logiche.

  1. Fatti (Facts): Asserzioni incondizionatamente vere sulle relazioni tra oggetti del mondo. Terminano con un punto fermo ..

    % genitore(X, Y) significa: "X è genitore di Y"
    genitore(mario, luca).
    genitore(mario, sara).
    genitore(luca, anna).
    genitore(sara, marco).
  2. Regole (Rules): Implicazioni logiche della forma Testa :- Corpo. dove il simbolo :- si legge “se” (, implicazione inversa) e la virgola , nel corpo indica la congiunzione logica AND ().

    % X è nonno/a di Y SE X è genitore di Z E Z è genitore di Y
    nonno(X, Y) :- genitore(X, Z), genitore(Z, Y).
     
    % Regola ricorsiva: X è antenato di Y
    antenato(X, Y) :- genitore(X, Y).                   % Caso base
    antenato(X, Y) :- genitore(X, Z), antenato(Z, Y).   % Passo ricorsivo
  3. Interrogazioni (Queries / Goals): Domande poste dall’utente all’interprete (?-) per verificare se un fatto è deducibile o per trovare per quali valori delle variabili un predicato è vero.

    ?- nonno(mario, anna).
    true.
     
    ?- nonno(mario, Nipote).
    Nipote = anna ;
    Nipote = marco.

Il motore inferenziale: Unificazione, Risoluzione SLD e Backtracking

Come fa Prolog a rispondere a una query senza che il programmatore abbia scritto un solo ciclo for? L’interprete Prolog applica automaticamente due meccanismi:

  1. Unificazione (Pattern Matching bidirezionale):
    Dati due termini logici (es. l’obiettivo corrente genitore(mario, Z) e un fatto nella base dati genitore(mario, luca)), l’unificazione cerca la sostituzione più generale delle variabili () che rende i due termini sintatticamente identici.
  2. Risoluzione SLD e Backtracking (Ricerca in profondità con ritorno sui propri passi):
    L’interprete esplora l’albero delle regole dall’alto verso il basso e da sinistra verso destra. Quando un sotto-obiettivo fallisce (o quando l’utente chiede una soluzione alternativa premendo ;), Prolog effettua automaticamente backtracking: annulla l’ultimo legame di variabile effettuato (unbinding), risale all’ultimo punto di scelta (choice point) e prova la clausola successiva!
flowchart TD
    Q["Query: <code>?- nonno(mario, Nipote).</code>"]
    R["Regola: <code>nonno(X, Y) :- genitore(X, Z), genitore(Z, Y).</code><br/>Unifica <code>X = mario, Y = Nipote</code>"]
    G1["Nuovo Goal: <code>genitore(mario, Z), genitore(Z, Nipote).</code>"]
    B1["Ramo 1: Unifica <code>genitore(mario, Z)</code> col fatto 1<br/><b>Z = luca</b>"]
    B2["Ramo 2 (Backtracking!): Unifica col fatto 2<br/><b>Z = sara</b>"]
    S1["Cerca <code>genitore(luca, Nipote)</code><br/>Trova fatto 3 ➔ <b>Nipote = anna</b> (Soluzione 1!)"]
    S2["Cerca <code>genitore(sara, Nipote)</code><br/>Trova fatto 4 ➔ <b>Nipote = marco</b> (Soluzione 2!)"]
    Q --> R --> G1
    G1 --> B1 --> S1
    G1 --> B2 --> S2

Tabella comparativa dei tre paradigmi

CaratteristicaParadigma Imperativo (es. C)Paradigma Funzionale (es. Haskell, Lisp)Paradigma Logico (es. Prolog)
Modello teorico di riferimentoMacchina di von Neumann / Macchina di Turing-calcolo (Lambda Calcolo di Church)Logica dei Predicati del Primo Ordine (Clausole di Horn)
Stile di programmazioneImperativo (Come calcolare passo passo)Dichiarativo (Cosa calcolare tramite funzioni)Dichiarativo (Quali relazioni sono vere)
Unità fondamentaleIstruzione / Procedura che modifica lo statoFunzione matematica pura Predicato / Relazione
VariabiliCelle di memoria mutabili (assegnamento distruttivo)Simboli immutabili legati a valoriVariabili logiche istanziate tramite unificazione
Meccanismo di ripetizioneCicli espliciti (for, while) + ricorsioneRicorsione e funzioni di ordine superiore (map, filter, fold)Ricorsione di regole + Backtracking automatico
Effetti collaterali (Side effects)Centrali (mutazione di stato e puntatori)Assenti nel funzionale puro (Trasparenza Referenziale)Assenti nella logica pura
Direzionalità del calcoloUnidirezionale (dagli input fissati all’output)Unidirezionale (dagli argomenti al valore di ritorno)Multidirezionale (lo stesso predicato può verificare o generare input/output)

La stessa informazione come funzione o come relazione

Una funzione di ordine superiore come map(f, xs) riceve una funzione da applicare a ogni elemento. Se f è pura, possiamo sostituire una sua chiamata con il valore risultante senza cambiare il comportamento osservabile. Una callback C permette di passare il comportamento, ma può leggere o modificare stato esterno. La simulazione di map in C richiede quindi un contratto di purezza se vogliamo usare lo stesso ragionamento.

In programmazione logica, il fatto genitore(anna, luca). descrive una relazione. Una regola per nonno(X, Z) può richiedere genitore(X, Y), genitore(Y, Z). Aggiungendo il fatto genitore(luca, mia)., la domanda nonno(anna, Chi) ammette Chi = mia. Una simulazione C può attraversare tabelle per cercare lo stesso risultato. L’unificazione e la ricerca delle soluzioni sono allora implementate esplicitamente.


Esempi guidati

Esempio 1: Simulare map e filter in C con puntatori a funzione

Anche se il C è un linguaggio imperativo, possiamo adottare uno stile funzionale scrivendo funzioni di ordine superiore che ricevono puntatori a funzione come argomento:

#include <stdio.h>
 
/* Funzione di ordine superiore MAP: applica f(x) ad ogni elemento di src */
void map_array(const int src[], int dest[], int n, int (*f)(int)) {
    for (int i = 0; i < n; i++) {
        dest[i] = f(src[i]);
    }
}
 
/* Funzione di ordine superiore REDUCE (FOLD): combina gli elementi con op(acc, x) */
int reduce_array(const int src[], int n, int init, int (*op)(int, int)) {
    int acc = init;
    for (int i = 0; i < n; i++) {
        acc = op(acc, src[i]);
    }
    return acc;
}
 
/* Funzioni pure da passare come argomento */
int triplo(int x) { return x * 3; }
int somma(int a, int b) { return a + b; }
int prodotto(int a, int b) { return a * b; }
 
int main(void) {
    int v[4] = {1, 2, 3, 4};
    int v_triplo[4];
 
    map_array(v, v_triplo, 4, triplo); /* v_triplo diventa {3, 6, 9, 12} */
 
    int s = reduce_array(v_triplo, 4, 0, somma);    /* 3 + 6 + 9 + 12 = 30 */
    int p = reduce_array(v_triplo, 4, 1, prodotto); /* 3 * 6 * 9 * 12 = 1944 */
 
    printf("Somma dei tripli = %d, Prodotto dei tripli = %d\n", s, p);
    return 0;
}

Esempio 2: Lo stesso problema risolto nei tre paradigmi (Appartenenza a una lista)

Problema: Verificare se l’elemento appartiene a una sequenza/lista .

  1. Imperativo (C): scorriamo un array mutando l’indice i:

    int appartiene_imp(const int v[], int n, int x) {
        for (int i = 0; i < n; i++) {
            if (v[i] == x) return 1;
        }
        return 0;
    }
  2. Funzionale (Python / Haskell style, senza cicli né mutazioni): una lista è vuota [] oppure è formata da una testa head e una coda tail:

    def appartiene_funz(lista, x):
        if not lista:              # Caso base: lista vuota -> False
            return False
        return (lista[0] == x) or appartiene_funz(lista[1:], x)
  3. Logico (Prolog): dichiariamo le due clausole di verità per il predicato membro(X, Lista) (dove [Testa | Coda] scompone la lista per unificazione):

    % Caso base (Fatto): X è membro di una lista se X è proprio la Testa della lista.
    membro(X, [X | _]).
     
    % Passo ricorsivo (Regola): X è membro della lista se X è membro della Coda.
    membro(X, [_ | Coda]) :- membro(X, Coda).

    Meraviglia della multidirezionalità in Prolog:

    • Se chiediamo ?- membro(2, [1, 2, 3]). Prolog risponde true. (verifica).
    • Se chiediamo ?- membro(E, [1, 2, 3]). con E variabile, Prolog genera uno per uno tutti gli elementi: E = 1 ; E = 2 ; E = 3!

Errori frequenti

Errori da evitare

  1. In Prolog, scambiare lettere minuscole (costanti) e MAIUSCOLE (variabili):
    Scrivere genitore(Mario, luca). non dichiara che l’individuo mario è genitore di luca, ma che qualsiasi oggetto Mario dell’universo (variabile universale!) è genitore di luca! I nomi di individui costanti devono sempre iniziare con una lettera minuscola (mario).
  2. In Prolog, scrivere X = X + 1 pensando che faccia un calcolo aritmetico:
    In Prolog l’operatore = indica l’unificazione sintattica, non la valutazione aritmetica! Se X vale 3, 3 = 3 + 1 fallisce (false) perché il termine 3 non unifica col termine composto +(3, 1). Per valutare un’espressione aritmetica in Prolog si usa l’operatore is: X1 is X + 1 (usando una nuova variabile X1, perché X già istanziata non può cambiare valore!).
  3. Nel paradigma funzionale, modificare in-place una lista passata come argomento:
    In linguaggi ibridi come Python o JavaScript, chiamare metodi distruttivi come lista.append(x) o lista.sort() dentro una funzione viola l’immutabilità e introduce side effects sul chiamante (meglio usare nuova = sorted(lista) o lista + [x]).

Esercizi di prova

Esercizio 1. Pipeline funzionale map / filter / reduce (Base)

Data la lista , determina passo dopo passo il valore prodotto dall’espressione funzionale:

Esercizio 2. Lettura e interrogazione di una base di conoscenza Prolog (Base)

Data la seguente base di conoscenza Prolog:

amico(anna, luca).
amico(luca, marco).
amico(anna, sara).
studia(luca, informatica).
studia(marco, matematica).
studia(sara, informatica).
 
compagno_studio(X, Y) :- amico(X, Y), studia(Y, informatica).

Quali soluzioni restituisce l’interprete Prolog per la query ?- compagno_studio(anna, Chi).? Mostra i passi di unificazione e backtracking.

Esercizio 3. Scrittura di regole logiche in Prolog: fratello (Intermedio)

Usando il predicato genitore(X, Y) (“X è genitore di Y”), scrivi in Prolog la regola per il predicato fratello(A, B) (“A e B sono fratelli/sorelle, cioè hanno almeno un genitore in comune”). Quale condizione aggiuntiva è necessaria affinché una persona non risulti fratello di se stessa?

Esercizio 4. Implementazione di filter in C con allocazione dinamica (Intermedio)

Scrivi in C la funzione di ordine superiore int *filter_dinamico(const int v[], int n, int (*pred)(int), int *out_n) che riceve un array v di n interi e un puntatore a funzione predicato pred, e restituisce un nuovo array allocato dinamicamente contenente solo gli elementi x per cui pred(x) restituisce un valore diverso da 0.

Esercizio 5. Somma degli elementi di una lista in Funzionale e in Prolog (Avanzato)

Esprimi il calcolo della somma degli elementi di una lista di numeri:

  1. Come funzione ricorsiva pura (senza cicli né variabili mutabili);
  2. Come predicato Prolog somma_lista(Lista, Somma) specificando il fatto base per la lista vuota [] e la regola ricorsiva per [Testa | Coda].

Provenienza del materiale

  • Dispensa ufficiale del corso: C1PROG1U4L6_Paradigmi_Funzionale_e_Logico tag accessibilità.pdf (Unità 4, Lezione 6 — I paradigmi funzionale e logico).
  • Marco Anisetti, Memoria, Appunti_di_Fine_Unità_4.pdf, cap. 5, paradigmi funzionale e logico.