[Next] [Up] [Previous]

Here is a sketch of the variable-substitution algorithm. It uses three user-specified complexity thresholds, whose purpose will become clear in the following description.

Given an expression [tex2html_wrap5822], compute its weight [tex2html_wrap5824]. Do not perform substitutions if [tex2html_wrap5826]. Otherwise, [tex2html_wrap5828] is a good candidate for variable substitution.

First try to substitute for the children of
[tex2html_wrap5830]. Given children [tex2html_wrap5832],
compute their weights [tex2html_wrap5834]. Substitute for a
child [tex2html_wrap5836] if and only if its relative
complexity is greater than
`*proportional-complexity-threshold*`. Thus, for each
[tex2html_wrap5838], if [tex2html_wrap5840], apply the
algorithm recursively to [tex2html_wrap5842]. If no
substitution can be performed on the descendants of
[tex2html_wrap5844], replace [tex2html_wrap5846] itself.

If no substitution can be performed on any of the [tex2html_wrap5848] or their subexpressions, then substitute for [tex2html_wrap5850] provided that [tex2html_wrap5852] is not a top-level expression. Also do not substitute if [tex2html_wrap5854] is one of the sides of a relational.

Given a top level expression [tex2html_wrap5856] having weight [tex2html_wrap5858], this algorithm is called as follows:

[LVerbatim1677]

where `(complexity-threshold e)` is defined as:

[LVerbatim1680]

Instead of computing [tex2html_wrap5860], we initialize the algorithm with the threshold [tex2html_wrap5862], since [tex2html_wrap5864] remains constant throughout the algorithm.

TV Raman

Thu Mar 9 20:10:41 EST 1995