I am using a recursive algorithm in designing a common Lisp program.
It overflows easily.
Does anybody know a way to prevent it without changing my algorithm?
I know some functional language has left fold and right fold. Is there
anything
like that in Lisp?
Richard
From: Friedrich Dominicus
Subject: Re: >>>>How to prevent stack overflow?<<<<
Date:
Message-ID: <38060F5F.94ADB642@inka.de>
Richard wrote:
>
> I am using a recursive algorithm in designing a common Lisp program.
> It overflows easily.
>
> Does anybody know a way to prevent it without changing my algorithm?
> I know some functional language has left fold and right fold. Is there
> anything
> like that in Lisp?
A hopefully not so wild guess. If you can make it tail-recursive an
overflow should not occur.
Regards
Friedrich
From: Reini Urban
Subject: Re: >>>>How to prevent stack overflow?<<<<
Date:
Message-ID: <380b0388.3835164@judy>
Richard wrote:
>I am using a recursive algorithm in designing a common Lisp program.
>It overflows easily.
>
>Does anybody know a way to prevent it without changing my algorithm?
since nobody answered this one satisfyingly enough, I'll make my try:
1) only by using an implementation which is does "tail-call elimination"
or as said, is "properly tail-recursive". Scheme systems require to be
tail-recursive to be conformant (BTW: nevertheless some are not
conformant in this regard), most (but not all) lisp systems seem to
support it as well.
even if your system does this, your algorithm must be changed to be
tail-recursive. This is generally quite easy and explained e.g. in the
book "Lisp" by Winston/Horn.
In my system which is not properly tail-recursive (as yours) I usually
give the advise to change the algorithm to use no recursion at all (->
iterative algorithm), or sometimes it helps to limit the depth of the
recursion, e.g. by splitting the data structure or recurse not that
often.
The iterative version of your algorithm may look ugly and unreadable but
once you verified the correctness of your algorithm and the additional
helper variables (counters, stack, ...) you may regard to the iterative
version as throw-away code.
>I know some functional language has left fold and right fold. Is there
>anything like that in Lisp?
sorry, cannot answer this. my guess is that right fold means proper
tail-recursion and left fold inlining.
--
Reini Urban
http://xarch.tu-graz.ac.at/autocad/news/faq/autolisp.html
······@xarch.tu-graz.ac.at (Reini Urban) writes:
> Richard wrote:
> >I am using a recursive algorithm in designing a common Lisp program.
> >It overflows easily.
> >
> >Does anybody know a way to prevent it without changing my algorithm?
...
> even if your system does this, your algorithm must be changed to be
> tail-recursive. This is generally quite easy and explained e.g. in the
> book "Lisp" by Winston/Horn.
>
> In my system which is not properly tail-recursive (as yours) I usually
> give the advise to change the algorithm to use no recursion at all (->
> iterative algorithm), or sometimes it helps to limit the depth of the
> recursion, e.g. by splitting the data structure or recurse not that
> often.
>
> The iterative version of your algorithm may look ugly and unreadable but
> once you verified the correctness of your algorithm and the additional
> helper variables (counters, stack, ...) you may regard to the iterative
> version as throw-away code.
Some algorithms are inherently recursive (tree traversal being one of
them). You cannot eliminate it. You can only masquerade it at a very
high program complexity price. Remember "the Peaceman" thread? :)
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
From: John Atwood
Subject: Re: >>>>How to prevent stack overflow?<<<<
Date:
Message-ID: <7uhr3f$3b7$1@news.NERO.NET>
Reini Urban <······@sbox.tu-graz.ac.at> wrote:
>Richard wrote:
>>I am using a recursive algorithm in designing a common Lisp program.
>>It overflows easily.
<snip>
>>I know some functional language has left fold and right fold. Is there
>>anything like that in Lisp?
>
>sorry, cannot answer this. my guess is that right fold means proper
>tail-recursion and left fold inlining.
The Loop facility, especially the collect and append clauses, are
analogous to folds in functional languages.
John Atwood
From: Paul Rudin
Subject: Re: >>>>How to prevent stack overflow?<<<<
Date:
Message-ID: <wkhfjlw13m.fsf@scientia.com>
>>>>> "John" == John Atwood <·······@bronze.cs.orst.edu> writes:
John> The Loop facility, especially the collect and append clauses,
John> are analogous to folds in functional languages.
Only very loosely; REDUCE is a better analogue...
Sent via Deja.com http://www.deja.com/
Before you buy.
From: David Hanley
Subject: Re: >>>>How to prevent stack overflow?<<<<
Date:
Message-ID: <380B5B2B.30F5AEB6@ncgr.org>
Richard wrote:
> I am using a recursive algorithm in designing a common Lisp program.
> It overflows easily.
>
> Does anybody know a way to prevent it without changing my algorithm?
You probably need to make it tail recursive. If you post some
more details, or perhaps the code, people can help.
dave
Richard <·······@cs.auckland.ac.nz> writes:
> I know some functional language has left fold and right fold. Is
> there anything like that in Lisp?
If you're talking about the same thing as I think you are (i.e. foldl
and foldr as described by Bird & Wadler), you need to look at REDUCE
* (reduce #'- '(3 2 1)) ;; ((3 - 2) - 1)
0
* (reduce #'- '(3 2 1) :from-end t) ;; (3 - (2 - 1))
2
There are various keyword arguments governing what to do at the edges
of the sequence.
-dan