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:
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.
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 matematicaf:A→B che associa ad ogni valore di input un unico valore di output.
Principi cardine della programmazione funzionale
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.
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!).
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).
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
map(f, lista): applica la funzione f a ciascun elemento di [x1,x2,…,xn] producendo la nuova lista [f(x1),f(x2),…,f(xn)].
filter(p, lista): applica il predicato booleano p ad ogni elemento e restituisce una nuova lista contenente solo gli elementi xi per cui p(xi)=Vero.
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 reducenumeri = [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 = 56somma_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.
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).
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 Ynonno(X, Y) :- genitore(X, Z), genitore(Z, Y).% Regola ricorsiva: X è antenato di Yantenato(X, Y) :- genitore(X, Y). % Caso baseantenato(X, Y) :- genitore(X, Z), antenato(Z, Y). % Passo ricorsivo
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:
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 ({Z/luca}) che rende i due termini sintatticamente identici.
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!
Logica dei Predicati del Primo Ordine (Clausole di Horn)
Stile di programmazione
Imperativo (Come calcolare passo passo)
Dichiarativo (Cosa calcolare tramite funzioni)
Dichiarativo (Quali relazioni sono vere)
Unità fondamentale
Istruzione / Procedura che modifica lo stato
Funzione matematica pura f:A→B
Predicato / Relazione R(x1,…,xn)
Variabili
Celle di memoria mutabili (assegnamento distruttivo)
Simboli immutabili legati a valori
Variabili logiche istanziate tramite unificazione
Meccanismo di ripetizione
Cicli espliciti (for, while) + ricorsione
Ricorsione 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 calcolo
Unidirezionale (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 x appartiene a una sequenza/lista L.
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;}
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)
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).
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
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).
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 + 1fallisce (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 variabileX1, perché X già istanziata non può cambiare valore!).
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]).
Quali soluzioni restituisce l’interprete Prolog per la query ?- compagno_studio(anna, Chi).? Mostra i passi di unificazione e backtracking.
Soluzione
L’interprete unifica la query con la testa della regola ponendo X = anna e Y = Chi, e deve soddisfare il corpo amico(anna, Chi), studia(Chi, informatica).:
Primo tentativo: amico(anna, Chi) unifica col 1° fatto amico(anna, luca) legando Chi = luca. Si passa al secondo goal studia(luca, informatica), che unifica col fatto studia(luca, informatica)→Successo! Prima soluzione: Chi = luca.
Backtracking: L’utente chiede altre soluzioni (;). Prolog annulla Chi = luca e cerca altri fatti per amico(anna, Chi). Il 2° fatto amico(luca, marco) non unifica (anna \= luca). Il 3° fatto amico(anna, sara) unifica legando Chi = sara. Si passa a studia(sara, informatica), che è vero →Successo! Seconda soluzione: Chi = sara.
Non ci sono altri fatti: la ricerca termina con Chi = luca ; Chi = sara.
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?
Soluzione
Se scrivessimo solo fratello(A, B) :- genitore(G, A), genitore(G, B)., interrogando ?- fratello(luca, luca). Prolog risponderebbe erroneamente true ponendo A = luca e B = luca! Dobbiamo imporre che A e B non unifichino (A \= B):
fratello(A, B) :- genitore(G, A), genitore(G, B), A \= B.
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.
Soluzione
#include <stdlib.h>int *filter_dinamico(const int v[], int n, int (*pred)(int), int *out_n) { if (!v || n <= 0 || !pred || !out_n) { if (out_n) *out_n = 0; return NULL; } int conta = 0; for (int i = 0; i < n; i++) { if (pred(v[i])) conta++; } *out_n = conta; if (conta == 0) return NULL; int *ris = (int *)malloc(conta * sizeof(int)); if (!ris) { *out_n = 0; return NULL; } int j = 0; for (int i = 0; i < n; i++) { if (pred(v[i])) { ris[j++] = v[i]; } } return ris;}
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:
Come funzione ricorsiva pura (senza cicli né variabili mutabili);
Come predicato Prolog somma_lista(Lista, Somma) specificando il fatto base per la lista vuota [] e la regola ricorsiva per [Testa | Coda].
def somma_funz(lista): return 0 if not lista else lista[0] + somma_funz(lista[1:])
Formulazione Logica in Prolog:
% Caso base: la somma della lista vuota è 0.somma_lista([], 0).% Passo ricorsivo: la somma di [Testa | Coda] è Somma se% SommaCoda è la somma di Coda E Somma vale Testa + SommaCoda.somma_lista([Testa | Coda], Somma) :- somma_lista(Coda, SommaCoda), Somma is Testa + SommaCoda.
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.