Abstract
Memoization is a well-known method which makes use of a table of previously-computed results in order to ensure that parts of a search (or computation)s pace are not revisited. A new technique is presented which enables the systematic and selective memoization of a wide range of algorithms. The technique overcomes disadvantages of previous approaches. In particular, the proposed technique can help programmers avoid mistakes that can result in sub-optimal use of memoization. In addition, the resulting memoized programs are amenable to analysis using equational reasoning. It is anticipated that further work will lead to proof of correctness of the proposed memoization technique.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Augusteijn, L. (1993) Functional Programming, Program Transformations and Compiler Construction. Philips Research Laboratories. ISBN 90-74445-04-7.
Burge, W.H. (1975) Recursive Programming Techniques. Addison-Wesley Publishing Company, Reading, Massachusetts.
Fairburn, J. (1986) Making form follow function: An exercise in functional programming style. University of Cambridge Computer Laboratory Technical Report No 89.
Field, A. J. and Harrison, P. G. (1988) Functional Programming. Addison-Wesley Publishing Company, Reading, Massachusetts.
Frost, R.A. (2002) W/AGE The Windsor Attribute Grammar Programming Environment. IEEE Symposia on Human Centric Computing Languages and Environments HCC’2002 96–99.
Frost, R.A. and Szydlowski, B. (1995) Memoizing purely-functional top-down backtracking language processors. Science of Computer Programming” (27) 263–288.
Frost, R.A. (1993) ‘Guarded attribute grammars’. Software Practice and Experience. 23(10) 1139–1156.
Frost, R.A. (1992) Constructing programs as executable attribute grammars. The Computer Journal 35(4) 376–389.
Frost, R.A. and Launchbury, E. J. (1989) Constructing natural language interpreters in a lazy functional language‘. The Computer Journal-Special edition on Lazy Functional Programming, 32(2) 108–121.
Hudak, P., Wadler, P., Arvind, Boutel, B., Fairbairn, J., Fasel, J., Hammond, K., Hughes, J., Johnsson, T., Kieburtz, D., Nikhil, R., Peyton Jones, S., Reeve, M., Wise, D. and Young, J. (1992) Report on the programming language Haskell, a non-strict, purely functional language, Version 1.2 ACM SIGPLAN Notices 27(5).
Hughes, R.J.M. (1985) Lazy memo functions. In proceedings. Conference on Functional Programming and Computer Architecture Nancy, France, September 1985. Springer-Verlag Lecture Note Series 201, editors G. Goos and J. Hartmanis, 129–146.
Johnson, M. (1995) Squibs and Discussions: Memoization in top-down parsing. Computational Linguistics 21(3) 405–417.
Khoshnevisan, H. (1990) Efficient memo-table management strategies. Acta Informatica 28, 43–81.
Koskimies, K. Lazy recursive descent parsing for modular language implementation. Software Practice and Experience, 20(8) 749–772, 1990.
Leermakers, R. (1993) The Functional Treatment of Parsing. Kluwer Academic Publishers, ISBN 0-7923-9376-7.
Michie, D. (1968) ‘Memo’ functions and machine learning. Nature 218 19–22.
Moggi E. (1989) Computational lambda-calculus and monads. IEEE Symposium on Logic in Computer Science, Asilomar, California, June 1989, 14–23.
Norvig, P. (1991) Techniques for automatic memoisation with applications to context-free parsing. Computational Linguistics 17(1) 91–98.
Panitz (1996) Termination proofs for a lazy functional language by abstract interpretation. http://citeseer.nj.nec.com/panitz96termination.html
Turner, D. (1985) A lazy functional programming language with polymorphic types. Proc. IFIP Int. Conf. on Functional Programmiong Languages and Computer Architecture. Nancy, France. Springer Verlag Lecture Notes in Computer Science 201.
Wadler, P. (1985) How to replace failure by a list of successes, in P. Jouannaud (ed.) Functional Programming Languages and Computer Architectures Lecture Notes in Computer Science 201, Springer-Verlag, Heidelberg, 113.
Wadler, P. (1990) Comprehending monads. ACM SIGPLAN/SIGACT/SIGART Symposium on Lisp and Functional Programming, Nice, France, June 1990, 61–78.
Wadler, P. (1995) Monads for functional programming, Proceedings of the Bastad Spring School on Advanced Functional Programming, ed J. Jeuring and E. Meijer. Springer Verlag Lecture Notes in Computer Science 925.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Frost, R. (2003). Monadic Memoization towards Correctness-Preserving Reduction of Search. In: Xiang, Y., Chaib-draa, B. (eds) Advances in Artificial Intelligence. Canadian AI 2003. Lecture Notes in Computer Science, vol 2671. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44886-1_8
Download citation
DOI: https://doi.org/10.1007/3-540-44886-1_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40300-5
Online ISBN: 978-3-540-44886-0
eBook Packages: Springer Book Archive