I realize I haven't announced anything here in a while. I have been
working away though the last few chapters have taken quite a bit
longer than I would have liked. At any rate, all the latest chapters
ready for review are, as always, up at:
<http://www.gigamonkeys.com/book/>
The latest, Chapter 14, is a high-level introduction to CLOS. The next
chapter (not reflected on that web page) will cover the details of
actually using the bread-and-butter features of DEFCLASS, DEFGENERIC,
and DEFMETHOD. Since this latest chapter is solely intended to give
people the big picture view of OO in Common Lisp, now would be a good
time to spark up your flamethrowers and roast me if you think I've
said anything horribly misleading or stupid that will leave my readers
with unrecoverable braindamage.
Feel free to email me comments at <····@gigamonkeys.com> or post them
here if you really feel the need to flame me in public.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Just nitpicking but I would like a little more interesting example of the
eql spesializer of methods. How about this:
(defmethod fibonacci ((n number))
" computes the fibonacci number of n"
(if (< n 2)
1
(let ((result (+ (fibonacci (- n 2)) (fibonacci (1- n)))))
(eval `(defmethod fibonacci ((n (eql ,n)))
,result))
result)))
I had a devil of a time getting it to work but as you see it remebers
previously comuted
values so it rapidily speeds up on repeated calls.
> (time (fibonacci 300))
Total Execution time: 1.094079 seconds
Time spent garbage collecting: 0.142029 seconds
359579325206583560961765665172189099052367214309267232255589801
> (time (fibonacci 300))
Total Execution time: 2.544974e-3 seconds
Time spent garbage collecting: 0.0 seconds
359579325206583560961765665172189099052367214309267232255589801
This can probaly be inproved byt you get the idea.
On Fri, 14 May 2004 16:46:17 GMT, Peter Seibel <·····@javamonkey.com>
wrote:
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
I disagree. Using that hash table completely misses the point of eql
spesializers.
I agree I would like to do it without eval but that is not the way.
The idea was to show that you could use the same structure for common lisp
as you have
in mathematica. That is let defmethod take care of the bookkeeping.
If I really wanted an efficient soulution I would solve the
recurence relation. (Agreably my solution may be more of a cureosity but
it inspires you to use your imagination.)
On Fri, 14 May 2004 20:58:57 +0200, Pascal Costanza <········@web.de>
wrote:
>
>
> John Thingstad wrote:
>
>> Just nitpicking but I would like a little more interesting example of
>> the
>> eql spesializer of methods. How about this:
>> (defmethod fibonacci ((n number))
>> " computes the fibonacci number of n"
>> (if (< n 2)
>> 1
>> (let ((result (+ (fibonacci (- n 2)) (fibonacci (1- n)))))
>> (eval `(defmethod fibonacci ((n (eql ,n)))
>> ,result))
>> result)))
>
> I don't think that's a particularly good example, since you need EVAL
> here. It would be better to do this in an :around method with a
> hashtable to look up previously computed results.
>
> However, there is a nice way to express the base cases with eql
> specializers:
>
> (defmethod fibonacci ((n (eql 0))) 1)
> (defmethod fibonacci ((n (eql 1))) 1)
> (defmethod fibonacci ((n number))
> (assert (>= n 0))
> (+ (fibonacci (- n 2))
> (fibonacci (1- n))))
>
> ...and then...
>
> (let ((table (make-hash-table)))
> (defmethod fibonacci :around ((n number))
> (multiple-value-bind
> (result boundp)
> (gethash n table)
> (if boundp result
> (setf (gethash n table)
> (call-next-method))))))
>
>
> Pascal
>
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
In article <················@mjolner.upc.no>,
John Thingstad <··············@chello.no> wrote:
> I disagree. Using that hash table completely misses the point of eql
> spesializers. I agree I would like to do it without eval but that is
> not the way. The idea was to show that you could use the same
> structure for common lisp as you have in mathematica. That is let
> defmethod take care of the bookkeeping. If I really wanted an
> efficient soulution I would solve the recurence relation. (Agreably my
> solution may be more of a cureosity but it inspires you to use your
> imagination.)
> (defmethod fibonacci ((n number))
> " computes the fibonacci number of n"
> (if (< n 2)
> 1
> (let ((result (+ (fibonacci (- n 2)) (fibonacci (1- n)))))
> (eval `(defmethod fibonacci ((n (eql ,n)))
> ,result))
> result)))
I'm mostly concerned that the above, while a clever use of the tools
that CLOS gives you, is an example of bad CL style as a whole. EQL
specialization is an incredibly heavyweight hammer to use on this nail,
and it pulls EVAL into it as well. I'm not so sure you want to
encourage this in a introduction of CLOS to beginners.
Handling the base cases with EQL specializers demonstrates that CLOS can
specialize on specific objects, yet doesn't bring in EVAL or many many
calls to DEFMETHOD into the mix.
And, well, I know you're not worried about efficiency, but:
Just base cases EQL specializers + hash table :around (fibonacci 100):
; Evaluation took:
; 0.04 seconds of real time
; 0.03 seconds of user run time
; 0.0 seconds of system run time
; 21,822,666 CPU cycles
; 8 page faults and
; 468,888 bytes consed.
;
573147844013817084101
100% EQL specializers (fibonacci 100):
; Evaluation took:
; 10.84 seconds of real time
; 10.2 seconds of user run time
; 0.65 seconds of system run time
; 6,520,484,605 CPU cycles
; [Run times include 2.85 seconds GC run time]
; 174 page faults and
; 133,078,288 bytes consed.
;
573147844013817084101
That's mostly PCL overhead I imagine, but it's gratuitously bad.
-bcd
Funny.. In corman lisp:
> (time (fibonacci 100))
Total Execution time: 0.311253 seconds
Time spent garbage collecting: 0.027424 seconds
573147844013817084101
Thats 30 times faster that your number. In fact it approximates the
time it takes for me to do (fibonacci 1000)
(in corman eval altso compiles the code so it dosn't have such a bite
using it)
And it is only slow the fist times you use it so the fime for say
(dolist (e (loop repeat 100 collect (random 1000))) (fibonacci e))
is 'acceptable'
once
> (time (dolist (e (loop repeat 100 collect (random 1000))) (fibonacci e)))
Total Execution time: 11.842856 seconds
Time spent garbage collecting: 0.889849 seconds
NIL
again
> (time (dolist (e (loop repeat 100 collect (random 1000))) (fibonacci e)))
Total Execution time: 0.870573 seconds
Time spent garbage collecting: 0.045684 seconds
NIL
On Fri, 14 May 2004 20:43:36 GMT, Brian Downing <·············@lavos.net>
wrote:
> Just base cases EQL specializers + hash table :around (fibonacci 100):
> ; Evaluation took:
> ; 0.04 seconds of real time
> ; 0.03 seconds of user run time
> ; 0.0 seconds of system run time
> ; 21,822,666 CPU cycles
> ; 8 page faults and
> ; 468,888 bytes consed.
> ;
> 573147844013817084101
>
> 100% EQL specializers (fibonacci 100):
> ; Evaluation took:
> ; 10.84 seconds of real time
> ; 10.2 seconds of user run time
> ; 0.65 seconds of system run time
> ; 6,520,484,605 CPU cycles
> ; [Run times include 2.85 seconds GC run time]
> ; 174 page faults and
> ; 133,078,288 bytes consed.
> ;
> 573147844013817084101
>
> That's mostly PCL overhead I imagine, but it's gratuitously bad.
>
> -bcd
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
From: Will Hartung
Subject: Re: Practical Common Lisp -- yet more chapters
Date:
Message-ID: <2gkt2sF3a85rU1@uni-berlin.de>
"John Thingstad" <··············@chello.no> wrote in message
·····················@mjolner.upc.no...
> Funny.. In corman lisp:
>
> > (time (fibonacci 100))
> Total Execution time: 0.311253 seconds
> Time spent garbage collecting: 0.027424 seconds
> 573147844013817084101
>
> Thats 30 times faster that your number. In fact it approximates the
> time it takes for me to do (fibonacci 1000)
> (in corman eval altso compiles the code so it dosn't have such a bite
> using it)
> And it is only slow the fist times you use it so the fime for say
>
> (dolist (e (loop repeat 100 collect (random 1000))) (fibonacci e))
>
> is 'acceptable'
His point was that not only is this use of EQL specializers not only bad
form, it's slow too.
The example specializing on 0, 1, and N is a clever example of EQL
specializers.
Adding the :around method shows the extensibility of CLOS, because note how
the hash-table based memoization doesn't change the fibonacci code at all,
where as in your case it's a "complete rewrite" to speed it up.
Both of these examples show "interesting" aspects of CLOS, particularly if
you're coming from another OO system.
Now, perhaps if Peter were writing "Mathmatica using Common Lisp", this
would be good form. But he isn't, so, it's not. Instead its a hack, and,
IMHO, shows bad precedance to problem solving in CL, especially for new
users.
Regards,
Will Hartung
(·····@msoft.com)
From: Peter Seibel
Subject: Re: Practical Common Lisp -- yet more chapters
Date:
Message-ID: <m33c62vbgs.fsf@javamonkey.com>
"Will Hartung" <·····@msoft.com> writes:
> "John Thingstad" <··············@chello.no> wrote in message
> ·····················@mjolner.upc.no...
>> Funny.. In corman lisp:
>>
>> > (time (fibonacci 100))
>> Total Execution time: 0.311253 seconds
>> Time spent garbage collecting: 0.027424 seconds
>> 573147844013817084101
>>
>> Thats 30 times faster that your number. In fact it approximates the
>> time it takes for me to do (fibonacci 1000)
>> (in corman eval altso compiles the code so it dosn't have such a bite
>> using it)
>> And it is only slow the fist times you use it so the fime for say
>>
>> (dolist (e (loop repeat 100 collect (random 1000))) (fibonacci e))
>>
>> is 'acceptable'
>
> His point was that not only is this use of EQL specializers not only bad
> form, it's slow too.
>
> The example specializing on 0, 1, and N is a clever example of EQL
> specializers.
>
> Adding the :around method shows the extensibility of CLOS, because note how
> the hash-table based memoization doesn't change the fibonacci code at all,
> where as in your case it's a "complete rewrite" to speed it up.
>
> Both of these examples show "interesting" aspects of CLOS, particularly if
> you're coming from another OO system.
FWIW, I played around with John's idea a bit, using the MOP instead of
EVAL. And came up with this (note INTERN-EQL-SPECIALIZER is part of
the MOP so the symbol may need to imported or the appropriate package
use-package'd to get this to work in some Lisps. And in other Lisp's
you'll be SOL:)
;;; Silly implementation of fib that uses the EQL specializers,
;;; NO-APPLICABLE-METHOD, and the MOP to implement memoization.
(defgeneric fib (n))
(defmethod fib ((n (eql 0))) 1)
(defmethod fib ((n (eql 1))) 1)
(defmethod no-applicable-method ((gf (eql #'fib)) &rest args)
(destructuring-bind (n) args
(unless (typep n '(integer 0)) (call-next-method))
(let ((result (+ (fib (- n 1)) (fib (- n 2)))))
(add-method
#'fib
(make-instance
'standard-method
:lambda-list '(n)
:specializers (list (intern-eql-specializer n))
:function (lambda (n) (declare (ignore n)) result)))
result)))
> Now, perhaps if Peter were writing "Mathmatica using Common Lisp", this
> would be good form. But he isn't, so, it's not. Instead its a hack, and,
> IMHO, shows bad precedance to problem solving in CL, especially for new
> users.
Though I appreciate John's suggestion, I agree that this might be a
bit much to throw at folks just at first. However I've written so many
versions of the FIB function using different techniques that it
occured to me that perhaps I could use it as a way to explore some of
the out of the way corners of the language: have an appendix of
nothing but different ways to implement FIB in Common Lisp, each one
using and/or abusing a different language feature. I'll have to see if
I really have as many clever/stupid implementations as I think I do.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
In article <··············@javamonkey.com>,
Peter Seibel <·····@javamonkey.com> wrote:
>Though I appreciate John's suggestion, I agree that this might be a
>bit much to throw at folks just at first. However I've written so many
>versions of the FIB function using different techniques that it
>occured to me that perhaps I could use it as a way to explore some of
>the out of the way corners of the language: have an appendix of
>nothing but different ways to implement FIB in Common Lisp, each one
>using and/or abusing a different language feature. I'll have to see if
>I really have as many clever/stupid implementations as I think I do.
FWIW, I think that's a bad idea -- nothing says "academic curiosity"
better than clever examples of fairly simple mathematical problems.
The Lisp literature is full of factorials, Fibonaccis, and towers of
Hanoi; it's the examples with unit tests and databases that are novel
and interesting...
--
Mike Kozlowski
http://www.klio.org/mlk/
Mike Kozlowski <···@klio.org> wrote in message news:<············@reader2.panix.com>...
> FWIW, I think that's a bad idea -- nothing says "academic curiosity"
> better than clever examples of fairly simple mathematical problems.
Sort of reminds me of "The evolution of a Haskell programmer":
http://www.willamette.edu/~fruehr/haskell/evolution.html
Alexander Schmolck wrote:
> Pascal Costanza <········@web.de> writes:
>
>
>>(let ((table (make-hash-table)))
>> (defmethod fibonacci :around ((n number))
>> (multiple-value-bind
>> (result boundp)
>> (gethash n table)
>> (if boundp result
>> (setf (gethash n table)
>> (call-next-method))))))
>
>
> Is there a reason not to write this as:
>
> (let ((table (make-hash-table)))
> (defmethod fibonacci :around ((n number))
> (or (gethash n table)
> (setf (gethash n table) (call-next-method)))))
>
> ?
Er, no, I guess not. I have overlooked gethash's second return value in
a recent different thread, and maybe I subconsciously wanted to
compensate for that. ;)
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
Sashank Varma wrote:
> I have defined a function FIB. Here it is, with one elision:
>
> ? (defun fib (...)
> answer)
[...]
> What did I elide?
A lambda list with an aux variable?
Jeremy.
In article <·····················@maka.cl.cam.ac.uk>,
Jeremy Yallop <······@jdyallop.freeserve.co.uk> wrote:
> Sashank Varma wrote:
> > I have defined a function FIB. Here it is, with one elision:
> >
> > ? (defun fib (...)
> > answer)
> [...]
> > What did I elide?
>
> A lambda list with an aux variable?
You're on the right track.
[Perhaps you know the complete solution and are being vague
so as not to spoil the fun for others.]
In article <··············@raw.grenland.fast.no>,
Raymond Wiker <·············@fast.no> wrote:
> Sashank Varma <····@vanderbilt.edu> writes:
>
> > I have defined a function FIB. Here it is, with one elision:
> >
> > ? (defun fib (...)
> > answer)
> > FIB
> > ? (fib 0)
> > 1
> > ? (fib 1)
> > 1
> > ? (fib 2)
> > 2
> > ? (fib 10)
> > 3628800
^^^^^^^
Note: This was a typo on my part; it should be 89.
> > ?
> >
> > What did I elide?
>
> Something like
>
> x &aux (answer (labels ((fib-i (y) ...)) (fib-i x)))
You're on the right track. Sure you need the LABELS?
;-)
Sashank Varma <····@vanderbilt.edu> writes:
> In article <··············@raw.grenland.fast.no>,
> Raymond Wiker <·············@fast.no> wrote:
>
>> Something like
>>
>> x &aux (answer (labels ((fib-i (y) ...)) (fib-i x)))
>
> You're on the right track. Sure you need the LABELS?
>
> ;-)
Well, I don't *need* the labels, no... but this makes the use
of &aux even more non-trivial :-)
--
Raymond Wiker Mail: ·············@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60
Try FAST Search: http://alltheweb.com/
In article <··············@raw.grenland.fast.no>,
Raymond Wiker <·············@fast.no> wrote:
> Sashank Varma <····@vanderbilt.edu> writes:
>
> > In article <··············@raw.grenland.fast.no>,
> > Raymond Wiker <·············@fast.no> wrote:
> >
> >> Something like
> >>
> >> x &aux (answer (labels ((fib-i (y) ...)) (fib-i x)))
> >
> > You're on the right track. Sure you need the LABELS?
> >
> > ;-)
>
> Well, I don't *need* the labels, no... but this makes the use
> of &aux even more non-trivial :-)
Touche.
Can't we do this without the eval or the hash table in a more CLOS style thus?
(defgeneric fib (n))
(defmethod fib ((n (eql 0))) 1)
(defmethod fib ((n (eql 1))) 1)
(defmethod fib ((n integer))
(assert (> n 1))
(let ((result (+ (fib (- n 2)) (fib (1- n)))))
(defmethod fib ((n (eql n))) result)
result))
The first invocation is of course slower than an iterative (i.e.,
non-recursive fib), but subsequent invocations are essentially
instantaneous - e.g., 1 millisecond or less for (fib 200) - due to the
memoization via eql specialized methods.
In article <············@newsreader2.netcologne.de>,
Pascal Costanza <········@web.de> wrote:
> (defun fib (n &aux (answer (if (< n 2) 1
> (+ (fib (- n 2))
> (fib (1- n))))))
> answer)
That's what I came up with! Perhaps my first non-trivial
use of an &AUX parameter ever.
[Aside: The reason my initial post contained the error:
> ? (fib 10)
> 3628800
was because I was also playing around with the same
trick and the factorial function:
> ? (defun fact (n &aux (answer (if (zerop n) 1 (* n (fact (1- n))))))
> answer)
> FACT
> ? (fact 0)
> 1
> ? (fact 10)
> 3628800
and I comingled the traces.]