Editing Partial evaluation

{{Short description|Technique for program optimization}}
{{Distinguish|partial application}}
{{More footnotes|date=May 2013}}
{{Evaluation strategy}}

In [[computing]], '''partial evaluation''' is a technique for several different types of [[optimization (computer science)|program optimization]] by [[Specialization (logic)|specialization]]. The most straightforward application is to produce new programs that run faster than the originals while being guaranteed to behave in the same way.

A [[computer program]] ''prog'' is seen as a [[map (mathematics)|map]]ping of input data into output data:

<math display="block">prog : I_\text{static} \times I_\text{dynamic} \to O,</math>

where <math>I_\text{static}</math>, the ''static data'', is the part of the input data known at compile time.

The partial evaluator transforms <math>\langle prog, I_\text{static}\rangle</math> into <math>prog^* : I_\text{dynamic} \to O</math> by precomputing all static input at compile time. <math>prog^*</math> is called the "residual program" and should run more efficiently than the original program. The act of partial evaluation is said to "residualize" <math>prog</math> to <math>prog^*</math>.

==Futamura projections==
A particularly interesting example of the use of partial evaluation, first described in the 1970s by Yoshihiko Futamura,<ref>[http://fi.ftmr.info/ Yoshihiko Futamura's website].</ref> is when ''prog'' is an [[Interpreter (computing)|interpreter]] for a [[programming language]].

If ''I''<sub>static</sub> is source code designed to run inside that interpreter, then partial evaluation of the interpreter with respect to this data/program produces ''prog''*, a version of the interpreter that only runs that source code, is written in the implementation language of the interpreter, does not require the source code to be resupplied, and runs faster than the original combination of the interpreter and the source. In this case ''prog''* is effectively a compiled version of ''I''<sub>static</sub>.

This technique is known as the first Futamura projection, of which there are three:
# Specializing an interpreter for given source code, yielding an executable.
# Specializing the specializer for the interpreter (as applied in #1), yielding a compiler.
# Specializing the specializer for itself (as applied in #2), yielding a tool that can convert any interpreter to an equivalent compiler.

They were described by Futamura in Japanese in 1971<ref>{{citation 
| title=Partial Evaluation of Computation Process --- An approach to a Compiler-Compiler
| volume=54-C
| journal=Transactions of the Institute of Electronics and Communications Engineers of Japan
| pages=721–728
| year=1971}}</ref> and in English in 1983.<ref>{{cite book |first=Y. |last=Futamura |chapter=Partial computation of programs |chapter-url= |title=RIMS Symposia on Software Science and Engineering |publisher=Springer |series=Lecture Notes in Computer Science |volume=147 |date=1983 |isbn=3-540-11980-9 |pages= 1–35|doi=10.1007/3-540-11980-9_13 |hdl=2433/103401}}</ref>

==See also==
* [[Compile-time function execution]]
* [[Memoization]]
* [[Partial application]]
* [[Run-time algorithm specialisation]]
* [[Smn theorem|s<sub>mn</sub> theorem]]
* [[Strength reduction]]
* [[Template metaprogramming]]

==References==
{{Reflist}}

===General references===
{{refbegin}}
*{{cite journal |first=Y. |last=Futamura |title=Partial Evaluation of Computation Process—An Approach to a Compiler-Compiler |journal=Higher-Order and Symbolic Computation |volume=12 |issue= 4|pages=381–391 |date=1999 |doi=10.1023/A:1010095604496 |citeseerx=10.1.1.10.2747 |s2cid=12673078 }}
*{{cite book |last1=Consel |first1=Charles |author2-link=Olivier Danvy |last2=Danvy |first2=Olivier |chapter=Tutorial Notes on Partial Evaluation |chapter-url= |title=POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages |publisher=Association for Computing Machinery |location= |date=1993 |isbn=0897915607 |pages=493–501 |doi=10.1145/158511.158707 |citeseerx=10.1.1.114.7330|s2cid=698339 }}
{{refend}}

==External links==
{{Refbegin}}
*{{cite book |url=http://www.itu.dk/people/sestoft/pebook/ |first1=Neil D. |last1=Jones |first2=Carsten K. |last2=Gomard |first3=Peter |last3=Sestoft |title=Partial Evaluation and Automatic Program Generation |year=1993 |publisher=Prentice Hall |isbn=9780130202499 }}
*{{cite web |editor-first=O. |editor-last=Danvy |title=Partial Evaluation and Semantics-Based Program Manipulation PEPM'99 |date=1999 |url=http://www.brics.dk/NS/99/1/BRICS-NS-99-1.pdf |citeseerx=10.1.1.164.2284 |ref={{harvid|PEPM'99}} }}
*{{cite book |first=Todd L. |last=Veldhuizen|chapter=C++ Templates as Partial Evaluation |year=1999 |title={{harvnb|PEPM'99}} |pages=15– |arxiv=cs/9810010 }}
* [http://people.csail.mit.edu/gregs/dynamic-pe.html Applying Dynamic Partial Evaluation to dynamic, reflective programming languages]
{{Refend}}

{{Compiler optimizations}}

{{DEFAULTSORT:Partial Evaluation}}
[[Category:Compiler optimizations]]
[[Category:Evaluation strategy]]