Escape analysis (full scope analysis proposal)

[Michel Fortin]

On 2008-11-13 00:53:50 -0500, Andrei Alexandrescu 
<SeeWebsiteForEmail at erdani.org> said:

> Michel Fortin wrote:
>> Everywhere I said there was no need for named regions, I also said 
>> named regions could be kept to ease the syntax. That said, I'm not so 
>> sure named regions are that good at simplifying the syntax. In your 
>> assign example above, the named-region version has an error: it forces 
>> the two pointers to be of the same region. That could be fine, but, 
>> assuming you're assigning to *p, it'd be more precise to write it like 
>> that:
>> 
>>     void assign(region R1, region R2)(int*R1* p, int*R2 r) if (R1 <= R2);
> 
> No, the code is correct as written (without the if). You may want to 
> reread the paper with an eye for region subtyping rules. This partly 
> backs up my point: understanding region analysis may be quite a burden 
> for the average programmer. Even you, who took pains to think through 
> everything and absorb the paper, are having trouble. And me too to be 
> honest :o).

Ok, I've reread that part and it's true that using Cyclone's subtyping 
rules it'd work fine with only one region name because Cyclone 
implicitly creates two regions from that, the first being a subset of 
the other, just as I wrote explicitly here. But what I missed out was 
one of Cyclone's syntactic construct, not a concept of regions.

... or perhaps we have a different notion of what is a syntax and what 
is a concept?


>> Once we get there, I think the no-named region syntax is better.
> 
> This is invalidated by the wrong assertion above.

Yes and no. It's true that Cyclone's region subtyping makes the syntax 
prettier. On the other side, the programmer has to be aware of how it 
works, and especially aware that changing the order his arguments will 
implicitly change the region relationship between them.


>> That said, for the swap example, where both values need to share the 
>> same region, the named region notation is simpler:
>> 
>>     void swap(region R)(int*R a, int*R b);
>>     void swap(int* a, int* b) if (region(a) == region(b));
> 
> No, for that swap there is no need to specify any region. You can swap 
> ints in any two regions. Probably you meant to use int** throughout.

Hum, you're right, I meant to make these "ref int*".


>> But I'd argue that most of the time regions do not need to be equal, 
>> but are subset or superset of each other, so reusing variable names 
>> makes more sense in my opinion.
> 
> Don't forget that using a region name twice may actually work with two 
> different regions, so far as they are in a subtyping relationship. 
> Region subtyping is key to both simplifying code and to understanding 
> code after simplification.

I'm not convinced that region subtyping is so simple to understand for 
neophytes, especially because you may assume the same region at first 
glance. Cyclone isn't C++, but this region subtyping rule makes me 
think of one of those many little known corners in C++ such as Koenig 
name lookup.

But I consider this just a syntactic issue about how to express regions 
though. And I may be completely wrong about its unintuitiveness.


>> In any case, I prefer a notation where regions constrains are attached 
>> directly to the type instead of being expressed somewhere else. 
>> Something like this (explained below):
>> 
>>     void assign(int*(r)* p, int* r) { *p = r; }
>>     void swap(ref int*(b) a, ref int*(a) b);
> 
> Sure. I'm sure there's understanding that that doesn't make anything 
> any simpler or any easier to implement or understand. It's just a minor 
> change in notation, and IMHO not to the better.

Ok, then we disagree here. I think this notation is better because it 
makes you think about things in term of pointer lifetime vs. the 
pointed data lifetime, which I think is much less abstract than 
variables being part of different regions where some regions encompass 
other regions. It's a shift in perspective from the syntactic approach 
of Cyclone, although under the hood the compiler would do mostly the 
same work.


>> Here, a parenthesis suffix after a pointer indicates the region 
>> constrain of the pointer, based on the region of another pointer.
> 
> I thought it means pointer to function. Oops.

And I though the syntax was the least of your concern right now? :-) 
This probably can't be the final syntax, but I think it makes things 
clear enough talk about about the concepts... for now.


>> In the first example, int*(r)* means that the integer pointer "*p" must 
>> not live beyond the value pointed by "r" (because we're going to assign 
>> "r" to "*p"). In the second example, the value pointed by "a" must not 
>> live longer than the one pointed by "b" and the value pointed by "b" 
>> must not live longer than the one pointed "a"; the net result is that 
>> they must have the same lifetime and need to be in the same region.
>> 
>> For something more complicated, you could give multiple 
>> commas-separated constrains:
>> 
>>     void choose(ref int*(a,b) result, int* a, int* b)
>>     {
>>         result = rand() > 0.5 ? a : b;
>>     }
> 
> This all is irrelevant. You essentially change the syntax. Syntax is, 
> again, the least of the problems to be solved.

Ok then. Let's go to the real problems.


>>> I suspect there are things you can't even express without symbolic 
>>> regions. Consider this example from Dan's slides:
>>> 
>>> struct ILst(region R1, region R2) {
>>>      int *R1 hd;
>>>      ILst!(R1, R2) *R2 tl;
>>> }
>>> 
>>> This code reflects the fact that the list holds pointer to integers in 
>>> one region, whereas the nodes themselves are in a different region. It 
>>> would be a serious challenge to tackle that without symbolic regions, 
>>> and simpler that won't be for anybody.
>> 
>> Today's templates are just fine for that. Just propagate variables 
>> through template arguments and apply region constrains to the members:
>> 
>>     struct ILst(alias var1, alias var2) {
>>         int*(var1) hd;
>>         ILst!(var1, var2)*(var2) tl;
>>     }
>>         int z;
>>     int*(z) a, b;
>>     ILst!(a, b) lst1;
>>     ILst!(&z, &z) lst2;
> 
> I hope you agree that this is just written symbols without much 
> meaning. This is not half-baked. It's not even rare. The cow is still 
> moving. I can't eat that! :o) I can't even start replying to it because 
> there are so many actual and potential issues, I'd need to get to work 
> on them first.

If you mean there aren't any explanation, then you're right that 
explanations were somewhat missing from my last post. Sorry. I guess I 
was too tired to notice the lack of instructions.

Basically you apply the same rules as for the function signatures in 
the preceding function examples. For instance, "int*(var1)" means the 
ht pointer points to an int that lives at least as long as the one 
pointed by var1 (var1 must be an "int*" pointer). This means that you 
can assign the content of var1 to it, or anything else that will live 
at least as long as var1. It also mean you can take its value and place 
it in var1, or any pointer with a shorter life.

Then, we have "ILst!(var1, var2)*(var2)". It's the same rules as the 
first, except that we have a different type beyond the pointer which 
must be valid through var2's lifetime.

The last code snippet shows how to use that template.

    int z;
    int*(z) a, b;
    ILst!(a, b) lst1;
    ILst!(&z, &z) lst2;

Here, we're declaring "int*(z)", which is a pointer to an int whose 
lifetime is equal or longer than the address of z. (ok, there's an 
error here, it should have been "int*(&z)"). And normally, you wouldn't 
explicitly write that, "int*" would be enough: the compiler should 
determine the default constrains automatically.

Then when you instanciate ILst!(a, b), the template will take the 
lifetime of a and b (which is the lifetime of the address of z) and 
apply it to pointers inside the struct.


>> We could even allow regions to propagate through type arguments too:
>> 
>>     struct ILst2(T1, T2) {
>>         int*(T1) hd;
>>         ILst2!(T1, T2)*(T2) tl;
>>     }
>>     ILst2!(typeof(&z), typeof(b)) lst3;

Again, some explanations were missing... Basically, 
region/scoping/lifetime constrains are attached to pointers. Which 
means that propagating a type ought to be enough to propagate the 
lifetime constrains too. "ILst2!(typeof(&z), typeof(b))" is exactly the 
same as "ILst!(&z, b)". ILst takes its constrains from variables while 
ILst2 takes its constrains from types.

But the two previous examples are a little stretched to make the 
concept more similar to Cyclone. With my proposal, you can do much 
better than this.

I think in most cases where you want to propagate constrains, you'll 
want to propagate a type too. If what you want is a linked list, it'd 
be better expressed generically like this:

	struct ListRoot(T) {
		ListNode!(T)* first;
	}
    struct ListNode(T) {
        T hd;
        ILst2!(T)* tl;
    }

	int global;
	void foo() {
		int a;
		ListRoot!(int*) listRoot;
		ListNode!(int*) listNode;
		listRoot.first = &listNode;
		listNode.hd = &a;
		listNode.hd = &global;
	}

Notice how there is absolutely no special annotation here; it's already 
valid template code.

Now, let the compiler apply some defaults according to these rules: 
types declared in local variables will be allowed to point to values of 
their own region, and structs members will be allowed to point to 
values of the same region the struct comes from. Annotated explicitly, 
the default annotations would look like this:

	struct ListRoot(T) {
		ListNode!(T)*(this) first; // pointer to something in the same region as this
	}
    struct ListNode(T) {
        T value; // if T is a pointer, it holds its own region annotations
        ILst2!(T)*(this) next; // pointer to something in the same 
region as this
    }

	int global;
	void foo() {
		int a;
		ListRoot!(int*(&listRoot)) listRoot;
		ListNode!(int*(&listNode)) listNode;
		listRoot.first = &listNode;
		listNode.value = &a;
		listNode.value = &global;
	}

With this scheme, the lifetime of all nodes in the linked list need to 
be equal or longer than the one of the preceding node (normally, they 
will all be equal), and the lifetime of the value pointer is determined 
by the type you give as a template argument to ListRoot and ListNode. 
Therefore, it becomes possible to construct the linked list on the 
stack when the root is on the stack, with no need for explicit 
annotations.

There is still one problem though. If you want to swap two nodes, you 
can't, because there is no guarenty that the lifetime of the "this" 
pointer of a ListNode is equal to lifetime of the "next" pointer. (In 
fact, the next pointer lifetime is longer or equal to the struct 
lifetime). So if we're going to swap or reorder nodes, we'll need a way 
to constrain the "this" pointer against the "next" pointer to create a 
circular reference and thus forcing the two pointers to point to the 
same region... perhaps something like this:
	
    struct ListNode(T) {
		ListNode*(next) this;
        T value;
        ILst2!(T)*(this) next;
    }

Not a very good syntax though.


>> I think this example is a good case for attaching region constrains 
>> directly to types instead of expressing them as conditional expressions 
>> elsewhere, as in "if (region a <= region b)".
> 
> I am thoroughly lost here, sorry. I can't even answer "this is so 
> wrong" or "this is pure genius". Probably it's somewhere in between 
> :o). At any rate, I suggest you develop a solid understanding of 
> Cyclone if you want to build something related to it.

I'll side with "pure genius", but I also consider myself biased. :-)


>>> I'm sorry about how you feel. Now we're in a conundrum of sorts. You 
>>> seem to strongly believe you can make some nice simplified regions 
>>> work, and make people like them. Taking that to a proof is hard. The 
>>> conundrum is, you are facing the prospect of putting work into it and 
>>> creating a system that, albeit correct, is not enticing.
>> 
>> Currently, I'm just trying to convince you (and any other potential 
>> silent listeners) that it can work.
> 
> I understand I've been blunt throughout this post, but please side with 
> me for a minute. I'm doing so for the following reasons: (a) I'm 
> essentially writing this post in negative time; (b) I believe you 
> currently don't have an attack on the problem you're trying to solve; 
> (c) I believe it's worthwhile for you to develop an attack on the 
> problem, (d) I think "we" = "the D community" should seriously consider 
> safety and consequently things like region analysis.

I don't mind about (a) and I agree about (d).

I'll say that because of my lack of expertise with Cyclone I have some 
difficulty expressing my proposal as a comparaison of what is different 
from Cyclone (it's difficult enough without it). You're the one asking 
for such a comparison and increasing the difficulty. I do not dislike 
the challenge, but I don't think you can take this as a proof that I 
don't understand well the problem I'm trying to solve when I may just 
be mixing some things about the approach taken by Cyclone.

Another thing not helping is that my original proposal has evolved a 
little since the first time I started the "full scope analysis 
proposal" thread. I also revamped the syntax I use to talk about the 
problem (and apparently I should do it again to avoid a conflicts with 
function names). Hunting in previous post the details I leave out in 
the more recent ones doesn't help anyone understanding what I'm talking 
about.

I'm thinking that maybe I should put everything in one document to have 
a coherent proposal that could evolve as a whole instead of one 
scattered on various post between which the syntax I use and some 
concepts have evolved.


> You can now stop siding with me and side again with yourself. At this 
> point you can easily guess that all of the above was to prepare you for 
> an even blunter comment. Here goes.
> 
> You say you want to convince people "it can work". But right now there 
> is no "it". You have no "it". Much less an "it" that can work.
> 
> But there is of course good hope that an "it" could emerge, and I 
> encourage you to continue working towards that goal. It's just a lot 
> more work than it might appear.

I'm pretty sure I hold that "it" just now, or something very near it. 
It's just that it seems I haven't explained it well enough for you (and 
probably anyone) to understand correctly. I should probably write it 
all down in one coherent and more formal document rather than 
scattering all the details over many different posts as half-documented 
concept-name-changing written-too-fast examples.


-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/