GHINSU:   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.

What is simple code?

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:
o They are shorter in size.
o They have fewer variables.
o They have fewer nested constructs.
o 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.

Current uses of code reduction

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:
o It is performed on high level programs.
o 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.

Related work

Here are some pointers to related work in the field of high level code reduction:
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.
Berlin A. & Weise D., "Compiling Scientific Code Using Partial Evaluation", IEEE Computer, vol.23 , no.12, pp.25-37, December 1990.
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.
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.
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?

<A HREF=Contents     (o)></A>
<A HREF=Code Reduction Module     (o)></A>
<A HREF=How does it help?

This page is maintained by Nikos Papaspyrou.
Please, feel free to send your comments, thoughts or suggestions to

Last updated: Monday May 15 1995, 12:05 EET DST.