www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Improvement in pure functions specification

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
https://github.com/dlang/dlang.org/pull/1528 -- Andrei
Dec 20 2016
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 20.12.2016 23:49, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


Good, except:

"$(P `pure` functions returning `void` will be always called even if it 
is strongly `pure`. The implementation must assume the function does 
something outside the confines of the type system and is therefore not 
allowed to elide the call, even if it appears to have no possible effect.)"

I think this makes no sense. What is the idea behind this paragraph?
Dec 20 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/20/16 7:40 PM, Timon Gehr wrote:

 On 20.12.2016 23:49, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Good, except:

 "$(P `pure` functions returning `void` will be always called even if it
 is strongly `pure`. The implementation must assume the function does
 something outside the confines of the type system and is therefore not
 allowed to elide the call, even if it appears to have no possible effect.)"

 I think this makes no sense. What is the idea behind this paragraph?


A function that traces execution via a debug statement, for example. -- 
Andrei
Dec 20 2016
next sibling parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Tuesday, December 20, 2016 19:58:38 Andrei Alexandrescu via Digitalmars-d 
wrote:

 On 12/20/16 7:40 PM, Timon Gehr wrote:

 On 20.12.2016 23:49, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Good, except:

 "$(P `pure` functions returning `void` will be always called even if it
 is strongly `pure`. The implementation must assume the function does
 something outside the confines of the type system and is therefore not
 allowed to elide the call, even if it appears to have no possible
 effect.)"

 I think this makes no sense. What is the idea behind this paragraph?


 A function that traces execution via a debug statement, for example. --
 Andrei


Well, ultimately, strongly pure functions that return void are either doing
something that works around the type system (e.g. using debug statements to
do operations which aren't pure), or they arguably shouldn't even compile,
because they can't possibly do anything that has any effect on the program
beyond eating up CPU time. So, as far as I can tell, we should either make
an exception for them (as the PR currently does) or make them illegal.

- Jonathan M Davis
Dec 20 2016
parent reply Observer <spurious.address yahoo.com> writes:
On Wednesday, 21 December 2016 at 01:05:50 UTC, Jonathan M Davis 
wrote:

 On Tuesday, December 20, 2016 19:58:38 Andrei Alexandrescu via 
 Digitalmars-d wrote:

 On 12/20/16 7:40 PM, Timon Gehr wrote:

 On 20.12.2016 23:49, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Good, except:

 "$(P `pure` functions returning `void` will be always called 
 even if it is strongly `pure`. The implementation must 
 assume the function does something outside the confines of 
 the type system and is therefore not allowed to elide the 
 call, even if it appears to have no possible effect.)"

 I think this makes no sense. What is the idea behind this 
 paragraph?


 A function that traces execution via a debug statement, for 
 example. -- Andrei


 Well, ultimately, strongly pure functions that return void are 
 either doing something that works around the type system (e.g. 
 using debug statements to do operations which aren't pure), or 
 they arguably shouldn't even compile, because they can't 
 possibly do anything that has any effect on the program beyond 
 eating up CPU time. So, as far as I can tell, we should either 
 make an exception for them (as the PR currently does) or make 
 them illegal.


It seems to me that a pure function could have a variety of
acceptable side effects which don't modify active memory and
that don't work around the type system or necessarily eat
significant CPU time, and that you probably don't want to
have elided.  Here are some examples.

(1) Serve as a convenient breakpoint handle in the debugger, 
perhaps
     as a kind of centralized this_cannot_ever_happen() function.
(2) conditionally_die(conditions);
(3) Sleep for some run-time-computable length of time.
(4) Yield the thread so other threads can take execution priority.
(5) Yield the entire process so other processes can take execution
     priority.
(6) Wait for an external trigger (perhaps a hardware interrupt, 
for
     instance).
(7) Invoke a pass of garbage collection.

Aside from the first, whether or not the pure function actually 
takes
that action might depend on some complex calculation run inside 
the
pure function.

My point here is that when considering what functions do, mutating
memory is only part of the story.  Control of time and other 
resources
can be a critical part of overall program execution, and you 
don't want
the compiler assuming it can ignore such aspects.
Dec 22 2016
next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 22 December 2016 at 18:04:51 UTC, Observer wrote:


 (1) Serve as a convenient breakpoint handle in the debugger, 
 perhaps
     as a kind of centralized this_cannot_ever_happen() function.
 (2) conditionally_die(conditions);
 (3) Sleep for some run-time-computable length of time.
 (4) Yield the thread so other threads can take execution 
 priority.
 (5) Yield the entire process so other processes can take 
 execution
     priority.
 (6) Wait for an external trigger (perhaps a hardware interrupt, 
 for
     instance).
 (7) Invoke a pass of garbage collection.



A function that does any of that cannot be pure.
Dec 22 2016
parent reply Observer <spurious.address yahoo.com> writes:
On Thursday, 22 December 2016 at 18:49:02 UTC, Stefan Koch wrote:

 On Thursday, 22 December 2016 at 18:04:51 UTC, Observer wrote:


 (1) Serve as a convenient breakpoint handle in the debugger, 
 perhaps
     as a kind of centralized this_cannot_ever_happen() 
 function.
 (2) conditionally_die(conditions);
 (3) Sleep for some run-time-computable length of time.
 (4) Yield the thread so other threads can take execution 
 priority.
 (5) Yield the entire process so other processes can take 
 execution
     priority.
 (6) Wait for an external trigger (perhaps a hardware 
 interrupt, for
     instance).
 (7) Invoke a pass of garbage collection.



 A function that does any of that cannot be pure.


You judge too quickly.  (1) is certainly possible:

% cat pure.d
pure void cannot_happen_breakpoint () {
     return;
}

int main () {
     cannot_happen_breakpoint();
     return 0;
}
% dmd --version
DMD64 D Compiler v2.071.0
Copyright (c) 1999-2015 by Digital Mars written by Walter Bright
% dmd pure.d
% nm -pr pure | fgrep cannot
0000000000422a60 T _D4pure24cannot_happen_breakpointFNaZv
% gdb pure
GNU gdb (Ubuntu 7.7.1-0ubuntu5~14.04.2) 7.7.1
Copyright (C) 2014 Free Software Foundation, Inc.
...
Reading symbols from pure...(no debugging symbols found)...done.
(gdb) break _D4pure24cannot_happen_breakpointFNaZv
Breakpoint 1 at 0x422a64
(gdb) run
Starting program: /home/anon/dlang/pure
warning: the debug information found in "/lib64/ld-2.19.so" does 
not match "/lib64/ld-linux-x86-64.so.2" (CRC mismatch).

[Thread debugging using libthread_db enabled]
Using host libthread_db library 
"/lib/x86_64-linux-gnu/libthread_db.so.1".

Breakpoint 1, 0x0000000000422a64 in 
pure.cannot_happen_breakpoint() ()

With respect to the others, I see in testing that the compiler
objects to a pure function calling an impure function such as
sched_yield().  I was misled in my thinking by the 
nearly-exclusive
focus on memory mutation in the TDPL discussion of pure functions.

Note to Andrei:  in a revised TDPL, this aspect should be 
broadened,
to include explicit mention of other sorts of things that a pure
function is not allowed to do.  Yes, I know the text says "a 
function
is considered pure if returning a result is its only effect", but
from a teaching point of view, that's not enough emphasis to catch
the reader's attention when the entire rest of the discussion is
about mutation.

(Though frankly, I don't know why sched_yield() shouldn't be 
marked
as pure in core.sys.posix.sched.  It's not like a pure function
cannot be interrupted by a timeslice expiration at the OS level,
so calling sched_yield() ought to open no new doors.)
Dec 22 2016
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 23 December 2016 at 06:53:25 UTC, Observer wrote:
[ ... ]

A pure function MUST NOT mutate any state except what is 
reachable through it's arguments.
This includes ANY operating system state.

As for your debugger point.
You can break on a pure function as well as on any other.
And, yes that breakpoint can be shifted or invalided by compiler 
optimizations.
That is why there are debug builds for which the compiler avoids 
most optimizations.
Dec 22 2016
parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Friday, December 23, 2016 07:29:49 Stefan Koch via Digitalmars-d wrote:

 On Friday, 23 December 2016 at 06:53:25 UTC, Observer wrote:
 [ ... ]

 A pure function MUST NOT mutate any state except what is
 reachable through it's arguments.
 This includes ANY operating system state.


That's not quite true. For instance, the spec specifically permits pure
functions to read and write the floating point exception flags. Also,
functions like malloc have been marked with pure, and that technically
involves mucking with the OS state, albeit in a very specific and limited
way. So, there _are_ a few instances where we allow it. That being said,
it's certainly true that _most_ things that would involve the OS state are
forbidden from being messed with in pure functions unless the resource in
question is accessed via a function parameter. And any exceptions to that
rule have to be for a very good reason.

- Jonathan M Davis
Dec 23 2016
prev sibling parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thursday, December 22, 2016 18:04:51 Observer via Digitalmars-d wrote:

 It seems to me that a pure function could have a variety of
 acceptable side effects which don't modify active memory and
 that don't work around the type system or necessarily eat
 significant CPU time, and that you probably don't want to
 have elided.  Here are some examples.

 (1) Serve as a convenient breakpoint handle in the debugger,
 perhaps
      as a kind of centralized this_cannot_ever_happen() function.


I suppose, but that doesn't really have anything to do with what a purity.
Any function could be a point to break in the debugger.


 (2) conditionally_die(conditions);


Depending on what you mean by conditionally die, yes, that's legit. Errors
can be thrown from pure functions (even strongly pure functions), and the
spec specifically allows a pure function to terminate the program (so
calling exit should be legit, though I'm not sure if it's actually marked as
pure).


 (3) Sleep for some run-time-computable length of time.


This doesn't really make sense. It _might_ make sense for a weakly pure
function to do so via a function argument, but once we're talking strongly
pure functions, this doesn't make sense at all. At that point, we're talking
functional purity. The same input is supposed to give the exact same output,
and the compiler is free to optimize out calls to the pure function when
it's called multiple times with the same arguments. So, relying on anything
to do with timing simply wouldn't work, and sleeping in a strongly pure
function just doesn't make sense. It's questionable as to whether it even
makes sense in a weakly pure one. Regardless, right now, it certainly isn't
legal, because there is no sleep function marked as pure in druntime.


 (4) Yield the thread so other threads can take execution priority.

 (5) Yield the entire process so other processes can take execution
      priority.


These both have basically the same problem as sleeping. They may no sense
for strongly pure functions and questionable sense for weakly pure ones and
are not currently allowed in pure functions.


 (6) Wait for an external trigger (perhaps a hardware interrupt,
 for
      instance).


This definitely does not sound legit. It explicit depends on the OS state,
which is the sort of thing that's generally banned in pure functions.


 (7) Invoke a pass of garbage collection.


This, however, would probably be legit for the same reasons that new and
malloc are considered pure. Certainly, most of core.memory.GC is either
marked as pure or /* FIXME pure */, and given that GC.free is already pure,
having GC.collect be pure would make sense.


 My point here is that when considering what functions do, mutating
 memory is only part of the story.  Control of time and other
 resources
 can be a critical part of overall program execution, and you
 don't want
 the compiler assuming it can ignore such aspects.


Conceptually, it makes no sense to be doing any of that sort of thing in a
strongly pure function, because at that point, we're really talking
functional purity. The same input is supposed to give the same output, and
while it's debatable whether timing is part of that, it would have to at
least be taking the same actions given the same input. And if the compiler
has to worry about how the timing of a pure function affects the program,
then it could _never_ elide a call to a pure function, which would defeat
one of the main reasons that the feature was introduced in the first place.
So, I'm inclined to think that anything with regards to timing has no
business in a pure function.

- Jonathan M Davis
Dec 23 2016
parent reply Observer <spurious.address yahoo.com> writes:
On Friday, 23 December 2016 at 11:11:09 UTC, Jonathan M Davis 
wrote:

 Conceptually, it makes no sense to be doing any of that sort of 
 thing in a strongly pure function, because at that point, we're 
 really talking functional purity.


I understand your points.  I had been thinking about purity purely
from the standpoint of external mutation, since that's what the 
TDPL
discussion emphasizes, and neglected to consider possible compiler
optimizations (hoisting calls out of loops, for instance).  That
sort of thing would definitely mess with all of the examples I had
proposed.
Dec 23 2016
parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Friday, December 23, 2016 14:12:54 Observer via Digitalmars-d wrote:

 On Friday, 23 December 2016 at 11:11:09 UTC, Jonathan M Davis

 wrote:

 Conceptually, it makes no sense to be doing any of that sort of
 thing in a strongly pure function, because at that point, we're
 really talking functional purity.


 I understand your points.  I had been thinking about purity purely
 from the standpoint of external mutation, since that's what the
 TDPL
 discussion emphasizes, and neglected to consider possible compiler
 optimizations (hoisting calls out of loops, for instance).  That
 sort of thing would definitely mess with all of the examples I had
 proposed.


Optimization really only comes into play when the function is "strongly"
pure so that the compiler can guarantee that the arguments aren't mutated
and thus can guarantee that the function will always give the same result
for the same arguments, but it was originally one of the primary goals of
pure. Once pure was expanded to include "weakly" pure functions that
accepted mutable arguments but just didn't access mutable global state, then
the benefits of pure expanded considerably without really adding to the
optimization opportunities beyond the fact that without relaxing the purity
rules, pure functions were almost useless, because having to have all of the
parameters be immutable or implicitly convertible to immutable was just too
restrictive to be useful in most cases.

But since the whole reason that pure was relaxed was to make it so that more
functions could be "strongly" pure, we really don't want to degrade pure so
far that we lose out on the original benefits that pure was supposed to
provide, much as the fact that a pure function can't access mutable, global
state except via its arguments is actually a big benefit in its own right
even without the optimizations entering into the mix.

- Jonathan M Davis
Dec 23 2016
prev sibling next sibling parent reply Meta <jared771 gmail.com> writes:
On Wednesday, 21 December 2016 at 00:58:38 UTC, Andrei 
Alexandrescu wrote:

 On 12/20/16 7:40 PM, Timon Gehr wrote:

 On 20.12.2016 23:49, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Good, except:

 "$(P `pure` functions returning `void` will be always called 
 even if it
 is strongly `pure`. The implementation must assume the 
 function does
 something outside the confines of the type system and is 
 therefore not
 allowed to elide the call, even if it appears to have no 
 possible effect.)"

 I think this makes no sense. What is the idea behind this 
 paragraph?


 A function that traces execution via a debug statement, for 
 example. -- Andrei


The compiler will have to be changed for this part. Currently 
it's a warning (or maybe it was an error, can't remember) to call 
a strongly pure function returning void without doing 
`cast(void)fun()`.
Dec 20 2016
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/20/16 8:10 PM, Meta wrote:

 The compiler will have to be changed for this part. Currently it's a
 warning (or maybe it was an error, can't remember) to call a strongly
 pure function returning void without doing `cast(void)fun()`.


Interesting. As soon as the spec change is merged, we get to file an 
issue :o). -- Andrei
Dec 20 2016
prev sibling next sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Tue, Dec 20, 2016 at 07:58:38PM -0500, Andrei Alexandrescu via Digitalmars-d
wrote:

 On 12/20/16 7:40 PM, Timon Gehr wrote:

 On 20.12.2016 23:49, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 
 Good, except:
 
 "$(P `pure` functions returning `void` will be always called even if
 it is strongly `pure`. The implementation must assume the function
 does something outside the confines of the type system and is
 therefore not allowed to elide the call, even if it appears to have
 no possible effect.)"
 
 I think this makes no sense. What is the idea behind this paragraph?


 
 A function that traces execution via a debug statement, for example.
 -- Andrei


Isn't that impure by definition?!  How can tracing execution even be
remotely considered pure?

I understand that debug statements are a kind of backdoor to facilitate
debugging... but still. I'd expect we wouldn't bend the definition of
pure just for the sake of debugging -- that just sounds backwards. If a
function has side-effects outside of what's passed as arguments, I can't
see any way of justifying it being marked as pure.


T

-- 
They pretend to pay us, and we pretend to work. -- Russian saying
Dec 20 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/20/16 8:02 PM, H. S. Teoh via Digitalmars-d wrote:

 Isn't that impure by definition?!  How can tracing execution even be
 remotely considered pure?


That's why the compiler is required compulsively to call it. -- Andrei
Dec 20 2016
parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Tue, Dec 20, 2016 at 08:16:36PM -0500, Andrei Alexandrescu via Digitalmars-d
wrote:

 On 12/20/16 8:02 PM, H. S. Teoh via Digitalmars-d wrote:

 Isn't that impure by definition?!  How can tracing execution even be
 remotely considered pure?


 
 That's why the compiler is required compulsively to call it. -- Andrei


I don't follow.

The question was how can a function with side-effects (even given D's
relaxed definition of pure, i.e., allowing mutation via arguments) can
be considered pure.  What has that got to do with the compiler being
required to call it?

I'd say a pure void function should be equivalent to no-op and elidable.
If you want to call a function with side-effects from pure code for
debugging purposes, call it via the debug statement, e.g.:

	void impureDebugger(...) { ... } // N.B.: NOT pure

	pure void noop() {}

	pure auto pureFunc(A...)(A args) {
		...
		noop();	// may be elided
		...
		debug impureDebugger(1,2,3); // won't be elided
		...
	}

I don't see any good reason why we should bend the definition of pure to
allow pure void functions with side effects.


T

-- 
Beware of bugs in the above code; I have only proved it correct, not tried it.
-- Donald Knuth
Dec 20 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/20/16 8:54 PM, H. S. Teoh via Digitalmars-d wrote:

 On Tue, Dec 20, 2016 at 08:16:36PM -0500, Andrei Alexandrescu via
Digitalmars-d wrote:

 On 12/20/16 8:02 PM, H. S. Teoh via Digitalmars-d wrote:

 Isn't that impure by definition?!  How can tracing execution even be
 remotely considered pure?


 That's why the compiler is required compulsively to call it. -- Andrei


 I don't follow.

 The question was how can a function with side-effects (even given D's
 relaxed definition of pure, i.e., allowing mutation via arguments) can
 be considered pure.  What has that got to do with the compiler being
 required to call it?

 I'd say a pure void function should be equivalent to no-op and elidable.


If it's elidable, it's as good as a bug in the program. Must be either a 
compile-time error or a special case. -- Andrei
Dec 20 2016
parent sarn <sarn theartofmachinery.com> writes:
On Wednesday, 21 December 2016 at 02:27:02 UTC, Andrei 
Alexandrescu wrote:

 If it's elidable, it's as good as a bug in the program. Must be 
 either a compile-time error or a special case. -- Andrei


I can't see it ending well to make it this kind of special case.  
For example, one day someone will take one of these 
not-really-pure-by-any-definition-but-labelled-pure-for-some-reason-and-treat
d-as-a-special-case functions and make it return, I don't know, an int, and
then be surprised that the compiler now elides the function call.  If users
rely on this special case behaviour, eventually someone will need a way to make
a "pure"-with-side-effects function return values without being treated like a
pure function.

On the other hand, making it a compilation error might get in the 
way of generic programming, so that's worth considering.
Dec 20 2016
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 21.12.2016 01:58, Andrei Alexandrescu wrote:

 On 12/20/16 7:40 PM, Timon Gehr wrote:

 On 20.12.2016 23:49, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Good, except:

 "$(P `pure` functions returning `void` will be always called even if it
 is strongly `pure`. The implementation must assume the function does
 something outside the confines of the type system and is therefore not
 allowed to elide the call, even if it appears to have no possible
 effect.)"

 I think this makes no sense. What is the idea behind this paragraph?


 A function that traces execution via a debug statement, for example. --
 Andrei


IMNSHO, that shouldn't restrict a non-debug build, and it should not be 
thought of as being outside the type system's confines. Also:

- 'void' should not be a special case: either all pure functions can be 
optimized, or none of them. (a void-returning pure function can be 
called in a non-void-returning pure function.)

- pure functions cannot be elided without considering their bodies in in 
any case, as they can terminate the program by throwing an error:

immutable(void) fail()pure nothrow  safe{
     throw new Error("boom!");
}

or cause the program to fail to terminate:

immutable(void) loop()pure nothrow  safe{
     for(;;){}
}
Dec 21 2016
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/21/2016 05:08 AM, Timon Gehr wrote:

 On 21.12.2016 01:58, Andrei Alexandrescu wrote:

 On 12/20/16 7:40 PM, Timon Gehr wrote:

 On 20.12.2016 23:49, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Good, except:

 "$(P `pure` functions returning `void` will be always called even if it
 is strongly `pure`. The implementation must assume the function does
 something outside the confines of the type system and is therefore not
 allowed to elide the call, even if it appears to have no possible
 effect.)"

 I think this makes no sense. What is the idea behind this paragraph?


 A function that traces execution via a debug statement, for example. --
 Andrei


 IMNSHO, that shouldn't restrict a non-debug build, and it should not be
 thought of as being outside the type system's confines. Also:

 - 'void' should not be a special case: either all pure functions can be
 optimized, or none of them. (a void-returning pure function can be
 called in a non-void-returning pure function.)

 - pure functions cannot be elided without considering their bodies in in
 any case, as they can terminate the program by throwing an error:

 immutable(void) fail()pure nothrow  safe{
     throw new Error("boom!");
 }

 or cause the program to fail to terminate:

 immutable(void) loop()pure nothrow  safe{
     for(;;){}
 }


I'm not a fan of claiming to be cleverer than all future programmers. 
Allowing pure void(void) functions and making the compiler call them 
compulsively was my way of saying "hm, this is clever. This is too 
blatant of an error so I can only assume you wrote this function hoping 
it will be called. No idea what you do there, but I'm going to call it."

Apparently everybody else in this thread is clever enough so I'll 
eliminate the special case.


Andrei
Dec 21 2016
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/20/2016 05:49 PM, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


Dropped the void functions. On to the next scandal:


A function that accepts only parameters without mutable indirections and
returns a result that has mutable indirections is called a $(I pure factory
function). An implementation may assume that all mutable memory returned by
the call is not referenced by any other part of the program, i.e. it is
newly allocated by the function.



Andrei
Dec 21 2016
next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Wednesday, 21 December 2016 at 15:40:42 UTC, Andrei 
Alexandrescu wrote:

 On 12/20/2016 05:49 PM, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Dropped the void functions. On to the next scandal:


A function that accepts only parameters without mutable 
indirections and
returns a result that has mutable indirections is called a $(I 
pure factory
function). An implementation may assume that all mutable memory 
returned by
the call is not referenced by any other part of the program, 
i.e. it is
newly allocated by the function.



 Andrei


Couldn't this be folded into :
"The implementation may not remove a call to a pure function if 
does allocate memory ?"

Since there is the concept of weakly pure functions the compiler 
cannot decide to remove functions on signature alone.
Meaning the body has to be available for it to even attempt to 
elide the call.

Therefore specifying implementation behavior based on the 
function signature is misleading IMO.
Dec 21 2016
parent Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wednesday, December 21, 2016 15:49:35 Stefan Koch via Digitalmars-d 
wrote:

 On Wednesday, 21 December 2016 at 15:40:42 UTC, Andrei

 Alexandrescu wrote:

 On 12/20/2016 05:49 PM, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Dropped the void functions. On to the next scandal:

A function that accepts only parameters without mutable
indirections and
returns a result that has mutable indirections is called a $(I
pure factory
function). An implementation may assume that all mutable memory
returned by
the call is not referenced by any other part of the program,
i.e. it is
newly allocated by the function.


 Andrei


 Couldn't this be folded into :
 "The implementation may not remove a call to a pure function if
 does allocate memory ?"

 Since there is the concept of weakly pure functions the compiler
 cannot decide to remove functions on signature alone.
 Meaning the body has to be available for it to even attempt to
 elide the call.

 Therefore specifying implementation behavior based on the
 function signature is misleading IMO.


Why would the function body need to be there to elide the call? Only calls
to "strongly" pure functions can be elided when called multiple times, so
"weak" purity doesn't enter into the equation. And how "strong" a pure
function is has everything to do with its signature and nothing to do with
its body. pure has always been designed with the idea that it would be the
function signature that mattered. The body only comes into play when
inferring purity.

What Andrei has put here is to codify what the compiler needs to look at to
determine whether a strongly pure function may have allocated and returned
that memory (or something that referred to that memory) and made it so that
the compiler is not allowed to elide the call in that specific case. There
is no need to specifically mention memory allocation unless you're looking
to indicate why the spec is saying that such calls cannot be elided.

- Jonathan M Davis
Dec 21 2016
prev sibling next sibling parent reply Johan Engelen <j j.nl> writes:
On Wednesday, 21 December 2016 at 15:40:42 UTC, Andrei 
Alexandrescu wrote:

 On 12/20/2016 05:49 PM, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Dropped the void functions. On to the next scandal:


I think you should be very careful in making sure that `pure` 
does not become a pessimization keyword.

```
$(P Any `pure` function that is not strongly pure cannot be 
memoized. The
      compiler is required to honor all calls to the function, 
even if it appears
      to do nothing. (Example: a pure function taking no arguments 
and returning
      `int*` cannot be memoized. It also should not because it may 
be a typical
      factory function returning a fresh pointer with each call.))
```
I don't know what "required to honor all calls" means, but I 
guess it means
```
auto a = foo(); // int* foo() pure;
auto b = foo();
```
cannot be transformed to
```
auto a = foo(); // int* foo() pure;
auto b = a;
```

Super contrived, but I hope you get my drift:
```
int *awesome() pure {
   static if (ohSoAwesome) {
      return new int;
   } else {
      return null;
   }
}
```
Tagging this function with `pure` would be a pessimization.
Instead of
   "Any `pure` function that is not strongly pure cannot be 
memoized."
why not
   "Any `pure` function that is not strongly pure _may not be 
assumed to be_ memoizable."

Another example:
```
/// Note: need to mark this function as non-pure, because 
otherwise the compiler deduces it as pure and then pessimizes our 
code.
int *bar(bool returnNull) nonpure {
   if (returnNull) {
      return null;
   } else {
      return new ...;
   }
}

auto a = bar(true);
auto b = bar(true);
auto c = bar(true);
```

My concern with the current wording (like for the void function 
thing) is that it actively prohibits the compiler to do a 
transformation even if that is valid.

-Johan
Dec 21 2016
next sibling parent reply Johan Engelen <j j.nl> writes:
On Wednesday, 21 December 2016 at 20:04:04 UTC, Johan Engelen 
wrote:

 
   "Any `pure` function that is not strongly pure _may not be 
 assumed to be_ memoizable."


That version of mine is also not correct :(

How about: "A strongly pure function can be assumed to be 
memoizable. For a not strongly pure function, well, `pure` does 
not add information regarding memoizability."
Dec 21 2016
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/21/2016 03:10 PM, Johan Engelen wrote:

 On Wednesday, 21 December 2016 at 20:04:04 UTC, Johan Engelen wrote:

   "Any `pure` function that is not strongly pure _may not be assumed
 to be_ memoizable."


 That version of mine is also not correct :(

 How about: "A strongly pure function can be assumed to be memoizable.
 For a not strongly pure function, well, `pure` does not add information
 regarding memoizability."


OK save for the colloquial "well". -- Andrei
Dec 21 2016
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/21/2016 03:04 PM, Johan Engelen wrote:

 On Wednesday, 21 December 2016 at 15:40:42 UTC, Andrei Alexandrescu wrote:

 On 12/20/2016 05:49 PM, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Dropped the void functions. On to the next scandal:


 I think you should be very careful in making sure that `pure` does not
 become a pessimization keyword.

 ```
 $(P Any `pure` function that is not strongly pure cannot be memoized. The
      compiler is required to honor all calls to the function, even if it
 appears
      to do nothing. (Example: a pure function taking no arguments and
 returning
      `int*` cannot be memoized. It also should not because it may be a
 typical
      factory function returning a fresh pointer with each call.))
 ```
 I don't know what "required to honor all calls" means, but I guess it means
 ```
 auto a = foo(); // int* foo() pure;
 auto b = foo();
 ```
 cannot be transformed to
 ```
 auto a = foo(); // int* foo() pure;
 auto b = a;
 ```


That is correct.


 Super contrived, but I hope you get my drift:
 ```
 int *awesome() pure {
   static if (ohSoAwesome) {
      return new int;
   } else {
      return null;
   }
 }
 ```


Where does ohSoAwesome come from?


 Tagging this function with `pure` would be a pessimization.


Not to worry. It's all up to what can be detected. If inlining is in 
effect then definitely things can be optimized appropriately.


 Instead of
   "Any `pure` function that is not strongly pure cannot be memoized."
 why not
   "Any `pure` function that is not strongly pure _may not be assumed to
 be_ memoizable."


Got it. Good point. Will do.


 Another example:
 ```
 /// Note: need to mark this function as non-pure, because otherwise the
 compiler deduces it as pure and then pessimizes our code.
 int *bar(bool returnNull) nonpure {
   if (returnNull) {
      return null;
   } else {
      return new ...;
   }
 }

 auto a = bar(true);
 auto b = bar(true);
 auto c = bar(true);
 ```

 My concern with the current wording (like for the void function thing)
 is that it actively prohibits the compiler to do a transformation even
 if that is valid.


Yah, we kind of assume without stating that whole "observable behavior" 
that C++ does.


Andrei
Dec 21 2016
next sibling parent Johan Engelen <j j.nl> writes:
On Wednesday, 21 December 2016 at 21:34:04 UTC, Andrei 
Alexandrescu wrote:

 On 12/21/2016 03:04 PM, Johan Engelen wrote:

 
 ```
 I don't know what "required to honor all calls" means, but I 
 guess it means
 ```
 auto a = foo(); // int* foo() pure;
 auto b = foo();
 ```
 cannot be transformed to
 ```
 auto a = foo(); // int* foo() pure;
 auto b = a;
 ```


 That is correct.


Is that _all_ it is saying? Or is it also saying this:
```
void bar() {
    auto a = foo(); // int* foo() pure;
}

// cannot remove the call to bar, because bar calls a pure 
function and all calls must be "honored"
bar();
```
Dec 21 2016
prev sibling next sibling parent reply Johan Engelen <j j.nl> writes:
On Wednesday, 21 December 2016 at 21:34:04 UTC, Andrei 
Alexandrescu wrote:

 On 12/21/2016 03:04 PM, Johan Engelen wrote:


 Super contrived, but I hope you get my drift:
 ```
 int *awesome() pure {
   static if (ohSoAwesome) {
      return new int;
   } else {
      return null;
   }
 }
 ```


 Where does ohSoAwesome come from?


A random bool.
Perhaps something like this:
```
version(LDC)
   ohSoAwesome = true;
else
   ohSoAwesome = false
```

;-)
   Johan
Dec 21 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/21/2016 04:42 PM, Johan Engelen wrote:

 On Wednesday, 21 December 2016 at 21:34:04 UTC, Andrei Alexandrescu wrote:

 On 12/21/2016 03:04 PM, Johan Engelen wrote:


 Super contrived, but I hope you get my drift:
 ```
 int *awesome() pure {
   static if (ohSoAwesome) {
      return new int;
   } else {
      return null;
   }
 }
 ```


 Where does ohSoAwesome come from?


 A random bool.
 Perhaps something like this:
 ```
 version(LDC)
   ohSoAwesome = true;
 else
   ohSoAwesome = false
 ```


Well randomness is not available in pure functions. Anyhow I've 
reformulated the wording and added an example. The sheer fact it works 
is pretty awesome.

https://github.com/dlang/dlang.org/pull/1528

For now I didn't want to give thrown values any special treatment, i.e. 
maximum freedom for the implementation.


Andrei
Dec 21 2016
parent reply Johan Engelen <j j.nl> writes:
On Wednesday, 21 December 2016 at 22:08:58 UTC, Andrei 
Alexandrescu wrote:

 Well randomness is not available in pure functions.


Internet discussions... a misunderstanding, I should've been more 
careful.
I meant "an arbitrary boolean value", not something random (e.g. 
the version(LDC) thing).


 Anyhow I've reformulated the wording and added an example. The 
 sheer fact it works is pretty awesome.

 https://github.com/dlang/dlang.org/pull/1528


Perhaps you forgot to push, I see no update.
Dec 22 2016
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/22/2016 11:45 AM, Johan Engelen wrote:

 On Wednesday, 21 December 2016 at 22:08:58 UTC, Andrei Alexandrescu wrote:

 Well randomness is not available in pure functions.


 Internet discussions... a misunderstanding, I should've been more careful.
 I meant "an arbitrary boolean value", not something random (e.g. the
 version(LDC) thing).


 Anyhow I've reformulated the wording and added an example. The sheer
 fact it works is pretty awesome.

 https://github.com/dlang/dlang.org/pull/1528


 Perhaps you forgot to push, I see no update.


Thanks! Pushed just now. -- Andrei
Dec 22 2016
prev sibling parent reply deadalnix <deadalnix gmail.com> writes:
On Wednesday, 21 December 2016 at 21:34:04 UTC, Andrei 
Alexandrescu wrote:

 Instead of
   "Any `pure` function that is not strongly pure cannot be 
 memoized."
 why not
   "Any `pure` function that is not strongly pure _may not be 
 assumed to
 be_ memoizable."


 Got it. Good point. Will do.


That worse than the current wording.

Strongly pure function can be memoized doesn't mean that non 
strongly pure function can never be, just that the compiler would 
have to prove it is correct to do so before doing it.

On the other hand, this new wording do not guarantee that the 
compiler can do memorization on strongly pure functions. I don't 
think this is reasonable and in effect, makes pure useless for 
the optimizer outside of trivial cases. If you lie to the 
compiler by bypassing the type system in the pure function, 
that's on you. All user should not be penalized because someone 
decided they were very smart and got hoisted by their own petard.
Dec 22 2016
parent reply Johan Engelen <j j.nl> writes:
On Thursday, 22 December 2016 at 20:53:37 UTC, deadalnix wrote:

 On Wednesday, 21 December 2016 at 21:34:04 UTC, Andrei 
 Alexandrescu wrote:

 Instead of
   "Any `pure` function that is not strongly pure cannot be 
 memoized."
 why not
   "Any `pure` function that is not strongly pure _may not be 
 assumed to
 be_ memoizable."


 Got it. Good point. Will do.


 That worse than the current wording.


Yes, and I fixed it a few minutes after: 
https://forum.dlang.org/post/tnvpmtxcmqiwlmedyiei forum.dlang.org
Dec 23 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/23/2016 12:32 PM, Johan Engelen wrote:

 On Thursday, 22 December 2016 at 20:53:37 UTC, deadalnix wrote:

 On Wednesday, 21 December 2016 at 21:34:04 UTC, Andrei Alexandrescu
 wrote:

 Instead of
   "Any `pure` function that is not strongly pure cannot be memoized."
 why not
   "Any `pure` function that is not strongly pure _may not be assumed to
 be_ memoizable."


 Got it. Good point. Will do.


 That worse than the current wording.


 Yes, and I fixed it a few minutes after:
 https://forum.dlang.org/post/tnvpmtxcmqiwlmedyiei forum.dlang.org


Is the situash good now? -- Andrei
Dec 23 2016
parent reply Johan Engelen <j j.nl> writes:
On Friday, 23 December 2016 at 17:42:40 UTC, Andrei Alexandrescu 
wrote:

 On 12/23/2016 12:32 PM, Johan Engelen wrote:

 On Thursday, 22 December 2016 at 20:53:37 UTC, deadalnix wrote:

 On Wednesday, 21 December 2016 at 21:34:04 UTC, Andrei 
 Alexandrescu
 wrote:

 Instead of
   "Any `pure` function that is not strongly pure cannot be 
 memoized."
 why not
   "Any `pure` function that is not strongly pure _may not 
 be assumed to
 be_ memoizable."


 Got it. Good point. Will do.


 That worse than the current wording.


 Yes, and I fixed it a few minutes after:
 https://forum.dlang.org/post/tnvpmtxcmqiwlmedyiei forum.dlang.org


 Is the situash good now? -- Andrei


Yeah, with the extra sentences it's clear to (at least) me. The 
"cannot be assumed" may be read as "can never be assumed"; but 
it's clarified at the end of the paragraph.

Perhaps I read this wrong but: the paragraph says that 
non-strongly-pure functions receive no special treatment, but 
then the next paragraph adds special treatment for a subset of 
non-strongly-pure functions... :)

It's all nitpicking of course, and now things may be obvious. But 
one year from now I'm sure we'll have trouble figuring out what 
was really meant... :S
Dec 23 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/23/2016 01:53 PM, Johan Engelen wrote:

 Perhaps I read this wrong but: the paragraph says that non-strongly-pure
 functions receive no special treatment, but then the next paragraph adds
 special treatment for a subset of non-strongly-pure functions... :)


Fixed. Keep destruction coming. -- Andrei
Dec 23 2016
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/23/2016 02:32 PM, Andrei Alexandrescu wrote:

 On 12/23/2016 01:53 PM, Johan Engelen wrote:

 Perhaps I read this wrong but: the paragraph says that non-strongly-pure
 functions receive no special treatment, but then the next paragraph adds
 special treatment for a subset of non-strongly-pure functions... :)


 Fixed. Keep destruction coming. -- Andrei


Added:

$(P Destructors will always be called even if they appear to be strongly 
pure.)

Any other special functions we should worry about?


Andrei
Dec 23 2016
parent deadalnix <deadalnix gmail.com> writes:
On Friday, 23 December 2016 at 20:01:49 UTC, Andrei Alexandrescu 
wrote:

 $(P Destructors will always be called even if they appear to be 
 strongly pure.)

 Any other special functions we should worry about?


 Andrei


Why ?
Dec 28 2016
prev sibling parent reply John Colvin <john.loughran.colvin gmail.com> writes:
On Wednesday, 21 December 2016 at 15:40:42 UTC, Andrei 
Alexandrescu wrote:

 On 12/20/2016 05:49 PM, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Dropped the void functions. On to the next scandal:


A function that accepts only parameters without mutable 
indirections and
returns a result that has mutable indirections is called a $(I 
pure factory
function). An implementation may assume that all mutable memory 
returned by
the call is not referenced by any other part of the program, 
i.e. it is
newly allocated by the function.



 Andrei


There are 3 levels:
1) no idea what's going on: e.g. the function returns a mutable 
reference and also reads from global mutable memory.
2) memory must be new: e.g. returns 2 mutable references, no 
accessing external mutable memory.
3) memory must be new and uniquely referenced: function returns 1 
mutable reference, does not access external mutable memory.

If I'm not mistaken only 3 enables anything useful like implicit 
casts to immutable.

Also, "returned references" should be extended to include "out" 
parameters, because there's no difference as far as memory 
uniqueness is concerned.
Dec 21 2016
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/21/2016 03:59 PM, John Colvin wrote:

 On Wednesday, 21 December 2016 at 15:40:42 UTC, Andrei Alexandrescu wrote:

 On 12/20/2016 05:49 PM, Andrei Alexandrescu wrote:

 https://github.com/dlang/dlang.org/pull/1528 -- Andrei


 Dropped the void functions. On to the next scandal:


 A function that accepts only parameters without mutable indirections and
 returns a result that has mutable indirections is called a $(I pure
 factory
 function). An implementation may assume that all mutable memory
 returned by
 the call is not referenced by any other part of the program, i.e. it is
 newly allocated by the function.



 Andrei


 There are 3 levels:
 1) no idea what's going on: e.g. the function returns a mutable
 reference and also reads from global mutable memory.


That would be not pure.


 2) memory must be new: e.g. returns 2 mutable references, no accessing
 external mutable memory.


Yah, they could refer one another.


 3) memory must be new and uniquely referenced: function returns 1
 mutable reference, does not access external mutable memory.


Yah.


 If I'm not mistaken only 3 enables anything useful like implicit casts
 to immutable.


The formulation is careful to not specify what can be done. For now "not 
referenced by any other part of the program" nicely covers 2 and 3.


 Also, "returned references" should be extended to include "out"
 parameters, because there's no difference as far as memory uniqueness is
 concerned.


Cool idea.


Andrei
Dec 21 2016