Re: [OpenMethod] review starts on 28th of April

From: Yannick Le Goc (ylegoc_at_[hidden])
Date: 2025-05-07 01:30:56

 Hello everybody,

Once again thank you Jean-Louis for your work and implication in your
different multiple dispatch related projects.
Here is my review:

* Introduction

As the author mentions it in the introduction of the documentation of the
OpenMethod project, the library implements
the features described in the N2216 paper with extra elements. The N2216
paper describes an extension to the C++
language with the virtual extra keyword and new rules of dispatch for
functions identified as multi-methods by the compiler.

* What is your evaluation of the design?

OpenMethod is the adaptation of a language based feature into a library.
Efforts were made to be as close as possible
to the proposal: open-methods are non-member functions and the virtual
keyword is replaced with a virtual_ptr or virtual_
class template acting as identifier for the "virtual" parameters of an
open-method. However there are some differences:
N2216 proposes to only add the virtual qualifier to a parameter of function
and let the compiler decide on what is an
open-method and what is an overrider of that open-method, allowing to have
a minimal approach.In the OpenMethod
project, it is necessary to first define a "guide" function which is not a
proper function definition but an open-method
declaration. Then the overriders can be defined as normal functions with a
body. The code is using extensively class
templates to implement the open-methods but macros are necessary to improve
the readibilty. The YOMM2 project
shows that it is possible to get rid of these macros with a compiler
supporting C++17.

The initial design proposed in N2216 was to provide the most static
implementation as possible of open-methods.
However I think this has too many limitations.

Indeed implementing multi-methods could have been done differently. This
could have been an STL feature proposing
a std::multi_function class extending the concept of std::function. As
polymorphism is implemented in the core C++
language, it seemed natural to want to extend it to another language
feature but adding more dimensions to the type-based
dispatch introduces difficulties (ambiguities, memory size, visibility). My
opinion is that a full library design is a better choice
and can provide more flexibility. The OpenMethod design demonstrates that
the language feature is maybe not a good
approach. Indeed it seemed mandatory for the author to add facets to the
library. Transposed into the original language
based feature, this would have been compiler options. Then we could rethink
the design of C++ multi-methods as a full
library feature.

To conclude, I think that the author made good design choices with all the
constraints he had to respect but I think that a
full library-based approach would be better.

* What is your evaluation of the implementation?

I made some tests in the
https://github.com/da-project/boost-open-method-test/ project.
The tests TestConst, TestNonConst, TestCovariance showed that types passed
to virtual_ptr can be const and covariant
return types can be used. Concerning the API, TestNoMacro showed that to
get rid of the macros, some useless names
have to be defined. The test also showed that it is possible to explicitly
call a specific overrider rather than rely on the choice
of the library by calling next(). It means that the next() function could
be removed.

One major issue highlighthed in N2216 is the potential ambiguities in the
multi-methods resolution. They can happen with
multiple inheritance in single dispatch and of course multiple dispatch. In
case of a single dispatch without multiple inheritance,
TestNoPerfectOverrider1 showed that the library selects the expected
overrider which is the most specialized one. However
in case of virtual inheritance and single dispatch,
TestNoPerfectOverrider1Virtual showed that the selected overrider was
different by simply changing the order of definition of the overriders. In
case of double dispatch, same behavior was shown in
TestNoPerfectOverrider2. Overriders can be defined in different compilation
units which for runtime reasons could be called in
a random order meaning an undefined behavior of the program, which is not
acceptable. This can be a tricky subject, but in my
opinion, the selection of an overrider when there is not a perfect match
should be clear to the programmer (documented as
well). In any case, a facet should be provided to always throw an exception
when there is an ambiguity.

I did not run performance tests but the documentation shows that good
performances have been obtained thanks to dedicated
internal data structures.

The smart pointers unique_virtual_ptr are not really interesting in my
opinion since they introduce a dependency to the library
in the data objects which is contrary to the idea of non-intrusive
open-methods.

* What is your evaluation of the documentation?

There should be more documentation on the "normal" use even if some parts
can seem obvious. For instance, there could be
examples of const types as well covariant return types. There should
definitely be a section concerning the resolution of
ambiguities. The documentation should be split in multiple pages, but I
think that this is usual in Boost.

* What is your evaluation of the potential usefulness of the library? Do
you already use it in industry?

The library implements an experimental feature but in simple cases, the
library should be usable in industry.

* Did you try to use the library? With which compiler(s)? Did you have any
problems?

I used gcc 11.4.0. The tests compiled well. However in Eclipse CDT 11.6.1,
the macro BOOST_OPENMETHOD_OVERRIDE
generates an error in the editor.

* How much effort did you put into your evaluation?

I tried the library on some specific tests and read the documentation.

* Are you knowledgeable about the problem domain?

I quickly present myself because it is linked to the subject and I may not
be fully objective in my review.

In my first job at the INRIA Montbonnot, a computer science research
center, I had to develop algorithms on C++ 3D
graph scenes implemented with OOP. I rapidly realized that I needed a tool
to implement process functions outside the class
hierarchy. Moreover depending on the algorithms, the tree traversal
strategy may vary (DFS or BFS). All that lead me to a specialized
implementation of open-methods limited to one dimension. Then on my free
time I worked on a generalized version of open-methods
or multi-methods and after reading the N2216 proposed implementation of
which OpenMethod is mainly inspired, I wrote a peer-reviewed
article "EVL: A framework for multi-methods in C++" (1) in which I expose
my prototype and also compare it to the N2216's one.
What is funny is that, I also cited YOMM11 in the article. At that time I
also realized that the Boost community was not ready for such
a tool because I remember Jean-Louis Leroy having posted an email on the
YOMM11 implementation but nobody answered.
Then I implemented a Java version (2) which was much easier than the C++
one.

My evaluation is ACCEPT but the ambiguities should be treated better.

To go further, I think that multiple dispatch belongs to the C++ dynamic
language paradigm and must be assumed. It is even a
step further in the dynamic language paradigm. In my opinion, in the
context of multi-methods, want to have everything solved at
compile-time is a mistake. That also means that using multi-methods implies
possible exceptions at runtime. But C++ is a rich multi-paradigm
language and one can choose to not use its dynamic paradigm implementation
i.e. not use multi-methods. Multi-methods remain an
experimental subject and I think that it is interesting to test the
concept, which at the end may reveal not useful. But that is an interesting
debate.

(1)
https://www.sciencedirect.com/science/article/pii/S0167642314003360#bbr0070
(2) https://da-project.github.io/evl/

* More information

If you are interested in multi-methods, I encourage you to read my article
(1) and also have a look at my Java implementation (2) if you
are not allergic to Java. I took the time to provide a list of examples (
https://da-project.github.io/evl/docs/examples.html), including the
implementation of some design patterns using multi-methods. I give examples
of multiple dispatch by for instance adding a simple state
object. I also explain my generalization of multiple dispatch (
https://da-project.github.io/evl/docs/theory.html).

A summary of the main differences between N2216 and EVL:
- Generalization of the multiple dispatch mechanism based on the comparison
of tuples of distance. It aims to provide an abstraction able
 to solve ambiguities at a higher level.
- Cache strategy rather than static dispatch table to control memory
footprint and avoid to have entries that will never be called and solve
ambiguities that will never arise.
- Multi-methods are objects so that their control is easier (visibility,
configuration, etc.).
My C++ implementation required a rough reflection implementation to be able
to provide an inheritance graph calculated from the
dynamic_cast operator. It is presented in the article (1).

Best regards,
Yannick

On Sun, Apr 27, 2025 at 3:15 PM Дмитрий Архипов via Boost <
boost_at_[hidden]> wrote:

> Dear Boost community. The peer review of the proposed Boost.OpenMethod will
> start on 28th of April and continue until May 7th. OpenMethods implements
> open
> methods in C++. Those are "virtual functions" defined outside of classes.
> They
> allow avoiding god classes, and visitors and provide a solution to the
> Expression Problem, and the banana-gorilla-jungle problem. They also
> support
> multiple dispatch. This library implements most of Stroustrup's
> multimethods
> proposal, with some new features, like customization points and
> inter-operability with smart pointers. And despite all that open-method
> calls
> are fast - on par with native virtual functions.
>
> You can find the source code of the library at
> https://github.com/jll63/Boost.OpenMethod/tree/master and read the
> documentation at https://jll63.github.io/Boost.OpenMethod/. The library is
> header-only and thus it is fairly easy to try it out. In addition,
> Christian
> Mazakas (of the C++ Alliance) has added the candidate library to his vcpkg
> repository (https://github.com/cmazakas/vcpkg-registry-test). The library
> is
> also available in Compiler Explorer under the name YOMM2.
>
> As the library is not domain-specific, everyone is very welcome to
> contribute a
> review either by sending it to the Boost mailing list, or me personally. In
> your review please state whether you recommend to reject or accept the
> library
> into Boost, and whether you suggest any conditions for acceptance. Other
> questions you might want to answer in your review are:
>
> * What is your evaluation of the design?
> * What is your evaluation of the implementation?
> * What is your evaluation of the documentation?
> * What is your evaluation of the potential usefulness of the library?
> * Did you try to use the library? With what compiler? Did you have any
> problems?
> * How much effort did you put into your evaluation? A glance? A quick
> reading? In-depth study?
> * Are you knowledgeable about the problems tackled by the library?
>
> Thanks in advance for your time and effort!
>
> Dmitry Arkhipov, Staff Engineer at The C++ Alliance.
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>