Peter Norvig in his book (PAIP) suggests a function that replaces a
named function with a memozied one, but, contrary to his opinion, that
won't work -- only the first call will be memoized, and recursive ones
will not.
Is there a way to make it work -- that is, to redefine all calls to a
function, including recursive ones, with memoizable?
·············@gmail.com" <············@gmail.com> writes:
> Peter Norvig in his book (PAIP) suggests a function that replaces a
> named function with a memozied one, but, contrary to his opinion, that
> won't work -- only the first call will be memoized, and recursive ones
> will not.
That's certainly not true in general (see below for an example),
but of course it depends on whether your compiler has e.g.
optimized away function calls.
Can you give us some more details?
USER 22 > (defun gazonk (n)
(format t "Gazonk!~%")
(if (= n 0)
:gazonk
(cons (gazonk (1- n))(gazonk (1- n)))))
GAZONK
USER 23 > (compile *)
GAZONK
NIL
NIL
USER 24 > (gazonk 2)
Gazonk!
Gazonk!
Gazonk!
Gazonk!
Gazonk!
Gazonk!
Gazonk!
((:GAZONK . :GAZONK) :GAZONK . :GAZONK)
USER 25 > (memo:memoize 'gazonk)
#<closure (HARLEQUIN-COMMON-LISP:SUBFUNCTION 1 MEMOIZE:MEMO) 2263CFCA>
USER 26 > (gazonk 2)
Gazonk!
Gazonk!
Gazonk!
((:GAZONK . :GAZONK) :GAZONK . :GAZONK)
USER 27 > (gazonk 2)
((:GAZONK . :GAZONK) :GAZONK . :GAZONK)
USER 28 >
--
(espen)
Espen Vestre <·····@vestre.net> writes:
> USER 22 > (defun gazonk (n)
> (format t "Gazonk!~%")
What about TRACE? Delete this format, and
> (if (= n 0)
> :gazonk
> (cons (gazonk (1- n))(gazonk (1- n)))))
> GAZONK
(trace gazonk)
(gazonk 2)
(memo:memoize 'gazonk)
(trace gazonk)
(gazonk 2)
--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay
············@gmail.com wrote:
> Peter Norvig in his book (PAIP) suggests a function that replaces a
> named function with a memozied one, but, contrary to his opinion, that
> won't work -- only the first call will be memoized, and recursive ones
> will not.
>
> Is there a way to make it work -- that is, to redefine all calls to a
> function, including recursive ones, with memoizable?
>
The same question puzzled me when I worked with Friedman's SAP, where he
actually fiddles with the code of the function to be memoized. The
solution (at least in Scheme) is much simpler. Just assign the memoized
function to old name, as in:
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
(define (memoize f)
(let ((cache '()))
(lambda args
(let ((v (assoc args cache)))
(if v
(cadr v)
(let ((v (apply f args)))
(set! cache (cons (list args v) cache))
v))))))
If you now do: (set! fib (memoize fib)) , all calls to fib are
memoized--which is easily tested by running (fib 100).
This, I guess is easily translated into CL
-- Hrvoje
·············@gmail.com" <············@gmail.com> writes:
> Is there a way to make it work -- that is, to redefine all calls to a
> function, including recursive ones, with memoizable?
The CLHS proclaims:
3.2.2.3 Semantic Constraints
[...]
• Within a function named F, the compiler may (but is not required
to) assume that an apparent recursive call to a function named F
refers to the same definition of F, unless that function has been
declared notinline. [...]
In other words, write your recursive function like this:
(defun my-recursive-function-to-be-memoized (...)
(declare (notinline my-recursive-function-to-be-memoized))
...)
and memoization should work so long as your CL is conformant.
--
Frode Vatvedt Fjeld
> In other words, write your recursive function like this:
>
> (defun my-recursive-function-to-be-memoized (...)
> (declare (notinline my-recursive-function-to-be-memoized))
> ...)
That's it, thank you for the hint.
·············@gmail.com" <············@gmail.com> writes:
>> In other words, write your recursive function like this:
>>
>> (defun my-recursive-function-to-be-memoized (...)
>> (declare (notinline my-recursive-function-to-be-memoized))
>> ...)
>
> That's it, thank you for the hint.
Btw, you can automate things a bit more, so you don't need to insert
that declaration manually:
(defun compile-and-memoize (function-name)
(assert (fboundp function-name))
(proclaim `(notinline ,function-name))
(setf (symbol-function function-name)
(memoize (compile function-name))))
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld wrote:
> ·············@gmail.com" <············@gmail.com> writes:
>
> >> In other words, write your recursive function like this:
> Btw, you can automate things a bit more, so you don't need to insert
> that declaration manually:
>
> (defun compile-and-memoize (function-name)
> (assert (fboundp function-name))
> (proclaim `(notinline ,function-name))
> (setf (symbol-function function-name)
> (memoize (compile function-name))))
No, this won't work. This way, the memoizer will also call the function
through the entry table, and the function in the entry table will be
wrapped into the memoizer, and there will be an infinite loop and stack
overflow. Lispworks, lisp, clisp confirm this.