I have some code where it is up to the user how many times a function will be called recursively.
Can it be detected when the system limit for it is reached ? (It gives seg faults now...but, I'd like to throw exceptions when it happens.)
I have some code where it is up to the user how many times a function will be called recursively.
Can it be detected when the system limit for it is reached ? (It gives seg faults now...but, I'd like to throw exceptions when it happens.)
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:
I'm considering putting a constant limit....but it seems like taking the easy way out.Code:(defun foo(n)(foo (* n n)))
Here is a 'transcript':
It took about 2 mins for the error.[minlisp](defun foo(n)(foo (* n n)))
foo
[minlisp](foo 68778)
Segmentation fault (core dumped)
[manasij7479@manasijn minlisp]$
Last edited by manasij7479; 12-02-2011 at 05:37 AM.
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.
I would say yes, since recursion is defined by the base case. Anything that evaluates to if (true), always, being the implicit base case for infinite recursion.
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.
Last edited by MK27; 12-02-2011 at 08:03 AM.
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
- 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.
Stick close to your desks and never program a thing,
And you all may sit in the standards commitee!
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.
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
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.
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
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.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
C programming resources:
GNU C Function and Macro Index -- glibc reference manual
The C Book -- nice online learner guide
Current ISO draft standard
CCAN -- new CPAN like open source library repository
3 (different) GNU debugger tutorials: #1 -- #2 -- #3
cpwiki -- our wiki on sourceforge
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.