Hello,
I'm going through the Little Schemer with Common Lisp. I got to the
problem of implementing + using 3 basic operations: "test if zero",
"increment by 1", "decrement by 1".
My solution is like this:
(defun myplus (x y)
(cond
((eql y 0) x)
(t (myplus (1+ x) (1- y)))))
But the little schemer's answer is like this (the difference is only
the last line):
(defun myplus2 (x y)
(cond
((eql y 0) x)
(t (1+ (myplus x (1- y))))))
My question is: why not my version? Isn't my version gonna be faster
because when the termination condition is reached it can return
immediately?
Thanks,
Ray
On Sat, 27 Jan 2007 20:29:16 +0100, Ray <··········@yahoo.com> wrote:
> Hello,
>
> I'm going through the Little Schemer with Common Lisp. I got to the
> problem of implementing + using 3 basic operations: "test if zero",
> "increment by 1", "decrement by 1".
>
> My solution is like this:
>
> (defun myplus (x y)
> (cond
> ((eql y 0) x)
> (t (myplus (1+ x) (1- y)))))
>
> But the little schemer's answer is like this (the difference is only
> the last line):
>
> (defun myplus2 (x y)
> (cond
> ((eql y 0) x)
> (t (1+ (myplus x (1- y))))))
>
> My question is: why not my version? Isn't my version gonna be faster
> because when the termination condition is reached it can return
> immediately?
>
> Thanks,
> Ray
>
Yes, you version is faster.
More so because your function call is tail recursive and has the
efficiency of
a loop. You should learn about that later on.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On Jan 28, 3:49 am, "John Thingstad" <··············@chello.no> wrote:
> > My question is: why not my version? Isn't my version gonna be faster
> > because when the termination condition is reached it can return
> > immediately?
>
> > Thanks,
> > Ray
> Yes, you version is faster.
> More so because your function call is tail recursive and has the
> efficiency of
> a loop. You should learn about that later on.
Thanks John! This is one very addictive little book, btw :)
Cheers
Ray
>
> --
> Using Opera's revolutionary e-mail client:http://www.opera.com/mail/
"Ray" <··········@yahoo.com> writes:
> Hello,
>
> I'm going through the Little Schemer with Common Lisp. I got to the
> problem of implementing + using 3 basic operations: "test if zero",
> "increment by 1", "decrement by 1".
>
> My solution is like this:
>
> (defun myplus (x y)
> (cond
> ((eql y 0) x)
> (t (myplus (1+ x) (1- y)))))
>
> But the little schemer's answer is like this (the difference is only
> the last line):
>
> (defun myplus2 (x y)
> (cond
> ((eql y 0) x)
> (t (1+ (myplus x (1- y))))))
>
> My question is: why not my version? Isn't my version gonna be faster
> because when the termination condition is reached it can return
> immediately?
Your code follows naturally from defining addition thus
x + 0 = x
x + Sy = Sx + y
Their code follows naturally from defining addition thus
x + 0 = x
x + Sy = S(x + y)
I was surprised when I saw their code because my memory told
me that the first definition was the common one, but
checking on the web
http://www.michaelbeeson.com/research/otter-lambda/index.php?include=PeanoArithmetic
http://en.wikipedia.org/wiki/Peano_axioms
http://planetmath.org/?op=getobj&from=objects&id=2789
I find only the second version. So my memory is playing
tricks and I guess that their code was written direct from
their definition.
Well, which version is faster? You can try it yourself:
CL-USER> (defun add1 (x y)
(case y
(0 x)
(otherwise
(add1 (1+ x)
(1- y)))))
ADD1
CL-USER> (defun add2 (x y)
(case y
(0 x)
(otherwise
(1+ (add2 x (1- y))))))
ADD2
CL-USER> (defun add2 (x y)
(case y
(0 x)
(otherwise
(1+ (add2 x
(1- y))))))
ADD2
CL-USER> (dolist (f '(add1 add2))
(compile f))
; Compiling LAMBDA (X Y):
; Compiling Top-Level Form:
; Compiling LAMBDA (X Y):
; Compiling Top-Level Form:
NIL
CL-USER> (dolist (f '(add1 add2))
(time (funcall f 1000000 1000000)))
Warning: TIME form in a non-null environment, forced to interpret.
Compiling entire form will produce more accurate times.
; Evaluation took:
; 0.13 seconds of real time
; 0.117506 seconds of user run time
; 9.0e-6 seconds of system run time
; 47,224,177 CPU cycles
; 0 page faults and
; 80 bytes consed.
;
Warning: TIME form in a non-null environment, forced to interpret.
Compiling entire form will produce more accurate times.
; Evaluation took:
; 0.45 seconds of real time
; 0.437243 seconds of user run time
; 0.0 seconds of system run time
; 159,005,155 CPU cycles
; 0 page faults and
; 80 bytes consed.
;
NIL
So yes, your version is running about three times the speed.
More importantly, if we up the problem size, to get more
accurate timing, their version overflows the control stack.
CL-USER> (dolist (f '(add1 add2))
(time (funcall f 10000000 10000000)))
Warning: TIME form in a non-null environment, forced to interpret.
Compiling entire form will produce more accurate times.
; Evaluation took:
; 1.22 seconds of real time
; 1.172575 seconds of user run time
; 0.0 seconds of system run time
; 427,571,228 CPU cycles
; 0 page faults and
; 80 bytes consed.
;
Warning: TIME form in a non-null environment, forced to interpret.
Compiling entire form will produce more accurate times.
A control stack overflow has occurred: the program has entered the yellow
control stack guard zone. Please note that you will be returned to the
Top-Level if you enter the red control stack guard zone while debugging.
; Evaluation aborted
So your code is clearly better. My only caveat is to point
out that you correctly didn't try timing it yourself. It is
Peano Arithmetic. It is only a toy example and it is not
worth bothering about performance issues. The best code is
often the code that is easiest to read, even if it only goes
at one third the speed of code that has been re-arranged.
Alan Crowe
Edinburgh
Scotland
On Jan 28, 4:55 am, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
<snip>
> So your code is clearly better. My only caveat is to point
> out that you correctly didn't try timing it yourself. It is
> Peano Arithmetic. It is only a toy example and it is not
> worth bothering about performance issues. The best code is
> often the code that is easiest to read, even if it only goes
> at one third the speed of code that has been re-arranged.
Many thanks Alan, that was very informative!
Regards,
Ray
>
> Alan Crowe
> Edinburgh
> Scotland
From: Christian Haselbach
Subject: Re: Question about a problem from Little Schemer
Date:
Message-ID: <epgsu6$bgh$3@online.de>
Alan Crowe wrote:
> Your code follows naturally from defining addition thus
>
> x + 0 = x
> x + Sy = Sx + y
>
> Their code follows naturally from defining addition thus
>
> x + 0 = x
> x + Sy = S(x + y)
>
> I was surprised when I saw their code because my memory told
> me that the first definition was the common one, but
> checking on the web
While the first version is faster, the second version has
some nice properties (which do not matter in an innermost
evaluation scenario).
For example assume the following definition of > :
0 > 0 = F
Sx > 0 = T
Sx > Sy = x > y
Then the (x + Sy) > 0 evaluates as follows:
(x + Sy) > 0
-> S(x + y) > 0
-> T
With the first definition of +, it evaluates as follows:
(x + Sy) > 0
(Sx + y) > 0
And now we need to have a concrete y to continue.
That is probably the reason you normally find the second
definition of +.
Regards,
Christian
Christian Haselbach <······@muon.de> writes:
> For example assume the following definition of > :
> 0 > 0 = F
> Sx > 0 = T
> Sx > Sy = x > y
>
> Then the (x + Sy) > 0 evaluates as follows:
> (x + Sy) > 0
> -> S(x + y) > 0
> -> T
That is fascinating. I think it would be fun to download
ACL2 and play with it. I guess that using it successfully
depends on getting the axioms just right, in the way that
you have illustrated.
Alan Crowe
Edinburgh
Scotland