Re: Lifetime tracking

[Marc Schütz via Digitalmars-d]

On Thursday, 2 June 2016 at 23:29:57 UTC, Timon Gehr wrote:



void foo(scope int* k){
void bar(){
scope int* x;
// need to check that lifetime of x ends not after 
lifetime of k

assign(x,k);
}
}

I.e. now we need a way to annotate 'assign' in order to specify 
the contract I have written down in the comments.

...
[1] It might be possible to get that example to pass the type 
checker with 'return' annotations only if I change 'ref' to 
'out',


There needs to be additional syntax for specifying that an input 
reference escapes through another parameter, not through 
returning. For example:


void assign(S, T)(ref S a, T b return!a) {
a = b;// accepted, as specified in the signature
}

void foo(scope int* k) {
void bar() {
scope int* x;
assign(x, k);  // accepted, because L(x) < L(k)
}
}

(By the way, both the `return` annotation in `assign()` and the 
`scope` in the declaration of `x` don't need to be explicit, they 
can inferred because `assign()` is a template and `x` is a local 
variable.)


But AFAICS, the point about `out` vs `ref` isn't correct. `out` 
resets the parameter to its `.init` value. The specification 
currently doesn't say whether this is done by assignment or by 
destruction followed by blitting, but in any case, both 
`opAssign()` and `~this()` have access to the original reference; 
therefore using `out` doesn't help in the general case (not an 
issue for POD types, though).


but often more than two lifetimes are involved, and then it 
falls flat on its face.


Can you expand on that? With the addition of a provision for 
escaping by reference as suggested (and maybe for escaping by a 
global variable/heap), the `return` syntax should be able to 
express all lifetime relations that don't go more than one 
indirection deep.

Re: Lifetime tracking

[Manu via Digitalmars-d]

On 4 June 2016 at 19:14, Walter Bright via Digitalmars-d
 wrote:
> On 6/3/2016 4:38 AM, Timon Gehr wrote:
>>
>> I'm sure there is some syntax that
>> will feel natural to D programmers.
>
>
> Aye, there's the rub. Nobody has found one in over 10 years, despite a lot
> of discussion.

What is unnatural about 'scope' as has been proposed by heaps of
people? I find DIP25 much more awkward and unnatural than 'scope'.

Re: Lifetime tracking

[Manu via Digitalmars-d]

On 3 June 2016 at 10:40, Stefan Koch via Digitalmars-d
 wrote:
> On Friday, 3 June 2016 at 00:31:31 UTC, Walter Bright wrote:
>
>> If they cover the cases that matter, it's good. Rust has the type system
>> annotations you want, but Rust has a reputation for being difficult to write
>> code for.
>
>
> I think we can incorporate typesafe borrowing without making it difficult to
> write.

I also haven't heard any reports from colleagues who have tried out
rust to a decent extent that borrow pointers are among the things that
make rust code hard to write.
'rust is hard' != 'borrowing is hard' .. also, I don't necessarily
think 'scope' would be identical to rust, it would be designed for D,
obviously.

Re: Lifetime tracking

[Walter Bright via Digitalmars-d]

On 6/4/2016 2:14 AM, Walter Bright wrote:

On 6/3/2016 4:38 AM, Timon Gehr wrote:

I'm sure there is some syntax that will feel natural to D programmers.


Aye, there's the rub. Nobody has found one in over 10 years, despite a lot of
discussion.


No one found one for Rust, either.

Re: Lifetime tracking

[Walter Bright via Digitalmars-d]

On 6/3/2016 4:38 AM, Timon Gehr wrote:

I'm sure there is some syntax that
will feel natural to D programmers.


Aye, there's the rub. Nobody has found one in over 10 years, despite a lot of 
discussion.

Re: Lifetime tracking

[Timon Gehr via Digitalmars-d]

On 03.06.2016 02:31, Walter Bright wrote:

On 6/2/2016 4:29 PM, Timon Gehr wrote:

// need to know that lifetime of a ends not after lifetime of b
void assign(S,T)(ref S a, T b){ a = b; }

void foo(scope int* k){
void bar(){
scope int* x;
// need to check that lifetime of x ends not after lifetime of k
assign(x,k);


It'll fail to compile because T is not annotated with 'scope'.
Annotating T with scope will then fail to compile because the assignment
to 'a' may outlive 'b'.
...


There are no actual execution traces with those issues. The point is 
that you need additional annotations that make it work.



}
}



 > Note that it is tempting to come up with ad-hoc solutions that make
some small finite set of examples work.

If they cover the cases that matter, it's good.


Yes, but how do you establish that they do without using sound reasoning 
of the style I'm advocating? For example, there are a lot of tests for 
DMD, but bugs that matter keep being reported. This issue can be 
essentially eradicated for many relevant parts of a type system design 
by sticking to at most a handful of basic principles.



Rust has the type system annotations you want,


We don't need to have the same annotations. We just need to be able to 
carry the same information around in the type system. I'm sure there is 
some syntax that will feel natural to D programmers.



but Rust has a reputation for being difficult to
write code for.


I don't think it is because it has sufficiently powerful annotations to 
write verifiably memory safe code and refactor it.


I do agree that ergonomics is an important consideration, but it should 
be optimized under the most basic constraints that a type system needs 
to fulfill. (Otherwise users will try it, get frustrated and use @system 
code.)


I assume the 'return' annotations we already have can stay and will 
cover quite some ground.

Re: Lifetime tracking

[docandrew via Digitalmars-d]

On Friday, 3 June 2016 at 00:40:09 UTC, Stefan Koch wrote:

On Friday, 3 June 2016 at 00:31:31 UTC, Walter Bright wrote:

If they cover the cases that matter, it's good. Rust has the 
type system annotations you want, but Rust has a reputation 
for being difficult to write code for.


I think we can incorporate typesafe borrowing without making it 
difficult to write.


+1, a big problem with Rust is just that the syntax is really 
ugly to those coming from D/C/C++/Java. An idea I had was using 
plain English attributes in function signatures to denote 
ownership.


e.g.

void myfunc(sees Myobj arg1, copies Myobj arg2, borrows Myobj 
arg3, owns Myobj arg4)

{
	//"sees arg1" - read-only reference (basically const now, but 
cannot be

//cast away)

	//"copies arg2" - read/write copy of argument. It works the same 
way
//value types work now, and will be freed after function 
exit (unless it is

//returned).

	//"borrows arg3" is a by-reference pass, may have the benefit of 
enabling
//optimization for small functions since it eliminates a 
copy
	// (maybe save a stack push and allow register re-use?). Will 
not be freed

//after function exits (ownership returns to calling
// function). Reference can be locked for multi-threaded apps.

	//"owns arg4" - frees after function exit (unless it is 
returned).

}

At a glance it's obvious who owns what, what's read-only, etc.

Also, a nice bonus is that "const" can become a more rigid 
guarantee - as in Rust,  there can exist multiple const 
references to an object, but only one mutable reference. 
Immutable or const by default is probably a bridge too far from 
what we're used to.


There are still a lot of corner-cases that I'd have to think 
through, i.e. calling class methods through a const/"sees" 
reference (would have to be "pure" calls only), good syntax for 
ownership changes mid-function (maybe use "sees" "copies" 
"borrows" and "owns" as operators?), passing to C functions, 
mangling, etc.


Anyhow, just some brainstorming to stir discussion. It looks 
pleasant to me, but I'm not sure if you can call it "D" anymore.


-Jon

Re: Lifetime tracking

[Stefan Koch via Digitalmars-d]

On Friday, 3 June 2016 at 00:31:31 UTC, Walter Bright wrote:

If they cover the cases that matter, it's good. Rust has the 
type system annotations you want, but Rust has a reputation for 
being difficult to write code for.


I think we can incorporate typesafe borrowing without making it 
difficult to write.

Re: Lifetime tracking

[Walter Bright via Digitalmars-d]

On 6/2/2016 5:21 PM, Walter Bright wrote:

Please give an example.


I see you did, so ignore that.

Re: Lifetime tracking

[Walter Bright via Digitalmars-d]

On 6/2/2016 4:29 PM, Timon Gehr wrote:

// need to know that lifetime of a ends not after lifetime of b
void assign(S,T)(ref S a, T b){ a = b; }

void foo(scope int* k){
void bar(){
scope int* x;
// need to check that lifetime of x ends not after lifetime of k
assign(x,k);


It'll fail to compile because T is not annotated with 'scope'. Annotating T with 
scope will then fail to compile because the assignment to 'a' may outlive 'b'.



}
}



> Note that it is tempting to come up with ad-hoc solutions that make some 
small finite set of examples work.


If they cover the cases that matter, it's good. Rust has the type system 
annotations you want, but Rust has a reputation for being difficult to write 
code for.

Re: Lifetime tracking

[Walter Bright via Digitalmars-d]

On 6/2/2016 4:05 PM, Timon Gehr wrote:

I'd like to point out again why that design is inadequate:

Whenever the type checker is using a certain piece of information to check
validity of a program, there should be a way to pass that kind of information
across function boundaries. Otherwise the type system is not modular. This is a
serious defect.


I don't understand where the defect is. Please give an example.

Re: Lifetime tracking

[tsbockman via Digitalmars-d]

On Thursday, 2 June 2016 at 23:29:57 UTC, Timon Gehr wrote:

On 03.06.2016 01:12, tsbockman wrote:

On Thursday, 2 June 2016 at 23:05:40 UTC, Timon Gehr wrote:
Whenever the type checker is using a certain piece of 
information to
check validity of a program, there should be a way to pass 
that kind
of information across function boundaries. Otherwise the type 
system

is not modular. This is a serious defect.


Would you mind giving a brief example of how that applies to 
`scope`?


(I'm asking for my own education; I have no personal opinion 
as to the

right implementation at the moment.)


The simplest example is this [1]:


Thanks for the explanation.

Re: Lifetime tracking

[Timon Gehr via Digitalmars-d]

On 03.06.2016 01:29, Timon Gehr wrote:



[1] It might be possible to get that example to pass the type checker
with 'return' annotations only if I change 'ref' to 'out', but often
more than two lifetimes are involved, and then it falls flat on its face.


To be slightly more explicit:

void multiAssign(A,B,C,D)(ref A a,B b,ref C c,D d){ a = b; c = d; }

Re: Lifetime tracking

[Timon Gehr via Digitalmars-d]

On 03.06.2016 01:12, tsbockman wrote:

On Thursday, 2 June 2016 at 23:05:40 UTC, Timon Gehr wrote:

Whenever the type checker is using a certain piece of information to
check validity of a program, there should be a way to pass that kind
of information across function boundaries. Otherwise the type system
is not modular. This is a serious defect.


Would you mind giving a brief example of how that applies to `scope`?

(I'm asking for my own education; I have no personal opinion as to the
right implementation at the moment.)


The simplest example is this [1]:

void foo(scope int* k){
void bar(){
scope int* x;
x = k; // ok: lifetime of x ends not after lifetime of k
}
}

Now we factor out the assignment:

// need to know that lifetime of a ends not after lifetime of b
void assign(S,T)(ref S a, T b){ a = b; }

void foo(scope int* k){
void bar(){
scope int* x;
// need to check that lifetime of x ends not after lifetime of k
assign(x,k);
}
}

I.e. now we need a way to annotate 'assign' in order to specify the 
contract I have written down in the comments.


Note that it is tempting to come up with ad-hoc solutions that make some 
small finite set of examples work. This is not how well-designed type 
systems usually come about. You need to think about what information the 
type checker requires, and how to pass it across function boundaries 
(i.e. how to encode that information in types). Transfer of information 
must be lossless, so one should resist the temptation to use more 
information than can be passed across function boundaries in case it is 
accidentally available.




[1] It might be possible to get that example to pass the type checker 
with 'return' annotations only if I change 'ref' to 'out', but often 
more than two lifetimes are involved, and then it falls flat on its face.

Re: Lifetime tracking

[Stefan Koch via Digitalmars-d]

On Thursday, 2 June 2016 at 23:05:40 UTC, Timon Gehr wrote:

On 03.06.2016 00:29, Walter Bright wrote:

On 6/2/2016 3:10 PM, Marco Leise wrote:

we haven't looked into borrowing/scoped enough


That's my fault.

As for scoped, the idea is to make scope work analogously to 
DIP25's
'return ref'. I don't believe we need borrowing, we've worked 
out

another solution that will work for ref counting.

Please do not reply to this in this thread - start a new one 
if you wish

to continue with this topic.



I'd like to point out again why that design is inadequate:

Whenever the type checker is using a certain piece of 
information to check validity of a program, there should be a 
way to pass that kind of information across function 
boundaries. Otherwise the type system is not modular. This is a 
serious defect.


Seconded.

Lifetime tracking

[Timon Gehr via Digitalmars-d]

On 03.06.2016 00:29, Walter Bright wrote:

On 6/2/2016 3:10 PM, Marco Leise wrote:

we haven't looked into borrowing/scoped enough


That's my fault.

As for scoped, the idea is to make scope work analogously to DIP25's
'return ref'. I don't believe we need borrowing, we've worked out
another solution that will work for ref counting.

Please do not reply to this in this thread - start a new one if you wish
to continue with this topic.



I'd like to point out again why that design is inadequate:

Whenever the type checker is using a certain piece of information to 
check validity of a program, there should be a way to pass that kind of 
information across function boundaries. Otherwise the type system is not 
modular. This is a serious defect.