Tipi primitivi - Algoritmi e strutture dati

Operatore significativo per i caratteri e codifica

L'unico operatore significativo per i caratteri è stabilire se sono uguali; si può poi fare un ordinamento lessicografico, che è complesso. Tutti questi codici sono definiti da standard internazionali perché è l'unica maniera che abbiamo per interpretare correttamente un testo quando viene trasmesso dall'altra parte dell'oceano.

Alcuni formati esterni di scambio portano scritto direttamente in modo esplicito qual è la codifica utilizzata, come l'XML. La prima riga dell'XML contiene una scritta che dice qual è la codifica dei caratteri utilizzati successivamente. Le pagine HTML, come prima riga, dicono qual è la codifica della pagina; analogamente per le mail, sono un tipo di codifica tuttora fatta con l'US-ASCII.

DateTime e rappresentazione delle date

Le date sono fondamentali: sbagliare una data o malinterpretarla significa perderci o guadagnarci milioni di dollari. Le date sono usate anche come timestamp, quindi per marcare temporalmente eventi. Anche la rappresentazione delle date è standardizzata secondo lo standard ISO 8601.

La rappresentazione interna delle date è però molto complessa. Per esempio, nel corso del tempo sono state utilizzate codifiche molto strane: Unix usa l'epoch, che è una codifica su 32 bit del numero di millisecondi trascorsi dal 1 gennaio 1970. Anche la data del resto è convenzionale; la data che noi usiamo, quella gregoriana, stabilisce convenzionalmente un sistema di numerazione che è pure sbagliato perché l'anno 0 non esiste, si è passati dal -1 al +1.

L'anno 2000 è stato un problema perché si riteneva che molti software usassero una codifica dell'anno su 2 cifre e con il passaggio all'anno 2000 saremmo passati da 1999 al 1900. Questo avrebbe comportato notevoli problemi nei calcoli, soprattutto nei sistemi di controllo. Il problema sembrava inizialmente legato alle banche, che però hanno fatto notare che i mutui a 30 anni li facevano anche nel 1970, quindi sapevano indicare già il 2000.

Molti sistemi di controllo, basati ad esempio su controllori a 8 bit, usavano per risparmiare delle codifiche molto compatte e il rischio era che qualcosa, nel fare il rollover (passaggio da 1999 a 1900), sballasse completamente quello che era il comportamento di quel sistema. Alcuni sistemi che avrebbero provocato disastri sono stati subito corretti.

Rappresentazione standardizzata DateTime

I computer rappresentano DateTime con un formato standardizzato che è sostanzialmente quello aaaammggoreminutisecondi, frazioni di secondo. Le frazioni di secondo sono rappresentate in modo da avere quella precisione, quindi si rappresentano come: 20220311T120000. Avendo la "T" che divide la parte della data da quella dell'ora, noi abbiamo comunque un punto preciso dove separare le due cose.

Problemi di fuso orario

Rimane il problema del fuso orario. Questa è la ragione per cui al mondo, sia i computer che molti dispositivi, come sistemi operativi, rappresentano internamente tutto su base UTC. Viene usato l'UTC perché in questo modo ci si può sincronizzare con macchine in altri posti del pianeta. Se non si fa così, non funziona più ad esempio il sistema di autenticazione alle mail, etc.

Per evitare di fare continui cambiamenti di fuso orario ogni volta che uno si sposta, si tiene come base l'UTC. Anche il protocollo NTP, che sincronizza gli orologi dei computer via rete, li sincronizza sull'UTC.

Rappresentazione esterna e ora locale

Per quanto riguarda la rappresentazione esterna, le persone non lavorano in UTC ma in ora locale. Quindi, quando comprano un dispositivo, devono dire in che fuso orario si trovano. Quando si configura un computer o un cellulare, di solito noi diciamo dove siamo, oppure lo capisce da solo con il GPS e aggancia l'ora locale di quella particolare zona.

Il problema è che in realtà i fusi orari sono convenzioni di natura politica e non fisica. L'Italia, ad esempio, non sta usando l'ora del suo fuso orario; a parte l'ora legale, sta usando l'ora media dell'Europa perché questa è la convenzione che viene usata.

Internamente è un problema perché software diversi o sistemi operativi diversi possono usare codifiche differenti. Unix usa le epoch, Windows usa una rappresentazione in microsecondi a partire dal 1 gennaio 1900 (forse), nei software di Microsoft l'ora è data in secondi in virgola mobile, quindi in secondi e frazioni di secondo, a partire da una certa data. Quindi, quello che noi vediamo se dichiariamo una cella come valore di data è una traduzione di un valore in secondi che viene fatto internamente dalla macchina.

Rappresentazione interna delle ore

Internamente le ore sono rappresentate come numeri in virgola fissa, tipo Unix e Windows, o numeri in virgola mobile come secondi e frazioni di secondo a partire da una certa data. I numeri in virgola fissa hanno una precisione infinita, mentre quelli in virgola mobile no; quando li sommiamo, ovviamente possiamo perdere dei decimali.

Per convenzione ci sono sistemi come le email che utilizzano una rappresentazione dove invece il fuso orario è esplicito, cioè viene indicata un'ora che è l'ora locale e di fianco qual è il fuso orario.

DateTime come tipo nativo

Le DateTime sono un formato che in alcune architetture è rappresentato anche come tipo nativo ma il più delle volte si usa una rappresentazione intera o quella in virgola mobile della macchina. Poi si fa un ragionamento a livello di sistema operativo, sia per ottenere la rappresentazione interna che quella esterna.

Google Takout permette di scaricare i propri dati mediante file JSON; tutti i JSON contengono le date in epoch, quindi dove ci dovrebbe essere una data c'è un numero. Per tradurlo, o utilizziamo librerie che esistono in Python, oppure online, con copia-incolla si capisce che data è.

Rappresentazione cronologica

La rappresentazione esterna aaaa/mm/gg 00:mm:ss è la migliore perché segue un ordine cronologico. Sulle date può essere definito un ordinamento. Sulla rappresentazione interna non ci sono problemi perché, che sia intero o in virgola mobile, l'ordinamento naturale di quella rappresentazione è anche quello cronologico. Se usiamo invece la notazione esterna, se usiamo quella standard, è quella che fa coincidere l'ordinamento lessicografico e quello cronologico; qualunque altra invece no.

Integer e rappresentazione degli interi

Il tipo astratto intero sono gli interi; normalmente si intendono gli interi relativi, non quelli naturali, o se si intendono quelli naturali lo si specifica. Essendo un tipo astratto, può permettersi di essere infinito. Sfortunatamente nessuna macchina è in grado di rappresentare un intero astratto; è necessario rappresentare un sottocampo degli interi, quelli rappresentabili da una macchina.

Se noi abbiamo una architettura a 32 bit e usiamo la rappresentazione a 32 bit di interi, possiamo andare da -2 miliardi a +2 miliardi. Con 64 bit abbiamo ovviamente un range molto più ampio degli interi rappresentabili, ma rimane il fatto che è un sottocampo di un insieme infinito, un sottocampo finito di un insieme infinito.

Abbiamo anche opzioni per rappresentare gli interi in macchine e sono normalmente indicati come signed int e unsigned int. Int non è l'integer, int è un insieme finito, int è il tipo nativo principale, cioè le macchine sono costruite intorno all'int (integer è il tipo astratto e int la sua rappresentazione interna, credo). L'int è un sottocampo e l'aritmetica degli int non è l'aritmetica degli interi.

Se noi facciamo n+1 sugli interi integer andiamo avanti all'infinito senza mai ritornare sullo stesso codice. Se noi facciamo su un int n+1, arrivati alla fine del campo, rimbalziamo all'inizio, quindi è come se il valore più grande rappresentabile in macchina fosse contiguo al valore più piccolo rappresentabile in macchina. Questo non è sempre una cosa desiderabile; l'aritmetica cosiddetta "in modulo" non è necessariamente l'aritmetica migliore per tutte le applicazioni.

Ad esempio, mi aspetto che se aumento la luminosità di un pixel, quando arrivo alla massima luminosità rappresentabile, succede che quel pixel rimane a quella luminosità. Ma se utilizziamo l'aritmetica intera e sommiamo un valore a quel pixel, esso diventa nero; prima diventava il più bianco possibile, quindi il pixel più bianco possibile diventa contiguo a quello più nero possibile. In elaborazione immagini questo può essere un problema.

Dobbiamo continuamente controllare le condizioni di bordo perché se sommiamo, quindi incrementiamo il valore di luminosità di un pixel, rischiamo di farlo diventare più scuro anziché più chiaro come ci aspetteremmo. Questo perché usiamo una codifica intera di una grandezza (luminosità) che non è un intero; segue infatti una matematica diversa, si chiama aritmetica saturata. Vuol dire che arrivati a un certo punto n+1 fa n e non -n.

Ci sono state alcune macchine di Intel e di AMD che hanno implementato l'aritmetica saturata in hardware. Questo perché in quel periodo moltissime operazioni grafiche venivano effettuate dalla CPU, quindi era importante avere un'aritmetica efficiente per poter fare questo tipo di calcoli. Ora invece ci sono coprocessori grafici, cioè schede grafiche, in cui l'aritmetica saturata è data per scontata.

Per quanto sia naturale pensare a un valore di luminosità come a un numero intero, non è ovvio che la luminosità segua la stessa matematica degli interi. Essa ha una sua matematica ed è un tipo astratto a sé, quindi il pixel potrebbe essere definito come un oggetto diverso dall'intero con cui è codificato in macchina. Questo rende l'idea di cosa si intende per codifica: essa è "implemento nel modo migliore possibile una grandezza che ha sue leggi e una sua matematica differente probabilmente da quella degli interi pensati per altri scopi".

Rational e numeri razionali

I numeri razionali traducono l'insieme Q, che è un insieme infinito quanto quello degli interi e anche lui ha problemi di implementazione. I numeri razionali non fanno parte dei tipi nativi di una macchina e hanno applicazioni molto specifiche.