View mode: basic / threaded / horizontal-split · Log in · Help
April 10, 2008
Re: pure or not pure?
Steven Schveighoffer wrote:
> I've been reading a bit about FP, and I see now that you are correct that 
> mutable data isn't allowed.  But let's not forget that D is not a functional 
> language, so a loop like:
> 
> for(int i = 0; i < n; i++)
>    statement;
> 
> Is legal inside a D pure function, whereas the same code would be achieved 
> through tail-recursion in a functional language.  Having mutable return 
> values and arguments may not prevent the compiler from considering the 
> function pure (then again, it may, that is my question).  But certainly, 
> comparing D to Haskell doesn't prove either case.

It doesn't. And whether we can have mutable arguments and/or mutable 
return values, is simply up to Walter. Nothing else.

However, I don't see any other way than both being immutable.

If you want to change the the value returned by a pure function, you 
have to make a copy of it. Just plain old COW. And most of the time, 
that feels natural anyway.

> I don't think the intent of bolting functional programming optimization 
> opportunities on top of D is going to mean that during pure functions we 
> will have to use a fully FP style.

That would be disaster. But that's just my opinion. :-)
April 10, 2008
Re: pure or not pure?
Janice Caron wrote:
> On 10/04/2008, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
> 
>> char[] c = new char[5];
>>
>> is invalid inside a pure function because the compiler cannot verify
>> uniqueness of mutable heap data, right?
> 
> No. As I said, new is special. It's integral to the language.

First of all, I think new is special anyhow.

Second, come to think of it, even if new weren't special, whatever it 
returns IS UNIQUE and as good as IMMUTABLE by others -- as seen FROM THE 
PERSPECTIVE OF THE  CALLER.

Which is actually all we care about, when we're inside a pure function.


In other words, if you new something, nobody else gets to change it 
since nobody else has a reference to this new data.

---

Ehrm. On second thought, it actually IS possible to end up in a 
situation where a just newed object may suddenly change in your hands, 
and also be referenced from other parts of the program.

(I'll leave constructing an example as an exercise.)

Now, the simplest thing to guarantee that not happening would be to deny 
newing of objects that have constructors.

When the compiler gets more advanced, it could examine such 
constructors, and only warn (or deny) newing objects where it can't 
verify such is not the case.

Until that, I guess we'll see what A/W have decided on this one. If, 
that is, they've come up with the above problem.
April 10, 2008
Re: pure or not pure?
"Georg Wrede" wrote
> Ehrm. On second thought, it actually IS possible to end up in a situation 
> where a just newed object may suddenly change in your hands, and also be 
> referenced from other parts of the program.
>
> (I'll leave constructing an example as an exercise.)
>
> Now, the simplest thing to guarantee that not happening would be to deny 
> newing of objects that have constructors.

In fact, I think the solution to this is to make a constructor that is pure 
:)

The problem with this is that the 'this' pointer is mutable when passed to 
the constructor, so you have mutable data being passed to a pure function. 
However, it is 'unique' data that has not been initialized anywhere, so this 
might be an exception to the rule.

Having the constructor pure solves any problems because you can't pass the 
'this' pointer out to some global function that might store it somewhere.

-Steve
April 10, 2008
Re: pure or not pure?
Steven Schveighoffer wrote:
> "Georg Wrede" wrote
> 
>>Ehrm. On second thought, it actually IS possible to end up in a situation 
>>where a just newed object may suddenly change in your hands, and also be 
>>referenced from other parts of the program.
>>
>>(I'll leave constructing an example as an exercise.)
>>
>>Now, the simplest thing to guarantee that not happening would be to deny 
>>newing of objects that have constructors.
> 
> 
> In fact, I think the solution to this is to make a constructor that is pure 
> :)

Yes. And thus, a pure constructor cannot write to class variables, only 
instance variables.

> The problem with this is that the 'this' pointer is mutable when passed to 
> the constructor, so you have mutable data being passed to a pure function. 
> However, it is 'unique' data that has not been initialized anywhere, so this 
> might be an exception to the rule.

I agree. One might consider the "this" varable as either actually 
pointing to this particular instance or else consider it invalid. If we 
define it so, then "this" can be considered immutable.

Besides, since we don't have a reallocating GC, and we can't (at least I 
don't now remember otherwise) store object instances in (potentially 
relocating) arrays (only references to them), the "this" pointer could 
be made immutable everywhere.

> Having the constructor pure solves any problems because you can't pass the 
> 'this' pointer out to some global function that might store it somewhere.

Yes.
April 11, 2008
Re: pure or not pure?
On Thu, 10 Apr 2008 21:41:15 +0400, Janice Caron <caron800@googlemail.com>  
wrote:

> On 10/04/2008, Koroskin Denis <2korden+dmd@gmail.com> wrote:
>>  OK, new is 'special', but what about malloc or my own allocator? (I  
>> happen
>> to work in a gamedev and we never use new nor malloc).
>>  I don't see how
>>
>>  special extern(C) void* malloc(size_t size);
>>
>>  differs from:
>>
>>  void* my_malloc(size_t size)
>>  {
>>    return malloc(size);
>>  }
>>
>>  and why can't it be 'special' too.
>
> Because you're modifying global state.
>
> One of the reasons why new is special is because you never have to
> delete (because the garbage collector takes care of it). This is
> directly comparable to, for example, Haskell, where new "things" are
> created all the time, and are never freed. It's built into the system.
> More - it /is/ the system. That's the status of new. It's the de facto
> heap allocation method in D.
>
> If you want to use custom allocators, there's nothing to stop you, but
> that doesn't change the fact that the minute you modify global state,
> you have a function that isn't pure.
>
> I think you're worrying too much. There should never be a need to call
> malloc and free inside a pure function. If you need a function that
> does impure stuff, just write the function anyway, and don't call it
> pure.

Well, I don't distinguish between new and malloc. They both are impure and
/shouldn't/ be callable from pure functions. In fact, there is a solution:
inew (for short, or new invariant(T) from accu-functional).

Obviously enough, new can't be pure:

T t1 = new T();
T t2 = new T();

Since it can't be rewritten to:

T t1 = new T();
T t2 = t1;

However, inew /is/ pure:

T t1 = inew T();
T t2 = t1;

Is this the key!?

Yet, there is one more exception: rand(). I believe Haskell /has/ random  
numbers,
therefore it should be callable from pure functions, isn't it?

Other solution could be to introduce some 'uncachable' keyword, so that we  
could declare:

uncachable int rand();
uncachable void* malloc(size_t size);

> [snip]
> I should have added: /neither/ of those functions is pure.
>
> In fact, I strongly doubt that any function declared extern(C) will be
> pure, for the simple and obvious reason that C doesn't have the "pure"
> keyword. :-)

Agreed, C doesn't but pure and impure follow the same calling convention
(I hope), so there is no difference between two from linker's point of  
view.

Can't see why isalpha/isdigit/tolower/etc. can't be declared pure:

extern "C" {
   pure int isalpha(int c);
   pure int isdigit(int c);
   pure int tolower(int c);
}
April 11, 2008
Re: pure or not pure?
On Thu, 10 Apr 2008 17:26:20 +0400, Steven Schveighoffer  
<schveiguy@yahoo.com> wrote:

> "Janice Caron" wrote
>> On 09/04/2008, Steven Schveighoffer wrote:
>>> So how is new char[] a pure function?
>>
>> new is special.
>>
>>>  And why can't I 'wrap' new?  For
>>>  instance, if I have a function:
>>>
>>>  int[] createIncreasingSequence(int s, int e, int step){...}
>>>
>>>  which creates an array of ints that start at s and end at e,  
>>> increasing
>>> by
>>>  step each time, why can't I make that pure?
>>
>> I reckon you can, but you got the return type wrong.
>>
>>    invariant(int)[] createIncreasingSequence(int s, int e, int  
>> step){...}
>>    {
>>        auto array = new int[(e-s)/step];
>>        foreach(ref a;array)
>>        {
>>            a = e;
>>            e += step;
>>        }
>>        return assumeUnique!(array);
>>    }
>
> This doesn't work for what I'm asking.  I'll add more detail to the  
> example.
> You have two functions f, and g:
>
> pure int f()
> {
>     int[] x = new int[5];
>     for(int i = 0; i < x.length; i++)
>        x[i] = 1 + i;
>
>     /* do stuff */
>     return result;
> }
>
> pure int g()
> {
>     int[] y = new int[15];
>     for(int i = 0; i < y.length; y++)
>         y[i] = 10 + (i * 3);
>
>     /* do stuff */
>     return result;
> }
>
> Now, I realize I have very similar code that initializes the int arrays,  
> so
> I want to put that into a function that creates and initializes an array
> with the given parameters:
>
> int[] createIncreasingSequence(int length, int start, int step)
> {
>     int[] result = new int[length];
>     for(int i = 0; i < result.length; i++)
>         result[i] = start + (i * step);
>     return result;
> }
>
> Now, I think we all agree that createIncreasingSequence is as pure as
> calling new, right?  That is, it doesn't affect any global state (except  
> for
> allocating heap data) and will return an equivalent array every time the
> same arguments are given.  But if I can't declare it as 'pure', then I  
> can't
> call it from f and g:
>
> pure int f()
> {
>    int[] x = createIncreasingSequence(5, 1, 1);
>
>    /* do stuff */
>    return result;
> }
>
> pure int g()
> {
>    int[] y = createIncreasingSequence(15, 10, 3);
>
>    /* do stuff */
>    return result;
> }
>
> So should there be a way to define createIncreasingSequence such that I  
> can
> call it from a pure function?  Or do I have to re-implement it in every  
> pure
> function I use?
>

There is a way with inew (invariant new):

class IncreasingSequence(int length)
{
public:
   this(int start, int step)
   {
      for(int i = 0; i < length; i++)
         elements[i] = start + (i * step);
   }

   int[length] elements;
}

pure int f()
{
   auto x = inew IncreasingSequence!(5)(1, 1);

   /* do stuff */
   return result;
}

pure int g()
{
   auto y = inew IncreasingSequence!(15)(10, 3);

   /* do stuff */
   return result;
}

Isn't it beautiful? Yet, it's /very/ close to wait you wanted.
April 11, 2008
Re: pure or not pure?
Nope, not close :)  In fact, I want a mutable array because I intend to play 
with the values later in the function (I didn't make that clear I guess).

I agree that in the case that I don't need a mutable array, returning an 
invariant array is an acceptable solution, I don't even think you need a 
class for it, a pure function will do just fine.

But returning a mutable array IMO does not make the function impure, it just 
means you cannot cache the return value.  The compiler could be made to 
assume this when seeing that the return value has a mutable heap pointer.

-Steve

"Koroskin Denis" wrote
On Thu, 10 Apr 2008 17:26:20 +0400, Steven Schveighoffer
wrote:
> "Janice Caron" wrote
>> On 09/04/2008, Steven Schveighoffer wrote:
>>> So how is new char[] a pure function?
>>
>> new is special.
>>
>>>  And why can't I 'wrap' new?  For
>>>  instance, if I have a function:
>>>
>>>  int[] createIncreasingSequence(int s, int e, int step){...}
>>>
>>>  which creates an array of ints that start at s and end at e, 
>>> increasing
>>> by
>>>  step each time, why can't I make that pure?
>>
>> I reckon you can, but you got the return type wrong.
>>
>>    invariant(int)[] createIncreasingSequence(int s, int e, int 
>> step){...}
>>    {
>>        auto array = new int[(e-s)/step];
>>        foreach(ref a;array)
>>        {
>>            a = e;
>>            e += step;
>>        }
>>        return assumeUnique!(array);
>>    }
>
> This doesn't work for what I'm asking.  I'll add more detail to the 
> example.
> You have two functions f, and g:
>
> pure int f()
> {
>     int[] x = new int[5];
>     for(int i = 0; i < x.length; i++)
>        x[i] = 1 + i;
>
>     /* do stuff */
>     return result;
> }
>
> pure int g()
> {
>     int[] y = new int[15];
>     for(int i = 0; i < y.length; y++)
>         y[i] = 10 + (i * 3);
>
>     /* do stuff */
>     return result;
> }
>
> Now, I realize I have very similar code that initializes the int arrays, 
> so
> I want to put that into a function that creates and initializes an array
> with the given parameters:
>
> int[] createIncreasingSequence(int length, int start, int step)
> {
>     int[] result = new int[length];
>     for(int i = 0; i < result.length; i++)
>         result[i] = start + (i * step);
>     return result;
> }
>
> Now, I think we all agree that createIncreasingSequence is as pure as
> calling new, right?  That is, it doesn't affect any global state (except 
> for
> allocating heap data) and will return an equivalent array every time the
> same arguments are given.  But if I can't declare it as 'pure', then I 
> can't
> call it from f and g:
>
> pure int f()
> {
>    int[] x = createIncreasingSequence(5, 1, 1);
>
>    /* do stuff */
>    return result;
> }
>
> pure int g()
> {
>    int[] y = createIncreasingSequence(15, 10, 3);
>
>    /* do stuff */
>    return result;
> }
>
> So should there be a way to define createIncreasingSequence such that I 
> can
> call it from a pure function?  Or do I have to re-implement it in every 
> pure
> function I use?
>

There is a way with inew (invariant new):

class IncreasingSequence(int length)
{
public:
   this(int start, int step)
   {
      for(int i = 0; i < length; i++)
         elements[i] = start + (i * step);
   }

   int[length] elements;
}

pure int f()
{
   auto x = inew IncreasingSequence!(5)(1, 1);

   /* do stuff */
   return result;
}

pure int g()
{
   auto y = inew IncreasingSequence!(15)(10, 3);

   /* do stuff */
   return result;
}

Isn't it beautiful? Yet, it's /very/ close to wait you wanted.
April 14, 2008
Re: pure or not pure?
On 11/04/2008, Koroskin Denis <2korden+dmd@gmail.com> wrote:
> I don't distinguish between new and malloc.

malloc() needs free().
new needs nothing, since we have a garbage collector.

That is a /big/ difference.
Next ›   Last »
1 2 3 4
Top | Discussion index | About this forum | D home