Valutazione parziale
![Questa voce è da wikificare](http://upload.wikimedia.org/wikipedia/commons/thumb/c/ce/Wikitext.svg/50px-Wikitext.svg.png)
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
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
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
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
- 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
- Teorema SMN
- Metaprogrammazione
Collegamenti esterni
- 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).
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)