www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - The disadvantage of purity

reply berni44 <dlang d-ecke.de> writes:
I recently looked at issue 3821 (detecting recursive data 
structures in std.format to avoid a crash) [1]. I think, it could 
be easily fixed by collecting pointers to objects where toString 
is called and preventing a second call. Unfortunately (some 
instances of) format would not be pure anymore and this entails a 
lot of other functions which would loose it's purity. (And it 
doesn't work in CTFE, but that's an other story.)

The weird thing is, that the original call to the function 
(formatObject in std.format) would behave like a pure function: 
The result is always the same and the non local changes are 
temporary and not visible from the outside. The problem is, that 
this function should indeed return something different, when it 
calls itself (indirectly) with identical parameters once more to 
prevent the original call from never returning...

I have not yet a deep understanding of purity, so maybe there is 
a way arround this problem I cannot see due to my limited 
knowledge. Any ideas?

And, maybe somewhat heretical: Does the advantage of purity here 
really outweight the problems it causes?

[1] https://issues.dlang.org/show_bug.cgi?id=3821
Dec 29 2019
next sibling parent reply sarn <sarn theartofmachinery.com> writes:
On Sunday, 29 December 2019 at 10:02:48 UTC, berni44 wrote:

 I have not yet a deep understanding of purity, so maybe there 
 is a way arround this problem I cannot see due to my limited 
 knowledge. Any ideas?


Here's a generic pattern you could use:

T foo(Value x) pure
{
   static T impl(Value x, ref State s) pure
   {
     // ...code recursively calling impl and tracking state with 
mutable s
   }
   State s;
   return impl(x, s);
}
Dec 29 2019
parent Dominikus Dittes Scherkl <dominikus scherkl.de> writes:
On Sunday, 29 December 2019 at 10:40:23 UTC, sarn wrote:

 On Sunday, 29 December 2019 at 10:02:48 UTC, berni44 wrote:

 I have not yet a deep understanding of purity, so maybe there 
 is a way arround this problem I cannot see due to my limited 
 knowledge. Any ideas?


 Here's a generic pattern you could use:

 T foo(Value x) pure
 {
   static T impl(Value x, ref State s) pure
   {
     // ...code recursively calling impl and tracking state with 
 mutable s
   }
   State s;
   return impl(x, s);
 }


Yes, exactly this.
Dec 29 2019
prev sibling parent reply Dominikus Dittes Scherkl <dominikus scherkl.de> writes:
On Sunday, 29 December 2019 at 10:02:48 UTC, berni44 wrote:


 The problem is, that this function should indeed return 
 something different, when it calls itself (indirectly) with 
 identical parameters once more to prevent the original call 
 from never returning...


This should indeed be NOT the same parameters. There should be a 
hidden additional parameter (lets name it "called_internal"), 
that be false in the original call and true in a recursion. With 
this it's perfectly pure while returning something different if 
called by itself.
Dec 29 2019
next sibling parent berni44 <dlang d-ecke.de> writes:
On Sunday, 29 December 2019 at 10:46:07 UTC, Dominikus Dittes 
Scherkl wrote:

 This should indeed be NOT the same parameters. There should be 
 a hidden additional parameter (lets name it "called_internal"), 
 that be false in the original call and true in a recursion. 
 With this it's perfectly pure while returning something 
 different if called by itself.


Thanks for your ideas, but unfortunately I think these cannot be 
used here. The reason is, that I have no control over the 
intermediate steps, so I cannot pass that additional parameter 
(ref State s in sarn's code). These intermediate steps consist of 
calls to toString, which then do, whatever the user want's them 
to do, and eventually call format again and format calls 
formatObject with identical parameters. I can't change the 
signature of toString, nor make the users implement that...
Dec 29 2019
prev sibling parent Paul Backus <snarwin gmail.com> writes:
On Sunday, 29 December 2019 at 10:46:07 UTC, Dominikus Dittes 
Scherkl wrote:

 On Sunday, 29 December 2019 at 10:02:48 UTC, berni44 wrote:


 The problem is, that this function should indeed return 
 something different, when it calls itself (indirectly) with 
 identical parameters once more to prevent the original call 
 from never returning...


 This should indeed be NOT the same parameters. There should be 
 a hidden additional parameter (lets name it "called_internal"), 
 that be false in the original call and true in a recursion. 
 With this it's perfectly pure while returning something 
 different if called by itself.


The problem with this approach is that the recursion may not be 
direct. For example:

import std;

struct A
{
     B[] bs;
     void toString(W)(ref W w) { formattedWrite(w, "%s", bs[0]); }
}

struct B
{
     C[] cs;
     void toString(W)(ref W w) { formattedWrite(w, "%s", cs[0]); }
}

struct C
{
     A[] as;
     void toString(W)(ref W w) { formattedWrite(w, "%s", as[0]); }
}

void main()
{
     A[] as = [A()];
     B[] bs = [B()];
     C[] cs = [C(as)];
     as[0].bs = bs;
     bs[0].cs = cs;

     writeln(as[0]); // crashes
}

Solving this is probably halting-equivalent in the general case 
(that is, impossible), so I'm not inclined to worry too much 
about it. If someone writes an infinite loop in their toString 
method, that's their problem.
Dec 29 2019