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 2021
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 2021
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 2021
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 2021
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 2021
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 2021
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 2021
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 2021
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 2021
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 2021
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 2021
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 2021
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 2021
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 2021
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 2021