www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - We need a way to make functions pure and/or nothrow based on the

reply Jonathan M Davis <jmdavisProg gmx.com> writes:
That is, there are plenty of cases where template code may or may not be able
to 
pure or nothrow and that whether it can or not depends on what it's templatized 
on. For instance, if you had a range which iterated over a range of characters 
in some manner (other than simply iterating over it as std.array would).
Whether 
or not empty could be pure or nothrow would depend on whether the range of 
characters that it holds has a empty which is pure or nothrow. At present, 
std.array's front is neither pure or nothrow, but it will hopefully become both 
later, and you could have a range of characters which isn't actually an array 
and whose empty is both pure and nothrow. So, whether or not the empty on the 
range type that you're instantiating can be pure or nothrow depends on what
it's 
iterating over. The only way that I know how to do that at present is to use 
static ifs and get 4 different implementations. e.g.

    static if((isArray!R && (functionAttributes!(std.array.empty!
(ElementType!R)) & FunctionAttribute.PURE)) ||
              (!isArray!R && (functionAttributes!(R.empty) & 
FunctionAttribute.PURE)))
    {
        static if((isArray!R && (functionAttributes!(std.array.empty!
(ElementType!R)) & FunctionAttribute.NOTHROW)) ||
                  (!isArray!R && (functionAttributes!(R.empty) & 
FunctionAttribute.NOTHROW)))
        {
             property bool empty() pure nothrow
            {
                return innerRange.empty;
            }
        }
        else
        {
             property bool empty() pure
            {
                return innerRange.empty;
            }
        }
    }
    else
    {
        static if((isArray!R && (functionAttributes!(std.array.empty!
(ElementType!R)) & FunctionAttribute.NOTHROW)) ||
                  (!isArray!R && (functionAttributes!(R.empty) & 
FunctionAttribute.NOTHROW)))
        {
             property bool empty() nothrow
            {
                return innerRange.empty;
            }
        }
        else
        {
             property bool empty()
            {
                return innerRange.empty;
            }
        }
    }


That is _not_ a pretty way to do this. And if the function that you're
declaring 
gets very complicated at all, you're going to need to find a way to get the 4 
versions to share code (probably via string mixin). The bodies are _identical_ 
and have no need to be different. _All_ you're changing is the function 
signature. And whether the function signature has pure and/or nothrow depends 
entirely on empty in this case. A more complicated function could depend on
half 
a dozen or a dozen different functions, and because you're dealing with a 
templated type or function, whether or not the function can be pure and/or 
nothrow varies with the type which is used to instantiate the template.

We really need to add a way to have a function marked as nothrow and/or pure 
based on whether the functions that it calls are nothrow and/or pure. Whether 
that should require listing the functions that need to be pure and/or nothrow
or 
whether the compiler should be able to figure it out on its own, I don't know. 
But the current situation is ugly.

The one problem I see is that if the compiler has to determine whether a given 
function can be pure and/or nothrow, it's going to potentially have to go 
arbitrarily deep into the call hierarchy to figure it out (which stinks of the 
halting problem), and it could require the source code of all of the functions 
that it has to check (or require that they've all already determined whether 
they can be pure and/or nothrow). I don't know whether that problem can be 
gotten around or what the best solution is if there is one, but the current 
situation is ugly.

As it stands, functions are likely to either be impure and be allowed to throw 
simply because doing otherwise would require declaring the function 4 times. 
std.algorithm and std.range are prime targets for places where functions 
_should_ be pure and nothrow if they can, but whether they can or not depends
on 
their template arguments. I really think that we need to find a solution to
this 
problem and relatively soon.

Does anyone have some good suggestions on how to solve this issue?

- Jonathan M Davis
Nov 14 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


The one problem I see is that if the compiler has to determine whether a given
function can be pure and/or nothrow, it's going to potentially have to go
arbitrarily deep into the call hierarchy to figure it out<


This is already done for pure functions, const, immutable, nothrow, etc, all of
them are transitive.



 Does anyone have some good suggestions on how to solve this issue?


I have an enhancement request on it, of course:
http://d.puremagic.com/issues/show_bug.cgi?id=5125

There I have suggested a  optional_tag(), the first argument is a compile-time
boolean and the second is an attribute/keyword like pure, nothrow,  safe, etc.:


 optional_tag(isPure!F, pure) int[] map(F)(F f, int[] data) {
    int[] res;
    foreach (x; data)
        res ~= f(x);
    return res;
}


Where isPure is just:

import std.traits: FunctionAttribute, functionAttributes;

template isPure(F) {
    enum bool isPure = functionAttributes!(F) & FunctionAttribute.PURE;
}


The name "optional_tag" may be improved. This solution is not much general, so
you may invent something more elegant.

Bye,
bearophile
Nov 14 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
  optional_tag(isPure!F, pure) int[] map(F)(F f, int[] data) {
     int[] res;
     foreach (x; data)
         res ~= f(x);
     return res;
 }


This may not suffice to correctly tell apart strong pure functions from weak
pure ones...

Bye,
bearophile
Nov 14 2010
parent reply =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
bearophile wrote:

  optional_tag(isPure!F, pure) int[] map(F)(F f, int[] data) {
     int[] res;
     foreach (x; data)
         res ~=3D f(x);
     return res;
 }


=20
 This may not suffice to correctly tell apart strong pure functions from=


 weak pure ones...

=20


	Untested:

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D8<------------------------------
template optionalTag (bool test, char[] tag) {
   static if (test)
      const char[] optionalTag =3D tag;
   else
      const char[] optionalTag =3D "";
}

template bool isPure(F)() {
   return functionAttributes!F & FunctionAttribute.PURE;
}

mixin(optionalTag!(isPure!F, "pure")) int[] map(F)(F f, int[] data) ...
------------------------------>8=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

	Of course, this suffers from the ugly syntax for string mixins...

		Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr
Nov 14 2010
parent bearophile <bearophileHUGS lycos.com> writes:
J. M. Berger:


 	Untested:


Test it! I think it can't work.

Bye,
bearophile
Nov 14 2010
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday 14 November 2010 04:26:56 bearophile wrote:

 Jonathan M Davis:

The one problem I see is that if the compiler has to determine whether a
given function can be pure and/or nothrow, it's going to potentially have
to go arbitrarily deep into the call hierarchy to figure it out<


 
 This is already done for pure functions, const, immutable, nothrow, etc,
 all of them are transitive.


Except that right now, all it has to do is look one level. If a function isn't 
marked as pure, then any pure function which tries to call it gets an error.
The 
signature is all that's needed. If the function being called is marked as pure 
but isn't really pure, then you'll get an error when that function is compiled. 
The compiler just has to worry about the signatures and doesn't have to dig 
arbitrarily deep. The same goes for the other attributes.

If you wanted to base the purity of a function on whether the functions it used 
being pure, you could just go off of the signatures, but then you couldn't get 
purity this way for more than one level, which doesn't solve the problem. For 
instance, all it would take would be a function in std.algorithm having to call 
empty on a range and have that empty being pure or not based on what _it_ was 
doing internally, and that std.algorithm function couldn't be pure. Effectively 
(ignoring the issue of mutual recursion), if you started at one function, you'd 
have to recursively check all of the functions that it calls for whether they 
can be pure, meaning that it cannot be compiled until all of them have been 
compiled. Right now, the signatures are enough. They wouldn't be if their
purity 
could changed. Now, since you'd be dealing with templates which have to be 
instantiated anyway, maybe it would work. But it could be seriously problematic.

- Jonathan M Davis
Nov 14 2010
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday 14 November 2010 04:26:56 bearophile wrote:

 Jonathan M Davis:

The one problem I see is that if the compiler has to determine whether a
given function can be pure and/or nothrow, it's going to potentially have
to go arbitrarily deep into the call hierarchy to figure it out<


 
 This is already done for pure functions, const, immutable, nothrow, etc,
 all of them are transitive.
 

 Does anyone have some good suggestions on how to solve this issue?


 
 I have an enhancement request on it, of course:
 http://d.puremagic.com/issues/show_bug.cgi?id=5125
 
 There I have suggested a  optional_tag(), the first argument is a
 compile-time boolean and the second is an attribute/keyword like pure,
 nothrow,  safe, etc.:
 
 
  optional_tag(isPure!F, pure) int[] map(F)(F f, int[] data) {
     int[] res;
     foreach (x; data)
         res ~= f(x);
     return res;
 }
 
 
 Where isPure is just:
 
 import std.traits: FunctionAttribute, functionAttributes;
 
 template isPure(F) {
     enum bool isPure = functionAttributes!(F) & FunctionAttribute.PURE;
 }
 
 
 The name "optional_tag" may be improved. This solution is not much general,
 so you may invent something more elegant.


 optional_tag as you suggest it does not deal with the same issue that I'm 
trying to address - though it is quite similar. My problem is when you have a 
function within a template where purity and nothrowability the functions called 
within that function depend on some or all of the template's parameters. So, 
checking the purity of a single function isn't going to do it (which appears to 
be what your  optional_tag is doing). Instead, you need a way to tell the 
compiler that if every function call within a function is pure, then mark it is 
pure. If no function call within a function is nothrow, then mark it as
nothrow. 
So,  optional(pure) or  optional(nothrow) makes more sense.

The more I look at it, the more it looks feasible too, because in this case,
the 
concern is templates. All of the functions in question or inside of templates 
trying to be instantiated. If a function call isn't a function within a 
template, then you already know whether it is pure or nothrow. If it's within a 
template, then you'll know as soon as its instantiated (even if it has to check 
other functions within templates that it calls), because any template functions 
that it uses have to be instantiated before it can be instantiated anyway.

Your issue with map is similar, and it could probably be dealt with as part of 
my suggestion, but it's more narrow than what I'm trying to address.

- Jonathan M Davis
Nov 14 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


 So, checking the purity of a single function isn't going to do it (which
appears to 
 be what your  optional_tag is doing).


The first argument of  optional_tag is a compile-time boolean, so you may test
all the functions you want (this reminds me Java checked exceptions a bit):

 optional_tag(isPure!foo && isPure!bar && isPure!spam, pure) int foo(int x) {
  return foo(x) + bar(x) + spam(x);
}



 you need a way to tell the compiler that if every function call within a
 function is pure, then mark it is pure. If no function call within a
 function is nothrow, then mark it as nothrow. 


The 'pure' tag is a way to tell some extra semantics to the compiler, that a
function doesn't use global mutable state. This is useful for the programmer
because it's simpler to reason about the function (and sometimes it decreases
bug count too), and it's useful for the compiler, because in some situations it
may optimize more aggressively, memory management too. The "nothrow" tag does
something similar for exceptions.

But if you add  optional(pure) you aren't protected against some bugs, because
if you call a not pure function your function automatically becomes not pure.
The good thing of  optional(pure) is that it's shorter and simpler to use.

Bye,
bearophile
Nov 14 2010
prev sibling parent reply Tomasz Sowi&#324;ski <just ask.me> writes:
== Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 [snip]
 We really need to add a way to have a function marked as nothrow and/or pure
 based on whether the functions that it calls are nothrow and/or pure. Whether
 that should require listing the functions that need to be pure and/or nothrow
or
 whether the compiler should be able to figure it out on its own, I don't know.
 But the current situation is ugly.
 The one problem I see is that if the compiler has to determine whether a given
 function can be pure and/or nothrow, it's going to potentially have to go
 arbitrarily deep into the call hierarchy to figure it out (which stinks of the
 halting problem), and it could require the source code of all of the functions
 that it has to check (or require that they've all already determined whether
 they can be pure and/or nothrow). I don't know whether that problem can be
 gotten around or what the best solution is if there is one, but the current
 situation is ugly.
 As it stands, functions are likely to either be impure and be allowed to throw
 simply because doing otherwise would require declaring the function 4 times.
 std.algorithm and std.range are prime targets for places where functions
 _should_ be pure and nothrow if they can, but whether they can or not depends
on
 their template arguments. I really think that we need to find a solution to
this
 problem and relatively soon.
 Does anyone have some good suggestions on how to solve this issue?


I recall a discussion on this:
http://www.digitalmars.com/d/archives/digitalmars/D/Generic_code_autoconst_autopure_autonothrow_116383.html

Although auto(pure) syntax is nice, I think the way to go is explicit qualifier
propagation because of the
problems you mentioned.

There could be a way of attaching a compile-time predicate to a qualifier,
either with a new keyword, or by
allowing mixing in qualifiers. It is quite generic, however, I predict it will
impose boilerplate in the style of
"if (check if this function is pure/nothrow/...) then (compose a
pure/nothrow/... string). Perhaps a simple
qualifier forwarding approach is more appealing:

// Forward a qualifier, if exists on R.empty
 property bool empty() __traits(fwdQual, R.empty, pure, nothrow)
{
    return innerRange.empty;
}

// Forward the intersection of all qualifiers from the functions involved.
auto reduce(fun, R)(R r) __traits(fwdQual, fun, R.empty, R.popFront, R.front);

The (accepted?) proposal of prettifying traits should help too:
__traits(fwdQual, ...) -> meta.fwdQual(...)

I'm a bit concerned how this cooks with the implementation of traits, e.g. I
noticed that a TraitsArgument cannot
be a StorageClass...
http://www.d-programming-language.org/traits.html
Any idea how hard it'd be to implement?

--
Tomek
Nov 14 2010
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Sunday 14 November 2010 07:18:24 Tomasz Sowi&#324;ski wrote:

 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article
 

 [snip]
 We really need to add a way to have a function marked as nothrow and/or
 pure based on whether the functions that it calls are nothrow and/or
 pure. Whether that should require listing the functions that need to be
 pure and/or nothrow or whether the compiler should be able to figure it
 out on its own, I don't know. But the current situation is ugly.
 The one problem I see is that if the compiler has to determine whether a
 given function can be pure and/or nothrow, it's going to potentially
 have to go arbitrarily deep into the call hierarchy to figure it out
 (which stinks of the halting problem), and it could require the source
 code of all of the functions that it has to check (or require that
 they've all already determined whether they can be pure and/or nothrow).
 I don't know whether that problem can be gotten around or what the best
 solution is if there is one, but the current situation is ugly.
 As it stands, functions are likely to either be impure and be allowed to
 throw simply because doing otherwise would require declaring the
 function 4 times. std.algorithm and std.range are prime targets for
 places where functions _should_ be pure and nothrow if they can, but
 whether they can or not depends on their template arguments. I really
 think that we need to find a solution to this problem and relatively
 soon.
 Does anyone have some good suggestions on how to solve this issue?


 
 I recall a discussion on this:
 http://www.digitalmars.com/d/archives/digitalmars/D/Generic_code_autoconst_
 autopure_autonothrow_116383.html
 
 Although auto(pure) syntax is nice, I think the way to go is explicit
 qualifier propagation because of the problems you mentioned.


The more I think about it, the more it seems doable though. We're talking about 
template functions or functions within template types here. They're the only 
functions whose purity or throwability could potentially change, because you 
don't necessarily know which types you're dealing with. With a normal function, 
it's known. And since you're going to have to instantiate all of these
templates 
anyway, it really isn't costing much extra, and you don't have to worry about 
the halting problem.

Essentially, if we had a way to mark a function within a template (be it a 
directly templated function or within a templated type) so that it becomes pure 
and nothrow if it can, what you get is this:

1. If all of the functions that it calls aren't in templates, then it can check 
for purity and nothrowability just by looking at their signatures. If the're
all 
pure, make the function pure. If they're all nothrow, make the function nothrow.

2. If one or more of the functions are in templates, that function has to be 
instantiated before you can do anything with it anyway, so instantiate the 
template. Any of its functions marked for potential purity and throwability go 
through #1 or #2, at which point their signatures are known (and since they
have 
to be instantiated before the compiler can know whether they even exist, that 
doesn't add any additional potential recursion). Once their signatures are 
known, you make the function pure if they're all pure and nothrow if they're
all 
nothrow.

All it would take would be an appropriate attribute on a template function to 
make it conditionally pure and conditionally nothrow. So, you could have 
 auto_pure and  auto_nothrow or something similar, and the compiler should be 
able to take care of it. Or, you could make it a bit more generic with
something 
like  auto(pure) or  optional(pure), similar to Bearophile's suggestion.

- Jonathan M Davis
Nov 14 2010