On Thursday, 15 May 2014 at 10:46:21 UTC, Ola Fosheim Grøstad wrote:
> On Thursday, 15 May 2014 at 09:45:52 UTC, Don wrote:
>> But it turns out that @memoizable isn't actually an interesting property, whereas '@noglobal' is.
>>
>> "No global state" is a deep, transitive property of a function. "Memoizable" is a superficial supersetextra property which the compiler can trivially determine from @noglobal.
>
> Uhm. That is a pretty strong assumption. "memoizable" is very useful property when you do multihreading, transactions or anything that requires locking.

It's useful, but it's not a deep property, and importantly, it isn't transient. The compiler can trivially work it out if it knows the function is @noglobal.

> And you can still access globals, you just need a guarantee that globals don't change until you are done.

Sure, but how can the compiler statically check that? It's a tough problem.
(That's not a rhetorical question, BTW. If you have a solution, that would be awesome).

> Considering that > 90% of the functions I write don't do IO or globals I'd rather specify the opposite. "io", "global" whatever. That is also easy to enforce, i.e. you don't get to access IO/globals if you don't annotate the function.

I agree, I'd personally like to have an annotation '@global', and put 'pure:' at the top of every module.

Don:

> I'd personally like to have an annotation '@global', and put 'pure:' at the top of every module.

I suggested a little more powerful @outer:
https://d.puremagic.com/issues/show_bug.cgi?id=5007

Bye,
bearophile

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.
>
> But note that "strong purity" isn't an official concept, it was
> just the terminology I used when explain to Walter what I meant.
> I don't like the term because it's rather misleading
> -- in reality you could define a whole range of purity strengths
> (more than just two).
> The stronger the purity, the more optimizations you can apply.

Yeah, I agree. The problem is that it always seems necessary to use the terms weak pure to describe the distinction - or maybe I just suck at coming up with a better way to describe it than you did initially. Your recent post in this thread talking about @noglobal seems to be a pretty good alternate way to explain it though. Certainly, the term pure throws everyone off at first.

- Jonathan M Davis

On 15.5.2014. 12:48, Don wrote:
> On Thursday, 15 May 2014 at 10:31:47 UTC, luka8088 wrote:
>> On 15.5.2014. 11:45, Don wrote:
>>> On Thursday, 15 May 2014 at 08:14:50 UTC, luka8088 wrote:
>>>> On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
>>>>> On Thu, 15 May 2014 05:51:14 +0000
>>>>> via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>>>>>
>>>>>> Yep, purity implies memoing.
>>>>>
>>>>> No, it doesn't. _All_ that it means when a function is pure is that
>>>>> it cannot
>>>>> access global or static variables unless they can't be changed after
>>>>> being
>>>>> initialized (e.g. they're immutable, or they're const value types),
>>>>> and it
>>>>> can't call any other functions which aren't pure. It means _nothing_
>>>>> else. And
>>>>> it _definitely_ has nothing to do with functional purity.
>>>>>
>>>>> Now, combined with other information, you _can_ get functional purity
>>>>> out it -
>>>>> e.g. if all the parameters to a function are immutable, then it _is_
>>>>> functionally pure, and optimizations requiring functional purity can
>>>>> be done
>>>>> with that function. But by itself, pure means nothing of the sort.
>>>>>
>>>>> So, no, purity does _not_ imply memoization.
>>>>>
>>>>> - Jonathan M Davis
>>>>>
>>>>
>>>> Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)"
>>>>
>>>> The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence.
>>>>
>>>> Even other sources are consistent on this matter, and this is what purity by definition is.
>>>
>>>
>>> Please note: D's 'pure' annotation does *not* mean that the function is pure. It means that it is statically verified to be OK to call it from a pure function.
>>>
>>> The compiler determines if a function is pure, the programmer never does.
>>>
>>> There are two things going on here, and they are quite distinct.
>>>
>>> (1) Really the keyword should be something like '@noglobal', rather than 'pure'. It's called pure for historical reasons. To reduce confusion I'll call D's pure '@noglobal' and the functional languages pure '@memoizable'.
>>>
>>> But it turns out that @memoizable isn't actually an interesting property, whereas '@noglobal' is.
>>>
>>> "No global state" is a deep, transitive property of a function. "Memoizable" is a superficial supersetextra property which the compiler can trivially determine from @noglobal.
>>>
>>> Suppose you have function f(), which calls function g().
>>>
>>> If f does not depend on global state, then g must not depend on global state.
>>>
>>> BUT if f() can be memoizable even if g() is not memoizable.
>>>
>>> This approach used by D enormously increases the number of functions which can be statically proven to be pure. The nomenclature can create confusion though.
>>>
>>>
>>> (2) Allowing GC activity inside a @noglobal function does indeed weaken
>>> our ability to memoize.
>>>
>>> The compiler can still perform memoizing operations on most functions that return GC-allocated memory, but it's more difficult. We don't yet have data on how much of a problem this is.
>>>
>>> An interesting side-effect of the recent addition of @nogc to the language, is that we get this ability back.
>>>
>>
>> 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. 'strong pure' means pure in the way that the functional language
> crowd means 'pure'.
> 'weak pure' just means doesn't use globals.
> 
> But note that "strong purity" isn't an official concept, it was just the
> terminology I used when explain to Walter what I meant. I don't like the
> term because it's rather misleading
> -- in reality you could define a whole range of purity strengths (more
> than just two).
> The stronger the purity, the more optimizations you can apply.
> 

Ok. Now it is much clearer, thanks.

On 15.5.2014. 13:04, Jonathan M Davis via Digitalmars-d wrote:
> 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.
>>
>> But note that "strong purity" isn't an official concept, it was
>> just the terminology I used when explain to Walter what I meant.
>> I don't like the term because it's rather misleading
>> -- in reality you could define a whole range of purity strengths
>> (more than just two).
>> The stronger the purity, the more optimizations you can apply.
> 
> Yeah, I agree. The problem is that it always seems necessary to use the terms weak pure to describe the distinction - or maybe I just suck at coming up with a better way to describe it than you did initially. Your recent post in this thread talking about @noglobal seems to be a pretty good alternate way to explain it though. Certainly, the term pure throws everyone off at first.
> 
> - Jonathan M Davis
> 

Yeah, +1.

Or @isolated, as in "isolated from outer scopes".

On Thursday, 15 May 2014 at 05:51:16 UTC, Ola Fosheim Grøstad wrote:
> On Thursday, 15 May 2014 at 02:49:28 UTC, Adam Sakareassen via Digitalmars-d wrote:
>> The more D allows 'pure' functions to diverge from functional purity the less relevant the flag is for compiler optimisations.
> ...
>> By the same reasoning cacheability is important.  A pure function might be called within a loop with a parameter that is not altered during the loop.  If the compiler knows the function is pure, it can perform the calculation before the loop and simply reuse the cached result for each iteration.
>
> Yep, purity implies memoing. Malloc and new are not pure because they return objects that can be differentiated by address.

There's an important difference between malloc and new: malloc returns a pointer, but new returns a typed object. This is crucial IMO, because the returned objects are equal to each other. They aren't identical, but then different int variables with the same value aren't identical either, and a function returning int is still considered pure. So it's not identity (~ address) that matters.

>
> Pure in D seems pointless to me.

Not at all: Don't think of it in terms of low-level optimization opportunities, but in terms of semantics. For example, you get the concept of uniqueness. And the optimizations can still be done, because strongly pure functions can be recognized by their signatures.

Marc Schütz:

> And the optimizations can still be done, because strongly pure functions can be recognized by their signatures.

What optimizations do you think GDC compiler is doing (or will do) on pure functions?

Bye,
bearophile

On Thursday, 15 May 2014 at 11:03:35 UTC, Don wrote:
>> And you can still access globals, you just need a guarantee that globals don't change until you are done.
>
> Sure, but how can the compiler statically check that? It's a tough problem.
> (That's not a rhetorical question, BTW. If you have a solution, that would be awesome).

What you need is some way to formally specify what a lock covers or rather register what globals can be accessed in a transaction. So you basically need some sort of whole program analysis.

With transactional memory you only take the lock if the transaction fails, so it is ok if locking is slow or to take multiple locks. The CPU reverts to regular mutex based locking and clears the cache if another thread touch the memory that has been used in the transaction.

At least that is how I read the Haswell documentation.

> I agree, I'd personally like to have an annotation '@global', and put 'pure:' at the top of every module.

It makes a lot of sense to put the annotation burden on the things you want less of, yes. "Do I really need to make this @global? Maybe I should do it some other way…"

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?

On Thursday, 15 May 2014 at 11:35:46 UTC, bearophile wrote:
> Marc Schütz:
>
>> And the optimizations can still be done, because strongly pure functions can be recognized by their signatures.
>
> What optimizations do you think GDC compiler is doing (or will do) on pure functions?
>

I don't know whether it does or will do any. It is a theoretical option ("can be done"). It's the kind of optimizations Ole talked about that apply only to functionally pure functions.

But the important point is that `new` can be pure, if you consider pure to be about equality, not identity. This applies only to typed allocators, not malloc.