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:
> 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 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.
(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.
> > 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 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.
> (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.
> "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 ?
> > 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 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.
> (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.
> On Aug 9, 5:44 am, Ken Tilton <kennytil...@optonline.net> wrote:
> > case.learn...@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 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.
> > (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.
> > "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 -
> > > > 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 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.
> > > (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.
> > > "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.
> 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:
> 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.
Slobodan Blazeski <slobodan.blaze...@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
> On Aug 9, 4:58 am, case.learn...@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:
> > 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.
On Aug 9, 4:55 pm, Tamas Papp <tkp...@gmail.com> wrote:
> Slobodan Blazeski <slobodan.blaze...@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
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.
Slobodan Blazeski <slobodan.blaze...@gmail.com> writes: > On Aug 9, 4:55 pm, Tamas Papp <tkp...@gmail.com> wrote: >> Slobodan Blazeski <slobodan.blaze...@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
> Slobodan Blazeski <slobodan.blaze...@gmail.com> writes: > > On Aug 9, 4:55 pm, Tamas Papp <tkp...@gmail.com> wrote: > >> Slobodan Blazeski <slobodan.blaze...@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
> > 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.
Slobodan Blazeski <slobodan.blaze...@gmail.com> writes: > On Aug 9, 4:55 pm, Tamas Papp <tkp...@gmail.com> wrote: >> Slobodan Blazeski <slobodan.blaze...@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
> 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:
- 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.
"andrew.ba...@gmail.com" <andrew.ba...@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.
Tamas Papp <tkp...@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.
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
mmcconnell17...@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.
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.
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
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
Tamas Papp <tkp...@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 Neuss <lastn...@mathematik.uni-karlsruhe.de> writes: > Tamas Papp <tkp...@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 Papp <tkp...@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).
Tamas Papp <tkp...@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.
