On Friday, 11 July 2014 at 21:04:05 UTC, H. S. Teoh via
Digitalmars-d wrote:
On Thu, Jul 10, 2014 at 08:10:36PM +0000, via Digitalmars-d
wrote:
Hmm. Seems that you're addressing a somewhat wider scope than
what I had
in mind. I was thinking mainly of 'scope' as "does not escape
the body
of this block", but you're talking about a more general case of
being
able to specify explicit lifetimes.
Indeed, but it includes what you're suggesting. For most use
cases, just `scope` without an explicit lifetime annotation is
fully sufficient.
[...]
A problem that has been discussed in a few places is safely
returning
a slice or a reference to an input parameter. This can be
solved
nicely:
scope!haystack(string) findSubstring(
scope string haystack,
scope string needle
);
Inside `findSubstring`, the compiler can make sure that no
references
to `haystack` or `needle` can be escape (an unqualified
`scope` can be
used here, no need to specify an "owner"), but it will allow
returning
a slice from it, because the signature says: "The return value
will
not live longer than the parameter `haystack`."
This does seem to be quite a compelling argument for explicit
scopes. It
does make it more complex to implement, though.
[...]
An interesting application is the old `byLine` problem, where
the
function keeps an internal buffer which is reused for every
line that
is read, but a slice into it is returned. When a user naively
stores
these slices in an array, she will find that all of them have
the same
content, because they point to the same buffer. See how this is
avoided with `scope!(const ...)`:
This seems to be something else now. I'll have to think about
this a bit
more, but my preliminary thought is that this adds yet another
level of
complexity to 'scope', which is not necessarily a bad thing,
but we
might want to start out with something simpler first.
It's definitely an extension and not as urgently necessary,
although it fits well into the general topic of borrowing:
`scope` by itself provides mutable borrowing, but `scope!(const
...)` provides const borrowing, in the sense that another object
temporarily takes ownership of the value, so that the original
owner can only read the object until it is "returned" by the
borrowed value going out of scope. I mentioned it here because it
seemed to be an easy extension that could solve an interesting
long-standing problem for which we only have workarounds today
(`byLineCopy` IIRC).
And I have to add that it's not completely thought out yet. For
example, might it make sense to have `scope!(immutable ...)`,
`scope!(shared ...)`, and if yes, what would they mean...
[...]
An open question is whether there needs to be an explicit
designation
of GC'd values (for example by `scope!static` or `scope!GC`),
to say
that a given values lives as long as it's needed (or
"forever").
Shouldn't unqualified values already serve this purpose?
Likely yes. It might however be useful to contemplate, especially
with regards to allocators.
[...]
Now, for the problems:
Obviously, there is quite a bit of complexity involved. I can
imagine
that inferring the scope for templates (which is essential,
just as
for const and the other type modifiers) can be complicated.
I'm thinking of aiming for a design where the compiler can
infer all
lifetimes automatically, and the user doesn't have to. I'm not
sure if
this is possible, but based on what Walter said, it would be
best if we
infer as much as possible, since users are lazy and are
unlikely to be
thrilled at the idea of having to write additional annotations
on their
types.
I agree. It's already getting ugly with `const pure nothrow @safe
@nogc`, adding another annotation should not be done
lightheartedly. However, if the compiler could infer all the
lifetimes (which I'm quite sure isn't possible, see the
haystack-needle example), I don't see why we'd need `scope` at
all. It would at most be a way not to break backward
compatibility, but that would be another case where you could say
that D has it backwards, like un-@safe by default...
My original proposal was aimed at this, that's why I didn't put
in
explicit lifetimes. I was hoping to find a way to define things
such
that the lifetime is unambiguous from the context in which
'scope' is
used, so that users don't ever have to write anything more than
that.
This also makes the compiler's life easier, since we don't have
to keep
track of who owns what, and can just compute the lifetime from
the
surrounding context. This may require sacrificing some
precision in
lifetimes, but if it helps simplify things while still giving
adequate
functionality, I think it's a good compromise.
I agree it looks a bit intimidating at first glance, but as far
as I can tell it should be relatively straightforward to
implement. I'll explain how I think it could be done:
The obvious things: The parser needs to recognize the new syntax,
and scope needs to be turned into a type modifier and stored in
the internal data structures accordingly.
It is then possible to define a hierarchy of lifetimes. At the
top are global and static variables and the GC heap
(`scope!static` or just unannotated), then the come function
parameters, then local variables in function bodies, and finally
local variables in lower scopes like `if` blocks. This is purely
based on lexical scope and order of declaration (local variables
are destroyed in inverse order of construction, for example); it
can be derived from the AST. Furthermore, it is a strict
hierarchy; lifetimes higher in the hierarchy are strict super
sets of lower lifetimes.
A variables effective lifetime is then its place in this
hierarchy, or the lifetime of its owner if one is specified.
Once that's done, the semantic phase needs to be extended to
check for scope correctness. This seems complicated, but actually
needs to touch only a few places. Any time a scope value is
copied, by assignment, returning from a function, passing to a
function, throwing, and what else I may have missed, the compiler
needs to check that the destination's effective lifetime is not
wider than that of the source.
For function calls, an additional step is necessary, but it isn't
really complicated either. Let's take `findSubstring` as an
example:
scope!haystack(string) findSubstring(
scope string haystack,
scope string needle
);
void foo() {
string[$] h = "Hello, world!";
auto found = findSubstring(h, ", ");
// `typeof(found)` is now `scope!h`
}
As owners in function signatures may refer to other parameters
(or `this`), the compiler needs to match up these parameters with
what is passed in, and substitute them accordingly for type
deduction (only for `auto` return values).
And that's it, AFAICS. Notice that none of this requires flow
control analysis or inter-procedural things, it can all be
decided locally at the place of assignment/calling/etc.
[...]
I also have a few ideas about owned types and move semantics,
but this
is mostly independent from borrowing (although, of course, it
integrates nicely with it). So, that's it, for now. Sorry for
the long
text. Thoughts?
It seems that you're the full borrowed reference/pointer
problem, which
is something necessary. But I was thinking more in terms of the
baseline
functionality -- what is the simplest design for 'scope' that
still
gives useful semantics that covers most of the cases? I know
there are
some tricky corner cases, but I'm wondering if we can somehow
find an
easy solution for the easy parts (presumably the more common
parts),
while still allowing for a way to deal with the hard parts.
At least for now, I'm thinking in the direction of finding
something
with simple semantics that, at the same time, produces complex
(interesting) effects when composed, that we can use to solve
the
borrowed pointer problem.
I already wrote this in a reply to Walter. I believe in some
cases we can allow automatic borrowing without any annotation at
all, not even bare `scope`. The most obvious examples are pure
functions with signatures that guarantee that nothing can be
escaped from them:
void foo(int[] p) pure; // obvious, function has no
opportunity
// to keep a reference to `p`
int bar(int[] p) pure; // returns an `int` but that's a
value
// type, and that's ok
int[] baz(const(int)[] p) pure;
// the return type is not `const`
and thus
// cannot come from `p`
Maybe there are some cases with non-pure functions, too. But on
the other hand, I also think that in the end we won't get around
introducing explicit annotations, because the above rules can
never cover enough cases to disregard the remaining ones.
Anyway, I don't believe that explicit annotations will be needed
often enough to turn the users away. It will be mostly library
writers who have to use them, and Phobos can set a good example
there and work out a good style, just as it has done for other
matters.
It also helps to take a glance at Rust's standard library, to see
how frequent or infrequent lifetime annotations will be. They
keep popping up here and there, but they are not littered all
over the source code. They're frequent enough to confirm my
suspicion that they cannot be disregarded, but they're also
infrequent enough not to be an annoyance. (I only looked at a few
modules, though.)