venerdì 8 luglio 2011

Template, Generics e quello che non sempre viene spiegato

Anni fa, in occasione dell'uscita della versione 5 del linguaggio Java (release Tiger) tenni un seminario di dipartimento presso l'Universita' degli Studi di Modena e Reggio Emilia nel quale presentavo tutte le novita' introdotte nel linguaggio (qualche copia del seminario si trova ancora in giro, anche se non garantisco l'autenticita' - chi vuole averne una copia autentica mi contatti).
Una delle novita' di Java 5 erano i "Java Generics". In occasione della presentazione di generics, una eminenza grigia, professorone con anni di esperienza nella OOP e nella programmazione C++, con tono sprezzante e quasi schifato disse:

    hanno copiato i templates C++ e li hanno applicati a Java, nulla di nuovo!

All'epoca ero troppo educato per rispondere male! Con questo articolo pero' voglio mettere in chiaro le differenze fra i templates del C++ e i generics di Java, sottolineando come il pensiero sopra espresso dal professore universitario sia ben lontano dalla realta'.

Si consideri Java Generics, di cosa si tratta? Generics e' un modo per evitare errori grossolani di conversione di tipi facendo fare del lavoro sporco al compilatore. Il compilatore Java e' sempre stato fortemente tipizzato, ma solo per quello che riguarda i tipi primitivi. Nel caso degli oggetti, grazie al principio di sostituzione e alla base comune, Object, ogni oggetto potrebbe essere convertito in uno di un altro tipo passando per un Object. Questo genera una serie di errori di coerenza come il seguente:

   Persona madre = new Persona();
   Persona padre = new Persona();
   Animale cane  = new Animale();
   List famigliari = new LinkedList();
   famigliari.add( madre );
   famigliari.add( padre );
   famigliari.add( cane );    // disastro!

A meno che non si abbia una forte considerazione del proprio cane, esso non andrebbe inserito nella lista dei famigliari (il fatto che il proprio cane debba essere inserito o meno nella lista dei famigliari è un argomento che esula da generics!). Il problema nasce a run-time, quando si cerchera' di manipolare gli oggetti eseguendo dei cast che non saranno verificati.
Generics permette di intercettare tali errori permettendo ad una classe di definire dei "segnaposto" generici il cui tipo verra' specificato al momento della creazione dell'istanza. In altre parole il codice di cui sopra diviene:

   Persona madre = new Persona();
   Persona padre = new Persona();
   Animale cane  = new Animale();
   List famigliari = new LinkedList();
   famigliari.add( madre );
   famigliari.add( padre );
   famigliari.add( cane );    // errore di compilazione

In questo caso il compilatore sa che la lista deve accettare solo istanze valide di Persona, e quindi rifiuta di compilare un programma con un simile errore di logica.
Si noti che il controllo di coerenza avviene solo a compile-time: a run-time l'informazione sui tipi viene totalmente rimossa (type erasure) e tutti i tipi generici sono sostituiti con Object. Questo e' dovuto al fatto che un programma compilato con Generics deve poter eseguire anche su una virtual machine che di generics non sa nulla.

I template C++ sono differenti. Anzitutto i template consentono due funzionalita': generics e meta-programming. La prima funzionalita' e' analoga a quella di Java: si definisce un marcaposto per un tipo e tale tipo verra' specificato al momento della istanziazione (nel codice). Il programma di cui sopra diventa:

  class Persona{};
  class Animale{};

  template< class L >
  class List{
  private:
   L elements[3];

   public:
   inline void add( L newElement ){
          // add code
   }
  };


  // quando occorre usare la lista
  List famigliari
< Persona >;
  famigliari.add( padre );
  famigliari.add( madre );
  famigliari.add( cane ); // errore di compilazione


Il sistema riporta un errore di compilazione simile al seguente:

   error: no matching function for call to ‘List::add(Animale&)’
   note: candidates are: void List::add(L) [with L = Persona]

Potrebbe sembrare che almeno nella implementazione di Generics Java e C++ siano identici, in realta' C++ permette la definizione di classi compilate in modo differente per ogni tipo specificato. Quindi mentre in Java esiste una sola classe List che accetta degli Object controllati dal compilatore, in C++ possono esistere piu' versioni della lista compilata ciascuna con ogni tipo richiesto.

Ma la differenza fra i templates C++ e Java Generics diventa ancora piu' evidente quando si parla di meta-programming. In sostanza i templates C++ possono essere applicati non solo a delle classi, ma anche a dei metodi:

   template
   T findMax (T a, T b) {
     T result;
     result = (a>b)? a : b;
     return (result);
   }

ovviamente per avere senso i template applicati ai metodi dovranno spesso  sfruttare anche l'overloading degli operatori.

Infine il C++ utilizza i template per "capire", a tempo di compilazione, come parametrizzare il codice che genera. E' quindi possibile forzare non solo il tipo di un parametro, ma anche il valore, in modo da costringere il compilatore a compilare il codice con un parametro inserito in modo hard-coded. Si consideri il seguente esempio:

template< int printCount, int spaces >
class Printer{
public:
  static void print(){
    string printString = "Hello World!";
    for( int i = 0; i < printCount; i++ ){

      // stampo gli spazi
      for( int j = 0; j < spaces; j++ )
        cout << " ";

      // stampo la linea e l'andata a capo
      cout << i << " " << printString << endl;
    }
  }


  void croack(){
    string printString = "Hello World!";
    for( int i = 0; i < printCount; i++ ){

      // stampo gli spazi
      for( int j = 0; j < spaces; j++ )
        cout << " ";

      // stampo la linea e l'andata a capo
      cout << i << " " << printString << endl;
    }
  }
};


  int main( int argc, char** argv ){
    cout << "Programma in esecuzione" << endl;
    Printer< 5, 5 >::print();

    Printer< 2 , 8> myPrinter;
    myPrinter.croack();
    cout << "Programma terminato" << endl;
  }

La classe Printer definisce due metodi identici: print (statico) e croack (di istanza). Tali metodi traggono vantaggio del valore di due parametri specificati come template (spaces e printCount) per stampare un certo numero di volte e con un certo numero di spazi di indentazione la famosa stringa "Hello World". La cosa interessante, e che Java non permette, e' che il valore dei parametri viene specificato direttamente al momento della chiamata della funzione statica o della creazione dell'istanza. In Java la classe Printer avrebbe dovuto avere una implementazione simile alla seguente:

public class Printer{
       PRINTCOUNT printCount;
       SPACES      spaces;

       public Printer( PRINTCOUNT count, SPACES spcs ){
                 printCount = count;
          spaces     = spcs;
       }
      
       // metodi analoghi alla classe C++
}

e la si sarebbe dovuta istanziare cosi':

  Printer printer = new Printer(5, 10);

senza la possibilita' di usare il metodo statico direttamente.
Riassumendo quindi Generics e' solo una branchia del template programming, che si estende ben oltre la semplice "specifica variabile dei tipi" e i "controlli di compilazione". L'idea dietro al templating e' si quella di creare classi generiche, ma anche algoritmi generici (come la funzione findMax di cui sopra) e dare la possibilita' al compilatore di capire cosa succedera' a run-time, generando codice specifico per il programma.

In considerazione di questi semplici esempi didattici, e considerata l'affermazione del professore riportata all'inizio, viene da chiedersi se tale professore sia maggiormente incompetente in Java, in C++ o in generale nella OOP. E la cosa che fa ancora piu' amarezza, e' che tale professore continuera' a formare studenti e programmatori che dovranno apprendere da soli cosa realmente siano i templates.


mercoledì 6 luglio 2011

To Dual or not to Dual?

Una delle differenze fra PostgreSQL e Oracle e' nel funzionamento sintattico e semantico dell'istruzione SELECT. Agli utenti Oracle potrebbe risultare strano, ma la clausola FROM di una istruzione SELECT in PostgreSQL e' opzionale:

Command:     SELECT
Description: retrieve rows from a table or view
Syntax:
[ WITH [ RECURSIVE ] with_query [, ...] ]
SELECT [ ALL | DISTINCT [ ON ( expression [, ...] ) ] ]
    * | expression [ [ AS ] output_name ] [, ...]
    [ FROM from_item [, ...] ]
...


Questo significa che, qualora non sia necessario recuperare le tuple con accesso ad una tabella (ad esempio perche' le tuple vengono generate al volo da una stored procedure), la clausola FROM puo' essere omessa.
In altre parole il comando

SELECT 'W PostgreSQL';

fa quello che ci aspetta:

  ?column?  
--------------
 W PostgreSQL
(1 row)


mentre in Oracle l'istruzione

SELECT 'W Oracle';

non funziona poiche' la SELECT in Oracle si aspetta obbligatoriamente la clausola FROM. La soluzione che spesso si trova nei manuali e nella guida ufficiale e' di usare la tabella speciale "dual" nella clausola FROM, ossia l'istruzione funzionante diventa:

SELECT 'W Oracle' FROM dual;

Che cosa e' dual? E' una tabella (come tutte le altre) creata al momento di inizializzazione dell'istanza Oracle, assieme al catalogo di sistema. La tabella contiene esattamente una tupla con una singola colonna (di nome dummy) con valore 'X'. In PostgreSQL si puo' ricreare una tabella dual Oracle-like con i seguenti comandi:

# CREATE TABLE dual( dummy char(1) );
CREATE TABLE
# INSERT INTO dual(dummy) VALUES('X');
INSERT 0 1

Se sull'istanza PostgreSQL ora si esegue la query in stile Oracle-like si ottiene il risultato voluto:

# SELECT 'W Oracle' FROM dual;
 ?column?
----------
 W Oracle
(1 row)


Quindi e' possibile su PostgreSQL simulare il comportamento Oracle creando una tabella dual in modo molto semplice.
E' bene comunque spendere qualche considerazione circa la tabella dual di Oracle. Anzitutto e' bene capire come mai la query con la clausola "FROM dual" funziona su entrambi i sistemi. Il linguaggio SQL prevede che un join senza filtro riporti in uscita il prodotto cartesiano delle tuple delle relazioni coinvolte; questo significa che per ogni record presente in dual (unica relazione coinvolta) viene riportato in uscita un record con i valori selezionati di dual (in questo caso nessuno) e eventuali altri valori (in questo caso la stringa). E' facile verificare questo aggiungendo un record a dual ed eseguendo nuovamente la query:

# INSERT INTO dual(dummy) VALUES('Y');
INSERT 0 1
# SELECT 'W Oracle' FROM dual;
 ?column?
----------
 W Oracle
 W Oracle
(2 rows)


Spiegato quindi il mistero della clausola "FROM dual" si puo' analizzare in dettaglio cosa comporti questo approccio.
Anzitutto l'accesso alla tabella richiede un sequential scan per ogni query. La cosa non impatta sulle prestazioni, poiche' la tabella e' piccola e sicuramente non viene mai paginata, tuttavia il motore di esecuzione deve comunque effettuare l'accesso come per ogni normale tabella.
In secondo luogo qualora il contenuto di dual sia modificato (ad esempio aggiungendo un record) si otterra' che molte query non funzioneranno piu' nel modo voluto. Si pensi ad esempio a query del tipo

SELECT laMiaStoredProcedureDistruttiva() FROM dual;

che vengono eseguite piu' volte a causa di una manomissione di dual.
Analogamente, la rimozione del record da dual produce una query funzionante ma con output nullo. Entrambe le situazioni sono pericolose, ma la seconda (nessun record in dual) e' difficilmente individuabile nel caso di test automatici, poiche' la query di fatto esegue correttamente.

Quale comportamento e' corretto?
Personalmente ritengo che Oracle applichi un concetto di uniformita': tutte le query devono avere una relazione (esistente) nella clausola FROM. PostgreSQL e' piu' flessibile in questo, ammettendo che le tuple potrebbero essere generate al volo anche senza partire da un prodotto cartesiano.
Lato sintattico la sintassi di PostgreSQL e' sicuramente migliore: perche' scrivere sempre "FROM dual" nelle proprie query quando non serve l'output di dual? Lato semantico la metodologia di Oracle e' sicuramente piu' uniforme.
Infine occorre tenere presente che PostgreSQL garantisce che query SELECT senza clausola FROM funzioneranno sempre, anche in presenza di manomissioni allo schema (a patto di non rovinare gli operatori!), Oracle potrebbe mostrare comportamenti differenti fra le istanze a seconda del contenuto di dual.