The future of lambda delegates

[Mikola Lysenko]

"Lionello Lunesu" <lio at lunesu.remove.com> wrote in message 
news:ec1a8l$19ab$1 at digitaldaemon.com...
> kris wrote:
>> I'm hoping there's another option, better than both the above (or the 
>> above combination) ~ it's seems apparent that neither present an ideal 
>> resolution
>
> Delegates are a pretty advanced programming technique. I don't think it 
> would be bad solution to just let the programmer mark the exceptional 
> cases. At least until a fail-safe general solution becomes available.
>

Well, I think everyone can agree that the best possible solution would be an 
omniscient static escape analyzer.  It would guarantee that programs use the 
stack as much as possible, and only resort to the heap when absolutely 
necessary.

Sadly, such a program is an abomination of logic - its very existence a 
paradox.  So, we will have to settle for whatever escape analysis logic is 
available.  Real world analyzers have that unfortunate "maybe" case.  If we 
want to automate everything, then we need to assume heap allocation for all 
of the places where the implementation could fail.  As Kris pointed out, 
this is not good enough.

Here is what I propose:
1. The default frame-type is determined through static escape analysis.
2. Functions can be declared to explicitly contain a stack based frame.
3. If the escape analyzer determines that a function declared with a stack 
frame contains an escaping delegate, then it may raise an error.

With these rules, we use all the information an escape analyzer can tell us. 
As Walter posted,

>Static escape analysis can yield 3 results:
>
>1) guaranteed to not escape
>2) might escape
>3) does escape

Simply marking everything except the first case as heap allocated does not 
distinguish between cases 2 and 3.  Nor does adding an "ultimate" override, 
since it could overpower the analyzer even in case 3.

This weaker override can only be applied to cases 1 and 2.  In case 1, it is 
merely redundant, but should be legal.  In case 3, it is blatantly wrong, so 
the compiler should say so.  In case 2, it is impossible for the compiler to 
determine whether the human was right or wrong, so we can allow the usage. 
This allows the programmer to effectively use each piece of information.

Here is a visual representation of this argument using ascii-tables:
[monospace]
Omniscient analyzer:
+-------------------------+----------------+
| Escape Analyzer Result  | Interpretation |
+-------------------------+----------------+
| No Escape               | Stack          |
| Does Escape             | Heap           |
+-------------------------+----------------+
2 total cases: {Stack, Heap}

Without an override (non-omniscient):
+-------------------------+----------------+
| Escape Analyzer Result  | Interpretation |
+-------------------------+----------------+
| No Escape               | Stack          |
| Might Escape            | Heap           |
| Does Escape             | Heap           |
+-------------------------+----------------+
2 total cases: {Stack, Heap}

With an ultimate override:
+-------------------------+-------------+----------+
| Escape Analyzer Result  | No Override | Override |
+-------------------------+-------------+----------+
| No Escape               | Stack       | Stack    |
| Might Escape            | Heap        | Stack    |
| Does Escape             | Heap        | Stack    |
+-------------------------+-------------+----------+
2 total cases: {(Stack, Stack), (Heap, Stack)}

With an weak override:
+-------------------------+-------------+----------+
| Escape Analyzer Result  | No Override | Override |
+-------------------------+-------------+----------+
| No Escape               | Stack       | Stack    |
| Might Escape            | Heap        | Stack    |
| Does Escape             | Heap        | Error    |
+-------------------------+-------------+----------+
3 total cases: {(Stack, Stack), (Heap, Stack), (Heap, Error)}
[/monospace]

Moreover, this strategy is independent of the type of escape analyzer used. 
The quality of the static checking could become a quality of implementation 
issue, much like the optimizer.  Picking one specific strategy would require 
integrating it into the core specification, which will create headaches for 
future generations of D compilers. This method is flexible enough to allow a 
short-term simple implementation, which can later be extended into a more 
powerful and accurate system.