Tutti gli articoli di gigabytes

C++11 singleton pattern, again, really.

In questo post voglio correggerne uno di qualche tempo fa, precisamente questo. Il post non contiene errori, che io sappia, ma ha un fondamentale problema: la soluzione presentata è lungi dall’essere ottimale.

Il problema è l’implementazione di un singleton thread-safe, e presentavo la soluzione alle race-condition del Double Checked Locking usando i nuovi std::atomic del C++11. Il punto è che sporcarsi le mani con tipi atomici, sincronizzazioni, locking e quant’altro, in C++11 non serve proprio.

Continua a leggere

Buon Darwin Day a tutti!

Oggi 12 febbraio si festeggia il Darwin Day 2014, nell’anniversario della nascita del biologo naturalista Charles Darwin.

É molto interessante questa iniziativa, che ci ricorda che nonostante tutto quello che è successo dal 1809, la scienza e la logica di noi scimmie evolute hanno ancora molto da fare per diminuire il numero di scimmiotti in circolazione (coloro che scimmiottano ciò che gli viene insegnato senza metterlo in discussione).

Buon compleanno, Charles!

A quanto pare, la fisica quantistica dimostra un po’ di tutto…

Gira di nuovo su Facebook questo link:
La fisica quantistica dimostra che la vita continua dopo la morte

Leggetelo con calma ma non aspettatevi illuminazioni. Si tratta di una bufalata vecchia come la morte, appunto… Girava un articolo sulla stessa notizia almeno un anno fa. Non entro nel merito di cosa la fisica quantistica dica o non dica, perché non essendo un fisico evito di fare brutte figure, ma nella mia ignoranza scorgo le caratteristiche tipiche di tutto quel sotto genere di “pseudo-scienza” che si aggira sui social network come un virus. Stessa notizia reiterata nel tempo. Titolo clamoroso. Assenza di fonti. Nessuno ne parla, perché tutti tacciono?

Se ci si vuole sporcare le mani con la vera fisica quantistica, si può partire da qui. Altrimenti, è facile incorrere in qualsiasi tipo di strafalcione, perché le ipotesi e i risultati di questa branca della scienza sono così paradossali per il senso comune che è difficile distinguerli dalle stupidaggini, se non si va affondo.

Continua a leggere

C# lock keyword in C++11 (quasi)

Alcuni linguaggi, come il Java o il C#, mettono a disposizione una primitiva a livello di linguaggio per specificare che un certo blocco di codice debba essere eseguito da un solo thread alla volta. In C# questa parola chiave è lock, che funziona più o meno così:

lock(obj) {
   something();
}

Ogni thread che esegue questo pezzo di codice sulla stessa istanza di obj acquisisce un lock esclusivo (dichiarato automaticamente dal compilatore nella classe di appartenenza del codice in questione).

Continua a leggere

I dare you to say new and delete again, I double dare you

Una delle cose che tormentano i programmatori C e C++ di tutte le età è l’annosa questione della gestione della memoria.

Una delle cose che più mi piacciono del C++11 è proprio come viene affrontato il problema. Ero tentato di dire “risolto”, ma sarebbe stato errato. In effetti, il problema della gestione della memoria non si può “risolvere” con qualche feature del linguaggio. Si deve affrontare apertamente.

Continua a leggere

Qualunque cosa tu scelga di fare…

Questo post è un commento Facebook cresciuto troppo, ad un post di un amico che citava una statistica:

3 milioni e 700mila persone in Italia né studiano, né lavorano, né stanno seguendo alcun percorso formativo [...]

Ho deciso di trasformare il mio commento in un post di questo blog perché stava diventando troppo lungo per non sembrare una trollata, ma in ogni caso da tempo aspettavo l’ispirazione per mettere nero su bianco la mia opinione su alcune cose… In origine sarebbe stata la risposta al seguente commento, che replicava alla mia opinione che si debba ripartire dal modo in cui vediamo cultura e formazione culturale (cultura in senso ampio, anche e soprattutto scientifica):

Nicola, quello è sicuramente un problema, ma non credo sinceramente che sia la chiave di lettura del dato Istat che ho riportato. Il problema non è lo studio, è la prospettiva… Qualunque cosa tu scelga di fare oggi…

Bene, ecco come la penso…
Continua a leggere

La pigrizia dei programmatori

Una breve apparizione per riportare quella che penso sia una delle descrizioni più accurate della giornata tipica di un esemplare tipico di “programmatore” (almeno se si trova nel suo habitat e non si sta avvicinando la stagione della release), presa direttamente da questo post, che per il resto parla di tutt’altro (programmazione funzionale).

La riporto tale e quale:

Programmers are procrastinators. Get in, get some coffee, check the mailbox, read the RSS feeds, read the news, check out latest articles on techie websites, browse through political discussions on the designated sections of the programming forums. Rinse and repeat to make sure nothing is missed. Go to lunch. Come back, stare at the IDE for a few minutes. Check the mailbox. Get some coffee. Before you know it, the day is over.

Chi non si ritrova? :)

In principio era Darwin

L’Escherichia coli è un batterio molto importante per la vita di tutti i mammiferi di questo pianeta, compreso l’uomo. È un parassita che si annida nell’intestino di un neonato fin dai primi minuti, e comincia a riprodursi consumando ossigeno e liberando anidride carbonica, rendendo l’ambiente adatto alla vita di altri tipi di batteri, che aiutano l’organismo ospite in molteplici attività, compresa la digestione e l’espulsione delle scorie.
Ma questo batterio è importante per noi anche per un altro motivo: è stato, per i biologi di tutto il Novecento, la stele di Rosetta per la comprensione dei meccanismi di trasmissione ereditaria del patrimonio genetico negli organismi viventi. La semplicità di questo organismo si contrappone alla complessità di alcuni suoi organi, ad esempio le ciglia con cui si sposta, il cui funzionamento è stato nondimeno spiegato nel dettaglio. Questo batterio è stato la chiave, negli ultimi vent’anni, di un esperimento che, osservando 45.000 generazioni di batteri riprodottisi in vitro, ha mostrato in diretta il funzionamento dei meccanismi di selezione naturale alla base dell’evoluzione delle specie. Ogni scienziato che si rispetti, può avere accesso e controllare i dati di questo importante esperimento:

Ai fondamentalisti, invece, [Lenski, l'autore dell'esperimento, ndr] consiglia di accontentarsi dei miliardi di Escherichia coli che ciascuno di essi ha nel proprio intestino: oltre al fatto che bisogna lavarsi bene le mani dopo essere andati in bagno, questo significa anche che al mondo ci sono miliardi di miliardi di Escherichia coli, ciascuno dei quali si riproduce più volte al giorno. E poiché all’incirca una volta su un miliardo si verifica una mutazione, più o meno tutte le possibili mutazioni avvengono ogni giorno, comprese quelle estremamente improbabili: vogliamo veramente credere che Dio, se c’è, si abbassa a sprecare quotidianamente miracoli nei nostri intestini?

Con questa chiosa finale, Piergiorgio Odifreddi termina in bellezza il capitolo “Osservare l’evoluzione in atto” del suo libro In princio era Darwin, da cui ho preso anche tutte le informazioni riportate sopra sul batterio. Come si vede da questo pezzo, Odifreddi mantiene anche in questo libro il suo stile sprezzante e la sua attitudine a dire schiettemente ciò che pensa senza falso timore reverenziale.

Non si tratta, però, di un libro di opinioni, bensì di una breve storia della “evoluzione dell’evoluzionismo”, dai lavori di chi, prima di Darwin, ha gettato le basi del suo lavoro, fino ai successivi esperimenti di genetica di Mendel, e alla comprensione dei meccanismi di genetica e di genomica conquistati nel Novecento grazie anche ai primi lavori sul moscerino della frutta e, appunto, ai recenti studi sull’Escherichia coli.

Il libricino, breve e di scorrevolissima lettura, racconta la storia di questa branca così tartassata della scienza moderna, incrociandola con quella dei suoi protagonisti e dei suoi detrattori (verso i quali Odifreddi non si risparmia accese critiche), e suscita la voglia di approfondire l’argomento anche a chi, come questo comune Homo sapiens, non è mai stato un biologo.

Ora saluto, è ora di pranzo, vado a dare ai miei Eschericchini qualcosa da mangiare ;)

Noi due ci complementiamo (in gruppo)

Nella vita quotidiana di un informatico, alcuni strumenti sono talmente radicati che non ci si accorge neanche della loro presenza. Uno di questi è il complemento a due.

Nel lontano 2005 mentre imparavo a scuola i primi rudimenti di elettronica, un prof ci spiegò come venivano rappresentati i numeri all’interno di un sistema digitale. Una volta capito il sistema di numerazione binario, ci si spostò sul problema di rappresentare i numeri negativi.

La prima idea che viene in mente è utilizzare un bit per indicare il segno del numero. Quindi se abbiamo a disposizione 8 bit, e il numero 42 si rappresenta come 00101010, allora -42 sarà 10101010. Semplice ma inadatto. Il problema di questo sistema è la difficoltà di realizzazione dei circuiti per la somma. Un sommatore è un elemento molto semplice di per sé, in quanto la somma binaria si implementa semplicemente con uno XOR tra i due bit da sommare e il bit di riporto delle cifre precedenti. Una grande comodità sta nel fatto che un sommatore da 16 bit si può ottenere semplicemente mettendo in cascata due sommatori identici da 8 bit. Questo vale però per numeri positivi. Se esprimiamo numeri negativi con il semplice sistema che abbiamo appena inventato, la somma diventa molto più complicata. Il bit di segno di ognuno dei due addendi va analizzato per sapere se è positivo o negativo, e la logica per la somma va cablata in modo ad-hoc a seconda di quanti bit usiamo per rappresentare il numero, e ottenere un sommatore di una certa larghezza a partire da sommatori più piccoli non è così ovvio.

Il sistema di complemento a due rappresenta i numeri negativi in un modo che lascia la somma molto semplice da realizzare, mantenendo la comodità di avere un bit che indichi istantaneamente il segno del numero. Ma come funziona? Il complemento a due viene di solito spiegato, anche a livello universitario (per lo meno nel corso di Architettura degli Elaboratori dove l’ho sentito spiegare io all’università), nel seguente modo, ne più ne meno:

Il complemento a due di un numero si ottiene invertendo tutti i bit e sommando uno.

Facciamo un esempio. Abbiamo detto che il numero 42 a 8 bit si scrive 00101010, invertendo tutti i bit si ottiene 11010101, e sommando 1 si ottiene quindi che -42 va rappresentato con il numero 11010110 (che interpretato come numero positivo sarebbe 214). Ma perchè questo meccanismo così strano? Risposta: perchè la somma tra due numeri in complemento a due, siano essi positivi o negativi, si esegue con un normale sommatore binario senza alcuna modifica. Davvero? Si. Facciamo un esempio.

$$
\begin{align}
-42 + 10 &= 11010110 + 00001010 \\
&= (214) + 10 \\
&= (224) = 11100000 = -32
\end{align}
$$

Anche casi particolari funzionano bene, visto che guardacaso, -42 + 42 fa proprio zero. Quindi sembra funzionare, e si capisce il vantaggio di usare una rappresentazione in cui la somma si implementa esattamente come se i numeri negativi non esistessero. Ma si riesce a convincersi del perchè funziona?

Quarantaquattro bit in fila per 8 con resto di 4

Il funzionamento del complemento a due sfrutta la struttura del gruppo additivo \(\mathbb{Z}_n\), ovvero degli interi in aritmetica modulare. Per mantenere le cose semplici facciamo finta di avere a disposizione solo 3 bit. Eseguendo una somma binaria scartando l’ultimo riporto otteniamo proprio una somma modulo \(2^3=8\), e quindi si tratta proprio del gruppo \(\mathbb{Z}_8\). Di seguito compiliamo una tabella con il risultato di tutte le somme possibili:

$$\begin{array}{c|cccc|cccc}
+ & \mathbf{0} & \mathbf{1} & \mathbf{2} & \mathbf{3} & \mathbf{4} & \mathbf{5} & \mathbf{6} & \mathbf{7} \\
\hline
\mathbf{0} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\mathbf{1} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 0 \\
\mathbf{2} & 2 & 3 & 4 & 5 & 6 & 7 & 0 & 1 \\
\mathbf{3} & 3 & 4 & 5 & 6 & 7 & 0 & 1 & 2 \\ \hline
\mathbf{4} & 4 & 5 & 6 & 7 & 0 & 1 & 2 & 3 \\
\mathbf{5} & 5 & 6 & 7 & 0 & 1 & 2 & 3 & 4 \\
\mathbf{6} & 6 & 7 & 0 & 1 & 2 & 3 & 4 & 5 \\
\mathbf{7} & 7 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
\end{array}$$

Essendo un gruppo, ogni elemento \(n\) ha un inverso \(-n\) (o opposto, visto che parliamo di somma), e ciò si può notare anche dal fatto che nella tabella c’è uno zero in ogni riga, ovvero per ogni elemento \(n\) si può trovare un elemento \(-n\) tale che \(n+(-n)=0\). Ad esempio, in questo caso l’opposto di \(3\) è \(5\), perchè \(3+5=0\,(\mathrm{mod}\,8)\). La rappresentazione binaria del numero \(3\) con 3 bit è 011, mentre il \(5\) si esprime come 101, che guardacaso è il complemento a due di \(3\). È solo un caso?

In effetti no. È facile calcolare gli opposti in questo gruppo: se abbiamo a disposizione \(b\) bit, e \(n\) e \(m\) sono opposti in \(\mathbb{Z}_{2^b}\), allora \(n+m=2^b\) e quindi \(m=2^b-n\), che risulta essere proprio il complemento a due di \(n\). Infatti, il complemento dei bit di \(n\) (chiamiamolo \(\overline n\)) si ottiene sottraendo \(n\) al numero ottenuto impostando tutti i \(b\) bit disponibili:
$$\overline n = \underbrace{111\ldots 111}_{b\,\text{bit}} – n = 2^b – 1 – n$$
Quindi ci siamo:
$$\overline n + 1 = (2^b – 1 – n) + 1 = 2^b – n = -n$$

Ecco svelato il mistero. Fissata una lunghezza delle parole di \(b\) bit, il complemento a due di un numero è il suo opposto nel gruppo additivo \(\mathbb{Z}_{2^b}\). Ecco perchè la somma si esegue esattamente come fosse una numerazione binaria standard, che è il vantaggio principale di questo sistema. Una conseguenza di ciò è che anche l’ordinamento tra due numeri dello stesso segno si esegue allo stesso modo (mentre per segni opposti basta confrontare ovviamente solo il bit di segno).

Inoltre, manteniamo ancora il fatto che il bit più significativo della parola indichi il segno del numero. Infatti, con questo sistema i numeri considerati “negativi” sono nella forma \(2^b-n\) dove \(n\) dev’essere minore di \(2^{b-1}\) (cioè la metà di tutto il range disponibile), perchè altrimenti non avremmo un opposto per ogni numero. Quindi, il range di numeri positivi rappresentabili va da zero a \(2^{b-1}-1\), ovvero tutte le combinazioni di \(b\) bit che tengono a zero il bit più significativo. Al contrario, nei valori considerati negativi il bit più significativo vale 1. In riferimento alla tabella mostrata qui sopra, questo vuol dire che i numeri da zero a \(3\) sono “positivi”, mentre quelli da \(4\) a \(7\) sono i rispettivi opposti. In realtà, dalla tabella si vede bene che il \(4\) è l’opposto di se stesso, non l’opposto di zero. Questo è un comportamento auspicabile, perchè non vogliamo un valore (positivo o negativo che sia) che sommato a zero dia ancora zero. L’origine di ciò, comunque, è che se consideriamo lo zero come un caso a se, il numero di valori positivi è uno in meno dei valori negativi disponibili. Quello che avanza è il più piccolo di tutti i numeri negativi a disposizione, che rappresenta quindi il “fondo scala” del nostro sistema di numerazione. Il range di tutti i valori rappresentabili con \(b\) bit va quindi da \(-2^{b-1}\) a \(2^{b-1}-1\). Ad esempio, con 8 bit si ottiene un range da \(-128\) a \(127\).

La somma non è l’unica operazione aritmetica del mondo. Eseguire il prodotto in modo semplice sarebbe auspicabile. Ancora una volta, in complemento a due il prodotto si esegue esattamente come se si trattasse di normali numeri in notazione binaria. Questo perchè in realtà lo sono. Stiamo lavorando su un gruppo \(\mathbb{Z}_N\), e il fatto che associamo ad alcuni valori il ruolo di numeri “negativi” non cambia le proprietà del gruppo. Di conseguenza, aggiungendoci l’operazione di moltiplicazione e lavorando dunque sull’anello \(\mathbb{Z}_N\), tutto continua a funzionare.

Bits, bits everywhere

E cosa succede se, ad un certo punto, il numero di bit che abbiamo a disposizione non è più sufficiente? In altre parole, ora vedremo come si esegue una promozione che aumenta il numero di bit disponibili, ovvero come si implementa il seguente pezzo di codice C:

int8_t i;
int16_t j = i;

Vogliamo un’operazione universale, ovvero un procedimento che funzioni senza dover distinguere il caso in cui il numero originario sia negativo o positivo. Vorremmo anche evitare di dover calcolare il valore assoluto del numero, estendere i bit e poi ricalcolare l’opposto.

Il procedimento in questione esiste e si chiama sign extension, e consiste nell’aggiungere bit più significativi, e copiare il bit di segno del numero in tutti i nuovi bit aggiunti. Ciò ovviamente funziona nel caso di un numero positivo (cifre zero in più a sinistra non cambiano nulla), ma vediamo come funziona con numeri negativi. Ad esempio, il numero -42, che in 8 bit come già detto è 11010110, si promuove a 16 bit copiando il bit di segno su tutti gli 8 bit aggiuntivi, diventando quindi 1111111111010110. Questo funziona perchè \(n < 2^{b-1}\), e calcolando \(2^b - n\) lasciavamo intatto a 1 l'ultimo bit più significativo, ovvero il \(b\)-esimo bit. Quindi, se aumentiamo il numero di bit a \(v>b\), sicuramente calcolando \(-n = 2^v – n\) lasciamo intatti a 1 tutti i bit più significativi fino al \(b\)-esimo.

Da ciò segue che anche l’operazione inversa, ovvero la coercion, è ancora più semplice: basta tagliare via i bit più significativi. Se il valore in questione è rappresentabile correttamente anche in un minore numero di bit, i bit più significativi tagliati via saranno tutti a 1 (se il valore è negativo) o tutti a zero (se è positivo), e corrispondono a quelli che verrebbero aggiunti nella promozione. Altrimenti, il numero è troppo grande in valore assoluto per essere rappresentato e il risultato viene ovviamente troncato male.

Occupiamo su per giù, due bit o poco più…

Se io fossi il complemento a due, mi offenderei. Tutti sanno che esisto, tutti mi conoscono (come funziono, ovvero la storia di complementare i bit e aggiungere uno), ma nessuno si interessa di chi sono (perchè funziono, e quanto funziono bene rispetto agli altri). Con questo non voglio certo dire che non si sa come funziona. Voglio dire che non lo si insegna. Il complemento a due viene insegnato di solito come uno dei primi argomenti in un corso di elettronica digitale o in un corso di architettura degli elaboratori. Salvo professori particolarmente attenti, viene spiegato come regola caduta dal cielo e non si perdono 10 minuti per riassumere le cose importanti: perchè funziona, e perchè è stato scelto ormai come standard di fatto al posto di altri sistemi. In un corso, che sia esso di informatica o di ingegneria, questo sarebbe un perfetto esempio iniziale di quanto un minimo ragionamento astratto può portare a scelte progettuali vincenti.