Partial Evaluation
A term for the metaprogramming technique that consists in program transformation into simpler programs specialized for execution in an environment where some information is known as compared to a generic environment. Typically, a function that takes many arguments is partially evaluated considering as known the values of some of the arguments (the static arguments) while some other arguments are still to be determined (the dynamic arguments).See also Partial Evaluation 101.
Partial evaluation of a function λs d → FOO with a known value BAR for s is really just like optimizing function λd → FOO considering that known value. The most simple way of doing partial evaluation is to keep around partially curried closures, doing no optimization. Conversely, knowing how to partially evaluate a function automatically leads to optimization techniques in presence of same known information.
People like Andrzej Filinski have used suitable type-systems to give nice formal models of what can be automatically partially-evaluated.
The Futamura projections explain how to build a compiler for a language L written in language M, out of a specific interpreter of language L in language M, and a partial evaluator for language M, as well as other such tricks.
Partial evaluation is instrumental in allowing efficient implementation of deep meta^n-level descriptions of systems, by folding together all the statically known levels into a one interpreter or compiler.
Most computing systems do only static partial evaluation during compilation. People at project COMPOSE also do partial evaluation at runtime from templates obtained at compile-time.
We at the TUNES project would like to provide dynamic partial evaluation. Because we manipulate semantical objects, and thus have no such thing as "compile time". Instead, the user may explicitly and programmatically request some partial evaluation whenever he thinks it should be done.
Partial Evaluation is better understood in a framework of Staged Evaluation (that can be formalized with modal logics), wherein total/traditional evaluation of programs is conceptually executed in several stages, the last of these stages being the final user-visible "run-time" (which obviously depends on who the users are, and what are their points of views).
Another way to look at it is that instead of simplifying programs using some kind of total generic single-minded reduction strategy, a more cunning strategy would be used. Now, even usual partial evaluation then looks like some kind of single-metaminded reduction, that only consists in single-minded binding analysis and inlining taking into account only one (very powerful, but still) kind of static information, statically determined by the partial evaluator (actually, software like the partial evaluators from COMPOSE allow -- and require -- quite of bit of user parametrization of the PE). Instead of having a one static partial evaluator, it could be imagined that metaprograms be grown to manipulate and optimize other programs until they automatically solve problems at hands with minimal user concern for efficiency. The task is certainly daunting, and most everyone would say it's impossible but there is no reason to believe it is as stupid an ambition as some would pretend.
Indeed, this reminds me a Chinese story with Mister Smart, Mister Stupid, and the Mountain to move. Basically, there's a big mountain that is a real inconvenience to everybody; someday, Mr Smart sees Mr Stupid hitting the mountain with a pick, and asks him why he does it. Mr Stupid explains that everyday after his work, he does attack the mountain, so as to get rid of it. Hence Mister Smart laughs at Mr Stupid, finally, he tries to convince Mister Stupid that what he does is useless and wasteful, and will never succeed. But then, Mister Stupid replies that surely he'll never be able to see the end of this work personally. But after his death, his son eldest son would replace him, and so on, until the mountain would be vanquished.
- An Online Bibliography of Partial Evaluation.
- A Computational Formalization for Partial Evaluation.
- Foundations of Partial Evaluation and Program Specialization course notes.
This page is linked from: A taxonomy of program transformers Code Generation COMPOSE group Descartes Java Max Methods of Reflection Partial Evaluation 101 Performance Scheme Static Supercompilation Synthetix