Soluzione del quiz e commenti

Siccome ogni promessa è debito, andiamo finalmente a spiegare in che modo ho generato l’immagine oggetto del quiz che vi ho proposto qualche giorno fa. Anzi, già che ci siamo, eccone un’altra versione nuova di pacca, e ancora più dettagliata rispetto alla precedente:

Si tratta di un classico esempio di immagine raster, curioso termine che ha origine nella lingua inglese (in cui deriva dal latino rastrum, “rastrello”) ed è stato successivamente reimportato in italiano con il suo nuovo significato tecnico, in una sorta di girotondo linguistico. Un’immagine raster non è altro che una griglia rettangolare di pixel a ciascuno dei quali è associato un colore; nel nostro caso i colori in gioco sono solo due, bianco e nero, e si parla perciò più propriamente di una bitmap, o griglia di bit, l’idea essendo ovviamente che un bit acceso corrisponda a un pixel nero e un bit spento a uno bianco (o viceversa, non è importante).

Un’immagine di questo tipo si presta molto facilmente a rappresentare una relazione binaria tra numeri naturali: quest’ultima infatti non è altro che un insieme di coppie ordinate di elementi di \(\mathbb{N}\), o se si preferisce un sottoinsieme del prodotto cartesiano \(\mathbb{N}\times \mathbb{N}\) (che per definizione è l’insieme di tutte le coppie ordinate di numeri naturali). Ora, si dà il caso che \(\mathbb{N}\times \mathbb{N}\) sia proprio una griglia bidimensionale (infinita, ma non sottilizziamo…), e quindi che un suo sottoinsieme \(R\) sia completamente determinato “accendendo” tutti e soli i pixel di questa griglia che corrispondono a coppie \((a,b)\) di numeri naturali che appartengono a \(R\). Si ottiene così quello che si suole chiamare il grafico della relazione binaria \(R\).

Nell’immagine precedente la relazione raffigurata è quella di divisibilità, usualmente denotata \(a\mid b\), definita come segue:

\(a\mid b\) se e solo se esiste \(n\in \mathbb{N}\) tale che \(b = na\)

In altri termini, il pixel di coordinate \((a,b)\) (partendo dall’angolo in alto a sinistra) è acceso se e solo se \(a\mid b\), cioè \(a\) divide \(b\).

Naturalmente il discorso può essere ripetuto pari pari per qualunque altra relazione tra numeri naturali. Ad esempio, due numeri \(a\) e \(b\) si dicono coprimi se non hanno fattori primi in comune, o equivalentemente se il loro m.c.d. è 1. Il seguente è il grafico della relazione “\(a\) è coprimo a \(b\)” sull’insieme dei numeri naturali minori di 80, ingrandito quattro volte (o se preferite, con pixel di lato 4):

Niente male, nevvero? La vedrei bene come stampa da appendere al muro, o magari come tappeto, al posto di un più classico persiano.

Tra l’altro, certe proprietà di una relazione binaria emergono chiaramente dal suo grafico: ad esempio l’immagine precedente è simmetrica per riflessione attorno alla diagonale principale, il che corrisponde al fatto che la relazione di coprimalità è simmetrica (se \(a\) è coprimo con \(b\) allora è anche vero che \(b\) è coprimo con \(a\)). O ancora, la diagonale principale è formata da soli pixel bianchi: questo significa che la relazione in esame è irriflessiva (nessun numero è coprimo con sé stesso). Viceversa nell’immagine a inizio post la diagonale principale è formata da soli pixel neri: questo perché ogni numero è divisibile per sé stesso, ovvero la relazione di divisibilità è riflessiva. Per la cronaca, essa è anche antisimmetrica e transitiva (e quindi è una relazione d’ordine parziale), e con un po’ di impegno anche queste altre proprietà potrebbero essere messe in evidenza per via grafica.

Ma parlare di queste cose ci porterebbe su un’altra strada; quello che voglio fare adesso è invece spiegare in che maniera ho generato queste immagini. Si tratta in realtà di un esercizio di programmazione abbastanza semplice. Come i lettori di vecchia data di questo blog forse ricorderanno, da circa un anno a questa parte il mio linguaggio di programmazione preferito è il Lisp, nella sua variante nota come Scheme, ed è pertanto in tale linguaggio che ho implementato il programma in questione.

Ora, poiché il Lisp è sfortunatamente molto poco conosciuto rispetto a linguaggi più tradizionali come C e derivati, immagino che questo post perderà gran parte del suo interesse per molti di voi. D’altro canto non posso neanche somministrarvi un crash-course del tipo “il Lisp in mezz’ora” (ammesso che una cosa del genere sia possibile), quindi non mi resta che confidare nella leggibilità del mio codice. Almeno una cosa però la devo assolutamente spiegare: laddove nella stragrande maggioranza dei linguaggi di programmazione si scrive f(x) per indicare l’applicazione della funzione f all’argomento x, in Scheme si scrive invece (f x); similmente si scrive (f a b) se f è una funzione di due argomenti, e così via. La stessa notazione si applica anche ai predicati: così ad esempio un test quale a>0 si scrive (in maniera un po’ perversa) come (> a 0). Senza questa dritta, un sorgente Lisp rischia di sembrare solo un’accozzaglia di parentesi messe giù a caso.

Il modo più naturale di implementare in Scheme una relazione binaria tra numeri naturali è quello di definire il corrispondente predicato, cioè una procedura che mangia due numeri naturali e ritorna #t (“vero”) se i due numeri sono in relazione tra loro e #f (“falso”) altrimenti. Ad esempio per la relazione di divisibilità questo si fa come segue:

(define (divides? a b)
  (if (= a 0)
      (= b 0)
      (= (remainder b a) 0)))

(È convenzione comune in Scheme dare ai predicati un nome che termina con un punto di domanda, per evidenziare che il risultato è un valore di verità. La sintassi dell’espressione condizionale if è quella che ci si aspetta: (if x y z) significa “se x è vero allora il risultato è y, altrimenti è z“.)

In generale, supponiamo di avere un predicato pred cui si possa dare in pasto una qualunque coppia di numeri naturali e di voler produrre il suo grafico. Siccome i numeri naturali sono infiniti (ma va?), dovremo accontentarci di graficare la relazione su un sottoinsieme di \(\mathbb{N}\times \mathbb{N}\), per esempio sul quadrato \([0,n]\times [0,n]\). La prima cosa da fare è quella di calcolare (pred a b) per tutti i valori di a e b compresi tra 0 e \(n\) e memorizzare i risultati in una struttura dati opportuna. Siccome in Lisp (che, ricordiamo, è l’acronimo di list processing) la struttura dati per eccellenza è la lista, raccoglieremo tutti questi simpatici bit in una lista. Questo si può fare con una ricorsione che, se stessi scrivendo in inglese, definirei almost straightforward (è un classico esercizio da primi capitoli di un libro di programmazione in Lisp), e otteniamo così una procedura di questo tipo (in cui supponiamo che i simboli pred e n siano già definiti):

(define (gen-bit-list i j)
  (cond ((> i n) '())
        ((= j n) (cons (pred i j)
                       (gen-bit-list (+ i 1) 0)))
        (else (cons (pred i j)
                    (gen-bit-list i (+ j 1))))))

(cond è un costrutto analogo allo switch del C: si tratta di un condizionale multiplo, o sequenza di if effettuati uno dopo l’altro.) L’indice i corre sulle righe e l’indice j sulle colonne, e la ricorsione è sul quadrato \([0,n]\times [0,n]\) con l’ordinamento lessicografico. Questo significa che l’indice j viene incrementato fino a raggiungere la fine di una riga (j=n); quando ciò accade viene incrementato i e resettato a zero j. La condizione di terminazione è i>n, nel qual caso la procedura ritorna la lista vuota (che in Scheme si denota con '() e in altri dialetti di Lisp con nil); la ricorsione fa il resto, costruendo a partire da questo caso base la lista desiderata.

C’è ancora un piccolo caveat: siccome un predicato ritorna non un numero ma un valore di verità (cioè #t o #f), la procedura così com’è costruisce in realtà una lista di valori di verità, mentre noi vogliamo una lista di bit. Per rimediare a ciò basta definire quello che in gergo si chiama un wrapper, cioè una procedura che “avvolge” il predicato pred e converte il suo valore nella forma che desideriamo:

(define (pred-wrapper a b)
  (if (pred a b) 1 0))

e sostituire poi tutte le chiamate a pred con chiamate a pred-wrapper.

Occorre ora trasformare questa lista di bit in un’immagine bitmap vera e propria. Il modo più semplice per farlo è quello di usare il formato (plain) PBM che, per citare la relativa pagina di manuale, è talmente semplice che

we hardly need to define the format here, because you can decode it by inspection.

Sostanzialmente, un file plain PBM è formato da un header (che specifica larghezza e altezza della griglia di bit) seguito dalla sequenza di bit che compongono l’immagine, ciascuno dei quali è rappresentato dal numero 0 (bianco) o 1 (nero), separati da spazi. Più semplice di così si muore! Ecco la procedura che scrive la lista di bit ottenuta in precedenza nel file associato alla porta port (che deve essere stata precedentemente aperta in scrittura):

(define (write-bit-list lst port)
  (if (null? lst)
      (display "\n" port)
      (begin (display (string (car lst) " ") port)
             (write-bit-list (cdr lst) port))))

(car e cdr sono i nomi che il Lisp dà alle procedure che ritornano la testa e la coda di una lista, quelle che di solito vengono chiamate head e tail.)

A questo punto resta solo da mettere assieme queste procedure con il codice che provvede ad aprire il file di output e a scrivere l’header PBM. Il programma completo è:

(define (graph pred n filename)
  (define (pred-wrapper a b) (if (pred a b) 1 0))

  (define (gen-bit-list i j)
    (cond ((> i n) '())
          ((= j n) (cons (pred-wrapper i j)
                         (gen-bit-list (+ i 1) 0)))
          (else (cons (pred-wrapper i j)
                      (gen-bit-list i (+ j 1))))))

  (define (write-bit-list lst port)
    (if (null? lst)
        (display "\n" port)
        (begin (display (string (car lst) " ") port)
               (write-bit-list (cdr lst) port))))

  (let ((outport (open-output-file filename)))
    (display (string "P1\n" (+ n 1) " " (+ n 1) "\n")
             outport)                             ; PBM header
    (write-bit-list (gen-bit-list 0 0) outport)   ; raster data
    (close-output-port outport)))

L’immagine del quiz è stata prodotta con un comando del tipo
(graph divides? 255 "prova.pbm") e successivamente sottoposta a un veloce passaggio con GIMP per convertirla in formato PNM compresso e ingrandirla.

In realtà, questa prima versione di graph può essere migliorata in vari modi. Tanto per cominciare, notiamo che la lunghezza della lista di bit generata da gen-bit-list cresce come il quadrato di n (lato dell’immagine), e ciò può portare a ricorsioni che esauriscono lo spazio disponibile per lo stack anche per valori di n relativamente bassi. Un modo di procrastinare questo problema è quello di memorizzare, al posto dei singoli bit, direttamente i byte che si ottengono “impacchettando” 8 bit alla volta. In questo modo diventa anche molto più facile creare in output un file in formato PBM vero e proprio (che si differenzia dal plain PBM proprio per il fatto che i bit sono rappresentati come tali, cioè come cellette all’interno di un byte, e non tramite i simboli 0 e 1).

Un’altra piccola ma significativa modifica consiste nell’introdurre la possibilità di graficare la relazione data non necessariamente sul quadrato \([0,n]\times [0,n]\) ma su un qualunque rettangolo \([r_{0},r_{1}]\times [c_{0},c_{1}]\) per opportuni numeri naturali \(r_{0}\), \(r_{1}\), \(c_{0}\) e \(c_{1}\). Implementando tutte queste idee sono arrivato alla versione corrente del programma (ribattezzato pred-plot), con cui ho prodotto le immagini di questo post:

(define (pred-plot pred r0 r1 c0 c1 filename)
  (define (pred-wrapper a b) (if (pred a b) 1 0))

  (define (pad w)
    (if (= (string-length w) 8)
        w
        (pad (string w 0))))

  (define (gen-byte-list i j w)
    (cond ((> i r1)
           '())
          ((> j c1)
           (cons (pad w) (gen-byte-list (+ i 1) c0 "")))
          ((= (string-length w) 8)
           (cons w (gen-byte-list i j "")))
          (else
           (gen-byte-list i (+ j 1) (string w (pred-wrapper i j))))))

  (define (write-byte-list lst port)
    (if (null? lst)
        (display "\n" port)
        (begin (write-char (integer->char (car lst)) port)
               (write-byte-list (cdr lst) port))))

  (let ((byte-list (map (lambda (w) (string->number w 2))
                        (gen-byte-list r0 c0 "")))
        (outport (open-output-file filename)))
    (display (string "P4\n" (+ (- c1 c0) 1)
                     " " (+ (- r1 r0) 1) "\n")
             outport)                             ; PBM header
    (write-byte-list byte-list outport)           ; raster data
    (close-output-port outport)))

(Nota: il codice precedente funziona senza problemi con l’interprete Scheme del MIT, che è quello che uso di solito; non garantisco per gli altri, anche se un qualunque interprete R5RS dovrebbe andare bene.)

L’ovvio passo successivo consiste nel passare dalle immagini in bianco e nero a quelle in toni di grigio, ovvero dal grafico di una relazione binaria a quello di una operazione binaria. Ciò rende possibile ad esempio generare immagini come questa:

che rappresenta il grafico dell’addizione nel quadrato \([0,255]^{2}\). Per questo e altri sviluppi vi rimando però a una prossima (spero) puntata.