Tra una base di dati e l'altra mi sto dedicando a leggere con calma e pazienza e calma il famoso SICP, cioè Structure and Interpretation of Computer Programs, un libro molto amato da (tra gli altri) Peter Norvig che parla di computers, programmi, programmi del computers e altre cose che centrano con i programmi e con i computers. Tra queste pagine c'è un bell'esercizio che mi ha aperto in due le cervella per una-due ore che recita così:
In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 asDefinire one e two direttamente è semplicemente un gioco di sostituzioni:[clojure] (define zero (lambda (f) (lambda (x) x)))
(define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x))))) [/clojure]
This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the λ-calculus.
Define one and two directly. Give a direct definition of the addition procedure +.
[plain] (add-1 zero) → (lambda (f) (lambda (x) (f ((zero f) x)))) → (lambda (f) (lambda (x) (f ( (lambda (x) x) x)))) → (lambda (f) (lambda (x) (f x))) [/plain]
[plain] (add-1 uno) → (lambda (f) (lambda (x) (f ((uno f) x)))) → (lambda (f) (lambda (x) (f ( (lambda (x) (f x)) x)))) → (lambda (f) (lambda (x) (f (f x)))) [/plain]
È inutile dire che arrivato a questo punto m'ero un po' perso tra tutte queste funzioni e metafunzioni e così via. Che cos'è che si sta facendo, davvero? Su cosa stiamo operando?
La risposta è semplice una volta capìta, capirla però non è immediato (non lo è stato per me, almeno). Come suggerisce il testo dell'esercizio, stiamo più o meno cercando di creare un sistema di numerazione usando, al posto dei numeri, funzioni. Mind-boggling, davvero. Per venire fuori dall'astratto: quando contiamo usando le dita, contiamo oggetti; ora invece contiamo applicando ripetutamente una funzione a sé stessa. Lo so, non è che sia una spiegazione molto più concreta, ma quello che conta è che passi l'idea; in generale, il numerale di Church corrispondente all'intero n è una funzione che riceve in input una funzione f e ritorna una funzione g che è la composizione di f su f n volte. Se questa spiegazione non è ancora chiara (posso capirvi), ignoratela per un attimo, più tardi sarà più chiara.
Le definizioni di zero e di add-1 possono sembrare convolute a prima vista, ma ragionandoci su un attimo si può tirar fuori qualcosa.
[code] (define zero (lambda (f) (lambda (x) x))) [/code]
zero è una funzione che ritorna una funzione; la funzione ritornata prende in input una funzione f e, quale che sia f, ritorna la funzione identità. f viene del tutto ignorata, in pratica. Un esempio con zero:
[code] > ((zero (lambda (x) (* x 2))) 5) 5 > ((zero (lambda (x) (+ x 2))) 5) 5 > ((zero (lambda (x) (* x 193824))) 5) 5
[/code]
Come previsto, zero f ritorna sempre (lambda (x) x), cioè la funzione identità; applicando la funzione identità a 5 si ottiene 5. Tutto tranquillo fin'ora (cioè più o meno, ecco).
[code] (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x))))) [/code]
add-1 prende in input un numerale di Church n e ritorna una funzione; questa funzione ritornata prende in input una funzione f e ritorna a sua volta una funzione g(x) che ha come definizione g(x) := f ((n f) x).
Respiro. Partiamo dalla fine: come si potrebbe spiegare in parole più povere la funzione g? Muovendoci dall'interno verso l'esterno: (n f) applica n (che è il nostro numero di Church, cioè una funzione) alla funzione f; se ricordate ciò che è scritto poco più sopra, possiamo vedere un numero di Church n come l'applicazione ripetuta n volte di una funzione: (n f) significa, in pratica, componi f con sé stessa n volte. Ovviamente, (n f) ritorna una funzione (la funzione f composta n volte, per l'appunto); ma se vogliamo ottenere un dato concreto, bisogna dare in pasto a questa funzione un argomento: questo argomento è la x della nostra g(x). (lambda (x) (f ((n f) x))) compone f con sé stessa n volte, valuta il valore di questa funzione su input x, quindi sul valore ottenuto applica un'altra volta f. Ritornando all'isomorfismo intero-numero di Church: add-1 n non fa altro che prendere un NdC n, cioè una funzione che prende in input una funzione f e effettua n composizioni su sé stessa, ed aumentare il numero di composizioni effettuate da n a n+1.
Vedendo qualche esempio:
[code] > (define one (add-1 zero)) > (define two (add-1 one)) > (define three (add-1 two)) > ((three (lambda (x) (+ x 11))) 1) 34 > ((two (lambda (x) (* x x))) 3) 81 > ((three add1) 0) 3 [/code]
Esplicitando ad esempio la quarta riga:
[code] ((three (lambda (x) (+ x 11))) 1) → ((three f) 1) → ((lambda (x) (f (f (f x)))) 1) → ((lambda (x) (+ (+ (+ x 11) 11) 11)) 1) → ... ((lambda (x) (+ x 33)) 1) 33+1=34 [/code]
Applicando la triplice composizione di (+ x 11) si ottiene ovviamente (+ x 33), che in ultima analisi è insomma la stessa cosa di (three (lambda (x) (+ x 11))). 33+1 fa 34, come da seconda elementare.
La riga 8 introduce un concetto interessante, che tornerà utile per specificare la somma tra NdC. Applicare 3 volte (+ x 1) a 0 fa evidentemente 3, cioè il numero di applicazioni ripetute di (+ x 1). Possiamo quindi sfruttare add1 (che non è la nostra add-1 definita a inizio post!) per scrivere un convertitore da NdC a intero:
[code] (define (church->int n) ( (n add1) 0)) [/code]
Voilà! Preciso ed essenziale. Ma non è finita qui. Introduciamo una notazione molto informale e che abuseremo per descrivere meglio la funzione appena definita:
Ovvero: add1 composto n volte (n è un NdC, se volessimo essere precisi dovremmo dire "composto int(n) volte", ma passatemi il termine) con sé stesso su input 0 dà int(n). È esattamente quanto descritto nella funzione appena sopra, solo un po' più chiaro (forse).
"Che bisogno c'era di questa notazione?" vi starete chiedendo. Forse nessuno, boh, alla fine nessuno ha certezze nella vita (io men che meno), ma in un attimo risulterà quantomento un simpatico stratagemma per capire meglio come definire la somma tra due NdC che, con questa notazione, è quasi un processo immediato:
add-1 (con il trattino!) composto a volte su input b equivale a dire a+b in termini di NdC! La corrispondente funzione somma è la seguente:
[code] (define (sum a b) ( (a add-1) b)) [/code]
(a add-1) prende add-1 e la compone int(a) volte con sé stessa. Questa nuova funzione viene applicata al NdC b, ed ecco che abbiamo definito la somma tra NdC senza usare ripetutamente add-1!