Article

Free access

A bounds inference method for vector-based memoization

Authors:

Masami HagiyaAuthors Info & Claims

ICFP '97: Proceedings of the second ACM SIGPLAN international conference on Functional programming

Pages 176 - 187

https://doi.org/10.1145/258948.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(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
Show More Cited By

Index Terms

A bounds inference method for vector-based memoization

Recommendations

A bounds inference method for vector-based memoization

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 Conferences

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

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

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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
IFIP WG 2.8: IFIP WG 2.8

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICFP97

Sponsor:

SIGPLAN
IFIP WG 2.8

ICFP97: International Conference on Functional Programming 1997

June 9 - 11, 1997

Amsterdam, The Netherlands

Acceptance Rates

ICFP '97 Paper Acceptance Rate 25 of 78 submissions, 32%;

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
379
Total Downloads

Downloads (Last 12 months)101
Downloads (Last 6 weeks)17

Reflects downloads up to 18 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(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
Chin WKhoo S(2001)Calculating Sized TypesHigher-Order and Symbolic Computation10.1023/A:101299681617814:2-3(261-300)Online publication date: 1-Sep-2001
https://dl.acm.org/doi/10.1023/A%3A1012996816178
Liu YStoller STeitelbaum T(2001)Strengthening invariants for efficient computationScience of Computer Programming10.1016/S0167-6423(01)00003-X41:2(139-172)Online publication date: 24-Oct-2001
https://dl.acm.org/doi/10.1016/S0167-6423%2801%2900003-X
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 Table of Contents