Re: [boost] Provisional Boost.Generic and Boost.Auto_Function (concepts without concepts)

Subject: Re: [boost] Provisional Boost.Generic and Boost.Auto_Function (concepts without concepts)
From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2010-12-14 02:35:04

Hi Matt,

I apologize if this response took a while, I got buried into a few
things that needed my immediate attention and almost missed replying
to this email of yours. That said, please see some of my thoughts
in-lined below.

On Sun, Nov 14, 2010 at 6:15 AM, Matt Calabrese <rivorus_at_[hidden]> wrote:
> For those of you who were following the Boost.Auto_Function call for
> interest, this thread sort of spawned off of that.
>
> Boost.Generic (not a part of boost) is a C++0x library intended to replace
> BCCL as a way of specifying concepts and concept maps, and, when used in
> conjunction with Boost.Auto_Function (also not a part of boost, though it's
> in the sandbox and has online documentation at
> http://www.rivorus.com/auto_function ) as a way to get concept-based
> function template overloading. For anyone who followed the original thread,
> I'm happy to say that I'm just a few days away from being able to fully and
> automatically recognize standard library and user-defined iterator types,
> though I've had a [not so] surprising amount of compiler crashes and
> workarounds along the way. For an example of how concept mapping will look
> (revised from earlier versions as I've made much more progress with
> implementation), see http://codepaste.net/n47ocu And for an example of how
> this will be used by Boost.Auto_Function, see http://codepaste.net/1faj21 .
> At this point I'm not trying to do the equivalent of what would have been
> C++0x "scoped" concept maps, though at some point I may try to support them,
> but it would imply calling algorithms through macro invocations (yuck).
>

Interesting! So which compilers are you using to test your
implementation? Is this with MSVC or GCC?

> During development, I've come to some realizations that I'd like discussion
> about here, mostly concerning concept map lookup and ODR. Essentially, the
> way the library works is by assembling a compile-time list of concept maps
> piecewise throughout a translation unit for a given type or combination of
> types via a clever use of overload resolution that I talked about briefly in
> the BOOST_AUTO_FUNCTION call for interest thread. Underneath the hood, there
> is something that resembles tag-dispatching, however it is all done entirely
> within decltype. In short, the way the concept-based overloading works is
> that the macro used for specifying a function that dispatches based on
> concept maps generates something along the lines of this. The "magic" shown
> in comments is something I'm able to already do, as talked about in the
> other thread:
>
> /////
> template< class It >
> void foo( It&& it )
> {
> Â typedef decltype
> Â  Â  Â  Â  Â ( function_returning_type_with_a_nested_static_function
> Â  Â  Â  Â  Â  Â ( /* magical way to get a type that inherits from all concept
> tags */() )
> Â  Â  Â  Â  Â )
> Â  Â  Â  Â  Â fun_holder;
>
> Â fun_holder::impl( std::forward< It >( it ) );
> }
> /////
>
> Now, this is great, but I'm wondering what this means with respect to ODR.
> If the user is working with the algorithm "correctly", the typedef will
> resolve to the same type regardless of the translation unit, however, the
> "path" taken when inside of the decltype via overload resolution may vary
> depending on the translation unit when different, orthogonal concept maps
> are specified for the same type in one translation unit but not in the other
> (or if concept maps are specified in a different order I.E. via different
> #include orders). My question is, does this violate ODR in any meaningful
> sense? Since technically the typedefs should resolve to the same type in
> each translation unit, not including user error, is there a problem?
>

I don't see an obvious problem here in terms of ODR here because you
are using a template -- which by definition still gets instantiated
anyway across multiple translation units, and is not required to have
a single definition anyway. The only worrying thing is that if the
nested function invocation referred to has a static but non-extern
linkage, and thus will be defined in multiple translation units --
some compilers issue a diagnostic on this occurrence although I forget
if the standard requires that a diagnostic be emitted in cases where
you have nested static functions in templates. Maybe those who
actually know enough about the relevant sections of the standard can
chime in.

> The next question is much more devious and I have a feeling implies a
> blatant violation of ODR.
>
> Consider the following code, assuming "foo" does concept-based dispatching
> in a way similar to the above:
>
> /////
> foo( 5 );
>
> /* a concept map that specifies "int" models a concept that may affect
> dispatching */
>
> foo( 5 );
> /////
>
> With the definition of foo given above, what would effectively happen is
> that the second call to "foo" will not be able to dispatch based on the new
> concept map! The reason why is because both calls will use foo< int >, and
> since it was already instantiated once for int, that first definition will
> be used. Note that this problem technically even exists with traditional tag
> dispatch, though I wonder if there may be some sort of solution that is
> standard.
>

Note that your concept map is computed at "compile-time" right, and
should be in a globally accessible scope -- i.e. a template
specialization or a template class in a namespace -- right? Unless
you're able to create a concept map at runtime or call the foo
function outside of a function body, then I don't see how adding a new
concept_map might be an issue for ODR.

Of course unless you're talking about invocations of foo<...> on
multiple translation units where you have one translation unit already
defining the concept map and the others having a different set of
concept maps. In which case you will get around that by marking
foo<...> as an inline function, thus allowing multiple definitions
across translation units be acceptable. I'm not sure if that's what
you're looking for or asking, and if I'm not making sense please
enlighten me more as to what your concern actually is. ;)

> A hackish workaround I've come up for this is if we change the defintion of
> "foo" to be generated as the following:
>
> /////
> // Uses C++0x function template default arguments
> template< class It, class TagType = /* magical way to get a type that
> inherits from all concept tags */ >
> void foo( It&& it )
> {
> Â typedef decltype
> Â  Â  Â  Â  Â ( function_returning_type_with_a_nested_static_function
> Â  Â  Â  Â  Â  Â ( TagType() )
> Â  Â  Â  Â  Â )
> Â  Â  Â  Â  Â fun_holder;
>
> Â fun_holder::impl( std::forward< It >( it ) );
> }
> /////
>
> Going back to the example calling code, "foo" will now correctly dispatch
> differently if the intermediate concept map should affect concept-based
> dispatch. This might seem like a perfect solution, but now we are pretty
> much definitely violating ODR, since a function that calls "foo" in
> different translation units will very possibly see different TagTypes even
> though the overload resolution internal to "foo" would resolve the same.
>
> Am I clear on this problem and why I believe my solution only works if you
> don't consider ODR violations?
>

Like I already mentioned above, if
`function_returning_type_with_a_nested_static_function` is a template,
and the static function is defined in-line, I don't think you'll run
into ODR violations here. If you're worried of the foo function being
defined differently across multiple translation units, then that's
fine because that is the nature of templates AFAIK. ;)

> The final solution that I believe sidesteps all ODR violations would be if I
> force calls to such algorithms to be done via a macro. The macro would
> internally do the trick that is currently shown inside of the definition of
> "foo", only it would now do it at the caller's scope. If I decide to
> eventually try to support scoped concept maps I would be forced down such a
> route anyway, so my question ends up being at what point does the library
> cease being a convenience? Is it worth supporting concepts as accurately as
> possible, including the above desired behavior, if the calling code has to
> become:
>
> /////
> BOOST_GENERIC_CALL( (foo)( 5 ) );
>
> /* a concept map that specifies "int" models a concept that may affect
> dispatching */
>
> BOOST_GENERIC_CALL( (foo)( 5 ) );
> /////
>
> or, if you want a more practical example:
>
> /////
> BOOST_GENERIC_CALL( (advance)( vector_.begin(), 5 ) );
> /////
>
> This is a problem that I would prefer to be resolved sooner rather than
> later since I want to reduce code rewrites. Any feedback is greatly
> appreciated, especially if you have insight into these problems.
>
> I'll try to get Boost.Generic in its current, very limited form up on the
> sandbox and the docs online as soon as possible.
>

I don't like the idea with making function calls macro functions.
Unless I'm missing what you're saying above with ODR violations, I
don't see them at all, granted that templates in general are
instantiated per translation unit, and that you'll find ODR in cases
where you have statics defined in multiple TU's that either differ or
are exposed through a non-template class.

Maybe looking at how Phoenix gets around the ODR issue might help --
I've never found any problems with the way Phoenix actors have static
nested functions in templates, and I've never had compilers complain
of ODR in those cases either.

HTH

-- 
Dean Michael Berris
deanberris.com