www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Koenig lookup in D?

reply "monarch_dodra" <monarchdodra gmail.com> writes:
Koenig lookup in C++ ( also known as
http://en.wikipedia.org/wiki/Argument-dependent_name_lookup ), is
a mechanism that alows functions (in particular templates) to
call a function that operates on an object of a specific
namespace, without having to qualify the namespace of the
function.

The root reason for this mechanism, is that it allows writing
templated functions that can operate on objects from any
namespace.

For example:

//----
namespace foo
{
      struct A{};
      void do_it(A);
}
namespace bar
{
      struct A{};
      void do_it(A);
}

template <typename T>
void doer(T t)
{
      do_it(t); //[1]
}

int main()
{
      foo::A fa;
      bar::A ba;
      doer(fa); //OK!
      doer(ba); //OK!
}
//----

In this example, the template doer is able to call "do_it"
without qualifying, which allows it to compile. This is *key* in
allowing templates in C++ to operate on function from any
namespace.

This is very important for working with "meta interfaces". If any
body here has used the boost graph library, you'd know you can do
some real cool things with this: BGL defines *algorithms*. You
define the objects and their corresponding functions. Pass your
*object* to the algorithm, and *it* will find your functions.

----------------

In D, this might not seem necessary, since you don't *need* to
qualify function calls, if they uniquely resolve. On the other
hand, with D's anti hijack rules, *all* functions must be know
*at* the call site. What this basically means is that while
Koenig lookup is not "needed" per se, it doesn't work either.

Here is an example, at its simplest: I'd like to define a range,
but for implementation reasons, I'll make front/popFront/empty as
non-members. This is supposed to work, right? After all, that's
what UFCS is for. Let's try it!

//--
module a;

struct A
{}

 property bool empty(A)
{
      return false;
}

 property int front(A)
{
      return 0;
}

void popFront(A)
{}
//--
import a;
void main()
{
      A a;
      bool b = a.empty; //OK
      int  f = a.front; //OK
      a.popFront();     //OK
}
//--

Sweet deal, right? We just created an awesome new range! Did we
though? What happens if we call "assert(isInputRange!R)"? I'll
tell you what happens: An Error!

But why? Simple! std.range.isInputRange is not aware of the
functions `a.front`/`a.popFront`/`a.empty`. As such, the code we
wrote and compiles in main *doesn't* compile in std.range.

What this means is that it turns out our awesome new range,
wasn't really a range :( That's -1 point for extendability.

------------------------

Does this seem normal to you? It doesn't to me. Arguably, we've
never had the need for this, but at the same time, we don't have
any kicks ass BGL-like extend-able library either.

I think that D's non-hijack rules are pretty sweet, but I also
think that D should apply Koenig's rules: If a template is
dependent on a parameter from a particular module (say "a"), then
the functions inside that module should also be taken into
account when building the template instance. It would be
*partial* hijack in the sense that you can only hijack the
templates that operate on *your* types anyways, but in no case
change the behavior of that of others'.

This would, of course, be a MASSIVE change, so it would require
DIP and all that jazz, but I wouldn't mind starting with a little
bit of discussion on the issue, see if anybody has workarounds to
share, etc...
Aug 27 2013
next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 8/27/2013 12:45 AM, monarch_dodra wrote:
 The root reason for this mechanism, is that it allows writing
 templated functions that can operate on objects from any
 namespace.

I believe the root reason was so that operator overloads would work when the rvalue was the class type. (In C++ you have to write non-member functions to handle those cases.) D solves that via other mechanisms, so Koenig lookup is not necessary.
Aug 27 2013
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 27 August 2013 at 07:54:06 UTC, Walter Bright wrote:
 On 8/27/2013 12:45 AM, monarch_dodra wrote:
 The root reason for this mechanism, is that it allows writing
 templated functions that can operate on objects from any
 namespace.

I believe the root reason was so that operator overloads would work when the rvalue was the class type. (In C++ you have to write non-member functions to handle those cases.) D solves that via other mechanisms, so Koenig lookup is not necessary.

D solves the "operator overloads" mechanism in other ways, yes. But it does not provide a mechanism to resolve function calls that are defined by the caller, to operate on the passed in type. At least, none that I know know of.
Aug 27 2013
prev sibling next sibling parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Tuesday, 27 August 2013 at 07:54:06 UTC, Walter Bright wrote:
 On 8/27/2013 12:45 AM, monarch_dodra wrote:
 The root reason for this mechanism, is that it allows writing
 templated functions that can operate on objects from any
 namespace.

I believe the root reason was so that operator overloads would work when the rvalue was the class type. (In C++ you have to write non-member functions to handle those cases.) D solves that via other mechanisms, so Koenig lookup is not necessary.

The only reason slices work as ranges in D is because std.range imports std.array. As in the example in the original post, for slices, front, popFront, and empty are free functions, so std.range cannot find them without importing std.array directly. As a result, slices are the ONLY ranges that can do this, which is a bit hacky. I'm not sure what the resolution of this is. Anti-hijacking is import, and ADL can get quite messy, but ADL is also important. We may just have to ensure that all template interfaces are satisfied via member functions.
Aug 27 2013
prev sibling next sibling parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Tuesday, 27 August 2013 at 08:37:24 UTC, Peter Alexander wrote:
 I'm not sure what the resolution of this is. Anti-hijacking is 
 import

*important :)
Aug 27 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 27 August 2013 at 08:39:52 UTC, Peter Alexander wrote:
 On Tuesday, 27 August 2013 at 08:37:24 UTC, Peter Alexander 
 wrote:
 I'm not sure what the resolution of this is. Anti-hijacking is 
 import

*important :)

We should be able to inject import into templates.
Aug 27 2013
prev sibling next sibling parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Tuesday, 27 August 2013 at 07:45:14 UTC, monarch_dodra wrote:
 I think that D's non-hijack rules are pretty sweet, but I also
 think that D should apply Koenig's rules: If a template is
 dependent on a parameter from a particular module (say "a"), 
 then
 the functions inside that module should also be taken into
 account when building the template instance. It would be
 *partial* hijack in the sense that you can only hijack the
 templates that operate on *your* types anyways, but in no case
 change the behavior of that of others'.

That still makes hijacking a real issue though. It limits the hijacking to template functions, but it's still there. What if ADL was only used with UFCS on an instance of a template type? e.g. void foo(T)(T t) { import std.stdio; writeln(t); // always std.stdio t.writeln(); // used ADL, maybe std.stdio, but can be specialised by T "foo".writeln(); // always std.stdio } This kind of makes sense, because T could implement writeln() as a member function anyway, so by using UFCS you are voluntarily opening yourself up to hijacking.
Aug 27 2013
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 27 August 2013 at 10:00:50 UTC, Peter Alexander wrote:
 On Tuesday, 27 August 2013 at 07:45:14 UTC, monarch_dodra wrote:
 I think that D's non-hijack rules are pretty sweet, but I also
 think that D should apply Koenig's rules: If a template is
 dependent on a parameter from a particular module (say "a"), 
 then
 the functions inside that module should also be taken into
 account when building the template instance. It would be
 *partial* hijack in the sense that you can only hijack the
 templates that operate on *your* types anyways, but in no case
 change the behavior of that of others'.

That still makes hijacking a real issue though. It limits the hijacking to template functions, but it's still there. What if ADL was only used with UFCS on an instance of a template type? e.g. void foo(T)(T t) { import std.stdio; writeln(t); // always std.stdio t.writeln(); // used ADL, maybe std.stdio, but can be specialised by T "foo".writeln(); // always std.stdio } This kind of makes sense, because T could implement writeln() as a member function anyway, so by using UFCS you are voluntarily opening yourself up to hijacking.

That sounds relativelly safe. An even safer approach might be: Allow an ADL call only if there are no local symbols that match. This way, you could argue that there is no hijacking, if there was no matching call.
Aug 27 2013
prev sibling next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
27-Aug-2013 11:45, monarch_dodra пишет:
 Koenig lookup in C++ ( also known as
 http://en.wikipedia.org/wiki/Argument-dependent_name_lookup ), is
 a mechanism that alows functions (in particular templates) to
 call a function that operates on an object of a specific
 namespace, without having to qualify the namespace  ...

ADL has a "bug of surprise" written all over it. It doesn't work all that well in C++ to being with. Even after all these years: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2103.pdf -- Dmitry Olshansky
Aug 27 2013
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
27-Aug-2013 17:33, Dmitry Olshansky пишет:
 27-Aug-2013 11:45, monarch_dodra пишет:
 Koenig lookup in C++ ( also known as
 http://en.wikipedia.org/wiki/Argument-dependent_name_lookup ), is
 a mechanism that alows functions (in particular templates) to
 call a function that operates on an object of a specific
 namespace, without having to qualify the namespace  ...

ADL has a "bug of surprise" written all over it.

*Bag.. though hardly a typo )
 It doesn't work all
 that well in C++ to being with. Even after all these years:
 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2103.pdf

-- Dmitry Olshansky
Aug 27 2013
parent Walter Bright <newshound2 digitalmars.com> writes:
On 8/27/2013 6:35 AM, Dmitry Olshansky wrote:
 27-Aug-2013 17:33, Dmitry Olshansky пишет:
 ADL has a "bug of surprise" written all over it.

*Bag.. though hardly a typo )

I think you've coined a new term!
Aug 27 2013
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 27 August 2013 at 13:35:36 UTC, Dmitry Olshansky 
wrote:
 27-Aug-2013 17:33, Dmitry Olshansky пишет:
 27-Aug-2013 11:45, monarch_dodra пишет:
 Koenig lookup in C++ ( also known as
 http://en.wikipedia.org/wiki/Argument-dependent_name_lookup 
 ), is
 a mechanism that alows functions (in particular templates) to
 call a function that operates on an object of a specific
 namespace, without having to qualify the namespace  ...

ADL has a "bug of surprise" written all over it.

*Bag.. though hardly a typo )
 It doesn't work all
 that well in C++ to being with. Even after all these years:
 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2103.pdf


Well, I don't expect we'd actually change the way things are done *now*, and for all the "bugs" ADL had, it also allowed for some very powerful and *extendable* generic programming. D has a way of doing things that C++ can, but usually, with a twist that makes it safer and/or more powerful, or with some very well thought mechanics. In this case, it really feels as if the whole a host of functionality is just both supported, *and* with no workarounds :/ If we don't have ADL I kind of like the notion of "forced import infection" though...
Aug 27 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Tuesday, 27 August 2013 at 13:51:51 UTC, monarch_dodra wrote:
 D has a way of doing things that C++ can, but usually, with a 
 twist that makes it safer and/or more powerful, or with some 
 very well thought mechanics.

 In this case, it really feels as if the whole a host of 
 functionality is just both supported, *and* with no workarounds 
 :/

 If we don't have ADL I kind of like the notion of "forced 
 import infection" though...

What do you mean by that ? Being able to force feed an import in a template instantiation ? That'd be great, because of UFCS.
Aug 27 2013
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 27 August 2013 at 15:10:45 UTC, deadalnix wrote:
 On Tuesday, 27 August 2013 at 13:51:51 UTC, monarch_dodra wrote:
 D has a way of doing things that C++ can, but usually, with a 
 twist that makes it safer and/or more powerful, or with some 
 very well thought mechanics.

 In this case, it really feels as if the whole a host of 
 functionality is just both supported, *and* with no 
 workarounds :/

 If we don't have ADL I kind of like the notion of "forced 
 import infection" though...

What do you mean by that ? Being able to force feed an import in a template instantiation ? That'd be great, because of UFCS.

I'm unsure ^^ you brought it up: "We should be able to inject import into templates." Did you have anything specific in mind?
Aug 27 2013
prev sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Tuesday, 27 August 2013 at 16:59:14 UTC, monarch_dodra wrote:
 On Tuesday, 27 August 2013 at 15:10:45 UTC, deadalnix wrote:
 On Tuesday, 27 August 2013 at 13:51:51 UTC, monarch_dodra 
 wrote:
 D has a way of doing things that C++ can, but usually, with a 
 twist that makes it safer and/or more powerful, or with some 
 very well thought mechanics.

 In this case, it really feels as if the whole a host of 
 functionality is just both supported, *and* with no 
 workarounds :/

 If we don't have ADL I kind of like the notion of "forced 
 import infection" though...

What do you mean by that ? Being able to force feed an import in a template instantiation ? That'd be great, because of UFCS.

I'm unsure ^^ you brought it up: "We should be able to inject import into templates." Did you have anything specific in mind?

We can already do this (sortof) by passing some imports in a string/mixin template to the template. Obviously you have to write the template with this in mind though, which isn't ideal. Also you'd have to check for duplicate imports.
Aug 27 2013