www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Implementing tail-const in D

reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
Since tail-const (more correctly called head-mutable) was 
mentioned here lately (in the 'I closed a very old bug!'[1] 
thread), I've been racking my brain to figure out what needs 
doing to make a viable solution.

Unqual is the standard way today to get a head-mutable version of 
something. For dynamic arrays, static arrays, pointers and value 
types, including structs without aliasing, thi works. For AAs, 
classes, and structs with aliasing, Unqual is the wrong tool, but 
it's the tool we have, so it's what we use.

Unqual has other uses, so HeadMutable!T should be a separate 
template. This means parts of Phobos will need to be reworked to 
support types not currently supported. However, given these types 
are not currently supported, this should not break any existing 
code.

While it is generally desirable for T to be implicitly castable 
to HeadMutable!T (just like const(int[]) is implicitly castable 
to const(int)[]), the rules for such implicit casting in the 
language today are inconsistent[2] and incompatible with alias 
this[3], opDispatch, opDot, subclassing, and constructors.

Instead of implicit casting, I therefore propose we use a method 
headMutable(), which will attempt to call the appropriate 
functions to do the conversion. With these two building blocks, 
we have what we need for tail-const (head-mutable) ranges and 
other constructs.

What does your code need to do to support HeadMutable? If you 
have a templated struct that holds an array or pointer, the type 
of which depends on a template parameter, you can define a 
function opHeadMutable that returns a head-mutable version. 
That's it.

If you use HeadMutable!T anywhere, you almost definitely should 
use headMutable() when assigning to it, since T might not be 
implicitly castable to HeadMutable!T.

So what does all of this look like? An example templated struct 
with opHeadMutable hook:

struct R(T) {
     T[] arr;
     auto opHeadMutable(this This)() {
         import std.traits : CopyTypeQualifiers;
         return R!(CopyTypeQualifiers!(This, T))(arr);
     }
}

This is the code you will need to write to ensure your types can 
be converted to head-mutable. opHeadMutable provides both a 
method for conversion, and a way for the HeadMutable!T template 
to extract the correct type.

The actual implementation of HeadMutable!T and headMutable is 
available here:
https://gist.github.com/Biotronic/67bebfe97f17e73cc610d9bcd119adfb


My current issues with this:
1) I don't like the names much. I called them Decay, decay and 
opDecay for a while. Name suggestions are welcome.
2) As mentioned above, implicit conversions would be nice, but 
that'd require an entirely new type of implicit conversion in 
addition to alias this, opDispatch, opDot and interfaces/base 
classes. This would require some pretty darn good reasons, and I 
don't think a call to headMutable() is that much of a problem.

Questions:
Is a DIP required for this? Should I create a PR implementing 
this for the range types in Phobos? What other types would 
benefit from this?

I welcome any and all... feck it. Destroy!

--
   Simen

[1]: 
https://forum.dlang.org/post/egpcfhpediicvkjuklwo forum.dlang.org
[2]: https://issues.dlang.org/show_bug.cgi?id=18268
[3]: Alias this is too eager, and allows for calling mutating 
methods on the temporary value it returns. If alias this was used 
to allow const(int[]) to convert to const(int)[], 
isInputRange!(const(int[])) would return true.
Jan 23
next sibling parent reply Nicholas Wilson <iamthewilsonator hotmail.com> writes:
On Tuesday, 23 January 2018 at 09:36:03 UTC, Simen Kjærås wrote:
 Questions: Is a DIP required for this?
A DIP is required for language changes. So yes.
Jan 23
parent reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Tuesday, 23 January 2018 at 12:12:42 UTC, Nicholas Wilson 
wrote:
 On Tuesday, 23 January 2018 at 09:36:03 UTC, Simen Kjærås wrote:
 Questions: Is a DIP required for this?
A DIP is required for language changes. So yes.
No language changes are proposed - this is all library code. -- Simen
Jan 23
parent reply Andrea Fontana <nospam example.com> writes:
On Tuesday, 23 January 2018 at 12:39:12 UTC, Simen Kjærås wrote:
 On Tuesday, 23 January 2018 at 12:12:42 UTC, Nicholas Wilson 
 wrote:
 On Tuesday, 23 January 2018 at 09:36:03 UTC, Simen Kjærås 
 wrote:
 Questions: Is a DIP required for this?
A DIP is required for language changes. So yes.
No language changes are proposed - this is all library code. -- Simen
It would be useful to have one or more short examples. Just to see what actually change in a common scenario. Andrea
Jan 23
parent reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Tuesday, 23 January 2018 at 14:17:26 UTC, Andrea Fontana wrote:
 On Tuesday, 23 January 2018 at 12:39:12 UTC, Simen Kjærås wrote:
 On Tuesday, 23 January 2018 at 12:12:42 UTC, Nicholas Wilson 
 wrote:
 On Tuesday, 23 January 2018 at 09:36:03 UTC, Simen Kjærås 
 wrote:
 Questions: Is a DIP required for this?
A DIP is required for language changes. So yes.
No language changes are proposed - this is all library code. -- Simen
It would be useful to have one or more short examples. Just to see what actually change in a common scenario. Andrea
Your wish is my command. For the most part, the changes will require that instead of storing Unqual!Ts, use HeadMutable!Ts, and when assigning to a HeadMutable!T, remember to assign headMutable(rhs). Here's a somewhat simplistic map function. As you can see, not a whole lot is changed - map passes head-mutable versions of its arguments to MapResult, and MapResult implements opHeadMutable(), otherwise everything is exactly as you'd expect. import std.range; auto map(alias fn, R)(R r) if (isInputRange!(HeadMutable!R)) { // Pass head-mutable versions to MapResult. return MapResult!(fn, HeadMutable!R)(headMutable(r)); } struct MapResult(alias fn, R) if (isInputRange!R) { R range; this(R rng) { range = rng; } property auto front() { return fn(range.front); } void popFront() { range.popFront(); } property bool empty() { return range.empty; } // The only change to MapResult: auto opHeadMutable(this This)() { import std.traits : CopyTypeQualifiers; return MapResult!(fn, HeadMutable!(CopyTypeQualifiers!(This, R)))(range); } } unittest { import std.algorithm : equal; const a = [1,2,3,4].map!(v => v*2); assert(!isInputRange!(typeof(a))); // Here, std.algorithm.map gives up, since a const MapResult is not // an input range, and calling Unqual on it doesn't give a sensible // result. // HeadMutable makes this work, since the type system now knows how // to make a head-mutable version of the type. auto b = a.map!(v => v/2); assert(equal([1,2,3,4], b)); } -- Simen
Jan 23
parent Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Tuesday, 23 January 2018 at 14:55:39 UTC, Simen Kjærås wrote:
 auto map(alias fn, R)(R r) if (isInputRange!(HeadMutable!R))
 {
     // Pass head-mutable versions to MapResult.
     return MapResult!(fn, HeadMutable!R)(headMutable(r));
 }
Another thing that I didn't think of when writing the above code was how this works with a mutating lambda: unittest { const a = [1,2,3,4].map!((ref v) => v*=2); HeadMutable!(typeof(a)) b; // static assert "No head-mutable type for const(MapResult!(__lambda1, int[]))" } Which makes sense - there is no way to make a head-mutable version of a from itself - it would break the constness guarantees. -- Biotronic
Jan 24
prev sibling next sibling parent reply sarn <sarn theartofmachinery.com> writes:
On Tuesday, 23 January 2018 at 09:36:03 UTC, Simen Kjærås wrote:
 Since tail-const (more correctly called head-mutable) was 
 mentioned here lately (in the 'I closed a very old bug!'[1] 
 thread), I've been racking my brain to figure out what needs 
 doing to make a viable solution.
Have you seen Rebindable in Phobos? I know it's not the same thing as what you're talking about, but it's relevant. https://dlang.org/library/std/typecons/rebindable.html
Jan 23
parent Jacob Carlborg <doob me.com> writes:
On 2018-01-24 00:10, sarn wrote:

 Have you seen Rebindable in Phobos?  I know it's not the same thing as 
 what you're talking about, but it's relevant.
 https://dlang.org/library/std/typecons/rebindable.html
I'm pretty sure he has since it's use in the implementation [1] ;) [1] https://gist.github.com/Biotronic/67bebfe97f17e73cc610d9bcd119adfb#file-headmutable-d-L10 -- /Jacob Carlborg
Jan 24
prev sibling next sibling parent reply Nick Treleaven <nick geany.org> writes:
On Tuesday, 23 January 2018 at 09:36:03 UTC, Simen Kjærås wrote:
 Unqual is the standard way today to get a head-mutable version 
 of something. For dynamic arrays, static arrays, pointers and 
 value types, including structs without aliasing, thi works. For 
 AAs, classes, and structs with aliasing, Unqual is the wrong 
 tool, but it's the tool we have, so it's what we use.
I made an old PR for a Rebindable that works with const/immutable structs with aliasing: https://github.com/dlang/phobos/pull/4363 I didn't have time to get it merged though. I didn't think about AAs, but we already have Rebindable for classes, and Rebindable could probably easily support the other types. Then we could swap those uses of Unqual for Rebindable.
Jan 24
parent Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Wednesday, 24 January 2018 at 11:21:59 UTC, Nick Treleaven 
wrote:
 On Tuesday, 23 January 2018 at 09:36:03 UTC, Simen Kjærås wrote:
 Unqual is the standard way today to get a head-mutable version 
 of something. For dynamic arrays, static arrays, pointers and 
 value types, including structs without aliasing, thi works. 
 For AAs, classes, and structs with aliasing, Unqual is the 
 wrong tool, but it's the tool we have, so it's what we use.
I made an old PR for a Rebindable that works with const/immutable structs with aliasing: https://github.com/dlang/phobos/pull/4363
Nice. I guess HeadMutable should use Rebindable in those cases, if you get this merged. It addresses a somewhat orthogonal issue though. We need to be able to call mutating methods on the resulting value, e.g. popFront(), without mutating aliased values. For that to work, the type must be able to specify how to make a head-mutable version of itself. Rebindable cannot offer this kind of access (and shouldn't). -- Simen
Jan 24
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Jan 23, 2018 at 09:36:03AM +0000, Simen Kjrs via Digitalmars-d wrote:
[...]
 struct R(T) {
     T[] arr;
     auto opHeadMutable(this This)() {
         import std.traits : CopyTypeQualifiers;
         return R!(CopyTypeQualifiers!(This, T))(arr);
     }
 }
 
 This is the code you will need to write to ensure your types can be
 converted to head-mutable. opHeadMutable provides both a method for
 conversion, and a way for the HeadMutable!T template to extract the
 correct type.
I like this idea quite much, actually, in spite of the lack of support for implicit conversions, which is a loss (but as you said, we can't support that without breaking a lot of existing stuff or introducing massive changes that are unlikely to be accepted by Walter & Andrei). Basically, instead of a bunch of convoluted rules with poorly-understood corner cases, we delegate the responsibility of constructing a head mutable type to the type itself, so the user code decides for itself how to construct such a thing. It's a clever idea. In fact, if the standard implementation of opHeadMutable is basically the same across all types (or most types), it could even be provided as a mixin template in the library, then all you have to do is to `mixin headMutable` or something along those lines, and off you go.
 The actual implementation of HeadMutable!T and headMutable is
 available here:
 https://gist.github.com/Biotronic/67bebfe97f17e73cc610d9bcd119adfb
 
 
 My current issues with this:
 1) I don't like the names much. I called them Decay, decay and opDecay
 for a while. Name suggestions are welcome.
I'll leave the bikeshedding to others. :-P
 2) As mentioned above, implicit conversions would be nice, but that'd
 require an entirely new type of implicit conversion in addition to
 alias this, opDispatch, opDot and interfaces/base classes. This would
 require some pretty darn good reasons, and I don't think a call to
 headMutable() is that much of a problem.
In fact, if done correctly, I think the *lack* of implicit conversion might actually be a good thing, because the code will be more self-documenting as to what its intent really is. const(MyRange!T) r = ...; ... auto s = r.headMutable; // <-- explicit documentation of intent as opposed to: const(MyRange!T) r = ...; ... MyRange!(const T) s = r; // <-- intent not as clear While one could argue the latter is more concise and therefore more readable, the problem is that it hides the fact that user-defined code is being executed to perform the implicit conversion, and since D allows you to do all sorts of stuff with compile-time arguments, there's no guarantee that the implicit call to r.headMutable actually does what you think it does. Having to call .headMutable explicitly makes it clear that user code is being invoked, so that there is no illusion that we're just "automatically" promoting const(Templ!T) to Templ!(const T).
 Questions:
 Is a DIP required for this? Should I create a PR implementing this for
 the range types in Phobos? What other types would benefit from this?
[...] Since this would be introducing new symbols to Phobos, as well as, arguably, a new paradigm (or a significant extension to the existing paradigms), I think it would be best to get Andrei's attention on this issue and persuade him to support this, before submitting any PRs, lest the PR gets stuck in the queue over nitpicks and rot forever. For one thing, I'm in favor of something in this general direction (even if it doesn't end up being this specific proposal), so that we can use const more pervasively than right now, because currently, the transitivity of const severely limits how much code can actually use it. As Jonathan David has said, many of us have pretty much given up on const because it's just too difficult to work with. Having standard library support for .headMutable is an important first step in making const more widely usable, so that more code can benefit from its guarantees. T -- Talk is cheap. Whining is actually free. -- Lars Wirzenius
Jan 25
parent reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Thursday, 25 January 2018 at 19:54:55 UTC, H. S. Teoh wrote:
 I like this idea quite much, actually, in spite of the lack of 
 support for implicit conversions, which is a loss (but as you 
 said, we can't support that without breaking a lot of existing 
 stuff or introducing massive changes that are unlikely to be 
 accepted by Walter & Andrei).
Yeah. Arrays and pointers are special, and turn into their head-mutable equivalents completely unbidden, when passed to functions. No other types in the language does that, and it seems a weird semantic to specify for a given type, especially if just for making head-mutable work.
 Basically, instead of a bunch of convoluted rules with 
 poorly-understood corner cases, we delegate the responsibility 
 of constructing a head mutable type to the type itself, so the 
 user code decides for itself how to construct such a thing. 
 It's a clever idea.
Thank you. Given D's template system is very powerful, I think a solution where the type couldn't define its own conversion wouldn't be anywhere near viable.
 In fact, if the standard implementation of opHeadMutable is 
 basically the same across all types (or most types), it could 
 even be provided as a mixin template in the library, then all 
 you have to do is to `mixin headMutable` or something along 
 those lines, and off you go.
I believe this should be possible, but https://issues.dlang.org/show_bug.cgi?id=11098 causes me headaches: mixin template headMut() { auto opHeadMutable(this This)() { import std.traits : CopyTypeQualifiers, TemplateArgsOf, TemplateOf; import std.meta : staticMap; alias Tmpl = TemplateOf!This; alias Args = TemplateArgsOf!This; template Apply(T...) { static if (is(T[0])) alias Apply = HeadMutable!(CopyTypeQualifiers!(This, T)); else alias Apply = T; // cannot use local '__lambda1' as parameter } alias ReturnType = Tmpl!(staticMap!(Apply, Args)); return ReturnType(this); } } Another thought: T.opHeadMutable() and the free function headMutable() do basically the same thing, and could be unified through UFCS. There'd be a free function headMutable() that works for built-in types and UDTs that don't define their own T.headMutable(), and then UDTs with T.headMutable() would Just Work™. One less moving part.
 Questions:
 Is a DIP required for this? Should I create a PR implementing 
 this for
 the range types in Phobos? What other types would benefit from 
 this?
[...] Since this would be introducing new symbols to Phobos, as well as, arguably, a new paradigm (or a significant extension to the existing paradigms), I think it would be best to get Andrei's attention on this issue and persuade him to support this, before submitting any PRs, lest the PR gets stuck in the queue over nitpicks and rot forever.
My thoughts exactly, and the reason I haven't yet created a PR for it.
 For one thing, I'm in favor of something in this general 
 direction (even if it doesn't end up being this specific 
 proposal), so that we can use const more pervasively than right 
 now, because currently, the transitivity of const severely 
 limits how much code can actually use it. As Jonathan David has 
 said, many of us have pretty much given up on const because 
 it's just too difficult to work with.  Having standard library 
 support for .headMutable is an important first step in making 
 const more widely usable, so that more code can benefit from 
 its guarantees.
Thanks. I hope it can at least be a stepping stone on the way. -- Simen
Jan 25
parent Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
On Thursday, 25 January 2018 at 21:33:10 UTC, Simen Kjærås wrote:
 On Thursday, 25 January 2018 at 19:54:55 UTC, H. S. Teoh wrote:
 In fact, if the standard implementation of opHeadMutable is 
 basically the same across all types (or most types), it could 
 even be provided as a mixin template in the library, then all 
 you have to do is to `mixin headMutable` or something along 
 those lines, and off you go.
I believe this should be possible
I'm wrong, of course. Consider these two types: struct S(T) { T payload; } struct U(T) { T[] payload; } Clearly, a mixin would have problems with at least one of these. In the general case, the correlation between template parameters and member types can be arbitrarily complex, so a general solution is impossible, but even with this simple example there are problems. I wrote up a more formal description of what I'm suggesting: https://gist.github.com/Biotronic/c6eefeb9796309360a5e8696d91d924d -- Simen
Jan 29