article

Free access

A bounds inference method for vector-based memoization

Authors:

Masami HagiyaAuthors Info & Claims

ACM SIGPLAN Notices, Volume 32, Issue 8

Pages 176 - 187

https://doi.org/10.1145/258949.258965

Published: 01 August 1997 Publication History

Abstract

The dynamic-sized tabulation method can be used to eliminate redundant calls for certain classes of recursive programs. An innovative aspect of the method is the use of lambda abstractions that may subsequently be converted to bounded vectors, in order to share redundant calls via vector lookup.To facilitate this conversion to vector form, we propose a new inference method to conservatively determine the bounds for arithmetic parameters of recursive functions. Suitable techniques for inferring the safe bounds of these parameters are introduced, together with supporting transformations. The resulting method can obtain efficient vector-based programs without the need for run-time bounds checking.

References

[1]

Richard S. Bird. Tabulation techniques for recursive programs. ACM Computing Surveys, 12(4):403-417, December 1980.

Digital Library

[2]

W.W. Bledsoe. A new method for proving certain Presburger formulae. In Proc of ICJAI, pages 15-21, 1975.

[3]

R.M. Burstall and J. Darhngton. A transformation system for developing recursive programs. Journal of A GM, 24(1):44-67, January 1977.

Digital Library

[4]

Wei-Ngan Chin. Towards an automated tupling strategy. In $rd A CM Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 119- 132, Copenhagen, Denmark, ACM Press, June 1993. ACM Press.

Digital Library

[5]

Wei-Ngan Chin and John Darlington. A higher-order removal method. LISP and Symbolic Computation, 9(4):287-322, 1996.

Digital Library

[6]

Wei-Ngan Chin and Masami Hagiya. A transformation method for dynamic-sized tabulation. Acta Informatica, 32:93-115, March 1995.

Digital Library

[7]

Norman H. Cohen. Eliminating redundant recursive calls. A CM Trans. on Programming Languages and Systems, 5(3):265-299, July 1983.

Digital Library

[8]

R. Gupta. A fresh look at optimizing array bound checking. In A CM SIGPLAN Conf. on Program Lang. Design and Impl., pages 272-282, New York, June 1990.

Digital Library

[9]

J Hughes, L Pareto, and A Sabry. Proving the correctness of reactive systems using sized types. In ~3rd A CM Principles of Programming Languages Conference, pages 410-423. ACM Press, January 1996.

Digital Library

[10]

N.D. Jones, C.K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall, 1993.

Digital Library

[11]

P Kolte and M Wolfe. Elimination of redundant array subscript range checks. In A GM Conference on Programming Language Design and Implementation, pages 270-278. ACM Press, .Iune 1995.

Digital Library

[12]

Donald Michie. Memo functions and machine learning. Nature, 218:19-22, April 1968.

[13]

N. Perry. Hope+. Tech Note: IC/FPR/LANG/2.5.1/7, DoC, Imperial College, 1989.

[14]

Alberto Pettorossi. A powerful strategy for deriving programs by transformation. In 3rd A CM LISP and Functional Programming Conference, pages 273-281. ACM Press, 1984.

Digital Library

[15]

William. Pugh. The omega test: A fast practical integer programming algorithm for dependence analysis. Communications of A CM, 8:102-114, 1992.

Digital Library

[16]

Akihiko Takano. Generalized partial computation for a lazy functional language. In A CM Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pages 1-11, New Haven, Connecticut, August 1991. ACM Press.

Digital Library

Cited By

MacDonough ACaspersen MEdwards SBarnes TGarcia D(2017)Recursive ConvergenceProceedings of the 2017 ACM SIGCSE Technical Symposium on Computer Science Education10.1145/3017680.3022457(771-772)Online publication date: 8-Mar-2017
https://dl.acm.org/doi/10.1145/3017680.3022457
Liu YStoller S(2002)Dynamic Programming via Static IncrementalizationProgramming Languages and Systems10.1007/3-540-49099-X_19(288-305)Online publication date: 28-Mar-2002
https://doi.org/10.1007/3-540-49099-X_19
MacDonough ACaspersen MEdwards SBarnes TGarcia D(2017)Recursive ConvergenceProceedings of the 2017 ACM SIGCSE Technical Symposium on Computer Science Education10.1145/3017680.3022457(771-772)Online publication date: 8-Mar-2017
https://dl.acm.org/doi/10.1145/3017680.3022457
Show More Cited By

Index Terms

A bounds inference method for vector-based memoization

Recommendations

A bounds inference method for vector-based memoization
ICFP '97: Proceedings of the second ACM SIGPLAN international conference on Functional programming

The dynamic-sized tabulation method can be used to eliminate redundant calls for certain classes of recursive programs. An innovative aspect of the method is the use of lambda abstractions that may subsequently be converted to bounded vectors, in order ...
PAC-Bayes bounds for twin support vector machines

Twin support vector machines are regarded as a milestone in the development of support vector machines. Compared to standard support vector machines, they learn two nonparallel hyperplanes rather than one as in standard support vector machines for ...
Radius margin bounds for support vector machines with the RBF kernel

An important approach for efficient support vector machine (SVM) model selection is to use differentiable bounds of the leave-one-out (loo) error. Past efforts focused on finding tight bounds of loo (e.g., radius margin bounds, span bounds). However, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 32, Issue 8

Aug. 1997

322 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/258949

Chairmen:
Simon Peyton Jones
Univ. of Glasgow, Glasgow, Scotland, UK
,
Mads Tofte
Univ. of Copenhagen, Denmark
,
Editor:
A. Michael Berman
Rowan Univ. Glassboro, NJ

Issue’s Table of Contents

ICFP '97: Proceedings of the second ACM SIGPLAN international conference on Functional programming
August 1997
326 pages
ISBN:0897919181
DOI:10.1145/258948
Chairmen:
Simon Peyton Jones
Univ. of Glasgow, Glasgow, Scotland, UK
,
Mads Tofte
Univ. of Copenhagen, Denmark
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ

Copyright © 1997 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1997

Published in SIGPLAN Volume 32, Issue 8

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
380
Total Downloads

Downloads (Last 12 months)102
Downloads (Last 6 weeks)18

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

MacDonough ACaspersen MEdwards SBarnes TGarcia D(2017)Recursive ConvergenceProceedings of the 2017 ACM SIGCSE Technical Symposium on Computer Science Education10.1145/3017680.3022457(771-772)Online publication date: 8-Mar-2017
https://dl.acm.org/doi/10.1145/3017680.3022457
Liu YStoller S(2002)Dynamic Programming via Static IncrementalizationProgramming Languages and Systems10.1007/3-540-49099-X_19(288-305)Online publication date: 28-Mar-2002
https://doi.org/10.1007/3-540-49099-X_19
MacDonough ACaspersen MEdwards SBarnes TGarcia D(2017)Recursive ConvergenceProceedings of the 2017 ACM SIGCSE Technical Symposium on Computer Science Education10.1145/3017680.3022457(771-772)Online publication date: 8-Mar-2017
https://dl.acm.org/doi/10.1145/3017680.3022457
Liu YStoller S(2008)Dynamic Programming via Static IncrementalizationAutomatic Program Development10.1007/978-1-4020-6585-9_9(71-92)Online publication date: 2008
https://doi.org/10.1007/978-1-4020-6585-9_9
Luca BAndrei SAnderson HKhoo SHatcliff JTip F(2006)Program transformation by solving recurrencesProceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation10.1145/1111542.1111563(121-129)Online publication date: 9-Jan-2006
https://dl.acm.org/doi/10.1145/1111542.1111563
Liu YStoller S(2003)Optimizing Ackermann's function by incrementalizationACM SIGPLAN Notices10.1145/966049.77739838:10(85-91)Online publication date: 7-Jun-2003
https://dl.acm.org/doi/10.1145/966049.777398
Liu YStoller SLeuschel M(2003)Optimizing Ackermann's function by incrementalizationProceedings of the 2003 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation10.1145/777388.777398(85-91)Online publication date: 7-Jun-2003
https://dl.acm.org/doi/10.1145/777388.777398
Liu YStoller S(2003)Dynamic Programming via Static IncrementalizationHigher-Order and Symbolic Computation10.1023/A:102306802048316:1-2(37-62)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1023/A%3A1023068020483
Liu YStoller S(2002)Program optimization using indexed and recursive data structuresACM SIGPLAN Notices10.1145/509799.50304137:3(108-118)Online publication date: 14-Jan-2002
https://dl.acm.org/doi/10.1145/509799.503041
Liu YStoller SThiemann P(2002)Program optimization using indexed and recursive data structuresProceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulation10.1145/503032.503041(108-118)Online publication date: 14-Jan-2002
https://dl.acm.org/doi/10.1145/503032.503041
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents