I'm running OpenMCL on Mac OS X on an older PowerBook. Consider the
following function, taken from Godel, Escher, Bach:
(defun q (n)
(if (< n 1)
(error "argument to q(n) < 1")
(if (< n 3)
1
(+ (q (- n (q (1- n)))) (q (- n (q (- n 2))))))))
(q 50) takes longer to compute than I care to wait.
So, remembering the lectures on SICP, I write memo to memoize a function
which takes a single argument:
(defun memo (fn)
(let ((table (make-hash-table :test 'equal)))
(lambda (n)
(multiple-value-bind (result foundp) (gethash n table)
(if foundp
result
(setf (gethash n table) (funcall fn n)))))))
The problem with this is that the (funcall fn n) in the last line
doesn't go through the hash table, so that
(funcall (memo 'q) 50)
still takes "forever".
So I pull out Norvig and see that the trick is to use setf and
symbol-function:
(defun memoize (fn-name)
(setf (symbol-function fn-name) (memo (symbol-function fn-name))))
Yet
(memomize 'q)
(q 50)
still takes "forever", as if (funcall fn n) still doesn't go through the
memoized routine (a brute-force memoization implementation returns the
answer immediately).
Any suggestions?
Partly answering my own question, this code works with SBCL and
LispWorks personal edition.
Is this a bug in OpenMCL?
Bob Felts <····@stablecross.com> wrote:
> I'm running OpenMCL on Mac OS X on an older PowerBook. Consider the
> following function, taken from Godel, Escher, Bach:
>
> (defun q (n)
> (if (< n 1)
> (error "argument to q(n) < 1")
> (if (< n 3)
> 1
> (+ (q (- n (q (1- n)))) (q (- n (q (- n 2))))))))
>
> (q 50) takes longer to compute than I care to wait.
>
> So, remembering the lectures on SICP, I write memo to memoize a function
> which takes a single argument:
>
> (defun memo (fn)
> (let ((table (make-hash-table :test 'equal)))
> (lambda (n)
> (multiple-value-bind (result foundp) (gethash n table)
> (if foundp
> result
> (setf (gethash n table) (funcall fn n)))))))
>
> The problem with this is that the (funcall fn n) in the last line
> doesn't go through the hash table, so that
>
> (funcall (memo 'q) 50)
>
> still takes "forever".
>
> So I pull out Norvig and see that the trick is to use setf and
> symbol-function:
>
> (defun memoize (fn-name)
> (setf (symbol-function fn-name) (memo (symbol-function fn-name))))
>
> Yet
> (memomize 'q)
> (q 50)
>
> still takes "forever", as if (funcall fn n) still doesn't go through the
> memoized routine (a brute-force memoization implementation returns the
> answer immediately).
>
> Any suggestions?
>
>
Bob Felts <····@stablecross.com> wrote:
> Partly answering my own question, this code works with SBCL and
> LispWorks personal edition.
>
> Is this a bug in OpenMCL?
No. CLHS 3.2.2.3:
: 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.
--
Juho Snellman
Juho Snellman <······@iki.fi> wrote:
> Bob Felts <····@stablecross.com> wrote:
> > Partly answering my own question, this code works with SBCL and
> > LispWorks personal edition.
> >
> > Is this a bug in OpenMCL?
>
> No. CLHS 3.2.2.3:
>
> : 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.
That did the trick. Thanks.
····@stablecross.com (Bob Felts) writes:
> I'm running OpenMCL on Mac OS X on an older PowerBook. Consider the
> following function, taken from Godel, Escher, Bach:
>
> (defun q (n)
> (if (< n 1)
> (error "argument to q(n) < 1")
> (if (< n 3)
> 1
> (+ (q (- n (q (1- n)))) (q (- n (q (- n 2))))))))
>
> (q 50) takes longer to compute than I care to wait.
> [...]
> So I pull out Norvig and see that the trick is to use setf and
> symbol-function:
>
> (defun memoize (fn-name)
> (setf (symbol-function fn-name) (memo (symbol-function fn-name))))
>
> Yet
> (memomize 'q)
> (q 50)
>
> still takes "forever", as if (funcall fn n) still doesn't go through the
> memoized routine (a brute-force memoization implementation returns the
> answer immediately).
>
> Any suggestions?
(asdf:oos 'asdf:load-op :memoize)
; loading system definition from /usr/local/asdf-install/site-systems/memoize.asd into #<PACKAGE ASDF0>
;; Loading file /usr/local/asdf-install/site-systems/memoize.asd ...
; registering #<SYSTEM MEMOIZE #x2052F376> as MEMOIZE
;; Loaded file /usr/local/asdf-install/site-systems/memoize.asd
;; Compiling file /a6/asdf-install/site/memoize-1.6/memoize.lisp ...
;; Wrote file /a6/asdf-install/site/memoize-1.6/OBJ-CLISP-239-I686/memoize.fas
;; Loading file /a6/asdf-install/site/memoize-1.6/OBJ-CLISP-239-I686/memoize.fas ...
;; Loaded file /a6/asdf-install/site/memoize-1.6/OBJ-CLISP-239-I686/memoize.fas
0 errors, 0 warnings
NIL
[80]> (defun q (n)
(if (< n 1)
(error "argument to q(n) < 1")
(if (< n 3)
1
(+ (q (- n (q (1- n)))) (q (- n (q (- n 2))))))))
Q
[83]> (memoize:memoize-function 'q)
Q
[85]> (time (q 50))
Real time: 2.3E-5 sec.
Run time: 0.0 sec.
Space: 8 Bytes
25
[86]>
--
__Pascal Bourguignon__ http://www.informatimago.com/
"This statement is false." In Lisp: (defun Q () (eq nil (Q)))
Pascal Bourguignon <···@informatimago.com> wrote:
> ····@stablecross.com (Bob Felts) writes:
>
> > I'm running OpenMCL on Mac OS X on an older PowerBook. Consider the
> > following function, taken from Godel, Escher, Bach:
> >
> > (defun q (n)
> > (if (< n 1)
> > (error "argument to q(n) < 1")
> > (if (< n 3)
> > 1
> > (+ (q (- n (q (1- n)))) (q (- n (q (- n 2))))))))
> >
> > (q 50) takes longer to compute than I care to wait.
> > [...]
> > So I pull out Norvig and see that the trick is to use setf and
> > symbol-function:
> >
> > (defun memoize (fn-name)
> > (setf (symbol-function fn-name) (memo (symbol-function fn-name))))
> >
> > Yet
> > (memomize 'q)
> > (q 50)
> >
> > still takes "forever", as if (funcall fn n) still doesn't go through the
> > memoized routine (a brute-force memoization implementation returns the
> > answer immediately).
> >
> > Any suggestions?
>
>
> (asdf:oos 'asdf:load-op :memoize)
Well, yes; I could load some code to do this. But I want to write code
as much as I study it. In my follow up post, I noted that this code
worked in LispWorks and SBCL but not OpenMCL. Is this a bug in OpenMCL,
or is this a "Lispism" that I need to know about?