Hello-
I was at my very first try at recursion an obtaining a palindrome when
the following snippet of code brought CMUCL to a grinding halt (in fact,
almost my whole system, as it kept eating more memory away):
* (defun palindrome (x)
(cond ((null x) 0)
(t (car (list (palindrome (nthcdr (- (length x) 1) x)))))))
PALINDROME
* (palindrome '(1 2 3 4 5 6 7 8 9))
[GC threshold exceeded with 2,157,496 bytes in use. Commencing GC.]
[GC completed with 1,502,592 bytes retained and 654,904 bytes freed.]
[GC will next occur when at least 3,502,592 bytes are in use.]
[GC threshold exceeded with 3,517,184 bytes in use. Commencing GC.]
[GC completed with 3,517,184 bytes retained and 0 bytes freed.]
[GC will next occur when at least 5,517,184 bytes are in use.]
[GC threshold exceeded with 5,530,376 bytes in use. Commencing GC.]
[GC completed with 5,532,328 bytes retained and -1,952 bytes freed.]
[GC will next occur when at least 7,532,328 bytes are in use.]
[GC threshold exceeded with 7,547,560 bytes in use. Commencing GC.]
[GC completed with 7,549,512 bytes retained and -1,952 bytes freed.]
[GC will next occur when at least 9,549,512 bytes are in use.]
[GC threshold exceeded with 9,560,656 bytes in use. Commencing GC.]
[GC completed with 9,562,608 bytes retained and -1,952 bytes freed.]
[GC will next occur when at least 11,562,608 bytes are in use.]
[GC threshold exceeded with 11,577,840 bytes in use. Commencing GC.]
[GC completed with 11,573,944 bytes retained and 3,896 bytes freed.]
[GC will next occur when at least 13,573,944 bytes are in use.]
[GC threshold exceeded with 13,585,080 bytes in use. Commencing GC.]
[GC completed with 13,587,040 bytes retained and -1,960 bytes freed.]
[GC will next occur when at least 15,587,040 bytes are in use.]
Interrupted at #x1000C930.
Restarts:
0: [CONTINUE] Return from BREAK.
1: [ABORT ] Return to Top-Level.
Debug (type H for help)
(UNIX::SIGINT-HANDLER #<unavailable-arg>
#<unavailable-arg>
#.(SYSTEM:INT-SAP #x3DFA81C0))
0]
And control G saved the day!
I'm using CMUCL on Debian Woody pre-3.0 on ILISP with XEmacs 21.
Could this have been an expected result?
Thanks in advance,
Best reagards,
Henry
···········@uol.com.br
________________________________________________________
Micro$oft-Free Human 100% Debian GNU/Linux
KMFMS "Bring the genome to the people!"
From: Brian Palmer
Subject: Re: Newbie emergency - Attempt at recursion broguth CMUCL to a halt
Date:
Message-ID: <0whhelv2r7n.fsf@fable3.Stanford.EDU>
synthespian <···········@uol.com.br> writes:
> Hello-
>
> I was at my very first try at recursion an obtaining a palindrome when
> the following snippet of code brought CMUCL to a grinding halt (in fact,
> almost my whole system, as it kept eating more memory away):
>
> * (defun palindrome (x)
> (cond ((null x) 0)
> (t (car (list (palindrome (nthcdr (- (length x) 1) x)))))))
> And control G saved the day!
> I'm using CMUCL on Debian Woody pre-3.0 on ILISP with XEmacs 21.
> Could this have been an expected result?
Yep. Think of what happens when x is '(1). (length x) is 1, so (nthcdr
(- 1 1) '(1)) == (nthcdr 0 '(1)), which is the result of applying
nthcdr 0 times to the list. This returns the list itself, so
palindrome is called again with the exact same arguments.
--
If nature has made any one thing less susceptible than all others of
exclusive property, it is the action of the thinking power called an
idea, which an individual may exclusively possess [only] as long as he
keeps it to himself.... -- Thomas Jefferson
From: Pierpaolo BERNARDI
Subject: Re: Newbie emergency - Attempt at recursion broguth CMUCL to a halt
Date:
Message-ID: <kn2z8.74698$vF6.2235810@news2.tin.it>
"synthespian" <···········@uol.com.br> ha scritto nel messaggio ········································@uol.com.br...
> Hello-
>
> I was at my very first try at recursion an obtaining a palindrome when
> the following snippet of code brought CMUCL to a grinding halt (in fact,
> almost my whole system, as it kept eating more memory away):
>
> * (defun palindrome (x)
> (cond ((null x) 0)
> (t (car (list (palindrome (nthcdr (- (length x) 1) x)))))))
TRACE is your friend.
Why you do (CAR (LIST x)) ?
What is this function supposed to return? (the cond has two branches,
in one it returns 0, in the other it returns the result of a recursive call,
so this function either does not terminate or returns 0).
What is (NTHCDR (- (LENGTH X) 1) X) when is X is bound
to (FOO BAR BAZ) ?
What is (NTHCDR (- (LENGTH X) 1) X) when is X is bound
to (BAZ) ?
HTH.
P.
On Sun, 28 Apr 2002 23:39:12 -0300, Pierpaolo BERNARDI wrote:
> "synthespian" <···········@uol.com.br> ha scritto nel messaggio
> ········································@uol.com.br...
>> Hello-
>>
>> I was at my very first try at recursion an obtaining a palindrome when
>> the following snippet of code brought CMUCL to a grinding halt (in
>> fact, almost my whole system, as it kept eating more memory away):
>>
>> * (defun palindrome (x)
>> (cond ((null x) 0)
>> (t (car (list (palindrome (nthcdr (- (length x) 1) x)))))))
>
> TRACE is your friend.
>
> Why you do (CAR (LIST x)) ?
>
> What is this function supposed to return? (the cond has two branches,
> in one it returns 0, in the other it returns the result of a recursive
> call, so this function either does not terminate or returns 0).
>
> What is (NTHCDR (- (LENGTH X) 1) X) when is X is bound to (FOO BAR BAZ)
> ?
>
> What is (NTHCDR (- (LENGTH X) 1) X) when is X is bound to (BAZ) ?
>
>
> HTH.
>
> P.
Hi-
I wanted to obtain the last element of a list of indeterminate length.
Then, I would go on to reversing the elements one by one and consing them
(not there yet). But then I made this huge confusion and got stuck, CMUCL
coughed, and spitted, and I came here to ask you guys.
Thanks for the helping hand,
Cheers
henry
···········@uol.com.br
|
________________________________________________________
Micro$oft-Free Human 100% Debian GNU/Linux
KMFMS "Bring the genome to the people!"
"synthespian" <···········@uol.com.br> wrote in message ······································@uol.com.br...
>
> I wanted to obtain the last element of a list of indeterminate length.
> Then, I would go on to reversing the elements one by one and consing them
> (not there yet). But then I made this huge confusion and got stuck, CMUCL
> coughed, and spitted, and I came here to ask you guys.
>
You did the right thing by asking us.
If you want the last element of a list, you can use the LAST
function to get the last CONS in the list and take the car.
(defun last-element (list)
(car (last list)))
Or you could be a bit more perverse (and more general!)
(defun last-element (sequence)
(find-if (constantly t) sequence :from-end t))
From: Kalle Olavi Niemitalo
Subject: Re: Newbie emergency - Attempt at recursion broguth CMUCL to a halt
Date:
Message-ID: <874rhrq35u.fsf@Astalo.y2000.kon.iki.fi>
synthespian <···········@uol.com.br> writes:
> I wanted to obtain the last element of a list of indeterminate length.
There is a function called LAST.
* (last '(a b c d e))
(E)
* (last '())
NIL
See also REVERSE and APPEND (or NCONC).