www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Creating immutable arrays in safe code

reply Dennis <dkorpel gmail.com> writes:
I like passing around immutable data, but I don't like creating 
it. Here are some toy examples to illustrate:

```D
immutable(int)[] positive(int[] input)  safe
{
     return input.filter!(x => x > 0).array;
}
```

 Error: cannot implicitly convert expression 
 `array(filter(input))` of type `int[]` to `immutable(int)[]`
So we need to tell the compiler the data is unique, but that's not ` safe`: ```D immutable(int)[] positive(int[] input) safe { return input.filter!(x => x > 0).array.assumeUnique(); } ```
 Error: ` safe` function `positive` cannot call ` system` 
 function `assumeUnique`
I can use `.idup` instead of `assumeUnique()` in ` safe` code, but that makes a redundant copy. We could mark the function ` trusted`, but I don't want ` trusted` functions all over my code, so I thought I'd make a little helper function: ```D auto iarray(R)(R range) { auto result = range.array; return (() trusted => result.assumeUnique)(); } ``` And I got plenty of use out of it so far. Maybe something like that already exists in Phobos, but I couldn't find it. It has its limits however: ```D immutable(int)[] sortedPositive(int[] input) safe { return input.filter!(x => x > 0).iarray.sort.release; } ``` That doesn't work because you can't sort an immutable array, so we're back to: ```D immutable(int)[] sortedPositive(int[] input) trusted { return input.filter!(x => x > 0).array.sort.release.assumeUnique(); } ``` I could make another primitive (`iarraySort`), but I wonder if there are more convenient ways to create immutable data in general?
Jul 16
next sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 7/16/21 1:19 PM, Dennis wrote:

 I like passing around immutable data
I think the D community needs to talk more about guidelines around 'immutable'. We don't... And I lack a complete understanding myself. :) To me, 'immutable' is a demand of the user from the provider that the data will not mutate. So, I don't agree with the sentiment "I like passing around immutable data" because 'immutable' limits usability without a user to demand it to begin with. To me, 'immutable' must be used when really needed.
 , but I don't like creating it.
I think making newly-created data 'immutable' renders it less useful. (The caller cannot mutate it.) So to me, newly created data should be mutable for the most usability. 'immutable' should be decided by the caller. Luckily, we have 'pure' allows the caller to make it 'immutable' effortlessly: import std; pure int[] positive(int[] input) safe { return input.filter!(x => x > 0).array; } void main() { immutable p = positive([1, 2]); } Now the function is 'pure' and the caller's data is 'immutable' because the caller decided it had to be immutable. On the other hand, the function is happier because it is useful to callers that may mutate the data. :) Ali
Jul 16
parent reply Dennis <dkorpel gmail.com> writes:
On Friday, 16 July 2021 at 20:39:41 UTC, Ali Çehreli wrote:
 So to me, newly created data should be mutable for the most 
 usability.
It's clear that I stripped away too much context with the toy examples, so let me try to add some back. I don't like forcing the use of `immutable` in general, but it's useful for transforming reference types into value types (inspired by [invariant strings](https://www.digitalmars.com/articles/b01.html) and `std.bigint`). The actual data structure I'm working with is a tree that looks like: ```D struct Expression { immutable(Expression)[] children; int value; } ```
 Now the function is 'pure' and the caller's data is 'immutable' 
 because the caller decided it had to be immutable.
I've encountered the use of `pure` for creating immutable data before, e.g: [Function Purity and Immutable Data Structure Construction](https://www.digitalmars.com/articles/b92.html). But `pure` is no silver bullet: ```D import std; pure: safe: struct Expression { immutable(Expression)[] children; int value; } Expression withSortedChildren(Expression exp) { return Expression(expr.children.dup.sort!((a, b) => a.value < b.value).release); } ```
 Error: cannot implicitly convert expression 
 `sort(dup(cast(const(Expression)[])expr.children)).release()` 
 of type `Expression[]` to `immutable(Expression)[]`
I've tried structuring it in a way that makes the compiler allow the conversion to immutable, but had no luck so far.
Jul 16
parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 7/16/21 3:21 PM, Dennis wrote:

 But `pure` is no silver bullet:
Agreed. I occasionally struggle with these issues as well. Here is a related one: import std; void foo(const int[] a) { auto b = a.array; b.front = 42; // Error: cannot modify `const` expression `front(b)` } I think that is a Phobos usability issue with array() because the freshly *copied* int elements are const. Really? So just because the programmer promised not to modify the parameter, now he/she is penalized to be *safe* with own data. I am not sure whether array() is the only culprit with this problem. (I think array() can be improved to pick mutable type for element types that have no indirections.)
 ```D
 import std;

 pure:  safe:

 struct Expression
 {
      immutable(Expression)[] children;
      int value;
 }

 Expression withSortedChildren(Expression exp)
 {
      return Expression(expr.children.dup.sort!((a, b) => a.value <
 b.value).release);
 }
 ```

 Error: cannot implicitly convert expression
 `sort(dup(cast(const(Expression)[])expr.children)).release()` of type
 `Expression[]` to `immutable(Expression)[]`
I've tried structuring it in a way that makes the compiler allow the conversion to immutable, but had no luck so far.
I don't have a solution and you have more experience with this. :/ Ali
Jul 16
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Jul 16, 2021 at 08:19:32PM +0000, Dennis via Digitalmars-d-learn wrote:
[...]
 ```D
 immutable(int)[] positive(int[] input)  safe
 {
     return input.filter!(x => x > 0).array;
 }
 ```
[...]
 I could make another primitive (`iarraySort`), but I wonder if there
 are more convenient ways to create immutable data in general?
Have you tried `pure`? T -- They say that "guns don't kill people, people kill people." Well I think the gun helps. If you just stood there and yelled BANG, I don't think you'd kill too many people. -- Eddie Izzard, Dressed to Kill
Jul 16
parent reply Dennis <dkorpel gmail.com> writes:
On Friday, 16 July 2021 at 20:45:11 UTC, H. S. Teoh wrote:
 Have you tried `pure`?
The code in question is all ` safe pure nothrow`.
Jul 16
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Jul 16, 2021 at 10:23:31PM +0000, Dennis via Digitalmars-d-learn wrote:
 On Friday, 16 July 2021 at 20:45:11 UTC, H. S. Teoh wrote:
 Have you tried `pure`?
The code in question is all ` safe pure nothrow`.
Hmm, OK. Not sure why .array isn't being inferred as unique... but yeah, you probably have to resort to using trusted with .assumeUnique. T -- Тише едешь, дальше будешь.
Jul 16
parent reply ag0aep6g <anonymous example.com> writes:
On 17.07.21 00:27, H. S. Teoh wrote:
 Hmm, OK. Not sure why .array isn't being inferred as unique... but yeah,
 you probably have to resort to using  trusted with .assumeUnique.
In addition to `pure`, you also need a const/immutable input and a mutable output, so that the output cannot be a slice of the input. For std.array.array it might be possible to carefully apply `Unqual` to the element type. I tried doing that, but `-preview=dip1000` causes trouble. This fails: ---- int[] array(const int[] input) pure nothrow safe { int[] output; foreach (element; input) output ~= element; return output; } void main() pure nothrow safe { const int[] c = [1, 2, 3]; immutable int[] i = array(c); /* Without `-preview=dip1000`: works, because the result is unique. With `-preview=dip1000`: "Error: cannot implicitly convert". */ } ---- I'm not sure what's going on. `pure` being involved makes me think of issue 20150. But it also fails with my fix for that issue. So maybe it's another bug.
Jul 16
parent reply Dennis <dkorpel gmail.com> writes:
On Saturday, 17 July 2021 at 05:44:24 UTC, ag0aep6g wrote:
 I tried doing that, but `-preview=dip1000` causes trouble. This 
 fails:
 (...)
 I'm not sure what's going on.
I'm not completely caught up, but from what I see, pure and immutable have a history of issues: [Issue 11503 - Type system breaking caused by implicit conversion for the value returned from pure function](https://issues.dlang.org/show_bug.cgi?id=11503) [Issue 11909 - Struct members and static arrays break pure function escape analysis (immutability violation)](https://issues.dlang.org/show_bug.cgi?id=11909) [Issue 15660 - break immutable with pure function and mutable reference params](https://issues.dlang.org/show_bug.cgi?id=15660) There used to be a complex `isReturnIsolated` check, but the [fix for issue 15660](https://github.com/dlang/dmd/pull/8048) reduced it to a check 'is the function strongly `pure`' which means 'parameters are values or immutable'. To reduce code breakage, the 'strong pure' requirement is only needed with -dip1000, which is why your example doesn't work with it.
Jul 17
parent reply ag0aep6g <anonymous example.com> writes:
On 17.07.21 13:05, Dennis wrote:
 There used to be a complex `isReturnIsolated` check, but the [fix for 
 issue 15660](https://github.com/dlang/dmd/pull/8048) reduced it to a 
 check 'is the function strongly `pure`' which means 'parameters are 
 values or immutable'. To reduce code breakage, the 'strong pure' 
 requirement is only needed with -dip1000, which is why your example 
 doesn't work with it.
Hm, as far as I understand, "strongly pure" doesn't require `immutable` parameters. `const` should be enough. The spec says: "A strongly pure function has no parameters with mutable indirections" [1]. Seems to me that the fix is buggy. Also, conflating other issues with DIP1000 is such an obviously terrible idea. [1] https://dlang.org/spec/function.html#pure-functions
Jul 17
parent reply Dennis <dkorpel gmail.com> writes:
On Saturday, 17 July 2021 at 12:05:44 UTC, ag0aep6g wrote:
 Hm, as far as I understand, "strongly pure" doesn't require 
 `immutable` parameters. `const` should be enough. The spec 
 says: "A strongly pure function has no parameters with mutable 
 indirections" [1].
I just took the description from the source code: ```D enum PURE : ubyte { impure = 0, // not pure at all fwdref = 1, // it's pure, but not known which level yet weak = 2, // no mutable globals are read or written const_ = 3, // parameters are values or const strong = 4, // parameters are values or immutable } ``` I don't know whether the spec or code is correct.
 Also, conflating other issues with DIP1000 is such an obviously 
 terrible idea.
Yup, [remember this](https://github.com/dlang/dmd/pull/8035#discussion_r174771516)?
Jul 17
next sibling parent rikki cattermole <rikki cattermole.co.nz> writes:
On 18/07/2021 12:56 AM, Dennis wrote:
 I don't know whether the spec or code is correct.
Unless otherwise specified, the code is authoritative.
Jul 17
prev sibling parent reply ag0aep6g <anonymous example.com> writes:
On 17.07.21 14:56, Dennis wrote:
 On Saturday, 17 July 2021 at 12:05:44 UTC, ag0aep6g wrote:
 Hm, as far as I understand, "strongly pure" doesn't require 
 `immutable` parameters. `const` should be enough. The spec says: "A 
 strongly pure function has no parameters with mutable indirections" [1].
I just took the description from the source code: ```D enum PURE : ubyte {     impure      = 0,    // not pure at all     fwdref      = 1,    // it's pure, but not known which level yet     weak        = 2,    // no mutable globals are read or written     const_      = 3,    // parameters are values or const     strong      = 4,    // parameters are values or immutable } ```
That looks off to me. Unless DMD has some secret knowledge about a shortcoming in the established definition of "strongly pure", I think those enum values are badly named. At a glance, the only meaningful use of `PURE.strong` seems to be in dcast.d, introduced by the PR you linked. Changing that to `PURE.const_` doesn't break any tests for me. So I'm inclined to believe that `PURE.strong` is nonsense, and that `PURE.const_` already means "strongly pure". However, changing that instance doesn't fix the issue. Apparently, DMD doesn't even recognize int[] array(const int[] input) pure { ... } as `PURE.const_`.
 I don't know whether the spec or code is correct.
When it comes to purity, another piece in the puzzle is David Nadlinger's article: https://klickverbot.at/blog/2012/05/purity-in-d/ There, a function with a `const int[]` parameter is described as "strongly pure". As far as I can remember, when DMD and that article disagreed in the past, DMD was wrong. [...]
 Yup, [remember 
 this](https://github.com/dlang/dmd/pull/8035#discussion_r174771516)?
Hehe, I knew I had complained about it before. It's doubly bad: (1) We're missing out on bug fixes, because they're hidden behind `-preview=dip1000` for no reason. (2) When `-preview=dip1000` ever becomes the default, code will break that doesn't even use the features of DIP 1000.
Jul 17
parent reply ag0aep6g <anonymous example.com> writes:
On 17.07.21 15:56, ag0aep6g wrote:
 At a glance, the only meaningful use of `PURE.strong` seems to be in 
 dcast.d, introduced by the PR you linked. Changing that to `PURE.const_` 
 doesn't break any tests for me. So I'm inclined to believe that 
 `PURE.strong` is nonsense, and that `PURE.const_` already means 
 "strongly pure".
 
 However, changing that instance doesn't fix the issue. Apparently, DMD 
 doesn't even recognize
 
      int[] array(const int[] input) pure { ... }
 
 as `PURE.const_`.
I've dug a bit deeper, and apparently I'm to blame for confusing things. In issue 15862 [1], I stated that functions with mutable indirections in the return type cannot be strongly pure. That's wrong, but it seems to have found its way into DMD. The core of issue 15862 is true: Two calls to `array` cannot be merged into one. But that doesn't make it weakly pure. Mutability in the return type is distinct from weak/strong purity. These are all true: * `array` is "strongly pure". * `array` is a "pure factory function". * The result of one call to `array` cannot be reused for another, identical call. [1] https://issues.dlang.org/show_bug.cgi?id=15862.
Jul 18
parent zjh <fqbqrr 163.com> writes:
On Sunday, 18 July 2021 at 10:02:07 UTC, ag0aep6g wrote:
 On 17.07.21 15:56, ag0aep6g wrote:
+1. IMO,`strong pure` is `the outside world` has no impact on me. `Funcs` don't have any `indirect`.
Jul 18