The term "memoization" in computer science typically refers to the somewhat magical ability of a simple RAM lookup table of previous function results to transform a slow recursive implementation of a function into a fast implementation of the function. Thus, the following extremely slow Lisp implementation of Fibonacci is suddenly transformed into a high performance implementation by the simple usage of memoization which remembers the results of previous calls to fib so they don't have to be laboriously recomputed. (defun fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) We now note that it doesn't harm performance "too" much if we sometimes forget a particular result and have to recompute it; this is somewhat akin to a "page fault" in a virtual memory system. In fact, for many applications, a finite, fixed-size "memo table" is often good enough for government work. Question: does anyone here have an academic _reference_ for this last statement that a fixed-size memo table is good enough? I seem to recall reading a short paper (in English) from the 1960's or 1970's which made precisely this point about fixed-size memo tables. Sadly, Google hasn't been able to find this paper for me, and the Elsevier & other paywalls won't allow me to search some of these old journals.
A few months ago the problem of memoizing a huge data tree came up and how to keep it using a small memo table. I was referred to the following enlightening article (warning this is all phrased in terms of Haskell -- which I think is a wonderful language -- but that's another discussion). This has been the subject of discussion in lots of the AI literature. I'll see if I can find some other references. http://okmij.org/ftp/Haskell/index.html#memo-off Victor On Sat, Mar 9, 2013 at 9:52 AM, Henry Baker <hbaker1@pipeline.com> wrote:
The term "memoization" in computer science typically refers to the somewhat magical ability of a simple RAM lookup table of previous function results to transform a slow recursive implementation of a function into a fast implementation of the function.
Thus, the following extremely slow Lisp implementation of Fibonacci is suddenly transformed into a high performance implementation by the simple usage of memoization which remembers the results of previous calls to fib so they don't have to be laboriously recomputed.
(defun fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
We now note that it doesn't harm performance "too" much if we sometimes forget a particular result and have to recompute it; this is somewhat akin to a "page fault" in a virtual memory system.
In fact, for many applications, a finite, fixed-size "memo table" is often good enough for government work.
Question: does anyone here have an academic _reference_ for this last statement that a fixed-size memo table is good enough?
I seem to recall reading a short paper (in English) from the 1960's or 1970's which made precisely this point about fixed-size memo tables.
Sadly, Google hasn't been able to find this paper for me, and the Elsevier & other paywalls won't allow me to search some of these old journals.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* Henry Baker <hbaker1@pipeline.com> [Mar 09. 2013 16:22]:
[...]
We now note that it doesn't harm performance "too" much if we sometimes forget a particular result and have to recompute it; this is somewhat akin to a "page fault" in a virtual memory system.
There are very many ways this could be made precise...
In fact, for many applications, a finite, fixed-size "memo table" is often good enough for government work.
For some definition of "many" and "enough".
Question: does anyone here have an academic _reference_ for this last statement that a fixed-size memo table is good enough?
I seem to recall reading a short paper (in English) from the 1960's or 1970's which made precisely this point about fixed-size memo tables.
[...]
Cormen et al., Introduction to Algorithms, (2nd ed.) doesn't seem to give a single reference about memoization. A few "old enough" ones may be Samuel, A. L. , IBM J. Res. Dev., 3, 210 (1959). Michie, D. , Research Memorandum MIP-R-29, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968). Burstall, R. M. , and Popplestone, R. J. , Machine Intelligence 2 (edit. by Dale, E., and Michie, D.), 207 (Oliver and Boyd, Edinburgh, 1968); POP-2 Papers (Oliver and Boyd, Edinburgh, 1968). Popplestone, R. J. , Research Memorandum MIP-R-30, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968). Michie, D. , and Chambers, R. A. , Machine Intelligence 2 (edit. by Dale, E., and Michie, D.), 137 (Oliver and Boyd, Edinburgh, 1968). Michie, D. , and Chambers, R. A. , Experimental Programming Reports : No. 14, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968); in Towards a Theoretical Biology (edit. by Waddington, C. H.), 1 (Edinburgh University Press) (in the press). Donaldson, P. E. K. , Proc. Third Intern. Conf. Medical Electronics, 173 (1960). Eastwood, E. , Proc. I.E.E., 115, 203 (1968). Zeeman, E. C. , and Buneman, O. P. , Towards a Theoretical Biology (edit. by Waddington, C. H.), 1, 140 (Edinburgh University Press, 1968). Fredkin, E. , in The Programming Language LISP : Its Operation and Applications (edit. by Berkeley, E. C., and Bobrow, D. G.) (MIT Press, 1964). Pivar, M. , and Finkelstein, M. , in The Programming Language LISP : Its Operation and Applications (edit. by Berkeley, E. C., and Bobrow, D. G.) (MIT Press, 1964). This was cheerfuly copied & pasted from http://www.nature.com/nature/journal/v218/n5136/abs/218019a0.html Suggest to check Knuth's TAOCP. Best, jj
Found it! (I've been trying to find this reference for several months.) Hilden, J. "Elimination of recursive calls using a small table of randomly selected function values." BIT 16,1 (1976), 60-73. I'm sure Hilden's wasn't the first memo implementation which forgot some entries, but Hilden's paper focused on this particular issue the best. At 07:43 AM 3/9/2013, Joerg Arndt wrote:
* Henry Baker <hbaker1@pipeline.com> [Mar 09. 2013 16:22]:
[...]
We now note that it doesn't harm performance "too" much if we sometimes forget a particular result and have to recompute it; this is somewhat akin to a "page fault" in a virtual memory system.
There are very many ways this could be made precise...
In fact, for many applications, a finite, fixed-size "memo table" is often good enough for government work.
For some definition of "many" and "enough".
Question: does anyone here have an academic _reference_ for this last statement that a fixed-size memo table is good enough?
I seem to recall reading a short paper (in English) from the 1960's or 1970's which made precisely this point about fixed-size memo tables.
[...]
Cormen et al., Introduction to Algorithms, (2nd ed.) doesn't seem to give a single reference about memoization.
A few "old enough" ones may be
Samuel, A. L. , IBM J. Res. Dev., 3, 210 (1959).
Michie, D. , Research Memorandum MIP-R-29, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968).
Burstall, R. M. , and Popplestone, R. J. , Machine Intelligence 2 (edit. by Dale, E., and Michie, D.), 207 (Oliver and Boyd, Edinburgh, 1968); POP-2 Papers (Oliver and Boyd, Edinburgh, 1968).
Popplestone, R. J. , Research Memorandum MIP-R-30, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968).
Michie, D. , and Chambers, R. A. , Machine Intelligence 2 (edit. by Dale, E., and Michie, D.), 137 (Oliver and Boyd, Edinburgh, 1968).
Michie, D. , and Chambers, R. A. , Experimental Programming Reports : No. 14, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968); in Towards a Theoretical Biology (edit. by Waddington, C. H.), 1 (Edinburgh University Press) (in the press).
Donaldson, P. E. K. , Proc. Third Intern. Conf. Medical Electronics, 173 (1960). Eastwood, E. , Proc. I.E.E., 115, 203 (1968).
Zeeman, E. C. , and Buneman, O. P. , Towards a Theoretical Biology (edit. by Waddington, C. H.), 1, 140 (Edinburgh University Press, 1968).
Fredkin, E. , in The Programming Language LISP : Its Operation and Applications (edit. by Berkeley, E. C., and Bobrow, D. G.) (MIT Press, 1964).
Pivar, M. , and Finkelstein, M. , in The Programming Language LISP : Its Operation and Applications (edit. by Berkeley, E. C., and Bobrow, D. G.) (MIT Press, 1964).
This was cheerfuly copied & pasted from http://www.nature.com/nature/journal/v218/n5136/abs/218019a0.html
Suggest to check Knuth's TAOCP.
Best, jj
A very recent paper on this is "Selective Memoization" http://arxiv.org/pdf/1106.0447.pdf which gives lots of other references. Victor On Sat, Mar 9, 2013 at 11:36 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Found it! (I've been trying to find this reference for several months.)
Hilden, J. "Elimination of recursive calls using a small table of randomly selected function values." BIT 16,1 (1976), 60-73.
I'm sure Hilden's wasn't the first memo implementation which forgot some entries, but Hilden's paper focused on this particular issue the best.
At 07:43 AM 3/9/2013, Joerg Arndt wrote:
* Henry Baker <hbaker1@pipeline.com> [Mar 09. 2013 16:22]:
[...]
We now note that it doesn't harm performance "too" much if we sometimes forget a particular result and have to recompute it; this is somewhat akin to a "page fault" in a virtual memory system.
There are very many ways this could be made precise...
In fact, for many applications, a finite, fixed-size "memo table" is often good enough for government work.
For some definition of "many" and "enough".
Question: does anyone here have an academic _reference_ for this last statement that a fixed-size memo table is good enough?
I seem to recall reading a short paper (in English) from the 1960's or 1970's which made precisely this point about fixed-size memo tables.
[...]
Cormen et al., Introduction to Algorithms, (2nd ed.) doesn't seem to give a single reference about memoization.
A few "old enough" ones may be
Samuel, A. L. , IBM J. Res. Dev., 3, 210 (1959).
Michie, D. , Research Memorandum MIP-R-29, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968).
Burstall, R. M. , and Popplestone, R. J. , Machine Intelligence 2 (edit. by Dale, E., and Michie, D.), 207 (Oliver and Boyd, Edinburgh, 1968); POP-2 Papers (Oliver and Boyd, Edinburgh, 1968).
Popplestone, R. J. , Research Memorandum MIP-R-30, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968).
Michie, D. , and Chambers, R. A. , Machine Intelligence 2 (edit. by Dale, E., and Michie, D.), 137 (Oliver and Boyd, Edinburgh, 1968).
Michie, D. , and Chambers, R. A. , Experimental Programming Reports : No. 14, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968); in Towards a Theoretical Biology (edit. by Waddington, C. H.), 1 (Edinburgh University Press) (in the press).
Donaldson, P. E. K. , Proc. Third Intern. Conf. Medical Electronics, 173 (1960). Eastwood, E. , Proc. I.E.E., 115, 203 (1968).
Zeeman, E. C. , and Buneman, O. P. , Towards a Theoretical Biology (edit. by Waddington, C. H.), 1, 140 (Edinburgh University Press, 1968).
Fredkin, E. , in The Programming Language LISP : Its Operation and Applications (edit. by Berkeley, E. C., and Bobrow, D. G.) (MIT Press, 1964).
Pivar, M. , and Finkelstein, M. , in The Programming Language LISP : Its Operation and Applications (edit. by Berkeley, E. C., and Bobrow, D. G.) (MIT Press, 1964).
This was cheerfuly copied & pasted from http://www.nature.com/nature/journal/v218/n5136/abs/218019a0.html
Suggest to check Knuth's TAOCP.
Best, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Of course, "memoization" is a silly neologism, redolent of 1950's office work ;-) when I teach this subject, I use the perfectly good word "memorization". Cris Moore Cristopher Moore Professor, Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/ On Mar 9, 2013, at 10:24 AM, Victor Miller wrote:
A very recent paper on this is "Selective Memoization" http://arxiv.org/pdf/1106.0447.pdf which gives lots of other references.
Victor
On Sat, Mar 9, 2013 at 11:36 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Found it! (I've been trying to find this reference for several months.)
Hilden, J. "Elimination of recursive calls using a small table of randomly selected function values." BIT 16,1 (1976), 60-73.
I'm sure Hilden's wasn't the first memo implementation which forgot some entries, but Hilden's paper focused on this particular issue the best.
At 07:43 AM 3/9/2013, Joerg Arndt wrote:
* Henry Baker <hbaker1@pipeline.com> [Mar 09. 2013 16:22]:
[...]
We now note that it doesn't harm performance "too" much if we sometimes forget a particular result and have to recompute it; this is somewhat akin to a "page fault" in a virtual memory system.
There are very many ways this could be made precise...
In fact, for many applications, a finite, fixed-size "memo table" is often good enough for government work.
For some definition of "many" and "enough".
Question: does anyone here have an academic _reference_ for this last statement that a fixed-size memo table is good enough?
I seem to recall reading a short paper (in English) from the 1960's or 1970's which made precisely this point about fixed-size memo tables.
[...]
Cormen et al., Introduction to Algorithms, (2nd ed.) doesn't seem to give a single reference about memoization.
A few "old enough" ones may be
Samuel, A. L. , IBM J. Res. Dev., 3, 210 (1959).
Michie, D. , Research Memorandum MIP-R-29, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968).
Burstall, R. M. , and Popplestone, R. J. , Machine Intelligence 2 (edit. by Dale, E., and Michie, D.), 207 (Oliver and Boyd, Edinburgh, 1968); POP-2 Papers (Oliver and Boyd, Edinburgh, 1968).
Popplestone, R. J. , Research Memorandum MIP-R-30, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968).
Michie, D. , and Chambers, R. A. , Machine Intelligence 2 (edit. by Dale, E., and Michie, D.), 137 (Oliver and Boyd, Edinburgh, 1968).
Michie, D. , and Chambers, R. A. , Experimental Programming Reports : No. 14, Dept. Machine Intelligence and Perception (Edinburgh Univ., 1968); in Towards a Theoretical Biology (edit. by Waddington, C. H.), 1 (Edinburgh University Press) (in the press).
Donaldson, P. E. K. , Proc. Third Intern. Conf. Medical Electronics, 173 (1960). Eastwood, E. , Proc. I.E.E., 115, 203 (1968).
Zeeman, E. C. , and Buneman, O. P. , Towards a Theoretical Biology (edit. by Waddington, C. H.), 1, 140 (Edinburgh University Press, 1968).
Fredkin, E. , in The Programming Language LISP : Its Operation and Applications (edit. by Berkeley, E. C., and Bobrow, D. G.) (MIT Press, 1964).
Pivar, M. , and Finkelstein, M. , in The Programming Language LISP : Its Operation and Applications (edit. by Berkeley, E. C., and Bobrow, D. G.) (MIT Press, 1964).
This was cheerfuly copied & pasted from http://www.nature.com/nature/journal/v218/n5136/abs/218019a0.html
Suggest to check Knuth's TAOCP.
Best, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Cris Moore -
Henry Baker -
Joerg Arndt -
Victor Miller