C++ で多重ディスパッチをする方法と Julia ２

Question

前の質問は こちら です。文字数上限に達してしまったため、続きをここに記述します。

追記３：

色々理解が整理できたので質問し直します。C++ ではメンバ関数として仮想関数を実装すれば、例えば、次のように

#include <iostream>
#include <vector>
#include <memory>

struct Animal {
    virtual ~Animal() = 0;
    virtual void printlntype() {
        std::cout << "Animal" << std::endl;
    }
};
Animal::~Animal() {}

struct Dog final : Animal {
    void printlntype() override {
        std::cout << "Dog" << std::endl;
    }
};

struct Cat final : Animal {
    // void printlntype() override {
    //     std::cout << "Cat" << std::endl;
    // }
};

int main() {

    auto dog = Dog();
    auto cat = Cat();
    dog.printlntype();
    cat.printlntype();

    auto animals = std::vector<std::shared_ptr<Animal>>{
        std::make_shared<Dog>(),
        std::make_shared<Cat>()
    };

    for (auto const & animal: animals) {
        animal->printlntype();
    }

}

スーパー型 Animal のポインタとして呼び出された関数はもともと？部分型 Dog だったときオーバーロードされるので、１変数（クラスについての）部分型ポリモルフィズムができ、配列などそのポリモルフィズムを実現できることは分かります。

多変数で部分型ポリモルフィズムを考えるときには、（１変数での実装しかできない）メンバ関数のポリモルフィズムを使うわけにはいかないので、普通の関数として実装することになります。以下のように実装すれば（Animal 型を継承する全ての型を入れた std::variant 的なものが自動で作れるのかどうかを除いて）、

/*
g++-HEAD -std=c++2a multiple_dispatch.cpp
./a.out
*/

#include <concepts>
#include <iostream>
#include <vector>
#include <variant>
#include <memory>

struct Animal {
    virtual ~Animal() = 0;
};
Animal::~Animal() {}

struct Dog final : Animal {};

struct Cat final : Animal {};

using SubAnimal = std::variant<Dog, Cat>;

// one variable

template <std::derived_from<Animal> T>
auto printlntype(T const &) {
    std::cout << "Animal" << std::endl;
}

auto printlntype(Dog const &) {
    std::cout << "Dog" << std::endl;
}

// auto printtype(Cat const &) {
//     std::cout << "Cat" << std::endl;
// }

// two variables

template <std::derived_from<Animal> T>
auto printlntype(T const &, T const &) {
    std::cout << "Animal Animal" << std::endl;
}

template <std::derived_from<Animal> T>
auto printlntype(Dog const &, T const &) {
    std::cout << "Dog Animal" << std::endl;
}

template <std::derived_from<Animal> T>
auto printlntype(T const &, Dog const &) {
    std::cout << "Animal Dog" << std::endl;
}

auto printlntype(Dog const &, Dog const &) {
    std::cout << "Dog Dog" << std::endl;
}

int main() {
    auto dog = Dog();
    auto cat = Cat();

    // single dispatch
    printlntype(dog);
    printlntype(cat);

    // double dispatch
    printlntype(dog, dog);
    printlntype(dog, cat);
    printlntype(cat, dog);
    printlntype(cat, cat);

    auto animals = std::vector<std::shared_ptr<std::variant<Dog, Cat>>>{
        std::make_shared<SubAnimal>(SubAnimal(Dog())),
        std::make_shared<SubAnimal>(SubAnimal(Cat()))
    };

    // single dispatch
    for (auto const & animal: animals) {
        std::visit(
            [] (const auto & x) {
                printlntype(x);
            },
            *animal
        );
    }

    // double dispatch
    for (auto const & v_animal1: animals) {
        for (auto const & v_animal2: animals) {
            std::visit(
                [&] (const auto & animal1) {
                    std::visit(
                        [&] (const auto & animal2) {
                            printlntype(animal1, animal2);
                        },
                        *v_animal2
                    );
                },
                *v_animal1
            );
        }
    }
}

実行結果は

Dog
Animal
Dog Dog
Dog Animal
Animal Dog
Animal Animal
Dog
Animal
Dog Dog
Dog Animal
Animal Dog
Animal Animal

となり、多変数部分型ポリモルフィズム、つまりマルチディスパッチが実現できると思います。Julia の文章が言いたいことというのは、

1. 一般的に C++ で想定されている部分型ポリモルフィズムの実現方法がメンバ関数としてのシングルディスパッチであり、それではマルチディスパッチは実現できないということ。
2. C++ でマルチディスパッチを実現しようとすればできるが、パラメトリックポリモルフィズムが絡んだとき、つまり、配列などのコンテナの要素の型に関して部分型ポリモルフィズムをするときには、std::variant を使ったようなコードを書く必要があり、そのあたりのコードがパフォーマンス的によろしくない、もしくは自動的に subtyping された std::variant 的なものが作れないためにコードが煩雑であり、現実的でない？どちらにせよ、あまり一般的に（まだ？）使われていない。

ということなんでしょうか？

---

** 追記４ **：

Julia だと確かに以下のように if ... else .. を使ったものでもそうでなくてもコンパイルされた機械語は全く同じです。

mutable struct Dog end
mutable struct Cat end
foo(::Dog) = println("Dog")
foo(::Cat) = println("Cat")

t = 0
a = if t == 0 Dog() else Cat() end
b = Dog()

@code_native foo(a)
@code_native foo(b)

ただ C++ でも等価な機械語になるかどうかは分かりませんが、if ... else ... を使ったコードは以下のように書けますよね？

#include <iostream>
#include <variant>

struct Dog {};
struct Cat {};
using DogOrCat = std::variant<Dog, Cat>;

auto foo(Dog const &) {
    std::cout << "Dog" << std::endl;
}
auto foo(Cat const &) {
    std::cout << "Cat" << std::endl;
}

int main() {
    auto t = 0;
    auto a = [&] () {
        if (t == 0) {
            return DogOrCat(Dog());
        }
        return DogOrCat(Cat());
    } ();
    std::visit(
        [] (auto const & x) {
            foo(x);
        },
        a
    );
}

仮想関数テーブルによりシングルディスパッチが可能であることは理解しています。質問はそこではなくて、

1. 今の例のような std::variant, もしくはもっと洗練された何かを使って多重ディスパッチを実現することが可能ではないか？
2. この実装では 明示的に DogOrCat を作成しているが、Animal を Dog と Cat が継承しているときに、自動的にそれに対応する std::variant を生成できるのか？
3. この実装では長ったらしい表現（std::variant や std::visit）を書かなければいけないが、避けることはできないのか？
4. この実装のポリモルフィズムは実践的に問題となる点（パフォーマンスやバグ、表現力が不十分であるなど）を抱えているのか？
5. 上記の点が全てクリアされているならば、Julia と同じぐらいの表現力で多重ディスパッチ可能であると言えるのではないか？
6. そうであるならばもとの Julia の文章はこの方式によるポリモルフィズムを想定していない or 不適切であるということになるのではないか？

ということです。

Comments

[izmktr]

もしかしたら私の勘違いかもしれませんが、
auto dog = Dog() と auto dog = new Dog() と Animal *dog = new Dog() の違いが問題になる話じゃないでしょうか？
本来書かないといけないサンプルは後ろの2個のどちらかのように思います

Answer 1

こんにちは。

なるほど。実引数の型ではなく、実引数のインスタンスの型に応じてオーバーロードしたいのですね。

静的型付けの言語が本質的には対応しない機能です。オーバーロード解決はコンパイル時に行われるため、コンパイル時に型が決まっている必要があります。しかし、実引数のインスタンスの型は実行時に決まります。

しかし、事前に対応する型のリストを決定することで、（恐らくconceptを待たなくても）ご提示のような方法で記述することは可能ですね。
std::visitは多変数に対応していますので、これは正に多重ディスパッチと思います。

    for (auto const & v_animal1: animals) {
        for (auto const & v_animal2: animals) {
            std::visit(
                [&] (const auto & animal1, const auto & animal2) {
                    printlntype(animal1, animal2);
                },
                *v_animal1,
                *v_animal2
            );
        }
    }

st::visit呼び出しや余計なラムダ式定義も必要なので使い勝手はいまいちですが、マクロを使って誤魔化すことも可能です。

#define PRINT_INT_TYPE(A, B)\
            std::visit(\
                [] (const auto & animal1, const auto & animal2) {\
                    printlntype(animal1, animal2);\
                },\
                A,\
                B\
            )

    （中略）

    for (auto const & v_animal1: animals) {
        for (auto const & v_animal2: animals) {
            PRINT_INT_TYPE(*v_animal1, *v_animal2);
        }

なお、C++は静的型付け言語ですので、using SubAnimal = std::variant<Dog, Cat>; のような方法で対応する型を指定することが必須です。これによりコンパイル時に必要な型の組み合わせを自動的に網羅することができ、リストから外れた型を指定した時にコンパイル・エラーにすることができます。
この機能があるので、ご提示のソースのAnimalクラスやstd::derived_fromも必要ないと思います。
wandbox

そして、動的型付け言語の場合は、実行時にオーバーロード解決されるため容易に実現可能ですね。
当たり前ですが、実行時に条件分岐するので、その分遅いです。もちろん、C++の上記実装も実行時に仮想関数呼び出しを行いますので、その分のオーバーヘッドがあります。

さて、この問題は、静的型付けと動的型付けのどちらを使うかの問題と思います。
一般に動的型付け言語は静的型付け言語に比べて、コンパイル時のバグのチェック能力が低いです。（当たり前ですが、実行に決まる型をコンパイル時にチェックすることはできませんから）
ですので、大規模開発には向きません。逆に小規模開発の時は面倒な手順が少ないので便利です。

追記への回答

ちんたら書いているうちに追記がありましたので、回答してみます。

1. 今の例のような std::variant, もしくはもっと洗練された何かを使って多重ディスパッチを実現することが可能ではないか？

お使いの機能はconceptという今正に標準規格へ取り入れることが議論されている機能です。
つまり、現時点ではもっとも洗練されている方法と思います。

1. この実装では 明示的に DogOrCat を作成しているが、Animal を Dog と Cat が継承しているときに、自動的にそれに対応する std::variant を生成できるのか？

現時点では無理と思います。インクルードしているヘッダの相違でst::variantが取り込む型が変わってしまうことになるので、将来的にも対応しないような気がします。

1. この実装では長ったらしい表現（std::variant や std::visit）を書かなければいけないが、避けることはできないのか？

C++は、「長ったらしい表現」をある意味推奨しているので避けることは困難と思います。
マクロを使うことで隠すことはできるでしょうが、却って可読性を落とす危険もあるので使う時は要注意です。

1. この実装のポリモルフィズムは実践的に問題となる点（パフォーマンスやバグ、表現力が不十分であるなど）を抱えているのか？

私に分かる範囲では無いように感じます。今、標準規格を制定する人たちが深い議論を進めている筈です。彼らが採用と決定したら、安心して使っても、まず大丈夫だろうと思います。

1. 上記の点が全てクリアされているならば、Julia と同じぐらいの表現力で多重ディスパッチ可能であると言えるのではないか？

全てを完全にクリアできるとは思えないですが、多重ディスパッチ可能と言える程度にはクリアできているように感じます。

1. そうであるならばもとの Julia の文章はこの方式によるポリモルフィズムを想定していない or 不適切であるということになるのではないか？

その通りと思います。
動的型付け言語は自由度が高いですから、そのような実装は得意です。その代わり、バグ検出能力を犠牲にします。ですので、簡単にプログラムできることを取るのか、大規模プログラムを開発できることを取るのかの選択となります。どちらが優れているという話ではなく、どのようなプログラム開発に向いているのかという話です。

Answer 2

Julia の文法知らないのでC++風に書きますが
多分、Julia ではこれができるんだと思います

auto a = type == 0 ? Animal() : Dog();   // C++ではNG

foo(a);   //type == 0 ならfoo(Animal) が呼ばれる
foo(a);   //type == 1 ならfoo(Dog) が呼ばれる

C++は型があるので、最初の条件演算子で
autoを使おうとも、trueとfalseの型が違うのでエラーになります

これはnewを使ってポインタにすればうまくいきます

Animal *a = type == 0 ? new Animal() : new Dog(); // OK

foo(a);  // typeに関わらず、必ずfoo(Animal *)が呼ばれる

なぜこうなるかというと、aの型がAnimal*だからです
ここをautoにすることは出来ません

ちなみに、大問題が発生しますが、以下のような書き方ならFoo(Dog*)が呼ばれます

auto a = type == 0 ? (Dog *) new Animal() : new Dog(); // OK

foo(a);  // typeに関わらず、必ずfoo(Dog *)が呼ばれる

aの変数の中を見て、ではなくautoによって型が確定しているので、
その型を見て「コンパイル時に」どの関数を呼び出すか確定しています
ポリモルフィズムをするなら「実行時に」どの関数を呼び出す確定しないといけません

実行時にどの関数を呼び出すか決める場合、
この関数は分岐する可能性があるという表を作る必要があります
それを指定するのがvirtualというキーワードです

仮想関数テーブルで調べてもらえれば、C++ではどうやって実現していて
普通の関数に適用できない理由もわかると思います

Comments

[Paalon]

追記４にコメントを書きました。