Valutazione parziale

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.

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 S_{n}^{m} di Kleene sappiamo che un tale sistema può essere realizzato.

Esempio[modifica | modifica wikitesto]

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.

peval[modifica | modifica wikitesto]

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 | modifica wikitesto]

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"

In fine 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).

Fonti[modifica | modifica wikitesto]


Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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