We need a way to make functions pure and/or nothrow based on the purity and/or nothrowability of the functions that they call

[Jonathan M Davis]

On Sunday 14 November 2010 07:18:24 Tomasz Sowiński wrote:
> == Quote from Jonathan M Davis (jmdavisProg at 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