Valutazione parziale

tecnica che permette di ottimizzare un programma specializzandolo

In Informatica, la valutazione parziale è una tecnica che permette di ottimizzare un programma specializzandolo, in pratica consiste nel fatto di valutare un programma per cui sia nota una parte degli input, in modo tale da ottenere un programma specializzato rispetto a tale input, ma che risulti essere più efficiente dell'originale.

Supponiamo di avere un programma P ed n-upla di valori v1,..,vn (per i suoi primi n valori di ingresso), l'obbiettivo è individuare un programma P' tale che abbia lo stesso comportamento di P, quando i suoi primi n ingressi sono v1,..,vn, ma che sia più efficiente. Grazie al Teorema di Kleene sappiamo che un tale sistema può essere realizzato.

Esempio

modifica

f(x,y) = if (x>0 and x<=10) then print(x) else h(y)

Se volessimo specializzare f per il valore x=5, allora:

f5(y) = print(5)

Notiamo subito l'ottimizzazione di questa riga di codice, per cui f5 risulta più efficiente per qualunque valore di y.

Inoltre, la valutazione parziale, permette di generare automaticamente un compilatore a partire da un interprete

Nel contesto dei programmi, il calcolo di una tale funzione di ottimizzazione viene fatto da un valutatore parziale peval; questi è capace di specializzare i programmi scritti in un certo linguaggio M e può essere definito come una funzione:

peval: ProgM * dati -> ProgM

che, dato un programma scritto nel linguaggio M ed un input dati, per alcuni suoi dati di ingresso, produce un altro programma sempre scritto nel linguaggio M, ma che rappresenta una specializzazione del primo.

A questo punto, consideriamo un generico programma P scritto nel linguaggio M (PM) e separiamo in suoi dati in ingresso il due sottoinsiemi IS e ID tali che:

  • IS contiene solo i dati statici ovvero i dati su cui è possibile effettuare una specializzazione.
  • ID contiene i restanti dati dinamici.

PM: IS x ID -> Output

Si ha, come abbiamo visto nell'esempio precedente della specializzazione della funzione f5, che:

peval(PM, IS) = P' dove P'(ID) = PM(IS, ID);

queste equazioni descrivono le proprietà del valutatore parziale.

Proiezioni di Futamura

modifica

Un esempio particolarmente interessante di questo, fu descritto la prima volta nel 1970 da Yoshihiko Futamura, quando venne considerato come programma un interprete per un linguaggio di programmazione, come tale può anch'esso essere parzialmente valutato. Supponiamo di avere un interprete scritto in M del linguaggio L (ILM); l'interprete riceve due dati in ingresso, un programma scritto in L (PL) ed il codice sorgente IS. Specializziamo l'interprete rispetto ad un particolare programma progL:

peval(int, prog) = int' tale che ∀s -> int'(s) = int(prog, s)

Quindi fissato un programma, int(prog, s) è equivalente a int'(s), ma int'(s) allora è la traduzione di prog da L a M, ossia il risultato della compilazione di prog sulla macchina astratta M (prima proiezione di Futamura).

intˁ tra l'altro rappresenta una versione dell'interprete che esegue solo il codice sorgente ed è indipendente da prog, è scritto nel linguaggio dell'interprete ed è eseguito più velocemente rispetto alla classica interpretazione.

Supponiamo ora che anche peval sia scritto nel linguaggio M, allora è possibile applicare peval a peval stesso. Dato che i parametri di peval sono un programma scritto in M e dei dati specializzati, nulla vieta di applicare a peval come programma peval stesso e come dati un interprete del linguaggio L:

peval(peval, int) = peval' tale che per ogni prog, peval'(prog) = peval(int, prog)

dalla prima proiezione di Futamura sappiamo che peval(int, prog) dà come risultato il codice compilato di prog. Dunque peval' è il compilatore da L a M (seconda proiezione di Futamura).

"In questo modo si può convertire sistematicamente un interprete nel corrispondente compilatore"

Infine applichiamo peval a peval e peval:

peval(peval, peval) = peval' tale che per ogni int si ha: peval'(int) = peval(peval, int)

per la seconda proiezione di Futamura si ha anche che peval(peval, int) dà come risultato il compilatore da L a M. Dunque peval' è un programma di M che, dato un interprete del linguaggio L scritto in M, produce il compilatore da L a M: peval' è un generatore di compilatori per M, o compiler compiler (terza proiezione di Futamura).

Bibliografia

modifica


Voci correlate

modifica

Collegamenti esterni

modifica
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica