The following code which is suppose to memoize the fibinacci function
from Norvig's PAIIP doesn't seem to work on MCL 4.3 on a powermac G4 400Mhz.
(The code is almost exactly the same)
(defun memoize (fn)
(setf (symbol-function fn) (memo (symbol-function fn))))
(defun memo (fn)
(let ((table (make-hash-table)))
#'(lambda (arg)
(multiple-value-bind (val ok) (gethash arg table)
(if ok
val
(setf (gethash arg table) (funcall fn arg)))))))
(defun fib (n)
(cond ((eql n 1) 1)
((eql n 2) 1)
(t
(+ (fib (- n 1)) (fib (- n 2))))))
I tried compiling and loading the pfsl file. If I do
(memo 'fib)
then try
(fib 40)
I takes a while
If I try (fib 41) it takes even longer.
Can anyone help?
In article <············@slb2.atl.mindspring.net>, "Scott McIntire"
<········@mindspring.com> wrote:
> I tried compiling and loading the pfsl file. If I do
> (memo 'fib)
use: (memoize 'fib)
> then try
> (fib 40)
> I takes a while
> If I try (fib 41) it takes even longer.
>
> Can anyone help?
>
>
? (memoize 'fib)
#<COMPILED-LEXICAL-CLOSURE #x98501DE>
? (time (fib 40))
(FIB 40) took 0 milliseconds (0.000 seconds) to run.
102334155
?
Rainer Joswig, ISION Internet AG, Harburger Schlossstrasse 1,
21079 Hamburg, Germany, Tel: +49 40 77175 226
Email: ·············@ision.de , WWW: http://www.ision.de/
Thanks for the response.
I apologize, I mis-posted, I meant (memoize 'fib)
Bit I still have the problem. After doing (memoize 'fib)
I have the following commands/results:
? (time (fib 35))
(FIB 35) took 1,903 milliseconds (1.903 seconds) to run.
Of that, 178 milliseconds (0.178 seconds) were spent in The Cooperative
Multitasking Experience.
9227465
? (time (fib 36))
(FIB 36) took 2,962 milliseconds (2.962 seconds) to run.
And yes, if I later do (fib 35) or (fib 36) it will take 0.00 seconds to
compute. This is what memo would allow; however, memoize should do more:
as the computation proceeds (fib 35) calls (fib 34) (fib 33) and these also
should be stored in the hash table. When (fib 35) is done all fibinocci
numbers from 1 to 35 should be stored in the lexical closure fib.
So, (fib 36) should be quick - its not.
What went wrong!
----------
In article <···································@news.is-europe.net>, Rainer
Joswig <·············@ision.de> wrote:
> In article <············@slb2.atl.mindspring.net>, "Scott McIntire"
> <········@mindspring.com> wrote:
>
>> I tried compiling and loading the pfsl file. If I do
>> (memo 'fib)
>
> use: (memoize 'fib)
>
>> then try
>> (fib 40)
>> I takes a while
>> If I try (fib 41) it takes even longer.
>>
>> Can anyone help?
>>
>>
>
> ? (memoize 'fib)
> #<COMPILED-LEXICAL-CLOSURE #x98501DE>
>
> ? (time (fib 40))
> (FIB 40) took 0 milliseconds (0.000 seconds) to run.
> 102334155
>
> ?
>
> Rainer Joswig, ISION Internet AG, Harburger Schlossstrasse 1,
> 21079 Hamburg, Germany, Tel: +49 40 77175 226
> Email: ·············@ision.de , WWW: http://www.ision.de/
(fib 35) calls (fib 33) as well, not just (fib 34).
Good luck,
Tunc
On Sun, 12 Mar 2000, Scott McIntire wrote:
> Thanks for the response.
>
> I apologize, I mis-posted, I meant (memoize 'fib)
> Bit I still have the problem. After doing (memoize 'fib)
>
> I have the following commands/results:
>
> ? (time (fib 35))
> (FIB 35) took 1,903 milliseconds (1.903 seconds) to run.
> Of that, 178 milliseconds (0.178 seconds) were spent in The Cooperative
> Multitasking Experience.
> 9227465
> ? (time (fib 36))
> (FIB 36) took 2,962 milliseconds (2.962 seconds) to run.
>
>
> And yes, if I later do (fib 35) or (fib 36) it will take 0.00 seconds to
> compute. This is what memo would allow; however, memoize should do more:
> as the computation proceeds (fib 35) calls (fib 34) (fib 33) and these also
> should be stored in the hash table. When (fib 35) is done all fibinocci
> numbers from 1 to 35 should be stored in the lexical closure fib.
> So, (fib 36) should be quick - its not.
>
> What went wrong!
>
>
>
>
> ----------
> In article <···································@news.is-europe.net>, Rainer
> Joswig <·············@ision.de> wrote:
>
>
> > In article <············@slb2.atl.mindspring.net>, "Scott McIntire"
> > <········@mindspring.com> wrote:
> >
> >> I tried compiling and loading the pfsl file. If I do
> >> (memo 'fib)
> >
> > use: (memoize 'fib)
> >
> >> then try
> >> (fib 40)
> >> I takes a while
> >> If I try (fib 41) it takes even longer.
> >>
> >> Can anyone help?
> >>
> >>
> >
> > ? (memoize 'fib)
> > #<COMPILED-LEXICAL-CLOSURE #x98501DE>
> >
> > ? (time (fib 40))
> > (FIB 40) took 0 milliseconds (0.000 seconds) to run.
> > 102334155
> >
> > ?
> >
> > Rainer Joswig, ISION Internet AG, Harburger Schlossstrasse 1,
> > 21079 Hamburg, Germany, Tel: +49 40 77175 226
> > Email: ·············@ision.de , WWW: http://www.ision.de/
>
>
* Scott McIntire wrote:
> And yes, if I later do (fib 35) or (fib 36) it will take 0.00 seconds to
> compute. This is what memo would allow; however, memoize should do more:
> as the computation proceeds (fib 35) calls (fib 34) (fib 33) and these also
> should be stored in the hash table. When (fib 35) is done all fibinocci
> numbers from 1 to 35 should be stored in the lexical closure fib.
> So, (fib 36) should be quick - its not.
The compiler is probably doing a non-full function call for the
recursion, and thus the memoization is not helping. You should be
able to see this by disassembling the function.
You can avoid this and related optimizations like tail-call
elimination by declaring the function NOTINLINE. I posted some code
here a while ago which had a memoized-function definer which did just
this.
--tim
In article <············@slb0.atl.mindspring.net>, "Scott McIntire" <········@mindspring.com> wrote:
> And yes, if I later do (fib 35) or (fib 36) it will take 0.00 seconds to
> compute. This is what memo would allow; however, memoize should do more:
> as the computation proceeds (fib 35) calls (fib 34) (fib 33) and these also
> should be stored in the hash table. When (fib 35) is done all fibinocci
> numbers from 1 to 35 should be stored in the lexical closure fib.
> So, (fib 36) should be quick - its not.
>
> What went wrong!
try this,
(let ((ccl::*nx-never-tail-call* (list 'fib)))
(defun fib (n)
(cond ((eql n 1) 1)
((eql n 2) 1)
(t
(+ (fib (- n 1)) (fib (- n 2)))))))
(memoize 'fib)
regards,
abe
Keke Abe wrote:
>
> In article <············@slb0.atl.mindspring.net>, "Scott McIntire" <········@mindspring.com> wrote:
...
> > What went wrong!
MCL's compiler will automagically turn the recursive definition
of fib into an iterative, tail-optimized version. ( since positive
integer ops are commutative this is OK).
So the pre-memoized function FIB is only called once. Thus,
the memoized facade is bypassed during the computation.
> (let ((ccl::*nx-never-tail-call* (list 'fib)))
> (defun fib (n)
> (cond ((eql n 1) 1)
> ((eql n 2) 1)
> (t
> (+ (fib (- n 1)) (fib (- n 2)))))))
Alternatively, you can say
(defun fib (n )
(declare (notinline fib ))
.... )
Which will effectively do what the above does without
refering to the MCL specific internal variable and does away
with the enclosing LET. Regardless, You have to tell the compiler
"don't do that magic that you do". :-)
Lyman
----------
In article <·················@mindspring.com>, "Lyman S. Taylor"
<············@mindspring.com> wrote:
> Keke Abe wrote:
>>
>> In article <············@slb0.atl.mindspring.net>, "Scott McIntire"
> <········@mindspring.com> wrote:
> ...
>> > What went wrong!
>
> MCL's compiler will automagically turn the recursive definition
> of fib into an iterative, tail-optimized version. ( since positive
> integer ops are commutative this is OK).
> So the pre-memoized function FIB is only called once. Thus,
> the memoized facade is bypassed during the computation.
>
>> (let ((ccl::*nx-never-tail-call* (list 'fib)))
>> (defun fib (n)
>> (cond ((eql n 1) 1)
>> ((eql n 2) 1)
>> (t
>> (+ (fib (- n 1)) (fib (- n 2)))))))
>
fib is not written as a tail recursive function, so I'm suprised that the
compiler will turn it into iteration.
> Alternatively, you can say
>
> (defun fib (n )
> (declare (notinline fib ))
> .... )
>
> Which will effectively do what the above does without
> refering to the MCL specific internal variable and does away
> with the enclosing LET. Regardless, You have to tell the compiler
> "don't do that magic that you do". :-)
>
>
> Lyman
Thanks, much appreciated.
-Scott McIntire
In article <············@slb0.atl.mindspring.net>, "Scott McIntire"
<········@mindspring.com> wrote:
> > Alternatively, you can say
> >
> > (defun fib (n )
> > (declare (notinline fib ))
> > .... )
> >
> > Which will effectively do what the above does without
> > refering to the MCL specific internal variable and does away
> > with the enclosing LET. Regardless, You have to tell the compiler
> > "don't do that magic that you do". :-)
Actually it has nothing to do with INLINING. INLINING is a different
concept and means code inlining.
What you could do is use a different level for the DEBUG
optimization value. Consult the MCL manual.
> >
> >
> > Lyman
>
> Thanks, much appreciated.
>
> -Scott McIntire
>
Rainer Joswig, ISION Internet AG, Harburger Schlossstrasse 1,
21079 Hamburg, Germany, Tel: +49 40 77175 226
Email: ·············@ision.de , WWW: http://www.ision.de/
In article <···································@news.is-europe.net>,
Rainer Joswig <·············@ision.de> wrote:
>In article <············@slb0.atl.mindspring.net>, "Scott McIntire"
><········@mindspring.com> wrote:
>> > Alternatively, you can say
>> >
>> > (defun fib (n )
>> > (declare (notinline fib ))
>> > .... )
>> >
>> > Which will effectively do what the above does without
>> > refering to the MCL specific internal variable and does away
>> > with the enclosing LET. Regardless, You have to tell the compiler
>> > "don't do that magic that you do". :-)
>Actually it has nothing to do with INLINING. INLINING is a different
>concept and means code inlining.
Actually, it does have something to do with inlining, because the
notinline declaration does indeed make the example work as intended in
MCL 4.3. The difference in timing is hard to miss; it's a factor of
around 300 for (fib 40).
--
Dave Seaman ·······@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://mojo.calyx.net/~refuse/mumia/021700amnesty.html>
* Rainer Joswig wrote:
> Actually it has nothing to do with INLINING. INLINING is a different
> concept and means code inlining.
Yes, but one of the things that a NOTINLINE declaration means is that
you can't short-circuit self-calls (section 3.2.2.3).
--tim
In article <···············@cley.com>, Tim Bradshaw <···@cley.com>
wrote:
> * Rainer Joswig wrote:
>
> > Actually it has nothing to do with INLINING. INLINING is a different
> > concept and means code inlining.
>
> Yes, but one of the things that a NOTINLINE declaration means is that
> you can't short-circuit self-calls (section 3.2.2.3).
Where is that in ANSI CL? ANSI CL says nothing about
this stuff, IIRC. It is just an accident that it behaves
in MCL that way, I guess. It's documented, but I think it's
kind of a misuse of the INLINE declaration.
Rainer Joswig, ISION Internet AG, Harburger Schlossstra�e 1,
21079 Hamburg, Germany, Tel: +49 40 77175 226
Email: ·············@ision.de , WWW: http://www.ision.de/
Rainer Joswig <·············@ision.de> writes:
> In article <···············@cley.com>, Tim Bradshaw <···@cley.com>
> wrote:
> > Yes, but one of the things that a NOTINLINE declaration means is that
> > you can't short-circuit self-calls (section 3.2.2.3).
>
> Where is that in ANSI CL? ANSI CL says nothing about
> this stuff, IIRC.
Actually, right in section 3.2.2.3, although perhaps not quite so
directly:
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. The consequences of redefining such a recursively defined
function F while it is executing are undefined.
This constraint would seem to imply that conforming compilers cannot do
tail-call elimination on functions declared NOTINLINE, since the
compiler is not allowed to assume that it is the same function.
BTW, what happened to the Hyperspec located at www.harlequin.com ? My
link to it took me to a different site named www.xanalys.com instead.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
>>>>> On 14 Mar 2000 15:41:10 -0800, Thomas A Russ ("Thomas") writes:
Thomas> BTW, what happened to the Hyperspec located at www.harlequin.com ? My
Thomas> link to it took me to a different site named www.xanalys.com instead.
Global Graphics acquired bankrupt Harlequin, and split off the
IT (knowledge tools, languages, etc.) part into "Xanalys".
So the Hyperspec is, naturally, located on he Xanalys web site.
···@sevak.isi.edu (Thomas A. Russ) writes:
> Actually, right in section 3.2.2.3, although perhaps not quite so
> directly:
>
> 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. The consequences of redefining such a recursively defined
> function F while it is executing are undefined.
>
> This constraint would seem to imply that conforming compilers cannot do
> tail-call elimination on functions declared NOTINLINE, since the
> compiler is not allowed to assume that it is the same function.
This wouldn't necessarily prohibit tail-call elimination; although
the compiler could not assume it was the same function, it can still
discard the current stack frame and replace the CALL with an indirect
JMP.
That section seems to imply that compilers are normally allowed to
skip indirection through the function cell of a symbol on an apparent
recursive call, but if the function is declared NOTINLINE, then the
indirection *must* (appear to) happen.
--
~jrm
Joe Marshall <·········@alum.mit.edu> writes:
> ···@sevak.isi.edu (Thomas A. Russ) writes:
>
> > Actually, right in section 3.2.2.3, although perhaps not quite so
> > directly:
[ ... ]
> This wouldn't necessarily prohibit tail-call elimination; although
> the compiler could not assume it was the same function, it can still
> discard the current stack frame and replace the CALL with an indirect
> JMP.
Correct.
> That section seems to imply that compilers are normally allowed to
> skip indirection through the function cell of a symbol on an apparent
> recursive call, but if the function is declared NOTINLINE, then the
> indirection *must* (appear to) happen.
Allegro CL interprets the spec this way as well.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
* Joe Marshall wrote:
> This wouldn't necessarily prohibit tail-call elimination; although
> the compiler could not assume it was the same function, it can still
> discard the current stack frame and replace the CALL with an indirect
> JMP.
I think that's right.
> That section seems to imply that compilers are normally allowed to
> skip indirection through the function cell of a symbol on an apparent
> recursive call, but if the function is declared NOTINLINE, then the
> indirection *must* (appear to) happen.
Fortunately this is just what you need to make memoizing work -- you
need to make sure that you go through the function cell because that's
the place you've stuffed the closure that does the memoization.
--tim
In article <···············@cley.com>, Tim Bradshaw <···@cley.com>
wrote:
> Fortunately this is just what you need to make memoizing work -- you
> need to make sure that you go through the function cell because that's
> the place you've stuffed the closure that does the memoization.
Thanks, for the clarification!
Rainer Joswig, ISION Internet AG, Harburger Schlossstra�e 1,
21079 Hamburg, Germany, Tel: +49 40 77175 226
Email: ·············@ision.de , WWW: http://www.ision.de/
Rainer Joswig wrote:
[Tim Bradshaw said:]
>> Yes, but one of the things that a NOTINLINE declaration means is that
>> you can't short-circuit self-calls (section 3.2.2.3).
>
> Where is that in ANSI CL? ANSI CL says nothing about
> this stuff, IIRC. It is just an accident that it behaves
> in MCL that way, I guess. It's documented, but I think it's
> kind of a misuse of the INLINE declaration.
Well, section 3.2.2.3 of the HyperSpec says
| * 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.
and
| * A call within a file to a named function that
| is defined in the same file refers to that function,
| unless that function has been declared notinline.
It seems to me that this indicates that with a NOTINLINE
declaration for function F, the compiler isn't supposed
to assume that calls to F inside F's definition will
always refer to that same definition of F. In other words,
it should arrange that redefining F will make those calls
refer to the new definition. Which is exactly what's needed
for things like memoizing to work.
--
Gareth McCaughan ················@pobox.com
sig under construction
* Rainer Joswig wrote:
> Where is that in ANSI CL? ANSI CL says nothing about
> this stuff, IIRC. It is just an accident that it behaves
> in MCL that way, I guess. It's documented, but I think it's
> kind of a misuse of the INLINE declaration.
In section 3.2.2.3 like I said:
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. The consequences of redefining such a
recursively defined function F while it is executing are
undefined.
--tim
Rainer Joswig wrote:
>
...
>
> Actually it has nothing to do with INLINING. INLINING is a different
> concept and means code inlining.
As others have pointed out, NOTINLINE means something more than the
"negation" of INLINE. It prohibits an assortment of clever tricks.
> What you could do is use a different level for the DEBUG
> optimization value. Consult the MCL manual.
1. Yes, you could also turn the compiler all the way off (or partially off)
That too will solve the problem. Personally, I prefer to keep
the compiler cranked up when I use MCL. You just have to communicate
with it from time to time. :-) Besides this should be portable
CL. Each implementation may vary as to which value of debug will turn
the tail optimization off. Additionally, cranking DEBUG up will
interfere with other nontail call related stuff.
2. Take a gander at the example on p.342 of the Macintosh Common
Lisp Reference Manual (MCL version 4.0, Chap 9's entry on TRACE) where NOTINLINE
to used to keep FACT from being optimized away for the trace example.
The MCL manual is where I first came across NOTINLINE. :-)
Lyman
Scott McIntire wrote:
...
> fib is not written as a tail recursive function, so I'm suprised that the
> compiler will turn it into iteration.
>
Believe me, you're not the only one. I used to be a TA for course in which we
had a lab that used the recursive FIB to talk about the output TRACE will give. When
we used MCL the answers in the lab would be FIB gets called once and spits out the
answer.... as opposed to what they were suppose to see. :-)
So each quarter I had to explain how MCL was "smarter than your average bear". :-)
And how to temporarily turn it off, with a magical "notinline" incantation.
Lyman