Stack Size?

Stack Size?

[Robert Uhl <ruhl@4dv.net>]

I have the following empirical-integral function defined:

(define (integral func from to)
  (define step (/ (- to from) 2048))
  (define (my-int func from to)
    (if (>= from to)
	(func to)
	(+ (func from) (my-int func (+ from step) to))))
  (my-int func from to))

I recognise that this may not be the most attractive of ways to do it,
but it should do the job.  Unfortunately, the following sequence of
actions causes a stack overflow:

(define (q x) (- 10 (* 8 x)))
(integral q 0 1.25)

How deep can guile's stack be?  This example does _not_ crash on
umb-scheme, which is interesting.  Can anyone suggest a workaround?

-- 
Robert Uhl <ruhl@4dv.net>
Fight to your last cartridge, then fight with your bayonets.
No surrender.  Fight to the death.
                  --Gen. Henri Guisan, Switzerland, July '40

_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Joshua Judson Rosen]

On Mon, Aug 05, 2002 at 03:27:37AM -0600, Robert Uhl <ruhl@4dv.net> wrote:
> I have the following empirical-integral function defined:
> 
> (define (integral func from to)
>   (define step (/ (- to from) 2048))
>   (define (my-int func from to)
>     (if (>= from to)
> 	(func to)
> 	(+ (func from) (my-int func (+ from step) to))))
>   (my-int func from to))
> 
> I recognise that this may not be the most attractive of ways to do it,
> but it should do the job.  Unfortunately, the following sequence of
> actions causes a stack overflow:
> 
> (define (q x) (- 10 (* 8 x)))
> (integral q 0 1.25)
> 
> How deep can guile's stack be?  This example does _not_ crash on
> umb-scheme, which is interesting.  Can anyone suggest a workaround?

I don't know about guile's stack-limitations, but I can suggest that
you write your function in a tail-recursive way, which would allow you
to avoid the stack, e.g.:

(define (integral func from to)
  (define step (/ (- to from) 2048))
  (define (my-int func from to base-value)
    (if (>= from to)
        (+ base-value (func to))
        (my-int func (+ from step) to (+ base-value (func from)))))
  (my-int func from to 0))

_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Neil Jerram]

>>>>> "ruhl@4dv" == ruhl@4dv net (Robert Uhl <<ruhl@4dv.net>)> writes:

    ruhl@4dv> How deep can guile's stack be?

From the HEAD CVS manual, in the index under `stack overflow':

Stack overflow
--------------

   Stack overflow errors are caused by a computation trying to use more
stack space than has been enabled by the `stack' option.  They are
reported like this:

     (non-tail-recursive-factorial 500)
     -|
     ERROR: Stack overflow
     ABORT: (stack-overflow)

   If you get an error like this, you can either try rewriting your
code to use less stack space, or increase the maximum stack size.  To
increase the maximum stack size, use `debug-set!', for example:

     (debug-set! stack 200000)
     =>
     (show-file-name #t stack 200000 debug backtrace depth 20 maxdepth 1000 frames 3 indent 10 width 79 procnames cheap)
     
     (non-tail-recursive-factorial 500)
     =>
     122013682599111006870123878542304692625357434...

   If you prefer to try rewriting your code, you may be able to save
stack space by making some of your procedures "tail recursive".  For a
description of what this means, see *Note Proper tail recursion:
(r5rs)Proper tail recursion.


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Robert Uhl <ruhl@4dv.net>]

I've re-written the function, but it seems to me that it'd perhaps
make more sense for Guile to simply grow the stack until it runs out
of memory.  Is there a technical reason this doesn't happen?

-- 
Robert Uhl <ruhl@4dv.net>
I really have to hand it to Fox this time, they've hit an all new low.
And I just love new lows.  They remind me that progress is growth, and
growth is a two way street.                              --Rick Felice

_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Neil Jerram]

>>>>> "ruhl@4dv" == ruhl@4dv net (Robert Uhl <<ruhl@4dv.net>)> writes:

    ruhl@4dv> I've re-written the function, but it seems to me that it'd perhaps
    ruhl@4dv> make more sense for Guile to simply grow the stack until it runs out
    ruhl@4dv> of memory.  Is there a technical reason this doesn't happen?

No idea, I'm afraid.  Perhaps it's considered a good thing for a
language to allow applications to have a grip on their stack usage?

According to the output of `(debug-options 'full)', you can turn off
stack size checking by setting the limit to 0, i.e.:

(debug-set! stack 0)

        Neil



_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Robert Uhl <ruhl@4dv.net>]

Neil Jerram <neil@ossau.uklinux.net> writes:
> 
> > I've re-written the function, but it seems to me that it'd perhaps
> > make more sense for Guile to simply grow the stack until it runs
> > out of memory.  Is there a technical reason this doesn't happen?
> 
> No idea, I'm afraid.  Perhaps it's considered a good thing for a
> language to allow applications to have a grip on their stack usage?

In a dynamic, functional language such as Scheme--or indeed any
language--I'm not so certain I agree.  While on the one hand switching
to a tail function is certainly more efficient, it seems to me that
that's not always the case.  And certainly it can often be much
clearer to write a bunch of functions which call bunches of functions
which...

> According to the output of `(debug-options 'full)', you can turn off
> stack size checking by setting the limit to 0, i.e.:
> 
> (debug-set! stack 0)

Well, I'll not do that unless I need to--but I'd really rather I
didn't need to.  Que sera sera, I s'pose:-)

It seems to me somewhat broken that one must set a debug option
explicitly off.  Sort of a command-line switch --behave-yourself, when
that should be the default behaviour.  Certainly, stack size checks
may be _very_ useful when testing code.  But just as certainly, in
production those same checks are a nuisance, and can cause code to
break.

Or am I just being foolish?  It's a definite possibility, I'll
grant:-)

-- 
Robert Uhl <ruhl@4dv.net>
The purpose of the First Amendment's free-speech guarantee was pretty
clearly to protect political discourse.  But liberals reject the notion
that free speech is therefore limited to political topics, even broadly
defined.  True, that purpose is not inscribed in the amendment itself.
But why leap to the conclusion that a broadly worded constitutional
freedom (`the right of the people to keep and bear arms') is narrowly
limited by its stated purpose, unless you're trying to explain it away?
My New Republic colleague Mickey Kaus says that if liberals interpreted
the Second Amendment the way they interpret the rest of the Bill of
Rights, there would be law professors arguing that gun ownership is
mandatory.       --Michael Kinsley Washington Post, January 8, 1990

_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Mikael Djurfeldt]

ruhl@4dv.net (Robert Uhl <ruhl@4dv.net>) writes:

> Neil Jerram <neil@ossau.uklinux.net> writes:
> > 
> > > I've re-written the function, but it seems to me that it'd perhaps
> > > make more sense for Guile to simply grow the stack until it runs
> > > out of memory.  Is there a technical reason this doesn't happen?
> > 
> > No idea, I'm afraid.  Perhaps it's considered a good thing for a
> > language to allow applications to have a grip on their stack usage?

Guile is supposed to be "nice" towards novice users.  Infinite
recursions is a very common error.  Without a stack check, the effect
is that the machine freezes due to excessive swapping, preventing the
novice user from even examining what has happened.

> It seems to me somewhat broken that one must set a debug option
> explicitly off.  Sort of a command-line switch --behave-yourself, when
> that should be the default behaviour.  Certainly, stack size checks
> may be _very_ useful when testing code.  But just as certainly, in
> production those same checks are a nuisance, and can cause code to
> break.

It's probably a bad idea to use large stacks in production code and,
if not, it's rather easy to set the option to whatever one wants.

Maybe the correct setting is a very large stack?

M

_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Mikael Djurfeldt]

ruhl@4dv.net (Robert Uhl <ruhl@4dv.net>) writes:

> Neil Jerram <neil@ossau.uklinux.net> writes:
> > 
> > > I've re-written the function, but it seems to me that it'd perhaps
> > > make more sense for Guile to simply grow the stack until it runs
> > > out of memory.  Is there a technical reason this doesn't happen?
> > 
> > No idea, I'm afraid.  Perhaps it's considered a good thing for a
> > language to allow applications to have a grip on their stack usage?

Guile is supposed to be "nice" towards novice users.  Infinite
recursions is a very common error.  Without a stack check, the effect
is that the machine freezes due to excessive swapping, preventing the
novice user from even examining what has happened.

> It seems to me somewhat broken that one must set a debug option
> explicitly off.  Sort of a command-line switch --behave-yourself, when
> that should be the default behaviour.  Certainly, stack size checks
> may be _very_ useful when testing code.  But just as certainly, in
> production those same checks are a nuisance, and can cause code to
> break.

It's probably a bad idea to use large stacks in production code and,
if not, it's rather easy to set the option to whatever one wants.

Maybe the correct setting is a very large stack?

M



_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Mikael Djurfeldt]

ruhl@4dv.net (Robert Uhl <ruhl@4dv.net>) writes:

> Neil Jerram <neil@ossau.uklinux.net> writes:
> > 
> > > I've re-written the function, but it seems to me that it'd perhaps
> > > make more sense for Guile to simply grow the stack until it runs
> > > out of memory.  Is there a technical reason this doesn't happen?
> > 
> > No idea, I'm afraid.  Perhaps it's considered a good thing for a
> > language to allow applications to have a grip on their stack usage?

Guile is supposed to be "nice" towards novice users.  Infinite
recursions is a very common error.  Without a stack check, the effect
is that the machine freezes due to excessive swapping, preventing the
novice user from even examining what has happened.

> It seems to me somewhat broken that one must set a debug option
> explicitly off.  Sort of a command-line switch --behave-yourself, when
> that should be the default behaviour.  Certainly, stack size checks
> may be _very_ useful when testing code.  But just as certainly, in
> production those same checks are a nuisance, and can cause code to
> break.

It's probably a bad idea to use large stacks in production code and,
if not, it's rather easy to set the option to whatever one wants.

Maybe the correct setting is a very large stack?

M



_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Robert Uhl <ruhl@4dv.net>]

Mikael Djurfeldt <mdj@kvast.blakulla.net> writes:
> 
> Guile is supposed to be "nice" towards novice users.  Infinite
> recursions is a very common error.  Without a stack check, the
> effect is that the machine freezes due to excessive swapping,
> preventing the novice user from even examining what has happened.

We've all written infinite loops in our novitiate; we've all written
infinitely-recursing programmes.  But I've rarely used environments
which cared until I exhausted the machine.

The novice can still kill the currently running bit, and then step
through his code if he desires...

> It's probably a bad idea to use large stacks in production code and,
> if not, it's rather easy to set the option to whatever one wants.

It's a probably a bad idea to use large amounts of memory in
production code.  Except that sometimes it's necessary.  The situation
with excessive stack usage is not quite analogous (I'm not going to
argue in favour of excessive function calls!), but somewhat similar.

-- 
Robert Uhl <ruhl@4dv.net>
The strongest reason for the right for the people to bear arms is, as a
last resort, to protect themselves against tyranny in government.  
                                              --Thomas Jefferson


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Rob Browning]

Mikael Djurfeldt <mdj@kvast.blakulla.net> writes:

> Guile is supposed to be "nice" towards novice users.  Infinite
> recursions is a very common error.  Without a stack check, the
> effect is that the machine freezes due to excessive swapping,
> preventing the novice user from even examining what has happened.

Yeah, though I *was* surprised the first time I had a perfectly good
recursion fall over in guile, one that I believe had been working fine
in another scheme.

I tend to think that if we're going to enforce a stack limit, it
should be fairly high by default.  Otherwise if you write a module
that you know will be likely to use very large stacks for normal
inputs, you've got to either communicate the need to raise the stack
limit to everyone using your module via documentation, or you've got
to raise the limit with a debug-set! call inside the module, and the
latter solution is unworkable when you have two modules that have
different ideas of how high the stack limit needs to be, since the
result becomes dependent on load order.

BTW, how does guile's stack limit apply to guile threads?  Is the
limit per-thread or global?

(A part of me wonders whether or not we're just infringing on ulimit's
 territory here...)

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG=1C58 8B2C FB5E 3F64 EA5C  64AE 78FE E5FE F0CB A0AD


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Lynn Winebarger]

On Sunday 01 September 2002 12:13, Rob Browning wrote:
> Mikael Djurfeldt <mdj@kvast.blakulla.net> writes:
> 
> > Guile is supposed to be "nice" towards novice users.  Infinite
> > recursions is a very common error.  Without a stack check, the
> > effect is that the machine freezes due to excessive swapping,
> > preventing the novice user from even examining what has happened.

       There should be a smarter way to choose this kind of stack
enforcement, that could be implemented if guile moves towards
faster continuations (i.e. requiring more analysis than the parser
does now) and stops using a single stack.  I'm not sure exactly
what I'm talking about, but I have a vague idea that this
is probably done in most optimizing scheme interpreters/compilers.
I think Dybvig's dissertation is on this very topic.
     Then a single stack could be used for certain simple types
of recursions that would catch the novice cases and, while
still being annoying for someone who knows what they're doing
when they write a simple,deep recursion, might avoid some
of the most egregious trespasses against the non-novice.

> I tend to think that if we're going to enforce a stack limit, it
> should be fairly high by default.  Otherwise if you write a module
> that you know will be likely to use very large stacks for normal
> inputs, you've got to either communicate the need to raise the stack
> limit to everyone using your module via documentation, or you've got
> to raise the limit with a debug-set! call inside the module, and the
> latter solution is unworkable when you have two modules that have
> different ideas of how high the stack limit needs to be, since the
> result becomes dependent on load order.

       It's a bad idea for a default.  Most novices are not novices 
forever, yet compiling this option in seems to optimize for that case.  If
this is aimed at the application scripting user, the application
can have a button for novice/expert mode.  If it's for just
plain old general purpose REPL usage, everybody's entitled
to experience at least one accidental infinite recursion.

> (A part of me wonders whether or not we're just infringing on ulimit's
>  territory here...)
    The answer is yes.  Actually, the answer is plain old scheme mode
should never run out of stack because it is not C.  Application writers
should be able to tweak that behaviour, perhaps, or maybe they should
just be able to set a bound on how much system memory the gc is
allowed to allocate.  You know, register a hook for when that happens
so they can ask the user whether to proceed or whatever.  There would
probably be some standard system exception this could throw if the
user wanted to give up so the system wouldn't have to abort.

Lynn


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user

Re: Stack Size?

[Paul Jarc]

Rob Browning <rlb@defaultvalue.org> wrote:
> or you've got to raise the limit with a debug-set! call inside the
> module, and the latter solution is unworkable when you have two
> modules that have different ideas of how high the stack limit needs
> to be, since the result becomes dependent on load order.

They could check the current limit and change it only if it needs to
be raised.  FWIW.


paul


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-user