Tail Recusion

[rapega]

Hi,



I am new to newlisp and did my standard test to it:



(define (mt n) (println n)(mt (+ 1 n)))

(mt 1)



that should run infinte in any tail recursive lisp.

It crashed at 2048 in newlisp, but amazingly fast!



Is there no tail recursion detection or am doing it wrong?



Thank you,



Ralf

[Lutz]

There is no tail-recursion optimization in newLISP. You can increase the stack size when starting newLISP, e.g.:

Code Select Expand


newlisp -s 10000

for a stack size of 10000. For each stack position newLISP will reserve 80 memoy bytes by adjusting some other stacks used internally (result stack and environment stack). You can inquire the stack size using sys-info:

Code Select Expand

> (sys-info)
(449 268435456 384 1 0 10000 0 4640 10403 1030)
> (sys-info 5)
10000
>


Welcome to newLISP!

[conan]

Sorry to bring back to life such an old post. But I left aside newlisp for a while and now I'm catching up. And this got me puzzled:



I tested the crashing function with -s 47000 and I get a stack overflow:

Code Select Expand


46998

ERR: call or result stack overflow : +
called from user defined function simple-crash


(simple-crash has the same definition given by rapega)



However when I call the same function with -s 48000 I get a segmentation fault:

Code Select Expand


47617
Segmentation fault (core dumped)


I tried to examine the process by stopping it around the number it will crash, to look for clues to what's happening, so I wrote this one:

Code Select Expand


(define (crash x stop)
(println x)
(if (>= x stop)
(begin
(println "Press ENTER to continue...")
(read-char)))

(crash (+ 1 x) stop))


But couldn't find anything relevant. Memory seems fine, I recover around 100 Kb after the crash. And I didn't see anything strange going on.



So my question is why I get a segmentation fault with a bigger stack? Shouldn't I get another stack overflow just with a bigger number?



BTW I'm using newLISP v.10.4.5

[Lutz]

The limitation is not set by newLISP but by the OS and different on each platform, you are running on. For your program, the highest limit seems to be on FreeBSD with 599099 and the lowest Windows XP with 16250.



Even a simple C program will segfault at 262015 on OSX and at 65095 on Windows:

Code Select Expand

#include <stdio.h>
#include <stdlib.h>

void mt(int n)
{
printf("%dn", n);
mt(n + 1);
}

int main()
{
mt(1);
exit(0);
}


But the much more important point is the following:



Don't just replace iteration with recursion. Leave recursion for appropriate problems like the traversal of tree structure and similar problems, then you will almost never hit a stack limit even with the standard 2047, newLISP starts up.



Replacing iteration with recursion seems to be interesting from a theoretical view of functional programming but is impractical for readable and efficient programs. That is why almost no programming language outside of academia implements tail recursion optimization.

[cormullion]

Guido agrees with Lutz.. :)



http://neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html">//http://neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html

[rickyboy]

Guido agrees with Lutz.. :)



http://neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html">//http://neopythonic.blogspot.pt/2009/04/tail-recursion-elimination.html

You can't be serious ...



If you are, that post contains so many wrong ideas, I don't know where to start.

[cormullion]

I've no idea what he's on about to be honest...)

[xytroxon]

I've no idea what he's on about to be honest...)

It's just one of those on-going fundamental difference in personal philosophy that come to a head now and then...



http://www.thetimes.co.uk/tto/news/uk/article3765790.ece">//http://www.thetimes.co.uk/tto/news/uk/article3765790.ece



I find that there are pluses and minuses to both sides' views, but I have real work to do.



Warp Factor 10.4.8.    Engage.



-- xytroxon