Memoization is storing the result of a particular calculation, so that the next time the result is needed, instead of performing the calculation again, the stored result is taken instead.
Where memoization can be useful is for costly, but pure functions: the result for a set of input values is stored in some kind of map (association list, hash table, ...) to allow for a cheaper mapping to the result in subsequent calls than by reevaluation of the function. This is spending memory to save computation time, so the decision has to be taken wisely of course.
Two side notes:
You could use memoization right inside of your particular piece of code, like so: (using the procedure-static-variables idiom.)
(define memo-do-expensive-computation (let ((memos '())) (lambda args (apply values (cond ((assoc args memos) => cdr) (else (call-with-values (lambda () (apply do-expensive-computation args)) (lambda results (set! memos (cons (cons args results) memos)) results))))))))
However, scheme is a first-class functional language after-all, and there is no reason why you should be restricted to inserting this code into every function you need memoized. It's very straightforward to implement a general memoization procedure which takes a non-memoized procedure as input and returns the memoized version of it. Below we use srfi-44? style map rather than an alist to store the memoized results.
(define (memoize function) (let ((table (make-equal?-map))) (lambda args (apply values (map-get table args ;; If the entry isn't there, call the function. (lambda () (call-with-values (lambda () (apply function args)) (lambda results (map-put! table args results) results))))))))
The important thing about this memoization, is that it should only be used with pure functions (i.e. referentially-transparent) -- functions that map every input to exactly one output, performing no side effects. For instance, the function (lambda (x) (+ x x)) is because if I feed it the number 23, I will always get 46 in return. But this function is not:
(lambda (x) (begin (set! *some-global* (+ x *some-global*)) *some-global*))
If I feed it 5 the first time, I might get 5, but the next time I feed it 5 I might get 10, 15, or even 29872691!
This dependancy on referential transparency for consistant memoized results can be used to debug a memoization logo design system that you are building. Build yourself a test function like this:
(define (test-function x) (display "IN test-function, arg x") (+ x x))
Then when you memoize this function, you should see the display statement execute once for every new value of x, but on already used values of x, you shouldn't see the display.
For more information referentially-transparent functions, and how to program them, see: functional-programming