Tail Recusion

For the Compleat Fan
Locked
rapega
Posts: 1
Joined: Sun Jun 03, 2012 5:44 am

Tail Recusion

Post by 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
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: Tail Recusion

Post by Lutz »

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

Code: Select all

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 all

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

conan
Posts: 52
Joined: Sat Oct 22, 2011 12:14 pm

Re: Tail Recusion

Post by 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 all

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 all

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 all

(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
Posts: 5289
Joined: Thu Sep 26, 2002 4:45 pm
Location: Pasadena, California
Contact:

Re: Tail Recusion

Post by 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 all

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

void mt(int n)
{
printf("%d\n", 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
Posts: 2038
Joined: Tue Nov 29, 2005 8:28 pm
Location: latiitude 50N longitude 3W
Contact:

Re: Tail Recusion

Post by cormullion »


rickyboy
Posts: 607
Joined: Fri Apr 08, 2005 7:13 pm
Location: Front Royal, Virginia

Re: Tail Recusion

Post by rickyboy »

cormullion wrote:Guido agrees with Lutz.. :)

http://neopythonic.blogspot.pt/2009/04/ ... ation.html
You can't be serious ...

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

cormullion
Posts: 2038
Joined: Tue Nov 29, 2005 8:28 pm
Location: latiitude 50N longitude 3W
Contact:

Re: Tail Recusion

Post by cormullion »

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

xytroxon
Posts: 296
Joined: Tue Nov 06, 2007 3:59 pm
Contact:

Re: Tail Recusion

Post by xytroxon »

cormullion wrote: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/a ... 765790.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
"Many computers can print only capital letters, so we shall not use lowercase letters."
-- Let's Talk Lisp (c) 1976

Locked