Abstract
A technique to eliminate computational redundancy from a large and automatically detectable class of non-linear functions is introduced. It combines the advantages of existing memoisation and source-to-source program transformation techniques whilst greatly reducing the major disadvantages that are commonly associated with these two approaches. The method presented here uses a variant of memo-functions in which, regardless of the size of the memo-tables, the cost of table insertion and lookup operations are almost entirely eliminated. When compared to contemporary program transformation schemes, the technique presented achieves comparable improvements in efficiency whilst being mechanical. In addition, this technique is more generally applicable and require less compile-time deductive capacity than the corresponding program transformation schemes.
More precisely, the paper outlines a new technique for eliminating commutative redundancy from bilinear functions using local transient memo-lists instead of global memo-tables. Function evaluation is carried out in a bottom-up manner in which the results of inner nodes of the dependency graph are calculated first, and then only passed to those nodes higher-up in the graph that require them. In this way memo-lists “ripple” out from the inner nodes, and are subsequently used to generate new memo-lists for the next ripple. This technique overcomes the management cost of memo-tables, since table insertions and look-ups are now replaced by a single list cons and head operations respectively. Furthermore, it has some scope for parallel evaluation.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J W Backus. Can programming be liberated from the von neumann style? Communications of the ACM, 21(8):613–641, 1978.
J W Backus. The algebra of functional programs: function level reasoning, linear equations and extended definitions, volume 107, chapter 1, pages 1–43. Springer-Verlag, 1981.
R Bailey, A J Field, and H Khoshnevisan. Efficient implementation of functional programs. Research Report, Imperial College, 1986.
R S Bird. Tabulation techniques for recursive programs. ACM Computing Surveys, 12(4):403–417, 1980.
R S Bird. Improving programs by the introduction of recursion. Communications of the ACM, 20(1):856–863, 77.
R M Burstall and J D Darlington. A transformation system for developing recursive programs. Journal of the ACM, 24(1), 1977.
N H Cohen. Eliminating redundant recursive calls. ACM Transactions on Programming Languages and Systems, 5:265–269, 1983.
J Darlington. A synthesis of several sorting programs. Acta Informatica, 11(1), 1978.
P G Harrison, and H Khoshnevisan. The mechanical transformation of data types. The Computer Journal, 35(2):138–146, 1992.
P G Harrison, and H Khoshnevisan. A new approach to recursion removal. Theoretical Computer Science, 93:91–113, 1992.
P G Harrison, and H Khoshnevisan. On the synthesis of function inverses. Acta Informatica, 29:211–239, 1992.
H Khoshnevisan. Efficient memo-table management strategies. Acta Informatica, 28:43–81, 1990.
M S Paterson, and C E Hewitt. Comparative schematology, record of project mac. In Proceedings: Conference on Concurrent Systems and Parallel Computation, Woods Hole, Mass, pages 119–127, June 1970.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Khoshnevisan, H., Afshar, M. (1994). Mechanical elimination of commutative redundancy. In: Le Charlier, B. (eds) Static Analysis. SAS 1994. Lecture Notes in Computer Science, vol 864. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58485-4_58
Download citation
DOI: https://doi.org/10.1007/3-540-58485-4_58
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58485-8
Online ISBN: 978-3-540-49005-0
eBook Packages: Springer Book Archive