Hi everyone,
I'm kind of new to Lisp. I'm doing this Newton method problem (not a
homework problem; I'm learning programming myself). These are two
different ways of coding the same solution:
(defun good-enough (n guess)
(< (abs (- (square guess) n)) 0.0001))
(defun square (x)
(* x x))
(defun improve-guess (n guess)
(/ (+ guess (/ n guess)) 2))
FIRST:
(defun newton-sqrt (n)
(newton-sqrt-aux n 1.0))
(defun newton-sqrt-aux (n guess)
(cond ((good-enough n guess) guess)
(t (newton-sqrt-aux n (improve-guess n guess)))))
SECOND:
(defun newton-sqrt (n)
(let ((guess 1.0))
(loop
(cond ((good-enough n guess) (return guess)))
(setq guess (improve-guess n guess)))))
The what is really the difference between the two, and how I should
think about them?
Thank you.
·············@gmail.com wrote:
> Hi everyone,
>
> I'm kind of new to Lisp. I'm doing this Newton method problem (not a
> homework problem; I'm learning programming myself). These are two
> different ways of coding the same solution:
>
> (defun good-enough (n guess)
> (< (abs (- (square guess) n)) 0.0001))
>
> (defun square (x)
> (* x x))
>
> (defun improve-guess (n guess)
> (/ (+ guess (/ n guess)) 2))
>
> FIRST:
>
> (defun newton-sqrt (n)
> (newton-sqrt-aux n 1.0))
>
> (defun newton-sqrt-aux (n guess)
> (cond ((good-enough n guess) guess)
> (t (newton-sqrt-aux n (improve-guess n guess)))))
Lisp has flet, labels, and lambda so you never need to create a
standalone function needed only by one caller. Your desired aux func
calls itself, so you need labels.
Using cond to code if is pretty scary, btw.
>
> SECOND:
>
> (defun newton-sqrt (n)
> (let ((guess 1.0))
> (loop
> (cond ((good-enough n guess) (return guess)))
> (setq guess (improve-guess n guess)))))
Ouch. Untested:
(loop for guess = 1.0 then (improve-guess n guess)
when (good-enough n guess) return guess)
>
> The what is really the difference between the two, and how I should
> think about them?
(a) nothing, so (b) you should think about the program you are trying to
write, not this.
You might also think that Lisp is huge enough to give you lotsa ways to
implement the same thing. As one brilliant wag once said (paraphrasing)
(1- lotsa) of them are wrong. How to choose? The question is not how you
should think about the code solutions, the question is how do you think
about the problem? Write the code the same way. Sure, one may well think
about the problem the wrong way, but if so no computer language rules of
thumb will help.
kt
--
http://www.theoryyalgebra.com/
"Algebra is the metaphysics of arithmetic." - John Ray
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
On Aug 9, 5:44 am, Ken Tilton <···········@optonline.net> wrote:
> ·············@gmail.com wrote:
> > Hi everyone,
>
> > I'm kind of new to Lisp. I'm doing this Newton method problem (not a
> > homework problem; I'm learning programming myself). These are two
> > different ways of coding the same solution:
>
> > (defun good-enough (n guess)
> > (< (abs (- (square guess) n)) 0.0001))
>
> > (defun square (x)
> > (* x x))
>
> > (defun improve-guess (n guess)
> > (/ (+ guess (/ n guess)) 2))
>
> > FIRST:
>
> > (defun newton-sqrt (n)
> > (newton-sqrt-aux n 1.0))
>
> > (defun newton-sqrt-aux (n guess)
> > (cond ((good-enough n guess) guess)
> > (t (newton-sqrt-aux n (improve-guess n guess)))))
>
> Lisp has flet, labels, and lambda so you never need to create a
> standalone function needed only by one caller. Your desired aux func
> calls itself, so you need labels.
>
> Using cond to code if is pretty scary, btw.
>
>
>
> > SECOND:
>
> > (defun newton-sqrt (n)
> > (let ((guess 1.0))
> > (loop
> > (cond ((good-enough n guess) (return guess)))
> > (setq guess (improve-guess n guess)))))
>
> Ouch. Untested:
>
> (loop for guess = 1.0 then (improve-guess n guess)
> when (good-enough n guess) return guess)
>
>
>
> > The what is really the difference between the two, and how I should
> > think about them?
>
> (a) nothing, so (b) you should think about the program you are trying to
> write, not this.
>
> You might also think that Lisp is huge enough to give you lotsa ways to
> implement the same thing. As one brilliant wag once said (paraphrasing)
> (1- lotsa) of them are wrong. How to choose? The question is not how you
> should think about the code solutions, the question is how do you think
> about the problem? Write the code the same way. Sure, one may well think
> about the problem the wrong way, but if so no computer language rules of
> thumb will help.
>
> kt
>
> --http://www.theoryyalgebra.com/
>
> "Algebra is the metaphysics of arithmetic." - John Ray
>
> "As long as algebra is taught in school,
> there will be prayer in school." - Cokie Roberts
>
> "Stand firm in your refusal to remain conscious during algebra."
> - Fran Lebowitz
>
> "I'm an algebra liar. I figure two good lies make a positive."
> - Tim Allen- Hide quoted text -
>
> - Show quoted text -
Quick pick the right answer:
1. I'm dreaming
2. I'm halucinating
3. Aliens abducted Kenny and replace him with some hybrid who
impersonates him (badly)
4. Kenny is actully being nice & helpfull to a newbie.
Hm... 3
Get our old Kenny back you alien scumbag or we're starting an
intergalactical war of the worlds ?
On Aug 9, 8:04 am, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Aug 9, 5:44 am, Ken Tilton <···········@optonline.net> wrote:
>
>
>
>
>
> > ·············@gmail.com wrote:
> > > Hi everyone,
>
> > > I'm kind of new to Lisp. I'm doing this Newton method problem (not a
> > > homework problem; I'm learning programming myself). These are two
> > > different ways of coding the same solution:
>
> > > (defun good-enough (n guess)
> > > (< (abs (- (square guess) n)) 0.0001))
>
> > > (defun square (x)
> > > (* x x))
>
> > > (defun improve-guess (n guess)
> > > (/ (+ guess (/ n guess)) 2))
>
> > > FIRST:
>
> > > (defun newton-sqrt (n)
> > > (newton-sqrt-aux n 1.0))
>
> > > (defun newton-sqrt-aux (n guess)
> > > (cond ((good-enough n guess) guess)
> > > (t (newton-sqrt-aux n (improve-guess n guess)))))
>
> > Lisp has flet, labels, and lambda so you never need to create a
> > standalone function needed only by one caller. Your desired aux func
> > calls itself, so you need labels.
>
> > Using cond to code if is pretty scary, btw.
>
> > > SECOND:
>
> > > (defun newton-sqrt (n)
> > > (let ((guess 1.0))
> > > (loop
> > > (cond ((good-enough n guess) (return guess)))
> > > (setq guess (improve-guess n guess)))))
>
> > Ouch. Untested:
>
> > (loop for guess = 1.0 then (improve-guess n guess)
> > when (good-enough n guess) return guess)
>
> > > The what is really the difference between the two, and how I should
> > > think about them?
>
> > (a) nothing, so (b) you should think about the program you are trying to
> > write, not this.
>
> > You might also think that Lisp is huge enough to give you lotsa ways to
> > implement the same thing. As one brilliant wag once said (paraphrasing)
> > (1- lotsa) of them are wrong. How to choose? The question is not how you
> > should think about the code solutions, the question is how do you think
> > about the problem? Write the code the same way. Sure, one may well think
> > about the problem the wrong way, but if so no computer language rules of
> > thumb will help.
>
> > kt
>
> > --http://www.theoryyalgebra.com/
>
> > "Algebra is the metaphysics of arithmetic." - John Ray
>
> > "As long as algebra is taught in school,
> > there will be prayer in school." - Cokie Roberts
>
> > "Stand firm in your refusal to remain conscious during algebra."
> > - Fran Lebowitz
>
> > "I'm an algebra liar. I figure two good lies make a positive."
> > - Tim Allen- Hide quoted text -
>
> > - Show quoted text -
>
> Quick pick the right answer:
> 1. I'm dreaming
> 2. I'm halucinating
> 3. Aliens abducted Kenny and replace him with some hybrid who
> impersonates him (badly)
> 4. Kenny is actully being nice & helpfull to a newbie.
>
> Hm... 3
> Get our old Kenny back you alien scumbag or we're starting an
> intergalactical war of the worlds ?- Hide quoted text -
>
> - Show quoted text -
I have no idea what you're talking about.
Mark.
On Aug 9, 4:20 pm, ·············@gmail.com wrote:
> On Aug 9, 8:04 am, Slobodan Blazeski <·················@gmail.com>
> wrote:
>
>
>
>
>
> > On Aug 9, 5:44 am, Ken Tilton <···········@optonline.net> wrote:
>
> > > ·············@gmail.com wrote:
> > > > Hi everyone,
>
> > > > I'm kind of new to Lisp. I'm doing this Newton method problem (not a
> > > > homework problem; I'm learning programming myself). These are two
> > > > different ways of coding the same solution:
>
> > > > (defun good-enough (n guess)
> > > > (< (abs (- (square guess) n)) 0.0001))
>
> > > > (defun square (x)
> > > > (* x x))
>
> > > > (defun improve-guess (n guess)
> > > > (/ (+ guess (/ n guess)) 2))
>
> > > > FIRST:
>
> > > > (defun newton-sqrt (n)
> > > > (newton-sqrt-aux n 1.0))
>
> > > > (defun newton-sqrt-aux (n guess)
> > > > (cond ((good-enough n guess) guess)
> > > > (t (newton-sqrt-aux n (improve-guess n guess)))))
>
> > > Lisp has flet, labels, and lambda so you never need to create a
> > > standalone function needed only by one caller. Your desired aux func
> > > calls itself, so you need labels.
>
> > > Using cond to code if is pretty scary, btw.
>
> > > > SECOND:
>
> > > > (defun newton-sqrt (n)
> > > > (let ((guess 1.0))
> > > > (loop
> > > > (cond ((good-enough n guess) (return guess)))
> > > > (setq guess (improve-guess n guess)))))
>
> > > Ouch. Untested:
>
> > > (loop for guess = 1.0 then (improve-guess n guess)
> > > when (good-enough n guess) return guess)
>
> > > > The what is really the difference between the two, and how I should
> > > > think about them?
>
> > > (a) nothing, so (b) you should think about the program you are trying to
> > > write, not this.
>
> > > You might also think that Lisp is huge enough to give you lotsa ways to
> > > implement the same thing. As one brilliant wag once said (paraphrasing)
> > > (1- lotsa) of them are wrong. How to choose? The question is not how you
> > > should think about the code solutions, the question is how do you think
> > > about the problem? Write the code the same way. Sure, one may well think
> > > about the problem the wrong way, but if so no computer language rules of
> > > thumb will help.
>
> > > kt
>
> > > --http://www.theoryyalgebra.com/
>
> > > "Algebra is the metaphysics of arithmetic." - John Ray
>
> > > "As long as algebra is taught in school,
> > > there will be prayer in school." - Cokie Roberts
>
> > > "Stand firm in your refusal to remain conscious during algebra."
> > > - Fran Lebowitz
>
> > > "I'm an algebra liar. I figure two good lies make a positive."
> > > - Tim Allen- Hide quoted text -
>
> > > - Show quoted text -
>
> > Quick pick the right answer:
> > 1. I'm dreaming
> > 2. I'm halucinating
> > 3. Aliens abducted Kenny and replace him with some hybrid who
> > impersonates him (badly)
> > 4. Kenny is actully being nice & helpfull to a newbie.
>
> > Hm... 3
> > Get our old Kenny back you alien scumbag or we're starting an
> > intergalactical war of the worlds ?- Hide quoted text -
>
> > - Show quoted text -
>
> I have no idea what you're talking about.
>
> Mark.- Hide quoted text -
>
> - Show quoted text -
Shut up and get your laser pistol. I'll explain you on the way. We
have aliens to fight.
On Aug 8, 9:44 pm, Ken Tilton <···········@optonline.net> wrote:
> ·············@gmail.com wrote:
> > Hi everyone,
>
> > I'm kind of new to Lisp. I'm doing this Newton method problem (not a
> > homework problem; I'm learning programming myself). These are two
> > different ways of coding the same solution:
>
> > (defun good-enough (n guess)
> > (< (abs (- (square guess) n)) 0.0001))
>
> > (defun square (x)
> > (* x x))
>
> > (defun improve-guess (n guess)
> > (/ (+ guess (/ n guess)) 2))
>
> > FIRST:
>
> > (defun newton-sqrt (n)
> > (newton-sqrt-aux n 1.0))
>
> > (defun newton-sqrt-aux (n guess)
> > (cond ((good-enough n guess) guess)
> > (t (newton-sqrt-aux n (improve-guess n guess)))))
>
> Lisp has flet, labels, and lambda so you never need to create a
> standalone function needed only by one caller. Your desired aux func
> calls itself, so you need labels.
>
> Using cond to code if is pretty scary, btw.
>
>
>
> > SECOND:
>
> > (defun newton-sqrt (n)
> > (let ((guess 1.0))
> > (loop
> > (cond ((good-enough n guess) (return guess)))
> > (setq guess (improve-guess n guess)))))
>
> Ouch. Untested:
>
> (loop for guess = 1.0 then (improve-guess n guess)
> when (good-enough n guess) return guess)
>
>
>
> > The what is really the difference between the two, and how I should
> > think about them?
>
> (a) nothing, so (b) you should think about the program you are trying to
> write, not this.
>
> You might also think that Lisp is huge enough to give you lotsa ways to
> implement the same thing. As one brilliant wag once said (paraphrasing)
> (1- lotsa) of them are wrong. How to choose? The question is not how you
> should think about the code solutions, the question is how do you think
> about the problem? Write the code the same way. Sure, one may well think
> about the problem the wrong way, but if so no computer language rules of
> thumb will help.
>
> kt
>
> --http://www.theoryyalgebra.com/
>
> "Algebra is the metaphysics of arithmetic." - John Ray
>
> "As long as algebra is taught in school,
> there will be prayer in school." - Cokie Roberts
>
> "Stand firm in your refusal to remain conscious during algebra."
> - Fran Lebowitz
>
> "I'm an algebra liar. I figure two good lies make a positive."
> - Tim Allen- Hide quoted text -
>
> - Show quoted text -
The answer is very helpful. Thank you.
In addition to the other replies, there is a whole story about whether
tail recursion is as efficient as iteration. newton-sqrt-aux is tail-
recursive. This means two things: it calls itself (the "recursive"
part), and the last thing the k-th call does is to return the result
of the (k+1)-st call (the "tail" part). Sometimes tail-recursion will
be implemented as a jump from one part of the function back to near
the beginning. That is likely what the second version, with loop,
does. Other times, there is a stack of function calls. The k-th call
to newton-sqrt-aux will create the (k+1)-st call to newton-sqrt-aux.
All the calls will remain on the stack until the deepest call
finishes, at which point they unwind in reverse order.
One danger of the stack-based approach is that the stack may fill up
after a few thousand calls, making the program crash. This is not a
theoretical danger. Even compiled, an intensely recursive program can
run out of space and crash. (It's not just Lisp. I've crashed Java
with tail-recursive functions, and I bet it could happen in most
languages.)
A newbie should note that many people feel tail recursion is
beautiful. It is the right solution for many problems. One of the
good things about Lisp is that it encourages this style.
Again for the sake of the newbie, I can't resist an example in Allegro
CL 8.0.
(defun ct (n)
"Count backwards tail-recursively from n to 0."
(if (<= n 0)
'done
(ct (1- n))))
(ct 1000000)
;; This crashes the interpreter.
;; And you'd expect it to!
;; Interpreted functions naturally use a stack.
(compile 'ct)
;; Change it to a compiled function.
(ct 1000000)
DONE
;; very fast
(disassemble 'ct) ;; look for jmp
;; disassembly of #<Function CT>
;; formals: N
;; constant vector:
0: DONE
;; code start: #x21d9ec74:
0: 55 pushl ebp
1: 8b ec movl ebp,esp
3: 56 pushl esi
4: 83 ec 2c subl esp,$44
7: 83 f9 01 cmpl ecx,$1
10: 74 03 jz 15
12: ff 57 8b call *[edi-117] ; SYS::TRAP-WNAERR
15: 80 7f cb 00 cmpb [edi-53],$0 ; SYS::C_INTERRUPT-PENDING
19: 74 03 jz 24
21: ff 57 87 call *[edi-121] ; SYS::TRAP-SIGNAL-HIT
24: 89 45 e4 movl [ebp-28],eax ; N
27: 33 d2 xorl edx,edx
29: a8 03 testb al,$3
31: 75 0d jnz 46
33: 3b c2 cmpl eax,edx
35: 7f 16 jnle 59
37: 8b 46 12 movl eax,[esi+18] ; DONE
40: f8 clc
41: c9 leave
42: 8b 75 fc movl esi,[ebp-4]
45: c3 ret
46: 8b 9f 97 fe movl ebx,[edi-361] ; EXCL::<=_2OP
ff ff
52: ff 57 27 call *[edi+39] ; SYS::TRAMP-TWO
55: 3b f8 cmpl edi,eax
57: 75 ea jnz 37
59: 33 d2 xorl edx,edx
61: b2 04 movb dl,$4
63: 8b 5d e4 movl ebx,[ebp-28] ; N
66: f6 c3 03 testb bl,$3
69: 75 08 jnz 79
71: 8b c3 movl eax,ebx
73: 2b c2 subl eax,edx
75: 70 02 jo 79
77: eb c0 jmp 15
79: 8b c3 movl eax,ebx
81: 8b 9f df fd movl ebx,[edi-545] ; EXCL::-_2OP
ff ff
87: ff 57 27 call *[edi+39] ; SYS::TRAMP-TWO
90: eb b3 jmp 15
···············@yahoo.com writes:
> One danger of the stack-based approach is that the stack may fill up
> after a few thousand calls, making the program crash. This is not a
> theoretical danger. Even compiled, an intensely recursive program can
> run out of space and crash. (It's not just Lisp. I've crashed Java
> with tail-recursive functions, and I bet it could happen in most
> languages.)
I agree (and your example, which I cut from this reply, is
instructive). But in the actual case, the OP is safe: Newton's method
either converges quickly or diverges wildly. Sometimes it is possible
to demonstrate convergence analytically.
Best,
Tamas
Tamas Papp <······@gmail.com> writes:
> But in the actual case, the OP is safe: Newton's method either
> converges quickly or diverges wildly.
This thread may be relevant here:
Floating point arithmetic (epsilon)
http://groups.google.com/group/comp.lang.lisp/browse_frm/thread/73793a5fed4be8c6
My participation in that thread dropped off before I could share my
eventual solution, as it took many more days of analysis and
experimentation to get it right.
--
Steven E. Harris
Tamas Papp <······@gmail.com> writes:
> I agree (and your example, which I cut from this reply, is instructive).
> But in the actual case, the OP is safe: Newton's method either converges
> quickly or diverges wildly.
You can easily construct problems with arbitrary slow convergence or cycles
of the Newton iterates.
> Sometimes it is possible to demonstrate convergence analytically.
For _every_ smooth and well-posed problem good convergence is guaranteed if
your starting guess is sufficiently close to the solution.
Nicolas
Nicolas Neuss <········@mathematik.uni-karlsruhe.de> writes:
> Tamas Papp <······@gmail.com> writes:
>
>> I agree (and your example, which I cut from this reply, is instructive).
>> But in the actual case, the OP is safe: Newton's method either converges
>> quickly or diverges wildly.
>
> You can easily construct problems with arbitrary slow convergence or cycles
> of the Newton iterates.
>
>> Sometimes it is possible to demonstrate convergence analytically.
>
> For _every_ smooth and well-posed problem good convergence is guaranteed if
> your starting guess is sufficiently close to the solution.
The proof I know guarantees things for an epsilon neighborhood of the
root. Nice result in analysis, but of little practical value, as
there is no way to find out that epsilon.
Tamas
Tamas Papp <······@gmail.com> writes:
> there is no way to find out that epsilon.
Have you looked at Erik Naggum's scaled-epsilon� function from the
thread I mentioned yesterday? I used that in my Newton's Method solver
to adapt epsilon to the root being searched. Regardless of the magnitude
of the root candidate, using this scaled-epsilon function can determine
whether the next delta is below the precision threshold.
Footnotes:
� http://groups.google.com/group/comp.lang.lisp/msg/3bcc6f325cda63fc
--
Steven E. Harris
Tamas Papp <······@gmail.com> writes:
> The proof I know guarantees things for an epsilon neighborhood of the
> root. Nice result in analysis, but of little practical value, as there
> is no way to find out that epsilon.
If you have control over first and second derivatives, you can easily find
an explicit formula for epsilon which can be of practical value. Many
formulations of the Newton convergence theorem quantify this epsilon (the
usual convergence proof will spit it out).
Nicolas
On Aug 9, 4:58 am, ·············@gmail.com wrote:
> Hi everyone,
>
> I'm kind of new to Lisp. I'm doing this Newton method problem (not a
> homework problem; I'm learning programming myself). These are two
> different ways of coding the same solution:
>
> (defun good-enough (n guess)
> (< (abs (- (square guess) n)) 0.0001))
>
> (defun square (x)
> (* x x))
>
> (defun improve-guess (n guess)
> (/ (+ guess (/ n guess)) 2))
>
> FIRST:
>
> (defun newton-sqrt (n)
> (newton-sqrt-aux n 1.0))
>
> (defun newton-sqrt-aux (n guess)
> (cond ((good-enough n guess) guess)
> (t (newton-sqrt-aux n (improve-guess n guess)))))
>
> SECOND:
>
> (defun newton-sqrt (n)
> (let ((guess 1.0))
> (loop
> (cond ((good-enough n guess) (return guess)))
> (setq guess (improve-guess n guess)))))
>
> The what is really the difference between the two, and how I should
> think about them?
>
> Thank you.
By the way you could define square as macro to gain some speed, if you
don't plan to use it as argument, for better explanation search
Grahams On Lisp for Computation at compile-time (chapter 13) freely
available at http://www.paulgraham.com/onlisp.html
(defmacro square (x)
`(* ,x ,x))
2nd Sometimes is better to keep functions as global, in order to reuse
them as utilities.
See On Lisp - Programming Bottom-Up and Utilities.
3rd cond looks better than nested if's , but avoid using cond in
situations where if or even when/unless will suffice.
have a nice lisping
bobi
On Aug 9, 4:45 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Aug 9, 4:58 am, ·············@gmail.com wrote:
>
>
>
>
>
> > Hi everyone,
>
> > I'm kind of new to Lisp. I'm doing this Newton method problem (not a
> > homework problem; I'm learning programming myself). These are two
> > different ways of coding the same solution:
>
> > (defun good-enough (n guess)
> > (< (abs (- (square guess) n)) 0.0001))
>
> > (defun square (x)
> > (* x x))
>
> > (defun improve-guess (n guess)
> > (/ (+ guess (/ n guess)) 2))
>
> > FIRST:
>
> > (defun newton-sqrt (n)
> > (newton-sqrt-aux n 1.0))
>
> > (defun newton-sqrt-aux (n guess)
> > (cond ((good-enough n guess) guess)
> > (t (newton-sqrt-aux n (improve-guess n guess)))))
>
> > SECOND:
>
> > (defun newton-sqrt (n)
> > (let ((guess 1.0))
> > (loop
> > (cond ((good-enough n guess) (return guess)))
> > (setq guess (improve-guess n guess)))))
>
> > The what is really the difference between the two, and how I should
> > think about them?
>
> > Thank you.
>
> By the way you could define square as macro to gain some speed, if you
> don't plan to use it as argument, for better explanation search
> Grahams On Lisp for Computation at compile-time (chapter 13) freely
> available athttp://www.paulgraham.com/onlisp.html
>
> (defmacro square (x)
> `(* ,x ,x))
>
> 2nd Sometimes is better to keep functions as global, in order to reuse
> them as utilities.
> See On Lisp - Programming Bottom-Up and Utilities.
>
> 3rd cond looks better than nested if's , but avoid using cond in
> situations where if or even when/unless will suffice.
>
> have a nice lisping
>
> bobi- Hide quoted text -
>
> - Show quoted text -
This is more stylistic but adding documentation string and proper
naming would be very nice. Lispers have tradition of very-long-and-
descriptive-names http://www.cs.northwestern.edu/academics/courses/325/readings/names.html
from
http://www.cs.northwestern.edu/academics/courses/325/readings/
Slobodan Blazeski <·················@gmail.com> writes:
> By the way you could define square as macro to gain some speed,
I would guess the speed-up would be negligible compared to leaving it a
function and declaiming it to be inline.
> if you
> don't plan to use it as argument, for better explanation search
I don't understand what "don't plan to use it as argument" means.
> Grahams On Lisp for Computation at compile-time (chapter 13) freely
> available at http://www.paulgraham.com/onlisp.html
>
> (defmacro square (x)
> `(* ,x ,x))
Ack! This is incorrect code. Don't copy it. Consider:
(defparameter *count* 0)
(square (incf *count*)) => 2
(square (incf *count*)) => 6
The side effects will kill you. The above was somewhat contrived, but
imagine you want to work with successive prime numbers and have a nice
function NEXT-PRIME that will give you the next prime number in
sequence.
(square (next-prime))
would produce the same evil results from being evaluated twice. So you
would need to introduce a macro like
(defmacro square (x)
(let ((var (gensym)))
`(let ((,var ,x))
(* ,var ,var))))
At which point the macro may slow things down, since you would lose any
declarations such as in:
(let ((n 10))
(declare (fixnum n))
(square n))
So that means you now need to perhaps write a much more complicated
macro, perhaps something like:
(defmacro square (x)
(if (atom x)
`(* ,x ,x)
(let ((var (gensym)))
`(let ((,var ,x))
(* ,var ,var)))))
QUESTION: Is this safe in the presence of symbol-macros? I've never
really used them, so I don't know a lot about them.
Anyway, at this point the macro is getting a bit on the hairy side, so I
would suggest using an in-lined function and letting the compiler worry
about how to handle the argument evaluation.
--
Thomas A. Russ, USC/Information Sciences Institute
Slobodan Blazeski <·················@gmail.com> writes:
> By the way you could define square as macro to gain some speed, if you
> don't plan to use it as argument, for better explanation search
> Grahams On Lisp for Computation at compile-time (chapter 13) freely
> available at http://www.paulgraham.com/onlisp.html
>
> (defmacro square (x)
> `(* ,x ,x))
This gives negligible speed improvement and is unsafe. See
http://www.gigamonkeys.com/book/macros-defining-your-own.html,
"Plugging the leaks."
For speed improvements, use declarations or compiler macros (Mark, you
can ignore compiler macros for now).
> 2nd Sometimes is better to keep functions as global, in order to reuse
> them as utilities.
> See On Lisp - Programming Bottom-Up and Utilities.
Except that in this program, the helper functions are very specific so
there is no point in doing that.
BTW, On Lisp is not something I would recommend for newbies.
Tamas
On Aug 9, 4:55 pm, Tamas Papp <······@gmail.com> wrote:
> Slobodan Blazeski <·················@gmail.com> writes:
> > By the way you could define square as macro to gain some speed, if you
> > don't plan to use it as argument, for better explanation search
> > Grahams On Lisp for Computation at compile-time (chapter 13) freely
> > available athttp://www.paulgraham.com/onlisp.html
>
> > (defmacro square (x)
> > `(* ,x ,x))
>
> This gives negligible speed improvement and is unsafe. Seehttp://www.gigamonkeys.com/book/macros-defining-your-own.html,
> "Plugging the leaks."
Tend to disagreee , for other opinion see cl-statistics.
>
> For speed improvements, use declarations or compiler macros (Mark, you
> can ignore compiler macros for now).
Mark can ignore the whole optimization staff for now.
>
> > 2nd Sometimes is better to keep functions as global, in order to reuse
> > them as utilities.
> > See On Lisp - Programming Bottom-Up and Utilities.
>
> Except that in this program, the helper functions are very specific so
> there is no point in doing that.
newton-sqrt-aux should be labeled , but square is a general purpose
function/ macro that I end up writing or including a lot for the
other decide for yourself.
>
> BTW, On Lisp is not something I would recommend for newbies.
Chapter 1. The Extensible Language 1 consisted of
1.1. Design by Evolution 1
1.2. Programming Bottom-Up 3
1.3. Extensible Software 5
1.4. Extending Lisp 6
1.5. Why Lisp (or When
Is a great read even for a newbie and even if you decide to continue
with the rest of the book later in your journey. Especially 1-4 are
real eye opener for a new lisp programmer.
Bobi
>
> Tamas
Slobodan Blazeski <·················@gmail.com> writes:
> On Aug 9, 4:55 pm, Tamas Papp <······@gmail.com> wrote:
>> Slobodan Blazeski <·················@gmail.com> writes:
>> > By the way you could define square as macro to gain some speed, if you
>> > don't plan to use it as argument, for better explanation search
>> > Grahams On Lisp for Computation at compile-time (chapter 13) freely
>> > available athttp://www.paulgraham.com/onlisp.html
>>
>> > (defmacro square (x)
>> > `(* ,x ,x))
>>
>> This gives negligible speed improvement and is unsafe. Seehttp://www.gigamonkeys.com/book/macros-defining-your-own.html,
>> "Plugging the leaks."
>
> Tend to disagreee , for other opinion see cl-statistics.
Its usage in cl-statistics is just as ill-advised. This is not an idea
to copy for SQUARE.
Zach
On Aug 9, 11:43 am, Zach Beane <····@xach.com> wrote:
> Slobodan Blazeski <·················@gmail.com> writes:
> > On Aug 9, 4:55 pm, Tamas Papp <······@gmail.com> wrote:
> >> Slobodan Blazeski <·················@gmail.com> writes:
> >> > By the way you could define square as macro to gain some speed, if you
> >> > don't plan to use it as argument, for better explanation search
> >> > Grahams On Lisp for Computation at compile-time (chapter 13) freely
> >> > available athttp://www.paulgraham.com/onlisp.html
>
> >> > (defmacro square (x)
> >> > `(* ,x ,x))
>
> >> This gives negligible speed improvement and is unsafe. Seehttp://www.gigamonkeys.com/book/macros-defining-your-own.html,
> >> "Plugging the leaks."
>
> > Tend to disagreee , for other opinion see cl-statistics.
>
> Its usage in cl-statistics is just as ill-advised. This is not an idea
> to copy for SQUARE.
>
> Zach
Just to elaborate for OP's benefit: if you do (defmacro square
(x) ...) then as Slobodan noted, you can't use square as a function
argument to lots of lisp's incredibly useful functions. For example,
you might want to do (mapcar #'square '(1 2 3 4)) and get (1 4 9 16).
Not possible if square is a macro. Since square is not used this way
in your program, I think that Slobodan was taking a no-harm no-foul
approach. I'd prefer the function to the macro though.
·············@gmail.com" <············@gmail.com> writes:
>> Its usage in cl-statistics is just as ill-advised. This is not an idea
>> to copy for SQUARE.
>>
>> Zach
>
> Just to elaborate for OP's benefit: if you do (defmacro square
> (x) ...) then as Slobodan noted, you can't use square as a function
> argument to lots of lisp's incredibly useful functions. For example,
> you might want to do (mapcar #'square '(1 2 3 4)) and get (1 4 9 16).
> Not possible if square is a macro. Since square is not used this way
> in your program, I think that Slobodan was taking a no-harm no-foul
> approach. I'd prefer the function to the macro though.
There's an additional problem if the form X has any side-effects. If
SQUARE is a function, the form is evaluated once and the value is
passed to the function. With SQUARE as a macro as defined, the form is
evaluated twice, duplicating the side-effect.
Zach
Slobodan Blazeski <·················@gmail.com> writes:
> On Aug 9, 4:55 pm, Tamas Papp <······@gmail.com> wrote:
>> Slobodan Blazeski <·················@gmail.com> writes:
>> > By the way you could define square as macro to gain some speed, if you
>> > don't plan to use it as argument, for better explanation search
>> > Grahams On Lisp for Computation at compile-time (chapter 13) freely
>> > available athttp://www.paulgraham.com/onlisp.html
>>
>> > (defmacro square (x)
>> > `(* ,x ,x))
>>
>> This gives negligible speed improvement and is unsafe. Seehttp://www.gigamonkeys.com/book/macros-defining-your-own.html,
>> "Plugging the leaks."
>
> Tend to disagreee , for other opinion see cl-statistics.
Look at this:
(defun square (x)
(* x x))
(defmacro square-macro (x)
;; unsafe
`(* ,x ,x))
(declaim (inline square-inline))
(defun square-inline (x)
;; inlined version
(* x x))
(defparameter *n* 1000000)
(time (let ((sum 0))
(dotimes (i *n*)
(incf sum (square (/ i *n*))))))
(time (let ((sum 0))
(dotimes (i *n*)
(incf sum (square-macro (/ i *n*))))))
(time (let ((sum 0))
(dotimes (i *n*)
(incf sum (square-inline (/ i *n*))))))
Now the evaluation times:
; plain vanilla
; /tmp/file86RiQF.fasl written
; compilation finished in 0:00:00
Evaluation took:
9.636 seconds of real time
9.358577 seconds of user run time
0.086987 seconds of system run time
[Run times include 0.441 seconds GC run time.]
0 calls to %EVAL
0 page faults and
725,466,656 bytes consed.
; compiling file "/tmp/fileg05YV9.lisp" (written 09 AUG 2007 05:52:58 PM):
; your unsafe macro
; /tmp/fileg05YV9.fasl written
; compilation finished in 0:00:00
Evaluation took:
9.945 seconds of real time
9.629536 seconds of user run time
0.093985 seconds of system run time
[Run times include 0.465 seconds GC run time.]
0 calls to %EVAL
0 page faults and
741,483,296 bytes consed.
; compiling file "/tmp/filehj4WOX.lisp" (written 09 AUG 2007 05:53:11 PM):
; inlined version
; /tmp/filehj4WOX.fasl written
; compilation finished in 0:00:00
Evaluation took:
9.596 seconds of real time
9.318584 seconds of user run time
0.088987 seconds of system run time
[Run times include 0.431 seconds GC run time.]
0 calls to %EVAL
0 page faults and
725,481,264 bytes consed.
The speed "improvement" provided by the macro is within the margin of
error (if you rerun, you get different slightly different times).
You have gained nothing, but got an unsafe macro on your hands. Hint:
(defparameter *a* 1)
(square-macro (incf *a*)) ; => 6
Lessons learned:
- using macros for optimization is dubious at best
- most compilers are pretty smart, don't try to second-guess them
BTW, the above was done with SBCL.
>> For speed improvements, use declarations or compiler macros (Mark, you
>> can ignore compiler macros for now).
> Mark can ignore the whole optimization staff for now.
Poor optimization staff. Imagine being hired explicitly for
optimization, then being ignored. ;-)
> Is a great read even for a newbie and even if you decide to continue
> with the rest of the book later in your journey. Especially 1-4 are
> real eye opener for a new lisp programmer.
I agree that On Lisp is a great book, but PCL and Graham's ANSI CL are
better as an introduction.
Tamas
Tamas Papp <······@gmail.com> wrote:
> (defparameter *n* 1000000)
>
> (time (let ((sum 0))
> (dotimes (i *n*)
> (incf sum (square (/ i *n*))))))
While I don't disagree with the general sentiment (macros shouldn't be
used for optimization, when inlining does the same job), your
benchmark probably isn't a very good illustration of that. The
overhead of doing all the computations with ratios (due to the use of
/) is probably completely overwhelming any other effects.
Using for example ROUND instead of / will show the effects better:
(time (let ((sum 0))
(dotimes (i *n*)
(incf sum (square (round i *n*))))))
;;; etc for the other three loops
With this, the macro version should be slower than either of the
functions, since the ROUND is executed twice due to the buggy macro
definition.
--
Juho Snellman