Archivio autore: glipari

Tirare i dadi

Qualche giorno fa su un (poco) noto social, il buon Zar poneva una questione apparentemente semplice.

“Ci sono cinque dadi a sei facce recanti (le facce) i seguenti numeri: 0, 0, 1, 2, 3, 4. Si lanciano tutti insieme e si fa la somma dei valori ottenuti. Problema: calcolare le probabilità di uscita dei numeri da 0 a 20.”

Nel post linkato Zar fa la trattazione matematica, e vi consiglio di leggerlo tutto perché merita. Nel “socialino dell’ammmore” abbiamo anche discusso alcune soluzioni al problema tramite programmini in vari linguaggi di programmazione. Io, che nel frattempo mi sono parecchio arrugginito con Haskell, ne ho approfittato per proporre 2 soluzioni con questo elegante linguaggio di programmazione: la prima semplice semplice, la seconda una generalizzazione della prima. Dato che le soluzioni le avevo messe su pastebin e chissà che fine faranno, adesso le riposto qui, così magari viene voglia anche a voi di provare nel vostro linguaggio di programmazione preferito.

Cominciamo con la prima:

module Main where
import System.Environment

main :: IO ()
main = do args <- getArgs          
          putStrLn("Probabilità di " ++
                   (args !! 0) ++ " con 5 dadi : " ++ " = " ++ 
                   show( prob_dadi (read (args!!0)::Integer) 5 ))
          -- putStrLn("Test : " ++ show(test))


prob_faccia :: Integer -> Rational               
prob_faccia 0 = 2/6
prob_faccia 1 = 1/6
prob_faccia 2 = 1/6
prob_faccia 3 = 1/6
prob_faccia 4 = 1/6
prob_faccia n = 0
                
prob_dadi :: Integer -> Integer -> Rational
             
prob_dadi n 0 | n == 0   = 1
              | n > 0    = 0
              | n < 0    = 0
                           
prob_dadi n nd  =  (prob_faccia 0)  *  (prob_dadi n (nd-1)) + 
                   (prob_faccia 1)  *  (prob_dadi (n-1) (nd-1)) +
                   (prob_faccia 2)  *  (prob_dadi (n-2) (nd-1)) +  
                   (prob_faccia 3)  *  (prob_dadi (n-3) (nd-1)) +
                   (prob_faccia 4)  *  (prob_dadi (n-4) (nd-1))


test = (test_loop 20)

test_loop (-1) = 0
test_loop n = (prob_dadi n 5) + test_loop (n-1)

Il programmino prende sulla linea di comando il numero di cui si vuole calcolare la probabilità (tra 5 e 20 ovviamente) e restituisce la probabilità in forma di frazione. La funzione principale è prob_dadi che naturalmente è ricorsiva. Il primo parametro n è il numero di cui si vuole calcolare la probabilità, il secondo è il numero di dadi da lanciare.

Per ottenere n, si lancia un dado e:
– si calcola la probabilità che venga 1, e si moltiplica per la probabilità che i restanti nd-1 dadi ottengano n-1;
– si calcola la probabilità che venga 2, e si moltiplica per la probabilità che i restanti nd-1 dadi ottengano il numero n-2
– ecc.
Tutte queste probabilità si sommano per ottenere la probabilità finale.
Resta da stabilire la fine della ricorsione: la probabilità di ottenere n > 0 con 0 dadi, è sempre 0; la probabilità di ottenere n == 0 con 0 dadi è pari a 1.

E’ chiaro? Spero di si. Se avete capito questo programmino, potrete agevolmente capire il secondo programmino che generalizza il contenuto delle facce mettendolo in una lista.
Ecco il codice (ATTENZIONE: per mia praticità, e per confondervi un po’ le idee, qui ho scambiato l’ordine dei parametri della prob_dadi! adesso prende prima il numero dei dadi e poi il numero da ottenere):

module Main where
import System.Environment

main :: IO ()
main = do args <- getArgs          
          putStrLn("Probabilità di " ++
                   (args !! 0) ++ " con 5 dadi : " ++ " = " ++ 
                   show( prob_dadi 5 (read (args!!0)::Integer)))
          -- putStrLn("Test : " ++ show(test))

facce :: [Integer]
facce = [0, 0, 1, 2, 3, 4]

prob_faccia :: Rational
prob_faccia = 1/6

prob_partial:: Integer -> Integer -> Integer -> Rational
prob_partial nd n faccia =  
  prob_faccia * (prob_dadi (nd-1) (n-faccia))


prob_dadi :: Integer -> Integer -> Rational             
prob_dadi 0 n | n == 0   = 1
              | n > 0    = 0
              | n < 0    = 0

prob_dadi nd n =
  sum (map (prob_partial nd n) facce)  

test = (test_loop 20)

test_loop (-1) = 0
test_loop n = (prob_dadi 5 n) + test_loop (n-1)

Qui prob_dadi fa una sommatoria (che nel programma precedente era svolta a mano, elemento per elemento) di una lista che risulta dall’applicazione (tramite map) della funzione prob_partial agli elementi della lista facce.

La funzione prob_partial fa la moltiplicazione di prima:
– calcola la probabilità di ottenere una certa faccia, e la moltiplica per la probabilità di ottenere il numero n-faccia con nd-1 dadi.

E adesso a voi! (Voglio la stessa cosa in Lisp, mi raccomando!)

Uno script per sistemare i downloads

Ciao a tutti,

è una vita che non scrivo sui miei blog, oggi ho deciso di ricominciare piano piano, postando qui sopra un scriptino bash che ho scritto da me medesimo per sistemare i file scaricati tramite browser.

Come sapete, Firefox (e anche Chrome) scaricano i file in una cartella ben precisa, per default la cartella “Downloads”. In genere, questo comportamento è molto utile, perché ci evita di perdere tempo ogni volta a selezionare la cartella giusta dove mettere il file. Lo scarichiamo, a volte lo apriamo, guardiamo, e passiamo avanti. Il fatto è che la cartella “Downloads” tende a riempirsi molto presto: non è raro che arrivi a contenere centinaia e centinaia di file dai nomi più assurdi. Per esempio, la mia cartella adesso contiene moltissimi pdf dai nomi tipo tdtp-14-15(2).pdf, oppure 1-s2.0-030439759400202T-main.pdf

Anche se decidessimo di sistemare il file dopo averlo scaricato, andare a guardare le icone con una interfaccia grafica alla scoperta del file appena scaricato è sinceramente piuttosto noioso: come minimo bisogna memorizzare il nome del file e individuarlo tra tanti, e se si tratta di una sequenza alfanumerica come quella di cui sopra non è che sia tanto facile o veloce.

Quindi ho fatto uno script che, lanciato da linea di comando, sposta l’ultimo file scaricato da Downloads alla directory corrente. Per cui, se sto cercando un articolo che mi serve per la mia ricerca:

  • lo scarico
  • lo apro da firefox (con okular o con evince) per leggere l’abstract e vedere se mi interessa
  • se mi interessa, da terminale lancio lo script deplace dalla directory papers, e voilà, il file è archiviato nel punto giusto.

Il vantggio di questo approccio per me è che io ho sempre un terminale aperto, e con autojump mi sposto velocemente tra le directory. Lo script prende anche un opzione -d per cancellare il file da Downloads, e un nome di file opzionale per rinominare il file in qualche cosa di più leggibile.

Ed ecco lo script finalmente.

#!/bin/bash

function show_help {
    echo "deplace [Options] [new filename]"
    echo "    This command will copy the last modified file in ~/Downloads/ into the current directory, optionally renaming it "
    echo "    Options:"
    echo "    -h or -? : show this help"
    echo "    -d deletes the original file"
}

# flag for the -d option, default is to not delete
delete=0

# initialize getopts
OPTIND=1

# process flags
while getopts "h?d" opt; do
    case "$opt" in
        h|\?)
            show_help
            exit 0
            ;;
        d)
            delete=1
            ;;
    esac
done

# move cursor after last processed flag
# what is left in $* is everything else (e.g. file names...)
shift $((OPTIND-1))

# default new name is the same as the current name
new_name=

# is there is an additional argument, set it as the new filename
if [ $# -ge 1 ]
then
    new_name=$1
fi
# Handling filenames containing spaces: 
# Store previous configuration for separation symbol
SAVEIFS=$IFS
# Now separation symbols do not include space
IFS=$(echo -en "\n\b")

# Identify last file modified in directory downloads
file_to_move=~/Downloads/$(ls -1tr ~/Downloads/ | tail -1)
# copy the file
cp $file_to_move ./$new_name
# if delete option has been selected, delete the file
if [ "$delete" -eq 1 ]
then
    rm $file_to_move
    echo $file_to_move" has been moved into ./"$new_name
else
    echo $file_to_move" has been copied into ./"$new_name
fi

# restore previous options
IFS=$SAVEIFS

Non sono un grande esperto di script bash. Se qualcuno ha delle correzioni da proporre, oppure dei suggerimenti per migliorare il codice, non esiti a scriverle nei commenti!

Saluti alla prossima volta (che speriamo non sia fra un anno!)

Linguaggi regolari

Oggi si va un po’ di più sulla teoria. Oh, prima o poi toccava farlo. Qui il link al post precedente.

Linguaggi

Chi di voi conosce Noam Chomsky? Si proprio lui, avete sentito bene: il vecchio anarchico americano, uno dei pochissimi rimasti. Una persona decisamente controcorrente, sempre pronto a dire la sua fuori dal coro, dai tempi in cui si oppose alla guerra in Vietnam, fino alla guerra del golfo e la guerra in Iraq con il suo attivismo pacifista, nonostante l’età. In effetti, non deve essere facile essere come lui in un paese come gli USA.

Ma che c’entra Noam Chomsky con l’informatica e con le espressioni regolari? Moltissimo a dire la verità. Infatti, il vero mestiere di Noam Chomsky è quello del ricercatore nel campo della linguistica, e uno dei padri ispiratori della disciplina della linguistica computazionale, una disciplina al confine tra l’informatica e la linguistica classica.

In particolare, Chomsky è l’inventore del concetto di grammatica generativa e della classificazione dei linguaggi formali. Cosè un linguaggio formale?

Si parte con un alfabeto definito come un insieme di simboli (ad esempio le lettere dell’alfabeto italiano o inglese, oppure il codice ASCII). L’importante è definire appunto l’insieme dei simboli.

Una parola è una sequenza di simboli. Ad esempio, se prendiamo l’alfabeto italiano, sono parole le seguenti abc, aaaa, informatica, parola, ecc. Basta prendere una sequenza di simboli, non importa se abbia o no “senso comune”. La sequenza potrebbe anche essere illimitata, ovvero contenere un numero a priori illimitato di simboli.

A questo punto un linguaggio L è un sottoinsieme delle possibili parole. Ad esempio, potrei definire un linguaggio L1 che contiene le parole “Giuseppe” e “aaa”. Non che un linguaggio così abbia senso, ma è per farvi capire la generalità della definizione. Un altro linguaggio potrebbe essere quello dei codici di una tastiera che permettono l’apertura di una porta. Ovvero, l’esempio visto negli scorsi post. Ad esempio, il linguaggio L2 di una fantomatica porta potrebbe contenere due parole soltanto, 12A45 e 22B48.

Oppure potrei dire che il linguaggio L3 contiene parole che cominciano per il simbolo a e successivamente sono formate da un numero da zero a illimitato di sequenze della coppia ab. Per esempio, aababab è una parola del linguaggio, così come a e aab, mentre la parola aaa non lo è.

Quindi i linguaggi possono contenere un numero finito di parole, oppure infinito. Nel primo caso basta elencarle tutte. Nel secondo caso, devo dare una regola di appartenenza.

Le regole di un linguaggio

Concentriamoci sul secondo caso: vogliamo definire un linguaggio dando delle regole. Possiamo farlo in due modi: generativo, oppure riconoscitivo.

Nel caso generativo, diamo delle regole per generare tutte le parole che appartengono al linguaggio: in pratica, dato l’alfabeto iniziale e le regole, possiamo creare la lista delle parole che compongono il linguaggio. Queste regole si chiamano grammatica. Si, proprio come la vostra vecchia grammatica di italiano che portavate a scuola tutti i giorni quando eravate dei pischelli. Naturalmente, in questo contesto, grammatica significa in realtà algoritmo o procedura per generare un elenco di parole.

Nel caso riconoscitivo, vogliamo risolvere in problema leggermente diverso: data una parola, vogliamo sapere se questa fa parte di un linguaggio. Naturalmente, ogni linguaggio avrà le sue regole. Salta fuori che un cosa come gli automi che abbiamo visto negli scorsi post sarebbero adatti ad implementare dei riconoscitori.

I due metodi sono uno il duale dell’altro: in particolare, una strategia per riconoscere se una data parola w appartiene o no al linguaggio potrebbe essere la seguente:

  • generare la lista di tutte le parole del linguaggio che hanno la stessa lunghezza di w;
  • vedere se w è presente nella lista.

Viceversa, se vogliamo generare tutte le parole di un linguaggio, si potrebbe:

  • generare tutte le possibili parole di lunghezza 1, 2, 3, … n,
  • e vedere quali di queste sono riconosciute dal riconoscitore.

E quindi, grammatica o riconoscitore, per noi pari sono. Più o meno.

Potenza espressiva

Ma non tutti i linguaggi sono ugualmente “facili”. In particolare, certi linguaggi sono più “semplici” e altri sono più difficili. Chomsky classificò i linguaggi in varie categorie, a seconda del tipo di algoritmo per generare/riconoscere il linguaggio. Ecco la tabella dal più “semplice” al più “complesso”.

Tipo Linguaggio Tipo di Automa
3 Linguaggi regolari Automi a stati finiti
2 Linguaggi liberi dal contesto Automi a pila
1 Linguaggi dipendenti dal contesto Automi lineari
0 Ricorsivo Decisore / Macchina di Turing

Avete visto cosa c’è in alto a destra? I nostri amici automi a stati finiti! Si, gli automi sono in grado di riconoscere la categoria di linguaggi più semplice che c’è. Invece nella casella in basso a destra c’è la famosa Macchina di Turing, la macchina calcolatrice più espressiva di tutte. Quindi, i linguaggi ricorsivi sono i più “difficili” di tutti.

Esempio

A questo punto bisogna fare un esempio. Prendiamo il linguaggio che avevo definito prima: una parola appartiene al linguaggio se c’è una a come primo simbolo seguita da una sequenza di un numero qualsiasi (anche 0) di coppie ab. Ecco l’automa che riconosce le parole di questo linguaggio:

automa-linguaggio.png

Figure 1: Automa a stati finiti per il linguaggio dell’esempio

Nel disegnare la figura, ho fatto l’assunzione che se uno stato riceve un simbolo per cui non ha un arco in uscita, allora si blocca con errore. Per esempio, se mentre siamo in S0 arriva una b, allora l’automa si blocca con un errore. In realtà avrei dovuto mettere un stato apposito, per esempio ERR in cui si finisce quando arriva un simbolo inaspettato, e aggiungere degli archi da ciascuno stato allo stato di errore. Ma il disegno si complica inutilmente, e allora molto spesso si utilizza questa scorciatoia.

L’automa in figura definisce il linguaggio in maniera esatta. Cioè, invece di scrivere la definizione del linguaggio a parole, descrivo l’automa, che sicuramente è più preciso di qualunque descrizione in italiano. In effetti, l’automa è un modo procedurale di definire il linguaggio.

E se volessi utilizzare una grammatica? Si scrive più o meno così:

\displaystyle  a(ab)^n

dove l’elevazione a n indica la ripetizione per un numero intero di volte dei simboli contenuti tra le parentesi tonde. Sembra quasi uguale a un’espressione regolare, vero? L’espressione sarebbe:

a(ab)*

dove l’asterisco significa “il precedente pattern può essere ripetuto un numero arbitrario di volte (anche zero volte)”.

Notate che il pattern è illimitato. In altre parole, non abbiamo messo un limite alla lunghezza delle parole del linguaggio. Il nostro linguaggio L contiene dunque un numero infinito di parole! Tuttavia, poiché il pattern con cui queste parole sono generate è molto semplice, altrettanto semplici sono la grammatica e l’automa che lo descrivono.

Quindi, la difficoltà di un linguaggio non ha niente a che vedere con il numero di parole che contiene, ma semmai con la complessità del pattern di riconoscimento. Nell’ultima puntata spiegherò perché un automa a stati finiti non è poi così potente, e cosa non può riconoscere.

Errata Corrige

Nello scorso post ho fatto un errore: nella figura ho messo una freccia da da S3 a S2 con etichetta “2”; in realtà, la freccia doveva essere da S3 a S4, sempre con etichetta “2”. Grazie a Stefano per la segnalazione, è molto gratificante avere lettori attenti che ti trovano i bachi! Grazie ancora.

Macchine a stati finiti – 2

Seconda puntata. Cominciamo risolvendo il problema della scorsa volta. Ricordiamo che i due codici che aprono la porta sono 12A45 e 22B48. Ecco il sistema corretto, dove per semplicità ho tolto tutti gli archi rossi: fate l’assunzione implicita che, ogni volta che premo un tasto sbagliato, il sistema vada automaticamente in S0

soluzione.png

Figure 1: Soluzione corretta del riconoscitore con due codici.

Anche così non è proprio semplicissimo, ma sono evidenti due file orizzontali di stati (anche perché le ho messe apposta così): quella superiore si occupa del primo codice 12A45, mentre quella inferiore si occupa del secondo codice 22B48. Inoltre, se mentre sto facendo il primo codice premo 2, il sistema passa a S2, e se mentre sto facendo il secondo codice premo 1, il sistema passa a S1, per cui ho tutte le frecce incrociate. Si può dimostrare (ma è abbastanza evidente) che questo automa riconosce solo i due codici voluti.

Implementazione

Come si implementano nella pratica questi automi? Non è affatto difficile, una volta che avete fatto il grafo. Se siete degli smanettoni elettronici, potete provare a costruire un semplice circuito digitale che riconosca i due codici. Innanzitutto serve una locazione di memoria per fare in modo di ricordarsi in quale stato siamo arrivati. Serve memorizzare 10 stati, per cui basta un registro a 4 bit. Poi naturalmente un tastierino alfanumerico che vi dia in output una sequenza di bit diversa per ogni tasto.

Poi si costruisce una bella tabella, con tante righe quanti sono gli stati, e con tante colonne quanti sono i possibili simboli in input. Nelle cella alla posizione (s,x) ci si mette lo stato in cui si finisce quando siamo nello stato s e riceviamo in input il simbolo x Per esempio, una cosa così:

Stato ‘1’ ‘2’ ‘4’ ‘5’ ‘8’ ‘A’ ‘B’ ‘*’
S0 S1 S2 S0 S0 S0 S0 S0 S0
S1 S1 S3 S0 S0 S0 S0 S0 S0
S2 S1 S4 S0 S0 S0 S0 S0 S0
S3 S1 S4 S0 S0 S0 S5 S0 S0
S4 S1 S4 S0 S0 S0 S0 S6 S0
               

Non avevo molta voglia di scriverla tutta a mano, ma naturalmente queste tabelle possono essere generate automaticamente. A questo punto avete sulle righe la rappresentazione in bit dello stato, e sulle colonne la rappresentazione in bit dell’input, e produrrete in output la rappresentazione in bit del prossimo stato. Questo è un semplice circuito combinatorio, e un elettronico dilettante dovrebbe sapere come sintetizzarlo, vero?

E quindi basta, abbiamo finito. E se vogliamo riprogrammarlo periodicamente con nuovi codici? Potete usare un Programmable Logic Device, ad esempio.

Avete la mano porcina per i lavori manuali, come il sottoscritto, e volete smanettare come un vero informatico che non si abbassa a toccare nient’altro che la tastiera di un PC? Potete implementare la stessa cosa in un qualunque linguaggio di programmazione. Lo stato viene memorizzato in una variabile, la tabella con uno switch-case oppure con una sequenza di if-then-else, oppure ancora con un array-bidimensionale. Non starò qui a spiegare per filo e per segno come fare, i nostri affezionati lettori di Ok, Panico sanno già tutto, vero?

Conclusioni parziali

Ma le espressioni regolari dove sono? La scorsa volta avevamo detto che avremmo parlato di RE, e fin qui abbiamo visto automi, macchine, latch e circuiti combinatori. Dove diavolo sono le RE?

In realtà le RE risolvono esattamente questo problema: come riconoscere una sequenza di caratteri in un testo (ed eventualmente fare delle sostituzioni). Quindi, i più sgamati di voi avranno probabilmente capito che gli automi e le RE sono collegati. Ma come?

La risposta alla prossima puntata!

Macchine a stati finiti

Recentemente ci sono stati alcuni post su Ok, Panico che riguardavano le espressioni regolari, (RE). Mi sono detto che forse è il caso di fare una serie di post un pochino teorici sull’argomento, se ve la sentite. Ve la sentite? Ma sì, dai. Cominciamo da lontano, (anche se non troppo).

Un esempio di automa

Una macchina a stati finiti (o automa a stati finiti) è un aggeggio matematico-informatico che può aiutarci a descrivere alcuni semplici sistemi automatici. Per spiegarvi in pratica di cosa si tratta, parto come al solito da un esempio pratico: il sistema d’accesso al mio palazzo.

Il portone del palazzo dove abito, come quasi tutti i palazzi di Parigi, si apre quando si inserisce il codice alfanumerico corretto su una tastiera. La tastiera permette l’inserimento delle cifre 0-9, e delle lettere A e B. Un tipico codice contiene 5 caratteri, per esempio 12A45. Se si inserisce il codice corretto la porta si apre, altrimenti niente. Se sbagliate qualche cifra potete sempre ripartire da capo. Ad esempio, se sbagliate e premete 23 come prime due cifre, potere ricominciare da capo immediatamente, e quindi la porta si aprirà anche con la sequenza 2312A45, l’importante è che gli ultimi 5 caratteri siano corretti.

Come è implementato il circuito elettronico che regola l’apertura della porta? Esso riceve i caratteri, uno alla volta, e appena ha riconosciuto la sequenza giusta apre la porta. Quindi, il circuito deve ricordarsi la storia passata. Vediamo come può farlo efficacemente facendo un piccolo diagramma “a palle”:

macchina.png

Figure 1: Macchina a stati per l’apertura del portone con un codice

Ogni “palla” rappresenta uno stato del sistema. Inizialmente il sistema si trova nello stato S0, e aspetta i nostri comandi. Ogni comando che arriva può causare una “transizione di stato” che viene rappresentata da una freccia (o più precisamente, un arco orientato). Ho indicato in nero le transizioni “buone” per noi, mentre ho indicato in rosso le transizioni che ci fanno “tornare indietro” perché abbiamo sbagliato il codice. Per aprire la porta a partire dallo stato S0 dobbiamo fare uno dei percorsi con gli archi “neri”. Inoltre, ho colorato di verde la “palla” corrispondente allo stato che vogliamo raggiungere.

Ad esempio, se il sistema è nello stato S0 e premiamo il tasto ‘1’, il sistema si porta nello stato S1, altrimenti resta nello stato S0. Se il sistema si trova nello stato S3, abbiamo fatto la metà dello sforzo: se premiamo ancora il tasto ‘4’ andiamo avanti, se facciamo un errore torniamo allo stato S0, e infine se premiamo ‘1’ andiamo direttamente nello stato S1 perché questo potrebbe essere l’inizio di una nuova sequenza corretta.

Sembra complicato? In realtà la rappresentazione grafica è un pochino complicata da disegnare e da leggere per chi non è pratico (mentre è o dovrebbe essere pane per i denti di ogni informatico). La figura che vedete si chiama “grafo orientato”, e come potete immaginare c’è un’intera branca della matematica che se ne occupa.

Dato che abbiamo formalizzato il problema, potremmo fare delle analisi. Per esempio, è possibile dimostrare formalmente che:

  • da qualunque stato parto tra S0, S1, S2, S3, S4, digitando il codice giusto arrivo in S5;
  • che non c’è nessun altro modo per raggiungere S5.

In altre parole, possiamo dimostrare che il sistema funziona come volevamo: basta enumerare tutti i possibili casi.

Macchine a stati finiti

Le macchine a stati finiti sono utilizzate in moltissimi campi dell’ingegneria, dall’elettronica all’informatica, e sono state studiate per molti anni. Sono infatti alla base della teoria dell’informazione.

Si chiamano macchine o automi perché all’inizio furono applicate alla meccanica. D’altronde, i primi computer erano meccanici (la pascalina, la macchina analitica di Babbage…), e in molti casi servivano ad automatizzare dei compiti ripetitivi, da cui il nome di automi (in inglese si usa la parola latina automaton al singolare, e automata al plurale). Sono “a stati finiti” perché il numero di stati (le palle nel disegno) sono in numero finito.

Quest’ultima cosa è importante. Il fatto che gli stati siano finiti ci permette di controllare tutti i possibili percorsi nel grafo, ma ci dice anche che queste macchine non sono poi così tanto potenti … ma ne riparleremo più avanti.

La macchina che vi ho presentato è un riconoscitore, perché il suo scopo è di riconoscere una sequenza di input. Le macchine a stati finiti possono essere usati anche per scopi di controllo: si può complicare la notazione permettendo la possibilità di dare dei “comandi”. Ad esempio una macchina a stati finiti può essere utilizzata per leggere dei valori di temperatura e dei valori orari, e comandare l’accensione o lo spegnimento di una caldaia. In quel caso si parla di sistema ibrido ed è l’argomento di cui mi sto occupando recentemente nelle mie ricerche.

Macchine a stati finiti possono essere utilizzate per implementare il sistema di navigazione dei menu del vostro televisori; e ancora, Emacs, il mio editor preferito, usa gli automi a stati finiti per riconoscere sequenze di pressione dei tasti per comandi complicati; e lo stesso fa l’editor Vim. Insomma, dovunque ci sia uno “stato” in base al quale bisogna fare cose diverse, si possono utilizzare gli automi.

In questa mini-serie di post, noi ci focalizzeremo solo sulle macchine riconoscitrici: lo scopo è riconoscere se una sequenza in input è corretta. Se lo è, l’automa termina su uno stato di “accettazione” (nell’esempio in figura, lo stato S5 colorato in verde). Se la sequenza non è corretta, l’automa finisce su uno stato “non accettante” e “rifiuta” la sequenza.

Un esercizio

Per concludere questo primo post facciamo un esercizio. Supponiamo che i codici validi per aprire la porta siano 2: oltre a 12A45 c’è anche 22B48. Come facciamo a definire un unico automa che si occupi di aprire la porta in uno (e uno solo) dei due casi?

Proviamo subito.

seconda.png

Figure 2: Questa macchina non funziona

Senza stare a pensarci su, ho semplicemente aggiunto sugli archi le etichette del secondo codice.

Secondo voi, funziona bene questo secondo automa?

La risposta è niente affatto! Non posso semplicemente aggiungere le etichette sugli archi in questa maniera brutale, perché così facendo ho fatto un errore: all’uscita di S1 ci sono due archi che hanno l’etichetta ‘2’. Se il sistema è in S1 e viene premuto il tasto ‘2’ che succede? Si ricomincia ritorna in S1 oppure si va a S2?

Inoltre, anche supponendo di risolvere il problema togliendo l’etichetta ‘2’ dall’arco S1 -> S2, la porta si apre con molti più codici di prima! Ad esempio, il codice 12B48 apre la porta, e non dovrebbe.

Insomma, è tutto sbagliato. Volete pensare un po’ a risolvere il problema da soli? La prossima puntata vi riporto la soluzione e si continua la strada verso le espressioni regolari.

Il conto torna

Alla TV francese danno un programma TV che si intitola Des chiffres et des lettres in cui i concorrenti si sfidano a risolvere sia giochi di parole che di aritmetica. Uno dei giochini si intitola Le compte est bon: vengono dati alcuni numeri, e un numero obiettivo, e lo scopo è di ottenere l’obiettivo (o avvicinarcisi il più possibile) applicando le quattro operazioni aritmetiche alla serie di iniziale numeri.

Per capire di cosa si tratta, facciamo subito un piccolo esempio: dati i numeri 5, 100, 6, 3, 10 e 1, bisogna cercare di ottenere il numero 635 utilizzando soltanto le quattro operazioni +, -, * e /.

Una possibile sequenza che porta alla soluzione è:

5+100 = 105; 6*105 = 630; 3-1 = 2; 10/2 = 5; 630+5 = 635;

Come vedete, non è poi molto difficile, ma bisogna perderci un attimo di tempo a provare un po’ di combinazioni.

Viene fuori che la maestra di mio figlio, che frequenta la CM2 (quinta elementare) qui in Francia, propone questo tipo di esercizi per allenare i ragazzini a fare i conti. Divertente, no? Non l’avevo mai visto fare in Italia, ma può darsi che mi sbagli, se seguite questo blog e ne sapete di più sugli esercizi che vengono dati in quinta elementare in Italia, scrivetelo nei commenti! A questo sito trovare parecchi esercizi simili per tutte le classi delle elementari.

Fatto sta che qualche giorno fa, mio figlio si presenta con questa sequenza: 1, 2, 5, 10, 25, 50, e il numero da ottenere era 668. Non riusciva a trovare la soluzione, e voleva sapere se potevo trovarla io.

Dopo averci pensato qualche secondo, gli ho detto che secondo me non c’era soluzione. “Forse ho sbagliato a copiare qualche numero”, mi risponde lui, “ma mi sembrava di aver ricopiato attentamente dalla lavagna”.

Come sapere se c’è o no soluzione al problema? Beh, da buon ingegnere, ho pensato che il modo migliore era di scrivere un programmino che provasse tutte le combinazioni. Con 5 numeri non dovrebbero essere tantissime. Ovviamente, essendo un problema semplice, il modo veloce di risolverlo era usare il Python, il mio lignuaggio di fast-prototyping preferito ormai.

Volete provarci da soli? Allora non guardate il programma seguente.

import copy
import argparse

numeri = [5, 100, 6, 3, 10, 1]
soluzione = 635

def elimina(i, lista):
    l = []
    l = copy.copy(lista[:i])
    l = l + copy.copy(lista[(i+1):])
    return l


def operazione(lista, sol, ops, ris, operazione, a, b):
    l3 = copy.copy(lista)
    l3.append(ris)
    op = ops + str(a) + operazione + str(b) + ' = ' + str(ris) + '; '
    calcola(l3, sol, op)


def calcola(lista, sol, ops):
    if len(lista) == 1:
        if lista[0] == sol:
            print "TROVATO! ", ops
    else:
        n = lista[0]
        l = elimina(0, lista)
        for i, x in enumerate(l):
            l2 = elimina(i, l)

            n1 = n + x
            operazione(l2, sol, ops, n1, '+', n, x)

            n1 = n - x
            operazione(l2, sol, ops, n1, '-', n, x)

            n1 = x - n
            operazione(l2, sol, ops, n1, '-', x, n)

            n1 = n * x
            operazione(l2, sol, ops, n1, '*', n, x)

            if x != 0 and n % x == 0:
                n1 = n / x
                operazione(l2, sol, ops, n1, '/', n, x)

            if n != 0 and x % n == 0:
                n1 = x / n
                operazione(l2, sol, ops, n1, '/', x, n)


def main():
    parser = argparse.ArgumentParser(description='Inserisci i numeri')
    parser.add_argument('nums', nargs='+', default=numeri)
    parser.add_argument('--s', default=soluzione)

    args = parser.parse_args()
    num = [int(x) for x in args.nums]
    sol = int(args.s)

    print num, ' ??? ', sol
    calcola(num, sol, "")


if __name__ == "__main__":
    main()

E lanciando il programma si ottengono… ben 2 risultati!

[1, 2, 5, 10, 25, 50]  ???  668
TROVATO!  10-1 = 9; 2+5 = 7; 25+50 = 75; 9*75 = 675; 675-7 = 668; 
TROVATO!  1-25 = -24; 2+5 = 7; 10*50 = 500; -24*7 = -168; 500--168 = 668; 
TROVATO!  25-1 = 24; 2+5 = 7; 10*50 = 500; 24*7 = 168; 500+168 = 668; 

La seconda in realtà coinvolge dei numeri negativi, quindi andrebbe eliminata. E quindi aveva ragione mio figlio e torto io. Mai contare troppo sulle proprie doti matematiche!

Il programma l’ho scritto un po’ di fretta e non è il massimo dello stile, e non sono neanche completamente sicuro che sia corretto. E quindi, per chi volesse esercitarsi, ho tre domande a diverso grado di difficoltà:

  • Sapete modificare il programma per evitare che stampi soluzioni negative?
  • E se voleste memorizzarle tutte le soluzioni in un vettore per riutilizzarle dopo?
  • Infine, sapete dimostrarne la correttezza?

Dimenticavo: ovviamente, un programma analogo è disponibile in linea qui.

Ah, questi francesi!

Un esercizio in Python

A me piace molto il C++, ci lavoro e lo insegno. Ma riconosco che sia un linguaggio “un po’ complicato” (eufemismo). Per tante cose di tutti giorni, serve qualcosa di più semplice. Come sapete, recentemente mi sto appassionando al Python: e siccome la maniera migliore per fissare quello che uno impara è di metterlo per iscritto e provare a spiegarlo agli altri, oggi si parla di Python. Vi presento un piccolo esercizio in Python in cui svilupperemo le nostre abilità con la programmazione funzionale.

Supponiamo di avere un file pieno di numeri interi separati da virgole. Il file è però un pochino disordinato: su una linea ci possono essere un numero variabile di numeri, e tra un numero e l’altro e tra le virgole ci possono essere un numero variabile di spazi. Obiettivo: leggere tutti i numeri e metterli in una lista. Facile facile.

Esempio di file in input:

12 , 25, 
34, -15,    17  , 
100, 24

, 37, 99

Comciamo con il leggere tutto il file:

file = open('dati.txt', 'r')
lines = file.readlines()
all = ""
for x in lines :
    all = all + x

lines è una lista di stringhe, una per ogni linea, e con il ciclo le mettiamo tutte insieme.
Poi le splittiamo e infine le trasformiamo in interi:

nums = all.split(',')
intnum = []
for x in nums : 
    intnum.append(int(x))
print intnum

Insomma, facile. Ma tutti quei cicli for… non si può fare in maniera più compatta? Ovviamente si!
Ecco come. Innanzitutto, eliminiamo il primo ciclo for utilizzando la funzione read() che legge tutto in una stringa.

file = open('dati.txt', 'r')
all = file.read()

La stringa all adesso contiene tutto il file in una sola stringa. Adesso proviamo a fare lo split e a transformare tutto in numeri in un colpo solo:

intnum = map(int, all.split(','))
print intnum

La funzione map() applica la funzione passata come primo argomento, ovvero int(), a tutti gli elementi della lista passata come secondo argomento, ovvero al risultato di all.split(‘,’), e produce dunque una lista di interi.

A questo punto potremmo anche far tutto in una sola linea:

print map(int, open('dati.txt','r').read().split(','))

Alternativamente, invece della map() potete usare la list comprehension:

print [int(x) for x in open('dati.txt','r').read().split(',')]

Voilà, tutto in una linea!

Esercizio per casa: supponete di avere un file di configurazione con delle “proprietà”, ogni proprietà può avere assegnato un valore numerico. Ad esempio:

pippo = 15,
pluto = 25, paperino = 104, 
paperone = 75, qui, quo, qua

Nel file qui quo e qua non hanno alcun valore assegnato, quindi supponiamo che il vaolre di default per loro sia 0.
L’esercizio consiste nel leggere il file e produrre un dizionario {key,value}. L’output del programma sul file precedente dovrebbe essere:

{'pippo': 15, 'paperino': 104, 'pluto': 25, 'qua': 0, 'paperone': 75, 'qui': 0, 'quo': 0}

Cercate di farlo con il codice più breve e compatto possibile!

Buon divertimento! (poi posterò la mia soluzione, e non è affatto detto che la mia sarà la più “compatta”)

PS: nella prima versione di questo post, leggevo il file con readlines() solo per fare una join() successiva. In realtà basta fare read() per leggere l’intero file, e quindi ho editato la seconda parte del post.

Un semplice parser in C++

E’ da tantissimo che non scrivo più su questo amato blog, è ora di ricominciare! E allora, prima della fine dell’anno, faccio un post in cui vi racconto di un progettino a cui ho lavorato nel mio tempo libero (insomma…) nell’ultimo mesetto. Una versione in inglese di questo post la trovate su algoland.

Si tratta di Tiny Parser (TIPA), un parser scritto in C++11, di cui vi propongo una primissima versione (ancora in alpha):

https://github.com/glipari/tipa

Ho progettato questo parser prendendo in prestito alcuni dei concetti della libreria Boost::Spirit. A differenza di Spirit, però, il mio parser è molto più semplice e quasi del tutto template-free. Questo vuol dire che è più facile da usare, ma anche molto meno potente di Spirit.

Alcune cose che non mi sono piaciute di Spirit: prima di tutto la difficoltà nell’apprendere l’uso della libreria. Ogni tanto mi capitava di fare un errore stupido nella dichiarazione di un oggetto: a quel punto il compilatore mi subissave di messaggi di errori incomprensibili (o quasi) dovuti all’uso dei template, e andare a cpiare cosa non andava non era affatto semplice.
A volte il parser che avevo scritto semplicemente non funzionava ma non riuscivo a capire dove avevo sbagliato. Forse nell’uso di uno di quelle macro BOOST_ADAPT? O forse il mio parser non faceva back-tracking in maniera corretta? Boh. E infine non riuscivo a configurare i messaggi di errore come volevo (per non parlare del bug che ho trovato una volta). Per non parlare del tempo che ci voleva a compilare.

Invece, quello che mi piace di Spirit è la possibilità di scrivere le regole del parser quasi come si scrivono le regole EBNF. Volevo quella feature evitando tutta la complessità.

E quindi ho scritto una libreria che fornisce questa particolare feature: per scrivere un parser devi scrivere le regole come se fosse EBNF, ma usando il C++.

Sfortunatamente, estrarre informazioni utili dal testo parsato (che brutta parola in italiano!) è meno automatico che con Spirit. Dovete scrivere esplicitamente il codice di estrazione. Un po’ noioso, lo ammetto, ma per lo meno se fate un errore, il compilatore ve lo riporta in maniera comprensibile! Ed è più facile fare il debugging.

Ecco un esempio della grammatica per una calcolatrice aritmetica (che funziona solo con gli interi):

    // These are the parsing rules
    rule expr, primary, term, 
	op_plus, op_minus, op_mult, op_div, r_int;
    
    // An expression is sequence of terms separated by + or -
    expr = term >> *(op_plus | op_minus);
    op_plus = rule('+') > term;    
    op_minus = rule('-') > term;

    // A term is a sequence of primaries, separated by * or /
    term = primary >> *(op_mult | op_div);
    op_mult = rule('*') > primary;
    op_div = rule('/') > primary;

    // A primary is either an integer or 
    // an expression within parenthesis
    primary = r_int | 
	rule('(') >> expr >> rule(')');

    // An integer is an integer!
    r_int = rule(tk_int);

Tutto qui. Notate che potete definire e unsare una regola (rule) prima di assegnargli un valore. Questo vuol dire che potete facilmente costruire regole ricorsive a volontà! Per esempio: “expr” è definita in termini di “term”, che è definita in termini di “primari” che è definita in termini di … expr!

(Se volete fare una comparazione con l’ultima versione di Spirit X3, guardate qui)

Aspettare, queste sono solo le regole, dobbiamo capire come usarle per fare il parsing di una stringa o di un file. Ecco come fare:

    // preparing the "context" of the parser
    parser_context pc;
    pc.set_stream(str);

    bool f = false;
    try {
	f = expr.parse(pc);
    } catch(parse_exc &e) {
	cout << "Parse exception!" << endl;
    }

In pratica, dovete prerarare un oggetto di tipo “parser_context”, che verrà passato a tutte le regole durante il parsing. Questo oggetto deve essere inizializzato con un oggetto di tipo stream (nel codice qui sopra l’oggetto str). Poi, prendete la regola “radice” (nel nostro caso l’oggetto expr), e chiamate il metodo parse() passandogli il contesto.

Il metodo ritorna semplicemente true (se l’espressione è stata riconosciuta correttamente dal parser) o false. Se viene trovato un errore, e anche possibile lanciare un’eccezione, dipendentemente dal tipo di errore (l’error handling ie ancora in una fase molto preliminare dello sviluppo!).

Sapere se l’espressione è corretta è indubbiamente utile, ma è solo metà del lavoro. La maggior parte delle volte dobbiamo fare qualcosa con l’espressione, per esempio calcolare il risultato, oppure semplifricarla, oppure che so io. Quindi, come possiamo estrarre informazioni utili durante il parsing? Supponiamo di voler costruire l’albero binario che rappresenta l’espressione aritmetica. Prima di tutto, ecco le classi per rappresentare codesto albero:

class tree_node {
public:
    virtual int compute() = 0;
    virtual ~tree_node() {}
};

class op_node : public tree_node {
protected:
    shared_ptr<tree_node> left;
    shared_ptr<tree_node> right;
public:
    void set_left(shared_ptr<tree_node> l) {
	left = l;
    }
    void set_right(shared_ptr<tree_node> r) {
	right = r;
    }
};

class leaf_node : public tree_node {
    int value;
public:
    leaf_node(int v) : value(v) {}
    virtual int compute() { return value; }
};

#define OP_NODE_CLASS(xxx,sym)		 \
    class xxx##_node : public op_node {  \
    public:                              \
      virtual int compute() {            \
	int l = left->compute();         \
	int r = right->compute();        \
	return l sym r;                  \
      }                                  \
    }

OP_NODE_CLASS(plus,+);
OP_NODE_CLASS(minus,-);
OP_NODE_CLASS(mult,*);
OP_NODE_CLASS(div,/);

Una foglia dell’albero è un semplice numero intero. Un nodo non foglia rappresenta un’operazione aritmetica tra il sottoalbero sinistro e quello destro. Per esempio, se un albero ha come nodo “radice” un nodo di tipo “plus_node”, allora per calcolarne il valore bisogna prima calcolare il valore dei sottoalberi sinistro e destro, quindi sommare i due valori. Spero sia chiaro nel codice!

Poi, uso una classe di supporto (helper class) per costruire l’albero in maniera incrementale:

class builder {
    stack< shared_ptr<tree_node> > st;
public:
    void make_leaf(parser_context &pc) {
	auto x = pc.collect_tokens();
        if (x.size() < 1) throw string("Error in collecting integer");
	int v = atoi(x[x.size()-1].second.c_str());
	auto node = make_shared<leaf_node>(v);
	st.push(node);
    } 

    template<class T>
    void make_op(parser_context &pc) {
	auto r = st.top(); st.pop();
	auto l = st.top(); st.pop();
	auto n = make_shared<T>();
	n->set_left(l);
	n->set_right(r);
	st.push(n);
    }
    
    int get_size() { return st.size(); }

    shared_ptr<tree_node> get_tree() {
	return st.top();
    }
};

Questa classe usa internamente uno stack dove memorizza i risultati parziali. Quando il parser trova un intero, chiamiamo il metodo make_leaf() che costruisce un nodo foglia (leaf_node) e lo mette sullo stack. L’intero viene letto dall’oggetto parser_context usando il metodo pc.collect_tokens().
Quando il parser trova un’operazione, il nodo corrispondente viene costruito usando il metodo template make_op(), dove il parametro template T rappresenta il nodo corrispondente all’operazione.

In ultimo, abbiamo bisogno di chiamare questi metodi al momento opportuno. Ecco come fare:

    builder b; 
    using namespace std::placeholders;

    r_int   [std::bind(&builder::make_leaf,           &b, _1)];
    op_plus [std::bind(&builder::make_op<plus_node>,  &b, _1)];
    op_minus[std::bind(&builder::make_op<minus_node>, &b, _1)];
    op_mult [std::bind(&builder::make_op<mult_node>,  &b, _1)];
    op_div  [std::bind(&builder::make_op<div_node>,   &b, _1)];

Non vi preoccupate, non è rocket science!
Prima creo l’oggetto b di tipo builder. Poi dico ad ogni regola quale funzione deve essere chiamata quando la regola viene valutata con successo: se make_leaf() e make_op() fossere semplici funzioni sarebbe molto semplice. Dato che sono metodi di una classe, è un po’ più complicato: devo prima trasformarli in funzioni. Per fare questa trasformazione uso la funzione della libreria standard std::bind(), legando l’oggetto b al metodo. A prima vista può sembrare un po’ difficile, ma vi suggerisco di dare uno sguardo la riferimento per la funzione std::bind function description nel manuale di riferimento.

E questo è tutto. Potete trovare il codice di questo esempio nel repository nel file tipa/example/arithmetic.cpp

Se siete curiosi e volete fare una prova, per favore scaricate il tutto da github e fatemi sapere cosa ne pensate. La licenza è GPLv3, come faccio di solito. Sono disponibile a implementare nuove features se sono ragionevolmente semplici, e ovviamente vi prego di segnalarmi i bug che troverete.

E con questo vi saluto e vi auguro un felice anno nuovo!

Perché JavaScript non va bene per i dispositivi mobili

E’ possibile che un tablet possa sostituire efficacemente un PC?

Qualche tempo fa mi sono imbattuto in questo post che contiene un sacco di informazioni interessanti sui linguaggi di programmazione dinamici e sul perché non siano adatti alla programmazione di applicazioni per dispositivi mobili. Ne consiglio a tutti la lettura. Ma dato che il post è lungo, ne farò qui un sommario aggiungendo i miei commenti.

Il garbage collector

I linguaggi di programmazione possono essere categorizzati in molti modi. Uno dei modi è quello di distinguere i linguaggi managed da quelli unmanaged. I primi utilizzano, tra le altre cose, il meccanismo di garbage collection (o GC) per gestire automaticamente la memoria dinamica utilizzata dai nostri programmi, mentre i secondi lasciano il compito di gestire la memoria essenzialmente al programmatore. Tra i linguaggi managed ci sono per lo più linguaggi dinamici come Python, Ruby, JavaScript, ma anche linguaggi compilati come Java e Haskell. Il tipico linguaggio unmanaged è il C/C++. Oggi, moltissimi linguaggi sono managed, e la ragione sarà più evidente nel proseguimento del post.

La GC è stata inventata da una vecchia conoscenza di questo blog: da John McCarthy, si proprio lui, l’inventore del linguaggio LISP. L’idea è quella di liberare il programmatore dal difficile compito di dover gestire personalmente la memoria dinamica. In un linguaggio non managed, come il C ad esempio, ogni volta che faccio una p = malloc(nbytes) ottengo un puntatore a una nuova zona di memoria della dimensione richiesta che posso usare per memorizzare i miei dati; corrispondentemente, quando quella zona di memoria non mi serve più dovrò fare una free(p) per liberare la memoria e renderla di nuovo disponibile. Se mi scordo di fare la free(), e magari cancello il puntatore, la memoria resterà occupata, almeno fino a quando il programma resterà in esecuzione. Se il programma rimane in esecuzione per lungo tempo, è bene assicurarsi che ad ogni malloc() corrisponda sempre una free(), altrimenti la memoria occupata dal programma potrebbe crescere in maniera incontrollata.

Pensate ad esempio ad un server che accetta richieste di connessione; questo programma eseguirà per un tempo indeterminato, giorni, mesi, anni. Supponiamo che ad ogni richiesta venga allocata della memoria, ma al termine del completamente del servizio questa memoria non viene deallocata. Ad ogni richiesta, le dimensioni della memoria del programma continueranno a crescere mandando prima o poi in crash il sistema. Inoltre, la memoria si riempie di spazzatura, ovvero dati ormai inutili. Un tale tipo di errore viene chiamato memory leak, perché sembra che la memoria “goccioli via” come da un secchio bucato. Nel passato, il numero di errori che avevano a che fare con una cattiva gestione della memoria da parte del programma era piuttosto elevato, per cui si pensò di porre rimedio sottraendo il compito di gestire la memoria al programmatore.

I linguaggi managed permettono al programmatore di allocare memoria per i propri dati; evitano però che il programmatore debba liberare la memoria quando non è più necessaria. In pratica, permettono la malloc(), ma evitano di farci fare la free(). Un algoritmo, chiamato garbage collector periodicamente analizza la memoria del nostro programma per vedere se qualche zona di memoria precedentemente allocata può essere liberata. In pratica, raccoglie la spazzatura per noi. Per far questo, ad ogni zona di memoria viene associato un contatore dei riferimenti (reference counter) che conta quanti puntatori attivi riferiscono quella particolare zona di memoria. Ogni volta che la zona viene riferita da una nuova variabile puntatore, il contatore viene incrementato; ogni volta che un puntatore che riferisce quella zona viene cancellato, il contatore viene decrementato. Quando il contatore raggiunge il valore zero, vuol dire che nessun’altra parte del programma riferisce quella zona, che quindi può essere liberata. Non viene però liberata immediatamente (a causa di una serie di casi particolari, non è sempre così facile accorgersi del fatto che una zona di memoria può essere liberata!). In particolare, il GC esegue periodicamente due fasi: nella prima, chiamata mark, si marcano le zone da liberare; nella seconda, chiamata sweep, le zone marcate vengono effettivamente liberate.

La GC è stata sempre oggetto del contendere tra due diversi modi di vedere la programmazione: da una parte quelli che dicono che la GC è la panacea di tutti i mali; dall’altra quelli che dicono che la GC è inutilmente pesante e sostanzialmente inutile. Chi ha ragione? Il post che ho citato all’inizio ci da un punto di vista secondo me molto chiaro e rilevante.

VM

Per implementare la GC ci vuole una Virtual Machine. In pratica, bisogna essere in grado di tradurre un assegnamento tra puntatori in una operazione più complicata che coinvolge i reference counters. Inoltre, le variabili puntatori assumono uno status tutto particolare e differente dalle variabili int o float, perché il GC deve essere in grado di riconoscerle e seguire la “pista” alla ricerca di zone di memoria da liberare. Naturalmente, una VM significa overhead in più di traduzione. E’ vero che ci sono i Just in Time Compilers, che generano codice macchina a partire dal byte code; è anche vero che la VM si può evitare del tutto, come ad esempio fa Haskell con un run-time corposo. Quello che è importate sottolineare però è che per quanto si possa ottimizzare lo strato di VM o di run-time, resta il fatto che l’algoritmo di GC va implementato, e per quanto si possa fare in maniera efficiente, resta sempre un algoritmo piuttosto pesante.

Problemi con il GC

Io vedo due ordini di problemi con il GC. Il primo è strettamente tecnico: il GC ha bisogno di analizzare la memoria del nostro programma alla ricerca di zone di memoria da poter liberare. Mentre fa questo lavoro, la VM quasi sempre di blocca in attesa che il GC abbia finito. Questo perché il GC “legge” e “modifica” le strutture dati del gestore di memoria, e queste strutture dati sono costantemente utilizzate dalla VM sia per allocare nuova memoria, sia per aggiornare i reference counters. Non è sempre possibile permettere che il GC vada in parallelo con il resto del programma, per cui potrebbe accadere che la vostra applicazione abbia un piccolo “freeze” (cioè si blocchi completamente) per un po’ di tempo a causa del GC.

Quanto dura questo “freeze” dipende da un sacco di fattori, il più importante dei quali è l’uso che il programma fa della memoria. Se il programma alloca e libera continuamente tanti oggetti di piccola dimensione, il GC potrebbe prendere tantissimo tempo per eseguire, e il freze potrebbe durare anche qualche secondo. Un altro problema tecnico è capire quando il GC viene eseguito per liberare la memoria. All’inizio del post ho scritto che il GC viene eseguito periodicamente, ma con quale periodo? beh, dipende anche dall’utilizzo della memoria: se c’è poca memoria libera nel sistema, il GC verrà eseguito più frequentemente, nel tentativo di liberare memoria, e questo incrementerà l’overhead, cioè il numero e la durata dei “freeze”.

In ogni caso, quel che è peggio è che quasi nessun linguaggio managed permette al programmatore di controllare quando e quanto spesso il GC va in esecuzione. Quindi il programmatore ha poco controllo.

E veniamo con questo al secondo ordine di problemi del GC. Dato che la gestione della memoria è completamente demandata al sistema e nascosta al programmatore, il programmatore poco esperto tende a usare tanta memoria, creando e distruggendo oggetti inutilmente. Per esempio, in programmi Java scritti da programmatori poco esperti è comune leggere codice come il seguente:

String s = new String("Questa è una stringa");
String c = s.toUpperCase();

questa linea di codice crea un oggetto di tipo stringa per copia da una costante di tipo stringa. Quindi trasforma tutti i caratteri in maiuscolo.
Quello che il programmatore non sa, o dimentica spesso, è che la classe stringa è immutabile, ovvero non si può modificare un oggetto di classe stringa. Ad esempio, ogni volta che volete rimuovere un carattere da una String Java, viene creata un nuovo oggetto di tipo stringa che contiene tutti i caratteri di quello originale meno quello da rimuovere. Per cui, nella riga sopra ci sono 3 oggetti: la stringa originale, quella puntata da s che non può essere modificata, e quella puntata da c. Quella puntata da s è quindi un inutile duplicato, anzi più che inutile, dannoso, perché prima o poi il GC dovrà occuparsi anche di lui! Un modo efficiente di scrivere sarebbe semplicemente:

String s = "Questa è una stringa";
String c = s.toUpperCase();

In questo caso ci sono solo due oggetti, l’originale e quello puntato da c. Di esempi così se ne potrebbero fare molti. E’ così facile creare nuovi oggetti che il programmatore inesperto lo fa senza quasi accorgersene, incrementando notevolmente il lavoro del GC e quindi la lentezza del programma.

Quello che io considero un problema, però, è anche la forza dei linguaggi managed. Poiché non c’è da occuparsi della gestione della memoria, scrivere programmi funzionanti (anche se non molto efficienti) è più semplice, quindi aumenta la produttività del programmatore medio, si riduce il time-to-market, il costo di sviluppo, ecc. E finché la potenza e la memoria disponibile aumentavano, non c’erano problemi: più memoria avete sul vostro PC, meglio funzioneranno programmi scritti con linguaggi managed.

Come detto efficacemente da Miguel de Icaza,

This is a pretty accurate statement on the difference of the mainstream VMs for managed languages (.NET, Java and Javascript). Designers of managed languages have chosen the path of safety over performance for their designs.

Alcuni numeri

Nel post il buon Drew Crawford riporta alcune statistiche che non conoscevo, prese da questo paper. Riporto qui le frasi più importanti, come fa Drew:

In particular, when garbage collection has five times as much memory as required, its runtime performance matches or slightly exceeds that of explicit memory management. However, garbage collection’s performance degrades substantially when it must use smaller heaps. With three times as much memory, it runs 17% slower on average, and with twice as much memory, it runs 70% slower. Garbage collection also is more susceptible to paging when physical memory is scarce. In such conditions, all of the garbage collectors we examine here suffer order-of-magnitude performance penalties relative to explicit memory management. […]
These graphs show that, for reasonable ranges of available memory (but not enough to hold the entire application), both explicit memory managers substantially outperform all of the garbage collectors. For instance, pseudoJBB running with 63MB of available memory and the Lea allocator completes in 25 seconds. With the same amount of available memory and using GenMS, it takes more than ten times longer to complete (255 seconds). We see similar trends across the benchmark suite. The most pronounced case is 213 javac: at 36MB with the Lea allocator, total execution time is 14 seconds, while with GenMS, total execution time is 211 seconds, over a 15-fold increase.

La conclusione quindi è che per stare sicuri di avere performance decenti con il GC, bisogna avere almeno 3-4 volte la memoria minima strettamente necessaria (cioè quella richiesta da un programma che usa allocazione esplicita della memoria). Su un PC prendetevi almeno 4Gb di RAM (meglio 8Gb) e andate tranquilli. Su un dispositivo mobile però non è così semplice.

Il problema delle webapp

Una webapp è una applicazione web, che di solito usa il cosidetto AJAX, ovvero una combinazione di programmi client e server, per fornire funzionalità dinamiche complesse. Per quanto riguarda la parte client, si usa JavaScript (o più propriamente ECMAScript), un linguaggio ormai popolarissimo proprio in ambito web. Si tratta di un linguaggio dinamico, managed, che usa il browser come VM. E naturalmente, usa un GC per gestire la memoria. Essendo un linguaggio vero e proprio, è possibile costruire applicazioni anche molto complesse, che però eseguiranno nel vostro browser.

Una web app particolarmente complicata, ad esempio, è Google Docs, che cerca di replicare un subset delle funzionalità di una suite office sul browser. Qualche anno fa, quando Google Docs fu proposto, ci fu una certa euforia fra i primi utilizzatori e fra gli stessi sviluppatori: era convinzione diffusa che si potesse interamente sostituire una suite come Microsoft Office con qualcosa come Google Docs basata interamente sul web. Se usate Google Docs sul vostro PC, e se questo è abbastanza carrozzato, non ci sono grandi problemi: non è velocissimo, ma è ancora usabile. Se invece qualcuno tentasse di usare Google Docs sul suo Tablet o sul cellulare, beh, i tempi di risposta andrebbero a farsi benedire. Ecco cosa dice personale di Google a proposito:

Complex web apps–the kind that Google specializes in–are struggling against the platform and working with a language that cannot be tooled and has inherent performance problems.

A dire la verità, anche web app molto più semplici soffrono notevolmente: per esempio provate ad accedere alla pagina di Dropbox tramite browser su tablet: dovrete attendere diversi secondi dopo ogni click. In effetti, molto meglio scaricarsi l’app di Dropbox e tentare di fare le proprie operazioni da lì (ma anche quella non è un fulmine).

Il problema è duplice. Il primo problema è di lentezza del processore. Una cosa è avere un bell’Intel i7 sul proprio desktop o portatile, una cosa completamente diversa è di avere un ARM progettato e realizzato con il risparmio energetico in mente. Inoltre, JavaScript è interpretato (o JIT-compilato), e le performance sono nettamente inferiori per questo motivo; Drew calcola che un programma JavaScript è da 5 a 10 volte più lento su un dispositivo mobile rispetto allo stesso programma su PC. Quello che richiede un secondo sul PC può richiedere 10 secondi sul mobile. Leggetevi attentamente la prima parte del post per una lunga analisi delle differenze di velocità.

A questo aggiungete il fatto che JavaScript usa il GC, e che la memoria di un dispositivo mobile è severamente limitata e avete il quadro completo della situazione.

Cosa succederà ora?

Eh, ad avere la palla di cristallo.

Ovviamente, credo non sia possibile continuare sulla strada di sviluppare Webapp sempre più complesse con l’idea che possano completamente sostituire programmi sviluppati nativimente per la piattaforma hardware. I programmi .exe, insomma, non spariranno tanto presto, anzi.

Per quanto riguarda Android, la strada scelta da Google di basarsi su Java è sembrata essere vincente all’inizio, perché ha permesso di sviluppare una grande quantità di app in breve tempo grazie alla maggiore produttività e sicurezza di un linguaggio managed come Java. Sul lungo termine però, il GC sta ponendo più problemi che soluzioni perché, come descrive Drew, i programmatori si vedono costretti ad aggirare il GC con trucchi e trucchetti per evitare la degradazione delle performance.

Si tornerà ad utilizzare il C++ anche sui dispositivi mobili? Credo piuttosto che l’hardware arriverà in soccorso del software ancora una volta… ma chi può saperlo?

Copiare gli oggetti in C++: parte seconda

Seconda puntata della mini-serie (qui la prima puntata). Oggi vediamo le funzioni virtuali.

Funzioni Virtuali

La scorsa volta ho anticipato uno dei meccanismi di base della programmazione OO: l’ereditarietà tra le classi (ovvero i tipi di dati). Il programmatore può definire nuovi tipi di dati utilizzando il meccanismo delle classi; e può mettere le classi in relazione di ereditarietà fra loro.

Supponiamo di aver fatto un programma con due classi, la classe Base e la classe Derivata:

class Base {
public:
  void print() {
     cout << "Ciao, sono di tipo Base" << endl;
  }
};

class Derivata : public Base {
public:
  void function() {
     cout << "Ciao, è stata chiamata la funzione()" << endl;
  }
};

La classe Derivata “eredita” le caratteristiche della classe base, e in particolare tutte le sue funzioni.
Nella programmazione ad oggetti una funzione all’interno di una classe viene chiamata anche “metodo”, quindi da adesso cercherò di utilizzare questo termine. La classe derivata ha dunque 2 metodi: print() e function(). Ecco che li uso:

...
int main() {
  Derivata x;
  x.print();
  x.function();
}

Il programma produce il seguente output:

Ciao, sono di tipo Base
Ciao, è stata chiamata la funzione()

In pratica, l’oggetto x della classe Derivata ha “ereditato” il metodo print() dalla classe Base, e quando lo invoco, viene eseguito il codice del metodo Base::print() (ovvero della funzione print() che sta dentro la classe Base).

C’è qualcosa che non va, vero? Vorremmo che stampasse la cosa corretta, ovvero “Ciao, sono di tipo Derivata“. Per fare questo, possiamo ridefinire il metodo print() dentro la classe Derivata:

#include <iostream>
using namespace std;
class Base {
public:
  void print() {
     cout << "Ciao, sono di tipo Base" << endl;
  }
};

class Derivata : public Base {
public:
  void print() {
     cout << "Ciao, sono di tipo Derivata" << endl;
  }
  void function() {
     cout << "Ciao, è stata chiamata la funzione()" << endl;
  }
};

int main() {
  Derivata x;
  x.print();
  x.function();
}

Adesso ci sono due print(): la prima la indichiamo con Base::print(), ed è il metodo implementato dentro la classe Base; la seconda la chiamiamo Derivata::print(). Quindi, se usiamo il nome “esteso” (cioè includendo anche il nome della classe) vediamo che si tratta di due metodi differenti.

Potete scaricare il file, compilarlo e lanciarlo con

g++ prova.cpp -o prova
./prova

E dovrebbe darvi in output:

Ciao, sono di tipo Derivata
Ciao, è stata chiamata la funzione()

Ora va meglio, no? Però, c’è un però. Siamo sicuri che venga sempre chiamata la funzione giusta? Vediamo cosa succede con l’upcasting.

L’upcasting è la tecnica di utilizzare un oggetto della classe derivata tramite un puntatore o un riferimento a un oggetto della classe padre. Ed ecco l’esempio in due righe:

int g(Base *p)
{
    p->print();
    p->function();
}

int main() {
    Derivata x;
    Base *q = &x;
    g(q);
}

Questo aggeggio non compila! (provare per credere…). Il perché è presto detto: quando scrivete p->function(), il compilatore non ha idea di quale sia l’oggetto a cui p sta puntando. È vero che noi (i programmatori) che abbiamo appena scritto il programma sappiamo che p sta puntando a un oggetto di tipo Derivata. Ma il compilatore non può fare questa assunzione: deve tener conto che l’oggetto puntato da p potrebbe essere benissimo di tipo Base! Per esempio, magari la funzione g() viene chiamata da qualche altra parte nel programma (non è questo il caso, ma il compilatore non può fare di queste assunzioni). E d’altronde, se volevamo specificare che p dovesse in ogni caso puntare ad un oggetto di classe Derivata, potevamo specificare “Derivata” come tipo del puntatore p! Invece abbiamo scritto “Base *p”, e il compilatore non può fare altro che arrendersi, e utilizzare l’assunzione minima: p punta ad un oggetto di tipo Base o a un tipo derivato (ma non si sa quale). E poiché il metodo function() non è presente nella classe Base, il compilatore da errore.

Eliminiamo dunque la chiamata a function() per il momento, ed ecco il codice completo che potete scaricare ed eseguire.

#include <iostream>
using namespace std;
class Base {
public:
  void print() {
     cout << "Ciao, sono di tipo Base" << endl;
  }
};

class Derivata : public Base {
public:
  void print() {
     cout << "Ciao, sono di tipo Derivata" << endl;
  }
  void function() {
     cout << "Ciao, è stata chiamata la funzione()" << endl;
  }
};
int g(Base *p)
{
    p->print();
}

int main() {
    Derivata x;
    Base *q = &x;
    g(q);
    x.function();
}

E questa vi stampa:

Ciao, sono di tipo Base
Ciao, è stata chiamata la funzione()

Di nuovo? (che palle questo C++!).
Beh, si di nuovo, e d’altronde, che vi aspettavate? Se p è di tipo “puntatore a Base”, chiamarà il metodo Base::print(), anche se l’oggetto è di tipo Derivata. La regola è:

Se si chiamano metodi di oggetti tramite puntatori, il metodo effettivamente chiamato dipende dal tipo del puntatore, e non dal tipo dell’oggetto.

La stessa regola vale anche per i riferimenti. Ecco l’esempio di prima usando un riferimento invece del puntatore:

int g(Base &r)
{
    r.print();
}

int main() {
    Derivata x;
    g(x);
    x.function();
}

E questa vi stampa ancora:

Ciao, sono di tipo Base
Ciao, è stata chiamata la funzione()

E se invece io volessi chiamare il metodo dipendentemente dal tipo dell’oggetto? Posso farlo?
Non è difficile, basta specificare “virtual” davanti la dichiarazione del metodo. Ecco il programma modificato.

#include <iostream>
using namespace std;
class Base {
public:
  virtual void print() {
     cout << "Ciao, sono di tipo Base" << endl;
  }
};

class Derivata : public Base {
public:
  virtual void print() {
     cout << "Ciao, sono di tipo Derivata" << endl;
  }
  void function() {
     cout << "Ciao, è stata chiamata la funzione()" << endl;
  }
};
int g(Base &r)
{
    r.print();
}

int main() {
    Derivata x;
    g(x);
    x.function();
}

Se compilate ed eseguite quest’ultimo, vi stamperà a video:

Ciao, sono di tipo Derivata
Ciao, è stata chiamata la funzione()

Che è successo? La regola completa è:

Se si chiamano metodi di oggetti tramite puntatori:

  1. se il metodo è dichiarato “virtual” nella classe base, il metodo effettivamente chiamato dipende dal tipo dell’oggetto puntato e non dal tipo del puntatore;
  2. se il metodo è dichiarato normalmente in tutte le classi della gerarchia, il metodo chiamato dipende dal tipo del puntatore, e non dal tipo dell’oggetto puntato.

Il primo meccanismo di chiamata dei metodi delle classi si chiama dynamic binding, mentre il secondo si chiama static binding. Come fa il compilatore a sapere quale metodo chiamare nel primo caso? abbiamo detto che non sa quale sia il vero tipo dell’oggetto puntato! Il compilatore usa delle tabelle chiamate “virtual tables” (e completamente nascoste all’utente) di puntatori a funzione: ogni oggetto possiede al suo interno, oltre ai suoi dati privati, anche questa tabella, riempita con gli indirizzi giusti delle funzioni da chiamare. La chiamata di un metodo tramite puntatore implica quindi un “salto” utilizzando l’indirizzo contenuto dentro la corrispondente riga della tabella.

Nel nostro esempio, la tabella avrà una sola riga (perché c’è una sola funzione virtuale). UN oggetto di tipo Base metterà nella riga della virtual table l’indirizzo della funzione Base::print(); un oggetto di tipo Derivata metterà nella tabella l’indirizzo della funzione Derivata::print(). La chiamata p.print() viene tradotta in due passi: 1) prendo l’indirizzo dalla tabella 2) ci salto dentro.

Confronti

Dato che ci sono questi due passi (invece di uno solo come nelle chiamate normali), alcuni si ostinano a dire che il C++ sia “inefficiente” rispetto al C. A me in realtà sembra che l’impatto di tale meccanismo sia trascurabile sulle nuove architetture, e assolutamente trascurabile comparato ai vantaggi che si ottengono dal punto di vista della pulizia del codice!

Altri linguaggi OO non hanno questa distinzione tra metodi virtuali e non. Per esempio in Java, tutti i metodi sono automaticamente virtuali, e non c’è modo di implementare lo static binding: non esiste neanche la parole chiave virtual! Stessa cosa con il Python. Meglio o peggio? Sicuramente più semplici da studiare e imparare: meno flessibili e controllabili, però. Il C++ si è fatto da sempre un punto d’onore nell’essere estremamente controllabile dal programmatore, che può fare il fine tuning dei meccanismi di base del linguaggio.

Disegnare le forme

Torniamo al nostro esempio delle forme, che abbiamo introdotto la scorsa puntata. Come abbiamo detto, possiamo creare forme di tipo diverso, tutte derivate da Shape. Possiamo anche raggrupparle in un vettore di puntatori.
Inoltre, dobbiamo essere in grado di disegnarle tutte in una volta. Per cui, converrebbe avere un bel ciclo for sul contenuto del vettore per chiamare la funzione draw() su ognuna di esse.

int main() {
  Shape * shapes[3];

  shapes[0] = new Circle(1,1,4);
  shapes[1] = new Rect(2,2,5,6);
  shapes[2] = new Triangle(3,3,7,10);

  for (int i=0; i<3; ++i) shapes[i]->draw();
  ...
}

Dove draw() è un metodo virtuale della classe Shape. In questo modo, ognuna delle forme potrà ridefinire la funzione draw() nella maniera più opportuna, e il metodo corretto verrà chiamato secondo il meccanismo del dynamic binding descritto precedentemente.
Ecco degli snapshot di codice. Innanzitutto la classe Shape:

class Shape {
 protected:
  int xx,yy;
 public:
  Shape(int x, int y);
  void move(int x, int y);

  virtual void draw() = 0;
  virtual void resize(int scale) = 0;
  virtual void rotate(int degree) = 0;
};

Abbiamo una funzione move() specifica della classe Shape; e tre metodi virtuali che saranno ridefiniti nelle classi derivate. La scrittura ” = 0″ dopo la dichiarazione del metodo significa che non intendiamo fornire una implementazione per questi metodi nella classe Shape. In altre parole, questi metodi sono virtuali puri. Non si possono istanziare oggetti di una classe che ha metodi virtuali puri, quindi non possiamo creare oggetti di tipo Shape, perché altrimenti il compilatore non saprebbe che funzione chiamare quando uno scrive obj.draw(). Va bene, nel nostro caso non esistono “forme astratte” ma solo “forme concrete” come triangoli, cerchi, ecc., e quindi impediamo che si possano creare oggetti di tipo Shape.

Adesso vediamo una classe derivata, per esempio la Circle:

class Circle : public Shape {
  int rr;
 public:
  Circle(int x, int y, int r);
  virtual void draw();
  virtual void resize(int scale);
  virtual void rotate(int degree);
};

Diciamo che Circle deriva da Shape, e definisce i tre metodi virtuali. L’implementazione la forniamo un un file a parte:

Circle::Circle(int x, int y, int r) : Shape(x,y), rr(r) {}

void Circle::draw()
{
  cout << "Circle::draw() called" << endl;
  PR(xx); PR(yy); PR(rr); 
}

void Circle::resize(int scale)
{
  cout << "Circle::resize() called" << endl;
  rr *= scale;
  PR(xx); PR(yy); PR(rr); 
}

void Circle::rotate(int degree)
{
  cout << "Circle::rotate() called" << endl;
  PR(xx); PR(yy); PR(rr); 
}

Facciamo lo stesso per Triangle, Rectangle, ecc.

Infine, utilizziamo le forme nel file principale:

#include "circle.hpp"
#include "rect.hpp"
#include "triangle.hpp"

int main()
{
  Shape * shapes[3];

  shapes[0] = new Circle(1,1,4);
  shapes[1] = new Rect(2,2,5,6);
  shapes[2] = new Triangle(3,3,7,10);

  int i;

  for (i=0; i<3; ++i) TRACE(shapes[i]->draw());
  
  for (i=0; i<3; ++i) TRACE(shapes[i]->move(1,1));
  
  for (i=0; i<3; ++i) TRACE(shapes[i]->resize(2));
  
  for (i=0; i<3; ++i) TRACE(shapes[i]->rotate(1));
}

TRACE è una macro che mi sono definito per evitare di ripetere sempre lo stesso codice nell’esempio. Tutto il codice dell’esempio lo trovate qui. Ed ecco le istruzioni per compilare:

  • scaricate, e scompattate con:

    tar xzvf cpp_shapes.tgz

  • entrate nella directory e compilate con:

    make

  • infine eseguite il programma con

    ./shapes

Conclusioni

Ok, più o meno ci siamo. Spero abbiate compreso il meccanismo di base delle funzioni/metodi virtuali. La prossima puntata sarà un intermezzo per spiegare un design pattern piuttosto classico: il Composite. Alla prossima!