Thread: Can it be detected if stack space is about to expire?

Any technique to do that would be system specific.

Generally, it would be better to either code your function non-recursively, or write it more carefully so it does not recurse so deeply.

Originally Posted by grumpy

Any technique to do that would be system specific.

Generally, it would be better to either code your function non-recursively, or write it more carefully so it does not recurse so deeply.

Well it is a lisp(sort of !) interpreter I wrote.. and I can't stop the user from defining stupid functions like:

Code:

(defun foo(n)(foo (* n n)))

I'm considering putting a constant limit....but it seems like taking the easy way out.

Here is a 'transcript':

[minlisp](defun foo(n)(foo (* n n)))
foo
[minlisp](foo 68778)
Segmentation fault (core dumped)
[manasij7479@manasijn minlisp]$

It took about 2 mins for the error.

A smart way would be to change the interpreter so it detects infinitely recursive functions, rather than executing them and going into the nether-nether.

This is an issue for all runtime interpreters, I think. IMO it is better to handle at runtime than compile time and I'm sure that is the most common method. Ie, rather than assessing the code, allow it to run, but set an arbitrary limit (maybe: configurable) to the depth of the recursion and when this is exceeded throw an error. It doesn't guarantee avoiding a seg fault, but it will catch more cases and be less prone to mistake. I'd rather risk a seg fault due to my own foolishness or ignorance (most programmers learn about this fairly early, don't they? You only have to get hamstrung once to get it.) than be told incorrectly there is a problem with my code.

- Use libsigsegv
- Check that it's supported in your platform
- Install a stack overflow handler

You can handle the stack overflow in several ways. Typically, you would longjmp back to the fault point and either inform of the stack overflow, or handle the recursion differently.

There is nothing wrong with a recursive function that potentially uses infinite stack space... You should assume the stack can grow arbitrarily. Running out of stack is the same as running out of memory -- your program simply ran out of memory, no program can be expected to function properly without enough memory.

The problem is grace when running out of memory. Most suggestions how to fix this are probably going to involve rearchitecting your code to some degree. For instance you can have a stack that you control directly rather than using the processor stack, but this stops you from representing recursive processing by actually recursing, which is nothing to sneeze at. The only way to avoid major changes to the code is with machine-specific hacks, like querying the stack pointer or catching the memory exception and processing it a special way if it's a stack exception.

Originally Posted by Elkvis

you have an interpreter - essentially a virtual machine - why not implement your own managed stack? you manage objects allocated by the interpreted code, why not also manage its stack in software?

I think the problem might be that a call in the interpreted code is implemented by a call in the VM, this deeply entwines the program stack with the machine stack. This is the same problem Python has and why "Stackless Python" is an ongoing wish-I-had sort of dream. Tying the interpreter stack to the machine stack is a recipe for all kinds of awful problems, not just oppressive stack use to store interpreter variables. In fact I doubt that's what the stack is being used for, this sounds like a problem with recursion.

Originally Posted by brewbuck

There is nothing wrong with a recursive function that potentially uses infinite stack space...

I disagree brewbuck.

A function that actually attempts to use more resources than are available to it is fundamentally flawed.

This flaw needs to be addressed as early as possible in the development process. In requirements, always. In architecture and design if possible, so the problem is prevented completely. At run time if necessary, with mitigation of the effects that occur (if that mitigation is less expensive to achieve than an architectural change) but that should not be the default treatment. If the problem can be anticipated at all, and can be reasonably addressed, leaving it unaddressed is incompetence and laziness by a software developer.

The only cases that are forgivable are when a problem is not actually identified (for example, insufficient time is available to identify edge cases, and developers are not super-human), or if the cost to address it is excessive compared with the benefit (which then makes it a management decision, and the risks should be borne by management).

In a functional language it might be a good idea to implement recursion on your own stack. They tend to use the stack more than imperative languages, and use the heap a lot less. Otherwise you would need a large pre-allocated stack, and you wouldn't be able to resize it, because it would invalidate pointers in the stack.

Originally Posted by grumpy

I disagree brewbuck.

A function that actually attempts to use more resources than are available to it is fundamentally flawed.

But that's not the same thing as one which potentially does so, which is why I said it's a bad idea to make a decision based on the code at compile time.

Vis, implementing a stack, I know the perl does this -- it's a global heap structure.

Originally Posted by MK27

But that's not the same thing as one which potentially does so, which is why I said it's a bad idea to make a decision based on the code at compile time.

That depends on the compile-time analysis.

There are plenty of cases where the compiler or interpreter can unambiguously assess that a function is infinitely recursive (for example, a function calling itself with the same data it received, directly or indirectly, or a function unconditionally calling itself). In those cases, it is reasonable to make a decision at compile time.

There are also plenty of cases where the compiler can assess a likelihood of infinite recursion. Those should be reported (for example, a compiler warning) but I agree it would be inappropriate to flatly refuse to compile.