Valutazione parziale

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 v₁,..,v_n (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 v₁,..,v_n, ma che sia più efficiente. Grazie al Teorema $S_{n}^{m}$ di Kleene sappiamo che un tale sistema può essere realizzato.

Esempio

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:

f₅(y) = print(5)

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

Peval

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: Prog^M * dati -> Prog^M

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 (P^M) e separiamo in suoi dati in ingresso il due sottoinsiemi I_S e I_D tali che:

I_S contiene solo i dati statici ovvero i dati su cui è possibile effettuare una specializzazione.
I_D contiene i restanti dati dinamici.

P^M: I_S x I_D -> Output

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

peval(P^M, I_S) = P' dove P'(I_D) = P^M(I_S, I_D);

queste equazioni descrivono le proprietà del valutatore parziale.

Proiezioni di Futamura

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 (I_L^M); l'interprete riceve due dati in ingresso, un programma scritto in L (P^L) ed il codice sorgente I_S. Specializziamo l'interprete rispetto ad un particolare programma prog^L:

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

Yoshihiko Futamura, Partial Evaluation of Computation Process – An Approach to a Compiler-Compiler (PDF), in Systems, Computers, Controls, vol. 2, n. 5, 1971, pp. 45–50. Reprinted in Higher-Order and Symbolic Computation 12 (4): 381–391, 1999, with a foreword.
Charles Consel and Olivier Danvy, Tutorial Notes on Partial Evaluation, in Proceedings of the Twentieth Annual ACM Symposium on Principles of Programming Languages, 1993, pp. 493–501.

Voci correlate

Collegamenti esterni

(EN) Eric W. Weisstein, Valutazione parziale, su MathWorld, Wolfram Research.
(EN) Denis Howe, partial evaluation, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
Neil D. Jones, Carsten K. Gomard, and Peter Sestoft: Partial Evaluation and Automatic Program Generation (1993) Book, full text available online.
partial-eval.org Archiviato il 22 giugno 2021 in Internet Archive. - a large "Online Bibliography of Partial Evaluation Research".
1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99), su brics.dk. URL consultato il 22 giugno 2009 (archiviato dall'url originale il 4 febbraio 2006).
C++ Templates as Partial Evaluation, 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99), su osl.iu.edu. URL consultato il 22 giugno 2009 (archiviato dall'url originale il 13 dicembre 2002).

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