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 2018
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 2018
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 2018
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 2018
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 2018
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 2018
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 2018
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 2018
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 2018
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 2018
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Jan 23, 2018 at 09:36:03AM +0000, Simen Kjærås 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 2018
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 2018
parent reply 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 2018
parent sclytrack <sclytrack fake.com> writes:
On Monday, 29 January 2018 at 13:07:05 UTC, Simen Kjærås wrote:

 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 wrote up a more formal description of what I'm suggesting:

 https://gist.github.com/Biotronic/c6eefeb9796309360a5e8696d91d924d

 --
   Simen



 headUnqualified
struct HeadUnqualifiedType1
{
	HeadUnqualifiedType2 field;
}

tailQualifierHeadUnqualified(const) HeadUnqualifiedType1 a;

//Stupid opaque data types.
Mar 10 2018