<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
                            Partial Evaluation
			    ******************

Introduction:
************

Inputs to programs can be classified as static or dynamic. Static inputs
are command line inputs, for example, while dynamic inputs are the inputs
accepted by the program while it is running. 

A program specializer or partial evaluator will specialize a program
w.r.t. its static inputs. In general, however, programs may also be specialized 
not only based on exact knowledge of the static inputs but also some 
meta-information about the static or the dynamic inputs (e.g., input
number is always positive).

Given a program, p, static inputs SI, dynamic inputs DI, and outputs O, 
we can write:

  O = [p](SI,DI)

Given a partial evaluator, mix, we can write:

  ps = [mix](p, SI)

where ps is the specialization of program p and:

  O = [ps](DI)

Compilation by Partial Evaluation: 
*********************************

The following equations should be self-explanatory:

  output = [source](input)

  output = [interpreter](source, input)

  AAA = [mix](interpreter, source)

  output = [AAA](input)

What is AAA? AAA is (a more efficient) system that takes inputs and 
produces outputs, like the original source code, when executed.  
Essentially, it is something similar to machine/target code.  Therefore:

  output = [target](input)

  target = [mix](interpreter, source)  ... (i)

Equation (i) represents the first Futamura projection, which says that target 
code is obtained by specializing an interpreter w.r.t. the source program. 
Target is in output language of mix, very often the language used for 
writing the interpreter (Prolog in our case).

From equation (i)

   BBB = mix(mix,interpreter)  

   target = [BBB](source)

What is BBB? BBB transforms source program into target program. Therefore, BBB
must be a compiler. Thus, a partial evaluator specialized w.r.t. an interpreter
yields a compiler. Thus:

   target = [compiler](source)  

   compiler = mix(mix,interpreter)   ... (ii)

Equation (ii) represents the second Futamura projection: a compiler of 
a language L is obtained by specializing mix w.r.t. an interpreter for L.
It describes how compilers can be automatically obtained from an 
interpreter.

Continuing:

   CCC = [mix](mix, mix)

   compiler = [CCC](interpreter)

What is CCC? CCC transforms interpreters into compilers. 
Therefore, it must be a compiler generator.

   compiler = [cogen](interpreter)

   cogen = [mix](mix, mix)  ... (iii)

Equation (iii) represents the 3rd Futamura projection which describes
how compiler generators may be automatically obtained. A compiler
generator is obtained by specializing mix w.r.t. itself. 

References:

N. Jones: An Introduction to Partial Evaluation, ACM Computing
Surveys; 28(3) Sep 1996.

Y. Futamura: Partial Evaluation of Computation Process---an 
Approach to a Compiler Compiler. Systems Computers and Control,
2(5):45-50.