4 ms·
Do you mean buffer overflow? What language protects against stack overflow?
by jayd16 9y ago
Do you mean buffer overflow? What language protects against stack overflow?
- kibwen 9y agoIt's not languages but compilers that protect against stack overflow. Rust has contributed code to LLVM that causes stack overflows to abort the process (via guard pages and stack cookies), which means that theoretically you could enable this for C and C++ as well. See https://github.com/rust-lang/rust/issues/16012 https://github.com/rust-lang/rust/issues/16012
- nine_k 9y agoIf you forbid self-recursive functions, the required depth of stack can be statically analyzed. I believe such tools exist even for (a feature-limited subset of) C.
- kibwen 9y agoNot just self-recursion, but all recursion, including transitive mutual recursion. I think it may be possible to do this via strictly lexically-scoped symbols (so imagine C with no forward declarations). Might still be ways to sneak recursion in there though.
- scatters 9y agoThat's what fix point combinators are for. The Y combinator won't work in a language like C++, but the Z will work fine. For example, here's Z in C++14, used to compute 5 factorial: https://godbolt.org/g/se5B8u https://godbolt.org/g/se5B8u
- kibwen 9y agoYeah, I specifically had combinators in mind when considering ways to sneak recursion in. :P And it occurs to me you'd have to forbid function pointers too.
- greiskul 9y agoYup, and you would probably not be able to do Object Oriented Programming either (or have to limit it horrendously), cause an object is similar to a closure, and you therefore can use it for unbounded recursion.
- nine_k 9y agoYes, I meant any recursive calls via a chain of calls to other functions. I think proving that no recursion exists should be relatively simple, just keep following the call graph and keep a set of the nodes (functions) called; you either reach the terminal node(s), or reach an already-visited node again, which means a recursion exists.
- soberhoff 9y agoWhat if functions are first class? Then imagine a function gets passed in as an argument and called. You won't know what function you're calling until runtime.
- SilasX 9y agoI thought that self recursion was fine so long as the calls were provably "smaller problems" than the function calling them, something like "bounded recursion".
- nine_k 9y agoIf you can prove that the recursion is bounded, great! But sometimes it is hard, and I'm afraid it's equivalent to the halting problem in general case. Without recursion, though, finding the maximal depth of the call graph is definitely solvable, and likely not even very hard.
- SilasX 9y agoReally? I thought the problems were equivalent, of proving that e.g. a loop vs its recursive equivalent were bounded. Side note: an interesting case is the Stable Marriage Problem. It's easy to write the O(n) algorithm and prove its bound, but it's hard to translate into a bounded recursive algorithm that does the same thing. (At least as far as I understand -- I searched it on Stack Overflow and that's what it said, and I've tried the problem itself. A Coq fanatic insisted that "if you can prove the run time is bounded it's easy to write the bounded recursive equivalent" but somehow that never translated into an actual insight on how to do it.)
- UncleMeat 9y agoProving that a loop is bounded is also undecidable.
- Thiez 9y agoOnly in the general case. In many/most loops that humans would find useful in practice you can prove termination.
- nine_k 9y agoIn general case, yes, of course. There are still cases where you can prove that a recursion is bounded (I suppose something like dependent types could help here). There are definitely cases where you can prove that a loop is bounded, because the semantics of the language requires them to: a loop with a counter (not otherwise mutated), iteration over a known finite structure, etc. Well, both C++ and Haskell allow you to use compiler features that are undecidable in general case, but usually work well in practical cases. Also, if e.g. your recursion / loop analysis is taking too long, you can just stop the analyzer. If the code can't be reasonably proved right, it should be considered wrong (with a chance of a false negative).