In the "Opportunities for D" thread, Walter again mentioned the topics ref counting, GC, uniqueness, and borrowing, from which a lively discussion developed [1]. I took this thread as an opportunity to write down some ideas about these topics. The result is a rather extensive proposal for the implementation of borrowing, and its implementations:

http://wiki.dlang.org/User:Schuetzm/scope

This is not a real DIP, but before I put more work into formalizing it, I'd like to hear some thoughts from the languages gurus here:

* Is this the general direction we want to go? Is it acceptable in general?
* Is the proposal internally consistent?
* How big would the effort to implement it be? (I suspect it's a large amount of work, but relatively straightforward.)

[1] http://forum.dlang.org/thread/lphnen$1ml7$1@digitalmars.com

Cool initiative!

It is probably a good idea to look at what other languages with linear type systems are doing:

http://en.m.wikipedia.org/wiki/Substructural_type_system

My gut feeling is that borrowing in D will suffer the same problems as @safe without a high level IR that is proven correct. Meaning, if the IR is correct you can add new language features without breaking the type system.

On Sunday, 24 August 2014 at 13:14:45 UTC, Marc Schütz wrote:
> http://wiki.dlang.org/User:Schuetzm/scope
I like this.
It removes pretty much all of the need for manual memory management for me. I would love to see this implemented.

On 25/08/2014 1:14 a.m., "Marc Schütz" <schuetzm@gmx.net>" wrote:
> In the "Opportunities for D" thread, Walter again mentioned the topics
> ref counting, GC, uniqueness, and borrowing, from which a lively
> discussion developed [1]. I took this thread as an opportunity to write
> down some ideas about these topics. The result is a rather extensive
> proposal for the implementation of borrowing, and its implementations:
>
> http://wiki.dlang.org/User:Schuetzm/scope
>
> This is not a real DIP, but before I put more work into formalizing it,
> I'd like to hear some thoughts from the languages gurus here:
>
> * Is this the general direction we want to go? Is it acceptable in general?
> * Is the proposal internally consistent?
> * How big would the effort to implement it be? (I suspect it's a large
> amount of work, but relatively straightforward.)
>
> [1] http://forum.dlang.org/thread/lphnen$1ml7$1@digitalmars.com

Have you considered what happens when you cast away scope?
I didn't read anything about that, unless I missed something.

I do have to ask this, because what if you wanted to optionally return a scoped reference?

Can't scope(int*) on return type be equivalent to scope!(a,b)(int*)? How often this is not desired?

On Monday, 25 August 2014 at 01:09:59 UTC, Ola Fosheim Grøstad wrote:
> Cool initiative!
>
> It is probably a good idea to look at what other languages with linear type systems are doing:
>
> http://en.m.wikipedia.org/wiki/Substructural_type_system

The idea is mostly inspired by Rust, but it came out very different. Rust's borrowing rules are way more complicated. It also has to deal with move semantics, for example. And it annotates lifetimes, not owners, and thereby gets non-hierarchical dependencies, as far as I understand it. I believe this proposal is close to the best we can achieve without resorting to data flow analysis.

>
> My gut feeling is that borrowing in D will suffer the same problems as @safe without a high level IR that is proven correct. Meaning, if the IR is correct you can add new language features without breaking the type system.

I'm unfortunately not familiar with the theoretical foundations of type systems, and formal logic. So I'm not sure what exactly you mean here. It seems to me the problems with @safe are with the way it was implemented (allow everything _except_ certain things that are known to be bad, instead of the opposite way: allow nothing at first, but lift restrictions where it's safe to do so), they are not conceptual.

But if you see potential problems, or know a way to avoid them, this is exactly the kind of thing I'd like to see discussed.

On Monday, 25 August 2014 at 10:06:12 UTC, Rikki Cattermole wrote:
> Have you considered what happens when you cast away scope?
> I didn't read anything about that, unless I missed something.

Right, this should be specified. But it's fairly obvious what would happen: you lose the safety guarantees (=> @system), and you're responsible to make sure you don't get dangling references. You'd basically get what you have with normal pointers. I don't think it has any deeper implications than that, but I'm not sure there aren't any obscure optimizations the compiler could make based on scope. If there are, it's no different from casting away const, in this respect.

>
> I do have to ask this, because what if you wanted to optionally return a scoped reference?

Well, it's part of the return type, so it's either scoped, or it isn't. You could return a tuple with a scoped and a non-scoped pointer, though.

If it's only about returning a non-scoped pointer from a function with a scoped return type, that's fine, because it's adding scope, not removing it. (Use case: ScopeBuffer.)

On Monday, 25 August 2014 at 10:27:53 UTC, Kagamin wrote:
> Can't scope(int*) on return type be equivalent to scope!(a,b)(int*)? How often this is not desired?

You mean as a default?

It would be desired in `chooseStringAtRandom`, but not in the `findSubstring`, whose returned string shouldn't be limited by the scope of the needle. If it is made the default, there would need to be a way to opt out, such as removing an owner.

But note that in the `chooseStringAtRandom` example, it would be sufficient to declare it as:

    scope chooseStringAtRandom(scope(string) a, scope(string) b) {
        return random() % 2 == 0 ? a : b;
    }

Type deduction would then automatically add `a` and `b` as the owners, by the rules under "Owner tracking".

Marc Schütz:

> http://wiki.dlang.org/User:Schuetzm/scope

It looks nice. But perhaps it needs some kind of proof of correctness.

Have you read the old blog posts (written before the creation of Rust) by Bartosz Milewski regarding the borrowing in D?


>Implementation of this feature is possible without doing flow control or interprocedural analysis.<

I remember that Walter has recently said that he's willing to add some kind of flow analysis to the D front-end.

Bye,
bearophile

On Monday, 25 August 2014 at 11:09:48 UTC, Marc Schütz wrote:
> I believe this proposal is close to the best we can achieve without resorting to data flow analysis.

I agree with bearophile, perhaps data flow analysis would be desirable. So I think it would be a good idea to hold the door open on that.

> I'm unfortunately not familiar with the theoretical foundations of type systems, and formal logic. So I'm not sure what exactly

I don't know all that much about linear type systems, but this is an opportunity to learn more for all of us! :-)

> you mean here. It seems to me the problems with @safe are with the way it was implemented (allow everything _except_ certain things that are known to be bad, instead of the opposite way: allow nothing at first, but lift restrictions where it's safe to do so), they are not conceptual.

Because real programming languages are hard to reason about it is difficult to say where things break down. So one usually will map the constructs of the language onto something simpler and more homogeneous that is easier to reason about.

When it comes to @safe I think the main problem is that D makes decisions on constructs and not on the "final semantics" of the program. If you have a dedicated high level IR you can accept any program segment that can be proven to be memory safe in terms of the IR. The point is to have an IR that is less complicated than the full language, but that retains needed information that is lost in a low level IR and which you need to prove memory safety.

memset() is not unsafe per se, it is unsafe with the wrong parameters. So you have to prove that the parameters are in the safe region. Same thing with freeing memory and borrowed pointers etc. You need a correctness proof even if you give up on generality.

You may reject many safe programs but at least verify as many simple safe programs as you can.

A bonus of having a high level IR is that you more easily can combine languages with fewer interfacing problems. That would be an advantage if you want a DSL to cooperate with D.

> But if you see potential problems, or know a way to avoid them, this is exactly the kind of thing I'd like to see discussed.

The problem is that D is too complex to reason about with any reasonable level of confidence. So you need to reduce the language to a level where you can reason about it with confidence and build the other constructs on top of that.

(That way you don't have to reason about the combinatorial explosion of constructs, just the building blocks).

Ola.