On 5/15/14, 6:02 AM, Steven Schveighoffer wrote:
> On Wed, 14 May 2014 20:50:08 -0400, Walter Bright
> <newshound2@digitalmars.com> wrote:
>
>> On 5/14/2014 5:03 PM, Meta wrote:
>>> Allocating memory through new and malloc should always be pure, I
>>> think, because
>>> failure either returns null in malloc's case,
>>
>> malloc cannot be pure if, with the same arguments, it returns null
>> sometimes and not other times.
>
> Basically, you are saying that malloc must return the same block
> whenever it's called with the same parameters. This is simply nonsense.
>
> null is not special, it's just another block.
>
> I'm not saying malloc should be pure based on this, but the possibility
> that it returns null does not disqualify it.

Null is special - it's a singularity. It can't be subsequently used for constructing a proper object. That makes it different even after we discount for comparing pointers.

Andrei

On 05/15/2014 02:57 PM, Steven Schveighoffer wrote:
> On Thu, 15 May 2014 02:50:05 -0400, Ola Fosheim Grøstad
> <ola.fosheim.grostad+dlang@gmail.com> wrote:
>
>> On Thursday, 15 May 2014 at 06:29:06 UTC, bearophile wrote:
>>> A little example of D purity (this compiles):
>>
>>> bool randomBit() pure nothrow @safe {
>>>     return (new int[1].ptr) > (new int[1].ptr);
>>> }
>>
>> Yes, and then you may as well allow a random generator with private
>> globals. Because memoing is no longer sound anyway.
>
> This has nothing to do with allocators being pure. They must be pure as
> a matter of practicality.
>
> The issue that allows the above anomaly is using the address of
> something. There is a reason functional languages do not allow these
> types of things. But in functional languages, allocating is allowed.
> ...

Not really, allocation is just an implementation detail. The computational language is meaningful independent of how you might achieve evaluation of expressions. I can in principle evaluate an expression of such a language on paper without managing a separate store, even though this usually will help efficiency.

Functional programming languages are not about taking away features from a procedural core language. They are based on the idea that the fundamental operation is substitution of terms.

> To be honest, code that would exploit such an anomaly is only ever used
> in "proof" exercises, and never in real code.

Hashtables are quite real.

> I don't think it's an issue.
>
> -Steve

This is the issue:

On Thu, 15 May 2014 10:48:07 +0000
Don via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>
>> Yes. 'strong pure' means pure in the way that the functional
>> language crowd means 'pure'.
>> 'weak pure' just means doesn't use globals.

There is no way to make that claim precise in an adequate way such that it is correct.

On 5/15/14, 6:28 AM, Dicebot wrote:
> This is not true. Because of such code you can't ever automatically
> memoize strongly pure function results by compiler. A very practical
> concern.

I think code that doesn't return pointers should be memoizable. Playing tricks with pointer comparisons would be appropriately penalized. -- Andrei

On 15 May 2014 23:47, Steven Schveighoffer via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
> On Thu, 15 May 2014 09:40:03 -0400, Manu via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>
>> On 15 May 2014 22:30, Steven Schveighoffer via Digitalmars-d
>>
>> <digitalmars-d@puremagic.com> wrote:
>>>
>>> On Thu, 15 May 2014 07:52:20 -0400, Manu via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>>>
>>>> On 15 May 2014 10:50, Walter Bright via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>>>>>
>>>>>
>>>>> On 5/14/2014 5:03 PM, Meta wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>> Allocating memory through new and malloc should always be pure, I
>>>>>> think,
>>>>>> because
>>>>>> failure either returns null in malloc's case,
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> malloc cannot be pure if, with the same arguments, it returns null
>>>>> sometimes
>>>>> and not other times.
>>>>
>>>>
>>>>
>>>> Even if it doesn't fail, malloc called with identical arguments still
>>>> returns a different result every time.
>>>> You can't factor malloc outside a loop and cache the result because
>>>> it's being called repeatedly with the same argument like you're
>>>> supposed to be able to do with any other pure function.
>>>> You shouldn't be able to do that with gcalloc either... how can gcalloc
>>>> be
>>>> pure?
>>>
>>>
>>>
>>> That only applies to strong-pure functions. malloc would be weak-pure,
>>> since
>>> it returns a mutable pointer.
>>
>>
>> Why should returning a mutable pointer imply weak purity?
>
>
> Because if it were strong-pure, the compiler could optimize two sequential calls as returning the same exact thing. Imagine if a constructor to a mutable object always returned the same object because the constructor's parameters were immutable. It would be useless.
>
> -Steve

I don't follow. Forget that it's a pointer... it's just a number. A
strong pure function simply doesn't modify it's inputs (which we can
guarantee with const/immutable args), and returns the same output.
It shouldn't matter if the output is mutable or not, it just has to be
the same. Whether it's the number 10, or a pointer.

I guess it logically follows that the output must be const or immutable, because it can only possibly be returning a pointer to, or to a member of, one of it's args... and 'turtles all the way down'. But that leads me back to where I started... how can it possibly be that an allocator of any sort can be pure? If you can allocate a new pointer, you can return it as a const or immutable pointer if you like, and then the function looks awfully like a strong pure function even though it returns a new pointer every time. That's not pure at all.

On 05/15/2014 05:24 PM, Andrei Alexandrescu wrote:
> On 5/15/14, 3:31 AM, luka8088 wrote:
>> Yeah, I read all about weak/string purity and I do understand the
>> background. I was talking about strong purity, maybe I should pointed
>> that out.
>>
>> So, to correct myself: As I understood strong purity implies
>> memoization. Am I correct?
>
> Yes, as long as you don't rely on distinguishing objects by address.
>
> Purity of allocation is frequently assumed by functional languages

Examples?

> because without it it would be difficult to get much work done.

Why?

> Then,
> most functional languages make it difficult or impossible to distinguish
> values by their address.

If it's not impossible because of lack of the concept it's not a pure functional language.

> In D that's easy. A D programmer needs to be
> aware of that, and I think that's fine.
>
>
> Andrei
>
>

It's not fine: The spec claims that this problem does not exist.

http://dlang.org/function.html

"... and in cases where the compiler can guarantee that a pure function cannot alter its arguments, it can enable full, functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)"

On 05/15/2014 11:45 AM, Don wrote:
>
> "No global state" is a deep, transitive property of a function.
> "Memoizable" is a superficial supersetextra

Why? A memoizable function is still memoizable if it is changed internally to memoize values in global memory, for example.

> property which the compiler
> can trivially determine from @noglobal.

On Thu, 15 May 2014 12:01:35 -0400, Manu via Digitalmars-d <digitalmars-d@puremagic.com> wrote:

> On 15 May 2014 23:47, Steven Schveighoffer via Digitalmars-d

>> Because if it were strong-pure, the compiler could optimize two sequential
>> calls as returning the same exact thing. Imagine if a constructor to a
>> mutable object always returned the same object because the constructor's
>> parameters were immutable. It would be useless.
>
> I don't follow. Forget that it's a pointer... it's just a number.

But that doesn't make sense. What you are returning is not the pointer value, but the pointed-at object. When you return an allocated object, you aren't returning the pointer, just a way to get to the object.

> A
> strong pure function simply doesn't modify it's inputs (which we can
> guarantee with const/immutable args), and returns the same output.
> It shouldn't matter if the output is mutable or not, it just has to be
> the same. Whether it's the number 10, or a pointer.

define "the same"?

char[] foo(int x) pure {return to!(char[])(x);}

would you argue that foo(5) always returns "5"? Or would you argue that it returns {length:1, ptr:0xee532000}?

A memoization would mean it's always returning the same exact object, not the same value.

> I guess it logically follows that the output must be const or
> immutable, because it can only possibly be returning a pointer to, or
> to a member of, one of it's args... and 'turtles all the way down'.

You are thinking of uniqueness of the result. That does not require strong purity.

> But that leads me back to where I started... how can it possibly be
> that an allocator of any sort can be pure? If you can allocate a new
> pointer, you can return it as a const or immutable pointer if you
> like, and then the function looks awfully like a strong pure function
> even though it returns a new pointer every time. That's not pure at
> all.

Strong pure is not required for implicit casting, uniqueness is. You can establish uniqueness based on comparing the return types to the parameters.

But a "strong pure" (and like Don says, this is really a bad description) as I understand it means pure in the functional purity sense -- all immutable parameters, all immutable returns, no global access. These can be optimized similarly to all functional languages (memoization of results, reordering or factoring of calls, dispatching calls to multiple threads, etc.).

-Steve

On Thu, 15 May 2014 11:42:00 -0400, Timon Gehr <timon.gehr@gmx.ch> wrote:

> On 05/15/2014 02:57 PM, Steven Schveighoffer wrote:
>> On Thu, 15 May 2014 02:50:05 -0400, Ola Fosheim Grøstad
>> <ola.fosheim.grostad+dlang@gmail.com> wrote:
>>
>>> On Thursday, 15 May 2014 at 06:29:06 UTC, bearophile wrote:
>>>> A little example of D purity (this compiles):
>>>
>>>> bool randomBit() pure nothrow @safe {
>>>>     return (new int[1].ptr) > (new int[1].ptr);
>>>> }
>>>
>>> Yes, and then you may as well allow a random generator with private
>>> globals. Because memoing is no longer sound anyway.
>>
>> This has nothing to do with allocators being pure. They must be pure as
>> a matter of practicality.
>>
>> The issue that allows the above anomaly is using the address of
>> something. There is a reason functional languages do not allow these
>> types of things. But in functional languages, allocating is allowed.
>> ...
>
> Not really, allocation is just an implementation detail. The computational language is meaningful independent of how you might achieve evaluation of expressions. I can in principle evaluate an expression of such a language on paper without managing a separate store, even though this usually will help efficiency.
>
> Functional programming languages are not about taking away features from a procedural core language. They are based on the idea that the fundamental operation is substitution of terms.

But they do not deal in explicit pointers. Otherwise, that's a can of worms that would weaken the guarantees, similar to how D's guarantees are weakened.

We have no choice in D, we must accept that explicit pointers are used.

>> To be honest, code that would exploit such an anomaly is only ever used
>> in "proof" exercises, and never in real code.
>
> Hashtables are quite real.

Pretend I'm ignorant, what does this imply?

> This is the issue:
>
> On Thu, 15 May 2014 10:48:07 +0000
> Don via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>>
>>> Yes. 'strong pure' means pure in the way that the functional
>>> language crowd means 'pure'.
>>> 'weak pure' just means doesn't use globals.
>
> There is no way to make that claim precise in an adequate way such that it is correct.

This doesn't help, I'm lost with this statement.

-Steve

On 5/15/2014 2:45 AM, Don wrote:
> An interesting side-effect of the recent addition of @nogc to the language, is
> that we get this ability back.

I hadn't thought of that. Pretty cool!

On 5/15/14, 9:03 AM, Timon Gehr wrote:
> On 05/15/2014 05:24 PM, Andrei Alexandrescu wrote:
>> On 5/15/14, 3:31 AM, luka8088 wrote:
>>> Yeah, I read all about weak/string purity and I do understand the
>>> background. I was talking about strong purity, maybe I should pointed
>>> that out.
>>>
>>> So, to correct myself: As I understood strong purity implies
>>> memoization. Am I correct?
>>
>> Yes, as long as you don't rely on distinguishing objects by address.
>>
>> Purity of allocation is frequently assumed by functional languages
>
> Examples?

cons 1 2 is equal to cons 1 2

>> because without it it would be difficult to get much work done.
>
> Why?

It's rather obvious. You've got to have the ability to create new values in a pure functional programming language.

>> Then,
>> most functional languages make it difficult or impossible to distinguish
>> values by their address.
>
> If it's not impossible because of lack of the concept it's not a pure
> functional language.

Agreed.

>> In D that's easy. A D programmer needs to be
>> aware of that, and I think that's fine.
>>
>>
>> Andrei
>>
>>
>
> It's not fine: The spec claims that this problem does not exist.

We must fix the spec. Please submit a pull request, thanks.


Andrei