Im just starting to program in lisp so please bear with me. As an
exercise, I was supposed to write the + function for 2
integers(symbols). This is what I wrote
(defun our+ (n m)
(cond
( (zerop m) n)
(t (+ (1+ n) (1- m) ) ) ) )
The suggested answer is as follows.
(defun our-add ( n m)
(cond
( (zerop m) n)
(t (1+ (our-add n (1- m) ) ) ) ) )
My question is this: Is there any difference in performance between the
first and the second?
Granted, I want to follow what the author has deemed accurate but I
dont want to do so blindly. Thanks in advance.
zion_zii wrote:
> Im just starting to program in lisp so please bear with me. As an
> exercise, I was supposed to write the + function for 2
> integers(symbols). This is what I wrote
>
> (defun our+ (n m)
> (cond
> ( (zerop m) n)
> (t (+ (1+ n) (1- m) ) ) ) )
>
> The suggested answer is as follows.
>
> (defun our-add ( n m)
> (cond
> ( (zerop m) n)
> (t (1+ (our-add n (1- m) ) ) ) ) )
>
> My question is this: Is there any difference in performance between the
> first and the second?
> Granted, I want to follow what the author has deemed accurate but I
> dont want to do so blindly. Thanks in advance.
AFAI can see, the suggested version decrements m first (all the way
through) and then leaves the recursion, adding the 1 m times.
Your version decrements m and increments n immediately, and then goes on
to add them -- wait, your code doesn't recur, i.e. use "our+", but it
uses "+". So you're cheating ;)
If you use "our+" instead of "+" the operations are basically the same,
but happen in a different order.
Another difference is that the suggested version is recursing, while
your version would be tail-recursive, i.e. running in constant space and
possibly faster, AFAI can see right now.
Just keep in mind to separate builtin math from the kind of math you're
doing here, i.e. don't cheat using builtin "+".
--
The road to hell is paved with good intentions.
Ulrich Hobelmann wrote:
> zion_zii wrote:
>
>> Im just starting to program in lisp so please bear with me. As an
>> exercise, I was supposed to write the + function for 2
>> integers(symbols). This is what I wrote
>>
>> (defun our+ (n m)
>> (cond
>> ( (zerop m) n)
>> (t (+ (1+ n) (1- m) ) ) ) )
>>
>> The suggested answer is as follows.
>>
>> (defun our-add ( n m)
>> (cond
>> ( (zerop m) n)
>> (t (1+ (our-add n (1- m) ) ) ) ) )
>>
>> My question is this: Is there any difference in performance between the
>> first and the second?
>> Granted, I want to follow what the author has deemed accurate but I
>> dont want to do so blindly. Thanks in advance.
This is a weird exercise. I don't see how it would teach you anything
about Lisp because you can do exactly the same exercise in any
programming language that supports recursive calls.
> Just keep in mind to separate builtin math from the kind of math you're
> doing here, i.e. don't cheat using builtin "+".
Both versions cheat because even the second version uses the 1+ and 1-
functions. It's no wonder that the OP feels confused because the
suggested answer is confusing.
If you don't want to cheat, you can only do this by encoding numbers
manually, for example implicitly by the number of atoms in a list, or
some such.
Again, this exercise doesn't teach anything about Lisp.
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
(message (Hello 'Pascal)
(you :wrote :on '(Wed, 30 Nov 2005 00:20:33 +0100))
(
PC> If you don't want to cheat, you can only do this by encoding numbers
PC> manually, for example implicitly by the number of atoms in a list, or
PC> some such.
or better using Church numerals :)
(setq *zero* (lambda (f x) x))
(setq *one* (lambda (f x) (funcall f x)))
(setq *two* (lambda (f x) (funcall f (funcall f x))))
(defun val (n) "function that converts Church numerals to normal ones"
(funcall n #'1+ 0))
;;let's test that it works:
;;CL-USER> (mapcar #'val (list *zero* *one* *two*))
;;(0 1 2)
(defun succ (n) "1+" (lambda (f x) (funcall f (funcall n f x))))
(defun pred (n) "1-" (lambda (f x)
(funcall
(funcall n (lambda (g) (lambda (h) (funcall h (funcall g f))))
(lambda (u) x))
(lambda (u) u))))
;;test them
;;CL-USER> (val (pred *one*))
;;0
;;CL-USER> (val (succ *two*))
;;3
;;CL-USER> (val (succ (pred *one*)))
;;1
;;note that there are no negative Church numerals (at least i can't imagine
such)
;;CL-USER> (val (pred *zero*)
;;0
;;also an interesting fact
;;CL-USER> (val #'funcall)
;;1
(defun zero? (n) (funcall n (constantly nil) t))
;;and now our recursive plus
(defun plus (n m)
(if (zero? n) m
(plus (pred n) (succ m))))
;;CL-USER> (val (plus *two* (succ *two*)))
;;5
;;working but fantastically slow
;;actually there's a simplier version
(defun plus* (n m)
(lambda (f x)
(funcall n f
(funcall m f x))))
PC> Again, this exercise doesn't teach anything about Lisp.
this one teaches that functional programming in Lisp is tricky but possible
:)
P.S. Zermelo numerals can be simulated as
(setq *zero* nil)
(setq *one* '(nil))
(setq *two* '((nil)))
(defun succ (n) (cons n nil))
(defun pred (n) (car n))
(defun val (n) (if n (1+ (val (pred n))) 0))
(defun zero? (n) (null n))
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")
Pascal Costanza wrote:
> Both versions cheat because even the second version uses the 1+ and 1-
> functions. It's no wonder that the OP feels confused because the
> suggested answer is confusing.
Well, I'm assuming that 1+ and 1- are primitives to use. Of course it
would be nicer to have something like a zero (or nil) and an add1
function that pushes a value onto the list...
> If you don't want to cheat, you can only do this by encoding numbers
> manually, for example implicitly by the number of atoms in a list, or
> some such.
But in the end I think it doesn't really matter how the primitives work,
as long as you use only them.
> Again, this exercise doesn't teach anything about Lisp.
Nothing specific, no. Maybe the OP is just getting a feel for the language.
I don't think posting a (even useless) Lisp program on c.l.l hurts. If
anything, it makes more people comfortable with ((syntax)).
--
The road to hell is paved with good intentions.
(defun our+ (n m)
(cond
( (zerop m) n)
(t (+ (1+ n) (1- m) ) ) ) )
my bad the above should be
(defun our+ (n m)
(cond
( (zerop m) n)
(t (our+ (1+ n) (1- m) ) ) ) )
Question:
What is tail recursion?
Basically tail recursion is when a recursive function performs the
recursive call as the last expression. Compilers that perform tail call
optimization can transform the code into an iterative form.
http://en.wikipedia.org/wiki/Tail_recursion
--
Scott Bell
zion_zii wrote:
> (defun our+ (n m)
> (cond
> ( (zerop m) n)
> (t (+ (1+ n) (1- m) ) ) ) )
>
> my bad the above should be
>
> (defun our+ (n m)
> (cond
> ( (zerop m) n)
> (t (our+ (1+ n) (1- m) ) ) ) )
>
> Question:
>
> What is tail recursion?
(1+ (bla foo)) : here bla isn't a tail call, i.e. the function has to
remember that it will call 1+ when "bla" returns. But 1+ is a tail
call. In your book (or whatever) example that's recursive, you have all
these "1+"s that have to be remembered.
In the above version, the "t" is evaluated, and the rest in the COND is
run in tail position. The parameters to our+ can also be evaluated
directly (no recursion), and our+ is again in tail position. So it can
just update "n" and "m" and loop to its own beginning.
--
The road to hell is paved with good intentions.
On Tue, 29 Nov 2005 14:35:47 -0800, zion_zii wrote:
> Im just starting to program in lisp so please bear with me. As an
> exercise, I was supposed to write the + function for 2
> integers(symbols). This is what I wrote
>
> (defun our+ (n m)
> (cond
> ( (zerop m) n)
> (t (+ (1+ n) (1- m) ) ) ) )
>
> The suggested answer is as follows.
>
> (defun our-add ( n m)
> (cond
> ( (zerop m) n)
> (t (1+ (our-add n (1- m) ) ) ) ) )
This exercise looks like an adaptation of Exercise 1.9 in SICP, shown
here:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html#%_toc_%_sec_1.2.1
I recommend reading the treatment in the enclosing Section 1.2.1, "Linear
Recursion and Iteration", as linked above, with the following adaptation
of the two examples to CL:
Each of the following two procedures defines a method [sic] for adding two
positive integers in terms of the procedures 1+, which increments its
argument by 1, and 1-, which decrements its argument by 1.
(defun our-+ (a b)
(if (= a 0)
b
(1+ (our-+ (1- a) b))))
(defun our-+ (a b)
(if (= a 0)
b
(our-+ (1- a) (1+ b))))
I hope that clarifies what your book's author seems to be introducing.
--
Stephen Compall
Email: My username is s11. My domain is member..org, but insert the
abbreviation for `Free Software Foundation' between the dots.
"zion_zii" <·········@gmail.com> writes:
> Im just starting to program in lisp so please bear with me. As an
> exercise, I was supposed to write the + function for 2
> integers(symbols). This is what I wrote
>
> (defun our+ (n m)
> (cond
> ( (zerop m) n)
> (t (+ (1+ n) (1- m) ) ) ) )
>
> The suggested answer is as follows.
>
> (defun our-add ( n m)
> (cond
> ( (zerop m) n)
> (t (1+ (our-add n (1- m) ) ) ) ) )
>
> My question is this: Is there any difference in performance between the
> first and the second?
> Granted, I want to follow what the author has deemed accurate but I
> dont want to do so blindly. Thanks in advance.
>
Your version is tail recursive.
The trace is instructive:
common-lisp-user [8]: (trace our+)
Warning: Function OUR+ already TRACE'd, retracing it.
(OUR+)
common-lisp-user [9]: (our+ 4 4)
0: (OUR+ 4 4)
1: (OUR+ 5 3)
2: (OUR+ 6 2)
3: (OUR+ 7 1)
4: (OUR+ 8 0)
4: OUR+ returned 8
3: OUR+ returned 8
2: OUR+ returned 8
1: OUR+ returned 8
0: OUR+ returned 8
8
Notice how all the work is done going "in". This means you don't need
to remember anything for the "out" part. So you could change the
calls to jumps after replacing the arguments with the updated
values. (A call saves the state of the computation, asks another
function to do something, and then continues where it left off. A
jump simply says, "I'm done, go do something else.")
So you could write something like
(defun my+ (x y)
(tagbody
:start
(cond
((zerop y)
(go :finish))
(t (setf x (1+ x))
(setf y (1- y))
(go :start)))
:finish)
x)
Here's the trace of the suggested answer:
common-lisp-user [11]: (trace our-add)
Warning: Function OUR-ADD already TRACE'd, retracing it.
(OUR-ADD)
common-lisp-user [12]: (our-add 4 4)
0: (OUR-ADD 4 4)
1: (OUR-ADD 4 3)
2: (OUR-ADD 4 2)
3: (OUR-ADD 4 1)
4: (OUR-ADD 4 0)
4: OUR-ADD returned 4
3: OUR-ADD returned 5
2: OUR-ADD returned 6
1: OUR-ADD returned 7
0: OUR-ADD returned 8
8
Notice here that the "in" part decrements the y argument but does
nothing to the x argument. The function has to remember to do that
after the call returns. That means the function has to remember where
it was so it can pick up where it left off after the call returns. So
it can't just jump off to do something else because it hasn't finished
what it is doing yet. The "remembering" means that it uses extra
space. Thus if you were to run your version with a lisp that does
tail call optimization, you could run it on arbitrarily large
arguments. But OUR-ADD would eventually fill up the stack.
CL-USER> (our+ 10 1000000)
1000010
CL-USER> (our+ 10 10000000)
10000010
CL-USER> (our+ 10 100000000)
100000010
CL-USER>
CL-USER> (our-add 10 1000000)
1000010
CL-USER> (our-add 10 10000000)
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.
The problem with your version is that it is harder to axiomatize. The
suggested answer is equivalent to
x + 0 = x
x + (1+ y) = (1+ (x + y))
This corresponds to an induction so you can do proofs with it, where y
is the induction variable. Remember the induction principle:
If S(0) is true and
S(v) -> S(v + 1) is true
then S(v) is true.
You can see how this corresponds to the axioms for addition above.
But yours is
x + 0 = x
x + (1 + y) = (1+ x) + y
This doesn't correspond to the induction principle because both
variables change.
Here's what I mean by a proof.
Prove x + 1 = 1 + x.
Base case: x = 0.
0 + 1 = 1 + 0
The right side, 1 + 0, is equal to 1 by the first addition axiom.
The left side becomes
0 + (1+ 0) (Definition of successor)
which becomes (1+ (0 + 0)) by the second addition axiom.
which becomes
(1+ 0) by the first addition axiom.
This becomes 1 by the definition of successor. So you get
1 = 1 which is true.
Inductive case:
x + 1 = 1 + x -> (1+ x) + 1 = 1 + (1+ x)
That is, show that (1+ x) + 1 = 1 + (1+ x) is true
given the assumption that x + 1 = 1 + x is true.
(1+ x) + 1 becomes (1+ ((1+ x) + 0)) (second addition axiom)
which becomes (1+ (1+ x)) (first addition axiom)
1 + (1+ x) becomes (1+ (1 + x)) (second addition axiom)
which becomes (1+ (x + 1)) (induction hypothesis)
which becomes (1+ (1+ (x + 0))) (second addition axiom)
which becomes (1+ (1+ x)) (first addition axiom)
so the two sides are equal.
Having fun yet?
--
Fred Gilham ······@csl.sri.com
Do you know how it feels to be evil? It feels *normal*. A
conscience is so easily seared. -- "Nick"