What is Code Reduction?
Definitions
-
What is simple code?
-
Current uses of code reduction
-
Related work
A possible definition of code reduction
can be given as:
Code Reduction is a program transformation
that results in simpler code.
Of course, this definition is not a very robust one, unless
we define program transformation and
simpler code. In our context, one possible
definition for the former is the following:
Let L be the set of programs that
can be written in a specific programming language. A program
transformation is a function:
f: L -> L
with the property that for all programs P in L,
the programs P and f(P) are equivalent.
We will not formally define program equivalence
here, mainly because the definition of this term can be very
different in different contexts. By stating that two programs
are equivalent, we roughly mean that they produce the same output
when given the same input, thus deferring the problem to the
definitions of input and output.
However, we will not proceed to such definitions, since this
would be out of this document's scope.
But what do we mean by simpler code? What is an
objective measure of program simplicity? Does such a measure exist?
Although it is very hard to answer these questions, we can identify
some general properties that usually characterize
simpler programs:
They are shorter in size.
-
They have fewer variables.
-
They have fewer nested constructs.
-
They do not contain unclear or cryptic code.
Of course, a programmer would immediately object that there are
innumerable exceptions and these properties are in no way absolute.
Programmers can't help but admit that defining program simplicity
in a complete and robust way is an extremely hard task. However,
every software engineer is bound to have a (rather clear)
intuitive notion of program simplicity and as
a result we will not discuss the matter any further.
Code reduction techniques have traditionally been used for a very
long time in optimizing compilers. Usually, its
place is at the last stages of compilation, in an optimization phase.
In this case, the code has already been translated to some
intermediate representation or even to an assembly language.
However, the way in which code reduction is used in Ghinsu is
different for two reasons:
It is performed on high level programs.
-
Its goal is improved maintainance, not
efficiency.
As far as we know, the application of such techniques to programs
that are still in source form, having as result an equivalent program
in the same source form, is a novel approach.
Here are some pointers to related work in the field of high level
code reduction:
- [Ambr85]
- Ambriola V., Giannotti F., Pedreschi D. & Turini F.,
"Symbolic Semantics and Program Reduction",
IEEE Transactions on Software Engineering,
vol.11, no.8, pp.784-95,
August 1985.
- [Berl90]
- Berlin A. & Weise D.,
"Compiling Scientific Code Using Partial
Evaluation",
IEEE Computer,
vol.23 , no.12, pp.25-37,
December 1990.
- [Blaz93]
- Blazy S. & Facon P.,
"Partial Evaluation as an Aid to the Comprehension
of Fortran Programs",
in Proceedings of the Second International Workshop in Program
Comprehension;
Capri, Italy, pp.46-54;
1993.
- [Coen85]
- Coen-Porisini A., De Paoli F., Ghezzi C. & Mandrioli D.,
"Software Specialization via Symbolic
Execution",
IEEE Transactions on Software Engineering,
vol.11, no.8, pp.884-9,
August 1985.
- [Wegm91]
- Wegman M.N. & Zadeck F.K.,
"Constant Propagation with Conditional
Branches",
ACM Transactions on Programming Languages and Systems,
vol.13, no.2, pp.191-210,
April 1991.
What next?
Contents
Code Reduction Module
How does it help?
This page is maintained by
Nikos Papaspyrou.
Please, feel free to send your comments, thoughts or suggestions to
nickie@softlab.ntua.gr.
Last updated: Monday May 15 1995, 12:05 EET DST.