venerdì 26 giugno 2015

Turing e Template

Salve a tutti o lettori! Il blog languiva (in buona parte grazie a quella cosa chiamata "vita reale" che ha bloccato diversi GNUrants dallo scrivere qualcosa che non fosse relativo al lavoro o all'università).

Invece di lasciarvi in attesa che grossi articoli appaiano ho deciso di scrivere qualche paragrafo sui Template Engine e sulle macchine di Turing di cui ha già parlato il buon Federico.

La domanda che vi pongo è: preso un Template Engine (ad esempio Jinja2 per Python) questo è Turing-completo? Posso cioé scrivere un qualsiasi programma (da Quicksort a DooM) in forma di template?

Potete subito intuire che le conseguenze di una risposta affermativa a questa domanda non siano da poco, sia in termini di flessibilità del Template Engine (posso potenzialmente fare quello che voglio senza uscire dal Template Engine) sia in termini di sicurezza (un attaccante che riuscisse a sfruttare una mancata validazione dell'input che passo al Template Engine potrebbe far fare di tutto e di più al mio server).

Un vecchio detto recita: in teoria non c'è differenza tra la pratica e la teoria, in pratica la differenza c'è eccome!

Questo è uno dei casi in cui si verifica proprio questa situazione: in teoria io posso scrivere DooM come template Jinja2 ma in pratica non posso farlo perché il mio template engine non ha accesso all'hardware della mia macchina per cui il massimo risultato a cui poso aspirare è renderizzare le schermate una ad una sottoforma di file SVG.

Un po' di teoria

Prima di continuare a sproloquiare su macchine di Turing e Template occorre definire quale sia l'insieme minimo di caratteristiche che fanno sì che un linguaggio di programmazione, una definizione formale di regole di riscrittura o un modello computazionale astratto siano Turing-Completi e quindi equivalenti alla Macchina di Turing.

In primo luogo la memoria deve essere presente e deve essere infinita: non devo preoccuparmi di esaurirla.

In secondo luogo devo avere un modo per dare un input arbitrariamente grande (diciamo un infinito numerabile di possibili input) ed ottenere un numero intero che codifichi il mio output.

Devo ovviamente poter scrivere e leggere a piacere nella mia memoria e devo poter decidere cosa scrivere in base a determinate condizioni.

Ora prendiamo un modello di computo più user-friendly della Macchina di Turing e del Lambda Calcolo: la macchina RASP.

Questa macchina è dotata di infiniti registri contenenti ciascuno un numero intero qualsiasi e ha un set di sole quattro istruzioni:

  • INC x: incrementa di un'unità il registro x.
  • DEC x: decrementa di un'unità il registro x.
  • JZ x z: se il contenuto del registro x è pari a zero salta all'istruzione z.
  • HALT: la computazione è terminata.

È stato dimostrato che questo modello è Turing completo (tranquilli, non vi farò subire una dimostrazione formale). In alcune formulazioni DEC è sostituita da ZERO (istruzione che azzera il contenuto di un registro) e HALT è sostituita da GOTO (come condizione di arresto si assume che la macchina si fermi automaticamente dopo aver eseguito l'ultima istruzione).

Ora se il nostro Template Engine contempla quelle quattro istruzioni o degli equivalenti di quelle quattro istruzioni possiamo tranquillamente affermare che sia equivalente alla macchina RASP e, in virtù della proprietà transitiva, sia equivalente alla Macchina di Turing (ammesso ovviamente che sia abbia a disposizione una memoria infinita, ma siamo nel campo della teoria per cui la memoria è infinita per definizione).

Per tutti i calcolatori, Batman!

Forse ci sarete già arrivati, ma un Template Engine che abbia gli IF e permetta di scrivere operazioni aritmetiche di somma e sottrazione può tranquillamente eseguire tre di quelle quattro istruzioni. Se rinunciamo all'istruzione HALT in favore del più amichevole "quando hai finito di processare il template hai finito la computazione" e organizziamo accuratamente i nostri IF avremo tutto quello che ci serve!

Quindi la maggior parte dei Template Engine avanzati SONO Turing-completi, a dispetto del fatto che spesso servono "solo" ad evitare allo sviluppatore di scrivere tonnellate di codice ripetitivo e noioso.

Meditate gente, meditate...