On 5/28/2019 2:12 PM, Jonathan Marler wrote:
> turtles all the way down.

Again, it is not that simple. Call graphs have cycles in them, they are not acyclic. Furthermore, since you suggested different code be instantiated based on inferred attributes, you have a FAR FAR more complex problem to resolve, since the graph connections change at every decision point.

On Tue, May 28, 2019 at 9:10 AM Andrei Alexandrescu via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>
> int fun(int) pure;
> int fun(int);
>
> pure int gun(int x)
> {
>     return fun(x);
> }
>
> This doesn't work, but on the face of it it's not ambiguous - the second overload of fun() would not compile anyway.
>
> I was wondering whether allowing overloading on attributes in general would be a good idea. I suspect templates and attribute deduction make that difficult.

I have wanted to overload on nothrow-ness before.

On Tuesday, 28 May 2019 at 21:41:28 UTC, Walter Bright wrote:
> On 5/28/2019 2:12 PM, Jonathan Marler wrote:
>> turtles all the way down.
>
> Again, it is not that simple. Call graphs have cycles in them, they are not acyclic. Furthermore, since you suggested different code be instantiated based on inferred attributes, you have a FAR FAR more complex problem to resolve, since the graph connections change at every decision point.

Again, in this case it is that simple. I'll explain it another way, maybe it will make sense this time.

Attributes on functions inside template are inferred bottom-up, but templates are instantiated top-down.  So trying to use inferred attributes to affect template instances is going to get you into a cyclic mess.  In this case you are absolutely right.

What I was suggesting is that you propagate the state as to whether or not the GC is allowed top-down, the same way templates are instantiated.  You could do this today with template parameters, but like I said, it's not scalable because it requires every single template to add this parameter.  It works because you are propagating this state in the same direction as you are instantiating the templates, top down, so you know before you even see the inside of the template whether or not the GC is allowed.

So the argument that this creates a complex cyclic dependency resolution problem is not correct in the example I showed.  However, there are other arguments against it, the main one I see being that you would essentially need to add "implicit template parameters". This would be a big change to the language with alot of consequences, something that would most certainly require a DIP and alot of research and thought, but, you shouldn't immediately dismiss and idea with "Hell No", especially when you don't fully understand it.

On Tue, May 28, 2019 at 11:10 AM Walter Bright via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>
> On 5/28/2019 10:35 AM, Jonathan Marler wrote:
> > After reading Walter's response here, another thought came to mind that instead of attribute overloading, a template with static-if could also be used.
>
> @nogc attributes are often inferred. Such constructs would make it undecidable.

I have never encountered a case with @nogc where I would want to overload on attribute alone; the function signature is never the same between a @nogc and uses-gc function.

On Tuesday, 28 May 2019 at 21:41:28 UTC, Walter Bright wrote:
> On 5/28/2019 2:12 PM, Jonathan Marler wrote:
>> turtles all the way down.
>
> Again, it is not that simple. Call graphs have cycles in them, they are not acyclic. Furthermore, since you suggested different code be instantiated based on inferred attributes, you have a FAR FAR more complex problem to resolve, since the graph connections change at every decision point.

I read your response again and I think there's another piece you might be missing.

You are correct that call graphs are not acyclic, however, the inference of attributes only applies to templated-functions, not regular functions.  So we don't need to walk the entire graph to determine whether or not a template is allowed to use the GC, you only need to trace each template to it's nearest non-template function.  Of course, this is just the theory, in practice it's just propagated as an implicit template parameter, a feature which is probably worth looking into and discussing on its own.

On Tuesday, 28 May 2019 at 21:53:13 UTC, Manu wrote:
> On Tue, May 28, 2019 at 9:10 AM Andrei Alexandrescu via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>>
>> int fun(int) pure;
>> int fun(int);
>>
>> pure int gun(int x)
>> {
>>     return fun(x);
>> }
>>
>> This doesn't work, but on the face of it it's not ambiguous - the second overload of fun() would not compile anyway.
>>
>> I was wondering whether allowing overloading on attributes in general would be a good idea. I suspect templates and attribute deduction make that difficult.
>
> I have wanted to overload on nothrow-ness before.

Yeah I could see some nice ways to select an implementation based on nothrow.


struct CannotFail { bool failed() { return false; } }
struct CanFail { bool _failed; bool failed() { return _failed; } }


auto foo(bool mustBeNothrow)()
{
    static if (mustBeNothrow)
    {
        // logic ...
        return CanFail(true); // or CanFail(false);
    }
    else
    {
        if (foo!true().failed)
            throw new Exception("an exception");
        return CannotFail();
    }
}

Now you can call foo from nothrow code or code that can throw.  If the return value follows the same api in both cases, you can implement something like.

if (foo.failed)
{
    // do something
    // note: if this block can throw, then foo.failed will get reduced to "false"
    //       so this whole block should be removed
}

On Tuesday, 28 May 2019 at 20:26:50 UTC, Walter Bright wrote:
> On 5/28/2019 12:49 PM, Jonathan Marler wrote:
>> You're right it's undecidable inside the function, but I think it's decidable if you check it at the call site.
>
> Yet the call site may also be doing attribute inference.
>
> Think of a graph with nodes in it, all interconnected with arbitrary edges, including cycles, and you have to find a set of attributes that satisfy each of the edges in it, when adding any attribute changes the topology of the graph.
>
> Even if there is an algorithm which can solve this, and I don't have a PhD in graph theory and have no idea if there is one or not:

http://dev.stephendiehl.com/fun/006_hindley_milner.html ? And the so called Algorithm W. I'm nowhere close to understanding how it seems to work though.

Swift uses an altered version: https://github.com/apple/swift/blob/master/docs/TypeChecker.rst

I assume the solver magic is in here: https://github.com/apple/swift/blob/master/lib/Sema/CSSolver.cpp

Rust used to use it but changed: http://smallcultfollowing.com/babysteps/blog/2014/07/09/an-experimental-new-type-inference-scheme-for-rust/

Though rust treats functions with different return types as the same definition and gives you an error.

The thing you said about overloading on return types made me go and check around a bit. I already knew that swift does this at least. So I guess it isn't ambiguous since it's been implemented. But maybe it has something to do with the type system implementation they use?

Cheers,
- Ali

>
> 1. there may be N solutions - which one is picked?
> 2. how do you explain to the user why?
> 3. how do you explain to the user when N is zero?
> 4. the combinatorics of this may mean it takes essentially infinite time
> 5. I have a hard enough time implementing/debugging the current bottom-up method
> 6. I've spent years dealing with problems with forward references, when there are cycles in the reference graph and incomplete types. Your proposal makes that infinitely worse.
>
> Like I said, it looks workable for trivial boundary cases, but that isn't how things work when people start using such a feature.
>
> So, no. Hell no :-)

> @nogc attributes are often inferred. Such constructs would make it undecidable.

I doubt if nogc is needed to D.
- it takes resources attempts to rewrite phobos/compiler for two different worlds.
- we have good alternatives for that case: C++, rust, Go, Swift, ObjC..
- u can create almost same (x)strings, same int[]|double[]|real[], same maps/assoc.arrays with simple types(that (are|contains) no refs) through refcount.
even slices can be rewritten that do addref/release for refs-containers - slice { ptrToContainer, index, length }.
code can be same in text representation but incompatible at binary/obj - u cannot mix slices that point to GC-heap and using addref.
BUT when include types with refs fields, when u have MOAO, when field can be Object obj.. well, compatibility is finish here - u should use refcount with cycling-breaker, u should use weakptr. it will be not D, it will be Swift/ObjC with "D"-frontend that need another separate RT lets say DiNoGC.
why u want to do from D another Swift or C++ or rust? coz 0.1% lovers of bare metal want D for bare metal? but programmers for bare metal are 0.1% from all programmers and we have 0.0001%. we have totally 20kg of one programmer from 15k D-programmers (I threw dice) for whom u working, others use c++/rust/go.
u can continue improve D/C++ Calypso https://github.com/Syniurge/Calypso remove GC from it and .. and u'll get strange C++ that knows 2 persons only.
I can understand such job if no alternatives, somebody should be first, but we have alternatives with full RT already which grew up decades with a multimillion community for each alternative.
D is good and unlike to others coz it have GC and it very close to metal(can do sse/assembler with high order functions) in one bottle (lets leave metaprogramming, UFCS, CTFE for ads slogans).
u can say "without GC we can run D for WASM, for some hardware/arduino/raspberry". GC will appear in WASM. do u have RT for WASMwGC?

ok, lets say another:
how many people D-community will loose if will be declared "people, from today we finish works on nogc"?
probably.. two men?
D is good compiler, they cannot use strings, arrays, lambdas, well they can write own STL without GC.
but they cannot use classes with polymorphism.
with some allocator only.
ok, lets write such allocator that supports some refcount and weakptr and again need another slices(with 3 fields).
what to do with lambdas? same allocator too!
imo such an allocator is very similar to GC.
omg, we did cycle/loop to best DiNoGC and we are back to complicated version of slises, arrays/strings and classes and.. GC! again fking GC! that named aw/some allocator. ohh, no!).
well, 2 men that want D on raspberry, I tell u and u will be grateful to me, go now to C++/Swift/Go, no need to cherish wet dreams about DiNoGC, u will get better world there, not with some crutches named "C++ without classes/D with structs/strange SwifD"
Hallelujah!

On 5/28/2019 3:12 PM, Jonathan Marler wrote:
> You are correct that call graphs are not acyclic, however, the inference of attributes only applies to templated-functions, not regular functions.  So we don't need to walk the entire graph to determine whether or not a template is allowed to use the GC, you only need to trace each template to it's nearest non-template function.
Your algorithm will have to work for the worst case, which is all template code. This is hardly unreasonable, as Phobos is nearly entirely templates, with cyclical expansions. Worse, it's not just attribute inference, you proposed different code paths for different attributes, meaning the graph changes, too.

It's a combinatorial explosion.

On Wednesday, 29 May 2019 at 01:14:04 UTC, Walter Bright wrote:
> On 5/28/2019 3:12 PM, Jonathan Marler wrote:
>> You are correct that call graphs are not acyclic, however, the inference of attributes only applies to templated-functions, not regular functions.  So we don't need to walk the entire graph to determine whether or not a template is allowed to use the GC, you only need to trace each template to it's nearest non-template function.
> Your algorithm will have to work for the worst case, which is all template code. This is hardly unreasonable, as Phobos is nearly entirely templates, with cyclical expansions. Worse, it's not just attribute inference, you proposed different code paths for different attributes, meaning the graph changes, too.
>
> It's a combinatorial explosion.

Well, I didn't propose an algorithm.  I was just providing a visual aid to your graph analogy. My suggesion has nothing to do with attribute inference on templates.  If it did then you are completely right that this would be a combinatorial explosion.  The idea is actually pretty "dumb" at its core.  What's the simplest way to pass this information to a template?  Just add a template parameter.

foo(bool nogc, bool nothrow, bool pure,...)()
{
    // logic to do something different based on template parameters
}

Then we need a way infer these attributes when we aren't inside a template. You can do this today with things like:

foo!(__traits(compiles, new Object), __traits(compiles, throw new Object), ...)();

This function call is long, but the point of it is that this same call will pass the correct information based on whether the surrounding scope is nogc and/or nothrow. It infers the attributes before instantiating the template and passes the results to it.  But keep in mind, it is not inferring attributes for the template, it is only passing information about the caller to the template which it may or may not use.

But I think everyone can immediately see the problem with this.  We can't add these parameters to every single template, and then add these __traits to every single template instantiation. There would be more boiler-plate than actual code!

So came the idea of "implicit template parameters".  The idea would be that any template could access a set of implicit variables to customize behavior.  And to prevent an exponential explosion of template instances, you would only consider implicit template parameters when they are used, i.e.

template foo()
{
    static if (__traits(requiresNothrow))
        auto foo() nothrow { ... }
    else
        auto foo() { ... }
}

void bar1() { foo(); }
void bar2() nothrow { foo(); }

When the compiler sees the `requiresNoThrow` trait being used inside a template, it notes that it is using one of the known implicit template parameters, meaning that it will be instantiated differently when the implicit "requiresNothrow" template parameter changes, just like it would if it was a normal template parameter.

So in this example, the two calls to foo in bar1 and bar2 actually instantiate 2 versions of foo, even though they have the same "explicit template arguments", they have different "implicit template arguments".

To understand how this works, note that implicit and explicit template parameters work the same way.  So it would function just as if you had done this:

template foo(bool nothrow)
{
    static if (nothrow)
        auto foo() nothrow { ... }
    else
        auto foo() { ... }
}

void bar1()         { foo!(__traits(compiles, new Object))(); }
void bar2() nothrow { foo!(__traits(compiles, new Object))(); }

It's just that now you don't need the boilerplate.

Is it a good idea?  I don't know, but I think it's worth some thought.