On 9/3/16 10:01 AM, Tobias Müller wrote:
> On Friday, 2 September 2016 at 23:51:35 UTC, Manu wrote:
>> This pattern seems to bite me every direction I turn when trying to
>> write range or algorithm style code. C++ has ADL, and ADL works. I've
>> never thought about this problem in C++, or had any problems with ADL.
>
> IMO the root of this problem is that templates are *duck typed*. All
> those problems wouldn't even exist with concepts/traits/typeclasses
> (done right).
> ADL is only an ugly hack.
>
> And with "Design by Introspection" it only gets worse: If an optional
> operation exists, but is not found because of unexpected problems like
> these, it still compiles but you only get limited functionality or bad
> performance.

What problems are you referring to? -- Andrei

On Saturday, 3 September 2016 at 10:56:20 UTC, Tobias M wrote:
> On Saturday, 3 September 2016 at 10:33:22 UTC, Walter Bright wrote:
>> I don't think it is a template issue. It's a name lookup issue. There's LINQ in C#, for example.
>
> I think it is.
>
> The problem is lookup of dependent symbols (see C++ two phase lookup). Without real templates, all lookup can be done at definition time.
> I'm not very familiar with LINQ, but generally C# uses uses interfaces as constraints on generics, similar to traits/type classes. Lookup is then done once, considering only the interfaces, not for each the concrete type.

No, LINQ doesn't work because of interfaces, but because of extension methods (C#'s variant of UFCS). The IEnumerable<T> interface defines only a single method. All the useful functionality is implemented as extension methods which are only available if the user specifically imports the namespace in which where they're defined (just like D's ranges and range primitive implementations for arrays). Those extension methods are used as a fallback, similarly to UFCS in D: every type can override the extension methods by implementing the method itself. Also more inner namespaces (more closer to the method invocation) override more outer namespaces. For more info see:

1) https://github.com/ljw1004/csharpspec/blob/gh-pages/expressions.md#member-lookup Member Lookup
2) https://github.com/ljw1004/csharpspec/blob/gh-pages/expressions.md#member-access Member access and
3) https://github.com/ljw1004/csharpspec/blob/gh-pages/expressions.md#extension-method-invocations Extension method invocations

On 9/3/16 1:51 AM, Manu via Digitalmars-d wrote:
> I've
> never thought about this problem in C++, or had any problems with ADL.

How do you swap two objects of a generic type that may or may not define its own swap? -- Andrei

On 9/3/16 3:09 AM, Walter Bright wrote:
[snip]

What would be really nice is to allow ADL easily and without fuss when needed. On Manu's example:

module bob;
struct S {}
void f(S s);

module joe;
struct T {}
void f(T t);

module myalgorithm;
void test(T)(T t)
{
  mixin(adl!(T, "f"));
  f(t);
}

So adl!(T, "f") expands to an import of f from T's module if it defines a function f, or nothing if it doesn't.

Generally I agree that there's more upside to not introducing ADL for D.


Andrei

On 9/3/16 12:03 PM, Timon Gehr wrote:
> On 03.09.2016 11:37, Manu via Digitalmars-d wrote:
>> On 3 September 2016 at 18:56, Walter Bright via Digitalmars-d
>> <digitalmars-d@puremagic.com> wrote:
>>> On 9/3/2016 1:37 AM, Walter Bright wrote:
>>>>
>>>> I thought #4 in particular was rather cool, I plan to use it as an
>>>> example.
>>>
>>>
>>> https://github.com/dlang/phobos/pull/4762
>>
>> Complexity ramps up further if there are N arguments to the algorithm.
>> It needs to search each of the arguments modules.
>>
>
> template adl(string fun){ /* TODO */ }
>
> adl!"foo"(S.init,T.init);

Nice, yah, that kinds of stuff. -- Andrei

On 9/3/16 12:14 PM, Timon Gehr wrote:
> On 03.09.2016 10:37, Walter Bright wrote:
>> None of the algorithms used in std.algorithm or elsewhere in Phobos have
>> this particular issue.
>
> Yes they do. It is not possible to implement the range functions as
> non-members.

Yah, but I don't see this as an issue. The non-members would need to be in the same module even with ADL, so it's just a clerical matter. -- Andrei

On 9/3/16 1:24 PM, Walter Bright wrote:
> On 9/3/2016 3:12 AM, Walter Bright wrote:
>> If you are still determined to use it, you can use:
>>
>>    __traits(compiles, ...)
>>
>> like you would SFINAE in C++ to select which of the modules from the
>> argument
>> types selects a function that compiles.
>
> Eh, I realized it's simpler than that. Based on the code I already
> presented, each argument can be used to generate an import for its
> corresponding version of the function. Then, overloading rules apply and
> it works. Something like:
>
> Something like:
>
> void foo(T,U)(T t, U u)
> {
>     alias func = ModuleOf!T.func;
>     alias func = ModuleOf!U.func;
>
>     func(t, u);
> }

This only works with the respective modules do define `func`. We need something that conditionally plants the symbol depending on whether the module defines it or not. -- Andrei

On 2016-09-03 13:16, Walter Bright wrote:

>> It's mostly about how
>> templates specify what interface they require and how the requirements
>> are
>> satisfied by the caller. ADL is a workaround for the lack of a
>> convenient enough
>> such protocol in templates. Other approaches to generics solve this
>> particular
>> issue quite elegantly. (E.g. type classes implicitly pass along the
>> required
>> free-function functionality.) D's templates don't, this is why it is a
>> template
>> issue.
>>
>> By default, name lookup does not work in a way that would allow you to
>> actually
>> extend types using UFCS, and therefore none of Phobos works that way.
>
> Lambdas!

So, something like this:

module foo;

struct Foo {}
int front(Foo f);
void popFront(Foo f);
bool empty(Foo f);

module algo;

void algorithm(alias front, alias popFront, alias empty, T)(T t);

module user;

import foo;
import algo;

void main()
{
    Foo f;
    algorithm!(() => f.front, () => f.popFront(), () => f.empty)(f);
}

-- 
/Jacob Carlborg

On Saturday, 3 September 2016 at 10:33:22 UTC, Walter Bright wrote:
> On 9/3/2016 3:14 AM, Timon Gehr wrote:
>> On 03.09.2016 10:37, Walter Bright wrote:
>>> None of the algorithms used in std.algorithm or elsewhere in Phobos have
>>> this particular issue.
>>
>> Yes they do. It is not possible to implement the range functions as non-members.
>
> It's done for arrays via std.array.
>
>
>>> Nor have I seen ADL supported in any other
>>> language, despite many supporting generic algorithms.
>>
>> Which other such languages have templates like D or C++?
>
> I don't think it is a template issue. It's a name lookup issue. There's LINQ in C#, for example.

I agree that it's not a template issue. It's more of a modules vs namespaces issue. I think the lack of ADL is not a problem in C# because everyone can (and everyone does) extend an existing namespace, so most user's of LINQ algorithms just slap a `using System.Linq` on top of the file without caring in exactly which file the functionality they're using is coming from.

Personally I'm glad that D doesn't have ADL because ADL can make it very hard to find which overload is called.

On Saturday, 3 September 2016 at 10:11:05 UTC, Timon Gehr wrote:
>
> If ADL is done as a fallback, then it is only slower in those cases where it is either actually used, or __traits(compiles,...) is used to determine that some function overload does not exist.

True.
Still it does complicate the implementation.

AFAICS the point of ADL is importing function definitions automatically if they are referenced, thereby practically circumventing the guarantees imports give you.

In particular : "I will only import what is in that module, and I will only transitively import what is imported publicly by this module"

now it becomes : "I will import what is in that module, transitively import public imports, and maybe more if a function called from that module requires it."

Please do correct me if my interpretation is wrong.
I haven't heard of adl before this post.