Wadsworth proposed graph reduction for implementing functional languages. Its main virtue is to provide maximal sharings of both space and computation.
In this thesis, we propose a new graph reduction, Dealyed Substitution Graph Reduction (DSGR). DSGR defines two new rules that beta reduction, a major operation of graph reduction, must keep. The first rule is delayed-substitution rule. One or more beta reductions must be done to perform a function call of the program, because a beta reduction make only a rand value substitute for a bound variable. With delayed substitution rule, we do multiple bound-variable substitutions and, a function call can be performed through single beta reduction. So we can perform function calls efficiently. The second is exclusive-beta-reduction rule. To provide maximum sharings, each beta reduction makes a partial function graph. However, many of them are useless. DSGR does not make useless partial function graphs because exclusive-beta-reduction rule is to make absolutely necessary function graphs. Using exclusive-beta-reduction rule, we can save time and space.
DSGR is an efficient graph reduction for functional languages.
