A taxonomy of program transformers

A taxonomy of transformers.
transformer	information propagation	evaluation strategy	control restruct.		KMP test	elim struct.
transformer	information propagation	evaluation strategy	variant	genetic	KMP test	elim struct.
Partial Evaluation (PE)	constant	in-out	poly	mono	-	-
Deforestation	constant	out-in	poly	poly	-	+
Partial deduction	unification	unspecified	poly	mono	+	-
Positive SCP	unification	out-in	poly	poly	+	+
Perfect SCP	constraint	out-in	poly	poly	+	+
GPC	constraint	out-in	poly	poly	+	+

Legenda

information propagation

constant propagation:

the outcome of tests are ignored;

unification-based propagation:

substitutions into the transformed terms are used to represent the outcome of tests;

constraint-based propagation:

the transformer explicitly maintains sets of constraints recording previous tests (restrictions). Depending on the programming language other abstract properties may be propagated;
evaluation strategy
- inside-out (or call-by-value or applicative order);
- outside-in (or call-by-name or normal-order);
control restructuring

monovariant:

any program point in the subject program gives rise to zero or one program point in the residual program;

polyvariant:

any program point in the subject program can give rise to one or more program points in the residual program;

monogenetic:

any program point in the residual program is produced from a single program point of the subject program;

polygenetic:

any program point in the residual program may be produced from one or more program points of the subject program;
KMP test
- - : doesn't pass the test;
- + : pass the test;
eliminate date structures
- - : doesn't eliminate;
- + : eliminate;

This page is linked from: Program Transformation