Software Assurance Reference Dataset

[via Digitalmars-d]

On Thursday, 26 June 2014 at 09:35:20 UTC, Walter Bright wrote:
> On 6/26/2014 2:19 AM, bearophile wrote:
>> One kind of problem left is to avoid stack overflows.
>
> In general, stack overflow checking at compile time is the 
> halting problem. It needs a runtime check.

No, "is N bytes of stack is sufficient" is decidable if you don't 
count in the heap as an unlimited resource that preserves state. 
So it is not the halting problem. The halting problem would be 
"is K bytes of stack sufficient, for K in [0,infinity>".

You can also do a worst case analysis that requires you to 
specify too much stack, but proves that it is sufficient. E.g. 
set the recursive depth to the max number of nodes in a binary 
tree, even if you know that it will never get that deep.

But since you allow calls into C code you need extra annotations 
and probably have more pressing issues to deal with… (like GC).