Partial evaluation

Partial evaluation

In computing, partial evaluation is a technique for program optimization by specialization.

A computer program, "prog", is seen as a mapping of input data into output data::prog : I_{static} imes I_{dynamic} o O

I_{static}, the "static data", is the part of the input data known at compile time.

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

Futamura projections

A particularly interesting example of this, first described in the 1970s by Yoshihiko Futamura, is when "prog" is an interpreter for a programming language.

If Istatic is source code designed to run inside said 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 Istatic.

This technique is known as the first Futamura projection, of which there are three:

#Compiling by specializing an interpreter
#Compiler generation by self-application
#Compiler generator generation by double self-application

References

* Reprinted in "Higher-Order and Symbolic Computation" 12 (4): 381–391, 1999, with a foreword.
*

ee also

* Run-time algorithm specialisation
* Smn theorem
* Template metaprogramming

External links

* [http://www.itu.dk/people/sestoft/pebook/ Neil D. Jones, Carsten K. Gomard, and Peter Sestoft: "Partial Evaluation and Automatic Program Generation" (1993)] Book, full text available online.
* [http://partial-eval.org partial-eval.org] - a large "Online Bibliography of Partial Evaluation Research".
* [http://www.brics.dk/~pepm99/ 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)]
* [http://osl.iu.edu/~tveldhui/papers/pepm99/ C++ Templates as Partial Evaluation, 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)]
* [http://arxiv.org/pdf/cs.PL/9810010 C++ Templates as Partial Evaluation] a different version including Catat (pdf)
* [http://people.csail.mit.edu/gregs/dynamic-pe.html Applying Dynamic Partial Evaluation to dynamic, reflective programming languages]


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Evaluation strategy — Evaluation strategies Strict evaluation Applicative order Call by value Call by reference Call by sharing Call by copy restore Non strict evaluation Normal order Call by name Call by need/Lazy evaluation …   Wikipedia

  • Evaluation (disambiguation) — Evaluation is the process of characterizing and appraising something of interest or of determining the value of an expression (mathematics). Computer science * determining the value of an expression (programming) * Eager evaluation or strict… …   Wikipedia

  • Partial androgen insensitivity syndrome — Classification and external resources AIS results when the function of the androgen receptor (AR) is impaired. The AR protein (pictured) mediates the effects of androgens in the human body. ICD 10 …   Wikipedia

  • partial disability — The result of an injury that permanently reduces a worker s ability to function, but still permits the worker to do some gainful activity. Category: Accidents & Injuries Category: Employment Law & HR Category: Personal Finance & Retirement →… …   Law dictionary

  • Partial discharge — In electrical engineering, a partial discharge (PD) is a localised dielectric breakdown of a small portion of a solid or liquid electrical insulation system under high voltage stress. While a corona discharge is usually revealed by a relatively… …   Wikipedia

  • Short-circuit evaluation — Evaluation strategies Strict evaluation Applicative order Call by value Call by reference Call by sharing Call by copy restore Non strict evaluation Normal order Call by name Call by need/Lazy evaluation Call by …   Wikipedia

  • Partial volume — The partial volume effect occurs in medical imaging when a single voxel contains a mixture of multiple tissue values. A lower resolution increases this effect. The method to correct for the partial volume effect is referred to as partial volume… …   Wikipedia

  • Partial Portraits — Infobox Book | name = Partial Portraits author = Henry James country = United Kingdom language = English genre = Literary criticism publisher = Macmillan and Co., London release date = 8 May 1888 media type = Print (Hardback) pages = 408 pp isbn …   Wikipedia

  • Partial least squares regression — In statistics, the method of partial least squares regression (PLS regression) bears some relation to principal component analysis; instead of finding the hyperplanes of minimum variance, it finds a linear model describing some predicted… …   Wikipedia

  • Normalisation by evaluation — In programming language semantics, normalisation by evaluation (NBE) is a style of obtaining the normal form of terms in the λ calculus by appealing to their denotational semantics. A term is first interpreted into a denotational model of the λ… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”