Stack overflow

Hi,

I heard that one of the differences between Scheme and CL is that Scheme is "proper tail recursive" and CL isn't. Until today I'm not 100% what that could mean but I think I'm seeing an effect of it here.

(defun my-make-list (n)
  (cond
   ((< n 1) nil)
   (t (cons nil (my-make-list (- n 1))))))

If I run this on Lispworks with let's say merely n=200 I get a stack overflow, if I run it in Scheme with +100000 I just have to wait a little, but no stack overflow.

What I really do like about CL and Scheme is the excessive use of recursion, and the parenthesis too.
Does this mean I need to switch back to iteration when dealing with lists of over 200 elements in CL?
Setting the *stack-size* to a higher level?

If so ............. STUFF THAT!!!

Guenther

Re: Stack overflow

I'm not sure that the function you have, as written, is properly tail 
recursive anyway, but at any rate, for a properly tail recursive 
function I believe that Lispworks will do the optimization you want if 
you have declared the right optimization settings, so I'd consult the 
part of the manual that deals with that.

Howard

Guenther Schmidt wrote:
> Hi,
> 
> I heard that one of the differences between Scheme and CL is that Scheme 
> is "proper tail recursive" and CL isn't. Until today I'm not 100% what 
> that could mean but I think I'm seeing an effect of it here.
> 
> (defun my-make-list (n)
>  (cond
>   ((< n 1) nil)
>   (t (cons nil (my-make-list (- n 1))))))
> 
> If I run this on Lispworks with let's say merely n=200 I get a stack 
> overflow, if I run it in Scheme with +100000 I just have to wait a 
> little, but no stack overflow.
> 
> What I really do like about CL and Scheme is the excessive use of 
> recursion, and the parenthesis too.
> Does this mean I need to switch back to iteration when dealing with 
> lists of over 200 elements in CL?
> Setting the *stack-size* to a higher level?
> 
> If so ............. STUFF THAT!!!
> 
> Guenther
> 
> 

-- 
Howard Ding
<hading@hading.dnsalias.com>

Re: Stack overflow

Guenther Schmidt wrote:

> ...
> If I run this on Lispworks with let's say merely n=200 I get a stack 
> overflow, if I run it in Scheme with +100000 I just have to wait a 
> little, but no stack overflow.

Compile it then run it again. Do you have same stack overflow?

Jong-won

Re: Stack overflow

Dear all,

First of all thanks for your advice.

However having to write machine oriented code is *not* what I had in mind when I started with CL. I want the system (or the implementation) to take care of these trivialities automatically without having to worry about it myself.

Otherwise I might as well have gone for C.

I mean there are things that work fine up and until factor x but as soon as your application hits x+1 it crashes? I want to focus on logic, and the logic in the previous code was sound. A programing language that can't guarantee that code working with x+1 works the same as it did with x what good is that?

Guenther

Guenther Schmidt wrote:

> Hi,
> 
> I heard that one of the differences between Scheme and CL is that Scheme 
> is "proper tail recursive" and CL isn't. Until today I'm not 100% what 
> that could mean but I think I'm seeing an effect of it here.
> 
> (defun my-make-list (n)
>  (cond
>   ((< n 1) nil)
>   (t (cons nil (my-make-list (- n 1))))))
> 
> If I run this on Lispworks with let's say merely n=200 I get a stack 
> overflow, if I run it in Scheme with +100000 I just have to wait a 
> little, but no stack overflow.
> 
> What I really do like about CL and Scheme is the excessive use of 
> recursion, and the parenthesis too.
> Does this mean I need to switch back to iteration when dealing with 
> lists of over 200 elements in CL?
> Setting the *stack-size* to a higher level?
> 
> If so ............. STUFF THAT!!!
> 
> Guenther
> 
> 
>

Re: Stack overflow

* Guenther Schmidt wrote:
> (defun my-make-list (n)
>   (cond
>    ((< n 1) nil)
>    (t (cons nil (my-make-list (- n 1))))))

This function isn't properly tail recursive.  It might be that some
compilers are smart enough to convert it into a tail-recursive version
of itself, and then convert that to iteration.  However I very much
doubt that scheme-the-language would specify that this should happen.

(The tail-recursive equivalent is something like

(defun my-make-list/tr (n)
  (labels ((mml (m a)
             (if (< m 1) a (mml (1- m) (cons nil a)))))
    (mml n '())))

)

While it's true that scheme makes some guarantees about tail calls
that CL does not, in fact many CL compilers, including LW, do convert
tail calls, possibly at suitable optimisation settings.  Given the
above tail-recursive variant, and using the default optimisation
settings, LW does in fact convert the tail calls to iteration.

So what you are seeing isn't anything to do with tail-call conversion.
Both the scheme version and the CL version are building some huge
stack, and then unwinding it.  The difference is, in fact, that the
implementation of Scheme you are using has a larger stack limit than
LW's default limit.  I'm not really familiar with the details of the
LW implementation, but many CLs use the stack support from the
underlying hardware, and this is often somewhat limited (especially
for interpreted code as I suspect yours was where you have dozens of
interpreter frames).  Many scheme implementations simply heap-allocate
the stack, since they more-or-less need to do this anyway to support
call/cc.  Using the hardware stack support makes things like
coexistance with other languages (`foreign' code) a whole lot easier,
and that's often a design goal for CL implementations.

From the tone of your messages, I'd guess that Scheme is a much more
suitable language for you.  Or perhaps one of the pure functional
languages.  Or maybe woodwork? 

--tim