On Thursday, 26 June 2014 at 21:01:40 UTC, Araq wrote:
>>
>> Spark is a research language that does not work, as I've discovered and discussed with you before. It cannot be determined the max stack usage at compile time, again, this is the halting problem.
>>
>
> What?! It's easily solvable: Forbid recursion and indirect
> function calls and it's guaranteed that the program only requires
> a fixed size stack and you can compute an upper bound of the
> required stack size at compile-time. Which is BTW exactly what
> OpenCL does as GPUs tend to have no stacks.

Actually CUDA do have recursion, and indirect function calls.

Am 29.06.2014 11:07, schrieb ponce:
> On Thursday, 26 June 2014 at 21:01:40 UTC, Araq wrote:
>>>
>>> Spark is a research language that does not work, as I've discovered
>>> and discussed with you before. It cannot be determined the max stack
>>> usage at compile time, again, this is the halting problem.
>>>
>>
>> What?! It's easily solvable: Forbid recursion and indirect
>> function calls and it's guaranteed that the program only requires
>> a fixed size stack and you can compute an upper bound of the
>> required stack size at compile-time. Which is BTW exactly what
>> OpenCL does as GPUs tend to have no stacks.
>
> Actually CUDA do have recursion, and indirect function calls.

Not only that, CUDA offers a quite usable C++ subset whereas OpenCL keeps us in the primitive C land.

--
Paulo

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).

On Thursday, 26 June 2014 at 09:35:20 UTC, Walter Bright wrote:
> Stack overflows are not safety problems when a guard page is used past the end of the stack. Then, overflow checking is done in hardware. Guard pages aren't currently used for fibers, so overflows are a real danger there.

But a page is only 2K? So what happens if you skip more than 2K and never touch the guard page? Does D prove that the stack pointer is never moved more than 2K-1 without a read or write in that range?

Guard pages on a flat memory model are not as safe as a segmented memory model.

A compromise would be to inject runtime checks to see if there is sufficient stack space whenever you move the stack pointer and remove them when you can prove that there is enough room. E.g. collapse the checks into larger spans of stack space by propagating them upwards in the call chain.

Anyway, minimizing stack space is very useful for fibers in scientific simulations or real time systems since you want to be able to run as many as you can fit into memory. Each actor/agent could be very simple so I would not rule out the ability to prove it in most cases for some domains.

(Sorry for the very late answer.)

Walter Bright:

>>> Stack overflows are not safety problems when a guard page is used past the end
>>> of the stack.
>> It's not a safety problem in Erlang/Rust, because those languages are designed to manage such failures in a good way.
>
> Please explain.

The idea comes from Erlang language (and perhaps Erlang has coped it from something else), and then Rust copied it (and indeed, if you look at the "Influenced by" list here, you see Erlang, and it Rust has copied only the Erlang feature I am discussing here: http://en.wikipedia.org/wiki/Rust_language ).

Erlang systems must be extremely reliable, they run telecommunication systems that must just always work, with only seconds or minutes of downtime every year. But programs contains errors and bugs, so to face this problem Erlang (and now Rust) has chosen a curious strategy.

The description, see "4.3 Error handling philosophy" at page 104-109, a PDF file:
http://www.erlang.org/download/armstrong_thesis_2003.pdf

It's also a bit explained here, at the "3. What is fault-tolerance" section:
http://stackoverflow.com/questions/3172542/are-erlang-otp-messages-reliable-can-messages-be-duplicated/3176864#3176864

Some more technical info:
http://www.erlang.org/doc/design_principles/sup_princ.html

Bye,
bearophile

(Sorry for the very delayed answers.)

----------------

Walter Bright:

> Oh well, there goes about 90% of D programs and pretty much all use of the D runtime library!

Right. On the other hand the need for such strict safety requirements that forbid stack overflows, is not present in desktop software, it's for uncommon systems, with limited resources, that need to work reliably, like some car/plane electronics.

So when you have such needs you are willing to throw away 90% of D libs/Phobos, and probably to not use d-runtime too :-) And in such cases it's good to have as much compile-time assurances as possible.


> And I suspect the subset of D programs
> that don't have indirection or recursion is so small as to not be worth the bother.
>
> I do know there are a class of applications, for example in critical embedded
> systems, were recursion and indirection, and even allocation, are not allowed.
> Using D in such cases would require eschewing using Phobos, and some other care
> taken,

Right. And people in such fields are looking for something safer and nicer than C + a ton of static tests (and many of them don't seem to love Ada).

----------------

Andrei Alexandrescu:

>My understanding is that it can be done but only with annotations or whole program analysis.<

I agree. But people in (example) automotive industry could be (and probably are) willing to do both.

Thus is a specialized niche, so adding such annotations to D language seems too much. So I've suggested to add enough static introspection (and some way to attach compile-time semantics to UDAs) to allow specialized programmers to add to D those annotations (and leave other more complex tests to external tools).

----------------

H. S. Teoh:

> I think the compiler should be able to tell, at least for the simplest
> cases, whether something will definitely stop recursing.

Whiley language (http://whiley.org/ ) is able to do this, with the "loop variant" you write.

----------------

deadalnix:

>> 2) By alloca();
>
> it is @system

I'd like to use something like alloca (or much better something similar to the variable-length stack-allocated partially-library-defined arrays of C++14/C++17) even in @safe code (but not in stack-constrained code we were discussing here).


> We should have a page reserved at the end of the stack so we can
> throw when reaching it. The compiler can ensure we don't bypass
> it in case 1.

OK.

----------------

Ola Fosheim Grøstad:

> A compromise would be to inject runtime checks to see if there is
> sufficient stack space whenever you move the stack pointer

Run-time tests in debug mode seem useful.

Bye,
bearophile

On 7/10/2014 5:08 AM, bearophile wrote:
> (Sorry for the very late answer.)
>
> Walter Bright:
>
>>>> Stack overflows are not safety problems when a guard page is used past the end
>>>> of the stack.
>>> It's not a safety problem in Erlang/Rust, because those languages are
>>> designed to manage such failures in a good way.
>>
>> Please explain.
>
> The idea comes from Erlang language (and perhaps Erlang has coped it from
> something else), and then Rust copied it (and indeed, if you look at the
> "Influenced by" list here, you see Erlang, and it Rust has copied only the
> Erlang feature I am discussing here: http://en.wikipedia.org/wiki/Rust_language ).
>
> Erlang systems must be extremely reliable, they run telecommunication systems
> that must just always work, with only seconds or minutes of downtime every year.
> But programs contains errors and bugs, so to face this problem Erlang (and now
> Rust) has chosen a curious strategy.
>
> The description, see "4.3 Error handling philosophy" at page 104-109, a PDF file:
> http://www.erlang.org/download/armstrong_thesis_2003.pdf
>
> It's also a bit explained here, at the "3. What is fault-tolerance" section:
> http://stackoverflow.com/questions/3172542/are-erlang-otp-messages-reliable-can-messages-be-duplicated/3176864#3176864
>
>
> Some more technical info:
> http://www.erlang.org/doc/design_principles/sup_princ.html
>
> Bye,
> bearophile

Thanks for the links!

On Monday, 30 June 2014 at 08:00:37 UTC, Ola Fosheim Grøstad
wrote:
> On Thursday, 26 June 2014 at 09:35:20 UTC, Walter Bright wrote:
>> Stack overflows are not safety problems when a guard page is used past the end of the stack. Then, overflow checking is done in hardware. Guard pages aren't currently used for fibers, so overflows are a real danger there.
>
> But a page is only 2K? So what happens if you skip more than 2K and never touch the guard page? Does D prove that the stack pointer is never moved more than 2K-1 without a read or write in that range?
>

The compiler can ensure that you hit at least every 4k or so. It
doesn't look like a very hard constraint to have a volatile load
per untouched 4k of stack (which should be very rare).

On Friday, 11 July 2014 at 17:28:39 UTC, deadalnix wrote:
> The compiler can ensure that you hit at least every 4k or so. It
> doesn't look like a very hard constraint to have a volatile load
> per untouched 4k of stack (which should be very rare).

Sure, it should be possible to work it into the backend at the code-gen level.

For fibers without recursion I think the most powerful approach would be to do whole program analysis to establish a minimum of N for the typical case (without unbounded recursion). Of course, then alloca also have to extend the stack and do book keeping of the additional storage  taken by alloca() or simply have a separate alloc-stack.

On 7/11/2014 10:28 AM, deadalnix wrote:
> The compiler can ensure that you hit at least every 4k or so.

And it already does.